Submission #785099

#	Time	Username	Problem	Language	Result	Execution time	Memory
785099		vjudge1	Catfish Farm (IOI22_fish)	C++17	0 / 100	1089 ms	16280 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) {
        // 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];
        if (c == -1 || lo > hi) {
            return 0LL;
        }
        ll s = 0;
        for (int i = 0; i < fish[c].size(); i++) {
            if (lo <= Y[fish[c][i]] && Y[fish[c][i]] < hi) {
                s += W[fish[c][i]];
            }
        }
        return s;
    };
    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 < cand.size(); j++) {
            for (int k = 0; k < h.size(); k++) {
                pd[j][0] = max(pd[j][0], dp[k][0] + get_sum(i - 1, h[k] + 1, cand[j] + 1));
                pd[j][1] = max(pd[j][1], dp[k][1] + get_sum(i, cand[j] + 1, h[k] + 1));
            }
        }
        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: In lambda function:
fish.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < fish[c].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:38:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int j = 0; j < fish[i - 1].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for (int j = 0; j < fish[i + 1].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~
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 < cand.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int k = 0; k < h.size(); k++) {
      |                             ~~^~~~~~~~~~

• 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