fork download 
  1. #include<bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  3. using namespace std;
  4. typedef long long ll;
  5. const int MODD = 998244353;
  6. const int MOD = 1e9 + 7;
  7. const long long INF = 1e9 + 10;
  8. const int N = 2e5 + 20;
  9. const double epsilon = 1e-4;
  10. int n;
  11. ll mem[N][4];
  12. vector<int> number_of_students_in_each_team;
  13. long long dp(int idx, int remainder,vector<pair<int, int>> &elements)
  14. {
  15.     if (idx == elements.size()) return 0;
  16.     else if (idx > elements.size() || n - idx < 3) return INF;
  17.  
  18.     auto &ret = mem[idx][remainder];
  19.     if (ret != -1) return ret;
  20.     ll first = INF, second = INF, third = INF;
  21.     first = dp(idx + 3, 0, elements) + (elements[idx + 2].first - elements[idx].first);
  22.     if (idx + 3 < elements.size()) second = dp(idx + 4, 1, elements) + (elements[idx + 3].first - elements[idx].first);
  23.     if (idx + 4 < elements.size()) third = dp(idx + 5, 2, elements) + (elements[idx + 4].first - elements[idx].first);
  24.     return ret = min({first, second, third});
  25. }
  26. void print_dp(int idx, int remainder,vector<pair<int, int>> &elements)
  27. {
  28.     if (idx >= elements.size() || n - idx < 3) return;
  29.  
  30.     ll opt = dp(idx, remainder, elements);
  31.     ll first = INF, second = INF, third = INF;
  32.     first = dp(idx + 3, 0, elements) + (elements[idx + 2].first - elements[idx].first);
  33.     if (idx + 3 < elements.size()) second = dp(idx + 4, 1, elements) + (elements[idx + 3].first - elements[idx].first);
  34.     if (idx + 4 < elements.size()) third = dp(idx + 5, 2, elements) + (elements[idx + 4].first - elements[idx].first);
  35.  
  36.     if (opt == first) 
  37.     {
  38.         number_of_students_in_each_team.push_back(3);
  39.         print_dp(idx + 3, 0, elements);
  40.     }
  41.     else if (opt == second)
  42.     {
  43.         number_of_students_in_each_team.push_back(4);
  44.         print_dp(idx + 4, 1, elements);
  45.     } 
  46.     else if (opt == third) 
  47.     {
  48.         number_of_students_in_each_team.push_back(5);
  49.         print_dp(idx + 5, 2, elements);
  50.     }
  51. }
  52. void solve() 
  53. {
  54.     cin >> n;
  55.     vector<pair<int, int>> elements(n);
  56.     vector<int> result(n);
  57.     for (int i = 0; i < n; i++)
  58.     {
  59.         cin >> elements[i].first;
  60.         elements[i].second = i;
  61.     }    
  62.     memset(mem, -1, sizeof mem);
  63.     sort(elements.begin(), elements.end());
  64.     ll diversity = dp(0, 3, elements);
  65.  
  66.     print_dp(0, 3, elements);
  67.     ll num_of_teams = number_of_students_in_each_team.size();
  68.     int student = 0;
  69.     for (int i = 0; i < number_of_students_in_each_team.size(); i++)
  70.     {
  71.         for (int j = 0; j < number_of_students_in_each_team[i]; j++)
  72.         {
  73.             result[elements[student++].second] = i + 1;
  74.         }
  75.     }
  76.     cout << diversity << " " <<  num_of_teams << '\n';
  77.  
  78.     for (auto &it: result) cout << it << " ";
  79.  
  80.     elnehaya: cout << '\n';
  81. }
  82. int main() {
  83.     fast;
  84.     int t = 1;
  85.   // cin >> t;
  86.  
  87.     while (t--) {
  88.         solve();
  89.  
  90.     }
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 9880KB
comments (?)
stdin 
Standard input is empty
stdout 
0 0
https://ideone.com/TWUxSA
language:
C++14 (gcc 8.3)
created:
5 days 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!