Submission #203824

#	Time	Username	Problem	Language	Result	Execution time	Memory
203824		BartolM	Dostavljač (COCI18_dostavljac)	C++17	140 / 140	1442 ms	4472 KiB

dostavljac

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;

const int INF=0x3f3f3f3f;
const int N=505;

int n, m;
vector <int> ls[N],lss[N];
int val[N];
int dp[N][N][2];
int dp2[N][N][2];

int rek2(int par, int pos, int x, int fl);

int rek(int node, int x, int fl) {
    if (x<0) return -INF;
    if (x==0) return 0;
    if (ls[node].size()==0) return (!!x)*val[node];

    int &ret=dp[node][x][fl];
    if (ret!=-1) return ret;

    ret=rek2(node, 0, x, fl);
    ret=max(ret, rek2(node, 0, x-1, fl)+val[node]);

    return ret;
}

void dfs(int node, int par) {
    ls[par].pb(node);
    for (int sus:lss[node]) {
        if (sus==par) continue;
        dfs(sus, node);
    }
}

void load() {
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; ++i) scanf("%d", val+i);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        lss[a].pb(b);
        lss[b].pb(a);
    }
}

void solve() {
    dfs(1, 0);
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    printf("%d\n", rek(1, m, 1));
}

int main() {
    load();
    solve();
    return 0;
}

int rek2(int par, int pos, int x, int fl) {
    if (x<0) return -INF;
    if (pos==ls[par].size()) return 0;

    int node=ls[par][pos];

    int &ret=dp2[node][x][fl];
    if(ret!=-1) return ret;

    ret=rek2(par, pos+1, x, fl);
    for (int i=1; i<x; ++i) {
        ret=max(ret, rek(node, i, 0)+rek2(par, pos+1, x-i-2, fl));
        if (fl) ret=max(ret, rek(node, i, 1)+rek2(par, pos+1, x-i-1, 0));
    }

    return ret;
}

Compilation message (stderr)

dostavljac.cpp: In function 'int rek2(int, int, int, int)':
dostavljac.cpp:78:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos==ls[par].size()) return 0;
         ~~~^~~~~~~~~~~~~~~~
dostavljac.cpp: In function 'void load()':
dostavljac.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:54:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=n; ++i) scanf("%d", val+i);
                              ~~~~~^~~~~~~~~~~~~
dostavljac.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14