A - Frog 1

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int f[maxn];
int h[maxn];
int main(){
    // debug;
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++) cin>>h[i];
    memset(f,0x3f,4*N+10);
    f[1] = 0;
    for(int i = 1;i<=N;i++){
        f[i+1] = min(f[i+1],f[i] + abs(h[i+1] - h[i]));
        f[i+2] = min(f[i+2],f[i] + abs(h[i+2] - h[i]));
    }
    cout<<f[N]<<'\n';

    return 0;
}

B - Frog 2

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,K;
int f[maxn];
int h[maxn];
int main(){
    // debug;
    ios;
    cin>>N>>K;
    for(int i = 1;i<=N;i++) cin>>h[i];
    memset(f,0x3f,4*N+100);
    f[1] = 0;
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=K;j++){
            if(i+j<=N) f[i+j] = min(f[i+j],f[i] + abs(h[i+j] - h[i]));
        }
    }
    cout<<f[N]<<'\n';

    return 0;
}

C - Vacation

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int w[maxn][3];
int f[maxn][3];
int main(){
    // debug;
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++) cin>>w[i][0]>>w[i][1]>>w[i][2];
    f[1][0] = w[1][0],f[1][1] = w[1][1],f[1][2] = w[1][2];
    for(int i = 2;i<=N;i++){
        for(int j = 0;j<3;j++){
            for(int k = 0;k<3;k++){
                if(j != k) f[i][j] = max(f[i][j],f[i-1][k] + w[i][j]);
            }
        }
    }
    cout<<max(max(f[N][0],f[N][1]),f[N][2])<<'\n';
    return 0;
}

D - Knapsack 1

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,W;
int w[maxn],v[maxn];
ll dp[maxn];
int main(){
    // debug;
    ios;

    cin>>N>>W;
    for(int i = 1;i<=N;i++) cin>>w[i]>>v[i];
    for(int i = 1;i<=N;i++){
        for(int j = W;j>=w[i];j--){
            dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
        }
    }
    cout<<dp[W]<<'\n';

    return 0;
}

E - Knapsack 2

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll inf = 1e18;
using namespace std;

int N,W;
ll w[maxn],v[maxn];
ll dp[maxn];
int main(){
    // debug;
    ios;

    cin>>N>>W;
    for(int i = 1;i<=N;i++) cin>>w[i]>>v[i];
    for(int i = 1;i<=N;i++){
        for(int j = 100000;j>=v[i];j--){
            if(dp[j] == 0){
                if(dp[j-v[i]] != 0) dp[j] = dp[j-v[i]] + w[i];
                else if(j - v[i] == 0) dp[j] = w[i]; 
            }else{
                if(dp[j-v[i]] != 0) dp[j] = min(dp[j],dp[j-v[i]] + w[i]);
                else if (j - v[i] == 0) dp[j] = min(dp[j],w[i]); 
            }
        }
    }
    for(int i = 100000;i>=0;i--){
        if(dp[i] != 0 && dp[i] <= W){
            cout<<i<<'\n';
            return 0;
        }
    }
    cout<<0<<'\n';

    return 0;
}

F - LCS

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

string s,t;
int f[3030][3030];
pii from[3030][3030];
int lens,lent;

void dfs(int x,int y){
    if(x<= 0 || y<=0) return ;
    dfs(from[x][y].fs,from[x][y].sc);
    cout<<s[x];
}
void upd(int i,int j,int x,int y){
    if(s[x] == t[y]) from[i][j] = {x,y};
    else from[i][j] = from[x][y];
}
int main(){
    // debug;
    ios;
    cin>>s>>t;
    lens = s.length(),lent = t.length();
    s = "#" + s; t = "^"+t;
    for(int i = 1;i<=lens;i++){
        for(int j = 1;j<=lent;j++){
            if(s[i] == t[j]) {
                f[i][j] = f[i-1][j-1] + 1;
                upd(i,j,i-1,j-1);
            }else{
                f[i][j] = max(f[i-1][j],f[i][j-1]);
                if(f[i-1][j] > f[i][j-1]) upd(i,j,i-1,j);
                else upd(i,j,i,j-1);
            } 
        }
    }
    int x = from[lens][lent].fs,y = from[lens][lent].sc;
    dfs(x,y);
    if(s[lens] == t[lent]) cout<<s[lens];


    return 0;
}

