akhauriyash/Code-Regression huggingface dataset:
/*  -*- coding: utf-8 -*-
 *
 * 1589.cc: Unhappy Class
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 8;
const int MAX_M = 300;
const int D = 5;
const int MAX_T = MAX_N * D;
const int MAX_L = MAX_N * D;

/* typedef */

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

/* global variables */

vpii nbrs[MAX_T + 1];
int dp[MAX_T + 1][MAX_L + 1];

/* subroutines */

inline void setmax(int &a, int b) { if (a < b) a = b; }

/* main */

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

  for (int i = 0; i < m; i++) {
    int di, ai, ki, ti;
    scanf("%d%d%d%d", &di, &ai, &ki, &ti);
    ai--;
    int si = di * n + ai;
    nbrs[si].push_back(pii(si + ki, ti));
  }

  int t = n * D;
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;

  for (int i = 0; i < t; i++)
    for (int j = 0; j <= l; j++)
      if (dp[i][j] >= 0) {
	setmax(dp[i + 1][j], dp[i][j]);

	if (j < l) {
	  vpii &nbri = nbrs[i];
	  for (vpii::iterator vit = nbri.begin(); vit != nbri.end(); vit++)
	    setmax(dp[vit->first][j + 1], dp[i][j] + vit->second);
	}
      }

  int maxd = 0;
  for (int j = 0; j <= l; j++) setmax(maxd, dp[t][j]);

  printf("%d\n", maxd);
  return 0;
}



Measured memory_bytes: 3244
using System;

namespace ALDS1_4_B_BinarySearch
{
	class Program
	{
		static void Main ( string[] args )
		{
			//input
			int arraySize = int.Parse (Console.ReadLine ());
			int[] searchArray = new int[arraySize];

			string[] inputStr = Console.ReadLine ().Split (' ');
			for (int lp = 0; lp < searchArray.Length; lp++)
			{
				searchArray[lp] = int.Parse (inputStr[lp]);
			}

			arraySize = int.Parse (Console.ReadLine ());
			int[] elementArray = new int[arraySize];

			inputStr = Console.ReadLine ().Split (' ');
			for (int lp = 0; lp < elementArray.Length; lp++)
			{
				elementArray[lp] = int.Parse (inputStr[lp]);
			}

			//process
			int count = 0;

			foreach (var item in elementArray)
			{
				bool isFind = BinarySearch (searchArray, item);

				if (isFind)
				{
					count++;
				}
			}

			Console.WriteLine (count);
		}

		static bool BinarySearch ( int[] numArray, int searchNum )
		{
			int lowerIndex = 0;
			int upperIndex = numArray.Length - 1;

			while (lowerIndex <= upperIndex) 
			{
				int middleIndex = (lowerIndex + upperIndex) / 2;
				int item = numArray[middleIndex];

				bool isFind = item == searchNum;

				if (isFind)
				{
					return true;
				}
				else
				{
					if (item < searchNum)
					{
						lowerIndex = middleIndex + 1;
					}
					else
					{
						upperIndex = middleIndex - 1;
					}
				}
			}

			return false;
		}
	}
}

Measured memory_bytes: 22108
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    ll A, B, C, K;
    cin >> A >> B >> C >> K;

    ll res = 0;
    if (K>0) 
    {
        res += min(A, K);
        K -= A;
    }
    // cout << K << endl;
    if (K>0)
        K -= B;
    // cout << K << endl;
    if (K>0)
        res -= K;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node {
  int key;
  struct _Node *next, *prev;
} Node;

Node *nil;

Node* listSearch(int key) {
  Node *cur = nil->next;
  while(cur != nil && cur->key != key) {
    cur = cur->next;
  }
  return cur;
}

