Submission #1044975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044975		vanea	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	428 ms	293960 KiB

boxes

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

const ll INF = 1e18;

ll delivery(int n, int k, int l, int p[]) {
    vector<ll> dp1(n+1), dp2(n+2);
    ll ans = INF;
    for(int i = 1; i <= n; i++) {
        int last = max(0, i-k);
        ll lastP = (last ? p[last-1] : 0);
        ll lastP1 = (i-1 ? p[i-2] : 0);
        dp1[i] = dp1[last] + lastP*2 + p[i-1]-lastP;
        //dp1[i] = min(dp1[i], dp1[i-1] + p[i-1]-lastP1 + (l-lastP1));
        //cout << dp1[i] << '\n';
    }
    for(int i = n; i >= 1; i--) {
        int last = min(n+1, i+k);
        ll lastP = (last != n+1 ? (l-p[last-1]) : 0);
        ll lastP1 = (last != n+1 ? p[last-1] : l);
        //ll lastP2 = (last != n+1 ? p[last-1] : )
        dp2[i] = dp2[last] + 2*lastP + lastP1-p[i-1];
        //dp2[i] = min(dp2[i], dp2[i+1] + lastP2 + p[i-1]);
    }
    for(int i = 0; i <= n; i++) {
        ll add1 = 0, add2 = 0;
        if(i) add1 = min((ll)p[i-1], (ll)l-p[i-1]);
        if(i != n) add2 = min(p[i], l-p[i]);
        ans = min(ans, add1+add2+dp1[i]+dp2[i+1]);
    }
    return ans;
}
/*
int main()
{
    int arr[5] = {1,5,5,15,19};
    cout << delivery(5, 2, 20, arr);
}*/

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:15:12: warning: unused variable 'lastP1' [-Wunused-variable]
   15 |         ll lastP1 = (i-1 ? p[i-2] : 0);
      |            ^~~~~~

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