akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        //var n = int.Parse(Console.ReadLine());
        int[] hwk = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var h = hwk[0];
        var w = hwk[1];
        var k = hwk[2];

        var ans = 0;
        string[] c = new string[h];
        for (int i = 0; i < c.Length; i++)
        {
            c[i] = Console.ReadLine();
        }

        //bit探索(bit全探索)
        for (int x = 0; x < Math.Pow(2, h); x++)
        {
            var array1 = new bool[h];

            // 右からk桁目を取り出す
            for (int s = 0; s < h; s++)
            {
                var y = (x >> s) & 1;
                if (y == 1) array1[s] = true;
            }

            for (int z = 0; z < Math.Pow(2, w); z++)
            {
                var array2 = new bool[w];

                // 右からk桁目を取り出す
                for (int j = 0; j < w; j++)
                {
                    var zz = (z >> j) & 1;
                    if (zz == 1) array2[j] = true;
                }

                var tmp = 0;
                for (int a = 0; a < h; a++)
                {
                    if (array1[a] == true) continue;
                    for (int b = 0; b < w; b++)
                    {
                        if (array2[b] == false)
                        {
                            if (c[a][b] == '#') tmp++;
                        }
                        if (tmp > k) break;
                    }
                    if (tmp > k) break;
                }

                if (tmp == k) ans++;
            }
        }

        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 28732
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int sqr(int x){return x*x;}
int a[SIZE];
int main(){
    DRI(N);
    REP(i,N)RI(a[i]);
    int an=2e9;
    REPP(k,-100,101){
        int me=0;
        REP(i,N){
            me+=sqr(a[i]-k);
        }
        an=min(an,me);
    }
    cout<<an<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define LEN 100000

int max(int arr[], int n){
	int i;
	int m=0;
	for(i=0;i<n;i++){
		if(m<arr[i]){
			m = arr[i];
		}
	}
	return m;
}

int check(int arr[], int m, int n){
	int c;
	int i;
	int a=500000000;
	int p;
	c = m / 2;
	for(i=0;i<n;i++){
		if(a>abs(arr[i]-c)&&arr[i]!=m){
			a = abs(arr[i]-c);
			p = arr[i];
		}
	}
	return p;
}

int main(void){
	int n;
	int arr[LEN];
	int i;
	int m1;
	int m2;
	scanf("%d", &n);
	for(i=0;i<n;i++){
		scanf("%d", &arr[i]);
	}
	m1 = max(arr, n);
	m2 = check(arr, m1, n);
	printf("%d %d", ((m1>m2)?m1:m2), ((m1>m2)?m2:m1));
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
    int N,x; cin >> N >> x;
    vector<int> a(N);
    rep(i,N) cin >> a[i];
    ll ans = 0;
    rep(i,N-1){
        int sum = a[i]+a[i+1];
        if(sum > x){
            int k = sum-x;
            int d = min(k,a[i+1]);
            k -= d;
            a[i+1] -= d;
            ans += d;
            if(a[i+1] == 0){
                ans += k;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;

const ll linf = 1LL << 62;
const int inf = 999999;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

#define Endl endl
#define pr(x) cout << x << endl
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define all(x) x.begin(),x.end()
#define atcoder(int)1e9+7
#define rep(i,n) for(int i = 0;i<n;i++)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)


ll gcd(ll a, ll b) {//最大公約数
	if (a%b == 0)return b;
	else gcd(b, a%b);
}

ll lcm(ll a, ll b) {//最小公倍数
	return (a / gcd(a, b))*b;
}

int  main() {
	
	ll a, b, c,sum =0;
	cin >> a >> b >> c;

	for (int i = 1; i < 10010; i++) {
		sum += a;
		if (sum % b == c) {
			pr("YES");
			return 0;
		}
	}
	pr("NO");

	return 0;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace DailyCP
{
    class cc
    {
        public static void Main()
        {
            //int t =  Convert.ToInt32(Console.ReadLine());
            //for (int T = 0; T < t; T++)
            //{
            int n = Convert.ToInt32(Console.ReadLine());
            //int[] nk = Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
            //int n = nk[0];
            //int k = nk[1];
            Console.WriteLine(2 * 3.141592 * n);
        }
        
    }
}

Measured memory_bytes: 27628
import java.util.*;

public class Main {
    
    static int[] measureDistance(int x,int y,int[] arrx, int[] arry){
        int[] arrDistance = new int[arrx.length];
         for(int i = 0; i < arrx.length; i++) {
            int dx = x - arrx[i];
            int dy = y - arry[i];
            if(dx < 0){
                dx = -1 * dx;
            }
            if(dy < 0){
                dy = -1 * dy;
            }
            arrDistance[i] = dx + dy;
        }
         return arrDistance;
    }
    static int indexOf(int[] a){
        int min = a[0];
        for(int i = 1; i < a.length; i++){
            if(a[i] < min) min = a[i];
        }
        
        int index = 0;
        
        for(int i = 0; i < a.length; i++) {
            if(a[i] == min){
                index = i;
                i = a.length;
            }
        }
        return index;
    } 
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //Number of Students
        int M = sc.nextInt(); //Number of checkpoint
        
        int[] arrStudentsX = new int[N];
        int[] arrStudentsY = new int[N];
        for(int i = 0; i < N; i++) {
            arrStudentsX[i] = sc.nextInt();
            arrStudentsY[i] = sc.nextInt();
        }
        
        int[] arrCheckpointX = new int[M];
        int[] arrCheckpointY = new int[M];
        for(int i = 0; i < M; i++) {
            arrCheckpointX[i] = sc.nextInt();
            arrCheckpointY[i] = sc.nextInt();
        }
        
        int[] result = new int[N];
        for(int i = 0; i < N; i++){
            int x = arrStudentsX[i];
            int y = arrStudentsY[i];
            int[] arr = measureDistance(x,y,arrCheckpointX,arrCheckpointY);
            result[i] = indexOf(arr) + 1;
        }
        
        for(int i = 0; i < N; i++){
            System.out.println(result[i]);
        }
        
    }
    
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long q,h,s,d,n;
  cin >> q >> h >> s >> d >> n;
  cout << min(min(min(q*4*n,h*2*n),s*n),n/2*d+(n%2)*min(min(s,h*2),q*4)) << endl;
}

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

#define IN_NUM 3

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

int main(void) {
  int l[IN_NUM];
  int i;

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

  qsort(l, IN_NUM, sizeof(l[0]), asc);

  printf("%d %d %d\n", l[0], l[1], l[2]);

  return (0);
}



Measured memory_bytes: 2060
from itertools import accumulate

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
As = list(map(int, input().split()))

Ls = [As[-1]] + list(accumulate(As, gcd))
Rs = list(accumulate(As[::-1], gcd))[::-1] + [As[0]]

ans = 0
for i in range(N):
    g = gcd(Ls[i], Rs[i+1])
    ans = max(ans, g)
print(ans)


Measured memory_bytes: 14528
//shara's here
//SPEEEEEEEEEED IS KEEEEEEEEEEY
//REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEAAAAAAAAAAAAAAAAAAAADDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
#include <bits/stdc++.h>
using namespace std;
typedef string s;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18 + 10;
const ll MINF = -(1e18 + 10);
const ll MOD = 1e9 + 7;
#if defined(BANYANYA)
#include "/home/xsharawi/Desktop/cpp/debug.hpp"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define pb push_back
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vll vector<vector<ll> >
#define ins insert
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int main(){
	speed
	s ss; cin >> ss;
	if(ss[2]==ss[3]&&ss[4]==ss[5])cout << "Yes" << endl;
	else cout << "No" << endl;









	
	
	
	






return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/



Measured memory_bytes: 256
N = gets.chomp.to_i
T = gets.chomp.split.map!{|i| i.to_i}
M = gets.chomp.to_i
while p = gets&.chomp&.split&.map!{|i| i.to_i}
  p T.reduce(:+) - T[p[0]-1] + p[1]
end


Measured memory_bytes: 1788
a, b, c = map(int, input().split())

if 0 < a ** 2 + b ** 2 + c ** 2 - 2 * a * b - 2 * b * c - 2 * c * a and c - (a + b) > 0:
    ans = "Yes"
else:
    ans = "No"
print(ans)


Measured memory_bytes: 2940
import sys
input = sys.stdin.readline
x = int(input())
l = [i % 2 == 0 for i in range(100003)]
ans = 1
if x == 2:
    print(2)
    exit()
for i in range(3, 100003):
    if not l[i-1]:
        continue
    elif i >= x:
        print(i)
        break
    for j in range(1, 100003 // i + 1):
        l[i * j - 1] = False
else:
    print(100003)

Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll                long long int
#define ld                long double
#define pb                push_back
#define mk                make_pair
#define in(i,a,n)         for(ll i=0;i<n;++i) cin>>a[i];
#define out(i,a,n)        for(ll i=0;i<n;++i) cout<<a[i]<<" ";
#define sz(c)             (ll)c.size()
#define all(c)            c.begin(), c.end()
#define rall(c)           c.rbegin(), c.rend()
#define loop(i,a,b)       for(ll i=a;i<b;i++)
#define rloop(i,a,b)      for(ll i=a;i>b;i--)
#define F                 first
#define S                 second
#define copy(a,b)         copy(all(a),back_inserter(b));
#define intersect(a,b,w)    set_intersection(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define union(a,b,w)      set_union(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define diff(a,b,w)       set_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define symdiff(a,b,w)    set_symmetric_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define deb(x) cout << #x << " " << x << endl
#define inf INT_MAX
const ll N = 200010;
const ll MOD = 998244353;
ll mod(ll n) {
    return (n % MOD + MOD) % MOD;
}

void solve(){
    string s;
    cin >> s;
    ll dp[2019];
    ll ans = 0;
    fill(dp, dp + 2019, 0);
    dp[s[0] - '0'] = 1;
    for(ll i=1; i<sz(s); i++)
    {
        ll d = s[i] - '0';
        ll temp_dp[2019];
        fill(temp_dp, temp_dp + 2019, 0);
        temp_dp[d] = 1;
        for(ll j=0; j<2019; j++)
        {
            if(dp[j] > 0)
            {
                ll rem = (10 * j + d) % 2019;
                if(rem == 0) ans += dp[j];
                temp_dp[rem] += dp[j];
            }
        }
        for(ll j=0; j<2019; j++)
        {
            dp[j] = temp_dp[j];
        }
    }
    cout << ans;
}

int main(){
    //fin fout
    fast
    ll T = 1; //cin >> T;
    loop(i, 0, T) solve();
    /*#ifdef LOCAL
    clock_t tStart = clock();
    cerr<<fixed<<setprecision(10)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
    #endif*/
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define V vector<ll>
using namespace std;
using ll = long long;


int main(){
    string a,b;
    cin>>a>>b;
    string s=a+b;
    int n=stoi(s);
    bool f=false;
    rep(i,1,2000){
        if(n==i*i) f=true; 
    }
    if(f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main()
{
	int n,x[200000],y[200000],a;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> x[i];
		y[i] = x[i];
	}
	sort(x, x + n);
	for (int i = 0; i < n; i++) {
		if (x[n / 2]<=y[i])cout << x[n / 2 - 1] << endl;
		else cout << x[n / 2] << endl;
	}
    return 0;
}



Measured memory_bytes: 3712
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int comp(const void *p,const void *q){
	return *(int *)p - *(int *)q;
}
int main(){
	int a[100000],b[100000],n,k,x,i,j,ans;
	while(1){
		scanf("%d%d",&n,&k);
		if(n==0 && k==0)break;ans=0;
		memset(b,0,sizeof(int)*(n+1));
		for(i=0;i<k;i++){
			scanf("%d",&x);
			a[i]=x;
			b[x]=1;
		}
		qsort(a,k,sizeof(int),comp);
		for(i=0;i<=n;i++){
			if(i!=0)b[i]=(b[i]+b[i-1])*b[i];
			if(b[i]>ans)ans=b[i];
		}
		for(i=0;i<=n;i++){
			if(b[i]>1){
				for(j=1;j<b[i];j++){
					b[i-j]=b[i];
				}
			}
		}
		if(a[0]==0){
			for(i=0;i<=n;i++){
				if(b[i]==0){
					x=1;
					if(i-1>=0)x+=b[i-1];
					if(i+1<=n)x+=b[i+1];
					if(x>ans)ans=x;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1372
#include<bits/stdc++.h>
using namespace std;
int main(){
	int k,n,i,sum=0;
	scanf("%d %d",&k,&n);
	int a[k];
	for(i=0;i<k;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+k);
	for(i=0;i<n;i++){
		sum+=a[i];
	}
	printf("%d\n",sum);
	  return 0;
  } 

Measured memory_bytes: 3840
#include<iostream>
using namespace std;
int main(){
	int f=0;
	int n=0;
	int a[200];
	int b[200];
	int c[200];
	int t[200];
	int d[200][200];
	int i=0;
	int j=0;
	int k=0;
	int r=0;
	int s=0;
	
	for(i=0;i<200;i++){
		a[i]=0;
		b[i]=0;
		c[i]=0;
		t[i]=0;
		for(j=0;j<200;j++){
			d[i][j]=0;
		}
	}
	cin>>f;
	cin>>n;
	for(i=0;i<f;i++){
		cin>>t[i];
	}
	for(i=0;i<n;i++){
		cin>>a[i];
		cin>>b[i];
		cin>>c[i];
	}
	for(i=1;i<f;i++){
		for(j=0;j<n;j++){
			if(t[i]>=a[j] && b[j]>=t[i]){
				for(k=0;k<n;k++){
					if(t[i-1]>=a[k] && b[k]>=t[i-1]){
						if(c[k]>c[j]){
							r=d[i-1][k]+c[k]-c[j];
						}else{
							r=d[i-1][k]+c[j]-c[k];
						}
					}
					if(d[i][j]<r){
						d[i][j]=r;
					}
					r=0;
				}
			}
		}
	}
	for(i=0;i<n;i++){
		if(s<d[f-1][i]){
			s=d[f-1][i];
		}
	}
	cout<<s<<endl;
}

Measured memory_bytes: 3240
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
	char ch=getchar();int f=0,x=1;
	while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}
	return f*x;
}
int n,k,a[200005],num[200005];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=a[i-1]) sum++;
		num[sum]++;
	}
	sort(num+1,num+sum+1,cmp);
	if(sum<=k) cout<<"0";
	else
	{
		int temp=0;
		for(int i=1;i<=k;i++)
		{
			temp+=num[i];
			
		}
		cout<<n-temp;
	}
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return 1;}return 0;}
template<class T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return 1;}return 0;}

int main() {
  int a,b;
  cin >> a >> b;
  if (a >= 13) cout << b << endl;
  else if (a <= 5) cout << 0 << endl;
  else cout << b / 2 << endl;
}


Measured memory_bytes: 3608
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc.Split(bufio.ScanWords)
    a := nextInt()
    b := nextInt()
    fmt.Printf("%d %d\n", a * b, a*2 + b*2)
}


Measured memory_bytes: 1088
x,y=map(int,input().split())

if x>=0 and y>=0:
  if y>x:
    print(y-x)
    exit()
  else:
    if y==0:
      print(x-y+1)
      exit()
    else:
      print(x-y+2)
      exit()
if x>=0 and y<0:
  if abs(y)>=x:
    print(abs(y)-x+1)
    exit()
  else:
    print(x-abs(y)+1)
    exit()
if x<0 and y>=0:
  if y-abs(x)>=0:
    print(y-abs(x)+1)
    exit()
  else:
    if y==0:
      print(abs(x)-y)
      exit()
    print(abs(x)-y+1)
    exit()
else:
  if x-y<=0:
    print(abs(x-y))
  else:
    print(abs(y-x)+2)

Measured memory_bytes: 3316
#include "bits/stdc++.h"

using namespace std;

typedef long long LL;
typedef unsigned long UL;

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

int main()
{
    int n;
    cin >> n;
    
    vector<pair<int, int>> ab(n), cd(n);
    REP(i, n)
    {
        cin >> ab[i].first >> ab[i].second;
    }
    REP(i, n)
    {
        cin >> cd[i].first >> cd[i].second;
    }

    sort(ab.begin(), ab.end(),greater<pair<int,int>>());
    sort(cd.begin(), cd.end());

    int ans = 0, mj;
    vector<int> used(n, -1);

    REP(i, n)
    {
        mj = -1;
        REP(j, n)
        {
            if (cd[i].first > ab[j].first && cd[i].second > ab[j].second && find(used.begin(), used.end(), j) == used.end() && ab[j].second == max(ab[j].second, mj))
            {
                used[i] = j;
                mj = ab[j].second;
            }
        }

        if (used[i] != -1)
        {
            ++ans;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


while True:

    num_player,num_word = map(int,input().split())
    if num_player == 0 and num_word == 0:
        break

    Q = deque()
    table = [False]*(num_player+1)

    for i in range(1,num_player+1):
        Q.append(i)

    for i in range(1,num_word+1):

        tmp_str = input()
        if len(Q) == 1:
            continue

        player = Q.popleft()

        if i%15 == 0:
            if tmp_str == "FizzBuzz":
                Q.append(player)
        elif i%3 == 0:
            if tmp_str == "Fizz":
                Q.append(player)
        elif i%5 == 0:
            if tmp_str == "Buzz":
                Q.append(player)
        else:
            if tmp_str == "FizzBuzz" or tmp_str == "Fizz" or tmp_str == "Buzz":
                pass
            else:
                if int(tmp_str) == i:
                    Q.append(player)

    while len(Q) > 0:
        table[Q.popleft()] = True

    First = True
    for i in range(1,num_player+1):
        if table[i] == True:
            if First == True:
                print("%d"%(i),end="")
                First = False
            else:
                print(" %d"%(i),end="")
    print()


Measured memory_bytes: 14040
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,k,ans=0;
    cin>>n>>k;
    vector<int> l(n);
    for(int i=0;i<n;i++){
        cin>>l[i];
    }
    sort(l.begin(),l.end());
    for(int i=0;i<k;i++){
        ans+=l[n-1-i];
    }
    cout<<ans;
}

Measured memory_bytes: 256
n = gets.chars.map(&:to_i)+[0]
s = n.size

ans = 0
s.times do |i|
    
    if n[i]<5 or (n[i]==5 and n[i+1]<5)
        ans += n[i]
    else
        ans += 10 - n[i]
        n[i+1] += 1
    end
end

puts ans


Measured memory_bytes: 72348
<?php

fscanf(STDIN, "%d %d %d %d", $A ,$B, $C, $K);

if($A > $K){
  echo $K; 
}else if($A >= $K || $A + $B >= $K){
  echo $A;
}else {
  echo $A - ($K - ($A + $B));
}


Measured memory_bytes: 15952
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MAX 1000005
#define pb push_back
#define vi vector<int>
#define endl '\n'
using namespace std;
// cnt total no. of elements between range from a to b which contains digit d exactly k times
string b;
int k;
vi num;
int dp[128][4][2];		//dp[pos][cnt][f]	f=if number has become less or not 
int call(int pos,int cnt,int f)
{
	if(cnt>k)
		return 0;
	if(num.size()==pos){
		if(cnt==k)
			return 1;
		return 0;
	}
	int limit,res=0;
	
	if(dp[pos][cnt][f]!=-1)
		return dp[pos][cnt][f];
	if(f==0)
		limit=num[pos];
	else
		limit=9;
		
	for(int i=0;i<=limit;i++)
	{
		int nf=f;
		int ncnt=cnt;
		if(i<limit)
			nf=1;
		if(i!=0)
			ncnt++;
		if(cnt<=k)
			res+=call(pos+1,ncnt,nf);
	}
	return dp[pos][cnt][f]=res;
}		

int solve(string b)
{
	num.clear();
	for(int i=0;i<b.length();i++)
	{
		num.pb(b[i]-'0');
	}
	memset(dp,-1,sizeof(dp));
	int res=call(0,0,0);
	return res;
}
signed main()
{
	fastio;
	cin>>b>>k;
	int res=solve(b);
	cout<<res<<endl;
	return 0;
}




Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	while(1){
		int m=1000;
		int ans=0;
		scanf("%d",&n);
		if(n==0) break;
		m-=n;
		while(m>0){
			if(m>=500) m-=500;
			else if(m>=100) m-=100;
			else if(m>=50) m-=50;
			else if(m>=10) m-=10;
			else if(m>=5) m-=5;
			else m--;
			
			ans++;
		}
		
		printf("%d\n",ans);
		
	}
	return 0;
}

Measured memory_bytes: 0
t1,t2 = map(int,input().split())
a1,a2 = map(int,input().split())
b1,b2 = map(int,input().split())
p1 = t1*a1
q1 = t1*b1
p2 = p1+t2*a2
q2 = q1+t2*b2
if p2 == q2:
  print("infinity")
  exit()
if (p1>q1 and p2>q2) or (p1<q1 and p2<q2):
  print(0)
  exit()
x = abs(p1-q1)
y = abs(q2-p2)
if x%y == 0:
  ans = (x//y)*2
else:
  ans = (x//y)*2+1
print(ans)
  

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

long long max(long long A,long long B){
    return A>B?A:B;
}

long long min(long long A,long long B){
    return A<B?A:B;
}

int main(void){
    long long n,l,sum=0,eat=1e9;
    scanf("%lld%lld",&n,&l);
    for (int i=0; i<n; i++){
        long long apple=l+i;
        if (llabs(apple)<llabs(eat)){
            eat=apple;
        }
        sum+=apple;
    }
    printf("%lld\n",sum-eat);
    return 0;
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int64_t> A(N);
    vector<int64_t> D;
    struct map{
        int b;
        int64_t c;
    };
    vector<map> bc;
    int64_t answer = 0;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        A.at(i) = a;
    }
    sort(A.begin(), A.end());
    for(int i=0;i<M;i++){
        int b;
        int64_t c;
        cin >> b >> c;
        bc.push_back({b, c});
    }
    sort(bc.begin(), bc.end(), [](const map& x, const map& y) { return x.c > y.c;});
    int count = 0;
    bool flag = false;
    for(auto i = bc.begin(); i != bc.end(); ++i){
        for(int j=0; j< i->b; j++){
            if(count == N){
                flag = true;
                break;
            }
            D.push_back(i->c);
            count++;
        }
        if(flag){
            break;
        }
    }
    for(int i=0;i<count;i++){
        if(A.at(i) >= D.at(i)){
            break;
        }
        A.at(i) = D.at(i);
    }
    for(int i=0;i<N;i++){
        answer += A.at(i);
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 4464
a,b = map(int, input().split())

if min(a,b)<0 and max(a,b)>0:
    print("Zero")
    exit()
if min(a,b)>0:
    print("Positive")
    exit()


c = -min(a,b) - max(a,b) + 1

if c%2==0:
    print("Positive")
else:
    print("Negative")

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

using namespace std;

int main() {  
  string S;
  cin >> S;
  int res = 0;
  int tmp = 0;
  for (size_t i = 0; i < 3; ++i) {
    if (S[i] == 'R') {
      ++tmp;
    } else {
      tmp = 0;
    }
    res = max(res, tmp);
  }
  cout << res << endl;

  return 0;
}


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

using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	ll mult=1ll;
	ll m18 = 1ll;
	for (int i=0;i< 18;i++) {
		m18 *= 10;
	}

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

	for (int i=0;i<n;i++) {
		if (a.at(i) == 0ll){
			cout << 0 << endl;
			return 0;
		}
	}
	for (int i=0;i<n;i++) {
		if (a.at(i) <= m18/mult) {
			mult *= a.at(i);
		} else {
			cout << "-1" << endl;
			return 0;
		}

	}
	cout << mult << endl;
	return 0;
}


Measured memory_bytes: 4060
#include <stdio.h>

int main(void)
{
	int i, j;
	int num[10];
	char str[11];
	
	while (scanf("%s", str) != EOF){
		i = 0;
		while (str[i] != '\0'){
			num[i] = str[i] - 0x30;
			i++;
		}
	
		for (i = 9; i > 0; i--){
			for (j = 0; j < i; j++){
				num[j] = (num[j] + num[j + 1]) % 10;
			}
		}
		printf("%d\n", num[0]);
	}
	
	return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
int main() {
    int h, w;
    scanf("%d%d", &h, &w);
    string s[50];
    for (auto i = 0; i < h; i++) cin >> s[i];
    bool flag = true;
    for (auto i = 0; i < h; i++) {
        for (auto j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                if (i - 1 >= 0 && s[i-1][j] == '#') continue;
                if (i + 1 < h && s[i+1][j] == '#') continue;
                if (j - 1 >= 0 && s[i][j-1] == '#') continue;
                if (j + 1 < w && s[i][j+1] == '#') continue;
                flag = false;
                break;
            }
        }
    }
    puts(flag ? "Yes" : "No");
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))


Measured memory_bytes: 318300
n = int(input())
options = []
x = 6
while x <= n:
    options.append(x)
    x *= 6
x = 9
while x <= n:
    options.append(x)
    x *= 9
dp = list(range(n + 1))
for opt in options:
    for i in range(n - opt + 1):
        dp[i + opt] = min(dp[i + opt], dp[i] + 1)
print(dp[-1])


Measured memory_bytes: 6900
A, B, C, X, Y = map(int, input().split())

p1 = 2 * C * min(X, Y) + A * (X - min(X, Y)) + B * (Y - min(X, Y))
p2 = 2 * C * max(X, Y)
p3 = A * X + B * Y
print(min(p1, p2, p3))

Measured memory_bytes: 9184
MOD = 10**9 + 7
m = 666666 + 500
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMBinitialize(m)


def main():
    X, Y = (int(i) for i in input().split())
    if (X+Y) % 3 != 0:
        return print(0)
    ans = COMB((X+Y)//3, X - (X+Y)//3)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 79768
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MAX 300003
#define MOD 998244353

long long modpow(long long a,long long n,long long mod){
  long long res=1;
  while(n>0){
    if(n&1){       //nのbitと...00001を比較  nが2で割り切れるならtrue
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    n>>=1;
  }
  return res;
}

long long modinv(long long a,long long mod){
  return modpow(a,mod-2,mod);
}

long long fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<MAX;i++){
    fac[i]=(fac[i-1]*i)%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

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

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

  COMinit();

  ll ans=0;
  for(ll i=0;i<=N;i++){
    if(A*i>K){
      break;
    }
    if((K-A*i)%B!=0){
      continue;
    }
    ll j=(K-A*i)/B;
    ans+=COM(N,i)*COM(N,j)%MOD;
    ans%=MOD;
  }
  cout<<ans<<endl;
}


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

using namespace std;

const int oo = 1e9 + 7;
const int N = 2e5 + 1;
vector <int> g[N];
int d[N];
queue <int> q;

void bfs(int v) {
	fill(d, d + N, oo);
	d[v] = 0;
	q.push(v);
	while (q.size()) {
		v = q.front();
		q.pop();
		for (auto x : g[v])
			if (d[v] + 1 < d[x]) {
				d[x] = d[v] + 1;
				q.push(x);
			}
	}
}

main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs(0);
	if (d[n - 1] <= 2)
		return cout << "POSSIBLE" << endl, 0;
	cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 13168
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

int main()
{
	string S, T;
	cin >> S >> T;

	int count = 0;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] == T[i]) {
			count++;
		}
	}

	cout << count << endl;

}






Measured memory_bytes: 3648
#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 1'000'000'007;

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

int mul(int a, int b) {
  return (int)((long long)a * b % mod);
}

int pw(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b % 2 == 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return res;
}

char s[100'009];

int main() {
  scanf("%s", s);
  int n = (int)strlen(s);
  int cnt = 0;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '1') {
      add(ans, mul(pw(2, cnt), pw(3, n - i - 1)));
      ++cnt;
    }
  }
  add(ans, pw(2, cnt));
  printf("%d\n", ans);
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int n, k, c, a[200000];
string s;
int mini[200000], maxi[200000];
int main() {
  cin >> n >> k >> c;
  cin >> s;
  maxi[0] = -1;
  set<pair<int, int> > sl, sr;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'o') {
      a[i] = 1;
      maxi[i] = i;
    } else if (i == 0) {
      maxi[i] = -1;
    } else {
      maxi[i] = maxi[i - 1];
    }
  }
  mini[n - 1] = n;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == 'o') {
      mini[i] = i;
    } else if (i == n - 1) {
      mini[i] = n;
    } else {
      mini[i] = mini[i + 1];
    }
  }
  int cnt = 0;
  int p = 0;
  while (a[p] == 0) {
    p++;
  }
  cnt++;
  sl.insert({p + 1, 1});
  while (cnt < k) {
    sl.insert({mini[p + c + 1] + 1, cnt + 1});
    p = mini[p + c + 1];
    cnt++;
  }
  cnt = 1;
  p = n - 1;
  while (a[p] == 0) {
    p--;
  }
  sr.insert({p + 1, k});
  while (k - cnt) {
    p = maxi[p - c - 1];
    sr.insert({p + 1, k - cnt});
    cnt++;
  }
  decltype(sl)::iterator it = sl.begin();

  while (it != sl.end()) {
    pair<int, int> aaa = *it;
    if (sr.find(*it) != sr.end()) {
      printf("%d\n", aaa.first);
    }
    it++;
  }
  printf("\n");
}

Measured memory_bytes: 22788
h = 1
w = 1
while True:
	nums = list(map(int, input().split(" ")))
	h = nums[0]
	w = nums[1]
	if h == 0 and w == 0:
		break

	for i in range(h):
		for j in range(w):
			print("#", end="")
		print("")
	
	print("")


Measured memory_bytes: 7016
import heapq as q
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ans = 0

v = []
q.heapify(v)

ab.sort()
i = 0
for j in range(m):
  while True:
    if i >= n:
      break
    a, b = ab[i]
    if a > j + 1:
      break
    q.heappush(v, -b)
    i += 1
  if v:
    ans -= q.heappop(v)
print(ans)

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

int main(){
    string s,t,u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if(u==s){
        a--;
    }
    else{
        b--;
    }

    cout << a << ' ' << b << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
def deque_divisor(n):
    d = deque()
    for i in range(int(n**(1/2)),0,-1):
        if i**2 == n:
            d.append(i)
            continue
        if n % i == 0:
            d.appendleft(i)
            d.append(n//i)
    return d

n = int(input())

candidate = (set(deque_divisor(n)) | set(deque_divisor(n-1)))
candidate.discard(1)

ans = 0

for i in candidate:
    k = n
    while k % i == 0:
        k //= i
    k %= i
    if k == 1:
        ans += 1

print(ans)

Measured memory_bytes: 4328
import System.Environment
import Data.Maybe
import Data.List
import Control.Exception

main :: IO ()
main = do
  isTest <- getEnv "TEST" `catch` (\(SomeException _) -> return "")
  if isTest == "1"
    then do
      testFile <- readFile "tests"
      putStrLn $ tests testFile
    else do
      input <- getContents
      putStrLn $ trim (solve (trim input))

--処理
solve :: String -> String
solve s =
  show $ ((sum.) . ((t:).) . (fmap ((min t) . (\(a, b) -> a - b)).) . zip)
    (drop 1 list)
    list
  where (n:t:list) = fmap read (words s) :: [Int]

tests :: String -> String
tests text = case testParse text of
  Right bodys -> unlines (fmap (\(i, body) -> test i body) (zip [1 ..] bodys))
  Left  msg   -> "Test file parse error:" ++ msg

test :: Int -> (String, String) -> String
test n (input, outputRight)
  | output == outputRight
  = header ++ "Passed"
  | otherwise
  = header
    ++ "Faild\n"
    ++ "Right:"
    ++ show outputRight
    ++ "\nOutput:"
    ++ show output
 where
  header = "test" ++ show n ++ ":"
  output = trim $ solve input

testParse :: String -> Either String [(String, String)]
testParse s = case lines s of
  (sp1:sp2:bodys) -> testBodysParse sp1 sp2 bodys
  _               -> Left "testParse"

testBodysParse
  :: String -> String -> [String] -> Either String [(String, String)]
testBodysParse sp1 sp2 = (traverse . testBodyParse) sp2 . (split sp1)

testBodyParse :: String -> [String] -> Either String (String, String)
testBodyParse sp body = case fmap (trim . unlines) (split sp body) of
  [input, output] -> Right (input, output)
  _               -> Left "testBodyParse"

split :: Eq a => a -> [a] -> [[a]]
split spratar = foldr f [[]]
 where
  f x (p:ps) | x == spratar = [] : p : ps
             | otherwise    = (x : p) : ps
  f _ _ = undefined

trimHead :: String -> String
trimHead = dropWhile (\s -> isJust (elemIndex s [' ', '\t', '\n', '\r']))

trim :: String -> String
trim = reverse . trimHead . reverse . trimHead

Measured memory_bytes: 140540
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

typedef long long ll;

const int N=1<<14,M=205,P=998244353,G=3;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }
void upd(int &x,int k){ x=add(x,k); }
int pwr(int a,int k){ 
	int res=1;
	for(;k;k>>=1,a=mul(a,a))
		if(k&1)res=mul(res,a);
	return res;
}

int n,m,ans,fac[N],inv[N];

int C(int n,int m){
	if(n<0||m>n)return 0;
	return mul(fac[n],mul(inv[m],inv[n-m]));
}

void ntt(int n,int *x,int f){
	for (int i=0,j=0;i<n;++i){
		if(i<j)swap(x[i],x[j]);
		for(int l=n>>1;(j^=l)<l;l>>=1);
	}
	for(int s=2;s<=n;s<<=1){
		int m=s>>1;
		for(int j=0;j<n;j+=s){
			int wn=pwr(G,(P-1)/s),w=1;
			if(f==-1)wn=pwr(wn,P-2);
			lop(k,0,m){
				int z=mul(x[j+m+k],w);
				x[j+m+k]=sub(x[j+k],z);
				x[j+k]=add(x[j+k],z);
				w=mul(w,wn);
			}
		}
	}
	if(f==-1){
		int y=pwr(n,P-2);
		lop(i,0,n)x[i]=mul(x[i],y);
	}
}

void mul(int n,int *a,int m,int *b,int *c){
	static int A[N],B[N];
	int p=1;
	while(p<n+m-1)p<<=1;
	lop(i,0,n)A[i]=a[i]; lop(i,n,p)A[i]=0;
	lop(i,0,m)B[i]=b[i]; lop(i,m,p)B[i]=0;
	ntt(p,A,1),ntt(p,B,1);
	lop(i,0,p)c[i]=mul(A[i],B[i]);
	ntt(p,c,-1);
}
	
int f[N],ff[N],tr[N],g[N];

void dp(){
	rep(i,0,n){
		tr[i]=inv[i+2];
		ff[i]=mul(f[i],inv[i]);
	}
	tr[0]=0;
	mul(n+1,ff,n+1,tr,g);
	rep(i,0,n)g[i]=mul(g[i],fac[i+2]);
	rep(i,0,n)g[i]=add(g[i],mul(f[i],add(1,C(i+1,2))));
	rep(i,0,n)f[i]=g[i];
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	freopen("my.out","w",stdout);
#endif
	cin>>n>>m;
	fac[0]=1; lop(i,1,N)fac[i]=mul(fac[i-1],i);
	inv[1]=1; lop(i,2,N)inv[i]=mul(P-P/i,inv[P%i]);
	inv[0]=1; lop(i,1,N)inv[i]=mul(inv[i],inv[i-1]);

	f[0]=1;
	lop(k,0,m)dp();

	rep(k,0,n)ans=add(ans,mul(C(n,k),f[k]));
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i<x;i++)
bool f[4005][4005];
int x1[1005],y1[1005],x2[1005],y2[1005],w,h,n;
int main()
{
	srand((unsigned int)time(NULL));
	while(1)
	{
		vector<int>x,y;
		scanf("%d %d %d",&w,&h,&n); if(!w) return 0;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&x1[i]);
			scanf("%d",&y1[i]);
			scanf("%d",&x2[i]);
			scanf("%d",&y2[i]);
			x.pb(x1[i]);
			if(x1[i]) x.pb(x1[i]-1);
			x.pb(x2[i]-1);
			if(x2[i]!=w) x.pb(x2[i]);
			y.pb(y1[i]);
			if(y1[i]) y.pb(y1[i]-1);
			y.pb(y2[i]-1);
			if(y2[i]!=h) y.pb(y2[i]);
		}
		x.pb(0); x.pb(w-1);
		y.pb(0); y.pb(h-1);
		sort(x.begin(),x.end());
		sort(y.begin(),y.end());
		x.erase(unique(x.begin(),x.end()),x.end());
		y.erase(unique(y.begin(),y.end()),y.end());
		for(int i=0;i<x.size();i++)
		{
			for(int j=0;j<y.size();j++)
			{
				f[i][j]=false;
			}
		}
		for(int i=0;i<n;i++)
		{
			int a=lower_bound(x.begin(),x.end(),x1[i])-x.begin();
			int b=lower_bound(x.begin(),x.end(),x2[i]-1)-x.begin();
			int c=lower_bound(y.begin(),y.end(),y1[i])-y.begin();
			int d=lower_bound(y.begin(),y.end(),y2[i]-1)-y.begin();
			for(int j=a;j<=b;j++)
			{
				for(int k=c;k<=d;k++)
				{
					f[j][k]=true;
				}
			}
		}
		int ret=0;

		for(int i=0;i<x.size();i++)
		{
			for(int j=0;j<y.size();j++)
			{
				if(!f[i][j])
				{
					ret++;
					queue<P>que;
					que.push(mp(i,j));
					while(!que.empty())
					{
						P p=que.front();que.pop();
						if(f[p.f][p.s]) continue;
						f[p.f][p.s]=true;
						int dx[4]={0,1,0,-1};
						int dy[4]={1,0,-1,0};
						for(int k=0;k<4;k++)
						{
							int nx=p.f+dx[k];
							int ny=p.s+dy[k];
							if(!(0<=nx && nx<x.size())) continue;
							if(!(0<=ny && ny<y.size())) continue;
							if(f[nx][ny]) continue;
							que.push(mp(nx,ny));
						}
					}
				}
			}
		}
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 5328
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;



void chmax(ll &a,ll b) {
	if (a < b)a = b;
}

bool prime(int n) {
	if (n == 1) {
		return false;
	}
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	int n, c;
	cin >> n >> c;
	vector<vector<int>>data(c, vector<int>(101010,0));

	rep(i, 0, n) {
		int s, t, c;
		cin >> s >> t >> c;
		c--, s--;
		data[c][s]++;
		data[c][t]--;
	}



	rep(i, 0, c) {
		rep(j, 1, 101010) {
			data[i][j] += data[i][j - 1];
		}
	}

	rep(i, 0, c) {
		rep(j, 1, 101010) {
			if (data[i][j] > 1)data[i][j] = 1;
		}
	}

	int ans = 0;
	rep(j, 0, 101010) {
		int temp = 0;
		rep(i, 0, c) {
			temp += data[i][j];
		}
		ans = max(ans, temp);
	}

	cout << ans << endl;

	
	return 0;
}

Measured memory_bytes: 14196
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 11100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
long long p[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lld",p+i);
		if(p[i]==0){
			printf("0\n");return 0;
		}
	}
	__int128 ret=1;
	for(int i=0;i<a;i++){
		ret*=p[i];
		if(ret>(mod-7)*(mod-7)){
			printf("-1\n");return 0;
		}
	}
	printf("%lld\n",(long long)ret);

}

Measured memory_bytes: 2484
#include <iostream>
#include <vector>
#include <climits>
#include <functional>

using namespace std;

template<typename T>
struct segment_tree {
    using F = function<T(T, T)>;

    int n;
    vector<T> node;
    F merge;
    T identity;

    segment_tree(int n, F merge, T identity)
        : n(n), node(n<<1, identity), merge(merge), identity(identity) {}

    T operator[](int i) { return node[i + n]; }

    void set(int i, T x) {
        node[i += n] = x;
        while (i >>= 1) node[i] = merge(node[i<<1|0], node[i<<1|1]);

    }

    T fold(int l, int r) {
        T res = identity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = merge(res, node[l++]);
            if (r & 1) res = merge(node[--r], res);
        }
        return res;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    auto merge = [](int a, int b) { return a + b; };
    segment_tree<int> seg(n, merge, 0);
    while (q--) {
        int com, x, y;
        cin >> com >> x >> y;
        x--;
        if (com) cout << seg.fold(x, y) << '\n';
        else seg.set(x, seg[x] + y);
    }
}



Measured memory_bytes: 3628
#include<stdio.h>
int linear(int A[],int n,int key){
    int i=0;
    A[n]= key;
    while(A[i]!=key)i++;
    return i !=n ;
}
int main(){
    int a,b,num=0,i,j,key,l,n,q,S[10000+1];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&S[i]);
    }
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&key);
        if( linear(S,n,key) )num++;
    }
    printf("%d\n",num);
      return 0;
    }


Measured memory_bytes: 2108