Submission #579787

#	Time	Username	Problem	Language	Result	Execution time	Memory
579787		2fat2code	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1201 ms	139436 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define int long long
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1505;

int n, m, K, ans, lol[nmax][nmax], ultim[nmax];
vector<int>slava[nmax], marian[nmax];
vector<vector<int32_t>>haida;

void simuleaza(){
    haida.resize(n, vector<int32_t>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(lol[i][j] == 0){
                haida[i][j] = -1;
            }
            else if(lol[i][j] == 2){
                slava[i].push_back(j);
            }
            else{
                marian[i].push_back(j);
            }
        }
    }
    set<pair<int,int>>alic;
    for(int i=0;i<K;i++){
        alic.clear();
        for(int j=0;j<n;j++){
            alic.insert({slava[j].size(), j});
        }
        for(int j=0;j<n;j++) ultim[j] = 0;
        auto it = alic.end();
        for(int j=1;j<=n/2;j++){
            --it;
            haida[it->sc][slava[it->sc].back()] = i;
            slava[it->sc].pop_back();
            ultim[it->sc] = 1;
        }
        for(int j=0;j<n;j++){
            if(ultim[j] != 1){
                haida[j][marian[j].back()] = i;
                marian[j].pop_back();
            }
        }
    }
}

int find_maximum(int32_t k, vector<vector<int32_t>> x) {
	n = x.size();
    m = x[0].size();
    K = k;
	vector<pair<int,pair<int,int>>>xd;
	for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            ans -= (long long)x[i][j];
            lol[i][j] = 1;
            xd.push_back({x[i][j] + x[i][m-(k-j)], {i, j}});
        }
	}
	sort(all(xd));
	reverse(all(xd));
	for(int i=0;i<(k*n/2);i++){
        auto it = xd[i];
        lol[it.sc.fr][it.sc.sc] = 0;
        lol[it.sc.fr][m-(k-it.sc.sc)] = 2;
        ans += it.fr;
	}
	simuleaza();
	allocate_tickets(haida);
	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