| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 496174 | kevin | 선물상자 (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";
ll delivery(int N, int K, int L, vector<int> ar){
sort(ar.begin(), ar.end());
vector<vector<ll>> cost(N, vector<ll>(2, 0));
for(int i=0; i<N; i++){
if(i<K) {
cost[i][0] = (ll)ar[i] + min(ar[i], L - ar[i]);
cost[N-1-i][1] = (ll)(L - ar[N-1-i]) + min(ar[N-1-i], L - ar[N-1-i]);
}
else {
cost[i][0] = (ll)ar[i] + min(ar[i], L - ar[i]) + cost[i-K][0];
cost[N-1-i][1] = (ll)(L - ar[N-1-i]) + min(ar[N-1-i], L - ar[N-1-i]) + cost[N-1-i+K][1];
}
}
ll ans = cost[0][1];
ans = min(ans, cost[N-1][0]);
for(int i=0; i<N-1; i++){
ans = min(ans, cost[i][0] + cost[i+1][1]); //- max(min(ar[i], L - ar[i]), min(ar[i+1], L - ar[i+1])));
}
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0);
// if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
// int N, K, L;
// cin>>N>>K>>L;
// vector<int> ar(N);
// for(int i=0; i<N; i++) cin>>ar[i];
// cout<<delivery(N, K, L, ar);
// }