제출 #218505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218505		socho	선물상자 (IOI15_boxes)	C++14	100 / 100	679 ms	450240 KiB

boxes

#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
 
const long long MXN = 10000005;
long long n, k, l, pos[MXN], rpos[MXN];
long long dpleft[MXN];
long long dpright[MXN];
 
long long delivery(int N, int K, int L, int p[]) {
	for (int i=0; i<MXN; i++) {
		dpleft[i] = -1;
		dpright[i] = -1;
	}
	n = N;
	k = K;
	l = L;
	for (int i=0; i<n; i++) {
		pos[i] = p[i];
		rpos[i] = L - p[i];
	}
	long long best = LLONG_MAX;
	for (int i=0; i<n; i++) {
		dpleft[i] = pos[i] * 2;
		if (i - k >= 0) dpleft[i] += dpleft[i-k];
	}
	for (int i=n-1; i>=0; i--) {
		dpright[i] = rpos[i] * 2;
		if (i + k < n) dpright[i] += dpright[i+k];
	}
	// for (int i=0; i<n; i++) cout << dpleft[i] << ' '; cout << endl;
	// for (int i=0; i<n; i++) cout << dpright[i] << ' '; cout << endl;
	
	best = min(best, dpleft[n-1]);
	best = min(best, dpright[0]);
	
	for (int i=0; i<n-1; i++) {
		best = min(best, dpleft[i] + dpright[i+1]);
	}
	for (int i=0; i<n-1; i++) {
		// skip i..i+k-1 using the circle
		long long unt = l;
		if (i >= 1) unt += dpleft[i-1];
		if (i + k < n) unt += dpright[i+k];
		best = min(best, unt);
	}
	
	return best;
	
}

컴파일 시 표준 에러 (stderr) 메시지

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:27:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  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