akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <complex>
#include <cmath>
using namespace std;
 
//内積
double dot(complex<double> z1, complex<double> z2) {
    return z1.real()*z2.real() + z1.imag()*z2.imag();
}
 
int main(int argc, char** argv) {
    const double EPS = 1e-10;
    double xA, yA, xB, yB, xC, yC, xD, yD;
    complex<double> a, b, c, d;
    while(cin >> xA >> yA >> xB >> yB >> xC >> yC >> xD >> yD) {
        a.real(xA); a.imag(yA);
        b.real(xB); b.imag(yB);
        c.real(xC); c.imag(yC);
        d.real(xD); d.imag(yD);
        if(abs(dot(a-b, c-d)) < EPS) { //ABとCDの内積が0ならば直交
            cout << "YES" << endl;
        }else {
            cout << "NO" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3064
A, B, C, X, Y = map(int, input().split(' '))
cost = 0
if A + B <= 2 * C:
    cost = A * X + B * Y
else:
    Z = min(X, Y)
    X -= Z
    Y -= Z
    cost = 2 * C * Z
    if X >= 1 and A >= 2 * C:
        cost += 2 * C * X
        X = 0
    elif X >= 1:
        cost += A * X
        X = 0
    if Y >= 1 and B >= 2 * C:
        cost += 2 * C * Y
        Y = 0
    elif Y >= 1:
        cost += B * Y
        Y = 0
print(cost)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using std::__gcd;
using std::sort;

void trans(char *s,char *p,int shift){
	for(int i=0;;++i){
		if( isalpha(s[i]) )
			p[i] = (s[i]-'a'+shift)%26 + 'a';
		else p[i] = s[i];
		if( s[i] == 0 ) return;
	}
}

bool check(char *s){
	if( *s != 't' ) return 0;
	++s;
	if( *s != 'h' ) return 0;
	++s;
	if( *s == 'e' ) return 1;
	else if( *s == 'i' && *(s+1) == 's' ) return 1;
	else if( *s == 'a' && *(s+1) == 't' ) return 1;
	return 0;
}

int main(){
	char s[100];
	while( gets(s) ){
		char p[100];
		bool ok = 0;
		for(int i=0;!ok&&i<26;++i){
			trans(s,p,i);
			for(int j=0;!ok&&s[j];++j)
				if(check(p+j)) ok = 1;
		}
		printf("%s\n",p);
	}
	return 0;	
}

Measured memory_bytes: 928
#include<bits/stdc++.h>
using namespace std;
#define N 5003
int n,m,s,e,base,V[N],HEAD[N],Ne[N],b,k,K[N],H[N],E[N],an;
int h,t,Q[N],q,FO[N],TO[N],Now[N],D[N];
int Ma[N],S[N];
void DO() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(Ma[S[j]]+FO[j]>Ma[E[j]])Ma[E[j]]=Ma[S[j]]+FO[j];
		}
	}
}
int main() {
	memset(Ma,-61,sizeof(Ma)),Ma[1]=0;
	scanf("%d %d %d",&n,&m,&base);
	for(int i=1; i<=m; i++) {
		scanf("%d %d %d",&s,&e,&FO[i]);
		FO[i]-=base,Ne[++b]=HEAD[s],HEAD[s]=b,E[b]=e;
		S[i]=s;
	}
	DO(),an=Ma[n],DO();
	if(an!=Ma[n]) {
		printf("-1");
		return 0;
	}
	printf("%d",max(Ma[n],0));
	return 0;
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

// double dis(double dx, double dy)
// {
// }

int main()
{
    int n;
    cin >> n;
    vector<double> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    vector<int> per(n);
    rep(i, n) per[i] = i;

    double ans = 0;
    double cnt = 0;
    do
    {
        cnt++;
        double cal = 0;
        rep(i, n - 1)
        {
            cal = pow(pow(x[per[i + 1]] - x[per[i]], 2.0) + pow(y[per[i + 1]] - y[per[i]], 2.0), 0.5);
            ans += cal;
        }
    } while (next_permutation(all(per)));
    ans /= cnt;
    cout << fixed << setprecision(10);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  ll M = 50 * 50 + 1;
  ll dp[M][M+M];
  dp[0][M] = 1;
  int n, a;
  cin >> n >> a;
  vector<int> x(n);
  for (int i = 0; i < n; ++i) {
      int y;
      cin >> y;
      x[i] = y - a;
  }

  for (int i = 0; i < n; ++i) {
      for (int j = 0; j < M + M; ++j) {
          dp[i+1][j] = dp[i][j];
          if (j - x[i] >= 0) dp[i+1][j] += dp[i][j-x[i]];
      }
  }

  cout << dp[n][M] - 1 << endl;
  return 0;
}


Measured memory_bytes: 3968
#include <iostream>
#include <vector>
#include<string>
#include<algorithm>
#include<cmath>
#define REP(i,n) for(int i=0; i<int(n); i++)
using namespace std;
int main() {
	int N;
	cin >> N;
	int X, Y;
	X = N / 1.08;
	Y = X + 1;
	if ( floor(X * 1.08) == N) {
		cout << X << endl;
	}
	else if ( floor(Y * 1.08) == N) {
		cout << Y << endl;
	}
	else {
		cout << ":(" << endl;
	}
}

Measured memory_bytes: 256
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
ia = -1
ib = -1

nowtime = 0
cnt = 0
for i in range(n):
    if nowtime + a[i] <= k:
        nowtime += a[i]
        cnt += 1
        ia = i
    else:
        break

ans = cnt
# print(ans, nowtime)
for i in range(m):
    while nowtime + b[i] > k and ia >= 0:
        nowtime -= a[ia]
        cnt -= 1
        ia -= 1
    if nowtime + b[i] > k:
        break
    nowtime += b[i]
    cnt += 1
    ans = max(ans, cnt)

print(ans)

Measured memory_bytes: 117772
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
struct edge{
  int u; int v; ll c;
};
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<edge>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;
int n,m;

ll Bellman(int s, int t, WeightedGraph& G){
  vector<ll> d(n);
  for(int i = 0; i < n; ++i)d[i]=INF;
  d[0]=0;
  for(int i = 0; i < n-1; ++i){
    for(int j = 0; j < m; ++j){
      int u = G[j].u;
      int v = G[j].v;
      ll c = G[j].c;
      if(d[v]>d[u]+c){
        d[v]=d[u]+c;
      }
    }
  }
  vector<bool> pos(n, false);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      int u = G[j].u;
      int v = G[j].v;
      ll c = G[j].c;
      if(d[u]>INF32)continue;
      if(d[v]>d[u]+c){
        pos[v] = true;
      }
      if(pos[u]) pos[v] = true; 
    }
  }
  //for(int i = 0; i < n; ++i)cout << pos[i] << endl;
  if(pos[n-1])return 1;
  return min(d[n-1],0LL);
}

int main(){
  ll p;cin >> n >> m >> p;
  WeightedGraph G(m);
  for(int i = 0; i < m; ++i){
    int a, b; ll c; cin >> a >> b >> c;
    --a;--b;
    G[i]={a, b,-1*c+p};
  }
  ll ans = Bellman(0, n-1, G);
  cout << -1*ans << endl;
}


Measured memory_bytes: 384
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
x = sorted(inpl())

ans = 10**100
for p in range(1,101):
    s = 0
    for i in range(n):
        s += (x[i] - p)**2
    ans = min(ans,s)

print(ans)

Measured memory_bytes: 30732
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if (a < b) {
        cout << "a < b" << endl;
    }
    else if (a > b) {
        cout << "a > b" << endl;
    }
    else {
        cout << "a == b" << endl;
    }
}

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

int main(){
	long long int n;
	cin >> n;
	long long int a[n];
	for(int i=0;i<n;i++)cin >> a[i];
	deque <int> b;
	if(n%2==0){
		b.push_back(a[0]);
		for(int i=1;i<n;i++){
			b.push_front(a[i]);
			i++;
			b.push_back(a[i]);
		}
		for(int i=0;i<n;i++){
			cout << b[i];
			if(i!=n-1)
				cout << " ";
		}
		cout << endl;
	}
	else{
		b.push_back(a[0]);
		for(int i=1;i<n;i++){
			b.push_back(a[i]);
			i++;
			b.push_front(a[i]);
		}
		for(int i=0;i<n;i++){
			cout << b[i];
			if(i!=n-1)
				cout << " ";
		}
		cout << endl;
	}
}


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

int main(void){
    string S;
    cin >> S;
    int n = S.length();
    string A;
    for(int i = 0; i < n; i+=2){
        A = A + S[i];
    }
    cout << A << endl;
    return 0;
}

Measured memory_bytes: 3100
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <cstdio>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;



#define INF 2000000000
#define MAX_V 10
const int MAX_N =10000000;


bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x*=i;
    return x;
}

ll gcd(ll a,ll b) { return b ? gcd(b, a%b) : a; }

ll func(ll a,ll b,ll& ans_x,ll& ans_y){
    if(b == 0){
        ans_x = 1;
        ans_y = 0;
        return a;
    }else{
        ll ret = func(b,(a%b),ans_y,ans_x);
        ans_y -= (a/b)*ans_x;
        return ret;
    }
}

ll par[MAX_N],ranking[MAX_N];

void init(ll n){
    rep(i,n){
        par[i]=i;
        ranking[i]=0;
    }
}

ll find(ll x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
}

void unite(ll x,ll y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    
    if(ranking[x]<ranking[y]) par[x]=y;
    else{
        par[y]=x;
        if(ranking[x]==ranking[y]) ranking[x]++;
    }
}

bool same(ll x,ll y){
    return find(x)==find(y);
}



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin>>n;
    vector<ll> a(4);
    rep(i,n){
        string s;
        cin>>s;
        if(s=="AC") a[0]++;
        else if(s=="WA") a[1]++;
        else if(s=="TLE") a[2]++;
        else a[3]++;
    }
    cout<<"AC x "<<a[0]<<endl;
    cout<<"WA x "<<a[1]<<endl;
    cout<<"TLE x "<<a[2]<<endl;
    cout<<"RE x "<<a[3]<<endl;
    return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
const int INF=1001001001;

int main() {
  int N;
  string S;
  cin>>N>>S;
  int stack=0,l=0;
  for(int i=0;i<N;i++){
    if(S[i]=='('){stack++;}
    else if(stack>0){stack--;}
    else{l++;}
  }
  int r=stack;
  string ans;
  for(int i=0;i<l;i++){
    ans+='(';
  }
  ans+=S;
  for(int i=0;i<r;i++){
    ans+=')';
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3596
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  string n;cin>>n;

  rep(i,0,n.size()){
    if(n[i]=='9'){out("Yes");return 0;}
  }
  out("No");



  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <list>

#define pb push_back
#define pk pop_back
#define _for(i,j,k) for(int i = (j); j < k; ++j)

using namespace std;

int main()
{
    int N,a,b;
    scanf("%d %d %d",&N,&a,&b);
    printf("%d ",min(a,b));
    if(a+b > N) printf("%d\n",a+b-N);
    else printf("0\n");
    return 0;
}

Measured memory_bytes: 256
#include <stdbool.h>
#include <stdio.h>
typedef long long ll;
ll modpow(ll a, ll n, ll MOD) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return (a * modpow(a, n - 1, MOD) % MOD);
	ll t = modpow(a, n / 2, MOD);
	return (t * t % MOD);
}
ll popCnt(ll num) {
	int res = 0;
	for (int i = 0; i < 64; i++) {
		if (num >> i & 1) {
			res++;
		}
	}
	return res;
}
int main() {
	int n;
	int cnt = 0;
	char x[200001];
	scanf("%d%s", &n, x);
	for (int i = 0; i < n; i++) {
		x[i] -= '0';
		if (x[i] == 1) {
			cnt++;
		}
	}
	ll mx = 0, px = 0;
	bool is0 = false;
	for (int i = 0; i < n; i++) {
		px += x[i] * modpow(2, n - i - 1, cnt + 1) % (cnt + 1);
		if (cnt == 1) {
			is0 = true;
		} else {
			mx += x[i] * modpow(2, n - i - 1, cnt - 1) % (cnt - 1);
		}
	}
	for (int i = 0; i < n; i++) {
		ll now = 0;
		if (x[i] == 1) {
			if (is0) {
				printf("0\n");
				continue;
			}
			now = mx;
			now += (cnt - 1);
			now -= modpow(2, n - i - 1, cnt - 1);
			now %= (cnt - 1);
		} else {
			now = px;
			now += modpow(2, n - i - 1, cnt + 1);
			now %= (cnt + 1);
		}
		int ans = 1;
		while (popCnt(now) != 0) {
			// printf("x:%d", num);
			int c = popCnt(now);
			// printf(" cnt:%d\n", c);
			now = now % c;
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1908
nm = input().split()
n = int(nm[0])
m = int(nm[1])
h = input().split()
r = [1] * len(h)
for i in range(m):
	ab = input().split()
	a = int(ab[0])
	b = int(ab[1])

	if int(h[a-1]) > int(h[b-1]):
		r[b-1] = 0
	elif int(h[a-1]) < int(h[b-1]):
		r[a-1] = 0
	else:
		r[a-1] = 0
		r[b-1] = 0

cnt = 0

for i in r:
	if int(i) == 1:
		cnt += 1
# print(r)
print(cnt)

Measured memory_bytes: 17440
fun main(args: Array<String>) {
    arc093a()
}

fun arc093a() {
    val n = readLine()!!.toInt()
    val aList = listOf(0) + readLine()!!.split(' ').map { it.toInt() } + listOf(0)

    val allSum = (1..n + 1).map { Math.abs(aList[it - 1] - aList[it]) }.sum()

    val answer = (1..n).map {
        val before = aList[it - 1]
        val curr = aList[it]
        val after = aList[it + 1]
        if (curr in before..after || curr in after..before) allSum else {
            allSum - Math.min(Math.abs(before - curr), Math.abs(after - curr)) * 2
        }
    }.joinToString(System.lineSeparator())

    println(answer)
}


Measured memory_bytes: 59840
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0

const ll inf = (ll)1e16;
const ll mod = (ll)1e9 + 7;
const ld eps = 1e-18;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int main() {
	ll k;	cin >> k;
	int n = 50;
	vector<ll> ret(n, n - 1);
	ll alldo = k / n;
	ll sub = alldo*(n - 1);
	ll left = k - alldo*n;
	rep(i, n) {
		ret[i] += alldo*n - sub;
	}
	rep(i, n) {
		if (left == 0)	break;
		ret[i] += n + 1;
		rep(j, n)	ret[j]--;
		left--;
	}
	cout << n << endl;
	rep(i, n) {
		cout << (i ? " " : "") << ret[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); \
                      cerr << "\n\n" << "Time elapsed: " << \
                      (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
                      return 0
#define ll long long int
#define ull unsigned long long int
#define db long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound 
#define pii pair<int , int>
#define pdd pair<db , db>
#define pll pair<ll , ll>
#define vpl vector<pll >
#define vll vector<ll >
#define mod 1000000007
#define mod1 998244353 
#define inf 1000000000000000007
#define eps 0.000001
#define stp fixed<<setprecision(20)
#define endl '\n'

ll dp[100005][15];

int main()
{
    fastio;
    #ifdef APNA_IO
        start_routine();
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);    
    #endif

    string s;cin>>s;
    ll n=s.length();
    s='*'+s;

    dp[0][0]=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<13;j++)
        {
            if(s[i]!='?')
            {
                ll x=j*10+(s[i]-'0');
                x%=13;

                dp[i][x]=(dp[i][x]+dp[i-1][j])%mod;
                continue;
            }

            for(ll k=0;k<10;k++)
            {
                ll x=j*10+k;
                x%=13;

                dp[i][x]=(dp[i][x]+dp[i-1][j])%mod;
            }
        }
    }
    cout<<dp[n][5];





    #ifdef APNA_IO
        end_routine();
    #endif
}


Measured memory_bytes: 12140
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
X,K,D = map(int, input().split())
q1,min1 =divmod(X,D)
q1 =abs(q1)
if min1 >=0:
    min2 =min1 -D
else:
    min2 =min1 +D

ans =0
if K <= q1:
    ans =abs(X) -K *D
elif K %2 ==0 and q1 %2 ==0:
    ans =abs(min1)
elif K %2 ==1 and q1 %2 ==1:
    ans =abs(min1)
elif K %2 ==0 and q1 %2 ==1:
    ans =abs(min2)
elif K %2 ==1 and q1 %2 ==0:
    ans =abs(min2)
print(ans)

Measured memory_bytes: 9092
#include<iostream>
#define INF 99999999

typedef long long ll;
using namespace std;
ll n,t[100],cnt[100][21],dp[100][21];
 
ll dfs(ll a,ll b){
	if(a==n-1){
		return (b==t[n-1]);
	}
	
	if(dp[a][b]!=-1){
		return dp[a][b];
	}

	ll ans=0;
	if(0<=b+t[a]&&b+t[a]<=20)ans+=dfs(a+1,b+t[a]);
	if(0<=b-t[a]&&b-t[a]<=20)ans+=dfs(a+1,b-t[a]);
	
	return dp[a][b]=ans;
}
int main(){
	for(int i=0;i<100;i++){
		for(int j=0;j<21;j++){
			dp[i][j]=-1;
		}
	}
	cin>>n;

	for(int i=0;i<n;i++)cin>>t[i];
	cout<<dfs(1,t[0])<<endl;

	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  int N; cin >> N;
  vector<char> P(N); for(auto& p : P) cin >> p;
  vector<char> Q(N); for(auto& q : Q) cin >> q;
  string Ps(P.begin(), P.end());
  string Qs(Q.begin(), Q.end());

  std::deque<string> que{};
  que.push_back("");
  vector<string> res{};
  while (!que.empty()) {
    auto s = que.front();
    que.pop_front();
    if ((int)s.size() == N) {
      res.push_back(s);
      continue;
    }
    for (int i = 1; i <= N; ++i) {
      char c = '0' + i;
      if (s.find(c) == s.npos) {
        que.push_back(s + c);
      }
    }
  }
  boost::sort(res, std::less<string>());

  auto Pitr = boost::lower_bound(res, Ps);
  auto Qitr = boost::lower_bound(res, Qs);
  auto Pindex = std::distance(res.begin(), Pitr);
  auto Qindex = std::distance(res.begin(), Qitr);
  auto ans = std::abs(Pindex - Qindex);

  cout << ans << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int a, b;
  cin >> a >> b;
  if ((a * b) & 1)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>


using namespace std;

int main(int argc, char const *argv[])
{

    long long  A, B;

    cin>>A>>B;
    long bo = B;
    long ans = 1;
    while (A+1>bo)
    {
        ans++;
        bo *= B;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
program poker;
var
	a, b : integer;
begin
	readln(a, b);
		if a = 1 then
			if a = b then
				writeln('Draw')
			else
				writeln('Alice')
		else if b = 1 then
			if b = a then
				writeln('Draw')
			else
				writeln('Bob')
		else
			if a > b then
				writeln('Alice')
			else if b > a then
				writeln('Bob')
			else
				writeln('Draw');
end.

Measured memory_bytes: 128
import collections
import itertools

# N枚の投票用紙
N = int(input())

s = []
for _ in range(N):
    s.append(input())

counter = collections.Counter(s)

mode_v = counter.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, counter.most_common()
)

l_it=list(it)
l_it.sort()
for k, v in l_it:
    print(k)

Measured memory_bytes: 46904
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

signed main(){
        int n;
        scanf("%d", &n);
        for(int i=0;i<n;i++){
                int a,b,c;
                scanf("%d %d %d",&a,&b,&c);
                int t=std::max({a,b,c});
                if(a*a+b*b+c*c-t*t-t*t==0) printf("YES\n");
                else printf("NO\n");
        }
        return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  	int N ;
  	cin >> N ;
  	int sum = 0;
  for (int i = 0; i < N; i++) {
    int l,r;
    cin >> l >> r;
    sum += r - (l-1);
 }
  cout << sum << endl;
 }

Measured memory_bytes: 256
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	print( (N-1)*N // 2)


if __name__ == '__main__':
	main()

Measured memory_bytes: 12220
#include <bits/stdc++.h>
using namespace std;
 typedef long long ll;
 
int main() {

ll n;
cin>>n;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int count =0;
ll ans=1;
for(int i=0;i<n-1;i++){
if(v[i]==v[i+1]){
ans*=v[i];
count++;
i++;
if(count==2)break;
}
}
if(count!=2)ans=0;
cout<<ans<<endl;
}


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

const int N=200,mod=1000000007;
typedef long long ll;
const ll inf=1e18;
inline void reduce(int&x){x+=x>>31&mod;}

vector<pair<ll,ll> >vec[N];
ll f[N];
int Q,cnt;
void Init(){
	f[0]=f[1]=1;cnt=1;
	for(;f[cnt]<=inf;++cnt)f[cnt+1]=f[cnt-1]+f[cnt];--cnt;
	for(int i=2;i<=f[3]+f[0];++i)vec[1].emplace_back(1,i);
	for(int i=2;i<=cnt;++i){
		for(auto j:vec[i-1]){
			auto t=make_pair(j.second,j.first+j.second);
			for(;t.second<=f[i-1]+f[i+2]&&t.second<=inf;t.second+=t.first)vec[i].push_back(t);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	Init();
	for(cin>>Q;Q --> 0;){
		ll x,y;cin>>x>>y;if(x>y)swap(x,y);
		int res=1,ans=0;
		for(;f[res]<=x&&f[res+1]<=y;++res);if(res>1)--res;
		if(res==1)ans=x*y%mod;
		else{
			for(auto i:vec[res-1]){
				if(i.second<=y)reduce(ans+=(x-i.first)/i.second%mod-mod);
				if(i.second<=x)reduce(ans+=(y-i.first)/i.second%mod-mod);
			}
		}
		cout<<res<<' '<<ans<<'\n';
	}
	return 0;
}


Measured memory_bytes: 4096
target = input()
m = int(input())
for i in range(m):
    arr= input().split()
    if arr[0] == 'print':
        print(eval('target[' + eval('arr[1]') + ':' + str(int(eval('arr[2]'))+1)+ ']'))
    if arr[0] == 'reverse':
        s_str = eval('target[' + eval('arr[1]') + ':' + str(int(eval('arr[2]'))+1)+ ']')
        target = eval('target[:' +eval('arr[1]') +']') + ''.join(list(reversed(s_str))) + eval('target[' +str(int(eval('arr[2]'))+1) +':]')
    if arr[0] == 'replace':
        target = eval('target[:' +eval('arr[1]') +']') + eval('arr[3]') + eval('target[' + str(int(eval('arr[2]'))+1) +':]')


Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define si(n) scanf("%d",&n);
#define PI acos(-1.0)
#define sl(n) scanf("%lld",&n);
#define sf(n) scanf("%lf",&n);
#define ss(n) scanf("%s",n);
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define forc(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define sor(n) sort(n.begin(),n.end())
#define sorcmp(n) sort(n.begin(),n.end(),cmp)
#define rev(n) reverse(n.begin(),n.end())
#define pi(x)  printf("%d",x);
#define pl(x)  printf("%lld",x);
#define pf(x)  printf("%.10lf",x);
#define ps(x)  printf("%s",x);
#define en() printf("\n");
#define random_shuffle(r...)random_shuffle(r,[](int _){return rand()%_;})
#define SQR(a) (a)*(a)
#define sp(x) fixed<<setprecision(x)
#define mod 1000000007
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define bug cout<<"Here"<<endl
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
template <typename T> T POW(T B,T P){ if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return SQR(POW(B,P/2));}
ll powmod(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%mod;a = a*a%mod;b >>= 1;}return ans;}


int main()
{
	string str,ptr;
	cin>>str>>ptr;
	int mn=INT_MAX;
	for(int i=0;i<=(int)str.size()-ptr.size();i++)
    {
        int k=i;
        int cnt=0;
        for(int j=0;j<ptr.size() && k<str.size();j++)
        {
            if(str[k]==ptr[j]) cnt++;
            k++;
        }

        int need=ptr.size()-cnt;
        mn=min(mn,need);

        }

    cout<<mn<<endl;



	return 0;
}


Measured memory_bytes: 3632
import queue
N, M = map(int, input().split())


path = [[] for i in range(N + 1)]


for i in range(M):
    a,b = map(int,input().split())
    path[a].append(b)
    path[b].append(a)


flag_directions = [-1 for i in range(N + 1)]

q = queue.Queue()
for p in path[1]:
    q.put((1, p))

while not q.empty():
    current, to = q.get()
    if flag_directions[to] == -1:
        flag_directions[to] = current 
        for next_room in path[to]:
            q.put((to, next_room))


print('Yes')
for f in flag_directions[2:]:
    print(f)


Measured memory_bytes: 112728
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    string S;
    cin >> S;
    int N = S.length();
    string M, L;
    for (int i = 0; i < (N - 1) / 2; i++) {
        M += S[i];
    }
    int T = M.length();
    for (int i = 0; i < T; i++) {
        L += S[i + T + 1];
    }

    if (M == L) {
            cout<<"Yes"<<endl;

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


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

int T,N,K,X[100000+10],A[100000+10];

int main()
{
    cin >> T;
    for(int t=0;t<T;t++)
    {
        cin >> N >> K;
        for(int i=0;i<N;i++)
           cin >> X[i];
        for(int i=0;i<N-1;i++)
           A[i]=X[i+1]-X[i];
        sort(A,A+N-1);
        int sum=0;
        for(int i=0;i<N-1-(K-1);i++)
            sum+=A[i];
        cout << sum << endl; 
    }
}


Measured memory_bytes: 3948
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

S = input()
N = len(S)
counter = [0] * N

strlist = [0, 0]
for i in range(N):
    if S[i] == "R":
        if i % 2 == 0:
            strlist[0] += 1
        else:
            strlist[1] += 1
    else:
        if i % 2 == 0:
            counter[i - 1] += strlist[1]
            counter[i] += strlist[0]
        else:
            counter[i - 1] += strlist[0]
            counter[i] += strlist[1]
        strlist = [0, 0]

strlist2 = [0, 0]
for i in range(N):
    if S[-i - 1] == "L":
        if i % 2 == 0:
            strlist2[0] += 1
        else:
            strlist2[1] += 1
    else:
        if i % 2 == 0:
            counter[-i] += strlist2[1]
            counter[-i - 1] += strlist2[0]
        else:
            counter[-i] += strlist2[0]
            counter[-i - 1] += strlist2[1]
        strlist2 = [0, 0]
print(*counter)

Measured memory_bytes: 74552
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>
#include <list>
#include <iomanip>
#include <cctype>
#include<chrono>
#include<random>

#define for0(i, N)    for (long long i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (long long i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (long long i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (long long i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (long long i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (long long i = (x), a = 0; a < (N);    \
                              i = (i + 1) % (N), ++a)
#define int long long

long double constexpr pi = 3.141592653589793;

template<class T>
constexpr T sigma1(T i, T n){
    return (n - i + 1) * (i + n) / 2;
}

template<class T>
constexpr T sigma2(T i, T n){
    return (i == 1 ? n * (n + 1) * (2 * n + 1) / 6 :
            sigma2(1, n) - sigma2(1, i - 1));
}

template<class T>
constexpr T sigma3(T i, T n){
    if (i == 1) {
        auto temp = sigma1(i, n);
        return temp * temp;
    }
    return sigma2(1, n) - sigma2(1, i - 1);
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

long long constexpr inf = std::numeric_limits<long long>::max();

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<vector<ll>> vvll;


signed main(void){
    cin.tie(0); ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);

    ll x, n;
    cin >> x >> n;

    vll p(101, 0);

    for0(i, n){
        ll pp;
        cin >> pp;
        ++p[pp];
    }

    if (!p[x]) {
        cout << x << "\n";

    } else {
        for1n(i, 100){
            if ((x - i >= 0 && !p[x - i]) || x - i < 0) {
                cout << x - i<< "\n";
                return 0;
            } else if ((x + i <= 100 && !p[x + i]) || x + i > 100) {
                cout << x + i<< "\n";
                return 0;
            }
        }
    }


    return 0;
}


Measured memory_bytes: 3652
#define usingfile1
#include <iostream>
#include <cstdio>
#include <cmath>
int file_reopen(){
	freopen("task.in","r",stdin);
	freopen("task.out","w",stdout);
}
using namespace std;
bool tomax(int &a,int b){return b>a?(a=b,1):0;}
void main_program(){
	int n,m;cin>>n>>m;
	int limit=m/n;
	int rtm=sqrt(m);
	int ans=0;
	for(int i=min(rtm+1,limit);i>=1;--i){
		if(m%i!=0)continue;
		if(i<=limit)tomax(ans,i);
		if(m/i<=limit)tomax(ans,m/i);
	}
	printf("%d\n",ans);
}
int main(){
	ios::sync_with_stdio(0);
	#ifdef usingfile
	file_reopen();
	main_program();
	fclose(stdin);fclose(stdout);
	#else
	main_program();
	#endif
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <vector>
#include <queue>

#define PI 3.14159265359

#define INF 1000000;

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

using namespace std;


/*
class ElectronicPetEasy
{
public:
	string isDifficult(int st1, int p1, int t1, int st2, int p2, int t2)
	{
		
	}
};
*/




int main()
{
	int N, sum, res;
	
	while (cin >> N, N)
	{
		res = 0;
		for (int i=1; i<=N; i++)
		{
			sum = i;
			for (int j=i+1; j<=N; j++)
			{
				sum += j;
				if (sum == N) res++;
				if (sum > N) break;
			}
		}
		cout << res << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

int i=0;
int main(void){
    int x;
     char s[3];
     char t[3];
    scanf("%s %s", s,t);
    for(x=0;x<3;x++)
    {
      if(s[x]==t[x]) i++;
    }
       printf("%d", i);
}


Measured memory_bytes: 128
S = str(input())


mae = int(S[0] + S[1])
ushiro = int(S[2] + S[3])

#
# print(mae)
# print(ushiro)

YYMM = False

MMYY = False

if 99 >= mae and mae >= 0 and 12 >= ushiro and ushiro >= 1:
    YYMM = True

if 12 >= mae and mae >= 1 and 99 >= ushiro and ushiro >= 0:
    MMYY = True


if YYMM and MMYY:
    print('AMBIGUOUS')
    exit()

if YYMM:
    print('YYMM')
    exit()

if MMYY:
    print('MMYY')
    exit()

print('NA')


Measured memory_bytes: 3064
/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (win, osx, linux)
 * Author: step_by_step
 * Time: 2020-03-19 17:35:03
**/

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

int main()
{
    //freopen("circus.in", "r", stdin);
    //freopen("circus.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    string s;
    cin >> s;
    ll ans = 0;
    int cnt0 = 0, cnt1 = 0;
    rep(i, 0, sz(s)) {
        if (s[i] == '0') {
            cnt0++;
        } else {
            cnt1++;
        }
    }
    repb(i, cnt1, 0) {
        ans += (i + 1) / 2;
    }
    string t;
    int cur = 0;
    rep(i, 0, sz(s)) {
        if (s[i] == '0') {
            t += '0';
        } else {
            cur++;
            if (i == sz(s) - 1 || s[i] != s[i + 1]) {
                ans += 1LL * cnt0 * (cur / 2);
                if (cur % 2 == 1) {
                    t += '1';
                }
                cur = 0;
            }
        }
    }
    int rem0 = 0;
    rep(i, 0, sz(t)) {
        if (t[i] == '0') {
            rem0++;
        }
    }
    int cur_1_pos = 0;
    rep(i, 0, sz(t)) {
        if (t[i] == '1') {
            int bad = (i + 1) / 2 - (cur_1_pos + 1) / 2;
            ans += rem0 - bad;
            cur_1_pos++;
        }
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3884
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

ll lcm(ll a, ll b) {
  const ll g = __gcd(a, b);
  return a / g * b;
}

void solve(ll N, vector<ll> T) {
  ll res = 1;
  for (ll i: T) res = lcm(res, i);
  cout << res << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	scanf("%lld", &N);
	vector<ll> T(N-1+1);
	for (int i = 0 ; i <= N-1 ; i++) {
	  scanf("%lld", &T[i]);
	}
	solve(N, T);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ff first 
#define ss second
#define mod 1000000007
#define INF 1000000007
#define lim 200005
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

//problem based
struct node{
	int l,r; ll mim,lazy;
	void reset(int l = 0, int r = 0, ll mim = 0, ll lazy = 0)	{ this->mim=mim; this->l=l; this->r=r; this->lazy = lazy; }
};
vector<node> segTree(4*lim);

//problem based
void merge(node& f,node j,node k)
{
	f.reset(j.l,k.r,max(j.mim+j.lazy,k.mim+k.lazy));
}

void merge(int i)
{
	merge(segTree[i],segTree[2*i],segTree[2*i+1]);
}

void build(int l,int r,int i = 1)
{
	if(l==r) { segTree[i].reset(l,l); return; }
	int m = (l+r)/2;
	build(l,m,2*i);
	build(m+1,r,2*i+1);
	merge(i);
}

//problem based
inline void update_lazy(ll val,node &d) { d.lazy += val; }

//problem based
inline void update_lazy(node &a,node &b) { update_lazy(a.lazy,b); }

//problem based
inline bool check_lazy(node &a){ return a.lazy; }

void push(int i)
{
	update_lazy(segTree[i],segTree[2*i]);
	update_lazy(segTree[i],segTree[2*i+1]);
	merge(i);
}

// minorly problem based (function arguments and stuff)
void range_update(ll val,int l,int r,int i=1)
{
	node &a = segTree[i];
	if(r<a.l || l>a.r) return;
	if(a.l>=l && a.r<=r) { update_lazy(val,a); return; }
	if(check_lazy(a)) push(i);
	range_update(val,l,r,2*i); range_update(val,l,r,2*i+1);
	merge(i);
}

void update_no(ll val, int l, int i=1)
{
	node &a=segTree[i];
	if(a.l==a.r){ a.reset(l,l,val); return; }
	update_no(val,l,2*i+(l>(a.l+a.r)/2));
	merge(i);
}

// problem based (use merge smartly or write your own).
inline void take(int i) { merge(segTree[0],segTree[0],segTree[i]); }

void query(int l,int r,int i=1)
{
	node &a=segTree[i];
	if(r<a.l || l>a.r)return;
	if(a.l >= l && a.r <= r) { take(i); return; }
	if(check_lazy(a)) push(i);
	query(l,r,2*i); query(l,r,2*i+1);
}

//problem based
ll act_query(int l,int r)
{
	segTree[0].reset(-INF,-1,-1e18,0);
	query(l,r);
	return segTree[0].mim;
}

int main()
{
	nfs_mw;
	ll ans = 0;
	int i,j,k,n,m,l[lim],r[lim]; ll a[lim];
	cin>>n>>m;
	vector<pair<int,int>> open,close;
	for(i=0; i<m; i++){
		cin>>l[i]>>r[i]>>a[i];
		open.pb(mp(l[i],i));
		close.pb(mp(r[i],i));
	}
	sort(open.begin(), open.end());
	sort(close.begin(), close.end());
	build(0,n);
	for(i=1,j=0,k=0; i<=n; i++){
		for(; j<m && open[j].ff == i; j++) 
			range_update(a[open[j].ss],0,l[open[j].ss]-1);
		ll v = act_query(0,i-1);
		ans = max(ans,v);
		update_no(v,i);
		for(; k<m && close[k].ff == i; k++) 
			range_update(-a[close[k].ss],0,l[close[k].ss]-1);
	}
	cout<<ans;
}



// //problem based
// int query_bs(int val = 0, int i = 1) // returns rightmost position with value < val, -1 if it does not exist.
// {
// 	node &a = segTree[i]; int ret;
// 	if(a.mim + a.lazy >= val) return -1;
// 	if(a.l == a.r) return a.r;
// 	if(check_lazy(a)) push(i);
// 	return ((ret = query_bs(val,2*i+1)) != -1)?ret:query_bs(val,2*i);	
// }

Measured memory_bytes: 25444
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

class UnionFind{ //連結判定
private:
    std::vector<int> parent; //parent[i] = parent of node i
    std::vector<int> rank;
    std::vector<int> size;
public:
    //constructor
    UnionFind(int N){
        for(int i=0; i<N; i++) parent.push_back(i); //parent = [0,1,..,N-1]
        for(int i=0; i<N; i++) rank.push_back(0); //rank = [0,0,..,0]
        for(int i=0; i<N; i++) size.push_back(1);
    }
    //initialize
    void init(int N){
        parent.clear();
        rank.clear();
        size.clear();
        for(int i=0; i<N; i++) parent.push_back(i); //parent = [0,1,..,N-1]
        for(int i=0; i<N; i++) rank.push_back(0); //rank = [0,0,..,0]
        for(int i=0; i<N; i++) size.push_back(1);
    }
    int root(int a){
        if(parent[a] == a) return a;
        return parent[a] = root(parent[a]); //親が自分自身になるまで再帰を呼び出す & 経路圧縮 
    }
    void unite(int a, int b){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return; //ノードa, bがすでに連結しているとき
        //次数の大きい方を親として連結
        if(rank[rootA] < rank[rootB]){
            size[rootB] += size[rootA];
            parent[rootA] = rootB;
        }
        else{
            size[rootA] += size[rootB];
            parent[rootB] = rootA;
            if(rank[rootA] == rank[rootB]) rank[rootA]++;
        }
    }
    bool same(int a, int b){
        return root(a) == root(b); //ノードa, bが同じ木に属するかどうか
    }
    int get_size(int a){
        return size[root(a)];
    }
};

int main()
{
    int N;
    cin >> N;
    vector<Pii> p(N);
    for(int i=0; i<N; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end());

    const int M = 1e6+1;
    UnionFind uf(M);
    for(int i=0; i<N-1; i++){
        if(p[i].first == p[i+1].first) uf.unite(p[i].second, p[i+1].second);
    }

    vector<int> szx(M);
    for(int i=0; i<N; i++){
        if(i != N-1 && p[i].first != p[i+1].first) szx[uf.root(p[i].second)]++;
        else if(i == N-1) szx[uf.root(p[i].second)]++;
    }

    ll ans = 0;
    for(int i=0; i<M; i++) ans += (ll)uf.get_size(i) * szx[i];
    cout << ans - N << endl;
}

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

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//infinity
#define INF 999999999

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

	int count = 0;
	FOR(i, 1, N+1){
		int a;
		cin >> a;
		while(a % 2 == 0){
			a = a / 2;
			count++;
		}
	}
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 256