akhauriyash/Code-Regression huggingface dataset:
#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 MAX = 1000;
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)

// ax+by=gcd(a,b)の解(x,y)を求める
ll extgcd(ll a, ll b, ll& x, ll& y) {
	ll d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a/b) * x;
	} else {
		x = 1; y = 0;
	}
	return d;
}

ll mod_inverse(ll a, ll m) {
	ll x, y;
	extgcd(a, m, x, y);
	return (m + x % m) % m;
}

#define MAX_P 1000001
ll fact[MAX_P];	// n! mod p のテーブル O(p)

void make_fact(ll p) {
	ll n, wp;
	for (ll i = 0; i < MAX_P; i++) {
		if (i == 0) n = 1;
		else n = (n * i) % p;
		fact[i] = n;
	}
}

// n!=a p^eとしたときのa mod pを求める。O(log_p n)
ll mod_fact(ll n, ll p, ll& e) {
	e = 0;
	if (n == 0) return 1;

	// pの倍数の部分を計算
	ll res = mod_fact(n/p, p, e);
	e += n / p;

	// (p-1)!≡-1なので,(p-1)!^(n/p)はn/pの偶奇だけで計算できる
	if (n/p % 2 != 0) return res * (p - fact[n%p]) % p;
	return res * fact[n%p] % p;
}

// nCk mod pを求める。O(log_p n)
ll mod_comb(ll n, ll k, ll p) {
	if (n < 0 || k < 0 || n < k) return 0;
	ll e1, e2, e3;
	ll a1 = mod_fact(n, p, e1), a2 = mod_fact(k, p, e2), a3 = mod_fact(n-k, p, e3);
	if (e1 > e2 + e3) return 0;
	return a1 * mod_inverse((a2*a3)%p, p) % p;
}

int main() {
	ll x, y; cin >> x >> y;
	make_fact(MOD);
	ll ax, ay;
	ax = x;
	while(1) {
		ll tmp = 2 * ax;
		if (y == tmp) {
			if (ax == x) {
				ay = 0; break;
			}
		}
		if (tmp < y){
			ay = y - tmp;
			if (ax + ay * 2 == x) {
				break;
			}
		}
		if (ax == 0) {
			ax = -1; ay = -1; break;
		} else if (ax == 1) {
			ax = 0;
		} else {
			ax -= 2;
		}
	}
	if (ax == -1 && ay == -1) {
		cout << "0" << endl; return 0;
	}
	ll ret = mod_comb(ax+ay, ax, MOD);
	cout << ret << endl;
}

Measured memory_bytes: 11456
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
struct edge {int to, cost;};
int x[114514];
int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a%b);
}
signed main() {
	int n, X; cin >> n >> X;
	rep(i, n)cin >> x[i];
	x[n] = X; n++;
	sort(x, x + n);
	vector<int>V;
	rep(i, n - 1)V.push_back(abs(x[i] - x[i + 1]));
	int mg = inf;
	rep(i, V.size()) {
		mg = min(mg, gcd(V[i], V[0]));
	}
	cout << mg << endl;
}

Measured memory_bytes: 2168
#include <stdio.h>
int main() {
	char str[1001], line[1016], buf[1001], *p1, *p2;
	int q, a, b, n;
	scanf("%s\n%d\n", str, &q);  // read q  
	while (q--) {                // loop q times
		for (p1 = line; (*p1 = getchar()) != '\n';)p1++;  // read line
		sscanf(line, "%*s %d %d%n", &a, &b, &n);          // parse it
		switch (line[2]) {
			case 'p':  // replace
				*p1 = '\0';
				for (p1 = line + n + 1, p2 = str + a; *p1; *p2++ = *p1++);
				break;
			case 'v':  // reverse
				p1 = buf;
				for (p2 = str + a; p2 <= str + b; *p1++ = *p2++);
				for (p2 = str + a; p2 <= str + b; *p2++ = *--p1);
				break;
			case 'i':  // print
				for (p1 = str + a; p1 <= str + b; putchar(*p1++));
				putchar('\n');
		}
	}
}


Measured memory_bytes: 2076
let range start stop =
  let rec iter l i = match i-start with
    | 0 -> start::l
    | _ -> iter (i::l) (i-1)
  in if start > stop then [] else iter [] stop

let find v n x =
  let check v1 v2 x =
    let v3 = x-(v1+v2) in
    v2 < v3 && v3 <= n
  in
  let rec iter i c =
    if i > n then c
    else iter (i+1) (if check v i x then c+1 else c)
  in iter (v+1) 0
    

let () =
  let rec loop () =
    match Scanf.scanf "%d %d\n" (fun n x -> n,x) with
    | 0,0 -> ()
    | n,x ->
      let l = range 1 (if n < x/3 then n else x/3) in
      let c = List.fold_left
          (fun acc v -> acc + (find v n x)) 0 l in
      Printf.printf "%d\n" c;
      loop ()
  in
  loop ()

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

#define debug(x) cerr<<#x<<"="<<x<<endl;
#define m(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int MAXN=1e5+10;
int a[3][105],dp[3][105];

int main(){
	int n;
	scanf("%d",&n);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		dp[1][i]=dp[1][i-1]+a[1][i];
		dp[2][i]=max(dp[2][i-1],dp[1][i])+a[2][i];
	}
	printf("%d\n",dp[2][n]);
	return 0;
}

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

int main() {
  long N, A, B; // n, blue, red
  cin >> N >> A >> B;

  long ball = 0;
  long rem;

  ball += N/(A+B)*A;
  rem = N%(A+B);
  ball += min(A, rem);

  cout << ball << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define INF (1e9 + 7)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string S; cin >> S;
  vector<int> ans(S.size(), 0);
  REP(i, S.size()){
    if(S[i] == 'A'|| S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
      if(i == 0){
        ans[i]++;
      }else{
        ans[i] = ans[i-1] + 1;
      }
    }
  }
  int ANS = 0;
  for(auto &i : ans){
    ANS = max(ANS, i);
  }
  cout << ANS << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int A = sc.nextInt();
        int[] x = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            x[i] = sc.nextInt();
        }

        long[][][] dp = new long[N + 1][N + 1][N * A + 1];
        for (int i = 0; i < N; ++i) {
            dp[i][0][0] = 1;
        }

        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= i; ++j) {
                for (int k = 1; k <= N * A; ++k) {
                    if (k < x[i]) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]];
                    }
                }
            }
        }

        long ans = 0;
        for (int j = 1; j <= N; ++j) {
            ans += dp[N][j][j * A];
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 87616
require 'pp'

n = gets.chomp!.to_i
r = gets.chomp!

po = 'A'.codepoints[0]
po2 = 'Z'.codepoints[0]
r.chars.each do |ch|
    c = ((ch.codepoints[0] - po + n) % po + po)
    if c > po2
        print (c - 26).chr
    else
        print c.chr
    end
end

puts ""


Measured memory_bytes: 4988
while True:
    H, W = list(map(int, input().split()))
    if H == 0 and W == 0:
        break
    for i in range(H):
        if i % 2 == 0 and W % 2==0:
            print("#."*int(W/2))
        elif i % 2 == 0 and W % 2 ==1:
            print("#."*int(W/2)+"#")
        elif i % 2 == 1 and W % 2==0:
            print(".#"*int(W/2))
        elif i % 2 == 1 and W % 2 ==1:
            print(".#"*int(W/2)+".")
    print()    


Measured memory_bytes: 5616
#include<stdio.h>

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

    int k;
    scanf("%d", &k);

    int H[n];

    int i;
    for(i = 0; i < n; i++){
        scanf("%d", &H[i]);
    }

    int cnt = 0;
    for(i = 0; i < n; i++){
        if(H[i] >= k){
            cnt++;
        }
    }

    printf("%d\n", cnt);

    return 0;
}

Measured memory_bytes: 512
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    ans = pow(10,N,MOD) - pow(9,N,MOD)*2 + pow(8,N,MOD)
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9236
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define pf push_front
#define ins insert

//{
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...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

int n,ans;
set<pint> aa;

