Educational Dynamic Programming Contest - AtCoder

a.cpp

// Ivan Carvalho
// Problem A - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 2*1e9;

int dp[MAXN],N,K,h[MAXN];

int main(){

	scanf("%d",&N);
	K = 2;
	for(int i = 1;i<=N;i++){
		scanf("%d",&h[i]);
	}

	for(int i = 2;i<=N;i++){
		dp[i] = INF;
		for(int j = i-1;j>=max(i - K,1);j--){
			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]) );
		}
	}

	printf("%d\n",dp[N]);

	return 0;

}

b.cpp

// Ivan Carvalho
// Problem B - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = 2*1e9;

int dp[MAXN],N,K,h[MAXN];

int main(){

	scanf("%d %d",&N,&K);
	for(int i = 1;i<=N;i++){
		scanf("%d",&h[i]);
	}

	for(int i = 2;i<=N;i++){
		dp[i] = INF;
		for(int j = i-1;j>=max(i - K,1);j--){
			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]) );
		}
	}

	printf("%d\n",dp[N]);

	return 0;

}

c.cpp

// Ivan Carvalho
// Problem C - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int vis[MAXN][3],dp[MAXN][3],N,A[3][MAXN];

int solve(int pos,int last){

	if(pos == N + 1) return 0;

	if(vis[pos][last]) return dp[pos][last];
	vis[pos][last] = 1;

	int best = 0;

	for(int i = 0;i<3;i++){
		if(i != last) best = max(best, A[i][pos] + solve(pos+1,i) );
	}

	return dp[pos][last] = best;

}

int main(){

	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%d %d %d",&A[0][i],&A[1][i],&A[2][i]);
	}

	printf("%d\n", max(solve(1,0), max(solve(1,1),solve(1,2)) ) );

	return 0;

}

d.cpp

// Ivan Carvalho
// Problem D - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXW = 1e5 + 10;

long long knapsack[MAXW];
int N,W;

int main(){

	cin >> N >> W;

	for(int item = 1;item<=N;item++){
		int w,v;
		cin >> w >> v;
		for(int i = W;i>=w;i--) knapsack[i] = max(knapsack[i-w] + v,knapsack[i]);
	}

	long long best = 0;
	for(int i = 0;i<=W;i++) best = max(best,knapsack[i]);
	cout << best << endl;

	return 0;

}

e.cpp

// Ivan Carvalho
// Problem E - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXV = 1e5 + 10;
const int MAXN = 1e3 + 10;
const ll INF = 1e13;

ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];

int main(){

	cin >> N >> W;
	for(int i = 1;i<=N;i++){
		cin >> wi[i] >> vi[i];
		V += vi[i];
	}

	for(int i = 1;i<=V;i++) dp[i] = INF;
	dp[0] = 0;
	
	for(int item = 1;item<=N;item++){
		int w = wi[item], v = vi[item];
		for(int i = V;i>=v;i--){
			dp[i] = min(dp[i],dp[i - v] + w);
		}
	}

	for(int i = V;i>=0;i--){
		if(dp[i] <= W){
			cout << i << endl;
			break;
		}
	}

	return 0;

}

f.cpp

// Ivan Carvalho
// Problem F - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3010;

string s,t;
int dp[MAXN][MAXN],N,M;
stack<char> resposta;

int solve(int a,int b){

	if(a < 0 || b < 0) return 0;

	if(dp[a][b] != -1) return dp[a][b];

	if(s[a] == t[b]) return dp[a][b] = 1 + solve(a-1,b-1);

	return dp[a][b] = max(solve(a-1,b),solve(a,b-1));

}

void build(int a,int b){

	if(a < 0 || b < 0) return;

	if(s[a] == t[b]){
		resposta.push(s[a]);
		build(a-1,b-1);
		return;
	}

	if(solve(a-1,b) > solve(a,b-1)) build(a-1,b);
	else build(a,b-1);

}

int main(){

	memset(dp,-1,sizeof(dp));

	cin >> s;
	cin >> t;

	N = (int)s.size();
	M = (int)t.size();

	build(N-1,M-1);

	while(!resposta.empty()){
		cout << resposta.top();
		resposta.pop();
	}
	cout << endl;

	return 0;

}

g.cpp

// Ivan Carvalho
// Problem G - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

vector<int> grafo[MAXN];
int dp[MAXN],vis[MAXN],N,M;

int solve(int v){

	if(vis[v]) return dp[v];

	vis[v] = 1;
	int best = 0;

	for(int u : grafo[v]){
		best = max(best, solve(u) + 1 );
	}

	return dp[v] = best;

}

int main(){

	scanf("%d %d",&N,&M);
	for(int i = 1;i<=M;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
	}

	int best = 0;
	for(int i = 1;i<=N;i++) best = max(best, solve(i) );
	printf("%d\n",best);

	return 0;

}

h.cpp

// Ivan Carvalho
// Problem H - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
const int MOD = 1e9 + 7;

char entrada[MAXN][MAXN];
int dp[MAXN][MAXN],vis[MAXN][MAXN];
int N,M;

int solve(int x,int y){

	if(x >= N || y >= M) return 0;
	if(entrada[x][y] == '#') return 0;

	if(vis[x][y]) return dp[x][y];
	if(x == N - 1 && y == M - 1) return dp[x][y] = 1;

	vis[x][y] = 1;
	return dp[x][y] = (solve(x+1,y) + solve(x,y+1)) % MOD;

}

int main(){

	scanf("%d %d",&N,&M);
	for(int i = 0;i<N;i++){
		scanf("%s",entrada[i]);
	}

	printf("%d\n",solve(0,0));

	return 0;

}

i.cpp

// Ivan Carvalho
// Problem I - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3002;

double dp[MAXN][MAXN],P[MAXN];
int vis[MAXN][MAXN],N;

double solve(int pos,int heads){
	
	if(heads < 0) return 0.0;

	if(pos == 0){
		return (heads == 0);
	}

	if(vis[pos][heads]) return dp[pos][heads];
	vis[pos][heads] = 1;

	return dp[pos][heads] =  (P[pos])*solve(pos-1,heads-1) + (1.0 - P[pos])*solve(pos-1,heads);

}

int main(){

	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> P[i];
	}

	double tot = 0;
	for(int heads = 0;heads<=N;heads++){
		int tails = N - heads;
		if(heads > tails) tot += solve(N,heads);
	}

	printf("%.9lf\n",tot);

	return 0;

}

j.cpp

// Ivan Carvalho
// Problem J - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 302;

double dp[MAXN][MAXN][MAXN];
int N,vis[MAXN][MAXN][MAXN];

double solve(int x,int y,int z){
	
	if(vis[x][y][z]) return dp[x][y][z];
	//printf("Solving %d %d %d\n",x,y,z);
	vis[x][y][z] = 1;

	if(x == 0 && y == 0 && z == 0) return dp[x][y][z] = 0;

	int soma = x + y + z;
	double convertido = (double)soma;
	double tot = (N - soma)/convertido;
	
	//printf("Tot antes %d %d %d %d %lf\n",N - soma,x,y,z,tot);

	if(x != 0) tot += x*((solve(x-1,y,z) + 1)/convertido);
	if(y != 0) tot += y*((solve(x+1,y-1,z) + 1)/convertido);
	if(z != 0) tot += z*((solve(x,y+1,z-1) + 1)/convertido);

	//printf("Tot (%d,%d,%d) = %lf\n",x,y,z,tot);

	return dp[x][y][z] = tot;

}

int main(){

	int a[4] = {0,0,0,0};

	cin >> N;

	for(int i = 1;i<=N;i++){
		int x;
		cin >> x;
		a[x]++;
	}

	printf("%.9lf\n",solve(a[1],a[2],a[3]));

	return 0;
}

k.cpp

// Ivan Carvalho
// Problem K - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 1e5 + 10;
const int MAXN = 1e3 + 10;

int A[MAXN],dp[MAXK],N,K;

