Submission #787070

#	Time	Username	Problem	Language	Result	Execution time	Memory
787070		Pablo_No	카니발 티켓 (IOI20_tickets)	C++17	27 / 100	657 ms	214136 KiB

tickets

    #include "tickets.h"
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <iostream>
     
    using namespace std;
     
    #define int long long
     
    bool cmp(pair<pair<pair<int, int>, pair<int, int>>, int> a, pair<pair<pair<int, int>, pair<int, int>>, int> b)
    {
    	return a.first.first.first+a.first.second.first < b.first.second.first+b.first.first.first;

    }
     
    long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
    	int n = x.size();
    	int m = x[0].size();
     
    	std::vector<std::vector<signed>> ans(n, vector<signed>(m, -1));
    	long long ansv = 0;
     
    	vector<multiset<pair<int, int>>> sx(n);
     
    	for (int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++)
    			sx[i].insert({x[i][j], j});
    	}
     
    	for(int as = 0; as < k; as++)
    	{
    		vector<pair<pair<pair<int, int>, pair<int, int>>, int>> poss;
    		for(int i = 0; i < n; i++)
    		{
    			poss.push_back({{*sx[i].begin(), *sx[i].rbegin()}, i});
    		}
    		sort(poss.begin(), poss.end(), cmp);
    		int mv = poss[n/2-1].first.first.first;
    		for(int i = 0; i < n/2; i++)
    		{
    			//cout << poss[i].first.first.first << ' ' << poss[i].first.first.second << '\n';
    			ansv += mv-poss[i].first.first.first;
    			ans[poss[i].second][poss[i].first.first.second] = as;
    			if(sx[poss[i].second].find({poss[i].first.first.first, poss[i].first.first.second}) != sx[poss[i].second].end())
    				sx[poss[i].second].erase(sx[poss[i].second].find({poss[i].first.first.first, poss[i].first.first.second}));
    		}
    		for(int i = n/2; i < n; i++)
    		{
    			//cout << poss[i].first.second.first << ' ' << poss[i].first.second.second << '\n';
    			ansv += poss[i].first.second.first-mv;
    			ans[poss[i].second][poss[i].first.second.second] = as;
    			if(sx[poss[i].second].find({poss[i].first.second.first, poss[i].first.second.second}) != sx[poss[i].second].end())
    				sx[poss[i].second].erase(sx[poss[i].second].find({poss[i].first.second.first, poss[i].first.second.second}));
    		}
    	}
     
    	allocate_tickets(ans);
    	return ansv;
    }

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