Submission #1234534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234534		oolimry	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	1491 ms	105136 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define debu(x) cerr<<#x<<" = "<<x<<"\n";
#define debu2(x,y) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<"\n";

//forgetting to make my priority queue a minimum heap one :(
int n,k,l;
#define int long long
int dist(int x, int y)
{
	if(x>y)swap(x,y);
	return min(y-x,l-y+x);
}
#undef int 

long long delivery(int N, int K, int L, int p[]) 
{
	#define int long long
	n=N;k=K;l=L;
    int ans=0;
    
    int prev=0;
    for(int i=0;i<N;i++)
    {
		ans+=dist(prev,p[i]);
		prev=p[i];
	}
	ans+=dist(prev,0);
	
	priority_queue<pii,vector<pii>,greater<pii>>dp;
	dp.push(mp(0,0));
	
	for(int i=1;i<N;i++)
	{
		int curr=dist(0,p[i-1])+dist(0,p[i])-dist(p[i-1],p[i]);
		while(i-dp.top().ss>K){dp.pop();}
		dp.push(mp(curr+dp.top().ff,i));
	}
	
	while(n-dp.top().ss>K){dp.pop();}
	ans+=dp.top().ff;
	#undef int 
	return ans;
}

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