Submission #897782

#	Time	Username	Problem	Language	Result	Execution time	Memory
897782		aqxa	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	477 ms	294004 KiB

boxes

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

const int N = 1e7 + 10; 

#include "boxes.h"

ll ans0[N], ans1[N]; 

long long delivery(int n, int k, int m, int p[]) {
	for (int i = 0; i < n; ++i) {
		if (i < k) {
			ans0[i] = p[i] + min(p[i], m - p[i]); 
			ans1[n - 1 - i] = (ll) m - p[n - 1 - i] + min((ll)p[n - 1 - i], (ll)m - p[n - 1 - i]); 
		} else {
			ans0[i] = ans0[i - k] + p[i] + min(p[i], m - p[i]); 
			ans1[n - 1 - i] = ans1[n - 1 - i + k] + (ll) m - p[n - 1 - i] + min((ll)p[n - 1 - i], (ll)m - p[n - 1 - i]); 
		}
	}
	ll ans = ans0[n - 1]; 
	ans = min(ans, ans1[0]); 
	for (int i = 0; i < n - 1; ++i) {
		ans = min(ans, ans0[i] + ans1[i + 1]); 
	}

    return ans;
}

 
 
// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
 
// 	int n, k, m; 
// 	cin >> n >> k >> m; 
// 	int pos[n]; 
// 	for (int i = 0; i < n; ++i) {
// 		cin >> pos[i]; 
// 	}
// 	cout << "answer: " << delivery(n, k, m, pos) << "\n";
 
// 	return 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