Submission #678458

#	Time	Username	Problem	Language	Result	Execution time	Memory
678458		hello_there_123	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	265 ms	524288 KiB

boxes

#include <bits/stdc++.h>
//#include "boxes.h"
using namespace std;
 
int delivery(int n, int k, int l, int p[]) 
{
	int pre[l+3],pre2[l+3];
	memset(pre,0,sizeof(pre));
	memset(pre2,0,sizeof(pre2));
	deque<int>left,right;
	for(int i=0;i<n;i++){
		if(p[i]<=l/2) left.push_front(p[i]);
		else{
			right.push_back(l-p[i]);
		}
	}
	sort(right.begin(),right.end());
	for(int i=0;i<left.size();i++){
		pre[(left.size()-i-1)%k]+=left[i];
	}
	for(int i=0;i<right.size();i++){
		pre2[(right.size()-i-1)%k]+=right[i];
	}
	int ans = 1e9;
	for(int i=0;i<(n+l-1)/k;i++){
		int cur = i*l;
		cur+=2*(pre[(left.size()-1)%k]+pre2[(right.size()-1)%k]);
		ans = min(ans,cur);
		for(int j=0;j<k;j++){
			if(left.empty() && right.empty()) break;
			if(left.empty()){
				pre2[(right.size()-1)%k]-=right.front();
				right.pop_front();
			}
			else if(right.empty()){
				pre[(left.size()-1)%k]-=left.front();
				left.pop_front();
			}
			else{
				if(left.front()>right.front()){
					pre[(left.size()-1)%k]-=left.front();
					left.pop_front();
				}
				else{
					pre2[(right.size()-1)%k]-=right.front();
					right.pop_front();				
				}
				
			}
			
		}
		
	}
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'int delivery(int, int, int, int*)':
boxes.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<left.size();i++){
      |              ~^~~~~~~~~~~~
boxes.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<right.size();i++){
      |              ~^~~~~~~~~~~~~

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