Submission #518692

#	Time	Username	Problem	Language	Result	Execution time	Memory
518692		amukkalir	Friend (IOI14_friend)	C++17	0 / 100	1 ms	332 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
typedef long long ll; 
using namespace std; 
#define pb push_back; 

const int nax = 1e5; 
ll dp[nax+5]; 
ll tree[4*nax+5]; 
int n; 

void upd(int idx, int l, int r, int where) {
	if(l == r && l == where) tree[idx] = dp[where]; 
	else if (l <= where && where <= r) {
		int m = (l+r)>>1; 
		upd(idx<<1, l, m, where); 
		upd(idx<<1|1, m+1, r, where); 
		tree[idx] = max(tree[idx<<1], tree[idx<<1|1]); 
	}
}

ll query(int idx, int l, int r, int from, int to) {
	if(to < l || from > r) return 0; 
	else if (l <= from && to <= r) return tree[idx]; 
	else {
		int m = (l+r) >> 1; 
		return max(query(idx<<1, l, m, from, to), query(idx<<1|1, m+1, r, from, to));
	}
}

ll get (int l, int r) {
	if(r < l) return 0; 
	return query(1, 0, n-1, l, r); 
}


// Find out best sample
int findSample(int N,int confidence[],int host[],int protocol[]){
	n = N; 
	dp[0] = confidence[0]; 
	
	ll ans = dp[0]; 
	for(int i=1; i<N; i++)	 {
		dp[i] = confidence[i] + max(get(0, host[i]-1), get(host[i]+1, i)); 
		upd(1, 0, n-1, i); 
		ans = max(ans, dp[i]); 
	}

	return ans; 
}

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