#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/****************************************************************/
const int MAXN = 2000;
int N, x[2000], y[2000], w[2000], pos[2000];
int treearray[2000];
struct Seg {
int data[2000];
void set(int x, int val) {
data[x] = val;
}
void build() {
}
void update(int x, int val) {
data[x] = val;
}
ll query() {
// cout << "Query: ";
// FOR(i, 0, N) cout << data[i] << " ";
ll best = 0;
FOR(i, 0, N) FOR(j, i, N) {
ll tmp = 0;
FORE(x, i, j) tmp += data[x];
maxx(best, tmp);
}
// cout << ":: " << best << "\n";
return best;
}
} tree;
struct upd {
ll vx, vy;
int ia, ib;
upd(ll _vx, ll _vy, int _a, int _b) : vx(_vx), vy(_vy), ia(_a), ib(_b) {}
};
v<upd> lines;
void perform_swap(int i, int j) {
// cout << "Swapping " << i << " " << j << "\n";
swap(pos[i], pos[j]);
tree.update(pos[i], w[i]);
tree.update(pos[j], w[j]);
}
void setup() {
cin >> N;
v<int> pnts(N);
FOR(i, 0, N) {
cin >> x[i] >> y[i] >> w[i];
pnts[i] = i;
}
sort(all(pnts), [](int &i, int &j) {
return mp(x[i], y[i]) < mp(x[j], y[j]);
});
FOR(i, 0, N) {
pos[pnts[i]] = i;
tree.set(i, w[pnts[i]]);
}
tree.build();
}
int main() {
io();
setup();
FOR(i, 0, N) FOR(j, 0, N) if (x[i] < x[j])
lines.push_back(upd(x[j] - x[i], y[j] - y[i], i, j));
sort(all(lines), [](upd &a, upd &b) {
if (a.vy*b.vx == b.vy*a.vx)
return mp(x[a.ia], x[a.ib]) < mp(x[b.ia], x[b.ib]);
return a.vy*b.vx > b.vy*a.vx;
});
ll best = tree.query();
for (int i = 0; i < lines.size(); ) {
ll curx = lines[i].vx, cury = lines[i].vy;
while (i < lines.size() && cury*lines[i].vx == curx*lines[i].vy) {
perform_swap(lines[i].ia, lines[i].ib);
i++;
}
maxx(best, tree.query());
}
cout << best << "\n";
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < lines.size(); ) {
~~^~~~~~~~~~~~~~
bulldozer.cpp:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i < lines.size() && cury*lines[i].vx == curx*lines[i].vy) {
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
640 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
640 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
3 ms |
640 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
556 ms |
640 KB |
Output is correct |
2 |
Correct |
560 ms |
640 KB |
Output is correct |
3 |
Correct |
574 ms |
640 KB |
Output is correct |
4 |
Correct |
572 ms |
640 KB |
Output is correct |
5 |
Correct |
570 ms |
640 KB |
Output is correct |
6 |
Correct |
564 ms |
640 KB |
Output is correct |
7 |
Correct |
558 ms |
640 KB |
Output is correct |
8 |
Correct |
568 ms |
640 KB |
Output is correct |
9 |
Correct |
571 ms |
640 KB |
Output is correct |
10 |
Correct |
571 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
304 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 |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
1 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 |
560 ms |
640 KB |
Output is correct |
22 |
Correct |
569 ms |
640 KB |
Output is correct |
23 |
Correct |
580 ms |
640 KB |
Output is correct |
24 |
Correct |
559 ms |
640 KB |
Output is correct |
25 |
Correct |
596 ms |
640 KB |
Output is correct |
26 |
Correct |
567 ms |
640 KB |
Output is correct |
27 |
Correct |
558 ms |
640 KB |
Output is correct |
28 |
Correct |
560 ms |
640 KB |
Output is correct |
29 |
Correct |
562 ms |
640 KB |
Output is correct |
30 |
Correct |
585 ms |
640 KB |
Output is correct |
31 |
Correct |
582 ms |
640 KB |
Output is correct |
32 |
Correct |
557 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
556 ms |
640 KB |
Output is correct |
2 |
Correct |
560 ms |
640 KB |
Output is correct |
3 |
Correct |
574 ms |
640 KB |
Output is correct |
4 |
Correct |
572 ms |
640 KB |
Output is correct |
5 |
Correct |
570 ms |
640 KB |
Output is correct |
6 |
Correct |
564 ms |
640 KB |
Output is correct |
7 |
Correct |
558 ms |
640 KB |
Output is correct |
8 |
Correct |
568 ms |
640 KB |
Output is correct |
9 |
Correct |
571 ms |
640 KB |
Output is correct |
10 |
Correct |
571 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
304 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 |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
1 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 |
560 ms |
640 KB |
Output is correct |
22 |
Correct |
569 ms |
640 KB |
Output is correct |
23 |
Correct |
580 ms |
640 KB |
Output is correct |
24 |
Correct |
559 ms |
640 KB |
Output is correct |
25 |
Correct |
596 ms |
640 KB |
Output is correct |
26 |
Correct |
567 ms |
640 KB |
Output is correct |
27 |
Correct |
558 ms |
640 KB |
Output is correct |
28 |
Correct |
560 ms |
640 KB |
Output is correct |
29 |
Correct |
562 ms |
640 KB |
Output is correct |
30 |
Correct |
585 ms |
640 KB |
Output is correct |
31 |
Correct |
582 ms |
640 KB |
Output is correct |
32 |
Correct |
557 ms |
640 KB |
Output is correct |
33 |
Execution timed out |
2049 ms |
49892 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
556 ms |
640 KB |
Output is correct |
2 |
Correct |
560 ms |
640 KB |
Output is correct |
3 |
Correct |
574 ms |
640 KB |
Output is correct |
4 |
Correct |
572 ms |
640 KB |
Output is correct |
5 |
Correct |
570 ms |
640 KB |
Output is correct |
6 |
Correct |
564 ms |
640 KB |
Output is correct |
7 |
Correct |
558 ms |
640 KB |
Output is correct |
8 |
Correct |
568 ms |
640 KB |
Output is correct |
9 |
Correct |
571 ms |
640 KB |
Output is correct |
10 |
Correct |
571 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
304 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 |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
1 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 |
560 ms |
640 KB |
Output is correct |
22 |
Correct |
569 ms |
640 KB |
Output is correct |
23 |
Correct |
580 ms |
640 KB |
Output is correct |
24 |
Correct |
559 ms |
640 KB |
Output is correct |
25 |
Correct |
596 ms |
640 KB |
Output is correct |
26 |
Correct |
567 ms |
640 KB |
Output is correct |
27 |
Correct |
558 ms |
640 KB |
Output is correct |
28 |
Correct |
560 ms |
640 KB |
Output is correct |
29 |
Correct |
562 ms |
640 KB |
Output is correct |
30 |
Correct |
585 ms |
640 KB |
Output is correct |
31 |
Correct |
582 ms |
640 KB |
Output is correct |
32 |
Correct |
557 ms |
640 KB |
Output is correct |
33 |
Execution timed out |
2049 ms |
49892 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
640 KB |
Output is correct |
2 |
Correct |
3 ms |
640 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
3 ms |
640 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
3 ms |
640 KB |
Output is correct |
10 |
Correct |
3 ms |
640 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 |
556 ms |
640 KB |
Output is correct |
17 |
Correct |
560 ms |
640 KB |
Output is correct |
18 |
Correct |
574 ms |
640 KB |
Output is correct |
19 |
Correct |
572 ms |
640 KB |
Output is correct |
20 |
Correct |
570 ms |
640 KB |
Output is correct |
21 |
Correct |
564 ms |
640 KB |
Output is correct |
22 |
Correct |
558 ms |
640 KB |
Output is correct |
23 |
Correct |
568 ms |
640 KB |
Output is correct |
24 |
Correct |
571 ms |
640 KB |
Output is correct |
25 |
Correct |
571 ms |
640 KB |
Output is correct |
26 |
Correct |
2 ms |
304 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
560 ms |
640 KB |
Output is correct |
37 |
Correct |
569 ms |
640 KB |
Output is correct |
38 |
Correct |
580 ms |
640 KB |
Output is correct |
39 |
Correct |
559 ms |
640 KB |
Output is correct |
40 |
Correct |
596 ms |
640 KB |
Output is correct |
41 |
Correct |
567 ms |
640 KB |
Output is correct |
42 |
Correct |
558 ms |
640 KB |
Output is correct |
43 |
Correct |
560 ms |
640 KB |
Output is correct |
44 |
Correct |
562 ms |
640 KB |
Output is correct |
45 |
Correct |
585 ms |
640 KB |
Output is correct |
46 |
Correct |
582 ms |
640 KB |
Output is correct |
47 |
Correct |
557 ms |
640 KB |
Output is correct |
48 |
Execution timed out |
2049 ms |
49892 KB |
Time limit exceeded |
49 |
Halted |
0 ms |
0 KB |
- |