main(){
	cin>>n;
	rep(i,n){
		int t;
		cin>>t;
		if(aa.count(mp(min(i+1,t),max(i+1,t)))==0){
			aa.ins(mp(min(i+1,t),max(i+1,t)));
		}else ans++;
	}
	dans;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,double>P;
struct ed{int to;double co;};
ed edge;
int num[101],n,st,go,m,pre[101];
double x[101],y[101],d[101];
vector<ed>v[101];
int main(){
  while(cin>>n,n){
    map<int,int>m1,m2;
    r(i,101)v[i].clear();
    r(i,n)cin>>num[i]>>x[i]>>y[i],m1[num[i]]=i,m2[i]=num[i];
    r(i,n)r(j,n)if(i!=j){
      double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      edge.co=dis,edge.to=j;
      if(dis<=50)v[i].push_back(edge);
    }
    cin>>m;
    while(m--){
      memset(pre,-1,sizeof(pre));
      int stt,goo;
      cin>>stt>>goo;st=m1[stt];go=m1[goo];
      r(i,101)d[i]=1e9;
      d[st]=0;
      priority_queue<P,vector<P>,greater<P> >q;
      q.push(P(st,0));
      while(!q.empty()){
        P pp=q.top();q.pop();
        int tt=pp.first;
        double di=pp.second;
        if(d[tt]<di)continue;
        r(i,v[tt].size()){
          edge=v[tt][i];
          if(d[edge.to]>di+edge.co){
            pre[edge.to]=tt;
            d[edge.to]=di+edge.co;
            q.push(P(edge.to,di+edge.co));
          }
        }
      }
      if(d[go]==1e9)cout<<"NA"<<endl;
      else{
        vector<int>vv;
        for(;go!=-1;go=pre[go])vv.push_back(go);
        reverse(vv.begin(),vv.end());
        r(i,vv.size()){
          if(i)cout<<' ';
          cout<<m2[vv[i]];
        }
        cout<<endl;
      }
    }
  }
}

Measured memory_bytes: 3280
N, M = map(int, input().split())
H = list(map(int, input().split()))
g = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  g[a-1].append(b-1); g[b-1].append(a-1)

ans = 0
for i in range(N):
  neighbors = g[i]
  h = H[i]
  res = True
  for node in neighbors:
    res *= h > H[node]
  ans += res

print(ans)

Measured memory_bytes: 29420
N,T = map(int,input().split())
A = list(map(int,input().split()))
minP,prof,pc = 10**9+1,0.5,0
for i in range(N):
    minP = min(minP,A[i])
    d = A[i]-minP
    if d > prof:
        prof = d
        pc = 1
    elif d == prof:
        pc += 1
print(pc)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N], dp[3][N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin>>a[i]>>b[i]>>c[i];
	}
	dp[0][0] = a[0];
	dp[1][0] = b[0];
	dp[2][0] = c[0];
	for(int i = 1; i < n; ++i){
		dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
		dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
		dp[2][i] = c[i] + max(dp[0][i-1], dp[1][i-1]);
	}
	cout<<max(dp[0][n-1], max(dp[1][n-1], dp[2][n-1]))<<endl;
}

Measured memory_bytes: 2560
n = input()
a = int(n[:2])
b = int(n[2:])
x = 0 < a <= 12
y = 0 < b <= 12
if x and y :
    print('AMBIGUOUS')
elif not x and y:
    print('YYMM')
elif x and not y:
    print('MMYY')
else:
    print('NA')

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

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;
 
public:
  u64 a;
 
  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};


typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a[ohara],b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    using mint=modint<MOD>;
    
    cin>>n>>m;
    rep(i,n)cin>>a[i];
    rep(i,m)cin>>b[i];

    mint dp[n+10][m+10]={};
    rep(i,n+1)dp[i][0]=1;
    rep(i,m+1)dp[0][i]=1;
    rrep(i,1,n+1){
        rrep(j,1,m+1){
            dp[i][j]+=dp[i-1][j]+dp[i][j-1];
            if(a[i-1]!=b[j-1])dp[i][j]-=dp[i-1][j-1];
        }
    }
    Cout(dp[n][m].value());
    return 0;
}


