fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <set>
  4. #include <vector>
  5. #include <algorithm>
  6. #define nmax 3010
  7.  
  8. using namespace std;
  9.  
  10. int n, m;
  11. int p[nmax], c[nmax], votes[nmax], backupVotes[nmax];
  12.  
  13. multiset <int> st[nmax], backup[nmax];
  14.  
  15. int main()
  16. {
  17.     scanf("%d %d", &n, &m);
  18.  
  19.     for (int i = 1; i <= n; i++) {
  20.  
  21.         scanf("%d %d", &p[i], &c[i]);
  22.  
  23.         st[p[i]].insert(c[i]); votes[p[i]]++;
  24.     }
  25.  
  26.     for (int i = 1; i <= m; i++) {
  27.  
  28.         backup[i] = st[i];
  29.         backupVotes[i] = votes[i];
  30.     }
  31.  
  32.     long long int answer = 1e18;
  33.  
  34.     for (int i = 1; i <= n; i++) {
  35.  
  36.         //party 1 wins with (i) votes
  37.  
  38.         long long int cur_answer = 0;
  39.  
  40.         for (int j = 2; j <= m; j++)
  41.             while (votes[j] >= i) {
  42.  
  43.                 cur_answer += *st[j].begin();
  44.  
  45.                 st[j].erase(st[j].begin());
  46.  
  47.                 votes[j]--; votes[1]++;
  48.  
  49.             }
  50.  
  51.         if (votes[1] >= i) answer = min(answer, cur_answer); else
  52.         {
  53.             int dif = i - votes[1];
  54.             vector <int> cur_array;
  55.  
  56.             for (int j = 2; j <= m; j++)
  57.                 for (set<int>::iterator it = st[j].begin(); it != st[j].end(); it++)
  58.                     cur_array.push_back(*it);
  59.  
  60.             sort(cur_array.begin(), cur_array.end());
  61.  
  62.             for (int j = 1; j <= dif; j++) cur_answer += cur_array[j - 1];
  63.  
  64.             answer = min(answer, cur_answer);
  65.         }
  66.  
  67.         for (int j = 1; j <= m; j++) {
  68.  
  69.             st[j] = backup[j];
  70.             votes[j] = backupVotes[j];
  71.         }
  72.     }
  73.  
  74.     printf("%I64d", answer);
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
5 5
2 100
3 200
4 300
5 800
5 900
stdout
copy 
                                                             600
https://ideone.com/3lWBUz
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!