Submission #1074412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074412		zsombor	Catfish Farm (IOI22_fish)	C++17	67 / 100	1065 ms	37208 KiB

fish

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

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

ll solve2() {
    f[1].push_back({n + 1, 0});
    f[2].push_back({n + 1, 0});
    sort(f[1].begin(), f[1].end());
    sort(f[2].begin(), f[2].end());
    ll sum1 = 0, sum2 = 0, h, nxt = 0;
    for (auto p: f[1]) sum1 += p.second;
    for (auto p: f[2]) sum2 += p.second;
    if (n == 2) return max(sum1, sum2);
    ans = sum2;
    for (auto p: f[2]) {
        h = p.first - 1;
        while (h >= f[1][nxt].first) sum2 += f[1][nxt++].second;
        ans = max(ans, sum2);
        sum2 -= p.second;
    }
    return ans;
}

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 solve() {
    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;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    ll sum = 0;
    for (int i = 0; i < m; i++) {
        X[i]++;
        Y[i]++;
        f[X[i]].push_back({Y[i], W[i]});
        sum += W[i];
    }
    bool st1 = true, st2 = true;
    for (int i = 0; i < m; i++) {
        if (X[i] % 2 == 0) st1 = false;
        if (X[i] > 2) st2 = false;
    }
    if (st1) return sum;
    if (st2) return solve2();
    return solve();
}

Compilation message (stderr)

fish.cpp: In function 'void get_dp1(int, int)':
fish.cpp:34: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]
   34 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'void get_dp2(int, int)':
fish.cpp:47: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]
   47 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:61: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]
   61 |     for (int k = 0; k < f[i - 2].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'll solve()':
fish.cpp:80: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]
   80 |         for (int j = 0; j < f[i].size(); 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: 14 / 14
• Subtask 8: 0 / 16