Submission #816974

#	Time	Username	Problem	Language	Result	Execution time	Memory
816974		finn__	Catfish Farm (IOI22_fish)	C++17	44 / 100	1101 ms	429076 KiB

fish

#include "fish.h"

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

constexpr size_t N = 3001;

struct state
{
    int64_t s, l, z;
};

state f[N][N];
int64_t p[N][N];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
    // subtask 1
    {
        bool all_even = 1;
        for (size_t i = 0; i < m; ++i)
            all_even &= !(x[i] & 1);
        if (all_even)
        {
            int64_t sum = 0;
            for (size_t i = 0; i < m; ++i)
                sum += w[i];
            return sum;
        }
    }

    // subtask 2
    {
        bool leq1 = 1;
        for (size_t i = 0; i < m; ++i)
            leq1 &= x[i] <= 1;
        if (leq1)
        {
            int64_t z = 0, t = 0;
            vector<pair<int, int>> zero, one;
            for (size_t i = 0; i < m; ++i)
                if (x[i])
                    one.emplace_back(y[i], w[i]), z += w[i];
                else
                    zero.emplace_back(y[i], w[i]), t += w[i];

            if (n == 2)
                return max(t, z);

            sort(one.begin(), one.end());
            sort(zero.begin(), zero.end());

            int64_t ans = z;
            auto it = zero.begin(), jt = one.begin();
            for (int i = 0; i <= n && (it != zero.end() || jt != one.end()); ++i)
            {
                if (it != zero.end() && it->first < i)
                    z += it->second, ++it;
                if (jt != one.end() && jt->first < i)
                    z -= jt->second, ++jt;
                ans = max(ans, z);
            }

            return ans;
        }
    }

    for (size_t i = 1; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            f[i][j].s = f[i][j].l = f[i][j].z = INT64_MIN / 2;

    for (size_t i = 0; i < m; ++i)
        p[x[i]][y[i] + 1] = w[i];
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 1; j <= n; ++j)
            p[i][j] += p[i][j - 1];

    for (size_t i = 1; i < n; ++i)
        for (size_t j = 0; j <= n; ++j)
        {
            for (size_t k = 0; k < j; ++k)
                f[i][j].s = max(f[i][j].s, p[i - 1][j] - p[i - 1][k] + max(f[i - 1][k].s, f[i - 1][k].z));
            for (size_t k = j; k <= n; ++k)
                f[i][j].s = max(f[i][j].s, f[i - 1][k].z);

            for (size_t k = j; k <= n; ++k)
                f[i][j].l = max(f[i][j].l, max(f[i - 1][k].l, f[i - 1][k].s) + p[i][k] - p[i][j]);

            f[i][j].z = max(f[i - 1][j].s, f[i - 1][j].l) + p[i][j];
            if (!j)
            {
                for (size_t k = 0; k <= n; ++k)
                    f[i][j].z = max(f[i][j].z, f[i - 1][k].z);
            }
        }

    int64_t ans = 0;
    for (size_t j = 0; j <= n; ++j)
        ans = max(ans, max(f[n - 1][j].s, max(f[n - 1][j].l, f[n - 1][j].z)));
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:21:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
fish.cpp:26:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |             for (size_t i = 0; i < m; ++i)
      |                                ~~^~~
fish.cpp:35:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
fish.cpp:41:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             for (size_t i = 0; i < m; ++i)
      |                                ~~^~~
fish.cpp:68:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:69:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         for (size_t j = 0; j < n; ++j)
      |                            ~~^~~
fish.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
fish.cpp:74:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
fish.cpp:75:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         for (size_t j = 1; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:78:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:79:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         for (size_t j = 0; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:83:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |             for (size_t k = j; k <= n; ++k)
      |                                ~~^~~~
fish.cpp:86:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |             for (size_t k = j; k <= n; ++k)
      |                                ~~^~~~
fish.cpp:92:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |                 for (size_t k = 0; k <= n; ++k)
      |                                    ~~^~~~
fish.cpp:98:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     for (size_t j = 0; j <= n; ++j)
      |                        ~~^~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16