oj.uz

Submission #732695

# Submission time Handle Problem Language Result Execution time Memory
732695 2023-04-29T07:36:00 Z math_rabbit_1028 Catfish Farm (IOI22_fish) C++17
53 / 100
 593 ms 84100 KB 
#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

long long zero[101010], full[101010];
vector< pair<int, long long> > ylist[101010];
vector< long long > sum[101010], dp[2][101010];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for (int i = 0; i < M; i++) {
        X[i] += 1;
        Y[i] += 1;
        ylist[X[i]].push_back({Y[i], 0});
        ylist[X[i] - 1].push_back({Y[i], 0});
        ylist[X[i] + 1].push_back({Y[i], 0});
    }

    for (int i = 0; i <= N + 1; i++) {
        ylist[i].push_back({0, 0});
        ylist[i].push_back({N, 0});
        sort(ylist[i].begin(), ylist[i].end());
        ylist[i].erase(unique(ylist[i].begin(), ylist[i].end()), ylist[i].end());
    }

    for (int i = 0; i < M; i++) {
        int idx = lower_bound(ylist[X[i]].begin(), ylist[X[i]].end(), make_pair(Y[i], 0LL)) - ylist[X[i]].begin();
        ylist[X[i]][idx].second = W[i];
    }

    for (int i = 0; i <= N + 1; i++) {
        sum[i].push_back(0);
        for (int j = 1; j < ylist[i].size(); j++) {
            sum[i].push_back(sum[i].back() + ylist[i][j].second);
        }
    }

    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j < ylist[i].size(); j++) dp[0][i].push_back(0);
        for (int j = 0; j < ylist[i].size(); j++) dp[1][i].push_back(0);
    }
    for (int j = 1; j < ylist[0].size() - 1; j++) dp[0][0][j] = -1e18;
    for (int j = 1; j < ylist[0].size() - 1; j++) dp[1][0][j] = -1e18;
    full[0] = -1e18;
    for (int i = 2; i <= N + 1; i++) {
        vector<int> all;
        for (int t = 0; t < ylist[i - 2].size(); t++) all.push_back(ylist[i - 2][t].first);
        for (int t = 0; t < ylist[i - 1].size(); t++) all.push_back(ylist[i - 1][t].first);
        for (int t = 0; t < ylist[i].size(); t++) all.push_back(ylist[i][t].first);
        sort(all.begin(), all.end());
        all.erase(unique(all.begin(), all.end()), all.end());

        int j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            zero[i] = max(zero[i], dp[1][i - 1][k] + sum[i][j]);
        }
        zero[i] = max(zero[i], zero[i - 1]);
        zero[i] = max(zero[i], full[i - 1] + sum[i][ylist[i].size() - 1]);

        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            full[i] = max(full[i], dp[0][i - 1][k] + sum[i - 1][ylist[i - 1].size() - 1] - sum[i - 1][k]);
        }
        full[i] = max(full[i], full[i - 1]);
        full[i] = max(full[i], zero[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        full[i] = max(full[i], full[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            full[i] = max(full[i], dp[1][i - 2][l] + sum[i - 1][ylist[i - 1].size() - 1]);
        }

        long long val0 = 0, val1 = 0;
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            val0 = max(val0, dp[0][i - 1][k] - sum[i - 1][k]);
            val1 = max(val1, dp[1][i - 1][k] + sum[i][j]);
        }
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            dp[0][i][j] = max(dp[0][i][j], val0 + sum[i - 1][k]);
            dp[1][i][j] = max(dp[1][i][j], val1 - sum[i][j]);
            dp[1][i][j] = max(dp[1][i][j], full[i - 1] + sum[i][ylist[i].size() - 1] - sum[i][j]);
            dp[0][i][j] = max(dp[0][i][j], zero[i - 2] + sum[i - 1][k]);
            dp[0][i][j] = max(dp[0][i][j], full[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        }
        long long val2 = 0;
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            if (ylist[i][j].first != all[t]) continue;
            val2 = max(val2, dp[1][i - 2][l]);
            dp[0][i][j] = max(dp[0][i][j], val2 + sum[i - 1][k]);
        }
        long long val3 = 0;
        j = 0, k = 0, l = 0;
        for (int t = all.size() - 2; t >= 1; t--) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            if (ylist[i][j].first != all[t]) continue;
            val3 = max(val3, dp[1][i - 2][l] + sum[i - 1][k]);
            dp[0][i][j] = max(dp[0][i][j], val3);
        }
    }
    long long res = 0;
    res = zero[N + 1];
    return res;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:33: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]
   33 |         for (int j = 1; j < ylist[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:39: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]
   39 |         for (int j = 0; j < ylist[i].size(); j++) dp[0][i].push_back(0);
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:40: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]
   40 |         for (int j = 0; j < ylist[i].size(); j++) dp[1][i].push_back(0);
      |                         ~~^~~~~~~~~~~~~~~~~
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 j = 1; j < ylist[0].size() - 1; j++) dp[0][0][j] = -1e18;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:43: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]
   43 |     for (int j = 1; j < ylist[0].size() - 1; j++) dp[1][0][j] = -1e18;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:47: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]
   47 |         for (int t = 0; t < ylist[i - 2].size(); t++) all.push_back(ylist[i - 2][t].first);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:48: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]
   48 |         for (int t = 0; t < ylist[i - 1].size(); t++) all.push_back(ylist[i - 1][t].first);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:49: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]
   49 |         for (int t = 0; t < ylist[i].size(); t++) all.push_back(ylist[i][t].first);
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 36380 KB Output is correct
2 Correct 166 ms 41564 KB Output is correct
3 Correct 56 ms 25400 KB Output is correct
4 Correct 53 ms 25400 KB Output is correct
5 Correct 491 ms 71768 KB Output is correct
6 Correct 593 ms 84100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 262 ms 45676 KB Output is correct
3 Correct 249 ms 51076 KB Output is correct
4 Correct 143 ms 36340 KB Output is correct
5 Correct 183 ms 41772 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9792 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 53 ms 25340 KB Output is correct
11 Correct 52 ms 25400 KB Output is correct
12 Correct 160 ms 36400 KB Output is correct
13 Correct 198 ms 41772 KB Output is correct
14 Correct 159 ms 36924 KB Output is correct
15 Correct 150 ms 37424 KB Output is correct
16 Correct 170 ms 36928 KB Output is correct
17 Correct 167 ms 39192 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25424 KB Output is correct
2 Correct 52 ms 25348 KB Output is correct
3 Correct 107 ms 32940 KB Output is correct
4 Correct 118 ms 32068 KB Output is correct
5 Correct 201 ms 42708 KB Output is correct
6 Correct 167 ms 42500 KB Output is correct
7 Correct 191 ms 42448 KB Output is correct
8 Correct 168 ms 42560 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9796 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9792 KB Output is correct
8 Correct 8 ms 9792 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct
10 Correct 8 ms 10192 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 5 ms 9796 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9796 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9792 KB Output is correct
8 Correct 8 ms 9792 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct
10 Correct 8 ms 10192 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 5 ms 9796 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 7 ms 10152 KB Output is correct
17 Correct 45 ms 16564 KB Output is correct
18 Correct 47 ms 16032 KB Output is correct
19 Correct 50 ms 15796 KB Output is correct
20 Correct 38 ms 15408 KB Output is correct
21 Correct 36 ms 15436 KB Output is correct
22 Correct 69 ms 20776 KB Output is correct
23 Correct 20 ms 11660 KB Output is correct
24 Correct 42 ms 15008 KB Output is correct
25 Correct 7 ms 9956 KB Output is correct
26 Correct 17 ms 11560 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9796 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9792 KB Output is correct
8 Correct 8 ms 9792 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct
10 Correct 8 ms 10192 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 5 ms 9796 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 7 ms 10152 KB Output is correct
17 Correct 45 ms 16564 KB Output is correct
18 Correct 47 ms 16032 KB Output is correct
19 Correct 50 ms 15796 KB Output is correct
20 Correct 38 ms 15408 KB Output is correct
21 Correct 36 ms 15436 KB Output is correct
22 Correct 69 ms 20776 KB Output is correct
23 Correct 20 ms 11660 KB Output is correct
24 Correct 42 ms 15008 KB Output is correct
25 Correct 7 ms 9956 KB Output is correct
26 Correct 17 ms 11560 KB Output is correct
27 Correct 11 ms 11092 KB Output is correct
28 Correct 189 ms 35876 KB Output is correct
29 Correct 294 ms 48408 KB Output is correct
30 Incorrect 403 ms 77604 KB 1st lines differ - on the 1st token, expected: '102439236138254', found: '102440153599307'
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25424 KB Output is correct
2 Correct 52 ms 25348 KB Output is correct
3 Correct 107 ms 32940 KB Output is correct
4 Correct 118 ms 32068 KB Output is correct
5 Correct 201 ms 42708 KB Output is correct
6 Correct 167 ms 42500 KB Output is correct
7 Correct 191 ms 42448 KB Output is correct
8 Correct 168 ms 42560 KB Output is correct
9 Correct 202 ms 52172 KB Output is correct
10 Correct 124 ms 27608 KB Output is correct
11 Correct 258 ms 45004 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9712 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9796 KB Output is correct
18 Correct 52 ms 25392 KB Output is correct
19 Correct 73 ms 25340 KB Output is correct
20 Correct 77 ms 25376 KB Output is correct
21 Correct 61 ms 25372 KB Output is correct
22 Correct 298 ms 45500 KB Output is correct
23 Incorrect 405 ms 53836 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '77782926777237'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 36380 KB Output is correct
2 Correct 166 ms 41564 KB Output is correct
3 Correct 56 ms 25400 KB Output is correct
4 Correct 53 ms 25400 KB Output is correct
5 Correct 491 ms 71768 KB Output is correct
6 Correct 593 ms 84100 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 262 ms 45676 KB Output is correct
9 Correct 249 ms 51076 KB Output is correct
10 Correct 143 ms 36340 KB Output is correct
11 Correct 183 ms 41772 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 7 ms 9792 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 53 ms 25340 KB Output is correct
17 Correct 52 ms 25400 KB Output is correct
18 Correct 160 ms 36400 KB Output is correct
19 Correct 198 ms 41772 KB Output is correct
20 Correct 159 ms 36924 KB Output is correct
21 Correct 150 ms 37424 KB Output is correct
22 Correct 170 ms 36928 KB Output is correct
23 Correct 167 ms 39192 KB Output is correct
24 Correct 54 ms 25424 KB Output is correct
25 Correct 52 ms 25348 KB Output is correct
26 Correct 107 ms 32940 KB Output is correct
27 Correct 118 ms 32068 KB Output is correct
28 Correct 201 ms 42708 KB Output is correct
29 Correct 167 ms 42500 KB Output is correct
30 Correct 191 ms 42448 KB Output is correct
31 Correct 168 ms 42560 KB Output is correct
32 Correct 5 ms 9728 KB Output is correct
33 Correct 6 ms 9796 KB Output is correct
34 Correct 6 ms 9684 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Correct 7 ms 9684 KB Output is correct
37 Correct 6 ms 9684 KB Output is correct
38 Correct 7 ms 9792 KB Output is correct
39 Correct 8 ms 9792 KB Output is correct
40 Correct 8 ms 9876 KB Output is correct
41 Correct 8 ms 10192 KB Output is correct
42 Correct 6 ms 9940 KB Output is correct
43 Correct 7 ms 9940 KB Output is correct
44 Correct 5 ms 9796 KB Output is correct
45 Correct 6 ms 9940 KB Output is correct
46 Correct 6 ms 9812 KB Output is correct
47 Correct 7 ms 10152 KB Output is correct
48 Correct 45 ms 16564 KB Output is correct
49 Correct 47 ms 16032 KB Output is correct
50 Correct 50 ms 15796 KB Output is correct
51 Correct 38 ms 15408 KB Output is correct
52 Correct 36 ms 15436 KB Output is correct
53 Correct 69 ms 20776 KB Output is correct
54 Correct 20 ms 11660 KB Output is correct
55 Correct 42 ms 15008 KB Output is correct
56 Correct 7 ms 9956 KB Output is correct
57 Correct 17 ms 11560 KB Output is correct
58 Correct 11 ms 11092 KB Output is correct
59 Correct 189 ms 35876 KB Output is correct
60 Correct 294 ms 48408 KB Output is correct
61 Incorrect 403 ms 77604 KB 1st lines differ - on the 1st token, expected: '102439236138254', found: '102440153599307'
62 Halted 0 ms 0 KB -