Submission #49310

#	Time	Username	Problem	Language	Result	Execution time	Memory
49310		IvanC	Dostavljač (COCI18_dostavljac)	C++17	140 / 140	278 ms	3004 KiB

dostavljac

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14