oj.uz

Submission #732614

# Submission time Handle Problem Language Result Execution time Memory
732614 2023-04-29T06:41:39 Z math_rabbit_1028 Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 77416 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();
            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 k = lower_bound(ylist[i - 1].begin(), ylist[i - 1].end(), make_pair(all[t], 0LL)) - ylist[i - 1].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 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();
            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();
            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:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         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:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 36056 KB Output is correct
2 Correct 285 ms 41400 KB Output is correct
3 Correct 56 ms 25448 KB Output is correct
4 Correct 58 ms 25416 KB Output is correct
5 Execution timed out 1081 ms 71480 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 381 ms 45280 KB Output is correct
3 Correct 449 ms 50792 KB Output is correct
4 Correct 251 ms 36144 KB Output is correct
5 Correct 285 ms 41376 KB Output is correct
6 Correct 6 ms 9736 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9752 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 57 ms 25316 KB Output is correct
11 Correct 57 ms 25344 KB Output is correct
12 Correct 296 ms 36192 KB Output is correct
13 Correct 368 ms 41480 KB Output is correct
14 Correct 288 ms 36660 KB Output is correct
15 Correct 255 ms 37340 KB Output is correct
16 Correct 276 ms 36648 KB Output is correct
17 Correct 345 ms 38852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25344 KB Output is correct
2 Correct 55 ms 25420 KB Output is correct
3 Correct 106 ms 32572 KB Output is correct
4 Correct 97 ms 31812 KB Output is correct
5 Correct 172 ms 42204 KB Output is correct
6 Correct 193 ms 42344 KB Output is correct
7 Correct 179 ms 42208 KB Output is correct
8 Correct 167 ms 42196 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 8 ms 9704 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9764 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 8 ms 10052 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 9828 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 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 8 ms 9704 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9764 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 8 ms 10052 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 9828 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 8 ms 10068 KB Output is correct
17 Correct 77 ms 16352 KB Output is correct
18 Correct 73 ms 15664 KB Output is correct
19 Correct 63 ms 15540 KB Output is correct
20 Correct 52 ms 15196 KB Output is correct
21 Correct 61 ms 15196 KB Output is correct
22 Correct 110 ms 20648 KB Output is correct
23 Correct 33 ms 11564 KB Output is correct
24 Correct 70 ms 14796 KB Output is correct
25 Correct 8 ms 10008 KB Output is correct
26 Correct 28 ms 11348 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 8 ms 9704 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9764 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 8 ms 10052 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 9828 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 8 ms 10068 KB Output is correct
17 Correct 77 ms 16352 KB Output is correct
18 Correct 73 ms 15664 KB Output is correct
19 Correct 63 ms 15540 KB Output is correct
20 Correct 52 ms 15196 KB Output is correct
21 Correct 61 ms 15196 KB Output is correct
22 Correct 110 ms 20648 KB Output is correct
23 Correct 33 ms 11564 KB Output is correct
24 Correct 70 ms 14796 KB Output is correct
25 Correct 8 ms 10008 KB Output is correct
26 Correct 28 ms 11348 KB Output is correct
27 Correct 11 ms 10964 KB Output is correct
28 Correct 305 ms 35616 KB Output is correct
29 Correct 613 ms 48080 KB Output is correct
30 Execution timed out 1063 ms 77416 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25344 KB Output is correct
2 Correct 55 ms 25420 KB Output is correct
3 Correct 106 ms 32572 KB Output is correct
4 Correct 97 ms 31812 KB Output is correct
5 Correct 172 ms 42204 KB Output is correct
6 Correct 193 ms 42344 KB Output is correct
7 Correct 179 ms 42208 KB Output is correct
8 Correct 167 ms 42196 KB Output is correct
9 Correct 236 ms 51968 KB Output is correct
10 Correct 115 ms 27196 KB Output is correct
11 Correct 247 ms 44728 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 57 ms 25428 KB Output is correct
19 Correct 57 ms 25420 KB Output is correct
20 Correct 55 ms 25440 KB Output is correct
21 Correct 54 ms 25420 KB Output is correct
22 Correct 329 ms 45168 KB Output is correct
23 Incorrect 377 ms 53616 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 261 ms 36056 KB Output is correct
2 Correct 285 ms 41400 KB Output is correct
3 Correct 56 ms 25448 KB Output is correct
4 Correct 58 ms 25416 KB Output is correct
5 Execution timed out 1081 ms 71480 KB Time limit exceeded
6 Halted 0 ms 0 KB -