G - Longest Path

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,M;
queue<int> q;
int dis[maxn],in[maxn];
int h[maxn],ne[maxn],e[maxn],idx;
void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}

int solve(){
    for(int i = 1;i<=N;i++) if(in[i] == 0) q.push(i);
    while(q.size()){
        int u = q.front();q.pop();
        for(int i = h[u];i;i = ne[i]){
            int v = e[i];
            dis[v] = max(dis[v],dis[u] + 1);
            if(--in[v] == 0){
                q.push(v);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=N;i++) ans = max(ans,dis[i]);
    return ans;
}
int main(){
    // debug;
    ios;
    cin>>N>>M;
    for(int i = 1;i<=M;i++){
        int x,y;cin>>x>>y;
        add(x,y);
        in[y]++;
    }
    cout<<solve()<<'\n';


    return 0;
}

H - Grid 1

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll mod = 1000000007;
using namespace std;

int H,W;
char G[1010][1010];
ll f[1010][1010];
ll sovle(){
    f[1][1] = 1;
    for(int i = 1;i<=H;i++){
        for(int j = 1;j<=W;j++){
            if(i == 1 && j == 1) continue;
            if(G[i][j] == '#') continue;
            f[i][j] = (f[i-1][j] + f[i][j-1]) %mod;
        }
    }
    return f[H][W];
}

int main(){
    // debug;
    ios;
    cin>>H>>W;
    for(int i = 1;i<=H;i++){
        for(int j = 1;j<=W;j++){
            cin>>G[i][j];
        }
    }
    cout<<sovle()<<'\n';
    return 0;
}

I - Coins

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
double p[maxn];
double f[3030][3030];
int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++) cin>>p[i];
    f[1][1] = p[1]; f[1][0] = 1-p[1];
    for(int i = 2;i<=N;i++){
        for(int j = 0;j<=i;j++){
            if(j == 0) {
                f[i][0] = f[i-1][0] * (1-p[i]);
                continue;
            }
            if (j-1>=0) f[i][j] += f[i-1][j-1] * p[i];
            f[i][j] += f[i-1][j] * (1-p[i]);
        }
    }
    double ans = 0;
    for(int i = 1;i<=N;i++){
        if(i > N-i) ans += f[N][i];
    }
    cout.precision(10);
    cout<<ans<<'\n';
    return 0;
}

J - Sushi

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int cnt[4];
double dp[333][333][333];
double dfs(int a,int b,int c){
    if(a + b + c == 0) return 0.0;
    if(dp[a][b][c] > -0.5) return dp[a][b][c];
    double res = double(N)/(a+b+c);
    if(a) res += dfs(a-1,b,c) * a/(a+b+c);
    if(b) res += dfs(a+1,b-1,c) * b/(a+b+c);
    if(c) res += dfs(a,b+1,c-1) * c/(a+b+c);
    return dp[a][b][c] = res;
}
int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++){
        int x;cin>>x;
        ++cnt[x];
    }
    for(int i = 0;i<=N;i++)
        for(int j = 0;j<=N;j++)
            for(int k = 0;k<=N;k++)
                dp[i][j][k] = -1;
    cout.precision(12);
    cout<<dfs(cnt[1],cnt[2],cnt[3])<<'\n';


    return 0;
}

K - Stones

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,K;
int w[maxn],min_w = 1e9;
int f[maxn][2];

bool dfs(int k,int p){
    if(k<min_w) return 0;
    if(f[k][p] != -1) return f[k][p];
    int nx = 1;
    for(int i = 1;i<=N;i++) if(k>=w[i]) nx = nx & dfs(k-w[i],p^1);
    return f[k][p] = nx ^ 1;
}

