Submission #685146

#	Time	Username	Problem	Language	Result	Execution time	Memory
685146		dostigator	Bigger segments (IZhO19_segments)	C++17	13 / 100	18 ms	35824 KiB

segments

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
#define Y second
#define X first
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
const ll INF=1e18;
const int inf=1e9;
const int N=2e5+505;
const int M=3e3+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

/*From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH*/

int n,a[N],dp[M][M];
ll pref[N];

ll sum(int l,int r){
	if(r==0)return 0;
	return pref[r]-pref[l-1];
}

void solve(){
	cin>>n;
	for(int i=0; i<M; ++i)for(int j=0; j<M; ++j)dp[i][j]=-1;
	for(int i=1; i<=n; ++i){
		cin>>a[i];
		pref[i]=pref[i-1]+a[i];
	}dp[0][0]=0;
	int res=0;
	for(int i=1; i<=n; ++i){
		for(int ans=1; ans<=i; ++ans){
			dp[i][ans]=dp[i-1][ans];
			int l=0,r=i-1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(dp[mid][ans-1]==-1){
					l=mid+1;
					continue;
				}
				if(sum(dp[mid][ans-1],mid)<=sum(mid+1,i)){
					dp[i][ans]=mid+1;
					res=max(res,ans);
					l=mid+1;
					continue;
				}r=mid-1;
			}
		}
	}cout<<res<<endl;
}

int main(){
	//srand(time(0));
	//freopen("hotel.in","r",stdin);
	//freopen("hotel.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1,lolol=0;
//	cin>>tt;
	while(tt--) {
		//cout<<"Case "<<++lolol<<": ";
		solve();
	}
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:71:11: warning: unused variable 'lolol' [-Wunused-variable]
   71 |  int tt=1,lolol=0;
      |           ^~~~~

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