Submission #219192

#	Time	Username	Problem	Language	Result	Execution time	Memory
219192		emil_physmath	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	710 ms	323576 KiB

boxes

#include <algorithm>
#include "boxes.h"
using namespace std;
typedef long long llong;
const int maxN = 10000001;

int n;
llong dppref_[maxN], dpsuff_[maxN];
llong mn[maxN];

inline llong dppref(int i) { return (i < 0) ? 0 : dppref_[i]; }
inline llong dpsuff(int i) { return (i >= n) ? 0 : dpsuff_[i]; }
long long delivery(int n_, int k, int len, int pos[])
{
    n = n_;
    for (int i = 0; i < n; ++i)
        dppref_[i] = 2LL * pos[i] + dppref(i - k);
    for (int i = n - 1; i >= 0; --i)
        dpsuff_[i] = 2LL * (len - pos[i]) + dpsuff(i + k);
    llong ans = dpsuff(0);
    const llong inf = 50000000000000000LL;
    fill(mn, mn + maxN, inf);
    for (int i = n - 1; i >= 0; --i)
    {
        ans = min(ans, dppref(i) + dpsuff(i + 1));
        ans = min(ans, mn[i % k] + dppref(i - 1) - (i / k) * (llong)len);
        ++i;
        mn[i % k] = min(mn[i % k], (i / k) * (llong)len + dpsuff(i));
        --i;
    }
    /*for (int i = 0; i < n; ++i)
    {
        ans = min(ans, dppref(i) + dpsuff(i + 1));
        for (int j = i + 2; j <= n; ++j)
        {
            if (i % k != j % k)
                continue;
            llong curans = j / k - i / k;
            curans *= len;
            curans += dppref(i - 1) + dpsuff(j);
            ans = min(ans, curans);
        }
    }*/
    return ans;
}
/*
3 2 8
1 2 5

10
*/
/*
3 2 100
10 47 60

120
*/

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