Submission #538154

#	Time	Username	Problem	Language	Result	Execution time	Memory
538154		huangqr	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	796 ms	258512 KiB

boxes

#include "boxes.h"

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

long long delivery(int N, int K, int L, int p[]) {
	vector<ll>l={0},r={0};
	for(int i=0;i<N;i++){
		if(p[i]!=0){
			if(p[i]<=L/2)l.push_back(p[i]);
			else r.push_back(L-p[i]);
		}
	}
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	ll ans=0;
	/*cout<<"L:\n";
	for(auto x:l)cout<<x<<" ";
	cout<<"\nR:\n";
	for(auto x:r)cout<<x<<" ";
	cout<<"\n";*/
	vector<ll>dpl(l.size(),0),dpr(r.size(),0);
	ll n=l.size()+r.size()-2;
	for(int i=1;i<l.size();i++){
		dpl[i]=2*l[i]+dpl[max(0,i-K)];
		//cout<<"dpl"<<i<<": "<<dpl[i]<<"\n";
	}
	for(int i=1;i<r.size();i++){
		dpr[i]=2*r[i]+dpr[max(0,i-K)];
		//cout<<"dpr"<<i<<": "<<dpr[i]<<"\n";
	}
	ans=dpl.back()+dpr.back();
	//cout<<"pre-ans:"<<ans<<"\n";
	for(int i=0;i<l.size();i++){
		ll circ_left_amt = l.size()-1-i;
		if(circ_left_amt>K)continue;
		ll circ_right_amt = K - circ_left_amt;
		ll right_idx = r.size() - 1 - circ_right_amt;
		if(right_idx < 0)right_idx = 0;
		ll chal = dpl[i]+dpr[right_idx]+L; 
		ans=min(ans,chal);
	}
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=1;i<l.size();i++){
      |              ~^~~~~~~~~
boxes.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=1;i<r.size();i++){
      |              ~^~~~~~~~~
boxes.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0;i<l.size();i++){
      |              ~^~~~~~~~~
boxes.cpp:24:5: warning: unused variable 'n' [-Wunused-variable]
   24 |  ll n=l.size()+r.size()-2;
      |     ^

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