Submission #78679

#	Time	Username	Problem	Language	Result	Execution time	Memory
78679		nxteru	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	1745 ms	87040 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 x,y;
  bool operator<(const li&q)const{
      if(y==0)return q.x*q.y>0;
      if(q.y==0)return x*y<0;
      return y*q.x<q.y*x;
  }
};
struct qu{
  ll x,y,k,a,b;
  bool operator<(const qu&q)const{
      if(y*q.x!=q.y*x){
          if(y==0)return q.x*q.y>0;
          if(q.y==0)return x*y<0;
          return y*q.x<q.y*x;
      }
      return k<q.k;
  }
};
struct po{
  ll x,y,i;
  bool operator<(const po&q)const{
      if(x!=q.x)return x>q.x;
      return y>q.y;
  }
};
struct sgt{
  ll x,ma,mi;  
};
ll n,k,x[2005],y[2005],w[2005],pl[2005],ans,seg[1<<12],sma[1<<12],smi[1<<12];
vector<P>line[2005];
map<li,ll>o;
vector<qu>q;
vector<po>poi;
bool vi[2005][2005];
void add(int a,ll c){
    a+=(1<<11)-1;
    sma[a]+=c;
    smi[a]+=c;
    while(a>0){
        a=(a-1)/2;
        sma[a]=max(sma[a*2+1],sma[a*2+2]);
        smi[a]=min(smi[a*2+1],smi[a*2+2]);
        seg[a]=max(max(seg[a*2+1],seg[a*2+2]),sma[a*2+2]-smi[a*2+1]);
    }
}
sgt que(int a,int b,int l,int r,int v){
    if(r<a||b<l)return sgt{0,-INF,INF};
    if(a<=l&&r<=b)return sgt{seg[v],sma[v],smi[v]};
    sgt ls=que(a,b,l,(l+r-1)/2,v*2+1),rs=que(a,b,(l+r+1)/2,r,v*2+2);
    return sgt{max(max(ls.x,rs.x),rs.ma-ls.mi),max(ls.ma,rs.ma),min(ls.mi,rs.mi)};
}
int main(void){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)scanf("%lld%lld%lld",x+i,y+i,w+i);
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++)line[j].clear();
        k=0;
        o.clear();
        for(int j=i+1;j<n;j++){
            if(x[i]==x[j])continue;
            li p={x[i]-x[j],y[i]-y[j]};
            if(o.find(p)==o.end()){
                line[k].PB(P(-x[i],i));
                o[p]=k++;
            }
            line[o[p]].PB(P(-x[j],j));
        }
        for(int l=0;l<k;l++){
            sort(line[l].begin(),line[l].end());
            ll e=0;
            for(int a=0;a<line[l].size();a++){
                for(int b=a+1;b<line[l].size();b++){
                    int v=line[l][a].S,u=line[l][b].S;
                    if(vi[v][u]||vi[u][v])continue;
                    q.PB(qu{x[v]-x[u],y[v]-y[u],e,v,u});
                    e++;
                    vi[v][u]=true;
                    vi[u][v]=true;
                }
            }
        }
    }
    for(int i=0;i<n;i++)poi.PB(po{x[i],y[i],i});
    sort(poi.begin(),poi.end());
    ll s=0;
    for(int i=0;i<n;i++){
        s+=w[poi[i].i];
        pl[poi[i].i]=i+1;
        add(i+1,s);
    }
    ans=max(ans,que(0,n,0,(1<<11)-1,0).x);
    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++){
            ll 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);
        }
        ans=max(ans,que(0,n,0,(1<<11)-1,0).x);
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int a=0;a<line[l].size();a++){
                         ~^~~~~~~~~~~~~~~
bulldozer.cpp:85:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int b=a+1;b<line[l].size();b++){
                               ~^~~~~~~~~~~~~~~
bulldozer.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++){
                 ~^~~~~~~~~
bulldozer.cpp:109: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:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<t.size();j++){
                     ~^~~~~~~~~
bulldozer.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
bulldozer.cpp:67:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++)scanf("%lld%lld%lld",x+i,y+i,w+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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