結果
問題 |
No.1208 anti primenumber game
|
ユーザー |
|
提出日時 | 2020-08-30 15:11:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 1,828 bytes |
コンパイル時間 | 3,213 ms |
コンパイル使用メモリ | 196,456 KB |
最終ジャッジ日時 | 2025-01-13 22:32:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
#include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using tp3 = tuple<int, int, int>; //using Mat = vector<vector<ll>>; constexpr int INF = 1 << 28; constexpr ll INFL = 1ll << 60; constexpr int dh[4] = { 0,1,0,-1 }; constexpr int dw[4] = { -1,0,1,0 }; bool isin(const int H, const int W, const int h, const int w) { return 0 <= h && h < H && 0 <= w && w < W; } // ============ template finished ============ using Mat = array<array<ll, 2>, 2>; int main() { ll N, M; cin >> N >> M; vector<ll> A(N); rep(i, N)cin >> A[i]; vector<Mat> dp(N + 1); for (auto& mat : dp)rep(i, 2)rep(j, 2)mat[i][j] = INFL; rep(i, 2)rep(j, 2)dp.back()[i][j] = 0; for (int land = N - 1; land >= 0; --land) { // 1つ残っている = false { // 先手 = true dp[land][false][true] = dp[land + 1][true][false] + 1 - M; // 後手 = false dp[land][false][false] = dp[land + 1][true][true] - (1 - M); } // 全て残っている = true { // 先手 = true dp[land][true][true] = max( A[land] > 1 ? dp[land][false][false] + A[land] - 1 : -INFL, // 1つ残して取る dp[land + 1][true][false] + A[land] - M // 全部取る ); // 後手 = false dp[land][true][false] = min( A[land] > 1 ? dp[land][false][true] - (A[land] - 1) : INFL, // 1つ残して取る dp[land + 1][true][true] - (A[land] - M) // 全部取る ); } } auto value = dp.front()[true][true]; cout << (value > 0 ? "First" : "Second") << endl; return 0; }