oj.uz

Submission #168419

# Submission time Handle Problem Language Result Execution time Memory
168419 2019-12-13T03:27:53 Z IldarKA Bigger segments (IZhO19_segments) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;
int n;
long long a[3001];
int dp[3001][3001];
int main(){
    cin >> n;
    if(n > 3000){
        assert(0);
    }
    for(int i = 1;  i <= n; i++){
        cin >> a[i];
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; i++){
        int po = i - 1;
        long long sum = 0;
        long long sum2 = 0;
        int mx = 0;
        for(int j = i; j <= n; j++){
            sum += a[j];
            while(po > 0 && sum2 + a[po] <= sum){
                sum2 += a[po];
                mx = max(dp[po][i - 1], mx);
                po--;
            }
            if(po < i - 1){
                dp[i][j] = max(mx + 1, dp[i][j]);
            }
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++){
        mx = max(dp[i][n], mx);
    }
    cout << mx;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 36.0

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

Subtask #5
0 / 27.0

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