#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5+ 5, MOD = 998244353;
#define int ll
int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
void test() {
cin >> n;
for(int i = 1;i <= n;i++){
cin >> x[i] >> y[i] >> w[i];
a.push_back({x[i],-y[i],i});
}
sort(a.begin(),a.end());
for(int i = 0;i < (int)a.size();i++){
pos[a[i][2]] = i + 1;
t[i + 1] = a[i][2];
}
vector<pair<long double,pair<int,int>>> cur;
for(int i = 1;i <= n;i++){
for(int j = i+1;j <= n;j++){
long double val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
cur.push_back({val,{i,j}});
}
}
ll res = 0;
sort(cur.rbegin(),cur.rend());
for(int i = 0;i < (int)cur.size();i++){
vector<pair<int,int>> ss;
for(int j = i;j <= (int)cur.size();j++){
if(j == (int)cur.size() || cur[j].first != cur[i].first){
i = j - 1;
break;
}
int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
pos[cur[j].second.second]);
ss.push_back({L,R});
}
vector<ll> sums;
sort(ss.begin(),ss.end());
ll mn = 0,curs = 0;
ll max_checked;
for(int j = 0;j < (int)ss.size();j++) {
if (j && max_checked >= ss[j].second) continue;
int mx = ss[j].second;
for (int k = j; k <= (int) ss.size(); k++) {
if (k == (int) ss.size() || ss[k].first != ss[j].first) {
j = k - 1;
break;
}
max_checked = ss[k].second;
mx = ss[k].second;
}
int l = ss[j].first, r = mx;
while (l < r) {
swap(t[l], t[r]);
pos[t[l]] = l;
pos[t[r]] = r;
l++;
r--;
}
}
for(int j = 1;j <= n;j++){
curs += w[t[j]];
res = max(res,curs - mn);
mn = min(mn,curs);
}
}
cout << res << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
test();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9304 KB |
Output is correct |
| 9 |
Correct |
4 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 11 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 4 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8924 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8668 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 4 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8924 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8668 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 4 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8924 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8668 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9304 KB |
Output is correct |
| 9 |
Correct |
4 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9052 KB |
Output is correct |
| 11 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
