Submission #817472

#	Time	Username	Problem	Language	Result	Execution time	Memory
817472		finn__	Catfish Farm (IOI22_fish)	C++17	18 / 100	264 ms	71284 KiB

fish

#include "fish.h"

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

constexpr size_t N = 100001;

struct state
{
    vector<int64_t> s, l, z;
};

state f[N];
vector<int64_t> p[N];
vector<uint32_t> coords[N];

size_t ind(size_t x, int y)
{
    return lower_bound(coords[x].begin(), coords[x].end(), y) - coords[x].begin();
}

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
    for (size_t i = 0; i < m; ++i)
    {
        coords[x[i]].push_back(y[i] + 1);
        if (x[i])
            coords[x[i] - 1].push_back(y[i] + 1);
        if (x[i] + 1 < n)
            coords[x[i] + 1].push_back(y[i] + 1);
    }

    for (size_t i = 0; i < n; ++i)
    {
        coords[i].push_back(0);
        sort(coords[i].begin(), coords[i].end());
        coords[i].resize(unique(coords[i].begin(), coords[i].end()) - coords[i].begin());
        f[i].s.resize(coords[i].size());
        f[i].l.resize(coords[i].size());
        f[i].z.resize(i ? coords[i - 1].size() : 1);
        p[i].resize(coords[i].size());
    }

    for (size_t i = 1; i < n; ++i)
    {
        fill(f[i].s.begin(), f[i].s.end(), INT64_MIN / 2);
        fill(f[i].l.begin(), f[i].l.end(), INT64_MIN / 2);
        fill(f[i].z.begin(), f[i].z.end(), INT64_MIN / 2);
    }

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

    for (size_t i = 1; i < n; ++i)
    {
        // Update s
        int64_t h = f[i - 1].s[0];
        size_t k = 0, l = i == 1 ? SIZE_MAX : 0;
        for (size_t j = 1; j < coords[i].size(); ++j)
        {
            while (k < coords[i - 1].size() && coords[i - 1][k] < coords[i][j])
            {
                h = max(h, f[i - 1].s[k] - p[i - 1][k]);
                ++k;
            }
            while (l < f[i - 1].z.size() && coords[i - 2][l] < coords[i][j])
            {
                size_t v = ind(i - 1, coords[i - 2][l]);
                if (v == coords[i - 1].size() || coords[i - 1][v] > coords[i - 2][l])
                    --v;
                h = max(h, f[i - 1].z[l] - p[i - 1][v]);
                ++l;
            }

            size_t u = ind(i - 1, coords[i][j]);
            if (u == coords[i - 1].size() || coords[i - 1][u] > coords[i][j])
                --u;
            f[i].s[j] = max(f[i].s[j], h + p[i - 1][u]);
        }

        h = INT64_MIN;
        l = f[i - 1].z.size() - 1;
        for (size_t j = coords[i].size() - 1; j < coords[i].size(); --j)
        {
            while (l != SIZE_MAX && (i == 1 || coords[i - 2][l] > coords[i][j]))
            {
                h = max(h, f[i - 1].z[l]);
                f[i].s[j] = max(f[i].s[j], h);
                --l;
            }
            if (l != SIZE_MAX)
            {
                h = max(h, f[i - 1].z[l]);
                f[i].s[j] = max(f[i].s[j], h);
                --l;
            }
        }

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

        // Update z
        k = 0;
        for (size_t j = 0; j < f[i].z.size(); ++j)
        {
            while (k + 1 < coords[i].size() && coords[i][k + 1] <= coords[i - 1][j])
                ++k;
            f[i].z[j] = max(f[i].z[j], max(f[i - 1].s[j], f[i - 1].l[j]) + p[i][k]);

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

    int64_t ans = 0;
    for (size_t j = 0; j < f[n - 1].s.size(); ++j)
        ans = max(ans, max(f[n - 1].s[j], f[n - 1].l[j]));
    for (size_t j = 0; j < f[n - 1].z.size(); ++j)
        ans = max(ans, f[n - 1].z[j]);
    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:24:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
fish.cpp:33:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
fish.cpp:44:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:51:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
fish.cpp:53:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
fish.cpp:57:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~

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