Submission #579776

#	Time	Username	Problem	Language	Result	Execution time	Memory
579776		2fat2code	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	517 ms	57584 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];
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);
            }
        }
    }
    for(int i=0;i<n;i++){
        int xd = 0;
        for(int j=0;j<m;j++){
            if(haida[i][j] == -1) xd++;
        }
      //  cout << xd << '\n';
        if(xd != m - K) exit(0);
    }
    for(int i=0;i<K;i++){
        int curr = 0;
        for(int j=0;j<n;j++){
            if(slava[j].size() && curr < n/2){
                ++curr;
                haida[j][slava[j].back()] = i;
                slava[j].pop_back();
            }
            else{
                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: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10