Submission #78724

#	Time	Username	Problem	Language	Result	Execution time	Memory
78724		nxteru	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	591 ms	66456 KiB

bulldozer

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct segtree{
  ll s[1<<12],ma[1<<12],mi[1<<12];
  void init(void){
      for(int i=0;i<1<<12;i++){
          s[i]=0;
          ma[i]=-INF;
          mi[i]=INF;
      }
  }
  void up(int a,ll x){
      a+=(1<<11)-1;
      ma[a]=x;
      mi[a]=x;
      while(a>0){
          a=(a-1)/2;
          ma[a]=max(ma[a*2+1],ma[a*2+2]);
          mi[a]=min(mi[a*2+1],mi[a*2+2]);
          s[a]=max(max(s[a*2+1],s[a*2+2]),ma[a*2+2]-mi[a*2+1]);
      }
  }
};
struct poi{
  ll x,y,a,b;
  bool operator<(const poi&q)const{
      if(y*q.x!=q.y*x)return y*q.x<q.y*x;
      if(a!=q.a)return a<q.a;
      return b<q.b;
  }
};
ll n,x[2005],y[2005],w[2005],s[2005],t[2005],ans;
segtree seg;
vector<PP>so;
vector<poi>q;
int main(void){
    seg.init();
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        ll nx,ny,nw;
        scanf("%lld%lld%lld",&nx,&ny,&nw);
        so.PB(PP(P(nx,ny),nw));
    }
    sort(so.begin(),so.end());
    seg.up(0,0);
    for(int i=0;i<n;i++){
        x[i]=so[i].F.F;
        y[i]=so[i].F.S;
        w[i]=so[i].S;
        s[i+1]+=s[i]+w[i];
        seg.up(i+1,s[i+1]);
        t[i]=i+1;
    }
    ans=seg.s[0];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(x[i]-x[j]>0){
                q.PB(poi{x[i]-x[j],y[i]-y[j],min(i,j),max(i,j)});
            }
        }
    }
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();i++){
        int a=q[i].a,b=q[i].b;
        s[t[a]]=s[t[a]]-w[a]+w[b];
        seg.up(t[a],s[t[a]]);
        swap(t[a],t[b]);
        if(i+1==q.size()||q[i].y*q[i+1].x!=q[i+1].y*q[i].x)ans=max(ans,seg.s[0]);
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++){
                 ~^~~~~~~~~
bulldozer.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i+1==q.size()||q[i].y*q[i+1].x!=q[i+1].y*q[i].x)ans=max(ans,seg.s[0]);
            ~~~^~~~~~~~~~
bulldozer.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
bulldozer.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&nx,&ny,&nw);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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