제출 #1017960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017960		isaachew	Ski 2 (JOI24_ski2)	C++17	12 / 100	1 ms	388 KiB

Main

#include <bits/stdc++.h>
/*
 If all H_i are different, then 0 cost
 
 ST2: must root at 1, everything built at 1
 If min, must increase
 ST3: permutation
 If cost and height are both less, then do not rearrange them, as less cost available sooner
 Height same as before -> need extra "connection facility"
 Increase height of maximum cost only
 
 Number of extra connections req = max num with same height - 1
 
 O(n^3) dp with this
 */
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<std::pair<long long,long long>> vec;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        vec.push_back({a,b});
        if(a>300)return 0;//no
    }
    std::sort(vec.begin(),vec.end());
    long long basecost=0;
    for(int i=1;i<n;i++){
        if(vec[i].first==vec[0].first){
            vec[i].first++;
            basecost+=k;
        }
    }
    std::vector<int> islots(301);
    std::vector<std::pair<long long,long long>> places;//where a new min is
    int curmin=1e9+1;
    for(int i=0;i<n;i++){
        islots[vec[i].first]++;
        if(vec[i].second<curmin){
            curmin=vec[i].second;
            places.push_back(vec[i]);
        }
    }
    int ind=0;
    long long mincost=1e18;
    std::vector<std::vector<long long>> vals;
    for(int i=1;i<=n;i++){
        std::vector<int> slots(600);
        for(int j=0;j<=300;j++){
            slots[j]=islots[j];
        }
        long long ecost=0;
        int extra=0;
        for(int j=places[ind].first+1;j<600;j++){
            extra+=slots[j];
            if(extra>i){
                slots[j]=i;
                ecost+=extra-i;
                extra-=i;
            }else{
                slots[j]=extra;
                extra=0;
            }
        }
        long long fcost=ecost*k+(i-1)*places[ind].second;
        mincost=std::min(mincost,fcost);
        /*
        int eind=places[ind].first+1;//actual extra
        for(int j=0;j<300;j++){
            long long fcost=ecost*k+(i-1)*places[ind].second;
            mincost=std::min(mincost,fcost);
            
            while(slots[eind]>=i){
                eind++;
            }
            slots[eind]++;
            ecost+=eind-(places[ind].first+1);
        }
         */
    }
    std::cout<<mincost+basecost<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 33
• Subtask 5: 0 / 27
• Subtask 6: 0 / 14