Submission #376533

#	Time	Username	Problem	Language	Result	Execution time	Memory
376533		qwerasdfzxcl	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	640 ms	281292 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
 
using namespace std;
typedef long long ll;
vector<int> a;
int n, k, l;
ll dp[10001000], dp2[10001000];
 
int dist(int x, int y){
    return min(y-x, l-y+x);
}
 
int val(int x, int y){
    return y-x+dist(0, x)+dist(0, y);
}
 
ll delivery(int N, int K, int L, int pos[]){
    n=N, k=K, l=L;
    for (int i=0;i<n;i++){
        int tmp;
        tmp = pos[i];
        if (!tmp) continue;
        a.push_back(tmp);
    }
    n = a.size();
    int cnt=1;
    dp[0]=dist(0, a[0])*2;
    for (int i=1;i<n;i++){
        //printf("dp[%d]: ", i);
        if (i-k+1<=0) dp[i]=val(a[0], a[i]);
        else dp[i]=dp[i-k]+val(a[i-k+1], a[i]);
        //printf("%lld\n", dp[i]);
    }
  	dp2[n-1]=dist(0, a[n-1])*2;
  	for (int i=n-2;i>=0;i--){
      if (i+k-1>=n-1) dp2[i]=val(a[i], a[n-1]);
      else dp2[i]=dp2[i+k]+val(a[i], a[i+k-1]);
    }
  	ll ans=min(dp[n-1], dp2[0]);
  	for (int i=1;i<n-1;i++) ans = min(ans, dp[i]+dp2[i+1]);
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:26:15: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |     n = a.size();
      |         ~~~~~~^~
boxes.cpp:27:9: warning: unused variable 'cnt' [-Wunused-variable]
   27 |     int cnt=1;
      |         ^~~

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