oj.uz

Submission #4665

# Submission time Handle Problem Language Result Execution time Memory
4665 2013-12-02T14:52:35 Z tncks0121 파일 삭제 (GA3_delete) C++
75 / 120
 120 ms 36820 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); 
        } 
    }*/

	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); 
		}
	}
  
    return Table[N][K]; 
}

Subtask #1
15.0 / 15.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36552 KB Output is correct
2 Correct 36 ms 36552 KB Output is correct
3 Correct 76 ms 36552 KB Output is correct
4 Correct 20 ms 36552 KB Output is correct
5 Correct 56 ms 36552 KB Output is correct
6 Correct 0 ms 36552 KB Output is correct
7 Correct 80 ms 36552 KB Output is correct
8 Correct 28 ms 36552 KB Output is correct
9 Correct 72 ms 36552 KB Output is correct
10 Correct 72 ms 36552 KB Output is correct
11 Correct 56 ms 36552 KB Output is correct
12 Correct 56 ms 36552 KB Output is correct
13 Correct 84 ms 36552 KB Output is correct
14 Correct 120 ms 36552 KB Output is correct
15 Correct 104 ms 36552 KB Output is correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 36820 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -