oj.uz

Submission #1074365

# Submission time Handle Problem Language Result Execution time Memory
1074365 2024-08-25T10:06:04 Z zsombor Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 37712 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m, ans = 0;
vector<vector<pair<int, ll> > > f(2e5);
vector<vector<ll> > dp1(2e5);
vector<vector<ll> > dp2(2e5);

void get_dp1(int i, int j) {
    ll h0, h = f[i][j].first - 1, val = 0;
    for (auto p: f[i]) if (p.first <= h) val -= p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        if (h0 < h) continue;
        dp1[i][j] = max(dp1[i][j], dp1[i - 1][k] + val);
        dp1[i][j] = max(dp1[i][j], dp2[i - 1][k] + val);
    }
    ans = max(ans, dp1[i][j]);
}

void get_dp2(int i, int j) {
    ll h0, h = f[i][j].first - 1, val = 0, nxt = 0;
    for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 1].size(); k++) {
        h0 = f[i - 1][k].first - 1;
        if (h0 >= h) break;
        if (k) val -= f[i - 1][k - 1].second;
        while (h0 >= f[i][nxt].first) val -= f[i][nxt++].second;
        dp2[i][j] = max(dp2[i][j], dp2[i - 1][k] + val);
    }
    if (i == 1) {
        ans = max(ans, dp2[i][j]);
        return;
    }
    val = nxt = 0;
    for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
    for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
    for (int k = 0; k < f[i - 2].size(); k++) {
        h0 = f[i - 2][k].first - 1;
        while (h0 >= f[i - 1][nxt].first && h0 >= f[i - 1][nxt].first) val -= f[i - 1][nxt++].second;
        dp2[i][j] = max(dp2[i][j], dp1[i - 2][k] + val);
        dp2[i][j] = max(dp2[i][j], dp2[i - 2][k] + val);
    }
    ans = max(ans, dp2[i][j]);
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        X[i]++;
        Y[i]++;
        f[X[i]].push_back({Y[i], W[i]});
    }
    f[0].push_back({1, 0});
    for (int i = 0; i <= n + 1; i++) {
        f[i].push_back({n + 1, 0});
        sort(f[i].begin(), f[i].end());
    }
    dp1[0] = dp2[0] = {0ll, ll(-1e18)};
    for (int i = 1; i <= n; i++) {
        dp1[i].resize(f[i].size(), 0);
        dp2[i].resize(f[i].size(), 0);
        for (int j = 0; j < f[i].size(); j++) {
            get_dp1(i, j);
            get_dp2(i, j);
        }
    }
    return ans;
}

Compilation message

fish.cpp: In function 'void get_dp1(int, int)':
fish.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'void get_dp2(int, int)':
fish.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int k = 0; k < f[i - 1].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int k = 0; k < f[i - 2].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 0; j < f[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 22976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14428 KB Output is correct
2 Execution timed out 1086 ms 27660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23900 KB Output is correct
2 Correct 36 ms 23896 KB Output is correct
3 Correct 46 ms 25968 KB Output is correct
4 Correct 41 ms 25936 KB Output is correct
5 Correct 70 ms 29856 KB Output is correct
6 Correct 72 ms 29268 KB Output is correct
7 Correct 63 ms 29832 KB Output is correct
8 Correct 62 ms 29900 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14428 KB Output is correct
2 Correct 6 ms 14496 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 7 ms 14464 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 8 ms 14544 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Correct 7 ms 14536 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 10 ms 14768 KB Output is correct
11 Correct 8 ms 14460 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 7 ms 14428 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14428 KB Output is correct
2 Correct 6 ms 14496 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 7 ms 14464 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 8 ms 14544 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Correct 7 ms 14536 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 10 ms 14768 KB Output is correct
11 Correct 8 ms 14460 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 7 ms 14428 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 9 ms 14428 KB Output is correct
16 Correct 9 ms 14492 KB Output is correct
17 Correct 109 ms 17732 KB Output is correct
18 Correct 120 ms 18460 KB Output is correct
19 Correct 78 ms 18232 KB Output is correct
20 Correct 92 ms 18328 KB Output is correct
21 Correct 81 ms 18224 KB Output is correct
22 Correct 274 ms 21936 KB Output is correct
23 Correct 13 ms 15172 KB Output is correct
24 Correct 44 ms 16644 KB Output is correct
25 Correct 8 ms 14440 KB Output is correct
26 Correct 13 ms 15204 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14428 KB Output is correct
2 Correct 6 ms 14496 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 7 ms 14464 KB Output is correct
5 Correct 7 ms 14428 KB Output is correct
6 Correct 8 ms 14544 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Correct 7 ms 14536 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 10 ms 14768 KB Output is correct
11 Correct 8 ms 14460 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 7 ms 14428 KB Output is correct
14 Correct 7 ms 14428 KB Output is correct
15 Correct 9 ms 14428 KB Output is correct
16 Correct 9 ms 14492 KB Output is correct
17 Correct 109 ms 17732 KB Output is correct
18 Correct 120 ms 18460 KB Output is correct
19 Correct 78 ms 18232 KB Output is correct
20 Correct 92 ms 18328 KB Output is correct
21 Correct 81 ms 18224 KB Output is correct
22 Correct 274 ms 21936 KB Output is correct
23 Correct 13 ms 15172 KB Output is correct
24 Correct 44 ms 16644 KB Output is correct
25 Correct 8 ms 14440 KB Output is correct
26 Correct 13 ms 15204 KB Output is correct
27 Correct 8 ms 14944 KB Output is correct
28 Execution timed out 1079 ms 32012 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23900 KB Output is correct
2 Correct 36 ms 23896 KB Output is correct
3 Correct 46 ms 25968 KB Output is correct
4 Correct 41 ms 25936 KB Output is correct
5 Correct 70 ms 29856 KB Output is correct
6 Correct 72 ms 29268 KB Output is correct
7 Correct 63 ms 29832 KB Output is correct
8 Correct 62 ms 29900 KB Output is correct
9 Correct 59 ms 29596 KB Output is correct
10 Correct 75 ms 25800 KB Output is correct
11 Correct 133 ms 37204 KB Output is correct
12 Correct 10 ms 14684 KB Output is correct
13 Correct 7 ms 14428 KB Output is correct
14 Correct 10 ms 14484 KB Output is correct
15 Correct 10 ms 14428 KB Output is correct
16 Correct 7 ms 14428 KB Output is correct
17 Correct 6 ms 14428 KB Output is correct
18 Correct 33 ms 23776 KB Output is correct
19 Correct 20 ms 23888 KB Output is correct
20 Correct 20 ms 23900 KB Output is correct
21 Correct 22 ms 23696 KB Output is correct
22 Correct 54 ms 30408 KB Output is correct
23 Correct 90 ms 37204 KB Output is correct
24 Correct 94 ms 37712 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 22976 KB Time limit exceeded
2 Halted 0 ms 0 KB -