oj.uz

답안 #991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991 2013-06-06T22:39:56 Z tncks0121 파일 삭제 (GA3_delete) C++
40 / 120
 9 ms 5048 KB 
#include <vector> 
#include <algorithm> 
  
using namespace std; 
const int SZ = 1005; 
const int INF = 987654321; 
  
vector<int> Gph[SZ]; 
vector<int> Que; 
int Table[SZ][SZ], Tmp[SZ]; 
int Parent[SZ], Size[SZ]; 
  
int DeletePlan( int N, int M, int K, int *A, int *B) { 
    int i, j, 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); 
      
    int fr = 0; Que.push_back(0); 
    while(fr < Que.size()){ 
        int n = Que[fr++]; 
        for(i = 0; i < Gph[n].size(); i++) { 
            int g = Gph[n][i]; 
            Que.push_back(g); Parent[g] = n; 
        } 
    } 
  
    for(i = 0; i < N + M; i++) { 
        Table[i][1] = 1; if(i >= M) Size[i] = 1; 
        for(j = 2; j <= N; j++) Table[i][j] = INF; 
    } 
  
    for(i = (int)Que.size() - 1; i > 0; i--){ 
        int n = Que[i], p = Parent[n]; 
        Size[p] += Size[n]; Table[n][Size[n]] = 1; 
        for(j = 1; j <= Size[p]; j++) Tmp[j] = Table[p][j]; 
        for(j = 1; j <= Size[p]; j++){ 
            for(k = j; k <= Size[p]; k++) Table[p][k] = min(Table[p][k], Tmp[k - j] + Table[n][j]); 
        } 
    } 
  
    int ret = INF; 
    for(i = 0; i < N + M; i++) ret = min(ret, Table[i][K]); 
  
    return ret; 
}

Subtask #1
15.0 / 15.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4916 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 -

Subtask #4
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 5048 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 -