Submission #4667

#	Time	Username	Problem	Language	Result	Execution time	Memory
4667		tncks0121	파일 삭제 (GA3_delete)	C++98	75 / 120	124 ms	36752 KiB

delete

#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 / 15
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 45