oj.uz

Submission #763511

# Submission time Handle Problem Language Result Execution time Memory
763511 2023-06-22T11:45:14 Z raysh07 Catfish Farm (IOI22_fish) C++17
100 / 100
 887 ms 179676 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (long long)(1e18)
 
const int N = 1e5 + 69;
vector <int> ok[N];
map <int, long long> a[N];
unordered_map <int, long long> ac[N];
unordered_map <int, long long> dp[N][2];
vector <int> opt[N];
 
long long val(int i, int j){
    int idx = upper_bound(ok[i].begin(), ok[i].end(), j) - ok[i].begin() - 1;
    assert(idx >= 0);
    return ac[i][ok[i][idx]];
}
 
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for (int i = 0; i < m; i++){
        a[x[i] + 1][y[i] + 1] = w[i];
        ok[x[i] + 1].push_back(y[i] + 1);
    }
    ok[0].push_back(0);
    a[0][0] = 0;
    ok[n + 1].push_back(0);
    a[n + 1][0] = 0;
    ok[n + 2].push_back(0);
    a[n + 2][0] = 0;
    
    for (int i = 0; i < n; i++){
        a[i + 1][0] = 0;
        ok[i + 1].push_back(0);
        sort(ok[i + 1].begin(), ok[i + 1].end());
        
        long long v = 0;
        for (auto &[x, y] : a[i + 1]){
            v += y;
            y = v;
        }
    }
    
    for (int i = 0; i <= n + 2; i++){
        for (auto [x, y] : a[i]){
            ac[i][x] = y;
        }
    }
    
    dp[0][1][0] = dp[0][0][0] = 0; //0, 1 --> not processed / processed 
    opt[0].push_back(0);
    for (int i = 1; i <= n + 1; i++){
        for (int x : ok[i - 1]) opt[i].push_back(x);
        for (int x : ok[i + 1]) opt[i].push_back(x);
        
        sort(opt[i].begin(), opt[i].end());
        opt[i].erase(unique(opt[i].begin(), opt[i].end()), opt[i].end());
        
        for (int j : opt[i]){
            dp[i][0][j] = dp[i][1][j] = -INF;
        }
        if (i != (n + 1)){
        for (int j : opt[i]){
            if (j == 0) continue;
            dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][0] + val(i - 1, j) - val(i, j));
            dp[i][0][j] = max(dp[i][0][j], dp[i - 1][1][0] - val(i, j));
        }
        long long mx = -INF;
        int pt = 1;
        for (int j : opt[i]){
            if (j == 0) continue;
            while (pt != opt[i - 1].size() && opt[i - 1][pt] <= j){
                mx = max(mx, dp[i - 1][0][opt[i - 1][pt]]);
                pt++;
            }
            dp[i][0][j] = max(dp[i][0][j], mx - val(i, j) + val(i - 1, j));
        }
        
        mx = -INF;
        pt = opt[i - 1].size() - 1;
        for (int j : opt[i]){
            if (j == 0) continue;
            while (pt != 0 && opt[i - 1][pt] >= j){
                mx = max(mx, dp[i - 1][1][opt[i - 1][pt]]);
                pt--;
            }
            dp[i][1][j] = max(dp[i][1][j], mx - val(i, j) + val(i + 1, j));
        }
        for (int j : opt[i]){
            if (j == 0) continue;
            dp[i][1][j] = max(dp[i][1][j], dp[i][0][j] + val(i, j) + val(i + 1, j));
        }
        }
        for (int j : opt[i - 1]){
            if (j == 0) continue;
            dp[i][0][0] = max(dp[i][0][0], dp[i - 1][1][j] - val(i, j));
            dp[i][1][0] = max(dp[i][1][0], dp[i - 1][1][j]);
        }
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][0]);
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][1][0]);
    }
    
    long long sum = 0;
    for (int i = 0; i <= n + 1; i++){
        sum += dp[i][0].size();
        sum += dp[i][1].size();
    }
    
    assert(sum <= 2 * (2 * m + n + 2));
    
    long long ans = -INF;
    ans = max(ans, dp[n + 1][0][0]);
    ans = max(ans, dp[n + 1][1][0]);
    return ans;
}
 
// int main(){
//     int n, m; cin >> n >> m;
    
//     vector <int> a(m), b(m), c(m);
//     for (auto &x : a) cin >> x;
//     for (auto &x : b) cin >> x;
//     for (auto &x : c) cin >> x;
    
//     cout << max_weights(n, m, a, b, c) << "\n";
//     return 0;
// }

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while (pt != opt[i - 1].size() && opt[i - 1][pt] <= j){
      |                    ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 92620 KB Output is correct
2 Correct 196 ms 103748 KB Output is correct
3 Correct 93 ms 80828 KB Output is correct
4 Correct 81 ms 80928 KB Output is correct
5 Correct 679 ms 179676 KB Output is correct
6 Correct 687 ms 163032 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26088 KB Output is correct
2 Correct 340 ms 116684 KB Output is correct
3 Correct 412 ms 136004 KB Output is correct
4 Correct 166 ms 92692 KB Output is correct
5 Correct 207 ms 103876 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26036 KB Output is correct
8 Correct 13 ms 26160 KB Output is correct
9 Correct 13 ms 26096 KB Output is correct
10 Correct 81 ms 80928 KB Output is correct
11 Correct 79 ms 80904 KB Output is correct
12 Correct 204 ms 99560 KB Output is correct
13 Correct 235 ms 113252 KB Output is correct
14 Correct 188 ms 96116 KB Output is correct
15 Correct 230 ms 106364 KB Output is correct
16 Correct 206 ms 96164 KB Output is correct
17 Correct 213 ms 106232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 80836 KB Output is correct
2 Correct 79 ms 80880 KB Output is correct
3 Correct 135 ms 85288 KB Output is correct
4 Correct 121 ms 87628 KB Output is correct
5 Correct 201 ms 98892 KB Output is correct
6 Correct 189 ms 98880 KB Output is correct
7 Correct 198 ms 98884 KB Output is correct
8 Correct 207 ms 98892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26088 KB Output is correct
2 Correct 14 ms 26072 KB Output is correct
3 Correct 13 ms 26056 KB Output is correct
4 Correct 15 ms 26156 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26284 KB Output is correct
10 Correct 17 ms 26708 KB Output is correct
11 Correct 14 ms 26400 KB Output is correct
12 Correct 14 ms 26580 KB Output is correct
13 Correct 13 ms 26224 KB Output is correct
14 Correct 17 ms 26520 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26088 KB Output is correct
2 Correct 14 ms 26072 KB Output is correct
3 Correct 13 ms 26056 KB Output is correct
4 Correct 15 ms 26156 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26284 KB Output is correct
10 Correct 17 ms 26708 KB Output is correct
11 Correct 14 ms 26400 KB Output is correct
12 Correct 14 ms 26580 KB Output is correct
13 Correct 13 ms 26224 KB Output is correct
14 Correct 17 ms 26520 KB Output is correct
15 Correct 11 ms 26324 KB Output is correct
16 Correct 15 ms 26752 KB Output is correct
17 Correct 78 ms 37788 KB Output is correct
18 Correct 80 ms 37900 KB Output is correct
19 Correct 67 ms 37824 KB Output is correct
20 Correct 65 ms 37036 KB Output is correct
21 Correct 69 ms 36980 KB Output is correct
22 Correct 135 ms 48020 KB Output is correct
23 Correct 30 ms 28900 KB Output is correct
24 Correct 63 ms 34804 KB Output is correct
25 Correct 15 ms 26580 KB Output is correct
26 Correct 28 ms 28640 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26088 KB Output is correct
2 Correct 14 ms 26072 KB Output is correct
3 Correct 13 ms 26056 KB Output is correct
4 Correct 15 ms 26156 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26284 KB Output is correct
10 Correct 17 ms 26708 KB Output is correct
11 Correct 14 ms 26400 KB Output is correct
12 Correct 14 ms 26580 KB Output is correct
13 Correct 13 ms 26224 KB Output is correct
14 Correct 17 ms 26520 KB Output is correct
15 Correct 11 ms 26324 KB Output is correct
16 Correct 15 ms 26752 KB Output is correct
17 Correct 78 ms 37788 KB Output is correct
18 Correct 80 ms 37900 KB Output is correct
19 Correct 67 ms 37824 KB Output is correct
20 Correct 65 ms 37036 KB Output is correct
21 Correct 69 ms 36980 KB Output is correct
22 Correct 135 ms 48020 KB Output is correct
23 Correct 30 ms 28900 KB Output is correct
24 Correct 63 ms 34804 KB Output is correct
25 Correct 15 ms 26580 KB Output is correct
26 Correct 28 ms 28640 KB Output is correct
27 Correct 18 ms 28428 KB Output is correct
28 Correct 378 ms 82052 KB Output is correct
29 Correct 595 ms 115180 KB Output is correct
30 Correct 667 ms 118164 KB Output is correct
31 Correct 713 ms 118128 KB Output is correct
32 Correct 507 ms 101100 KB Output is correct
33 Correct 676 ms 118676 KB Output is correct
34 Correct 718 ms 118608 KB Output is correct
35 Correct 206 ms 61260 KB Output is correct
36 Correct 651 ms 115800 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 80836 KB Output is correct
2 Correct 79 ms 80880 KB Output is correct
3 Correct 135 ms 85288 KB Output is correct
4 Correct 121 ms 87628 KB Output is correct
5 Correct 201 ms 98892 KB Output is correct
6 Correct 189 ms 98880 KB Output is correct
7 Correct 198 ms 98884 KB Output is correct
8 Correct 207 ms 98892 KB Output is correct
9 Correct 221 ms 105132 KB Output is correct
10 Correct 141 ms 72312 KB Output is correct
11 Correct 323 ms 118496 KB Output is correct
12 Correct 14 ms 26076 KB Output is correct
13 Correct 14 ms 26156 KB Output is correct
14 Correct 13 ms 26068 KB Output is correct
15 Correct 13 ms 26068 KB Output is correct
16 Correct 13 ms 26036 KB Output is correct
17 Correct 13 ms 26068 KB Output is correct
18 Correct 80 ms 80868 KB Output is correct
19 Correct 91 ms 80912 KB Output is correct
20 Correct 84 ms 80980 KB Output is correct
21 Correct 79 ms 80800 KB Output is correct
22 Correct 242 ms 105764 KB Output is correct
23 Correct 367 ms 127436 KB Output is correct
24 Correct 372 ms 129376 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 92620 KB Output is correct
2 Correct 196 ms 103748 KB Output is correct
3 Correct 93 ms 80828 KB Output is correct
4 Correct 81 ms 80928 KB Output is correct
5 Correct 679 ms 179676 KB Output is correct
6 Correct 687 ms 163032 KB Output is correct
7 Correct 14 ms 26088 KB Output is correct
8 Correct 340 ms 116684 KB Output is correct
9 Correct 412 ms 136004 KB Output is correct
10 Correct 166 ms 92692 KB Output is correct
11 Correct 207 ms 103876 KB Output is correct
12 Correct 13 ms 26068 KB Output is correct
13 Correct 14 ms 26036 KB Output is correct
14 Correct 13 ms 26160 KB Output is correct
15 Correct 13 ms 26096 KB Output is correct
16 Correct 81 ms 80928 KB Output is correct
17 Correct 79 ms 80904 KB Output is correct
18 Correct 204 ms 99560 KB Output is correct
19 Correct 235 ms 113252 KB Output is correct
20 Correct 188 ms 96116 KB Output is correct
21 Correct 230 ms 106364 KB Output is correct
22 Correct 206 ms 96164 KB Output is correct
23 Correct 213 ms 106232 KB Output is correct
24 Correct 88 ms 80836 KB Output is correct
25 Correct 79 ms 80880 KB Output is correct
26 Correct 135 ms 85288 KB Output is correct
27 Correct 121 ms 87628 KB Output is correct
28 Correct 201 ms 98892 KB Output is correct
29 Correct 189 ms 98880 KB Output is correct
30 Correct 198 ms 98884 KB Output is correct
31 Correct 207 ms 98892 KB Output is correct
32 Correct 15 ms 26088 KB Output is correct
33 Correct 14 ms 26072 KB Output is correct
34 Correct 13 ms 26056 KB Output is correct
35 Correct 15 ms 26156 KB Output is correct
36 Correct 13 ms 26068 KB Output is correct
37 Correct 13 ms 26068 KB Output is correct
38 Correct 13 ms 26068 KB Output is correct
39 Correct 13 ms 26068 KB Output is correct
40 Correct 14 ms 26284 KB Output is correct
41 Correct 17 ms 26708 KB Output is correct
42 Correct 14 ms 26400 KB Output is correct
43 Correct 14 ms 26580 KB Output is correct
44 Correct 13 ms 26224 KB Output is correct
45 Correct 17 ms 26520 KB Output is correct
46 Correct 11 ms 26324 KB Output is correct
47 Correct 15 ms 26752 KB Output is correct
48 Correct 78 ms 37788 KB Output is correct
49 Correct 80 ms 37900 KB Output is correct
50 Correct 67 ms 37824 KB Output is correct
51 Correct 65 ms 37036 KB Output is correct
52 Correct 69 ms 36980 KB Output is correct
53 Correct 135 ms 48020 KB Output is correct
54 Correct 30 ms 28900 KB Output is correct
55 Correct 63 ms 34804 KB Output is correct
56 Correct 15 ms 26580 KB Output is correct
57 Correct 28 ms 28640 KB Output is correct
58 Correct 18 ms 28428 KB Output is correct
59 Correct 378 ms 82052 KB Output is correct
60 Correct 595 ms 115180 KB Output is correct
61 Correct 667 ms 118164 KB Output is correct
62 Correct 713 ms 118128 KB Output is correct
63 Correct 507 ms 101100 KB Output is correct
64 Correct 676 ms 118676 KB Output is correct
65 Correct 718 ms 118608 KB Output is correct
66 Correct 206 ms 61260 KB Output is correct
67 Correct 651 ms 115800 KB Output is correct
68 Correct 221 ms 105132 KB Output is correct
69 Correct 141 ms 72312 KB Output is correct
70 Correct 323 ms 118496 KB Output is correct
71 Correct 14 ms 26076 KB Output is correct
72 Correct 14 ms 26156 KB Output is correct
73 Correct 13 ms 26068 KB Output is correct
74 Correct 13 ms 26068 KB Output is correct
75 Correct 13 ms 26036 KB Output is correct
76 Correct 13 ms 26068 KB Output is correct
77 Correct 80 ms 80868 KB Output is correct
78 Correct 91 ms 80912 KB Output is correct
79 Correct 84 ms 80980 KB Output is correct
80 Correct 79 ms 80800 KB Output is correct
81 Correct 242 ms 105764 KB Output is correct
82 Correct 367 ms 127436 KB Output is correct
83 Correct 372 ms 129376 KB Output is correct
84 Correct 887 ms 164008 KB Output is correct
85 Correct 843 ms 173160 KB Output is correct
86 Correct 645 ms 157424 KB Output is correct
87 Correct 664 ms 163704 KB Output is correct
88 Correct 13 ms 26156 KB Output is correct
89 Correct 733 ms 163552 KB Output is correct
90 Correct 609 ms 163040 KB Output is correct
91 Correct 511 ms 155084 KB Output is correct