Submission #246069

#	Time	Username	Problem	Language	Result	Execution time	Memory
246069		kshitij_sodani	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	57 ms	512 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
typedef int64_t llo;
#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];
llo sl(int aa,int bb){
	return (it[aa].b-it[bb].b)/(it[aa].a-it[bb].a);
}
ll dist2(int i,int 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 dist(int k,int i,int j){


	return (dist2(k,i)*dist2(k,j))/(dist2(i,j));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		ll aa,bb;
		cin>>it[i].a>>it[i].b;
		cin>>cc[i];
	}

	llo ans=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			vector<pair<ll,llo>> aa;
			vector<pair<ll,llo>> bb;
		//	cout<<i<<","<<j<<endl;
			for(int 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].a};
				v2={it[j].a-it[k].a,it[j].b-it[k].a};
				if(v1.a*v2.b-v2.b*v2.a>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());
			sort(bb.begin(),bb.end());
			llo cost=cc[i]+cc[j];
			ans=max(ans,cost);
			for(auto jj:aa){
				cost+=jj.b;
				ans=max(ans,cost);
			}
			cost=cc[i]+cc[j];
			ans=max(ans,cost);
			for(auto jj:bb){
				cost+=jj.b;
				ans=max(ans,cost);
			}
		}
	}

	cout<<ans<<endl;






	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:30:6: warning: unused variable 'aa' [-Wunused-variable]
   ll aa,bb;
      ^~
bulldozer.cpp:30:9: warning: unused variable 'bb' [-Wunused-variable]
   ll aa,bb;
         ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20