PROBLEM LINK:
Author: Rahul Thakur
Tester: Rahul Thakur
Editorialist: Rahul Thakur
DIFFICULTY:
EASY
PREREQUISITES:
DP
PROBLEM:
We have to find the minimum possible cost in which we can make a perfect team such that all players do well together and if it is not possible then print -1.
EXPLANATION:
We have to use Dynamic Programming in the solution. For the solution we have to use dp[i][j], where dp[i][j] will store the minimum cost possible to make a pair of ith kind of player with jth kind of player. Problem with this solution is that checking all the pairs will cost in O(n* n) complexity and that will lead to time limit exceed. So we need a data structure which have find , delete and other operations in O(lgn) complexity so checking for minimum between pairs will lead into O(n* lgn) complexity and we can use the same method for checking the other two kind of pairings of the players also. Time complexity of this solution is O(n* lgn).
SOLUTIONS:
Setter's Solution
//hail to jwalaji
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
# define M_PI 3.14159265358979323846
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
void solve() {
ll ns[4];
F0R(i, 4) {
cin >> ns[i];
}
vector<vl> cost(4);
ll x;
F0R(i, 4) {
F0R(j, ns[i]) {
cin >> x;
cost[i].pb(x);
}
}
vector<vector<vector<ll>>> bad(3);
F0R(i, 3) {
bad[i].resize(ns[i + 1]);
ll m;
cin >> m;
F0R(j, m) {
ll x, y;
cin >> x >> y;
x--;
y--;
bad[i][y].pb(x);
}
}
vector<vl>dp(4);
F0R(i, 4) {
dp[i].resize(ns[i]);
}
F0R(i, ns[0]) {
dp[0][i] = cost[0][i];
}
F0R(i, 3) {
multiset<ll>s;
F0R(j, ns[i]) {
s.ins(dp[i][j]);
}
F0R(j, ns[i + 1]) {
for (auto k : bad[i][j])
s.erase(s.find(dp[i][k]));
if (s.empty())
dp[i + 1][j] = MOD;
else {
dp[i + 1][j] = *s.begin() + cost[i + 1][j];
}
for (auto k : bad[i][j]) {
s.ins(dp[i][k]);
}
}
}
ll ans = *min_element(dp[3].begin(), dp[3].end());
if (ans >= MOD) {
ans = -1;
}
cout << ans << nl;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}