Submission #817000

#	Time	Username	Problem	Language	Result	Execution time	Memory
817000		finn__	Catfish Farm (IOI22_fish)	C++17	53 / 100	1077 ms	433856 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;
        }
    }

    // subtask 3
    {
        bool all_y_zero = 1;
        for (size_t i = 0; i < m; ++i)
            all_y_zero &= !y[i];

        if (all_y_zero)
        {
            vector<int64_t> v(n);
            for (size_t i = 0; i < m; ++i)
                v[x[i]] = w[i];
            vector<array<array<int64_t, 2>, 2>> f(n);
            for (size_t i = 1; i < n; ++i)
                for (size_t j = 0; j < 2; ++j)
                    fill(f[i][j].begin(), f[i][j].end(), INT64_MIN / 2);
            for (size_t i = 1; i < n; ++i)
            {
                f[i][0][0] = max(f[i - 1][1][0], f[i - 1][0][0]);
                f[i][1][0] = max(f[i - 1][0][1], f[i - 1][1][1]) + v[i];
                f[i][0][1] = max(f[i - 1][0][0] + v[i - 1], f[i - 1][1][0]);
                f[i][1][1] = max(f[i - 1][0][1], f[i - 1][1][1]);
            }

            return max(f[n - 1][0][0], max(f[n - 1][0][1], max(f[n - 1][1][0], f[n - 1][1][1])));
        }
    }

    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)
    {
        // Update s
        int64_t h = f[i - 1][0].s;
        for (size_t j = 1; j <= n; ++j)
        {
            f[i][j].s = max(f[i][j].s, h + p[i - 1][j]);
            h = max(h, f[i - 1][j].s - p[i - 1][j]);
        }
        for (size_t j = 0; j <= n; ++j)
        {
            for (size_t k = j; k <= n; ++k)
                f[i][j].s = max(f[i][j].s, f[i - 1][k].z);
        }

        // Update l
        int64_t g = 0; // max f_i-1,k,s f_i-1,k-l + p_ik over all k >= j
        for (size_t j = n; j <= n; --j)
        {
            g = max(g, max(f[i - 1][j].l, f[i - 1][j].s) + p[i][j]);
            f[i][j].l = max(f[i][j].l, g - p[i][j]);
        }

        // Update z
        for (size_t j = 0; j <= n; ++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:71:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
fish.cpp:77:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |             for (size_t i = 0; i < m; ++i)
      |                                ~~^~~
fish.cpp:80:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |             for (size_t i = 1; i < n; ++i)
      |                                ~~^~~
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 i = 1; i < n; ++i)
      |                                ~~^~~
fish.cpp:95:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:96:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         for (size_t j = 0; j < n; ++j)
      |                            ~~^~~
fish.cpp:99:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
fish.cpp:101:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
fish.cpp:102:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         for (size_t j = 1; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:105:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:109:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |         for (size_t j = 1; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:114:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |         for (size_t j = 0; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:116:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |             for (size_t k = j; k <= n; ++k)
      |                                ~~^~~~
fish.cpp:122:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |         for (size_t j = n; j <= n; --j)
      |                            ~~^~~~
fish.cpp:129:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |         for (size_t j = 0; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:134:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |                 for (size_t k = 0; k <= n; ++k)
      |                                    ~~^~~~
fish.cpp:141:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |     for (size_t j = 0; j <= n; ++j)
      |                        ~~^~~~

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