| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 797 |
2013-03-02T17:14:08 Z |
tncks0121 |
파일 삭제 (GA3_delete) |
C++ |
|
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];
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
