Submission #1028335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028335		shmax	Carnival Tickets (IOI20_tickets)	C++17	35 / 100	2328 ms	491168 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>


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

using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()


template<typename T>
using vec = vector<T>;

const int maxN = 305;
const int maxK = 305;
int dp[maxN][maxN * maxK / 2];
int mv[maxN][maxN * maxK / 2];


long long find_maximum(i32 k, vector<vector<i32>> d) {


    int n = len(d);
    int m = len(d[0]);
    vec<int> cnt(n, m);
    int ans = 0;
//    memset(dp, -1000'000'000'000'000'00LL, sizeof dp);
    memset(mv, -1, sizeof mv);

    for(int i=0;i<=n;i++){
        for(int j=0;j<n*k/2;j++){
            dp[i][j] = -1e17;
        }
    }

//    vec<vec<int>> dp(n + 1, vec<int>(n * k / 2 + 1, -1e17));
//    vec<vec<int>> move(n + 1, vec<int>(n * k / 2 + 1, -1));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int sums = 0;
        for (int j = m - 1; j >= m - k; j--) {
            sums += d[i - 1][j];
        }
        for (int j = k; j >= 0; j--) {
            for (int l = 0; l <= min(n * k / 2, i * k) - j; l++) {
                if (dp[i - 1][l] + sums >= dp[i][l + j]) {
                    dp[i][l + j] = dp[i - 1][l] + sums;
                    mv[i][l + j] = j;
                }
            }
            if (j != 0) {
                sums -= d[i - 1][m - k + (k - j)];
                sums -= d[i - 1][k - j];
            }
        }
    }

    ans = dp[n][n * k / 2];
    int cur = n * k / 2;
    for (int i = n; i > 0; i--) {
        cnt[i - 1] = mv[i][cur];
        cur -= mv[i][cur];
    }

    {
        vec<vec<i32>> ops(n, vec<i32>(m, -1));
        vec<int> from_bot(n, 0);
        for (int t = 0; t < k; t++) {
            vec<int> ids(n);
            iota(all(ids), 0);
            sort(all(ids), [&](int a, int b) {
                return cnt[a] < cnt[b];
            });
            for (int i = 0; i < n / 2; i++) {
                int id = ids[i];
                int pos = from_bot[id];
                assert(0 <= pos and pos < m);
                ops[id][pos] = t;
                from_bot[id]++;
            }
            for (int i = n / 2; i < n; i++) {
                int id = ids[i];
                int pos = t - from_bot[id];
                ops[id][m - pos - 1] = t;
                cnt[id]--;
            }
        }
        allocate_tickets(ops);
    }
    return ans;
}

• 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