oj.uz

Submission #732594

# Submission time Handle Problem Language Result Execution time Memory
732594 2023-04-29T06:32:33 Z math_rabbit_1028 Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 77688 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());

        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            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]);

        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            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]);
        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            full[i] = max(full[i], dp[1][i - 2][l] + sum[i - 1][ylist[i - 1].size() - 1]);
        }

        long long val0 = 0, val1 = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            val0 = max(val0, dp[0][i - 1][k] - sum[i - 1][k]);
            val1 = max(val1, dp[1][i - 1][k] + sum[i][j]);
        }
        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            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;
        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            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;
        for (int t = 1; t < all.size() - 1; t++) {
            int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
            int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
            int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
            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:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:56:17: warning: unused variable 'l' [-Wunused-variable]
   56 |             int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
      |                 ^
fish.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:63:17: warning: unused variable 'j' [-Wunused-variable]
   63 |             int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
      |                 ^
fish.cpp:65:17: warning: unused variable 'l' [-Wunused-variable]
   65 |             int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
      |                 ^
fish.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:72:17: warning: unused variable 'j' [-Wunused-variable]
   72 |             int j = lower_bound(ylist[i].begin(), ylist[i].end(), make_pair(all[t], 0LL)) - ylist[i].begin();
      |                 ^
fish.cpp:73:17: warning: unused variable 'k' [-Wunused-variable]
   73 |             int k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].begin();
      |                 ^
fish.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:82:17: warning: unused variable 'l' [-Wunused-variable]
   82 |             int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
      |                 ^
fish.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:89:17: warning: unused variable 'l' [-Wunused-variable]
   89 |             int l = lower_bound(ylist[i - 2].begin(), ylist[i - 2].end(), make_pair(all[t], 0LL)) - ylist[i - 2].begin();
      |                 ^
fish.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 36340 KB Output is correct
2 Correct 298 ms 41524 KB Output is correct
3 Correct 69 ms 25428 KB Output is correct
4 Correct 54 ms 25440 KB Output is correct
5 Execution timed out 1088 ms 71684 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 410 ms 45564 KB Output is correct
3 Correct 446 ms 51056 KB Output is correct
4 Correct 261 ms 36184 KB Output is correct
5 Correct 296 ms 41580 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9728 KB Output is correct
8 Correct 6 ms 9796 KB Output is correct
9 Correct 5 ms 9796 KB Output is correct
10 Correct 61 ms 25420 KB Output is correct
11 Correct 60 ms 25436 KB Output is correct
12 Correct 337 ms 36324 KB Output is correct
13 Correct 356 ms 41484 KB Output is correct
14 Correct 301 ms 36796 KB Output is correct
15 Correct 241 ms 37232 KB Output is correct
16 Correct 305 ms 36796 KB Output is correct
17 Correct 322 ms 39112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 25412 KB Output is correct
2 Correct 60 ms 25420 KB Output is correct
3 Correct 127 ms 32792 KB Output is correct
4 Correct 112 ms 31876 KB Output is correct
5 Correct 179 ms 42508 KB Output is correct
6 Correct 182 ms 42336 KB Output is correct
7 Correct 179 ms 42428 KB Output is correct
8 Correct 171 ms 42504 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9792 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9796 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9904 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9936 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 9900 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9792 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9796 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9904 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9936 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 9900 KB Output is correct
15 Correct 8 ms 9920 KB Output is correct
16 Correct 8 ms 10068 KB Output is correct
17 Correct 75 ms 16724 KB Output is correct
18 Correct 68 ms 16100 KB Output is correct
19 Correct 73 ms 15844 KB Output is correct
20 Correct 59 ms 15556 KB Output is correct
21 Correct 53 ms 15564 KB Output is correct
22 Correct 114 ms 20956 KB Output is correct
23 Correct 32 ms 11700 KB Output is correct
24 Correct 76 ms 15216 KB Output is correct
25 Correct 8 ms 9940 KB Output is correct
26 Correct 30 ms 11584 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9792 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9796 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9904 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9936 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 9900 KB Output is correct
15 Correct 8 ms 9920 KB Output is correct
16 Correct 8 ms 10068 KB Output is correct
17 Correct 75 ms 16724 KB Output is correct
18 Correct 68 ms 16100 KB Output is correct
19 Correct 73 ms 15844 KB Output is correct
20 Correct 59 ms 15556 KB Output is correct
21 Correct 53 ms 15564 KB Output is correct
22 Correct 114 ms 20956 KB Output is correct
23 Correct 32 ms 11700 KB Output is correct
24 Correct 76 ms 15216 KB Output is correct
25 Correct 8 ms 9940 KB Output is correct
26 Correct 30 ms 11584 KB Output is correct
27 Correct 11 ms 11092 KB Output is correct
28 Correct 342 ms 36004 KB Output is correct
29 Correct 591 ms 48460 KB Output is correct
30 Execution timed out 1040 ms 77688 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 25412 KB Output is correct
2 Correct 60 ms 25420 KB Output is correct
3 Correct 127 ms 32792 KB Output is correct
4 Correct 112 ms 31876 KB Output is correct
5 Correct 179 ms 42508 KB Output is correct
6 Correct 182 ms 42336 KB Output is correct
7 Correct 179 ms 42428 KB Output is correct
8 Correct 171 ms 42504 KB Output is correct
9 Correct 220 ms 51976 KB Output is correct
10 Correct 137 ms 27412 KB Output is correct
11 Correct 280 ms 44876 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 7 ms 9792 KB Output is correct
16 Correct 5 ms 9792 KB Output is correct
17 Correct 5 ms 9796 KB Output is correct
18 Correct 53 ms 25352 KB Output is correct
19 Correct 54 ms 25440 KB Output is correct
20 Correct 53 ms 25336 KB Output is correct
21 Correct 60 ms 25408 KB Output is correct
22 Correct 355 ms 45396 KB Output is correct
23 Incorrect 367 ms 57196 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 233 ms 36340 KB Output is correct
2 Correct 298 ms 41524 KB Output is correct
3 Correct 69 ms 25428 KB Output is correct
4 Correct 54 ms 25440 KB Output is correct
5 Execution timed out 1088 ms 71684 KB Time limit exceeded
6 Halted 0 ms 0 KB -