Submission #1268471

#TimeUsernameProblemLanguageResultExecution timeMemory
1268471MMihalevBulldozer (JOI17_bulldozer)C++20
5 / 100
31 ms328 KiB
#include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; const int MAX_N=2e2+2; const long long INF=(1LL<<62); int n; long long x[MAX_N]; long long y[MAX_N]; long long cost[MAX_N]; bool allzero=1; vector<pair<long long,long long>>order; long long distance(long long A,long long B,long long x0,long long y0) { return A*x0+B*y0; } long long solvefor() { long long curbest=0; for(int i=0;i<order.size();i++) { long long cur=0; for(int j=i;j<order.size();j++) { cur+=order[j].second; curbest=max(curbest,cur); } } return curbest; } vector<pair<long long,long long>>norder; void normalize() { norder.clear(); norder.push_back(order[0]); for(int i=1;i<order.size();i++) { if(order[i].first==norder.back().first) { norder.back().second+=order[i].second; continue; } norder.push_back(order[i]); } swap(order,norder); } void solve() { for(int i=1;i<=n;i++) { order.push_back({x[i],cost[i]}); } sort(order.begin(),order.end()); normalize(); long long ans=max(0LL,solvefor()); if(!allzero) { for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { long long A=y[i]-y[j]; long long B=x[j]-x[i]; //long long C=-A*x[i]-B*y[i]; long long gc=__gcd(A,B); //gc=__gcd(gc,C); A/=gc;B/=gc;//C/=gc; order.clear(); for(int idx=1;idx<=n;idx++) { order.push_back({distance(A,B,x[idx],y[idx]),cost[idx]}); } sort(order.begin(),order.end()); normalize(); ans=max(ans,solvefor()); } } } cout<<ans<<"\n"; } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) { cin>>x[i]>>y[i]>>cost[i]; if(y[i]!=0)allzero=0; } solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...