oj.uz

Submission #639654

# Submission time Handle Problem Language Result Execution time Memory
639654 2022-09-10T19:23:35 Z luanaamorim K blocks (IZhO14_blocks) C++14
0 / 100
 15 ms 32212 KB 
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#define MAX (int) 2e3
#define ll long long
#define INF (ll) 1e9
#define dbug(x) cout << #x << ' ' << x << endl

using namespace std;

ll n, m, arr[MAX], memo[MAX][MAX], maior[MAX][MAX], l, r, resp;
pair<ll, ll> dp[MAX][101];

ll f(int i, int k)
{
	if (k < 0) return INF;
	if (i > n) return (k?INF:0);
	if (~memo[i][k]) return memo[i][k];
	ll resp = INF;
	for (int j = i; j <= n; j++)
		resp = min(resp, f(j+1, k-1) + maior[i][j]);
 
	return memo[i][k] = resp;
}

void dct(int i, int j, int l, int r, int k)
{
	if (i > j) return;
	int mid = (i+j)>>1;
	dp[mid][k] = {INF, r+1};
	for (int idx = mid; idx <= r; idx++)
		dp[mid][k] = min(dp[mid][k], {dp[idx+1][k-1].first + maior[mid][idx], -idx});

	int optmid = -dp[mid][k].second;
	dct(i, mid-1, optmid, r, k);
	dct(mid+1, j, l, optmid, k); 
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		// arr[i]%=1000000;
		// cout << arr[i] << ' ';
	}
	// cout << endl;

	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			maior[i][j] = max(arr[j], maior[i][j-1]);
 
 	for (int i = 0; i <= n+1; i++)
		for (int j = 0; j <= m; j++)
			dp[i][j] = {INF, -1};
 
 	dp[n+1][0] = {0, 0};
	// for (int i = n; i >= 1; i--)
	// {
	// 	for (int k = 1; k <= m; k++)
	// 	{
	// 		dp[i][k] = {INF, i};
	// 		for (int j = n; j >= i; j--)
	// 			dp[i][k] = min(dp[i][k], {dp[j+1][k-1].first + maior[i][j], j});
	// 	}
	// }

 	memset(memo, -1, sizeof memo);
 	// f(1, m);
	for (int i = 1; i <= m; i++)
	{
		dct(1, n, 1, n, i);
		if (dp[1][i].first != f(1, i)) cout <<i << endl;
		// for (int j = 1; j <= n; j++)
		// {
		// 	if (memo[j][i] == -1) memo[j][i] = INF;
		// 	if (memo[j][i] != dp[j][i].first)
		// 	{
		// 		dbug(dp[j][i].first);
		// 		// dbug(i);
		// 	}
		// }
		// cout << endl;
	}

	cout << dp[1][m].first  << endl;


}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 12 ms 31572 KB Output is correct
4 Correct 12 ms 31560 KB Output is correct
5 Correct 12 ms 31512 KB Output is correct
6 Correct 12 ms 31572 KB Output is correct
7 Correct 13 ms 31620 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 13 ms 31572 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 13 ms 31696 KB Output is correct
12 Correct 13 ms 32212 KB Output is correct
13 Incorrect 13 ms 32212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31560 KB Output is correct
2 Correct 13 ms 31536 KB Output is correct
3 Correct 13 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 12 ms 31572 KB Output is correct
6 Correct 13 ms 31572 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 13 ms 31616 KB Output is correct
10 Correct 12 ms 31576 KB Output is correct
11 Correct 12 ms 31652 KB Output is correct
12 Correct 13 ms 31572 KB Output is correct
13 Incorrect 15 ms 31572 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 12 ms 31572 KB Output is correct
4 Correct 12 ms 31560 KB Output is correct
5 Correct 12 ms 31512 KB Output is correct
6 Correct 12 ms 31572 KB Output is correct
7 Correct 13 ms 31620 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 13 ms 31572 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 13 ms 31696 KB Output is correct
12 Correct 13 ms 32212 KB Output is correct
13 Incorrect 13 ms 32212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 12 ms 31572 KB Output is correct
4 Correct 12 ms 31560 KB Output is correct
5 Correct 12 ms 31512 KB Output is correct
6 Correct 12 ms 31572 KB Output is correct
7 Correct 13 ms 31620 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 13 ms 31572 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 13 ms 31696 KB Output is correct
12 Correct 13 ms 32212 KB Output is correct
13 Incorrect 13 ms 32212 KB Output isn't correct
14 Halted 0 ms 0 KB -