Submission #308064

#	Time	Username	Problem	Language	Result	Execution time	Memory
308064		jwvg0425	Carnival Tickets (IOI20_tickets)	C++17	12 / 100	93 ms	10368 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#define all(x) x.begin(), x.end()
#define xx first
#define yy second

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<ii64> ts[1505];
ii trace[85][10005];
i64 table[85][10005];
bool calc[85][10005];
int n, m;

i64 solve(int k, int idx, int scnt)
{
    if (idx == n)
    {
        if (scnt == 0)
            return 0;
        else
            return -(1ll << 60);
    }

    if (calc[idx][scnt])
        return table[idx][scnt];
    
    auto& res = table[idx][scnt];
    res = -(1ll << 60);
    calc[idx][scnt] = true;
    int used = k * idx;
    int sused = k * n / 2 - scnt;
    int lused = used - sused;
    int lcnt = k * n / 2 - lused;

    for (int suse = 0; suse <= min(k, scnt); suse++)
    {
        int luse = k - suse;
        if (luse > lcnt)
            continue;

        i64 sv = (suse == 0) ? 0 : ts[idx][suse - 1].xx;
        i64 lv = (luse == m) ? ts[idx].back().xx : 
            ts[idx].back().xx - ts[idx][m - 1 - luse].xx;
        
        i64 now = lv - sv + solve(k, idx + 1, scnt - suse);
        
        if (now > res)
        {
            res = now;
            trace[idx][scnt] = ii(suse, luse);
        }
    }

    return res;
}

i64 find_maximum(int k, vector<vector<int>> x)
{
    n = x.size();
    m = x[0].size();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ts[i].emplace_back(x[i][j], j);

    vector<vector<int>> ans(n, vector<int>(m, -1));

    for (int color = 0; color < n; color++)
    {
        sort(all(ts[color]));

        for (int i = 1; i < ts[color].size(); i++)
            ts[color][i].xx += ts[color][i - 1].xx;
    }

    i64 ret = solve(k, 0, k * n / 2);

    int gidx = 0;
    int cnt = k * n / 2;
    for (int color = 0; color < n; color++)
    {
        for (int i = 0; i < trace[color][cnt].xx; i++)
        {
            ans[color][ts[color][i].yy] = gidx;
            gidx = (gidx + 1) % k;
        }

        int lgi = gidx;

        for (int i = 0; i < trace[color][cnt].yy; i++)
        {
            ans[color][ts[color][m - 1 - i].yy] = lgi;
            lgi = (lgi + 1) % k;
        }
        cnt -= trace[color][cnt].xx;
    }

    allocate_tickets(ans);

    return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'i64 find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 1; i < ts[color].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~

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