제출 #633486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633486		Lawliet	메기 농장 (IOI22_fish)	C++17	23 / 100	1095 ms	35004 KiB

fish

#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
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16