제출 #591732

#제출 시각아이디문제언어결과실행 시간메모리
591732l_reho선물상자 (IOI15_boxes)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; long long delivery(int N, int K, int L, int p[]) { vector<long long> dpA(N+1, 0); vector<long long> dpB(N+1, 0); for(int i = 1; i <= N; i++){ if(i >= K){ dpA[i] = dpA[i-K]+p[i-1]*2; }else dpA[i] = dpA[0]+p[i-1]*2; } priority_queue<pair<long long, int>> pq; vector<long long> M(N+1, 0); for(int i = N-1; i >= 0; i--){ if(i+K > N-1) dpB[i] = dpB[N] + (L-p[i])*2; else dpB[i] = dpB[i+K] + (L-p[i])*2; while(!pq.empty() && pq.top().second > i+K+1) pq.pop(); pq.push({-dpB[i], i}); M[i] = -pq.top().first; } long long ans = LLONG_MAX; for(int i = 0; i <= N; i++) ans = min(ans, dpA[i] + dpB[i]); for(int i = 0; i < N; i++){ // eliminiamo questo ciclo ans = min(ans, dpA[i] + M[i] + (long long)L); /* for(int j = 1; j <= K; j++){ if(i+j > N) break; ans = min(ans, dpA[i] + dpB[i+j] + (long long)L); } */ } // considerando che L è una costante, bisogna solo cercare i e i+j minimi // posso risolverlo Nlogn return ans; }
#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...