Submission #800136

#	Time	Username	Problem	Language	Result	Execution time	Memory
800136		LittleCube	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	560 ms	88276 KiB

tickets

    #include "tickets.h"
    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define F first
    #define S second
    #define ll long long
    using namespace std;
     
    int pcnt[1500];
    vector<int> pos[1500], neg[1500];
     
    ll find_maximum(int k, vector<vector<int>> x)
    {
    	int n = x.size();
    	int m = x[0].size();
    	vector<vector<pii>> a;
    	vector<vector<int>> answer;
    	a.resize(n), answer.resize(n);
    	priority_queue<pii> pq;
    	ll ans = 0;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < k; j++)
    			ans -= x[i][j];
    		pq.push(pii(x[i][m - 1] + x[i][k - 1], i));
    	}
    	for (int t = 1; t <= n / 2 * k; t++)
    	{
    		auto [val, i] = pq.top();
    		pq.pop();
    		ans += val;
    		pcnt[i]++;
    		if (pcnt[i] < k)
    			pq.push(pii(x[i][m - 1 - pcnt[i]] + x[i][k - 1 - pcnt[i]], i));
    	}
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < k - pcnt[i]; j++)
    			neg[i].emplace_back(j);
    		for (int j = 0; j < pcnt[i]; j++)
    			pos[i].emplace_back(m - j - 1);
    	}
    	for (int i = 0; i < n; i++)
    		answer[i].resize(m, -1);
     
    	for (int i = 0; i < k; i++)
    	{
    		vector<int> vis(n, 0);
    		int l = n / 2, r = n / 2;
    		for (int j = 0; j < n; j++)
    			if (pos[j].empty())
    			{
    				r--;
    				answer[j][neg[j].back()] = i;
    				neg[j].pop_back();
    				vis[j] = 1;
    			}
    			else if (neg[j].empty())
    			{
    				l--;
    				answer[j][pos[j].back()] = i;
    				pos[j].pop_back();
    				vis[j] = 1;
    			}
    		for (int j = 0; j < n; j++)
    			if (!vis[j])
    			{
    				if (l)
    				{
    					l--;
    					answer[j][pos[j].back()] = i;
    					pos[j].pop_back();
    				}
    				else
    				{
    					r--;
    					answer[j][neg[j].back()] = i;
    					neg[j].pop_back();
    				}
    			}
    	}
    	allocate_tickets(answer);
    	return ans;
    }

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10