akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007

ll gcd(ll a, ll b){
  if(a < b) return gcd(b, a);
  ll r = a % b;
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
 
ll lcm(ll a, ll b){
  ll ret = (a * b)/gcd(a,b);
  return ret;
}

int main(){
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n);
  
  for(ll i=0; i<n; i++){
    cin >> a[i];
    a[i] = a[i]/2;
  }
  
  ll alcm = a[0];
  for(ll i=1; i<n; i++){
  	alcm = lcm(alcm, a[i]);
    if(alcm > m){
      cout << 0 << endl;
      return 0;
    }
  }
  
  for(ll i=0; i<n; i++){
  	if((alcm/a[i]) % 2 == 0){
      cout << 0 << endl;
      return 0;
    }
  }
  
  ll ans = (ll)((m/alcm + 1)/2);;
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
#include <cctype>

using namespace std;

int main()
{
	double x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	printf("%.6f\n", sqrt(pow(x2 - x1, 2.0) + pow(y2 - y1, 2.0)));
	return 0;
}

Measured memory_bytes: 1236
from fractions import gcd
a, b, c, d = map(int, input().split())
cnt_c = (b // c) - ((a-1) // c)
cnt_d = (b // d) - ((a-1) // d)
cd = c*d//gcd(c, d)
cnt_cd = (b // (cd)) - ((a-1) // (cd))
cnt_all = b-a+1
print(cnt_all - (cnt_c + cnt_d - cnt_cd))

Measured memory_bytes: 5048
n = int(input())
s1 = input()
s2 = input()
ans = 1
start = 0
yoko = 0
mae = 0
for i in range(len(s1)):
    if yoko == 1:
        yoko = 0
        continue
    if mae == 0:
        if s1[i] == s2[i]:
            ans *= 3
            mae = 1
        else:
            yoko = 1
            ans *= 6
            mae = 2
        start = 1
    else:
        if mae == 1:
            #縦→縦
            if s1[i] == s2[i]:
                ans *= 2
            #縦→横
            else:
                ans *= 2
                yoko = 1
                mae = 2
        else:
            #横→縦
            if s1[i] == s2[i]:
                mae = 1
            #横→横
            else:
                ans *= 3
                yoko = 1
print(ans % 1000000007)


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

using namespace std;

typedef long long int lli;

lli employees[4001];
bool checked[4001];

signed main()
{
	lli n;
	while (cin >> n, n) {
		for (lli i = 1; i <= 4000; ++i) employees[i] = checked[i] = false;

		vector<lli> ans;

		for (lli i = 0; i < n; ++i) {
			lli num, a, b; cin >> num >> a >> b;

			if (checked[num]) continue;

			employees[num] += a * b;

			if (employees[num] >= 1000000) {
				ans.push_back(num);
				checked[num] = true;
			}
		}

		if (ans.size()) {
			for (lli i = 0; i < ans.size(); ++i) {
				cout << ans[i] << endl;
			}
		} else {
			cout << "NA" << endl;
		}
	}
}

Measured memory_bytes: 1268
/*
 *　026 - A
 */

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan1 = new Scanner(System.in);

		int slime_Num;
		String slime_Str;
		int[] slime1 = new int[10000];
		int[] slime2 = new int[10000];
		int i;
		int kekka1;
		int kekka2;

		// スライム数とスライムの種類列を入力

		slime_Num = scan1.nextInt(); scan1.nextLine();
		slime_Str = scan1.nextLine();

		String[] result = slime_Str.split(" ");

		for(i = 0; i < result.length ; i++) {
			slime1[i] = Integer.parseInt(result[i]);
		}

		System.arraycopy(slime1,0,slime2,0,result.length);

		kekka1 = Comp_Num.Comp1(slime1 , result.length , slime_Num);
		kekka2 = Comp_Num.Comp2(slime2 , result.length , slime_Num);

		//結果を表示
		if(kekka1 <= kekka2) {
			System.out.println(kekka1);
		}else {
			System.out.println(kekka2);
		}

	}

}

//比較用のクラス
class Comp_Num{

	static int Comp1(int[] slime, int length, int slime_Num){

		int before = slime[0];
		int after;
		int kaisu = 0;

		for(int i = 1; i < length; i++) {
			if(i + 1 < length) {
				after = slime[i + 1];
			}else {
				after = 0;
			}
			if(before == slime[i]) {
				if(slime_Num == 2 ) {
					if(before == 1) {
						slime[i] = 2;
					}else {
						slime[i] = 1;
					}
				}
				for(int j = 1; j <= slime_Num ;j++) {
					if(j != before && j != after) {
						slime[i] = j;
					}
				}
				kaisu++;
			}
			before = slime[i];
		}
		return kaisu;
	}

	static int Comp2(int[] slime, int length, int slime_Num){

		int x;
		int y;
		int kaisu;

		for(int i = 0; i < (int)(length / 2) ; i++) {
			x = slime[i];
			y = slime[length - (1 + i)];
			slime[length - (1 + i)] = x;
			slime[i] = y;
		}

		kaisu = Comp1(slime, length, slime_Num);
		return kaisu;

	}

}



Measured memory_bytes: 23892
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int ar[2*n];
	for (int i=0;i<n*2;i++)
	{
		cin>>ar[i];
	}
	sort(ar,ar+n*2);
	int m=0;
	for (int i=0;i<2*n;i+=2)
	{
		m+=ar[i];
	}
	printf ("%d\n",m);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

map<ll, ll> mp;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int N;
    cin >> N;
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        ll a;
        cin >> a;
        ll q = a-i;
        if(mp.count(q) != 0){
            ans += mp[q];
        }
        ll p = -a-i;
        if(mp.count(p) == 0){
            mp[p] = 1;
        }else{
            mp[p]++;
        }
    }
    cout << ans << endl;
}

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

bool is_prime(int k)
{
	for(int j=2;j*j<=k;j++){
		if(k%j==0) {
			return false;
		}
	}
    return true;
}

int main()
{
    stringstream ss;
    // 入力
    int A,B;
    cin>>A>>B;
    if(A<=8 && B<=8) cout<<"Yay!"<<endl;
    else cout<<":("<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define SENTINEL 1000000000
using namespace std;

void Merge(int left, int mid, int right);
void MergeSort(int left, int right);

int A[500000];
int count = 0;

int main(){

	int n;
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> A[i];
	}
	
	MergeSort(0,n);
	
	for(int i=0; i<n; i++){
		cout << A[i];
		if(i!=n-1){
			cout << " ";
		}
	}
	
	cout << "\n" << count << "\n";

}

void Merge(int left, int mid, int right){
	int n1, n2;
	
	n1 = mid - left;
	n2 = right - mid;
	
	int L[n1+1], R[n2+1];
	
	for(int i=0; i<n1; i++){
		L[i] = A[left+i];
	}
	for(int i=0; i<n2; i++){
		R[i] = A[mid+i];
	}
	L[n1] = SENTINEL;
	R[n2] = SENTINEL;
	for(int i=0,j=0,k=left; k<right; k++){
		if(L[i] == SENTINEL && R[j] == SENTINEL) break;
		count++;
		if(L[i] <= R[j]){
			A[k] = L[i];
			i++;
		}else{
			A[k] = R[j];
			j++;
		}
	}
	
}

void MergeSort(int left, int right){
	
	int mid;
	if(left+1 < right){
		mid = (left + right) / 2;
		MergeSort(left, mid);
		MergeSort(mid, right);
		Merge(left, mid, right);
	}
	
}

Measured memory_bytes: 5064
#include<iostream>
using namespace std;
int main(){
  string S;
  int N,ans=0;
  cin>>N>>S;
  for(int i=0;i<S.size()-2;i++){
    if(S[i]=='A'){
      if(S[i+1]=='B'&&S[i+2]=='C'){
        ans++;
      }
    }
  }
  cout<<ans;
}

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

using namespace std;

