oj.uz

Submission #936163

# Submission time Handle Problem Language Result Execution time Memory
936163 2024-03-01T09:50:38 Z shoryu386 The short shank; Redemption (BOI21_prison) C++17
0 / 100
 132 ms 285268 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 126316 KB Output is correct
2 Runtime error 132 ms 285268 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 126300 KB Output is correct
2 Runtime error 8 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 31 ms 126316 KB Output is correct
2 Runtime error 132 ms 285268 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 126352 KB Output is correct
2 Runtime error 7 ms 604 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 31 ms 126316 KB Output is correct
2 Runtime error 132 ms 285268 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 126316 KB Output is correct
2 Runtime error 132 ms 285268 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -