akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int k,p;
        scanf("%d%d",&k,&p);
        printf("%d\n",k%p?k%p:p);
    }

    return 0;
}

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

using namespace std;

typedef long long ll;

const int N = 109, M = 1e5 + 9, OO = 0x3f3f3f3f;
const int llOO = 0x3f3f3f3f;

int n, cap, w[N], v[N];

ll dp[N][M];

ll solve(int i, int rem){
    if(rem < 0) return -llOO;
    if(i == n)  return 0;

    ll &ret = dp[i][rem];
    if(~ret)    return ret;

    return ret = max(solve(i + 1, rem), v[i] + solve(i + 1, rem - w[i]));
}

int main(){

    cin >> n >> cap;
    for(int i = 0;i < n;i++)
        cin >> w[i] >> v[i];

    memset(dp, -1, sizeof dp);

    cout << solve(0, cap);
}


Measured memory_bytes: 85376
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define ull unsigned long long
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define eps 1e-9
#define P pair<int, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES\n"; }
void NO() { cout << "NO\n"; }
void Yes() { cout << "Yes\n"; }
void No() { cout << "No\n"; }

int main() {
	int n, q, t, ans = 0;
	vector<int> v;
	cin >> n;
	v.resize(n);
	REP(i, n)
		cin >> v[i];
	sort(all(v));

	cin >> q;
	while (q--) {
		cin >> t;
		if (binary_search(all(v), t))
			ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3160
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n=I()
lis=[LI() for i in range(n)]
lis.sort(key=lambda x:x[1])
#print(lis)
time=0
for i in range(n):
    time+=lis[i][0]
    if time>lis[i][1]:
        print("No")
        sys.exit()
print("Yes")
    

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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);

    for(int i = 0; i < n; i++){
        cin >> p.at(i);
    }

    sort(p.begin(), p.end());
    int res = 0;

    for(int i = 0; i < k; i++){
        res += p.at(i);
    }

    cout << res << endl;
}

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

# mp = dict()
# for ix in range(N):
#     mp[ix+1] = A[ix]

hist = []
exists = [0] * (N+1)
cur = 1
cnt = 0

# ここがおかしい?
# while True:
#     cur = mp[cur]
#     cnt += 1
#     # K -= 1

#     if exists[cur] != 0:
#         break
#     else:
#         exists[cur] = 1
#         hist.append(cur)

A = [0] + A
# print(A)
while exists[cur] == 0:
    hist.append(cur)
    exists[cur] = 1
    cur = A[cur]

cycle_sp = cur
# cycle_l = 0
cycle_sp_ix = hist.index(cycle_sp)

import sys
if K < cycle_sp_ix:
    print(hist[K])
    sys.exit()

cycle_l = len(hist) - cycle_sp_ix
# while True:
#     cur = mp[cur]
#     cycle_l += 1

#     if cur == cycle_sp:
#         break

rest = (K-cycle_sp_ix) % cycle_l
# print("cnt:", cnt)

# print("K:", K)
# print("cycle_l:", cycle_l)
# print("rest:", rest)

print(hist[rest + cycle_sp_ix])
# while rest != 0:
#     cur = mp[cur]
#     rest -= 1

# print(cur)




"""
# hist = [1]
hist = {1: 0}
while True:

    hk = hist.keys()[-1]

    if not mp[hk] in hist.keys():
        # hist.append(mp[hist[-1]])
        hist[mp[hk]] = 0

    else:
        # found
        cstart = hist.index(mp[hk])
        cend = len(hist)
        cycle_l = cend - cstart
        # print("hist:", hist)
        # print("cstart:", cstart)
        # print("cend:", cend)
        # print("cycle_l:", cycle_l)

        ans_i = (K - cstart) % cycle_l
        # print("ans_i:", ans_i)
        ans = hist[cstart + ans_i]

        print(ans)
        break
"""

