| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 590535 |
2022-07-06T05:44:02 Z |
조영욱(#8414) |
Bulldozer (JOI17_bulldozer) |
C++17 |
|
5 ms |
768 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef pair<P,int> Pi;
Pi arr[2000];
Pi arr1[2000];
typedef pair<P,P> PP;
vector<PP> vec;
long long ccw(P a,P b,P c) {
return 1LL*a.first*b.second+1LL*b.first*c.second+1LL*c.first*a.second-1LL*a.second*b.first-1LL*b.second*c.first-1LL*c.second*a.first;
}
bool comp(PP a,PP b) {
return 1LL*a.first.first*b.first.second-1LL*a.first.second*b.first.first>0;
}
bool comp1(Pi a,Pi b) {
if (a.first.first==b.first.first) {
return a.first.second<b.first.second;
}
return a.first.first<b.first.first;
}
int pos[2000];
int rev[2000];
struct Node {
long long lsum,rsum,lrsum,sum;
};
const int sz=2048;
Node seg[sz*2];
Node merge(Node l,Node r) {
Node ret;
ret.lsum=max(l.lsum,l.sum+r.lsum);
ret.rsum=max(r.rsum,r.sum+l.rsum);
ret.lrsum=max({l.lrsum,r.lrsum,l.rsum+r.lsum});
ret.sum=l.sum+r.sum;
return ret;
}
Node sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return {0,0,0,0};
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return merge(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,int val) {
i+=sz;
seg[i]={val<0?0:val,val<0?0:val,val<0?0:val,val};
while (i>1) {
i/=2;
seg[i]=merge(seg[i*2],seg[i*2+1]);
}
}
main() {
int n;
scanf("%lld",&n);
for(int i=0;i<n;i++) {
scanf("%lld %lld %lld",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
arr1[i]=Pi(arr[i].first,i);
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
int dx=arr[j].first.first-arr[i].first.first;
int dy=arr[j].first.second-arr[i].first.second;
swap(dx,dy);
dy=-dy;
if (dy<0) {
dy=-dy;
dx=-dx;
}
if (dy==0&&dx>0) {
dx=-dx;
}
//printf("%d %d %d %d\n",i,j,dx,dy);
vec.push_back(PP(P(dx,dy),P(i,j)));
}
}
sort(vec.begin(),vec.end(),comp);
sort(arr1,arr1+n,comp1);
for(int i=0;i<n;i++) {
pos[arr1[i].second]=i;
rev[i]=arr1[i].second;
update(i,arr[rev[i]].second);
}
vector<int> temp;
long long ret=0;
for(int ind=0;ind<vec.size();ind++) {
//printf("%d %d\n",pos[vec[ind].second.first],pos[vec[ind].second.second]);
ret=max(ret,sum(0,n-1).lrsum);
PP now=vec[ind];
temp.push_back(pos[vec[ind].second.first]);
temp.push_back(pos[vec[ind].second.second]);
if (ind+1!=vec.size()&&(!comp(vec[ind],vec[ind+1])&&!comp(vec[ind+1],vec[ind]))) {
continue;
}
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(),temp.end()),temp.end());
//printf("%d\n",temp.size());
int in=0;
while (in<temp.size()) {
int mnpos=temp[in];
in++;
while (1) {
if (in+1==temp.size()) {
break;
}
int pr=rev[temp[in-1]];
int now=rev[temp[in]];
int nt=rev[temp[in+1]];
if (ccw(arr[pr].first,arr[now].first,arr[nt].first)!=0) {
break;
}
in++;
}
int mxpos=temp[in];
for(int i=mnpos;i<=mxpos;i++) {
update(i,0);
}
for(int i=mnpos;i<=mxpos;i++) {
int j=mnpos+mxpos-i;
if (i>=j) {
break;
}
swap(rev[i],rev[j]);
pos[rev[i]]=i;
pos[rev[j]]=j;
update(i,arr[rev[i]].second);
update(j,arr[rev[j]].second);
}
in++;
}
temp.clear();
}
printf("%lld",ret);
return 0;
}
Compilation message
bulldozer.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
67 | main() {
| ^~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:100:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int ind=0;ind<vec.size();ind++) {
| ~~~^~~~~~~~~~~
bulldozer.cpp:106:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if (ind+1!=vec.size()&&(!comp(vec[ind],vec[ind+1])&&!comp(vec[ind+1],vec[ind]))) {
| ~~~~~^~~~~~~~~~~~
bulldozer.cpp:113:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | while (in<temp.size()) {
| ~~^~~~~~~~~~~~
bulldozer.cpp:117:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | if (in+1==temp.size()) {
| ~~~~^~~~~~~~~~~~~
bulldozer.cpp:103:12: warning: variable 'now' set but not used [-Wunused-but-set-variable]
103 | PP now=vec[ind];
| ^~~
bulldozer.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
bulldozer.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%lld %lld %lld",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
720 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
2 ms |
720 KB |
Output is correct |
| 4 |
Correct |
3 ms |
720 KB |
Output is correct |
| 5 |
Correct |
2 ms |
720 KB |
Output is correct |
| 6 |
Correct |
4 ms |
720 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Correct |
3 ms |
768 KB |
Output is correct |
| 9 |
Correct |
3 ms |
656 KB |
Output is correct |
| 10 |
Correct |
2 ms |
720 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
596 KB |
Output is correct |
| 6 |
Correct |
4 ms |
596 KB |
Output is correct |
| 7 |
Correct |
4 ms |
596 KB |
Output is correct |
| 8 |
Correct |
4 ms |
596 KB |
Output is correct |
| 9 |
Correct |
5 ms |
596 KB |
Output is correct |
| 10 |
Correct |
5 ms |
596 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
224 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
596 KB |
Output is correct |
| 6 |
Correct |
4 ms |
596 KB |
Output is correct |
| 7 |
Correct |
4 ms |
596 KB |
Output is correct |
| 8 |
Correct |
4 ms |
596 KB |
Output is correct |
| 9 |
Correct |
5 ms |
596 KB |
Output is correct |
| 10 |
Correct |
5 ms |
596 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
224 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
596 KB |
Output is correct |
| 6 |
Correct |
4 ms |
596 KB |
Output is correct |
| 7 |
Correct |
4 ms |
596 KB |
Output is correct |
| 8 |
Correct |
4 ms |
596 KB |
Output is correct |
| 9 |
Correct |
5 ms |
596 KB |
Output is correct |
| 10 |
Correct |
5 ms |
596 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
224 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
720 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
2 ms |
720 KB |
Output is correct |
| 4 |
Correct |
3 ms |
720 KB |
Output is correct |
| 5 |
Correct |
2 ms |
720 KB |
Output is correct |
| 6 |
Correct |
4 ms |
720 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Correct |
3 ms |
768 KB |
Output is correct |
| 9 |
Correct |
3 ms |
656 KB |
Output is correct |
| 10 |
Correct |
2 ms |
720 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
