arfin97

[UVa 11292] Dragon of Loowater

Feb 21st, 2017
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. //https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2267
  2. //..Binary Search Solution:
  3. //http://www.algorithmist.com/index.php/UVa_11292
  4. //..Stay Ahead Greedy Solution:
  5. //https://github.com/marioyc/Online-Judge-Solutions/blob/master/UVA/Contest%20Volumes/11292%20-%20Dragon%20of%20Loowater.cpp
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. int main(){
  11.     int n, m;
  12.     while(scanf("%d %d", &n, &m) == 2){
  13.         if(n == 0 && m == 0) break;
  14.  
  15.         int dragon[n];
  16.         int knight[m];
  17.         int killed[n];
  18.  
  19.         //Taking inputs ar sorting'em;
  20.         for(int i = 0; i < n; i++){
  21.             scanf("%d", &dragon[i]);
  22.         }
  23.         for(int i = 0; i < m; i++){
  24.             scanf("%d", &knight[i]);
  25.         }
  26.         for(int i = 0; i < n; i++){
  27.             killed[i] = 0;
  28.         }
  29.         sort(dragon, dragon+n);
  30.         sort(knight, knight+m);
  31.  
  32.         //Killing the dragons and counting the coins;
  33.         int coin = 0;
  34.         for(int i = 0; i < n; i++){
  35.             for(int j = 0; j < m; j++){
  36.                 if(dragon[i] == 0) break;
  37.                 if(knight[j] >= dragon[i]){
  38.                     coin += knight[j];
  39.                     killed[i] = 1;
  40.                     knight[j] = 0;
  41.                     dragon[i] = 0;
  42.                 }
  43.             }
  44.         }
  45.         //Killed array checker; if 1 then killed;
  46.         int flag = 1;
  47.         for(int i = 0; i < n; i++){
  48.             if(killed[i] != 1){
  49.                 flag = 0;
  50.                 break;
  51.             }
  52.         }
  53.  
  54.         //if all killed
  55.         if(flag == 1) printf("%d\n", coin);
  56.  
  57.         else printf("Loowater is doomed!\n");
  58.     }
  59.     return 0;
  60. }
Add Comment
Please, Sign In to add comment