#include<bits/stdc++.h>
using namespace std;
const int nmax=2e3+42;
struct info
{
long long x,y,gain;
};
int n;
info inp[nmax];
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
return a.first*b.second<a.second*b.first;
}
pair<long long,long long> cur;
bool eq(info u,info v)
{
return (u.x-v.x)*cur.second==cur.first*(u.y-v.y);
}
bool cmp_2(info u,info v)
{
return (u.x-v.x)*cur.second<cur.first*(u.y-v.y);
}
long long solve(pair<long long,long long> a)
{
cur=a;
sort(inp+1,inp+n+1,cmp_2);
long long ret=0,cur_best=0,sum_now=0;
for(int i=1;i<=n;i++)
{
sum_now+=inp[i].gain;
if(eq(inp[i],inp[i+1])==0||i==n)
{
cur_best=max(cur_best+sum_now,sum_now);
sum_now=0;
}
ret=max(ret,cur_best);
}
return ret;
}
struct line
{
int i,j;
long long up;
long long down;
};
vector<line> all,help;
bool eq_line(line u,line v)
{
return u.up*v.down==u.down*v.up;
}
bool cmp_line(line a,line b)
{
if(a.up*b.down!=a.down*b.up)return a.up*b.down<a.down*b.up;
if(a.j!=b.j)return a.j>b.j;
return a.i>b.i;
}
struct mem
{
long long sum,mx_pref,mx_suff,mx_interval;
};
mem tree[4*nmax];
mem my_merge(mem a,mem b)
{
mem ret;
ret.sum=a.sum+b.sum;
ret.mx_pref=max(a.mx_pref,a.sum+b.mx_pref);
ret.mx_suff=max(b.mx_suff,b.sum+a.mx_suff);
ret.mx_interval=max(a.mx_interval,b.mx_interval);
ret.mx_interval=max(ret.mx_interval,a.mx_suff+b.mx_pref);
return ret;
}
void update(int node,int l,int r,int pos,long long add)
{
if(l==r)
{
tree[node].sum+=add;
tree[node].mx_pref=max(tree[node].sum,0LL);
tree[node].mx_suff=max(tree[node].sum,0LL);
tree[node].mx_interval=max(tree[node].sum,0LL);
return;
}
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,add);
else update(node*2+1,av+1,r,pos,add);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
int where[nmax];
int main()
{
scanf("%i",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);
if(n==1)
{
printf("%lld\n",max(0LL,inp[1].gain));
return 0;
}
pair<long long,long long> start={0,1};
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
long long up=inp[i].x-inp[j].x;
long long down=inp[i].y-inp[j].y;
if(down)
{
long long g=__gcd(abs(up),abs(down));
up=up/g;
down=down/g;
if(down<0)down=-down,up=-up;
if(up*start.second<down*start.first)start={up,down};
}
}
start.first--;
long long outp=0;
outp=max(outp,solve(start));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
line cur;
cur.i=i;
cur.j=j;
long long up=inp[i].x-inp[j].x;
long long down=inp[i].y-inp[j].y;
if(down)
{
long long g=__gcd(abs(up),abs(down));
up=up/g;
down=down/g;
if(down<0)down=-down,up=-up;
cur.up=up;
cur.down=down;
all.push_back(cur);
}
}
if(all.size())
{
sort(all.begin(),all.end(),cmp_line);
help.push_back(all[0]);
for(auto k:all)
if(k.i!=help.back().i||k.j!=help.back().j)help.push_back(k);
all=help;
}
for(int i=1;i<=n;i++)
{
where[i]=i;
update(1,1,n,i,inp[i].gain);
}
for(int i=0;i<all.size();i++)
{
int j=i;
for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
{
int le=where[all[j].i];
int ri=where[all[j].j];
/*
cout<<all[j].i<<" "<<all[j].j<<" -> "<<le<<" "<<ri<<" "<<all[j].up<<" "<<all[j].down<<endl;
for(int t=1;t<=n;t++)cout<<where[t]<<" ";cout<<endl;
*/
assert(abs(le-ri)==1);
update(1,1,n,le,-inp[le].gain);
update(1,1,n,ri,-inp[ri].gain);
swap(where[all[j].i],where[all[j].j]);
swap(inp[le],inp[ri]);
update(1,1,n,le,+inp[le].gain);
update(1,1,n,ri,+inp[ri].gain);
}
i=j-1;
outp=max(outp,tree[1].mx_interval);
}
printf("%lld\n",outp);
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:197:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for(int i=0;i<all.size();i++)
| ~^~~~~~~~~~~
bulldozer.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
| ~^~~~~~~~~~~
bulldozer.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
117 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
bulldozer.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
768 KB |
Output is correct |
3 |
Correct |
7 ms |
768 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
7 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
0 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
6 ms |
704 KB |
Output is correct |
22 |
Correct |
7 ms |
704 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
5 ms |
768 KB |
Output is correct |
25 |
Correct |
10 ms |
768 KB |
Output is correct |
26 |
Correct |
7 ms |
704 KB |
Output is correct |
27 |
Correct |
6 ms |
768 KB |
Output is correct |
28 |
Correct |
5 ms |
768 KB |
Output is correct |
29 |
Correct |
6 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
768 KB |
Output is correct |
31 |
Correct |
6 ms |
768 KB |
Output is correct |
32 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
768 KB |
Output is correct |
3 |
Correct |
7 ms |
768 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
7 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
0 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
6 ms |
704 KB |
Output is correct |
22 |
Correct |
7 ms |
704 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
5 ms |
768 KB |
Output is correct |
25 |
Correct |
10 ms |
768 KB |
Output is correct |
26 |
Correct |
7 ms |
704 KB |
Output is correct |
27 |
Correct |
6 ms |
768 KB |
Output is correct |
28 |
Correct |
5 ms |
768 KB |
Output is correct |
29 |
Correct |
6 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
768 KB |
Output is correct |
31 |
Correct |
6 ms |
768 KB |
Output is correct |
32 |
Correct |
6 ms |
768 KB |
Output is correct |
33 |
Execution timed out |
2053 ms |
121256 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
768 KB |
Output is correct |
3 |
Correct |
7 ms |
768 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
7 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
7 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
0 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
6 ms |
704 KB |
Output is correct |
22 |
Correct |
7 ms |
704 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
5 ms |
768 KB |
Output is correct |
25 |
Correct |
10 ms |
768 KB |
Output is correct |
26 |
Correct |
7 ms |
704 KB |
Output is correct |
27 |
Correct |
6 ms |
768 KB |
Output is correct |
28 |
Correct |
5 ms |
768 KB |
Output is correct |
29 |
Correct |
6 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
768 KB |
Output is correct |
31 |
Correct |
6 ms |
768 KB |
Output is correct |
32 |
Correct |
6 ms |
768 KB |
Output is correct |
33 |
Execution timed out |
2053 ms |
121256 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
6 ms |
768 KB |
Output is correct |
18 |
Correct |
7 ms |
768 KB |
Output is correct |
19 |
Correct |
6 ms |
768 KB |
Output is correct |
20 |
Correct |
7 ms |
768 KB |
Output is correct |
21 |
Correct |
6 ms |
768 KB |
Output is correct |
22 |
Correct |
6 ms |
768 KB |
Output is correct |
23 |
Correct |
7 ms |
768 KB |
Output is correct |
24 |
Correct |
7 ms |
768 KB |
Output is correct |
25 |
Correct |
6 ms |
768 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
256 KB |
Output is correct |
28 |
Correct |
0 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
0 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
256 KB |
Output is correct |
36 |
Correct |
6 ms |
704 KB |
Output is correct |
37 |
Correct |
7 ms |
704 KB |
Output is correct |
38 |
Correct |
6 ms |
768 KB |
Output is correct |
39 |
Correct |
5 ms |
768 KB |
Output is correct |
40 |
Correct |
10 ms |
768 KB |
Output is correct |
41 |
Correct |
7 ms |
704 KB |
Output is correct |
42 |
Correct |
6 ms |
768 KB |
Output is correct |
43 |
Correct |
5 ms |
768 KB |
Output is correct |
44 |
Correct |
6 ms |
896 KB |
Output is correct |
45 |
Correct |
6 ms |
768 KB |
Output is correct |
46 |
Correct |
6 ms |
768 KB |
Output is correct |
47 |
Correct |
6 ms |
768 KB |
Output is correct |
48 |
Execution timed out |
2053 ms |
121256 KB |
Time limit exceeded |
49 |
Halted |
0 ms |
0 KB |
- |