제출 #1138970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138970		bekzhan29	Bulldozer (JOI17_bulldozer)	C++20	25 / 100	2098 ms	78752 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]);
}
ll solve()
{
	ll ans=0;
	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);
	}
	return 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);
	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;
		
		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: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20