Submission #1074365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074365		zsombor	Catfish Farm (IOI22_fish)	C++17	58 / 100	1086 ms	37712 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m, ans = 0;
vector<vector<pair<int, ll> > > f(2e5);
vector<vector<ll> > dp1(2e5);
vector<vector<ll> > dp2(2e5);

void get_dp1(int i, int j) {
    ll h0, h = f[i][j].first - 1, val = 0;
    for (auto p: f[i]) if (p.first <= h) val -= p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        if (h0 < h) continue;
        dp1[i][j] = max(dp1[i][j], dp1[i - 1][k] + val);
        dp1[i][j] = max(dp1[i][j], dp2[i - 1][k] + val);
    }
    ans = max(ans, dp1[i][j]);
}

void get_dp2(int i, int j) {
    ll h0, h = f[i][j].first - 1, val = 0, nxt = 0;
    for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        if (h0 >= h) break;
        if (k) val -= f[i - 1][k - 1].second;
        while (h0 >= f[i][nxt].first) val -= f[i][nxt++].second;
        dp2[i][j] = max(dp2[i][j], dp2[i - 1][k] + val);
    }
    if (i == 1) {
        ans = max(ans, dp2[i][j]);
        return;
    }
    val = nxt = 0;
    for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 2].size(); k++) {
        h0 = f[i - 2][k].first - 1;
        while (h0 >= f[i - 1][nxt].first && h0 >= f[i - 1][nxt].first) val -= f[i - 1][nxt++].second;
        dp2[i][j] = max(dp2[i][j], dp1[i - 2][k] + val);
        dp2[i][j] = max(dp2[i][j], dp2[i - 2][k] + val);
    }
    ans = max(ans, dp2[i][j]);
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        X[i]++;
        Y[i]++;
        f[X[i]].push_back({Y[i], W[i]});
    }
    f[0].push_back({1, 0});
    for (int i = 0; i <= n + 1; i++) {
        f[i].push_back({n + 1, 0});
        sort(f[i].begin(), f[i].end());
    }
    dp1[0] = dp2[0] = {0ll, ll(-1e18)};
    for (int i = 1; i <= n; i++) {
        dp1[i].resize(f[i].size(), 0);
        dp2[i].resize(f[i].size(), 0);
        for (int j = 0; j < f[i].size(); j++) {
            get_dp1(i, j);
            get_dp2(i, j);
        }
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'void get_dp1(int, int)':
fish.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'void get_dp2(int, int)':
fish.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int k = 0; k < f[i - 2].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 0; j < f[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

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