Submission #1248190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248190		kokokai	Bigger segments (IZhO19_segments)	C++20	100 / 100	56 ms	13896 KiB

segments

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 5e5+4;
int a[N];
pair<ll,ll> dp[N];
ll pre[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    if(fopen("text.inp","r")){
        freopen("text.inp","r",stdin);
        //freopen("text.out","w",stdout);
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    reverse(a+1,a+1+n);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    //dp[i][j]=min phan cuoi khi chon i->n va used j
    for(int i=1;i<=n;i++){
        dp[i]={9e17,0};
    }
    dp[n+1]={0,0};
    for(int i=n+1;i>=1;i--){
        if(i<=n){
            if(dp[i].fi > dp[i+1].fi+a[i]){
                dp[i].fi=dp[i+1].fi+a[i];
                dp[i].se=dp[i+1].se;
            }else if(dp[i].fi == dp[i+1].fi+a[i]){
                dp[i].se=max(dp[i].se,dp[i+1].se);
            }
        }
        ll sum=dp[i].fi;
        int l=0,r=i-2,an=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pre[i-1]-pre[mid] >= sum){
                an=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        if(an == -1) continue;
        ll nsum=pre[i-1]-pre[an];
        an++;
        if(dp[an].fi == nsum){
            dp[an].se=max(dp[an].se,dp[i].se+1);
        }else if(dp[an].fi > nsum){
            dp[an].fi=nsum;
            dp[an].se=dp[i].se+1;
        }
    }
    for(int i=n+1;i>=1;i--){
        //cerr<<i<<' '<<dp[i].fi<<' '<<dp[i].se<<'\n';
    }
    int ans=dp[1].se;
    cout<<ans<<'\n';

}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("text.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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