oj.uz

답안 #797

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

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

Subtask #2
25.0 / 25.0

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

Subtask #3
35.0 / 35.0

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

Subtask #4
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 36544 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -