Submission #5447334
Source Code Expand
#include<bits/stdc++.h> using namespace std; int A,B; vector<int> a, b; int dp[1001][1001]; int turn1(int asize, int bsize); int turn2(int asize, int bsize); signed main() { cin >> A >> B; a.reserve(A); b.reserve(B); for(int i=0; i<A; i++) cin >> a[i]; for(int i=0; i<B; i++) cin >> b[i]; std::fill( dp[0], dp[1000], -1 ); cout << turn1(A,B) << endl; return 0; } int turn1(int asize, int bsize) { if(dp[asize][bsize] != -1) return dp[asize][bsize]; if(asize ==0 && bsize == 0) return 0; if(asize == 0) { int t = b[B-bsize] + turn2(asize, bsize-1); dp[asize][bsize] = t; return t; } if(bsize == 0) { int t = a[A-asize] + turn2(asize-1, bsize); dp[asize][bsize] = t; return t; } int t = max(a[A-asize] + turn2(asize-1, bsize), b[B-bsize] + turn2(asize, bsize-1)); dp[asize][bsize] = t; return t; } int turn2(int asize, int bsize) { if(dp[asize][bsize] != -1) return dp[asize][bsize]; if(asize ==0 && bsize == 0) return 0; if(asize == 0) { int t = turn1(asize, bsize-1); dp[asize][bsize] = t; return t; } if(bsize == 0) { int t = turn1(asize-1, bsize); dp[asize][bsize] = t; return t; } int t = min(turn1(asize-1, bsize), turn1(asize, bsize-1)); dp[asize][bsize] = t; return t; }
Submission Info
Submission Time | |
---|---|
Task | B - ゲーム |
User | s4port |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1393 Byte |
Status | WA |
Exec Time | 13 ms |
Memory | 4224 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 3 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 3 ms | 4096 KB |
01 | AC | 13 ms | 4224 KB |
02 | WA | 4 ms | 4224 KB |
90 | AC | 3 ms | 4096 KB |
91 | AC | 3 ms | 4096 KB |