Submission #634456

#	Time	Username	Problem	Language	Result	Execution time	Memory
634456		Cross_Ratio	Gorgeous Pill (FXCUP3_gorgeous)	C++14	0 / 100	0 ms	340 KiB

gorgeous

#include <bits/stdc++.h>
using namespace std;
int C[300005];
long long int D[300005];
long long int DP[1005][1005];
const long long int INF = 1e18;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> C[i];
    for(i=0;i<N;i++) cin >> D[i];
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            for(int k = 0; k <= N; k++) DP[j][k] = -INF;
        }
        DP[i][i+1] = (C[i]==1 ? D[i] : 0);
        for(int len = 1; len < N; len++) {
            for(j=0;j+len<=N;j++) {
                if(j==0) {
                    DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                }
                else if(j+len==N) {
                    DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
                }
                else {
                    if(C[j+len]!=len+1 && C[j-1] != len+1) {
                        DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                        DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
                    }
                    else if(C[j+len]==len+1 && C[j-1] == len+1) {
                        if(D[j+len] > D[j-1]) DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                        else DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
                    }
                    else {
                        if(C[j+len]==len+1) DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                        else DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
                    }
                }
            }
        }
        cout << DP[0][N] << ' ';
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49