oj.uz

Submission #858822

# Submission time Handle Problem Language Result Execution time Memory
858822 2023-10-09T08:36:55 Z LucaIlie Catfish Farm (IOI22_fish) C++17
52 / 100
 490 ms 790480 KB 
#include "fish.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 3002;
const long long INF = 1e18;
long long costCell[MAX_N][MAX_N], dp[MAX_N][MAX_N], dpLower[MAX_N][MAX_N], spX[MAX_N][MAX_N], maxPref1[MAX_N][MAX_N], maxSuf2[MAX_N][MAX_N], maxPref3[MAX_N][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 Runtime error 454 ms 790480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6504 KB Output is correct
2 Runtime error 490 ms 790372 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 368 ms 770944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8804 KB Output is correct
2 Correct 2 ms 8804 KB Output is correct
3 Correct 1 ms 6504 KB Output is correct
4 Correct 1 ms 6504 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 7 ms 51288 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 51348 KB Output is correct
13 Correct 3 ms 19548 KB Output is correct
14 Correct 6 ms 51368 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8804 KB Output is correct
2 Correct 2 ms 8804 KB Output is correct
3 Correct 1 ms 6504 KB Output is correct
4 Correct 1 ms 6504 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 7 ms 51288 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 51348 KB Output is correct
13 Correct 3 ms 19548 KB Output is correct
14 Correct 6 ms 51368 KB Output is correct
15 Correct 7 ms 51544 KB Output is correct
16 Correct 3 ms 19548 KB Output is correct
17 Correct 33 ms 55192 KB Output is correct
18 Correct 28 ms 54608 KB Output is correct
19 Correct 28 ms 55132 KB Output is correct
20 Correct 25 ms 55068 KB Output is correct
21 Correct 25 ms 55132 KB Output is correct
22 Correct 48 ms 57172 KB Output is correct
23 Correct 15 ms 54108 KB Output is correct
24 Correct 30 ms 54928 KB Output is correct
25 Correct 7 ms 51292 KB Output is correct
26 Correct 12 ms 53668 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8804 KB Output is correct
2 Correct 2 ms 8804 KB Output is correct
3 Correct 1 ms 6504 KB Output is correct
4 Correct 1 ms 6504 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 7 ms 51288 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 51348 KB Output is correct
13 Correct 3 ms 19548 KB Output is correct
14 Correct 6 ms 51368 KB Output is correct
15 Correct 7 ms 51544 KB Output is correct
16 Correct 3 ms 19548 KB Output is correct
17 Correct 33 ms 55192 KB Output is correct
18 Correct 28 ms 54608 KB Output is correct
19 Correct 28 ms 55132 KB Output is correct
20 Correct 25 ms 55068 KB Output is correct
21 Correct 25 ms 55132 KB Output is correct
22 Correct 48 ms 57172 KB Output is correct
23 Correct 15 ms 54108 KB Output is correct
24 Correct 30 ms 54928 KB Output is correct
25 Correct 7 ms 51292 KB Output is correct
26 Correct 12 ms 53668 KB Output is correct
27 Correct 49 ms 459348 KB Output is correct
28 Correct 150 ms 119380 KB Output is correct
29 Correct 271 ms 428344 KB Output is correct
30 Correct 383 ms 503888 KB Output is correct
31 Correct 384 ms 505620 KB Output is correct
32 Correct 191 ms 109396 KB Output is correct
33 Correct 386 ms 513364 KB Output is correct
34 Correct 427 ms 513276 KB Output is correct
35 Correct 131 ms 442220 KB Output is correct
36 Correct 371 ms 425540 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 368 ms 770944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 790480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -