Submission #1183947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183947		catch_me_if_you_can	Bulldozer (JOI17_bulldozer)	C++20	80 / 100	1651 ms	172936 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e3+5;
const int INF = 2e18;

struct ndata
{
	int L, R, S, T;
};

ndata create(int x)
{
	ndata ret;
	ret.L = ret.R = ret.S = max(x, 0ll);
	ret.T = x;
	return ret;
}

void rev(ndata &d)
{
	swap(d.L, d.R);
	return;
}

ndata merge(const ndata &d1, const ndata &d2)
{
	ndata d3;
	d3.L = max(d1.L, d1.T + d2.L);
	d3.R = max(d2.R, d2.T + d1.R);
	d3.S = max(max(d1.S, d2.S), d1.R + d2.L);
	d3.T = d1.T + d2.T;
	return d3;
}

struct seg_tree
{
	vector<ndata> tree;

	void build(const vector<int> &a, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{
			tree[id] = create(a[m]);
			return;
		}	
		build(a, 2*id, l, m);
		build(a, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}

	void init(int n, const vector<int> &a)
	{
		tree.resize(4*n+50);
		build(a, 1, 1, n);
		return;
	}

	void upd(int p, int val, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = create(val);
			return;
		}
		int m = (l+r)/2;
		if(p <= m)
			upd(p, val, 2*id, l, m);
		else
			upd(p, val, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}

	int Q()
	{
		return tree[1].S;
	}
};

in sloppy(in pt1, in pt2)
{
	in zz = {pt1[1]-pt2[1], pt1[0]-pt2[0]};
	if(zz[1] < 0)
	{
		zz[1] = -zz[1];
		zz[0] = -zz[0];
	}
	if(zz[1] == 0)
		return {1, 0};
	int g = __gcd(abs(zz[1]), abs(zz[0]));
	zz[1]/=g;
	zz[0]/=g;
	return zz;
}

bool comp(array<int, 4> s1, array<int, 4> s2)
{
	int XX = s1[0]*s2[1];
	int YY = s2[0]*s1[1];
	if(XX < YY)
		return true;
	if(XX > YY)
		return false;
	return (((in){s1[3], s1[4]}) < ((in){s2[3], s2[4]}));
}

int dot(in x1, in x2)
{
	return x1[0]*x2[0] - x1[1]*x2[1];
}

signed main()
{
	fast();
	int n; cin >> n;
	vector<in> pt(n+1);
	vector<int> w(n+1);
	bool wtf = true;
	for(int i = 1; i <= n; i++)
	{
		cin >> pt[i][0] >> pt[i][1] >> w[i];
		wtf = wtf&(pt[i][1] == 0);
	}
	if(n == 1)
	{
		cout << max(w[1], 0ll) << "\n";
		return 0;	
	}
	if(wtf)
	{
		vector<in> nup(n+1);
		for(int i = 1; i <= n; i++)	
			nup[i] = {pt[i][0], w[i]};
		sort(nup.begin()+1, nup.end());
		vector<int> b(n+1);
		for(int i = 1; i <= n; i++)
			b[i] = nup[i][1];
		seg_tree work;
		work.init(n, b);
		cout << work.Q() << endl;
		return 0;
	}
	vector<array<int, 4>> GG;
	for(int i = 1; i <= n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			auto [x, y] = sloppy(pt[i], pt[j]);
			GG.pb({x, y, i, j});
		}
	}
	sort(GG.begin(), GG.end(), comp);
	vector<vector<in>> ff;
	in lst = {-1, -1};
	in st = {GG[0][0], GG[0][1]};
	for(auto [x, y, i, j]: GG)
	{
		//cout << x << " " << y << endl;
		if(((in){x, y}) == lst)
			ff.back().pb({i, j});
		else
		{
			ff.pb({{i, j}});
			lst = {x, y};
		}
	}
	/*for(auto s: ff)
	{
		cout << "Next set: " << endl;
		for(auto [i, j]: s)
			cout << pt[i][0] << " "  << pt[i][1] << " " << pt[j][0] << " " << pt[j][1] << endl;
	}*/
	
	vector<int> where(n+1);
	vector<in> srt(n+1);
	for(int i = 1; i <= n; i++)
		srt[i] = {dot(pt[i], st), i};
	sort(srt.begin()+1, srt.end());
	vector<int> s(n+1);
	for(int i = 1; i <= n; i++)
	{
		s[i] = w[srt[i][1]];
		where[srt[i][1]] = i;
	}
	seg_tree work;
	work.init(n, s);
	int ANS = work.Q(); 
	if(ff.size() == 1)
	{
		cout << ANS << "\n";	
		return 0;
	}
	//cout << st[0] << " " << st[1] << endl;
	for(auto T: ff)
	{
		//cout << "Current perm " << endl;
		vector<int> WTF(n+1);
		/*for(int i = 1; i <= n; i++)
			WTF[where[i]] = i;
		for(int i = 1; i <= n; i++)
			cout << WTF[i] << " ";
		cout << endl;*/
		for(auto [i, j]: T)
		{
			work.upd(where[i], w[j], 1, 1, n);
			work.upd(where[j], w[i], 1, 1, n);
			swap(where[i], where[j]);
			//assert(abs(where[i]-where[j]) == 1);
		}
		ANS = max(ANS, work.Q());
	}
	cout << ANS << "\n";
	return 0;
}	

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