Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2267
- //..Binary Search Solution:
- //http://www.algorithmist.com/index.php/UVa_11292
- //..Stay Ahead Greedy Solution:
- //https://github.com/marioyc/Online-Judge-Solutions/blob/master/UVA/Contest%20Volumes/11292%20-%20Dragon%20of%20Loowater.cpp
- #include <bits/stdc++.h>
- using namespace std;
- int main(){
- int n, m;
- while(scanf("%d %d", &n, &m) == 2){
- if(n == 0 && m == 0) break;
- int dragon[n];
- int knight[m];
- int killed[n];
- //Taking inputs ar sorting'em;
- for(int i = 0; i < n; i++){
- scanf("%d", &dragon[i]);
- }
- for(int i = 0; i < m; i++){
- scanf("%d", &knight[i]);
- }
- for(int i = 0; i < n; i++){
- killed[i] = 0;
- }
- sort(dragon, dragon+n);
- sort(knight, knight+m);
- //Killing the dragons and counting the coins;
- int coin = 0;
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- if(dragon[i] == 0) break;
- if(knight[j] >= dragon[i]){
- coin += knight[j];
- killed[i] = 1;
- knight[j] = 0;
- dragon[i] = 0;
- }
- }
- }
- //Killed array checker; if 1 then killed;
- int flag = 1;
- for(int i = 0; i < n; i++){
- if(killed[i] != 1){
- flag = 0;
- break;
- }
- }
- //if all killed
- if(flag == 1) printf("%d\n", coin);
- else printf("Loowater is doomed!\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment