oj.uz

답안 #536675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536675 2022-03-13T19:13:07 Z blue K개의 묶음 (IZhO14_blocks) C++17
0 / 100
 1 ms 324 KB 
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000LL;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	vll A(1+N, INF);
	for(int i = 1; i <= N; i++) cin >> A[i];

	ll* DP[1+K];
	DP[0] = new ll[1+N];
	DP[1] = new ll[1+N];
	for(int k = 2; k <= K; k++)
	{
		DP[k] = DP[k-2];
	}

	for(int i = 1; i <= N; i++)
	{
		DP[0][i] = DP[1][i] = +INF;
	}

	DP[0][0] = 0;

	for(int k = 1; k <= K; k++)
	{
		// cerr << "\n\n\n\n\n k = " << k << '\n';
		vector<int> mxp;
		vector<ll> mndp;

		// DP[k][0] = 0;
		DP[k][0] = INF;

		for(int i = 1; i <= N; i++)
		{
			// cerr << "\n\n\n";
			// cerr << "i = " << i << '\n';
			// cerr << "push value " << k-1 << ' ' << i-1 << " : " << DP[k-1][i-1] << '\n';

			mxp.push_back(i-1);

			if(mndp.empty())
				mndp.push_back(DP[k-1][max(i-1, k-1)] + A[i]);
			else
				mndp.push_back(min(mndp.back(), DP[k-1][max(i-1, k-1)] + A[i]));

			// cerr << "push P " << mndp.back() << '\n';

			while(A[mxp.back()] <= A[i])
			{

				// cerr << "pop A " << mndp.back() << '\n';


				mxp.pop_back();
				mndp.pop_back();
			}

			// cerr << "pop B " << mndp.back() << '\n';

			mndp.pop_back();

			if(mndp.empty())
				mndp.push_back(DP[k-1][max(mxp.back(), k-1)] + A[i]);
			else
				mndp.push_back(min(mndp.back(), DP[k-1][max(mxp.back(), k-1)] + A[i]));

			// cerr << "push Q " << mndp.back() << '\n';

			DP[k][i] = mndp.back();

			// cerr << k << ' ' << i << " : " << DP[k][i] << '\n';
		}
	}

	cout << DP[K][N] << '\n';
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -