Submission #306473

#	Time	Username	Problem	Language	Result	Execution time	Memory
306473		giorgikob	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	768 KiB

tickets

#include "tickets.h"
#include <vector>

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

    bool ok = true;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(x[i][j] > 1){
                ok = false;
            }
        }
    }

    vector<vector<int>> answer(n, vector<int>(m,-1));
    ll result = 0;

	if(m == 1){
        vector<vector<int>> answer(n, vector<int>(m,0));
        vector<int>v;
        for(int i = 0; i < n; i++) v.pb(x[i][0]);
        sort(v.begin(),v.end());
        ll result = 0;
        for(int i = 0; i < n; i++) result += abs(v[i]-v[n/2]);
        allocate_tickets(answer);
        return result;
	}

	if(ok){
        /*vector< pair<vector<int>,int> > v(n);
        for(int i = 0; i < n; i++){
            v[i] = {x[i],i};
        }*/
        sort(x.begin(),x.end());

        vector<int>a(m,0);
        for(int j = 0; j < m; j++){
            int sum = 0;
            for(int i = 0; i < n; i++){
                sum += x[i][j];
            }
            a[j] = max(sum,n-sum);
        }

        int l = 0, r = m-1;
        for(int i = 0; i < k; i++){
            if(a[l] > a[r]){
                result += a[l];
                for(int j = 0; j < n; j++){
                    answer[j][l] = i;
                }
                l++;
            } else {
                result += a[r];
                for(int j = 0; j < n; j++){
                    answer[j][r] = i;
                }
                r--;
            }
        }
        allocate_tickets(answer);
        return result;
	}

    allocate_tickets(answer);
	return result;
}

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