int main(){
    // debug;
    ios;

    cin>>N>>K;
    for(int i = 1;i<=N;i++) cin>>w[i],min_w = min(min_w,w[i]);
    memset(f,-1,sizeof f);
    dfs(K,0);
    if(f[K][0] == 1) cout<<"First\n";
    else cout<<"Second\n";

    return 0;
}

L - Deque

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
ll w[maxn];
ll f[3030][3030]; // = X-Y

ll solve(){
    for(int i = 1;i<=N;i++) f[i][i] = w[i];
    for(int len = 2;len<=N;len++){
        for(int i = 1;i<=N-len+1;i++){
            int j = i+len-1;
            f[i][j] = max(f[i][j],w[i] - f[i+1][j]);
            f[i][j] = max(f[i][j],w[j] - f[i][j-1]);
        }
    }
    return f[1][N];
}

int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++) cin>>w[i];
    for(int i = 1;i<=N;i++) for(int j = 1;j<=N;j++) f[i][j] = -1e18;
    cout<<solve()<<'\n';

    return 0;
}

M - Candies

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const ll mod = 1000000007;
using namespace std;

int N,K;
int cnt[maxn];
ll f[111][maxn],pre[maxn];

ll solve(){
    for(int i = 0;i<=K;i++) f[1][i] = (i<=cnt[1])? 1:0;
    for(int i = 2;i<=N;i++){ // child
        memset(pre,0,sizeof pre);
        pre[0] = f[i-1][0];
        for(int j = 1;j<=K;j++) pre[j] = (f[i-1][j] + pre[j-1]);
        for(int j = K;j>=0;j--){ //want to use
            if(j-cnt[i]-1 >= 0) f[i][j] = pre[j] - pre[j-cnt[i]-1];
            else f[i][j]  =  pre[j];
            f[i][j] %= mod;
        }
    }
    return f[N][K];
}

int main(){
    // debug;
    ios;

    cin>>N>>K;
    for(int i = 1;i<=N;i++) cin>>cnt[i];
    cout<<solve()<<'\n';


    return 0;
}

N - Slimes

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
ll w[maxn];
ll f[405][405][405];

ll solve(){
    memset(f,-1,sizeof f);
    for(int i = 1;i<=N;i++) f[1][i][i] = 0;
    for(int len = 2;len<=N;len++){
        for(int i = 1;i<=N-len+1;i++){
            int j = i+len-1;
            for(int k = i;k<j;k++){
                int lenl = k-i+1,lenr = len-lenl;
                if(f[len][i][j] == -1) f[len][i][j] = f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1];
                else f[len][i][j] = min(f[len][i][j],f[lenl][i][k] + f[lenr][k+1][j] + w[j] - w[i-1]);
            }
        }
    }
    return f[N][1][N];
}

int main(){
    // debug;
    ios;

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

    cout<<solve()<<'\n';

    return 0;
}

O - Matching

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1000000007;
using namespace std;

int N;
int G[22][22];
ll f[22][(1<<21)+5];

ll solve(){
    for(int j = 0;j<N;j++){
        if(G[0][j] == 1) f[0][1<<j] += 1;
    }
    for(int i = 1;i<N;i++){
        for(int j = 0;j<N;j++){
            if(G[i][j] == 1){
                for(int hs = 0;hs<(1<<N);hs++){
                    if(!(hs>>j & 1)) f[i][hs | (1<<j)] =  (f[i][hs | (1<<j)] + f[i-1][hs])%mod;
                }
            }
        }
    }
    return f[N-1][(1<<N)-1];
}
int main(){
    // debug;
    ios;

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

    cout<<solve()<<"\n";
    return 0;
}

P - Independent Set

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
const int mod = 1000000007;
using namespace std;

int N;
ll f[maxn][2];
int h[maxn],e[maxn*2],ne[maxn*2],idx;
void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}

