oj.uz

Submission #1003552

# Submission time Handle Problem Language Result Execution time Memory
1003552 2024-06-20T12:48:52 Z teesla Cigle (COI21_cigle) C++14
0 / 100
 23 ms 1444 KB 
#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 somaPedaco = sum[r-1] - sum[l-1];
        if(somaPedaco >= sum[l-1]) continue;
        int qnt = 0;
    
        int cima = l, baixo = l-1;
        int SumCima = tam[l];
        int SumBaixo = tam[l-1];
    
        while(cima < r){
    
    
            if(SumCima == SumBaixo) {
                qnt++;
                baixo--;
                cima++;
                SumBaixo+= tam[baixo];
                SumCima+= tam[cima];
                dp[l][r] = min(dp[l][r], dp[min(1, baixo)][l-1] + qnt);
            }
            else if(SumCima > SumBaixo) {baixo--; SumBaixo+= tam[baixo]; dp[l][r] = min(dp[l][r], dp[min(1, baixo)][l-1] + qnt);}
            else{ cima++; SumCima += tam[cima];}
        }
    
    
        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]);
    }
    cout << maior << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1444 KB Output is correct
2 Correct 19 ms 1372 KB Output is correct
3 Correct 20 ms 1372 KB Output is correct
4 Correct 19 ms 1368 KB Output is correct
5 Correct 20 ms 1372 KB Output is correct
6 Incorrect 19 ms 1372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -