제출 #1370566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370566		cnam9	친구 (IOI14_friend)	C++20	27 / 100	0 ms	344 KiB

friend

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


using namespace std;

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] = max(dp[v][1], dp[v][0]);
        if (v == 0) break;
        int u = host[v];

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

• 서브태스크 1: 0 / 11
• 서브태스크 2: 8 / 8
• 서브태스크 3: 0 / 8
• 서브태스크 4: 19 / 19
• 서브태스크 5: 0 / 23
• 서브태스크 6: 0 / 31