Submission #1040724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040724		idas	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	388 ms	293760 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)

using namespace std;
typedef long long ll;

const ll LINF=1e18;
const int MxN=1e7+10;
ll n, k, l, a[MxN], b[MxN];

long long delivery(int N, int K, int L, int p[]) {
    n=N; k=K; l=L;

    int in=0;
    while(in<n && p[in]==0) in++;
    FOR(i, in, n) p[i-in]=p[i];
    n-=in;

    FOR(i, 0, n)
    {
        if(i-k>=0) a[i]=a[i-k];
        a[i]+=p[i];
        a[i]+=min(1LL*p[i], l-p[i]);
    }

    for(int i=n-1; i>=0; i--){
        if(i+k<=n-1) b[i]=b[i+k];
        b[i]+=l-p[i];
        b[i]+=min(1LL*p[i], l-p[i]);
    }

    ll ans=min(a[n-1], b[0]);
    FOR(i, 0, n-1) ans=min(ans, a[i]+b[i+1]);

    return ans;
}

Compilation message (stderr)

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