Submission #567899

#	Time	Username	Problem	Language	Result	Execution time	Memory
567899		Trisanu_Das	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	561 ms	278980 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
ll dp1[10000007];
ll dp2[10000007];
 
ll delivery(int n, int k, int l, int pos[])
{
    for (int i = 1;i <= n;i++) dp1[i]= dp1[max(0,i - k)] + 2 * pos[i - 1];
    for (int i=  n;i >= 1;i--) dp2[i]= dp2[min(n + 1,i + k)] + 2 * (l - pos[i - 1]);
 
    ll ans=1e18;
    for (int i = 1;i <= n + 1;i++) ans = min(ans, dp1[i - 1] + dp2[i]);
    for (int i = k;i <= n;i++) ans = min(ans,dp1[i - k] + dp2[i + 1] + l);
    return ans;
}

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