int main(void) {
    string S, T;
    cin >> S >> T;
    if(S[0] == T[2] && S[1] == T[1] && S[2] == T[0]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int H, W;
    
    while(true){
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        for (int i = 0; i < H; i++){
            for ( int j = 0; j < W; j++){
                if(i==0 || i==H-1 || j==0 || j == W-1){
                    cout << "#";
                }
                else{
                    cout << ".";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3096
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int[] v = new int[5005];
        for(int i = 0;i < 5005;i++){
            v[i] = 1;
        }
        int p = 3;
        while(true){
            if(p*p > 10010){
                break;
            }else{
                if(v[(p-1)/2] == 0){
                    p += 2;
                }else{
                    int t = p*p;
                    while(t < 10010){
                        v[(t-1)/2] = 0;
                        t += 2*p;
                    }
                    p += 2;
                }
            }
        }
        while(scan.hasNext()){
        	int n = scan.nextInt();
        	if(n == 0){
        		break;
        	}
        	n += (n%2==0)?-1:0;
        	for(int i = n/2;i > 1;i--){
        		if(v[i] == 1 && v[i-1] == 1){
        			System.out.println(2*(i-1)+1 + " " + (2*i+1));
        			break;
        		}
        	}
        }
	}
}

Measured memory_bytes: 31912
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
prev = a[0]
total = 0
for i, j in zip(a[1:], b):
    if prev >= j:
        total += j
        prev = i
    else:
        task = prev + i
        if task <= j:
            total += task
            prev = 0
        else:
            total += j
            prev = task - j
print(total)

Measured memory_bytes: 18624
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}

struct edge{int to, cost;};

class Graph
{
public:
    int V;
    vector<vector<edge>> G;

    Graph(int V): V(V){
        G = vector<vector<edge>>(V, vector<edge>(0));
    }

    void add_edge(int from, int to, int cost){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    bool dfs(int v, vec &u, int p, vec &n){
        u[v] = p;
        n[p]++;
        REP(i, G[v].size()){
            if(u[G[v][i].to] == p) return false;
            else if(u[G[v][i].to] == -1){
                if(!dfs(G[v][i].to, u, 1 - p, n)) return false;
            }
        }
        return true;
    }

};

signed main(){

    int N, M; cin >> N >> M;
    vector<vector<bool>> exist(N, vector<bool>(N, false));
    int A, B;
    REP(i, M){
        cin >> A >> B;
        exist[A - 1][B - 1] = true;
        exist[B - 1][A - 1] = true;
    }
    Graph G(N);
    REP(i, N) REP(j, i) if(!exist[i][j]) G.add_edge2(i, j, 0);

    vec u(N, -1), n(2);
    vector<Pii> p;
    REP(i, N){
        if(u[i] == -1){
            n[0] = 0; n[1] = 0;
            if(!G.dfs(i, u, 0, n)){
                cout << -1 << endl;
                return 0;
            }
            p.push_back(Pii(n[0], n[1]));
        }
    }

    vector<bool> dp(N + 1, false);
    dp[0] = true;
    REP(i, p.size()){
        vector<bool> dq(N + 1, false);
        REP(j, N + 1){
            if(dp[j]){
                dq[j + p[i].first] = true;
                dq[j + p[i].second] = true;
            }
        }
        dp = dq;
    }
    int mm = INF, nn = -1;
    REP(i, N + 1){
        if(dp[i] && llabs(N - 2 * i) < mm){
            mm = llabs(N - 2 * i);
            nn = i;
        }
    }
    int ans = nn * (nn - 1) / 2 + (N - nn) * (N - nn - 1) / 2;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 11264
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int int64_t
#define double long double
#define pii pair<int, int>
#define pdd pair<double, double>
#define F first
#define S second
#define pb push_back
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> orset;

const int N = 202000;

bool can(int k, int n){
   if(k == 1)
      return false;
   while(n){
      if(n % k == 1)
         return true;
      if(n % k)
         return false;
      n /= k;
   }
   return false;
}

int32_t main(){
   ios_base :: sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int n; cin >> n;
   int ans = 0;
   int k = n - 1;
   set<int> lol;
   for(int i = 1; i <= sqrt(k); i ++){
      if(can(i, n)){
         lol.insert(i);
      }
      if(can(k / i, n))
         lol.insert(k / i);
   }
   for(int i = 1; i <= sqrt(n); i ++){
      if(can(i, n)){
         lol.insert(i);
      }
      if(can(n / i, n))
         lol.insert(n / i);
   }
   cout << lol.size();
}


Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <queue>
# include <stack>
# define MOD 1000000000+7
# define INF 1000000000
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;
ll counter;
ll keta(ll i) {
	counter = 0;
	while (i > 10) {
		i /= 10;
		counter++;
	}
	return counter;
	
}
int main() {
	ll a = 0, b = 0, n = 0;
	std::string str,str2;
	cin >> str>>str2;
	if (str[0] == str2[0])a++;
	if (str[1] == str2[1])a++;
	if (str[2] == str2[2])a++;
	cout << a << endl;
}


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

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

	int n = 0;
	std::cin >> n;

	std::vector<unsigned long long> list;
	unsigned long long input = 0;
	for (int i = 0; i < n; ++i) {
		std::cin >> input;
		list.push_back(input);
	}
	int li = 0, ri = n-1;
	unsigned long long lt = 0, rt = 0;
	while (li <= ri) {
		if (lt <= rt) {
			lt += list[li++];
		}
		else {
			rt += list[ri--];
		}
	}
	unsigned long long sa = (rt >= lt) ? rt - lt : lt - rt;
	std::cout << sa;
	return 0;
}


Measured memory_bytes: 2420
// 解説読んだ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N;
    ll x;
    cin >> N >> x;
    ll a[N], ans = 0, min_cost[N];
    for(int i=0;i<N;i++){
        cin >> a[i];
        ans += a[i];
        min_cost[i] = a[i];
    }
    
    ll total_cost;
    for(int j=1;j<N;j++){   // 魔法を唱える回数をj回に固定
        for(int i=0;i<N;i++){
            if(i-j<0)
                min_cost[i] = min(a[N+(i-j)], min_cost[i]);
            else
                min_cost[i] = min(a[i-j], min_cost[i]);
        }
        total_cost = j*x;
        for(int i=0;i<N;i++){
            total_cost += min_cost[i];
        }
        ans = min(total_cost, ans);
        
    }

    cout << ans << endl;

}

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

int main() {
    long long N; cin >> N;
    while (N > 0) {
        long long low = 0, high = N;
        while (high - low > 1) {
            long long mid = (low + high) / 2;
            if (mid * (mid + 1)/2 >= N) high = mid;
            else low = mid;
        }
        cout << high << endl;
        N -= high;
    }
}

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


int main(){
	int a,b;
	cin >> a >> b;
	int ans = 0;
	if(a > b){
		ans += a;
		if(a-1 > b){
			ans += a-1;
		}else{
			ans += b;
		}
	}else{
		ans += b;
		if(a > b-1){
			ans += a;
		}else{
			ans += b-1;
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [a, b, c] = input[0].map(Number);

  return b - a === c - b ? "YES" : "NO";
};

console.log(main(read()));


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

int main(void){
  char b;
  cin>>b;
  switch (b)
  {
      case 'A':
          cout<<'T';
          break;
      case 'T':
          cout<<'A';
          break;
      case 'G':
          cout<<'C';
          break;
      case 'C':
          cout<<'G';
          break;
  
      default:
          break;
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,n = 0,c,d,i;
  cin >> a >> b >> c >> d;
  for (i = 1; i <= a; i++){
    if (i <= b){
      n += c;
    }
    else
    {
      n += d;
    }
    
  }
  cout << n <<'\n';
  return 0;
}

Measured memory_bytes: 256
def my_index(l,x):
    if x in l:
        return l.index(x)+1
    else:
        return 0
    
A_1_1,A_1_2,A_1_3=map(int,input().split())
A_2_1,A_2_2,A_2_3=map(int,input().split())
A_3_1,A_3_2,A_3_3=map(int,input().split())
N=int(input())
A=[A_1_1,A_1_2,A_1_3,A_2_1,A_2_2,A_2_3,A_3_1,A_3_2,A_3_3]

for i in range(N):
    bi=int(input())
    for j in range(len(A)):
        if A[j]==bi:
            if j==0:
                A_1_1=0
            elif j==1:
                A_1_2=0
            elif j==2:
                A_1_3=0
            elif j==3:
                A_2_1=0
            elif j==4:
                A_2_2=0
            elif j==5:
                A_2_3=0
            elif j==6:
                A_3_1=0
            elif j==7:
                A_3_2=0
            elif j==8:
                A_3_3=0
            else:
                pass
        else:
            pass

bingo_1=[A_1_1,A_1_2,A_1_3]
bingo_2=[A_2_1,A_2_2,A_2_3]
bingo_3=[A_3_1,A_3_2,A_3_3]
bingo_4=[A_1_1,A_2_1,A_3_1]
bingo_5=[A_1_2,A_2_2,A_3_2]
bingo_6=[A_1_3,A_2_3,A_3_3]
bingo_7=[A_1_1,A_2_2,A_3_3]
bingo_8=[A_1_3,A_2_2,A_3_1]

ans=0

if sum(bingo_1)==0:
    ans=1
elif sum(bingo_2)==0:
    ans=1
elif sum(bingo_3)==0:
    ans=1
elif sum(bingo_4)==0:
    ans=1
elif sum(bingo_5)==0:
    ans=1
elif sum(bingo_6)==0:
    ans=1
elif sum(bingo_7)==0:
    ans=1
elif sum(bingo_8)==0:
    ans=1
else:
    ans=0

if ans==1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	unordered_set<char> x;
	char temp;
	for(int i=0;i!=k;++i){
		cin>>temp;
		x.insert(temp);
	}
	while(true){
		string s=to_string(n);
		bool check=true;
		for(auto i:s){
			if(x.find(i)!=x.end()){
				check=false;
				break;
			}
		}
		if(check){
			cout<<n;
			return 0;
		}
		else
			++n;
	}
}


Measured memory_bytes: 256
import sys
import re

input = sys.stdin.readline
def gets(): return input().strip()
def geti(): return map(int, input().split())
def getf(f): return f(input())
def gi(): return int(input())

n = gi()
minv = 999999

for i in geti():
    v = 0

    while i % 2 == 0:
        i >>= 1
        v += 1

    minv = min(minv, v)

print(minv)


Measured memory_bytes: 3188
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

void dfs(int current, int paint, vector<int> &color, vector<vector<pair<int, int> > > &edges)
{
    if(color[current] != -1){
        return;
    }
    color[current] = paint;
    for(int i = 0; i < edges[current].size(); i++){
        dfs(edges[current][i].first, (paint + edges[current][i].second) % 2, color, edges);
    }
    return;
}

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

    vector<vector<pair<int, int> > > edges(n, vector<pair<int, int> >());

    for(int i = 0; i < n-1 ; i++){
        int u,v,w;
        cin >>u >>v >>w;
        edges[u-1].push_back(make_pair(v-1, w));
        edges[v-1].push_back(make_pair(u-1, w));
    }

    vector<int> color(n, -1);

    dfs(0, 0, color, edges);

    for(int i = 0; i < n; i++){
        printf("%d\n", color[i]);
    }

    return 0;
}

Measured memory_bytes: 8192
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

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

    int N; cin >> N;
    ll H; cin >> H;
    priority_queue<LP> que;
    rep(i, N) {
        ll a, b; cin >> a >> b;
        que.push(LP(a, 1));
        que.push(LP(b, 0));
    }

    int ans = 0;

    while(H > 0) {
        LP lp = que.top(); que.pop();
        if(lp.second == 0) {
            H -= lp.first;
            ans ++;
            continue;
        }
        ll a = lp.first;
        for(; H > 0; ){
            H -= a;
            ans ++;
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
int main(){
	long N, answer = 0;
	vector<long> factor;
	cin >> N;
	for(long i = 1; i <= sqrt(N); i++){
		if(N % i == 0){
			factor.push_back(i);
			factor.push_back(N/i);
		}
	}
	sort(factor.begin(), factor.end());
	long size = factor.size();
	answer = factor[size/2 - 1] + factor[size/2] - 2;
	cout << answer << endl;
}

Measured memory_bytes: 384
import qualified Data.ByteString.Char8 as B
import Data.Char
import Data.List

main :: IO ()
main = do
    [_, m] <- readInts
    as <- readInts
    print $ solve m as

readInts :: IO [Int]
readInts = unfoldr (B.readInt . B.dropWhile isSpace) <$> B.getLine

solve :: Int -> [Int] -> Int
solve m = foldl' (+) 0
    . map (\x -> x * (x - 1) `div` 2)
    . map length
    . group
    . sort
    . map (`mod` m)
    . scanl' (+) 0


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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

LL s1(int I, int O, int J, int L)
{
	LL res = 0;

	res += J / 2 * 2;
	J %= 2;
	res += L / 2 * 2;
	L %= 2;
	res += I / 2 * 2;
	I %= 2;
	if (L && J && I)
	{
		res+=3;
		L--;
		J--;
		I--;
	}

	res += O;

	return res;
}

LL s2(int I, int O, int J, int L)
{
	LL res = 0;

	if (L && J && I)
	{
		res+=3;
		L--;
		J--;
		I--;
	}
	res += J / 2 * 2;
	J %= 2;
	res += L / 2 * 2;
	L %= 2;
	res += I / 2 * 2;
	I %= 2;

	if (L && J && I)
	{
		res+=3;
		L--;
		J--;
		I--;
	}

	res += O;

	return res;
}


int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_Stdio(false); cin.tie(0);

	int I, O, T, J, L, S, Z;
	cin>>I>>O>>T>>J>>L>>S>>Z;

	LL res = max(s1(I, O, J, L), s2(I, O, J, L));

	cout<<res<<endl;

}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

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

	int N,K;
	cin >> N >> K;
	/*int A[100000];
	int tmp;
	for(int i=0; i<N; i++){
		cin >> A[i];
		if(A[i] == 1) tmp = i;
	}*/
	N -= K;
	K--;
	if(N <= 0) cout << 1 << endl;
	else cout << 1 + ceil((double)N/K) << endl;

	return 0;
}



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

int main () {
  int N,K,sum = 0;
  cin >> N >> K;
  for (int i = 0;i < N; i++){
    int x;
    cin >> x;
    if (K - x > x)
      sum += x * 2;
    else
      sum += (K - x)*2;
  }
  cout << sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define SAMPLE 1000000
using namespace std;
using P=pair<int,int>;
using M=map<int,int>;
using ll=long long;
 
int main(){
    int n,m;cin>>n>>m;
    vector<set<int>> edge(n);
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        edge[a-1].insert(b-1);
        edge[b-1].insert(a-1);
    }

    int cnt=0;

    vector<int> path(n-1);
    for(int i=0;i<n-1;i++) path[i]=i+1;
    sort(path.begin(),path.end());
    
    do{
        set<int> visited;
        int now=0;
        visited.insert(0);
        bool able=true;

        for(int i=0;i<n-1;i++){
            int next=path[i];
            if(edge[now].count(next)==1&&visited.count(next)==0){
                now=next;
                visited.insert(next);
            }
            else {
                able=false;
                break;
            }
        }

        if(able) cnt++;
    }while(next_permutation(path.begin(),path.end()));

    cout << cnt << endl;
    
}

Measured memory_bytes: 256
/* Isn't passion overrated?*/

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
vector<vector<ll> >arr;
vector<ll>cost;
vector<ll>ans,out;
void dfs(ll root, ll parent)
{
    bool b = false;
    ll val = -1;
    ll idx = -1;
    vector<ll> :: iterator itr = lower_bound(ans.begin(),ans.end(),cost[root]);
    if(itr == ans.end())
    {
        ans.pb(cost[root]);
    }
    else
    {
        idx = itr - ans.begin();
        val = ans[idx];
        ans[idx] = cost[root];
        b = true;
    }
    out[root] = ans.size();
    for(ll i = 0; i < arr[root].size(); i++)
    {
        if(arr[root][i] == parent)
            continue;
        dfs(arr[root][i],root);
    }
    if(b)
    {
        ans[idx] = val;
    }
    else
    {
        ans.pop_back();
    }
}
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin>>n;
    arr = vector<vector<ll> >(n+1);
    cost = vector<ll>(n+1);
    for(ll i = 1; i <= n; i++)
        cin>>cost[i];
    out = vector<ll>(n+1);
    for(ll i = 0; i < n-1; i++)
    {
        ll a,b;
        cin>>a>>b;
        arr[a].pb(b);
        arr[b].pb(a);
    }
    dfs(1,-1);
    for(ll i = 1; i < out.size(); i++)
        cout<<out[i]<<endl;
    return 0;
}


Measured memory_bytes: 31608
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
ll gcd(ll a,ll b){
    ll m = min(a,b);
    ll M = max(a,b);
    if(M%m==0){
        return m;
    }else{
        return gcd(m,M%m);
    }
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
int main(){
    int n,x;
    cin >> n>>x;
    vector<int> data(n+1);
    rep(i,0,n){
        cin >> data[i];
    }
    data[n]=x;
    sort(data.begin(),data.end());    
    vector<int> diff(n+10);
    rep(i,0,n){
        diff[i]=data[i+1]-data[i];
        //cout<<diff[i]<<endl;
    }
    int now = diff[0];
    rep(i,0,n){
        now = gcd(now,diff[i]);
    }
    cout<<now<<endl;

  return 0;
}

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

void ans(bool f) {
  cout << (f ? "YES" : "NO") << endl;
}

int main() {
  long double x, y;
  while (cin >> x >> y) {
    vector<pair<long long, long long>> in;
    in.push_back(make_pair((long long)(100000.0 * x), (long long)(100000.0 * y)));
    for (int i = 0; i < 3; ++i) {
      cin >> x >> y;
      in.push_back(make_pair((long long)(100000.0 * x), (long long)(100000.0 * y)));
    }

    long long dx1 = in[0].first - in[1].first;
    long long dy1 = in[0].second - in[1].second;
    long long dx2 = in[2].first - in[3].first;
    long long dy2 = in[2].second - in[3].second;

    if (dx1 == 0) {
      ans(dy2 == 0);
      continue;
    } else if (dx2 == 0) {
      ans(dy1 == 0);
      continue;
    } else {
      ans(dy1 * dy2 == dx1 * dx2 * -1);
    }
  }
}

Measured memory_bytes: 3124
H, W = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(H)]
l = []

for h in range(H):
    for w in range(W-1):
        if d[h][w]%2:
            d[h][w+1] += 1
            d[h][w] -= 1
            l.append((h+1, w+1, h+1, w+2))

for h in range(H-1):
    if d[h][W-1]%2:
        d[h][W-1] -= 1
        d[h+1][W-1] += 1
        l.append((h+1, W, h+2, W))

print(len(l))
for i in l:
    print(*i)

Measured memory_bytes: 26660
import java.util.*;

import java.lang.*;

import java.math.*;



public class Main {

	Scanner sc = new Scanner(System.in);

	class taple{

		double x;

		double y;

		taple(double x,double y){

			this.x = x;

			this.y = y;

		}

		taple getRightDir(){

			taple dir = new taple(-y,x);

			taple ret = new taple(0,0);

			ret.x = dir.x/Math.sqrt(dir.x*dir.x+dir.y*dir.y);

			ret.y = dir.y/Math.sqrt(dir.x*dir.x+dir.y*dir.y);

			return ret;

		}

		taple add(taple t){

			return new taple(t.x+x,t.y+y);

		}

	}

	void run(){

		taple[] t= new taple[1001];

		t[0] = new taple(1, 0);

		for(int i = 1; i < 1001; i++){

			t[i] = t[i-1].add(t[i-1].getRightDir());

//			System.out.println(i+" "+t[i-1].getRightDir().x + " "+t[i-1].getRightDir().y);

//			System.out.println(i+" "+t[i].x+" "+t[i].y);

		}

		for(;;){

			int n =sc.nextInt();

			if(n == -1) break;

			System.out.println(t[n-1].x + "\n"+t[n-1].y);

		}

	}

	public static void main(String[] args){

		Main m = new Main();

		m.run();

	}

}

Measured memory_bytes: 12000
import numpy as np
N,K,Q=list(map(int,input().split()))
res=np.array([K-Q for _ in range(N)])
for _ in range(Q):
    i=int(input())
    res[i-1]+=1
for i in res:
    if i>0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 17128
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	int zero = 0, one = 0, two = 0;
	for (int i = 0; i < n; ++i) {
		int num = a[i], cnt = 0;
		if (num % 2 == 0) num /= 2, ++cnt;
		if (num % 2 == 0) ++cnt;

		if (cnt == 2) ++two;
		else if (cnt == 1) ++one;
		else if (cnt == 0) ++zero;
	}
	if (one == 0) cout << (zero <= two + 1 ? "Yes" : "No") << "\n";
	else cout << (zero <= two ? "Yes" : "No") << "\n";
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int inf = 1 << 20;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    cout << max(a-b-b,0) << endl;
}

Measured memory_bytes: 256
n = int(input())
xy_lst = [list(map(int,input().split())) for _ in range(n)]

def distance(x1,y1,x2,y2):
    return ((x1-x2)**2+(y1-y2)**2)**0.5
def add(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer


dis_lst = []
for i in range(n-1):
    for j in range(1,n-i):
        x1 = xy_lst[i][0]
        y1 = xy_lst[i][1]
        x2 = xy_lst[i+j][0]
        y2 = xy_lst[i+j][1]
        dis_lst.append(distance(x1,y1,x2,y2))

average = (n-1)/add(n-1)*sum(dis_lst)
print(average)

Measured memory_bytes: 3064
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 524288
class segtree
{
public:
	int seg[SIZE * 2];
	int flag[SIZE * 2];
	void update(int beg, int end, int node, int lb, int ub, int num)
	{
		if (ub<beg || end<lb)return;
		if (beg <= lb&&ub <= end)
		{
			seg[node] += num;
			flag[node] += num;
			return;
		}
		if (flag[node])
		{
			seg[node * 2] += flag[node];
			seg[node * 2 + 1] += flag[node];
			flag[node * 2] += flag[node];
			flag[node * 2 + 1] += flag[node];
			flag[node] = 0;
		}
		update(beg, end, node * 2, lb, (lb + ub) / 2, num);
		update(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub, num);
		seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
	}
	int get(int beg, int end, int node, int lb, int ub)
	{
		if (ub<beg || end<lb)return -1000000000;
		if (beg <= lb&&ub <= end)
		{
			return seg[node];
		}
		if (flag[node])
		{
			seg[node * 2] += flag[node];
			seg[node * 2 + 1] += flag[node];
			flag[node * 2] += flag[node];
			flag[node * 2 + 1] += flag[node];
			flag[node] = 0;
		}
		return max(get(beg, end, node * 2, lb, (lb + ub) / 2), get(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub));
	}
};
segtree tree;
vector<int>dat[SIZE];
int main()
{
	int num, gen;
	scanf("%d%d", &num, &gen);
	for (int i = 0; i < num; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		dat[za].push_back(zb);
	}
	int maxi = 0;
	for (int i = 0; i < gen; i++)tree.update(1, i + 1, 1, 0, SIZE - 1, -1);
	for (int i = 0; i < gen + 2; i++)
	{
		for (int j = 0; j < dat[i].size(); j++)tree.update(1, dat[i][j], 1, 0, SIZE - 1, 1);
		maxi = max(maxi, tree.get(i + 2, SIZE, 1, 0, SIZE - 1));
 
		tree.update(0, SIZE - 1, 1, 0, SIZE - 1, -1);
	}
	printf("%d\n", max(maxi, num - gen));
}

Measured memory_bytes: 24320
import math

A, B = map(int, input().split())

if A == 0 and B == 0:
  print(0)
  exit()

Amin = A + 0.0
Amax = A + 0.9
Bmin = B + 0.0
Bmax = B + 0.9
priceA = priceB = 0
priceAA = priceBB = 0

priceA = math.ceil(Amin / 0.08)
priceAA = math.ceil(Amax / 0.08)
priceB = math.ceil(Bmin / 0.10)
priceBB = math.ceil(Bmax / 0.10)

ansi = ansj = 0

for i in range(priceA, priceAA+1):
  if i == priceB:
    ansi = i
    break
  if i == priceBB:
    ansi = i
    break

for j in range(priceB, priceBB+1):
  if j == priceA:
    ansj = j
    break
  if j == priceAA:
    ansj = j
    break

#print(priceA, priceAA)
#print(priceB, priceBB)
#print(ansi, ansj)

if ansi == 0 and ansj == 0:
  print(-1)
else:
  if ansi ==0 or ansj == 0:
    print(max(ansi, ansj))
  else:
    print(min(ansi, ansj))


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,j,N) for(int i = (N-1);i >= (j);i--)
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

LL N,K;

int main()
{
    LL ans = 0;
    cin >> N >> K;
    if(K == 0){
        cout << N*N <<endl;
        return 0;
    }
    _rep(b,K+1,N){
        ans += ((N-b+1)/b + 1)*(b-K);
        LL res = ((N-b+1)%b);
        ans += max((LL)0,res-K);
    }
    cout << ans <<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<iomanip>
using namespace std;

int main() {
	string S;
	cin >> S;
	int p=700;
	for(int i=0;i<3;i++){
		if(S[i]=='o'){
			p += 100;
		}
	}
	cout << p << endl;

	return 0;
}


Measured memory_bytes: 256
num=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(num[K-1])

Measured memory_bytes: 3060
#104_C
D,G=map(int,input().split())
Pb=[]
for _ in range(D):
    p,c=map(int,input().split())
    Pb.append((p,c))

Ans=10**4+1

for i in range(2**D):
    score=0
    cnt=0
    max_flg=-1
    for j in range(D):
        p,c=Pb[j]
        if (i>>j)&1:
            score+=p*(j+1)*100+c
            cnt+=p
        else:
            max_flg=j
    
    if score<G:
        if max_flg==-1:
            continue
        if -(-(G-score)//((max_flg+1)*100))>=Pb[max_flg][0]:
             continue
        else:
            cnt+=-(-(G-score)//((max_flg+1)*100))
    
    Ans=min(Ans,cnt)
    #print(Ans)

print(Ans)

Measured memory_bytes: 3188
# -*- coding: utf-8 -*-
import sys

def main():
	sx, sy, tx, ty = map(int, input().split(" "))
	
	ans = []
	
	# 1往復目
	for _ in range(sx, tx):
		ans.append("R")
	for _ in range(sy, ty):
		ans.append("U")
	for _ in range(tx, sx, -1):
		ans.append("L")
	for _ in range(ty, sy, -1):
		ans.append("D")
		
	# 2往復目
	ans.append("D")
	for _ in range(sx, tx+1):
		ans.append("R")
	for _ in range(sy-1, ty):
		ans.append("U")
	ans.append("L")
	
	ans.append("U")
	for _ in range(tx, sx-1, -1):
		ans.append("L")
	for _ in range(ty+1, sy, -1):
		ans.append("D")
	ans.append("R")
	
	print("".join(ans))
	
if __name__ == "__main__":
	main()
	

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

int main() {
    ll N;
    cin >> N;
    vector<double> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    double ave = accumulate(a.begin(), a.end(), 0.0) / N;
    ll ans = -1;
    double min_value = INT_MAX;
    for (ll i = 0; i < N; i++) {
        if (abs(a[i] - ave) < min_value) {
            min_value = abs(a[i] - ave);
            ans = i;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 768
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define in(x, l, r) (ll)(l) <= (x) && (x) < (ll)(r)

int main() {
    char a;
    cin >> a;
    if (in(a,'A','Z'+1)) cout << 'A' << endl;
    else cout << 'a' << endl;
}

Measured memory_bytes: 3592
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 924844033;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll dp[4001][2001][2] = {};
int main() {
	int n, k; cin >> n >> k;
	ll p[2001]; p[0] = 1;
	Rep(i,1, 2001) {
		p[i] = p[i - 1] * (ll)i%MOD;
	}
	int chk;
	dp[0][0][0] = 1;
	int cnt = 0;
	rep(aa, 2) {
		rep(i, k) {
			chk = -1;
			for (int j = i; j < n; j += k) {
				if (i == j)continue;
				rep(l, 2000) {
					(dp[cnt + 1][l][0] += dp[cnt][l][0] + dp[cnt][l][1]) %= MOD;
					(dp[cnt + 1][l + 1][1] += dp[cnt][l][0]) %= MOD;
					if (chk < 0) {
						(dp[cnt + 1][l + 1][1] += dp[cnt][l][1]) %= MOD;
					}
				}
				cnt++; chk = 1;
			}
		}
	}
	ll out = p[n];
	ll res = 0;
	rep1(i,n ) {
		ll csum = p[n - i];
		(csum *= (dp[cnt][i][0] + dp[cnt][i][1])%MOD) %= MOD;
		if (i % 2) {
			(res += csum) %= MOD;
		}
		else {
			(res += MOD - csum) %= MOD;
		}
	}
	(out += MOD - res) %= MOD;
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 125312
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

    int n, a, b;
    cin >> n;

    vector<pair<int, int>> ba(n);
    rep(i, n){
        cin >> a >> b;
        ba[i] = make_pair(b, a);
    }

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

    int time = 0;
    rep(i, n){
        b = ba[i].first;
        a = ba[i].second;

        time += a;
        if(time > b){
            puts("No");
            return 0;
        }
    }
    
    puts("Yes");

    return 0;
}

Measured memory_bytes: 1920
N, K = map(int, input().split())

ans = [False]*N
for i in range(K):
    d = int(input())
    A = list(map(int, input().split()))
    for j in range(len(A)):
        ans[A[j]-1] = True

cnt = 0
for i in range(len(ans)):
    if(ans[i] == False):
        cnt += 1
print(cnt)

Measured memory_bytes: 9220
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <iomanip>

using namespace std;

int main(){
    int A, B, H, M;
    cin >> A >> B >> H >> M;

    double shortStitchAngle;
    double longStitchAngle;
    double betweenTwoStitchAngle;

    double result;

    shortStitchAngle = 2.0 * M_PI * (M / 60.0);
    longStitchAngle = 2.0 * M_PI * ( (H * 60.0 + M) / 720.0);

    betweenTwoStitchAngle = abs(shortStitchAngle - longStitchAngle);
    if(betweenTwoStitchAngle >= M_PI){
        betweenTwoStitchAngle = 2 * M_PI - betweenTwoStitchAngle;
    }

    result = sqrt(A*A + B*B - (2*A*B*cos(betweenTwoStitchAngle)));

/*
    cout << shortStitchAngle << endl;
    cout << longStitchAngle << endl;
    cout << betweenTwoStitchAngle << endl;
*/
    cout << setprecision(20) << result;
    cout << endl;
//    printf("%10.5d\n", result);
    return 0;
}





Measured memory_bytes: 4192
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back

int n, k;
vector<vector<int> > road, G;
vector<int> c, r;

void make_graph(int s){
    vector<int> d(n,1<<30);
    queue<int> q;
    q.push(s);
    d[s]=0;
    while(q.size()){
        int v=q.front();
        q.pop();
        if(d[v]==r[s]) continue;
        rep(j, road[v].size()){
            int to = road[v][j];
            if(d[to]==1<<30){
                q.push(to);
                d[to]=d[v]+1;
                G[s].pb(to);
                //cout<<to<<" ";
            }
        }
    }
    //cout<<endl;
}

int dijkstra(int from, int to){
    struct state {
        int v, d;
        bool operator<(const state& s) const{
            return d>s.d;
        }
    };
    vector<int> d(n,1<<30);
    vector<bool> vis(n,false);
    priority_queue<state> q;
    d[from]=0;
    q.push({from,0});
    while(q.size()){
        state s=q.top();
        q.pop();
        if(d[s.v]<s.d) continue;
        vis[s.v]=1;
        rep(i, G[s.v].size()){
            int to=G[s.v][i];
            int cost=c[s.v];
            if(!vis[to] && d[to]>s.d+cost){
                d[to]=s.d+cost;
                q.push({to,d[to]});
            }
        }
    }
    return d[to];
}

int main(){
    cin>>n>>k;
    road.resize(n);
    G.resize(n);
    c.resize(n);
    r.resize(n);
    rep(i,n){
        int a,b; cin>>a>>b;
        c[i]=a; r[i]=b;
    }
    rep(i,k){
        int a,b; cin>>a>>b;
        road[a-1].pb(b-1);
        road[b-1].pb(a-1);
    }
    rep(i,n) make_graph(i);
    cout << dijkstra(0,n-1) << endl;
}

Measured memory_bytes: 68848
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iomanip>    // fixed, setprecision
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <numeric>    // accumulate
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  double W, H, x, y;
  cin >> W >> H >> x >> y;
  cout << fixed << setprecision(6) << W * H / 2.0;
  cout << " " << (x == W / 2.0 && y == H / 2.0 ? 1 : 0) << endl;
}


Measured memory_bytes: 3216
#include <iostream>

using namespace std;

int n, y;

double func1(double a, double b){
   return a * (1.0 + (double)y * b / 100.0);
}

double func2(double a, double b){
   double t = (1.0 + b / 100.0);
   double r = 1.0;
   for(int i=0;i<y;i++){
      r *= t;
   }
   return a * r;
}

main(){
   while(cin >> n >> y && n){
      double valM = -10000000.0;
      int idx;
      for(int i=0;i<n;i++){
         double a, res;
         int t, b;
         cin >> b >> a >> t;
         if(t == 1){
            res = func1(1.0, a);
            if(valM < res){
               valM = res;
               idx = b;
            }
         }
         if(t == 2){
            res = func2(1.0, a);
            if(valM < res){
               valM = res;
               idx = b;
            }
         }
      }
      cout << idx << endl;
   }

}

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

using namespace std;


const int L = 15; 
const int N = 1<<L; 
int d[L][L];
int ss[L][N];
int dp[N][L];

int n,MSK;

void sub_sum(int i){
    vector<int> pos(n, 0); // [j..0] : + - - - - 
    int sum = 0;
    for (int j = 0; j < n; j++) {
        pos[j] = d[i][j] - sum;
        sum += d[i][j];
    }
    sum = 0;
    // since ...1000 by ...0111 add +---
    for (int msk = 1; msk < MSK; msk++) {
        sum += pos[__builtin_ctz(msk)];
        ss[i][msk] = sum;
    }
}

void solve() {
    int m;
    cin >> n >> m;
    MSK = 1<<n;
    //memset(d, 0x3f, sizeof d);
    for (int _ = 0; _ < m; _++) {
        int x,y,c;
        cin >> x >> y >> c;
        x--;y--;
        d[x][y] = d[y][x] = c;
    }
    for (int i = 0; i < n; i++) {
        d[i][i] = 0;
    }
    for (int i = 0; i < n; i++) {
        sub_sum(i);
    }

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int msk = 1; msk < MSK; msk++) {
        for (int sub = msk; sub; (sub-=1)&=msk) {
            int T = msk^sub;
            for (int j = 0; j < n; j++) {
                if (sub & (1<<j)) {
                    int sum = 0;
                    for (int i = 0; i < n; i++) {
                        if (i!=j && (sub & (1<<i)))
                            sum += ss[i][T];
                    }
                    dp[msk][j] = min(dp[msk][j], dp[sub][j] + sum);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (msk & (1<<i)) continue;
            for (int j = 0; j < n; j++) {
                if ((msk & (1<<j)) && d[i][j]) {
                    dp[msk^(1<<i)][i] = min(dp[msk^(1<<i)][i], dp[msk][j] + ss[i][msk^(1<<j)]);
                }
            }
        }
    }

    //for (int msk = 0; msk < MSK; msk++) {
    //    for (int i = 0; i < n; i++) {
    //        cout << dp[msk][i] << ' ';
    //    }cout << "\n";
    //}
    cout << dp[MSK-1][n-1];
}

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


Measured memory_bytes: 4096
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n;

	scanf("%d", &n);

	int q, r;

	q = n / 100;
	r = n % 100;

	for (int i = 0; i <= q; i++)
	{
		int nq, nr;

		nq = q - i;
		nr = r + 100 * i;

		if (r <= q * 5)
		{
			printf("1\n");

			return 0;
		}
	}

	printf("0\n");

	return 0;
}

Measured memory_bytes: 128