oj.uz

답안 #633446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633446 2022-08-22T13:22:35 Z Lawliet 메기 농장 (IOI22_fish) C++17
3 / 100
 82 ms 7276 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];
ll dp[maxn][5][5];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) 
{
    n = N;

    ll aans = 0;

    for(int i = 0 ; i < M ; i++)
    {
        X[i]++; Y[i]++; aans += W[i];
        // s[ X[i] ][ Y[i] ] += W[i];
    }

    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
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2160 KB Output is correct
2 Correct 27 ms 2636 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 80 ms 7276 KB Output is correct
6 Correct 82 ms 7272 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 43 ms 4016 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 18 ms 1492 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 18 ms 1492 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2160 KB Output is correct
2 Correct 27 ms 2636 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 80 ms 7276 KB Output is correct
6 Correct 82 ms 7272 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 43 ms 4016 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
9 Halted 0 ms 0 KB -