Submission #345030

#	Time	Username	Problem	Language	Result	Execution time	Memory
345030		pggp	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	931 ms	311884 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

long long delivery(int N, int K, int L, int p[]){
	vector < int > positions;
	for (int i = 0; i < N; ++i)
	{
		positions.push_back(p[i]);
	}

	vector < int > l, r;
	vector < long long > l_dp, r_dp;
	for (int i = 0; i < N; ++i)
	{
		if(positions[i] > L/2){
			r.push_back(positions[i]);
		}
		else{
			l.push_back(positions[i]);
		}
	}
	sort(r.begin(), r.end(), greater < int >());
	l_dp.resize(N + 1);
	r_dp.resize(N + 1);
	for (int i = 0; i < l.size(); ++i)
	{
		if(i >= K){
			l_dp[i] = l_dp[i - K] + l[i];
		}
		else{
			l_dp[i] = l[i];
		}
	}
	for (int i = 0; i < r.size(); ++i)
	{
		if(i >= K){
			r_dp[i] = r_dp[i - K] + (L - r[i]);
		}
		else{
			r_dp[i] = L - r[i];
		}
	}
	//cout << r.size() << " " << l.size() << endl; 
	long long a1, b1;
	a1 = 0;
	b1 = 0;
	if(l.size() > 0){
		a1 = 2 * l_dp[l.size() - 1];
	}
	if(r.size() > 0){
		b1 = 2 * r_dp[r.size() - 1];
	}
	long long ans = a1 + b1;
	//cout << ans << endl;
	for (int i = 1; i < K; ++i)
	{
		//cout << ans << endl;
		long long a, b;

		long long s = l.size() - i - 1;
		if(s < 0){
			a = 0;
		}
		else{
			a = 2 * l_dp[l.size() - i - 1];
		}
		
		long long t = (r.size() - (K - i) - 1);
		//cout << "A = " << t << endl;
		if(t < 0){
			b = 0;
		}
		else{
			//cout << r.size() << endl;
			b = 2 * r_dp[r.size() - (K - i) - 1];
		}
		ans = min(ans, a +  b + L);
	}


	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < l.size(); ++i)
      |                  ~~^~~~~~~~~~
boxes.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < r.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