제출 #1077847

#제출 시각아이디문제언어결과실행 시간메모리
1077847vnm06Bulldozer (JOI17_bulldozer)C++14
5 / 100
1 ms1116 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; struct Point { long long x, y, val, nom; Point() {} Point(long long a, long long b, long long c, long long d) { x=a; y=b; val=c; nom=d; } }; bool operator<(Point p, Point q) { if(p.x==q.x) return p.y>q.y; return p.x<q.x; } struct Line { Point a, b; Line() {} Line(Point p, Point q) { a.x=p.x; a.y=p.y; a.val=p.val; a.nom=p.nom; b.x=q.x; b.y=q.y; b.val=q.val; b.nom=q.nom; } }; bool cmp(Line p, Line q) { if(p.a.x==p.b.x) return 1; if(q.a.x==q.b.x) return 1; return ((p.b.y-p.a.y) * (q.b.x-q.a.x)) < ((q.b.y-q.a.y) * (p.b.x-p.a.x)); } long long n, brl=0; long long pos[2005]; Point P[2005]; vector<Line> L; long long ans=0; long long A[2005]; void solve() { long long res=0; for(long long i=0; i<n; i++) { res+=A[i]; if(res<0) res=0; if(res>ans) ans=res; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(long long i=0; i<n; i++) cin>>P[i].x>>P[i].y>>P[i].val; sort(P, P+n); for(long long i=0; i<n; i++) P[i].nom=i; for(long long i=0; i<n; i++) { A[i]=P[i].val; pos[i]=i; for(long long j=i+1; j<n; j++) { L.push_back(Line(P[i], P[j])); ///cout<<L[brl].a.x<<" "<<L[brl].a.y<<" "<<L[brl].b.x<<" "<<L[brl].b.y<<"\n"; brl++; } } ///cout<<brl<<endl; //sort(L.begin(), L.end(), cmp); /** for(int i=0; i<L.size(); i++) { for(int j=0; j<L.size(); j++) { if(!cmp(L[i], L[j])) swap(L[i], L[j]); } } for(long long i=0; i<brl; i++) { solve(); Point t1=L[i].a, t2=L[i].b; swap(A[pos[t1.nom]], A[pos[t2.nom]]); swap(pos[t1.nom], pos[t2.nom]); }*/ solve(); cout<<ans<<endl; 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...