| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1183919 | lance0 | Friend (IOI14_friend) | C++20 | 0 ms | 0 KiB |
#include <friend.h>
int findSample(int n, int confidence[], int host[], int protocol[]) {
int dp[n][2] = {};
for (int i = 0; i < n; i++) {
dp[i][0] = confidence[i];
}
for (int i = n-1; i > 0; i--) {
int j = host[i];
if (protocol[i] == 0) {
dp[j][0] += dp[i][1]; // dont take invitee
dp[j][1] += max(dp[i][0], dp[i][1]); // free to do anything with invitee
} else if (protocol[i] == 1) {
dp[j][0] += max(dp[i][0], dp[i][1]); // free to do anything with invitee
dp[j][0] = max(dp[j][0], dp[j][1] + dp[i][0]); // as well as the case of taking host but not invitee (1 person case)
dp[j][1] += dp[i][1]; //dont take either
} else {
dp[j][0] = max(dp[j][0] + dp[i][1], dp[i][0] + dp[j][1]); // taking one is fine
dp[j][1] += dp[i][1]; // and so is taking none
}
return max(dp[0][0], dp[0][1]) //best is dependent on taking or not person 0, so just look at both.
}
}