Submission #671672

#	Time	Username	Problem	Language	Result	Execution time	Memory
671672		ReLice	Divide and conquer (IZhO14_divide)	C++17	100 / 100	66 ms	51148 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define ld long double
#define int long long
#define pb push_back
#define sz size()
#define fr first
#define sc second
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e7;
vector <ll> x(N),g(N),a(N),pref(N),pref2(N);
map<ll,vector<ll>> mp ;
void solve(){
    ll n,i,mx=-1,l,r,k;
    cin>>n;
	ll suf[n];
	for(i=0;i<n;i++) cin>>x[i]>>g[i]>>a[i];
	pref[0]=a[0];
	pref2[0]=g[0];
	for (i=1;i<n;i++){
		pref[i]=pref[i-1];
		pref[i]+=a[i];
		pref2[i]=pref2[i-1]+g[i];
		mp[pref[i]].pb(i);
	}
	suf[n-1]=pref[n-1]-x[n-1];
	for(ll i=n-2;i>=0;i--) suf[i] = max(suf[i + 1], pref[i] - x[i]);
	for(ll i=0;i<n;i++){
        k=-x[i];
		if(i>0)k+=pref[i-1];
		l=i;
        r=n;
		while(l+1<r){
			ll mid=(l+r)>>1;
			if(suf[mid]>=k) l=mid;
			else r=mid;
		}
		mx=max(mx,pref2[l]-pref2[i]+g[i]);
	}
	cout<<mx<<endl;
}
signed main(){
    //fre("divide");
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
}

Compilation message (stderr)

divide.cpp: In function 'void fre(std::string)':
divide.cpp:12:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:12:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52