Measured memory_bytes: 33920
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            :oyhhhhhhyo:    
#define next         .sdNNNmNNNNNNNmds. 
#define y0          -hNNNNy`yNNNNNN`/Nh-
#define y1          mNNNNNd+dNNNNNN+sNNm
#define yn          mNNNNNNNNy--:smNNNms
#define tm          .+oooooosyysooooo+- 
#define read               :yhy/        
#define rank              :mNmo         
#define index              ... 
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 55;
int a[N];
int n;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int cnt = 0;
    rep(i, 1, n) {
        cin >> a[i];
        cnt += a[i] != i;
    }
    cout << (cnt == 0 || cnt == 2 ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
lis = []

for i in range(N):
    s = input()
    if i == 0:
        end_w = s[0]

    if s in lis:
        print("No")
        exit()
    else:
        if s[0] == end_w:
            lis.append(s)
            end_w = s[-1]
        else:
            print("No")
            exit()

print("Yes")


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

int main(){
    int n,w;
    cin>>n>>w;
    long long a[n],b[n];
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    long long ans=0;
    long long dp[w+1]={};
    for(int i=0;i<n;i++){
        for(int j=w;j>-1;j--){
            if(j+a[i]<=w){
            dp[j+a[i]]=max(dp[j+a[i]],dp[j]+b[i]);
            ans=max(ans,dp[j+a[i]]);
            }
        }
        cerr<<i<<" "<<ans<<endl;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	if(a<=12&&a>=6) b=b/2;
	if(a<6) b=0;
	cout<<b;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n;
bool o=true;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a%2==1)o=false;
    }
    if(o)cout<<"second\n";
    else cout<<"first\n";
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

func main() {
	io := NewIo(os.Stdin, os.Stdout)
	defer io.Flush()
	k := io.NextInt()
	a := io.NextInt()
	b := io.NextInt()
	for i := a; i <= b; i++ {
		if i%k == 0 {
			io.Println("OK")
			return
		}
	}
	io.Println("NG")
}

// Io is I/O object
type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

// NewIo returns a new Io instance
func NewIo(r io.Reader, w io.Writer) *Io {
	return &Io{
		reader: bufio.NewReader(r),
		writer: bufio.NewWriter(w),
	}
}

// Flush flushes writer
func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

// NextLine scans a line from stdin
func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

// Next return a word from stdin
func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

// NextInt returns an integer from stdin
func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

// Println is a wrapper of fmt.Fprintln
func (io *Io) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


Measured memory_bytes: 1776
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<bitset>
#include <iomanip>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000;

bool com(P a,P b){
	return a.second<b.second;
}

int n,m,p[100010],y[100010];
pair<int,int> a[100010];
map<int,int> h;

int main(){
	int count=0;
	cin>>n>>m;
	REP(i,m){
		cin>>p[i]>>y[i];
		a[i]={p[i],y[i]};
	}
	sort(a,a+m);
	for(int i=0;i<m;i++){
		DEB(a[i].first)DEB(a[i].second)END
		if(0<i&&a[i-1].first<a[i].first){
			count=0;
		}
		h[a[i].second]=count+1;
		count++;
	}
	REP(i,m){
		cout<<setw(6)<<setfill('0')<<p[i];
		cout<<setw(6)<<setfill('0')<<h[y[i]]<<endl;
	}
	return 0;
}

Measured memory_bytes: 7808
var
	A,B,C,D,T,tmp:Longint;
function gcd(a,b:Longint):Longint;
begin
	if b=0 then gcd:=a else gcd:=gcd(b,a mod b);
end;
begin
	read(A,B,C,D);
	A:=A-C;
	B:=B-D;
	if A<0 then A:=-A;
	if B<0 then B:=-B;
	if(A=0)or(B=0)then begin
		writeln(0);
		exit;
	end;
	d:=gcd(A,B);
	A:=A div d;
	B:=B div d;
	if A>B then begin
		tmp:=A;
		A:=B;
		B:=tmp;
	end;
	if A=B then T:=A else T:=A+B-1;
	writeln(T*d);
end.


Measured memory_bytes: 128
//psudora
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define mod 1000000007
#define fast ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)

int main()
{
	fast;
    int k, n;
 
    cin >> k >> n;
 
    int a[n + 5];
    vector < int > b;
 
    for(int i = 0; i < n; i++) cin >> a[i];
 
    for(int i = 0; i < n - 1; i++) b.push_back(a[i + 1] - a[i]);
 
    b.push_back(k - a[n - 1] + a[0]);
 
    int sum = 0;
 
    sort(b.begin(), b.end());
 
    for(int i = 0; i < b.size() - 1; i++) sum += b[i];
 
    cout << sum << endl;
 
    return 0;
}


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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)


void func(long long N, long long K){
    lli sum = 0;
    if(K==0){
        cout<<N*N<<endl;
        return;
    }
    for(lli i=K+1;i<=N;i++){
        lli a = (i-K)*(N/i);
        sum += (a+ max(0LL,N%i-K+1));
    }
    cout<<sum<<endl;
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    func(N, K);
    return 0;
}


Measured memory_bytes: 384
/* Coached by rainboy */
#include <stdio.h>

int main() {
	int n, i, k, ans;

	scanf("%d", &n);
	ans = k = 0;
	for (i = 0; i < n; i++) {
		int p;

		scanf("%d", &p);
		if (p == i + 1)
			k++;
		else
			ans += (k + 1) / 2, k = 0;
	}
	ans += (k + 1) / 2;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int C = sc.nextInt();
		int B = sc.nextInt();
		if ((A<B && B<C) || (C<B && B<A)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 21972
# Nが3の倍数かつ、配列が「aがm個とbがm個とcがm個」かつ、a^b == c ならTrue

n = int(input())
nums = list(map(int, input().split()))

if max(nums) == 0:
    print('Yes')
    exit()

if n % 3:
    print('No')
    exit()

m = n // 3
nums.sort()
for i in range(m-1):
    if nums[i] != nums[i+1] or nums[m+i] != nums[m+i+1] or nums[2*m+i] != nums[2*m+i+1]:
        print('No')
        exit()

if nums[0] ^ nums[m] == nums[2*m]:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 14212
H,W = gets.split.map &:to_i
S = (0...H).map{ gets.chomp.split("") }
walls = S.flatten.count("#")

bfs = [0]
visited = {}
d = 1
road = nil
while bfs.size > 0
  d += 1
  bfs.each{ |w| visited[w] = 1 }
  nbfs = []
  bfs.each{ |w|
    i = w/W; j = w % W
    [
      [i+1,j],
      [i-1,j],
      [i,j+1],
      [i,j-1],
    ].map{ |u,v|
      w = u*W+v
      if 0 <= u && u < H && 0 <= v && v < W && S[u][v] == "." && !visited[w]
        nbfs << w
      end
    }
  }
  bfs = nbfs.uniq
  if bfs.include?(H*W-1)
    road = d
    break
  end
end

p road ? H*W - road - walls : -1

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

int main(){
  int N, K, cnt;
  string s;
  cin >> N >> K;
  cin >> s;
  cnt = 0;
  for (int i=0;i<N-1;i++){
    if (s[i]==s[i+1]) cnt++;
  }
  cout << min(cnt+K*2,N-1) << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
int main() {
    string S;
    cin>>S;
    int ans=0;
    int a=S.size();
    for(int i=0; i<a/2; i++){
        if(S.at(i)!=S.at(a-1-i)){
            ans++;
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>

int main(){
    char ch;
    
    scanf("%c",&ch);
    
    if(ch=='A'){
        printf("T\n");
    }
    
    else if(ch=='T'){
        printf("A\n");
    }
    
    else if(ch=='C'){
        printf("G\n");
    }
    
    else if(ch=='G'){
        printf("C\n");
    }
    
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int n,c[9],r,i;
	fill(c,c+9,0);
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> r;
		++c[min(8,r/400)];
	}
	r = 0;
	for(i=0; i<8; ++i){
		if(c[i]){
			++r;
		}
	}
	cout << max(1,r) << " " << (r+c[8]) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll N;
  cin >> N;

  double ans = (N+1)/2;
  ans /= (double)N;
  cout << fixed << setprecision(10) << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	if ReadInt() == 1 {
		fmt.Println("Hello World")
	} else {
		fmt.Println(ReadInt() + ReadInt())
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


Measured memory_bytes: 1840
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> void pr_vec(vector<T> &v, char ep=' '){int n=v.size();REP(ni,n){cout<<v[ni];if(ni!=n-1)cout<<ep;}cout<<endl;};
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N,M,X;
    cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M, 0));
    REP(i, N){
        cin >> C[i];
        REP(j, M) cin >> A[i][j];
    }

    ll ans = MAXINF;
    REP(i, 1<<N){
        vector<ll> tot(M);
        ll m = 0;
        REP(j, N){
            if(i&(1<<j)){
                m += C[j];
                REP(k, M){
                    tot[k] += A[j][k];
                }
            }
        }
        bool f = true;
        REP(j, M){
            if(tot[j] < X) f = false;
        }

        if(f){
            chmin(ans, m);
        }
    }

    if(ans == MAXINF) pr(-1);
    else pr(ans);
}

Measured memory_bytes: 3632
numbers = list(map(int, input().split(" ")))

arr_a = []
arr_b = []
matrix = []

for i in range(numbers[0]):
    arr_a = list(map(int, input().split(" ")))
    arr_a.append(sum(arr_a))
    matrix.append(arr_a)
    
for i in range(numbers[1]):
    total = 0
    for j in range(numbers[0]):
        total += matrix[j][i]
    arr_b.append(total)

arr_b.append(sum(arr_b))
matrix.append(arr_b)

for i in range(numbers[0] + 1):
    for j in range(numbers[1] + 1):
        if j == numbers[1]:
            print(matrix[i][j])
            
        else:
            print(matrix[i][j], end="")
            print(" ", end="")


Measured memory_bytes: 6748
module Main where

import           Control.Monad
import           Data.List
import           Data.Ord
import           Data.List.Split
import           Data.Array.IO
import qualified Data.Vector.Unboxed as V

main :: IO ()
main = do
  [a, b] <- map read . words <$> getLine :: IO [Int]
  print . length $ filter ok [a .. b]
  where
    ok a = let s = show a 
           in s == reverse s


Measured memory_bytes: 1020
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		
		String s = fs.next();
		
		for(int i = 0; i < s.length()/2 ; i++) {
			if(s.charAt(i) != s.charAt(s.length() - i -1)) {
				System.out.println("No");
				return;
			}
		}
		
		for(int i = 0; i < ((s.length() - 1)/2)/2 ; i++) {
			if(s.charAt(i) != s.charAt((s.length() - 1)/2 - i - 1)) {
				System.out.println("No");
				return;
			}
		}
		
		for(int i = (s.length()+3)/2 - 1; i < s.length(); i++) {
			if(s.charAt(i) != s.charAt(s.length() - (i - ((s.length()+3)/2 - 1))-1)) {
				System.out.println("No");
				return;
			}
		}
		
		
		System.out.println("Yes");
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


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

bool u[10000009];

signed main(){
    int n;
    cin>>n;
    int sum=0;
    vector<int>v;
    for(int i=2;i<=10000008;i++)if(!u[i]){
        v.push_back(i);
        for(int j=i+i;j<10000008;j+=i){
            u[j]=1;
        }
    }

    r(i,v.size()){
        if(v[i]>n)break;
        if(!u[2+v[i]])sum++;
    }
    cout<<sum*2<<endl;
}



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

#define ll long long
#define deb(x) cerr << #x << ":" << x << "\n"
#define all(x) x.begin(),x.end()
#define sz(x) x.size()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

void solve()
{
	int x;
	cin>>x;
	cout<<8-((x-400)/200)<<"\n";
}

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int GCD(int a, int b){
   return b ? GCD(b, a%b) : a;
}

int LCM(int a, int b){
   return (a * b)/(GCD(a, b));
}

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

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

   return 0;
}

Measured memory_bytes: 256
macro_rules! scan {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };

    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
}

fn main() {
    let (n, k) = scan!(usize, usize);
    println!("{}", n - k + 1);
}


Measured memory_bytes: 4352
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int k = sc.nextInt();
    int c = 0;
    for(int i=0; i<n; i++){
      int h = sc.nextInt();
      if(h>=k){
        c++;
      }
    }
    System.out.println(c);
  }
}

Measured memory_bytes: 46352
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}


int main(){
  int w = 0,e = 0,n;
  cin >> n;
  string s;
  cin >> s;
  rep(i,n){
    if(s[i] == 'W') w++;
    if(s[i] == 'E') e++;
  }
  int ans = n + 1;
  int rw = 0,re = 0;
  rep(i,n){
    if(s[i] == 'W') w--;
    if(s[i] == 'E') e--;
    ans = min(ans,rw+e);
    if(s[i] == 'W') rw++;
    if(s[i] == 'E') re++;
  }
  cout << ans << endl;
  return 0;
}


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


using namespace std;



const int MAXN = 500 + 23;







int n, x[MAXN], z[MAXN * MAXN];
bitset<MAXN * MAXN> mark;


struct cmp {
	bool operator () (int a, int b) {
		return x[a] <= x[b];
	}
};
struct cmp2 {
	bool operator () (int a, int b) {
		return x[a] >= x[b];
	}
};


set<int, cmp> s;
set<int, cmp2> t;




int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		x[i]--;
		z[x[i]] = i;
		mark[x[i]] = true;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			s.insert(i);
	for (int i = 0; i < n * n; i++) if (!mark[i]) {
		if (s.empty()) break;
		int f = *s.begin();
		s.erase(s.begin());
		if (x[f] < i) return cout << "No", 0;
		z[i] = f;
		mark[i] = true;
	}
	if (!s.empty()) return cout << "No", 0;
	for (int i = 0; i < n; i++)
		for (int j = i; j < n - 1; j++)
			t.insert(i);
	for (int i = n * n - 1; ~i; i--) if (!mark[i]) {
		if (t.empty()) break;
		int f = *t.begin();
		t.erase(t.begin());
		if (x[f] > i) return cout << "No", 0;
		z[i] = f;
		mark[i] = true;
	}
	if (!t.empty()) return cout << "No", 0;
	cout << "Yes\n";
	for (int i = 0; i < n * n; i++) cout << z[i] + 1 << ' ';
	return 0;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define go(i,x,a) for(int i=a;i<x;i++)
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,m,a[maxn],head[maxn],k,in[maxn],rt;
int tl;
bool ans=0;
ll up[maxn],q[maxn];

struct edd{
	int nxt,v;
}e[maxn*2];

inline void add(int a,int b){
	e[k].v=b; e[k].nxt=head[a]; head[a]=k++;
	e[k].v=a; e[k].nxt=head[b]; head[b]=k++;
}

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

void dfs(int u,int fa){
	if(ans) return;
	if(in[u]==1){
		up[u]=a[u];return;
	}
	ll d,big=0;tl=0;
	for(int i=head[u];i+1;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		if(ans) return;
		up[u]+=up[v],big=max(big,up[v]);//算出石头最多的子节点 
	}
	//我们在“子节点自行解决的时候 ”，子节点总权值-2，父节点权值-1 
	if(big>up[u]-big) d=up[u]-big;
	else d=up[u]/2;//能够“自行解决 ”的数量 
	if(a[u]>up[u]){ans=1;return;}
	if(up[u]-a[u]>d){ans=1;return;}//如果需要“自行解决 ”的数量大于能够“自行解决 ”的数量，不成立 
	up[u]-=2*(up[u]-a[u]); //减去要“自行解决 ”的数量
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(head,-1,sizeof(head)); k=0;
	n=rd(); int x,y;
	go(i,n+1,1) a[i]=rd();
	go(i,n,1){ x=rd(); y=rd(); add(x,y); in[x]++; in[y]++; }
	if(n==2){
		if(a[1]!=a[2]) printf("NO");
		else puts("YES");
	}
	else{
		go(i,n+1,1){
			if(in[i]>1){
				x=i;break;
			}
		}
		dfs(x,0);
		if(ans||up[x]) printf("NO");
		else puts("YES");
	}
	return 0;
} 

Measured memory_bytes: 11264
import bisect

N, K = map(int, input().split())
Xs = list(map(int, input().split()))

point0 = bisect.bisect(Xs, 0)
plusXs = Xs[point0:]
if point0 != 0:
    minusXs = Xs[point0-1::-1]
else:
    minusXs = []

# print(plusXs)
# print(minusXs)

min_plus = max(0, K-len(minusXs))
max_plus = min(K, len(plusXs))

ans = 10**10
for plus_index in range(min_plus, max_plus + 1):
    # print(plus_index)
    if plus_index == 0:
        temp = -minusXs[K - 1]
    elif K - plus_index == 0:
        temp = plusXs[plus_index-1]
    else:
        p = plusXs[plus_index - 1]
        m = -minusXs[K - plus_index - 1]
        temp = min(2*p+m, p+2*m)

    if temp < ans:
        ans = temp
    # print(temp)
print(ans)


Measured memory_bytes: 14484
#include<bits/stdc++.h>
using namespace std;
char a[100005];
int x=0,y=0,ans=0;
int main()
{
    cin>>a;
    for (int i=0;i<sizeof(a);i++)
     if (x==y){x++; if(a[i]=='p') ans--;}
     else{y++; if(a[i]=='g') ans++;}
    printf("%d\n",ans);
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    ll n,k;cin>>n>>k;
    map<ll,ll> mp;
    for(int i=1;i<=n;i++) mp[i%k]++;
    ll res=0;
    for(int i=0;i<=k-1;i++){
        ll anum=mp[i];
        ll bnum=mp[(k-i)%k];
        ll cnum=mp[(k-i)%k];
        if((2*i)%k!=0) continue;
        //cout<<i<<" "<<(k-i)%k<<" "<<anum<<" "<<bnum<<" "<<cnum<<endl;
        res += anum*bnum*cnum;
    }
    cout<<res<<endl;
}


Measured memory_bytes: 12800
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


X = I()

for i in range(X,1000000):
    for j in range(2,int(i**.5)+1):
        if i % j == 0:
            break
    else:
        print(i)
        break


Measured memory_bytes: 63128
import sys
from collections import deque
INF = float('inf')

input = sys.stdin.readline
n,m = map(int, input().split())
AB = [tuple(map(int,input().split())) for i in range(m)]
G = [[] for _ in range(n)]

for a, b in AB:
    a , b = a-1 , b-1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
dist = [INF]*n
dist[0] = 0
back = [-1] * n
while q:
    v = q.popleft()
    for to in G[v]:
        if dist[v] + 1 >=dist[to]:continue
        dist[to] = dist[v]
        back[to] = v+1
        q.append(to)
print('Yes')
print(*back[1:],sep='\n')

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

#define ll long long

template<typename T> void drop(const T &x){cout<<x<<'\n';exit(0);}

void solve() {
  string s; cin >> s;
  reverse(s.begin(), s.end());
  string ss = "";
  for(int i=0; i<s.size(); ++i) {
    ss += s.at(i);
    if(ss == "maerd" || ss == "remaerd" || ss == "esare" || ss == "resare") ss = "";
  }
  cout << (ss == "" ? "YES" : "NO") << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T=1;
  //cin >> T;
  while(T--) solve();

  return 0;
}


Measured memory_bytes: 3792
N = int(input())

comm_list = [input().split() for _ in  range(N)]

dictionary = set()

for comm, v in comm_list:
    if comm == 'insert':
        dictionary.add(v)
    elif comm == 'find':
        if v in dictionary:
            print('yes')
        else:
            print('no')
    else:
        raise


Measured memory_bytes: 300744
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,cnt = 0;
  
  cin >> n;
  
  vector<int> a(n);
  
  for(int i = 0;i < n;i++){
    cin >> a.at(i);
    if((i + 1) % 2)
      if(a.at(i) % 2)
        cnt++;
  }
  
  cout << cnt << endl;
}


Measured memory_bytes: 3596
import heapq
n, m = map(int, input().split())
aa = list(map(int, input().split()))
aa = [-b for b in aa]
heapq.heapify(aa)

for _ in range(m):
  ma = -1 * (heapq.heappop(aa))
  heapq.heappush(aa, (-1) * (ma // 2))

print((-1) * sum(aa))

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

#define fastIO ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define ld long double
#define ll long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vi vector<ll>
#define min3(a, b, c) min(a,min(b, c))
#define min4(a, b, c, d) min(a, min(b, min(c, d)))
#define max3(a, b, c) max(a,max(b, c))
#define max4(a, b, c, d) max(a, max(b, max(c, d)))
#define INF (int)1e9



int main()
{
    fastIO
    ll n;
    cin>>n;
    if(n%1000)
    {
        cout<<1000-(n%1000);
    }   
    else
    {
        cout<<n%1000;
    }
    return 0;
}


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

int main() {
    ll n,m;
    std::cin >> n>>m;
    
    if(n==m){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m, k = map(int, input().split())
fr = [0]*n
uf_fr = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf_fr.union(a-1, b-1)
    fr[a-1] += 1
    fr[b-1] += 1

for i in range(k):
    c, d = map(int, input().split())
    if uf_fr.find(c-1) == uf_fr.find(d-1):
        fr[c-1] += 1
        fr[d-1] += 1

ans_list = []
for i in range(n):
    ans_list.append(uf_fr.size(i) - fr[i] - 1)
print(*ans_list)

Measured memory_bytes: 18260
// Created by arvybhatt

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

#define ll long long int
using namespace std;


ll power(ll x, ll y) { ll temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } 

int main()
{
	fast;
	int n,m;cin>>n>>m;
	int a[m];
	rep(i,m)
	cin>>a[i];
	ll sum=0;
	rep(i,m)
	{
		sum+=a[i];
	}
	if(sum>n)
		cout<<"-1";
	else
		cout<<n-sum<<"\n";

}


Measured memory_bytes: 3652
#include<stdio.h>

int main(void){

  int N;
  int m;
  int Sum=0;

  scanf("%d", &N);
  scanf("%d", &m);
  int As[m];
  for (int i=0;i<m ;i++ ) {
  scanf("%d", &As[i]);
}
for (int i=0;i<m ;i++ ) {
  Sum+=As[i];
}
if(N-Sum>0|N-Sum==0){
     printf("%d",N-Sum);

   }else{
     printf("%d",-1);

   }

  return 0;
}

Measured memory_bytes: 1764
#include<bits/stdc++.h>
#define ll long long int
#define F first
#define S second
#define pb push_back
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y);
#define sdl(x) scanf("%lld",&x)
#define sd2l(x,y) scanf("%lld%lld",&x,&y);
#define sz(x) (int)(x.size())
#define nax 201010
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define mp make_pair
#define pi pair<int ,int>
#define pii pair <int,pi>
using namespace std;
int arr[nax];
ll sum[nax];
int BIT[nax];
map<ll ,int> mapp;
vector< ll > sor;
void update(int idx,int val)
{
    while(idx < nax)
    {
        BIT[idx]+=val;
        idx+=idx & -idx;
    }
}
int query(int idx)
{
    int ret = 0;
    while(idx > 0)
    {
        ret+=BIT[idx];
        idx-=idx & -idx;
    }
    return ret;
}
int main(int argc, char const *argv[])
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  int n,k;
  sd2(n,k);
  for (int i = 1; i <= n; ++i)
  {
      sd(arr[i]);
  }
  ll fans  = 0;
  for(int i = 1;i<= n;)
  {
      int start = i;
      int prev= arr[start];
      while(start<=n && arr[start]-prev <= k)
        prev = arr[start],start++;
      fans+=arr[start-1]+k-arr[i];
      i = start;
  }
  printf("%lld\n",fans);
  return 0;
}
 

Measured memory_bytes: 1024
#include <stdio.h>
  
int main() {
int a,b,c,i,n;
n=0;
scanf("%d%d%d",&a,&b,&c);
for(i=a ; i<=b ; i ++){
if( c%i == 0 ) n=n+1;
}
printf("%d\n",n);
return 0;
}

Measured memory_bytes: 596