#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;
ll n;
class All{
public:
struct Node{
ll st, dr, total;
ll ssm;
};
Node all[NMAX * 4];
Node combine(Node a, Node b){
Node rez;
rez.st = max({a.st, a.total + b.st, 0LL});
rez.dr = max({b.dr, b.total + a.dr, 0LL});
rez.total = a.total + b.total;
rez.ssm = max({a.ssm, b.ssm, a.dr + b.st, 0LL}); ///hmmm
return rez;
}
void update(ll node, ll st, ll dr, ll a, ll b){
if(st == dr){
//b = max(b, 0);
all[node] = {max(b, 0LL), max(0LL, b), b, max(0LL, b)};
return;
}
ll mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b);
}else{
update(node * 2 + 1, mid + 1, dr, a, b);
}
all[node] = combine(all[node * 2], all[node * 2 + 1]);
}
Node best(){
return all[1];
}
}st;
struct poll{
ll x, y, val, idx;
};
poll v[NMAX], a[NMAX];
map <pii, ll> mp;
struct event{
pii p;
double timp;
};
vector <event> events;
bool cmp(event a, event b){
if(a.timp != b.timp)
return a.timp < b.timp;
if(a.p.second != b.p.second)
return a.p.second < b.p.second;
return a.p.first < b.p.first;
}
///De analizat
void swapElements(ll a, ll b){
st.update(1, 1, n, v[a].idx, v[b].val);
st.update(1, 1, n, v[b].idx, v[a].val);
swap(v[a].idx, v[b].idx);
}
///De analizat
bool cmpp(poll a, poll b){
if(a.x != b.x)
return a.x > b.x;
return a.y > b.y;
}
void compute(ll i, ll 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);
ll 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);
reverse(v + 1, v + n + 1);
for(i = 1; i <= n; i++){
for(ll j = i + 1; j <= n; j++){
compute(i, j);
}
}
for(i = 1; i <= n; i++){
st.update(1, 1, n, i, v[i].val);
v[i].idx = i;
}
sort(events.begin(), events.end(), cmp);
reverse(events.begin(), events.end(), cmp);
ll maxim = st.best().ssm;
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:120:45: error: no matching function for call to 'reverse(std::vector<event>::iterator, std::vector<event>::iterator, bool (&)(event, event))'
120 | reverse(events.begin(), events.end(), cmp);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bulldozer.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:1165:5: note: candidate: 'template<class _BIter> void std::reverse(_BIter, _BIter)'
1165 | reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
| ^~~~~~~
/usr/include/c++/10/bits/stl_algo.h:1165:5: note: template argument deduction/substitution failed:
bulldozer.cpp:120:45: note: candidate expects 2 arguments, 3 provided
120 | reverse(events.begin(), events.end(), cmp);
| ^
bulldozer.cpp:122:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(i = 0; i < events.size(); i++){
| ~~^~~~~~~~~~~~~~~
bulldozer.cpp:124:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if(i < events.size() - 1 && events[i].timp == events[i + 1].timp){
| ~~^~~~~~~~~~~~~~~~~~~