int solve(int k){

	if(dp[k] != -1) return dp[k];

	if(k == 0) return dp[k] = 0;

	int ans = 0;
	for(int i = 1;i<=N;i++){
		if(A[i] > k) continue;
		if(solve(k - A[i]) == 0){
			ans = 1;
			break;
		}
	}

	return dp[k] = ans;

}

int main(){

	memset(dp,-1,sizeof(dp));
	cin >> N >> K;
	for(int i = 1;i<=N;i++){
		cin >> A[i];
	}

	if(solve(K)) printf("First\n");
	else printf("Second\n");

	return 0;

}

l.cpp

// Ivan Carvalho
// Problem L - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 3002;

ll dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int A[MAXN],N;

ll solve(int i,int j){

	if(vis[i][j]) return dp[i][j];

	vis[i][j] = 1;

	if(i == j) return dp[i][j] = A[i];

	return dp[i][j] = max(A[i] - solve(i+1,j), A[j] - solve(i,j-1));

}

int main(){

	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> A[i];
	} 

	cout << solve(1,N) << endl;

	return 0;

}

m.cpp

// Ivan Carvalho
// Problem M - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 1e5 + 10;
const int MOD = 1e9 + 7;

int pref[MAXK],dp[MAXK],N,K;

int calc(int a,int b){
	if(a < 0) a = 0;
	int ans = pref[b];
	if(a != 0) ans -= pref[a-1];
	return ans % MOD;
}

int main(){

	cin >> N >> K;

	dp[0] = 1;

	for(int kid = 1;kid<=N;kid++){

		int c;
		cin >> c;

		pref[0] = dp[0];
		dp[0] = 0;
		for(int i = 1;i<=K;i++){
			pref[i] = (pref[i-1] + dp[i]) % MOD;
		}

		for(int i = 0;i<=K;i++){
			dp[i] = calc(i-c,i);
		}

	}

	int ans = dp[K];
	if(ans < 0) ans += MOD; 
	printf("%d\n",ans);

	return 0;

}

n.cpp

// Ivan Carvalho
// Problem N - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 410;
const ll INF = 1e14;

ll dp[MAXN][MAXN],V[MAXN],pref[MAXN];
int N;

ll calc(ll a,ll b){
	if(a > b) return INF;
	return pref[b] - pref[a-1];
}

ll solve(int ini,int fim){
	if(dp[ini][fim] != -1) return dp[ini][fim];
	if(ini == fim) return dp[ini][fim] = 0;
	if(ini + 1 == fim) return dp[ini][fim] = V[ini] + V[fim];

	ll best = INF;

	for(int i = ini;i<fim;i++){
		ll cand = solve(ini,i) + solve(i+1,fim) + calc(ini,fim);
		best = min(best,cand);
	}

	return dp[ini][fim] = best;

}

int main(){

	memset(dp,-1,sizeof(dp));

	cin >> N;
	for(int i = 1;i<=N;i++) cin >> V[i];

	for(int i = 1;i<=N;i++) pref[i] = pref[i-1] + V[i];

	cout << solve(1,N) << endl;

	return 0;

}

o.cpp

// Ivan Carvalho
// Problem O - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 21;
const int MAXL = (1 << 21 ) + 2;
const int MOD = 1e9 + 7;

int dp[MAXN][MAXL],mascara[MAXN],N;

int solve(int pos,int bitmask){

	if(pos == N) return (__builtin_popcount(bitmask) == N);
	if(dp[pos][bitmask] != -1) return dp[pos][bitmask];

	int tot = 0;
	for(int i = 0;i<N;i++){
		if(!(bitmask & (1 << i)) && ((1 << i) & mascara[pos])){
			tot = (tot + solve(pos+1, bitmask | (1 << i) )) % MOD;
		}
	}

	return dp[pos][bitmask] = tot;

}

int main(){

	memset(dp,-1,sizeof(dp));
	cin >> N;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			int x;
			cin >> x;
			if(x) mascara[i] |= (1 << j);
		}
	}
	cout << solve(0,0) << endl;

	return 0;

}

p.cpp

// Ivan Carvalho
// Problem P - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

