Submission #254194

#	Time	Username	Problem	Language	Result	Execution time	Memory
254194		Berted	Coins (LMIO19_monetos)	C++14	39.02 / 100	975 ms	186540 KiB

monetos

#include <iostream>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <random>
#include <vector>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppp pair<pii, pii>
using namespace std;
const int INF = 1e9;

const int cst = 64;

mt19937 rng(1);

int t, n, k1, k2, c;
int ar[351][351], pref[351][351], ans[351][351];
bool bt[351][351];

vector<ppp> v[90301];
vector<ppp> tp;
vector<int> tp2;
queue<pii> q;

int main()
{
	
	cin >> t >> n >> k1 >> k2;

	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> ar[i][n - j + 1];
			c += ar[i][n - j + 1];
		}
		for (int j = 1; j <= n; j++)
		{
			pref[i][j] = pref[i][j - 1] + ar[i][j];
		}
	}
	for (int i = 0; i < n * (n + 1); i++)
	{
		v[i].reserve(2 * cst);
	}
	q.push({0, 0});
	v[0].push_back({{c, 0}, {0, 0}});
	while (q.size())
	{
		pii c = q.front(); q.pop();
		//cout << "COORD : " << c.fst << ", " << c.snd << "\n";

		sort(v[c.fst * (n + 1) + c.snd].begin(), v[c.fst * (n + 1) + c.snd].end());

		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			while (tp.size() && tp.back().fst.fst == x.fst.fst) tp.pop_back();
			while (tp.size() && tp.back().fst.snd <= x.fst.snd) tp.pop_back();
			tp.push_back(x);
		}

		swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();
		for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
		{
			tp2.push_back(i);
		}
		shuffle(tp2.begin(), tp2.end(), rng);
		for (int i = 0; i < min((int)tp2.size(), cst); i++)
		{
			tp.push_back(v[c.fst * (n + 1) + c.snd][tp2[i]]);
		}
		tp2.clear();
		swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();
		/*
		cout << "VECTOR :\n";
		
		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			cout << x.fst.fst << ", " << x.fst.snd << " - " << x.snd.fst << ", " << x.snd.snd << "\n";
		}
		cout << "--\n";
		*/
		

		if (c.fst + 1 < n)
		{
			for (auto x : v[c.fst * (n + 1) + c.snd])
			{
				if (x.fst.fst >= c.snd)
				{
					v[(c.fst + 1) * (n + 1) + c.snd].push_back({{x.fst.fst - c.snd, x.fst.snd + pref[c.fst + 1][c.snd]}, {c.fst, c.snd}});
				}
			}
			if (!bt[c.fst + 1][c.snd])
			{
				bt[c.fst + 1][c.snd] = 1;
				q.push({c.fst + 1, c.snd});
			}
		}
		if (c.snd + 1 <= n)
		{
			for (auto x : v[c.fst * (n + 1) + c.snd])
			{
				if (x.fst.fst)
				{
					v[c.fst * (n + 1) + c.snd + 1].push_back({{x.fst.fst - 1, x.fst.snd + ar[c.fst][c.snd + 1]}, {c.fst, c.snd}});
				}
			}
			if (!bt[c.fst][c.snd + 1])
			{
				bt[c.fst][c.snd + 1] = 1;
				q.push({c.fst, c.snd + 1});
			}
		}
	}

	int mx = -1, mx2; pii c;
	//assert(::c - mx >= k1);
	for (int i = 0; i <= n; i++)
	{
		for (auto x : v[(n - 1) * (n + 1) + i])
		{
			if (x.fst.snd > mx)
			{
				mx = x.fst.snd;
				mx2 = x.fst.fst;
				c = {n - 1, i};	
			}
		}
	}

	//cout << mx << " " << mx2 << "  " << c.fst << ", " << c.snd << "\n";

	while (c != make_pair(0, 0))
	{
		//cout << "LOL : " <<  c.fst << ", " << c.snd << "\n";
		for (auto x : v[c.fst * (n + 1) + c.snd])
		{
			if (x.fst == make_pair(mx2, mx))
			{
				if (x.snd == make_pair(c.fst - 1, c.snd))
				{
					mx = x.fst.snd - pref[c.fst][c.snd];
					mx2 = x.fst.fst + c.snd;
					for (int i = c.snd; i > 0; i--)
					{
						ans[c.fst][i] = 1;
						::c--;
					}
					c = x.snd;
				}
				else
				{
					mx = x.fst.snd - ar[c.fst][c.snd];
					mx2 = x.fst.fst + 1;
					ans[c.fst][c.snd] = 1;
					::c -= (c.snd > 0);
					c = x.snd;
				}
				break;
			}
		}
	}
	/*
	for (int i = 0; i < n; i++)
	{
		for (int j = n; j > 0; j--)
		{
			cout << ans[i][j];
			if (j > 1) cout << " ";
		}
		cout << "\n";
	}
	cout << ::c << "\n";
	*/
	int pv = n;
	for (int i = n - 1; i >= 0 && ::c; i--)
	{
		int cur = 0;
		for (int j = 1; j <= pv && ::c; j++)
		{
			if (ans[i][j] == 1) 
			{
				cur++;
			}
			else 
			{
				ans[i][j] = 1; cur++; ::c--;
			}
		}
		pv = cur;
	}
	// cout << ::c << "\n";
	// assert(::c == 0);

	for (int i = 0; i < n; i++)
	{
		for (int j = n; j > 0; j--)
		{
			cout << ans[i][j];
			if (j > 1) cout << " ";
		}
		cout << "\n";
	}
	return 0;
}

Compilation message (stderr)

monetos.cpp: In function 'int main()':
monetos.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 39.01655540654 / 100