#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 1e3 + 5;
int n;
namespace SSM {
#define int ll
struct Node {
int sum, pref, suff, mx;
Node() : sum(0), pref(0), suff(0), mx(0) {;}
Node(int val) : sum(val), pref(max(0LL, val)), suff(max(0LL, val)), mx(max(0LL, val)) {;}
Node(int s, int p, int u, int m) : sum(s), pref(p), suff(u), mx(m) {;}
Node operator +(const Node& x) const {
return Node(x.sum + sum,
max(pref, sum + x.pref),
max(x.suff, x.sum + suff),
max({mx, x.mx, suff + x.pref}));
}
};
#undef int
Node aint[nmax * 4];
void upd(int poz, ll val, int node = 1, int cl = 0, int cr = n - 1) {
if(cl == cr) {
aint[node] = Node(val);
return;
}
int mid = cl + cr >> 1;
if(poz <= mid)
upd(poz, val, 2 * node, cl, mid);
else
upd(poz, val, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
ll query() { return aint[1].mx; }
};
vector< tuple<int,int,int> > points;
vector<int> ind;
namespace LineContainer { // catthink
pair<int,int> getline(int l, int r) { return {-(get<1>(points[l]) - get<1>(points[r])), -(get<0>(points[l]) - get<0>(points[r]))};};
auto cmpline = [](pair<int,int> l, pair<int,int> r) {
if(l.second == 0 && r.second == 0)
return false;
if(l.second == 0)
return true;
if(r.second == 0)
return false;
if(!((((ll)l.first * l.second) >= 0) ^ ((((ll)l.first * l.second) >= 0))))
return (ll)l.first * r.second > (ll)r.first * l.second;
return (ll)l.first * r.second < (ll)r.first * l.second;
};
auto eqline = [](pair<int,int> l, pair<int,int> r) { return !cmpline(l, r) && !cmpline(r, l); };
auto eq = [](int i, int j) { return eqline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1])); };
auto cmp = [](int i, int j) { return cmpline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1]))
|| (eq(i, j) && i < j); };
set<int, decltype(cmp)> heap(cmp);
void rev(int l, int r) {
if(l > 0 && ind[l - 1] < ind[l])
heap.erase(l - 1);
if(r < ind.size() - 1 && ind[r] < ind[r + 1])
heap.erase(r);
reverse(ind.begin() + l, ind.begin() + r + 1);
if(l > 0 && ind[l - 1] < ind[l])
heap.insert(l - 1);
if(r < ind.size() - 1 && ind[r] < ind[r + 1])
heap.insert(r);
for(int i = l; i <= r; i++) {
SSM::upd(i, get<2>(points[ind[i]]));
}
}
int startmove() {
if(heap.size() == 0)
return -1;
int u = *heap.begin(), last = u;
//cerr << "- " << u << '\n';
heap.erase(heap.begin());
while(!heap.empty() && eq(*heap.begin(), u)) {
if(*heap.begin() - u > 1) {
rev(last, u + 1);
last = *heap.begin();
}
u = *heap.begin();
heap.erase(heap.begin());
}
rev(last, u + 1);
return SSM::query();
}
}
int main() {
cin >> n;
points.resize(n);
ind.resize(n);
for(auto &[a, b, c] : points)
cin >> a >> b >> c;
sort(points.begin(), points.end());
for(int i = 0; i < n; i++)
//cerr << get<0>(points[i]) << ' ' << get<1>(points[i]) << '\n',
ind[i] = i;
for(int i = 0; i < n - 1; i++)
LineContainer::heap.insert(i);
int mx = 0, temp;
while((temp = LineContainer::startmove()) >= 0) {
//cerr << temp << '\n';
//cerr << "Ma-ta\n";
mx = max(mx, temp);
}
cout << mx << '\n';
}
Compilation message
bulldozer.cpp: In function 'void SSM::upd(int, ll, int, int, int)':
bulldozer.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = cl + cr >> 1;
| ~~~^~~~
bulldozer.cpp: In function 'void LineContainer::rev(int, int)':
bulldozer.cpp:63:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(r < ind.size() - 1 && ind[r] < ind[r + 1])
| ~~^~~~~~~~~~~~~~~~
bulldozer.cpp:68:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | if(r < ind.size() - 1 && ind[r] < ind[r + 1])
| ~~^~~~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:97:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto &[a, b, c] : points)
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
