Submission #1777383

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}


signed main(){
  string S;
  cin>>S;
  int n = S.size();
  vector<int> U(S.size(),INF),D(S.size(),INF);
  for(int i=0;i<n;i++) if(S[i] == 'U') U[i] = 0;
  for(int i=0;i<n;i++) if(S[i] == 'D') D[i] = 0;
  
  for(int i=1;i<n;i++) Min(U[i], U[i-1]+1);
  //for(int i=1;i<n;i++) Min(D[i], D[i-1]+1);

  //for(int i=n-2;i>=0;i--) Min(U[i],U[i+1]+1);
  for(int i=n-2;i>=0;i--) Min(D[i],D[i+1]+1);
  
  int ans = 0;
  for(int i=0;i<n;i++){
    if(S[i] == 'U') {
      ans += (n-i-1);
      ans += i* (2);
    }
    if(S[i] == 'D') {
      ans += (n-i-1) * (2);
      ans += i;
    }
  }
  cout<<ans<<endl;

  return 0;
}

Submission Info

Judge Result