akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5010;
const int MOD=1e9+7;
int n;
int h[N],tot;
struct Edge{
	int v,next;
}e[N*2];
int g[N];
int size[N];
int f[N][N][2];
void addEdge(int u,int v){
	e[++tot]=(Edge){v,h[u]}; h[u]=tot;
	e[++tot]=(Edge){u,h[v]}; h[v]=tot;
}
void readData(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		addEdge(u,v);
	}
}
void init(){
	g[0]=1;
	for(int i=2;i<=n;i+=2)
		g[i]=1ll*g[i-2]*(i-1)%MOD;
}
void dp_dfs(int u,int fa){
	size[u]=1;
	f[u][1][0]=1;
	static ll c[N][2];
	for(int I=h[u],v;I;I=e[I].next)
		if((v=e[I].v)!=fa){
			dp_dfs(v,u);
			for(int i=1;i<=size[u]+size[v];i++) c[i][0]=c[i][1]=0;
			for(int i=1;i<=size[u];i++)
				for(int j=1;j<=size[v];j++)
					for(int a=0;a<2;a++)
						for(int b=0;b<2;b++){
							static int t;
							t=1ll*f[u][i][a]*f[v][j][b]%MOD;
							c[i+j][a^b]+=t;
							if(!(j&1))
								c[i][a^b^1]+=1ll*t*g[j]%MOD;
						}
			size[u]+=size[v];
			for(int i=1;i<=size[u];i++){
				f[u][i][0]=c[i][0]%MOD;
				f[u][i][1]=c[i][1]%MOD;
			}
		}
}
int solve(){
	int sum[2]={0,0};
	for(int i=0;i<=n;i+=2)
		for(int j=0;j<2;j++)
			(sum[j]+=1ll*f[1][i][j]*g[i]%MOD)%=MOD;
	int res=(sum[0]-sum[1])%MOD;
	return res<0?res+MOD:res;
}
int main(){
	readData();
	init();
	dp_dfs(1,0);
	printf("%d\n",solve());
	return 0;
}


Measured memory_bytes: 195072
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a,b=0,c,d,e,f,i,j=0,k,l;
    scanf("%lld",&a);
    c=(a*(a+1))/2;
    for(i=1; i<=a; i++)
    {
        if(i%3==0 || i%5==0)
        {
            b+=i;
        }
    }
    printf("%lld\n",abs(b-c));
    return 0;
}


Measured memory_bytes: 3832
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n,m,x;
	int ans=0;
	cin >>n>>m>>x;
	vector<int>toll(n+2,0);
	int bef;
	rep(i,m){
		cin>>bef;
		toll[bef]++;
	}
	rep(i,n+1){
		toll[i+1]+=toll[i];
//		clog<<toll[i]<<" ";
	}
	cout<<min(toll[x]-toll[0] ,toll[n]-toll[x])<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#define maxn 100010
#define ll long long

struct node{int x,y,next;};
node e[4*maxn];
int first[2*maxn];
void buildroad(int x,int y)
{
	static int len=0;
	e[++len]=(node){x,y,first[x]};
	first[x]=len;
}
int n,m=0;
bool v[maxn*2],vis[maxn*2];//两个都是用来标记某个点是否到过的
void dfs_getm(int x)
{
	if(x>maxn-10)m++;//统计该联通块内y坐标的点的数量
	v[x]=true;
	for(int i=first[x];i;i=e[i].next)
	if(!v[e[i].y])dfs_getm(e[i].y);
}
ll ans=0;
void dfs_collectans(int x)
{
	if(x<=maxn-10)//如果是x坐标的点，就统计答案
	{
		ans+=(ll)m;
		for(int i=first[x];i;i=e[i].next)
		ans--;
	}
	vis[x]=true;
	for(int i=first[x];i;i=e[i].next)
	if(!vis[e[i].y])dfs_collectans(e[i].y);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		buildroad(x,y+maxn-10);//记得是无向边
		buildroad(y+maxn-10,x);
	}
	for(int i=1;i<=maxn-10;i++)
	{
		if(first[i]==0||v[i])continue;
		m=0;
		dfs_getm(i);
		dfs_collectans(i);
	}
	printf("%lld",ans);
}


Measured memory_bytes: 5248
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Contest
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            

            //出力
            Console.WriteLine(N*N*N);
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13140
def prim():
    visited = [0]*n
    d = [float("inf")]*n
    p = [-1]*n
    
    d[0] = 0

    while True:
        mincost = float("inf")
        for i in range(n):
            if visited[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == float("inf"):
            break

        visited[u] = 2

        for v in range(n):
            if visited[v] != 2 and M[u][v] != float("inf"):
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    visited[v] = 1
                
    ans = 0
    for i,j in enumerate(p[1:], start=1):
        ans += M[i][j]
        
    return ans


n = int(input())
M = []

for _ in range(n):
    M.append([x if x != -1 else float("inf") for x in map(int, input().split())])


print(prim())


Measured memory_bytes: 5956
#include <stdio.h>
#include <string.h>
 
int main(void)
{
  char A[200];
  int h,i,j,m,n;
  char t;
 
  scanf("%s",A);
  n=strlen(A);
  while (A[0]!='-'){
    scanf("%d",&m);
    for (i=0;i<m;i++){
      scanf("%d",&h);
      while(h-->0){
        t=A[0];
        for (j=1;j<n;j++){
          A[j-1]=A[j];
        }
        A[n-1]=t;
      }
    }
 
    for (i=0;i<n;i++)
      printf("%c",A[i]);
    printf("\n");
    scanf("%s",A);
    n=strlen(A);
  }
 
  return 0;
}


Measured memory_bytes: 2028
import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
    public static final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    public static final PrintStream out = System.out;

    public static void main(String[] args) {
        int K = in.nextInt();
        int X = in.nextInt();

        for (int i = Math.max(-1000000, X - K + 1); i <= Math.min(X + K - 1, 1000000); i++) {
            out.print(i);
            out.print(" ");
        }
    }
}


Measured memory_bytes: 21844
class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(input())
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
left[0] = 0
for i in range(1, k):
    left[i] += left[i-1]

ans = base*P.fac[k]
for i in range(1, n-1):
    tmp = x[i+1]-x[i]
    ans += tmp*left[i]
    ans %= mod
print(ans)



Measured memory_bytes: 76568
#include <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

typedef long long ll;

int main() {
  int tr, n;
  while (true) {
    cin >> tr >> n;
    if (tr == 0 && n == 0) break;
    double r = tr;

    int bias = 20;
    int x[41];
    memset(x, 0, sizeof(x));
    for (int i = 0; i < n; i++) {
      int xl, xr, h;
      cin >> xl >> xr >> h;
      xl += bias;
      xr += bias;
      for (int j = xl; j < xr; j++) {
	x[j] = max(x[j], h);
      }
    }

    double ans = 1000;
    for (int i = -r+1; i < 0; i++) {
      ans = min(ans, x[i+bias-1]-sqrt(r*r-i*i)+r);
    }
    ans = min(ans, x[bias-1]-sqrt(r*r)+r);
    for (int i = 0; i <= r-1; i++) {
      ans = min(ans, x[i+bias]-sqrt(r*r-i*i)+r);
    }

    printf("%.5f\n", ans);
  }
}

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

int main(void){
    int i, count=0;
    char str[3];
    scanf("%s", str);
    if ((strcmp(str, "AAA"))==0 || strcmp(str,"BBB")==0){
        printf("No");
    }
    else{
        printf("Yes");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    string S;
    cin >> S;
    map<char,int> m;
    rep(i,S.size()){
        m[S[i]]++;
    }
    int A=m['a'];
    int B=m['b'];
    int C=m['c'];
    int x=(A+B+C)/3;
    if(A-x<=1 && 0<=A-x && B-x<=1 && 0<=B-x && 0<=C-x && C-x<=1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    



}


Measured memory_bytes: 512
import java.util.Scanner;

public final class Main {
        public static void main(String[] args) {
                Scanner s = new Scanner(System.in);
                int N = s.nextInt();
                String S = s.next();

                int x = 0, max = 0;

                for (int i=0; i<N; i++) {
                        char c = S.charAt(i);
                        if (c == 'I') x++;
                        if (c == 'D') x--;

                        if (x > max) max = x;
                }
                if (x > max) max = x;

                System.out.println(max);

        }       
}



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

using namespace std;
using ll = long long;

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_V(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_M(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}

int main() {
    int N, X;
    cin>>N>>X;
    V<int> L(N);
    for (int i = 0; i < N; ++i) {
        cin>>L[i];
    }

    int D = 0, ans = 1;
    for (int i = 0; i < N; ++i) {
        D+=L[i];
        if(D<=X)ans++;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(void){
    ll l,r,ans = 2020,tmp;
    cin >> l >> r;
    if(r-l >= 2018){
        cout << 0 << endl;
        return 0;
    }
    for(ll i = l;i < r;i++){
        for(ll j = i+1;j <= r;j++){
            tmp = i*j % 2019;
            ans = min(ans,tmp);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cin.tie(0);
	cout.tie(0);
	bool out = false;
	long long int a,b,v,w,t;
	cin>>a>>v>>b>>w>>t;
	if(a<b && a+v*t>=b+w*t)
    {
     	out =true;
    }
    else if(a>b && a-v*t<=b-w*t)
    {
		out =true;
    }
	if(out)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
using namespace std;
 
int main() {
  ll N;
  cin >> N;
  ll A, B;
  vector<pair<ll, ll>> BA;
  for(ll i = 0; i < N; i++) {
    cin >> A >> B;
    BA.push_back(make_pair(B, A));
  }
  
  sort(BA.begin(), BA.end());
  
  ll limit = BA.at(N - 1).first;
  
  for(ll i = 0; i < N; i++) {
    limit -= BA.at(N - i - 1).second;
    if(i != N - 1) {
      if(limit>= BA.at(N - i - 2).first) limit = BA.at(N - i - 2).first;
    }
  }
  
  if(limit >= 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 6384
/* AtCoder Grand Contest 019. Problem B, by Abreto<m@abreto.net>. */
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

int main(void)
{
    ll cnt[26] = {0};
    int ch = 0;
    ll tot = 0;
    ll ans = 0;
    while( EOF != (ch = getchar()) )
    {
        if(ch < 'a' || ch > 'z') break;
        cnt[ch - 'a']++;
        tot++;
    }
    for(ch = 0;ch < 26;++ch)
    {
        ans += cnt[ch] * (tot - cnt[ch]);
    }
    ans>>=1;
    ans++;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define EPS 1e-10
#define INF 1000000000
#define mp make_pair
#define pb push_back

typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int,int> pii;
typedef long long ll;

int calcPow(int b, int e) {
  int rep = 1;
  for (int i = 0; i < e; i++) {
    rep *= b;
  }
  return rep;
}

void solve(vb dir) {
  int numerator = 0,
      dennominator = calcPow(2, dir.size() - 1);
  if (!dir[dir.size() - 1]) {
    numerator = 90 * calcPow(2, dir.size() - 1);
  }
  for (int i = 0; i < dir.size() - 1; i++) {
    if (dir[i]) {
      numerator -= 90 * calcPow(2, i);
    } else {
      numerator += 90 * calcPow(2, i);
    }
  }

  while (dennominator > 1) {
    if (numerator % 2 == 0) {
      numerator /= 2;
      dennominator /= 2;
    } else {
      break;
    }
  }
  if (dennominator == 1) {
    cout << numerator << endl;
  } else {
    cout << numerator << "/" << dennominator << endl;
  }
}

int main() {
  while (1) {
    string str;
    cin >> str;
    if (str == "#") {
      break;
    }
    vb dir;
    for (int i = 0; i < str.size(); i++) {
      if (str.substr(i, 5) == "north") {
        dir.pb(true);
      } else if (str.substr(i, 4) == "west") {
        dir.pb(false);
      }
    }
    solve(dir);
  }
}

Measured memory_bytes: 1204
from sys import stdin

num_blue = stdin.readline().rstrip()
word_blue = []

for i in range(int(num_blue)) :
    word_blue.append(stdin.readline().rstrip())


num_red = stdin.readline().rstrip()
word_red = []

for i in range(int(num_red)) :
    word_red.append(stdin.readline().rstrip())

counter_max = 0

for i in range(int(num_blue)):
   counter = word_blue.count(word_blue[i]) - word_red.count(word_blue[i])
   if counter > counter_max:
       counter_max = counter
   
print(counter_max)

Measured memory_bytes: 3064
#include<stdio.h>

int main(void){

	int a,b,i,sum;
	
	
	while(scanf("%d %d",&a,&b)!=EOF){
		
	
		sum=a+b;
	
		i=1;
		while(sum>9){
			sum=sum/10;
			i++;
		}

		printf("%d\n",i);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const ll MOD = 998244353;

// ax + by = gcd(a, b) となるような (x, y) を求める
// 多くの場合 a と b は互いに素として ax + by = 1 となる (x, y) を求める
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x); // 再帰的に解く
    y -= a / b * x;
    return d;
}

// 負の数にも対応した mod (a = -11 とかでも OK) 
inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}

ll f[1000001] = {};
ll lcmsum[1000001] = {};
int main() {
    ll n;
    cin >> n;
    
    rep(i,n){
        int a; cin >> a;
        f[a]++;
    }

    ll ans = 0;

    
    for(ll i = 1000000; i > 0; i--){
        ll tmpsum = 0;
        ll j = i;
        while(j <= 1000000){
            lcmsum[i] += tmpsum * j % MOD * f[j] % MOD + j * j % MOD * f[j] % MOD * (f[j] - 1) % MOD * modinv(2,MOD) % MOD;
            lcmsum[i] %= MOD;
            tmpsum = (tmpsum + j * f[j]) % MOD;
            if(j > i){
                lcmsum[i] += MOD - lcmsum[j];
                lcmsum[i] %= MOD;
            }
            j += i;
        }

        // lcmsum[i] = lcmsum[i] * modinv(i,MOD) % MOD;
        ans += lcmsum[i] * modinv(i,MOD) % MOD;
        ans %= MOD;
    }

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




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

int main() {
  
  int A, B, X;
  cin >> A >> B >> X;
  if (A <= X && A+B >= X) {
    cout << "YES" << endl;    
  }
  else {
    cout << "NO" << endl;   
  }
  


return 0;
}

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

int main()
{
	int a, b, c, j=1;
	cin >> a >> b >> c;
	int d[c+1];
	int e=min(a, b);
	for(int i=e; i>=1; i--)
	{
		if(a%i==0&&b%i==0)
		{
			d[j]=i;
			j++;
			
		}
			
	}
	cout << d[c] << endl;
	
	return 0;
}

Measured memory_bytes: 256
n = int(input())
dp = []
ans = 0
for i in range(9):
  A = [0]*9
  dp.append(A)
for i in range(1,n+1):
  st = str(i)
  if len(st) == 1:
    dp[i-1][i-1] += 1
  else:
    top = int(st[0])
    tale = int(st[len(st)-1])
    if tale != 0:
      dp[top-1][tale-1] += 1
for i in range(9):
  for j in range(i,9):
    if i != j:
      ans += dp[i][j]*dp[j][i]*2
    else:
      ans += dp[i][i]**2
print(ans)

Measured memory_bytes: 3064
//#define _GLIBCXX_DEBUG

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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
bool chmin(T &a,T b){if(a>b){a=b;return true;}else return false;}
template<typename T>
bool chmax(T &a,T b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}  
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,m;cin>>n>>m;
  vector<ll>a(n);
  rep(i,0,n)cin>>a[i];
  ll sum=0;
  rep(i,0,n)sum+=a[i];
  rep(i,0,n)if(a[i]*4*m>=sum)res++;
  ans1(res>=m);
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>
#include <fstream>
#include <ctime>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

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

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

template <class T>
std::vector<T> enum_div(T n) {
    std::vector<T> ret;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

bool isPrime(ll num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;


    for (ll i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
};


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

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

template<class T>
bool is_integer(T x) {
    return std::floor(x) == x;
}

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    vector<int> d(n);
    cin >> d;

    ll ans = 0;
    REP(i, n) {
        FOR(j, i + 1, n) {
            ans += d[i] * d[j];
        }
    }

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


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>

using namespace std;

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

  int n;
  cin >> n;
  string s[n];
  
  int i,j;
  for(i=0; i<n; ++i){
    cin >> s[i];
  }
  int res = 0;
  int has_ab = 0;
  int last_a = 0;
  int init_b = 0;
  int b_a = 0;

  for(i=0; i<n; ++i){
    string str = s[i];
    int size = str.size();
    if(str[0] == 'B'){
      if(str[size-1] == 'A'){
	++b_a; 
      }
      ++init_b;
    }
    if(str[size-1] == 'A'){
      ++last_a;
    }
    for(j=0; j<size-1; j++){
      if(str[j] == 'A' && str[j+1] == 'B') ++has_ab;
    }
  }
  
  int con = 0;
  if((init_b == b_a)&&(last_a == b_a)&&(b_a != 0)){
    con = b_a - 1;
  }else{
    con = min(last_a, init_b);
  }
  
  // printf("init_b = %d, last_a = %d, b_a = %d, has_ab = %d\n",init_b, last_a, b_a, has_ab);

  res = has_ab + con;
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
constexpr int tv[]={-3,-1,1,3};
constexpr int p10[]={100000000,10000000,1000000,100000,10000,1000,100,10,1};
constexpr int fact[]={40320,5040,720,120,24,6,2,1};

int my_hash(int f){
    vector<int> v={0,1,2,3,4,5,6,7,8};
    int ret=0;
    rep(i,8){
        auto itr=lower_bound(v.begin(),v.end(),f%10);
        ret+=fact[i]*(itr-v.begin());
        v.erase(itr);
        f/=10;
    }
    return ret;
}


int main(){
    
    int h,v;
    string a="123456789",b="123456789";
    using data=pair<int,int>;
    
    while(cin>>h>>v, h or v){
        vector<int> hm(362880,-10000000);
        int tc[]={v,h,h,v};
        rep(i,9)cin>>a[i];
        rep(i,9)cin>>b[i];
        int sa=stoi("1"+a)-1000000000,sb=stoi("1"+b)-1000000000;

        priority_queue<data> q;
        q.emplace(0,sa);
        
        while(1){
            int cost=q.top().fs;
            int board=q.top().sc;
            if(board==sb){
                cout<<-cost<<endl;
                break;
            }
            q.pop();
            int index=to_string(board).find('0');
            if(index==-1)index=0;
            rep(i,4){
                int fixed=(index+tv[i]+9)%9;
                int next=board;
                int fx=board/p10[fixed]%10;
                next=next+(p10[index]-p10[fixed]) * fx;
                int nc=cost-tc[i];
                int hval=my_hash(next);
                if(hm[hval]<nc){
                    q.emplace(nc, next);
                    hm[hval]=nc;
                }
            }
        }
    }
}



Measured memory_bytes: 7384
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;

void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const ll MAXN = 1e6 + 10;
const ll N = 4000 + 10;
const ll MN = 200 + 10;
const ll mod = 1e6;

ll a[3][MAXN] , dp[3][MAXN];

ll solve(int n, int t)
{
	if(n < 0)
		return 0;
	if(dp[t][n] != -1)
		return dp[t][n];
	for (int i = 0; i < 3; i++)
	{
		if(i != t)
			dp[t][n] = max(solve(n - 1, i) + a[t][n], dp[t][n]);
	}
	return dp[t][n];
}

int main()
{
	faster();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
			dp[j][i] = -1;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
			cin >> a[j][i];
	}
	cout << max(solve(n - 1, 0) , max(solve(n - 1, 1) , solve(n - 1, 2)));
}

Measured memory_bytes: 21632
# n: 数列の項数　m: 数列の和
# d=公約数とすると、数列は全項がdの倍数である
# よって数列の和もdの倍数である
# ゆえに、dはmの約数である
n, m = map(int, input().split())

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


d = divisor(m)
ans = 0
for i in d:
    # i: mの約数。数列の公約数でもある。
    # 公約数 * nが、mを超えない範囲で最大の公約数を求める
    if i * n <= m:
        ans = max(i, ans)

print(ans)

Measured memory_bytes: 38640
#include <stdio.h>
int main(){
  int n, i, j, k, l, a, A[101][101];
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      A[i][j] = 0;
    }
  }
  for(i=1;i<=n;i++){
    scanf("%d",&k);
    scanf("%d",&a);
    for(j=1;j<=a;j++){
      scanf("%d",&l);
      A[k][l]=1;
    }
  }
  for(i=1;i<=n;i++){
    printf("%d",A[i][1]);
    for(j=2;j<=n;j++){
      printf(" %d",A[i][j]);
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2052
#include<bits/stdc++.h>
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define int long long
#define mp make_pair
#define fr(i,a,b) for(i=a;i<b;i++)
#define mod 1000000007
#define FILEIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;

signed main()
{
	//FILEIO
 	//start_routine
	int n;
	cin>>n;
	int i;
	bool ans = 0;
	fr(i,1,n + 1)
	{
		int x;
		cin>>x;
		if(x&1) ans =1;
	}
	ans? cout<<"first":cout<<"second";
	//end_routine
}


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

using namespace std;
using ll = long long;

#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define REP(i,n) FOR(i, 0, n)
#define FORD(i,a,n) for(int i=(a); i>=(n); i--)
#define REPD(i,n) FOR(i, n, 0)

#define ALL(o) (o).begin(), (o).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T, vector<T>, greater<T> >;


map<int, ll> mp;

void solve(long long N, long long Q, std::vector<long long> B, std::vector<long long> C, ll sum){
	REP(i,Q) {
		sum += (C[i] - B[i]) * mp[B[i]];
		mp[C[i]] += mp[B[i]];
		mp[B[i]] = 0;
		cout << sum << endl;
	}
}

int main(){
	mp = map<int, ll>();
    long long N;
    scanf("%lld",&N);
	ll tmp;
	ll sum = 0;
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&tmp);
		mp[tmp]++;
		sum += tmp;
    }
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> B(Q);
    std::vector<long long> C(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&B[i]);
        scanf("%lld",&C[i]);
    }
    solve(N, Q, std::move(B), std::move(C), sum);
    return 0;
}



Measured memory_bytes: 10580
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    
    int N;
    cin >> N;
    int T,A;
    cin >> T >> A;
    int h[N];
    for(int i = 0;i < N;i++){
        cin >> h[i];
    }
    
   double diff = 1e10;
   int ans = -1;
   
   for(int i = 0;i < N;i++){
       double temp = abs(A - (T - h[i] * 0.006));
       if(temp < diff){
           diff = temp;
           ans = i + 1;
       }
   }
    cout << ans << endl;
    
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

ans = "APPROVED"
andflg = 1

for i in range(N):
    if A[i] % 2 == 0 and A[i] % 3 != 0 and A[i] % 5 != 0:
            ans = "DENIED"
            break

print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n,sum;
    cin>>n>>sum;
    int mi=inf;
    rep(i,n){
        int x;
        cin>>x;
        mi=min(x,mi);
        sum-=x;
    }
    cout<<sum/mi+n<<endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby
input = gets.chomp.split(" ")

n = input[0].to_i # even 
m = input[1].to_i # odd

nn = if(n > 1)
    n * (n-1)
else
    0
end

mm = if(m > 1)
    m*(m-1)
else
    0
end


result = (nn+mm)/2
puts result

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define test int t; cin >> t; while (t--)
#define fast ios::sync_with_stdio(NULL); cin.tie(NULL)
#define mod 1000000007
#define endl "\n"
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define ll long long
typedef vector<ll> vecll;
typedef vector<int> veci;
typedef vector<char> vecc;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
#define time 1.0 * clock() / CLOCKS_PER_SEC

int main(){
    fast;
    #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    #endif
    ll n,k,ans=0;
    cin>>n>>k;
    while(n!=0){
        n/=k;
        ++ans;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()
  if M == N-1:
    print(0); exit()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(y)
    if x == y: return
    if self.rank[x] < self.rank[y]: self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def root(self, x):
    if self.par[x] == -1: return x
    else: self.par[x] = self.root(self.par[x]); return self.par[x]
  def same(self, x, y): return self.root(x) == self.root(y)

main()

Measured memory_bytes: 109464
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define zero_pad(num) setfill('0') << std::right << setw(num)
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    int A,B,C,D,E,F;cin>>A>>B>>C>>D>>E>>F;
    double ansper=0;
    int answs=0;
    int anss=0;
    REP(w,31){
        REP(x,31){
            REP(y,F/C+1){
                REP(z,F/D+1){
                    double wsum=100*(A*w+B*x);
                    double ssum=C*y+D*z;
                    if(F>=wsum+ssum){
                        double nowp=100*ssum/(wsum+ssum);
                        if(nowp>ansper&&E*wsum>=ssum*100){
                            ansper=nowp;
                            answs=wsum+ssum;
                            anss=ssum;
                        }
                    }
                }
            }
        }
    }
    if(ansper==0)answs=100*A;
    cout<<answs<<" "<<anss<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
 
    int A, B, K;
    cin >> A >> B >> K;
    vector<int> N;
    
    for(int i = 1; i <= max(A,B); i++){
        if(A%i == 0 && B%i ==0){
            N.push_back(i);
        }
    }
    
    sort(N.rbegin(), N.rend());
    
    cout << N[K-1] << endl;
    
}


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

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

  int h,a; cin >> h >> a;

  int cnt = 0;

  while(h > 0){
    h -= a;
    cnt++;
  }
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <list>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define F first
#define S second

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


main(){
  int n,r;
  while(cin>>n>>r){
    deque<int> Q;
    rep(i,n)Q.pb(i);

    rep(i,r){
      int c;
      cin>>c;

      deque<int> A,B,C;

      int qs=(Q.size())/2;
      rep(j,qs){
	if(Q.empty())break;
	int t=Q.front();Q.pop_front();
	B.pb(t);
      }

      while(!Q.empty()){
	int t=Q.front();Q.pop_front();
	A.pb(t);
      }


      while(!A.empty() || !B.empty()){
	
	for(int j=0;j<c && !A.empty();j++){
	  int t=A.front();A.pop_front();
	  C.pb(t);
	}

	for(int j=0;j<c && !B.empty();j++){
	  int t=B.front();B.pop_front();
	  C.pb(t);
	}
      }
      Q=C;
    }
    int ans;
    while(!Q.empty()){
      ans=Q.front();
      Q.pop_front();
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();
		
		boolean[]ab = check(a,b);
		boolean[]ac = check(a,c);
		boolean[]ba = check(b,a);
		boolean[]bc = check(b,c);
		boolean[]ca = check(c,a);
		boolean[]cb = check(c,b);
		
		int ans = a.length()+b.length()+c.length();
		int m = Math.max(a.length(), Math.max(b.length(), c.length()));
		
		for (int i=0;i<=m;i++) {
			for (int j=0;j<=m;j++) {

				ans=Math.min(ans, solve(a,b,c,ab,bc,ac,i,j));
				ans=Math.min(ans, solve(a,c,b,ac,cb,ab,i,j));
				ans=Math.min(ans, solve(b,a,c,ba,ac,bc,i,j));
				ans=Math.min(ans, solve(b,c,a,bc,ca,ba,i,j));
				ans=Math.min(ans, solve(c,a,b,ca,ab,cb,i,j));
				ans=Math.min(ans, solve(c,b,a,cb,ba,ca,i,j));
			}
		}
		System.out.println(ans);
	}
	
	static boolean[] check (String s, String t){
		boolean[] ans = new boolean[s.length()];
		for (int i=0;i<s.length();i++) {
			boolean tmp = true;
			for (int j=0;j<Math.min(t.length(), s.length()-i);j++) {
				tmp &= (s.charAt(i+j)==t.charAt(j) || s.charAt(i+j)== '?' || t.charAt(j) == '?');
			}
			ans[i]=tmp;
		}
		return ans;
	}
	
	static int solve(String a, String b, String c, boolean[] ab, boolean[] bc, boolean[] ac, int i, int j) {
		if ((i>=a.length() || ab[i]) && (j>=b.length() || bc[j]) && (i+j >=a.length() || ac[i+j])) {
			return Math.max(a.length(), Math.max(i+b.length(), i+j+c.length()));
		} else {
			return Integer.MAX_VALUE;
		}
	}

}




Measured memory_bytes: 25440
n,k = gets.chomp.split(" ").map(&:to_i)
if k % 2 == 1
  cnt = 0
  n.times do |i|
    x = i+1
    cnt += 1 if x % k == 0
  end
  puts cnt ** 3
else
  cnt0 = 0
  cnt1 = 0
  n.times do |i|
    x = i+1
    cnt0 += 1 if x%k == 0
    cnt1 += 1 if x%k == k/2
  end
  puts cnt0 ** 3 + cnt1 ** 3
end

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

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

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int a,b;

int main(){
  cin >> a>> b;
  if(a>8||b>8){
    cout << ":(" << endl;
    return 0;
  }
  cout << "Yay!" << endl;
}


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

int main() {
  int n,m;
  cin>>n>>m;
  if(n>m){
    ll a=0;
    ll b=1;
    for(int i=1;i<=n;i++){
      a+=b;
      b*=10;
    }
    cout<<a*m<<endl;
  }
  else{
    ll a=0;
    ll b=1;
    for(int i=1;i<=m;i++){
      a+=b;
      b*=10;
    }
    cout<<a*n<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
int main() {
    ll n, k, x, y;
    ll ans = 0;
    double s;
    cin >> n >> k >> x >> y;
    s = (double)(n*k)*0.5;
    if (x*2 == n && y*2 == k) {
        ans = 1;
    }
    cout << setprecision(10) <<  s << ' ' << ans << endl;
    return 0;
}



Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
#define pb push_back
#define mp make_pair
#define int long long

int32_t main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
     cin>>a[i];
    int br=0,counter=1;
    for(int i=0;i<n;i++)
     {
         if(a[i]==counter) counter++;
         else br++;
     }
    if(counter==1) {cout<<-1; return 0;}
    cout<<br;
   return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const Ll N=4e5+5;
int a[N],l,r,n;
int main()
{
	cin>>n;
	int l=2e5+5,r=2e5+4;
	for(int i=1;i<=n;i++)
		if(i&1)cin>>a[++r];
		else cin>>a[--l];
	if(n&1)for(int i=r;i>=l;i--)cout<<a[i]<<' ';
	else for(int i=l;i<=r;i++)cout<<a[i]<<' ';
}

Measured memory_bytes: 2944
#include <iostream>

typedef long long llong;

using namespace std;

int main () {
  llong q, h, s, d, n;
  cin >> q >> h >> s >> d >> n;

  h = min(h, 2 * q);
  s = min(s, 2 * h);
  d = min(d, 2 * s);

  cout << (n / 2) * d + (n % 2) * s << endl;
}


Measured memory_bytes: 764
import bisect as bi

n=int(input())
a=list(map(int,input().split()))
a.sort()
m=a[-1];a=a[:-1]

i=max(bi.bisect_left(a,m/2)-1,0)
j=min(i+1,n-2)

if m/2-a[i]<a[j]-m/2:
    r=a[i]
else:
    r=a[j]

print(m,r)

Measured memory_bytes: 62704
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn dfs(
    cur: usize,
    parent: usize,
    graph: &Vec<Vec<usize>>,
    used: &mut Vec<HashSet<usize>>,
    color_dict: &mut HashMap<(usize, usize), usize>,
) {
    let mut next_color = 1;
    for &to in graph[cur].iter() {
        if to == parent {
            continue;
        }
        while used[cur].contains(&next_color) || used[to].contains(&next_color) {
            next_color += 1;
        }
        used[cur].insert(next_color);
        used[to].insert(next_color);
        color_dict.insert((cur, to), next_color);
        color_dict.insert((to, cur), next_color);
        dfs(to, cur, graph, used, color_dict);
    }
}

fn main() {
    let n = read::<usize>();
    let mut graph = vec![vec![]; n];
    let mut nodes = vec![];
    for i in 0..n - 1 {
        let v = read_vec::<usize>();
        let (a, b) = (v[0] - 1, v[1] - 1);
        graph[a].push(b);
        graph[b].push(a);
        nodes.push((a, b));
    }

    let mut used = vec![HashSet::new(); n];
    let mut color_dict = HashMap::new();
    dfs(0, 0, &graph, &mut used, &mut color_dict);

    let colors = color_dict.values().max().unwrap();
    println!("{}", *colors);
    for &(a, b) in nodes.iter() {
        println!("{}", color_dict[&(a, b)]);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 76156
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(true){
            int total = 0;
            String str = sc.next();
            if(str.equals("0")){
                break;
            }
            for(int i=0;i<str.length();i++){
                total += str.charAt(i)-'0';
            }
            System.out.printf("%d\n", total);
        }
        sc.close();
    }
}



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

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

    int N;
    int sum = 0;

    cin >> N;

    if (N%2==1)
    {
        cout << 0;
        return 0;
    }

    vector<int> V(N);

    rep(i, N) cin >> V[i];

    sort(V.begin(), V.end());

    if (V[(N-1)/2] == V[(N-1)/2+1])
    {
        cout << 0;
        return 0;
    }

    for (int i = V[(N-1)/2]+1; i<=V[(N-1)/2+1]; ++i)
    {
        ++sum;
    }

    cout << sum;

    return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

const long long INF = 1LL << 60;
int N,K;
long long dp[100100];
int h[100100];

int main(){
  cin >> N >> K;
  for(int i=0;i<N;i++) dp[i]=INF;
  for(int i=0;i<N;i++) cin >> h[i];

  dp[0]=0;
  for(int i=1;i<N;i++){
    for(int j = max(0, i - K); j < i; j++){
      dp[i]=min(dp[i],dp[j]+abs(h[j]-h[i]));
    }
  }
  cout << dp[N-1] << endl;
  return 0;
}


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

int a[5000];
int dp1[5010][5010];
int dp2[5010][5010];

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

	int N, K;
	cin >> N >> K;
	for(int i = 0; i < N; i++) {
		cin >> a[i];
	}

	dp1[0][0] = 1;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < K; j++) {
			if(!dp1[i][j]) continue;
			int nj = min(j + a[i], K);
			dp1[i + 1][j] = true;
			dp1[i + 1][nj] = true;
		}
	}
	dp2[N][0] = 1;
	for(int i = N - 1; i >= 0; i--) {
		for(int j = 0; j < K; j++) {
			if(!dp2[i + 1][j]) continue;
			int nj = min(j + a[i], K);
			dp2[i][j] = true;
			dp2[i][nj] = true;
		}
	}

	int ans = N;
	for(int i = 0; i < N; i++) {
		vector<int> x;
		for(int j = 0; j < K; j++) {
			if(dp2[i + 1][j]) x.push_back(j);
		}
		for(int j = 0; j < K; j++) {
			if(!dp1[i][j]) continue;
			auto it = lower_bound(x.begin(), x.end(), max(0, K - a[i] - j));
			if(it == x.end()) continue;
			if(j + *it < K) {
				ans--;
				//cout << a[i] << endl;
				break;
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 196224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;
/*
ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		else a=a*a%MOD;
		b>>=1;
	}
	return res;
}
*/


int main()
{
	//IOS;
	string s;
	cin>>s;
	int n=SZ(s);
	REP(i,n-1){
		if(s[i]==s[i+1]){
			cout<<i+1<<' '<<i+2<<'\n';
			return 0;
		}
	}
	REP(i,n-2){
		if(s[i]==s[i+2]){
			cout<<i+1<<' '<<i+3<<'\n';
			return 0;
		}
	}
	cout<<"-1 -1\n";
	return 0;
}


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

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


int main(){
int m,d, ans=0;
cin >> m >> d;

FOR(i,4,(m+1)){
    FOR(j,22,(d+1)){
        int a = j / 10, b = j % 10;
        if(b >= 2){
            if((a * b) == i) ans++;
        }
    }
}
cout << ans << endl;
}

Measured memory_bytes: 256