結果

問題 No.90 品物の並び替え
コンテスト
ユーザー mag
提出日時 2020-08-24 12:29:57
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 340 ms / 5,000 ms
コード長 1,466 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,568 ms
コンパイル使用メモリ 181,076 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-06 10:13:55
合計ジャッジ時間 2,774 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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