Submission #1073279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073279		mc061	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1584 ms	2097152 KiB

tickets

#include <bits/stdc++.h>
using namespace std;

void allocate_tickets(std::vector<std::vector<int>> _x);
long long find_maximum(int k, std::vector<std::vector<int>> d) {
    const int n = d.size(); //colors
    const int m = d[0].size(); //tickets per color
    vector<vector<int64_t>> dp(n+1, vector<int64_t>(n*k/2+1, -1e18));
    vector<vector<int64_t>> prev(n+1, vector<int64_t>(n*k/2+1));
    dp[0][0] = 0;
    vector<vector<int64_t>> val(n, vector<int64_t>(m+1, 0)); //what value gain by taking j with minus
    for (int i = 0; i < n; ++i) {
        int64_t res = 0;
        for (int j = m-1; j >= m-k; --j) {
            res += d[i][j];
        }
        int ptr = m-k;
        val[i][0] = res;
        for (int j = 1; j <= k; ++j) {
            res -= d[i][ptr];
            res -= d[i][j-1];
            val[i][j] = res;
            ptr++;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = n*k/2; j >= 0; --j) {
            for (int take = k; take >= 0; --take) {
                if (j+take >= n*k/2+1) continue;
                int64_t nxt_val = dp[i][j] + val[i][take];
                if (nxt_val > dp[i+1][j+take]) {
                    dp[i+1][j+take] = nxt_val;
                    prev[i+1][j+take] = take;
                }
            }
        }
    }
    int64_t ans = dp[n][(n*k)/2];
    int64_t j = (n*k)/2;

    vector<vector<int>> ans_c(n, vector<int>(m, -1));

    vector<array<int, 3>> less, more;

    for (int i = n; i > 0; --i) {
        int take_here = prev[i][j];
        int left = k-take_here;
        for (int x = 0; x < take_here; ++x) {
            less.push_back({d[i-1][x], i-1, x});
        }
        for (int x = m-1; x >= m-left; --x) {
            more.push_back({d[i-1][x], i-1, x});
        }
        j -= take_here;
    }    
    sort(less.begin(), less.end());
    sort(more.begin(), more.end());
    // for (int i = 0; i < less.size(); ++i) {
    //     cout << less[i][0] << " " << less[i][1] << " " << less[i][2] << endl;
    // }
    // cout << "\n";
    // for (int i = 0; i < more.size(); ++i) {
    //     cout << more[i][0] << " " << more[i][1] << " " << more[i][2] << endl;
    // }
    vector<set<int>> have_c(k);
    vector<bool> used(more.size(), false);
    for (int i = 0; i < less.size(); ++i) {
        bool ok = false;
        for (int j = 0; j < more.size(); ++j) {
            if (used[j]) continue;
            if (less[i][1] == more[j][1]) {
                continue;
            }
            if (less[i][0] > more[j][0]) continue;
            for (int x = 0; x < k; ++x) {
                if (!have_c[x].count(less[i][1]) && !have_c[x].count(more[j][1])) {
                    have_c[x].insert(less[i][1]);
                    have_c[x].insert(more[j][1]);
                    used[j] = true;
                    ans_c[less[i][1]][less[i][2]] = x;
                    ans_c[more[j][1]][more[j][2]] = x;
                    ok = true;
                    break;
                }
            }
            if (!ok) continue;
            break;
        }
        assert(ok==true);
    }
    allocate_tickets(ans_c);
    return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < less.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
tickets.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 0; j < more.size(); ++j) {
      |                         ~~^~~~~~~~~~~~~

• 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