oj.uz

Submission #977628

# Submission time Handle Problem Language Result Execution time Memory
977628 2024-05-08T07:51:21 Z SmuggingSpun Boxes with souvenirs (IOI15_boxes) C++14
35 / 100
 861 ms 6556 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 = 0; 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 = 0; j < d.size(); j++){
					for(int t = 0; t <= k; t++){
						minimize(dp[j][t][mask], dp[i][t][mask] + min(abs(d[i] - d[j]), L - abs(d[i] - d[j])));
					}
				}
			}
			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 = 0; 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:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int j = 0; j < d.size(); j++){
      |                    ~~^~~~~~~~~~
boxes.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i = 0; i < d.size(); i++){
      |                   ~~^~~~~~~~~~
boxes.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 5 ms 860 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 860 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 4 ms 604 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Incorrect 861 ms 6556 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 4 ms 604 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Incorrect 861 ms 6556 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 4 ms 604 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Incorrect 861 ms 6556 KB Output isn't correct
25 Halted 0 ms 0 KB -