結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
|
提出日時 | 2016-09-27 01:07:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 5,000 ms |
コード長 | 1,995 bytes |
コンパイル時間 | 1,960 ms |
コンパイル使用メモリ | 181,828 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-11-21 07:04:33 |
合計ジャッジ時間 | 2,978 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef unsigned int uint;typedef long long int ll;typedef unsigned long long int ull;#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}#define ALL(v) (v).begin(),(v).end()#define BIGINT 0x7FFFFFFF#define E107 1000000007void printbit(int u){if(u==0)cout<<0;else{int s=0,k=0;for(;0<u;u>>=1,k++)s=(s<<1)|(u&1);for(;0<k--;s>>=1)cout<<(s&1);}}#define TIME chrono::system_clock::now#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())template<typename T1,typename T2>ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;}int m,n;unordered_map<int,int> data[20];int calc(int bit,int pos){static map<pair<int,int>,int> memo;int b,i;pair<int,int> key(bit,pos);int score=0,high=0;if (memo.count(key)) return memo[key];// posを置くことによって得られる得点for (i=0,b=bit;i<n&&0<b;i++,b>>=1){if (b&1){if (data[i].count(pos))score+=data[i][pos];}}bit|=1<<(pos);// 次にi,...を置くことによって得られる得点for (i=0,b=bit;i<n;i++,b>>=1){if (!(b&1)){high=max(high,calc(bit,i));}}return memo[key] = high+score;}int main(){int i,j,k,l;cin>>n>>m;for (i=0;i<m;i++){scanf("%d%d%d",&j,&k,&l);data[j][k] = l;}int score=0;for (i=0;i<n;i++){score = max(score,calc(0,i));}cout<<score<<endl;return 0;}