oj.uz

답안 #858811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858811 2023-10-09T08:25:01 Z LucaIlie 메기 농장 (IOI22_fish) C++17
15 / 100
 1000 ms 540984 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++ ) {
        for ( int i = 1; i < ys[x].size(); i++ )
            spX[x][ys[x][i]] = spX[x][ys[x][i - 1]] + costCell[x][ys[x][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]] );
    }

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

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 255280 KB Output is correct
2 Correct 404 ms 286384 KB Output is correct
3 Correct 161 ms 210376 KB Output is correct
4 Correct 161 ms 210208 KB Output is correct
5 Execution timed out 1053 ms 540984 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 122456 KB Output is correct
2 Correct 517 ms 295876 KB Output is correct
3 Correct 561 ms 322756 KB Output is correct
4 Correct 340 ms 256412 KB Output is correct
5 Correct 413 ms 286676 KB Output is correct
6 Correct 30 ms 122456 KB Output is correct
7 Correct 31 ms 122536 KB Output is correct
8 Correct 28 ms 122460 KB Output is correct
9 Correct 30 ms 122440 KB Output is correct
10 Correct 163 ms 210192 KB Output is correct
11 Correct 158 ms 210204 KB Output is correct
12 Correct 437 ms 278864 KB Output is correct
13 Correct 527 ms 317904 KB Output is correct
14 Correct 418 ms 267992 KB Output is correct
15 Correct 355 ms 264412 KB Output is correct
16 Correct 405 ms 267660 KB Output is correct
17 Correct 481 ms 295656 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 210028 KB Output is correct
2 Correct 160 ms 210000 KB Output is correct
3 Correct 270 ms 223140 KB Output is correct
4 Correct 243 ms 226336 KB Output is correct
5 Correct 378 ms 246344 KB Output is correct
6 Correct 364 ms 246100 KB Output is correct
7 Correct 375 ms 246300 KB Output is correct
8 Correct 365 ms 246352 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122460 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 30 ms 122460 KB Output is correct
5 Correct 28 ms 122316 KB Output is correct
6 Correct 28 ms 122460 KB Output is correct
7 Correct 27 ms 122460 KB Output is correct
8 Correct 27 ms 122532 KB Output is correct
9 Correct 28 ms 122712 KB Output is correct
10 Correct 30 ms 123372 KB Output is correct
11 Correct 28 ms 122780 KB Output is correct
12 Incorrect 31 ms 123228 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '444344977185'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122460 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 30 ms 122460 KB Output is correct
5 Correct 28 ms 122316 KB Output is correct
6 Correct 28 ms 122460 KB Output is correct
7 Correct 27 ms 122460 KB Output is correct
8 Correct 27 ms 122532 KB Output is correct
9 Correct 28 ms 122712 KB Output is correct
10 Correct 30 ms 123372 KB Output is correct
11 Correct 28 ms 122780 KB Output is correct
12 Incorrect 31 ms 123228 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '444344977185'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 122456 KB Output is correct
2 Correct 28 ms 122460 KB Output is correct
3 Correct 28 ms 122456 KB Output is correct
4 Correct 30 ms 122460 KB Output is correct
5 Correct 28 ms 122316 KB Output is correct
6 Correct 28 ms 122460 KB Output is correct
7 Correct 27 ms 122460 KB Output is correct
8 Correct 27 ms 122532 KB Output is correct
9 Correct 28 ms 122712 KB Output is correct
10 Correct 30 ms 123372 KB Output is correct
11 Correct 28 ms 122780 KB Output is correct
12 Incorrect 31 ms 123228 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '444344977185'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 210028 KB Output is correct
2 Correct 160 ms 210000 KB Output is correct
3 Correct 270 ms 223140 KB Output is correct
4 Correct 243 ms 226336 KB Output is correct
5 Correct 378 ms 246344 KB Output is correct
6 Correct 364 ms 246100 KB Output is correct
7 Correct 375 ms 246300 KB Output is correct
8 Correct 365 ms 246352 KB Output is correct
9 Correct 577 ms 296404 KB Output is correct
10 Correct 255 ms 198568 KB Output is correct
11 Correct 553 ms 274732 KB Output is correct
12 Correct 28 ms 122456 KB Output is correct
13 Correct 28 ms 122448 KB Output is correct
14 Correct 28 ms 122448 KB Output is correct
15 Correct 27 ms 122460 KB Output is correct
16 Correct 28 ms 122460 KB Output is correct
17 Correct 28 ms 122460 KB Output is correct
18 Correct 159 ms 210044 KB Output is correct
19 Correct 163 ms 210004 KB Output is correct
20 Correct 158 ms 210000 KB Output is correct
21 Correct 157 ms 210000 KB Output is correct
22 Incorrect 618 ms 297552 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '41487184087204'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 255280 KB Output is correct
2 Correct 404 ms 286384 KB Output is correct
3 Correct 161 ms 210376 KB Output is correct
4 Correct 161 ms 210208 KB Output is correct
5 Execution timed out 1053 ms 540984 KB Time limit exceeded
6 Halted 0 ms 0 KB -