제출 #216806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216806		mohamedsobhi777	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	537 ms	201464 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std ; 
const int M_N = 1e7 + 7 ;

long long dp1[M_N] , dp2[M_N]; 

long long delivery(int N, int K, int L, int p[]) {
    for(int i = 0 ; i < N ;i ++){
        long long cost = 2ll * p[i] ; 

        if(i>=K-1){
            dp1[i] =  (i==K-1?0:dp1[i-K]) +  min(cost ,1ll * L );
        }else{
            dp1[i] = cost; 
        }
    }
    for(int i = N-1 ; i >=0 ; i--){
        long long cost = 2ll * (L - p[i]) ; 

        if(i < N-K) {
            dp2[i] = dp2[i+K] + min(cost , 1ll *L) ; 
        }else{
            dp2[i] = cost ; 
        }
    }
    long long ret = dp2[0] ; 
    for(int i = 0 ; i < N ;i++){
        ret = min(ret , dp1[i] + dp2[i+1]) ; 
    }
    return ret; 
}

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