oj.uz

Submission #858833

# Submission time Handle Problem Language Result Execution time Memory
858833 2023-10-09T08:52:58 Z LucaIlie Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 495200 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][crtY] = dpLower[x][crtY] = -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][crtY] = max( dpLower[x][crtY], maxPref1[x - 1][prevY] + spX[x - 1][crtY] );
                    dp[x][crtY] = max( dp[x][crtY], maxPref1[x - 1][prevY] + spX[x - 1][crtY] );
                }
                if ( upper1 < ys[x - 1].size()) {
                    int prevY = ys[x - 1][upper1];
                    dp[x][crtY] = max( dp[x][crtY], maxSuf2[x - 1][prevY] - spX[x][crtY] );
                }
            }

            if ( x >= 2 ) {
                auto lower = upper_bound( ys[x - 2].begin(), ys[x - 2].end(), crtY );
                auto upper = lower_bound( ys[x - 2].begin(), ys[x - 2].end(), crtY );
                if ( lower != ys[x - 2].begin() ) {
                    lower--;
                    int prevY = *lower;
                    dpLower[x][crtY] = max( dpLower[x][crtY], maxPref3[x - 2][prevY] + spX[x - 1][crtY] );
                    dp[x][crtY] = max( dp[x][crtY], maxPref3[x - 2][prevY] + spX[x - 1][crtY] );
                }
                if ( upper != ys[x - 2].end() ) {
                    int prevY = *upper;
                    dpLower[x][crtY] = max( dpLower[x][crtY], maxSuf2[x - 2][prevY] );
                    dp[x][crtY] = max( dp[x][crtY], maxSuf2[x - 2][prevY] );
                }
            }

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

        for ( int i = 1; i < ys[x].size(); i++ ) {
            maxPref1[x][ys[x][i]] = max( maxPref1[x][ys[x][i]], maxPref1[x][ys[x][i - 1]] );
            maxPref3[x][ys[x][i]] = max( maxPref3[x][ys[x][i]], maxPref3[x][ys[x][i - 1]] );
        }
        for ( int i = ys[x].size() - 2; i >= 0; i-- )
            maxSuf2[x][ys[x][i]] = max( maxSuf2[x][ys[x][i]], maxSuf2[x][ys[x][i + 1]] );
    }
    /*for ( int x = 0; x <= n + 1; x++ ) {
        for ( int i = 0; i < ys[x].size(); i++ )
            printf( "(%d %lld) ", ys[x][i], dp[x][i] );
        printf( "\n" );
    }*/

    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: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:89:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for ( int i = 1; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~
fish.cpp:46:37: warning: unused variable 'lower2' [-Wunused-variable]
   46 |         int lower1 = 0, upper1 = 0, lower2 = 0, upper2 = 0;
      |                                     ^~~~~~
fish.cpp:46:49: warning: unused variable 'upper2' [-Wunused-variable]
   46 |         int lower1 = 0, upper1 = 0, lower2 = 0, upper2 = 0;
      |                                                 ^~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 239132 KB Output is correct
2 Correct 354 ms 262580 KB Output is correct
3 Correct 171 ms 210200 KB Output is correct
4 Correct 166 ms 210032 KB Output is correct
5 Execution timed out 1077 ms 495200 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 122484 KB Output is correct
2 Correct 504 ms 289032 KB Output is correct
3 Correct 586 ms 324088 KB Output is correct
4 Correct 294 ms 239144 KB Output is correct
5 Correct 335 ms 262660 KB Output is correct
6 Correct 28 ms 122460 KB Output is correct
7 Correct 28 ms 122456 KB Output is correct
8 Correct 28 ms 122456 KB Output is correct
9 Correct 28 ms 122460 KB Output is correct
10 Correct 167 ms 210200 KB Output is correct
11 Correct 187 ms 210000 KB Output is correct
12 Correct 396 ms 264720 KB Output is correct
13 Correct 449 ms 298648 KB Output is correct
14 Correct 354 ms 252068 KB Output is correct
15 Correct 387 ms 263748 KB Output is correct
16 Correct 351 ms 251864 KB Output is correct
17 Correct 418 ms 275336 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 210204 KB Output is correct
2 Correct 168 ms 210000 KB Output is correct
3 Correct 270 ms 221896 KB Output is correct
4 Correct 264 ms 225876 KB Output is correct
5 Correct 405 ms 245268 KB Output is correct
6 Correct 412 ms 245200 KB Output is correct
7 Correct 419 ms 245232 KB Output is correct
8 Correct 396 ms 245204 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122544 KB Output is correct
2 Correct 29 ms 122460 KB Output is correct
3 Correct 29 ms 122432 KB Output is correct
4 Correct 27 ms 122460 KB Output is correct
5 Correct 29 ms 122460 KB Output is correct
6 Correct 29 ms 122560 KB Output is correct
7 Correct 31 ms 122460 KB Output is correct
8 Correct 29 ms 122448 KB Output is correct
9 Correct 28 ms 122832 KB Output is correct
10 Correct 33 ms 123228 KB Output is correct
11 Correct 31 ms 122808 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 29 ms 122524 KB Output is correct
14 Correct 30 ms 123136 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122544 KB Output is correct
2 Correct 29 ms 122460 KB Output is correct
3 Correct 29 ms 122432 KB Output is correct
4 Correct 27 ms 122460 KB Output is correct
5 Correct 29 ms 122460 KB Output is correct
6 Correct 29 ms 122560 KB Output is correct
7 Correct 31 ms 122460 KB Output is correct
8 Correct 29 ms 122448 KB Output is correct
9 Correct 28 ms 122832 KB Output is correct
10 Correct 33 ms 123228 KB Output is correct
11 Correct 31 ms 122808 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 29 ms 122524 KB Output is correct
14 Correct 30 ms 123136 KB Output is correct
15 Correct 31 ms 122976 KB Output is correct
16 Correct 33 ms 123500 KB Output is correct
17 Correct 104 ms 143320 KB Output is correct
18 Correct 98 ms 140628 KB Output is correct
19 Correct 101 ms 142016 KB Output is correct
20 Correct 95 ms 138600 KB Output is correct
21 Correct 92 ms 138372 KB Output is correct
22 Correct 179 ms 154584 KB Output is correct
23 Correct 59 ms 129620 KB Output is correct
24 Correct 112 ms 141528 KB Output is correct
25 Correct 32 ms 123440 KB Output is correct
26 Correct 53 ms 128264 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122544 KB Output is correct
2 Correct 29 ms 122460 KB Output is correct
3 Correct 29 ms 122432 KB Output is correct
4 Correct 27 ms 122460 KB Output is correct
5 Correct 29 ms 122460 KB Output is correct
6 Correct 29 ms 122560 KB Output is correct
7 Correct 31 ms 122460 KB Output is correct
8 Correct 29 ms 122448 KB Output is correct
9 Correct 28 ms 122832 KB Output is correct
10 Correct 33 ms 123228 KB Output is correct
11 Correct 31 ms 122808 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 29 ms 122524 KB Output is correct
14 Correct 30 ms 123136 KB Output is correct
15 Correct 31 ms 122976 KB Output is correct
16 Correct 33 ms 123500 KB Output is correct
17 Correct 104 ms 143320 KB Output is correct
18 Correct 98 ms 140628 KB Output is correct
19 Correct 101 ms 142016 KB Output is correct
20 Correct 95 ms 138600 KB Output is correct
21 Correct 92 ms 138372 KB Output is correct
22 Correct 179 ms 154584 KB Output is correct
23 Correct 59 ms 129620 KB Output is correct
24 Correct 112 ms 141528 KB Output is correct
25 Correct 32 ms 123440 KB Output is correct
26 Correct 53 ms 128264 KB Output is correct
27 Correct 42 ms 127336 KB Output is correct
28 Correct 405 ms 211356 KB Output is correct
29 Correct 716 ms 299372 KB Output is correct
30 Execution timed out 1104 ms 365040 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 210204 KB Output is correct
2 Correct 168 ms 210000 KB Output is correct
3 Correct 270 ms 221896 KB Output is correct
4 Correct 264 ms 225876 KB Output is correct
5 Correct 405 ms 245268 KB Output is correct
6 Correct 412 ms 245200 KB Output is correct
7 Correct 419 ms 245232 KB Output is correct
8 Correct 396 ms 245204 KB Output is correct
9 Correct 546 ms 285948 KB Output is correct
10 Correct 288 ms 196804 KB Output is correct
11 Correct 580 ms 271328 KB Output is correct
12 Correct 28 ms 122456 KB Output is correct
13 Correct 30 ms 122708 KB Output is correct
14 Correct 28 ms 122460 KB Output is correct
15 Correct 29 ms 122460 KB Output is correct
16 Correct 27 ms 122460 KB Output is correct
17 Correct 27 ms 122460 KB Output is correct
18 Correct 170 ms 210000 KB Output is correct
19 Correct 182 ms 210264 KB Output is correct
20 Correct 173 ms 209988 KB Output is correct
21 Correct 179 ms 210096 KB Output is correct
22 Correct 536 ms 286016 KB Output is correct
23 Correct 684 ms 313132 KB Output is correct
24 Correct 720 ms 323920 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 239132 KB Output is correct
2 Correct 354 ms 262580 KB Output is correct
3 Correct 171 ms 210200 KB Output is correct
4 Correct 166 ms 210032 KB Output is correct
5 Execution timed out 1077 ms 495200 KB Time limit exceeded
6 Halted 0 ms 0 KB -