Submission #1176073

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1176073	2025-03-29 21:09:52	HasanV11010238	Džumbus (COCI19_dzumbus)	C++20	110 / 110	82 ms	40520 KiB

dzumbus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
#define ll long long
#define INF 1000000000000000
using namespace std;
vector<vector<vector<ll>>> dp;
vector<vector<int>> v;
vector<ll> vis, co;
void dfs(int x){
    vis[x] = 1;
    dp[x] = {{0, co[x], INF}, {INF, INF, INF}};
    for (auto el : v[x]){
        if (vis[el] == 1) continue;
        dfs(el);
        int n1 = dp[x].size(), n2 = dp[el].size();
        vector<vector<ll>> ndp(n1 + n2, vector<ll>(3, INF));
        for (int i = 0; i < n1; i++){
            for (int j = 0; j < n2; j++){
                ll mii = min(dp[el][j][0], min(dp[el][j][1], dp[el][j][2]));
                for (int k = 0; k < 3; k++){
                    ndp[i + j][k] = min(dp[x][i][k] + mii, ndp[i + j][k]);
                }
                for (int k1 = 1; k1 < 3; k1++){
                    for (int k2 = 1; k2 < 3; k2++){
                        int ad = 4 - k1 - k2;
                        if (i + j + ad >= n1 + n2) continue;
                        ndp[i + j + ad][2] = min(dp[x][i][k1] + dp[el][j][k2], ndp[i + j + ad][2]);
                    }
                }
            }
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30