oj.uz

Submission #49310

# Submission time Handle Problem Language Result Execution time Memory
49310 2018-05-25T14:50:21 Z IvanC Dostavljač (COCI18_dostavljac) C++17
140 / 140
 278 ms 3004 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510;
const int MAXL = 11;

int dp[MAXN][MAXN],tab[MAXN][MAXN],divide[MAXL][MAXN],filhos[MAXN],A[MAXN],N,M,temporario[MAXN];
vector<int> grafo[MAXN];

void adiciona(int vetor[],int antigo[],int peso,int vale){
	for(int i = M;i>=peso;i--){
		vetor[i] = max(vetor[i],antigo[i-peso] + vale);
	}
}

void adiciona_puro(int vetor[],int peso,int vale){
	for(int i = M;i>=peso;i--){
		vetor[i] = max(vetor[i],vetor[i-peso] + vale);
	}
}

void otimiza(int vetor[]){
	for(int i = 1;i<=M;i++) vetor[i] = max(vetor[i],vetor[i-1]);
}

void copia(int vetor1[],int vetor2[]){
	for(int i = 0;i<=M;i++) vetor2[i] = vetor1[i];
}

void maximiza(int vetor1[],int vetor2[]){
	for(int i = 0;i<=M;i++) vetor1[i] = max(vetor1[i],vetor2[i]);
}

void solve(int pai,int l,int r,int depth){
	if(l == r){
		int u = filhos[l];
		copia(divide[depth],divide[depth+1]);
		copia(divide[depth+1],temporario);
		for(int pega = 1;pega+1<=M;pega++){
			int valor = tab[u][pega];
			adiciona(temporario,divide[depth+1],pega+1,valor);
		}
		copia(temporario,divide[depth+1]);
		maximiza(tab[pai],divide[depth+1]);
		return;
	}
	int m = (l+r)/2;
	copia(divide[depth],divide[depth+1]);
	for(int i = l;i<=m;i++){
		int u = filhos[i];
		copia(divide[depth+1],temporario);
		for(int pega = 1;pega+2<=M;pega++){
			int valor = dp[u][pega];
			adiciona(temporario,divide[depth+1],pega+2,valor);
		}
		copia(temporario,divide[depth+1]);
	}
	solve(pai,m+1,r,depth+1);
	copia(divide[depth],divide[depth+1]);
	for(int i = m+1;i<=r;i++){
		int u = filhos[i];
		copia(divide[depth+1],temporario);
		for(int pega = 1;pega+2<=M;pega++){
			int valor = dp[u][pega];
			adiciona(temporario,divide[depth+1],pega+2,valor);
		}
		copia(temporario,divide[depth+1]);
	}
	solve(pai,l,m,depth+1);
	copia(divide[0],divide[depth]);
}

void dfs1(int v,int p){
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs1(u,v);
		copia(dp[v],temporario);
		for(int pega = 1;pega+2<=M;pega++){
			int valor = dp[u][pega];
			adiciona(temporario,dp[v],pega+2,valor);
		}
		copia(temporario,dp[v]);
	}
	adiciona_puro(dp[v],1,A[v]);
	otimiza(dp[v]);
}

void dfs2(int v,int p){
	int qtd = 0;
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs2(u,v);
	}
	for(int u : grafo[v]){
		if(u == p) continue;
		filhos[++qtd] = u;
	}
	if(qtd != 0) solve(v,1,qtd,0);
	adiciona_puro(tab[v],1,A[v]);
	otimiza(tab[v]);
	for(int i = 1;i<=qtd;i++) filhos[i] = 0;
}

int main(){
	cin >> N >> M;
	for(int i = 1;i<=N;i++) cin >> A[i];
	for(int i = 1;i<N;i++){
		int u,v;
		cin >> u >> v;
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	dfs1(1,-1);
	dfs2(1,-1);
	cout << tab[1][M] << endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 692 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 744 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 876 KB Output is correct
2 Correct 5 ms 1072 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 49 ms 1280 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1528 KB Output is correct
2 Correct 32 ms 1528 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1892 KB Output is correct
2 Correct 278 ms 1896 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 2512 KB Output is correct
2 Correct 56 ms 2512 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 2888 KB Output is correct
2 Correct 51 ms 3004 KB Output is correct