#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int N=(1<<11), INF=1e9+5;
int wei[N], gdzie[N], gdzie2[N];
ll val[N+N], pref[N+N], suf[N+N], res[N+N];
vector<pii> V2;
ll ans=0;
int n;
void dodaj(int v, int c){
val[v+N]+=c;
pref[v+N]=max(val[v+N], 0ll);
suf[v+N]=max(val[v+N], 0ll);
res[v+N]=max(val[v+N], 0ll);
v+=N;
v/=2;
while(v){
int l=v+v, r=l+1;
res[v]=max(res[l], res[r]);
pref[v]=max(pref[l], val[l]+pref[r]);
suf[v]=max(suf[r], val[r]+suf[l]);
val[v]=val[l]+val[r];
res[v]=max(res[v], pref[r]+suf[l]);
v/=2;
}
}
ll get_ans(){
/*ll dp=0, res=0;
for(int i=n-1; i>=0; i--){
dp=max(dp+val[i+N], 0ll);
res=max(res, dp);
}
deb(res);*/
return res[1];
}
void zmien(vector<int> V){
/*sort(all(V), [](int a, int b){return gdzie[a]<gdzie[b];});
//assert(V.size()==2);
int c=gdzie[V[0]];
ans=max(ans, get_ans());
for(int i=V.size()-1; i>0;i--){
dodaj(c, wei[V[i]]);
dodaj(gdzie[V[i]], -wei[V[i]]);
}
ans=max(ans, get_ans());
for(int i=V.size()-1; i>=0; i--){
if(i<=V.size()-1-i)break;
swap(gdzie[V[i]], gdzie[V[V.size()-i-1]]);
}
reverse(all(V));
for(int i=V.size()-1; i>0;i--){
dodaj(c, -wei[V[i]]);
dodaj(gdzie[V[i]], wei[V[i]]);
}
ans=max(ans, get_ans());*/
//for(int i=0; i<n; i++)cout<<gdzie[i]<<" ";cout<<"\n";
//assert(abs(gdzie[V[0]]-gdzie[V[1]])==1);
//deb(V[0], V[1], gdzie[V[0]], gdzie[V[1]]);
ans=max(ans, get_ans());
dodaj(gdzie[V[0]], wei[V[1]]);
dodaj(gdzie[V[1]], -wei[V[1]]);
ans=max(ans, get_ans());
//deb(val[N], val[N+1], val[N+2], val[N+3]);
dodaj(gdzie[V[0]], -wei[V[0]]);
dodaj(gdzie[V[1]], wei[V[0]]);
swap(gdzie[V[0]], gdzie[V[1]]);
ans=max(ans, get_ans());
}
int main(){
cin>>n;
V2.resize(n);
for(int i=0; i<n; i++)cin>>V2[i].st>>V2[i].nd>>wei[i], gdzie2[i]=i;
sort(gdzie2, gdzie2+n, [](int a, int b){if(V2[a].st==V2[b].st)return V2[a].nd>V2[b].nd;return V2[a].st<V2[b].st;});
for(int i=0; i<n; i++)gdzie[gdzie2[i]]=i;
for(int i=0; i<n; i++)dodaj(gdzie[i], wei[i]);
vector<pair<ld, pii> > V;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
int x=V2[i].st-V2[j].st, y=V2[i].nd-V2[j].nd;
if(x>0)y=-y, x=-x;
if(x==0 && y<0)y=-y;
ld kat=-atan2(x, y);
//deb(kat, x, y, i, j);
V.eb(kat, mp(i, j));
}
}
sort(all(V));
vector<pii> todo;
for(int i=0; i<V.size(); i++){
zmien({V[i].nd.st, V[i].nd.nd});
}
ans=max(ans, get_ans());
cout<<ans;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
736 KB |
Output is correct |
2 |
Correct |
4 ms |
724 KB |
Output is correct |
3 |
Correct |
4 ms |
724 KB |
Output is correct |
4 |
Correct |
5 ms |
724 KB |
Output is correct |
5 |
Correct |
4 ms |
724 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
724 KB |
Output is correct |
8 |
Correct |
4 ms |
724 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
4 ms |
772 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
724 KB |
Output is correct |
22 |
Correct |
4 ms |
724 KB |
Output is correct |
23 |
Correct |
4 ms |
724 KB |
Output is correct |
24 |
Correct |
5 ms |
724 KB |
Output is correct |
25 |
Correct |
4 ms |
728 KB |
Output is correct |
26 |
Correct |
4 ms |
724 KB |
Output is correct |
27 |
Correct |
4 ms |
724 KB |
Output is correct |
28 |
Correct |
4 ms |
724 KB |
Output is correct |
29 |
Correct |
4 ms |
724 KB |
Output is correct |
30 |
Correct |
4 ms |
732 KB |
Output is correct |
31 |
Correct |
4 ms |
736 KB |
Output is correct |
32 |
Correct |
4 ms |
732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
736 KB |
Output is correct |
2 |
Correct |
4 ms |
724 KB |
Output is correct |
3 |
Correct |
4 ms |
724 KB |
Output is correct |
4 |
Correct |
5 ms |
724 KB |
Output is correct |
5 |
Correct |
4 ms |
724 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
724 KB |
Output is correct |
8 |
Correct |
4 ms |
724 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
4 ms |
772 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
724 KB |
Output is correct |
22 |
Correct |
4 ms |
724 KB |
Output is correct |
23 |
Correct |
4 ms |
724 KB |
Output is correct |
24 |
Correct |
5 ms |
724 KB |
Output is correct |
25 |
Correct |
4 ms |
728 KB |
Output is correct |
26 |
Correct |
4 ms |
724 KB |
Output is correct |
27 |
Correct |
4 ms |
724 KB |
Output is correct |
28 |
Correct |
4 ms |
724 KB |
Output is correct |
29 |
Correct |
4 ms |
724 KB |
Output is correct |
30 |
Correct |
4 ms |
732 KB |
Output is correct |
31 |
Correct |
4 ms |
736 KB |
Output is correct |
32 |
Correct |
4 ms |
732 KB |
Output is correct |
33 |
Correct |
1336 ms |
66276 KB |
Output is correct |
34 |
Correct |
1333 ms |
66256 KB |
Output is correct |
35 |
Correct |
1337 ms |
66284 KB |
Output is correct |
36 |
Correct |
1334 ms |
66336 KB |
Output is correct |
37 |
Correct |
1341 ms |
66284 KB |
Output is correct |
38 |
Correct |
1338 ms |
66284 KB |
Output is correct |
39 |
Correct |
1326 ms |
66284 KB |
Output is correct |
40 |
Correct |
1327 ms |
66236 KB |
Output is correct |
41 |
Correct |
1331 ms |
66284 KB |
Output is correct |
42 |
Correct |
1362 ms |
66300 KB |
Output is correct |
43 |
Correct |
1320 ms |
66284 KB |
Output is correct |
44 |
Correct |
1338 ms |
66360 KB |
Output is correct |
45 |
Correct |
1302 ms |
66248 KB |
Output is correct |
46 |
Correct |
1338 ms |
66224 KB |
Output is correct |
47 |
Correct |
1309 ms |
66288 KB |
Output is correct |
48 |
Correct |
1299 ms |
66320 KB |
Output is correct |
49 |
Correct |
1311 ms |
66284 KB |
Output is correct |
50 |
Correct |
1301 ms |
66292 KB |
Output is correct |
51 |
Correct |
1305 ms |
66280 KB |
Output is correct |
52 |
Correct |
1319 ms |
66320 KB |
Output is correct |
53 |
Correct |
1333 ms |
66212 KB |
Output is correct |
54 |
Correct |
1314 ms |
66244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
736 KB |
Output is correct |
2 |
Correct |
4 ms |
724 KB |
Output is correct |
3 |
Correct |
4 ms |
724 KB |
Output is correct |
4 |
Correct |
5 ms |
724 KB |
Output is correct |
5 |
Correct |
4 ms |
724 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
724 KB |
Output is correct |
8 |
Correct |
4 ms |
724 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
4 ms |
772 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
4 ms |
724 KB |
Output is correct |
22 |
Correct |
4 ms |
724 KB |
Output is correct |
23 |
Correct |
4 ms |
724 KB |
Output is correct |
24 |
Correct |
5 ms |
724 KB |
Output is correct |
25 |
Correct |
4 ms |
728 KB |
Output is correct |
26 |
Correct |
4 ms |
724 KB |
Output is correct |
27 |
Correct |
4 ms |
724 KB |
Output is correct |
28 |
Correct |
4 ms |
724 KB |
Output is correct |
29 |
Correct |
4 ms |
724 KB |
Output is correct |
30 |
Correct |
4 ms |
732 KB |
Output is correct |
31 |
Correct |
4 ms |
736 KB |
Output is correct |
32 |
Correct |
4 ms |
732 KB |
Output is correct |
33 |
Correct |
1336 ms |
66276 KB |
Output is correct |
34 |
Correct |
1333 ms |
66256 KB |
Output is correct |
35 |
Correct |
1337 ms |
66284 KB |
Output is correct |
36 |
Correct |
1334 ms |
66336 KB |
Output is correct |
37 |
Correct |
1341 ms |
66284 KB |
Output is correct |
38 |
Correct |
1338 ms |
66284 KB |
Output is correct |
39 |
Correct |
1326 ms |
66284 KB |
Output is correct |
40 |
Correct |
1327 ms |
66236 KB |
Output is correct |
41 |
Correct |
1331 ms |
66284 KB |
Output is correct |
42 |
Correct |
1362 ms |
66300 KB |
Output is correct |
43 |
Correct |
1320 ms |
66284 KB |
Output is correct |
44 |
Correct |
1338 ms |
66360 KB |
Output is correct |
45 |
Correct |
1302 ms |
66248 KB |
Output is correct |
46 |
Correct |
1338 ms |
66224 KB |
Output is correct |
47 |
Correct |
1309 ms |
66288 KB |
Output is correct |
48 |
Correct |
1299 ms |
66320 KB |
Output is correct |
49 |
Correct |
1311 ms |
66284 KB |
Output is correct |
50 |
Correct |
1301 ms |
66292 KB |
Output is correct |
51 |
Correct |
1305 ms |
66280 KB |
Output is correct |
52 |
Correct |
1319 ms |
66320 KB |
Output is correct |
53 |
Correct |
1333 ms |
66212 KB |
Output is correct |
54 |
Correct |
1314 ms |
66244 KB |
Output is correct |
55 |
Correct |
1317 ms |
66260 KB |
Output is correct |
56 |
Correct |
1313 ms |
66320 KB |
Output is correct |
57 |
Correct |
1308 ms |
66260 KB |
Output is correct |
58 |
Correct |
1350 ms |
66284 KB |
Output is correct |
59 |
Correct |
1326 ms |
66276 KB |
Output is correct |
60 |
Correct |
1329 ms |
66268 KB |
Output is correct |
61 |
Correct |
1328 ms |
66300 KB |
Output is correct |
62 |
Correct |
1321 ms |
66280 KB |
Output is correct |
63 |
Correct |
1321 ms |
66260 KB |
Output is correct |
64 |
Correct |
1323 ms |
66232 KB |
Output is correct |
65 |
Correct |
1316 ms |
66284 KB |
Output is correct |
66 |
Correct |
1321 ms |
66236 KB |
Output is correct |
67 |
Correct |
1316 ms |
66208 KB |
Output is correct |
68 |
Correct |
1309 ms |
66260 KB |
Output is correct |
69 |
Correct |
1330 ms |
66276 KB |
Output is correct |
70 |
Correct |
1316 ms |
66360 KB |
Output is correct |
71 |
Correct |
1326 ms |
66284 KB |
Output is correct |
72 |
Correct |
1298 ms |
66284 KB |
Output is correct |
73 |
Correct |
1300 ms |
66244 KB |
Output is correct |
74 |
Correct |
1389 ms |
66256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |