#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
ll delivery(int n, int k, int L, int p[]){
if(k == 1){
ll ans = 0;
for(int i = 0; i < n; i++){
ans += min(p[i], L - p[i]) << 1;
}
return ans;
}
if(k == n){
ll ans = min(L, min(p[n - 1], L - p[0]) << 1);
for(int i = 0; i + 1 < n; i++){
minimize(ans, ll(p[i] + L - p[i + 1]) << 1LL);
}
return ans;
}
if(n <= 10){
vector<int>d(1, 0);
for(int i = 0; i < n; i++){
if(p[i] != d.back()){
d.emplace_back(p[i]);
}
}
vector<vector<vector<ll>>>dp(d.size(), vector<vector<ll>>(k + 1, vector<ll>(1 << n, INF)));
dp[0][k][(1 << n) - 1] = 0;
for(int mask = (1 << n) - 1; mask > -1; mask--){
for(int i = 1; i < d.size(); i++){
for(int j = 0; j <= k; j++){
minimize(dp[0][k][mask], dp[i][j][mask] + min(d[i], L - d[i]));
}
}
for(int i = 0; i < d.size(); i++){
minimize(dp[i][k][mask], dp[0][k][mask] + min(d[i], L - d[i]));
}
for(int i = 0; i < d.size(); i++){
for(int j = 1; j <= k; j++){
for(int t = 0; t < n; t++){
if(1 << t & mask){
minimize(dp[lower_bound(d.begin(), d.end(), p[t]) - d.begin()][j - 1][mask ^ (1 << t)], dp[i][j][mask] + min(abs(d[i] - p[t]), L - abs(d[i] - p[t])));
}
}
}
}
}
return dp[0][k][0];
}
}
Compilation message
boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 1; i < d.size(); i++){
| ~~^~~~~~~~~~
boxes.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
boxes.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
boxes.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
56 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |