제출 #785131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785131		vjudge1	Catfish Farm (IOI22_fish)	C++17	100 / 100	292 ms	27408 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 || c >= N) {
            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<ll> dp0{0}, dp1{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<ll> pmax(h.size() + 1);
        for (int j = 0; j < h.size(); j++) {
            pmax[j + 1] = max(pmax[j], dp0[j] + get_sum(i - 1, h[j] + 1, N));
        }
        vector<ll> smax(h.size() + 1);
        for (int j = h.size() - 1; j >= 0; j--) {
            smax[j] = max(smax[j + 1], dp1[j] + get_sum(i, 0, h[j] + 1));
        }
        vector<ll> pd0(cand.size());
        vector<ll> pd1(cand.size());
        pd1[0] = smax[0];
        for (int j = 0; j < h.size(); j++) {
            pd0[0] = max(pd0[0], dp1[j]);
        }
        for (int j = 1; j < cand.size(); j++) {
            int k = upper_bound(h.begin(), h.end(), cand[j]) - h.begin();
            pd0[j] = max(dp1[0], pmax[k] - get_sum(i - 1, cand[j] + 1, N));
            pd1[j] = max(pd0[j], smax[k] - get_sum(i, 0, cand[j] + 1));
        }
        swap(dp0, pd0);
        swap(dp1, pd1);
        swap(h, cand);
    }
    ll ans = 0;
    for (auto &v : dp1) {
        ans = max(ans, v);
    }
    return ans;
}

컴파일 시 표준 에러 (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:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int j = 0; j < h.size(); j++) {
      |                         ~~^~~~~~~~~~
fish.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j = 1; j < cand.size(); j++) {
      |                         ~~^~~~~~~~~~~~~

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