Submission #339524

#	Time	Username	Problem	Language	Result	Execution time	Memory
339524		fixikmila	Bigger segments (IZhO19_segments)	C++14	37 / 100	16 ms	4204 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
struct cat{ll a,b,c;};
cat dp[3001];
int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n;
    vector<ll>a(n+1),pref(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],pref[i]=pref[i-1]+a[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(pref[i]-pref[j]>=pref[j]-pref[dp[j].a]){
                if(dp[j].b+1>dp[i].b){
                    dp[i].b=dp[j].b+1;
                    dp[i].a=j;
                    dp[i].c=pref[i]-pref[j];
                }
                else if(dp[j].b+1==dp[i].b){
                    if(pref[i]-pref[j]<dp[i].c){
                        dp[i].a=j;
                        dp[i].c=pref[i]-pref[j];
                    }
                }
            }
        }
    }
    //cout<<dp[2].a<<" "<<dp[2].b<<" "<<dp[2].c<<endl;
    //cout<<dp[4].a<<" "<<dp[4].b<<" "<<dp[4].c<<endl;
    for(int i=0;i<=n;i++)
    ans=max(ans,dp[i].b);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:23:8: warning: unused variable 't' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
segments.cpp:23:14: warning: unused variable 'm' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |              ^
segments.cpp:23:16: warning: unused variable 'k' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                ^
segments.cpp:23:20: warning: unused variable 'sum' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
segments.cpp:23:26: warning: unused variable 'l' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                          ^
segments.cpp:23:30: warning: unused variable 'r' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                              ^
segments.cpp:23:34: warning: unused variable 'x' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                  ^
segments.cpp:23:38: warning: unused variable 'y' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                      ^
segments.cpp:23:42: warning: unused variable 'z' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                          ^
segments.cpp:23:52: warning: unused variable 'mn' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~
segments.cpp:23:65: warning: unused variable 'mx' [-Wunused-variable]
   23 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~

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