vector<int> grafo[MAXN];
ll dp[MAXN][2];
int N;

ll solve(int v,int c,int p){

	if(dp[v][c] != -1) return dp[v][c];

	ll tot = 1;
	for(int u : grafo[v]){
		if(u == p) continue;
		if(c == 0) tot = (tot * (solve(u,0,v) + solve(u,1,v))) % MOD;
		else tot = (tot * solve(u,0,v)) % MOD;
	}

	return dp[v][c] = tot;

}

int main(){

	memset(dp,-1,sizeof(dp));

	scanf("%d",&N);
	for(int i = 1;i<N;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	printf("%lld\n", (solve(1,0,-1) + solve(1,1,-1)) % MOD );

	return 0;

}

q.cpp

// Ivan Carvalho
// Problem Q - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
#define LSOne(S) ((S) & (-S))
using namespace std;

typedef long long ll;

const int MAXN = 2*1e5 + 10;

ll bit[MAXN],dp[MAXN];
ll h[MAXN],a[MAXN];
int N;

void update(int x, ll val){
	while(x <= N){
		bit[x] = max(bit[x],val);
		x += LSOne(x);
	}
}

ll query(int x){

	ll ans = 0;
	while(x > 0){
		ans = max(ans,bit[x]);
		x -= LSOne(x);
	}

	return ans;

}

int main(){

	scanf("%d",&N);

	for(int i = 1;i<=N;i++){
		scanf("%lld",&h[i]);
	}
	for(int i = 1;i<=N;i++){
		scanf("%lld",&a[i]);
	}

	for(int i = 1;i<=N;i++){
		dp[i] = query(h[i] - 1) + a[i];
		update(h[i],dp[i]);
	}

	ll best = 0;
	for(int i = 1;i<=N;i++) best = max(best,dp[i]);
	printf("%lld\n",best);

	return 0;

}

r.cpp

// Ivan Carvalho
// Problem R - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 50;
const int MOD = 1e9 + 7;

struct matrix{

	ll mat[MAXN][MAXN];

	matrix(int idd = 0){
		for(int i = 0;i<MAXN;i++){
			for(int j = 0;j<MAXN;j++){
				mat[i][j] = (idd) ? (i == j) : (0);
			}
		}
	}

	matrix operator*(const matrix& other)const{
		matrix ans;
		for(int i = 0;i<MAXN;i++){
			for(int j = 0;j<MAXN;j++){
				for(int k = 0;k<MAXN;k++){
					ans.mat[i][j] += mat[i][k]*other.mat[k][j];
					if(ans.mat[i][j] > MOD) ans.mat[i][j] %= MOD;
				}
			}
		}
		return ans;
	}

};

matrix exponentiation(matrix base, ll K){

	matrix ans(1);

	for(int i = 0;(1LL << i) <= K;i++){
		if((1LL << i) & K) ans = ans*base;
		base = base*base;
	}

	return ans;

}

int main(){

	matrix base;
	int N;
	ll K;
	cin >> N >> K;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++) cin >> base.mat[i][j];
	}

	matrix ans = exponentiation(base,K);
	ll paths = 0;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			paths = (paths + ans.mat[i][j]) % MOD;
		}
	}

	cout << paths << endl;

	return 0;

}

s.cpp

// Ivan Carvalho
// Problem S - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 1e4 + 10;
const int MAXD = 1e2 + 10;
const int MOD = 1e9 + 7;
 
vector<int> digitos;
string s;
int N,D;
ll dp[MAXN][2][MAXD];
 
ll solve(int pos,int flag,int resto){
 
	if(pos == N) return (resto == 0);
	if(dp[pos][flag][resto] != -1) return dp[pos][flag][resto];
 
	ll tot = 0;
	int limit = (flag) ? (digitos[pos]) : (9);
	for(int i = 0;i<=limit;i++){
		tot += solve(pos+1,flag && (i == limit), (resto + i) % D );
	}
 
	return dp[pos][flag][resto] = tot % MOD;
 
}
 