void dfs(int u,int fa = -1){
    bool isyz = true;
    for(int i = h[u]; i ;i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        isyz = false;
        dfs(v,u);
    }
    if(isyz) f[u][1] = 1,f[u][0] = 1;
    else{
        ll black =  1,white = 1;
        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(v == fa) continue;
            black *= f[v][1]; black %= mod;
            white *= (f[v][1] + f[v][0])%mod; white %= mod;
        }
        f[u][0] = black,f[u][1] = white;
    }
}
int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N-1;i++){
        int x,y;cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1);
    cout<<(f[1][0] + f[1][1])%mod;


    return 0;
}

Q - Flowers

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5+10;
using namespace std;

int N;
ll h[maxn],w[maxn],tr[maxn],f[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int x,ll v){
    for(int i = x;i<=N;i += lowbit(i)) tr[i] = max(tr[i],v);
}
ll query(int r){
    ll res = 0;
    for(int i = r;i>=1;i -= lowbit(i)) res = max(res,tr[i]);
    return res;
}

ll solve(){
    for(int i = 1;i<=N;i++){
        f[i] = query(h[i]-1) + w[i];
        add(h[i],f[i]);
    }
    ll mx = 0;
    for(int i = 1;i<=N;i++) mx = max(mx,f[i]);
    return mx;
}
int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++) cin>>h[i];
    for(int i = 1;i<=N;i++) cin>>w[i];
    cout<<solve()<<'\n';
    return 0;
}

R - Walk

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1e9 + 7;
using namespace std;

ll N,K;
struct node
{
    ll M[55][55];
};
node xi,ans;

node mul(const node & A,const node & B){
    node ans;
    memset(ans.M,0,sizeof ans.M);
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=N;j++){
            for(int k = 1;k<=N;k++){
                ans.M[i][j] += A.M[i][k] * B.M[k][j]%mod; ans.M[i][j] %= mod;
            }
        }
    }
    return ans;
}

int main(){
    // debug;
    ios;

    cin>>N>>K;
    for(int i = 1;i<=N;i++) for(int j = 1;j<=N;j++) cin>>xi.M[j][i];
    for(int i = 1;i<=N;i++) ans.M[i][1] = 1;
    while(K){
        if(K & 1) ans = mul(xi,ans);
        xi = mul(xi,xi);
        K >>= 1;
    }

    ll res = 0;
    for(int i = 1;i<=N;i++) res = (res + ans.M[i][1]) %mod;
    cout<<res<<'\n';

    return 0;
}

S - Digit Sum

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e4+10;
const int mod = 1000000007;
using namespace std;

string K;
ll D,len;
ll f[maxn][105];

ll dfs(int pos,int sum,bool limit){
    if(!limit && f[pos][sum] != -1) return f[pos][sum];
    if(pos == len+1) return f[pos][sum] = sum == 0;
    int up = limit ? (K[pos] -'0') : 9;
    ll ans = 0;
    for(int i = 0;i<=up;i++){
        ans += dfs(pos+1,(sum+i)%D,limit && i == up);
        ans %= mod;
    }
    if(!limit) f[pos][sum] = ans;
    return ans;
}

int main(){
    // debug;
    ios;

    cin>>K>>D;
    len = K.length();
    K = '#'+K;
    memset(f,-1,sizeof f);
    cout<<(dfs(1,0,1) - 1 + mod) %mod<<'\n';
    return 0;
}

T - Permutation

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int mod = 1e9+7;
using namespace std;

int N;
string s;
ll f[3030][3030];

void solve(){
    f[1][1] = 1;
    for(int i = 2;i<=N;i++){
        if(s[i-1] == '<'){
            for(int j = 1;j<=i;j++){
                f[i][j] = f[i][j-1] + f[i-1][j-1]; f[i][j] %= mod;
            }
        }else{
            for(int j = i;j>=1;j--){
                f[i][j] = f[i][j+1] + f[i-1][j]; f[i][j] %= mod;
            }
        }
    }
    ll ans = 0;
    for(int i = 1;i<=N;i++) ans = (ans + f[N][i]) %mod;
    cout<<ans<<'\n';
}

int main(){
    // debug;
    ios;

    cin>>N;
    cin>>s; 
    s = '#' + s;
    solve();

    return 0;
}