結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー | naimonon77 |
提出日時 | 2017-01-21 00:09:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 30 ms / 5,000 ms |
コード長 | 2,049 bytes |
コンパイル時間 | 2,561 ms |
コンパイル使用メモリ | 168,648 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-08-24 18:24:50 |
合計ジャッジ時間 | 2,689 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 14 ms
4,380 KB |
testcase_10 | AC | 5 ms
4,376 KB |
testcase_11 | AC | 5 ms
4,380 KB |
testcase_12 | AC | 30 ms
4,376 KB |
testcase_13 | AC | 16 ms
4,380 KB |
testcase_14 | AC | 15 ms
4,380 KB |
testcase_15 | AC | 5 ms
4,380 KB |
testcase_16 | AC | 9 ms
4,380 KB |
testcase_17 | AC | 6 ms
4,376 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define REP(i,a,b) for(int i=a;i<b;++i) #define rep(i,n) REP(i,0,n) #define chmax(a, b) (a = (a) < (b) ? (b) : (a)) #define chmin(a, b) (a = (a) > (b) ? (b) : (a)) typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define all(a) begin(a),end(a) #define ifnot(a) if(not (a)) #define dump(x) cerr << #x << " = " << (x) << endl // #define int ll #ifdef _MSC_VER const bool test = true; #else const bool test = false; #endif // int dx[] = { 0,1,0,-1 }; // int dy[] = { 1,0,-1,0 }; const int INF = 1 << 28; const ll INFL = (ll)1 << 58; ll mod = (int)1e9 + 7; const double eps = 1e-10; typedef long double Real; // return -1, 0, 1 int sgn(const Real& r) { return (r > eps) - (r < -eps); } int sgn(const Real& a, const Real &b) { return sgn(a - b); } //..................... const int MAX = (int)2e5 + 5; int N, M; vector<pair<int, int>> a[15]; int dp[1 << 16]; class BitState { public: int state; bool visited(int x) { return ((state >> x) & 1) == 1; } void add(int x) { state |= 1 << x; } int get(int x) { return ((state >> x) & 1) == 1; } int bit() { return state; } }; void solve() { cin >> N >> M; rep(i, M) { int item1, item2, score; cin >> item1 >> item2 >> score; a[item2].push_back({ item1,score }); } rep(mask, 1 << N) { rep(i, N) { BitState bs; bs.state = mask; if (bs.get(i) == 1) continue; bs.add(i); // if (mask == next_mask) cerr << "error!" << endl; int tmp = dp[mask]; rep(j, a[i].size()) { if (bs.get(a[i][j].first) == 1) { tmp += a[i][j].second; } } if (tmp > dp[bs.bit()]) dp[bs.bit()] = tmp; } // dump(mask); // print(); cerr << endl; } cout << dp[(1 << N) - 1] << endl; } signed main() { int T = 10; cout << fixed << setprecision(15); rep(i, T) { char s[MAX]; if (scanf("%s", s) == EOF) break; int n = strlen(s); for (int i = n - 1; i > -1; i--) { ungetc(s[i], stdin); } solve(); } return 0; }