Submission #616750

#	Time	Username	Problem	Language	Result	Execution time	Memory
616750		wiwiho	Carnival Tickets (IOI20_tickets)	C++14	25 / 100	1025 ms	84348 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

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

    assert(k == m);

    ll sum = 0;
    vector<pii> tmp;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            tmp.eb(mp(i, j));
        }
    }

    sort(iter(tmp), [&](pii a, pii b){ return x[a.F][a.S] > x[b.F][b.S]; });
    vector<vector<bool>> big(n, vector<bool>(m));
    vector<int> cnt(n);
    for(int i = 0; i < n * m / 2; i++){
        int r, c;
        tie(r, c) = tmp[i];
        big[r][c] = true;
        cnt[r]++;
    }

    vector<vector<int>> ans(n, vector<int>(m));
    int now = 0;
    for(int i = 0; i < n; i++){
        int cb = 0, cs = 0;
        for(int j = 0; j < m; j++){
            if(big[i][j]){
                ans[i][j] = (now + cb) % m;
                cb++;
                sum += x[i][j];
            }
            else{
                ans[i][j] = (now + cnt[i] + cs) % m;
                cs++;
                sum -= x[i][j];
            }
        }
        now += cnt[i];
        now %= m;
    }

	allocate_tickets(ans);
	return sum;
}

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