Submission #693847

#	Time	Username	Problem	Language	Result	Execution time	Memory
693847		79brue	Cigle (COI21_cigle)	C++17	48 / 100	1083 ms	11124 KiB

cigle

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[5002];
int DP[5002][5002];
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int m=1; m<n; m++){
        for(int s=1; s<=m; s++){
            int tmp = m, off = arr[m], ret = DP[s][m];
            bool ended = 0;
            for(int e=m+1; e<n; e++){
                int v = arr[e];
                while(!ended && off < v){
                    v -= off;
                    off = arr[--tmp];
                    if(tmp <= s){
                        ended = 1;
                        break;
                    }
                }
                if(!ended){
                    if(off == v) ret++, off = 0;
                    else off -= v;
                }
                DP[m+1][e+1] = max(DP[m+1][e+1], ret);
            }
        }
    }
//    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 (stderr)

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

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