void init(void) {
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(void) {
  Node *cur = nil->next;
  int isf = 0;
  while(1) {
    if(cur == nil) break;
    if(isf++>0) printf(" ");
    printf("%d",cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t) {
  if(t==nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(void) {
  deleteNode(nil->next);
}

void deleteLast(void) {
  deleteNode(nil->prev);
}

void deleteKey(int key) {
  deleteNode(listSearch(key));
}

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(void) {
  int key, n, i;
  int size = 0;
  int np = 0, nd = 0;
  char com[20];
  scanf("%d", &n);
  init();
  for(i=0;i<n;i++) {
    scanf("%s%d",com, &key);
    if (com[0] == 'i') {
      insert(key);
      np++;
      size++;
    } else if(com[0] == 'd') {
      if(strlen(com) > 6) {
        if(com[6] == 'F')
          deleteFirst();
        else if(com[6] == 'L')
          deleteLast();
      } else {
        deleteKey(key);
        nd++;
      }
      size--;
    }
  }
  printList();
  return 0;
}



Measured memory_bytes: 32948
#include<iostream>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
#define pi 3.141592653589793283462
int main(){
    int w,h,x,y,r;
    cin>>w>>h>>x>>y>>r;
    if(x>=r && x<=w-r){
        if(y>=r && y<=h-r)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 1156
import heapq
from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline

n = int(input())
#####単位元######
ide_ele = -1

#num:n以上の最小の2のべき乗
num =2**((n-1).bit_length())
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a = [int(input()) for i in range(n)]
    b = sorted(a)
    for i in range(n):
        a[i] = bisect.bisect_left(b,a[i])
    
    tank = [a[0]]
    used[a[0]] = 1
    update(a[0],a[0])
    
    for i in range(1,n):
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a[i]:
            ma = query(0,a[i])
            
            used[ma] -= 1
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
        update(a[i],a[i])

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
            used[e] -= 1
    print(res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 89436
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 1000000007;
const ll INF = 1001001001;
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; }

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    vector<vector<int>> edge;
    edge.resize(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    int ans = 0;
    rep(i,n){
        bool ok = true;
        for(int c:edge[i]){
            if(h[i]<=h[c]) ok = false;
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}

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

int main() {
  int C[3][3], A[3], B[3];

  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      cin >> C[i][j];
    }
  }

  int range = min(C[0][0], min(C[0][1], C[0][2]));
  bool ok = false;
  for (int i = 0; i <= range; ++i) {
    ok = true;
    A[0] = i;
    B[0] = C[0][0] - A[0];
    B[1] = C[0][1] - A[0];
    B[2] = C[0][2] - A[0];
    A[1] = max(C[1][0] - B[0], 0);
    A[2] = max(C[2][0] - B[0], 0);
    for (int j = 1; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        if (A[j] + B[k] != C[j][k]) {
          ok = false;
        }
      }
    }
    if (ok) break;
  }

  if (ok) cout << "Yes\n";
  else cout << "No\n";

  return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (A, B, N) = readLine()!!.split(" ").map(String::toLong)

    val n = N / B

    listOf(n * B - 1, N).map {
           ((A * it) / B - A * (it / B))
    }.max()!!.run(::println)
}

Measured memory_bytes: 38984
#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int N, sum;
	vector<int> A;
	
	cin >> N;
	
	for(int i = 0; i < N; i++){
		int t;
		cin >> t;
		A.push_back(t);
	}
	
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			sum += (A[i] * A[j]);
		}
	}
	
	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline

n_sq = {n*n for n in range(400*100+1)}

def is_gooddist(ta,tb):
	dist_sq = sum((y-z)*(y-z) for y,z in zip(ta,tb))
	return dist_sq in n_sq

def main():
	N,D=map(int,input().split())
	mX=[tuple(map(int,input().split())) for _ in [0,]*N]
	
	res = 0
	for i in range(N-1):
		tI = mX[i]
		for j in range(i+1,N):
			tJ = mX[j]
			res += is_gooddist(tI,tJ)
	print(res)

main()
	


Measured memory_bytes: 6380
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

ll r, d, x;
int main() {
	scanf("%lld %lld %lld", &r, &d, &x);
	for (int i = 0; i < 10; i++) {
		x = r * x - d;
		printf("%lld\n", x);
	}
}

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

int main(){
    int n,sum=0,x;cin>>n;x=n;
    while(x!=0){
        sum+=x%10;
        x/=10;
    }
    if(n%sum==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];
int main() {
  string s,t;
  cin>>s;
  cin>>t;
  int lens = s.length();
  int lent = t.length();

  //dp[i][j] is len lcs of 0-i-1 and 0-j-1
  //dp[i][j] = if(s[i-1]==t[j-1]) 1 + dp[i-1][j-1]
  //dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  //int dp[lens+1][lent+1] = {0};
  dp[0][0] = 0;
  for(int i =1;i<=lens;i++) {
    for(int j =1;j<=lent;j++) {
      if(s[i-1] == t[j-1]) {
        dp[i][j] = 1 + dp[i-1][j-1];
      } else {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
      }
     // printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
    }
  }
  int i = lens;
  int j = lent;
  string ans = "";
  while(i>=1 && j>=1) {
    if(s[i-1] == t[j-1]) {
      i--;
      j--;
      ans += s[i];
    } else {
      if(dp[i-1][j]>dp[i][j-1]) {
        i--;
      } else {
        j--;
      }
    }
  }
  reverse(ans.begin(),ans.end());
  //cout<<dp[lens][lent]<<endl;
  cout<<ans<<endl;

}

Measured memory_bytes: 35456
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
int MOD=1000000007;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

struct DP {
    lint dp;
    int sub;
    lint far;
    DP(lint dp=0,int sub=0,lint far=0):dp(dp),sub(sub),far(far){}
    DP operator+(const DP& a) const {
        return DP(2*(sub+a.sub)-max(far,a.far),sub+a.sub,max(far,a.far));
    }
    DP addRoot(int W){
        return DP(dp,sub+1,far+W);
    }
};
 
vector<DP> dp[MAX_N];
DP ans[MAX_N];
vector<int> to[MAX_N];
map<pint,int> edleng;

void addedge(int a,int b,int w=1){
    to[a].push_back(b);
    to[b].push_back(a);
    edleng[pint(a,b)]=w;
    edleng[pint(b,a)]=w;
}
 
DP rerootdfs(int v, int p=-1) {
    DP dpSum;
    dp[v] = vector<DP>(to[v].size());
    rep(i,to[v].size()) {
        int u = to[v][i];
        int W=edleng[pint(v,u)];
        if (u == p) continue;
        dp[v][i] = rerootdfs(u,v);
        dpSum = dpSum + dp[v][i];
        }
    return dpSum.addRoot(edleng[pint(v,p)]);
}
void rerootbfs(int v, const DP& dpP=DP(), int p=-1) {
    int deg = to[v].size();
    rep(i,deg) if (to[v][i] == p) dp[v][i] = dpP;
 
    vector<DP> dpLeft(deg+1);
    rep(i,deg) dpLeft[i+1] = dpLeft[i] + dp[v][i];
  
    vector<DP> dpRight(deg+1);
    for (int i = deg-1; i >= 0; --i) dpRight[i] = dpRight[i+1] + dp[v][i];
  
    ans[v] = dpLeft[deg].addRoot(edleng[pint(v,v)]);
 
    rep(i,deg) {
        int u = to[v][i];
        if (u == p) continue;
        DP d = dpLeft[i] + dpRight[i+1];
        rerootbfs(u, d.addRoot(edleng[pint(u,v)]), v);
    }
}

void reroot(){
    rerootdfs(0);
    rerootbfs(0);
}

//デフォルトで部分木のサイズ、最遠距離がついてくる


int main(void){
    int N;
    cin >> N;
    rep(i,N-1){
        int a,b;
        cin >> a >> b;
        a--,b--;
        addedge(a,b);
    }
    reroot();
    rep(i,N) cout << ans[i].dp << endl;
}


Measured memory_bytes: 82880
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

#define rep(i, n) for(int i=0;i<(int)(n);i++)

using namespace std;

int X;

int main() {
    cin >> X;
    string s = to_string(X);
    int fx = 0;
    for (int i = 0; i < s.length(); i++) {
        fx += (int) (s[i] - '0');
    }
    if (X % fx == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pow3(x) ((x)*(x)*(x))
using namespace std;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    long long ans=0;
    ans=(long long)(n/k)*(n/k)*(n/k);
    if((k&1)==0)ans+=pow3((long long)(n/(k/2))/2+(n/(k/2))%2);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

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

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

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}
void judgement(int a){
  if(a){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  if(a){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.pb(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
vec primefactorization(ll N){
  ll i=2;
  vec res;
  while(i*i<=N){
    while(!(N%i)){
      res.pb(i);
      N/=i;
    }
    i++;
  }
  if(N-1)res.pb(N);
  return res;
}
int main(){
  ll i,j,N,H,W,ans;
  cin>>N;
  vec v=eratosthenes(N*2);
  For(i,N,N*2){
    if(v[i])break;
  }
  cout<<i<<endl;
  return 0;
}

Measured memory_bytes: 2176
program prob1
    implicit none
    character(1) :: a, b, c
    character(3) :: s
    read(*,*) a, b, c

    s = achar(iachar('A') + iachar(a) - iachar('a'))
    s = s(1:1) // achar(iachar('A') + iachar(b) - iachar('a'))
    s = s(1:2) // achar(iachar('A') + iachar(c) - iachar('a'))
    write(*,'(a)') s

    stop
contains
end program prob1

Measured memory_bytes: 2876
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

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

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

bool dp[2000000] = {};
int counter[2000000] = {};

int main() {
  int N, A[SIZE];


  scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    scanf("%d", A + i);
    counter[A[i]]++;
  }

  sort(A, A + N);

  int ans = 0;

  for (int i = 0; i < N; i++) {
    ans += !dp[A[i]] && counter[A[i]] <= 1;
    if (!dp[A[i]]) {
      for (int j = 1; j * A[i] < 2000000; j++) {
        dp[j * A[i]] = true;
      }
    }
  }

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

  return 0;
}


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

using namespace std;

typedef short sho;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str; 
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll; 
typedef pair<ld,ld> pld;
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pld> vpd;

#define STDIO
#define mp make_pair 
#define FF first
#define SS second
#define sz(x) (int)x.size()
#define begin(x) (x).begin() 
#define end(x) (x).end()
#define rbegin(x) (x).rbegin()
#define rend(x) (x).rend()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front 
#define pb push_back
#define pp push
#define lb lower_bound 
#define ub upper_bound

inline void checkmin(int &x, int y){x = min(x, y);}
inline void checkmax(int &x, int y){x = max(x, y);}

int n;

void dfs(vs seq,int cnt)
{
	if(cnt==n)
	{
		for(int i=0;i<sz(seq);i++)
		{
			cout<<seq[i]<<endl;
		}
		exit(0);
	}
	vs nxt;
	for(int i=0;i<sz(seq);i++)
	{
		int mx=0;
		for(int j=0;j<sz(seq[i]);j++)
		{
			checkmax(mx,seq[i][j]-'a');
		}
		for(int j=0;j<=min(25,mx+1);j++)
		{
			string tmp=seq[i];
			tmp+=(char)('a'+j);
			nxt.pb(tmp);
		}
	}
	dfs(nxt,cnt+1);
}

int main()
{
	#ifndef STDIO
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /* start code */
    cin>>n; 
    vs seq;
    seq.pb("a");
    dfs(seq,1);
    /* end code */
	return 0;
}

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

int main() {
  int n,m;
  cin >> n >> m;
  int a[m],b[m];
  for(int i=0; i<m; i++) cin >> a[i] >> b[i];
  sort(a,a+m,greater<int>());
  int ans=0;
  for(int i=0; i<m-1; i++) ans+=n-min(n,a[i]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define U [7<<15]={}
#define G ((c=A[a]+A[P[a]]+C[a])%k?c:0)+M(
typedef long long L;using namespace std;map<L,L>T U;L P U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c;char s U;L M(L f){return f?B[f]+M(f^f&-f):0;}L S(L a,L i){for(a=G i++)-M(i);i<2e5;i+=i&-i)B[i]+=a;}L D(L f){L d;for(map<L,L>::iterator I=T[f].begin();I!=T[f].end();I++)d=I->first,d-P[f]?P[d]=f,C[d]=I->second,D(d),Z[f]+=++Z[d],Z[H[f]]<Z[d]?H[f]=d:0:0;}L K(L f){return Z[a=X[f]]>Z[n=X[b]]?n=b,b=f,K(n):abs(M(O[f])-(a-n?-G O[a])-K(P[a]):M(O[b])));}main(){for(cin>>n>>k;--*Z+n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;for(D(n=0);Z[a=H[P[n]]-n?n:0];*Z=++n)for(;!O[a];S(a=H[a],O[a]=++b))X[a]=n;for(cin>>a;cin>>s>>a>>b;S(H[a],O[a]),S(a,O[a]-1))*s&2?cout<<K(a)<<endl,0:A[a]+=b;}

Measured memory_bytes: 37188
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000


//?????????????????????????§£????????¢
//??????

int main(void){
    
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        set<string> s;
        string str; cin >> str;
        for(int j = 0; j < str.size(); j++){
            string a, b, ra, rb;
            
            a = str.substr(0, j);
            b = str.substr(j);
            ra = a;
            reverse(ra.begin(), ra.end());
            rb = b;
            reverse(rb.begin(), rb.end());

            //7??????????????¨??????
            s.insert(ra + b);
            s.insert(a + rb);
            s.insert(ra + rb);
            s.insert(b + a);
            s.insert(b + ra);
            s.insert(rb + a);
            s.insert(rb + ra);
        }

        cout << s.size() << endl;
    }
    return 0;
}

Measured memory_bytes: 3192
#include <iostream>

const int MAX_SIZE = 44 + 1;

int main() {
  int f[MAX_SIZE] = {0};
  
  int n = 0;

  std::cin >> n;

  f[0] = 1;
  f[1] = 1;

  for (int i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i -2];
  }

  std::cout << f[n] << std::endl;

  
  return 0;
}

Measured memory_bytes: 1164
s = input()

ans = 0
A_count = 0

pass_flag = 0

for i in range(len(s) - 1):
    # print(ans,A_count)
    if pass_flag:
        pass_flag = 0
        continue
    if s[i] == "B" and s[i + 1] == "C":
        ans += A_count
        pass_flag = 1
    elif s[i] == "A":
        A_count += 1
    else:
        A_count = 0

print(ans)


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

char ans[15];

int main(){
  string S; cin >> S;
  int now = 0;

  for (int i = 0; i < S.length(); i++){
    if (S[i] == 'B'){
      if (now > 0) now--;
    }else{
      ans[now] = S[i];
      now++;
    }
  }

  for (int i = 0; i < now; i++) cout << ans[i];
  cout << endl;

  return 0;
}


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

using namespace __gnu_pbds;
using namespace std;


#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pii pair<int,int>
#define pf push_front
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<pii>
#define pqsmall priority_queue<int,vector<int>,greater<int> >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define spitr set<pii>:: iterator
#define mitr map<int,int>:: iterator

int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}


typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;


#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl


int32_t main()
{
	fast;
	int n;cin>>n;
	int chk=n;
	vi v;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			v.pb(i);
			if(n/i!=i)
				v.pb(n/i);
		}
	}
	v.pb(n);

	int ans=0;
	for(int i=0;i<v.size();i++)
	{
		int tmp=n;
		while(tmp%v[i]==0)
			tmp/=v[i];
		if(tmp%v[i]==1)
			ans++;
	}

	n--;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ans++;
			if(n/i!=i)
				ans++;
		}
	}
	if(chk!=2)
		ans++;
	cout<<ans;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> V(N), C(N);
  for (int i = 0; i < N; i++) {
    cin >> V.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> C.at(i);
  }
  int ans = 0;
  for (int tmp = 0; tmp < (1 << N); tmp++) {
    bitset<20> s(tmp);
    int x = 0, y = 0;
    for (int i = 0; i < N; i++) {
      if (s.test(i)) {
        x += V.at(i);
        y += C.at(i);
      }
    }
    ans = max(ans, x - y);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

signed main() {
	long long n, m;
	cin >> n >> m;
	if (n > m) swap(n, m);
	if (n == 1) {
		if (m == 1) cout << 1 << endl;
		else cout << m - 2 << endl;
	}
	else {
		cout << (n - 2) * (m - 2) << endl;
	}
	return 0;
}

Measured memory_bytes: 888
A = [ list(map(int,input().split())) for _ in range(3)]
N = int(input())
b = [ int(input()) for _ in range(N)]

for ck in b:
    for i in range(3):
        for j in range(3):
            if ck == A[i][j]:
                A[i][j] = 0

if A[0][0] == 0 and A[0][1] == 0 and A[0][2] == 0:
    print('Yes')
elif A[1][0] == 0 and A[1][1] == 0 and A[1][2] == 0:
    print('Yes')
elif A[2][0] == 0 and A[2][1] == 0 and A[2][2] == 0:
    print('Yes')
elif A[0][0] == 0 and A[1][0] == 0 and A[2][0] == 0:
    print('Yes')
elif A[0][1] == 0 and A[1][1] == 0 and A[2][1] == 0:
    print('Yes')
elif A[0][2] == 0 and A[1][2] == 0 and A[2][2] == 0:
    print('Yes')
elif A[0][0] == 0 and A[1][1] == 0 and A[2][2] == 0:
    print('Yes')
elif A[0][2] == 0 and A[1][1] == 0 and A[2][0] == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
# AtCoder Beginner Contest 150 C - Count Order

import sys
import itertools

N = int(input())

P = list(map(int, sys.stdin.readline().strip().split()))
Q = list(map(int, sys.stdin.readline().strip().split()))


count = 1
a, b = 0, 0
for i in itertools.permutations([i for i in range(1, N+1)]):
    i = list(i)
    if i == P:
        a = count
    if i == Q:
        b = count
    count += 1

print(abs(a - b))


Measured memory_bytes: 3188
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i = 0; i < N; i++)
			A[i] = sc.nextInt();
		Arrays.sort(A);
		int point = 0, w = 0, h = 0;
		for(int i = N-1; i > 0; i--) {
			if(A[i] == A[i-1]) {
				w = A[i];
				point = i-2;
				break;
			}
		}
		for(int i = point; i > 0; i--) {
			if(A[i] == A[i-1]) {
				h = A[i];
				break;
			}
		}
		System.out.println((long)w*h);
	}

}

Measured memory_bytes: 49608
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)

vector<int> color(1e5+2, -1);
vector<vector<int>> V(1e5+2);
vector<P> E(1e5+2);

int side(int parent, int edge){
    return E[edge].first == parent ? E[edge].second : E[edge].first;
}

void rep(int parent, int edge){
    if (V[parent].size() == 1) return;
    int c = color[edge];
    int num = 0;
    REP(i, V[parent].size()){
        int e = V[parent][i];
        if (e != edge) {
            if (num == c) num++;
            color[e] = num;
            num++;
            rep(side(parent, e), e);
        }
    }      
    return;
}

int main() {
    int N;
    cin >> N;
    int a, b;
    REP(i, N-1) {
        cin >> a >> b;
        a--;
        b--;
        E[i].first = a;
        E[i].second = b;
        V[a].push_back(i);
        V[b].push_back(i);
    }
    int root = 0, d = 0;
    REP(i, N){
        int tmp = V[i].size();
        if (d < tmp){
            root = i;
            d = tmp;
        }
    }
    
    REP(i, d) {
        int e = V[root][i];
        color[e] = i;
        rep(side(root, e), e);
    }
    cout << d << endl;
    REP(i, N-1) cout << (color[i] + 1) << endl;


    return 0;
}


Measured memory_bytes: 10240
n = int(input())
A = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659]
lis = []
for a in A:
    if a%5 == 1:
        lis.append(a)
