oj.uz

Submission #936170

# Submission time Handle Problem Language Result Execution time Memory
936170 2024-03-01T09:57:01 Z shoryu386 The short shank; Redemption (BOI21_prison) C++17
15 / 100
 2000 ms 251984 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int n, d, t;
#define MAX 4007
 
int arr[MAX], dp[MAX][MAX];
 
int memo[MAX][MAX];
void costPrecomp(int l){;
	int ans = 0;
 
	if (arr[l] <= t) memo[l][l] = 1, ans = 1;
	else memo[l][l] = 0, ans = 0;
	
	int carry = arr[l] + 1;
	for (int x = l+1; x < n; x++){
		int val = min(arr[x], carry);
		if (val <= t) ans++;
		
		carry = min(carry, arr[x]);
		carry += 1;
		
		memo[l][x] = ans;
	}
}
 
inline int cost(int l, int r){ return memo[l][r];}
 
main(){
	cin >> n >> d >> t;
	for (int x = 0; x < n; x++) cin >> arr[x];
	for (int x = 0; x < n; x++) costPrecomp(x);
	
	memset(dp, 63, sizeof(dp));
	for (int x = 0; x < n; x++){
		dp[x][1] = min(dp[x][1], cost(0, x));
	
		vector<int> test;
	
		for (int z = 1; z <= n; z++){
			
			int bestLoc = -1;
			for (int y = 0; y < x; y++){
				if (dp[y][z-1] + cost(y+1, x) < dp[x][z]) dp[x][z] = dp[y][z-1] + cost(y+1, x), bestLoc = y;
			}
			
			if (bestLoc != -1) test.push_back(bestLoc);
			
		}
		
		//for (auto z : test) cout << z << ' ';
		//cout << '\n';
		
		vector<int> check = test; sort(check.begin(), check.end());
		assert(check == test);
	}
	
	cout << dp[n-1][d+1];
}

Compilation message

prison.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Correct 65 ms 140892 KB Output is correct
3 Correct 65 ms 140888 KB Output is correct
4 Correct 105 ms 142940 KB Output is correct
5 Correct 107 ms 142936 KB Output is correct
6 Correct 101 ms 142940 KB Output is correct
7 Correct 104 ms 142940 KB Output is correct
8 Correct 104 ms 142932 KB Output is correct
9 Correct 103 ms 142940 KB Output is correct
10 Correct 102 ms 142936 KB Output is correct
11 Correct 106 ms 142936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Runtime error 6 ms 532 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Correct 65 ms 140892 KB Output is correct
3 Correct 65 ms 140888 KB Output is correct
4 Correct 105 ms 142940 KB Output is correct
5 Correct 107 ms 142936 KB Output is correct
6 Correct 101 ms 142940 KB Output is correct
7 Correct 104 ms 142940 KB Output is correct
8 Correct 104 ms 142932 KB Output is correct
9 Correct 103 ms 142940 KB Output is correct
10 Correct 102 ms 142936 KB Output is correct
11 Correct 106 ms 142936 KB Output is correct
12 Correct 16 ms 126552 KB Output is correct
13 Correct 64 ms 141144 KB Output is correct
14 Correct 64 ms 140888 KB Output is correct
15 Correct 103 ms 142940 KB Output is correct
16 Correct 102 ms 142940 KB Output is correct
17 Correct 102 ms 142936 KB Output is correct
18 Correct 111 ms 142936 KB Output is correct
19 Correct 102 ms 142940 KB Output is correct
20 Correct 101 ms 142936 KB Output is correct
21 Correct 103 ms 142932 KB Output is correct
22 Correct 110 ms 142940 KB Output is correct
23 Execution timed out 2028 ms 251984 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Runtime error 7 ms 536 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Correct 65 ms 140892 KB Output is correct
3 Correct 65 ms 140888 KB Output is correct
4 Correct 105 ms 142940 KB Output is correct
5 Correct 107 ms 142936 KB Output is correct
6 Correct 101 ms 142940 KB Output is correct
7 Correct 104 ms 142940 KB Output is correct
8 Correct 104 ms 142932 KB Output is correct
9 Correct 103 ms 142940 KB Output is correct
10 Correct 102 ms 142936 KB Output is correct
11 Correct 106 ms 142936 KB Output is correct
12 Correct 16 ms 126552 KB Output is correct
13 Correct 64 ms 141144 KB Output is correct
14 Correct 64 ms 140888 KB Output is correct
15 Correct 103 ms 142940 KB Output is correct
16 Correct 102 ms 142940 KB Output is correct
17 Correct 102 ms 142936 KB Output is correct
18 Correct 111 ms 142936 KB Output is correct
19 Correct 102 ms 142940 KB Output is correct
20 Correct 101 ms 142936 KB Output is correct
21 Correct 103 ms 142932 KB Output is correct
22 Correct 110 ms 142940 KB Output is correct
23 Execution timed out 2028 ms 251984 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Correct 65 ms 140892 KB Output is correct
3 Correct 65 ms 140888 KB Output is correct
4 Correct 105 ms 142940 KB Output is correct
5 Correct 107 ms 142936 KB Output is correct
6 Correct 101 ms 142940 KB Output is correct
7 Correct 104 ms 142940 KB Output is correct
8 Correct 104 ms 142932 KB Output is correct
9 Correct 103 ms 142940 KB Output is correct
10 Correct 102 ms 142936 KB Output is correct
11 Correct 106 ms 142936 KB Output is correct
12 Correct 17 ms 126300 KB Output is correct
13 Runtime error 6 ms 532 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -