Submission #337434

#	Time	Username	Problem	Language	Result	Execution time	Memory
337434		YJU	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	4 ms	1008 KiB

bulldozer

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e3+5;
const ld pi=acos(-1);
const ll INF=(1LL<<30);
const ld zero=1e-6;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,x[N],y[N],c[N],pos[N],ans,ma[4*N],lma[4*N],rma[4*N],sum[4*N];
vector<ll> lis;
vector<pair<ld,pll> > event;

void mod(ll nda,ll ndb){
	ld cel=asin((y[nda]-y[ndb])/sqrt(SQ(y[nda]-y[ndb])+SQ(x[nda]-x[ndb])));
	cel=(cel+pi/2>2*pi?cel+pi/2-2*pi:cel+pi/2);
	//cout<<nda<<" "<<ndb<<" "<<cel/pi<<"\n";
	event.pb(mp(cel,mp(nda,ndb)));
	cel=(cel+pi>2*pi?cel-pi:cel+pi);
	event.pb(mp(cel,mp(nda,ndb)));
}

void upd(ll id,ll l,ll r,ll to){
	if(l==r-1){ma[id]=lma[id]=rma[id]=max(0LL,c[lis[l]]);sum[id]=c[lis[l]];return ;}
	ll mid=(l+r)>>1;
	if(to<mid)upd(id*2,l,mid,to);
	else upd(id*2+1,mid,r,to);
	sum[id]=sum[id*2]+sum[id*2+1];
	lma[id]=max(lma[id*2],lma[id*2+1]+sum[id*2]);
	rma[id]=max(rma[id*2]+sum[id*2+1],rma[id*2+1]);
	ma[id]=max(max(ma[id*2],ma[id*2+1]),lma[id*2+1]+rma[id*2]);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP(i,n){
		cin>>x[i]>>y[i]>>c[i];
		lis.pb(i);
	}
	sort(lis.begin(),lis.end(),[](ll A,ll B){
		if(x[A]!=x[B])return (x[A]<x[B]);
		return (y[A]>y[B]);
	});
	REP(i,n)pos[lis[i]]=i;
	REP(i,n)upd(1,0,n,i);
	ans=ma[1];
	
	REP(i,n){
		for(int j=i+1;j<n;j++){
			mod(lis[i],lis[j]);
		}
	}
	
	sort(event.begin(),event.end());
	
	//for(auto i:event)cout<<i.Y.X<<" "<<i.Y.Y<<"\n";
	
	REP(i,SZ(event)){
		if(i&&abs(event[i].X-event[i-1].X)<zero)ans=max(ans,ma[1]);
		//cout<<fixed<<setprecision(12)<<event[i].X<<" "<<event[i].Y.X<<" "<<event[i].Y.Y<<"\n";
		//REP(j,n)cout<<lis[j]<<(j==n-1?"\n":" ");
		//cout<<ma[1]<<"\n";
		ll nx=event[i].Y.X,ny=event[i].Y.Y;
		swap(lis[pos[nx]],lis[pos[ny]]);
		upd(1,0,n,pos[nx]);
		upd(1,0,n,pos[ny]);
		swap(pos[nx],pos[ny]);
	}
	cout<<ans<<"\n";
	return 0;
}

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