제출 #1293354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293354		haha	Bigger segments (IZhO19_segments)	C++20	37 / 100	2 ms	580 KiB

segments

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=5e3+5;

int n;
int a[maxn];
pair<int,ll> dp[maxn];
ll sum[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dp[0]={1,0};
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i],dp[i-1]);
        ll val=2*sum[i]-dp[i].s;
        int j=lower_bound(sum+i,sum+n+1,val)-sum;
        dp[j]=max(dp[j],make_pair(dp[i].f+1,sum[i]));
    }
    cout<<dp[n].f;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27