Submission #425288

#	Time	Username	Problem	Language	Result	Execution time	Memory
425288		muhammad_hokimiyon	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	2244 ms	63580 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

long long find_maximum(int k, std::vector<std::vector<int>> X) {
	int n = X.size();
	int m = X[0].size();
        vector<vector<int>> ans(n, vector<int>(m, -1));
        long long res = 0;
        set<pair<int, int>> s;
        vector<int> fi(n, k - 1);
        vector<int> ls(n, m - 1);
        vector<int> coun(n, k);
        for(int i = 0; i < n; i++){
                s.insert({X[i][fi[i]] + X[i][m - 1], i});
                for(int j = 0; j < k; j++)res -= X[i][j];
        }
        int cnt = 0;
        vector<pair<int, int>> A,B;
        while(cnt < n * k / 2){
                cnt++;
                auto x = *(--s.end());
                res += x.first;
                s.erase(--s.end());
                A.push_back({x.second, ls[x.second]});
                fi[x.second]--,ls[x.second]--;
                coun[x.second]--;
                if(coun[x.second] > 0){
                        s.insert({X[x.second][fi[x.second]] + X[x.second][ls[x.second]], x.second});
                }
        }
        for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++)X[i][j] = 0;
        }
        for(auto x : A){
                X[x.first][x.second] = 1;
        }
        for(int i = 0; i < n; i++){
                for(int j = 0; j <= fi[i]; j++)B.push_back({i, j});
        }
        for(auto x : B){
                X[x.first][x.second] = 2;
        }
        cnt = 0;
        vector<vector<int>> c(n, vector<int>(2, 0));
        for(auto x : A){
                c[x.first][0]++;
        }
        for(auto x : B){
                c[x.first][1]++;
        }
        while(cnt < k){
                int c1 = 0, c2 = 0;
                vector<int> us(n, false);
                for(int i = 0; i < n; i++){
                        if(c[i][0] && !c[i][1] && c1 < n / 2){
                                c[i][0]--;
                                c1++;
                                us[i] = true;
                                for(int j = 0; j < m; j++){
                                        if(X[i][j] == 1){
                                                X[i][j] = 0;
                                                ans[i][j] = cnt;
                                                break;
                                        }
                                }
                        }
                        if(!c[i][0] && c[i][1] && c2 < n / 2){
                                c[i][1]--;
                                c2++;
                                us[i] = true;
                                for(int j = 0; j < m; j++){
                                        if(X[i][j] == 2){
                                                X[i][j] = 0;
                                                ans[i][j] = cnt;
                                                break;
                                        }
                                }
                        }
                }
                for(int i = 0; i < n; i++){
                        if(us[i])continue;
                        if(c[i][0] && c1 < n / 2){
                                c[i][0]--;
                                c1++;
                                for(int j = 0; j < m; j++){
                                        if(X[i][j] == 1){
                                                X[i][j] = 0;
                                                ans[i][j] = cnt;
                                                break;
                                        }
                                }
                        }
                        else if(c[i][1] && c2 < n / 2){
                                c[i][1]--;
                                c2++;
                                for(int j = 0; j < m; j++){
                                        if(X[i][j] == 2){
                                                X[i][j] = 0;
                                                ans[i][j] = cnt;
                                                break;
                                        }
                                }
                        }
                }
                cnt++;
        }
        allocate_tickets(ans);
        return res;
}

• 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