Submission #798

#	Time	Username	Problem	Language	Result	Execution time	Memory
798		tncks0121	파일 삭제 (GA3_delete)	C++98	120 / 120	115 ms	118756 KiB

delete

#include <vector>
#include <algorithm>

using namespace std;
const int N_ = 10005, M_ = 3005;
const int INF = 987654321;

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

struct Intv {
	int l, r, lp, rp;
	Intv(): l(0), r(0), lp(-1), rp(-1) { }
	Intv(int l, int r): l(l), r(r), lp(-1), rp(-1) { }
	Intv(int l, int lp, int r, int rp): l(l), r(r), lp(lp), rp(rp) { }
};

using namespace sttic;

vector<int> Gph[M_];
vector<Intv> I;
int Table[M_][N_];

int file;

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

int DeletePlan( int N, int M, int K, int *A, int *B) {
	int i, j, ret = K;
	sttic::N = N; sttic::M = M; sttic::K = K;
	
	for(i = 1; i < M; i++) Gph[ B[i] ].push_back(i);
	for(i = 0; i < N; i++) Gph[ A[i] ].push_back(i + M);

	getInterval(0);

	vector<int> X;
	X.push_back(0);
	for(i = 0; i < I.size(); i++) X.push_back( I[i].r );

	sort( X.begin(), X.end() );
	X.resize( distance( X.begin(), unique( X.begin(), X.end() ) ) );

	for(i = 0; i < I.size(); i++){
		I[i].lp = lower_bound( X.begin(), X.end(), I[i].l - 1) - X.begin();
		I[i].rp = lower_bound( X.begin(), X.end(), I[i].r )    - X.begin();
	}

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

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

	return ret;
}

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