Submission #681770

#	Time	Username	Problem	Language	Result	Execution time	Memory
681770		Cross_Ratio	Cigle (COI21_cigle)	C++14	100 / 100	258 ms	67396 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
int A[5005];
int B[5005][5005];
int C[5005];
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 >> A[i];
    //A[0][0] = A[0][1] = .. = A[0][N+1] = 0
    for(j=1;j<N;j++) {
        for(i=0;i<=j-1;i++) C[i] = B[i][j];
        for(i=0;i+1<=j-1;i++) C[i+1] = max(C[i+1], C[i]);
        int val = C[j-1];
        int pt = j;
        int cnt = 0;
        int sum1 = 0, sum2 = 0;
        for(int k=j+1;k<N+1;k++) {
            if(k >= j+2) sum1 += A[k-2];
            while(sum2 < sum1 && pt-1>=0) {
                sum2 += A[pt-1];
                pt--;
            }
            if(k>=j+2&&sum1==sum2) {
                cnt++;
            }
            //cout << j << ", " << k << " : " << sum1 << ' '<< sum2 << ' ' << pt << ' ' << cnt << '\n';
            if(pt>=1) val = max(val, cnt + C[pt-1]);
            B[j][k] = max(B[j][k], val);
        }
    }
    int ans = 0;
    for(i=0;i<N;i++) ans = max(ans, B[i][N]);
    cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52