結果

問題 No.90 品物の並び替え
ユーザー magmag
提出日時 2020-08-24 12:29:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 340 ms / 5,000 ms
コード長 1,466 bytes
コンパイル時間 2,568 ms
コンパイル使用メモリ 181,076 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-06 10:13:55
合計ジャッジ時間 2,774 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 31 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 5 ms
6,816 KB
testcase_04 AC 5 ms
6,816 KB
testcase_05 AC 31 ms
6,816 KB
testcase_06 AC 32 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 340 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
#define rep2(i, a, n) for(int i = (a); i < (n); i++)
#define rep3(n)for(;n>0;n--)
#define rep(i, n) rep2(i,0,n)

template<class T>
inline bool chmax(T& a, T b){if(a<b){a=b;return true;} return false;}

void in(){} template<typename Head,typename... Tail> void in(Head&& head,Tail&&... tail){cin>>head;in(forward<Tail>(tail)...);}

void out(){cout<<endl;} template<typename Head,typename... Tail> void out(Head&& head,Tail&&... tail){cout<<head<<" ";out(forward<Tail>(tail)...);}

template<typename T,typename U> void Printarray2(T &f,U n){for(U i=0;i<n;i++)i!=n-1 ?cout<<f[i]<<" ":cout<<f[i]<<endl;}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n,m;
  in(n,m);
  int a,b,c;
	unordered_map<int,unordered_map<int,int>>shake;
  rep3(m){
    in(a,b,c);
    shake[a][b]=c;
  }

  /*
  品物を並べた時、item1がitem2よりも前であればscore点を獲得できるという意味である。
  得点表が与えられるので、品物を適切に並び替えた時、
  獲得できる得点を最大化したい。そのときの得点を出力せよ。
  */
  int res=0,s;
  vector<int> hoge(n);
	iota(hoge.begin(),hoge.end(),0);
  //Printarray2(hoge,n);
  do{
    s=0;
    rep(i,n-1){
      rep2(j,i+1,n){
        s+=shake[hoge[i]][hoge[j]];
      }
    }
    chmax(res,s);
    //out(res,s);
  }while(next_permutation(hoge.begin(),hoge.end()));
  cout<<res<<endl;
}
0