Submission #797

#	Time	Username	Problem	Language	Result	Execution time	Memory
797		tncks0121	파일 삭제 (GA3_delete)	C++98	75 / 120	22 ms	36544 KiB

delete

#include <vector>
#include <algorithm>

using namespace std;
const int SZ = 3005;
const int INF = 987654321;

namespace sttic {
	int N, M, K;
};

struct Intv {
	int l, r;
	Intv(): l(0), r(0) { }
	Intv(int l, int r): l(l), r(r) { }
};

using namespace sttic;

vector<int> Gph[SZ];
vector<Intv> I;
int Table[SZ][SZ];

int file;

void getInterval (int node){
	int i;
	if(node >= M) {
		++file;
		I.push_back( Intv(file, file) );
	}else {
		int st = file + 1;
		for(i = 0; i < Gph[node].size(); i++){
			int g = Gph[node][i];
			getInterval(g);
		}
		if(st <= file) I.push_back( Intv(st, file) );
	}
}

int DeletePlan( int N, int M, int K, int *A, int *B) {
	int i, j;
	sttic::N = N; sttic::M = M; sttic::K = K;

	for(i = 0; i < N; i++) Gph[ A[i] ].push_back(i + M);
	for(i = 1; i < M; i++) Gph[ B[i] ].push_back(i);

	getInterval(0);

	for(i = 0; i <= N; i++){
		for(j = 1; j <= K; j++) Table[i][j] = INF;
	}

	for(i = 0; i < I.size(); i++){
		Intv &d = I[i]; int len = d.r - d.l + 1;
		for(j = 1; j <= K && j <= d.r; j++){
			int &t = Table[d.r][j];
			t = min(t, Table[d.r - 1][j]);
			if(j >= len) t = min(t, Table[d.l - 1][j - len] + 1);
		}
	}

	return Table[N][K];
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 45