#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
ll p[1000000], to[10000], n;
struct SegTree
{
ll t[8000000][4], start;
ll operator[] (const int& i)
{
return t[i][0];
}
void build (ll n)
{
start = 1;
while (start < n) start <<= 1;
for (ll i = 2 * start - 1; i; i--)
merge (i);
}
void merge (ll node)
{
if (node >= start)
{
t[node][3] = p[node - start];
t[node][2] = max (0LL, p[node - start]);
t[node][1] = max (0LL, p[node - start]);
t[node][0] = max (0LL, p[node - start]);
}
else
{
t[node][3] = t[2 * node][3] + t[2 * node + 1][3];
t[node][2] = max (t[2 * node][3] + t[2 * node + 1][2], t[2 * node][2]);
t[node][1] = max (t[2 * node][1] + t[2 * node + 1][3], t[2 * node + 1][1]);
t[node][0] = max (max (t[2 * node][0], t[2 * node + 1][0]), t[2 * node][1] + t[2 * node + 1][2]);
}
}
void update (ll x, ll d)
{
p[x] = d;
x += start;
while (x)
{
merge (x);
x /= 2;
}
}
} t;
struct point
{
int x, y, c;
bool operator < (const point& b) const
{
return y < b.y;
}
} a[2000];
struct fraction
{
int a, b;
int p1, p2;
bool operator < (const fraction& d) const
{
if (!d.b) return true;
if (!b) return false;
return (a * d.b) < (b * d.a);
}
bool operator == (const fraction& d) const
{
if (!b && !d.b) return true;
if (!b || !d.b) return false;
return (a * d.b) == (b * d.a);
}
};
vector <fraction> d;
int main ()
{
cin >> n;
for (int i = 0; i < n; i++)
scanf ("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
sort (a, a + n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
int A = a[i].y - a[j].y;
int B = a[i].x - a[j].x;
d.push_back ({-B, A, i, j});
to[i] = i;
to[j] = j;
p[i] = a[i].c;
p[j] = a[j].c;
}
sort (d.begin(), d.end());
t.build (d.size ());
ll ans = t[1];
for (int i = 0; i < d.size ();)
{
if (d[i].b == 0) break;
int k = 0;
set < pair <int, int> > s;
while (i + k < d.size () && d[i + k] == d[i])
{
s.insert ({to[d[i + k].p1], d[i + k].p1});
s.insert ({to[d[i + k].p1], d[i + k].p2});
k++;
}
i += k;
while (s.size () > 1)
{
int l = s.begin () -> second, r = s.rbegin () -> second, p_l = p[to[l]], p_r = p[to[r]];
s.erase (s.begin ());
s.erase (*s.rbegin ());
t.update (to[r], p_l);
t.update (to[l], p_r);
swap (to[l], to[r]);
}
ans = max (ans, t[1]);
}
cout << ans;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:137:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < d.size ();)
~~^~~~~~~~~~~
bulldozer.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i + k < d.size () && d[i + k] == d[i])
~~~~~~^~~~~~~~~~~
bulldozer.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
