Submission #125016

#	Time	Username	Problem	Language	Result	Execution time	Memory
125016		dorijanlendvaj	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1681 ms	217552 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define ll long long
#define vl vector<ll>
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MOD=1000000007,N=1e7+10;
const char en='\n';
const ll LLINF=1ll<<60;
ll time1[N],time2[N],ans;
int n1,n2;

ll f(int r)
{
	int lo=max(0,r-n2),hi=min(n1,r)-1;
	while (lo<hi)
	{
		int mid=(lo+hi)/2;
		int i=mid,i1=mid+1;
		ll x=time1[n1-i]+time2[n2-(r-i)];
		i=i1;
		ll y=time1[n1-i]+time2[n2-(r-i)];
		if (x<=y) hi=mid;
		else lo=mid+1;
	}
	int i=lo;
	ll k=time1[n1-i]+time2[n2-(r-i)];
	ll k1=LLINF;
	int hi1=min(n1,r);
	if (i<hi1)
	{
		++i;
		k1=time1[n1-i]+time2[n2-(r-i)];
	}
	return min(k,k1)*2;
}

ll f1(int r)
{
	ll k=LLINF;
	for (int i=max(0,r-n2);i<=min(n1,r);++i) k=min(k,time1[n1-i]+time2[n2-(r-i)]);
	return k*2;
}

ll delivery(int n, int k, int l, int p[]) {
	vi h1,h2;
	for (int i=0;i<n;++i) if (p[i]*2<l) h1.pb(p[i]);
	else h2.pb(p[i]);
	reverse(h2.begin(),h2.end());
	for (int&a: h2) a=l-a;
	n1=h1.size();
	n2=h2.size();
	for (int i=0;i<min(k,n1);++i) time1[i+1]=h1[i];
	for (int i=k;i<n1;++i) time1[i+1]=h1[i]+time1[i-k+1];
	for (int i=0;i<min(k,n2);++i) time2[i+1]=h2[i];
	for (int i=k;i<n2;++i) time2[i+1]=h2[i]+time2[i-k+1];
	//for (int i=0;i<=n1;++i) cout<<time1[i]<<' ';
	//cout<<endl;
	//for (int i=0;i<=n2;++i) cout<<time2[i]<<' ';
	//cout<<endl;
	ans=(n+k-1)/k*1ll*l;
	for (int fc=0;fc*k<=n;++fc)
	{
		if (k<=100) ans=min(ans,f(fc*k)+fc*1ll*l);
		else ans=min(ans,f1(fc*k)+fc*1ll*l);
	}
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:56:12: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  n1=h1.size();
     ~~~~~~~^~
boxes.cpp:57:12: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  n2=h2.size();
     ~~~~~~~^~

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