Submission #1093162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093162		Luvidi	Nestabilnost (COI23_nestabilnost)	C++17	41 / 100	174 ms	197208 KiB

code1

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=5e3;
vector<int> adj[maxn];
int n;
ll dp[maxn+1][maxn+1],mn[maxn+1],a[maxn+1],f[maxn+1];

void dfs(int v,int p){
    for(int i:adj[v])if(i!=p)dfs(i,v);
    mn[v]=1e18;
    for(int i=1;i<=n;i++){
        if(a[v]>=i){
            dp[v][i]=1e18;
            continue;
        }
        dp[v][i]=f[i];
        for(int x:adj[v])if(x!=p){
            if(a[x]<i&&a[x]==(a[v]+1)%i){
                dp[v][i]+=min(mn[x],dp[x][i]-f[i]);
            }else{
                dp[v][i]+=mn[x];
            }
        }
        mn[v]=min(mn[v],dp[v][i]);
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>f[i];
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,1);
    cout<<mn[1];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    solve();
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 20
• Subtask 3: 7 / 7
• Subtask 4: 22 / 22
• Subtask 5: 0 / 39