Submission #1212368

#TimeUsernameProblemLanguageResultExecution timeMemory
1212368omarpaladines95Nile (IOI24_nile)C++20
17 / 100
2097 ms6412 KiB
#include <bits/stdc++.h> // This solves subtask 4. using namespace std; vector<long long> calculate_costs( vector<int> W, vector<int> A, vector<int> B, vector<int> E) { int N = W.size(); int Q = E.size(); vector<tuple<int, int, int>> artifacts(N); for (int i = 0; i < N; ++i) { artifacts[i] = make_tuple(W[i], A[i], B[i]); } // Sort artifacts by weight ascending first sort(artifacts.begin(), artifacts.end()); // Results for each D in E vector<long long> results(Q); for (int q = 0; q < Q; ++q) { int D = E[q]; // DP[i] stores the minimum cost for sending items from 0 to i. vector<long long> dp(N, ULLONG_MAX); dp[0] = get<1>(artifacts[0]); // Base case: Send 0 on its own. for (int i = 1; i < N; ++i) { // Case 1: send artifact i alone dp[i] = get<1>(artifacts[i]) + dp[i-1]; // Case 2: try to pair i with i-1 if (get<0>(artifacts[i]) - get<0>(artifacts[i-1]) <= D) { long long costLeft = i-2 >= 0 ? dp[i-2] : 0; long long costFromPairingWithNextOne = get<2>(artifacts[i]) + get<2>(artifacts[i-1]) + costLeft; dp[i] = min(dp[i], costFromPairingWithNextOne); } // Case 3: Try to pair i with i-2 if ((get<0>(artifacts[i]) - get<0>(artifacts[i-2]) <= D) && i-2 >= 0) { long long costLeftFromIMinus3 = i-3 >= 0 ? dp[i-3] : 0; long long costFromPairingWithIMinus2 = get<2>(artifacts[i]) + get<1>(artifacts[i-1]) + get<2>(artifacts[i-2]) + costLeftFromIMinus3; dp[i] = min(dp[i], costFromPairingWithIMinus2); } //cout << dp[i] << endl; } results[q] = dp[N-1]; } return results; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...