oj.uz

답안 #798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798 2013-03-02T18:02:30 Z tncks0121 파일 삭제 (GA3_delete) C++
120 / 120
 115 ms 118756 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 118456 KB Output is correct
2 Correct 0 ms 118456 KB Output is correct
3 Correct 0 ms 118456 KB Output is correct
4 Correct 0 ms 118456 KB Output is correct
5 Correct 0 ms 118456 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 118456 KB Output is correct
2 Correct 0 ms 118456 KB Output is correct
3 Correct 0 ms 118456 KB Output is correct
4 Correct 0 ms 118456 KB Output is correct
5 Correct 0 ms 118456 KB Output is correct
6 Correct 0 ms 118456 KB Output is correct
7 Correct 0 ms 118456 KB Output is correct
8 Correct 0 ms 118456 KB Output is correct
9 Correct 0 ms 118456 KB Output is correct
10 Correct 0 ms 118456 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 118456 KB Output is correct
2 Correct 0 ms 118456 KB Output is correct
3 Correct 4 ms 118456 KB Output is correct
4 Correct 2 ms 118456 KB Output is correct
5 Correct 1 ms 118456 KB Output is correct
6 Correct 1 ms 118456 KB Output is correct
7 Correct 0 ms 118456 KB Output is correct
8 Correct 0 ms 118456 KB Output is correct
9 Correct 0 ms 118456 KB Output is correct
10 Correct 0 ms 118456 KB Output is correct
11 Correct 1 ms 118456 KB Output is correct
12 Correct 2 ms 118456 KB Output is correct
13 Correct 2 ms 118456 KB Output is correct
14 Correct 7 ms 118456 KB Output is correct
15 Correct 4 ms 118456 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 118456 KB Output is correct
2 Correct 27 ms 118588 KB Output is correct
3 Correct 13 ms 118588 KB Output is correct
4 Correct 36 ms 118588 KB Output is correct
5 Correct 20 ms 118592 KB Output is correct
6 Correct 3 ms 118592 KB Output is correct
7 Correct 7 ms 118456 KB Output is correct
8 Correct 7 ms 118588 KB Output is correct
9 Correct 30 ms 118588 KB Output is correct
10 Correct 13 ms 118456 KB Output is correct
11 Correct 58 ms 118744 KB Output is correct
12 Correct 87 ms 118752 KB Output is correct
13 Correct 72 ms 118748 KB Output is correct
14 Correct 115 ms 118756 KB Output is correct
15 Correct 88 ms 118740 KB Output is correct