#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];
ll val[N+N];
vector<pii> V2;
ll ans=0;
int n;
void dodaj(int v, int c){
val[v+N]+=c;
}
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);
}
return res;
}
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());
}
int main(){
cin>>n;
V2.resize(n);
for(int i=0; i<n; i++)cin>>V2[i].st>>V2[i].nd>>wei[i], gdzie[i]=i;
sort(gdzie, gdzie+n, [](int a, int b){return V2[a]<V2[b];});
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);
V.eb(kat, mp(x, y));
}
}
sort(all(V));
vector<pii> todo;
for(int i=0; i<V.size(); i++){
zmien({V[i].nd.st, V[i].nd.nd});
}
cout<<ans;
}
Compilation message
bulldozer.cpp: In function 'void zmien(std::vector<int>)':
bulldozer.cpp:51:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(i<=V.size()-1-i)break;
| ~^~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:80: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]
80 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
1144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
1212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
1212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
1212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
1144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
