This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |