Submission #713248

#	Time	Username	Problem	Language	Result	Execution time	Memory
713248		t6twotwo	Catfish Farm (IOI22_fish)	C++17	0 / 100	1070 ms	20300 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int64_t>> solve(vector<vector<int>> &pos, vector<vector<array<int, 2>>> &w) {
    int N = pos.size() - 1;
    vector<vector<int64_t>> dp(N + 1);
    dp[0].push_back(0);
    for (int i = 1; i <= N; i++) {
        int M = pos[i].size();
        dp[i].resize(M);
        for (int j = 0, l = 0; j < M; j++) {
            int64_t add = 0;
            for (int k = 0; k < w[i - 1].size() && w[i - 1][k][0] <= pos[i][j]; k++) {
                add += w[i - 1][k][1];
            }
            for (int k = 0; k < pos[i - 1].size() && pos[i - 1][k] <= pos[i][j]; k++) {
                while (l < w[i - 1].size() && w[i - 1][l][0] <= pos[i - 1][k]) {
                    add -= w[i - 1][l][1];
                    l++;
                }
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + add);
            }
        }
    }
    return dp;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<array<int, 2>>> w(N + 1);
    for (int i = 0; i < M; i++) {
        w[X[i] + 1].push_back({Y[i], W[i]});
    }
    vector pos(N + 1, vector<int>{-1});
    for (int i = 1; i <= N; i++) {
        sort(w[i].begin(), w[i].end());
        for (auto [x, _] : w[i]) {
            if (i > 1) pos[i - 1].push_back(x);
            if (i < N) pos[i + 1].push_back(x);
        }
    }
    for (int i = 1; i <= N; i++) {
        sort(pos[i].begin(), pos[i].end());
    }
    auto dp1 = solve(pos, w);
    reverse(pos.begin() + 1, pos.end());
    reverse(w.begin() + 1, w.end());
    auto dp2 = solve(pos, w);
    int64_t ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < pos[i + 1].size(); j++) {
            ans = max(ans, dp1[N - i][j] + dp2[i + 1][j]);
        }
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'std::vector<std::vector<long int> > solve(std::vector<std::vector<int> >&, std::vector<std::vector<std::array<int, 2> > >&)':
fish.cpp:13:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |             for (int k = 0; k < w[i - 1].size() && w[i - 1][k][0] <= pos[i][j]; k++) {
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:16:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for (int k = 0; k < pos[i - 1].size() && pos[i - 1][k] <= pos[i][j]; k++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |                 while (l < w[i - 1].size() && w[i - 1][l][0] <= pos[i - 1][k]) {
      |                        ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 0; j < pos[i + 1].size(); 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