oj.uz

Submission #977598

# Submission time Handle Problem Language Result Execution time Memory
977598 2024-05-08T07:28:15 Z SmuggingSpun Boxes with souvenirs (IOI15_boxes) C++17
20 / 100
 2 ms 604 KB 
#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++){
				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:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 2 ms 604 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 2 ms 604 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 2 ms 604 KB Output isn't correct
16 Halted 0 ms 0 KB -