제출 #423441

#제출 시각아이디문제언어결과실행 시간메모리
423441Theo830친구 (IOI14_friend)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9; ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<int,int> #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training vector<vll>adj; ll arr[1005]; ll dp[1005][2]; ll solve(ll idx,bool ep){ if(dp[idx][ep] != -1){ return dp[idx][ep]; } ll sum = 0; ll maxi = 0; for(auto x:adj[idx]){ if(x > idx){ sum += solve(x,0); maxi = max(maxi,arr[x] + solve(x,1) - solve(x,0)); } } if(!ep){ sum += maxi; } return dp[idx][ep] = sum; } int findSample(int n, int confidence[], int host[], int protocol[]){ adj.assign(n+5,vll()); f(i,0,n){ arr[i] = confidence[i]; } f(i,1,n){ ll v = host[i]; if(protocol[i] == 1){ adj[v].pb(i); adj[i].pb(v); } else if(protocol[i] == 2){ for(auto x:adj[v]){ adj[i].pb(x); adj[x].pb(i); } } else{ for(auto x:adj[v]){ adj[i].pb(x); adj[x].pb(i); } adj[v].pb(i); adj[i].pb(v); } } memset(dp,-1,sizeof dp); return max(solve(0,0),solve(0,1)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...