Submission #705830

#	Time	Username	Problem	Language	Result	Execution time	Memory
705830		finn__	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	212 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, vector<vector<int>> x)
{
    size_t n = x.size();
    size_t m = x[0].size();
    vector<vector<int64_t>> f(n, vector<int64_t>(n * k / 2 + 1, INT64_MIN));
    vector<vector<size_t>> prev(n, vector<size_t>(n * k / 2 + 1, INT64_MIN));

    int64_t v = 0;
    for (size_t d = m - k; d < m; d++)
        v += x[0][d];
    for (size_t d = 0; d < k; d++)
    {
        f[0][d] = v;
        prev[0][d] = 0;
        v -= x[0][d] + x[0][m - k + d];
    }

    for (size_t i = 1; i < n; i++)
    {
        for (size_t j = 0; j < (i + 1) * k && j < f[i].size(); j++)
        {
            int64_t v = 0;
            for (size_t d = m - k; d < m; d++)
                v += x[i][d];

            for (size_t d = 0; d <= k && j - d < f[1].size(); d++)
            {
                if (f[i - 1][j - d] + v > f[i][j])
                    f[i][j] = f[i - 1][j - d] + v, prev[i][j] = j - d;
                v -= x[i][d] + x[i][m - k + d];
            }
        }
    }

    vector<vector<int>> a(n, vector<int>(m, -1));
    vector<int> low(k, 0), up(k, 0);
    size_t curr = n * k / 2;

    for (size_t i = n - 1; i < n; i--)
    {
        size_t low_left = curr - prev[i][curr], up_left = k - low_left;
        for (size_t j = 0; j < k; j++)
        {
            if (low[j] < n / 2 && low_left)
                a[i][--low_left] = j, low[j]++;
            else
                a[i][m - up_left--] = j, up[j]++;
        }
        curr = prev[i][curr];
    }

    allocate_tickets(a);

    return f[n - 1][n * k / 2];
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:15:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     for (size_t d = 0; d < k; d++)
      |                        ~~^~~
tickets.cpp:30:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |             for (size_t d = 0; d <= k && j - d < f[1].size(); d++)
      |                                ~~^~~~
tickets.cpp:46:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         for (size_t j = 0; j < k; j++)
      |                            ~~^~~
tickets.cpp:48:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             if (low[j] < n / 2 && low_left)

• 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