oj.uz

Submission #203824

# Submission time Handle Problem Language Result Execution time Memory
203824 2020-02-22T10:45:58 Z BartolM Dostavljač (COCI18_dostavljac) C++17
140 / 140
 1442 ms 4472 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4344 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4376 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4348 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4344 KB Output is correct
2 Correct 237 ms 4472 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 4392 KB Output is correct
2 Correct 97 ms 4344 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4472 KB Output is correct
2 Correct 1025 ms 4404 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 4472 KB Output is correct
2 Correct 241 ms 4344 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1442 ms 4412 KB Output is correct
2 Correct 155 ms 4344 KB Output is correct