제출 #536329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536329		michao	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	3 ms	724 KiB

bulldozer

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<11;
const int inf=(int)1e18+9;

struct node{
	int pref,suf,sum,maxi;
};

node t[MAX*2];

node merguj(node a,node b){
	node wyn={-inf,-inf,-inf,-inf};
	wyn.sum=a.sum+b.sum;
	wyn.pref=max(a.pref,a.sum+b.pref);
	wyn.suf=max(b.suf,b.sum+a.suf);
	wyn.maxi=max({a.maxi,b.maxi,a.suf+b.pref});
	return wyn;
}

const node neutral={-inf,-inf,0,0};

void update(int u,int c){
	u+=MAX-1;
	t[u]={max(0LL,c),max(0LL,c),c,max(0LL,c)};
	u>>=1;
	while (u){
		t[u]=merguj(t[u<<1],t[(u<<1)|1]);
		u>>=1;
	}
}

node query(int a,int b,int u,int lo,int hi){
	if (b<lo || a>hi)return neutral;
	if (lo>=a && hi<=b)return t[u];
	int mid=(lo+hi)>>1;
	node L=query(a,b,2*u,lo,mid);
	node R=query(a,b,2*u+1,mid+1,hi);
	return merguj(L,R);
}

int getmax(int l,int r){
	return query(l,r,1,1,MAX).maxi;
}

struct point{
	int x,y,w;
	point(int _x,int _y,int _w){
		x=_x,y=_y,w=_w;
	}
	point(){}
};

struct line{
	int id1,id2,diffx,diffy;
	line(int _id1,int _id2,int _diffx,int _diffy){
		id1=_id1;
		id2=_id2;
		diffx=_diffx;
		diffy=_diffy;
	} 
	line(){}
};

bool cmppoint(point p1,point p2){
	return mp(p1.x,p1.y)<mp(p2.x,p2.y);
}

int eval(line l1,line l2){
	return l1.diffy*l2.diffx-(l1.diffx*l2.diffy);
}

bool cmpline(line l1,line l2){
  if (eval(l1,l2)!=0)
		return l1.diffy*l2.diffx<l1.diffx*l2.diffy;
	return mp(l1.id1,l1.id2)<mp(l2.id1,l2.id2);
}
vector<line>l;
int pos[MAX];
int32_t main(){
  BOOST;
  int n;
  cin>>n;
  vector<point>p;
  for (int i=0;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		p.pb(point(x,y,w));
  }
  sort(p.begin(),p.end(),cmppoint);
  for (int i=0;i<sz(p);i++){
		for (int j=i+1;j<sz(p);j++){
			l.pb(line(i,j,p[i].x-p[j].x,p[i].y-p[j].y));
		}
  }
  sort(l.begin(),l.end(),cmpline);
  int ans=0;
  for (int i=0;i<n;i++)pos[i]=i;
  for (int i=0;i<n;i++){
		update(pos[i]+1,p[pos[i]].w);
  }
  ans=max(ans,getmax(1,n));
  for (int i=0;i<sz(l);i++){
		int x=l[i].id1;
		int y=l[i].id2;
		swap(pos[x],pos[y]);
		update(pos[x]+1,p[pos[x]].w);
		update(pos[y]+1,p[pos[y]].w);
		ans=max(ans,getmax(1,n));
  }
  cout<<ans;
  return 0; 
}

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