oj.uz

Submission #38712

# Submission time Handle Problem Language Result Execution time Memory
38712 2018-01-06T09:51:04 Z khohko Divide and conquer (IZhO14_divide) C++14
100 / 100
 243 ms 10824 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define N ((ll)(2e5+100))
#define MAX ((ll)(1e16+100))
#define ARRS ((ll)(2e5+100))
#define MOD ((ll)(1e9+7))
#define pb push_back

ll n;
struct va{
	ll x,g,c;
};
va a[ARRS];
ll pas=0;
void slv(ll l,ll r){
	if(l>=r)return;
	if(l==r-1){
		pas=max(a[l].g,pas);
		return;
	}
	ll m=(l+r)>>1;
	vector<pair<ll,ll> > v;
	vector<pair<ll,ll> > g;
	ll s=0,sg=0;
	for(int i=m+1; i<r; i++){
		s+=a[i].c;
		sg+=a[i].g;
		v.pb({s-(a[i].x-a[m].x),sg});
	}
	v.pb({0,0});
	s=sg=0;
	for(int i=m; i>=l; i--){
		s+=a[i].c;
		sg+=a[i].g;
		g.pb({s-(a[m].x-a[i].x),sg});
	}
	sort(v.begin(),v.end());
	sort(g.begin(),g.end());
	reverse(g.begin(),g.end());
	//cout<<m<<endl;
	//for(auto x:v){
		//cout<<x.fr<<"  "<<x.sc<<endl;
	//}
	//cout<<endl;
	//for(auto x:g){
		//cout<<x.fr<<"  "<<x.sc<<endl;
	//}
	//cout<<endl;
	ll mx=-MAX;
	ll ps=0;
	for(int i=0,j=0; i<v.size(); i++){
		while(j!=g.size()&&v[i].fr+g[j].fr>=0)mx=max(mx,g[j].sc),j++;
		//cout<<i<<" "<<j<<" "<<mx<<endl; 
		ps=max(ps,mx+v[i].sc);
	}
	pas=max(pas,ps);
	slv(l,m);
	slv(m+1,r);
	return;
}


int main(){
	//freopen("divide.in","r",stdin);
	//freopen("divide.out","w+",stdout);
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i].x>>a[i].g>>a[i].c;
	}
	slv(0,n);
	cout<<pas;
}

Compilation message

divide.cpp: In function 'void slv(long long int, long long int)':
divide.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0; i<v.size(); i++){
                    ^
divide.cpp:56:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j!=g.size()&&v[i].fr+g[j].fr>=0)mx=max(mx,g[j].sc),j++;
          ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6708 KB Output is correct
2 Correct 0 ms 6708 KB Output is correct
3 Correct 0 ms 6708 KB Output is correct
4 Correct 0 ms 6708 KB Output is correct
5 Correct 0 ms 6708 KB Output is correct
6 Correct 0 ms 6708 KB Output is correct
7 Correct 0 ms 6708 KB Output is correct
8 Correct 0 ms 6708 KB Output is correct
9 Correct 0 ms 6708 KB Output is correct
10 Correct 0 ms 6708 KB Output is correct
11 Correct 0 ms 6708 KB Output is correct
12 Correct 0 ms 6708 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6708 KB Output is correct
2 Correct 0 ms 6708 KB Output is correct
3 Correct 0 ms 6708 KB Output is correct
4 Correct 0 ms 6708 KB Output is correct
5 Correct 0 ms 6708 KB Output is correct
6 Correct 0 ms 6840 KB Output is correct
7 Correct 0 ms 6708 KB Output is correct
8 Correct 0 ms 6708 KB Output is correct
9 Correct 0 ms 6840 KB Output is correct
10 Correct 0 ms 6840 KB Output is correct
11 Correct 9 ms 7008 KB Output is correct
12 Correct 9 ms 7008 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7008 KB Output is correct
2 Correct 13 ms 7240 KB Output is correct
3 Correct 16 ms 7240 KB Output is correct
4 Correct 106 ms 8776 KB Output is correct
5 Correct 126 ms 8776 KB Output is correct
6 Correct 243 ms 10824 KB Output is correct
7 Correct 186 ms 10824 KB Output is correct
8 Correct 213 ms 10824 KB Output is correct
9 Correct 229 ms 10824 KB Output is correct
10 Correct 176 ms 10824 KB Output is correct
11 Correct 236 ms 10824 KB Output is correct
12 Correct 243 ms 10824 KB Output is correct