Submission #1075981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075981		TB_	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2047 ms	76724 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

typedef vector<ll> vl; 
typedef vector<vl> vvl; 

vl memo, p;
int n, k, l;

ll dp(ll pos){
    if(pos == n) return 0;
    ll &ans = memo[pos];
    if(ans != -1) return ans;
    ans = 1e18;
    ll extra = min((-p[pos]+l)%l, (p[pos]+l)%l);
    fo(i, k){
        ll next = pos+i;
        ans = min(ans, dp(next+1)+min((-p[next]+l)%l, (p[next]+l)%l)+extra);
        if(i==k-1||next+1==n) break;
        extra+=min((p[next]-p[next+1]+l)%l, (p[next+1]-p[next]+l)%l);
    }
    return ans;
}


long long delivery(int N, int K, int L, int P[]) {
    n=N;k=K;l=L;
    memo.assign(n+2, -1);
    fo(i, n) p.pb(P[i]);



    return dp(0);
}

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