print(*lis[:n],sep = " ")

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

int gcd(int a,int b){
  int temp;
  while(b!=0){
    temp=a%b;
    a=b;
    b=temp;
  }
  return a;
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  bool pc=true;
  vector<bool> d(1e6+1,false);
  int x;
  for(int i=0;i<N;i++){
    if(A.at(i)==1){
      continue;
    }
    if(d.at(A.at(i))){
      pc=false;
      break;
    }
    d.at(A.at(i))=true;
    for(int j=2;j<=sqrt(A.at(i));j++){
      if(A.at(i)%j==0){
        x=A.at(i)/j;
        if(d.at(j)||d.at(x)){
          pc=false;
          break;
        }
        d.at(j)=true;
        d.at(x)=true;
      }
    }
    if(!pc){
      break;
    }
  }
  if(pc){
    cout << "pairwise coprime" << endl;
    return 0;
  }
  int g=gcd(A.at(0),A.at(1));
  for(int i=2;i<N;i++){
    g=gcd(g,A.at(i));
  }
  if(g!=1){
    cout << "not coprime" << endl;
  }else{
    cout << "setwise coprime" << endl;
  }
  return 0;
}


Measured memory_bytes: 7284
N, M = map(int, raw_input().split())

fact = [0 for _ in range(100000+1)]
fact[0] = 1
for i in xrange(1, 100000+1):
    fact[i] = (fact[i-1] * i) % (10**9 + 7)

