| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 798 |
2013-03-02T18:02:30 Z |
tncks0121 |
파일 삭제 (GA3_delete) |
C++ |
|
115 ms |
118756 KB |
#include <vector>
#include <algorithm>
using namespace std;
const int N_ = 10005, M_ = 3005;
const int INF = 987654321;
namespace sttic {
int N, M, K;
};
struct Intv {
int l, r, lp, rp;
Intv(): l(0), r(0), lp(-1), rp(-1) { }
Intv(int l, int r): l(l), r(r), lp(-1), rp(-1) { }
Intv(int l, int lp, int r, int rp): l(l), r(r), lp(lp), rp(rp) { }
};
using namespace sttic;
vector<int> Gph[M_];
vector<Intv> I;
int Table[M_][N_];
int file;
void getInterval (int node){
int i;
if(node >= M) {
++file;
}else {
int st = file + 1;
for(i = 0; i < Gph[node].size(); i++) getInterval(Gph[node][i]);
if(st <= file) I.push_back( Intv(st, file) );
}
}
int DeletePlan( int N, int M, int K, int *A, int *B) {
int i, j, ret = K;
sttic::N = N; sttic::M = M; sttic::K = K;
for(i = 1; i < M; i++) Gph[ B[i] ].push_back(i);
for(i = 0; i < N; i++) Gph[ A[i] ].push_back(i + M);
getInterval(0);
vector<int> X;
X.push_back(0);
for(i = 0; i < I.size(); i++) X.push_back( I[i].r );
sort( X.begin(), X.end() );
X.resize( distance( X.begin(), unique( X.begin(), X.end() ) ) );
for(i = 0; i < I.size(); i++){
I[i].lp = lower_bound( X.begin(), X.end(), I[i].l - 1) - X.begin();
I[i].rp = lower_bound( X.begin(), X.end(), I[i].r ) - X.begin();
}
for(i = 0; i < X.size(); i++){
for(j = 1; j <= K; j++) Table[i][j] = INF;
}
for(j = 1; j <= I[0].r; j++) Table[0][j] = j;
for(i = 0; i < I.size(); i++){
Intv &d = I[i]; int len = d.r - d.l + 1;
if(d.l == INF) continue;
for(j = 1; j <= K && j <= d.r; j++){
int &t = Table[d.rp][j];
t = min(t, Table[d.rp - 1][j]);
if(j >= len) t = min(t, Table[d.lp][j - len] + 1);
}
if(i + 1 < I.size() && d.rp != I[i + 1].rp){
for(j = d.r + 1; j <= I[i + 1].r && j <= K; j++)
Table[d.rp][j] = min(Table[d.rp][j], Table[d.rp][j - 1] + 1);
}
}
for(i = 0; i <= K; i++){
int val = Table[I.back().rp][i] + (K - i);
if(val < ret) ret = val;
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 3 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 4 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 3 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 4 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 6 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 7 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 8 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 9 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 10 |
Correct |
0 ms |
118456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
118456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
118456 KB |
Output is correct |
| 5 |
Correct |
1 ms |
118456 KB |
Output is correct |
| 6 |
Correct |
1 ms |
118456 KB |
Output is correct |
| 7 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 8 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 9 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 10 |
Correct |
0 ms |
118456 KB |
Output is correct |
| 11 |
Correct |
1 ms |
118456 KB |
Output is correct |
| 12 |
Correct |
2 ms |
118456 KB |
Output is correct |
| 13 |
Correct |
2 ms |
118456 KB |
Output is correct |
| 14 |
Correct |
7 ms |
118456 KB |
Output is correct |
| 15 |
Correct |
4 ms |
118456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
118456 KB |
Output is correct |
| 2 |
Correct |
27 ms |
118588 KB |
Output is correct |
| 3 |
Correct |
13 ms |
118588 KB |
Output is correct |
| 4 |
Correct |
36 ms |
118588 KB |
Output is correct |
| 5 |
Correct |
20 ms |
118592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
118592 KB |
Output is correct |
| 7 |
Correct |
7 ms |
118456 KB |
Output is correct |
| 8 |
Correct |
7 ms |
118588 KB |
Output is correct |
| 9 |
Correct |
30 ms |
118588 KB |
Output is correct |
| 10 |
Correct |
13 ms |
118456 KB |
Output is correct |
| 11 |
Correct |
58 ms |
118744 KB |
Output is correct |
| 12 |
Correct |
87 ms |
118752 KB |
Output is correct |
| 13 |
Correct |
72 ms |
118748 KB |
Output is correct |
| 14 |
Correct |
115 ms |
118756 KB |
Output is correct |
| 15 |
Correct |
88 ms |
118740 KB |
Output is correct |
