Submission #667219

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
667219	2022-11-30 19:36:08	atigun	Boxes with souvenirs (IOI15_boxes)	C++11	35 / 100	1 ms	308 KiB

boxes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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