Measured memory_bytes: 32368
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <map>
#include <stdio.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll mod = (ll)pow(10.0, 9.0) + 7;
pint dx[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

ll min(ll a, ll b) {
	if (a < b)
		return a;


	return b;
}

ll max(ll a, ll b) {
	if (a < b)
		return b;

	return a;
}


ll  N, X;
vector<ll> S;

ll dp[100005][200];

int main() {
	

	cin >> N >> X;
	S.resize(N);
	rep(i, N) {


		cin >> S[i];
	}

	sort(S.begin(), S.end());
	for (int j = 1; j <= X; j++) {
		dp[j][0] = j % S[0];
	}
	for(int i = 1; i < N; i++){
		for (int j = 1; j <= X; j++) {
			dp[j][i] = i * dp[j][i - 1] + dp[j % S[i]][i - 1];
			dp[j][i] %= mod;
		}

	}
	cout << dp[X][N - 1] << endl;
	return 0;
}


Measured memory_bytes: 156544
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<lli, lli> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	lli r, c, n;
	cin >> r >> c >> n;
	vector<mp> v;
	rep(j, n){
		lli x[2], y[2];
		cin >> x[0] >> y[0] >> x[1] >> y[1];
		if(x[0]*y[0]*(x[0]-r)*(y[0]-c) == 0 && x[1]*y[1]*(x[1]-r)*(y[1]-c) == 0) rep(i, 2){
			if(x[i] == 0 || y[i] == c) v.push_back(mp(x[i]+y[i], j));
			else v.push_back(mp(r+c+r+c-x[i]-y[i], j));
		}
	}
	
	sort(v.begin(), v.end());
	
	vector<int> s;
	rep(i, v.size()){
		lli p = v[i].sec;
		if(s.empty() || p != s.back()) s.push_back(p);
		else s.pop_back();
	}
	
	if(s.empty()) cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

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

int main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, a,b;
    cin >> n >> a >> b;
    cout << (n*a>b ? b : n*a) << "\n";
    return 0; 
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 200000
#define BIRTHDAY 1009

typedef struct hash{
	int num;
	struct hash *next;
}hash;

void append(hash**, int);
void search(hash**, int);
void clean(hash**);
void possible();

int a_list[MAX_NUM] = {0};
int a_index = 0;
hash *hash_list[BIRTHDAY] = {NULL};

int main(void){
	int N, M;
	int a, b;
	int i;
	hash *p;

	scanf("%d %d", &N, &M);
	for(i = 0; i < M; i++){
		scanf("%d %d", &a, &b);
		if(a == 1){
			append(hash_list, b);
		}
		if(b == N){
			a_list[a_index++] = a;
		}
	}

	for(i=0; i<a_index; i++){
		search(hash_list, a_list[i]);
	}

	clean(hash_list);
	printf("IMPOSSIBLE");
	return 0;
}

void append(hash **list, int num){
	hash *p, *tmp;
	hash *item;
	tmp = NULL;

	for(p = list[num%BIRTHDAY]; p != NULL && p->num < num; p = p->next)
		tmp = p;

	item = (hash*)malloc(sizeof(hash));
	item->num = num;
	item->next = p;
	if(tmp == NULL)
		list[num%BIRTHDAY] = item;
	else
		tmp->next = item;
}

void search(hash **list, int num){
	hash *p;
	for(p = list[num%BIRTHDAY]; p != NULL && p->num <= num; p = p->next){
		if(p->num == num)
			possible();
	}
}

void possible(){
	clean(hash_list);
	printf("POSSIBLE");
	exit(0);
}

void clean(hash **list){
	int i;
	hash *p, *tmp;
	tmp = NULL;
	for(i = 0; i < BIRTHDAY; i++){
		for(p = list[i]; p != NULL; p = p->next){
			free(tmp);
			tmp = p;
		}
	}
}

Measured memory_bytes: 3712
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)
int main(){
  int x,a;cin>>x>>a;
  cout << (float)x/a << endl;
}

Measured memory_bytes: 256
n_players, init_point, n_questions = [int(x) for x in input().split(" ")]
answerer_ids = []
for i in range(n_questions):
    answerer_ids.append(int(input()) - 1)

survivers_list = ["Yes" for i in range(n_players)]
n_answers = [0 for i in range(n_players)]
for i in range(n_questions):
    n_answers[answerer_ids[i]] += 1

for i in range(n_players):
    score = init_point - n_questions + n_answers[i]
    if score > 0:
        print("Yes")
    else:
        print("No")
    

Measured memory_bytes: 9416
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
vector<string> v={"MON", "TUE", "WED", "THU", "FRI","SAT","SUN"};
int main(){

ll n,m,a,b,r=0,c,k;
string s,h="";
cin>>n;
cin>>s;
for (ll i=0;i<s.size();i++)
{
h+=((s[i]+n-'A')%26+'A');
}
cout<<h;


    return 0;

    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = int64_t;

int main()
{
  i64 h, n;
  std::cin >> h >> n;
  
  i64 sum = 0;
  
  for(i64 i=0;i<n;++i)
  {
    i64 x;
    std::cin >> x;
    sum+=x;
  }
  
  if(sum>=h)
  {
    std::cout << "Yes\n";
  }
  else
  {
	std::cout << "No\n";
  }
  
  return 0;
}

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

#define loop(s, e, i) for (int i=s; i<e; ++i)
#define print(s) cout << s << endl;
using namespace std;
using ll = long long;


int P[100];

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<ll>> S(N);

  loop(0, M, i) {
    ll k;
    cin >> k;
    loop(0, k, j) {
      ll s;
      cin >> s;
      s--;
      S[s].emplace_back(i);
    }
  }
  loop(0, M, i) {
    cin >> P[i];
  }

  ll count = 0;
  for (int bit=0; bit<(1 << N); bit++) {
    vector<ll> KON(M, 0);
    loop(0, N, i) {
      if (bit & (1<<i)) {
        for (auto si : S[i]) {
          KON[si]++;
        }
      }
    }
    bool allon = true;
    loop(0, M, i) {
      if (KON[i] % 2 != P[i]) {
        allon = false;
        break;
      }
    }
    if (allon) {
      count++;
    }
  }
  print(count);
}

