akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n, k;
vector<i64> a, b;
int main() {
  cin >> n >> k;
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];

  i64 ans = 0;
  for (int d = -1; (1ll << d) <= k; ++d) {
    if (d >= 0 && !(k & (1ll << d))) continue;

    i64 x; 
    if (d >= 0) {
      x = (k | ((1ll << d) - 1)) & (~(1ll << d));
    } else {
      x = k;
    }

    cerr << d << ' ' << x << endl;

    i64 v = 0;
    for (int i = 0; i < n; ++i) {
      if (!(a[i] & ~x)) {
        v += b[i];
      }
    }
    ans = max(ans, v);
  }

  cout << ans << endl;
  return 0;
}

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

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;

int n, d, M;

ll func(int s, int t){
  ll ret=0LL;
  if(s==t){
  	if(n>=s)ret++;
    if(n>=s*10+s)ret++;
    if(d<=2)return ret;
    repb(i, 1, d-2){
      ret += pow(10, i);
    }
    if(M<s)return ret;
    if(M>s){
      ret += ll(pow(10, d-2));
    }else{
      ret += n%ll(pow(10, d-1))/10;
      if(n%10>=t)ret++;
    }
  }else{
  	if(n>=10*s+t)ret++;
    if(d<=2)return ret;
    repb(i, 1, d-2){
      ret += pow(10, i);
    }
    if(M<s)return ret;
    if(M>s){
      ret += ll(pow(10, d-2));
    }else{
      ret += n%ll(pow(10, d-1))/10;
      if(n%10>=t)ret++;
    }
  }
  return ret;
}

int main(){
  cin>>n;
  int tmp=n;
  while(tmp!=0){tmp/=10;d++;}
  M = n/int(pow(10, d-1));
  vector<vector<ll>> cnt(10, vector<ll>(10));
  repb(i, 1, 10){
  	repb(j, 1, 10){
      cnt[i-1][j-1]=func(i, j);
    }
  }
  ll ans=0;
  repb(i, 1, 10){
  	repb(j, 1, 10){
      ans+=cnt[i-1][j-1]*cnt[j-1][i-1];
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 256
N,M,C = map(int,input().split())
b_list = list(map(int,input().split()))

count = 0
for i in range(N):
    a_list = list(map(int,input().split()))
    sum = 0
    for j in range(M):
        sum += a_list[j]*b_list[j]
    if sum + C > 0:
        count += 1
print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;

char s[55][55];
int vis[55][55];
int dd[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int n, m;
int ans, res;

struct PP {
	int x, y, flg;
} p, q;

int Bfs(int x, int y) {
	memset(vis, 0, sizeof(vis));
	queue <PP> qua;
	p.x = x, p.y = y, p.flg = 1;
	qua.push(p);
	while(!qua.empty()) {
		q = qua.front();
		qua.pop();
		if(q.x == n && q.y == m) return q.flg;
		if(!vis[q.x][q.y]) {
			vis[q.x][q.y] = 1;
			for(int i = 0; i < 4; i++) {
				int dx = q.x + dd[i][0];
				int dy = q.y + dd[i][1];
				if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && s[dx][dy] != '#' && !vis[dx][dy]) {
					PP tmp;
					tmp.x = dx, tmp.y = dy, tmp.flg = q.flg + 1;
					qua.push(tmp);
				}
			}
		}
	}
	return -1;
}

void Init() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
}

int main() {
	Init();
	ans = n * m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) if(s[i][j] == '#') ans--;
	if(s[1][1] == '#' || s[n][m] == '#') res = -1;
	else res = Bfs(1, 1);
	if(res == -1) ans = -1;
	else ans -= res;
	cout << ans << endl;
}

Measured memory_bytes: 256
/*
下面只考虑所有不为全集的染色方案，最后再加上1表示全集的染色方案即可 
设F(u, d)表示距离u不超过d的点集
对于一个染色的方案S（显然是一个联通块），考虑其直径L
显然能让F(u, d) = S且d最小的u只会在直径的中点或中边的两个端点上，而所有直径的中点和中边都是相同的。分情况讨论： 
(1)L为偶数。那么F(u, d) = S且d最小的点，显然u只能是直径中点，d = L / 2
(2)L为奇数。那么整个树被中边(u, v)分成了两个根分别是u和v的子树，每一边子树尽量取一个非叶子的（取不到就取叶子）且能作为直径端点的端点
   不放设F(u, (L + 1) / 2) = S，那么u这边的端点一定是叶子，因为dist(u, u这边的端点) = (L - 1) / 2，若其不是叶子会产生矛盾
   同时，若F(v, (L + 1) / 2) = S，则S是整棵树，这是不合法的情况
综上所述，能让F(u, d) = S且d最小的u一定是S直径的中点或中边的两个端点，同时u是唯一的
这样一个显然的计数思路就是枚举u计算对应的S数量。称u和S对应，即F(u, d) = S且d最小
接下来考虑一个点u计算F(u, d)的贡献。为了方便把u当做整个树的根
*/
/*
设最大深度为d1，去掉最大深度所在的子树、剩下的子树中的最大深度为d2
首先d < d1，这是为了保证F(u, d)不是整棵树
考虑d2 < d1的情况。想象一个d从小到大变化的过程
                   当d = d2时，F(u, d)的直径为2 * d2且中点为u，一个端点在d2所在子树中、另一个端点在d1所在子树中
                   当d = d2 + 1时，d1所在子树中的端点继续向外延伸，u是中边的一个端点且仍然满足条件
		   当d = d2 + 2时，d1所在子树中的端点继续向外延伸，直径存在中点且不是u（是u向延伸方向的邻点），此时不符合条件
    综上所述，d < d2 + 2
所以，只要d < min{d1, d2 + 2}，F(u, d)这个点集对应的点就是u
*/
/*
还要考虑的问题是，若u未被染黑则需存在一个被染黑的点v满足F(v, k > d) = F(u, d)  
显然满足条件则一定有k = d + dist(u, v)，并且此时一定满足F(u, d)是F(v, k)的子集。下面判断F(v, k)是否是F(u, d)的子集 
设v在u的儿子m所代表的子树中，那么F(m, d < d + 1)是F(v, k)的子集，那么合法的必要条件是m向下延伸的最远距离 < d，考虑u到v路径上所有点可以发现这也是充分条件
这个条件直观描述就是：m子树中所有点都被染黑
所以找到一个含有被染黑节点且深度最小的子树m，设m向下延伸的最远距离为d3，则d > d3
*/
/*
综上已经对于每个u找到了d的上界和下界，直接计算即可
*/

#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_N(200050);
typedef long long int LL;

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Size[Max_N], F1[Max_N], F2[Max_N];
char B[Max_N];
LL Ans;

inline void Add_Edge(int s, int t)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Head[s] = Total;
}

void dfs(int u, int fa)
{
	Size[u] = B[u] - '0';
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			dfs(v, u), Size[u] += Size[v];
			if (F1[v] + 1 >= F1[u])
				F2[u] = F1[u], F1[u] = F1[v] + 1;
			else
				if (F1[v] + 1 >= F2[u])
					F2[u] = F1[v] + 1;
		}
}

void work(int u, int fa)
{
	int l, r;//[l, r)
	l = (B[u] == '1' ? 0 : N + 1);
	if (fa != -1)
	{
		int d = (F1[fa] == F1[u] + 1 ? F2[fa] : F1[fa]);
		if (Size[1] - Size[u])
			l = min(l, d + 1);
		if (d + 1 >= F1[u])
			F2[u] = F1[u], F1[u] = d + 1;
		else
			if (d + 1 >= F2[u])
				F2[u] = d + 1;
	}
	r = min(F1[u], F2[u] + 2);
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			if (Size[v])
				l = min(l, F1[v] + 1);
			work(v, u);
		}
	if (l <= r - 1)
		Ans += r - l;
}

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v;i != N;++i)
		scanf("%d%d", &u, &v), Add_Edge(u, v), Add_Edge(v, u);
	scanf("%s", B + 1);
	dfs(1, -1), work(1, -1);
	printf("%lld", Ans + 1LL);
	return 0;
}

Measured memory_bytes: 13696
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N = 1e7;


vector<ll> A; ll ans; ll N;
void slove(){
  vector<ll> alt;
  for(ll i = 0; i < N; i++){ alt.push_back(A[i]);} sort(alt.begin(),alt.end());
  for(ll i = 0; i < N; i++){
    ll itr = lower_bound(alt.begin(),alt.end(),A[i]) - alt.begin();
     A[i] = itr;}
  //座標圧縮
  vector<ll> num(N,0);
  for(ll i = 1; i < N; i+= 2){
    //イテレータが奇数項目に、幾つ1,3,5,,,が不足しているのかを数える
    num[i]++; num[A[i]]++;}
  ll res = 0;
  for(ll i = 1; i < N; i+= 2){ if(num[i] == 2){ //奇数がちゃんと奇数項目に存在
    res++;}
 ans = N/2 - res;//Nが奇数の時も全体数は(N-1)/2であり、整合する
                           }
}
    
    


int main(){
   cin >> N; A.resize(N); ans = 0;
  for(ll i = 0; i < N; i++){ cin >> A[i];}
  
  slove();
  
  cout << ans << endl; return 0;}

Measured memory_bytes: 2676
h, w = map(int, input().split())
T = [[] for i in range(h)]
for i in range(h):
    a = list(map(lambda s: int(s) % 2, input().split()))
    T[i] = a

move = []
i, j = 0, 0
flag = False
if T[i][j] == 1:
    flag = True
while True:
    prex, prey = i, j
    if i % 2 == 0:
        j += 1
        if j == w:
            j -= 1
            i += 1
            if i == h:
                break
    else:
        j -= 1
        if j == -1:
            j += 1
            i += 1
            if i == h:
                break
    if flag:
        move.append((prex, prey, i, j))
    if flag and T[i][j] == 1:
        flag = False
    elif T[i][j] == 1:
        flag = True

print(len(move))
for i in range(len(move)):
    a, b, c, d = move[i][0], move[i][1], move[i][2], move[i][3]
    print(a + 1, b + 1, c + 1, d + 1)





Measured memory_bytes: 22544
#include<bits/stdc++.h>
using namespace std;
const int mxN=15,mxM=1e3+10,mxkey=5e3+10,INF=1e8+10;
int n,m,x,chave,k;
pair<int,int> chaves[mxM];
int dp[mxM][mxkey];

int solve(int index,int val){
    if(index==m && val!=chave)return INF;
    if(val==chave)return 0;
    if(dp[index][val]!=-1)return dp[index][val];

    return dp[index][val]=min(solve(index+1,val),solve(index+1,val|chaves[index].second)+chaves[index].first);
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof(dp));
    cin>>n>>m;
    chave=pow(2,n)-1;
    //cout<<chave<<"\n";
    for(int i=0;i<m;i++){
        cin>>chaves[i].first;
        chaves[i].second=0;
        cin>>x;
        for(int j=0;j<x;j++){
            cin>>k;
            chaves[i].second |=(1<<k-1);            
        }
    }
    sort(chaves,chaves+m);
    /*for(int i=0;i<m;i++){
        cout<<chaves[i].first<<" "<<chaves[i].second<<"\n";
    }*/
    int resp=solve(0,0);
    if(resp==INF)cout<<-1;
    else cout<<resp;

}

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

using namespace std;

#define debug(args...) //fprintf(stderr, args)

vector<int> digraph[100010];
int in_degree[100010];
int dp[100010];

int make_dp(int u) {
	debug("[ DP ] -> u = %d\n", u);
	if (dp[u] != -1) return dp[u];
	int best = 0;
	for (int v: digraph[u]) {
		int val = make_dp(v);
		best = max(best, val);
	}
	dp[u] = best + 1;
	return dp[u];
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		digraph[x].push_back(y);
		in_degree[y] += 1;
	}
	for (int i = 0; i < n; ++i) dp[i] = -1;
	for (int i = 0; i < n; ++i) {
		if (in_degree[i] == 0) make_dp(i);
	}
	int longest = -1;
	for (int i = 0; i < n; ++i) longest = max(longest, dp[i]);
	printf("%d\n", longest-1);
}

Measured memory_bytes: 11136
#include <iostream>

int main()
{
    int x, y;    
    while (1)
    {
        std::cin >> x >> y;
        if (x == 0 && y == 0)
            break;
        if(x <= y)
            std::cout << x << " " << y << std::endl;  
        else
            std::cout << y << " " << x << std::endl;
    }
    return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define _size(X) (int)((X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100;
int N;
int a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];

const int MAX_V = MAX_N*2;

int V;                 //頂点数
vector<int> G[MAX_V];  //グラフの隣接リスト
int match[MAX_V];      //マッチングのペア
bool used[MAX_V];      //dfsで既に調べたかのフラグ

void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}

bool dfs(int v) {
  used[v] = true;
  for (int i = 0; i < G[v].size(); ++i) {
    int u = G[v][i], w = match[u];
    if (w < 0 || (!used[w] && dfs(w))) {
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int bipartite_matching() {
  int res = 0;
  memset(match, -1, sizeof(match));
  for (int v = 0; v < V; ++v) {
    if (match[v] < 0) {
      memset(used, 0, sizeof(used));
      if (dfs(v)) {
        ++res;
      }
    }
  }
  return res;
}

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

  cin >> N;
  rep(i, N) cin >> a[i] >> b[i];
  rep(i, N) cin >> c[i] >> d[i];
  V = 2*N;

  rep(i, N) {
      rep(j ,N) {
          if (a[i] < c[j] && b[i] < d[j]) {
              add_edge(i, N+j);
          }
      }
  }

  int ans = bipartite_matching();

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N, M =  map(int, input().split())
path = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
ans = [-1]*N
def bfs():
  que = [0]
  while len(que)>0:
    a = que.pop(0)
    for i in path[a]:
      if ans[i] == -1:
        ans[i] = a+1
        que.append(i)
  if -1 in ans:
    print("No")
  else:
    print("Yes")
    for i in range(1, N):
      print(ans[i])
if  __name__ == "__main__":
  bfs()  

Measured memory_bytes: 36728
from functools import reduce
from operator import mul
import collections
n = int(input())
a = list(map(int, input().split()))
ra = [0]
for i in range(n):
    ra.append(ra[i]+a[i])

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

ca = collections.Counter(ra)
ans = 0
for item, value in ca.items():
    # print(item, value)
    if value >= 2:
        ans += cmb(value, 2)
# print(ca)
print(ans)

Measured memory_bytes: 44596
# 頭から倒せるだけ倒していく

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

count = 0
for i in range(n):
  if a[i] <= b[i]:
    count += a[i]
    b[i] -= a[i]
    count += min(a[i+1], b[i])
    a[i+1] = max(0, a[i+1] - b[i])
  else:
    count += b[i]

print(count)

Measured memory_bytes: 18624
import bisect
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    A, B, Q = map(int,input().split())
    s = [-10**20] + [int(input()) for k in range(A)] + [10**20,10**20]
    t = [-10**20] + [int(input()) for k in range(B)] + [10**20,10**20]

    for _ in range(Q):
        x = int(input())
        S = bisect.bisect_left(s,x)
        T = bisect.bisect_left(t,x)
        print(min(
            max(s[S],t[T])-x,
            x-min(s[S-1],t[T-1]),
            s[S]-x + s[S]-t[T-1],
            t[T]-x + t[T]-s[S-1],
            x-s[S-1] + t[T]-s[S-1],
            x-t[T-1] + s[S]-t[T-1]))
if __name__ == '__main__':
    main()


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

typedef long long ll;
const ll mod = 1e9 + 7;
const int N=2000000;
const int M=2000;

void Run()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int main()
{
    Run();
    int n;
    cin>>n;
    if(n>=400&&n<=599)
        cout<<8;
    else if(n>=600&&n<=799)
        cout<<7;
    else if(n>=800&&n<=999)
        cout<<6;
    else if(n>=1000&&n<=1199)
        cout<<5;
    else if(n>=1200&&n<=1399)
        cout<<4;
    else if(n>=1400&&n<=1599)
        cout<<3;
    else if(n>=1600&&n<=1799)
        cout<<2;
    else if(n>=1800&&n<=1999)
        cout<<1;
}


Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int main()
{
	int n,total=0;
	cin>>n;
	int a[n+1],b[n];
	for (int i=2;i<=n;i++)  cin>>a[i];
	a[1]=0x3ffffff;
	a[n+1]=0x3ffffff;
	for (int i=1;i<=n;i++)
	{
		b[i]=min(a[i],a[i+1]);
	}
	for (int i=1;i<=n;i++)  total+=b[i];
	cout<<total<<endl;
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

int per[MAXN];
int d[MAXN];
int x[MAXN];

int d1[MAXN];
int used[MAXN];

ll ans[MAXN];

vi cycle;

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n){
		scanf("%d", &x[i]);
	}
	REP(i, 1, n){
		d[i] = x[i] - x[i - 1];
		per[i] = i;
	}
	int m;
	ll k;
	scanf("%d%lld", &m, &k);
	REP(i, 0, m){
		int a;
		scanf("%d", &a);
		swap(per[a], per[a - 1]);
	}
	REP(i, 1, n){
		if (used[i]){
			continue;
		}
		cycle.clear();
		for(int j = i; !used[j]; j = per[j]){
			cycle.pb(j);
			used[j] = 1;
		}
		int offset = k % SZ(cycle);
		REP(j, 0, SZ(cycle)){
			d1[cycle[j]] = d[cycle[(j + offset) % SZ(cycle)]];
		}
	}
	ans[0] = x[0];
	REP(i, 1, n){
		ans[i] = ans[i - 1] + d1[i];
	}
	REP(i, 0, n){
		printf("%lld\n", ans[i]);
	}
}

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 4472
#include <bits/stdc++.h>
typedef long long int ll;
#define vaibhavv06               \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define int long long
#define MM(a,b) memset(a,b,sizeof(a))
const ll MOD = 1000000007;
using namespace std;

int32_t main(){
    vaibhavv06;
    
	int n; cin>>n;
	if(n%2==1) cout<<0<<endl;
	else {
		int ans=0;
		for(int i=10;i<=1e18;i*=5){
			if(i>n) break;
			ans+=n/i;
		}
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <stack>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define INF INT_MAX>>1 //要climits#includ

typedef long long ll;

using namespace std;

int main(void){
	int n, x; cin >> n >> x;
	int l[100001];
	int ans = 1;
	int now = 0;
	for(int i=0; i<n; i++){
		cin >> l[i];
		now += l[i];
		if(now <= x) ans++;
		else break;
	}
	cout << ans << endl;


	return 0;
}

/*
int main(void){
	int x, a; cin >> x >> a;
	if(x < a) cout << 0 << endl;
	else cout << 10 << endl;


	return 0;
}
*/

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int x,y,z;
    Scd3(x,y,z);

    printf ("%d %d %d\n", z, x, y );

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n,k,r,s,p;
	cin>>n>>k>>r>>s>>p;
	string t;
	cin>>t;
	ll ans=0;
	vector<int> used(n);
	rep(i,n){
		if(t[i]=='r'){
			if(i<=k-1) used[i]=0;
			else{
				if(used[i-k]==0) used[i]=-1;
				else used[i]=0;
			}
			if(used[i]==0){
				ans+=p;
			}
		}else if(t[i]=='s'){
			if(i<=k-1) used[i]=1;
			else{
				if(used[i-k]==1) used[i]=-1;
				else used[i]=1;
			}
			if(used[i]==1){
				ans+=r;
			}
		}else{
			if(i<=k-1) used[i]=2;
			else{
				if(used[i-k]==2) used[i]=-1;
				else used[i]=2;
			}
			if(used[i]==2){
				ans+=s;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 848
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define ip pair<ll,ll>
#define ff first
#define ss second
#define MAX 100005
const ll MOD = 1000000007;
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	ll n;
	cin>>n;
	ll a[n];
	ll hi = 1e18, prod = 1;
	int flag = 0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i] == 0)
			flag = 1;
	}
 
	if(flag){
		cout<<"0\n";
		return 0;
	}
	
	for(int i=0;i<n;i++){
		if(a[i] <= hi/prod)
			prod *= a[i];
		else{
			prod = -1;
			break;
		}
	}
 
	if(prod > hi)
		prod = -1;
	cout<<prod<<endl;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    map<int, int> mp1;
    rep(i, n) {
        int d;
        cin >> d;
        mp1[d]++;
    }
    int m;
    cin >> m;
    map<int, int> mp2;
    rep(i, m) {
        int t;
        cin >> t;
        mp2[t]++;
    }
    bool ans = true;
    for(auto x : mp2) {
        if(mp1[x.first] < x.second) ans = false;
    }
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 22304
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int max_a = 0, min_a = 1000;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        max_a = max(max_a, a);
        min_a = min(min_a, a);
    }
    cout << max_a - min_a << endl;
}


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

int main(){
  int N;
  int max_num,min_num;
  cin >> N;
  cin >> max_num >> min_num;
  if(max_num < min_num) swap(max_num, min_num);
  
  for(int i = 2; i < N; i++){
    int number;
    cin >> number;
    if(number > max_num)
      max_num = number;
    else if(number < min_num)
      min_num = number;
  }
  cout << max_num - min_num << endl;
}

Measured memory_bytes: 3576
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
int x[100100];
int l, q;
int a[100100], b[100100];

int d[100100][20];

int calc(int idx0, int idx1) {
    int t = idx0;
    int res = 0;
    int s = 19;
    while (true) {
        if (d[t][0] >= idx1) {
            res++;
            break;
        }
        while (d[t][s-1] >= idx1) s--;
        t = d[t][s-1];
        res += (1<<(s-1));
    }
    return res;
}

int calc0(int k) {
    int lb = k, ub = n+1;
    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if (x[mid] - x[k] <= l) {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    return lb;
}

void solve() {
    for (int i = 0; i <= n; i++) {
        d[i][0] = calc0(i);
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 0; j <= n; j++) {
            d[j][i] = d[d[j][i-1]][i-1];
        }
    }
    /*
    for (int j = 0; j < 5; j++) {
        for (int i = 0; i < n; i++) cerr << d[i][j] << " ";
        cerr << endl;
    }
    */
    for (int i = 0; i < q; i++) {
        if (a[i] > b[i]) swap(a[i], b[i]);
        cout << calc(a[i], b[i]) << endl;
    }
}

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i];
    x[n] = x[n-1]+1;
    cin >> l >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
}

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

    input();
    solve();
}


Measured memory_bytes: 9856
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll H,W;
    cin >> H >> W;
    vector<string> s(H);
    vector<vector<ll>> dp(H+1, vector<ll>(W+1, 1e18));
    rep(i,H){
        cin >> s[i];
    }
    dp[0][1] = 0;
    dp[1][0] = 0;
    rep(i,H){
        rep(j,W){
            if(j-1>=0){
                cmin(dp[i+1][j+1], dp[i+1][j] + ((s[i][j]=='#' && s[i][j-1] == '.')?1LL:0LL));
            }else{
                cmin(dp[i+1][j+1], dp[i+1][j] + ((s[i][j]=='#')?1LL:0LL));
            }
            if(i-1>=0){
                cmin(dp[i+1][j+1], dp[i][j+1] + ((s[i][j]=='#' && s[i-1][j] == '.')?1LL:0LL));
            }else{
                cmin(dp[i+1][j+1], dp[i][j+1] + ((s[i][j]=='#')?1LL:0LL));
            }
        }
    }
    cout << dp[H][W] << endl;
}

Measured memory_bytes: 384
# ABC147C - HonestOrUnkind2
from itertools import combinations


def main():
    N = int(input())
    testimonies = [[] for i in range(N + 1)]
    for i in range(1, N + 1):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            testimonies[i].append((x, y))

    for cnt_honest in range(N, 0, -1):
        for honest_people in combinations(range(1, N + 1), cnt_honest):
            is_consistent = True
            for i in honest_people:
                for x, y in testimonies[i]:
                    if (x in honest_people and not y) or (x not in honest_people and y):
                        is_consistent = False
                        break
                if not is_consistent:
                    break
            if is_consistent:
                print(cnt_honest)
                return
    print(0)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
x, y, a, b, c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
cand = p[:x] + q[:y] + r
cand.sort(reverse=True)
print(sum(cand[:x + y]))

Measured memory_bytes: 29212
#include <math.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <array>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std ;
#define rep(i, a, b) for (int i=a; i<(b); i++)
#define forn(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define ford(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define int long long
#define ii pair<int,int>
#define ar array
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define sz(x) ((int)(x).size())
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
//const int N = 3e5+7 ;
//const int INF = 1e18 ;
//const int MOD = 1e9 + 7 ;

void solve(){
	int d , t , s ;
	cin >> d >> t >> s ;
	if(t*s >= d){
		cout << "Yes\n" ;
	}
	else{
		cout << "No\n" ;
	}
}


int32_t main(){
    FAST_IO ;
    int t = 1 ;
//    cin >> t ;
    while(t--){
        solve() ;
    }
}


Measured memory_bytes: 3608
#include<iostream>
using namespace std;
int main() {
	long long n, m;
	long long t;
	cin >> n >> m;
	t = (n-2)*(m-2);
	if (n*m == 1) {
		cout << 1 << endl;
	}
	else if (n == 1 || m == 1) {
		cout << n*m - 2 << endl;
	}
	else {
		cout << t << endl;
	}
}

Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <set>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}



int main() {
	string S;

	cin >> S;

	rep(i, S.size()) {
		if (i % 2 == 0 && S[i] == 'L') {
			cout << "No";
			return 0;
		}
		else if (i % 2 == 1 && S[i] == 'R') {
			cout << "No";
			return 0;

		}

	}

	cout << "Yes";
	
	return 0;
}

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

int main(){
  int N,m,ans;
  
  cin >> N;
  
  for(int i = 0;i < N;i++){
    if(N <= 1000*(i+1)){
      ans=1000*(i+1)-N;
      break;
    }
   
  }
  
  cout << ans << endl;
  
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

ll n,m;
int f(int x,int y){
  return x + y * n;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin >> n >> m && n+m){
    vector<vector<double>> v(n,vector<double>(n));
    rep(i,n){
      rep(j,n){
        cin >> v[i][j];
      }
    }
    vector<vector<double>> dp(m+1,vector<double>(n,0));
    rep(i,n){
      dp[0][i] = 1.0;
    }
    rep(i,m){
      rep(j,n){
        rep(k,n){
          dp[i+1][k] = max(dp[i+1][k],dp[i][j] * v[j][k]);
        }
      }
    }
    double ans = 0;
    rep(i,n){
      ans = max(ans,dp[m-1][i]);
    }
    fcout(2) << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3332
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n; bool cnt0 = false; bool overf = false;
  ll multiple = 1;
  
  rep(i,n){
    ll x; cin >> x;
    if(x <= (1000000000000000000+multiple-1)/multiple){
      multiple *= x;
    }
    else overf = true;
    
    if(x == 0){
      cnt0 = true;
      break;
    }
  }
  
  if(cnt0) cout << 0 << endl;
  else if(overf or multiple > 1000000000000000000) cout << -1 << endl;
  else cout << multiple << endl;
  
  
}

Measured memory_bytes: 3580
n=int(input())
a=list(map(int,input().split()))

a.sort()
if a[0]==0:
    print(0)
else:
    a.sort(reverse=True)
    # print(a)

    ans=1
    for i in range(n):
        ans=a[i]*ans
        if ans>10**18:
            break

    if ans>10**18:
        print(-1)
    else:
        print(ans)

Measured memory_bytes: 84816
#[allow(unused_imports)]
use std::cmp::{max, min};
use std::collections::*;
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, a: usize, b: usize);
    let mut s = 0usize;
    for _ in 0..(n - 2) {
        parse!(it, x: usize);
        s ^= x;
    }
    let mut memo = HashMap::new();
    let ret = f(a, b, s, &mut memo)
        .map(|x| if x >= a { -1 } else { x as i64 })
        .unwrap_or(-1);
    println!("{}", ret);
}

fn f(
    a: usize,
    b: usize,
    x: usize,
    memo: &mut HashMap<(usize, usize, usize), Option<usize>>,
) -> Option<usize> {
    let key = (a, b, x);
    if let Some(&ret) = memo.get(&key) {
        return ret;
    }
    let ret = if (a ^ b ^ x) & 1 == 1 {
        None
    } else if x == 0 {
        if a < b {
            None
        } else {
            Some((a - b) / 2)
        }
    } else if a == 0 {
        if b != x {
            None
        } else {
            Some(0)
        }
    } else {
        let c = f(a >> 1, b >> 1, x >> 1, memo).map(|x| x * 2);
        let d = f((a - 1) >> 1, (b + 1) >> 1, x >> 1, memo).map(|x| x * 2 + 1);
        let ret = match (c, d) {
            (c, None) => c,
            (None, d) => d,
            (Some(c), Some(d)) => Some(min(c, d)),
        };
        ret
    };
    memo.insert(key, ret);
    ret
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 2120
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;

ll n,k;
double ans=0;
double f[300000];
bool flag[300000];

double dp(int i)
{
    if (i>=k) return 1;
    if (i==0) return 0;
    if (flag[i]) return f[i];
    flag[i]=1;
    f[i] = (dp(0) + dp(i*2))/2;
    return f[i];
}

int main()
{
    cin>>n>>k;
    for (int i=n; i>=1; --i)
    {
        ans += dp(i);
    }
    ans = ans/n;
    printf("%0.10lf\n",ans);

    return 0;
}



Measured memory_bytes: 1152
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(ll i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln = '\n';

const int mx=200010;
const ll mod=1e9+7;


int main(){
  string s,t;
  cin >> s >> t;
  int a,b;
  cin >> a >> b;
  string k;
  cin >> k;
  if(k==s){ a--; }else{ b--; }
  cout << a << " " << b << ln;
  return 0;
}

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

const int N = 2e5;
int fr[N+100],bac[N+100],pre[N+100];
char str[N+100];

int main()
{
	int n,k,c;
	scanf("%d%d%d",&n,&k,&c);
	scanf("%s",str+1);
	int total = 0;
	for(int i=1;i<=n;){
		if(str[i]=='o'){
			fr[i] = ++total;
			i += c+1;
		}
		else{
			i++;
		}
	}
	total = 0;
	for(int i=n;i>0;){
		if(str[i]=='o'){
			bac[i] = ++total;
			i -= (c+1);
		}
		else{
			i--;
		}
	}
	for(int i=n;i>0;i--){
		if(bac[i]==0){
			bac[i] = bac[i+1];
		}
	}
	for(int i=1;i<=n;i++){
		if(fr[i]==0){
			pre[i] = pre[i-1];
		}
		else{
			pre[i] = i;
		}
	}
	//for(int i=1;i<=n;i++){
		//printf("%d %d\n",fr[i],bac[i]);
	//}
	for(int i=1;i<=n;i++){
		if(str[i]=='x'){
			continue;
		}
		int bef = pre[i-1];
		int aft;
		if(fr[bef]){
			aft = max(i+1,bef+c+1);
		}
		else{
			aft = i+1;
		}
		if(fr[bef]+bac[aft]<k){
			printf("%d\n",i);
		}
	}
}


Measured memory_bytes: 6268
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  ll ans = 0;
  ll amari = 0;
  vector<ll> a(n + 1), b(n);
  rep(i, n + 1) cin >> a[i];
  rep(i, n) cin >> b[i];
  rep(i, n){
    b[i] += amari;
    if(a[i] <= b[i]){
      if(amari >= a[i]) amari = b[i] - amari;
      else amari = b[i] - a[i];
      ans += a[i];
    }else{
      ans += b[i];
      amari = 0;
    }
  }
  ans += min(a[n], amari);
  cout << ans << endl;
}

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

int main(){
string s;
  cin>>s;
  if(s.at(0)==s.at(1)){
    if(s.at(2)==s.at(3)&&s.at(2)!=s.at(0))
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
else if(s.at(0)==s.at(2)){
if(s.at(1)==s.at(3)&&s.at(1)!=s.at(0))
  cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}
  else if(s.at(0)==s.at(3)){
if(s.at(1)==s.at(2)&&s.at(1)!=s.at(0))
  cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}
  else
    cout<<"No"<<endl;
}

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

using namespace std;

long long ans, k;

int main(){
	cin >> k;
	for(int a = 1; a <= k; ++a){
		for(int b = 1; b <= k; ++b){
			for(int c = 1; c <= k; ++c){
				ans += __gcd(a, __gcd(b, c));
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3632
#方針 N人に配っても余っている場合は一人にすべて押し付けることで最大値を求める


N, x = map(int, input().split())
a = list(map(int, input().split()))

sort_a = sorted(a)

cnt = 0
sum_a = 0
for i in sort_a:
    x -= i
    if x >= 0:
        cnt += 1
    else:
        break

if x > 0:
    cnt -= 1

print(cnt)


Measured memory_bytes: 3060
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;

     cin>>n>>k;

     ll ara[n+2];

    input(ara,n);

    sort(ara,ara+n);


    ans=1e18;
    for(i=k-1; i<n; i++)
    {
        sum=ara[i]-ara[i-k+1];

        ans=min(ans,sum);
    }

    cout<<ans<<endl;


}



Measured memory_bytes: 4372
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,m,dist[1010][1010],ans;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
string s[1010];
queue <pair <pii,int> > q;

bool out(int x,int y)
{
	return x<0||y<0||x>=n||y>=m;
}

int main()
{
	cin>>n>>m;
	rep(i,n)
	{
		cin>>s[i];
		rep(j,m) if(s[i][j]=='#') q.push({{i,j},0});
	}
	while(!q.empty())
	{
		int x=q.front().fi.fi,y=q.front().fi.se,val=q.front().se;
		q.pop();
		rep(i,4)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(out(xx,yy)) continue;
			if(s[xx][yy]=='#') continue;
			if(dist[xx][yy]!=0) continue;
			dist[xx][yy]=val+1;
			ans=max(ans,val+1);
			q.push({{xx,yy},val+1});
		}
	}
	cout<<ans<<endl;
	rt0;
}//stane

Measured memory_bytes: 13456
using System;

namespace ABC073_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var sum = 0;
            for(var i=0;i<n;i++)
            {
                var sss = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                sum += (sss[1] - sss[0] + 1);
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 11092
# For taking integer inputs.
import math
from decimal import Decimal


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(Decimal, input().split()))


a, b = invr()


res = a * b
print(int(res))


Measured memory_bytes: 10076
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
#define MAX_N 100000

ll dp[MAX_N + 1];

int main(){
	int n,k;
	cin >> n >> k;
	int h[n];
	REP(i,n) cin >> h[i];
	REP(i,MAX_N + 1) dp[i] = INF;
	dp[0] = 0;
	for(int i = 1; i < n; i++){
		for(int j = 1; j <= k; j++){
			if(i - j >= 0) dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
		}
	}
	cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
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> ans(N);
  for(int i=0; i<N; i++) ans[A[i]-1]=i+1;
  for(int i=0; i<N; i++) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 4028
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S,T;cin>>S;cin>>T;
  int N=S.length();
  set<vector<int>>sset,tset;
  for(int c=0;c<26;c++){
    vector<int>s,t;
    for(int i=0;i<N;i++){
      if((int)S[i]-97==c)s.push_back(i);
      if((int)T[i]-97==c)t.push_back(i);
    }
    sset.insert(s);tset.insert(t);
  }
  cout<<(sset==tset?"Yes":"No");
}

Measured memory_bytes: 3264