Submission #1627217
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define INF 2000000000 #define LINF 9000000000000000000 typedef long long ll; typedef pair<int, int> P; int A, B; int a[1000], b[1000]; int dp[2003][2003]; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> A >> B; for (int i = 0; i < A; i++) cin >> a[i]; for (int i = 0; i < B; i++) cin >> b[i]; for (int i = 1; i <= A+B; i++) { for (int j = 0; j <= i; j++) { int x = j, y = i-j; if (!(x<=A&&y<=B)) continue; if ((A+B-i)%2==0) dp[x][y] = max((x>0?dp[x-1][y]+a[A-x]:0),(y>0?dp[x][y-1]+b[B-y]:0)); else dp[x][y] = min((x>0?dp[x-1][y]:INF),(y>0?dp[x][y-1]:INF)); //cout << "x,y,dp : " << x << ',' << y << ',' << dp[x][y] << endl; //for (int i = 0; i <= A; i++) { //for (int j = 0; j <= B; j++) { //cout << dp[i][j] << ' '; //} //cout << endl; //} //cout << endl; } } cout << dp[A][B] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - ゲーム |
User | moko_freedom |
Language | C++14 (GCC 5.4.1) |
Score | 3 |
Code Size | 963 Byte |
Status | AC |
Exec Time | 8 ms |
Memory | 8448 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 3 / 3 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 1 ms | 256 KB |
01 | AC | 6 ms | 8320 KB |
02 | AC | 8 ms | 8448 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |