Submission #235707

#	Time	Username	Problem	Language	Result	Execution time	Memory
235707		abacaba	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	586 ms	243944 KiB

boxes

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define ll long long
#define endl '\n'
#define pii pair<int, int>

inline void setin(string s) {
	freopen(s.c_str(), "r", stdin);
}

inline void setout(string s) {
	freopen(s.c_str(), "w", stdout);
}

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e7 + 15;
ll dp[2][N];

long long delivery(int n, int k, int l, int p[]) {
	for(int i = 0; i < n; ++i) {
		if(i < k)
			dp[0][i] = 2 * p[i];
        else
            dp[0][i] = dp[0][i-k] + 2 * p[i];
	}
    for(int i = n - 1; i >= 0; --i) {
        if(i + k >= n)
            dp[1][i] = 2 * (l - p[i]);
        else
            dp[1][i] = dp[1][i+k] + 2 * (l - p[i]);
    }
    ll ans = min(dp[0][n-1], dp[1][0]);
    for(int i = -1; i + 1 < n; ++i)
        ans = min(ans, (i == -1 ? 0ll : dp[0][i]) + l + dp[1][min(n, i + k + 1)]);
    for(int i = n; i >= 0; --i)
        ans = min(ans, dp[1][i] + l + (i - k - 1 >= 0 ? dp[0][i - k - 1] : 0ll));
    for(int i = 0; i + 1 < n; ++i)
        ans = min(ans, dp[0][i] + dp[1][i+1]);
    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