Submission #308056

#	Time	Username	Problem	Language	Result	Execution time	Memory
308056		jwvg0425	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	43 ms	13044 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>;

struct Ticket
{
    int color;
    int idx;
    int value;
};

vector<ii64> small[1505];
vector<ii64> large[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(scnt, (int)small[idx].size()); suse++)
    {
        int luse = k - suse;
        if (luse > lcnt || luse > large[idx].size())
            continue;

        i64 lv = (luse == 0) ? 0 : large[idx][luse - 1].yy;
        i64 sv = (suse == 0) ? 0 : small[idx][suse - 1].yy;
        
        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();

    vector<Ticket> tickets;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            Ticket t;
            t.color = i;
            t.idx = j;
            t.value = x[i][j];
            tickets.push_back(t);
        }
    }

    sort(all(tickets), [](const Ticket& l, const Ticket& r)
    {
        return l.value < r.value;
    });

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

    for (int l = 0; l < m * n / 2; l++)
    {
        int r = n * m - 1 - l;
        small[tickets[l].color].emplace_back(tickets[l].idx, tickets[l].value);
        large[tickets[r].color].emplace_back(tickets[r].idx, tickets[r].value);
    }

    for (int color = 0; color < n; color++)
    {
        for (int i = 1; i < small[color].size(); i++)
            small[color][i].yy += small[color][i - 1].yy;

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

    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][small[color][i].xx] = gidx;
            gidx = (gidx + 1) % k;
        }

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

    allocate_tickets(ans);

    return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'i64 solve(int, int, int)':
tickets.cpp:53:33: 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]
   53 |         if (luse > lcnt || luse > large[idx].size())
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~
tickets.cpp: In function 'i64 find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:106: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]
  106 |         for (int i = 1; i < small[color].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
tickets.cpp:109: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]
  109 |         for (int i = 1; i < large[color].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

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