oj.uz

Submission #517025

# Submission time Handle Problem Language Result Execution time Memory
517025 2022-01-22T11:32:43 Z pavement Boxes with souvenirs (IOI15_boxes) C++17
0 / 100
 1 ms 296 KB 
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll pref[100005], suff[100005], pp[100005];

ll delivery(int N, int K, int L, int p[]) {
	for (int i = 0; i < N; i++) {
		if (i % K == 0) pref[i] = (i ? (ll)pref[i - 1] : 0ll) + 2ll * p[i];
		else pref[i] = (ll)pref[i - 1] - 2ll * p[i - 1] + 2ll * p[i];
	}
	for (int i = N - 1; i >= 0; i--) {
		if ((N - i - 1) % K == 0) suff[i] = (i + 1 < N ? (ll)suff[i + 1] : 0ll) + 2ll * (L - p[i]);
		else suff[i] = (ll)suff[i + 1] - 2ll * (L - p[i + 1]) + 2ll * (L - p[i]);
	}
	ll ret = pref[N - 1];
	for (int i = 0; i < N; i++) pp[i] = (ll)(i ? pp[i - 1] : 0) + p[i];
	for (int i = N - 1, pt = N; i >= 0; i--) {
		while (i < pt && (pp[pt - 2] - pp[i - 1] + K - 1) / K * N + suff[pt - 1] <= (pp[pt - 1] - pp[i - 1] + K - 1) / K * N + suff[pt]) pt--;
		ret = min(ret, pref[i - 1] + (pp[pt - 1] - pp[i - 1] + K - 1) / K * N + suff[pt]);
	}
	return ret;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -