Submission #693872

#	Time	Username	Problem	Language	Result	Execution time	Memory
693872		79brue	Cigle (COI21_cigle)	C++17	0 / 100	4 ms	2772 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; /// 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 (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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52