oj.uz

Submission #246115

# Submission time Handle Problem Language Result Execution time Memory
246115 2020-07-08T07:38:53 Z kshitij_sodani Bulldozer (JOI17_bulldozer) C++14
5 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
typedef long double ll;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
pair<ll,ll> it[2001];
llo cc[2001];
/*ll sl(llo aa,llo bb){
	return (it[aa].b-it[bb].b)/(it[aa].a-it[bb].a);
}*/
ll dist2(llo i,llo j){

	return (it[i].a-it[j].a)*(it[i].a-it[j].a)+(it[i].b-it[j].b)*(it[i].b-it[j].b);
}
/*ll sect(pair<ll,ll> aa,pair<ll,ll> bb,pair<ll,ll> cc,pair<ll,ll> dd){

	


}
*/
ll dist(llo k,llo i,llo j){
	//ll xx=(dist2(i,k)*dist2(i,k)-dist2(j,k)*dist2(j,k)+dist2(i,j)*dist2(i,j))/((ll)2*dist2(i,j));
	ll xx=(dist2(i,k)-dist2(j,k)+dist2(i,j))/((ll)2*sqrt(dist2(i,j)));
	///((ll)2*dist2(i,j));

//	cout<<dist2(i,k)<<","<<dist2(j,k)<<","<<dist2(i,j)<<"<"<<xx<<endl;
	return dist2(i,k)-xx*xx;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n;
	llo ans=0;
	vector<pair<ll,llo>> ac;
	for(llo i=0;i<n;i++){

		cin>>it[i].a>>it[i].b;
		cin>>cc[i];
		ans=max(ans,cc[i]);
		ac.pb({it[i].a,cc[i]});
	}
	llo kk=0;
	sort(ac.begin(),ac.end());
	for(int i=0;i<n;i++){
		kk=max((llo)0,kk+ac[i].b);
		ans=max(ans,kk);
	}
	cout<<ans<<endl;
	return 0;

	
	
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			if(j==i){
				continue;
			}
			vector<pair<ll,llo>> aa;
			vector<pair<ll,llo>> bb;
		//	cout<<i<<","<<j<<endl;
			for(llo k=0;k<n;k++){
				if(k==i or k==j){
					continue;
				}
				pair<ll,ll> v1;
				pair<ll,ll> v2;
				v1={it[j].a-it[i].a,it[j].b-it[i].b};
				v2={it[j].a-it[k].a,it[j].b-it[k].b};
				if(v1.a*v2.b-v2.b*v2.a>(ll)0){
					aa.pb({dist(k,i,j),cc[k]});
			//		cout<<dist(k,i,j)<<"::"<<k<<endl;
				}
				else{
					bb.pb({dist(k,i,j),cc[k]});
				}
			}
			sort(aa.begin(),aa.end());
			reverse(aa.begin(),aa.end());

			sort(bb.begin(),bb.end());
			aa.pb({0,cc[i]+cc[j]});
			for(auto j:bb){
				aa.pb(j);
			}
			llo cost=0;
			ans=max(ans,cost);
			for(auto jj:aa){
				cost+=jj.b;
				cost=max(cost,(llo)0);
				ans=max(ans,cost);
			}

			
		}
	}

	cout<<ans<<endl;
	/*it[10]={0,0};
	it[11]={3,0};
	it[12]={1.5,2};*/
	//cout<<dist(12,10,11)<<endl;






	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -