제출 #748267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748267		bachhoangxuan	메기 농장 (IOI22_fish)	C++17	3 / 100	191 ms	39116 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
struct fish{
    int y=0;
    ll cost,f0=0,f1=0;
    friend bool operator<(fish a,fish b){
        return a.y<b.y;
    }
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<fish>> dp(N+1);
    vector<int> check(N+1,0);
    for(int i=0;i<M;i++){
        X[i]++;Y[i]++;
        dp[X[i]].push_back({Y[i]-1,W[i],0,0});
        check[X[i]]|=(Y[i]==1);
    }
    for(int i=0;i<=N;i++){
        if(!check[i]) dp[i].push_back({0,0,0,0});
        dp[i].push_back({N,0,0,0});
        sort(dp[i].begin(),dp[i].end());
    }
    for(auto &x:dp[0]) x.f0=x.f1=0;
    for(int i=1;i<=N;i++){
        int cur=0;
        ll sum=0,csum=0,Max=dp[i-1][0].f0;
        for(auto &a:dp[i]){
            csum+=a.cost;
            while(cur+1<(int)dp[i-1].size() && dp[i-1][cur+1].y<a.y){
                sum+=dp[i-1][cur].cost;cur++;
                Max=max(Max,dp[i-1][cur].f0-sum);
            }
            a.f0=Max+sum+dp[i-1][cur].cost;
        }
        Max=dp[i-1].back().f1+csum;
        for(int j=(int)dp[i].size()-1;j>=0;j--){
            auto &a=dp[i][j];
            while(cur && dp[i-1][cur-1].y>a.y){
                cur--,Max=max(Max,dp[i-1][cur].f1+csum);
            }
            csum-=a.cost;
            a.f1=Max-csum;
        }
        dp[i].front().f0=max(dp[i].front().f0,dp[i-1].front().f1);
        dp[i].back().f1=max({dp[i].back().f1,dp[i].back().f0,dp[i-1].front().f1});
    }
    return max(dp[N].front().f1,dp[N].back().f0);
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16