akhauriyash/Code-Regression huggingface dataset:
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = int.Parse(ReadLine());
            var list = new List<int>();
            var hashSet = new HashSet<int>();
            list.Add(s);
            hashSet.Add(s);
            int cnt = 1;

            while (true)
            {
                if (list[list.Count() - 1] % 2 == 0)
                {
                    cnt++;
                    int a = list[list.Count() - 1] / 2;
                    list.Add(a);
                    if (hashSet.Add(a) == false)
                    {
                        break;
                    }
                }
                else
                {
                    cnt++;
                    int a = 3 * list[list.Count() - 1] + 1;
                    list.Add(a);
                    if(hashSet.Add(a) == false)
                    {
                        break;
                    }
                }
            }

            WriteLine(cnt);
        }
    }
}



Measured memory_bytes: 13280
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね

def solve():
    x, y = getList()
    if (x + y) % 3 != 0 or 2 * x < y or 2 * y < x:
        print(0)
        return

    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    # print(a, b)
    fac, finv = fact_and_inv(max(x,y))
    print((fac[a+b] * divide(fac[a]) * divide(fac[b])) % MOD)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Measured memory_bytes: 91196
N, X, Y = map(int, input().split())

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    #pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                #dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        #pre = p

for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)


Measured memory_bytes: 136200
n = int(input())
a = list(map(int,input().split()))
a_cumsum = [0]*(n+1)
for i in range(n):
    a_cumsum[i+1] = a_cumsum[i] + a[i]

ans = 10**18
for i in range(n):
    ans = min(ans, abs(a_cumsum[-1] - a_cumsum[i]*2))
print(ans)

Measured memory_bytes: 26060
#include <bits/stdc++.h>
using namespace std;
constexpr auto MOD = 1000000007;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VLL;

string s;
long long n, m;

int main()
{
  cin >> n;
  vector<string> ls(n);
  VI lt(n);
  int al = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> ls[i] >> lt[i];
    al += lt[i];
  }
  cin >> s;
  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    ans += lt[i];
    if (s == ls[i])
      break;
  }
  cout << al - ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(int argc, char const *argv[]){
	int n,i=0;
	unsigned long l0,l1,an;
	scanf("%d",&n);
	if(n==0)
		printf("2");
	else if(n==1)
		printf("1");
	else{
		l0=2;
		l1=1;
		while(++i<n){
			an=l0+l1;
			l0=l1;
			l1=an;
		}
		printf("%lu",an);
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;

int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }

    int ans = 0;
    rep(i, n){
        if(i+1 == a[a[i]-1]){
            ans++;
        }
    }
    cout << ans/2 << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
long long int t, sum;
int main(){
	//ios::sync_with_stdio(0), cin.tie(0);
	//cout<< fixed<< setprecision(10) << x << endl;
	cin>>t;
	t--;
	vector<int> n(t);
	for(auto &x : n)cin>>x;
	sum = n[0];
	sum += n[t - 1];
	for(int a = 1; a < t; a++){
        sum += min(n[a - 1], n[a]);
	}
	cout<<sum<<"\n";
}


Measured memory_bytes: 256
import math

N = int(input())

class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def mul(self, a, b):
        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        #bp.append(1)
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))


def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

re = remainder()
primes = set()
for n in range(1, N + 1):
    prime = findAllOfPrime(n)
    for i, p in enumerate(prime):
        if p:
            primes.add(i)

A = math.factorial(N)
ans = 1
for p in primes:
    cnt = 1
    while A % p == 0:
        cnt += 1
        A //= p
    ans = re.mul(ans, cnt)
print(ans)




Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
bool sieve[10000000];
signed main() {
  ios::sync_with_stdio(false);
  while(true) {
    memset(sieve, 0, sizeof(sieve));
    int N, M; cin >> N >> M;
    if(N == 0 && M == 0) break;
    for(int i = N; M > 0; ++i) {
      if(sieve[i] == false) {
        for(int j = i; j < 10000000; j += i) {
          sieve[j] = true;
        }
        M--;
      }
    }
    int ans = -1;
    for(int i = N; ans == -1; ++i) {
      if(sieve[i] == false) {
        ans = i;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 12812
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

bool is_good[100001];
bool is_searched[100001];
int n, m;
int h[100001];
vector<int> graph[100001];

void search(int now){
	if (is_searched[now]) return;
	bool flg = true;
	for (auto x : graph[now]){
		if (h[now] <= h[x]){
			is_searched[now] = true;
			is_good[now] = false;
			return;
		}
	}
	for (auto x : graph[now]){
		is_searched[x] = true;
		is_good[x] = false;
	}
	is_good[now] = true;
	is_searched[now] = true;
	return;
}


int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> h[i];
	}
	for (int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= n; i++){
		search(i);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		if (is_good[i]){
			 ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9296
#include<stdio.h>
int main(){
int n,a[111],min=1111111,ans,i,ave,d;
scanf("%d",&n);
ave=0;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
ave+=a[i];
}
for(i=0;i<n;i++){
d=a[i]*n-ave;
if(d<0)
d=-d;
if(d<min){
ans=i;
min=d;
}
}
printf("%d\n",ans);
return 0;
}

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

int main(){
    long long N, M;
    cin >> N >> M;
    long long count;

    long long Snew, cnew;

    count=0;
    if(N > (long long) M/2 ){
        cout << (long long) M/2 << endl;
        return 0;
    }else{
        count+=N;
        cnew=M-2*N;

        Snew= (long long) cnew/4;
        count+=Snew;
    }
    cout << count << endl;

    return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MaxN 100000+100
typedef long long ll;
const ll mod=1000000007;
ll A[MaxN];
ll inv[MaxN];
ll jc[MaxN];
ll my_pow(ll ds,ll cf)
{
	ll sum=1;
	while(cf>0)
	{
		if(cf%2==1)
			sum=(sum*ds)%mod;
		ds=(ds*ds)%mod;
		cf/=2;
	}
	return sum;
}
ll ny(ll num)
{
	return my_pow(num,mod-2);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&A[i]);
	inv[0]=0;
	jc[0]=1;
	for(int i=1;i<=n;i++)
	{
		inv[i]=(inv[i-1]+ny(i))%mod;
	//	printf("%d\n",ny(i)); 
		jc[i]=(jc[i-1]*i)%mod;
	}
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		int z=i;
		int y=n-i+1;
		ll resu=(inv[z]+inv[y]-inv[1]+mod)%mod;
		resu=(resu*A[i])%mod;
		sum=(sum+resu)%mod;
	//	printf("%d-%d-%d %lld\n",A[i],z,y,resu);
	}
	sum=(sum*jc[n])%mod;
	printf("%lld\n",sum);
	return 0;
 } 

Measured memory_bytes: 2560
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  ll p, q, r;
  scanf("%lld%lld%lld", &p, &q, &r);
  printf("%lld\n", p + q + r - MAX(MAX(p, q), r));
  return 0;
}


Measured memory_bytes: 128
import math
def main():
    X, K, D = map(int, input().split())
    X = abs(X)
    if X >= K * D:
        return X - K * D
    overzero_K = math.ceil(X/D)
    overzero_X1 = X - overzero_K * D
    overzero_X2 = overzero_X1 + D
    left_K = K - overzero_K
    if left_K % 2 == 1: return overzero_X2
    else: return overzero_X1

print(abs(main()))


Measured memory_bytes: 9172
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <unordered_set>

using namespace std;

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

const ll mod = 1000000007;

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

  int n, q;
  cin >> n >> q;
  vector<vector<int> > stx(n, vector<int>(3));
  for (auto &x: stx) cin >> x[0] >> x[1] >> x[2];
  vector<int> d(q);
  for (auto &x: d) cin >> x;

  for (auto &x: stx) {
    x[0] -= x[2];
    x[1] -= x[2];
  }

  vector<int> time, pos;
  priority_queue<Pii, vector<Pii>, greater<Pii> > pque;
  priority_queue<int, vector<int>, greater<int> > watching;
  unordered_set<int> roadblock;
  for (auto &x: stx) {
    pque.emplace(x[0], x[2]);
    pque.emplace(x[1], x[2]);
  }
  int lastTime = -1000000007;
  while (!pque.empty()) {
    auto now = pque.top();
    pque.pop();
    if (now.first > lastTime) {
      while (!watching.empty()) {
        auto next = watching.top();
        if (roadblock.find(next) == roadblock.end()) watching.pop();
        else break;
      }
      if (watching.empty()) {
        time.push_back(lastTime);
        pos.push_back(-1);
      }
      else {
        auto next = watching.top();
        time.push_back(lastTime);
        pos.push_back(next);
      }
      lastTime = now.first;
    }
    if (roadblock.find(now.second) == roadblock.end()) {
      roadblock.insert(now.second);
      watching.push(now.second);
    }
    else {
      roadblock.erase(now.second);
    }
  }
  time.push_back(lastTime);
  pos.push_back(-1);

  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    auto it = upper_bound(time.begin(), time.end(), d[i]);
    int idx = distance(time.begin(), it) - 1;
    ans[i] = pos[idx];
  }

  for (auto &x: ans) cout << x << endl;

  return 0;
}


Measured memory_bytes: 31344
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
const int MAXN = 3005;
ll binom[MAXN][MAXN];
const ll MOD = 998244353;
int main() {
	for (int i = 0; i < MAXN; ++i)
		for (int j = 0; j <= i; ++j)
			if (!j || j == i) binom[i][j] = 1;
			else binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
	int n, x;
	scanf("%d%d", &n, &x);
	ll ans = 0;
	for (int a = 0; a <= n; ++a) {
		for (int b = 0; b <= a; ++b) {
			int c = min(b, a - b);
			if (b + c > x - 1) continue;
			if (b + b < x - 1) continue;
			int r = b - c;
			int t = x - 1 - b - c;
			assert(0 <= t && t <= r);
			ans = (ans + binom[r][t] * binom[n][a]) % MOD;
		}
		// Sum to s <= x - 2
		for (int s = a; s <= x - 2; ++s) {
			int t = s - a;
			if (t < 0 || t > a) continue;
			ans = (ans + binom[a][t] * binom[n][a]) % MOD;
		}
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 69120
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);

ll dp[MAXn];

ll w[MAXn], c[MAXn];

int main()
{
    IOS();
    ll n,W;
    cin>>n>>W;
    REP(i,n)cin>>w[i]>>c[i];
    REP(i,MAXn)dp[i] = INF;
    dp[0] = 0;
    REP(i,n)
    {
        for(int j = MAXn - 1;j >= c[i];j --)dp[j] = min(dp[j], dp[j-c[i]] + w[i]);
    }
    ll mx = 0;
    REP(i,MAXn)if(dp[i] <= W)mx = max(mx, i);
    cout<<mx<<endl;

}


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

     int n;
     cin>>n;
     vector<int>v;
     for(int i=0;i<n;i++)
     {
         int x;
         cin>>x;
         v.push_back(x);
     }
     sort(v.begin(),v.end());

         int u=(n/2)-1;
         if(v[u]==v[u+1])
         {
             cout<<"0"<<endl;

         }
         else
         {
             int ans=v[u+1]-v[u];
             cout<<ans<<endl;
         }


 }


Measured memory_bytes: 892
#include <stdio.h>
     
    int a[100001];
     
    int main()
    {
      int N;
      int bt = 1;
      scanf("%d", &N);
      for(int i = 1; i <= N; i++){
        scanf("%d", &a[i]);
      }
      int i = 0;
      while((bt != 2) && (i < N)){
        bt = a[bt];
        i++;
      }
      if(bt == 2) printf("%d\n", i);
      else        printf("%d\n", -1);
      return 0;
    }

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

int main(){
  int N;
  cin >> N;
  vector<int> X(N),L(N);
  for(int i=0;i<N;i++)  cin >> X.at(i) >> L.at(i);

  vector<pair<int,int>> rl(N);
  for(int i=0;i<N;i++){
    rl.at(i).first=X.at(i)+L.at(i);
    rl.at(i).second=X.at(i)-L.at(i);
  }
  sort(rl.begin(),rl.end());
  //for(int i=0;i<N;i++)  cout << rl.at(i).first << "," << rl.at(i).second << endl;
  int ans=0;
  int now_r=-(1e9+10);
  //cout << now_r << endl;
  for(int i=0;i<N;i++){
    int l=rl.at(i).second;
    if(now_r>l) continue;
    else{
      now_r=rl.at(i).first;
      ans++;
    }
  }
  cout << ans << endl;

	return 0;
}


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


template <int mod>
struct ModInt {
  int val;
  int trim(int x) const { return x >= mod ? x - mod : x < 0 ? x + mod : x; }
  ModInt(int v = 0) : val(trim(v % mod)) {}
  ModInt(long long v) : val(trim(v % mod)) {}
  ModInt &operator=(int v) { return val = trim(v % mod), *this; }
  ModInt &operator=(const ModInt &oth) { return val = oth.val, *this; }
  ModInt operator+(const ModInt &oth) const { return trim(val + oth.val); }
  ModInt operator-(const ModInt &oth) const { return trim(val - oth.val); }
  ModInt operator*(const ModInt &oth) const { return 1LL * val * oth.val % mod; }
  ModInt operator/(const ModInt &oth) const {
    function<int(int, int, int, int)> modinv = [&](int a, int b, int x, int y) {
      if (b == 0) return trim(x);
      return modinv(b, a - a / b * b, y, x - a / b * y);
    };
    return *this * modinv(oth.val, mod, 1, 0);
  }
  bool operator==(const ModInt &oth) const { return val == oth.val; }
  ModInt operator-() const { return trim(mod - val); }
  template<typename T> ModInt pow(T pw) {
    bool sgn = false;
    if (pw < 0) pw = -pw, sgn = true;
    ModInt ans = 1;
    for (ModInt cur = val; pw; pw >>= 1, cur = cur * cur) {
      if (pw&1) ans = ans * cur;
    }
    return sgn ? ModInt{1} / ans : ans;
  }
};

using mint = ModInt<1000000007>;
mint cur[1<<17], pre[1<<17];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n, k; cin >> n >> k;
  cur[k] = 1;
  for (int i = 0; i < n; ++i) {
    int a; cin >> a;
    swap(cur, pre);
    mint acc = 0;
    for (int i = 0; i < (1<<17); ++i) {
      tie(pre[i], acc) = make_pair(acc, pre[i] + acc);
    }
    for (int i = 0; i <= k; ++i) {
      cur[i] = pre[min(k, i + a) + 1] - pre[i];
    }
  }
  cout << cur[0].val << '\n';
}


Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <unordered_map>
#include <cstdio>
#include <climits>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

string s, t;
int k;
int d[310][310][310];

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> s >> k;
	t = s;
	reverse(all(t));
	int n = (int)s.size();
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		if (n <= i + j)continue;
		for (int l = 0; l <= k; l++)d[i + 1][j + 1][l] = max(d[i][j + 1][l], d[i + 1][j][l]);
		if (s[i] == t[j])for (int l = 0; l <= k; l++)d[i + 1][j + 1][l] = max(d[i + 1][j + 1][l], d[i][j][l] + 1);
		else for (int l = 0; l < k; l++)d[i + 1][j + 1][l + 1] = max(d[i + 1][j + 1][l + 1], d[i][j][l] + 1);
	}
	int ans = 0;
	for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++) {
		if (n <= i + j - 2)continue;
		int ma = 0;
		for (int l = 0; l <= k; l++)ma = max(ma, d[i][j][l]);
		if (i + j == n + 1)ans = max(ans, 2 * ma - 1);
		else ans = max(ans, 2 * ma);
	}
	cout << ans << endl;
}


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

main() {
    string O,E; cin >> O >> E;
    if(O.size()==E.size()){
        rep(i,O.size()){
            cout << O[i] << E[i];
        }
        cout << endl;
    }
    else {
        rep(i,O.size()){
            if(i==O.size()-1) cout << O[i] << endl;
            else cout << O[i] << E[i];
        }
    }

    return 0;
}

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

#define sc2(a,b)  scanf("%d %d",&a,&b)

int gcd(int a,int b) {
    if (a<b) swap(a,b);
    while (b>0) {
        int c=a%b;
        a=b;
        b=c;
    }
    return a;
}

int main(){
    int x,y;
    sc2(x,y);
    printf("%d\n",gcd(x,y));
    return 0;
}



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

using namespace std;
typedef long long ll;
const int MAXN = 1000100;

int N;
ll A, B;
ll arr[MAXN];

bool works (int x)
{
    ll ct = 0;
    for (int i = 0; i < N; i++)
    {
        ll nleft = arr[i] - x * B;
        if (nleft > 0)
            ct += (nleft - 1) / (A - B) + 1;
    }
    return ct <= x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    int lo = 1, hi = 1e9;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (works (mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    cout << lo << "\n";
}

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

int N,M;
int map[10][10];
int memo[10];
int ans=0;

void dfs(int d,int cur)
{
	memo[cur]=1;
	
	if(d==N-1)
	{
		int x=1;
		for(int i=0;i<N;i++)
			x=x&memo[i];
		if(x==1)ans++;
		memo[cur]=0;
		return;
	}
	
	for(int i=0;i<N;i++)
	{
		if(memo[i]==0 && map[cur][i])
		{
			dfs(d+1,i);
		}
	}
	memo[cur]=0;
	return;
}

int main()
{
	int a,b;
	
	cin >> N >> M;
	
	for(int i=0;i<M;i++)
	{
		cin >> a >> b;
		a--;
		b--;
		map[a][b]=1;
		map[b][a]=1;
	}
	
	dfs(0,0);
	
	cout << ans << endl;
	return 0;
}


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

def insertionSort(a,n):
    for i in range(n):
        v = a[i]
        j = i - 1
        while j >= 0 and a[j] > v:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = v 
        print(" ".join(map(str, a)))
        
insertionSort(a,n)
        

Measured memory_bytes: 5608
N = int(input())
A, B = map(int, input().split())
P = list(map(int, input().split()))
uA = []
oAuB = []
oB = []
for i in range(N):
    if P[i] <= A:
        uA.append(P[i])
    if A+1 <= P[i] and P[i] <= B:
        oAuB.append(P[i])
    if B+1 <= P[i]:
        oB.append(P[i])
print(min(len(uA), len(oAuB), len(oB)))


Measured memory_bytes: 3064
//Written by Zhu Zeqi
//Come on,baby
//Hack,please
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define CLR(x) memset(x,0,sizeof x)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define MAX 1000000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f
typedef long long ll;
//orz yht
using namespace std;
string i_s(int x){
	if(x==0)
	return "0";
	string ret="";
	while(x){
		ret=ret+(char)(x%10+'0');
		x/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}
string add(string a,string b){
	if(a=="")
	a="0";
	if(b=="")
	b="0";
	if(a.length()<b.length())
	swap(a,b);
	while(b.length()<a.length()){
		b='0'+b;
	}
	for(int i=0;i<a.length();i++){
		a[i]=a[i]+(b[i]-'0');
	}
	bool big=false;
	for(int i=a.length()-1;i>=0;i--){
		if(big){
			a[i]++;
		}
		big=false;
		if(a[i]>'9'){
			a[i]=a[i]-10;
			big=true;
		}
	}
	if(big)
	a='1'+a;
	return a;
}
string mul(string a,string b){
	vector<int> va,vb;
	if(a=="0" || b=="0")
	return "0";
	string ans;
	for(int i=0;i<a.length();i++){
		va.push_back(a[i]-'0');
	}
	for(int i=0;i<b.length();i++){
		vb.push_back(b[i]-'0');
	}
	reverse(va.begin(),va.end());
	reverse(vb.begin(),vb.end());
	vector<int> res;
	res.clear();
	res.resize(1005);
	for(int i=0;i<a.length();i++){
		for(int j=0;j<b.length();j++){
			res[i+j]+=(va[i]*vb[j]);
		}
	}
	for(int i=0;i<1005;i++){
		if(res[i]>9){
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	for(int i=0;i<1005;i++){
		ans+=(res[i]+'0');
	}
	reverse(ans.begin(),ans.end());
	int k=0;
	while(ans[k]=='0'){
		k++;
	}
	ans=ans.substr(k);
	return ans;
}
bool is_prime(int n){
	if(n<2)
    return false;
    for(int i=2;i*i<=n;i++)
    if(n%i==0)
    return false;
    return true;
}
int n,a[3][105],res,ans;
int main(){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	cin>>n;
	for(int i=1;i<=2;i++)
	for(int j=1;j<=n;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	res+=a[1][i];
	res+=a[2][n];
	ans=res;
	for(int i=n;i>=2;i--){
		res-=a[1][i];
		res+=a[2][i-1];
		ans=max(ans,res);
	}
	cout<<ans;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(a)  (a).begin(),(a).end()
ll dp[100005][13];

int main(){
  string s;
  cin >>s;
  ll mod = 1e9 + 7;
  ll n = s.size();
  dp[0][0] = 1;
  for(int i=0;i<n;i++){
    int c;
    if(s.at(i) == '?'){
      c = -1;
    }
    else{
      c = s.at(i) - '0';
    }
    for(int j=0;j<10;j++){
      if(c != -1 && c!= j){
        continue;
      }
      for(int k=0;k<13;k++){
        dp[i+1][(k*10+j)%13] += dp[i][k];
      }
    }
    for(int j=0;j<13;j++){
      dp[i+1][j] %= mod;
    }
  }
  ll res = dp[n][5];
  cout << res << endl;;
}

Measured memory_bytes: 10624
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT cin.tie(0); ios::sync_with_stdio(false);

template <class T>
inline bool chmax(T& a, T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline bool chmin(T& a, T b) {
    return a = (a > b) ? b : a;
}

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll A, B;
    cin >> A >> B;

    if (B % A == 0) {
        cout << A + B << endl;
    } else {
        cout << B - A << endl;
    }

    return 0;
}

Measured memory_bytes: 3600
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    ac, wa, tle, re =0, 0, 0, 0
    for i in range(n):
        s = input()
        if s == "AC":
            ac += 1
        elif s == "WA":
            wa += 1
        elif s == "TLE":
            tle += 1
        else:
            re += 1

    print("AC x {}".format(ac))
    print("WA x {}".format(wa)) 
    print("TLE x {}".format(tle))
    print("RE x {}".format(re))

if __name__=='__main__':
    main()

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

int n,x,d;

void so(int &a,int &b){
  int g=__gcd(a,b);
  a/=g;b/=g;
}

int f(int y){
  int mx=(n-y+n-1)*y/2;
  int mn=y*(y-1)/2;
  return mx-mn+1;
}

int g(int y){
  int l1=((n-y)+(n-1))*y/2,
      l2=y*(y-1)/2,
      r1=((n-y-d)+(n-1))*(y+d)/2+x,
      r2=(y+d)*(y+d-1)/2+x;

  //[l1,l2]がy個の数字で作った時のdの個数の範囲
  //[r1,r2]がy+d個の数字で作った時のdの個数の範囲+x
  //二つの範囲の重なり部分が重複して数えられてるのでこれを引く

  return max(min(l1,r1)-max(l2,r2)+1,0LL);
}

template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  cin>>n>>x>>d;

  //コーナーケース潰し
  if(!d&&!x)fin(1);
  if(!d)fin(n+1);
  if(!x)fin(n*(n-1)/2+1);
  if(x<0)x*=-1,d*=-1;

  //互いに素にする
  so(x,d);

  int ans=0;

  //i個で作れる数字の種類数を足す
  for(int i=0;i<=n;i++)  
    ans+=f(i);

  //xとdがsoなのでi個で作った数字と被るのは[i+d個で作った、dを取ってる個数がそれよりx個少ないやつ]だけ（ではないんだけど）なのでそれを引く
  for(int i=0;i<=n;i++)  
    if(i+d<=n&&i+d>=0)
      ans-=g(i);

  fin(ans);
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int n;
  while(scanf("%d",&n)!=EOF){
    if(n==1){
      printf("2\n");
      continue;
    }

    int a=4;
    for(int i=3;i<=n;i++){
      a+=i;
    }
    printf("%d\n",a);
  }
  return 0;
}



Measured memory_bytes: 1988
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    std::string s,t;
    std::cin >> s >> t;

    std::sort(s.begin(), s.end());
    std::sort(t.begin(), t.end(), std::greater<int>());

    rep(i,s.size()){
        if(s[i]<t[i]){
            std::cout << "Yes" << "\n";
            return 0;
        }
    }
    if(s[s.size()-1]==t[s.size()-1] && s.size()<t.size()){
        std::cout << "Yes" << "\n";
        return 0;
    }
    std::cout << "No" << "\n";
    return 0;
}


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

int main() {
  char c; cin >> c;
  
  if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define cst(x) cout<<fixed<<setprecision(x)
#define pi 3.14159265359
#define mod 1000000007
struct edge {
    int to; 
    int weight;
    edge(int t, int w) : to(t),weight(w) {}
};
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;
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; }

int N, M;
int ans = 0;
void dfs(const Graph &G, int v,int cnt, vector<bool> seen) {
    seen.at(v) = true; // v を訪問済にする
    cnt++;
    if(cnt == N) ans++;
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) {
        if (seen.at(next_v)) continue; // next_v が探索済だったらスルー
        dfs(G,next_v,cnt,seen); // 再帰的に探索
    }
    seen.at(v) = false;
    cnt--;
}

int main(){

    // 頂点数と辺数
    cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 頂点 0 をスタートとした探索
    vector<bool> seen(N,false); // 全頂点を「未訪問」に初期化
    dfs(G,0,0,seen);
    cout << ans << endl;
    return 0;
}


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

using namespace std;


int main() {
    int H, W, K;
    cin >> H >> W >> K;

    vector<vector<int>> c(H+2, vector<int>(W+2, 0));
    char in;

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> in;
            c[i][j] = in - '0';
        }
    }



    int answer = 0;
    vector<vector<int>> board(H+2, vector<int>(W+2, 0));

    for (int delete_i = 1; delete_i <= H; delete_i++) {
        for (int delete_j = 1; delete_j <= W; delete_j++) {
            board = c;

            for (int i = delete_i; i >= 1; i--) {
                board[i][delete_j] = board[i-1][delete_j];
            }

            int point = 0, tmp_number = 0, tmp_count = 0;
            bool combo = false;

            int increment = 0;

            // 連鎖する石が存在する限り続ける
            do {
                combo = false;

                for (int i = 1; i <= H; i++) {
                    tmp_number = 0, tmp_count = 0;

                    for (int j = 0; j < W+2; j++) {
                        // 前の石まででK個以上同じ石が連続したとき
                        if (tmp_count >= K) {
                            // 同じ石の場合
                            if (board[i][j] == tmp_number) {
                                tmp_count += 1;
                            
                            // 違う石の場合得点加算
                            } else {
                                combo = true;
                                point += tmp_number * tmp_count * (int)(pow(2.0, (float)increment));

                                // 石を1行下にずらす
                                for (int x = i; x >= 1; x--) {
                                    for (int y = j - tmp_count; y < j; y++) {
                                        board[x][y] = board[x-1][y]; 
                                    }
                                }

                                tmp_number = board[i][j];
                                tmp_count = 1;
                            }
                        } else {
                            if (board[i][j] == 0) {
                                tmp_number = 0;
                                tmp_count = 1;
                                continue;
                            }

                            if (board[i][j] == tmp_number) {
                                tmp_count += 1;
                            } else {
                                tmp_number = board[i][j];
                                tmp_count = 1;
                            }

                        }
                    }
                }

                increment++;
            } while (combo == true);

            answer = max(answer, point);
        }
    }

    cout << answer << endl;
    return 0;
}

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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
using namespace std;

int main(){
    int n;
    cin >> n;
    cout <<pow(n,3) << endl;
    return 0;
}

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

using namespace std;

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

const int SINF = 1000000009;
const ll INF =  1000000000000000018;

#define sp          cout << " "
#define nl          cout << "\n"
#define all(c)      (c).begin(),(c).end()
#define prec(n)     cout << fixed << setprecision(n)
#define PI          3.14159265358979323846264338327951
#define ifalse      ios_base::sync_with_stdio(false), cin.tie(NULL)

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

template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(auto x: v) {
    os << x << " ";
  }
  return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}

/********************* MODULAR ARITHMETIC *******************************/

ll MOD = 1000000007;

void mod(ll &a){ if(a > MOD) a %= MOD; }
ll add(ll a, ll b) { a += b; mod(a); return a; }
ll mul(ll a, ll b) { mod(a); mod(b); a *= b; mod(a); return a; }
ll sub(ll a, ll b) { mod(a); mod(b); a -= b; a += MOD; mod(a); return a; }

ll powr(ll a, ll b) {
  ll x = 1LL;
  while(b) {
    if(b & 1) x = mul(x, a);
    a = mul(a, a), b >>= 1;
  }
  return x;
}

ll inv(ll a) { return powr(a, (MOD - 2)); }

/******************************** START *********************************/
const int N = 3005;
vector < ld > v;
ld dp[N][N];

ld func(int n, int k) 
{
    if(n == 0) {
        if(k == 0) {
            return 1;
        }
        return 0;
    }
    if(k < 0) {
        return 0;
    }

    if(dp[n][k] > -1) {
        return dp[n][k];
    }
    ld a = v[n - 1] * func(n - 1, k - 1);
    ld b = (1 - v[n - 1]) * func(n - 1, k);
    return dp[n][k] = a + b;
}

int main()
{
  ifalse;
  int n;
  cin >> n;
  v.resize(n);
  cin >> v;

  int d = (n + 1) / 2;
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for(int i = 1; i <= n; i ++) {
      for(int j = 0; j <= n; j ++) {
          if(j - 1 >= 0) {
            dp[i][j] = v[i - 1] * dp[i - 1][j - 1];
          }
          dp[i][j] += (1 - v[i - 1]) * dp[i - 1][j];
      }
  }

  ld res = 0;
  for(int i = d; i <= n; i ++) {
      res += dp[n][i];
  }
  prec(14);
  cout << res, nl;
  return 0;
}

Measured memory_bytes: 141440
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<62;
const double pi=acos(-1.0);

map<int,int>id;
int tot;
int getid(int x)
{
	int&v=id[x];
	if(v)return v;
	return v=++tot;
}

int dgr[200111],f[200111];
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
int a[100111],b[100111],n;
bool check()
{
	multiset<int>x;for(int i=0;i<=n;i++)x.insert(a[i]);
	for(int i=0;i<=n;i++)
	{
		if(x.find(b[i])==x.end())return false;
		x.erase(x.find(b[i]));
	}
	return true;
}
int main()
{
	for(int i=0;i<200111;i++)f[i]=i;
	get1(n);
	for(int i=1;i<=n;i++){get1(a[i]);a[0]^=a[i];}
	for(int i=1;i<=n;i++){get1(b[i]);b[0]^=b[i];}
	if(!check())
	{
		puts("-1");
		return 0;
	}
	
	int ans=-1;
	for(int i=1;i<=n;i++)if(a[i]!=b[i])
	{
		int idx=getid(a[i]),idy=getid(b[i]);
		dgr[idx]++;dgr[idy]--;
		f[gf(idx)]=gf(idy);
		ans++;
	}
	getid(a[0]);getid(b[0]);
	for(int i=1;i<=tot;i++)if(f[i]==i)ans++;
	printendl(ans);
	return 0;
}

Measured memory_bytes: 8448
L, N = list(map(int, input().split()))
X = [int(input()) for i in range(N)]
Y = [L - X[i] for i in range(N)]

RL = [0]
RSL = [0]
for i in X:
  RL.append(i)
  RSL.append(RSL[-1] + i)

LL = [0]
LSL = [0]
for i in X[::-1]:
  LL.append(L - i)
  LSL.append(LSL[-1] + (L - i))

D = [RSL[i] + LSL[N - i] for i in range(N + 1)]

Ans = max(RL[N], LL[N])
for i in range(1, N):
  if i < (N + 1) // 2:
    k = N - 2 * i
    t = (D[i] - LSL[max(k - 1, 0)]) * 2  - LL[N - i]
    s = (D[i] - LSL[k]) * 2  - RL[i]
    Ans = max(Ans, t, s)
  else:
    k = 2 * i - N
    t = (D[i] - RSL[max(k - 1, 0)]) * 2  - RL[i]
    s = (D[i] - RSL[k]) * 2  - LL[N - i]
    Ans = max(Ans, t, s)
  
print(Ans)

Measured memory_bytes: 58808
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fr(i,a,b) for(ll i=a;i < b;i++)
#define fe(i,a,b) for(ll i=a;i <= b;i++)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fir first
#define sec second
#define tr(it,x) for(auto it = x.begin();it != x.end();it++)
#define mp make_pair
#define sz(x) (ll)x.size()
#define rep(i,n) for(ll i=0;i<n;i++)
#define double long double
#define accuracy ll precision = numeric_limits<double>::digits10
#define pll pair<ll,ll>
#define MAXN 100005
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define case(x) cout<<"Case #"<<x+1<<": "
#define endl "\n"
#define preturn(X) cout<<(X)<<endl; return 0
const int MOD = 1e9+7;
ll powmod(ll a,ll b,ll m=MOD){ll r=1;while(b>0){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}return r;}
ll power(ll a,ll b){ll r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
ll gcd(ll a,ll b){if(!b)return a;return gcd(b,a%b);}
ll inv(ll a, ll m = MOD){return powmod(a,m-2,m);}
ll lcm(ll a,ll b){return(a*b)/gcd(a,b);}

int32_t main(){
    int N,W;
    cin>>N>>W;
    vector<int> w(N),v(N);
    rep(i,N)cin>>w[i]>>v[i];
    vector<pair<int,vector<bool>>> dp(W+1,{0,vector<bool> (N,false)});
    for(int i = 0; i <= W; i++){
        for(int j = 0; j < N; j++){
            if(dp[i].second[j] || i + w[j] > W)continue;
            int val = dp[i].first + v[j];
            int weight = i + w[j];
            vector<bool> visit = dp[i].second;
            visit[j] = true;
            if(dp[weight].first < val){
                dp[weight] = {val,visit};
            }
        }
    }
    int maxval = 0;
    rep(i,W+1)maxval = max(maxval , dp[i].first);
    cout<<maxval<<endl;
}

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

using namespace std;

int main() {
  int input; cin >> input;
  for (int i = 0; i < (1<<3); i++) {
    int x = input / 1000;
    stringstream ss;
    ss << x;
    for (int j = 0; j < 3; j++) {
      int y = (input / int(pow(10,2-j))) % 10;

      if(i&(1<<j)) {
        ss << "+" << y;
        x += y;
      }
      else {
        ss << "-" << y;
        x -= y;
      }
    }
    if(x == 7) {
      ss << "=7";
      cout << ss.str() << endl;
      break;
    }
  }
}


Measured memory_bytes: 384
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    v=a[i]
    j=i-1
    while j>=0 and a[j]>v:
        a[j+1]=a[j]
        j-=1
    a[j+1]=v
    print(' '.join(map(str,a)))


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
typedef pair< int , int >PII;

string s[1009];
int dst[1009][1009];

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

    int h, w;
    cin >> h >> w;

    int ch, cw;
    cin >> ch >> cw;
    int dh, dw;
    cin >> dh >> dw;

    ch--; cw--;
    dh--; dw--;
    for (int i = 0; i < h; i++) cin >> s[i];

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            dst[i][j] = 1e9;
        }
    }

    dst[ch][cw] = 0;

    deque< PII >q;
    q.emplace_back(ch, cw);

    while (!q.empty()) {
        PII u = q.front(); q.pop_front();
        for (int i = -2; i <= 2; i++) {
            for (int j = -2; j <= 2; j++) {
                PII v(u.first+i, u.second+j);
                if (v.first < 0 || v.first >= h) continue;
                if (v.second < 0 || v.second >= w) continue;
                if (s[v.first][v.second]=='#') continue;
                int d = abs(i)+abs(j);

                if (d == 1) {
                    if (dst[v.first][v.second] > dst[u.first][u.second]) {
                        dst[v.first][v.second] = dst[u.first][u.second];
                        q.push_front(v);
                    }
                } else if (d > 1) {
                    if (dst[v.first][v.second] > dst[u.first][u.second]+1) {
                        dst[v.first][v.second] = dst[u.first][u.second]+1;
                        q.push_back(v);
                    }
                }
            }
        }
    }

    if (dst[dh][dw] == 1e9) dst[dh][dw] = -1;

    cout << dst[dh][dw] << "\n";


    return 0;
}


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

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define FOR(i,l,r) for(long long i=l; i<r; i++)
#define FOR_REV(i,r,l) for(long long i=r; i>=l; i--)
#define pb push_back
#define mp make_pair

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

    queue <ll> q;

    FOR (i,1,10)
    {
        q.push(i);
    }

    ll x;

    while (k--)
    {
        x = q.front();
        q.pop();

        if (x%10 != 0)
        {
            q.push(10*x + (x%10 - 1));
        }

        q.push(10*x + (x%10));

        if (x%10 != 9)
        {
            q.push(10*x + (x%10 + 1));
        }
    }

    cout<<x<<endl;
}


Measured memory_bytes: 1792