oj.uz

Submission #858819

# Submission time Handle Problem Language Result Execution time Memory
858819 2023-10-09T08:32:57 Z LucaIlie Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 530204 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[X[i]].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++ ) {
        for ( int i = 0; i < ys[x].size(); i++ ) {
            int crtY = ys[x][i];
            dp[x][crtY] = dpLower[x][crtY] = -INF;

            if ( x >= 1 ) {
                auto lower = upper_bound( ys[x - 1].begin(), ys[x - 1].end(), crtY );
                auto upper = lower_bound( ys[x - 1].begin(), ys[x - 1].end(), crtY );
                if ( lower != ys[x - 1].begin() ) {
                    lower--;
                    int prevY = *lower;
                    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 ( upper != ys[x - 1].end() ) {
                    int prevY = *upper;
                    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:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for ( int i = 0; i < ys[x].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~
fish.cpp:35:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for ( int i = 0; i < ys[x - 1].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~~~~~
fish.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for ( int i = 0; i < ys[x + 1].size(); i++ )
      |                          ~~^~~~~~~~~~~~~~~~~~
fish.cpp:41:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         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:87:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for ( int i = 1; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 258512 KB Output is correct
2 Correct 515 ms 289952 KB Output is correct
3 Correct 243 ms 210188 KB Output is correct
4 Correct 246 ms 210320 KB Output is correct
5 Execution timed out 1091 ms 530204 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 122536 KB Output is correct
2 Correct 626 ms 300100 KB Output is correct
3 Correct 698 ms 324912 KB Output is correct
4 Correct 473 ms 258392 KB Output is correct
5 Correct 514 ms 289984 KB Output is correct
6 Correct 27 ms 122456 KB Output is correct
7 Correct 28 ms 122712 KB Output is correct
8 Correct 27 ms 122460 KB Output is correct
9 Correct 28 ms 122456 KB Output is correct
10 Correct 241 ms 209976 KB Output is correct
11 Correct 244 ms 210004 KB Output is correct
12 Correct 553 ms 281312 KB Output is correct
13 Correct 641 ms 321296 KB Output is correct
14 Correct 503 ms 269856 KB Output is correct
15 Correct 483 ms 265480 KB Output is correct
16 Correct 510 ms 270024 KB Output is correct
17 Correct 598 ms 298816 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 210004 KB Output is correct
2 Correct 242 ms 210200 KB Output is correct
3 Correct 351 ms 222164 KB Output is correct
4 Correct 338 ms 226460 KB Output is correct
5 Correct 470 ms 245380 KB Output is correct
6 Correct 464 ms 245328 KB Output is correct
7 Correct 476 ms 245396 KB Output is correct
8 Correct 470 ms 245408 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 122512 KB Output is correct
2 Correct 28 ms 122324 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 28 ms 122460 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122312 KB Output is correct
7 Correct 29 ms 122448 KB Output is correct
8 Correct 27 ms 122536 KB Output is correct
9 Correct 30 ms 122712 KB Output is correct
10 Correct 31 ms 123228 KB Output is correct
11 Correct 29 ms 122972 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 28 ms 122512 KB Output is correct
14 Correct 30 ms 122968 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 122512 KB Output is correct
2 Correct 28 ms 122324 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 28 ms 122460 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122312 KB Output is correct
7 Correct 29 ms 122448 KB Output is correct
8 Correct 27 ms 122536 KB Output is correct
9 Correct 30 ms 122712 KB Output is correct
10 Correct 31 ms 123228 KB Output is correct
11 Correct 29 ms 122972 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 28 ms 122512 KB Output is correct
14 Correct 30 ms 122968 KB Output is correct
15 Correct 29 ms 122968 KB Output is correct
16 Correct 31 ms 123484 KB Output is correct
17 Correct 119 ms 144372 KB Output is correct
18 Correct 103 ms 140768 KB Output is correct
19 Correct 106 ms 141908 KB Output is correct
20 Correct 92 ms 138756 KB Output is correct
21 Correct 92 ms 138308 KB Output is correct
22 Correct 188 ms 154588 KB Output is correct
23 Correct 67 ms 131408 KB Output is correct
24 Correct 111 ms 143952 KB Output is correct
25 Correct 32 ms 123480 KB Output is correct
26 Correct 56 ms 130008 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 122512 KB Output is correct
2 Correct 28 ms 122324 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 28 ms 122460 KB Output is correct
5 Correct 28 ms 122456 KB Output is correct
6 Correct 28 ms 122312 KB Output is correct
7 Correct 29 ms 122448 KB Output is correct
8 Correct 27 ms 122536 KB Output is correct
9 Correct 30 ms 122712 KB Output is correct
10 Correct 31 ms 123228 KB Output is correct
11 Correct 29 ms 122972 KB Output is correct
12 Correct 31 ms 123228 KB Output is correct
13 Correct 28 ms 122512 KB Output is correct
14 Correct 30 ms 122968 KB Output is correct
15 Correct 29 ms 122968 KB Output is correct
16 Correct 31 ms 123484 KB Output is correct
17 Correct 119 ms 144372 KB Output is correct
18 Correct 103 ms 140768 KB Output is correct
19 Correct 106 ms 141908 KB Output is correct
20 Correct 92 ms 138756 KB Output is correct
21 Correct 92 ms 138308 KB Output is correct
22 Correct 188 ms 154588 KB Output is correct
23 Correct 67 ms 131408 KB Output is correct
24 Correct 111 ms 143952 KB Output is correct
25 Correct 32 ms 123480 KB Output is correct
26 Correct 56 ms 130008 KB Output is correct
27 Correct 45 ms 127836 KB Output is correct
28 Correct 439 ms 215036 KB Output is correct
29 Correct 755 ms 308364 KB Output is correct
30 Execution timed out 1085 ms 448368 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 210004 KB Output is correct
2 Correct 242 ms 210200 KB Output is correct
3 Correct 351 ms 222164 KB Output is correct
4 Correct 338 ms 226460 KB Output is correct
5 Correct 470 ms 245380 KB Output is correct
6 Correct 464 ms 245328 KB Output is correct
7 Correct 476 ms 245396 KB Output is correct
8 Correct 470 ms 245408 KB Output is correct
9 Correct 689 ms 301708 KB Output is correct
10 Correct 302 ms 196688 KB Output is correct
11 Correct 664 ms 271232 KB Output is correct
12 Correct 27 ms 122460 KB Output is correct
13 Correct 29 ms 122460 KB Output is correct
14 Correct 28 ms 122460 KB Output is correct
15 Correct 29 ms 122712 KB Output is correct
16 Correct 28 ms 122460 KB Output is correct
17 Correct 27 ms 122460 KB Output is correct
18 Correct 240 ms 210004 KB Output is correct
19 Correct 251 ms 210256 KB Output is correct
20 Correct 240 ms 210000 KB Output is correct
21 Correct 240 ms 210052 KB Output is correct
22 Correct 710 ms 302224 KB Output is correct
23 Correct 787 ms 322232 KB Output is correct
24 Correct 816 ms 331408 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 258512 KB Output is correct
2 Correct 515 ms 289952 KB Output is correct
3 Correct 243 ms 210188 KB Output is correct
4 Correct 246 ms 210320 KB Output is correct
5 Execution timed out 1091 ms 530204 KB Time limit exceeded
6 Halted 0 ms 0 KB -