結果
問題 | No.1267 Stop and Coin Game |
ユーザー | hamray |
提出日時 | 2020-11-11 17:52:43 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 2,351 bytes |
コンパイル時間 | 2,052 ms |
コンパイル使用メモリ | 149,152 KB |
実行使用メモリ | 15,772 KB |
最終ジャッジ日時 | 2023-09-30 00:39:06 |
合計ジャッジ時間 | 4,990 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,576 KB |
testcase_01 | AC | 2 ms
5,556 KB |
testcase_02 | AC | 2 ms
5,420 KB |
testcase_03 | AC | 2 ms
5,416 KB |
testcase_04 | AC | 2 ms
5,468 KB |
testcase_05 | AC | 2 ms
5,488 KB |
testcase_06 | AC | 2 ms
5,424 KB |
testcase_07 | AC | 2 ms
5,536 KB |
testcase_08 | AC | 10 ms
6,560 KB |
testcase_09 | AC | 2 ms
5,488 KB |
testcase_10 | AC | 86 ms
15,652 KB |
testcase_11 | AC | 22 ms
9,636 KB |
testcase_12 | AC | 5 ms
5,776 KB |
testcase_13 | AC | 2 ms
5,452 KB |
testcase_14 | AC | 2 ms
5,704 KB |
testcase_15 | AC | 1 ms
5,448 KB |
testcase_16 | AC | 90 ms
15,704 KB |
testcase_17 | AC | 2 ms
5,528 KB |
testcase_18 | AC | 3 ms
5,608 KB |
testcase_19 | AC | 2 ms
5,428 KB |
testcase_20 | AC | 2 ms
5,692 KB |
testcase_21 | AC | 2 ms
5,488 KB |
testcase_22 | AC | 2 ms
5,500 KB |
testcase_23 | AC | 2 ms
5,476 KB |
testcase_24 | AC | 37 ms
13,660 KB |
testcase_25 | AC | 59 ms
13,608 KB |
testcase_26 | AC | 2 ms
5,456 KB |
testcase_27 | AC | 4 ms
5,720 KB |
testcase_28 | AC | 2 ms
5,576 KB |
testcase_29 | AC | 2 ms
5,568 KB |
testcase_30 | AC | 70 ms
15,724 KB |
testcase_31 | AC | 2 ms
5,496 KB |
testcase_32 | AC | 11 ms
6,488 KB |
testcase_33 | AC | 36 ms
13,592 KB |
testcase_34 | AC | 56 ms
13,644 KB |
testcase_35 | AC | 70 ms
15,664 KB |
testcase_36 | AC | 2 ms
5,484 KB |
testcase_37 | AC | 15 ms
6,644 KB |
testcase_38 | AC | 77 ms
15,664 KB |
testcase_39 | AC | 7 ms
5,932 KB |
testcase_40 | AC | 3 ms
5,664 KB |
testcase_41 | AC | 7 ms
5,960 KB |
testcase_42 | AC | 2 ms
5,504 KB |
testcase_43 | AC | 10 ms
6,440 KB |
testcase_44 | AC | 70 ms
15,772 KB |
testcase_45 | AC | 2 ms
5,412 KB |
testcase_46 | AC | 2 ms
5,424 KB |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/all> //using namespace atcoder; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") const double pi = 3.141592653589793238462643383279; using namespace std; //typedef //------------------------------------------ typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> PII; typedef pair<long long, long long> PLL; typedef pair<int, PII> TIII; typedef long long LL; typedef unsigned long long ULL; typedef vector<LL> VLL; typedef vector<VLL> VVLL; //container util //------------------------------------------ #define ALL(a) (a).begin(), (a).endf() #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) #define SQ(a) ((a) * (a)) #define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).endf(); ++i) #define EXIST(s, e) ((s).find(e) != (s).endf()) #define SORT(c) sort((c).begin(), (c).endf()) //repetition //------------------------------------------ #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define REP(i, n) FOR(i, 0, n) #define MOD 1000000007 #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) const double EPS = 1e-4, PI = acos(-1); //ここから編集 typedef string::const_iterator State; ll N, V; vector<ll> a; int dp[1<<20]; ll sum[(1<<20)]; bool rec(int mask, int turn){ if(sum[mask] > V){ return 1; } if(dp[mask] != -1) return dp[mask]; for(int i=0; i<N; i++){ if(mask >> i & 1) continue; if(!rec(mask | (1<<i), turn^1)) return dp[mask] = 1; } return dp[mask] = 0; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cin >> N >> V; a.resize(N); REP(i,1<<N) dp[i] = -1; REP(i,N) cin >> a[i]; REP(i,(1<<N)) REP(j,N) if(i>>j&1) sum[i]+=a[j]; if(accumulate(all(a), 0LL) <= V){ cout << "Draw" << endl; }else{ if(rec(0, 0)) cout << "First" << endl; else cout << "Second" << endl; } return 0; }