Measured memory_bytes: 3616
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<utility>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<sstream>
#include<cstring>
#include<bitset>
#include<stack>
using namespace std;

int a,b,c;

int main()
{
	cin>>a>>b>>c;
	cout<<(a+b)*c/2<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long k = sc.nextInt();
        List<Integer> ll = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ll.add(sc.nextInt());
        }
        long ans2 = 0;
        for (int i = 0; i < k; i++) {
            ans2 += ll.get(i);
        }
        if(ans2 >= n){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }


    public static int log2(long x) {
        return (int) (Math.log(x) / Math.log(2));
    }
}


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

typedef long long ll;
ll mod = 1000000007;

ll power(ll x, ll y)
{
    ll res = 1;
    x = x%mod;
    while (y)
    {
        if (y&1) res = ((res%mod)*(x%mod))%mod;

        y>>=1;
        x = ((x%mod)*(x%mod))%mod;
    }
    return res;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    ll h, a;
    cin >> h >> a;
    h%a?cout << (h/a)+1 << "\n":cout<<h/a<<"\n";    

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>

using namespace std;
int main()
{
    int N,M;
    cin >> N >> M;
    vector<long long> H(N,0);
    vector<bool> OK(N,true);
    for(int i=0; i<N; i++)
    {
        cin >> H[i];
    }
    
    for(int i=0; i<M; i++)
    {
        int a,b;
        cin >> a >> b;
        if(H[a-1] - H[b-1] > 0)
        {
            OK[b-1] = false;
        }
        else if(H[a-1] - H[b-1] < 0)
        {
            OK[a-1] = false;
        }
        else
        {
            OK[a-1] = OK[b-1] =false;
        }
    }

    int sum = 0;
    for(auto ok: OK)
    {
        if(ok)
            ++sum;
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 4056
import std;
enum inf(T)()if(__traits(isArithmetic,T)){return T.max/4;}
T[]readarr(T=long)(){return readln.chomp.split.to!(T[]);}
void scan(T...)(ref T args){auto input=readln.chomp.split;foreach(i,t;T)args[i]=input[i].to!t;}
struct Queue(T){T[]e;auto enq(T t){e~=t;}auto enq(T[]ts){e~=ts;}T deq(){T tp=e[0];e=e.length>1?e[1..$]:[];return tp;}}
struct Stack(T){T[]e;auto push(T t){e~=t;}auto push(T[]ts){e~=ts;}T pop(){T tp=e[$-1];e=e.length>1?e[0..$-1]:[];return tp;}}
//END OF TEMPLATE

void main(){
    int k;
    k.scan;
    ulong sum;
    foreach(a;1..k+1){
        foreach(b;1..k+1){
            foreach(c;1..k+1)
                sum+=gcd(gcd(a,b),c);
        }
    }   
    sum.writeln;
}


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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(){

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

    qsort(d, n, sizeof(int), compare_int);
    
    int count=d[n/2] - d[(n/2)-1];

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

    return 0;
}

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

int main() {
  long A, B, M;
  cin >> A >> B >> M;
  vector<long> a(A);
  for (long i = 0; i < A; i++) cin >> a.at(i);
  vector<long> b(B);
  for (long i = 0; i < B; i++) cin >> b.at(i);
  long ans = 1e18;
  for (long i = 0; i < M; i++) {
    long x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    ans = min(ans, a.at(x) + b.at(y) - c);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  cout << min(ans, a.at(0) + b.at(0)) << "\n";
}

Measured memory_bytes: 1792
#include <stdio.h>

struct card {
  int value;
  char symbol;
};

void bubble_sort(struct card c[], int n) {
  struct card a;
  for (int i = 0; i < n; i++) 
    for (int j = n - 1; j > i; j--) 
      if (c[j].value < c[j - 1].value) {
	a = c[j];
	c[j] = c[j - 1];
	c[j - 1] = a;
      }
}

void selection_sort(struct card c[], int n) {
  int minj;
  struct card a;
  for (int i = 0; i < n - 1; i++) {
    minj = i;
    for (int j = i + 1; j < n; j++)
      if (c[j].value < c[minj].value)
	minj = j;
    a = c[i];
    c[i] = c[minj];
    c[minj] = a;
  }
}

int stable_check(struct card a[], struct card b[], int n) {
  for (int i = 0; i < n; i++) {
    if ((a[i].value != b[i].value) || (a[i].symbol != b[i].symbol))
      return 0;
  }
  return 1;
}

void print_card(struct card a[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%c%d", a[i].symbol, a[i].value);
    if (i != n - 1)
      printf(" ");
  }
  printf("\n");
}

int main(void) {
  int n;
  struct card c[36];
  struct card a[36];
  
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf(" %c%d", &c[i].symbol, &c[i].value);
    a[i] = c[i];
  }

  bubble_sort(c, n);
  selection_sort(a, n);

  print_card(c, n);
  printf("Stable\n");
  print_card(a, n);
  if (stable_check(c, a, n))
    printf("Stable\n");
  else
    printf("Not stable\n");
  
  return 0;
}



Measured memory_bytes: 2104
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
char in[11100];
vector<pair<int,pair<int,int> > >g[1500];
int dp[1500][1500];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<1500;i++)g[i].clear();
		for(int i=0;i<a;i++){
			int ph,pm,qh,qm,r,s;
			scanf("%s%d:%d%d:%d%d%d",in,&ph,&pm,&qh,&qm,&r,&s);
			int p=ph*60+pm;
			int q=qh*60+qm;
			g[p].push_back(make_pair(q,make_pair(r,s)));
		}
		for(int i=0;i<1500;i++)for(int j=0;j<1500;j++)
			dp[i][j]=-999999999;
		dp[0][0]=0;
		for(int i=0;i<1450;i++){
			for(int j=0;j<1450;j++){
				if(i<j){
					dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
					for(int k=0;k<g[i].size();k++){
						dp[g[i][k].first][j]=max(dp[g[i][k].first][j],dp[i][j]+g[i][k].second.first);
					}
				}else if(i>j){
					dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
					for(int k=0;k<g[j].size();k++){
						dp[i][g[j][k].first]=max(dp[i][g[j][k].first],dp[i][j]+g[j][k].second.second);
					}
				}else{
					dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
					dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
					for(int k=0;k<g[i].size();k++)for(int l=0;l<g[i].size();l++){
						if(k==l)continue;
						dp[g[i][k].first][g[i][l].first]=max(dp[g[i][k].first][g[i][l].first],dp[i][j]+g[i][k].second.first+g[i][l].second.second);
					}
				}
			}
		}
		int ret=0;
		for(int i=0;i<1450;i++)for(int j=0;j<1450;j++)ret=max(ret,dp[i][j]);
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 9908
n=int(input())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
#rint(sum(a[:-1]))

c=0
for i in range(n):
    if i == 0:
        c+=0
    elif i == 1:
        c+=a[0]
    else:
        c+=a[i//2]
print(c)

Measured memory_bytes: 94348
from collections import deque
from copy import deepcopy

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
field_org = [[-1] * W for _ in range(H)]
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = deque()
        q.append((i, j, 0))
        field = deepcopy(field_org)
        field[j][i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

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

using namespace std;
#define mx 200000
#define ll long long
    char s[100002];
int ar[5][10002];
int main()
{


   int n;
   cin>>n;
  scanf("%s",s+1);





   int l =strlen(s+1);

   ar[1][1] = 1;
   for(int i=1;i<=l;i++){
        for(int j=4;j>=2;j--){
            for(int k = 1;k<=199;k++){
                int x= k*10 +  (s[i] -'0');
                ar[j][x] =max(ar[j-1][k],ar[j][x]);

                //if(ar[j][x])cout<<j<<" "<<k<<" "<<x<<endl;
            }
        }
   }

   int res=0;


   for(int i=1000;i<=1999;i++) if(ar[4][i])res++;
   cout<<res<<endl;

    return 0;
}



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

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define INF 1e9
// constexpr ll INF = 1LL << 60;
int H, W, N;
int sr, sc;
string S, T;

bool solve(){
  int left = 0, right = W-1;
  if(S[N-1] == 'L') left++;
  if(S[N-1] == 'R') right--;
  REPR(i, N-2){
    if(T[i] == 'L') right = min(right+1, W-1); 
    if(T[i] == 'R') left =  max(left-1, 0);
    if(S[i] == 'L') left++;
    if(S[i] == 'R') right--;
    if(left > right) return false;
  }
  if(sc < left || right < sc) return false;
  int upper = 0, bottle = H-1;
  if(S[N-1] == 'U') bottle--;
  if(S[N-1] == 'D') upper++;
  REPR(i, N-2){
    if(T[i] == 'U') bottle = min(bottle+1, H-1);
    if(T[i] == 'D') upper = max(upper-1, 0);
    if(S[i] == 'U') upper++;
    if(S[i] == 'D') bottle--;
    if(upper > bottle) return false;
  }
  return upper <= sr && sr <= bottle;
}
int main(){
  cin >> H >> W >> N;
  cin >> sr >> sc;
  cin >> S >> T;
  sr--, sc--;
  if(solve()){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }

  return 0;
}



Measured memory_bytes: 776
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

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

const int MAX_P = 10000;
bool visited[MAX_P + 1];
int suf[MAX_P + 1];

void solve() {
    int n, p;
    cin >> n >> p;
    string s;
    cin >> s;
    ll ans = 0;
    if (p == 2 or p == 5) {
        fori (i, 0, n) {
            int val = s[i] - '0';
            if (val % p == 0) ans += i + 1;
        }
    }
    else {
        suf[0] = 1;
        int sum = 0;
        int pot = 1;
        ford (i, n - 1, 0) {
            int val = s[i] - '0';
            sum = (sum + pot * val) % p;
            ans += suf[sum];
            suf[sum]++;
            pot = (pot * 10) % p;
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}



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

int main(){
    int w;
    while(cin >> w){
        if(w == -1) break;

        int ans = 1150;
        ans += max(0, min(w-10 , 10)) * 125;
        ans += max(0, min(w-20 , 10)) * 140;
        ans += max(0, w-30) * 160;

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


Measured memory_bytes: 3092
import math

def f(s, x):
  return int(math.floor(s * (100 + x) / 100.0))

while True:
  (x, y, s) = map(int, raw_input().split())
  if x + y + s == 0:
    break

  ans = 0
  for i in xrange(1, s):
    for j in xrange(1, s - i + 1):
      if f(i, x) + f(j, x) == s:
        ans = max(ans, f(i, y) + f(j, y))

  print ans

Measured memory_bytes: 4368
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, n) for (int i = 1; i <= (n); ++i)
#define repd(i, n) for (int i = (n)-1; i >= 0; --i)
#define repds(i, n) for (int i = (n); i > 0; --i)
#define loop(i, x, n) for (int i = (x); i < (n); ++i)
#define loops(i, x, n) for (int i = (x); i <= (n); ++i)
#define loopd(i, x, n) for (int i = (x); i > (n); --i)
#define loopds(i, x, n) for (int i = (x); i >= (n); --i)
#define itrep(i, a) for (auto i = begin(a); i != end(a); ++i)
#define itrepd(i, a) for (auto i = rbegin(a); i != rend(a); ++i)
#define each(i, x) for (auto &&i : x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) ((int)a.size())
#define pow2(n) (n * n)
#define int ll
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using p_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
constexpr double eps = 1e-9;
ll mod = static_cast<ll>(1e9 + 7);
template <class T, class... Args>
constexpr void mins(T &a, Args... args) { a = min<T>({a, args...}); }
template <class T, class... Args>
constexpr void maxs(T &a, Args... args) { a = max<T>({a, args...}); }
template <class F>
class FixPoint : private F {
public:
    explicit constexpr FixPoint(F &&f) : F(std::forward<F>(f)) {}
    template <class... Args>
    constexpr decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template <class F>
constexpr decltype(auto) funcs(F &&f) { return FixPoint<F>{std::forward<F>(f)}; }
template <class T>
std::vector<T> vecs(int n, T &&val) { return std::vector<T>(std::forward<int>(n), std::forward<T>(val)); }
template <class... Args>
decltype(auto) vecs(int n, Args &&... args) { return std::vector<decltype(vecs(std::forward<Args>(args)...))>(std::forward<int>(n), vecs(std::forward<Args>(args)...)); }
template <class V, class T>
void fill(V &x, const T &val) { x = val; }
template <class V, class T>
void fill(vector<V> &vec, const T &val) {
    for (auto &&v : vec)
        fill(v, val);
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    int ans = 0;
    rep(i, k) ans += a[i];
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout.flush();
    return 0;
}

Measured memory_bytes: 3620
s = gets.chomp
if s[0..6] == "keyence"
  puts 'YES'
elsif s[-7..-1] == "keyence"
  puts 'YES'
elsif s[0]+s[-6..-1] == "keyence"
  puts 'YES'
elsif s[0..1]+s[-5..-1] == "keyence"
  puts 'YES'
elsif s[0..2]+s[-4..-1] == "keyence"
  puts 'YES'
elsif s[0..3]+s[-3..-1] == "keyence"
  puts 'YES'
elsif s[0..4]+s[-2..-1] == "keyence"
  puts 'YES'
elsif s[0..5]+s[-1] == "keyence"
  puts 'YES'
else
  puts 'NO'
end

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

using lli = int64_t;
using vi = vector<lli>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

void dfs(vvvi& g, vi& dist, int k, int p)
{
    for(auto& e : g[k]) if(e[0] != p)
    {
        dist[e[0]] = dist[k] + e[1];
        dfs(g, dist, e[0], k);
    }
}

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

    int n; cin >> n;

    vvvi g(n + 1);

    for(int i = 1; i < n; i++)
    {
        int a, b, c; cin >> a >> b >> c;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    int q, k; cin >> q >> k;

    vi dist(n + 1);

    dist[k] = 0;

    dfs(g, dist, k, -1);

    for(int i = 0; i < q; i++)
    {
        int x, y; cin >> x >> y;

        lli ans = dist[x] + dist[y];

        cout << ans << '\n';
    }

    return 0;
}

Measured memory_bytes: 25216
/*
*/

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <cstring>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define PI 3.141592653589793
#define MOD 1000000007LL
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<string> S(N);
  for (int i = 0; i < N; i++) cin >> S.at(i);
 
  sort(S.begin(), S.end());
  S.push_back("");
 
  vector<string> ans;
  for (int i = 1, cnt = 1, Max = 0; i <= N; i++) {
    if (S.at(i - 1) != S.at(i)) {
      if (cnt > Max) {
        ans.clear();
        Max = cnt;
      }
      if (cnt >= Max) ans.push_back(S.at(i - 1));
      cnt = 1;
    }
    else cnt++;
  }
 
  for (int i = 0; i < ans.size(); i++) cout << ans.at(i) << endl;
        return 0;
}


Measured memory_bytes: 17764
#include<bits/stdc++.h>
using namespace std;
int main()
{
    #ifdef TarekHasan
        //freopen("input.txt","r",stdin);
    #endif // TarekHasan
    long long int n; cin >> n;

    int arr[n+1]={0};

    for(long long int i=1;i<=n;i++)
    {
        for(long long int j=1;j<=n;j++)
        {
            for(long long int k=1;k<=n;k++)
            {
                long long int res = (i*i)+(j*j)+(k*k)+(i*j)+(j*k)+(i*k);
                if(res>n) break;
                arr[res]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout << arr[i] << endl;

    return 0;
}


Measured memory_bytes: 3620
#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;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair <long long,long long> ii;
// typedef complex<long double> point;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,a,b;
    cin >> n >> a >> b;
    bool am = true;
    while (true){
        if (am){
            if (a+1 != b){
                a++;
            } else {
                a--;
            }
            if (a <= 0){
                cout << "Borys" << endl;
                return 0;
            }
            am = false;
        }
        else {
            if (b-1 != a){
                b--;
            } else {
                b++;
            }
            if (b > n){
                cout << "Alice" << endl;
                return 0; 
            }
            am = true;
        }
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

class CalcExpression
{
	typedef string::const_iterator State;
	class ParseError {};


public:

	int expression(State& begin)
	{
		int ret = term(begin);

		while(true)
		{
			if(*begin == '+')
			{
				begin++;
				ret += term(begin);
			}
			else if(*begin == '-')
			{
				begin++;
				ret -= term(begin);
			}
			else break;
		}

		return ret;
	}


private:

	int term(State& begin)
	{
		int ret = factor(begin);

		while(true)
		{
			if(*begin == '*')
			{
				begin++;
				ret *= factor(begin);
			}
			else if(*begin == '/')
			{
				begin++;
				ret /= factor(begin);
			}
			else break;
		}

		return ret;
	}

	int factor(State &begin)
	{
		int ret = 0;

		if(*begin == '(')
		{
			begin++;
			ret = expression(begin);
			begin++;
		}
		else return number(begin);

		return ret;
	}

	int number(State& begin)
	{
		int ret = 0;

		while(isdigit(*begin))
		{
			ret *= 10;
			ret += *begin - '0';
			begin++;
		}

		return ret;
	}

};

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

	CalcExpression ce;
	while(n--)
	{
		string expression, buf;

		cin >> expression;
		string::const_iterator it = expression.begin();

		cout << ce.expression(it) << endl;
	}
}

Measured memory_bytes: 0
/*
    Written by Nitrogens
    Desire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

const int maxn = 1e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;

#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl

int a[105];
ll prefix[2][100005], dp[105][100005];

int main()
{
    //ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);

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

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    memset(dp, 0, sizeof(dp));
    //for(int i = 0; i <= 100000; i++)    dp[0][i] = 1;
    dp[0][k] = 1;
    prefix[0][k + 1] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            /*
            for(int l = 0; l <= a[i] && j + l <= k; l++)
            {
                dp[i][j] = (dp[i][j] + dp[i - 1][j + l]) % Mod;
            }
            */
            //dbg3(i, j, dp[i][j]);
            dp[i][j] = (prefix[0][min(j + a[i] + 1, k + 1)] - prefix[0][j] + Mod) % Mod;
            prefix[1][j + 1] = (prefix[1][j] + dp[i][j]) % Mod;
        }
        memcpy(prefix[0], prefix[1], sizeof(prefix[1]));
        memset(prefix[1], 0, sizeof(prefix[1]));
    }
    printf("%lld\n", dp[n][0]);

    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


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

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

struct Node *nil;

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

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

void printList(){
   struct 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(struct 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(){
    deleteNode(nil->prev);
}

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

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

int main(){
    int key,n,i;
    int size=0,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: 33044
from sys import setrecursionlimit; setrecursionlimit(10**9)
S = input()

def res(S, A, B):
    if not S:
        B.append(sum(list(map(int, A))))
        return None
    A += [S[0]]
    res(S[1:], A, B)
    A.pop()
    A[-1] += S[0]
    res(S[1:], A, B)
    return B

if len(S) == 1:
    print(int(S))
else:
    B = res(S[1:], [S[0]], [])
    print(sum(B))

Measured memory_bytes: 3064
#include<stdio.h>
int main(void){
	int i,len;
	char s[4096];
	while(scanf("%s",&s) != EOF ){
		if(s[0]=='0') break;
		else{
		int ans = 0;
		len = strlen(s);
	 	for(i = 0;i<len;i++) ans += s[i]-'0';
	printf("%d\n",ans);
}
}
	return 0;
}
	


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

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

    ll n;
    cin>> n;
    switch(n%10) {
    case 2:case 4:case 5:case 7:case 9: cout << "hon" << endl; break;
    case 0:case 1:case 6:case 8: cout << "pon" << endl; break;
    case 3: cout << "bon" << endl; break;
    }

    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
 
using namespace std;
 
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;
 
ll mod = 1e9+7;

int t,N,Q,lix,rix,safemin,safemax;
string s;
vector<vector<char>> mv;

string move(int ix) {
        REP(i,Q) {
        if (mv[i][0] == s[ix]){
            if (mv[i][1] == 'L') ix -= 1;
            else ix += 1;

            if (ix == 0) return "left";
            else if (ix == N+1) return "right";
        }
    }
    return "safe";
}

int main() {
    cin >> N >> Q;
    cin >> s;

    s = "n" + s + "n";
    REP(i,Q) {
        char ti,di;
        cin >> ti >> di;
        mv.push_back({ti,di});
    } 


    if (move(1) == "right" || move(N) == "left") {
        cout << 0 << endl;;
        return 0;
    }
        

    if (move(1) == "left") {
        lix = 1;
        safemin = N;
    }
        
    else {
        lix = 0;
        safemin = 1;
    }
        
    while (safemin - lix > 1) {
        t = (lix+safemin)/2;
        if (move(t) == "left") {
            lix = t;
        }
        else {
            safemin = t;
        }
    }
    

    if (move(N) == "right") {
        rix = N;
        safemax = 1;
    }
        
    else {
        rix = N+1;
        safemax = N;
        }
    while (- safemax + rix > 1) {
        t = (safemax + rix)/2;
        if (move(t) == "right") rix = t;
        else safemax = t;
    }
    
    cout << rix - lix - 1 << endl;
}

Measured memory_bytes: 12860
#include "bits/stdc++.h"
using ll = long long;
using namespace std;

int get(vector <int> &v, int d) {
   int ans = 0;
   for(auto &e: v) {
      ans += (e - d) * (e - d);
   }
   return ans;
}

bool isSquare(int a) {
   for(int i = 1; i * i <= a; i++) {
      if(i * i == a) return true;
   }
   return false;
}

void solve() {
   int a, b;
   cin >> a >> b;
   if(isSquare(stoi(to_string(a) + to_string(b)))) {
      cout << "Yes" << endl;
   } else {
      cout << "No" << endl;
   }
}

int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solve();
   } 
   return 0;
}


Measured memory_bytes: 3720
#include <iostream>
#include <set> 
#include <iterator>
#include <bitset> 
#include <bits/stdc++.h> 
using namespace std;
typedef  long long int ll;
ll mod=1000000007;
int dfs(int u,vector <int> adj[],int visited[])
{   visited[u]=1;
    int s=0;
    for(auto itr=adj[u].begin();itr!=adj[u].end();itr++)
    {   if(visited[*itr]==0)
            s=s+dfs(*itr,adj,visited);
    }
    return s+1;
}

int main() {
    int T=1;
    //cin>>t;
    while(T--)
    {   int n,m;
        cin>>n>>m;
        vector <int> adj[n+1];
        int visited[n+1]={0};
        for(int i=1;i<=m;i++)
        {   int u,v;
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        set <int, greater<int>> p;
        for(int i=1;i<=n;i++)
        {   if(visited[i]==0)
                p.insert(dfs(i,adj,visited));
        }
        cout<<*p.begin();
            
            
    }
	return 0;
}


Measured memory_bytes: 24716
def d_semi_common_multiple():
    from fractions import gcd
    from functools import reduce
    N, M = [int(i) for i in input().split()]
    A = [int(i) // 2 for i in input().split()]  # 先に2で割っておく

    def count_divide_2(n):
        ret = 0
        while n % 2 == 0:
            ret += 1
            n //= 2
        return ret

    def lcm(a, b):
        return a * b // gcd(a, b)

    # A の全要素について、2で割れる回数は等しいか？
    tmp = count_divide_2(A[0])
    for a in A:
        if count_divide_2(a) != tmp:
            return 0

    t = reduce(lambda x, y: lcm(x, y), A)
    return M // t - M // (2 * t)

print(d_semi_common_multiple())

Measured memory_bytes: 16308
N, M, C = map(int, input().split())
B = list(int(i) for i in input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
ok_count = 0

for i in range(N):
    calc_result = 0
    for m in range(M):
        calc_result += A[i][m] * B[m]
    if calc_result + C > 0:
        ok_count += 1

print(ok_count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const lli maxN = 1e10, maxX = 1e5 + 2; lli n, x, m;
map<lli, int> curr;
lli acc[maxX];

int main()
{
  while (scanf("%lld %lld %lld", &n, &x, &m) != EOF)
  {
    lli a = x;
    lli i;
    curr.clear();
    acc[0] = 0;
    for (i = 1; i <= n; i++)
    {
      DEBUG if (i < 10) printf("\t\t%lld %lld\n", i, a);
      if (curr.count(a)) break;
      curr[a] = i;
      acc[i + 1] = acc[i] + a;
      a = a * a % m;
    }

    if (i > n) printf("%lld\n", acc[n + 1]);
    else
    {
      lli first = curr[a];
      DEBUG printf("\t%lld %lld %lld\n", first, i, a);
      DEBUG printf("\t%lld | %lld %lld | %lld\n", acc[first], acc[i], acc[i] - acc[first], n - i);
      lli ans = acc[first], blockSize = i - first;
      lli fits = (n - first + 1) / blockSize;
      lli lefts = (n - first + 1) % blockSize;
      ans += (acc[i] - acc[first]) * fits; // full blocks sum
      ans += acc[first + lefts] - acc[first];
      lli target = 492443256176507 - ans;
      // printf("\t%lld | %lld\n", target, lefts);
      // for (lli j = first; j <= i; j++)
      //   if (acc[j] - acc[first] == target)
      //     printf("\tfound %lld\n", j);
      printf("%lld\n", ans);
    }
  }
  return 0;
}

Measured memory_bytes: 7296
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>

using namespace std;

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

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

struct UnionFind
{
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unionSet(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
                swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y)
    {
        return root(x) == root(y);
    }
    int root(int x)
    {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x)
    {
        return -data[root(x)];
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    int data[n];
    UnionFind u(n);
    REP(i, n)
    {
        cin >> data[i];
    }
    REP(i, m)
    {
        int a, b;
        cin >> a >> b;
        u.unionSet(a - 1, b - 1);
    }
    int ans = 0;
    REP(i, n)
    {
        if (u.findSet(i, data[i] - 1))
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
using System;

namespace arc071_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] max = new int[26];
            for (int i = 0; i < 26; i++)
            {
                max[i] = int.MaxValue;
            }
            for (int i = 0; i < n; i++)
            {
                string s = Console.ReadLine();
                int[] letter = new int[26];
                for (int j = 0; j < s.Length; j++)
                {
                    letter[s[j] - 97]++;
                }
                for (int j = 0; j < 26; j++)
                {
                    max[j] = Math.Min(max[j], letter[j]);
                }
            }
            for (int i = 0; i < 26; i++)
            {
                for (int j = 0; j < max[i]; j++)
                {
                    Console.Write((char)(i + 97));
                }
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 13140
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n; cin >> n;
    vector<ld> a(n);
    REP(i, n) { cin >> a[i]; }

    ld ans = 0;
    REP(i, n) {
        ans += 1.L / a[i];
    }
    cout << setprecision(20) << (1.L / ans) << endl;
    

    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll mod=1e9+7;
	   
int main() {
			fast
			// #ifndef ONLINE_JUDGE
			// freopen("input.txt","r",stdin);
			// freopen("output.txt","w",stdout);
			// #endif
			 
	     	ll n,m,x;
			cin>>n>>m>>x;
			ll arr[n][m];
			ll cost[n];
			for(ll i=0;i<n;i++)
			{
				cin>>cost[i];
				for(ll j=0;j<m;j++)
				{
					cin>>arr[i][j];
					
				}
				
			}

			ll ans=LLONG_MAX;
			ll check[m]={0};
			for(ll i=1;i<(1<<n);i++)
			{
				ll cs=0;
				memset(check,0,sizeof(check));
				for(ll j=0;j<n;j++)
				{
					if(i&(1<<j))
					{
						ll pre=j;
						cs+=cost[pre];
						for(ll k=0;k<m;k++)
						{
							check[k]+=arr[pre][k];
						}
					}
				}
				// cout<<cs<<endl;
				ll x1=0;
				for(ll j=0;j<m;j++)
				{
					// cout<<check[j]<<" ";
					if(check[j]>=x)
					x1+=1;
				}
				if(x1==m)
				{
					ans=min(ans,cs);
				}
				// cout<<endl;
			}
			if(ans==LLONG_MAX)
			ans=-1;
			cout<<ans<<endl;
			 
			return 0;
		 }	


Measured memory_bytes: 3636