제출 #1078835

#제출 시각아이디문제언어결과실행 시간메모리
1078835vnm06Bulldozer (JOI17_bulldozer)C++14
80 / 100
1321 ms251312 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 && q.a.x==q.b.x) return (p.b.y-p.a.y) > (q.b.y-q.a.y); if(p.a.x==p.b.x) return 1; if(q.a.x==q.b.x) return 0; if(((p.b.y-p.a.y) * (q.b.x-q.a.x)) == ((q.b.y-q.a.y) * (p.b.x-p.a.x))) return (p.b.x-p.a.x) > (q.b.x-q.a.x); 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)); } bool operator==(Line p, Line q) { 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)); } int n, brl=0; int 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; } } long long sum[8005], pref[8005], suf[8005], mx[8005]; void update(int v, int le, int ri, int id, long long val) { if(le==ri) { sum[v]=val; pref[v]=max(sum[v], 0LL); suf[v]=max(sum[v], 0LL); mx[v]=max(sum[v], 0LL); return; } int mid=(le+ri)/2; if(id<=mid) update(2*v, le, mid, id, val); else update(2*v+1, mid+1, ri, id, val); sum[v]=sum[2*v]+sum[2*v+1]; pref[v]=max(pref[2*v], sum[2*v]+pref[2*v+1]); suf[v]=max(suf[2*v+1], suf[2*v]+sum[2*v+1]); mx[v]=max(max(mx[2*v], mx[2*v+1]), suf[2*v]+pref[2*v+1]); } bool nepip[2005]; vector<int> upd; 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; stable_sort(L.begin(), L.end(), cmp); for(int i=0; i<n; i++) { update(1, 0, n-1, i, A[i]); } for(long long i=0; i<brl; i++) { if(i==0 || !(L[i]==L[i-1])) { ans=max(ans, mx[1]); for(int j=0; j<upd.size(); j++) nepip[upd[j]]=0; upd.resize(0); } Point t1=L[i].a, t2=L[i].b; if(nepip[pos[t1.nom]] || nepip[pos[t2.nom]]) continue; update(1, 0, n-1, pos[t2.nom], A[pos[t1.nom]]); update(1, 0, n-1, pos[t1.nom], A[pos[t2.nom]]); swap(A[pos[t1.nom]], A[pos[t2.nom]]); swap(pos[t1.nom], pos[t2.nom]); nepip[pos[t1.nom]]=1; nepip[pos[t2.nom]]=1; upd.push_back(pos[t1.nom]); upd.push_back(pos[t2.nom]); } ans=max(ans, mx[1]); cout<<ans<<endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for(int j=0; j<upd.size(); j++) nepip[upd[j]]=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...