Submission #948724

#	Time	Username	Problem	Language	Result	Execution time	Memory
948724		shenfe1	Bulldozer (JOI17_bulldozer)	C++17	80 / 100	2045 ms	41752 KiB

bulldozer

#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll

const int MAX=2000+15;
const int B=500;
const int maxB=1000;
const int N=104;
const int block=450;
const ll inf=1e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int x[MAX],y[MAX],a[MAX];
vector<pair<double,pii>> slope;
vector<pair<pii,int>> vec;
int pos[MAX],rev[MAX];
int f[MAX];
int p[MAX],mn[MAX],mx[MAX];

struct segtree{
  struct node{
    ll pref,suf,sum,ans;
    node(){
      pref=suf=sum=ans=0;
    }
  }t[4*MAX];

  node mrg(node a,node b){
    node res;
    res.sum=a.sum+b.sum;
    res.ans=max({a.ans,b.ans,a.suf+b.pref});
    res.suf=max(b.suf,b.sum+a.suf);
    res.pref=max(a.pref,a.sum+b.pref);
    return res;
  } 

  void update(int v,int tl,int tr,int pos,ll x){
    if(tl==tr){
      t[v].pref=max(0ll,x);
      t[v].suf=max(0ll,x);
      t[v].ans=max(0ll,x);
      t[v].sum=x;
      return;
    }
    int tm=(tl+tr)/2;
    if(pos<=tm)update(2*v,tl,tm,pos,x);
    else update(2*v+1,tm+1,tr,pos,x);
    t[v]=mrg(t[2*v],t[2*v+1]);
  }
}t;

vector<int> vv[MAX];
vector<int> can;

void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>y[i]>>a[i];
    vec.pb({{x[i],-y[i]},i});
  }
  sort(all(vec));
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(x[vec[i-1].S]!=x[vec[j-1].S]){
        double k=(0.0+y[vec[i-1].S]-y[vec[j-1].S])/(x[vec[i-1].S]-x[vec[j-1].S]);
        slope.pb({k,{vec[i-1].S,vec[j-1].S}});
      }
      else{
        slope.pb({-inf,{vec[i-1].S,vec[j-1].S}});
      }
    }
  }
  for(int i=0;i<n;i++){
    f[i+1]=a[vec[i].S];
    t.update(1,1,n,i+1,f[i+1]);
    pos[vec[i].S]=i+1;
    rev[i+1]=vec[i].S;
  }
  sort(all(slope));
  // reverse(all(slope));
  ll ans=t.t[1].ans;
  for(int k=0;k<sz(slope);k++){
    int i=slope[k].S.F,j=slope[k].S.S;
    i=pos[i];
    j=pos[j];
    if(i>j)swap(i,j);
    // cout<<"!! "<<slope[k].F<<" "<<i<<" "<<j<<"\n";
    vv[i].pb(j);
    can.pb(i);
    if(k==sz(slope)-1||slope[k].F!=slope[k+1].F){
      int r=-1;
      int lef=0;
      sort(all(can));
      for(int l:can){
        if(l<=r){
          while(!vv[l].empty()){
            // cout<<l<<" "<<vv[l].back()<<"\n";
            r=max(r,vv[l].back());
            vv[l].ppb();
          }
        }
        else{
          if(lef<=r){
            reverse(f+lef,f+r+1);
            reverse(rev+lef,rev+r+1);
            // cout<<lef<<" "<<r<<"\n";
            for(int d=lef;d<=r;d++){
              pos[rev[d]]=d;
              t.update(1,1,n,d,f[d]);
            }
          }
          lef=l;
          r=-1;
          while(!vv[l].empty()){
            r=max(r,vv[l].back());
            vv[l].ppb();
          }
        }
      }
      if(lef<=r){
        reverse(f+lef,f+r+1);
        reverse(rev+lef,rev+r+1);
        // cout<<lef<<" "<<r<<"\n";
        for(int d=lef;d<=r;d++){
          pos[rev[d]]=d;
          t.update(1,1,n,d,f[d]);
        }
      }
      can.clear();
      ans=max(ans,t.t[1].ans);
      // for(int i=1;i<=n;i++)cout<<f[i]<<" ";
      // cout<<"\n";
    }
    // cout<<t.t[1].ans<<"\n";
    // for(int i=1;i<=n;i++){
    //   cout<<f[i]<<" ";
    // }
    // cout<<"\n";
  }
  cout<<ans<<"\n";
}

signed main(){
  // freopen("triangles.in","r",stdin);
  // freopen("triangles.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

bulldozer.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
bulldozer.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

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