Submission #1138975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138975		bekzhan29	Bulldozer (JOI17_bulldozer)	C++20	80 / 100	685 ms	79012 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF (long long)(2e9)
#define mod2 998244353
#define mod 1000000007
#define eps 1e-9
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<pll, ll> plll;
mt19937 rng(29);
const ll N=2100;
ll n,ch=1,ans,k,pos[N];
struct point
{
	ll x,y,w,pos;
}a[N];
struct line
{
	ll a,b,c,p1,p2;
}lines[N*N];
line get_line(point a, point b)
{
	assert(a.x!=b.x||a.y!=b.y);
	line ans;
	ans.a=a.y-b.y;
	ans.b=b.x-a.x;
	ans.c=-ans.a*a.x-ans.b*a.y;
	return ans;
}
ll dist(point p, line l)
{
	return l.a*p.x+l.b*p.y+l.c;
}
bool cmp_x(point a, point b)
{
	return a.x<b.x;
}
bool cmp_slope(line a, line b)
{
	if(a.b==0)
		return 0;
	if(b.b==0)
		return 1;
	return -a.a*b.b<-b.a*a.b;
}
bool cmp(point a, point b)
{
	return dist(a,lines[0])<dist(b,lines[0]);
}
struct node
{
	ll pr,su,sum,ans;
};
struct segment_tree
{
	// https://github.com/bekzhan29/algos
private:
	int n;
	vector<node> tree;
	node merge(node a, node b)
	{
		node ans;
		ans.sum=a.sum+b.sum;
		ans.pr=max(a.pr,a.sum+b.pr);
		ans.su=max(b.su,b.sum+a.su);
		ans.ans=max({a.ans,b.ans,a.su+b.pr});
		return ans;
	}
	void build_tree(int v, int vl, int vr, point *a)
	{
		if (vl == vr)
		{
			if (a == NULL)
				tree[v] = {0,0,0,0};
			else
				tree[v] = {a[vl].w,a[vl].w,a[vl].w,a[vl].w};
			return;
		}
		int mid = (vl + vr) / 2;
		build_tree(v * 2, vl, mid, a);
		build_tree(v * 2 + 1, mid + 1, vr, a);
		tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
	}
	void upd_tree(int v, int vl, int vr, int pos, ll k)
	{
		if (vl == vr)
		{
			tree[v] = {k,k,k,k};
			return;
		}
		int mid = (vl + vr) / 2;
		if (pos <= mid)
			upd_tree(v * 2, vl, mid, pos, k);
		else
			upd_tree(v * 2 + 1, mid + 1, vr, pos, k);
		tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
	}
	node get_tree(int v, int vl, int vr, int l, int r)
	{
		if (l > r || l > vr || r < vl)
			return {0,0,0,0};
		if (l <= vl && vr <= r)
			return tree[v];
		int mid = (vl + vr) / 2;
		return merge(get_tree(v * 2, vl, mid, l, r), get_tree(v * 2 + 1, mid + 1, vr, l, r));
	}

public:
	void build(int len, point *a=NULL)
	{
		n = len;
		tree.resize(4 * n);
		build_tree(1, 1, n, a);
	}
	void upd(int pos, ll k)
	{
		upd_tree(1, 1, n, pos, k);
	}
	node get(int l, int r)
	{
		return get_tree(1, 1, n, l, r);
	}
};
segment_tree tree;
ll solve()
{
	return tree.get(1,n).ans;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].w;
		a[i].pos=i;
		ch&=a[i].y==0;
	}
	if(ch)
	{
		sort(a+1,a+n+1,&cmp_x);
		for(ll i=1;i<=n;i++)
		{
			ll sum=0;
			for(ll j=i;j<=n;j++)
				sum+=a[j].w,ans=max(ans,sum);
		}
		cout<<ans;
		return 0;
	}
	for(ll i=1;i<=n;i++)
		for(ll j=i+1;j<=n;j++)
		{
			lines[++k]=get_line(a[i],a[j]);
			lines[k].p1=a[i].pos;
			lines[k].p2=a[j].pos;
			if(lines[k].b<0)
				lines[k].a*=-1,lines[k].b*=-1,lines[k].c*=-1;
		}
	sort(lines+1,lines+k+1,&cmp_slope);
	lines[0]={INF,1,0};
	sort(a+1,a+n+1,&cmp);
	tree.build(n,a);
	for(ll i=1;i<=n;i++)
		pos[a[i].pos]=i;
	for(ll i=1;i<=k;i++)
	{
		ans=max(ans,solve());
		
		ll j=max(pos[lines[i].p1],pos[lines[i].p2]);
		swap(a[j],a[j-1]);
		pos[a[j-1].pos]=j-1;
		pos[a[j].pos]=j;
		tree.upd(j-1,a[j-1].w);
		tree.upd(j,a[j].w);
		
		ans=max(ans,solve());
	}
	cout<<ans;
}
/*
5
-5 5 -2
2 5 10
1 4 -2
-2 2 7
4 -5 4

*/

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