제출 #1182083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182083		tapilyoca	친구 (IOI14_friend)	C++20	100 / 100	385 ms	3600 KiB

friend

/***********************************************
* auth: tapilyoca                              *
* date: 04/09/2025 at 21:26:08                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const long long MOD = 1e9+7;

using ll = int;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using str = string;
#define dbg(x) cerr << #x << ": " << x << endl;

/***********************************************/

ll findSample(ll n, ll conf[], ll host[], ll p[]) {
    ll out = 0;

    ll take[n], notake[n];

    for(int i = 0; i < n; i++) {
        take[i] = conf[i];
        notake[i] = 0;    

        cerr << i << " " << take[i] << " " << notake[i] << endl;
    }

    for(int i = n-1; i >= 1; i--) {
        ll u = host[i];
        ll v = i;

        if(p[i] == 0) { // i am your friend
            // either take u, take v, or take none
            take[u] = take[u] + notake[v];
            notake[u] = max(notake[u] + notake[v], notake[u] + take[v]);
        }

        if(p[i] == 1) { // my friends are your friends
            // either take both, one, or none
            take[u] = max({take[u] + take[v], take[u] + notake[v], notake[u] + take[v]});
            notake[u] = notake[u] + notake[v];
        }

        if(p[i] == 2) { // we are your friends
            // either take u, take v, or take none
            take[u] = max(take[u] + notake[v], notake[u] + take[v]);
            notake[u] = notake[u] + notake[v];
        }
    }


    return max(take[0], notake[0]);
}

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