Submission #519635

#	Time	Username	Problem	Language	Result	Execution time	Memory
519635		silverfish	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	1781 ms	417884 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
using ll = long long;
const ll N = 10000007, inf = 1e18+10;

ll dp[N], s[N];
array<ll,2> fen[N];

void ins(ll v, int p){
        int po = p;
        for(;p<N;p+=p&-p){
                if(v < fen[p][0]){
                        fen[p][0] = v;
                        fen[p][1] = po;
                }
        }
}

int get(int p){
        ll mn=inf, mnpos = -1;
        for(;p;p-=p&-p){
                if(fen[p][0] < mn){
                        mn = fen[p][0];
                        mnpos = fen[p][1];
                }
        }
        return mnpos;
}


long long delivery(int n, int k, int L, int p[]) {
        ll l = L;
        fill(dp, dp+N, inf);
        fill(fen, fen+N, array<ll,2>{inf, -1});

        for(int i = 0; i < n; ++i){
                s[i] = (i ? dp[i-1] : 0) + min(2LL*(l-p[i]), l);
                ins(s[i], n-i);

                int pos = n-get(min(n-i+k-1, n));
                dp[i] = (pos ? dp[pos-1] : 0) +min({l,2LL*p[i], 2LL*(l-p[pos])});
        }

    return dp[n-1];
}

Compilation message (stderr)

boxes.cpp: In function 'int get(int)':
boxes.cpp:28:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   28 |         return mnpos;
      |                ^~~~~

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