Submission #93196

#TimeUsernameProblemLanguageResultExecution timeMemory
93196Alexa2001Bulldozer (JOI17_bulldozer)C++17
25 / 100
2025 ms33412 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 2005; typedef long long ll; ll ans = 0; int n, i, j, where[Nmax], ord[Nmax]; struct point { int x, y, p; bool operator < (const point &other) const { if(x == other.x) return y > other.y; return x > other.x; } }; point a[Nmax]; struct intr { int x, y, id1, id2; bool operator < (const intr &other) const { if((ll) x * other.y == (ll) y * other.x) return (make_pair(id1, id2) < make_pair(other.id1, other.id2)); return (ll) x * other.y < (ll) y * other.x; } bool operator == (const intr &other) const { return (ll) x * other.y == (ll) y * other.x; } }; vector<intr> intersect; void apply(intr A) { int p1 = where[A.id1], p2 = where[A.id2]; assert(p1 + 1 == p2); swap(where[A.id1], where[A.id2]); swap(ord[p1], ord[p2]); } ll eval() { ll ans = 0, s = 0; int i; for(i=1; i<=n; ++i) { int val = a[ord[i]].p; s = max(s, 0LL); s += val; ans = max(ans, s); } return ans; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin >> n; for(i=1; i<=n; ++i) cin >> a[i].x >> a[i].y >> a[i].p; sort(a+1, a+n+1); for(i=1; i<=n; ++i) ord[i] = i, where[i] = i; for(i=1; i<=n; ++i) for(j=i+1; j<=n; ++j) if(a[i].x != a[j].x) intersect.push_back({a[i].y - a[j].y, a[i].x - a[j].x, i, j}); ans = eval(); sort(intersect.begin(), intersect.end()); for(i=0; i<intersect.size(); ++i) { j = i; while(j<intersect.size() && intersect[i] == intersect[j]) apply(intersect[j++]); i = j - 1; ans = max(ans, eval()); } cout << ans << '\n'; return 0; }

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<intersect.size(); ++i)
              ~^~~~~~~~~~~~~~~~~
bulldozer.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j<intersect.size() && intersect[i] == intersect[j])
               ~^~~~~~~~~~~~~~~~~
#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...