oj.uz

답안 #639654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639654 2022-09-10T19:23:35 Z luanaamorim K개의 묶음 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -