Submission #977648

#	Time	Username	Problem	Language	Result	Execution time	Memory
977648		SmuggingSpun	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	482 ms	293852 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
ll delivery(int n, int k, int L, int p[]){
	if(k == 1){
		ll ans = 0;
		for(int i = 0; i < n; i++){
			ans += min(p[i], L - p[i]) << 1;
		}
		return ans;
	}
	if(k >= n){
		ll ans = min(L, min(p[n - 1], L - p[0]) << 1);
		for(int i = 0; i + 1 < n; i++){
			minimize(ans, ll(p[i] + L - p[i + 1]) << 1LL);
		}		
		return ans;
	}
	if(n <= 10){
		vector<int>d(1, 0);
		for(int i = 0; i < n; i++){
			if(p[i] != d.back()){
				d.emplace_back(p[i]);
			}
		}
		vector<vector<vector<ll>>>dp(d.size(), vector<vector<ll>>(k + 1, vector<ll>(1 << n, INF)));
		dp[0][k][(1 << n) - 1] = 0;
		for(int mask = (1 << n) - 1; mask > -1; mask--){
			for(int i = 0; i < d.size(); i++){
				for(int j = 0; j <= k; j++){
					minimize(dp[0][k][mask], dp[i][j][mask] + min(d[i], L - d[i]));
				}
			}
			for(int i = 0; i < d.size(); i++){
				for(int j = 0; j < d.size(); j++){
					for(int t = 0; t <= k; t++){
						minimize(dp[j][t][mask], dp[i][t][mask] + min(abs(d[i] - d[j]), L - abs(d[i] - d[j])));
					}
				}
			}
			for(int i = 0; i < d.size(); i++){
				for(int j = 1; j <= k; j++){
					for(int t = 0; t < n; t++){
						if(1 << t & mask){
							minimize(dp[lower_bound(d.begin(), d.end(), p[t]) - d.begin()][j - 1][mask ^ (1 << t)], dp[i][j][mask] + min(abs(d[i] - p[t]), L - abs(d[i] - p[t])));
						}
					}
				}
			}
		}	
		return dp[0][k][0];
	}
	vector<ll>l(n + 1), r(n + 1);
	l[0] = r[0] = 0;
	for(int i = 1; i <= n; i++){
		l[i] = l[max(0, i - k)] + (p[i - 1] << 1);
		r[i] = r[max(0, i - k)] + ((L - p[n - i]) << 1);
	}
	ll ans = INF;
	for(int i = 0; i <= n; i++){
		minimize(ans, l[i] + r[n - i]);
	}
	for(int i = k - 1; i < n; i++){
		minimize(ans, l[i - k + 1] + r[n - i - 1] + L);
	}
	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int i = 0; i < d.size(); i++){
      |                   ~~^~~~~~~~~~
boxes.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int i = 0; i < d.size(); i++){
      |                   ~~^~~~~~~~~~
boxes.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int j = 0; j < d.size(); j++){
      |                    ~~^~~~~~~~~~
boxes.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i = 0; i < d.size(); i++){
      |                   ~~^~~~~~~~~~

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