oj.uz

Submission #858843

# Submission time Handle Problem Language Result Execution time Memory
858843 2023-10-09T09:05:35 Z LucaIlie Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 495388 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 2;
const long long INF = 1e18;
unordered_map<int, long long> costCell[MAX_N], dp[MAX_N], dpLower[MAX_N], spX[MAX_N], maxPref1[MAX_N], maxSuf2[MAX_N], maxPref3[MAX_N];
vector <int> ys[MAX_N];

long long max_weights( int n, int m, vector <int> X, vector <int> Y, vector <int> W ) {

    for ( int i = 0; i < m; i++ ) {
        X[i]++;
        Y[i]++;
        costCell[X[i]][Y[i]] = W[i];
        ys[X[i] - 1].push_back( Y[i] );
        ys[X[i] + 1].push_back( Y[i] );
    }

    ys[0].clear();
    ys[n + 1].clear();
    for ( int x = 0; x <= n + 1; x++ )
        ys[x].push_back( 0 );
    for ( int x = 1; x <= n; x++ ) {
        sort( ys[x].begin(), ys[x].end() );
        ys[x].resize( unique( ys[x].begin(), ys[x].end() ) - ys[x].begin() );
    }

    for ( int x = 1; x <= n; x++ ) {
        vector<int> yss;
        for ( int i = 0; i < ys[x].size(); i++ )
            yss.push_back( ys[x][i] );
        for ( int i = 0; i < ys[x - 1].size(); i++ )
            yss.push_back( ys[x - 1][i] );
        for ( int i = 0; i < ys[x + 1].size(); i++ )
            yss.push_back( ys[x + 1][i] );
        sort( yss.begin(), yss.end() );
        yss.resize( unique( yss.begin(), yss.end() ) - yss.begin() );
        for ( int i = 1; i < yss.size(); i++ )
            spX[x][yss[i]] = spX[x][yss[i - 1]] + costCell[x][yss[i]];
    }

    dp[0][0] = dpLower[0][0] = 0;
    for ( int x = 1; x <= n + 1; x++ ) {
        int lower1 = 0, upper1 = 0, lower2 = 0, upper2 = 0;
        for ( int i = 0; i < ys[x].size(); i++ ) {
            int crtY = ys[x][i];
            dp[x][i] = dpLower[x][i] = -INF;

            if ( x >= 1 ) {
                while ( lower1 + 1 < ys[x - 1].size() && ys[x - 1][lower1 + 1] <= crtY )
                    lower1++;
                while ( upper1 < ys[x - 1].size() && ys[x - 1][upper1] < crtY )
                    upper1++;

                if ( lower1 >= 0 ) {
                    int prevY = ys[x - 1][lower1];
                    dpLower[x][i] = max( dpLower[x][i], maxPref1[x - 1][lower1] + spX[x - 1][crtY] );
                    dp[x][i] = max( dp[x][i], maxPref1[x - 1][lower1] + spX[x - 1][crtY] );
                }
                if ( upper1 < ys[x - 1].size() ) {
                    int prevY = ys[x - 1][upper1];
                    dp[x][i] = max( dp[x][i], maxSuf2[x - 1][upper1] - spX[x][crtY] );
                }
            }

            if ( x >= 2 ) {
                while ( lower2 + 1 < ys[x - 2].size() && ys[x - 2][lower2 + 1] <= crtY )
                    lower2++;
                while ( upper2 < ys[x - 2].size() && ys[x - 2][upper2] < crtY )
                    upper2++;

                if ( lower2 >= 0 ) {
                    int prevY = ys[x - 2][lower2];
                    dpLower[x][i] = max( dpLower[x][i], maxPref3[x - 2][lower2] + spX[x - 1][crtY] );
                    dp[x][i] = max( dp[x][i], maxPref3[x - 2][lower2] + spX[x - 1][crtY] );
                }
                if ( upper2 < ys[x - 2].size() ) {
                    int prevY = ys[x - 2][upper2];
                    dpLower[x][i] = max( dpLower[x][i], maxSuf2[x - 2][upper2] );
                    dp[x][i] = max( dp[x][i], maxSuf2[x - 2][upper2] );
                }
            }

            maxPref1[x][i] = dpLower[x][i] - spX[x][crtY];
            maxSuf2[x][i] = dp[x][i] + spX[x + 1][crtY];
            maxPref3[x][i] = dpLower[x][i];
        }

        for ( int i = 1; i < ys[x].size(); i++ ) {
            maxPref1[x][i] = max( maxPref1[x][i], maxPref1[x][i - 1] );
            maxPref3[x][i] = max( maxPref3[x][i], maxPref3[x][i - 1] );
        }
        for ( int i = ys[x].size() - 2; i >= 0; i-- )
            maxSuf2[x][i] = max( maxSuf2[x][i], maxSuf2[x][i + 1] );
    }

    return dp[n + 1][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:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for ( int i = 0; i < ys[x].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~
fish.cpp:34:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for ( int i = 0; i < ys[x - 1].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~~~~~
fish.cpp:36:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for ( int i = 0; i < ys[x + 1].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~~~~~
fish.cpp:40:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for ( int i = 1; i < yss.size(); i++ )
      |                          ~~^~~~~~~~~~~~
fish.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for ( int i = 0; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~
fish.cpp:52:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 while ( lower1 + 1 < ys[x - 1].size() && ys[x - 1][lower1 + 1] <= crtY )
      |                         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:54:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 while ( upper1 < ys[x - 1].size() && ys[x - 1][upper1] < crtY )
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:58:25: warning: unused variable 'prevY' [-Wunused-variable]
   58 |                     int prevY = ys[x - 1][lower1];
      |                         ^~~~~
fish.cpp:62:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 if ( upper1 < ys[x - 1].size() ) {
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:63:25: warning: unused variable 'prevY' [-Wunused-variable]
   63 |                     int prevY = ys[x - 1][upper1];
      |                         ^~~~~
fish.cpp:69:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 while ( lower2 + 1 < ys[x - 2].size() && ys[x - 2][lower2 + 1] <= crtY )
      |                         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:71:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 while ( upper2 < ys[x - 2].size() && ys[x - 2][upper2] < crtY )
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:75:25: warning: unused variable 'prevY' [-Wunused-variable]
   75 |                     int prevY = ys[x - 2][lower2];
      |                         ^~~~~
fish.cpp:79:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if ( upper2 < ys[x - 2].size() ) {
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:80:25: warning: unused variable 'prevY' [-Wunused-variable]
   80 |                     int prevY = ys[x - 2][upper2];
      |                         ^~~~~
fish.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for ( int i = 1; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 239088 KB Output is correct
2 Correct 322 ms 262576 KB Output is correct
3 Correct 170 ms 210004 KB Output is correct
4 Correct 159 ms 210188 KB Output is correct
5 Execution timed out 1061 ms 495388 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 122312 KB Output is correct
2 Correct 474 ms 288788 KB Output is correct
3 Correct 571 ms 324140 KB Output is correct
4 Correct 265 ms 238896 KB Output is correct
5 Correct 311 ms 262688 KB Output is correct
6 Correct 27 ms 122460 KB Output is correct
7 Correct 30 ms 122460 KB Output is correct
8 Correct 28 ms 122460 KB Output is correct
9 Correct 28 ms 122460 KB Output is correct
10 Correct 166 ms 210000 KB Output is correct
11 Correct 161 ms 210004 KB Output is correct
12 Correct 365 ms 264752 KB Output is correct
13 Correct 423 ms 298408 KB Output is correct
14 Correct 327 ms 251812 KB Output is correct
15 Correct 370 ms 263804 KB Output is correct
16 Correct 326 ms 251868 KB Output is correct
17 Correct 434 ms 275360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 210128 KB Output is correct
2 Correct 166 ms 210108 KB Output is correct
3 Correct 265 ms 222032 KB Output is correct
4 Correct 242 ms 226004 KB Output is correct
5 Correct 368 ms 245420 KB Output is correct
6 Correct 383 ms 245396 KB Output is correct
7 Correct 365 ms 245332 KB Output is correct
8 Correct 375 ms 245404 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122456 KB Output is correct
3 Correct 27 ms 122524 KB Output is correct
4 Correct 28 ms 122660 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122524 KB Output is correct
7 Correct 27 ms 122540 KB Output is correct
8 Correct 28 ms 122460 KB Output is correct
9 Correct 28 ms 122844 KB Output is correct
10 Correct 30 ms 123228 KB Output is correct
11 Correct 30 ms 122716 KB Output is correct
12 Correct 34 ms 123312 KB Output is correct
13 Correct 28 ms 122596 KB Output is correct
14 Correct 29 ms 122972 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122456 KB Output is correct
3 Correct 27 ms 122524 KB Output is correct
4 Correct 28 ms 122660 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122524 KB Output is correct
7 Correct 27 ms 122540 KB Output is correct
8 Correct 28 ms 122460 KB Output is correct
9 Correct 28 ms 122844 KB Output is correct
10 Correct 30 ms 123228 KB Output is correct
11 Correct 30 ms 122716 KB Output is correct
12 Correct 34 ms 123312 KB Output is correct
13 Correct 28 ms 122596 KB Output is correct
14 Correct 29 ms 122972 KB Output is correct
15 Correct 30 ms 122972 KB Output is correct
16 Correct 33 ms 123484 KB Output is correct
17 Correct 93 ms 143180 KB Output is correct
18 Correct 89 ms 140624 KB Output is correct
19 Correct 95 ms 142048 KB Output is correct
20 Correct 85 ms 138808 KB Output is correct
21 Correct 84 ms 138440 KB Output is correct
22 Correct 142 ms 154592 KB Output is correct
23 Correct 52 ms 129736 KB Output is correct
24 Correct 92 ms 141768 KB Output is correct
25 Correct 31 ms 123224 KB Output is correct
26 Correct 47 ms 128340 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122456 KB Output is correct
3 Correct 27 ms 122524 KB Output is correct
4 Correct 28 ms 122660 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122524 KB Output is correct
7 Correct 27 ms 122540 KB Output is correct
8 Correct 28 ms 122460 KB Output is correct
9 Correct 28 ms 122844 KB Output is correct
10 Correct 30 ms 123228 KB Output is correct
11 Correct 30 ms 122716 KB Output is correct
12 Correct 34 ms 123312 KB Output is correct
13 Correct 28 ms 122596 KB Output is correct
14 Correct 29 ms 122972 KB Output is correct
15 Correct 30 ms 122972 KB Output is correct
16 Correct 33 ms 123484 KB Output is correct
17 Correct 93 ms 143180 KB Output is correct
18 Correct 89 ms 140624 KB Output is correct
19 Correct 95 ms 142048 KB Output is correct
20 Correct 85 ms 138808 KB Output is correct
21 Correct 84 ms 138440 KB Output is correct
22 Correct 142 ms 154592 KB Output is correct
23 Correct 52 ms 129736 KB Output is correct
24 Correct 92 ms 141768 KB Output is correct
25 Correct 31 ms 123224 KB Output is correct
26 Correct 47 ms 128340 KB Output is correct
27 Correct 39 ms 127324 KB Output is correct
28 Correct 364 ms 211460 KB Output is correct
29 Correct 603 ms 299344 KB Output is correct
30 Correct 851 ms 365136 KB Output is correct
31 Correct 860 ms 362100 KB Output is correct
32 Correct 435 ms 233320 KB Output is correct
33 Correct 885 ms 369400 KB Output is correct
34 Correct 923 ms 369744 KB Output is correct
35 Correct 286 ms 197968 KB Output is correct
36 Correct 834 ms 327508 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 210128 KB Output is correct
2 Correct 166 ms 210108 KB Output is correct
3 Correct 265 ms 222032 KB Output is correct
4 Correct 242 ms 226004 KB Output is correct
5 Correct 368 ms 245420 KB Output is correct
6 Correct 383 ms 245396 KB Output is correct
7 Correct 365 ms 245332 KB Output is correct
8 Correct 375 ms 245404 KB Output is correct
9 Correct 479 ms 286028 KB Output is correct
10 Correct 253 ms 196944 KB Output is correct
11 Correct 525 ms 271444 KB Output is correct
12 Correct 27 ms 122324 KB Output is correct
13 Correct 29 ms 122460 KB Output is correct
14 Correct 27 ms 122456 KB Output is correct
15 Correct 27 ms 122460 KB Output is correct
16 Correct 27 ms 122560 KB Output is correct
17 Correct 28 ms 122456 KB Output is correct
18 Correct 163 ms 210148 KB Output is correct
19 Correct 162 ms 210112 KB Output is correct
20 Correct 165 ms 210000 KB Output is correct
21 Correct 164 ms 210132 KB Output is correct
22 Correct 500 ms 286248 KB Output is correct
23 Correct 650 ms 313172 KB Output is correct
24 Correct 668 ms 323920 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 239088 KB Output is correct
2 Correct 322 ms 262576 KB Output is correct
3 Correct 170 ms 210004 KB Output is correct
4 Correct 159 ms 210188 KB Output is correct
5 Execution timed out 1061 ms 495388 KB Time limit exceeded
6 Halted 0 ms 0 KB -