Submission #634453

#	Time	Username	Problem	Language	Result	Execution time	Memory
634453		Cross_Ratio	Gorgeous Pill (FXCUP3_gorgeous)	C++14	12 / 100	1586 ms	7736 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+len+1<=N) {
                    DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
                }
                if(j >= 1) {
                    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: 12 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49