Submission #404194

#	Time	Username	Problem	Language	Result	Execution time	Memory
404194		definitelynotmee	Friend (IOI14_friend)	C++98	16 / 100	8 ms	492 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;



int findSample(int n, int confidence[], int host[], int protocol[]){

    vector<vector<bool>> isFriend(n, vector<bool> (n,0));
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            isFriend[j][i] = isFriend[host[i]][j] && protocol[i];
            isFriend[i][j] = isFriend[j][i];
        }
        if(protocol[i] == 0 || protocol[i] == 2)
            isFriend[host[i]][i] = 1, isFriend[i][host[i]] = 1;
    }
    vector<int> dp(n,0);
    int resp = 0;
    for(int i = n-1; i >= 0; i--){
        for(int j = i+1; j < n; j++){
            if(!isFriend[i][j])
                dp[i] = max(dp[j],dp[i]);
        }
        dp[i]+=confidence[i];
        resp = max(resp,dp[i]);
    }
    return resp;
}  

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