Submission #672058

#	Time	Username	Problem	Language	Result	Execution time	Memory
672058		Username4132	Cigle (COI21_cigle)	C++14	100 / 100	486 ms	134388 KiB

cigle

#include<iostream>
#include "stdio.h"
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=(int)s; --i)

const int MAXN = 5010;
int n, mx, tmp, sum[MAXN], value[MAXN][MAXN], dp[MAXN][MAXN];

int main(){
    cin >> n;
    forn(i, n) scanf("%d", &tmp), sum[i+1] = sum[i] + tmp;

    dforn(i, n) dforsn(j, i+2, n){
        int pos = lower_bound(sum, sum+n, 2*sum[j]-sum[i+1]) - sum;
        value[i][j] = value[i+1][j]+(pos<n && sum[pos]==2*sum[j]-sum[i+1]);
        dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
        if(pos<n) dp[i][j] = max(dp[i][j], value[i][j] + dp[j][pos+1]);
    }

    forn(i, n) mx = max(mx, dp[0][i]);
    printf("%d\n", mx);
}

Compilation message (stderr)

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

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