oj.uz

답안 #590535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590535 2022-07-06T05:44:02 Z 조영욱(#8414) Bulldozer (JOI17_bulldozer) C++17
0 / 100
 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 -