Submission #516

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

delete

/* Subtask 1 - 5를 해결하는 코드 */

#include <vector>
#include <malloc.h>
#include <algorithm>

using namespace std;

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

const int N_ = 5005;
const int INF = 987654321;

int Table[3005][10005];
vector< vector<int> > Gph;

struct Intv {
    int l, r, ln, rn;
    Intv(): l(0), r(0), ln(0), rn(0) { }
	Intv(int l, int r): l(l), r(r), ln(0), rn(0) { }
	bool operator< (const Intv &t) const {
		if(l == INF) return false;
		if(t.l == INF) return true;
		return r != t.r ? r < t.r : l > t.l;
	}
} *D;

int file;
void Renumber( int node ){
	int i;
	if(node >= M){ // leaf node
		D[node].l = D[node].r = ++file;
	}else{
        D[node].l = INF;
        D[node].r = -INF;
		for(int i = 0; i < Gph[node].size(); i++){
			int g = Gph[node][i];
			Renumber(g);
            D[node].l = min(D[node].l, D[g].l);
            D[node].r = max(D[node].r, D[g].r);
		}
	}
}

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;
	sttic::F = N + M;

	Gph.resize(M);
	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 );

	D = (Intv*) calloc( F, sizeof(Intv) );
	Renumber (0);
	sort(D, D + M);
	while(D[M - 1].l == INF && M > 0) --M;

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

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

	for(i = 0; i < M; i++){
		D[i].ln = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].l - 1) );
		D[i].rn = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].r ) );
		//printf("%3d : [%3d, %3d] [%3d, %3d]\n", i, D[i].l - 1, D[i].r, D[i].ln, D[i].rn );
	}

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

	for(j = 1; j <= D[0].r; j++) Table[0][j] = j;
	for(i = 0; i < M; i++){
		Intv &d = D[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.rn][j];
			t = min(t, Table[d.rn - 1][j]);
			if(j >= len) t = min(t, Table[d.ln][j - len] + 1);
		}
		if(i + 1 < M && d.rn != D[i + 1].rn){
			for(j = d.r + 1; j <= D[i + 1].r && j <= K; j++) 
				Table[d.rn][j] = min(Table[d.rn][j], Table[d.rn][j - 1] + 1);
		}
	}
	
	for(i = 0; i <= K; i++){
		int val = Table[D[M - 1].rn][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