제출 #1003535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003535		teesla	Cigle (COI21_cigle)	C++14	0 / 100	30 ms	1372 KiB

cigle

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

int main(){

    int n; cin >> n;
    vector<int> tam(n+1, 0);
    vector<int> sum(n+1, 0);

    for(int i=1; i<=n; i++) cin >> tam[i];
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + tam[i];

    vector<vector<int>> dp(n+1, vector<int> (n+1,0));
    int maior = 0;

    for(int l = 1; l<= n; l++) for(int r = l; r<=n; r++){

        int qnt = 0;

        int cima = l, baixo = l-1;
        int SumCima = tam[l];
        int SumBaixo = tam[l-1];
        dp[l][r] = max(dp[l][r], dp[l-1][l-1]);

        while(cima < r and baixo >0){
            if(SumCima == SumBaixo) {
                qnt++;
                baixo--;
                cima++;
                SumBaixo+= tam[baixo];
                SumCima+= tam[cima];
                dp[l][r] = max(dp[l][r], dp[baixo][l-1] + qnt);
            }
            else if(SumCima > SumBaixo) {baixo--; SumBaixo+= tam[baixo]; dp[l][r] = max(dp[l][r], dp[baixo][l-1] + qnt);}
            else{ cima++; SumCima += tam[cima]; dp[l][r] = max(dp[l][r], dp[baixo][l-1] + qnt);}
        }
        


        //cout << l << ' '<< r << ' '<< qnt << endl;

        for(int oo = baixo; oo>=1; oo--){
            dp[l][r] = max(dp[l][r], dp[oo][l-1] + qnt);
        }
        maior = max(maior, dp[l][r]);
    }
    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=n; j++) cout << dp[i][j] << ' ';
    //     cout << endl;
    // }
    cout << maior << endl;
}

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