제출 #993946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993946		cpdreamer	Catfish Farm (IOI22_fish)	C++17	14 / 100	1104 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define V vector
#define pb push_back
struct segtree {
private:
    struct node {
        ll maxd;
    };

    node single(ll v) {
        return {v};
    }

    node neutral = {LLONG_MIN};

    node merge(node a, node b) {
        return {max(a.maxd, b.maxd)};
    }

public:
    int size;
    V<node> query;

    void init(int n) {
        size = 1;
        while (size < n)size *= 2;
        query.assign(2 * size, neutral);
    }

    void build(V<ll> &a, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < a.size()) {
                query[x] = single(a[lx]);
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
    }

    void build(V<ll> &a) {
        build(a, 0, 0, size);
    }

    node calc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l)
            return neutral;
        if (l <= lx && rx <= r)
            return query[x];
        int m = (lx + rx) / 2;
        node a = calc(l, r, 2 * x + 1, lx, m);
        node b = calc(l, r, 2 * x + 2, m, rx);
        return merge(a, b);
    }

    long long calc(int l, int r) {
        return calc(l, r, 0, 0, size).maxd;
    }
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    vector<vector<long long >> grid(N + 1, vector<long long>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        grid[X[i]][Y[i] + 1] += W[i];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= N; j++) {
            grid[i][j] += grid[i][j - 1];
        }
    }
    V<V<V<ll>>> dp(N, V<V<ll>>(N + 1, V<ll>(N + 1, 0)));
    V<V<V<ll>>> vp(N, V<V<ll>>(N + 1, V<ll>(N + 1, 0)));
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            dp[0][i][j] = max(0LL, grid[0][j] - grid[0][i]);
            vp[0][i][j] = dp[0][i][j] + max(0LL, grid[1][i] - grid[1][j]);
        }
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j <=min(N,10); j++) {
            V<ll> a;
            for (int g = 0; g <= min(N,10); g++)
                a.pb(dp[i - 1][g][j]);
            segtree tree_dp;
            tree_dp.init(N + 1);
            tree_dp.build(a);
            V<ll> b;
            for (int g = 0; g <= N; g++)
                b.pb(vp[i - 1][g][j]);
            segtree tree_vp;
            tree_vp.init(N + 1);
            tree_vp.build(b);
            for (int g = 0; g <= min(N,10); g++) {
                if (g <= j) {
                    dp[i][j][g] = tree_vp.calc(0, N + 1);
                } else {
                    dp[i][j][g] = max(tree_dp.calc(0, g + 1) + grid[i][g] - grid[i][j], tree_vp.calc(g, N + 1));
                }
                vp[i][j][g] = dp[i][j][g] + max(0LL, grid[i + 1][j] - grid[i + 1][g]);
            }
        }
    }
    ll ans = LLONG_MIN;
    for (int i = 0; i <= N; i++) {
        ans = max(ans, dp[N - 1][i][0]);
    }
    return ans;
}

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

fish.cpp: In member function 'void segtree::build(std::vector<long long int>&, int, int, int)':
fish.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~

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