Submission #693891

#	Time	Username	Problem	Language	Result	Execution time	Memory
693891		79brue	Cigle (COI21_cigle)	C++17	100 / 100	258 ms	67360 KiB

cigle

#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, maxVal = 0, match = 0, nextturn = 0;
            for(int e=m+1; e<=n; e++){
                if(arr[m] > sum[e] - sum[m]) continue;
                if(nextturn) match++, nextturn = 0;
                while(s>1 && sum[e] - sum[m] >= sum[m] - sum[s-2]){
                    s--;
                    maxVal = max(maxVal, DP[s][m] + match);
                }
                if(sum[e] - sum[m] == sum[m] - sum[s-1]) nextturn = 1;
                DP[m+1][e] = max(DP[m+1][e], maxVal);
            }
        }
        /// 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;
            for(int e=m+1; e<=n; e++){
                if(nextturn) match++, nextturn = 0;
                while(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(s == 1 && sum[e] - sum[m] >= sum[m] - sum[s-1]) break;
                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 (stderr)

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: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52