#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=987654321987654321;
LL gcd(LL a, LL b){return b?gcd(b, a%b):a;}
struct Q{
int buho;
LL p, q; //p/q
bool operator<(const Q &b){
if(buho!=b.buho)return buho<b.buho;
return p*b.q<b.p*q;
}
bool operator==(const Q &b){
return buho==b.buho&&p==b.p&&q==b.q;
}
};
int n;
pair<pll, int> point[2010];
vector<pair<Q, pii> > vc;
LL arr[2010];
int now[2010];
bool comp(pii a, pii b){
if(a.F==b.F)return now[a.S]<now[b.S];
return now[a.F]<now[b.F];
}
bool cmp(pair<Q, pii> a, pair<Q, pii> b){
if(a.F==b.F)return a.S>b.S;
return !(a.F<b.F);
}
bool cmp2(pair<pll, int> a, pair<pll, int> b){
if(a.F.F==b.F.F)return a.F.S>b.F.S;
return a.F.F<b.F.F;
}
struct SEGMENT_TREE {
struct NODE {
int st, fin;
LL lmax, rmax, tmax, sum;
} tree[15000];
int x;
void maketree(int point, int num) {
if(num==1)tree[point].st=tree[point].fin=++x;
if(num<=1)return;
maketree(point*2, num-num/2);
maketree(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
void updaterange(int point, int num, LL p) {
if(tree[point].st==tree[point].fin) {
tree[point].lmax=p;
tree[point].rmax=p;
tree[point].tmax=p;
tree[point].sum=p;
return;
}
if(num<=tree[point*2].fin)updaterange(point*2, num, p);
else updaterange(point*2+1, num, p);
tree[point].lmax=max(tree[point*2].lmax, tree[point*2].sum+tree[point*2+1].lmax);
tree[point].rmax=max(tree[point*2+1].rmax, tree[point*2+1].sum+tree[point*2].rmax);
tree[point].sum=tree[point*2].sum+tree[point*2+1].sum;
tree[point].tmax=max(max(tree[point*2].tmax, tree[point*2+1].tmax), max(tree[point*2].rmax+tree[point*2+1].lmax, max(tree[point].lmax, tree[point].rmax)));
}
LL ql(int point, int a, int b){
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].lmax;
if(tree[point].st>b||tree[point].fin<a)return -llinf;
return max(ql(point*2, a, b), qs(point*2, a, b)+ql(point*2+1, a, b));
}
LL qr(int point, int a, int b){
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].rmax;
if(tree[point].st>b||tree[point].fin<a)return -llinf;
return max(qr(point*2+1, a, b), qs(point*2+1, a, b)+qr(point*2, a, b));
}
LL qt(int point, int a, int b){
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].tmax;
if(tree[point].st>b||tree[point].fin<a)return -llinf;
return max(max(qt(point*2, a, b), qt(point*2+1, a, b)), max(qr(point*2, a, b)+ql(point*2+1, a, b), max(ql(point, a, b), qr(point, a, b))));
}
LL qs(int point, int a, int b){
if(a>b)return 0;
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].sum;
if(tree[point].st>b||tree[point].fin<a)return 0;
return qs(point*2, a, b)+qs(point*2+1, a, b);
}
void update(int a, LL num) {
updaterange(1, a, num);
}
}seg;
//seg.qt(1, 1, idy.size())
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %lld %lld", &point[i].F.F, &point[i].F.S, &arr[i]);
point[i].S=i;
}
seg.maketree(1, n);
for(int i=1; i<=n; i++){
for(int j=1; j<i; j++){
LL tx=point[i].F.F-point[j].F.F;
LL ty=point[i].F.S-point[j].F.S;
if(tx==0)continue;
Q temp;
if(tx*ty>0)temp.buho=1;
else if(tx*ty==0)temp.buho=0;
else temp.buho=-1;
LL gcdd=gcd(llabs(tx), llabs(ty));
tx=llabs(tx)/gcdd;
ty=llabs(ty)/gcdd;
temp.p=ty;
temp.q=tx;
vc.pb(mp(temp, mp(j, i)));
}
}
sort(point+1, point+n+1, cmp2);
sort(vc.begin(), vc.end(), cmp);
/*for(int i=0; i<vc.size(); i++){
printf("%lld/%lld : %c <-> %c\n", vc[i].F.p, vc[i].F.q, 'A'-1+vc[i].S.F, 'A'-1+vc[i].S.S);
}*/
for(int i=1; i<=n; i++){
seg.update(i, arr[point[i].S]);
now[point[i].S]=i;
}
LL ans=max(0ll, seg.qt(1, 1, n));
int pv=0;
while(pv<vc.size()){
vector<pii> tem;
//puts("----");
for(; pv<vc.size(); pv++){
if(now[vc[pv].S.F]<now[vc[pv].S.S]){
tem.pb(mp(vc[pv].S.F, vc[pv].S.S));
//printf("swapping %c %c\n", 'A'-1+vc[pv].S.F, 'A'-1+vc[pv].S.S);
}
else{
tem.pb(mp(vc[pv].S.S, vc[pv].S.F));
//printf("swapping %c %c\n", 'A'-1+vc[pv].S.S, 'A'-1+vc[pv].S.F);
}
if(pv==vc.size()-1){
pv++;
break;
}
if(!(vc[pv].F==vc[pv+1].F)){
pv++;
break;
}
}
sort(tem.begin(), tem.end(), comp);
for(int j=0; j<tem.size(); j++){
LL temp=seg.ql(1, now[tem[j].F], now[tem[j].F]);
seg.update(now[tem[j].F], seg.ql(1, now[tem[j].S], now[tem[j].S]));
seg.update(now[tem[j].S], temp);
swap(now[tem[j].F], now[tem[j].S]);
}
/*for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(now[j]==i)printf("%c ", j+'A'-1);
}
}
puts("");
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(now[j]==i)printf("%d ", arr[j]);
}
}*/
//puts("");
LL temp=seg.qt(1, 1, n);
//printf("ANS : %lld\n", temp);
ans=max(ans, temp);
//puts("----");
}
printf("%lld", ans);
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:132:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pv<vc.size()){
~~^~~~~~~~~~
bulldozer.cpp:135:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; pv<vc.size(); pv++){
~~^~~~~~~~~~
bulldozer.cpp:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pv==vc.size()-1){
~~^~~~~~~~~~~~~
bulldozer.cpp:154:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<tem.size(); j++){
~^~~~~~~~~~~
bulldozer.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
bulldozer.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &point[i].F.F, &point[i].F.S, &arr[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
760 KB |
Output is correct |
| 3 |
Correct |
8 ms |
760 KB |
Output is correct |
| 4 |
Correct |
7 ms |
760 KB |
Output is correct |
| 5 |
Correct |
8 ms |
760 KB |
Output is correct |
| 6 |
Correct |
7 ms |
760 KB |
Output is correct |
| 7 |
Correct |
7 ms |
764 KB |
Output is correct |
| 8 |
Correct |
7 ms |
760 KB |
Output is correct |
| 9 |
Correct |
8 ms |
760 KB |
Output is correct |
| 10 |
Correct |
7 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
760 KB |
Output is correct |
| 3 |
Correct |
8 ms |
760 KB |
Output is correct |
| 4 |
Correct |
7 ms |
760 KB |
Output is correct |
| 5 |
Correct |
8 ms |
760 KB |
Output is correct |
| 6 |
Correct |
7 ms |
760 KB |
Output is correct |
| 7 |
Correct |
7 ms |
764 KB |
Output is correct |
| 8 |
Correct |
7 ms |
760 KB |
Output is correct |
| 9 |
Correct |
8 ms |
760 KB |
Output is correct |
| 10 |
Correct |
7 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Incorrect |
9 ms |
760 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
