#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 2001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
int n;
class AINT{
public:
struct Node{
int st, dr, total;
int ssm;
};
Node aint[NMAX * 4];
Node combine(Node a, Node b){
Node rez;
rez.st = max({a.st, a.total + b.st, 0});
rez.dr = max({b.dr, b.total + a.dr, 0});
rez.total = a.total + b.total;
rez.ssm = max({a.ssm, b.ssm, a.dr + b.st, 0}); ///hmmm
return rez;
}
void update(int node, int st, int dr, int a, int b){
if(st == dr){
//b = max(b, 0);
aint[node] = {max(b, 0), max(0, b), b, max(0, b)};
return;
}
int mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b);
}else{
update(node * 2 + 1, mid + 1, dr, a, b);
}
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
Node best(){
return aint[1];
}
}st;
struct point{
int x, y, val;
};
point v[NMAX], a[NMAX];
map <pii, int> mp;
struct event{
pii p;
double timp;
};
vector <event> events;
bool cmp(event a, event b){
return a.timp < b.timp;
}
///De analizat
void swapElements(int a, int b){
st.update(1, 1, n, mp[{v[a].x, v[a].y}], v[b].val);
st.update(1, 1, n, mp[{v[b].x, v[b].y}], v[a].val);
swap(mp[{v[b].x, v[b].y}], mp[{v[a].x, v[a].y}]);
}
///De analizat
bool cmpp(point a, point b){
if(a.x != b.x)
return a.x < b.x;
return a.y > b.y;
}
void compute(int i, int j){
events.push_back({{i, j}, (double)(v[i].y - v[j].y) / (double)(v[i].x - v[j].x)});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i;
cin >> n;
for(i = 1; i <= n; i++){
cin >> v[i].x >> v[i].y >> v[i].val;
}
sort(v + 1, v + n + 1, cmpp);
for(i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
compute(i, j);
}
}
for(i = 1; i <= n; i++){
st.update(1, 1, n, i, v[i].val);
mp[{v[i].x, v[i].y}] = i;
}
sort(events.begin(), events.end(), cmp);
int maxim = 0;
for(i = 0; i < events.size(); i++){
swapElements(events[i].p.first, events[i].p.second);
if(i < events.size() - 1 && events[i].timp == events[i + 1].timp){
continue;
}
maxim = max(maxim, st.best().ssm);
}
cout << maxim;
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(i = 0; i < events.size(); i++){
| ~~^~~~~~~~~~~~~~~
bulldozer.cpp:118:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | if(i < events.size() - 1 && events[i].timp == events[i + 1].timp){
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
