Submission #12806

#	Time	Username	Problem	Language	Result	Execution time	Memory
12806		qja0950	Friend (IOI14_friend)	C++98	100 / 100	36 ms	3048 KiB

friend

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

using namespace std;

#define MAX_N 101101

int N;
int Dy[MAX_N][2];

int findSample(int n,int confidence[],int host[],int protocol[]) {
    N = n;
    for(int i=0; i<N; i++)
        Dy[i][1] = confidence[i];
    
    for(int i=N; i>=1; i--) {
        int p = protocol[i];
        int h = host[i];
        
        int i0 = Dy[i][0], i1 = Dy[i][1];
        int h0 = Dy[h][0], h1 = Dy[h][1];
        
        if(p == 0) {
            Dy[h][0] += max(i0, i1);
            Dy[h][1] += i0;
        }else if(p == 1) {
            Dy[h][0] += i0;
            Dy[h][1] = max(h1 + i1, max(h1 + i0, h0 + i1) );
        }else if(p == 2) {
            Dy[h][0] += i0;
            Dy[h][1] = max(h1 + i0, h0 + i1);
        }
    }
    
    return max(Dy[0][0], Dy[0][1]);
}

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