ans = 0
if N == M:
    ans += fact[N] * fact[M]
    ans += fact[M] * fact[N]
if N == M - 1 or M == N - 1:
    ans += fact[N] * fact[M]

ans %= (10**9 + 7)
print ans


Measured memory_bytes: 7896
import java.util.*

fun main(args: Array<String>) {
	val (n, m) = readLine()!!.split(" ").map({ it -> it.toInt() })
	val graph = WeightedDirectedGraph(n)
	for (i in 1..m) {
		val (a, b, c) = readLine()!!.split(" ").map({ it -> it.toInt() })
		val e = Edge(a - 1, b - 1, (-c).toLong())
		graph.addEdge(e)
	}
	val ans = bellmanFord(0, n - 1, graph)
	if (ans == null) {
		println("inf")
	} else {
		println(-ans)
	}
}

class Edge(val from: Int, val to: Int) {
	var cost = 0L
	constructor(from: Int, to: Int, cost: Long): this(from, to) {
		this.cost = cost
	}
}

class WeightedDirectedGraph(val size: Int) {
	val edges = Array<MutableList<Edge>>(this.size) { mutableListOf() }
	fun addEdge(e: Edge) {
		this.edges[e.from].add(e)
	}
}

fun bellmanFord(src: Int, snk: Int, graph: WeightedDirectedGraph): Long? {
	val costs = LongArray(graph.size) { Long.MAX_VALUE }
	costs[src] = 0L
	for (i in 1..(graph.size - 1)) {
		for (j in 0..(graph.size - 1)) {
			if (costs[j] == Long.MAX_VALUE) {
				continue
			}
			for (e in graph.edges[j]) {
				val newCost = costs[j] + e.cost
				costs[e.to] = Math.min(newCost, costs[e.to])
			}
		}
	}
	for (i in 1..graph.size) {
		for (j in 0..(graph.size - 1)) {
			if (costs[j] == Long.MAX_VALUE) {
				continue
			}
			for (e in graph.edges[j]) {
				val newCost = costs[j] + e.cost
				if (newCost < costs[e.to]) {
					costs[e.to] = newCost
					if (e.to == snk) {
						return null
					}
				}
			}
		}
	}
	return costs[snk]
}

