oj.uz

Submission #858809

# Submission time Handle Problem Language Result Execution time Memory
858809 2023-10-09T08:17:48 Z LucaIlie Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 1091804 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];
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++ ) {
        for ( int y = 1; y <= n; y++ )
            spX[x][y] = spX[x][y - 1] + costCell[x][y];
    }

    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;
            /*for ( int prevY: ys[x - 1] ) {
                if ( prevY <= crtY ) {
                    dpLower[x][crtY] = max( dpLower[x][crtY], dpLower[x - 1][prevY] + spX[x - 1][crtY] - spX[x - 1][prevY] );
                    dp[x][crtY] = max( dp[x][crtY], dpLower[x - 1][prevY] + spX[x - 1][crtY] - spX[x - 1][prevY] );
                }
                if ( prevY >= crtY )
                    dp[x][crtY] = max( dp[x][crtY], dp[x - 1][prevY] + spX[x][prevY] - spX[x][crtY] );
            }*/
            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 ) {
                for ( int prevY: ys[x - 2] ) {
                    if ( prevY <= crtY ) {
                        dpLower[x][crtY] = max( dpLower[x][crtY], dp[x - 2][prevY] + spX[x - 1][crtY] );
                        dp[x][crtY] = max( dp[x][crtY], dp[x - 2][prevY] + spX[x - 1][crtY] );
                    }
                    if ( prevY >= crtY ) {
                        dpLower[x][crtY] = max( dpLower[x][crtY], dp[x - 2][prevY] + spX[x - 1][prevY] );
                        dp[x][crtY] = max( dp[x][crtY], dp[x - 2][prevY] + spX[x - 1][prevY] );
                    }
                }
            }

            maxPref1[x][crtY] = dpLower[x][crtY] - spX[x][crtY];
            maxSuf2[x][crtY] = dp[x][crtY] + spX[x + 1][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]] );
        }
        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]] );
        }
    }

    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:38:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for ( int i = 0; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~
fish.cpp:81:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for ( int i = 1; i < ys[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 990268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 106072 KB Output is correct
2 Execution timed out 1104 ms 971108 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1142 ms 1091804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 106076 KB Output is correct
2 Correct 24 ms 106076 KB Output is correct
3 Correct 27 ms 106076 KB Output is correct
4 Correct 24 ms 106072 KB Output is correct
5 Correct 27 ms 106480 KB Output is correct
6 Correct 25 ms 106072 KB Output is correct
7 Correct 24 ms 106076 KB Output is correct
8 Correct 25 ms 106076 KB Output is correct
9 Correct 29 ms 108124 KB Output is correct
10 Correct 41 ms 114776 KB Output is correct
11 Correct 32 ms 108380 KB Output is correct
12 Correct 39 ms 114772 KB Output is correct
13 Correct 25 ms 106588 KB Output is correct
14 Correct 39 ms 114524 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 106076 KB Output is correct
2 Correct 24 ms 106076 KB Output is correct
3 Correct 27 ms 106076 KB Output is correct
4 Correct 24 ms 106072 KB Output is correct
5 Correct 27 ms 106480 KB Output is correct
6 Correct 25 ms 106072 KB Output is correct
7 Correct 24 ms 106076 KB Output is correct
8 Correct 25 ms 106076 KB Output is correct
9 Correct 29 ms 108124 KB Output is correct
10 Correct 41 ms 114776 KB Output is correct
11 Correct 32 ms 108380 KB Output is correct
12 Correct 39 ms 114772 KB Output is correct
13 Correct 25 ms 106588 KB Output is correct
14 Correct 39 ms 114524 KB Output is correct
15 Correct 40 ms 114408 KB Output is correct
16 Correct 39 ms 107100 KB Output is correct
17 Correct 709 ms 127316 KB Output is correct
18 Correct 629 ms 125888 KB Output is correct
19 Correct 419 ms 126064 KB Output is correct
20 Correct 352 ms 124788 KB Output is correct
21 Correct 318 ms 124424 KB Output is correct
22 Execution timed out 1058 ms 134564 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 106076 KB Output is correct
2 Correct 24 ms 106076 KB Output is correct
3 Correct 27 ms 106076 KB Output is correct
4 Correct 24 ms 106072 KB Output is correct
5 Correct 27 ms 106480 KB Output is correct
6 Correct 25 ms 106072 KB Output is correct
7 Correct 24 ms 106076 KB Output is correct
8 Correct 25 ms 106076 KB Output is correct
9 Correct 29 ms 108124 KB Output is correct
10 Correct 41 ms 114776 KB Output is correct
11 Correct 32 ms 108380 KB Output is correct
12 Correct 39 ms 114772 KB Output is correct
13 Correct 25 ms 106588 KB Output is correct
14 Correct 39 ms 114524 KB Output is correct
15 Correct 40 ms 114408 KB Output is correct
16 Correct 39 ms 107100 KB Output is correct
17 Correct 709 ms 127316 KB Output is correct
18 Correct 629 ms 125888 KB Output is correct
19 Correct 419 ms 126064 KB Output is correct
20 Correct 352 ms 124788 KB Output is correct
21 Correct 318 ms 124424 KB Output is correct
22 Execution timed out 1058 ms 134564 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1142 ms 1091804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 990268 KB Time limit exceeded
2 Halted 0 ms 0 KB -