Submission #785110

#	Time	Username	Problem	Language	Result	Execution time	Memory
785110		vjudge1	Catfish Farm (IOI22_fish)	C++17	40 / 100	1084 ms	20984 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<int>> fish(N);
    for (int i = 0; i < M; i++) {
        fish[X[i]].push_back(i);
    }
    vector<vector<ll>> pfs(N);
    for (int i = 0; i < N; i++) {
        sort(fish[i].begin(), fish[i].end(), [&](int x, int y) {return Y[x] < Y[y];});
        pfs[i].resize(fish[i].size() + 1);
        for (int j = 0; j < fish[i].size(); j++) {
            pfs[i][j + 1] = pfs[i][j] + W[fish[i][j]];
        }
    }
    auto get_sum = [&](int c, int lo, int hi) {
        if (c == -1 || lo > hi) {
            return 0LL;
        }
        int x = lower_bound(fish[c].begin(), fish[c].end(), lo, [&](int i, int t) {return Y[i] < t;}) - fish[c].begin();
        int y = lower_bound(fish[c].begin(), fish[c].end(), hi, [&](int i, int t) {return Y[i] < t;}) - fish[c].begin();
        return pfs[c][y] - pfs[c][x];
    };
    vector<array<ll, 2>> dp{{0, 0}};
    vector<int> h{-1};
    for (int i = 0; i < N; i++) {
        vector<int> cand{-1};
        if (i) {
            for (int j = 0; j < fish[i - 1].size(); j++) {
                cand.push_back(Y[fish[i - 1][j]]);
            }
        }
        if (i < N - 1) {
            for (int j = 0; j < fish[i + 1].size(); j++) {
                cand.push_back(Y[fish[i + 1][j]]);
            }
        }
        sort(cand.begin(), cand.end());
        vector pd(cand.size(), array<ll, 2>{0, 0});
        for (int j = 0; j < h.size(); j++) {
            pd[0][0] = max(pd[0][0], dp[j][1]);
            pd[0][1] = max(pd[0][1], dp[j][1] + get_sum(i, 0, h[j] + 1));
        }
        for (int j = 1; j < cand.size(); j++) {
            for (int k = 0; k < h.size(); k++) {
                if (h[k] <= cand[j]) {
                    pd[j][0] = max(pd[j][0], dp[k][0] + get_sum(i - 1, h[k] + 1, cand[j] + 1));
                }
                if (h[k] > cand[j]) {
                    pd[j][1] = max(pd[j][1], dp[k][1] + get_sum(i, cand[j] + 1, h[k] + 1));
                }
                pd[j][0] = max(pd[j][0], dp[0][1]);
                pd[j][1] = max(pd[j][1], pd[j][0]);
            }
        }
        swap(dp, pd);
        swap(h, cand);
    }
    ll ans = 0;
    for (auto &v : dp) {
        ans = max({ans, v[0], v[1]});
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:14:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for (int j = 0; j < fish[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:31:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int j = 0; j < fish[i - 1].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:36:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int j = 0; j < fish[i + 1].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j = 0; j < h.size(); j++) {
      |                         ~~^~~~~~~~~~
fish.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 1; j < cand.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int k = 0; k < h.size(); k++) {
      |                             ~~^~~~~~~~~~

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