Submission #607497

#	Time	Username	Problem	Language	Result	Execution time	Memory
607497		MrDeboo	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	561 ms	164356 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
long long delivery(int n, int k, int l, int p[]) {
    deque<int>x,y;
    for(int i=0;i<k;i++)y.push_back(0);
    for(int i=0;i<n;i++){
        if(p[i]==0)continue;
        int X=l-p[i];
        if(X<p[i])x.push_front(X);
        else y.push_back(p[i]);
    }
    for(int i=0;i<k;i++)x.push_front(0);
    long long X[k+1];
    long long Y[k+1];
    long long ans=0,f=0;
    for(int i=x.size()-1;i>=0;i-=k)f+=x[i]*2;
    for(int i=y.size()-1;i>=0;i-=k)f+=y[i]*2;
    ans=f;
    memset(X,0,sizeof X);
    memset(Y,0,sizeof Y);
    int g=1;
    for(int i=x.size()-1;i>=0;i--){
        if(x[i]==0)break;
        X[g++]+=(x[i]-x[i-1])*2;
        if(g==k+1)g=1;
    }
    g=1;
    for(int i=y.size()-1;i>=0;i--){
        if(y[i]==0)break;
        Y[g++]+=(y[i]-y[i-1])*2;
        if(g==k+1)g=1;
    }
    for(int i=1;i<=k;i++){
        X[i]+=X[i-1];
        Y[i]+=Y[i-1];
    }
    for(int i=0;i<=k;i++)ans=min(ans,f-X[i]-Y[k-i]+l);
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:17:23: warning: conversion from 'std::deque<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   17 |     for(int i=x.size()-1;i>=0;i-=k)f+=x[i]*2;
      |               ~~~~~~~~^~
boxes.cpp:18:23: warning: conversion from 'std::deque<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 |     for(int i=y.size()-1;i>=0;i-=k)f+=y[i]*2;
      |               ~~~~~~~~^~
boxes.cpp:23:23: warning: conversion from 'std::deque<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |     for(int i=x.size()-1;i>=0;i--){
      |               ~~~~~~~~^~
boxes.cpp:29:23: warning: conversion from 'std::deque<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |     for(int i=y.size()-1;i>=0;i--){
      |               ~~~~~~~~^~

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