#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)
ll gcd(ll a, ll b) {
return a ? gcd(b % a, a) : b;
}
struct P {
ll x, y, w;
ll operator * (const P &oth) const {
return x * oth.y - y * oth.x;
}
ll operator / (const P &oth) const {
return x * oth.x + y * oth.y;
}
};
P operator - (const P &a, const P &b) {
return { a.x - b.x, a.y - b.y };
}
const int N = 2005;
P a[N];
ll t[N * 4], mnp[N * 4], mxp[N * 4], pref[N], up[N * 4];
int pos[N];
int n;
pair<int, int> z[N * N];
void mrg(int v) {
t[v] = max(t[v * 2], t[v * 2 + 1]);
t[v] = max(t[v], mxp[v * 2 + 1] - mnp[v * 2]);
mxp[v] = max(mxp[v * 2], mxp[v * 2 + 1]);
mnp[v] = min(mnp[v * 2], mnp[v * 2 + 1]);
}
void build(int v = 1, int L = 0, int R = n) {
if (L == R) {
t[v] = 0;
mxp[v] = mnp[v] = pref[L];
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
mrg(v);
}
}
void push(int v, int L, int R) {
if (up[v]) {
if (L != R) {
up[v * 2] += up[v];
up[v * 2 + 1] += up[v];
}
mnp[v] += up[v];
mxp[v] += up[v];
up[v] = 0;
}
}
void upd(int l, int r, int x, int v = 1, int L = 0, int R = n) {
push(v, L, R);
if (l > r)
return;
if (l == L && r == R) {
up[v] += x;
push(v, L, R);
}
else {
int m = (L + R) >> 1;
upd(l, min(m, r), x, v * 2, L, m);
upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
mrg(v);
}
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y, w;
cin >> x >> y >> w;
a[i] = { x, y, w };
}
sort(a + 1, a + n + 1, [](P &a, P &b) {
return a.x == b.x ? a.y > b.y : a.x < b.x;
});
int ct = 0;
for (int i = 1; i <= n; i++) {
pos[i] = i;
pref[i] = pref[i - 1] + a[i].w;
for (int j = i + 1; j <= n; j++) {
z[ct++] = { i, j };
}
}
build();
sort(z, z + ct, [](pair<int, int> &p, pair<int, int> &q) {
P vp = a[p.second] - a[p.first], vq = a[q.second] - a[q.first];
if (vp.x > 0 || vp.x == 0 && vp.y < 0) {
swap(p.first, p.second);
vp.x = -vp.x;
vp.y = -vp.y;
}
if (vq.x > 0 || vq.x == 0 && vq.y < 0) {
swap(q.first, q.second);
vq.x = -vq.x;
vq.y = -vq.y;
}
ll prod = vp * vq;
if (prod != 0)
return prod > 0;
prod = (a[p.second] - a[p.first]) / (a[q.first] - a[p.first]);
if (prod != 0)
return prod > 0;
return vp.x < vq.x || vp.y < vq.y;
});;
ll ans = t[1];
for (int i = 0; i < ct; i++) {
int x = z[i].first,
y = z[i].second;
if (pos[x] > pos[y]) {
swap(x, y);
}
upd(pos[x], pos[y] - 1, -a[x].w);
upd(pos[x], pos[y] - 1, a[y].w);
swap(pos[x], pos[y]);
if (i == ct - 1 || (a[z[i + 1].second] - a[z[i + 1].first]) *
(a[y] - a[x]) != 0) {
ans = max(ans, t[1]);
}
}
cout << ans;
return 0;
}
Compilation message
bulldozer.cpp:45:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable : 4996)
bulldozer.cpp: In lambda function:
bulldozer.cpp:153:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (vp.x > 0 || vp.x == 0 && vp.y < 0) {
~~~~~~~~~~^~~~~~~~~~~
bulldozer.cpp:158:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (vq.x > 0 || vq.x == 0 && vq.y < 0) {
~~~~~~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
4 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
4 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
33 |
Correct |
1042 ms |
16240 KB |
Output is correct |
34 |
Correct |
1027 ms |
16256 KB |
Output is correct |
35 |
Correct |
1012 ms |
16248 KB |
Output is correct |
36 |
Correct |
1049 ms |
16244 KB |
Output is correct |
37 |
Correct |
1056 ms |
16248 KB |
Output is correct |
38 |
Correct |
1028 ms |
16352 KB |
Output is correct |
39 |
Correct |
1035 ms |
16340 KB |
Output is correct |
40 |
Correct |
1016 ms |
16348 KB |
Output is correct |
41 |
Correct |
1050 ms |
16252 KB |
Output is correct |
42 |
Correct |
1036 ms |
16252 KB |
Output is correct |
43 |
Correct |
1036 ms |
16248 KB |
Output is correct |
44 |
Correct |
1014 ms |
16220 KB |
Output is correct |
45 |
Correct |
1109 ms |
16276 KB |
Output is correct |
46 |
Correct |
999 ms |
16348 KB |
Output is correct |
47 |
Correct |
1031 ms |
16344 KB |
Output is correct |
48 |
Correct |
1032 ms |
16248 KB |
Output is correct |
49 |
Correct |
1058 ms |
16256 KB |
Output is correct |
50 |
Correct |
1026 ms |
16352 KB |
Output is correct |
51 |
Correct |
1104 ms |
16352 KB |
Output is correct |
52 |
Correct |
1046 ms |
16248 KB |
Output is correct |
53 |
Correct |
1058 ms |
16352 KB |
Output is correct |
54 |
Correct |
1006 ms |
16252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
4 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
3 ms |
384 KB |
Output is correct |
33 |
Correct |
1042 ms |
16240 KB |
Output is correct |
34 |
Correct |
1027 ms |
16256 KB |
Output is correct |
35 |
Correct |
1012 ms |
16248 KB |
Output is correct |
36 |
Correct |
1049 ms |
16244 KB |
Output is correct |
37 |
Correct |
1056 ms |
16248 KB |
Output is correct |
38 |
Correct |
1028 ms |
16352 KB |
Output is correct |
39 |
Correct |
1035 ms |
16340 KB |
Output is correct |
40 |
Correct |
1016 ms |
16348 KB |
Output is correct |
41 |
Correct |
1050 ms |
16252 KB |
Output is correct |
42 |
Correct |
1036 ms |
16252 KB |
Output is correct |
43 |
Correct |
1036 ms |
16248 KB |
Output is correct |
44 |
Correct |
1014 ms |
16220 KB |
Output is correct |
45 |
Correct |
1109 ms |
16276 KB |
Output is correct |
46 |
Correct |
999 ms |
16348 KB |
Output is correct |
47 |
Correct |
1031 ms |
16344 KB |
Output is correct |
48 |
Correct |
1032 ms |
16248 KB |
Output is correct |
49 |
Correct |
1058 ms |
16256 KB |
Output is correct |
50 |
Correct |
1026 ms |
16352 KB |
Output is correct |
51 |
Correct |
1104 ms |
16352 KB |
Output is correct |
52 |
Correct |
1046 ms |
16248 KB |
Output is correct |
53 |
Correct |
1058 ms |
16352 KB |
Output is correct |
54 |
Correct |
1006 ms |
16252 KB |
Output is correct |
55 |
Correct |
1020 ms |
16256 KB |
Output is correct |
56 |
Correct |
1014 ms |
16248 KB |
Output is correct |
57 |
Correct |
1031 ms |
16344 KB |
Output is correct |
58 |
Correct |
1029 ms |
16356 KB |
Output is correct |
59 |
Correct |
1010 ms |
16348 KB |
Output is correct |
60 |
Correct |
1020 ms |
16252 KB |
Output is correct |
61 |
Correct |
1018 ms |
16248 KB |
Output is correct |
62 |
Correct |
1029 ms |
16248 KB |
Output is correct |
63 |
Correct |
1020 ms |
16256 KB |
Output is correct |
64 |
Correct |
1012 ms |
16344 KB |
Output is correct |
65 |
Correct |
1018 ms |
16344 KB |
Output is correct |
66 |
Correct |
1068 ms |
16352 KB |
Output is correct |
67 |
Correct |
1056 ms |
16244 KB |
Output is correct |
68 |
Correct |
1069 ms |
16248 KB |
Output is correct |
69 |
Correct |
1046 ms |
16252 KB |
Output is correct |
70 |
Correct |
1034 ms |
16248 KB |
Output is correct |
71 |
Correct |
1045 ms |
16348 KB |
Output is correct |
72 |
Correct |
1069 ms |
16348 KB |
Output is correct |
73 |
Correct |
1010 ms |
16352 KB |
Output is correct |
74 |
Correct |
1002 ms |
16248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |