akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import static java.lang.System.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        ArrayList<Integer>[] el=new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            el[i]=new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            el[a].add(b);
            el[b].add(a);
        }
        int ans=0;
        Queue<Integer> q=new ArrayDeque<>();
        q.add(1);
        Queue<TreeSet<Integer>> keiro=new ArrayDeque<>();
        TreeSet<Integer> ts=new TreeSet<>();
        keiro.add(ts);
        while (!q.isEmpty()){
            int p=q.poll();
            TreeSet<Integer> temp=(TreeSet<Integer>) keiro.poll().clone();
            temp.add(p);
            if(temp.size()==n){
                ans++;
            }else {
                for (Integer k : el[p]) {
                    if (!temp.contains(k)) {
                        q.add(k);
                        keiro.add(temp);
                    }
                }
            }
        }
        out.println(ans);
    }
}

Measured memory_bytes: 30208
#include<bits/stdc++.h>
using namespace std;
void check()
{
    if(false)
    cout<<"C"<<endl;
}
long long gcd(long long a, long long b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

long long xxxxGCD(long long arr[], long long n) 
{ 
    long long result = arr[0]; 
    for (int i = 1; i < n; i++) 
    { 
        result = gcd(arr[i], result); 
  
        if(result == 1) 
        { 
           return 1; 
        } 
    } 
    return result; 
}


#define ll long long
const int sz = 200009;
vector<ll> g[sz];
ll rnk[sz];
ll par[sz];
ll xxxx(ll x) {
    
	if (x == par[x])
	{
	return x;
	}
	return par[x] = xxxx(par[x]);
}


ll tedX(ll x, ll y) {
	x = xxxx(x);
	y = xxxx(y);
	if (!(x != y))
	{
	    check();
	return 0;
	}
	if (!(!(rnk[x] < rnk[y]))) {
	    check();
		swap(x, y);
	}
	rnk[x] =rnk[x] + rnk[y];
	par[y] = x;
	return 0;
}

int main()
{
   ll t, i, x, j, y;
   long long z = 1, k, n;
	cin >> n >> t;
    //long long rnk[n];
    //long long par[n];
check();
	for(i= 1;i<n + 1;i+=1) {
		rnk[i] = 1;
		par[i] = i;
	}check();

	while (t--) {
		cin >> x >> y;
		check();
		tedX(x, y);
	}

	for(i= 1;i< n + 1;i+= 1) {
		if (!(par[i] != i)) {
		    check();
			z = max(z, rnk[i]);
			check();
			z-=1;
			z+=1;
		}
	}
check();	
check();
cout<<z<<"\n"<<endl;
check();
check();
}

Measured memory_bytes: 11448
#include <stdio.h>
#include <math.h>
int main(void){
  int x,a,b,c;
  scanf("%d%d%d%d",&a,&b,&c,&x);
  int i,j,k,count;
  for(i=0;i<=a;i++){
    for(j=0;j<=b;j++){
      for(k=0;k<=c;k++){
        if(500*i+100*j+50*k==x) count++;
      }
    }
  }
  printf("%d",count);
  return 0;
}

Measured memory_bytes: 128
n=int(input())
f=[]
for i in range(n):
    tmp=0
    op=list(map(int,input().split()))
    for j in range(10):
        tmp+=op[j]<<j
    f.append(tmp)

p=[]
for i in range(n):
    p.append(list(map(int,input().split())))

ans=-10**12
for i in range(1, 1<<10):
    tmp=0
    for j in range(n):
        consist=list(bin(f[j]&i)[2:])
        cnt=0
        for k in consist:
            if k=='1':
                cnt+=1
        tmp+=p[j][cnt]
    ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 68552
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def is_match(string, pattern):
    if pattern in string:
        return True
    else:
        return False

def main():
    N = int(input())
    S = input()
    dp = [0] * N
    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
    print(dp[-1])
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 14432
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;

int main()
{
	string str = "";
	int count = 0;

	while (getline (cin, str ) ){
		int max_wight;
		stringstream ssw (str );
		ssw >> max_wight;

		if (max_wight == 0 ){
			break;
		} // end if
		++count;
		
		int n;
		getline (cin, str );
		stringstream ssn(str);
		ssn >> n;

		vector <int> W (n, 0 );
		vector <int> V (n, 0 );
		vector <int> DP (max_wight + 1, 0 );
		int i,j;

		for (i = 0; i < n; ++i){
			getline (cin, str );
			while (str.find (',') != string::npos ){
				str = str.replace ( str.find (','), 1, " " );
			} // end while
			stringstream ss(str);
			ss >> V[i] >> W[i];
		} // end for

		for (i = 0; i < n; ++i){
			vector <int> dp = DP;
			for (j = W[i]; j <= max_wight; ++j){
				int p = j - W[i];
				if (dp[p] + V[i] > DP[j] ){
					DP[j] = dp[p] + V[i];
				} // end if 
			} // end for
		} // end for

		int maxvalue = DP[max_wight];
		int minwight = max_wight;

		for (j = max_wight - 1; j >= 0; --j){
			if (DP[j] >= maxvalue){
				minwight = j;
				maxvalue = DP[j];
			} // end if
		} // end for
		cout << "Case " << count << ':' << endl;
		cout << maxvalue << endl;
		cout << minwight << endl;
			
	} // end while	
	
	return 0;
}

Measured memory_bytes: 1256
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
using namespace std;

struct node{int p,l,r;};
node a[30];

void preo(node a[],int r)
{
	if(a[r].l==-1&&a[r].r==-1)cout<<" "<<r;
	else
	{
		cout<<" "<<r;
		if(a[r].l!=-1)preo(a,a[r].l);
		if(a[r].r!=-1)preo(a,a[r].r);
	}
}

void ino(node a[],int r)
{
	if(a[r].l==-1&&a[r].r==-1)cout<<" "<<r;
	else
	{
		if(a[r].l!=-1)ino(a,a[r].l);
		cout<<" "<<r;
		if(a[r].r!=-1)ino(a,a[r].r);
	}
}

void posto(node a[],int r)
{
	if(a[r].l==-1&&a[r].r==-1)cout<<" "<<r;
	else
	{
		if(a[r].l!=-1)posto(a,a[r].l);
		if(a[r].r!=-1)posto(a,a[r].r);
		cout<<" "<<r;
	}
}

int main()
{
	int n;cin>>n;
	for(int i=0;i<n;a[i++].p=-1);
	for(int i=0;i<n;i++)
	{
		int k;cin>>k;
		cin>>a[k].l>>a[k].r;
		if(a[k].l+1)a[a[k].l].p=k;
		if(a[k].r+1)a[a[k].r].p=k;
	}
	int r=0;
	for(int i=0;i<n;i++)
	{
		if(a[i].p==-1)
		{
			r=i;
			break;
		}
	}
	cout<<"Preorder"<<endl;
	preo(a,r);
	cout<<endl<<"Inorder"<<endl;
	ino(a,r);
	cout<<endl<<"Postorder"<<endl;
	posto(a,r);
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;
using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
  string s;cin>>s;
  string a;cin>>a;
  int ans=0;
  REP(i,3){
    if(a[i]==s[i]){
      ans=ans+1;
    }
  }
  cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X,Y,Z;
    cin >> X >> Y >> Z;
    int N = X+Y+Z;
    vec<ll> A(N),B(N),C(N);
    for(int i=0;i<N;i++) cin >> A[i] >> B[i] >> C[i];
    vec<int> idx(N);
    iota(idx.begin(),idx.end(),0);
    sort(idx.begin(),idx.end(),[&](int i,int j){
        return A[i]-C[i]>A[j]-C[j];
    });
    vec<ll> L(N+1),R(N+1);
    priority_queue<ll> Q;
    ll now = 0;
    for(int i=0;i<N;i++){
        int id = idx[i];
        Q.push(B[id]-A[id]);
        now += A[id];
        if(i<X){
            L[i+1] = now;
        }else{
            ll t = Q.top(); Q.pop();
            now += t;
            L[i+1] = max(L[i],now);
        }
    }
    now = 0;
    while(!Q.empty()) Q.pop();
    for(int i=N-1;i>=0;i--){
        int id = idx[i];
        Q.push(B[id]-C[id]);
        now += C[id];
        if(N-1-i<Z){
            R[i] = now;
        }else{
            ll t = Q.top(); Q.pop();
            now += t;
            R[i] = max(R[i+1],now);
        }
    }
    ll ans = 0;
    for(int i=X;i<=X+Y;i++) ans = max(ans,L[i]+R[i]);
    cout << ans << "\n";
}

Measured memory_bytes: 5752
/*
神题
行列建图，转化为环套树问题
分2种情况讨论，每种情况可转化为内向树上拓扑序计数，树型DP
O(n)
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400010
#define ll long long
#define mod 1000000007
using namespace std;

struct edge{int x, y, next;}a[N*2], c[N];
int n, l, p[N], x, y, jc[N], inv[N], l1, w[N], sum_v, sum_e, ans, ff, flag[N], fa[N], b[N], to[N], f1[N],
ans1, q[N], du[N], root, l2, f[N], size[N], sum, l3, d[N];

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=p[x]; p[x]=l;}
inline void dfs_circle(int x){
	flag[x]=1; sum_v++; d[++l3]=x;
	for(int i=p[x]; i; i=a[i].next)if(fa[x]!=a[i].y){
		sum_e++;
		if(flag[a[i].y]){
			if(ff)continue; ff=1;
			l=1; b[0]=a[i].y; b[1]=x;
		}else{fa[a[i].y]=x; dfs_circle(a[i].y);}
	}
}
inline void dfs_tree(int x, int fa){
	to[x]=fa;
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!f1[a[i].y])dfs_tree(a[i].y, x);
}

inline void add1(int x, int y){c[++l2].x=x; c[l2].y=y; c[l2].next=q[x]; q[x]=l2;}
inline void dp(int x){
	size[x]=1;
	for(int i=q[x]; i; i=c[i].next){dp(c[i].y); size[x]+=size[c[i].y];}
	f[x]=jc[size[x]-1];
	for(int i=q[x]; i; i=c[i].next)f[x]=(ll)f[x]*f[c[i].y]%mod*inv[size[c[i].y]]%mod;
}
inline int solve(){
	l2=0; root=n*2+1; q[root]=0;
	for(int i=1; i<=l3; i++)q[d[i]]=du[d[i]]=0;
	int x, y;
	for(int i=1; i<=l3; i++){
		x=d[i]; y=to[x];
		for(int j=p[x]; j; j=a[j].next)if(a[j].y<y){du[a[j].y]++; add1(x, a[j].y);}
	}
	for(int i=1; i<=l3; i++)if(!du[d[i]])add1(root, d[i]);
	dp(root); return f[root];
}

int main(){
	scanf("%d", &n);
	l=0; memset(p, 0, sizeof(p));
	for(int i=1; i<=n*2; i++){scanf("%d%d", &x, &y); add(x, n+y); add(n+y, x);}
	jc[0]=1; for(int i=1; i<=n*2; i++)jc[i]=(ll)jc[i-1]*i%mod;
	inv[0]=inv[1]=1; for(int i=2; i<=n*2; i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1; i<=n*2; i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
	memset(flag, 0, sizeof(flag)); l1=0; ans=1;
	memset(f1, 0, sizeof(f1));
	for(int i=1; i<=n*2; i++)if(!flag[i]){
		ff=sum_v=sum_e=0; fa[i]=0; l3=0; dfs_circle(i); sum_e--;
		if(sum_v!=sum_e){printf("0"); return 0;}
		w[++l1]=sum_v;
		x=b[1]; while(x!=b[0]){x=fa[x]; b[++l]=x;} b[l+1]=b[1];
		for(int j=1; j<=l; j++)f1[b[j]]=1;
		for(int j=1; j<=l; j++){x=b[j]; dfs_tree(x, 0);}
		for(int j=1; j<=l; j++)to[b[j]]=b[j-1]; ans1=solve();
		for(int j=1; j<=l; j++)to[b[j]]=b[j+1]; ans1=(ans1+solve())%mod;
		ans=(ll)ans*ans1%mod;
	}
	sum=0; for(int i=1; i<=l1; i++)sum+=w[i];
	ans=(ll)ans*jc[sum]%mod;
	for(int i=1; i<=l1; i++)ans=(ll)ans*inv[w[i]]%mod;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 33408
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, Y;
    cin >> N >> Y;
    int ax,ay,az;
    for (int x = 0; x <= N; x++){
        for (int y = 0; y <= N; y++){
            if (N-x-y >= 0){
                if (x*1000+y*5000+(N-x-y)*10000 == Y){
                    ax = x;
                    ay = y;
                    az = N-x-y;
                    cout << az << " " << ay << " " << ax << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}


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

int main()
{
  int N,X;
  cin >> N >> X;
  int m[100];
  int min_m = 1000;
  for(int i = 0;i < N;i++){
    cin >> m[i];
    X = X - m[i];
    min_m = min(min_m,m[i]);
  }

  int r = X / min_m;
  cout << (r + N) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
const ll mod = (ll) 1e9 + 7;
vvi inp, a, res;
ll n, k, ans = 0;


inline void matmul1()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            a[i][j] = 0;
            for (int k = 0; k < n; k++)
                a[i][j] = (a[i][j] + res[i][k]*inp[k][j]) % mod; 
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res[i][j] = a[i][j];
}
inline void matmul2()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            a[i][j] = 0;
            for (int k = 0; k < n; k++)
                a[i][j] = (a[i][j] + inp[i][k]*inp[k][j]) % mod; 
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            inp[i][j] = a[i][j];
}


void matexp()
{
    for (int i = 0; i < n; i++)
        res[i][i] = 1;   
    while (k > 0)
    {
        if (k & 1)
            matmul1();
        k >>= 1;
        matmul2();
    }
}


inline void solve()
{
    matexp();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = (ans + res[i][j]) % mod;
}


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n >> k;
    
    inp.resize(n,vi(n));
    a.resize(n,vi(n, 0));
    res.resize(n, vi(n, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> inp[i][j];
    
    solve();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
def ExtendedGCD(a, b, x, y):
    """
    ax + by = gcd(a, b)となる(y, x)の組,gcd(a,b)を返す
    """
    if b == 0:
        return 0, 1, a
    x, y, g = ExtendedGCD(b, a % b, y, x)
    return y - (a // b) * x, x, g


if __name__ == "__main__":
    a, b = map(int, input().split())
    y, x, gcd = ExtendedGCD(a, b, 0, 0)
    print(x, y)


Measured memory_bytes: 5612
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        a: usize,
        b: usize,
        k: usize
    };

    let x1 = if a > b { a } else { b };
    let x2 = if a > b { b } else { a };

    let mut count = 0;
    let mut y = x1;

    while x1 > 0 {
        let z1 = x1 / y;
        let z2 = x2 / y;

        if z1 * y == x1 && z2 * y == x2 {
            count += 1;
        }
        if count == k {
            println!("{}", y);
            break;
        }

        y -= 1;
    }
}


Measured memory_bytes: 2168
// Copyright 2019 yaito3014
#include "bits/stdc++.h"
using namespace std;
using namespace literals;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  struct Key {
    int cost = 0;
    int mask = 0;
  };
  const int All = (1 << N) - 1;
  vector<Key> keys(M);
  for (auto& key : keys) {
    int a, b;
    cin >> a >> b;
    key.cost = a;
    for (int i = 0; i < b; ++i) {
      int c;
      cin >> c;
      key.mask |= (1 << (c - 1));
    }
  }
  constexpr int INF = INT_MAX-100000;
  int n = 1 << N;
  vector<int> dp(n, INF);
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < M; ++j) {
      dp[i | keys[j].mask] = min(dp[i | keys[j].mask], dp[i] + keys[j].cost);
    }
  }
  int ans = dp[n - 1];
  if (ans == INF)ans = -1;
  cout << ans << endl;
}


Measured memory_bytes: 256
while True:
    m, f, r = map(int, input().split())
    score = m + f
    if m == f == r == -1:
        break
    elif m == -1 or f == -1:
        print('F')
    elif score >= 80:
        print('A')
    elif score >= 65:
        print('B')
    elif score >= 50 or (score >= 30 and r >= 50):
        print('C')
    elif score >= 30:
        print('D')
    else:
        print('F')


Measured memory_bytes: 5596
n = int(input())
b = [1]*(10**7+1)
for i in range(2, n+1):
    for j in range(i, 10**7+1, i):
        b[j] += 1
ans = 0
for i in range(1, n+1):
    ans += (i*b[i])
print(ans)

Measured memory_bytes: 145908
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#include <numeric>
#define ll long long
using namespace std;
int main() {
  int N;
  ll sum=0,h=0;
  cin>>N;
  ll A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  ll a=A[0],b=sum-a,ans=sum;
  ans=min(ans,abs(a-b));
  for(int i=1;i<N;i++){
    a+=A[i];
    b-=A[i];
    ans=min(ans,abs(a-b));
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>

struct Card {
    char suit;
    char value;
};

void printLine(struct Card C[], int N)
{
    int i;
    for (i = 0; i < N; i++) {
        if (i > 0) printf(" ");
        printf("%c%c", C[i].suit, C[i].value);
    }
    printf("\n");
}

void swap(struct Card *a, struct Card *b)
{
    struct Card tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

void selectionSort(struct Card C[], int N)
{
    int minj;
    for (int i = 0; i < N - 1; i++) {
        minj = i;
        for (int j = i; j < N; j++) {
            if (C[j].value < C[minj].value) {
                minj = j;
            }
        }
        if (i != minj) {
            swap(&C[i], &C[minj]);
        }
    }
}


void bubbleSort(struct Card C[], int N)
{
    int flag = 1;
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = N-1; j > i; j--) {
            if (C[j-1].value > C[j].value) {
                swap(&C[j], &C[j-1]);
                flag = 1;
            }
        }
    }
}

int isStable(struct Card C1[], struct Card C2[], int N)
{
    for (int i = 0; i < N; i++) {
        if (C1[i].suit != C2[i].suit) return 0;
    }
    return 1;
}

int main(void)
{  
    int i, N;
    struct Card C1[36];
    struct Card C2[36];

    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        char tmp[2];
        scanf("%s", tmp);
        C1[i].suit = tmp[0];
        C1[i].value = tmp[1];
    }

    for (i = 0; i < N; i++) {
        C2[i] = C1[i];
    }

    bubbleSort(C1, N);
    printLine(C1, N);
    printf("Stable\n");

    selectionSort(C2, N);
    printLine(C2, N);
    if (isStable(C1, C2, N)) {
        printf("Stable\n");
    } else {
        printf("Not stable\n");
    }

    return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Country
{
public:
  string A;
  int B, C;
  long long int D;
  vector<string> d;
  bool operator < (const Country& c) const
  {
    return this->C > c.C;
  }
};

int solve(int idx, long long int visited, const vector<Country>& c)
{
  if (idx >= (int)c.size())
    return 0;

  int ret = 0;
  if (!((1LL << idx) & visited) && (c[idx].D - ((1LL << (idx+1))-1) <= 0)) {
    ret = solve(idx+1, visited | c[idx].D, c) + c[idx].B;
  } else {
    if (!((1LL << idx) & visited))
      ret = solve(idx+1, visited | c[idx].D, c) + c[idx].B;
    ret = max(ret, solve(idx+1, visited, c));
  }
  return ret;
}

int main()
{
  int N;
  while (cin >> N) {
    if (N == 0)
      break;

    vector<Country> c(N);
    for (int i = 0; i < N; ++i) {
      cin >> c[i].A >> c[i].B >> c[i].C;
      for (int j = 0; j < c[i].C; ++j) {
        string dij;
        cin >> dij;
        c[i].d.push_back(dij);
      }
    }

    sort(c.begin()+1, c.end());
    for (int i = 0; i < N; ++i) {
      c[i].D = 1LL << i;
      for (unsigned int j = 0; j < c[i].d.size(); ++j) {
        for (int k = 0; k < N; ++k) {
          if (c[i].d[j] == c[k].A) {
            c[i].D |= 1LL << k;
            break;
          }
        }
      }
    }

    cout << solve(1, c[0].D, c)+c[0].B << endl;
  }
  return 0;
}

Measured memory_bytes: 1008
#include <iostream>
#include <vector>
#include <map>

using namespace std;

void make_alpha(string str, vector<int>& alpha) {
	int num = 0;
	int len = str.length(); 
	map<char,int> memo;
	for (int i = 0; i < len; ++i) {
		if (memo[str[i]] > 0) {
			alpha[i] = memo[str[i]];
		}
		else {
			++num;
			alpha[i] = num;
			memo[str[i]] = num;
		}
	}
	return;
}

int main(void) {
	string S,T;
	cin >> S >> T;
	vector<int> sa(S.length());
	make_alpha(S,sa);
	vector<int> ta(T.length());
	make_alpha(T,ta);
	if (sa == ta) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 2372
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W =sc.nextInt();
		int H =sc.nextInt();
		int x =sc.nextInt();
		int y =sc.nextInt();
		int r =sc.nextInt();
    if(x+r<=W && x-r>=0 && y+r<= H && y-r >=0){
        System.out.println("Yes");
    }else{
        System.out.println("No");
    }
	}
}


Measured memory_bytes: 26312
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    long long sum1=0,sum2=0;
    scanf("%d",&m);
    int a[m+5];
    for(int i=1;i<=m;i++)
    {
    	scanf("%d",&a[i]);
	}
	sort(a+1,a+m+1);
	if(m==2)
	printf("%d\n",abs(a[1]-a[2]));
	else
	{
			int x=1,y=m;
	int k=(m+1)/2;
	while(x!=k&&y!=k)
	{
		if(k<=(m+1)/2)
		{
			if(y!=(m+1)/2)
			sum1=sum1+abs(a[k]-a[y]);
		    k=y;
		    y--;
		}
		else
		{
			if(x!=(m+1)/2)
			sum1=sum1+abs(a[k]-a[x]);
			k=x;
			x++;
		}
	}
	x=1;y=m;
	k=(m+1)/2;
	while(x!=k&&y!=k)
	{
		if(k<(m+1)/2)
		{
			if(y!=(m+1)/2)
			sum2=sum2+abs(a[k]-a[y]);
		    k=y;
		    y--;
		}
		else
		{
			if(x!=(m+1)/2)
			sum2=sum2+abs(a[k]-a[x]);
			k=x;
			x++;
		}
	}
	printf("%lld\n",max(sum1,sum2));
	}
    return 0;
}

Measured memory_bytes: 640
import itertools
def op(x,y,i):
    if i=="+": return x+y
    elif i=="-": return x-y
    elif i=="*": return x*y

e0 = "((({} {} {}) {} {}) {} {})"
e1 = "(({} {} {}) {} ({} {} {}))"
def check(A, n):
    w,x,y,z = A
    S="+-*"
    for i in S:
        a = op(w,x,i)
        for j in S:
            b1,b2 = op(a,y,j),op(y,z,j)
            for k in S:
                if op(b1,z,k)==n: return e0.format(w,i,x,j,y,k,z)
                if op(a,b2,k)==n: return e1.format(w,i,x,k,y,j,z)
    return ""

n=10
while 1:
    x = map(int,raw_input().split())
    if x==[0,0,0,0]: break
    for e in itertools.permutations(x):
        s = check(e,n)
        if s!="": break
    else: s = "0"
    print s

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

using namespace std;

#define fore(i, s, e) for(int i = s; i < e; i++)
#define FIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() {
    int n, a, b; cin >> n >> a >> b;
    map<int, int> m;
    fore(i, 0, n) {
        int x;
        cin >> x;
        if(x <= a) m[0]++;
        if(a < x && x <= b) m[1]++;
        if(b < x) m[2]++;
    }
    cout << min({m[0], m[1], m[2]}) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int N,M;
  
   while(cin >> N >> M,N + M){
    int h[1600],w[1600];
    int counth[1500001] = {0};
    int countw[1500001] = {0};
    
    for(int i = 0;i < N;i++){
      cin >> h[i];
    }  

    for(int i = 0;i < M;i++){
      cin >> w[i];
    }

  for(int i = 0;i < N;i++){
    int sum;
    for(int j = i;j < N;j++){
      if(i == j){
	sum = h[i];
      } else {
	sum += h[j];
      }  
      counth[sum]++;
    }
  }

  for(int i = 0;i < M;i++){
    int sum;
    for(int j = i;j < M;j++){
      if(i == j){
	sum = w[i];
      } else {
	sum += w[j];
      }  
      countw[sum]++;
    }
  }

  int sum = 0;

  for(int i = 0;i < 1500001;i++){
    sum += counth[i] * countw[i];
  }

  cout << sum << endl;

  }
}



Measured memory_bytes: 14804
# abc072B
# https://atcoder.jp/contests/abc072/tasks/abc072_b

# 英小文字からなる文字列 s
# 前から奇数文字目だけを抜き出し文字列を出力
# 先頭の文字を１文字目とする


# 入力
s = str(input())

# 処理
# 奇数番目文字の抜き出し
print(s[::2])


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

int main(void) {
  int N;
  cin >> N;
  vector<long long> T(N), A(N);
  for (int i = 0; i < N; i++) {
    cin >> T[i] >> A[i];
  }

  long long t = 1LL, a = 1LL;
  for (int i = 0; i < N; i++) {
    if (T[i] >= t && A[i] >= a) {
      t = T[i];
      a = A[i];
    } else {
      long long b = max(ceil((long double)t / T[i]), ceil((long double)a / A[i]));
      t = T[i] * b;
      a = A[i] * b;
    }
  }
  cout << t + a << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = sum(b)
for i in range(len(c)):
    try:
        if a[a.index(i+1)+1] == i+2:
            ans += c[i]
    except IndexError:
        pass
print(ans)

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

auto print = [](auto &v) {
  for(auto x : v) {
    cout << x << " ";
  }
  cout << endl;
};

int stoi(const char c){
  return c - '0';
}

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string n;
  cin >> n;
  reverse(all(n));
  VVL dp(n.size() + 1, VL(2, 0));
  dp[0][0] = stoi(n[0]);
  dp[0][1] = 10 - stoi(n[0]);
  rep(i, n.size() - 1) {
    dp[i + 1][0] = min(dp[i][0] + stoi(n[i + 1]), dp[i][1] + stoi(n[i + 1]) + 1);
    dp[i + 1][1] = min(dp[i][0] + 10 - stoi(n[i + 1]), dp[i][1] + 10 - stoi(n[i + 1]) - 1);
  }
  out(min(dp[n.size() - 1][0], dp[n.size() - 1][1] + 1));

  return 0;
}


Measured memory_bytes: 55964
#include<bits/stdc++.h>
using namespace std;
int h,w;
char s[2005][2005],o;
int a[2005][2005],b[2005][2005];
int c[2005][2005],d[2005][2005];
int ans=0;

int main(){
	scanf("%d %d",&h,&w);
	for(int i=1;i<=h;i++){
		scanf("%c",&o);
		for(int j=1;j<=w;j++){
			scanf("%c",&s[i][j]);
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(s[i][j]=='#'){
				a[i][j]=0;
			}
			else{
				a[i][j]=a[i-1][j]+1;
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(s[i][j]=='#'){
				c[i][j]=0;
			}
			else{
				c[i][j]=c[i][j-1]+1;
			}
		}
	}
	for(int i=h;i>=1;i--){
		for(int j=w;j>=1;j--){
			if(s[i][j]=='#'){
				b[i][j]=0;
			}
			else{
				b[i][j]=b[i+1][j]+1;
			}
		}
	}
	for(int i=h;i>=1;i--){
		for(int j=w;j>=1;j--){
			if(s[i][j]=='#'){
				d[i][j]=0;
			}
			else{
				d[i][j]=d[i][j+1]+1;
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			ans=max(ans,a[i][j]+b[i][j]+c[i][j]+d[i][j]-3);
		}
	}
	printf("%d\n",ans);
	
	return 0;
}

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

int main(){
    int w, h, x, y, r;
    string result;
    cin >> w >> h >> x >> y >> r;
    if (x-r>=0 && x+r<=w){
        if (y-r>=0 && y+r<=h){
            result = "Yes";
        }
        else {
            result = "No";
        }
    }
    else {
        result = "No";
    }
    cout << result << endl;
}


Measured memory_bytes: 3204
#include<bits/stdc++.h>
#define f(a,n) for(ll i=a;i<n;i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define all(v) v.begin(),v.end()
using namespace std;
const ll mod=(1e+9)+7;
const ll size = 2e5+9;
ll gcd(ll a,ll b) {if(b==0)return a;return gcd(b,a%b);}
ll power(ll a,ll b,ll m = mod) {ll res = 1;while(b>0){if(b&1)res = (res*a)%m;b = b>>1;a = (a*a)%m;}return res;}


void solve()
{
    ll n;
    cin>>n;
    ll a[n],b;
    f(0,n)
    {
        cin>>a[i];
        a[i] -= (i+1);
    }
    sort(a,a+n);
    if(n&1)
    b = a[n/2];
    else
    b = (a[n/2]+a[(n/2) - 1])/2;
    ll ans = 0;
    f(0,n)
    ans += abs(a[i]-b);
    cout<<ans<<endl;

}

int main()
{
    #ifdef JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    clock_t beg = clock();
    solve();
    clock_t end = clock();
    fprintf(stderr, "%.3f sec, Copyright %c 2019 Skyscraper. \n", double(end - beg) / CLOCKS_PER_SEC , 184);
    return 0;
}

Measured memory_bytes: 1792
import numpy as np

n, k = map(int, input().split())
MOD = 10 ** 9 + 7
ref = np.array(list(range(n + 1)), dtype='int64')

ans = 0

for i in range(k, n + 2):
    min_sum = (ref[i - 1] * (ref[i - 1] + 1)) // 2
    max_sum = (n + ref[-i]) * (n - ref[-i] + 1) // 2
    ans += max_sum - min_sum + 1
    ans %= MOD

print(ans)

Measured memory_bytes: 36184
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/

ll N, M;
ll a[MAX], s[MAX];

ll ok(ll x) {
  ll cnt=0;
  for(ll i=0; i<N; i++) {
    ll pos=lower_bound(a, a+N, x-a[i])-a;
    cnt+=N-pos;
  }
  
  return cnt<M;
}

int main(void) {
  ll i, j, k;
  cin >> N >> M;
  
  for(i=0; i<N; i++) cin >> a[i];
  sort(a, a+N);
  
  
  ll l=0, r=INF;
  while(l+1<r) {
    ll m=(l+r)/2;
    if(ok(m)) r=m;
    else l=m;
  }
  
  for(i=0; i<N; i++) s[i+1]=s[i]+a[i];
  
  ll X=r;
  ll ans=0;
  for(i=0; i<N; i++) {
    ll pos=lower_bound(a, a+N, X-a[i])-a;
    ll cnt=N-pos;
    ans+=a[i]*cnt+(s[N]-s[pos]);
    M-=cnt;
  }
  
  ans+=(X-1)*M;
  pt(ans);
  
}



Measured memory_bytes: 1792
#include <iostream>

using namespace std;

#define INPUT_MIN -1000
#define INPUT_MAX 1000

int main()
{
	int a = 0, b = 0;
	
	cin >> a;
	cin >> b;
	
	
	if( (INPUT_MIN > a) || (INPUT_MAX < a) )
	{
		return 1;
	}
	
	if( (INPUT_MIN > b) || (INPUT_MAX < b) )
	{
		return 1;
	}
	
	if(a < b)
	{
		cout << "a < b" << endl;
	}
	else if(a > b)
	{
		cout << "a > b" << endl;
	}
	else
	{
		cout << "a == b" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3108
def prime_facorize(N):
    res = {1}
    for i in range(2, int(N ** 0.5) + 1):
        while N % i == 0:
            res.add(i)
            N /= i

        if N <= 1:
            break
    if N > 1:
        res.add(N)
    return res


A, B = map(int, input().split())
commons = prime_facorize(A) & prime_facorize(B)
print(len(commons))

Measured memory_bytes: 38640
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();
    String str = sc.next();
    char[] c = new char[n];

    for (int i = 0 ; i < n ; i++ ) {
      c[i] = str.charAt(i);
    }

    if (c[k-1] == 'A') {
      c[k-1] = 'a';
    }

    if (c[k-1] == 'B') {
      c[k-1] = 'b';
    }

    if (c[k-1] == 'C') {
      c[k-1] = 'c';
    }

    for (int i = 0 ; i < n ; i++ ) {
      System.out.print(c[i]);
    }
  }
}


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

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

const int N = 1e5 + 5;

char s[N];
int p[N], n;

bool solve() {
  if (s[1] == '0') return 0;
  if (s[n] == '1') return 0;
  for (int i = 1; i < n; ++i)
    if (s[i] != s[n - i]) return 0;

  int l = n;
  for (int i = n - 1; i >= 1; --i) {
    p[i] = l;
    if (s[i] == '1') l = i;
  }

  return 1;
}

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);

  if (solve()) {
    for (int i = 1; i < n; ++i) {
      printf("%d %d\n", i, p[i]);
    }
  } else {
    puts("-1");
  }
}


Measured memory_bytes: 1920
n, k = map(int, input().split())
num = [0] * 100000
for i in range(n):
  a, b = map(int, input().split())
  num[a - 1] += b
for i in range(100000):
  if num[i] > 0:
    k -= num[i]
    if k <= 0:
      ans = i + 1
      break
print(ans)

Measured memory_bytes: 5748
#include<stdio.h>
int main(){
int k=0,min=100000010,n,a[5],i,j;
scanf("%d\n",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n;i++){
if(a[i]<min){
min=a[i];
}
}
for(i=1;i<=min;i++){
for(j=0;j<n;j++){
if(a[j]%i!=0){
k=1;
break;
}
}
if(k==0){
printf("%d\n",i);
}
k=0;
}
return 0;
}


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

// iterator
#define REP(i,from, to) for(lli i=from;i<to;i++)
#define REPE(i,from, to) for(lli i=from;i<=to;i++)
#define REP_R(i,from, to) for(lli i=from;i>to;i--)
#define REPE_R(i,from, to) for(lli i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) { cin1(x[i]); }
#define ncin2(n, x, y)      REP(i, 0, n) { cin2(x[i], y[i]); }
#define ncin3(n, x, y, z)   REP(i, 0, n) { cin3(x[i], y[i], z[i]); }
#define ncinp(n, p)         REP(i, 0, n) { lli p1,p2; cin >> p1 >> p2; p[i] = P(p1, p2); }
#define ncin1_1(n, x)       REPE(i, 1, n) { cin1(x[i]); }
#define ncin2_1(n, x, y)    REPE(i, 1, n) { cin2(x[i], y[i]); }
#define ncin3_1(n, x, y, z) REPE(i, 1, n) { cin3(x[i], y[i], z[i]); }
#define ncinp_1(n, p)       REPE(i, 1, n) { lli p1,p2; cin >> p1 >> p2; p[i] = P(p1, p2); }

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;
typedef vector<lli> vlli;

int main() {
    lli x;
    cin1(x);
    // 953〜1000まで
    lli count_min = ceil(x / 105.0);
    lli count_max = x / 100;

    //cout2(count_min, count_max);
    REPE(i,count_min, count_max) {
        lli total = x - i * 100;
        //cout2(i, total);
        // count_min 個たして total になればいい
        if (5 * i >= total) {
            cout << 1 << endl;
            return 0;
        }
    }
            cout << 0 << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(a == b && b == c)
    cout << "No" << endl;
  else if(a != b && b != c && c != a)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  return 0;
}

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

int c[4],a[4]={1,2,4,8};
LL n;
int main()
{
	for(int i=0;i<4;i++)get1(c[i]);
	get1(n);n*=4;
	for(int i=1;i<4;i++)c[i]=min(c[i],c[i-1]*2);
//	for(int i=0;i<4;i++)printf("%d ",c[i]);
	LL ans=0;
	for(int i=3;i>=0;i--)
	{
		ans+=n/a[i]*c[i];
		n%=a[i];
	}
	printendl(ans);
	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define INF 1e+9


int main() {
	int n;
	int a[100001], b[100001];
	cin >> n;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] <= b[i]) {
			if ((b[i]-a[i])<=a[i+1]) {
				a[i + 1] -= (b[i] - a[i]);
				ans += b[i];
			}
			else {
				ans += (a[i] + a[i + 1]);
				a[i + 1] = 0;

			}
		}
		else {
			ans += b[i];
		}
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>

using namespace std;

const unsigned long long S = 4;

int main() {
    unsigned long long P[S]; // Q, H, S, D
    cin >> P[0] >> P[1] >> P[2] >> P[3];

    unsigned long long N;
    cin >> N;
    N *= 4;

    unsigned long long PS[S] = {1, 2, 4, 8};
    pair<unsigned long long, unsigned long long> PP[S] = {
        {8 * P[0], 0}, {4 * P[1], 1}, {2 * P[2], 2}, {P[3], 3}
    };

    sort(PP, PP + S);
    unsigned long long cnt[S] = {};
    for (unsigned long long i = 0; i < S; ++i) {
        if (N >= PS[PP[i].second]) {
            cnt[PP[i].second] += N / PS[PP[i].second];
            N = N % PS[PP[i].second];
        }
    }

    unsigned long long ans = 0;
    for (unsigned long long i = 0; i < S; ++i) {
        ans += cnt[i] * P[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int n;
int t[600001];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i=1;i<=100;++i) for (int j=1;j<=100;++j) for (int k=1;k<=100;++k) ++t[(i*i+j*j+k*k+i*j+j*k+k*i)];
	for (int i=1;i<=n;++i) cout << t[i] << "\n";
}

Measured memory_bytes: 3820
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
#include <utility>
#include <cstring>
#include <numeric>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define repll(i,n) for(long long int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
template <typename T_char>
char ToUpper (char cX) { return toupper(cX); }
//g++ -std=c++1z temp.cpp
//./a.exe
ll digit(ll a){
    ll count = 0;
    for (ll i = 0; i < a; i++)
    {   if (a == 0)
        {
            break;
        }else
        {
            a = a/10;
            count++;
        }
    }
    return count;
}
//桁数のカウント
//pow(x,n) == x^n
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a,   b) * b;}



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

char a;
scanf("%c",&a);
printf("%c",a + 1);




//////////////////////////////////////////////////////
return 0;}

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

using namespace std;

int main() {

    long long n, m, d;
    cin >> n >> m >> d;
    if (d == 0) {
        cout << fixed << setprecision(10) << (long double)(m - 1) * (n - d) / (long double)(n * n);
    }
    else {
        cout << fixed << setprecision(10) << (long double)(m - 1) * 2 * (n - d) / (long double)(n * n);
    }
    return 0;
}


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

string abc = "acdfhjlnpqrstuvwxyz";

main()
{
    int a, n; cin >> n >> a;

    int b = n / 500;
    b = 500 * b;

    if(b + a >= n)
    cout << "Yes";
    else
    cout << "No";
}


Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <cstdio>
#include <queue>
#include <unordered_set>

using namespace std;

#define rank roman_kaban


int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    int m = 2 * n - 1;
    if(x == 1 || x == m){ cout << "No"<< endl; return 0; }
    cout << "Yes\n";
    int start = x - n + 1;
    if(start <= 0) start += m;
    for(int i = 1; i <= m; i++){
        cout << start << "\n";
        ++start;
        if(start == m + 1) start = 1;
    }
    return 0;
}


/*
1 2 3 4 5 6 7
  2 3 4 5 6
    3 4 5
      4

2 3 4 5 6 7 1
  3 4 5 6 6
    4 5 6
      5

3 4 5 6 7 1 2
  4 5 6 6 2
    5 6 6
      6

4 5 6 7 1 2 3
  5 6 6 2 2
    6 6 2
      6

5 6 7 1 2 3 4
  6 6 2 2 3
    6 2 2
      2

6 7 1 2 3 4 5
  6 2 2 3 4
    2 2 3
      2

7 1 2 3 4 5 6
  2 2 3 4 5
    2 3 4
      3

*/


Measured memory_bytes: 1536
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    a=LIST()
    ct=0
    for i in range(n):
        if (i+1)%2==1 and a[i]%2==1:
            ct+=1
    print(ct)
if __name__ == '__main__':
    do()

Measured memory_bytes: 9068
#include <iostream>

using namespace std;

long long int com2(long long int n){
  if(n<2)
    return 0;
  else{
    long long int ans = n*(n-1);
    return ans/2;
  }
}


int main(void){
  long long int N;
  cin >> N;
  long long int A[N];
  long long int i;
  for(i=0; i<N; i++)
    cin >> A[i];

  long long int count[N]={0};
  for(i=0; i<N; i++)
    count[ A[i]-1 ]++;

  long long int sum = 0, copy_sum;

  for(i=0; i<N; i++)
    sum += com2(count[ i ]);

  for(i=0; i<N; i++){
    copy_sum = sum;
    copy_sum -= com2(count[ A[i]-1 ]);
    copy_sum += com2(count[ A[i]-1 ]-1);
    cout << copy_sum << endl;
  }
  
  
  return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n,i,m,a[101];
	cin >> n;
	for(i=0;i<n;i++) {
		cin >> a[i];
	}
	sort(a,a+n);
	m=1;
	for(i=1;i<n;i++)	{
		if(a[i]!=a[i-1])
			m++;
	}
	cout << m << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define for_p(i, a, b) for(int i = a; i < b; i++)
#define for_m(i, a, b) for(int i = a - 1; i >= b; i--)

//a = s1.size();
//vector<string> s1;
//string s2 = accumulate( s1.begin(), s1.end(), string() );

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0;
  int i = 0, j = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int  a2[512], a3[1024];
  char  s2[200000], s3[200000];
  
  std::string s1 = "";
  
  cin >> s1;
  a = s1.length();
  
  for(i = 1; i <= a; i++){
    if(i % 2 == 0){
      if(s1[i - 1] == 'L' || s1[i - 1] == 'U' || s1[i - 1] == 'D'){
        c++;
       }
      else{
        b++;
      }
    }else{
        if(s1[i - 1] == 'R' || s1[i - 1] == 'U' || s1[i - 1] == 'D'){
          c++;
        }else{
          b++;
        }
      }
    }
  
    if(b == 0){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
        
  










Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ri register int
#define forn(i, n) for(int i = 1; i <= (n); i++)
typedef long long ll;
using namespace std;
/* Template_In_Programming_Contest */

void rd(int& u) {scanf("%d", &u);}
void rd2(int& u, int& v) {scanf("%d%d", &u, &v);}
void rd3(int& u, int& v, int& w) {scanf("%d%d%d", &u, &v, &w);}
void ptn(int u) {printf("%d\n", u);}
void pte(int u) {printf("%d ", u);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int , int> pii;
typedef pair <ll , ll> pll;
typedef vector <int> vi;
const int N = 2000 + 5; 
int n, a[N];
int po[N];
int pre[N];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int x; rd(x); a[i] = x; ++po[x];
	}
	
	for(int i = 1; i <= 2000; i++)	pre[i] = pre[i - 1] + po[i];
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			int l = max(a[i] - a[j], a[j] - a[i]) + 1, r = (a[i] + a[j]) - 1;
			if(l <= r && l >= 0) {
				int sel = pre[r] - pre[l - 1];
				if(a[i] >= l && a[i] <= r) --sel;
				if(a[j] >= l && a[j] <= r) --sel;
				ans += sel;
			}
		}
	}
	cout << ans / 3 << endl;
	return 0;
}



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

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

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

    ll N,K; cin >> N >> K;

    ll ans = 1;
    ll sum = 1;
    N--;

    while(true){
        if(N*K < sum) break;
        ll tmp = 0;
        if(sum%K == 0) tmp = sum/K;
        else tmp = (sum/K)+1;
        sum += tmp;
        ans++;
        N -= tmp;
    }

    cout << ans << endl;

    return 0;

}


Measured memory_bytes: 3176
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toLong() }.sorted()

    val sums = mutableListOf<Long>()
    aa.forEachIndexed { idx, a ->
        if (idx > 0) {
            sums.add(sums[idx-1] + a)
        } else {
            sums.add(a)
        }
    }

    var idx = 0
    for (i in 0 until n-1) {
        if (sums[i] * 2L < aa[i+1]) idx = i+1
    }

    println(n-idx)
}

Measured memory_bytes: 59704
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

const int N = 3e5 + 10;
const int MOD = 1e9 + 7;
const int64_t INF = 5e18;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int64_t ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i * j > n) {
                break;
            }
            int x = i * j;
            int need = n - x;
            if (need) ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <iomanip>
using namespace std;

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

int main() {
  int n, a[100100];
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  int gcdbef[100100], gcdaft[100100];
  gcdbef[2] = a[1];
  gcdaft[n-1] = a[n];

  for (int i = 3; i <= n; i++) {
    gcdbef[i] = gcd(gcdbef[i-1], a[i-1]);
  }
  for (int i = n-2; i >= 1; i--) {
    gcdaft[i] = gcd(gcdaft[i+1], a[i+1]);
  }
  int ans[100100];
  for (int i = 2; i <= n-1; i++) {
    ans[i] = gcd(gcdbef[i],gcdaft[i]);
  }
  ans[1] = gcdaft[1];
  ans[n] = gcdbef[n];

  int m = 0;
  for (int i = 1; i<=n; i++) {
    m = max(m, ans[i]);
  }

  cout << m << endl;
}


Measured memory_bytes: 1792
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    println(getAns(n))
}

fun getAns(num:Int):Int {
    var ret = 1
    for(i in (2..num)) {
        var tmp = i*i
        while (tmp <= num) {
            ret = Math.max(ret, tmp)
            tmp *= i
        }
    }
    return ret
}


Measured memory_bytes: 34568