Submission #78551

#	Time	Username	Problem	Language	Result	Execution time	Memory
78551		nxteru	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	7 ms	764 KiB

bulldozer

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct li{
  ll a,b;
  bool operator<(const li&q)const{
      return b*q.a<q.b*a;
  }
};
struct qu{
  ll x,y,a,b;
  bool operator<(const qu&q)const{
      if(x==0||q.x==0)return x*y>q.x*q.y;
      if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
      return x*y>q.x*q.y;
  }
  bool operator>(const qu&q)const{
      if(x==0||q.x==0)return x*y<q.x*q.y;
      if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
      return x*y<q.x*q.y;
  }
};
struct poi{
  ll x,y,i;
  bool operator<(const poi&q)const{
      if(y!=q.y)return y<q.y;
      return x>q.x;
  }
  bool operator>(const poi&q)const{
      if(y!=q.y)return y>q.y;
      return x<q.x;
  }
};
ll n,x[2005],y[2005],w[2005],k,pl[2005],ans,s[2005];
P seg[1<<12];
vector<P>lin[2005];
map<li,int>o;
vector<qu>q;
vector<poi>po;
void add(int a,ll c){
    a+=(1<<11)-1;
    seg[a].F+=c;
    seg[a].S+=c;
    while(a>0){
        a=(a-1)/2;
        seg[a].F=max(seg[a*2+1].F,seg[a*2+2].F);
        seg[a].S=min(seg[a*2+1].S,seg[a*2+2].S);
    }
}
ll ma(int a,int b,int l,int r,int v){
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return seg[v].F;
    return max(ma(a,b,l,(l+r-1)/2,v*2+1),ma(a,b,(l+r+1)/2,r,v*2+2));
}
ll mi(int a,int b,int l,int r,int v){
    if(r<a||b<l)return INF;
    if(a<=l&&r<=b)return seg[v].S;
    return min(mi(a,b,l,(l+r-1)/2,v*2+1),mi(a,b,(l+r+1)/2,r,v*2+2));
}
int main(void){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld",x+i,y+i,w+i);
        po.PB(poi{x[i],y[i],i});
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++)lin[j].clear();
        k=0;
        o.clear();
        for(int j=i+1;j<n;j++){
            if(y[i]==y[j])continue;
            li z={x[i]-x[j],y[i]-y[j]};
            if(o.find(z)==o.end()){
                lin[k].PB(P(y[i],i));
                o[z]=k++;
            }
            lin[o[z]].PB(P(y[j],j));
        }
        for(int j=0;j<k;j++){
            sort(lin[j].begin(),lin[j].end());
            for(int r=0;r<lin[j].size()-1-r;r++){
                int v=lin[j][r].S,u=lin[j][lin[j].size()-1-r].S;
                q.PB(qu{x[v]-x[u],y[v]-y[u],v,u});
            }
        }
    }
    sort(po.begin(),po.end());
    ll m=0;
    for(int i=0;i<n;i++){
        s[i+1]+=s[i];
        pl[po[i].i]=i+1;
        s[i+1]+=w[po[i].i];
        add(i+1,s[i+1]);
        ans=max(ans,s[i+1]-m);
        m=min(m,s[i+1]);
    }
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();i++){
        vector<P>t;
        t.PB(P(q[i].a,q[i].b));
        while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y*q[i].x){
            i++;
            t.PB(P(q[i].a,q[i].b));
        }
        for(int j=0;j<t.size();j++){
            int a=pl[t[j].F],b=pl[t[j].S],wa=w[t[j].F],wb=w[t[j].S];
            pl[t[j].F]=b;
            pl[t[j].S]=a;
            if(a>b){
                swap(a,b);
                swap(wa,wb);
            }
            add(a,-wa+wb);
            s[a]=s[a]-wa+wb;
        }
        for(int j=0;j<t.size();j++){
            int a=pl[t[j].F],b=pl[t[j].S];
            ans=max(ans,s[a]-mi(0,a,0,(1<<11)-1,0));
            ans=max(ans,ma(a,n,0,(1<<11)-1,0)-s[a-1]);
            ans=max(ans,s[b]-mi(0,b,0,(1<<11)-1,0));
            ans=max(ans,ma(b,n,0,(1<<11)-1,0)-s[b-1]);
        }
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

bulldozer.cpp: In member function 'bool qu::operator<(const qu&) const':
bulldozer.cpp:23:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
       if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
          ~~~^~
bulldozer.cpp: In member function 'bool qu::operator>(const qu&) const':
bulldozer.cpp:28:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
       if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
          ~~~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int r=0;r<lin[j].size()-1-r;r++){
                         ~^~~~~~~~~~~~~~~~~~
bulldozer.cpp:107:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++){
                 ~^~~~~~~~~
bulldozer.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y*q[i].x){
               ~~~^~~~~~~~~
bulldozer.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<t.size();j++){
                     ~^~~~~~~~~
bulldozer.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<t.size();j++){
                     ~^~~~~~~~~
bulldozer.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
bulldozer.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",x+i,y+i,w+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20