akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>

long long a[19]={9,90,900,(long long)9e3,(long long)9e4,(long long)9e5,(long long)9e6,(long long)9e7,(long long)9e8,(long long)9e9,(long long)9e10,(long long)9e11,(long long)9e12,(long long)9e13,(long long)9e14,(long long)9e15,(long long)9e16,(long long)9e17,(long long)9e18};
long long s;
long long dfs(int l,int e,int r,long long d,long long b)
{
	if(l==e&&!d)
		puts("");
	if(l--==e)return(d==0)*(e==r?10:1);
	if(d%a[r]!=0)return 0;
	long long c=0;
	for(int i=-9;i<=(r?9:8);i++)
		if(d-(long long)i*b==d-i*b)
			c+=(i<0?10+i:r?10-i:9-i)*dfs(l,e,r+1,d-i*b,b-a[l]-a[r]);
	return c;
}

int main()
{
	int d,i=1;scanf("%d",&d);
	for(long long b=9;i<20;b=b*10+9,i++)
		s+=dfs(i,i>>1,0,d,b);
	printf("%lld\n",s);
}

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

int main(){
  int N;
  cin >> N;
  vector<ll> A(N,0);
  ll sum = 0;
  for(int i=0;i<N;i++){
    cin >> A[i];
    sum += A[i];
  }
  sum -= 2*A[0];
  ll ans = abs(sum);
  for(int i=1;i<N-1;i++){
    sum -= 2*A[i];
    ans = min(ans,abs(sum));
  }
  cout << ans << endl;
}

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

int main() {
  int N;
  long K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    A.at(i)--;
  }
  
  vector<vector<int>> DP(63, vector<int>(N));
  for (int i = 0; i < N; i++) {
    DP.at(0).at(i) = A.at(i);
  }
  for (int i = 0; i + 1 < 63; i++) {
    for (int j = 0; j < N; j++) {
      DP.at(i + 1).at(j) = DP.at(i).at(DP.at(i).at(j));
    }
  }
  
  int now = 0;
  for (int i = 0; i < 63; i++) {
    if (K & (1L << i)) now = DP.at(i).at(now);
  }
  cout << now + 1 << "\n";
}

Measured memory_bytes: 54068
#include <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={0, 1, 0, -1}, dy[4]={-1, 0, 1, 0};
using namespace std;
//typedef pair<int, int> P;
struct P {
	int x, y;
	P(int x, int y):x(x), y(y){}
	P(){}
};

/** Problem1276 : PrimeGap **/
const int MAX = 1299710;

int main()
{
	vector<bool> isPrime(MAX);
	fill(isPrime.begin(), isPrime.end(), true);
	isPrime[0] = isPrime[1] = false;
	isPrime[2] = true;
	for (int i=2; i*i <= MAX; i++) {
		if (!isPrime[i]) continue;
		for (int j=2; j*i<=MAX; j++)
			isPrime[i*j]=false;
	}
	
	int N;
	while (cin>>N, N) {
		if (isPrime[N]) {
			cout << 0 << endl;
			continue;
		}
		
		int a=0, b=0;
		rep(i, MAX) {
			if (isPrime[N-i]) {
				a = N-i;
				break;
			}
		}
		
		rep(i, MAX) {
			if (isPrime[N+i]) {
				b = N+i;
				break;
			}
		}
		
		cout << b-a << endl;
	}
}

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

#define ll (long long)
#define REP(i,n) for(int i = 0;i<(int)n;i++)
#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (a);i>(b);i--)
#define COUNTER int i= 0,j = 0,k = 0,l = 0,m = 0, n= 0;
#define RETURN cout << endl;
/*vector<vector<int>>ArrayName = vector<vector<int>>(sizeofx, vector<int>(sizeofy, 0));*/
using namespace std;



int dfs (int x,int y,vector<vector<char>>&v);

int lim_x,lim_y;
int mx[] = {-1,1,0,0};
int my[] = {0,0,-1,1,};

int main (void){
    
    int x,y;
    int sh_x = 0,sh_y = 0;
    
    while(cin >> lim_x >> lim_y,lim_x+lim_y)
        {
            vector<vector<char>>v = vector<vector<char>>(lim_y, vector<char>(lim_x, 0));
            REP(i,lim_y)
            REP(j,lim_x)
            {
                cin >> v[i][j];
                if(v[i][j] == '@')
                    {
                        sh_y = i;
                        sh_x = j;
                    }
            }
            //cout << lim_x << " " << lim_y << endl;
            //cout << sh_x  <<" "<< sh_y << endl;
            cout << dfs(sh_x,sh_y,v) << endl;
            /*v is array name(pointer)*/
      
        }
    return 0;
}

int dfs(int x,int y, vector<vector<char>>&v)
{
    int counter = 1;
    for(int i = 0; i<4;i++){
            int tx = x+mx[i],ty = y+my[i];
            if((tx >= 0 && tx<lim_x) && (ty >= 0 && ty <lim_y) && (v[ty][tx] == '.'))
            {
                v[ty][tx] = '#';
                //cout << v[ty][tx] << endl;
                counter += dfs(tx, ty, v);
                //cout << "come on !" << endl;
            }
                
        }
            
    return counter;
}

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

using namespace std;

int main(){
	int n;
	cin>>n;
	switch(n%10){
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			puts("hon");
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			puts("pon");
			break;
		case 3:
			puts("bon");
			break;
	}
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string.h>
using namespace std;
#define pb push_back
#define all(v) v. begin(),v. end()
#define  rep(i,n,v) for(i=n;i<v;i++)
#define per(i,n,v) for(i=n;i>v;i--)
#define ff first 
#define ss second 
#define pp pair<ll,ll>
#define eps 1e-6
#define ll  long long
#define endl '\n'
void solve()
{
  ll n, a,m=0,b=1, k=0, i, j,l=2e9+7;
  string s, r, y;
  cin>>n;
  k=n%10;
  if(k==2 || k==4 || k==5 || k==7 || k==9) cout<<"hon";
  else if(k==0 || k==1 || k==6 || k==8) cout<<"pon";
  else cout<<"bon";
}
int main()
{
 ios_base::sync_with_stdio(false);
  cin. tie(0);cout. tie(0);
    ll t=1;
   //cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

Measured memory_bytes: 3648
N = int(input())
xy = []
ans = 0
for i in range(N):
    A = int(input())
    l = []
    for j in range(A):
        x, y = map(int, input().split())
        l.append([x, y])
    xy.append(l)
# print(xy)

#bit全探索
#bitたつ→正直者
#bitたたない→不親切もの
for i in range(2 ** N):
    tmp = [0 for _ in range(N)]
    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            #正直者
            tmp[j] = 1
            cnt += 1
    for j in range(N):
        if tmp[j] == 1:
            A = xy[j]
            for k in A:
                _x = k[0] - 1
                _y = k[1]
                if tmp[_x] != _y:
                    flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)


Measured memory_bytes: 44380
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct adja {
    int v;
    int c;
};

int n;
vector<adja> g[100];
int d[100];

void search() {
    fill_n(d, n, 1 << 20);
    queue<int> q;
    q.push(0);
    d[0] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0, s = g[u].size(); i < s; ++i) {
            if (d[g[u][i].v] > d[u] + g[u][i].c) {
                d[g[u][i].v] = d[u] + g[u][i].c;
                q.push(g[u][i].v);
            }
        }
    }
}

int main() {
    int u, k, v, c;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> u >> k;
        g[u].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> g[u][j].v >> g[u][j].c;
        }
    }
    search();
    for (int i = 0; i < n; ++i) {
        cout << i << " " << d[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3140
def F(a,b):
 A=len(a);r=[0]*A
 for i in range(A):
  f=1
  for j in range(min(A-i,len(b))):
   if len(set([a[i+j],b[j],'?']))>2:f=0
  r[i]=f
 return r+[1]
def Z(ix):
 i1,i2,i3=ix;ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3];A,B,C=map(len,[S[i]for i in ix]);q=A+B+C
 for l in range(A+1):
  if ab[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=range(3);M=[[F(S[i],S[j])for j in T]for i in T]
print(min([Z(i)for i in[(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]]))

Measured memory_bytes: 47964
s = input()
r = []
for i in range(len(s)):
    if s[i] == "0":
        r.append("0")
    elif s[i] == "1":
        r.append("1")
    elif s[i] == "B" and len(r) != 0:
        del r[-1]

    else:
        continue
print("".join(r))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1e18;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
    //a^tを求める
    //例：d[i] = mint(k/i).pow(n);
    //mint(2).pow(n); 2^n
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


mint dp[(1<<21)+5];


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


  dp[0]=1;
  rep(s,(1<<n)){
    int i=__builtin_popcount(s);

    rep(j,n){
      if (s&(1<<j)){
        if (a[i-1][j]==1){
          dp[s]+=dp[s^(1<<j)];
        }
      }
    }

  }
cout<<dp[(1<<n)-1];


}


Measured memory_bytes: 20024
#include <stdio.h>
#include <string.h>
#define N 16777217
/*const int N = 16777217;*/
int conv(char);
int hash(char []);
void insertElm(int);
char findElm(int);

int n;
char data[N];

main(){
  char com[13], len[13];
  int i;
  memset(data, 0, N);
  
  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%s", com);
    scanf("%s", len);
    if(!strcmp(com, "insert")) insertElm(hash(len));
    else printf("%s\n", (findElm(hash(len)) ? "yes" : "no"));
  }
  return 0;
}

int conv(char c){  
  if(c=='A')return 1;
  else if(c=='C')return 2;
  else if(c=='G')return 3;
  else if(c=='T')return 4; 
}
 
int hash(char len[10]){
  int res=0, size=strlen(len), r=1, i;
  for(i=size-1;i>=0;i--){
    res += r * conv(len[i]);
    r *= 4;
  }
  return res;
}
 
void insertElm(int x){
  data[x] = 1;
}
 
char findElm(int x){
  return data[x];
}




Measured memory_bytes: 18104
#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int F(int n) {
    int ret = 0;
    while (n) {
	int pc = __builtin_popcount(n);
	n %= pc;
	ret++;
    }
    return ret;
}

int N;
char S[200011];

int PLUS[200011], MINUS[200011];

void MAIN() {
    scanf("%d", &N);
    scanf("%s", S);
    reverse(S, S+N);

    int ones = count(S, S+N, '1');

    PLUS[0] = 1;
    MINUS[0] = 1;
    REP (i, N) {
	PLUS[i+1] = PLUS[i] * 2 % (ones + 1);
	MINUS[i+1] = MINUS[i] * 2 % (max(1, ones - 1));
    }

    LL plus_sum = 0, minus_sum = 0;
    REP (i, N) if (S[i] == '1') {
	plus_sum += PLUS[i];
	minus_sum += MINUS[i];
    }
    plus_sum %= ones + 1;
    minus_sum %= max(1, ones - 1);

    for (int i=N; i--;) {
	int ans = 0;
	if (S[i] == '0') {
	    int cur = (plus_sum + PLUS[i]) % (ones + 1);
	    ans = 1 + F(cur);
	} else if (ones == 1) {
	    ans = 0;
	} else {
	    int cur = (minus_sum - MINUS[i]) % (ones - 1);
	    if (cur < 0) cur += ones - 1;
	    ans = 1 + F(cur);
	}
	printf("%d\n", ans);
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 5524
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
#include <queue>
#include <deque>
#include <set>
#define ll long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define F first
#define S second
#define SHN 1e9
#define lSHN 1e18
using namespace std;
ll n,m;
ll t;
ll tim=1;
int main()
{
	cin >>n>>m;
	t=(n-m)*100+1900*m;
	for (int i=0;i<m;i++) tim*=2;
	cout <<t*tim;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define SZ(a) (int)(a).size()
using ll = long long;

int main() {
    cin.sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    if (n == 1) {
        printf("%lld\n", m);
        return 0;
    }
    int ans = 1;
    for (ll i = 2; i * i <= m; i++) {
        int cnt = 0;
        while (m % i == 0) {
            m /= i;
            cnt++;
            if (cnt % n == 0) {
                ans *= i;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    string a;
    bool c, f;
    int b;
    cin>>a;
    b=a.size();
    for(register int i=0;i<b;i++) 
    {
        if(a[i]=='C') 
        {
            for(register int j=i+1;j<b;j++)
            {
                if(a[j]=='F')
                {
                    printf("Yes");
                    return 0;
                }
            }
        }
    }
    printf("No");
    return 0;
}

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

using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;

// Debug
#ifdef SANYAM1101
	struct debug_printer{
		template<typename T, typename = void>
		struct is_ostreamable : std::false_type {};

		template<typename T>
		struct is_ostreamable<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T>())>> : std::true_type {};

		template<typename T, std::enable_if_t<is_ostreamable<T>::value, int> = 0>
		debug_printer& operator << (const T& t) {
			std::cerr << std::fixed << std::setprecision(20) << std::boolalpha << t; return *this;
		}

		template<typename T, typename U>
		debug_printer& operator << (const std::pair<T,U>& p) {
			return *this << "(" << p.first << " => " << p.second << ")";
		}

		template<typename T, std::enable_if_t<not is_ostreamable<T>::value, int> = 0>
		debug_printer& operator << (const T& container) {
			*this << "[";
			for(const auto& i: container) *this << i << ", ";
			return *this << (container.begin() != container.end() ? "\b\b]" : "]");
		}
	};

	template<typename Head, typename... Tail>
	void debug_f(std::string str, Head H, Tail... T) {
		debug_printer() << "\t" << str.substr(0, str.find(", ")) << " <=> " << H << "\n";
		if constexpr(sizeof...(T)) debug_f(str.substr(str.find(", ") + 2), T...);
	}

	#define trace(args...) do{ debug_printer() << "Line #" << __LINE__ << "\n"; debug_f(#args, args); } while(0)
#else
	#define trace(args...)
#endif

ll solver(int pos, int k, const vector<int>& p, const vector<int>& c){
	static vector<int> visited;
	visited.assign(p.size(), false);

	ll cycle_best = c[p[pos]], cycle_sum = 0;
	int moves = 0;
	for(; not visited[pos] and moves < k; ++moves){
		visited[pos] = true;
		pos = p[pos];
		cycle_sum += c[pos];
		cycle_best = max(cycle_best, cycle_sum);
	}

	int cycles = k / moves;
	ll ans = cycle_sum * (cycles - 1);
	k -= (cycles  - 1) * moves;

	ll post_best = 0, postsum = 0;
	if(cycles == 1) post_best = c[p[pos]];
	while(k--){
		pos = p[pos];
		postsum += c[pos];
		post_best = max(post_best, postsum);
	}

	return max(cycle_best, ans + post_best);
}

void solve(){
	int n, k;
	cin >> n >> k;

	vector<int> p(n), c(n);
	for(auto& i : p) cin >> i, --i;
	for(auto& i : c) cin >> i;

	ll ans = solver(0, k, p, c);
	for(int i = 1; i < n; ++i)
		ans = max(ans, solver(i, k, p, c));

	cout << ans << "\n";
}

signed main (void){
	// Fast_IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// Set Fixed Notation (default sucks), High Precision for Floating-Point Output
	cout << fixed << setprecision(20);

	// Multiple TCs
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}


Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int (i)=(s);(i)<(t);(i)++)


template <typename T>
class Weighted_quick_find {
	vector<pair<int, T>> data;
	vector<vector<int>> all;// par and id
public:
	Weighted_quick_find(int n) : data(n), all(n, vector<int>(1)) {
		for (int i = 0; i < n; i++) {
			data[i].first = i;
			all[i][0] = i;
		}
	}
	void unite(int a, int b, T d) {// node[a] + d = node[b]
		if (same(a, b)) return;
		d += data[a].second - data[b].second;
		a = data[a].first;
		b = data[b].first;
		if (all[a].size() < all[b].size()) swap(a, b), d = -d;
		for (auto& id : all[b]) {
			data[id] = { a, data[id].second + d };
		}
		copy(all[b].begin(), all[b].end(), back_inserter(all[a]));
	}
	bool same(int a, int b) const {
		return data[a].first == data[b].first;
	}
	T dist(int a, int b) const { // diff node[b] - node[a]
		return data[b].second - data[a].second;
	}
};

void solve_AOJ_DSL_1_B() {
	int N, Q;
	cin >> N >> Q;
	Weighted_quick_find<long long> wuf(N);

	FOR(i, 0, Q) {
		int a; cin >> a;
		if (!a) {
			int x, y, z; cin >> x >> y >> z;
			wuf.unite(x, y, z);
		}
		else {
			int x, y; cin >> x >> y;
			if (wuf.same(x, y)) {
				printf("%lld\n", wuf.dist(x, y));
			}
			else {
				puts("?");
			}
		}
	}
}

void solve_ABC_087_D() {
	int N, M; cin >> N >> M;
	Weighted_quick_find<long long> wuf(N);
	int flag = 1;
	FOR(i, 0, M) {
		long long l, r, d;
		cin >> l >> r >> d;
		l--, r--;
		if (wuf.same(l, r)) {
			if (wuf.dist(l, r) != d)flag = 0;
		}
		else {
			wuf.unite(l, r, d);
		}
	}
	cout << (flag ? "Yes" : "No") << endl;

}


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

	//solve_AOJ_DSL_1_B();
	solve_ABC_087_D();

	return 0;
}


Measured memory_bytes: 11004
#include<stdio.h>
int main(void){
    int train[10],i,input;
    for(i=0;i<10;i++){
        train[i]=0;
    }
    while(scanf("%d",&input)!=EOF){
        if(input!=0){
            for(i=0;;i++){
                if(train[i]==0){
                    train[i]=input;
                    break;
                }
            }
        }
        else if(input==0){
            for(i=9;i>=0;i--){
                if(train[i]!=0){
                    printf("%d\n",train[i]);
                    train[i]=0;
                    break;
                }
            }
        }
    }

return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#define int long long
using namespace std;

signed main() {
    int K, N;
    cin >> K >> N;
    vector<int> A(N + 1);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    A[N] = A[0] + K;
    int m = 0;
    for (int i = 0; i < N; ++i) {
        if (m < (A[i + 1] - A[i])) m = A[i + 1] - A[i];
    }
    
    cout << K - m << endl;
    return 0;
}

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

#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
typedef long double ld;
using namespace std;
#define endl "\n"
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
const int N=1e5+5, mxN=(1<<22);
int mod=1e9+7;
ll a[N],b[N],c[N];
ll arr[N]= {};
int n;
int bin(ll x, ll ar[])
{
    int low=0,high=n-1,ans=n;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(ar[mid]>x)
        {
            ans=mid;
            high=mid-1;
        }
        else
            low=mid+1;

    }
    return ans;

}
int main()
{
    FIO
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(int i=0; i<n; i++)
    {
        cin>>b[i];
    }
    for(int i=0; i<n; i++)
    {
        cin>>c[i];
    }

    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    for(int i=0; i<n; i++)
    {
        int ind=bin(b[i],c);
        arr[i]=n-ind;
    }
    for(int i=n-2;i>=0;i--)
    {
        arr[i]+=arr[i+1];

    }
    ll ans=0;
    for(int i=0; i<n; i++)
    {
        int ind=bin(a[i],b);
        if(ind!=n)
        {
            ans+=(ll)arr[ind];
        }
    }


    cout<<ans;

    return 0;

}






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

using namespace std;

int main()
{
	int n, p_t = 0, p_h = 0;
	string t, h;
	
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++)
	{
		cin >> t >> h;
		
		if(t > h)
			p_t += 3;
		else if(t < h)
			p_h += 3;
		else
		{
			p_t += 1;
			p_h += 1;
		}
	}
	
	cout << p_t << " " << p_h << "\n";
	
	return 0;
}


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

int main()
{
    int N ,K;
    cin >> N >> K;
    int H[N];
    for(int i = 0; i < N; i++){
        cin >> H[i];
    }
    sort(H, H + N);
    int times = 0;
    if(N- K > 0) times = N-K;
    int64_t res = 0;
    for(int i =0; i < times; i++)
    {
        res += H[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 1152
#!/usr/bin/env python
# coding: utf-8

# In[37]:


d, g = map(int, input().split())
pcs = [list(map(int, input().split()))for _ in range(d)]
"""
2 700
3 500
5 800

2 2000
3 500
5 800
"""


# In[ ]:


"""
完全に解くか、全くとかないかを総当たり
完全に解く問題の総score

総scoreが目標scoreを上回っている
 -> 手数を保存
scoreを下回っている
 -> 全く解いていない問題の中から 一つ選び、中途半端に解く
    scoreを上回る場合
     -> 手数に数える
    scoreを下回る場合
     -> continue
"""


# In[35]:


import math


# In[68]:


temp_str = ''
min_nb = float('inf')
# 完全、完全じゃない、全探索
for i in range(2**d):
    #print(i)
    score = 0
    solved_nb = 0
    # j桁目が1の時、j番目のpをscoreに加算
    for j in range(d):
        if (i>>j) & 1:
            score += (j+1) * 100 * pcs[j][0] + pcs[j][1]
            temp_str += '{}ten {}mon {}perf : total {}\n'.format((j+1)*100, pcs[j][0], pcs[j][1], score)
            solved_nb += pcs[j][0]
    
    # この時点で目標scoreを超えていれば、solved_nbを保存してcontinue
    if score >= g:
        min_nb = min(min_nb, solved_nb)
        #print(temp_str)
        continue
    
    # j桁目が0の中から一つ選び、
    
    #temp_score = score
    #temp_solved_nb = solved_nb
    #print(i)
    for j in range(d):
        
        if bin(i>>j)[-1] == '0':
            #print('a', j, score)
            j_nb = math.ceil((g-score)/((j+1)*100))
            score_judge = score + pcs[j][1]*j_nb 
            #print('b', j_nb, pcs[j][0])
            if j_nb <= pcs[j][0]-1 and score_judge > score:
                min_nb = min(min_nb, solved_nb+j_nb)
                temp_str += '{}ten {}mon: total {}\n'.format((j+1)*100, j_nb, (j+1)*100*j_nb)
                #print(temp_str)
    #print(temp_str)
print(min_nb)


# In[ ]:






Measured memory_bytes: 3444
"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc059/tasks/arc059_d

dp[i][j] = i回キーボードを押した時に、j文字の通り数
とすれば、O(N**2)で解ける。

0,1は等確率で現れることを考えれば、文字数を減らした場合のdp推移も簡単。
2(mod10**9+7)の逆元が必要かな→いらんかった

(最後に|s|文字になっている押し方/2**|s|)通りが求める答え
"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


N = int(input())

s = input()

dp = [0] * (N+1)
dp[0] = 1

mod = 10**9+7

for loop in range(N):

    ndp = [0] * (N+1)

    for i in range(N+1):

        dp[i] %= mod
        if i != N:
            ndp[i+1] += dp[i] * 2
            ndp[i+1] %= mod

        if i != 0:
            ndp[i-1] += dp[i]
            ndp[i-1] %= mod
        else:
            ndp[i] += dp[i]
            ndp[i] %= mod

    dp = ndp

    #print (dp)
inv = inverse(pow(2,len(s),mod) , mod)
print (dp[len(s)] * inv % mod)

    
        

Measured memory_bytes: 46440
#include <algorithm>
#include <iostream>
#include <queue>

#include <limits.h>

using namespace std;

typedef long long ll;

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;
}

class Edge {
    public:
        int to;
        int c;

        friend ostream& operator<<(ostream &os, const Edge &a) {
            os << "{to=" << a.to + 1 << ", c=" << a.c << "}";
            return os;
        }
};

class Elem {
    public:
        int i;
        ll distance;

        bool operator < (const Elem &other) const {
            return distance < other.distance;
        }

        bool operator > (const Elem &other) const {
            return distance > other.distance;
        }
};

const int MAX_N = 100000;
const int MAX_M = 100000;

int n;
int m;
int edge_num;
vector<Edge> adjlist[MAX_N];
priority_queue<Elem, vector<Elem>, greater<Elem> > q;

void print_edges() {
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ": ";
        for (auto edge : adjlist[i]) {
            cout << edge << ",";
        }
        cout << endl;
    }
}

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

    edge_num = m + n - 1;

    for (int i = 0; i < n - 1; i++) {
        adjlist[i + 1].push_back({i, 0});
    }

    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        adjlist[l - 1].push_back({r - 1, c});
    }

    // print_edges();

    vector<ll> d(n, LONG_LONG_MAX / 2);

    d[0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        Elem elem = q.top();
        q.pop();

        if (d[elem.i] < elem.distance) {
            continue;
        }

        for (auto edge : adjlist[elem.i]) {
            if (d[elem.i] + edge.c < d[edge.to]) {
                d[edge.to] = d[elem.i] + edge.c;
                q.push({edge.to, d[edge.to]});
            }
        }

        // for (int i = 0; i < n; i++) {
        //     cout << d[i] << ",";
        // }
        // cout << endl;
    }

    if (d[n - 1] == LONG_LONG_MAX / 2) {
        printf("%d\n", -1);
    } else {
        printf("%lld\n", d[n - 1]);
    }

    return 0;
}


Measured memory_bytes: 8568
use v5.18;
use warnings;

use constant MAX => 3;

chomp(my $line = <>);
my @cookies = split / /, $line;
my $count = 0;

if ( $cookies[0] == $cookies[1] && $cookies[1] == $cookies[2] ) {
  my ($is_odd) = grep { $_ % 2 == 1 } @cookies;
  say $is_odd ? 0 : -1;
  exit;
}

while (1) {
  my @harf = map {
    last if $_ % 2 == 1;
    $_ / 2;
  } @cookies;
  for (0 .. MAX - 1) {
    $cookies[$_] = $harf[ ($_ + 1) % MAX ] + $harf[ ($_ + 2) % MAX ];
  }
  $count += 1;
}
say $count;


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
bool f(int x) {
string s = to_string(x);
return s[0]==s[1] && s[1]==s[2];
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cout << fixed << setprecision(12);
  int x; cin>>x;
  while (!f(x)) x++;
  out(x);
  

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int A, B;
	cin >> A >> B;
	int K = (A+B)/2;
	if(std::abs(A-K)==std::abs(B-K))
		std::cout << K << std::endl;
	else
	 cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_STRING 600000

	int anX[100002];
	char sInput[MAX_STRING+1]="";

int main() {
	char* psInput;

	int i=0;
	int nPointNumber=0;
	int nFailed=0;
	int nTimeCounter=1;
	int nLeftTime=0;
	int nXDistance=0;
	int nYDistance=0;
	int nSumDistance=0;
	int nTempNumber=0;
	int nMagicNumber=0;
	int nSubTotal=0;
	int nTotal=0;
	int nOrgRoute=0;
	int nShortCutRoute=0;

	// read line 1
	gets(sInput);
	nPointNumber = atoi(sInput);

	anX[0]=0;

	// read line 2 ~
	gets(sInput);
	psInput = strtok(sInput," ");
	for (i=1;i<=nPointNumber;i++){
		anX[i] = atoi(psInput);
		psInput = strtok(NULL," ");
	}
	anX[nPointNumber+1]=0;

	for(i=1;i<=nPointNumber+1;i++){
		nSubTotal=nSubTotal+abs(anX[i]-anX[i-1]);
	}

	for(nMagicNumber=1;nMagicNumber<=nPointNumber;nMagicNumber++){
		nOrgRoute = abs(anX[nMagicNumber]-anX[nMagicNumber-1])+abs(anX[nMagicNumber+1]-anX[nMagicNumber]);
		nShortCutRoute = abs(anX[nMagicNumber+1]-anX[nMagicNumber-1]);

		printf("%d\n",nSubTotal-nOrgRoute+nShortCutRoute);
	}
    return 0;
}


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

using namespace std;
using ll = long long;

const int MOD = 998244353;

inline int lgput(int a, int x) {
  int res = 1;
  while (x > 0) {
    if (x % 2 == 1) res = 1LL * res * a % MOD;
    a = 1LL * a * a % MOD;
    x /= 2;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<ll> A(N);
  ll S = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    S += A[i];
  }
  vector<vector<ll>> dp(N + 1, vector<ll>(S + 1, 0));
  dp[0][0] = 1;
  auto dp2 = dp;

  for (int i = 0; i < N; i++) {
    for (int v = 0; v + A[i] <= S; v++) {
      dp[i + 1][v + A[i]] = (dp[i + 1][v + A[i]] + dp[i][v]) % MOD;
      dp[i + 1][v] = (dp[i + 1][v] + 2 * dp[i][v]) % MOD;

      dp2[i + 1][v + A[i]] = (dp2[i + 1][v + A[i]] + dp2[i][v]) % MOD;
      dp2[i + 1][v] = (dp2[i + 1][v] + dp2[i][v]) % MOD;
    }
  }
  ll all = (ll)lgput(3, N);
  ll com = 0;
  for (int i = S / 2 + 1; i <= S; i++)
    com = (com + 3 * dp[N][i]) % MOD;
  if (S % 2 == 0) {
    com = (com + 3 * dp[N][S / 2] % MOD - 6 * dp2[N][S / 2]) % MOD;
    com = (com + 3 * dp2[N][S / 2]) % MOD;
  }
  cout << (all - com < 0 ? all - com + MOD : all - com) << '\n';
  return 0;
}


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

int main(){
  int R, G, B, N;cin>>R>>G>>B>>N;
  int ans=0;

  for (int r=0;r<3001;++r){
    for (int g=0;g<3001;++g){
      if(N-R*r-G*g>=0&&((N-R*r-G*g)%B==0)) ans++;
    }
  }

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

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

#define int long long

signed main() {
	int h, w;
	long long ans = 1e11;
	cin >> h >> w;

	for(int h1 = 1 ; h1 <= h ; h1++){
		int area1 = h1 * w;
		
		int h2 = (h - h1)/2;
		int area2 = h2 * w;
		int area3 = (h-h1-h2) * w;
		int _min = min(area1, min(area2, area3));
		int _max = max(area1, max(area2, area3));
		ans = min(ans, _max - _min);
		
		int w2 = w/2;
		area2 = (h - h1) * w2;
		area3 = (h - h1) * (w - w2);
		_min = min(area1, min(area2, area3));
		_max = max(area1, max(area2, area3));
		ans = min(ans, _max - _min);
	}
	
	swap(w, h);
	for(int h1 = 1 ; h1 <= h ; h1++){
		int area1 = h1 * w;
		int h2 = (h - h1)/2;
		int area2 = h2 * w;
		int area3 = (h-h1-h2) * w;
		int _min = min(area1, min(area2, area3));
		int _max = max(area1, max(area2, area3));
		ans = min(ans, _max - _min);
		
		int w2 = w/2;
		area2 = (h - h1) * w2;
		area3 = (h - h1) * (w - w2);
		_min = min(area1, min(area2, area3));
		_max = max(area1, max(area2, area3));
		ans = min(ans, _max - _min);
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

/* //約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}*/

int main() {
  ll N;ll c=5,ans=0;
  cin >> N;
  if (N%2==1) {
    cout << 0 << endl;
    return 0;
  } 
  while(N/c>=1) {
    ans += (N/c)/2;
    c*=5;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n = input()
M = []
 
def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]
 
   for l in range(2, len(n)+1):
      for i in range(0, len(n)-l+1):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
 
   print m[0][len(n)-1]
 
for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

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

using namespace std;
using ll=int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi=vector<int>;
using vii=vector<vi>;
using vl=vector<ll>;
using vll=vector<vl>;
using tpi=tuple<int, int, int>;

using vqi=vector<queue<int>>;

int main() {
    using vsi=vector<set<int>>;
    int N;
    cin >> N;

    vii table(N + 1, vi(N + 1, -1));
    for (int i = 1; i <= N; i++) {
        int a;
        cin >> a;
        for (int j = 0; j < a; j++) {
            int x, y;
            cin >> x >> y;
            table[i][x] = y;
        }
    }

    using bs=bitset<15>;
    using vbi=vector<bs>;
    vbi v;
    for (int i = static_cast<int>(pow(2, N)) - 1; i >= 0; i--) {
        v.emplace_back(i);
    }

    int ans = -1;
    for (auto&& item:v) {
        bool satisfy = true;
        for (int i = 0; i < N; i++) {
            if (item[i] == 0) {
                continue;
            }
            for (int j = 1; j <= N; j++) {
                if (table[i + 1][j] == -1) {
                    continue;
                }

                if (table[i + 1][j] != item[j - 1]) {
                    satisfy = false;
                    break;
                }
            }
            if (!satisfy) {
                break;
            }
        }
        if (satisfy) {
            ans = max(ans, static_cast<int>(item.count()));
        }
    }

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


Measured memory_bytes: 896
#include<stdio.h>

int main()
{
	int mt[10],i,top[3],j,a;
	for(i=0;i<10;i++){
		scanf("%d",&mt[i]);
	}
	
	for(i=0;i<9;i++){
		for(j=0;j<9-i;j++){
			if(mt[j]>mt[j+1]){
				a=mt[j];
				mt[j]=mt[j+1];
				mt[j+1]=a;
			}
		}
	}
	
	printf("%d\n%d\n%d\n",mt[9],mt[8],mt[7]);
	return 0;
}

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

int main(){
    string s;
    cin >> s;

    int size = s.size();
    int kuro = 0;
    int shiro = 0;

    int flag = 1;

    rep(i, size){
        if(flag){
            if(s[i]=='1')   shiro++;
            else            kuro++;
            flag = 0;
        }else{
            if(s[i]=='1')   kuro++;
            else            shiro++;
            flag = 1;
        }
    }

    int ans = min(kuro, shiro);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
n = int(input())

town = [list(map(int, input().split())) for _ in range(n)]

distance = [[0]*n for _ in range(n)]
    
for i in range(n):
    for j in range(i,n):
        d = ( (town[i][0] - town[j][0])**2 + (town[i][1] - town[j][1])**2 ) ** 0.5
        distance[i][j] = d
        distance[j][i] = d

print(sum(map(sum, distance)) / n )


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define ll long long
using namespace std;



int main()
{
	string test;
	cin >> test;

	if (test == "ARC") {
		printf("ABC");
	} else {
		printf("ARC");
	}
	
	return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
using ll = long long;
using namespace std;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
//sort(a, a + N, greater<ll>())   // descend
//sort(a, a+N)                    //  ascend

/* 
void comb(vector<vector <ll> > &v) {
	ll mod=1000000007;
	rep (i,0,v.size()) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	rep (k,1,v.size()) {
		rep (j,1,k) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%mod;
		}
	}
}
/*main内でnCn~nC0 生成 **
vector<vector<ll> > v(n + 1, vector<ll>(n + 1, 0));
comb(v);
*/

int main(){
	ll n;
	cin>>n;
	ll a[110000];
	rep(i,0,n)cin>>a[i];
	sort(a,a+n);
	bool p=true;
	if(a[0]==0)rep(i,1,n-1){
		if(a[i]!=a[i+1]){p=false;break;}
		i++;
	}
	if(a[0]!=0)rep(i,0,n-1){
		if(a[i]!=a[i+1]){p=false;break;}
		i++;
	}
	ll g=1;
	rep(i,0,n/2) g=(g*2)%1000000007;
	if(p==false)cout<<"0";
	else cout<<g;
}





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

const int N = 1e5 + 5;

int dp[N][2];
int dw[N][2];
int asd[N];
int parent[N];
vector<int> adj[N];
int n, MOD;

void read() {
  scanf("%d %d", &n, &MOD);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
}

int solve(int pos, int color, int prv) {
  int &ret = dp[pos][color];
  if (ret != -1) return ret;

  parent[pos] = prv;
  ret = 1 % MOD;
  for (int nex : adj[pos]) {
    if (nex == prv) continue;

    int ways = solve(nex, 0, pos);
    if (color == 1) {
      ways = (ways + solve(nex, 1, pos)) % MOD;
    }

    ret = 1ll * ret * ways % MOD;
  }

  return ret;
}

void dfs(int now, int prv) {
  // printf("sekarang %d\n", now);
  asd[now] = (asd[now] + 1) % MOD;

  vector<int> prefBoth, sufBoth;
  vector<int> prefZero, sufZero;

  prefBoth = prefZero = {1 % MOD};
  for (int nex : adj[now]) {
    if (nex == prv) continue;

    prefBoth.push_back((solve(nex, 0, now) + solve(nex, 1, now)) % MOD);
    prefZero.push_back(solve(nex, 0, now));
  }
  prefZero.push_back(1 % MOD);
  prefBoth.push_back(1 % MOD);

  sufZero = prefZero;
  sufBoth = prefBoth;

  for (int i = 1; i < prefZero.size(); i++) {
    prefBoth[i] = 1ll * prefBoth[i] * prefBoth[i - 1] % MOD;
    prefZero[i] = 1ll * prefZero[i] * prefZero[i - 1] % MOD;
  }

  for (int i = sufZero.size() - 2; i >= 0; i--) {
    sufBoth[i] = 1ll * sufBoth[i] * sufBoth[i + 1] % MOD;
    sufZero[i] = 1ll * sufZero[i] * sufZero[i + 1] % MOD;
  }

  int cnt = 0;

  for (int nex : adj[now]) {
    if (nex == prv) continue;
    cnt++;

    asd[nex] = asd[now];
    asd[nex] = 1ll * asd[nex] * prefBoth[cnt-1] % MOD;
    asd[nex] = 1ll * asd[nex] * sufBoth[cnt+1] % MOD;
    // asd[nex] = (asd[nex] + 1ll * prefBoth[cnt-1] * sufBoth[cnt+1]) % MOD;

    dfs(nex, now);
  }
}

void work() {
  memset(dp, -1, sizeof dp);
  asd[1] = 0;
  solve(1, 0, -1);
  dfs(1, -1);

  for (int i = 1; i <= n; i++) {
    int ways = asd[i];

    ways = 1ll * ways * solve(i, 1, parent[i]) % MOD;

    // printf("i %d parent %d ways %d\n", i, parent[i], ways);

    printf("%d\n", (ways) % MOD);
  }
}

int main() {
  read();
  work();
  return 0;
}

Measured memory_bytes: 35072
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int N, Q;
    string S;
    cin >> N >> S >> Q;

    vector<set<int>> A(26);
    for (int i = 0; i < N; i++) {
        A[S[i] - 'a'].insert(i);
    }

    while (Q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int i;
            char c;
            cin >> i >> c;
            i--;

            for (auto&& a : A) {
                a.erase(i);
            }
            A[c - 'a'].insert(i);

        } else {
            int l, r;
            cin >> l >> r;
            l--, r--;

            int res = 0;
            for (auto&& a : A) {
                if (a.lower_bound(l) != a.upper_bound(r)) {
                    res++;
                }
            }

            cout << res << '\n';
        }
    }
}

Measured memory_bytes: 24184
def b170(x, y):

    for i in range(x+1):
        if 4*i + 2*(x-i) == y:
            return "Yes"

    return "No"

def main():
    x, y = map(int, input().split())
    print(b170(x, y))

if __name__ == '__main__':
    main()

Measured memory_bytes: 9172
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
// clang-format on

int N;
int s[MAX_N];

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  REP(i, N) cin >> s[i];

  priority_queue<int, vector<int>, greater<int>> q;

  int sum = 0;
  REP(i, N)
  {
    sum += s[i];
    if (s[i] % 10 != 0) q.push(s[i]);
  }

  if (sum % 10 != 0) {
    cout << sum << endl;
    return 0;
  }

  if (q.empty()) {
    cout << 0 << endl;
    return 0;
  }

  sum -= q.top();

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import deque

h, w = map(int, input().split())
p = [list(input()) for i in range(h)]

# メモ配列
INF = 10**7
# memo = [[INF]*w for i in range(h)]

# 探索用ベクトル
vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

# 幅探索用キューの準備
# 白マスをカウント
q = deque()
bcnt = 0
for i, vi in enumerate(p):
    for j, vj in enumerate(vi):
        if vj == '#':
            q.appendleft((j, i))
            bcnt+=1
            
qans = deque()
            
def bfs(q):
    for i in range(INF):
        # キューが空なら終了
        if len(q) == 0:
            return qans

        # キューから一つ取り出す
        x, y = map(int, q.pop())
#         print('xy', x, y)

        # 4方向のいずれかに白があれば、黒にする
        for j in range(4):
            nx, ny = x+vx[j], y+vy[j]

            # エリア外 or 黒色なら探索しない
            if nx < 0 or w <= nx or ny < 0 or h <= ny or p[ny][nx] == '#':
                continue

            p[ny][nx] = '#'
            qans.appendleft((nx, ny))

def printmap(a):
    for i in a:
        print(i)
        
# print(q)
# printmap(p)
for i in range(INF):
    qans = deque()
    q = bfs(q)
#     print(q)
#     printmap(p)
    # キューが空なら終了
    if len(q) == 0:
        ans = i
        break
    
print(ans)
# print(q)

Measured memory_bytes: 115804
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,flag=0,rem,i;
    vector<int>s;
    cin>>k;
    while(k>0)
    {
        rem=k%10;
        s.push_back(rem);
       k=k/10;
    }
    for(i=0;i<3;i++)
    {
        if(s[i]==7)
        {
        flag=1;
        break;
        }
    }
    if(flag==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3564
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pop_b pop_back
#define pf push_front
#define pop_f pop_front
#define mt make_tuple
#define eb emplace_back
#define sf(x) sizeof(x)
#define len(x) x.length()
#define sz(x) x.size()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define LB(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define UB(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld; 
typedef vector<int> vi;
typedef vector<set<ll>> vset;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef deque<ll> dql;
typedef deque<int> dqi;
typedef unsigned long long ull;
typedef tuple<int,int,int> State;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ", ";
	err(++it, args...);
	cout<<"\n";
}

#define vmax(type)   std::numeric_limits<type>::max()
#define vmin(type)   std::numeric_limits<type>::min()
#define each(a,x) for( auto &a:(x))
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rep2(i, l, r) for (ll i = (l); i < (r); i++)
#define rep2r(i, l, r) for (ll i = (r) - 1; i >= (l); i--)
#define range(a) a.begin(), a.end()
#define deb(x) cout<<#x<<" "<<x<<endl;
#define cinai(a, n) vi a(n); rep(i, n) { cin>>a[i]; }
#define cinal(a, n) vl a(n); rep(i, n) { cin>>a[i]; }
#define coutai(a, n) rep(i, n) { cout<<a[i]<<" "; } ent;
#define coutal(a, n) rep(i, n) { cout<<a[i]<<" "; } ent;
#define ent cout<<endl;
#define resize_vec(a) a.resize(unique(a.begin(), a.end()) - a.begin());
#define ms(dp, x) memset(dp, x, sf(dp))
#define endl '\n'

ll powm(ll a, ll b, ll mod) {
	ll res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

const ll mod = 1e9 + 7;
const ll N = 1000005;
const ll inf = 1e9;

void solve()
{
	string s, t;
	cin>>s>>t;
	int ans = 1e5;
	rep(i, s.length()){
		int ok = 0;
		if(i+t.length() > s.length())
			break;
		rep(j, t.length()){
			if(s[i+j] != t[j]){
				ok++;
			}
		}
		ans = min(ans, ok);
	}
	cout<<ans<<endl;
}

// #define _DEBUG 
// #define testCases
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc = 1;
#ifdef testCases
	cin>>tc;
#endif
	while(tc--)
	{
#ifdef _DEBUG
	int tt = clock();
#endif
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}




Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L
#define MOD 1000000007
//setprecision(15)
#define MAX_L 2000
#define MAX_H 666
ll dp[MAX_H+1][MAX_L+1];
ll dp2[MAX_H+1][MAX_L+1];
int main() {
	int S; cin >> S;
	for (int i = 3; i <= MAX_L; i++) {
		dp[1][i] = 1;
		dp2[1][i] = dp2[1][i-1] + 1;
	}
	for (int i = 2; i <= MAX_H; i++) {
		for (int j = i*3; j <= MAX_L; j++) {
			dp[i][j] = dp2[i-1][j-3];
			dp2[i][j] = (dp2[i][j-1] + dp[i][j]) % MOD;
		}
	}
	ll ans = 0; int cnt = 1;
	while (1) {
		ans = (ans + dp[cnt][S]) % MOD;
		cnt++;
		if (cnt > MAX_H || dp[cnt][S] == 0) break;
	}
	cout << ans << endl;
}

Measured memory_bytes: 18620