oj.uz

Submission #993946

# Submission time Handle Problem Language Result Execution time Memory
993946 2024-06-06T21:26:05 Z cpdreamer Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 848 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1104 ms 2097152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 815 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 0 ms 608 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 612 KB Output is correct
9 Correct 31 ms 55644 KB Output is correct
10 Correct 189 ms 433124 KB Output is correct
11 Correct 31 ms 55640 KB Output is correct
12 Correct 190 ms 432988 KB Output is correct
13 Correct 5 ms 7524 KB Output is correct
14 Correct 185 ms 432856 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 0 ms 608 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 612 KB Output is correct
9 Correct 31 ms 55644 KB Output is correct
10 Correct 189 ms 433124 KB Output is correct
11 Correct 31 ms 55640 KB Output is correct
12 Correct 190 ms 432988 KB Output is correct
13 Correct 5 ms 7524 KB Output is correct
14 Correct 185 ms 432856 KB Output is correct
15 Incorrect 190 ms 432856 KB 1st lines differ - on the 1st token, expected: '299', found: '10'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 0 ms 608 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 612 KB Output is correct
9 Correct 31 ms 55644 KB Output is correct
10 Correct 189 ms 433124 KB Output is correct
11 Correct 31 ms 55640 KB Output is correct
12 Correct 190 ms 432988 KB Output is correct
13 Correct 5 ms 7524 KB Output is correct
14 Correct 185 ms 432856 KB Output is correct
15 Incorrect 190 ms 432856 KB 1st lines differ - on the 1st token, expected: '299', found: '10'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 815 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 848 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -