fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class S, class T> inline S min_L(S a,T b){
  5.   return a<=b?a:b;
  6. }
  7. inline int my_getchar_unlocked(){
  8.   static char buf[1048576];
  9.   static int s = 1048576;
  10.   static int e = 1048576;
  11.   if(s == e && e == 1048576){
  12.     e = fread_unlocked(buf, 1, 1048576, stdin);
  13.     s = 0;
  14.   }
  15.   if(s == e){
  16.     return EOF;
  17.   }
  18.   return buf[s++];
  19. }
  20. inline int rdLine_L(char c[]){
  21.   int i;
  22.   int sz = 0;
  23.   for(;;){
  24.     i = my_getchar_unlocked();
  25.     if(i=='\r'){
  26.       continue;
  27.     }
  28.     if(i=='\n'){
  29.       break;
  30.     }
  31.     if(i==EOF){
  32.       if(sz==0){
  33.         c[sz] = '\0';
  34.         return -1;
  35.       }
  36.       break;
  37.     }
  38.     c[sz++] = i;
  39.   }
  40.   c[sz]='\0';
  41.   return sz;
  42. }
  43. struct MY_WRITER{
  44.   char buf[1048576];
  45.   int s;
  46.   int e;
  47.   MY_WRITER(){
  48.     s = 0;
  49.     e = 1048576;
  50.   }
  51.   ~MY_WRITER(){
  52.     if(s){
  53.       fwrite_unlocked(buf, 1, s, stdout);
  54.     }
  55.   }
  56. }
  57. ;
  58. MY_WRITER MY_WRITER_VAR;
  59. void my_putchar_unlocked(int a){
  60.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  61.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  62.     MY_WRITER_VAR.s = 0;
  63.   }
  64.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  65. }
  66. inline void wt_L(char a){
  67.   my_putchar_unlocked(a);
  68. }
  69. inline void wt_L(int x){
  70.   int s=0;
  71.   int m=0;
  72.   char f[10];
  73.   if(x<0){
  74.     m=1;
  75.     x=-x;
  76.   }
  77.   while(x){
  78.     f[s++]=x%10;
  79.     x/=10;
  80.   }
  81.   if(!s){
  82.     f[s++]=0;
  83.   }
  84.   if(m){
  85.     my_putchar_unlocked('-');
  86.   }
  87.   while(s--){
  88.     my_putchar_unlocked(f[s]+'0');
  89.   }
  90. }
  91. inline void wt_L(unsigned x){
  92.   int s=0;
  93.   char f[10];
  94.   while(x){
  95.     f[s++]=x%10;
  96.     x/=10;
  97.   }
  98.   if(!s){
  99.     f[s++]=0;
  100.   }
  101.   while(s--){
  102.     my_putchar_unlocked(f[s]+'0');
  103.   }
  104. }
  105. inline void wt_L(long long x){
  106.   int s=0;
  107.   int m=0;
  108.   char f[20];
  109.   if(x<0){
  110.     m=1;
  111.     x=-x;
  112.   }
  113.   while(x){
  114.     f[s++]=x%10;
  115.     x/=10;
  116.   }
  117.   if(!s){
  118.     f[s++]=0;
  119.   }
  120.   if(m){
  121.     my_putchar_unlocked('-');
  122.   }
  123.   while(s--){
  124.     my_putchar_unlocked(f[s]+'0');
  125.   }
  126. }
  127. inline void wt_L(unsigned long long x){
  128.   int s=0;
  129.   char f[21];
  130.   while(x){
  131.     f[s++]=x%10;
  132.     x/=10;
  133.   }
  134.   if(!s){
  135.     f[s++]=0;
  136.   }
  137.   while(s--){
  138.     my_putchar_unlocked(f[s]+'0');
  139.   }
  140. }
  141. int WRITER_DOUBLE_DIGIT = 15;
  142. inline int writerDigit_double(){
  143.   return WRITER_DOUBLE_DIGIT;
  144. }
  145. inline void writerDigit_double(int d){
  146.   WRITER_DOUBLE_DIGIT = d;
  147. }
  148. inline void wt_L(double x){
  149.   const int d = WRITER_DOUBLE_DIGIT;
  150.   int k;
  151.   int r;
  152.   double v;
  153.   if(x!=x || (x==x+1 && x==2*x)){
  154.     my_putchar_unlocked('E');
  155.     my_putchar_unlocked('r');
  156.     my_putchar_unlocked('r');
  157.     return;
  158.   }
  159.   if(x < 0){
  160.     my_putchar_unlocked('-');
  161.     x = -x;
  162.   }
  163.   x += 0.5 * pow(0.1, d);
  164.   r = 0;
  165.   v = 1;
  166.   while(x >= 10*v){
  167.     v *= 10;
  168.     r++;
  169.   }
  170.   while(r >= 0){
  171.     r--;
  172.     k = floor(x / v);
  173.     if(k >= 10){
  174.       k = 9;
  175.     }
  176.     if(k <= -1){
  177.       k = 0;
  178.     }
  179.     x -= k * v;
  180.     v *= 0.1;
  181.     my_putchar_unlocked(k + '0');
  182.   }
  183.   if(d > 0){
  184.     my_putchar_unlocked('.');
  185.     v = 1;
  186.     for(r=(0);r<(d);r++){
  187.       v *= 0.1;
  188.       k = floor(x / v);
  189.       if(k >= 10){
  190.         k = 9;
  191.       }
  192.       if(k <= -1){
  193.         k = 0;
  194.       }
  195.       x -= k * v;
  196.       my_putchar_unlocked(k + '0');
  197.     }
  198.   }
  199. }
  200. inline void wt_L(const char c[]){
  201.   int i=0;
  202.   for(i=0;c[i]!='\0';i++){
  203.     my_putchar_unlocked(c[i]);
  204.   }
  205. }
  206. inline void wt_L(string &x){
  207.   int i=0;
  208.   for(i=0;x[i]!='\0';i++){
  209.     my_putchar_unlocked(x[i]);
  210.   }
  211. }
  212. template<class S, class T> inline S chmin(S &a, T b){
  213.   if(a>b){
  214.     a=b;
  215.   }
  216.   return a;
  217. }
  218. int N;
  219. char S[1000000+2];
  220. int dp1[1000000+2];
  221. int dp2[1000000+2];
  222. int main(){
  223.   int i;
  224.   N =rdLine_L(S);
  225.   dp2[0] = 2;
  226.   for(i=(0);i<(N);i++){
  227.     dp1[i+1] = dp2[i+1] = 1073709056;
  228.     if(S[i]==' ' || 'a' <= S[i]  &&  S[i] <= 'z'){
  229.       chmin(dp1[i+1], dp1[i] + 1);
  230.       chmin(dp2[i+1], dp2[i] + 2);
  231.     }
  232.     if(S[i]==' ' || 'A' <= S[i]  &&  S[i] <= 'Z'){
  233.       chmin(dp1[i+1], dp1[i] + 2);
  234.       chmin(dp2[i+1], dp2[i] + 1);
  235.     }
  236.     chmin(dp1[i+1], dp2[i+1] + 2);
  237.     chmin(dp2[i+1], dp1[i+1] + 2);
  238.   }
  239.   wt_L(min_L(dp1[N], dp2[N]));
  240.   wt_L('\n');
  241.   return 0;
  242. }
  243. // cLay varsion 20201031-1
  244.  
  245. // --- original code ---
  246. // int N;
  247. // char S[1d6+2];
  248. // int dp1[1d6+2], dp2[1d6+2];
  249. // {
  250. //   N = rdLine(S);
  251. //   dp2[0] = 2;
  252. //   rep(i,N){
  253. //     dp1[i+1] = dp2[i+1] = int_inf;
  254. //     if(S[i]==' ' || 'a' <= S[i] <= 'z'){
  255. //       dp1[i+1] <?= dp1[i] + 1;
  256. //       dp2[i+1] <?= dp2[i] + 2;
  257. //     }
  258. //     if(S[i]==' ' || 'A' <= S[i] <= 'Z'){
  259. //       dp1[i+1] <?= dp1[i] + 2;
  260. //       dp2[i+1] <?= dp2[i] + 1;
  261. //     }
  262. //     dp1[i+1] <?= dp2[i+1] + 2;
  263. //     dp2[i+1] <?= dp1[i+1] + 2;
  264. //   }
  265. //   wt(min(dp1[N], dp2[N]));
  266. // }
  267.  
Success #stdin #stdout 0s 4228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7rlH50
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!