Submission #1138611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138611		bekzhan29	Bulldozer (JOI17_bulldozer)	C++20	25 / 100	2093 ms	580 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;
struct point
{
	ll x,y,w;
}a[N];
struct line
{
	ll a,b,c;
};
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;
}
bool cmp_x(point a, point b)
{
	return a.x<b.x;
}
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;
		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++)
		{
			ll two=max(0LL,a[i].w)+max(0LL,a[j].w);
			ans=max(ans,two);
			line l=get_line(a[i],a[j]);
			vector<pll>b,c;
			for(ll k=1;k<=n;k++)
				if(k!=i&&k!=j)
				{
					ll d=l.a*a[k].x+l.b*a[k].y+l.c;
					if(d<0)
						b.pb({-d,a[k].w});
					else
						c.pb({d,a[k].w});
				}
			sort(b.begin(),b.end());
			sort(c.begin(),c.end());
			ll sum=two;
			for(pll d:b)
				sum+=d.se,ans=max(ans,sum);
			sum=two;
			for(pll d:c)
				sum+=d.se,ans=max(ans,sum);
		}
	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