Submission #800207

#	Time	Username	Problem	Language	Result	Execution time	Memory
800207		PixelCat	Carnival Tickets (IOI20_tickets)	C++14	62 / 100	940 ms	2097152 KiB

tickets

#include "tickets.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1500;
const int INF = 1e18;
const int MAGIC = 10;

int find_maximum(i32 _k, vector<vector<i32>> x) {
    int k = _k;
    int n = sz(x);
    int m = sz(x[0]);
    vector<vector<i32>> answer(n, vector<i32>(m, -1));
    vector<vector<int>> cost(n, vector<int>(k + 1, 0));

    For(i, 0, n - 1) {
        For(j, 0, k - 1) cost[i][0] -= x[i][j];
        For(j, 1, k) cost[i][j] = cost[i][j - 1] + x[i][k - j] + x[i][m - j];
    }

    int cnt = n * k / 2;
    vector<vector<int>> dp(n, vector<int>(cnt + 1, -INF));
    vector<vector<int>> src(n, vector<int>(cnt + 1, -1));
    For(i, 0, k) {
        dp[0][i] = cost[0][i];
        src[0][i] = i;
    }
    For(i, 1, n - 1) For(j, 0, cnt) {
        int l = 0, r = min(k, j);
        if(j) {
            l = max(l, src[i][j - 1] - MAGIC);
            r = min(r, src[i][j - 1] + MAGIC);
        }
        For(c, l, r) {
            int val = dp[i - 1][j - c] + cost[i][c];
            if(val > dp[i][j]) {
                dp[i][j] = val;
                src[i][j] = c;
            }
        }
    }
    
    // contruct answer
    vector<int> le(n), ri(n);
    Forr(i, n - 1, 0) {
        int c = src[i][cnt];
        // cerr << cnt << " " << c << "\n";
        cnt -= c;
        le[i] = k - c - 1;
        ri[i] = m - c;
    }
    For(i, 0, k - 1) {
        int cl = n / 2, cr = n / 2;
        vector<int> vis(n, 0);
        For(j, 0, n - 1) {
            if(le[j] < 0) {
                answer[j][ri[j]] = (i32) i;
                ri[j]++;
                cr--;
                vis[j] = 1;
            } else if(ri[j] >= m) {
                answer[j][le[j]] = (i32) i;
                le[j]--;
                cl--;
                vis[j] = 1;
            }
        }
        For(j, 0, n - 1) if(!vis[j]) {
            if(cl) {
                answer[j][le[j]] = (i32) i;
                le[j]--;
                cl--;
            } else {
                answer[j][ri[j]] = (i32) i;
                ri[j]++;
                cr--;
            }
        }
    }

    // For(i, 0, n - 1) For(j, 0, k) {
    //     cerr << cost[i][j] << " \n"[j == k];
    // }
    // cnt = n * k / 2;
    // For(i, 0, n - 1) For(j, 1, cnt) {
    //     cerr << src[i][j] << " \n"[j == cnt];
    //     if(src[i][j] != -1 && src[i][j] < src[i][j - 1]) {
    //         assert(false);
    //     }
    // }

    allocate_tickets(answer);
    return dp[n - 1][n * k / 2];
}

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