fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  5.   int i;
  6.   sz++;
  7.   for(i=sz-1;i>k;i--){
  8.     a[i] = a[i-1];
  9.   }
  10.   a[k] = aval;
  11. }
  12. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  13.   int i;
  14.   sz++;
  15.   for(i=sz-1;i>k;i--){
  16.     a[i] = a[i-1];
  17.   }
  18.   for(i=sz-1;i>k;i--){
  19.     b[i] = b[i-1];
  20.   }
  21.   a[k] = aval;
  22.   b[k] = bval;
  23. }
  24. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  25.   int i;
  26.   sz++;
  27.   for(i=sz-1;i>k;i--){
  28.     a[i] = a[i-1];
  29.   }
  30.   for(i=sz-1;i>k;i--){
  31.     b[i] = b[i-1];
  32.   }
  33.   for(i=sz-1;i>k;i--){
  34.     c[i] = c[i-1];
  35.   }
  36.   a[k] = aval;
  37.   b[k] = bval;
  38.   c[k] = cval;
  39. }
  40. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  41.   int i;
  42.   sz++;
  43.   for(i=sz-1;i>k;i--){
  44.     a[i] = a[i-1];
  45.   }
  46.   for(i=sz-1;i>k;i--){
  47.     b[i] = b[i-1];
  48.   }
  49.   for(i=sz-1;i>k;i--){
  50.     c[i] = c[i-1];
  51.   }
  52.   for(i=sz-1;i>k;i--){
  53.     d[i] = d[i-1];
  54.   }
  55.   a[k] = aval;
  56.   b[k] = bval;
  57.   c[k] = cval;
  58.   d[k] = dval;
  59. }
  60. template<class S, class T> inline S chmin(S &a, T b){
  61.   if(a>b){
  62.     a=b;
  63.   }
  64.   return a;
  65. }
  66. #define main dummy_main
  67. int main(){
  68.   return 0;
  69. }
  70. #undef main
  71. int dp[100000];
  72. int ls[20];
  73. int lis[20][100000];
  74. int cost[20][100000];
  75. int sz;
  76. int arr[20];
  77. class Solution{
  78.   public:
  79.   int minimumIncompatibility(vector<int>& A, int K){
  80.     int i, mask;
  81.     int N = A.size();
  82.     int res;
  83.     int f;
  84.     K = N / K;
  85.     sort(A.begin(), A.end());
  86.     for(i=(0);i<(N);i++){
  87.       ls[i] = 0;
  88.     }
  89.     for(i=(0);i<(1<<N);i++){
  90.       int j;
  91.       sz = 0;
  92.       for(j=(0);j<(N);j++){
  93.         if(((i) &(1<<(j)))){
  94.           arr[sz++] = A[j];
  95.         }
  96.       }
  97.       if(sz != K){
  98.         continue;
  99.       }
  100.       for(j=(0);j<(N);j++){
  101.         if(((i) &(1<<(j)))){
  102.           f = j;
  103.           break;
  104.         }
  105.       }
  106.       for(j=(1);j<(K);j++){
  107.         if(arr[j-1] == arr[j]){
  108.           goto Q5VJL1cS;
  109.         }
  110.       }
  111.       arrInsert(ls[f], ls[f], lis[f], i, cost[f], arr[K-1] - arr[0]);
  112.       Q5VJL1cS:;
  113.     }
  114.     for(i=(0);i<(1<<N);i++){
  115.       dp[i] = 1073709056;
  116.     }
  117.     dp[0] = 0;
  118.     for(mask=(0);mask<((1<<N)-1);mask++){
  119.       if(dp[mask] < 1073709056){
  120.         for(f=(0);f<(N);f++){
  121.           if(!((mask) &(1<<(f)))){
  122.             break;
  123.           }
  124.         }
  125.         for(i=(0);i<(ls[f]);i++){
  126.           if(!(mask & lis[f][i])){
  127.             chmin(dp[mask|lis[f][i]], dp[mask] + cost[f][i]);
  128.           }
  129.         }
  130.       }
  131.     }
  132.     res = dp[(1<<N)-1];
  133.     if(res==1073709056){
  134.       return -1;
  135.     }
  136.     else{
  137.       return res;
  138.     }
  139.   }
  140. }
  141. ;
  142. // cLay version 20201206-1
  143.  
  144. // --- original code ---
  145. // #define main dummy_main
  146. // {}
  147. // #undef main
  148. // 
  149. // int dp[1d5];
  150. // int ls[20], lis[20][1d5], cost[20][1d5];
  151. // int sz, arr[20];
  152. // 
  153. // class Solution {
  154. // public:
  155. //   int minimumIncompatibility(vector<int>& A, int K) {
  156. //     int N = A.size(), res, f;
  157. //     K = N / K;
  158. //     sort(A.begin(), A.end());
  159. //     rep(i,N) ls[i] = 0;
  160. //     rep(i,1<<N){
  161. //       sz = 0;
  162. //       rep(j,N) if(BIT_ith(i,j)) arr[sz++] = A[j];
  163. //       if(sz != K) continue;
  164. //       rep(j,N) if(BIT_ith(i,j)) f = j, break;
  165. //       rep(j,1,K) if(arr[j-1] == arr[j]) break_continue;
  166. //       arrInsert(ls[f], ls[f], lis[f], i, cost[f], arr[K-1] - arr[0]);
  167. //     }
  168. // 
  169. //     rep(i,1<<N) dp[i] = int_inf;
  170. //     dp[0] = 0;
  171. // 
  172. //     rep(mask,(1<<N)-1) if(dp[mask] < int_inf){
  173. //       rep(f,N) if(!BIT_ith(mask,f)) break;
  174. //       rep(i,ls[f]) if(!(mask & lis[f][i])) dp[mask|lis[f][i]] <?= dp[mask] + cost[f][i];
  175. //     }
  176. // 
  177. //     res = dp[(1<<N)-1];
  178. //     return if[res==int_inf, -1, res];
  179. //   }
  180. // };
  181.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/hDVed8
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!