oj.uz

Submission #1073310

# Submission time Handle Problem Language Result Execution time Memory
1073310 2024-08-24T12:10:02 Z mc061 Carnival Tickets (IOI20_tickets) C++17
39 / 100
 3000 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

const int mxN = 1.5e3+6;
bool have_c[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
    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[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;
    // }
    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);
        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][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;
    };

    if (!go()) {
        sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
            return A[0] < B[0];
        });
    }
    
    while (!go()) {
        random_shuffle(more.begin(), more.end());
    }
    allocate_tickets(ans_c);
    return ans;
}

Compilation message

tickets.cpp: In lambda function:
tickets.cpp:84: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]
   84 |         for (int i = 0; i < less.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
tickets.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 19 ms 18692 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 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 16 ms 4700 KB Output is correct
6 Correct 354 ms 106364 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 Correct 0 ms 600 KB Output is correct
4 Correct 17 ms 2648 KB Output is correct
5 Correct 1477 ms 111836 KB Output is correct
6 Runtime error 1040 ms 2097152 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.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 1 ms 348 KB Output is correct
4 Correct 34 ms 4900 KB Output is correct
5 Execution timed out 3090 ms 214000 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 10 ms 2652 KB Output is correct
6 Correct 20 ms 3676 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 14 ms 3120 KB Output is correct
10 Correct 14 ms 3164 KB Output is correct
11 Correct 26 ms 4404 KB Output is correct
12 Correct 26 ms 4180 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 10 ms 2652 KB Output is correct
6 Correct 20 ms 3676 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 14 ms 3120 KB Output is correct
10 Correct 14 ms 3164 KB Output is correct
11 Correct 26 ms 4404 KB Output is correct
12 Correct 26 ms 4180 KB Output is correct
13 Correct 16 ms 5468 KB Output is correct
14 Correct 25 ms 11096 KB Output is correct
15 Correct 1591 ms 112488 KB Output is correct
16 Execution timed out 3080 ms 214772 KB Time limit exceeded
17 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 19 ms 18692 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 16 ms 4700 KB Output is correct
12 Correct 354 ms 106364 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 17 ms 2648 KB Output is correct
17 Correct 1477 ms 111836 KB Output is correct
18 Runtime error 1040 ms 2097152 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -