akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned x){
  int s=0;
  char f[10];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(double x){
  printf("%.15f",x);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
inline void wt_L(string &x){
  int i=0;
  for(i=0;x[i]!='\0';i++){
    putchar_unlocked(x[i]);
  }
}
long long N;
long long A;
long long B;
int main(){
  long long res1;
  long long res2;
  rd(N);
  rd(A);
  rd(B);
  if((B-A)%2==0){
    wt_L((B-A)/2);
    wt_L('\n');
    return 0;
  }
  res1 = A + (B-A-1) / 2;
  A = N + 1 - A;
  B = N + 1 - B;
  swap(A,B);
  res2 = A + (B-A-1) / 2;
  wt_L(min_L(res1, res2));
  wt_L('\n');
  return 0;
}
// cLay varsion 20191227-1

// --- original code ---
// ll N, A, B;
// {
//   ll res1, res2;
//   rd(N,A,B);
//   if((B-A)%2==0) wt((B-A)/2), return 0;
//   res1 = A + (B-A-1) / 2;
//   A = N + 1 - A;
//   B = N + 1 - B;
//   swap(A,B);
//   res2 = A + (B-A-1) / 2;
//   wt(min(res1,res2));
// }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    int k;
    cin>>k;
    string s;
    cin>>s;
    for(int i = 0 ; i < min((int)k,(int)s.length()); i ++){
        cout<<s[i];
    }
    if(k < s.length()){
        cout<<"...";
    }
}


Measured memory_bytes: 3604
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (long long)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
const int MAXN    = 2e5+9;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	double n;
	cin >> n;
	cout << fixed << setprecision(15) << (n/3)*(n/3)*(n/3);


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
using namespace std;
string str;
int N;

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> str >> N;
  bool ans[2] = {false, false};
  stack<int> st;
  int i = 0;
  int product = 0;
  while(i < str.length()){
    if( isdigit(str[i]) ){
      st.push(str[i] - '0');
    }else if(str[i] == '*'){
      i++;
      int top = st.top(); st.pop();
      st.push(top*(str[i] - '0'));
    }
    i++;
  }
  while(!st.empty()){
    product += st.top();
    st.pop();
  }
  if(product == N) ans[0] = true;

  product = str[0] - '0';
  i = 2;
  while(i < str.length()){
    if( isdigit(str[i]) ){
      if(str[i-1] == '*'){
        product *= (str[i] - '0');
      }else{
        product += str[i] - '0';
      }
    }
    i++;
  }
  if(product == N){
    ans[1] = true;
  }
  if(ans[1] && ans[0]){
    cout << 'U' << endl;
  }else if(ans[0]){
    cout << 'M' << endl;
  }else if(ans[1]){
    cout << 'L' << endl;
  }else{
    cout << 'I' << endl;
  }
}

Measured memory_bytes: 3228
// https://atcoder.jp/contests/abc176/tasks/abc176_d

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
template <typename T>
using VV = V<V<T>>;
using VVL = VV<ll>;
template <typename T>
using VVV = VV<V<T>>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
using asc_pq = priority_queue<T, V<T>, greater<T>>;

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline ll len(V<T> arr) {
  return arr.size();
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}

const ll INF = 1e18;

void solve();

#ifndef TEST
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void solve() {
  ll H, W;
  cin >> H >> W;

  ll ch, cw;
  cin >> ch >> cw;
  ch--, cw--;

  ll dh, dw;
  cin >> dh >> dw;
  dh--, dw--;

  V<string> mat(H);
  rep(h, H) cin >> mat[h];

  VVL costs(H, VL(W, INF));
  costs[ch][cw] = 0;

  asc_pq<P<ll, PL>> pq;
  pq.emplace(0, make_pair(ch, cw));

  auto is_inside = [&](ll h, ll w) {
    return 0 <= h && h < H && 0 <= w && w < W;
  };

  auto is_street = [&](ll h, ll w) { return mat[h][w] == '.'; };

  while (!pq.empty()) {
    auto [cost, loc] = pq.top();
    pq.pop();
    auto [h, w] = loc;

    for (int i = 0; i < 4; ++i) {
      ll nh = h + dy[i];
      ll nw = w + dx[i];

      if (is_inside(nh, nw) && is_street(nh, nw) &&
          chmin(costs[nh][nw], cost)) {
        pq.emplace(cost, make_pair(nh, nw));
      }
    }

    for (ll dx = -2; dx <= 2; ++dx) {
      for (ll dy = -2; dy <= 2; ++dy) {
        ll nh = h + dy;
        ll nw = w + dx;

        if (is_inside(nh, nw) && is_street(nh, nw) &&
            chmin(costs[nh][nw], cost + 1)) {
          pq.emplace(cost + 1, make_pair(nh, nw));
        }
      }
    }
  }

  ll res = costs[dh][dw];
  if (res == INF) drop(-1);
  cout << res << "\n";
}


Measured memory_bytes: 12656
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

typedef long long ll;

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    vector<int> c(n-1);
    for (int i = 0; i < n-1; i++) {
        cin >> c[i];
    }

    for (int i = 0; i < n; i++) {
        a[i]--;
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        ans += b[i];
    }

    for (int i = 0; i < n - 1; i++) {
        if (a[i]+1 == a[i+1]) {
            ans += c[a[i]];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;

int main(){
    int n, k;
    while(cin >> n >> k){
        if(n + k == 0)  break;
        string x[n];
        for(int i = 0; i < n; i++)  cin >> x[i];
        sort(x, x+n);

        set<int> ans;
        do{
            string tmp = "";
            for(int i = 0; i < k; i++)  tmp += x[i];
            ans.insert(stoi(tmp));
        }while(next_permutation(x, x+n));

        cout << ans.size() << endl;
    }
    return 0;
}


Measured memory_bytes: 3188
def factorize(n):
    if n == 1:
        return
    
    tmp = n

    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in fact:
                fact[i] = 1
            else:
                fact[i] = 0
         
    if tmp != 1:
        if tmp in fact:
            fact[tmp] = 1
        else:
            fact[tmp] = 0
    
    if len(fact) == 0:
        if N in fact:
            fact[N] = 1
        else:
            fact[N] = 0

A, B = list(map(int, input().split()))
fact = {}

factorize(A)
factorize(B)

cnt = 1

for val in fact.values():
    if val == 1:
        cnt += 1

print(cnt)

Measured memory_bytes: 63388
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const double pi = acos(-1);

int main() {
    ll n;
    cin >> n;

    vl v(4);
    rep(i, n) {
        string s;
        cin >> s;
        if(s == "AC") {
            v[0]++;
        }
        else if(s == "WA") {
            v[1]++;
        }   
        else if(s == "TLE") {
            v[2]++;
        }
        else if(s == "RE") {
            v[3]++;
        }
    }

    cout << "AC x " << v[0] << "\n";
    cout << "WA x " << v[1] << "\n";
    cout << "TLE x " << v[2] << "\n";
    cout << "RE x " << v[3] << "\n";
    
    re0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;


class union_find{
public:
  int uf[100010];
  union_find(int n){
    for(int i=0;i<n;i++){
      uf[i]=-1;
    }
  }
  int root(int i)
  {
    return uf[i]<0?i:uf[i]=root(uf[i]);
  }
  int unite(int i,int j)
  {
    if(-uf[i]<-uf[j]){
      uf[i]=j;
      return j;
    }
    else if(-uf[i]>-uf[j]){
      uf[j]=i;
      return i;
    }
    else{
      uf[i]=j;
      uf[j]--;
      return j;
    }
  }
};

int main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  vector<long long> d(n);
  for(int i=0;i<n;i++){
    scanf("%lld",&d[i]);
  }
  vector<pair<long long,pair<int,int> > > E(m);
  for(int i=0;i<m;i++){
    scanf("%d%d%lld",&(E[i].second.first),&(E[i].second.second),&(E[i].first));
    E[i].second.first--,E[i].second.second--;
  }
  sort(E.begin(),E.end());
  vector<int> A(2*n-1,-1),B(2*n-1,-1);
  vector<long long> X(2*n-1),Y(2*n-1),R(2*n-1),L(2*n-1);
  for(int i=0;i<n;i++){
    X[i]=d[i],Y[i]=0;
  }
  int t=n;
  union_find uf(n);
  vector<int> P(n);
  for(int i=0;i<n;i++)P[i]=i;
  vector<bool> use(m);
  for(int s=0;s<m;s++){
    int a=E[s].second.first,b=E[s].second.second;
    long long c=E[s].first;
    a=uf.root(a);
    b=uf.root(b);
    if(a!=b){
      int rt=uf.unite(a,b);
      X[t]=X[P[a]]+X[P[b]];
      Y[t]=c;
      R[t]=P[a];
      L[t]=P[b];
      P[rt]=t;
      t++;
      use[s]=true;
    }
    else{
      use[s]=false;
    }
  }
  queue<int> Q;
  Q.push(2*n-2);
  int ans=0;
  vector<long long> q(n);
  while(!Q.empty()){
    int i=Q.front();
    Q.pop();
    //printf("%d %lld %lld\n",i,X[i],Y[i]);
    if(X[i]>=Y[i]){
      queue<int> Q2;
      Q2.push(i);
      while(!Q2.empty()){
	int j=Q2.front();
	Q2.pop();
	if(j<n){
	  q[j]=X[i];
	}
	else{
	  Q2.push(R[j]);
	  Q2.push(L[j]);
	}
      }
    }
    else{
      Q.push(R[i]);
      Q.push(L[i]);
      ans++;
    }
  }
  for(int s=0;s<m;s++){
    if(!use[s]){
      if(E[s].first>min(q[E[s].second.first],q[E[s].second.second])){
	ans++;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}



Measured memory_bytes: 12032
n,p=map(int,input().split())

i=2
gcd=1
if(n>40):
    print(1)
elif(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            #print(i)
            gcd*=i
            p/=(i**n)
            i-=1
        i+=1
        
    print(gcd)

Measured memory_bytes: 3064
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
else :
    mods = deque(mod1 + mod0 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()

print(*ans)



Measured memory_bytes: 100364
#include <bits/stdc++.h>
    using namespace std;

    int main()
    {
        int n, m;
        cin >> n >> m;
        int arr[n], sum = 0;
        for(int i = 0; i < n; i++)
        {
          cin >> arr[i];
          sum += arr[i];
        }
        double bound = (double)sum/(m*4);
        int c = 0;
        for(int i = 0; i < n; i++)
        {
            if(arr[i] >= bound)
              c++;
        }
        if(c >= m)
          cout << "Yes";
        else
          cout << "No";
     }


Measured memory_bytes: 256
#include<stdio.h>
#define N 102

#define siro 0
#define hai 1
#define kuro 2

int ha[N],owa[N];
int o;
int time;
int iro[N];
int M[N][N];
void S(int);
int main(){
  int i,j,k,n,M2;
  
  scanf("%d",&o);
  
  for(i=1;i<=o;i++){
    for(j=1;j<=o;j++){
      M[i][j]=0;
    }
  }
  for(i=1;i<=o;i++){
    scanf("%d%d",&n,&k);
    for(j=1;j<=k;j++){ 
      scanf("%d",&M2);
      M[n][M2]=1;
    }
  }
  for(i=1;i<=o;i++){
    iro[i]=siro;
  }
  for(i=1;i<=o;i++){
    if(iro[i]==siro){
      S(i);
    }
  }
  for(i=1;i<=o;i++){
    printf("%d %d %d\n",i,ha[i],owa[i]);
  }
  return 0;
}
void S(int s){
  int j;
  iro[s]=hai;
  
  ha[s]=++time;
  
  for(j=1;j<=o;j++){ 
    if (M[s][j]==0) continue;
    if(iro[j]==siro)S(j);
  }
   owa[s]=++time;
  iro[s]=kuro;
 
}



Measured memory_bytes: 2112
def f(i, X):
    if i == 0:
        return 1

    elif X == 1:
        return 0

    elif X <= 1 + a[i-1]:
        return f(i-1, X-1)

    elif X == 2 + a[i-1]:
        return p[i-1] + 1

    elif X <= 2 + 2 * a[i-1]:
        return f(i-1, X-2-a[i-1]) + 1 + p[i-1]

    else:
        return p[i]

N, X = map(int, input().split())
a = [1]
p = [1]
for i in range(N):
    a.append(2 * a[-1] + 3)
    p.append(2 * p[-1] + 1)

print(f(N, X))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;

#define pb     push_back
#define mp     make_pair
#define all(v) v.begin() , v.end()
#define allr(v) v.rbegin(), v.rend()
#define forc(c,it) for(__typeof(c.begin()) it = c.begin(); it != c.end(); it++)
const ll INF =  0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAX = 2e5+5;

int d,n, k,  ans;
int cnt[MAX];
set<int> s;
vector<int> temp;

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	scanf("%d %d" , &n, &k);
	for(int i = 0 ; i < n ; i++){
		scanf("%d", &d);
		s.insert(d);
		cnt[d]++;
	}

	forc(s, it){
		temp.pb(cnt[*it]);
	}

	sort(all(temp));
	for(int i = temp.size() - 1 ; i >= 0 ; i--){
		k--;
		if(k < 0)
			ans += temp[i];
	}

	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 11512
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <set>
#include <string>
#include <math.h>
#include <map>
#include <climits>
#include <iomanip>


#define forn(i, n) for (int i = 0; i < int(n); i++)

#define ll long long

using namespace std;

void A();
void B();
void C();
void D();
void E();
void F();

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	C();


}

void A() {
	int n;
	cin >> n;

	double cir = n * 2 * 3.14159265358979323846;
	cout << setprecision(8) << cir << endl;
}
 
void B() {
	

	int n, m;
	cin >> n >> m;

	int sum = 0;
	forn(i, m) {
		int ss;
		cin >> ss;
		sum += ss;
	}

	if (sum > n) {
		cout << -1;
	}
	else {
		cout << (n - sum);
	}

	
}

void C() {
	int n;
	cin >> n;
	vector<int> occ(n, 0);

	forn(i, n-1) {

		int tt;
		cin >> tt;
		occ[tt - 1]++;

	}

	forn(i, n) {
		cout << occ[i] << endl;
	}

}

void D() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {

		int N;
		cin >> N;


		int result = 0;

		cout << "Case #" << t << ": ";

		cout << result << endl;

	}
}

void E() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {

		int N;
		cin >> N;


		int result = 0;

		cout << "Case #" << t << ": ";

		cout << result << endl;

	}
}

void F() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {

		int N;
		cin >> N;


		int result = 0;

		cout << "Case #" << t << ": ";

		cout << result << endl;

	}
}



Measured memory_bytes: 3968
package main

import "fmt"

func main() {
	var s1, s2 string
	fmt.Scanf("%s", &s1)
	fmt.Scanf("%s", &s2)

	same := true
	for i := 0; i < 3; i++ {
		if s1[i] != s2[2-i] {
			same = false
		}
	}
	if same {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
#include<iostream>
using namespace std;

int main(){
  int N; cin>>N;
  int ans=0;
  int h[20];
  bool x=true;
  for(int i=0;i<N;i++){
    cin>>h[i];
  }
  for(int i=0;i<N;i++){
    x=true;
    for(int j=0;j<=i;j++){
      if(h[i]-h[j]<0){
        x=false;
      }
    }
    if(x){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
N = input()
K = int(input())
L = len(N)

S = [ord(N[i]) - ord('0') for i in range(L)]

dp0 = [[0 for _ in range(K+1)] for _ in range(L)]
dp1 = [[0 for _ in range(K+1)] for _ in range(L)]

dp0[0][0] = 1
dp0[0][1] = S[0]-1
dp1[0][0] = 0
dp1[0][1] = 1

for i in range(1, L):
	for j in range(K+1):
		if j == 0:
			dp0[i][j] = dp0[i-1][j]
			dp1[i][j] = dp1[i-1][j]
		else:
			dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j] 
			if S[i] > 0:
				dp0[i][j] = dp0[i][j] + dp1[i-1][j-1]*(S[i]-1) + dp1[i-1][j]
				
			dp1[i][j] = dp1[i-1][j-(S[i]>0)]
	
print(dp0[L-1][K] + dp1[L-1][K])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c;
    cin>>a>>b>>c;
    if(a==b && a==c && b==c && c==a)
    {
        cout<<"Yes"<<endl;

    }
    else
    {
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
	int A,B,sum;
	cin >> A >> B ;
	
	if(A-1 > B){
    	sum = 2*A - 1;
    }
	else if(A-1 == B){
    	sum = A + B;
    }
	else if(B-1 > A){
    	sum = 2*B - 1;
    }
	else if(B-1 == A){
    	sum = A + B;
    }
  	else if(A = B){
    	sum = A + B;
    }
  
  	cout << sum <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> a(M),b(M);
  for(int i=0; i<M; i++){
    cin >> a.at(i) >> b.at(i);
  }
  vector<int> r(N);
  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      if(a.at(j)==i+1 || b.at(j)==i+1){
        r.at(i)++;
      }
    }
    cout << r.at(i) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;

int KnapSack(int W, vector<int> val, vector<int> wt, int n) {
	
	vector<vector<int>>  K(n + 1,vector<int>(W + 1));
	for (int i = 0; i <= n; i++) {
		for (int w = 0; w <= W; w++) {
			if (i == 0 || w == 0)
				K[i][w] = 0;
			else if (wt[i - 1] <= w)
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
			else
				K[i][w] = K[i - 1][w];
		}
	}

	return K[n][W];
}

signed main() {
	int n, Cap;
	cin >> n >> Cap;

	vector<int> Values(n);
	vector<int> Weights(n);
	for (int i = 0; i < n; i++) {
		cin >> Weights[i] >> Values[i];
	}
	cout << KnapSack(Cap, Values, Weights, n) << endl;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A[100010], B[100010];
    rep(i,0,N+1) cin >> A[i];
    rep(i,0,N) cin >> B[i];
    ll ans1 = 0;
    ll a2[100010];
    rep(i,0,N+1) a2[i] = A[i];
    rep(i,0,N){
        if(a2[i] >= B[i]){
            ans1 += B[i];
        }else{
            ans1 += a2[i];
            ll diff = B[i] - a2[i];
            a2[i] = 0;
            if(diff >= a2[i+1]){
                ans1 += a2[i+1];
                a2[i+1] = 0;
            }else{
                ans1 += diff;
                a2[i+1] -= diff;
            }
        }
    }

    ll ans2 = 0;
    rep(i,0,N+1) a2[i] = A[i];
    rrep(i,N-1,0){
        if(a2[i+1] >= B[i]){
            ans2 += B[i];
        }else{
            ans2 += a2[i+1];
            ll diff = B[i] - a2[i+1];
            a2[i+1] = 0;
            if(diff >= a2[i]){
                ans2 += a2[i];
                a2[i] = 0;
            }else{
                ans2 += diff;
                a2[i] -= diff;
            }
        }
    }
    ll ans = max(ans1, ans2);
    print(ans);


 


    
}

Measured memory_bytes: 2560
n, m = map(int, input().split())
h = list(map(int, input().split()))
x = [0 for i in range(n)]
for f in range(m):
  a, b = map(int, input().split())
  x[a-1] = max(x[a-1], h[b-1])
  x[b-1] = max(x[b-1], h[a-1])
ans = 0
for j in range(n):
  if x[j] < h[j]:
    ans += 1
print(ans)    

Measured memory_bytes: 20120
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int main()
{
    int n;
    std::cin >> n;

    std::unordered_map<std::string, bool> m;

    std::string past_string;
    std::cin >> past_string;
    m[past_string] = true;
    for (int i = 1; i < n; i++) {
        std::string temp;
        std::cin >> temp;

        if (m[temp] || past_string.back() != temp[0]) {
            std::cout << "No" << std::endl;
            return 0;
        }

        m[temp] = true;
        past_string = temp;
    }

    std::cout << "Yes" << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> D(N);
  for (int i = 0; i<N; i++){
    cin >> D.at(i);
  }
  
  vector<int> A(100);
  
  for(int i=0; i<N; i++){
    int tmp = D.at(i);
    A.at(tmp-1) = 1;
  }
  
  int ans=0;
  for(int i=0; i<100; i++){
    ans += A.at(i);
  }
  
  cout << ans << endl;
}

  
  

  
  // int型の2次元配列(3×4要素の)の宣言
  //vector<vector<int>> data(3, vector<int>(4));

  // 入力 (2重ループを用いる)
  //for (int i = 0; i < 3; i++) {
    //for (int j = 0; j < 4; j++) {
      //cin >> data.at(i).at(j);
    //}
  //}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int perm(string p){
  int ret = 1;
  string dummyp = p;
  sort(dummyp.begin(),dummyp.end());
  
  do{
    if(dummyp == p) return ret;
    ret++;
  }while(next_permutation(dummyp.begin(),dummyp.end()));
}

int main(){
  int n;
  string p,q;
  cin >> n;
  for(int i=0;i<n;i++){
    char c; cin >> c; p += c;
  }
  for(int i=0;i<n;i++){
    char c; cin >> c; q += c;
  }
  
  cout << abs(perm(p) - perm(q)) << endl;
  
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;++i)
#define END(x) (*(x.end()-1))
#define INF INT_MAX

using namespace std;
typedef long long ll;

int main(void){
    int K;
    cin>>K;
    ll ans=0;
    for(int i=1;i<=K;++i){
        for(int j=1;j<=K;++j){
            for(int k=1;k<=K;++k){
                ans+=gcd(gcd(i,j),k);
            }
        }
    }
    cout<<ans;
}
/*

*/

Measured memory_bytes: 3632
a,b,c,k = map(int,input().split())
sum = 0

if k >= a:
    sum += a
else:
    sum += k
    print(sum)
    exit()

k -= a+b
if k <= 0:
    print(sum)
    exit()

if k >= c:
    sum -= c
else:
    sum -= k

print(sum)

Measured memory_bytes: 9192
#include <bits/stdc++.h>

using namespace std;

int main(){
    string n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n.size();i++){
        sum+=n[i]-'0';
    }
    if(stoi(n)%sum==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

#define INF 1000000007

int main(){
    int n, k;
    std::cin >> n >> k;

    std::vector<int> x(n);
    for(int i = 0; i < n; ++i){
        std::cin >> x.at(i);
    }

    auto left = x.begin();
    int ans = INF, limit = n - k + 1;
    for(int j = 0; j < limit; ++j){
        auto right = left + k - 1;
        ans = std::min(ans, *right - *left + std::min(std::abs(*left), std::abs(*right)));
        ++left;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, a[55], ans;
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	bool flag = true;
	while (flag) {
		flag = false;
		rep(i, n) {
			if (a[i] >= n) {
				int memo = (a[i] - n) / n + 1;
				ans += memo;
				a[i] -= memo * n;
				rep(j, n) {
					if (i != j)a[j] += memo;
				}
				flag = true;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
using System;

namespace AOJ.ITP
{
    public class Print_A_Rectangle
    {
        public static void Main()
        {
            while (true)
            {
                var input = Console.ReadLine().Split(' ');
                int h = int.Parse(input[0]);
                int w = int.Parse(input[1]);
                if (h <= 0 || w <= 0) { break; }

                string line = new string('#', w);
                for (int i = 1; i <= h; i++)
                {
                    Console.WriteLine(line);
                }
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 7292
#include <iostream>

using namespace std;

int main() {
    int M,scale[10];
    scale[0]=1;
    for(int i=1;i<10;i++){
    scale[i] = scale[i-1]*2;
    }
    while(cin >> M){
    int i=0;
    int count=2;
    while(true){
        if(M==0) break;
        if(M % count!=0){
            M -= scale[i];
            if(M != 0){
            cout << scale[i] << " ";
            }
            else{
            cout << scale[i] <<endl;
            }
        }
        i++;
        count *= 2;
    }
    }
}

Measured memory_bytes: 1160
#include <iostream>
using namespace std;

int main()
{
   string word;
   long long z=0,n;
   cin>>n;
   cin>>word;
   for(int i=0;i<n;i++)
   {
       if(word[i]=='A'&&word[i+1]=='B'&&word[i+2]=='C'){z++;}
   }
   cout<<z;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a);i<(b);++i)
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const ll MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795;

int main()
{
	int r, g;
	cin >> r >> g;
	cout << r + 2 *(g - r) << endl;
	return 0;
}

Measured memory_bytes: 256
x,n=map(int,input().split())
if n==0:
    print(x)
else:
    a=list(map(int,input().split()))
    for i in range(n//2+1):
        if not(x-i in a):
            print(x-i)
            exit()
        if not(x+i in a):
            print(x+i)
            exit()
    print(x-1-n//2)

Measured memory_bytes: 9060
#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  while (cin >> n) {
    static int a[2 * 100000 + 10];
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    static int b[2 * 100000 + 10];
    int x = n / 2 - 1;
    int y = n / 2;
    for (int i = 0; i < n; ++i) {
      if (i % 2) b[x--] = a[i];
      else b[y++] = a[i];
    }
    if (n % 2 == 0) {
      for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << b[i];
      }
      cout << endl;
    } else {
      for (int i = n - 1; 0 <= i; --i) {
        if (i - (n - 1)) cout << ' ';
        cout << b[i];
      }
      cout << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n;
mii f,mnIndex;
ll ans[N];

int main(){
    readi(n);
    lp(i,1,n){
        int x;
        readi(x);
        ++f[x];
        if(!mnIndex[x]) mnIndex[x] = i;
    }

    f[0] = 1;
    for(auto it = f.rbegin(); (*it).f; ++it){
        auto prv = it;
        ++prv;
        ans[mnIndex[(*it).f]] += 1ll * ((*it).f - (*prv).f) * (*it).s;
        (*prv).s += (*it).s;
        mnIndex[(*prv).f] = min(mnIndex[(*prv).f], mnIndex[(*it).f]);
    }

    lp(i,1,n) printf("%lld\n", ans[i]);
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 11264
// include
#include <iostream>
#include <utility>  // pair用
#include <list>  // 頂点リスト pairリスト

// typedef
  
// macro
#define REP(index, num) for (auto index = 0; index < num; index++)

using namespace std;

const int CountPaths(const int currentNode, list<pair<int, int>> nodesPairsFromPath, list<int> inNodesList);
const bool IsVisited(const int node, list<int> inNodesList);

int main()
{
  int N, M;
  list<pair<int, int>> nodesPairsFromPath;
  list<int> nodesList;

  cin >> N >> M;

  REP(mId, M)
  {
    int a, b;
    cin >> a >> b;
    nodesPairsFromPath.push_back(make_pair(a, b));
    nodesList.push_back(a);
    nodesList.push_back(b);
  }

  // 重複要素消す
  nodesList.sort();
  nodesList.unique();

  // 深さ優先探索
  nodesList.remove(1);
  cout << CountPaths(1, nodesPairsFromPath, nodesList) << endl;

}

const int CountPaths(const int currentNode, list<pair<int, int>> inNodesPairsFromPath, list<int> inNodesList)
{
  int count = 0;

  // 全頂点訪問済みなら1を返す
  if (inNodesList.size() == 0)
    return 1;

  // 頂点リスト分探索する
  for (auto nItr = inNodesList.begin(); nItr != inNodesList.end(); ++nItr)
  {
    // 現在の頂点に対応する頂点を探す
    for (auto npItr = inNodesPairsFromPath.begin(); npItr != inNodesPairsFromPath.end(); ++npItr)
    {
      int a = (*npItr).first;
      int b = (*npItr).second;
      if (a == currentNode)
      {
        // bが訪問済みの頂点なら飛ばす
        if (IsVisited(b, inNodesList))
          continue;

        auto cpInNodesList = inNodesList;
        cpInNodesList.remove(b);
        *npItr = make_pair(-1, -1);  // 使い終わった辺は捨てる
        count += CountPaths(b, inNodesPairsFromPath, cpInNodesList);
      }
      else if (b == currentNode)
      { 
        // aが訪問済みの頂点なら飛ばす
        if (IsVisited(a, inNodesList))
          continue;

        auto cpInNodesList = inNodesList;
        cpInNodesList.remove(a);
        *npItr = make_pair(-1, -1); // 使い終わった辺は捨てる
        count += CountPaths(a, inNodesPairsFromPath, cpInNodesList);
      }
    }

  }

  return count;
}

const bool IsVisited(const int node, list<int> inNodesList)
{
  for (auto nItr = inNodesList.begin(); nItr != inNodesList.end(); ++nItr)
  {
    if ((*nItr) == node) return false;
  }

  return true;  // リストになければ訪問済み
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)

int main() {
	ll A, B, C, X, Y; cin >> A >> B >> C >> X >> Y;
	ll v1 = X * A + Y * B;
	ll v2 = min(X, Y) * 2 * C + abs(X - Y) * ((X >= Y) ? A : B);
	ll v3 = max(X, Y) * 2 * C;
	cout << min(v3, min(v1, v2)) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    while(1){
        int h,w;
        cin >> h >> w;
        if(h==0&&w==0) break;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

struct UnionFind {
	vector<int> d;
	UnionFind(int n = 0): d(n, -1) {}
	int find(int x) {
		if (d[x] < 0) return x;
		return d[x] = find(d[x]);
	}
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return false;
		if (d[x] > d[y]) swap(x, y);
		d[x] += d[y];
		d[y] = x;
		return true;
 	}
 	bool same(int x, int y) {
 		return find(x) == find(y);
	}
	int size(int x) {
		return -d[find(x)];
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	
	UnionFind uf(n);
	
	int ans = n - 1;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		if (uf.same(a, b) == false) {
			uf.unite(a, b);
			ans--;
		}
	}
	
	cout << ans << '\n';
	
	return 0;
}

Measured memory_bytes: 3744
#include <cstdio>

#define min(a, b) (a < b ? a : b)

int main()
{
    int no_of_operations, k;
    scanf("%d %d", &no_of_operations, &k);

    int value = 1;
    while(no_of_operations--)
        value += min(k, value);


    printf("%d\n", value);
    return 0;
}

Measured memory_bytes: 128
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

//constexpr int inf = 2147483647;
//constexpr int64_t inf64 = 9223372036854775807;
//constexpr int mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int d;
  cin >> d;

  if (d == 25) cout << "Christmas" << endl;
  if (d == 24) cout << "Christmas Eve" << endl;
  if (d == 23) cout << "Christmas Eve Eve" << endl;
  if (d == 22) cout << "Christmas Eve Eve Eve" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
  #define debug(x) cerr << #x << ": " << x << endl;
#else
  #define debug(x)
#endif

int main() {
  cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);

  ll N;
  cin >> N;

  vpll vl, vr;
  vll xmin(N, 0), xlast(N, 0);
  rep(i,N) {
    string s;
    cin >> s;
    for(auto c : s) {
      if(c =='(') xlast[i]++;
      else xlast[i]--;
      chmin(xmin[i], xlast[i]);
    }
    if(xlast[i] >= 0) vl.emplace_back(-xmin[i], i);
    else vr.emplace_back(xmin[i] - xlast[i], i);
  }

  sort(vl.begin(), vl.end());
  sort(vr.begin(), vr.end());

  ll tmin = 0, tlast = 0;
  for(auto p : vl) {
    ll i = p.second;
    chmin(tmin, tlast + xmin[i]);
    tlast += xlast[i];
  }
  for(auto p : vr) {
    ll i = p.second;
    chmin(tmin, tlast + xmin[i]);
    tlast += xlast[i];
  }

  if(tlast == 0 && tmin == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 34636
a,b,c = map(int,input().split())
l = []
l.append(abs(a-b)+abs(b-c))
l.append(abs(a-c)+abs(b-c))
l.append(abs(b-a)+abs(a-c))
l.append(abs(b-c)+abs(a-c))
l.append(abs(c-a)+abs(b-a))
l.append(abs(c-b)+abs(b-a))
print(min(l))

Measured memory_bytes: 3064
K =int(input())
l = [0, 1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836,194157,207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813,10493367, 10611772,10813692]
print(l[K])

Measured memory_bytes: 9280
#include <bits/stdc++.h>
using namespace std;

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
}

int ans = 0;
bool check = 0;
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  int a, b, c, n, x, y;
cin >> a>> b;
if(a+b>=10)pr("error");
else pr(a+b);
  return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int dp[1010][1010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s,t;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++) dp[i][j]=1e9;
    for(int i=0;i<=m;i++) dp[0][i]=i;
    for(int i=0;i<=n;i++) dp[i][0]=i;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i+1][j+1] = min(dp[i][j], min(dp[i+1][j],dp[i][j+1]))+1;
            if(s[i]==t[j]) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]);
            
        }
    }
    cout << dp[n][m] << endl;
    
    

}



Measured memory_bytes: 7180
#include<cstdio>
#include<cstring>
typedef long long LL;
const int N=5005,md=1e9+7;
int n,head[N],cnt,sz[N],mxd[N],rt,fac[N],iv[N],root;
int f[2][N];
bool tag;
struct edge{
	int to,nxt;
}e[N<<1];
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int P(int n,int m){return(LL)fac[n]*iv[n-m]%md;}
inline int pow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
	return ret;
}
void getrt(int now,int pre){
	sz[now]=1,mxd[now]=0;
	for(int i=head[now];i;i=e[i].nxt)
		if(e[i].to!=pre){
			getrt(e[i].to,now);
			sz[now]+=sz[e[i].to];
			if(mxd[now]<sz[e[i].to])mxd[now]=sz[e[i].to];
		}
	if(mxd[now]<n-sz[now])mxd[now]=n-sz[now];
	if(!rt||mxd[now]<mxd[rt])rt=now,tag=0;
	else if(mxd[now]==mxd[rt])tag=1;
}
int main(){
	scanf("%d",&n);
	for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
	iv[n]=pow(fac[n],md-2);
	for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[++cnt]=(edge){v,head[u]},head[u]=cnt;
		e[++cnt]=(edge){u,head[v]},head[v]=cnt;
	}
	rt=0;
	getrt(1,0);
	if(tag){
		printf("%lld\n",(LL)fac[n/2]*fac[n/2]%md);
		return 0;
	}
	root=rt,rt=0;
	getrt(root,0);
	int cur=0,lim=0;
	f[0][0]=1;
	for(int i=head[rt];i;i=e[i].nxt){
		int to=e[i].to;
		cur^=1;
		memset(f[cur],0,sizeof*f);
		lim+=sz[to];
		for(int j=lim;~j;--j)
			for(int k=0;k<=j&&k<=sz[to];++k)
				f[cur][j]=(f[cur][j]+(LL)f[cur^1][j-k]*C(sz[to],k)%md*P(sz[to],k))%md;
	}
	int ans=0;
	for(int i=0,x=1;i<=n;++i,x=md-x)
		ans=(ans+(LL)x*f[cur][i]%md*fac[n-i])%md;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
x,y=list(map(int, input().split()))
a=0
b=0
p=0
ans=0
for i in range(1,x+1):
	a=i
	p=2**20
	while a<y:
		a=a*2
		p=p/2
	ans=ans+p
print(ans/(2**20)/x)

Measured memory_bytes: 3064
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        
 
        Scanner sc = new Scanner(System.in);
        int H =sc.nextInt();
        int W =sc.nextInt();
        String[][] S =new String[H][W];
        boolean[] b1 =new boolean[H];
        boolean[] b2 =new boolean[W];
        
        for(int i=0;i<H;i++) {
            
            S[i]=sc.next().split("");
            for(int j=0;j<W;j++) {
                
                if(S[i][j].equals("#")) {
                    
                    b1[i]=true;
                    b2[j]=true;
                }
            }
        }
        for(int i=0;i<H;i++){
            if(b1[i]) {
                for(int j=0;j<W;j++) {
                    if(b2[j]) {
                        System.out.print(S[i][j]);
                    }
                }
            System.out.println("");
        }
    }
    }
} 

Measured memory_bytes: 40068
#include<iostream>
using namespace std;
int main(){
	int i, j, x, y;	
	while( cin >> x >> y ){
		
	if( x == 0 && y == 0 )
	break;
		
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		cout << "#";
		
		cout << "\n";
	}
	cout << "\n";
}
	return 0;
}


Measured memory_bytes: 3076