Submission #1171424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171424		ramalzaher	Ski 2 (JOI24_ski2)	C++17	0 / 100	2095 ms	320 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
using ll = long long;

int N;
ll K;
vector<ll> H, C;
ll best = numeric_limits<ll>::max();
void dfs(const vector<int>& order, int pos, vector<ll>& currentL, vector<int>& childCount, ll costSoFar) {
    if (pos == order.size()) {
        best = min(best, costSoFar);
        return;
    }
    
    int cur = order[pos]; 
    for (int j = 0; j < pos; j++) {
        int par = order[j];
        ll newL = max(H[cur], currentL[par] + 1);
        ll embankCost = K * (newL - H[cur]);
        ll extraExtCost = (childCount[par] >= 1 ? C[par] : 0);
        ll oldL = currentL[cur];  
        int oldChild = childCount[par];
        
        currentL[cur] = newL; 
        childCount[par]++;    
        
        dfs(order, pos + 1, currentL, childCount, costSoFar + embankCost + extraExtCost);
        childCount[par] = oldChild;
        currentL[cur] = oldL;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> K;
    H.resize(N);
    C.resize(N);
    for (int i = 0; i < N; i++){
        cin >> H[i] >> C[i];
    }
    
    for (int hotel = 0; hotel < N; hotel++) {
        vector<int> order;
        order.push_back(hotel);
        for (int i = 0; i < N; i++) {
            if (i == hotel) continue;
            order.push_back(i);
        }
        
        do {
            vector<ll> currentL(N, 0);
            vector<int> childCount(N, 0);
            currentL[order[0]] = H[order[0]];
            
            dfs(order, 1, currentL, childCount, 0);
            
        } while (next_permutation(order.begin() + 1, order.end()));
    }
    
    cout << best << "\n";
    return 0;
}

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