fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class S, class T> inline S chmin(S &a, T b){
  7.   if(a>b){
  8.     a=b;
  9.   }
  10.   return a;
  11. }
  12. template<class S, class T> inline S moddw_L(S a, const T b){
  13.   a %= b;
  14.   if(a < 0){
  15.     a += b;
  16.   }
  17.   return a;
  18. }
  19. template<class T> int PalindromeCost(const int N, const T A[]){
  20.   int i;
  21.   int res = 0;
  22.   for(i=(0);i<(N/2);i++){
  23.     if(A[i] != A[N-1-i]){
  24.       res++;
  25.     }
  26.   }
  27.   return res;
  28. }
  29. template<class T> int PalindromeCost(const vector<T> &A){
  30.   const int N = A.size();
  31.   int i;
  32.   int res = 0;
  33.   for(i=(0);i<(N/2);i++){
  34.     if(A[i] != A[N-1-i]){
  35.       res++;
  36.     }
  37.   }
  38.   return res;
  39. }
  40. int PalindromeCost(const string &A){
  41.   const int N = A.size();
  42.   int i;
  43.   int res = 0;
  44.   for(i=(0);i<(N/2);i++){
  45.     if(A[i] != A[N-1-i]){
  46.       res++;
  47.     }
  48.   }
  49.   return res;
  50. }
  51. template<class T, class S> int Slice(const int N, const T A[], const long long bg, const long long ed, const long long step, S res[]){
  52.   long long i;
  53.   long long k;
  54.   long long s;
  55.   int len = 0;
  56.   if(N == 0){
  57.     return 0;
  58.   }
  59.   s =(moddw_L(step,N));
  60.   assert(step != 0);
  61.   if(step > 0){
  62.     for(i = bg, k =(moddw_L(bg,N)); i < ed; i += step, k += s){
  63.       if(k >= N){
  64.         k -= N;
  65.       }
  66.       res[len++] = A[k];
  67.     }
  68.   }
  69.   else{
  70.     for(i = bg, k =(moddw_L(bg,N)); i > ed; i += step, k += s){
  71.       if(k >= N){
  72.         k -= N;
  73.       }
  74.       res[len++] = A[k];
  75.     }
  76.   }
  77.   return len;
  78. }
  79. template<class T> vector<T> Slice(const vector<T> &A, const long long bg, const long long ed, const long long step){
  80.   const int N = A.size();
  81.   long long i;
  82.   long long k;
  83.   long long s;
  84.   vector<T> res;
  85.   if(N == 0){
  86.     return res;
  87.   }
  88.   s =(moddw_L(step,N));
  89.   assert(step != 0);
  90.   if(step > 0){
  91.     for(i = bg, k =(moddw_L(bg,N)); i < ed; i += step, k += s){
  92.       if(k >= N){
  93.         k -= N;
  94.       }
  95.       res.push_back(A[k]);
  96.     }
  97.   }
  98.   else{
  99.     for(i = bg, k =(moddw_L(bg,N)); i > ed; i += step, k += s){
  100.       if(k >= N){
  101.         k -= N;
  102.       }
  103.       res.push_back(A[k]);
  104.     }
  105.   }
  106.   return res;
  107. }
  108. string Slice(const string &A, const long long bg, const long long ed, const long long step){
  109.   const int N = A.size();
  110.   long long i;
  111.   long long k;
  112.   long long s;
  113.   string res;
  114.   if(N == 0){
  115.     return res;
  116.   }
  117.   s =(moddw_L(step,N));
  118.   assert(step != 0);
  119.   if(step > 0){
  120.     for(i = bg, k =(moddw_L(bg,N)); i < ed; i += step, k += s){
  121.       if(k >= N){
  122.         k -= N;
  123.       }
  124.       res += A[k];
  125.     }
  126.   }
  127.   else{
  128.     for(i = bg, k =(moddw_L(bg,N)); i > ed; i += step, k += s){
  129.       if(k >= N){
  130.         k -= N;
  131.       }
  132.       res += A[k];
  133.     }
  134.   }
  135.   return res;
  136. }
  137. #define main dummy_main
  138. int main(){
  139.   return 0;
  140. }
  141. #undef main
  142. int calc(const string &s){
  143.   int N = s.size();
  144.   int res = 1073709056;
  145.   int k;
  146.   for(k=(1);k<(N);k++){
  147.     if(N%k==0){
  148.       int WKqLrJHZ;
  149.       remove_reference<decltype( PalindromeCost(Slice(s,WKqLrJHZ,N,k)) )>::type QAAnbtfa;
  150.       int om7Ebh6q = 0;
  151.       if((0) > ((k)-1)){
  152.         QAAnbtfa = 0;
  153.       }
  154.       else{
  155.         for(WKqLrJHZ = 0; WKqLrJHZ <= (k)-1; WKqLrJHZ++){
  156.           if(om7Ebh6q == 0){
  157.             QAAnbtfa =  PalindromeCost(Slice(s,WKqLrJHZ,N,k)) ;
  158.             om7Ebh6q = 1;
  159.             continue;
  160.           }
  161.           QAAnbtfa +=  PalindromeCost(Slice(s,WKqLrJHZ,N,k)) ;
  162.         }
  163.         if(om7Ebh6q==0){
  164.           QAAnbtfa = 0;
  165.         }
  166.       }
  167.       chmin(res, QAAnbtfa);
  168.     }
  169.   }
  170.   return res;
  171. }
  172. class Solution{
  173.   public:
  174.   int minimumChanges(string s, int k){
  175.     int myTeyldV;
  176.     int i;
  177.     int j;
  178.     int N = s.size();
  179.     static long long cost[201][201];
  180.     static long long dp[201];
  181.     for(i=(0);i<(N);i++){
  182.       for(j=(i);j<(N);j++){
  183.         cost[i][j] = calc(s.substr(i,j-i+1));
  184.       }
  185.     }
  186.     dp[0] = 0;
  187.     for(i=(1);i<(N+1);i++){
  188.       dp[i] = 4611686016279904256LL;
  189.     }
  190.     for(myTeyldV=(0);myTeyldV<(k);myTeyldV++){
  191.       for(i=(N+1)-1;i>=(0);i--){
  192.         dp[i] = 4611686016279904256LL;
  193.         for(j=(0);j<(i);j++){
  194.           chmin(dp[i], dp[j] + cost[j][i-1]);
  195.         }
  196.       }
  197.     }
  198.     return dp[N];
  199.   }
  200. }
  201. ;
  202. // cLay version 20231031-1
  203.  
  204. // --- original code ---
  205. // #define main dummy_main
  206. // {}
  207. // #undef main
  208. // 
  209. // int calc(const string &s){
  210. //   int N = s.size(), res = int_inf, k;
  211. //   rep(k,1,N) if(N%k==0) res <?= sum[i,0,k]( PalindromeCost(Slice(s,i,N,k)) );
  212. //   return res;
  213. // }
  214. // 
  215. // class Solution {
  216. // public:
  217. //   int minimumChanges(string s, int k) {
  218. //     int i, j, N = s.size();
  219. //     static ll cost[201][201], dp[201];
  220. // 
  221. //     rep(i,N) rep(j,i,N) cost[i][j] = calc(s.substr(i,j-i+1));
  222. // 
  223. //     dp[0] = 0;
  224. //     rep(i,1,N+1) dp[i] = ll_inf;
  225. // 
  226. //     rep(k){
  227. //       rrep(i,N+1){
  228. //         dp[i] = ll_inf;
  229. //         rep(j,i) dp[i] <?= dp[j] + cost[j][i-1];
  230. //       }
  231. //     }
  232. // 
  233. //     return dp[N];
  234. //   }
  235. // };
  236.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
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 
Standard output is empty
https://ideone.com/O4l4WR
language:
C++ (gcc 8.3)
created:
197 days 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!