Skip to content

Instantly share code, notes, and snippets.

@IvanIsCoding

IvanIsCoding/a.cpp

Last active October 21, 2023 09:07
Show Gist options
  • Save IvanIsCoding/a1fe3bfb85210642d47cf48b292dd725 to your computer and use it in GitHub Desktop.
Save IvanIsCoding/a1fe3bfb85210642d47cf48b292dd725 to your computer and use it in GitHub Desktop.
Download ZIP
Educational Dynamic Programming Contest - AtCoder
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
@adelkhah
Copy link

adelkhah commented Aug 27, 2020 •
edited
Loading

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment