oj.uz

Submission #693872

# Submission time Handle Problem Language Result Execution time Memory
693872 2023-02-03T10:55:41 Z 79brue Cigle (COI21_cigle) C++17
0 / 100
 4 ms 2772 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[5002], sum[5002];
int DP[5002][5002];
int maxV[5002];
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]), sum[i] = sum[i-1] + arr[i];
    for(int m=1; m<n; m++){
        /// Case 1. 아래가 더 짧거나 같다
        {
            int s = m; /// s ~ m 구간을 볼 것임
            int maxScore = 0, match = 0;
            for(int e=m+1; e<=n; e++){
                if(sum[e-1] - sum[m] < arr[m]) continue;
                if(e>m && s!=1 && sum[e-1] - sum[m] == sum[m] - sum[s-1] && sum[e] - sum[m] >= sum[m] - sum[s-2])
                    match++, s--;
                maxScore = max(maxScore, DP[s][m] + match);
                while(s > 1 && sum[m] - sum[s-2] <= sum[e] - sum[m]){
                    s--;
                    maxScore = max(maxScore, DP[s][m] + match);
                }
                DP[m+1][e] = max(DP[m+1][e], maxScore);
            }
        }
        /// Case 2. 위가 더 짧다
        {
            for(int i=1; i<=m; i++) maxV[i] = max(maxV[i-1], DP[i][m]);
            int s = m, match = 0, nextturn = 0, ended = 0;
            for(int e=m+1; e<=n; e++){
                if(nextturn) match++, nextturn = 0;
                while(!ended && s > 1 && sum[e] - sum[m] >= sum[m] - sum[s-1]){
                    if(sum[e] - sum[m] == sum[m] - sum[s-1]) nextturn = 1;
                    s--;
                }
                if(!ended && s == 1 && sum[e] - sum[m] >= sum[m] - sum[s-1]) ended = 1;
                DP[m+1][e] = max(DP[m+1][e], match + maxV[s]);
            }
        }
    }
//    for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) printf("%d %d: %d\n", i, j, DP[i][j]);
    for(int i=1; i<=n; i++) ans = max(ans, DP[i][n]);
    printf("%d", ans);
}

Compilation message

cigle.cpp: In function 'int main()':
cigle.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
cigle.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]), sum[i] = sum[i-1] + arr[i];
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 52.0

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