Submission #1370572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370572		cnam9	친구 (IOI14_friend)	C++20	27 / 100	1 ms	344 KiB

friend

#include <algorithm>
#include "friend.h"

constexpr int N = 1e5 + 5;
int s[N];
int dp[N][2];

int findSample(int n, int confidence[], int host[], int protocol[]) {
    for (int v = n - 1;; v--) {
        dp[v][1] += confidence[v];
        dp[v][1] = std::max(dp[v][1], dp[v][0]);
        if (v == 0) break;
        int u = host[v];

        dp[u][0] = std::max(dp[u][0] + dp[v][0], s[u] + dp[v][1]);
        s[u] += dp[v][protocol[v] == 0];
        dp[u][1] += dp[v][protocol[v] == 1];
    }
    return dp[0][1];
}

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 0 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31