Advertisement
mickypinata

USACO-T011: Barn Repair

Sep 21st, 2021
2,012
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: barn1
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 200;
  11.  
  12. int cows[N + 1];
  13. vector<int> edges;
  14.  
  15. int main(){
  16.  
  17.     freopen("barn1.in", "r", stdin);
  18.     freopen("barn1.out", "w", stdout);
  19.  
  20.     int limBoard, nCow;
  21.     scanf("%d%*d%d", &limBoard, &nCow);
  22.     if(nCow <= limBoard){
  23.         cout << nCow << '\n';
  24.         return 0;
  25.     }
  26.     for(int i = 1; i <= nCow; ++i){
  27.         scanf("%d", &cows[i]);
  28.     }
  29.     sort(cows + 1, cows + nCow + 1);
  30.     for(int i = 1; i < nCow; ++i){
  31.         edges.push_back(cows[i + 1] - cows[i] - 1);
  32.     }
  33.     sort(edges.begin(), edges.end());
  34.     int compCnt = nCow;
  35.     int sum = nCow;
  36.     for(int &w : edges){
  37.         sum += w;
  38.         --compCnt;
  39.         if(compCnt == limBoard){
  40.             break;
  41.         }
  42.     }
  43.     cout << sum << '\n';
  44.  
  45.     fclose(stdin);
  46.     fclose(stdout);
  47.  
  48.     return 0;
  49. }
  50.  
Advertisement
RAW Paste Data Copied
Advertisement