int main(){
 
	cin >> s;
	cin >> D;
	N = (int)s.size();
	for(int i = 0;i<N;i++){
		digitos.push_back(s[i] - '0');
	}
	memset(dp,-1,sizeof(dp));
 
	ll ans = solve(0,1,0) - 1;
	if(ans < 0) ans += MOD;
	cout << ans << endl;
 
 
	return 0;
 
}

t.cpp

// Ivan Carvalho
// Problem T - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 3010;
const int MOD = 1e9 + 7;

string s;
int vis[MAXN][MAXN],ok[MAXN][MAXN];
ll dp[MAXN][MAXN],somatorio[MAXN][MAXN];
int N;

ll solve(int pos, int ultimo);

ll calc(int pos,int ultimo);

ll solve(int pos,int ultimo){

	if(vis[pos][ultimo]) return dp[pos][ultimo];
	vis[pos][ultimo] = 1;

	if(ultimo > pos + 1) return dp[pos][ultimo] = 0;

	if(pos == 0) return dp[pos][ultimo] = 1;

	if(s[pos-1] == '>'){
		ll tot = calc(pos-1,N) - calc(pos-1,ultimo - 1);
		return dp[pos][ultimo] = ((tot + MOD) % MOD);
	}
	else{
		ll tot = calc(pos-1,ultimo-1);
		return dp[pos][ultimo] = (tot % MOD);
	}

}

ll calc(int pos,int ultimo){

	if(ultimo == 0) return 0;

	if(ok[pos][ultimo]) return somatorio[pos][ultimo];
	ok[pos][ultimo] = 1;

	ll tot = solve(pos,ultimo) + calc(pos,ultimo - 1);
	return somatorio[pos][ultimo] = (tot % MOD);

}

int main(){

	cin >> N;
	cin >> s;

	ll tot = 0;
	for(int i = 1;i<=N;i++){
		tot += solve(N-1,i);
	}

	tot %= MOD;

	cout << tot << endl;

	return 0;

}

u.cpp

// Ivan Carvalho
// Problem U - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 16;
const int MAXL = (1 << 16) + 10;
const ll NEG = -1e18;

vector<int> grafo[MAXL];
ll valor[MAXL],dp[MAXL],mat[MAXN][MAXN];
int vis[MAXL],N;

void brute(int pos,int bitmask,int submask){

	if(pos == N){
		if(__builtin_popcount(submask) == 0) return;
		grafo[bitmask].push_back(submask);
		return;
	}

	brute(pos+1,bitmask,submask);
	brute(pos+1, bitmask | (1 << pos), submask );
	brute(pos+1, bitmask | (1 << pos), submask | (1 << pos) );

}

void calcula(){

	for(int bitmask = 1;bitmask < (1 << N);bitmask++){
		for(int i = 0;i<N;i++){
			if(!(bitmask & (1 << i))) continue;
			for(int j = i+1;j<N;j++){
				if(!(bitmask & (1 << j))) continue;
				valor[bitmask] += mat[i][j];
			}
		}
	}

}

ll solve(int bitmask){

	if(bitmask == 0) return 0;
	if(vis[bitmask]) return dp[bitmask];

	vis[bitmask] = 1;

	ll best = NEG;

	for(int submask : grafo[bitmask]){
		best = max(best, solve(bitmask ^ submask) + valor[submask] );
	}

	return dp[bitmask] = best;

}

int main(){

	cin >> N;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			cin >> mat[i][j];
		}
	}

	brute(0,0,0);
	calcula();

	cout << solve((1 << N) - 1) << endl;

	return 0;

}

v.cpp

// Ivan Carvalho
// Problem V - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

vector<int> grafo[MAXN];
ll dp[MAXN],correction[MAXN],ansP[MAXN];
int N,M;

