分组背包+四位

https://ac.nowcoder.com/acm/contest/99784/E

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define INF 2e9
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<ll, ll>;
const double PI = acos(-1);
const int N = 1e3+ 10;
const int mod = 1e9 + 7;
int n,C,m;
bool st[N];
vector<array<ll,3>> v1[N];
vector<pii> a;
ll f[N][5];
void solve() {
	cin>>n>>C>>m;
	a.resize(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
	}
	int cnt=1;
	for(int i=1;i<=m;i++){
		ll x,y,w;cin>>x>>y>>w;
		v1[cnt].push_back({a[x].first,a[x].second,1});
		v1[cnt].push_back({a[y].first,a[y].second,1});
		v1[cnt].push_back({a[x].first+a[y].first,a[x].second+a[y].second+w,2});
		cnt++;
		st[x]=st[y]=1;
	}
	for(int i=1;i<=n;i++){
		if(!st[i]){
			v1[cnt++].push_back({a[i].first,a[i].second,1});
		}
	}
	ll ans=0;
	for(int i=1;i<cnt;i++){
		for(int j=C;j>=0;j--){
			for(int k=4;k>=1;k--){
				for(int p=v1[i].size()-1;p>=0;p--){
					if(k-v1[i][p][2]>=0&&j-v1[i][p][0]>=0)
					f[j][k]=max(f[j][k],f[j-v1[i][p][0]][k-v1[i][p][2]]+v1[i][p][1]);
					ans=max(ans,f[j][k]);
				}
			}
		}
	}
	cout<<ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
//	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}