제출 #437552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437552		Sohsoh84	Painting Walls (APIO20_paint)	C++14	63 / 100	1548 ms	39108 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 2e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

int n, m, k, C[MAXN];
vector<int> L[MAXN];
unordered_map<int, int> W[2]; 
ll dp[MAXN];

int minimumInstructions(
	int N, int M, int K, std::vector<int> tC,
	std::vector<int> tA, std::vector<std::vector<int>> tB) {
	
	n = N, m = M, k = K;
	for (int i = 0; i < n; i++) C[i] = tC[i];
	for (int i = 0; i < m; i++)
		for (int e : tB[i])
		       L[e].push_back(i);	
	
	set<pll> dp_st;
	dp_st.insert({0, n});

	for (int i = n - 1; i >= 0; i--) {
		int ind = i & 1;
		W[ind].clear();
		dp[i] = INF;
					
		dp_st.erase({dp[i + m + 1], i + m + 1});
		ll t = dp_st.begin() -> X;

		for (int p : L[C[i]]) {
			int l = W[ind][p] = W[1 - ind][(p + 1) % m] + 1;
			if (l >= m) dp[i] = t + 1;
		}
		
		dp_st.insert({dp[i], i});
	}

	if (dp[0] >= INF) return -1;
	return dp[0];
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37