제출 #667219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667219		atigun	선물상자 (IOI15_boxes)	C++11	35 / 100	1 ms	308 KiB

boxes

#include<bits/stdc++.h>
#include "boxes.h"
using namespace std;
typedef long long ll;

vector<ll> dpl, dpr;

ll delivery(int N, int K, int L, int p[]){
  dpl.assign(N, 1e18), dpr.assign(N, 1e18);
  dpl[0] = 2*p[0], dpr[N-1] = 2*(L-p[N-1]);
  for(int i = 1; i < N; i++)
    dpl[i] = (i-K>=0?dpl[i-K]:0) + p[i] + p[i];
  for(int i = N-2; i >= 0; i--)
    dpr[i] = (i+K<N?dpr[i+K]:0) + L-p[i] + L-p[i];
  ll ans = 1e18;
  for(int i = 0; i <= N; i++)
    ans = min(ans, (i-1>=0?dpl[i-1]:0) + (i<N?dpr[i]:0));
  for(int l = 0, r = min(N-1, K-1); r < N; l+= 1, r+= 1)
    ans = min(ans, L + (l-1>=0?dpl[l-1]:0) + (r+1<N?dpr[r]:0));
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30