Submission #287115

#	Time	Username	Problem	Language	Result	Execution time	Memory
287115		shayan_p	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	465 ms	119544 KiB

boxes

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "boxes.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e7 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

ll dp[maxn];

ll delivery(int n, int k, int l, int a[]){
    int lim = (l+1)/2;
    int ptlim = 0;
    while(ptlim < n && a[ptlim] < lim){	
	dp[ptlim] = 2ll * a[ptlim];
	if(ptlim >= k)
	    dp[ptlim]+= dp[ptlim-k];
	ptlim++;
    }
    for(int i = n-1; i >= ptlim; i--){
	dp[i] = 2ll * (l - a[i]);
	if(i + k < n)
	    dp[i]+= dp[i+k];
    }
    dp[n] = 0;
    
    ll ans = (ptlim > 0 ? dp[ptlim-1] : 0) + (ptlim < n ? dp[ptlim] : 0);
    if(ptlim > 0 && ptlim < n){
	for(int i = 0; i < ptlim; i++){
	    int cnt = ptlim - i;
	    if(cnt < k)
		ans = min(ans, (i == 0 ? 0 : dp[i-1]) + dp[min(n, i+k)] + 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