#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;
struct punct{
int x,y,cost;
} v[DIM];
struct panta{
int a,b,idx,idx2;
};
vector <panta> p;
struct segment_tree{
int best,pref,suf,sum;
} aint[DIM*4];
int n,i,j,k,sol;
int poz[DIM];
void update_nod (int nod){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[nod].sum = aint[fiu_st].sum + aint[fiu_dr].sum;
aint[nod].pref = max (aint[fiu_st].pref, aint[fiu_st].sum + aint[fiu_dr].pref);
aint[nod].suf = max (aint[fiu_dr].suf,aint[fiu_dr].sum + aint[fiu_st].suf);
aint[nod].best = max (aint[fiu_st].best,aint[fiu_dr].best);
aint[nod].best = max (aint[nod].best,aint[fiu_st].suf + aint[fiu_dr].pref);
aint[nod].best = max (aint[nod].best,max(aint[nod].pref,aint[nod].suf));
}
void build (int nod, int st, int dr){
if (st == dr){
aint[nod].sum = v[st].cost;
aint[nod].pref =v[st].cost;
aint[nod].suf = v[st].cost;
aint[nod].best = v[st].cost;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
update_nod(nod);
}
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod].sum = val;
aint[nod].pref = val;
aint[nod].suf = val;
aint[nod].best = val;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
update_nod(nod);
}
inline int cmp (punct a, punct b){
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
inline int cmp2 (panta p1, panta p2){
if (p1.a * p2.b == p1.b * p2.a){
if (p1.idx == p2.idx)
return p1.idx2 < p2.idx2;
return p1.idx < p2.idx;
}
return p1.a * p2.b < p1.b * p2.a;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i].x>>v[i].y>>v[i].cost;
sort (v+1,v+n+1,cmp);
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
p.push_back({v[j].y-v[i].y,v[j].x-v[i].x,i,j});
sort (p.begin(),p.end(),cmp2);
for (i=1;i<=n;i++)
poz[i] = i;
build (1,1,n);
sol = aint[1].best;
i = 0;
while (i < p.size()){
j = i;
while (j < p.size() && p[i].a * p[j].b == p[i].b * p[j].a){
update (1,1,n,poz[p[j].idx2], v[ p[j].idx ].cost);
update (1,1,n,poz[p[j].idx],v[ p[j].idx2 ].cost);
swap (poz[p[j].idx],poz[p[j].idx2]);
j++;
}
sol = max (sol,aint[1].best);
i = j;
}
cout<<sol;
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:108:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while (i < p.size()){
| ~~^~~~~~~~~~
bulldozer.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<panta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while (j < p.size() && p[i].a * p[j].b == p[i].b * p[j].a){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
