oj.uz

Submission #4667

# Submission time Handle Problem Language Result Execution time Memory
4667 2013-12-02T14:55:57 Z tncks0121 파일 삭제 (GA3_delete) C++
75 / 120
 124 ms 36752 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<int> I[SZ]; 
int Table[SZ][SZ]; 
  
int file; 
  
void getInterval (int node){ 
    int i; 
    if(node >= M) { 
        ++file; 
        I[file].push_back(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[file].push_back(st);
    } 
} 
  
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); 
        } 
    }*/

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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36624 KB Output is correct
2 Correct 0 ms 36624 KB Output is correct
3 Correct 0 ms 36624 KB Output is correct
4 Correct 0 ms 36624 KB Output is correct
5 Correct 0 ms 36624 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36624 KB Output is correct
2 Correct 0 ms 36624 KB Output is correct
3 Correct 0 ms 36624 KB Output is correct
4 Correct 0 ms 36624 KB Output is correct
5 Correct 0 ms 36624 KB Output is correct
6 Correct 0 ms 36624 KB Output is correct
7 Correct 4 ms 36624 KB Output is correct
8 Correct 0 ms 36624 KB Output is correct
9 Correct 0 ms 36624 KB Output is correct
10 Correct 4 ms 36624 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36624 KB Output is correct
2 Correct 32 ms 36624 KB Output is correct
3 Correct 84 ms 36624 KB Output is correct
4 Correct 20 ms 36624 KB Output is correct
5 Correct 68 ms 36624 KB Output is correct
6 Correct 0 ms 36624 KB Output is correct
7 Correct 96 ms 36624 KB Output is correct
8 Correct 32 ms 36624 KB Output is correct
9 Correct 72 ms 36624 KB Output is correct
10 Correct 76 ms 36624 KB Output is correct
11 Correct 56 ms 36624 KB Output is correct
12 Correct 64 ms 36624 KB Output is correct
13 Correct 84 ms 36624 KB Output is correct
14 Correct 120 ms 36624 KB Output is correct
15 Correct 124 ms 36624 KB Output is correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 36752 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -