fork download
copy 
  1. //Program: zabava
  2. //Author: gary
  3. //Date: 18/10/2014
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <iostream>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <string>
  14. #include <algorithm>
  15. using namespace std;
  16. #define SZ(x) ( (int) (x).size() )
  17. #define dbg(x) cerr << #x << " = " << x << endl;
  18. #define mp make_pair
  19. #define pb push_back
  20. #define fi first
  21. #define se second
  22. typedef long long ll;
  23. typedef pair<int, int> pii;
  24. // const int INF = 1e9;
  25. // const int MAX_N = ;
  26. ll g(int x) { return 1LL * x * (x + 1) / 2; }
  27. // n students, m groups
  28. ll func(int n, int m){
  29.   int a = n / m;
  30.   int b = n % m;
  31.   return b * g(a + 1) + (m - b) * g(a);
  32. }
  33. const int MAX_M = 100 + 5;
  34. const int MAX_K = 500 + 5;
  35. int N, M, K;
  36. int C[MAX_M];
  37. ll D[MAX_M][MAX_K];
  38.  
  39. void mmin(ll& a, ll b){
  40.   a = min(a, b);
  41. }
  42.  
  43. int main(){
  44.   int x;
  45.   scanf("%d%d%d", &N, &M, &K);
  46.   for(int i = 0; i < N; i++){
  47.     scanf("%d", &x);
  48.     C[x] ++;
  49.   }
  50.   for(int i = 1; i <= M; i++){
  51.     for(int j = K; j >= 0; j--){
  52.       D[i][j] = (1LL << 62);
  53.       for(int k = 0; j + k <= K; k++){
  54. 		mmin(D[i][j], D[i - 1][j + k] + func(C[i], k + 1));
  55.       }
  56.     }
  57.   }
  58.   printf("%lld\n", D[M][0]);
  59.   return 0;
  60. }
  61.  
Success #stdin #stdout 0s 3756KB
comments (?)
stdin
copy 
5 1 2
1
1
1
1
1
stdout
copy 
7
https://ideone.com/ME5JwQ
language:
C++ (gcc 8.3)
created:
10 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!