oj.uz

Submission #633449

# Submission time Handle Problem Language Result Execution time Memory
633449 2022-08-22T13:27:59 Z Lawliet Catfish Farm (IOI22_fish) C++17
6 / 100
 105 ms 9704 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 100010;

int n;

ll s[maxn][5];

ll maxSuffix[maxn], maxPrefix[maxn];
ll dp[maxn][5][5];

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]++;
        
        if( X[i] == 1 )
            maxPrefix[ Y[i] ] += W[i];
        else
            maxSuffix[ Y[i] ] += W[i];
    }

    for(int i = 1 ; i <= n ; i++)
        maxPrefix[i] += maxPrefix[i - 1];

    for(int i = n ; i > 0 ; i--)
        maxSuffix[i] += maxSuffix[i + 1];

    if( n == 2 )
        return max( maxPrefix[n] , maxSuffix[1] );

    ll aans = 0;

    for(int i = 0 ; i <= n ; i++)
        aans = max( aans , maxPrefix[i] + maxSuffix[i + 1] );

    return aans;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 3 ; j >= 0 ; j--)
            s[i][j] += s[i][j + 1];

    for(int hI = 0 ; hI <= 1 ; hI++)
    {
        for(int hB = 0 ; hB <= 1 ; hB++)
        {
            if( hB <= hI )
                dp[n][hI][hB] = 0;
            else
                dp[n][hI][hB] = s[n][hI + 1] - s[n][hB + 1];
        }
    }

    for(int i = n - 1 ; i > 0 ; i--)
    {
        for(int hI = 0 ; hI <= 1 ; hI++)
        {
            // Calculating dp[i][hI][0]

            for(int x = 0 ; x <= 1 ; x++)
            {
                if( x <= hI )
                    dp[i][hI][0] = max( dp[i][hI][0] , dp[i + 1][x][hI] );
                else
                    dp[i][hI][0] = max( dp[i][hI][0] , dp[i + 1][x][hI] + s[i][hI + 1] - s[i][x + 1] );
            }

            // Calculating dp[i][hI][hB] (hB > 0)
            ll maxFirst = dp[i + 1][0][hI];

            for(int x = 1 ; x >= 0 ; x--)
                maxSuffix[x] = max( maxSuffix[x + 1] , dp[i + 1][x][hI] + s[i][hI + 1] - s[i][x + 1] );

            for(int hB = 1 ; hB <= 1 ; hB++)
            {
                ll& ans = dp[i][hI][hB];

                maxFirst = max( maxFirst , dp[i + 1][hB][hI] );

                if( hB <= hI )
                {
                    ans = dp[i][hI][0];
                    continue;
                }

                ans = max( maxFirst + s[i][hI + 1] - s[i][hB + 1] , maxSuffix[hB + 1] );
            }
        }
    }

    ll ans = 0;

    for(int i = 0 ; i <= 1 ; i++)
        ans = max( ans , dp[1][i][0] );

    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3572 KB Output is correct
2 Correct 32 ms 4172 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 105 ms 8812 KB Output is correct
6 Incorrect 89 ms 8908 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '299997000000000'
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 5420 KB Output is correct
3 Correct 62 ms 9704 KB Output is correct
4 Correct 25 ms 4656 KB Output is correct
5 Correct 31 ms 5672 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 24 ms 4812 KB Output is correct
13 Correct 29 ms 5632 KB Output is correct
14 Correct 26 ms 4740 KB Output is correct
15 Correct 30 ms 5280 KB Output is correct
16 Correct 33 ms 4776 KB Output is correct
17 Correct 28 ms 5228 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Incorrect 14 ms 2900 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Incorrect 14 ms 2900 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3572 KB Output is correct
2 Correct 32 ms 4172 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1832 KB Output is correct
5 Correct 105 ms 8812 KB Output is correct
6 Incorrect 89 ms 8908 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '299997000000000'
7 Halted 0 ms 0 KB -