oj.uz

Submission #1073322

# Submission time Handle Problem Language Result Execution time Memory
1073322 2024-08-24T12:24:43 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>> 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;
                    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;
    // }
    // 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()) {
        random_shuffle(more.begin(), more.end());
    }
    allocate_tickets(ans_c);
    return ans; 
}

Compilation message

tickets.cpp: In lambda function:
tickets.cpp:89: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]
   89 |         for (int i = 0; i < less.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
tickets.cpp:90: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]
   90 |             while (ptr < more.size() && used[ptr] == true) ++ptr;
      |                    ~~~~^~~~~~~~~~~~~
tickets.cpp:92: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]
   92 |             for (int j = ptr; j < more.size(); ++j) {
      |                               ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 11 ms 18684 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 604 KB Output is correct
5 Correct 16 ms 4672 KB Output is correct
6 Correct 363 ms 105840 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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 680 ms 111800 KB Output is correct
6 Runtime error 956 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 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 19 ms 4956 KB Output is correct
5 Correct 2950 ms 219060 KB Output is correct
6 Correct 72 ms 4672 KB Output is correct
7 Correct 165 ms 177748 KB Output is correct
8 Runtime error 973 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1628 KB Output is correct
5 Correct 9 ms 2844 KB Output is correct
6 Correct 16 ms 3672 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 9 ms 3348 KB Output is correct
10 Correct 8 ms 3164 KB Output is correct
11 Correct 20 ms 4380 KB Output is correct
12 Correct 15 ms 4444 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 3 ms 1628 KB Output is correct
5 Correct 9 ms 2844 KB Output is correct
6 Correct 16 ms 3672 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 9 ms 3348 KB Output is correct
10 Correct 8 ms 3164 KB Output is correct
11 Correct 20 ms 4380 KB Output is correct
12 Correct 15 ms 4444 KB Output is correct
13 Correct 17 ms 5464 KB Output is correct
14 Correct 33 ms 11160 KB Output is correct
15 Correct 805 ms 112488 KB Output is correct
16 Correct 2897 ms 219172 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 6 ms 6236 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 1508 ms 147936 KB Output is correct
21 Correct 1508 ms 139084 KB Output is correct
22 Execution timed out 3065 ms 203392 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
0 / 10.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 11 ms 18684 KB Output is correct
7 Correct 1 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 2 ms 604 KB Output is correct
11 Correct 16 ms 4672 KB Output is correct
12 Correct 363 ms 105840 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 5 ms 2652 KB Output is correct
17 Correct 680 ms 111800 KB Output is correct
18 Runtime error 956 ms 2097152 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -