Typical DP Contest

Submission #5412790

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int lli;
typedef pair<int, int> P;


// dp[i][j]: ai、bj まで使った状態での価値の最大値
lli dp[1001][1001];
int main() {
    int A, B;
    cin >> A >> B;
    lli a[A];
    lli b[B];
    REP(i, A) {
        cin >> a[i];
    }
    REP(i, B) {
        cin >> b[i];
    }

    lli ans = 1;
    for(int i=0;i<=A;i++) {
        for (int j=0; j<B; j++) {
            // 相手のターン
            if ((i + j) % 2 == 1) {
                // a を使う
                if (i < A)
                    dp[i+1][j] = dp[i][j];
                // b を使う
                dp[i][j+1] = dp[i][j];
            }
            else {
                // a を使う
                if (i < A)
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a[i]);
                // b を使う
                dp[i][j+1] = max(dp[i][j+1], dp[i][j] + b[j]);
                //if (i == 0 && j == 1) {
                //    cout << "dp["<<i<<"]["<<j<<"]: " << dp[i][j]<<endl;
                //    cout << "dp["<<i<<"]["<<j+1<<"]: " << dp[i][j+1]<<endl;
                //    cout << "dp["<<i+1<<"]["<<j<<"]: " << dp[i+1][j]<<endl;
                //}
            }
        }
    }

    //for(int i=0;i<=A;i++) {
    //    for (int j=0; j<=B; j++) {
    //        cout << "dp["<<i<<"]["<<j<<"]: " << dp[i][j]<<endl;
    //    }
    //}


    cout << dp[A][B] << endl;
}

Submission

Task問題 B - ゲーム
User nameユーザ名 longtime
Created time投稿日時
Language言語 C++ (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1527 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 3 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 WA
01 WA
02 WA
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB