oj.uz

Submission #633486

# Submission time Handle Problem Language Result Execution time Memory
633486 2022-08-22T14:47:08 Z Lawliet Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 35004 KB 
#include "fish.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 100010;
 
int n;
 
ll dp[maxn][5][5];
 
vector<pair<int,int>> coin[maxn];

ll cost(int i, int hI, int hB, int hN)
{
    int realB = coin[i - 1][hB].first;
    int realN = coin[i + 1][hN].first;

    ll cost = 0;

    for(int j = hI ; j < (int)coin[i].size() ; j++)
        if( coin[i][j].first < realB || coin[i][j].first < realN ) cost += coin[i][j].second;

    return cost;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) 
{
    n = N;
 
    for(int i = 0 ; i < M ; i++)
    {
        X[i]++; Y[i]++;
        coin[ X[i] ].push_back( { Y[i] - 1 , W[i] } );
    }

    coin[0].push_back( { 0 , 0 } );
    coin[n + 1].push_back( { 0 , 0 } );

    for(int i = 1 ; i <= n ; i++)
    {
        sort( coin[i].begin() , coin[i].end() );

        coin[i].push_back( { n , 0 } );

        if( coin[i].front().first != 0 )
            coin[i].insert( coin[i].begin() , { 0 , 0 } );
    }
 
    for(int hI = 0 ; hI < (int)coin[n].size() ; hI++)
        for(int hB = 0 ; hB < (int)coin[n - 1].size() ; hB++)
            dp[n][hI][hB] = cost( n , hI , hB , 0 );
 
    for(int i = n - 1 ; i > 0 ; i--)
    {
        for(int hI = 0 ; hI < (int)coin[i].size() ; hI++)
        {
            for(int hB = 0 ; hB < (int)coin[i - 1].size() ; hB++)
            {
                ll& ans = dp[i][hI][hB];

                for(int x = 0 ; x < (int)coin[i + 1].size() ; x++)
                {
                    ans = max( ans , dp[i + 1][x][hI] + cost( i , hI , hB , x ) );
                }
            }
        }
    }
 
    ll ans = 0;
 
    for(int i = 0 ; i < (int)coin[1].size() ; i++)
        ans = max( ans , dp[1][i][0] );
 
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1088 ms 28148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25260 KB Output is correct
2 Correct 24 ms 25340 KB Output is correct
3 Correct 40 ms 24300 KB Output is correct
4 Correct 42 ms 26176 KB Output is correct
5 Correct 75 ms 27648 KB Output is correct
6 Correct 61 ms 27596 KB Output is correct
7 Correct 59 ms 27592 KB Output is correct
8 Correct 58 ms 27620 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 6 ms 2840 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '944218034284'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 6 ms 2840 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '944218034284'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 6 ms 2840 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '944218034284'
11 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25260 KB Output is correct
2 Correct 24 ms 25340 KB Output is correct
3 Correct 40 ms 24300 KB Output is correct
4 Correct 42 ms 26176 KB Output is correct
5 Correct 75 ms 27648 KB Output is correct
6 Correct 61 ms 27596 KB Output is correct
7 Correct 59 ms 27592 KB Output is correct
8 Correct 58 ms 27620 KB Output is correct
9 Correct 97 ms 30192 KB Output is correct
10 Correct 56 ms 18636 KB Output is correct
11 Correct 123 ms 35004 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2660 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2660 KB Output is correct
16 Correct 3 ms 2656 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 26 ms 25264 KB Output is correct
19 Correct 29 ms 25228 KB Output is correct
20 Correct 31 ms 25308 KB Output is correct
21 Correct 24 ms 25312 KB Output is correct
22 Correct 86 ms 30608 KB Output is correct
23 Correct 142 ms 33504 KB Output is correct
24 Correct 170 ms 34360 KB Output is correct

Subtask #8
0 / 16.0

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