oj.uz

Submission #732707

# Submission time Handle Problem Language Result Execution time Memory
732707 2023-04-29T07:44:15 Z math_rabbit_1028 Catfish Farm (IOI22_fish) C++17
12 / 100
 559 ms 83928 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++;
            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 = ylist[i].size() - 1, k = ylist[i - 1].size() - 1, l = ylist[i - 2].size() - 1;
        for (int t = all.size() - 2; t >= 1; t--) {
            while (ylist[i][j - 1] >= make_pair(all[t], 0LL)) j--;
            while (ylist[i - 1][k - 1] >= make_pair(all[t], 0LL)) k--;
            while (ylist[i - 2][l - 1] >= make_pair(all[t], 0LL)) l--;
            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 145 ms 36056 KB Output is correct
2 Correct 172 ms 41356 KB Output is correct
3 Correct 56 ms 25360 KB Output is correct
4 Correct 56 ms 25368 KB Output is correct
5 Correct 495 ms 71428 KB Output is correct
6 Correct 559 ms 83928 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 225 ms 45280 KB Output is correct
3 Correct 255 ms 50756 KB Output is correct
4 Correct 142 ms 36232 KB Output is correct
5 Correct 167 ms 41344 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 54 ms 25388 KB Output is correct
11 Correct 53 ms 25472 KB Output is correct
12 Correct 162 ms 36100 KB Output is correct
13 Correct 191 ms 41344 KB Output is correct
14 Correct 152 ms 36748 KB Output is correct
15 Correct 147 ms 37200 KB Output is correct
16 Correct 151 ms 36632 KB Output is correct
17 Incorrect 174 ms 38872 KB 1st lines differ - on the 1st token, expected: '45076987066882', found: '45080104577450'
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25420 KB Output is correct
2 Correct 58 ms 25368 KB Output is correct
3 Correct 118 ms 32576 KB Output is correct
4 Correct 95 ms 31804 KB Output is correct
5 Correct 165 ms 42320 KB Output is correct
6 Correct 169 ms 42244 KB Output is correct
7 Correct 161 ms 42272 KB Output is correct
8 Correct 167 ms 42216 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9748 KB Output is correct
3 Correct 5 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 6 ms 9684 KB Output is correct
7 Correct 5 ms 9792 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 6 ms 9936 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9940 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '361169275593'
15 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9748 KB Output is correct
3 Correct 5 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 6 ms 9684 KB Output is correct
7 Correct 5 ms 9792 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 6 ms 9936 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9940 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '361169275593'
15 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9748 KB Output is correct
3 Correct 5 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 6 ms 9684 KB Output is correct
7 Correct 5 ms 9792 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 7 ms 10068 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 6 ms 9936 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Incorrect 6 ms 9940 KB 1st lines differ - on the 1st token, expected: '360901324355', found: '361169275593'
15 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25420 KB Output is correct
2 Correct 58 ms 25368 KB Output is correct
3 Correct 118 ms 32576 KB Output is correct
4 Correct 95 ms 31804 KB Output is correct
5 Correct 165 ms 42320 KB Output is correct
6 Correct 169 ms 42244 KB Output is correct
7 Correct 161 ms 42272 KB Output is correct
8 Correct 167 ms 42216 KB Output is correct
9 Correct 191 ms 51824 KB Output is correct
10 Correct 112 ms 27264 KB Output is correct
11 Correct 251 ms 44744 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 9796 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 56 ms 25400 KB Output is correct
19 Correct 54 ms 25360 KB Output is correct
20 Correct 54 ms 25432 KB Output is correct
21 Correct 56 ms 25316 KB Output is correct
22 Correct 250 ms 45264 KB Output is correct
23 Incorrect 301 ms 53624 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '77782967623534'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 36056 KB Output is correct
2 Correct 172 ms 41356 KB Output is correct
3 Correct 56 ms 25360 KB Output is correct
4 Correct 56 ms 25368 KB Output is correct
5 Correct 495 ms 71428 KB Output is correct
6 Correct 559 ms 83928 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 225 ms 45280 KB Output is correct
9 Correct 255 ms 50756 KB Output is correct
10 Correct 142 ms 36232 KB Output is correct
11 Correct 167 ms 41344 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 5 ms 9684 KB Output is correct
16 Correct 54 ms 25388 KB Output is correct
17 Correct 53 ms 25472 KB Output is correct
18 Correct 162 ms 36100 KB Output is correct
19 Correct 191 ms 41344 KB Output is correct
20 Correct 152 ms 36748 KB Output is correct
21 Correct 147 ms 37200 KB Output is correct
22 Correct 151 ms 36632 KB Output is correct
23 Incorrect 174 ms 38872 KB 1st lines differ - on the 1st token, expected: '45076987066882', found: '45080104577450'
24 Halted 0 ms 0 KB -