제출 #627537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627537		dqhungdl	메기 농장 (IOI22_fish)	C++17	40 / 100	1086 ms	55276 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
const int MAX = 1e5 + 5;
bool markLow[MAX];
vector<ii> g[MAX];
vector<long long> S[MAX];
vector<vector<long long>> f[MAX];

long long calcCost(int col, int L, int R) {
    int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
    int r = upper_bound(g[col].begin(), g[col].end(), ii(R, 0)) - g[col].begin() - 1;
    if (l <= r)
        return S[col][r] - (l ? S[col][l - 1] : 0);
    return 0;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < M; i++) {
        g[X[i]].emplace_back(Y[i], W[i]);
        if (!Y[i])
            markLow[X[i]] = true;
    }
    for (int i = 0; i < N; i++) {
        if (!markLow[i])
            g[i].emplace_back(0, 0);
        g[i].emplace_back(N, 0);
    }
    for (int i = 0; i < N; i++) {
        sort(g[i].begin(), g[i].end());
        S[i].resize(g[i].size());
        S[i][0] = g[i][0].second;
        for (int j = 1; j < g[i].size(); j++)
            S[i][j] = S[i][j - 1] + g[i][j].second;
        f[i].resize(g[i].size(), vector<long long>(2));
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            if (i > 1) {
                for (int t = 0; t < g[i - 2].size(); t++) {
                    long long tmp = f[i - 2][t][1] + calcCost(i - 1, 0, max(g[i - 2][t].first, g[i][j].first));
                    f[i][j][0] = max(f[i][j][0], tmp);
                    f[i][j][1] = max(f[i][j][1], tmp);
                }
            } else {
                long long tmp = calcCost(0, 0, g[i][j].first);
                f[i][j][0] = max(f[i][j][0], tmp);
                f[i][j][1] = max(f[i][j][1], tmp);
            }
            for (int t = 0; t < g[i - 1].size(); t++) {
                if (g[i - 1][t].first <= g[i][j].first) {
                    f[i][j][0] = max(f[i][j][0], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
                    f[i][j][1] = max(f[i][j][1], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
                }
                if (g[i - 1][t].first >= g[i][j].first)
                    f[i][j][1] = max(f[i][j][1], f[i - 1][t][1] + calcCost(i, g[i][j].first, g[i - 1][t].first));
            }
        }
    }
    long long rs = 0;
    for (int j = 0; j < f[N - 1].size(); j++)
        rs = max({rs, f[N - 1][j][0], f[N - 1][j][1]});
    return rs;
}

//int main() {
//    freopen("../_input", "r", stdin);
//    int N, M;
//    assert(2 == scanf("%d %d", &N, &M));
//
//    std::vector<int> X(M), Y(M), W(M);
//    for (int i = 0; i < M; ++i) {
//        assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//    }
//
//    long long result = max_weights(N, M, X, Y, W);
//    printf("%lld\n", result);
//    return 0;
//}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 1; j < g[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
fish.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < g[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 for (int t = 0; t < g[i - 2].size(); t++) {
      |                                 ~~^~~~~~~~~~~~~~~~~
fish.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int t = 0; t < g[i - 1].size(); t++) {
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int j = 0; j < f[N - 1].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~

• 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