Measured memory_bytes: 53460
#include<iostream>
#include<string>

int main()
{
	std::string str;
	std::cin >> str;
	unsigned long long number_of_repeat = 0;
	std::cin >> number_of_repeat;
	unsigned long long number = 0;
	for (unsigned int index = 1; str.length() > index; ++index)
	{
		if (str.at(index) == str.at(index - 1))
		{
			number += 1;
			index += 1;
		}
	}
	if (1 == number_of_repeat)
	{
		std::cout << number;
		return 0;
	}
	unsigned long long count_on_repeat = 0;
	std::string str_on_repeat = str + str + str;
	for (unsigned int index = 1; str_on_repeat.length() > index; ++index)
	{
		if (str_on_repeat[index] == str_on_repeat[index - 1])
		{
			if (str.length() <= index)
			{
				count_on_repeat += 1;
			}
			index += 1;
		}
	}
	number += count_on_repeat * ((number_of_repeat - 1) / 2);
	if (0 == number_of_repeat % 2)
	{
		std::string str_on_last = str + str;
		for (unsigned int index = 1; str_on_last.length() > index; ++index)
		{
			if (str_on_last[index] == str_on_last[index - 1])
			{
				if (str.length() <= index)
				{
					number += 1;
				}
				index += 1;
			}
		}
	}
	std::cout << number;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define INF 1e8
typedef long long int ll;
const double PI = acos(-1);

using Graph = vector<vector<int>>;
int main() {
  string n;
  cin >> n;
  ll len = n.length();
  ll sum = 0;
  for (ll i = 0; i < len; i++) {
    sum += (int)(n[i] - '0');
  }

  if (sum % 9 == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 3748
class Integer
  def divisor_list
    require 'prime'

    return [] if self <= 0
    return [1] if self == 1

    prime_division.map.with_index { |(base, k), i|
      s = i.zero? ? 0 : 1
      (s..k).map { |n| base ** n }
    }.inject { |res, e| res + res.flat_map { |t| e.map { |v| t * v } } }.sort
  end
end

N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

def f(x)
  r = A.map { |a| a % x }.sort

  ruiA = Array.new(N, 0)
  ruiB = Array.new(N, 0)

  r.each_with_index do |d, i|
    ruiA[i] = ruiA[i - 1] if i > 0
    ruiB[i] = ruiB[i - 1] if i > 0

    ruiA[i] -= d
    ruiB[i] += x - d
  end

  N.times do |i|
    a = ruiA[i]
    b = ruiB[N - 1] - ruiB[i]

    next if a + b != 0
    next if b > K

    return true
  end

  false
end

sum = A.inject(:+)
ans = 1

sum.divisor_list.each do |x|
  ans = x if f(x) && ans < x
end

puts ans


Measured memory_bytes: 18680
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)

int main()
{
  int D, G;
  cin >> D >> G;

  int p[D + 1], c[D + 1];

  repd(h, 1, D + 1)
  {
    cin >> p[h] >> c[h];
  }

  int ans = 1001;
  repd(i, 1, pow(2, D) + 1)
  {
    int score = 0;
    int cnt = 0;

    rep(j, D)
    {
      if (i & 1 << j)
      {
        // j番目の問をComplete
        cnt += p[j + 1];
        score += 100 * (j + 1) * p[j + 1] + c[j + 1];
      }
    }
    // 足りない点数分の問を解く
    if (G > score)
    {
      repdm(k, D, 0)
      {
        if (i & 1 << (k - 1))
        {
          int ch;
        }
        else
        {
          int remain = ceil((float)(G - score) / (float)(100 * k));
          if (remain <= p[k])
          {
            cnt += remain;
            score += remain * 100 * k;
          }
          else
          {
            cnt += p[k];
            score += p[k] * 100 * k;
          }
        }
        if (score >= G)
          break;
      }
    }

    if (ans > cnt)
    {
      ans = cnt;
    }
  }
  cout << ans << endl;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int n, m;
    cin >> n >> m;
    int a[SIZE];
    for( int i = 0; i < SIZE; ++i ) a[i] = -1;

    for( int i = 0; i < m; ++i ) {
        int s, c;
        cin >> s >> c;
        if( s == 1 && c == 0 ) {
            if( n == 1 ) {
                if( a[1] != -1 && a[1] != 0 ) {
                    cout << -1 << endl;
                    return 0;

                }
                a[1] = 0;
                continue;
            }
            cout << -1 << endl;
            return 0;

        }
        if( a[s] != -1 && a[s] != c ) {
            cout << -1 << endl;
            return 0;

        }
        a[s] = c;

    }
    if( m == 0 && n == 1 ) {
        cout << 0 << endl;
        return 0;

    }
    for( int i = 1; i <= n; ++i ) {
        if( a[i] == -1 ) {
            if( i == 1 ) cout << 1;
            else cout << 0;

        } else {
            cout << a[i];

        }
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define get(x)((x)>=0?_A[x]:_A2[-(x)])
#define ll long long
using namespace std;
const int N=2.5e5+5;
const ll mo=23333333333333333LL;
int n;
ll Z,A,_A[N],_A2[N],Y,ans;
map<ll,int>h;
char c[N];
inline ll mult(ll x,ll y){
	Z=x*y-(ll)((long double)x*y/mo)*mo;
	return (Z<0?Z+mo:Z<mo?Z:Z-mo);
}
ll ksm(ll x,ll y){
	ll t=1;
	for(;y;y>>=1,x=mult(x,x))if(y&1)t=mult(t,x);
	return t;
}
struct P{
	int x;ll y;
	P(int _x=0,ll _y=0){x=_x;y=_y;}
	P operator+(const P &b){
		return P(x+b.x,(y+mult(get(x),b.y))%mo);
	}
}a[N];
int main(){
	scanf("%d\n%s",&n,c+1);
	A=1e6+7;
	_A[0]=1;
	fo(i,1,n)_A[i]=mult(_A[i-1],A);
	_A2[0]=1;_A2[1]=ksm(A,mo-2);
	fo(i,2,n)_A2[i]=mult(_A2[i-1],_A2[1]);
	fd(i,1,n){
		if(c[i]=='>')a[i]=P(1,0);
		if(c[i]=='<')a[i]=P(-1,0);
		if(c[i]=='+')a[i]=P(0,1);
		if(c[i]=='-')a[i]=P(0,-1);
		a[i]=a[i]+a[i+1];
	}
	Y=a[1].y;
	fd(i,1,n+1){
		ll b=mult((a[i].y-Y+mo)%mo,get(-a[i].x));
		ans+=h[b];
		b=mult(a[i].y,get(-a[i].x));
		++h[b];
	}
	cout<<ans;
}

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

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll x;
    cin>>x;
    int ans=0;
    for(ll i=0;i<10000;i++){
        for(ll j=-10000;j<10000;j++){
            if(i*i*i*i*i-j*j*j*j*j==x){
                cout<<i<<' '<<j<<endl;
                ans=1;
                break;
            }
        }
        if(ans==1){
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3560
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,i; char p[1009][1009];
void x(int i, int j){p[i][j]=94;p[i+1][j]=118;b--;}
int main(int j){
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(i=1;i<=n;)memset(p[i++]+1,46,m);
	for(i=1;i<n&&b&&m&1;i+=2)x(i,m);
	if(b&n&m>2&n>1)x(n-1,m-2);
	for(i=1;i<n;i++)for(j=1;j<=m&&b;j++)if(p[i][j]+p[i+1][j]<99)x(i,j);
	for(i=1;i<=n;i++)for(j=1;j<m&&a;j++)if(p[i][j]+p[i][j+1]<99)p[i][j]=60,p[i][j+1]=62,a--;
	puts(a|b?"NO":"YES");
	for(i=1;!a&!b&i<=n;)puts(p[i++]+1);
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll,P> V;
const ll INF=2e18;
ll N,M,K,L,A,H;
struct Edge{
    P to;
    ll cost;
};

int main(){
    while(cin>>N>>M>>L>>K>>A>>H,N!=0){
        map<P,vector<Edge> > vs;
        for(int i=0;i<L;i++){
            int tmp;
            cin>> tmp;
            for(int j=0;j<M;j++){
                Edge e={P(tmp,j+1),1};
                vs[P(tmp,j)].push_back(e);
            }
        }
        for(int i=0;i<K;i++){
            ll x,y,t;
            cin>>x>>y>>t;
            for(int j=M;j-t>=0;j--){
                Edge e={P(y,j-t),t};
                vs[P(x,j)].push_back(e);
                e.to.first=x;
                vs[P(y,j)].push_back(e);
            }
        }
        map<P,ll> minCost;
        for(ll i=0;i<N;i++){
            for(ll j=0;j<=M;j++){
                minCost[P(i,j)]=INF;
            }
        }
        minCost[P(A,M)]=0;
        priority_queue<V, vector<V> , greater<V> > pq;
        pq.push( V(0,P(A,M))  );
        while(!pq.empty()){
            P now=pq.top().second;
            ll nowCost=pq.top().first;
            pq.pop();
            if(minCost[now]<nowCost)continue;

            for(auto edge : vs[now]){
                P to=edge.to;
                ll cost=minCost[now]+edge.cost;
                if(minCost[to]>cost){
                    minCost[to]=cost;
                    pq.push(V(cost,to));
                }
            }
        }
        ll ans=INF;
        for(ll i=0;i<=M;i++){
            ans=min(ans,minCost[P(H,i)]);
        }
        if(ans==INF){
            cout<<"Help!"<<endl;
        }else{
            cout<<ans<<endl;
        }
    }
    return 0;
}


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

int main(){
	int N,M;
	cin >> N >> M;
	int A=0,B;
	int loop;
	for(loop=0;loop<M;loop++){
		cin >> B;
		A += B;
	}
	if(A<=N){
		cout << N-A << endl;
	}else{
		cout << "-1" << endl;
	}
	return 0;
}


Measured memory_bytes: 3624
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef int_fast64_t ll;

template<int N, typename T, T M>
struct ModFact {
    T fact[N+1];
    constexpr ModFact() : fact() {
        fact[0] = 1;
        for (int i=0; i<N; ++i)
            fact[i+1] = (fact[i]*(i+1))%M;
    }
};
 
ModFact<100000, ll, MOD> fact;

ll ans;
int N, M, cnt = 0;
constexpr ll th = 1LL<<45;
char S[200000];

int main() {
    scanf("%d\n", &N);
    M = N << 1;
    fread_unlocked(S, 1, M, stdin);
    ans = fact.fact[N];
    char *E = S + M, *C = S;
    while(C < E) {
		if((*C++^cnt)&1) {
            ans = ans * cnt % MOD;
            if(--cnt < 0) break;
        } else ++cnt;
	}
    printf("%lld\n", cnt == 0 ? ans % MOD : 0);
    return 0;
}


Measured memory_bytes: 384