fork download
copy 
  1.     public int minCost(String s, int[] cost, int k) {
  2.         int n = s.length();
  3.  
  4.         final int CCC = 100;
  5.         final int L = 6;
  6.         final int INF = 1000 * 1000 * 1000 + 500;
  7.         int[][][][] with = new int[2][k+2][n+2][L];
  8.         int[][][][] without = new int[2][k+2][n+2][L];
  9.         for(int a = 0; a < 2; ++a)
  10.             for(int b = 0; b <= k; ++b)
  11.                 for(int c = 0; c <= n; ++c)
  12.                     for(int d = 0; d < L; ++d)
  13.                         with[a][b][c][d] = without[a][b][c][d] = INF;
  14.         for(int d = 0; d < L; ++d)
  15.             with[0][0][0][d] = without[0][0][0][d] = 0;
  16.         for(int position = 0; position < n; ++position) {
  17.             int letter = s.charAt(position) - 'a';
  18.             for(int b = 0; b <= k; ++b)
  19.                 for(int c = 0; c <= n; ++c)
  20.                     for(int d = 0; d < L; ++d) {
  21.                         with[1][b][c][d] = without[1][b][c][d] = INF;
  22.                         for(int d2 = 0; d2 < L; ++d2) {
  23.                             if(d != d2 || c == 0)
  24.                                 without[0][b][c][d2] = min(without[0][b][c][d2], with[0][b][c][d]);
  25.                             if(c == 0)
  26.                                 with[0][b][c][d2] = min(with[0][b][c][d2], without[0][b][c][d]);
  27.  
  28.                         }
  29.                     }
  30.             for(int b = 0; b <= k; ++b)
  31.                 for(int c = 0; c <= n; ++c)
  32.                     for(int d = 0; d < L; ++d) {
  33.                         int old = with[0][b][c][d];
  34.                         if(d == letter)
  35.                             with[1][b][c+1][d] = min(with[1][b][c+1][d], old - CCC*position + cost[position]);
  36.                         if(d != letter && c-1 >= 0)
  37.                             with[1][b][c-1][d] = min(with[1][b][c-1][d], old + CCC*position + cost[position]);
  38.                         with[1][b+1][c][d] = min(with[1][b+1][c][d], old); // not taking it
  39.  
  40.                         old = without[0][b][c][d];
  41.                         if(d == letter && c-1 >= 0)
  42.                             without[1][b][c-1][d] = min(without[1][b][c-1][d], old + CCC*position + cost[position]);
  43.                         if(d != letter)
  44.                             without[1][b][c+1][d] = min(without[1][b][c+1][d], old - CCC*position + cost[position]);
  45.                         without[1][b+1][c][d] = min(without[1][b+1][c][d], old); // not taking it
  46.                     }
  47.             for(int b = 0; b <= k; ++b)
  48.                 for(int c = 0; c <= n; ++c)
  49.                     for(int d = 0; d < L; ++d) {
  50.                         with[0][b][c][d] = with[1][b][c][d];
  51.                         without[0][b][c][d] = without[1][b][c][d];
  52.                     }
  53.         }
  54.         int ans = INF;
  55.         for(int b = 0; b <= k; ++b)
  56.             for(int d = 0; d < L; ++d) {
  57.                 ans = min(ans, with[0][b][0][d]);
  58.                 ans = min(ans, without[0][b][0][d]);
  59.             }
  60.         if(ans == INF) ans = -1;
  61.         return ans;
  62.     }
  63.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:5: error: expected unqualified-id before 'public'
     public int minCost(String s, int[] cost, int k) {
     ^
stdout
copy 
Standard output is empty
https://ideone.com/KhwmSW
SRM 680 div1-hard
language:
C++14 (gcc 8.3)
created:
9 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!