Submission #1073327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073327		mc061	Carnival Tickets (IOI20_tickets)	C++14	35 / 100	2799 ms	496980 KiB

tickets

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int mxN = 300+6;
bool have_c[mxN][mxN]={};

int64_t dp[mxN][mxN*mxN];
int64_t prv[mxN][mxN*mxN];

void allocate_tickets(std::vector<std::vector<int>> _x);
long long find_maximum(int k, std::vector<std::vector<int>> d) {
    srand(time(0));
    const int n = d.size(); //colors
    const int m = d[0].size(); //tickets per color
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n*k/2; ++j) {
            dp[i][j] = -1e18;
        }
    }
    // 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>> 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 = 0; j <= n*k/2; ++j) {
            if (dp[i][j] == -1e18) continue;
            for (int take = 0; take <= k && j+take <= n*k/2; ++take) {
                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;
                    prv[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 = prv[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(), [&] (const auto& A, const auto& B) {
        return A[1] > B[1];
    });
    sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
        return A[1] < B[1];
    });
    // 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;
    // }
    // cerr << more.size() << " " << less.size() << "\n";
    auto go = [&] () {
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < n; ++j) {
                have_c[i][j] = false;
            }
        }
        // random_shuffle(less.begin(), less.end());
        // random_shuffle(more.begin(), more.end());
        vector<bool> used(more.size(), false);
        int ptr = 0;
        for (int i = 0; i < less.size(); ++i) {
            while (ptr < more.size() && used[ptr] == true) ++ptr;
            bool ok = false;
            for (int j = ptr; 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][less[i][1]] && !have_c[x][more[j][1]]) {
                        have_c[x][less[i][1]] = true;
                        have_c[x][more[j][1]] = true;
                        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;
            }
            if (!ok) return false;
        }
        return true;
    };
    while (!go()) {
        if (rand()%2) {
            sort(less.begin(), less.end(), [&] (const auto& A, const auto& B) {
                return A[1] > B[1];
            });
        }
        else {
            sort(less.begin(), less.end(), [&] (const auto& A, const auto& B) {
                return A[1] < B[1];
            });
        }
        if (rand()%2) {
            random_shuffle(more.begin(), more.end());
        }
        else {
            if (rand()%2) {
                sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
                    return A[1] < B[1];
                });
            }
            else {
                sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
                    return A[1] > B[1];
                });
            }
        }
    }
    allocate_tickets(ans_c);
    return ans; 
}

Compilation message (stderr)

tickets.cpp: In lambda function:
tickets.cpp:96: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]
   96 |         for (int i = 0; i < less.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
tickets.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             while (ptr < more.size() && used[ptr] == true) ++ptr;
      |                    ~~~~^~~~~~~~~~~~~
tickets.cpp:99:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (int j = ptr; j < more.size(); ++j) {
      |                               ~~^~~~~~~~~~~~~

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