Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1770
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1770
Shuffle
By Cristhian Bonilha, UTFPR 
Brazil
Timelimit: 1
Your favorite band just released a new album, and to make this experience even more exciting you decided to listen to the songs in a random order. To do that you wrote an algorithm that would make a playlist with K songs of the album. The problem is that your algorithm is not very effective in the way the songs are chosen, in a way that some songs could be played more than once before other songs would be played for the first time.
Given the number of songs of the album, the duration of each song, and the playlist generated by your algorithm, say how long it would take for you to listen to all the songs of the album at least once, if that is possible.
Input
There will be at most 150 test cases. Each test case starts with two integers M and K, indicating the number of songs in the album and the number of songs in your playlist (1 ≤ M ≤ 100, 1 ≤ K ≤ 1000).
Following there will be M integers mi, indicating that the i-th song of the album has mi minutes (1 ≤ mi ≤ 300, for each 1 ≤ i ≤ M).
Following there will be K integers ki, indicating that the i-th song of the playlist is the track of number ki (1 ≤ ki ≤ M, for each 1 ≤ i ≤ K).
The input ends with end of file (EOF).
Output
For each test case print one line, containing one integer, indicating how long it would take for you to listen to all the songs of the album at least once. If this is not possible, print -1.
| Input Sample | Output Sample |
|
3 5 |
497 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
map < int,int> mp;
int m;
int k;
vector<int> v;
int ans;
int q;
while(cin >> m >> k)
{
v.assign(m,0);
for (int i = 0 ; i < m ; i++)
{
cin >> v[i];
}
ans = 0;
for (int i = 0 ; i < k; i++)
{
cin >> q;
--q;
if (mp.size() < m) ans+= v[q];
mp[q]++;
}
if (mp.size() < m) cout << "-1\n";
else cout << ans << '\n';
mp.clear();
v.clear();
}
}
Input
Output