Submission #1024554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024554		MarwenElarbi	Cigle (COI21_cigle)	C++17	100 / 100	129 ms	196696 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define ll long long
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5005;
long long dp[nax][nax];
int mx[nax];
signed main(){
    iostream::sync_with_stdio(false);
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    int tab[n];
    for (int i = 1; i <= n; ++i)
    {
        cin>>tab[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i-1; ++j)
        {
            mx[j]=dp[j][i-1];
        }
        for (int j = 1; j <= i-1; ++j)
        {
            mx[j]=max(mx[j],mx[j-1]);
        }
        int a=0,b=0,x=0,pct=0,pos=i-1;
        for (int j = i; j <= n; ++j)
        {
            b+=tab[j];
            while(pos>0&&a<b) {
                a+=tab[pos];
                pos--;
            }
            if (pos>0&& a==b) {
                pct++;
                x=max(x,mx[pos]+pct);
            }
            dp[i][j+1]=x;
        }
    }
    ll res=0;
    for (int i = 1; i <= n; ++i)
    {
        res=max(res,dp[i][n]);
    }
    cout <<res<<endl;
}

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