제출 #813105

#제출 시각아이디문제언어결과실행 시간메모리
813105Kerim선물상자 (IOI15_boxes)C++17
20 / 100
1 ms232 KiB
#include "boxes.h" #include "bits/stdc++.h" using namespace std; #define ll long long int f(int n, int k){ return (n+k-1) / k; } long long delivery(int n, int k, int l, int p[]) { vector<int> arr(n+2); arr[n+1] = l; for (int i = 1; i <= n; i++) arr[i] = p[i-1]; ll answer = 0; if (k == 1){//subtask1 for (int i = 1; i <= n; i++) answer += 2LL * min(arr[i], l - arr[i]); } else if(k == n){//subtask2 answer = l; for (int i = 0; i + 1 <= n + 1; i++) answer = min(answer, 2LL * (arr[i] + l - arr[i+1])); } else if(n <= 1000){ vector<ll> pref(n+1), suf(n+1); answer = f(n, k) * 1LL * l; for (int i = 1; i <= n; i++){ pref[i] = arr[i]; if (i >= k) pref[i] += pref[i-k]; } for (int i = n; i >= 1; i--){ suf[i] = l - arr[i]; if (i + k <= n) suf[i] += suf[i+k]; } for (int i = 0; i <= n; i++) for (int j = i+1; j <= n+1; j++){ int c = f(j-i-1, k); answer = min(answer, c*1LL*l + 2*(pref[i] + suf[j])); } } return answer; }
#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...