oj.uz

Submission #1073281

# Submission time Handle Problem Language Result Execution time Memory
1073281 2024-08-24T11:47:33 Z mc061 Carnival Tickets (IOI20_tickets) C++17
27 / 100
 350 ms 108296 KB 
#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(), [&] (const auto& A, const auto& B) {
        return A[0] < B[0];
    });
    sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
        return A[0] < B[0];
    });
    // 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);
    vector<int> order(k);
    iota(order.begin(), order.end(), 0);
    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;
            random_shuffle(order.begin(), order.end());
            for (int y = 0; y < k; ++y) {
                int x = order[y];
                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

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:73: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]
   73 |     for (int i = 0; i < less.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
tickets.cpp:75: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]
   75 |         for (int j = 0; j < more.size(); ++j) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 11 ms 18524 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 15 ms 4652 KB Output is correct
6 Correct 350 ms 108296 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 0 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 2 ms 1424 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 2 ms 1424 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 11 ms 18524 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 15 ms 4652 KB Output is correct
12 Correct 350 ms 108296 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Runtime error 1 ms 604 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -