【競プロ】ABC18D

D - バレンタインデー

ABC18Dを解きました。

制約がP、Qいずれも<=18なのでbit全探索を考えましたが、さすがにPもQも全探索すると間に合いそうにありません。（2^18=262144）

Pを固定してQの方は条件の合うものを足しこんだ上、貪欲に多い方からとれば間に合いそうです。

古い問題ですが青difを自力で解けて嬉しかったです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
 int n,m,p,q,r;
 cin>>n>>m>>p>>q>>r;
 int x[r];
 int y[r];
 int z[r];
 int maxsum=0;
 rep(i,r){
   cin>>x[i]>>y[i]>>z[i]; 
   x[i]--;
   y[i]--;
 }
 for(int bit=0;bit<(1<<n);bit++){
   map<int,int>xx;
   int sum=0;
   for(int i=0;i<n;i++){
     if(bit & (1<<i)){
       xx[i]++;
     }
   }
   if(xx.size() != p) continue;
   vector<int>yy(m,0);     
   rep(i,r){
     if(xx[x[i]]>=1) yy[y[i]]+=z[i];
   }
   sort(yy.rbegin(),yy.rend());
   rep(i,q) sum+=yy[i];
   //cout<<sum<<endl;
   maxsum=max(maxsum,sum);    
 }
 cout<<maxsum<<endl;   
 return 0;
}