Submission #1037479

#TimeUsernameProblemLanguageResultExecution timeMemory
1037479omarpaladines95Meetings (IOI18_meetings)C++14
4 / 100
5590 ms253228 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; void ComputeDistanceMatrix(int N, const std::vector<int>& H, std::vector<std::vector<int>>& D) { for (int i = 0; i < N; ++i) { D[i][i] = H[i]; for (int j = i+1; j < N; ++j) { D[i][j] = max(H[j], D[i][j-1]); } } } long long minCostForCandidateIdx (const std::vector<int>& H, int L, int R, int candidateIdx, const std::vector<std::vector<int>>& D) { long long costForCandidate = 0; for (int i = L; i < candidateIdx; ++i) { costForCandidate += D[i][candidateIdx]; } for (int i = candidateIdx; i <= R; ++i) { costForCandidate += D[candidateIdx][i]; } return costForCandidate; } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { int Q = L.size(); std::vector<long long> C(Q); int N = H.size(); std::vector<std::vector<int>> distanceMatrix(N, std::vector<int>(N)); ComputeDistanceMatrix(N, H, distanceMatrix); for (int j = 0; j < Q; ++j) { long long minSize = LLONG_MAX; for (int candidateIdx = L[j]; candidateIdx <= R[j]; ++candidateIdx) { long long curCost = minCostForCandidateIdx(H, L[j], R[j], candidateIdx, distanceMatrix); minSize = min(minSize, curCost); } C[j] = minSize; } return C; }
#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...