oj.uz

답안 #871453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871453 2023-11-10T20:40:58 Z Cyber_Wolf The short shank; Redemption (BOI21_prison) C++17
35 / 100
 824 ms 75424 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 5e3+5;

lg n, d, tim;
lg dp[2][N];
lg t[N], lst[N];
vector<lg> o[N];

lg C(lg i, lg j)
{
	lg ans = o[j].size()-(lower_bound(o[j].begin(), o[j].end(), i)-o[j].begin());
	return ans;
}

void compute(lg lev, lg l, lg r, lg optl, lg optr)
{
	if(l > r)	return;
	lg mid = (l+r)/2;
	array<lg, 2> best = {1000000000000, optl};
	for(int i = optl; i <= min(optr, mid-1); i++)
	{
		best = min(best, {dp[(lev+1)&1][i]+C(i+1, mid), i});
	}
	dp[lev&1][mid] = best[0];
	compute(lev, l, mid-1, optl, best[1]);
	compute(lev, mid+1, r, best[1], optr);
	return;
}

int main()
{
	fastio;
	cin >> n >> d >> tim;
	for(int i = 1; i <= n; i++)	
	{
		cin >> t[i];
	}
	for(int i = 1; i <= n; i++)
	{ 
		for(int j = i; j >= 1; j--)
		{
			if(t[j]+i-j <= tim)
			{
				lst[i] = j;
				break;
			}
		}
		o[i].push_back(lst[i]);
		for(auto it : o[i-1])	o[i].push_back(it);
		sort(o[i].begin(), o[i].end());
	}
	d = min(n, d);
	t[0] = 1e18;
	memset(dp, 0x3f, sizeof(dp));
	dp[d&1][0] = 0;
	for(int i = 1; i <= n; i++)	dp[d&1][i] = C(1, i);
	// for(int i = 1; i <= n; i++)
	// {
		// for(int j = 0; j < d; j++)
		// {
			// for(int k = i-1; k >= 0; k--)
			// {
				// dp[i][j] = min(dp[k][j+1]+C(k+1, i), dp[i][j]);
			// }
		// }
	// }
	for(int i = d-1; i >= 0; i--)
	{
		for(int j = 1; j <= n; j++)	dp[i&1][j] = 1e15;
		compute(i, 1, n, 1, n);
	}
	// for(int i = 1; i <= n; i++)
	// {
		// for(int j = 0; j <= d; j++)
		// {
			// cout << dp[j][i] << ' ';
		// }
		// cout << '\n';
	// }
	cout << dp[0][n] << '\n';
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 9 ms 1880 KB Output is correct
5 Correct 13 ms 1884 KB Output is correct
6 Correct 3 ms 1820 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 11 ms 1884 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 2 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 9 ms 1880 KB Output is correct
5 Correct 13 ms 1884 KB Output is correct
6 Correct 3 ms 1820 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 11 ms 1884 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 4 ms 1884 KB Output is correct
14 Correct 4 ms 1628 KB Output is correct
15 Correct 9 ms 1884 KB Output is correct
16 Correct 13 ms 1884 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 7 ms 1884 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 5 ms 2000 KB Output is correct
21 Correct 7 ms 1884 KB Output is correct
22 Correct 11 ms 1884 KB Output is correct
23 Correct 307 ms 75212 KB Output is correct
24 Correct 449 ms 75020 KB Output is correct
25 Correct 565 ms 75020 KB Output is correct
26 Correct 735 ms 75092 KB Output is correct
27 Correct 824 ms 75012 KB Output is correct
28 Correct 233 ms 74824 KB Output is correct
29 Correct 251 ms 75424 KB Output is correct
30 Correct 277 ms 75012 KB Output is correct
31 Correct 435 ms 75088 KB Output is correct
32 Correct 373 ms 74836 KB Output is correct
33 Correct 378 ms 75084 KB Output is correct
34 Correct 198 ms 74828 KB Output is correct
35 Correct 791 ms 75076 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Runtime error 2 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 9 ms 1880 KB Output is correct
5 Correct 13 ms 1884 KB Output is correct
6 Correct 3 ms 1820 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 11 ms 1884 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 4 ms 1884 KB Output is correct
14 Correct 4 ms 1628 KB Output is correct
15 Correct 9 ms 1884 KB Output is correct
16 Correct 13 ms 1884 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 7 ms 1884 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 5 ms 2000 KB Output is correct
21 Correct 7 ms 1884 KB Output is correct
22 Correct 11 ms 1884 KB Output is correct
23 Correct 307 ms 75212 KB Output is correct
24 Correct 449 ms 75020 KB Output is correct
25 Correct 565 ms 75020 KB Output is correct
26 Correct 735 ms 75092 KB Output is correct
27 Correct 824 ms 75012 KB Output is correct
28 Correct 233 ms 74824 KB Output is correct
29 Correct 251 ms 75424 KB Output is correct
30 Correct 277 ms 75012 KB Output is correct
31 Correct 435 ms 75088 KB Output is correct
32 Correct 373 ms 74836 KB Output is correct
33 Correct 378 ms 75084 KB Output is correct
34 Correct 198 ms 74828 KB Output is correct
35 Correct 791 ms 75076 KB Output is correct
36 Correct 0 ms 604 KB Output is correct
37 Runtime error 2 ms 860 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 9 ms 1880 KB Output is correct
5 Correct 13 ms 1884 KB Output is correct
6 Correct 3 ms 1820 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 11 ms 1884 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Runtime error 2 ms 860 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -