akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 5010;

int n, m, dp[maxn][maxn];

int main() {
    cin >> n;
    string tmp;
    cin >> tmp;
    m = tmp.size();

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        for (int j = 1; j <= i; j++) {
          dp[i][j] = (2LL * dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
        }
    }

    int res = dp[n][m];
    for (int i = 0; i < m; i++) {
        res = 1LL * res * ((mod + 1) / 2) % mod;
    }

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


Measured memory_bytes: 67072
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db long double

using namespace std;
const int N=1e5+10;
int rd()
{
	int x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
};
int to[N<<1],nt[N<<1],w[N<<1],hd[N],tot=1;
void add(int x,int y,int z)
{
	++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
	++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;
}
int n,sz[N],mx[N],mm,r1,r2;
LL de[N],ans;
void dfs(int x,int ffa)
{
	sz[x]=1;
	for(int i=hd[x];i;i=nt[i])
	{
		int y=to[i];
		if(y==ffa) continue;
		dfs(y,x);
		sz[x]+=sz[y],mx[x]=max(mx[x],sz[y]);
	}
	mx[x]=max(mx[x],n-sz[x]);
	if(mm>mx[x]) mm=mx[x],r1=x;
}
void dfs2(int x,int ffa)
{
	ans+=2*de[x];
	for(int i=hd[x];i;i=nt[i])
	{
		int y=to[i];
		if(y==ffa) continue;
		de[y]=de[x]+w[i];
		dfs2(y,x);
	}
}

int main()
{
	n=rd();
	for(int i=1;i<n;++i)
	{
		int x=rd(),y=rd(),z=rd();
		add(x,y,z);
	}
	mm=n;
	dfs(1,0);
	for(int i=1;i<=n;++i)
		if(mx[i]==mm&&i!=r1) r2=i;
	dfs2(r1,0);
	LL ee;
	if(!r2)
	{
		ee=1<<30;
		for(int i=hd[r1];i;i=nt[i])
			ee=min(ee,1ll*w[i]);
	}
	else
	{
		for(int i=hd[r1];i;i=nt[i])
			if(to[i]==r2) {ee=w[i];break;}
	}
	printf("%lld\n",ans-ee);
	return 0; 
}


Measured memory_bytes: 8576
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  
  int n; rd(n);
  auto a=readln.split.to!(int[]);

  int cnt=0;
  void f(int i=0, int pro=1){
    if(i==n){if(pro%2==0) cnt++; return;}
    for(int d=-1; d<=1; d++) f(i+1, pro*(a[i]+d));
  }

  f();
  writeln(cnt);
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

Measured memory_bytes: 256
s = gets.chomp.split(" ").map(&:to_i)

paths = [[]]
count = 0
while(s[1] > count)
    a = ""
    a = gets.chomp.split(" ").map(&:to_i)
    paths[count] = a
    count = count + 1
end

h = Hash.new(0)
initArray = [*1..s[0]]
initArray.each{|e| h[e] = 0}

for i in 0..s[1]-1
    paths[i].each{ |e| h[e] += 1 }
end
h = h.sort {|(k1, v1), (k2, v2)| k2 <=> k1 }.reverse
h.each do |key, value|
    print(value)
    print("\n")
end


Measured memory_bytes: 1788
n=gets.to_i-1
a=gets.chomp.split(" ").map(&:to_i)
re=a[0]+a[n-1]
n.times do |i|
  break if i==n-1
    if a[i] > a[i+1]
      re+=a[i+1]
    else
      re+=a[i]
  end
end
puts re

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define l S.size()

int main(){
	string S;
	cin >> S;
	const int m = 1000000007;
	long long dp[100010][4] = {};
	for (int i = l; i >= 0; i--){
		for (int j = 3; j >= 0; j--){
			if (i == l)
				dp[i][j] = (j == 3 ? 1 : 0);
			else{
				dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3 : 1);
				if (j < 3 && (S[i] == '?' || S[i] == "ABC"[j]))
					dp[i][j] += dp[i+1][j+1];
				dp[i][j] %= m;
			}
		}
	}
	cout << dp[0][0] << endl;
	return 0;
} 

Measured memory_bytes: 3584
#include <bits/stdc++.h>
			using namespace std;
			#define ll long long
			#define INF 100000000LL
			#define mod 1000000007
			#define pll pair<long,long>
			#define se second
			#define fi first
			#define pb push_back
			#include <ext/pb_ds/assoc_container.hpp>
			#include <ext/pb_ds/tree_policy.hpp>
			using namespace __gnu_pbds;

			typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
			typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update>pllordered_set;
			
			
			int main()
			{
				ll n;
				cin>>n;
				vector<ll> v(n);
				map<ll,ll> m;
				for(ll i=0;i<n;i++)
					{cin>>v[i];m[v[i]]++;}
				
				sort(v.begin(),v.end());
				if(v[n-1]-v[0]>1)
				{
					cout<<"No";
					exit(0);
				}
				ll c1=0,c2=0;
				if(v[n-1]==v[0])
				{
					if(v[0]+1==n)
						cout<<"Yes";
					else if(n>=(2*v[0]))
						cout<<"Yes";
					else
						cout<<"No";
						
				}
				else
				{
					c1=m[v[0]];
					c2=m[v[n-1]];
					if(c2>=2*(v[n-1]-c1) &&v[n-1]>c1)
						cout<<"Yes";
					else
					{
						cout<<"No";
					}
				}
			}
						
			


Measured memory_bytes: 7296
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#define INF (1e9 + 7)
#define dist(x1, y1, x2, y2) sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
typedef long long int ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

ll N = 20;

/*  PrimeFact
    init(N): 初期化。O(N log log N)
    get(n): クエリ。素因数分解を求める。O(log n)
 */
struct PrimeFact {
    vl spf;
    PrimeFact(ll N) { init(N); }
    void init(ll N) { // 前処理。spf を求める
        spf.assign(N + 1, 0);
        for (ll i = 0; i <= N; i++) spf[i] = i;
        for (ll i = 2; i * i <= N; i++) {
            if (spf[i] == i) {
                for (ll j = i * i; j <= N; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }
    map<ll, ll> get(ll n) { // nの素因数分解を求める
        map<ll, ll> m;
        while (n != 1) {
            m[spf[n]]++;
            n /= spf[n];
        }
        return m;
    }
};

int main(){
    
    ll N, temp;
    ll ans = 0;
    cin >> N;
    struct PrimeFact s(N);
    map<ll, ll> p;
    rep2(i, 1, N + 1){
        p = s.get(i);
        temp = i;
        for (const auto& [key, value] : p){
            temp *= (value + 1);
        }
        ans += temp;
    }
	cout << ans << endl;
	return 0;
	
}



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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
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;}
const int MOD = 1000000007;

long long gcd(long long m, long long n) {
    return n != 0 ? gcd(n, m % n) : m;
}

long long lcm(long long m, long long n) {
    // If both m and n are large numbers, the result is overflow without parentheses.
    return m * (n / gcd(m, n));
}

int main() {
    int n, k;
    cin >> n >> k;
    if (n * (n - 1) / 2 - (n - 1) < k) {
        cout << -1 << endl;
        return 0;
    }

    cout << n * (n - 1) / 2 - k << endl;

    FOR(i, 1, n) {
        FOR(j, i + 1, n + 1) {
            if (i == 1) {
                cout << i << " " << j << endl;
            } else {
                if (k > 0) {
                    k--;
                } else {
                    cout << i << " " << j << endl;
                }
            }
        }
    }
}


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

int main(){
    int N;
    string S;
    cin >> N >> S;
    // 許されるのは,1. ....... 2. ######### 3. ......######
    // 黒始まりだったら黒
    std::vector<int> stonenum(N);
    int blacknum = 0;
    for(int i=0; i < N; i++){
        if(S.at(i)=='#'){
            blacknum ++;
        }
        stonenum.at(i) = blacknum;
    }

    int change;
    int totblack = stonenum.at(N - 1);
    int min_c = N - totblack;
    for(int i=0; i < N; i++){

        change = stonenum.at(i) + (N - i - 1 - totblack + stonenum.at(i));//左の黒をひっくり返す + 右の白(=右側の石-(左の黒))をひっくり返す
        min_c = min(min_c, change);
    }
    cout << min_c << endl;
    return 0;
}


Measured memory_bytes: 1412
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> x, y;
        x.push_back(0);
        y.push_back(0);
        
        for (int i = 1; i < N; i++) {
            int n, d;
            cin >> n >> d;

            x.push_back(x[n] + dx[d]);
            y.push_back(y[n] + dy[d]);
        }

        const int inf = 1 << 30;
        int xmin = inf, ymin = inf;
        int xmax = -inf, ymax = -inf;

        for (int i = 0; i < N; i++) {
            xmin = min(x[i], xmin);
            ymin = min(y[i], ymin);
            xmax = max(x[i], xmax);
            ymax = max(y[i], ymax);
        }

        cout << xmax - xmin + 1 << " " << ymax - ymin + 1 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#define MAXV 10005
#define MAXE 100005
using namespace std;

int N,E;
bool V[MAXV];
vector<int> G[MAXV],out;
int indeg[MAXV];

void bfs(int u){
    queue<int> q;
    q.push(u);
    V[u]=true;
    int i;
    while(!q.empty()){
        int a=q.front();q.pop();
        out.push_back(a);
        for(i=0;i<G[a].size();i++){
            int v=G[a][i];
            indeg[v]--;
            if(indeg[v]==0&&!V[v]){
                V[v]=true;
                q.push(v);
            }
        }
    }
}

void tsort(){
     int i;
     for(i=0;i<N;i++){
        if(!V[i]&&indeg[i]==0){
            bfs(i);
        }
     }
     for(i=0;i<out.size();i++)cout<<out[i]<<endl;
}

int main(){
    cin>>N>>E;
    int i,j;
    for(i=0;i<E;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
    }

    memset(indeg,0,sizeof(indeg));
    for(i=0;i<N;i++)V[i]=false;
    for(i=0;i<N;i++){
        for(j=0;j<G[i].size();j++){
            indeg[G[i][j]]++;
        }
    }
    tsort();
    return 0;
}

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

int main ()
{
    int h, w;
    do
    {
        cin >> h >> w;
        for (int i = 0;i < h;i++)
        {
            for (int j = 0;j < w;j++)
            {
                cout << "#";
            }
            cout << endl;
        }
        if (!(h == 0 && w == 0))cout << endl;
    }while(!(h == 0 && w == 0));
    
    return 0;
}


Measured memory_bytes: 3100
N = gets.to_i
a_list = gets.split.map(&:to_i)
table = a_list.group_by { |a| a }.map { |k, v| [k, v.size] }.to_h
ans = table.map do |k, v|
  if k > v
    v
  else
    v - k
  end
end.reduce(0, :+)
puts ans


Measured memory_bytes: 30340
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,nn;
  cin>>n;
  deque<char> s;
  while(n!=0){
    nn=n%26;
    if(nn==0){
      nn+=26;
      n-=1;
    }
    n/=26;
    s.push_front(nn+96);
  }
  for(int i=0;i<s.size();i++){
    cout<<s[i];
  }
  cout<<endl;
}

Measured memory_bytes: 3636
n, k = map(int, input().split())
A = list(map(int, input().split()))

output = []
count = 0
for i in range(k, n):
    if A[i] > A[count]:
        output.append("Yes")
    else:
        output.append("No")
    count += 1
    
print(*output, sep="\n")


Measured memory_bytes: 111368
n,m=map(int,input().split())
l1=list(map(int,input().split()))
l2=list(map(int,input().split()))
INF=10**9+7
ls1,ls2=[],[]
tmp1,tmp2=0,0
for i in l1:
    tmp1+=i
    ls1.append(tmp1)
for i in l2:
    tmp2+=i
    ls2.append(tmp2)
w=0
for i,j in enumerate(l1):
    w+=ls1[-1]-ls1[i]-j*(n-i-1)
h=0
for i,j in enumerate(l2):
    h+=ls2[-1]-ls2[i]-j*(m-i-1)
print((w*h)%INF)

Measured memory_bytes: 22416
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int a[200001];
int b[200001]={};

int main() {
	int n;
	cin>>n;
	rep(i,n)cin>>a[i+1];
	for(int i=n;i>0;--i){
		int total=0;
		for(int j=2;j<n/i+1;++j){
			total+=b[i*j];
		}
		total%=2;
		if(total!=a[i])b[i]=1;
	}
	int m=0;
	rep(i,n)m+=b[i+1];
	cout<<m<<endl;
	vi v;
	if(m>0){
		rep(i,n){
			if(b[i+1]>0)v.push_back(i+1);
		}
		cout<<v[0];
		for(int i=1;i<v.size();++i)cout<<" "<<v[i];
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 2936
#include <iostream>
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
int a[100001],b[100001],c[100001];
//0->swim
//1->catch bugs
//2->homework

ll dp[100001][3][3];


ll solve(int day,int activity,int no_of_day){
    
    if(day==n) return 0;
    ll ans = 0;
    
    if(dp[day][activity][no_of_day]!=-1) return dp[day][activity][no_of_day];
    
    if(activity!=0 and no_of_day!=2){
        if(activity==0) 
        ans = max(ans,a[day]+solve(day+1,0,2));
        else
        ans = max(ans,a[day]+solve(day+1,0,1));
    }
    
    if(activity!=1 and no_of_day!=2){
        if(activity==1) 
        ans = max(ans,b[day]+solve(day+1,1,2));
        else
        ans = max(ans,b[day]+solve(day+1,1,1));
    }
    
    if(activity!=2 and no_of_day!=2){
        if(activity==2) 
        ans = max(ans,c[day]+solve(day+1,2,2));
        else
        ans = max(ans,c[day]+solve(day+1,2,1));
    }
    
    return dp[day][activity][no_of_day] = ans;
    
    
}
int main() {
    
    cin>>n;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    
    ll ans = solve(0,0,1);
    
    ans = max(solve(0,1,1),ans);
    ans = max(ans,solve(0,2,1));

	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 16256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int main() {
    
    int i;
    cin >> i;
    cout << (i == 7 ||i == 5 ||i == 3 ? "YES" : "NO") << endl;
    
}

Measured memory_bytes: 764
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Main{

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	public static void main(String[] args) {
		FastReader sc = new FastReader();
		String s=sc.nextLine();
		String t=sc.nextLine();
		System.out.println(areRotations(s, t)|| areRotations(t, s)==true?"Yes":"No");
	}
	
	static boolean areRotations(String str1, String str2)
    {
        // There lengths must be same and str2 must be 
        // a substring of str1 concatenated with str1.  
        return (str1.length() == str2.length()) &&
               ((str1 + str1).indexOf(str2) != -1);
    }

}

Measured memory_bytes: 22612
import java.util.Scanner;
public class Main {
	private static Scanner sc;
	public static void main(String[] args){
		sc = new Scanner(System.in);
		int a = sc.nextInt();
		int countOdd =0;
		for (int i=0; i<a; i++){
			int b = sc.nextInt();
			if (b%2!=0){
				countOdd++;
			}else {
				countOdd+=0;
			}
		}
		if (countOdd%2!=0)
			System.out.println("NO");
		else
			System.out.println("YES");
	}
}

Measured memory_bytes: 32960
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
l=a[0]
for i in range(1,n):l=lcm(l,a[i])
for i in a:
  ans+=l*pow(i,mod-2,mod)%mod
  ans%=mod
print(ans)

Measured memory_bytes: 4084
d = [0]
ans = 0

def prime(n):
    if n == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        else:
            i += 1
    return True
    
for i in range(10 ** 5 // 2):
    if prime(2 * i + 1) and prime(i + 1):
        ans += 1
    d.append(ans)

Q = int(input())

for _ in range(Q):
    l, r = map(int, input().split())
    print(d[r // 2 + 1] - d[l // 2 + 1 - 1])

Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using P = pair<int,int>;
using ll = long long;
static const int INF = 1000000000;
static const ll MOD = 1000000007;

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}



int main(){
	int n;
	cin >> n;
	
	ll ans = 1;
	for(ll i = 0; i < n; ++i){
		ans = ans * (i + 1) % MOD;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
using namespace std;
static char gc(){
	static char buf[1<<6],*p1=buf,*p2=buf;
	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<5,stdin),p1==p2)?EOF:*p1++;
}
template <class T>
inline void read(T&data){
	data=0;
	register char ch=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0'){
		data=(data<<3)+(data<<1)+(ch&15);
		ch=getchar();
	}
	return;
}
const int _ = 200101,mod = 1e9+ 7;
int  aa[_],n,Data[_],sum1[_],sum2[_],loc[_],LOC[_],qz[_],hz[_],sum[_];
inline int poww(register int ax,register int cc){
	register int ret=1,Base=ax;
	for(;cc;cc>>=1,Base=1LL*Base*Base%mod)if(cc&1)ret=1LL*ret*Base%mod;
	return ret;
}
inline int Que1(register int l,register int r){	return 1LL*sum1[r]*poww(sum1[l-1],mod-2)%mod;}
inline int Que2(register int l,register int r){	return 1LL*sum2[r]*poww(sum2[l-1],mod-2)%mod;}
inline int lowbit(register int k){return k&(-k);}
inline int query1(register int l,register int r){
	if(r<l)return 0;
	register int ret1=0,ret2=0;
	for(register int i=l-1;i;i-=lowbit(i))ret1=(ret1+qz[i])%mod;
	for(register int i=r;i;i-=lowbit(i))ret2=(ret2+qz[i])%mod;
	return (ret2-ret1+mod)%mod;
}
inline int query2(register int l,register int r){
	if(r<l)return 0;
	register int ret1=0,ret2=0;
	for(register int i=l-1;i;i-=lowbit(i))ret1=(ret1+hz[i])%mod;
	for(register int i=r;i;i-=lowbit(i))ret2=(ret2+hz[i])%mod;
	return (ret2-ret1+mod)%mod;
}
inline int query3(register int l,register int r){
	if(r<l)return 0;
	register int ret1=0,ret2=0;
	for(register int i=l-1;i;i-=lowbit(i))ret1=(ret1+sum[i])%mod;
	for(register int i=r;i;i-=lowbit(i))ret2=(ret2+sum[i])%mod;
	return (ret2-ret1+mod)%mod;
}
inline void fix(register int loc,register int zh1,register int zh2){
	for(register int i=loc;i<=n;i+=lowbit(i))qz[i]=(qz[i]+zh1)%mod,hz[i]=(hz[i]+zh2)%mod,sum[i]++;
	return;
}
int main(){
	//freopen("belief.in","r",stdin);
	//freopen("belief.out","w",stdout);
	read(n);
	for(register int i=1;i<=n;++i)read(aa[i]),aa[i]=aa[i]>n?n:aa[i],++Data[aa[i]];
	for(register int i=n-1;i>=1;--i)Data[i]=Data[i]+Data[i+1];
	for(register int i=1;i<=n;++i)Data[i]=Data[i]-n+i;
	for(register int i=1;i<=n;++i)if(Data[i]<0){cout<<0<<endl;return 0;}
	sum1[0]=sum2[0]=1;
	for(register int i=1;i<=n;++i)sum1[i]=1LL*sum1[i-1]*Data[i] %mod;
	if(!sum1[n]){puts("0");return 0;}
	for(register int i=1;i<=n;++i){
		--Data[i];
		if(Data[i]==0)loc[i]=i,sum2[i]=sum2[i-1];
		else loc[i]=loc[i-1],sum2[i]=1LL*sum2[i-1]*Data[i]%mod;
	}
	LOC[n+1]=n+1;
	for(register int i=n;i>=1;--i)
		if(!Data[i]) LOC[i]=i;
		else LOC[i]=LOC[i+1];
	register int ans=0,ni2=poww(2,mod-2);
	for(register int i=1;i<=n;++i){
		register int f=1LL*query1(loc[aa[i]]+1,aa[i])*poww(Que2(aa[i]+1,n),mod-2)%mod*Que1(aa[i]+1,n)%mod;
		ans=(ans+1LL*f*ni2%mod)%mod;
		f=1LL*query2(aa[i]+1,LOC[aa[i]+1]-1)*poww(Que2(1,aa[i]),mod-2)%mod*Que1(1,aa[i])%mod;
		f=1LL*f*ni2%mod;
		ans=(ans-f+mod)%mod;
		f=query3(aa[i]+1,n);
		ans=(ans+1LL*f*sum1[n]%mod)%mod;
		fix(aa[i],1LL*Que1(1,aa[i])*Que2(aa[i]+1,n)%mod,1LL*Que2(1,aa[i])*Que1(aa[i]+1,n)%mod);
	}
	cout<<ans;
}


Measured memory_bytes: 7296
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
#include <utility>
#include <map>
#include <queue>
#include <stack>

using namespace std;

#define INF 210000000
#define int long long

int gcd(int a, int b) {
  int amari = a % b;
  int c = b;
  if (amari == 0) {
    return b;
  } else {
    return gcd(b, amari);
  }
}

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

signed main() {
    int x,y;
    cin >> x >> y;
    map<int,int> cnt;
    if(x == 4 || x == 6 || x == 9 || x == 11){
        cnt[2]++;
    }else if(x == 2){
        cnt[3]++;
    }else{
        cnt[1]++;
    }
    if(y == 4 || y == 6 || y == 9 || y == 11){
        cnt[2]++;
    }else if(y == 2){
        cnt[3]++;
    }else{
        cnt[1]++;
    }
    string ans = "No";
    for(auto& a : cnt){
        if(a.second == 2){
            ans = "Yes";
            break;
        }
    }
    cout << ans;
}



Measured memory_bytes: 256
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    x = [i - j for i,j in zip(a,b)]
    
    p = 0
    m = 0
    for num in x:
        if num < 0:
            m += (-num//2) * 2
        else:
            p += num
    
    if 2 * p <= m:
        print('Yes')
    else:
        print('No')

if __name__ =='__main__':
    main() 

Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	long long times;
	cin>>times;
	long long cnt=1,dif=1;
	long long sum=0;
		if(s.size()==1){
		printf("%lld\n",times/2);
		return 0;
	}
	for(int i=1;i<s.size();i++){
		while(s[i]==s[i-1]){
			if(i>=s.size())
				break;
			i++;
			cnt++;	
		}
		sum+=cnt/2;
		cnt=1;
		if(i<s.size()) dif++;
	}
	//cout<<dif<<endl;
	if(dif==1){
		printf("%lld\n",(s.size()*times)/2);
	}
	else if(s[0]==s[s.size()-1]){
		int cnt1=1,cnt2=1;
		int i=1;
		while(s[i]==s[i-1]){
			i++;
			cnt1++;
		}
		i=s.size()-1;
		while(s[i]==s[i-1]){
			i--;
			cnt2++;
		}
		//cout<<cnt1<<" "<<cnt2<<" ";
		sum=(sum-cnt1/2-cnt2/2)*times+cnt1/2+cnt2/2+(cnt1+cnt2)/2*(times-1);
		printf("%lld\n",sum);	
	}
	else printf("%lld\n",sum*times);
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
std::map<T, int> prime_factorize(T x) {
  std::map<T, int> primes;
  for (T factor = 2; factor * factor <= x; factor++) {
    if (x % factor == 0) {
      T count = 0;
      while (x % factor == 0) {
          count++;
          x /= factor;
      }
      primes[factor] = count;
    }
  }
  if (x != 1) primes[x] = 1;
  return primes;
}

int N, M;
int main() {
  cin >> N >> M;
  int i = 1, vmax = 1;
  for (; i * i <= M; ++i) {
    if (M % i != 0) continue;
    int x = M / i;
    if (i >= N) {
      vmax = x;
      break;
    }
    if (x >= N) vmax = i;
  }
  cout << vmax << endl;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if (n > 1) {
        ans += n * (n-1) / 2;
    }
    if (m > 1) {
        ans += m * (m-1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
ans = 0
if k%2 == 0:
    #k mod halfの個数は
    mod1 = (n+(k//2))//k
    #k mod0の個数は
    mod2 = n//k
    
    ans += mod1**3 + mod2**3
    
else:
    #kmod0の個数は
    modk = n//k
    
    ans += modk**3
print(ans)

Measured memory_bytes: 38384
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define INF 1987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset(a,0,sizeof(a));
#define MEM_1(a) memset(a,-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 123456789;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int ddx[] = { 0,0,1,1,1,-1,-1,-1 }, ddy[] = { 1,-1,1,0,-1,1,0,-1 };

int a[100001];
int main() {
	int n;
	scanf("%d%d",&n,a);
	fup(i,1,n,1)scanf("%d",a+i);
	sort(a,a+n+1);
	int ans=0;
	fup(i,1,n,1)ans=gcd(ans,a[i]-a[i-1]);
	printf("%d",ans);
}

Measured memory_bytes: 640
def main():
  N = int(input())
  X = list(map(int, input().split()))

  ANS = 1000000000000000000000000000000000

  for i in range(1,101):
    C_ANS = 0
    for j in X:
      C_ANS += (i-j)**2
    if C_ANS < ANS:
      ANS = C_ANS
  
  print(ANS)

if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
N, M = map(int, input().split())
AB = [ list(map(int, input().split())) for _ in range(N)]

new_AB = sorted(AB, key=lambda x: x[0])
m = M
i = 0
cost = 0
while m > 0:
    item = new_AB[i][1]
    if item >= m:
        buy_count = m
    else:
        buy_count = item
    m -= buy_count
    cost += buy_count * new_AB[i][0]
    #print("cost ",cost)
    i += 1

print(cost)

Measured memory_bytes: 29796
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] h = new int[N];
    for (int i = 0; i < N; i++) {
      h[i] = sc.nextInt();
    }
    int[] dp = new int[N];
    for (int i = 0; i < N; i++) {
      dp[i] = Integer.MAX_VALUE;
    }
    dp[0] = 0;
    for (int i = 0; i < N-1; i++) {
      for (int k=1; i+k < N && k <=K; k++) {
        dp[i+k] = Math.min(dp[i+k], dp[i] + Math.abs(h[i+k]-h[i]));
      }
    }
    System.out.println(dp[N-1]);
  }
}

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

int main() {

  int a[4];
  int b[4];

  int n;
  while(1) {
    cin >> n;
    if(n == 0) break;

    for(int k=0;k<n;k++){

    for(int j=0;j<4;j++)cin >> a[j];
    for(int j=0;j<4;j++)cin >> b[j];


    int ans[4] ={};    

    ans[0] = a[0]*b[0] - a[1]*b[1] - a[2]*b[2] - a[3]*b[3];
    ans[1] = a[0]*b[1] + a[1]*b[0] + a[2]*b[3] - a[3]*b[2];
    ans[2] = a[0]*b[2] - a[1]*b[3] + a[2]*b[0] + a[3]*b[1];
    ans[3] = a[0]*b[3] + a[1]*b[2] - a[2]*b[1] + a[3]*b[0];

    cout<<ans[0] <<" "<<ans[1]<<" "<<ans[2] <<" "<<ans[3]<<endl;

    }
  }

  return 0;
}

Measured memory_bytes: 1160
# C - Attack Survival
N, K, Q = map(int, input().split())
A = [0]*Q
for i in range(Q):
    A[i] = int(input())
####
score = [0]*N
for a in A:
    score[a-1] += 1

for sc in score:
    pt = K -Q + sc
    if pt > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 8636
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
n = len(s)
cnt = 0
g_cnt = 0
p_cnt = 0
for i in range(n):
    if g_cnt > p_cnt:
        if s[i] == 'g':
            cnt += 1
            p_cnt += 1
        else:
            p_cnt += 1
    else:
        if s[i] == 'g':
            g_cnt += 1
        else:
            cnt -= 1
            g_cnt += 1
print(cnt)

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

int main(){
  int N;
  cin >> N;
  long int sum=0;
  vector<long int> A(N+1),B(N);
  for(int i=0;i<N+1;i++){
    cin >> A.at(i);
  }
  for(int i=0;i<N;i++){
    cin >> B.at(i);
  }
  for(int i=0;i<N;i++){
    if(B.at(i)<A.at(i)){
      sum+=B.at(i);
      continue;
    }else if(B.at(i)>=A.at(i)){
      sum+=A.at(i);
      B.at(i)=B.at(i)-A.at(i);
    }
    if(B.at(i)<A.at(i+1)){
      sum+=B.at(i);
      A.at(i+1)-=B.at(i);
    }else if(B.at(i)>=A.at(i+1)){
      sum+=A.at(i+1);
      A.at(i+1)=0;
    }
  }
  cout << sum << endl;
    
}

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

using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999
int ans[11][11]={};

vector<vector<int> > d(int y,int x,vector<vector<int> > t){
    int dx[]={0,0,0,-1,1};
    int dy[]={-1,0,1,0,0};
    rep(k,5){
        int ddy=y+dy[k],ddx=x+dx[k];
        if(ddx>=0&&ddy>=0&&ddx<10&&ddy<10){
            t[ddy][ddx]=!t[ddy][ddx];
        }
    }
    return t;
}

int main(){
    int n;
    cin>>n;
    rep(loop,n){
        vector<vector<int> > data;
        rep(i,10){
            vector<int> a(10);
            rep(j,10)cin>>a[j];
            data.pb(a);
        }
//        rep(i,10){rep(j,10)cout<<data[i][j]<<" ";cout<<endl;}
        rep(i,1<<10){
            vector<vector<int> > t=data;
            rep(j,11)rep(k,11)ans[j][k]=0;
            rep(j,10){
                ans[0][j]=((i&(1<<j))!=0);
                if(ans[0][j])t=d(0,j,t);
            }
            for(int j=1;j<10;j++){
                for(int k=0;k<10;k++){
                    if(t[j-1][k]==1){
                        ans[j][k]=1;
                        t=d(j,k,t);
                    }
                }
            }
            bool f=true;
            rep(j,10){
                if(t[9][j]==1)f=false;
            }
            if(f){
                rep(j,10){
                    rep(k,10){
                        if(k)cout<<" ";
                        cout<<ans[j][k];
                    }
                    cout<<endl;
                }
                break;
            }
        }
    }
}

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

#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define eb emplace_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector< pair<int,int> > vii;
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    cout << max({a+b,a-b,a*b}) << endl;
    return 0;
}



Measured memory_bytes: 384
import java.util.*;

class Main {

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

		int a = answer.nextInt();
		int b = answer.nextInt();
		int area = a*b;
		int periphery =(a+b)*2;

		System.out.println(area + " " + periphery);

	}
 }

Measured memory_bytes: 17156
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: usize = iterator.next().unwrap().parse().unwrap();
    let b: usize = iterator.next().unwrap().replace(".", "").parse().unwrap();

    let ans = a * b / 100;

    return ans.to_string();
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
    IOS;
    long long a,b;
    cin >> a >> b;
    long double ans = a*b;
    if(a==1 || b==1){
        cout << 1 <<endl;
    }else{
        cout << setprecision(100)<<ceil(ans/2) <<endl;
    }
}

Measured memory_bytes: 3712
m[101][101];main(i,j,x,y){for(;scanf("%d%d",&y,&x),x;){
	for(getchar(),j=0;j<y;getchar(),j++)for(i=0;i<x;i++)m[i][j]=getchar();
	for(x=y=i=0;i<999;i++)if(m[x][y]=='>')x++;else if(m[x][y]=='<')x--;else if(m[x][y]=='v')y++;else if(m[x][y]=='^')y--;else break;
	if(i==999)puts("LOOP");else printf("%d %d\n",x,y);
}exit(0);}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int a = Integer.parseInt(str[0]);
		int b = Integer.parseInt(str[1]);

		if (a >= 13) {
			System.out.println(b);
		} else if (a >= 6) {
			System.out.println(b / 2);
		} else {
			System.out.println("0");
		}
	}
}


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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long ll;


#define SZ(x) ((int)(x).size())
#define BIT(n) (1ll<<(n))
#define SORT(c) sort((c).begin(),(c).end())
#define RALL(a) (a).rbegin(), (a).rend()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define CLR(a) memset((a), 0 ,sizeof(a))
#define retrun return
//#define INF 1000000010ll
#define MOD 1000000007ll
//#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define RREP(i,n)  
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define COUT(str) cout << str << endl


template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
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> inline T sqr(T x) { return x*x; }


//------------------------------------------------------------------------------------------------------
int N, A[2][101], dp[2][101];
//---------------------------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(y, 0, 2) rep(x, 0, N) cin >> A[y][x];

	dp[0][0] = A[0][0];
	rep(y, 0, 2) rep(x, 0, N) {
		if (x) chmax(dp[y][x], dp[y][x - 1] + A[y][x]);
		if (y) chmax(dp[y][x], dp[y - 1][x] + A[y][x]);
	}

	cout << dp[1][N - 1] << endl;

	return 0;
}

Measured memory_bytes: 256
def resolve():
	s = input()
	a = len(s) - 1
	z = 0
	for i in range(len(s)):
		if s[i] == 'A':
			a = min(a, i)
		if s[i] == 'Z':
			z = max(z, i)
	print(z - a + 1)
resolve()

Measured memory_bytes: 40352
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
  int p, cs, W, H;
  int sx, sy, gx, gy;
  
  cin >> cs;
  while(cs--){
    cin >> W >> H;
    
    int field[20][20];
    memset(field, 0, sizeof(field));
    field[0][0] = 1;
    
    bool flag1[20][20], flag2[20][20];
    memset(flag1, true, sizeof(flag1));
    memset(flag2, true, sizeof(flag2));
    
    cin >> p;
    
    for(int i = 0 ; i < p ; i++){
      cin >> sx >> sy >> gx >> gy;
      if(sx == gx) flag1[min(sy, gy)][sx] = false;
      if(sy == gy) flag2[sy][min(sx, gx)] = false;
    }

    for(int i = 0 ; i <= H ; i++){
      for(int j = 0 ; j <= W ; j++){
	if(i > 0 && flag1[i-1][j]) field[i][j] += field[i-1][j];
	if(j > 0 && flag2[i][j-1]) field[i][j] += field[i][j-1];
      }
    }

    if(field[H][W] == 0) cout << "Miserable Hokusai!" << endl;
    else cout << field[H][W] << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, a = LI()
x = LI()

dp = [[[0] * (2500+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
    xi = x[i-1]
    for j in range(2500+1):
        for k in range(i):
            dp[i][k][j] = dp[i-1][k][j]
    for j in range(xi, 2500+1):
        for k in range(1, i+1):
            dp[i][k][j] += dp[i-1][k-1][j-xi]
ans = 0
for i in range(1, n+1):
    ans += dp[-1][i][i*a]
print(ans)

Measured memory_bytes: 125284
#include<iostream>
using namespace std;
#define df 0
#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
typedef long int li;

int isprime(li a){
  if(a==1)return 0;
  for(int i=2,sq=3;sq<a;i++){
    sq=i*i;
    if(a%i==0)return 0;
  }
  return 1;
}

int main(){
  if(df) printf("*debug mode*\n");
  li a; cin >>a;
  while(not isprime(a)) a++;
  cout << a;
}

/// confirm df==0 ///


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N,K,res=1;
	scanf("%d%d",&N,&K);
	for(int i=0;i<N-1;i++)res*=(K-1);
	printf("%d\n",res*K);
	return 0;
}




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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    Int(n);
    int t = 0, x = 0, y = 0;
    rep(i, n) {
        int3(a, b, c);
        int diff = abs(x-b) + abs(y-c);
        if (a-t < diff) {
            cout << "No" << endl;
            return 0;
        } else if ( ((a-t)-diff) % 2) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;


    return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    if(a + b <= 16 && a <= 8 && b <= 8) cout << "Yay!" << endl;
    else cout << ":(" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

void solve() {
    string s;
    cin >> s;
    if (s.back() == 's') cout << (s + "es") << '\n';
    else cout << (s + "s") << '\n';
}

int main() {
    FASTIO;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
} 

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

long long INF=LLONG_MAX;

int p[10],q[10];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	int a[n];
	for(int i = 0; i < n; i++)cin >> p[i];
	for(int i = 0; i < n; i++)cin >> q[i];
	for(int i = 0; i < n; i++)a[i] = i+1;
	ll cur = 1, pp = 0, qq = 0;
	do{
		//for(int i = 0 ; i <n; i++)cout << a[i] << ' ';
		//cout << endl;
		//cout << cur << endl;
		bool ok = 1;
		for(int i = 0; i < n && ok && !pp; i++){
			if(p[i]!=a[i])ok=0;
		}
		if(ok&&!pp)pp=cur;
		ok = 1;
		for(int i = 0; i < n && ok && !qq; i++){
			if(q[i]!=a[i])ok=0;
		}
		if(ok&&!qq)qq=cur;
		cur++;
		if(pp&&qq)break;
	}while(next_permutation(a,a+n));
	//cout << pp << ' ' << qq << endl;
	cout << abs(pp-qq) << endl;
}	


Measured memory_bytes: 256
//============================================================================
// Name        : test1.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

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

	int num1 = 0;

	for(int i=0;i<s.size();++i){
		if(i%2 == 0){
			if(s[i]=='0') num1 += 1;
		}else{
			if(s[i]=='1') num1 += 1;
		}
	}

	int num2 = 0;
	for(int i=0;i<s.size();++i){
		if(i%2 == 1){
			if(s[i]=='0') num2 += 1;
		}else{
			if(s[i]=='1') num2 += 1;
		}
	}

	if(num1<num2) cout << num1 << endl;
	else cout << num2 << endl;

}


Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
	int a,b,c;
	int x,y,z;
	scanf("%d %d %d",&a,&b,&c);
	if(a>b){
		x=b; b=a; a=x;
	}
	if(b>c){
		y=c; c=b; b=y;
	}
	if(a>b){
		z=b; b=a; a=z;
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
ll r[4005]={0};
ll g[4005]={0};
ll b[4005]={0};
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("text1.in","r",stdin);
	//freopen("text1.out","w",stdout);
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll ans=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]=='R'){
			r[i]=r[i+1]+1;
			g[i]=g[i+1];
			b[i]=b[i+1];
			ans=ans+g[i]*b[i];
		} 
		else if(s[i]=='G'){
			g[i]=g[i+1]+1;
			r[i]=r[i+1];
			b[i]=b[i+1];
			ans=ans+r[i]*b[i];
		} 
		else if(s[i]=='B'){
			g[i]=g[i+1];
			r[i]=r[i+1];
			b[i]=b[i+1]+1;
			ans=ans+r[i]*g[i];
		} 
	}
	for(int i=0;i<n;i++){
		int j=1;
		while(i+j*2<s.size()){
			if(s[i]!=s[i+j] && s[i+j]!=s[i+j+j] && s[i]!=s[i+j+j]){
				ans--;
			}
			j++;
		}	
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using vi=vector<int>;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<int> a(n),b(n);
    rep(i,n){
        int x; cin >> x;
        a[i]=b[i]=x;
    }
    sort(b.begin(),b.end());
    reverse(b.begin(),b.end());
    if(b[0]==b[1]){
        rep(i,n) cout << b[0] << "\n";
    }
    if(b[0]==b[1]) return 0;
    int maxi;
    rep(i,n){
        if(a[i]==b[0]) maxi=i;
    }
    rep(i,n){
        if(i!=maxi){
            cout << b[0] << "\n";
        }else{
            cout << b[1] << "\n";
        }
    }
    return 0;
}   

Measured memory_bytes: 4780
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,a[2];
int dp[105][2];

int main(void){
	//memset(dp,0,sizeof(dp));
	scanf("%d%d%d",&n,&a[0],&a[1]);
	ll res=0;
	bool flag=false;
	int flag2=0;
	int fl=0;
	for(int i=0;i<n;i++){
		int v;
		scanf("%d",&v);
		if(a[0]==a[1]){
			res^=v%(a[0]+1);
		}
		if(a[0]>a[1]){
			if(a[1]>=v){
				res^=v;
			}else{
				flag=true;
			}
		}
		if(a[0]<a[1]){
			if(a[0]>=v){
				res^=v;
			}else if(a[1]+1>=v){
				fl=v;
				flag2++;
			}else{
				flag=true;
			}
		}
	}
	if(a[0]==a[1]){
		printf("%s\n",res!=0LL?"Hanako":"Jiro");
		return 0;
	}
	if(a[0]>a[1]){
		if(flag || flag2>=2 || flag2==n){
			printf("Hanako\n");
		}else{
			printf("%s\n",res!=0LL?"Hanako":"Jiro");
		}
	}else{
		if(flag || flag2>=2 || flag2==n){
			printf("Jiro\n");
		}else{
			if(flag2==0)printf("%s\n",res!=0LL?"Hanako":"Jiro");
			else{
				printf("%s\n",(res<=a[0] & fl-res>=0 & fl-res<=a[0])?"Hanako":"Jiro");
			}
		}
	}
	/*
	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++){
			set<int> se;
			for(int k=1;k<=a[j];k++){
				if(i-k>=0){
					se.insert(dp[i-k][1-j]);
				}
			}
			int g=0;
			while(se.count(g)!=0)g++;
			dp[i][j]=g;
		}
	}
	for(int i=0;i<=n;i++){
		printf("%d ",dp[i][0]);
	}
	printf("\n");
	for(int i=0;i<=n;i++){
		printf("%d ",dp[i][1]);
	}
	printf("\n");
	*/
	return 0;
} 


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

using namespace std;

const int N = 2e5+10; 
int c[N], sta[N], fin[N], tim, mx[N][2];
vector<int> g[N], tour[N][2];

void prep_tour(int u, int p) {
    sta[u] = tim++;
    for (int i = 0; i < 2; i++) {
        tour[mx[u][i]][i].emplace_back(sta[u]);
    }
    for (int v: g[u])if(v!=p){
        mx[v][0] = max(v, mx[u][0]);
        mx[v][1] = max(min(v,mx[u][0]), mx[u][1]);
        prep_tour(v, u);
    }
    fin[u] = tim;
}

int down(int u, const vector<int>& t) {
    return lower_bound(t.begin(), t.end(), fin[u]) - lower_bound(t.begin(), t.end(), sta[u]);
}

void dfs(int u, int p, int mp, int mg) {
    c[u] = c[p];
    if (u > mg) {
        c[u] += down(u, tour[mp][u>mp]);
    } else if (mp > mg) {
        c[u] += down(u, tour[mp][0]) - down(u, tour[mg][1]);
    }
    for (int v: g[u])if(v!=p){
        dfs(v, u, max(mp, u), max(mg, p));
    }
}

void solve() {
    int n; cin >> n;
    for (int _ = 1; _ < n; _++) {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    mx[1][0] = 1; prep_tour(1, 0);
    dfs(1, 0, 1, 1);
    for (int i = 2; i <= n; i++) {
        cout << c[i] << ' ';
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 43244