void dfs1(int v,int p){

	dp[v] = 1;
	vector<int> children;
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs1(u,v);
		dp[v] = (dp[v] * (1 + dp[u])) % M;
		children.push_back(u);
	}

	vector<ll> prefV,sufV;
	ll pref = 1, suf = 1;
	for(int i = 0;i<(int)children.size();i++){
		int u = children[i];
		prefV.push_back(pref);
		pref = (pref * (1 + dp[u])) % M;
	}
	for(int i = (int)children.size() - 1;i>=0;i--){
		int u = children[i];
		sufV.push_back(suf);
		suf = (suf * (1 + dp[u])) % M;
	}
	reverse(sufV.begin(),sufV.end());
	for(int i = 0;i<(int)children.size();i++){
		int u = children[i];
		correction[u] = (prefV[i]*sufV[i]) % M;
	}

}

void dfs2(int v,int p){

	ansP[v] = (dp[v] * correction[v]) % M;

	for(int u : grafo[v]){
		if(u == p) continue;
		correction[u] = (correction[u] * (correction[v]) + 1) % M;
		dfs2(u,v);
	}

}

int main(){

	scanf("%d %d",&N,&M);
	for(int i = 1;i<N;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	dfs1(1,-1);
	correction[1] = 1;
	dfs2(1,-1);

	for(int i = 1;i<=N;i++) printf("%lld\n",ansP[i]);

	return 0;

}

w.cpp

// Ivan Carvalho
// Problem W - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2*1e5 + 10;

vector<int> adiciona[MAXN],retira[MAXN];
ll seg[4*MAXN],lazy[4*MAXN],dp[MAXN],valor[MAXN];
int N,M,ini[MAXN],fim[MAXN];

void propagate(int pos,int left,int right){

	if(lazy[pos] == 0) return;

	if(left != right){
		lazy[2*pos] += lazy[pos];
		lazy[2*pos+1] += lazy[pos];
	}

	seg[pos] += lazy[pos];
	lazy[pos] = 0;

}

void update(int pos,int left, int right,int i,int j,ll delta){

	propagate(pos,left,right);
	if(left > right || left > j || right < i) return;

	if(left >= i && right <= j){
		lazy[pos] += delta;
		propagate(pos,left,right);
		return;
	}

	int mid = (left+right)/2;
	update(2*pos,left,mid,i,j,delta);
	update(2*pos+1,mid+1,right,i,j,delta);

	seg[pos] = max(seg[2*pos],seg[2*pos+1]);

}

ll query(int pos,int left,int right,int i,int j){

	propagate(pos,left,right);

	if(left >= i && right <= j) return seg[pos];

	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return max(query(2*pos,left,mid,i,j), query(2*pos+1,mid+1,right,i,j));

}

int main(){

	scanf("%d %d",&N,&M);

	for(int i = 1;i<=M;i++){
		scanf("%d %d %lld",&ini[i],&fim[i],&valor[i]);
		adiciona[ini[i]].push_back(i);
		retira[fim[i]].push_back(i);
	}

	for(int i = 1;i<=N;i++){
		for(int j : adiciona[i]){
			update(1,0,N,0,ini[j] - 1,valor[j]);
		}
		dp[i] = query(1,0,N,0,i-1);
		update(1,0,N,i,i,dp[i]);
		for(int j : retira[i]){
			update(1,0,N,0,ini[j] - 1,-valor[j]);
		}
	}

	ll best = 0;
	for(int i = 1;i<=N;i++) best = max(best,dp[i]);
	printf("%lld\n",best);

	return 0;

}

x.cpp

// Ivan Carvalho
// Problem X - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;

typedef tuple<int,int,int> trinca;
typedef long long ll;

const int MAXW = 2*1e4 + 10;

vector<trinca> guloso;
ll dp[MAXW];
int N;

int main(){

	cin >> N;
	for(int i = 1;i<=N;i++){
		int w,s,v;
		cin >> w >> s >> v;
		guloso.push_back(make_tuple(s+w,w,v));
	}

	sort(guloso.begin(),guloso.end());

	for(trinca davez : guloso){
		int solid = get<0>(davez), w = get<1>(davez);
		ll v = get<2>(davez);
		for(int i = MAXW-1;i>=0;i--){
			if(i + w <= solid){
				dp[i+w] = max(dp[i+w],dp[i] + v);
			}
		}
	}

	ll best = 0;
	for(int i = 0;i<MAXW;i++) best = max(best,dp[i]);
	cout << best << endl;

	return 0;

}

y.cpp

// Ivan Carvalho
// Problem Y - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;

const int MAXN = 2*1e5 + 10;
const int MAXK = 3010;
const int MOD = 1e9 + 7;

vector<ii> pontos;
ll fatorial[MAXN],invfatorial[MAXN],qnts[MAXK];
int H,W,N;

ll fast_expo(ll x,int y){
	if(y == 0) return 1;
	if(y & 1) return (x*fast_expo(x,y-1)) % MOD;
	ll temp = fast_expo(x,y/2);
	return (temp*temp) % MOD;
}

ll binomial(ll n,ll k){
	return ((fatorial[n]*invfatorial[k] % MOD)*invfatorial[n - k]) % MOD;
}

int main(){

	fatorial[0] = invfatorial[0] = 1;
	for(int i = 1;i<MAXN;i++){
		fatorial[i] = (fatorial[i-1]*i) % MOD;
		invfatorial[i] = fast_expo(fatorial[i],MOD - 2);
	}

	cin >> H >> W >> N;
	pontos.push_back(ii(H,W));

	for(int i = 0;i<N;i++){
		int x,y;
		cin >> x >> y;
		pontos.push_back(ii(x,y));
	}

	sort(pontos.begin(),pontos.end());

	for(int i = 0;i<=N;i++){
		qnts[i] = binomial(pontos[i].first + pontos[i].second - 2, pontos[i].first - 1 );
	}

	for(int i = 0;i<N;i++){
		for(int j = i+1;j<=N;j++){
			int deltax = pontos[j].first - pontos[i].first;
			int deltay = pontos[j].second - pontos[i].second;
			if(deltax < 0 || deltay < 0) continue;
			qnts[j] -= binomial(deltax+deltay,deltay)*qnts[i];
			qnts[j] %= MOD;
		}
	}

	if(qnts[N] < 0) qnts[N] += MOD;
	cout << qnts[N] << endl;

	return 0;

}

z.cpp

// Ivan Carvalho
// Problem Z - Educational Dynamic Programming Contest - AtCoder
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 2*1e5 + 10;

struct line{

	ll a,b;

	line(ll _a,ll _b){
		a = _a;
		b = _b;
	}

	ll get(ll x){return a*x + b;}

	ld get(ld x){return a*x + b;}

};

ld inter(line l1,line l2){

	return -(l1.b - l2.b)/ld(l1.a - l2.a);

}

bool useless(line l1,line l2,line l3){
	return inter(l1,l3) < inter(l2,l1);
}

vector<line> CHT;
ll dp[MAXN],h[MAXN],C;
int chtPtr,N;

void add(line l){

	while(CHT.size() >= 2 && useless(CHT[CHT.size()-2],CHT.back(),l) ){
		CHT.pop_back();
	}

	CHT.push_back(l);

}

ll query(ll x){

	if(chtPtr >= CHT.size()) chtPtr = CHT.size() - 1;

	while(chtPtr + 1 < CHT.size() && CHT[chtPtr].get(x) > CHT[chtPtr+1].get(x) ){
		chtPtr++;
	}

	return CHT[chtPtr].get(x);

}

int main(){

	scanf("%d %lld",&N,&C);

	for(int i = 1;i<=N;i++){
		scanf("%lld",&h[i]);
	}

	add(line(-2*h[1], h[1]*h[1] + C ));

	for(int i = 2;i<=N;i++){

		dp[i] = query(h[i]) + h[i]*h[i];
		add(line(-2*h[i], h[i]*h[i] + dp[i] + C ));

	}

	printf("%lld\n",dp[N]);

	return 0;

}

I have a doubt in m.cpp (Candy distribution prob). What is the role of pref[] array.

I have a doubt in m.cpp (Candy distribution prob). What is the role of pref[] array.

It stands for prefix sum

dude thank you so much for the short and easy to read code really helped me for learning the problems thanks again ❤️