Submission #1074239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074239		zsombor	Catfish Farm (IOI22_fish)	C++17	0 / 100	1053 ms	22388 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> > dp(2e5);

void get_dp(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;
    dp[i][j] = val;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        while (h0 >= f[i][nxt].first) val -= f[i][nxt++].second;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + val);
        if (f[i - 1][k].first <= h) val -= f[i - 1][k].second;
    }
    ans = max(ans, dp[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());
    }
    dp[0] = {0ll, ll(-1e18)};
    for (int i = 1; i <= n; i++) {
        dp[i].resize(f[i].size(), 0);
        for (int j = 0; j < f[i].size(); j++) get_dp(i, j);
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'void get_dp(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 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40: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]
   40 |         for (int j = 0; j < f[i].size(); j++) get_dp(i, j);
      |                         ~~^~~~~~~~~~~~~

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