Submission #87986

#	Time	Username	Problem	Language	Result	Execution time	Memory
87986		Pajaraja	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	584 ms	196148 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
long long sol[20000033],rem[10000000];
long long delivery(int N, int K, int L, int p[]) 
{
	int n=N,k=K,l=L;
	int z=-1;
	fill(sol,sol+10000000,0);
	fill(rem,rem+10000000,0);
	for(int i=0;i<n-1;i++) if((p[i]<=(l/2)&&p[i+1]>(l/2))) 
	{
		z=i;
		break;
    }
	if(p[0]<=(l/2)&&z==-1) z=n-1;
	if(z==-1)
	{
		long long soln=0;
		for(int i=0;i<n-1;i++) soln+=(long long)(p[i+1]-p[i])*((long long)(i+k)/k);
		soln+=(l-p[n-1])*((long long)(n+k-1)/k);
		return 2*soln;
	}
	if(z==n-1)
	{
		long long solt=0;
		for(int i=n-1;i>0;i--) solt+=(long long)(p[i]-p[i-1])*((long long)(n-i+k-1)/k);
		solt+=p[0]*((long long)(n+k-1)/k);
		return 2*solt;
	}
	sol[1]=2*p[0];
	rem[0]=p[0];
	for(int i=1;i<=z;i++)
	{
		rem[i%k]+=p[i]-p[i-1];
		sol[i+1]=sol[i]+2*rem[i%k];
    }
	fill(rem,rem+10000000,0);
	rem[(n-1)%k]=l-p[n-1];
	sol[n]=2*rem[(n-1)%k];
	for(int i=n-2;i>z;i--)
	{
		rem[i%k]+=p[i+1]-p[i];
		sol[i+1]=sol[i+2]+2*rem[i%k];
    }
    long long rez=sol[z+1]+sol[z+2];
    for(int i=z;i>fmax(-1,z-k);i--) rez=fmin(rez,sol[i]+l+(sol[i+k+1]));
    return rez;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:47:45: warning: conversion to 'long long int' from '__gnu_cxx::__promote_2<long long int, long long int, double, double>::__type {aka double}' may alter its value [-Wfloat-conversion]
     for(int i=z;i>fmax(-1,z-k);i--) rez=fmin(rez,sol[i]+l+(sol[i+k+1]));
                                         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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