Submission #948705

#	Time	Username	Problem	Language	Result	Execution time	Memory
948705		shenfe1	Bulldozer (JOI17_bulldozer)	C++17	60 / 100	2007 ms	36048 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;

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});
  }
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(x[i]!=x[j]){
        ld k=(0.0+y[i]-y[j])/(x[i]-x[j]);
        slope.pb({k,{i,j}});
        // cout<<i<<" "<<j<<" "<<k<<"\n";
      }
    }
  }
  sort(all(vec));
  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;
  // cout<<ans<<"\n";
  int l=n,r=1;
  for(int k=0;k<sz(slope);k++){
    int i=slope[k].S.F,j=slope[k].S.S;
    l=min(l,pos[i]);
    r=max(r,pos[i]);
    l=min(l,pos[j]);
    r=max(r,pos[j]);
    // swap(f[pos[i]],f[pos[j]]);
    // swap(pos[i],pos[j]);
    // t.update(1,1,n,pos[i],f[pos[i]]);
    // t.update(1,1,n,pos[j],f[pos[j]]);
    if(k==sz(slope)-1||slope[k].F!=slope[k+1].F){
      reverse(f+l,f+r+1);
      reverse(rev+l,rev+r+1);
      // cout<<l<<" "<<r<<"\n";
      for(int d=l;d<=r;d++){
        pos[rev[d]]=d;
        t.update(1,1,n,d,f[d]);
      }
      ans=max(ans,t.t[1].ans);
      l=n;
      r=1;
    }
    // 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: 0 / 20
• Subtask 5: 0 / 20