제출 #57946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57946		E869120	Boxes with souvenirs (IOI15_boxes)	C++14	25 / 100	2 ms	420 KiB

boxes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int v[10000009], NN, KK, LL; bool used[10000009];

long long dist(int L, int R, int ty) {
	while (L >= NN) { L -= NN; R -= NN; }
	long long V1 = v[L % NN], V2 = v[R % NN];
	long long ret = min(V2, LL - V1);

	if (L < NN && R >= NN) ret = (LL - V1) + V2;
	if (ty == 1 && ((NN - L) > KK || R > KK + NN || !(L < NN && R >= NN))) return (1LL << 60);
	ret *= 2;
	return min(1LL * LL, ret);
}

int c[10000009];

long long delivery(int N, int K, int L, int pos[]) {
	NN = N; KK = K; LL = L;
	for (int i = 0; i < N; i++) v[i] = pos[i];

	for (int i = 0; i < N; i++) c[i] = dist(i, i + K - 1, 0);

	long long minx = (1LL << 60);

	for (int i = 0; i < N; i++) {
		if (used[i] == true) continue;

		long long cx = i, sum = 0;
		while (cx + K < i + N) { sum += c[cx % N]; cx += K; }

		long long ex = i;
		while (used[ex % N] == false) {
			used[ex % N] = true;
			minx = min(minx, sum + dist(cx, ex + N - 1, 0));
			//cout << ex << " " << sum + dist(cx, ex + N - 1, 0) << endl;
			sum -= c[ex % N]; ex += K; sum += c[cx%N]; cx += K;
		}
	}
	if (K * 2 < N) {
		for (int i = 0; i < N; i++) used[i] = false;
		for (int i = 0; i < N; i++) {
			if (used[i] == true) continue;

			long long cx = i, sum = 0;
			while (cx + K * 2 < i + N) { sum += c[cx % N]; cx += K; }

			long long ex = i;
			while (used[ex % N] == false) {
				used[ex % N] = true;
				minx = min(minx, sum + dist(cx, ex + N - 1, 1));
				//cout << ex % N << " " << cx % N << " " << sum + dist(cx, ex + N - 1, 1) << endl;
				sum -= c[ex % N]; ex += K; sum += c[cx%N]; cx += K;
			}
		}
	}
	return minx;
}

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

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:25:41: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  for (int i = 0; i < N; i++) c[i] = dist(i, i + K - 1, 0);
                                     ~~~~^~~~~~~~~~~~~~~~~
boxes.cpp:38:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    minx = min(minx, sum + dist(cx, ex + N - 1, 0));
                                                 ^
boxes.cpp:38:43: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    minx = min(minx, sum + dist(cx, ex + N - 1, 0));
                                    ~~~~~~~^~~
boxes.cpp:54:50: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     minx = min(minx, sum + dist(cx, ex + N - 1, 1));
                                                  ^
boxes.cpp:54:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     minx = min(minx, sum + dist(cx, ex + N - 1, 1));
                                     ~~~~~~~^~~

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