Submission #800711

#	Time	Username	Problem	Language	Result	Execution time	Memory
800711		firewater	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	503 ms	274336 KiB

boxes

#include "boxes.h"
#include <stdio.h>
#include <stdlib.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;




















#define N 10001000
ll n,k,ans,x,len,a[N],f[N],g[N];
long long delivery(int NN, int K, int L, int ppp[]) {
    n=NN;
    k=K;
    len=L;
    for(ll i=1;i<=n;++i)
        a[i]=ppp[i-1];
    memset(f,0x7f,sizeof(f));
    memset(g,0x7f,sizeof(g));
    ans=len*n;
    f[0]=0;
    g[n+1]=0;
    for(int i=1;i<=n;++i)
        f[i]=f[max(i-k,0ll)]+min(a[i]*2,len*2);
    for(int i=n;i>0;--i)
        g[i]=g[min(i+k,n+1)]+min((len-a[i])*2,len);
    for(int i=0;i<=n;++i)
        ans=min(ans,f[i]+g[i+1]);
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:45:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |     for(int i=n;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