Submission #1210393

#TimeUsernameProblemLanguageResultExecution timeMemory
1210393PagodePaivaNile (IOI24_nile)C++20
67 / 100
2094 ms7300 KiB
#include "nile.h" #include<bits/stdc++.h> using namespace std; const int N = 200010; long long dp[N]; long long custo[N]; long long w[N]; vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { int n = W.size(); long long sum = 0; vector <array <int, 3>> ordenar; for(int i = 0;i < n;i++){ ordenar.push_back({W[i], A[i], B[i]}); } sort(ordenar.begin(), ordenar.end()); for(int i = 0;i < n;i++){ w[i+1] = ordenar[i][0]; sum += (long long) (ordenar[i][1]); custo[i+1] = ordenar[i][1] - ordenar[i][2]; } vector <long long> resposta; for(auto d : E){ dp[0] = 0; for(int i = 1;i <= n;i++){ dp[i] = dp[i-1]; if(i > 1){ if(abs(w[i] - w[i-1]) <= d){ dp[i] = max(dp[i], dp[i-2] + custo[i] + custo[i-1]); } } if(i > 2){ if(abs(w[i] - w[i-2]) <= d){ dp[i] = max(dp[i], dp[i-3] + custo[i] + custo[i-2]); } } } resposta.push_back(sum - dp[n]); } return resposta; }
#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...