akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ld long double
#define endl "\n"
#define ff first
#define ss second
#define pi pair<ll, ll>
#define PI 3.141592653589793238462643383279502884L
#define mp make_pair
#define pb push_back
#define fall(i, a, b) for (int i = a; i < b; i++)
#define sz(x) (ll) x.size()
#define all(x) x.begin(), x.end()
#define ed cout << "ed";
ll M = 1e9 + 7;
#define int ll


ll poow(ll a, ll b, ll m)
{

    if (b % 2 == 0)
        return (((ll)pow(a, b / 2) % m) * ((ll)pow(a, b / 2) % m)) % m;
    else
        return (((ll)pow(a, (b - 1) / 2) % m) * ((ll)pow(a, (b + 1) / 2) % m)) % m;
}

bool subsum(ll ar[], ll s, ll n)
{
    if (n == 0 && s != 0)
        return false;
    else if (s <= 0)
        return true;

    else if (ar[n - 1] > s)
        return subsum(ar, s, n - 1);
    else
        return (subsum(ar, s - ar[n - 1], n - 1) || subsum(ar, s, n - 1));
}
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l)
    {
        int mid = l + (r - l) / 2;

        if (arr[mid] == x)
            return mid;

        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        return binarySearch(arr, mid + 1, r, x);
    }

    return -1;
}
signed main()
{
    fio;
    bool b=false;
   ll a,i,j;
    cin>>a;
    ll cnt=0;
    for(i=1;i*i<=a;i++)
    {
        if(a%i==0 )
            {
            	if(i*i==a)
            		cnt++;
				else
    				cnt+=2;
    		}
    }


    if(cnt==2)
        cout<<"1";
    else{

    	int f=sqrt(a);
        ll isPrime[f+1]={0};
        isPrime[0]=0;
        isPrime[1]=1;
        for(i=2;i*i<=f;i++)
        {
            if(isPrime[i]==0)
                for(j=i*i;j<=f;j+=i)
                    isPrime[j]=1;
        }
        vector<int> v;
        for(i=2;i<=f;i++)
        {if(isPrime[i]==0)
            v.push_back(i);
        }
         map<int,int> fre;
        for(i=0;i<v.size();i++)
        {
            while(a%v[i]==0)
            {
                fre[v[i]]++;
                a=a/v[i];
            }
        }
        int c=0;
        for(auto i=fre.begin();i!=fre.end();i++)
        {
            int in=1;
            int sum=1;
            while(sum<=(i->second))
            {
            in++;
                c++;
               sum+=in;
            }
        }
        if(a>1)c++;
        cout<<c;
    }
    return 0;
}



Measured memory_bytes: 12096
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#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 repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

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

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

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int H, W;
  cin >> H >> W;
  int N;
  cin >> N;
  int mx = max(H, W);
  int ans = (N + mx - 1) / mx;
  cout << ans << "\n";
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define F first
#define S second 
#define var auto
using namespace std;
typedef long long ll;

int ANS(ll n , deque<int> & beg , deque<int> & ed)
{
	if(n == 1)
	{
		return 0;
	}
	if(n == 2)
	{
		beg.pb(1);
		ed.pb(1);
		return 1;
	}
	if(n % 2)
	{
		int numcol = ANS(n / 2 , beg , ed);
		beg.push_front(numcol + 1);
		ed.push_front(numcol + 1);
		beg.pb(numcol + 2);
		ed.push_front(numcol + 2);
		return numcol + 2;
	}
	else
	{
		int numcol = ANS(n / 2 , beg , ed);
		beg.push_front(numcol + 1);
		ed.push_front(numcol + 1);
		return numcol + 1;
	}
}

int main()
{
	ll n;cin >> n;
	deque<int> beg , ed;
	ANS(n + 1 , beg , ed);
	cout << beg.size() + ed.size() << '\n';

	for(var a : beg)
		cout << a << " ";
	for(var a : ed)
		cout << a << " ";
}



Measured memory_bytes: 3608
H, W = map(int, input().split())
field = []
for _ in range(H):
    tmp = input()
    if tmp.count('#') == 0:
        continue
    else:
        field.append(tmp)
ans_field = ["."] * len(field)
for column in range(W):
    del_flag = True
    for row in range(len(field)):
        if field[row][column] == '#':
            del_flag = False
            break
    if not del_flag:
        for row in range(len(field)):
            ans_field[row] += field[row][column]
for val in ans_field:
    print(val[1:])


Measured memory_bytes: 9156
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b;
  int k;
  cin >> a >> b >> k;
  REP(i,k){
    if(i%2==0){//高橋くん
      if(a%2==1){
        a--;
        a/=2;
        b+=a;
      }
      else{
        a/=2;
        b+=a;
      }
    }
    else{//青木くん
      if(b%2==1){
        b--;
        b/=2;
        a+=b;
      }
      else{
        b/=2;
        a+=b;
      }
    }
  }
    cout << a << " " << b <<endl;
}

Measured memory_bytes: 256
while True:
    H,W = map(int,input().split())
    if H == 0 and W == 0:
        break
    else:
        for i in range(H):
            for j in range(W):
                if i == 0 or i == H -1:
                    print("#",end ="")                 
                else:
                  if j == 0 or j == W -1:
                    print("#",end ="")
                  else:
                    print(".",end ="")  
            print()
        print()


Measured memory_bytes: 7000
#include<bits/stdc++.h>
using namespace std;
int main(){
  int c=0;
	string s,t;
  cin>>s>>t;
  if(s[0]==t[0])
    c++;
if(s[1]==t[1])
    c++;
if(s[2]==t[2])
    c++;
  cout<<c<<endl;
}

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

const int MAX = 1e6 + 10;
const int INF = 1e9;

int dp[2][MAX];

void solve(){
  vector<int> tetra;
  int v = 1, cnt = 2;
  while(v < MAX){
    tetra.push_back(v);
    v = cnt * (cnt+1) * (cnt+2) / 6;
    cnt++;
  }
  for(int i = 0 ; i < MAX ; i++) dp[0][i] = dp[1][i] = INF;
  
  dp[0][0] = dp[1][0] = 0;
  for(int v = 0 ; v <= MAX ; v++){  
    for(int i = 0 ; i < (int)tetra.size() ; i++){
      if(v + tetra[i] > MAX) continue;
      dp[0][v + tetra[i]] = min(dp[0][v+tetra[i]], dp[0][v] + 1);
      if(tetra[i] % 2) dp[1][v + tetra[i]] = min(dp[1][v+tetra[i]], dp[1][v] + 1);
    }
  }
}

int main(){
  solve();
  int N;
  while(cin >> N, N) cout << dp[0][N] << ' ' << dp[1][N] << endl;

  return 0;
}

Measured memory_bytes: 9032
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int y = n/2+n%2;
    double ans = (double)y/n;
    printf("%.7f\n",ans);

    return 0;
}

Measured memory_bytes: 256
import collections
import heapq

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

def construct():
    A_queue = [(-c, x) for x, c in collections.Counter(A).items()]
    heapq.heapify(A_queue)
    index = [None]*(N+1)
    for i, a in enumerate(A):
        if index[a] is None:
            index[a] = i

    B_queue = [(-c, x) for x, c in collections.Counter(B).items()]
    heapq.heapify(B_queue)

    answer = [None]*N

    while B_queue:
        neg_cb, b = heapq.heappop(B_queue)

        neg_ca, a = heapq.heappop(A_queue)
        if a == abs(b):
            if not A_queue: return None
            hold = (neg_ca, a)
            neg_ca, a = heapq.heappop(A_queue)
        else:
            hold = None

        answer[index[a]] = b
        index[a] += 1
        if neg_cb < -1:
            heapq.heappush(B_queue, (neg_cb+1, b))
        if neg_ca < -1:
            heapq.heappush(A_queue, (neg_ca+1, a))
        if hold is not None:
            heapq.heappush(A_queue, hold)
    else:
        return answer

answer = construct()
if answer is None:
    B = [-x for x in B]
    answer = construct()
    if answer is not None:
        answer = [-x for x in answer]

if answer:
    print('Yes')
    print(*answer)
else:
    print('No')


Measured memory_bytes: 185884
def gcd(a,b):
  if a<b:
    a,b=b,a
  if a%b==0:
    return b
  return gcd(b,a%b)
  
N, M = map(int, input().split())
S = input()
T = input()
p = gcd(N, M)
n = N // p
m = M // p
for i in range(p):
  if S[i*n] != T[i*m]:
    print(-1)
    exit()
print((N*M)//p)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#include<numeric>
#include<cstdlib>
#define ll long long int
#define all(x) x.begin(),x.end()
 
 #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
#define v vector<long long int> 
#define vv vector< int> 
#define gcd(m,n) __gcd(m,n)
#define vp vector<pair<long long int ,long long int>>
#define pb push_back
#define mp make_pair
#define pp pop_back
#define iter vector<int>::iterator
#define pa pair<long long int ,long long int> 
#define f(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,n) for (ll i=a ; i<n ;i+=1)
#define fe(d,e) for(auto d:e)
#define mod 1000000007
#define F first
#define S second
#define sett set<long long int>
#define um unordered_map<ll,ll>
# define N 100005LL
using namespace std;

vector<vector<ll>> graph(200005);
ll visited[200005]; 

void dfs(ll node){
    visited[node]=1;
    cout<<node<<" ";
    for (ll u:graph[node]){
        if(!visited[u])dfs(u);
    }
}
auto factor(int n){
    vector <int> ans;
    for (int i=2;i<=sqrt(n);i+=1){
        if (n%i==0){
            if (i==n/i)ans.pb(i);
            else{
                ans.pb(i);
                ans.pb(n/i);
            }
        }
    }
    ans.pb(n);
    return ans;
}
auto solve(){
    string s;
    string t;
    cin>>s>>t;
    v ans;
    f(i,s.length()-t.length()+1){
        ll x=0;
        f(j,t.length()){
            if (t[j]!=s[i+j])x++;


        }
        ans.pb(x);
    }
    cout<<*min_element(all(ans));



}



int main(){
    ll t=1;
    while(t--)
    
        solve();
    }

    

Measured memory_bytes: 7736
S = input()

if len(S) > 9:
    print("NO")
elif "KIH" not in S or "B" not in S or "R" not in S:
    print("NO")
elif ("A" in S and len(set(S)) > 6) or ("A" not in S and len(set(S)) > 5):
    print("NO")
elif S.index("B") > S.index("R") or S.index("B") < S.index("K") or S.index("R") < S.index("K"):
    print("NO")
elif S[:S.index("K")].count("A") > 1 or S[S.index("H"):S.index("B")].count("A") > 1 or S[S.index("B"):S.index("R")].count("A") > 1 or S[S.index("R"):].count("A") > 1:
    print("NO")
else:
    print("YES")
    


Measured memory_bytes: 3064
package main

import (
	"fmt"
	"math"
)

func getAnswer(a, b int) int {
	A := getDigit(a)
	B := getDigit(b)
	if A > B {
		return A
	} else {
		return B
	}
}

func getDigit(num int) int {
	i := 1
	for {
		if num < 10 {
			break
		}
		num = num / 10
		i += 1
	}
	return i
}

var N int

func main() {
	fmt.Scan(&N)
	hoge := int(math.Sqrt(float64(N)))
	for i := hoge; i > 0; i-- {
		if N%i == 0 {
			//			fmt.Println(N/i, i)
			fmt.Println(getAnswer(i, N/i))
			break
		}
	}
}

Measured memory_bytes: 512
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int numeration = in.nextInt();
		
		//create an array
		int[] values = new int[numeration];
		
		for(int i = 0; i < numeration; i++){
			values[i] = in.nextInt();	
		}
		
		in.close();
		
		int maxp = values[1]-values[0];
		int minv = Math.min(values[1], values[0]);
		for(int i = 2; i < numeration; i ++) {
			maxp = Math.max(maxp, values[i] - minv);
			minv = Math.min(minv, values[i]);
				}
		
		System.out.println(maxp);

	}

}



Measured memory_bytes: 100292
<?php
$input = trim(fgets(STDIN));
$input = explode(" ",$input);

if($input[0] > $input[1]){echo'a > b';}
elseif($input[0] < $input[1]){echo'a < b';}
elseif($input[0] == $input[1]) echo'a == b';

?>

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

int main(){
    int x;
    cin >> x;
    int a = x / 1000;
    x = x - a*1000;
    int b = x/100;
    x = x - b*100;
    int c = x/10;
    x = x -c*10;
    int d = x;
    char op1 = '-';char op2 = '-'; char op3 = '-';
    for(int i = 0; i<2; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                if(a+pow(-1,i)*b+ pow(-1, j)*c+ pow(-1,k)*d == 7){
                    if(i == 0){
                        op1 = '+';
                    }
                    if(j == 0){
                        op2 ='+';
                    }
                    if(k == 0){
                        op3 = '+';
                    }
                    printf("%d%c%d%c%d%c%d=7\n",a,op1,b,op2,c,op3,d);
                  	return 0;
                }
            }
        }
    } 
}

  

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

int main(int argc, char const *argv[])
{
    long n, m, k;
    cin >> n >> m >> k;
    vector<long> A(n + 1);
    vector<long> B(m + 1);

    for (long i = 0; i < n; i++)
    {
        cin >> A.at(i);
    }
    for (long i = 0; i < m; i++)
    {
        cin >> B.at(i);
    }

    vector<long> a(n + 1);
    vector<long> b(m + 1);

    long temp_sum = 0;
    for (long i = 0; i <= n; i++)
    {
        a.at(i) = temp_sum;
        temp_sum += A.at(i);
    }

    temp_sum = 0;
    for (long i = 0; i <= m; i++)
    {
        b.at(i) = temp_sum;
        temp_sum += B.at(i);
    }

    long ans = 0;
    long j = m;
    for (long i = 0; i <= n; i++)
    {
        if (a.at(i) > k)
        {
            continue;
        }
        while (a.at(i) + b.at(j) > k)
        {
            j--;
        }
        ans = max(ans, i + j);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 9564
import sys

n = int(input())
al = list(map(int, input().split()))
sys.setrecursionlimit(10 ** 5)


def gcd(a, b):
    if b < a:
        a, b = b, a
    if b % a == 0:
        return a
    else:
        return gcd(a, b % a)


def gcdl(num, n):
    ans = num[0]
    for i in range(n):
        ans = gcd(ans, num[i])
    return ans


print(gcdl(al, n))


Measured memory_bytes: 14224
#include <iostream>
#include <vector>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
int  h, k[100], o[9], u = 0, ans = 0;
#define rep(i,n) for(int i =0;i < n;i++)
int main() {
    cin >> h;
    rep(i, h) {
        cin >> k[i];
        if (k[i] < 400) o[0]++;
        else if (k[i] < 800)o[1]++;
        else if (k[i] < 1200)o[2]++;
        else if (k[i] < 1600)o[3]++;
        else if (k[i] < 2000)o[4]++;
        else if (k[i] < 2400)o[5]++;
        else if (k[i] < 2800)o[6]++;
        else if (k[i] < 3200)o[7]++;
        else o[8]++;
    }
    rep(i, 8) {
        if (o[i] > 0) {
            ans++;
        }
    }
    cout << (ans > 0 ? ans : 1) << " " << (ans + o[8]) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
#define lg 18
//<<fixed << setprecision(9)
int n;
void mul( ll arr[][60], ll brr[][60])
{
    ll m[n][60];
    int i,j,k;
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            m[i][j]=0;
            rep(k,0,n)
            {
                m[i][j]+=arr[i][k]*brr[k][j];
                m[i][j]%=mod;
            }
        }
    }
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            arr[i][j]=m[i][j];
        }
    }
}
void power(ll arr[][60],ll k)
{
    if(k==1) return;
    int i,j;
    ll brr[n][60];
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            brr[i][j]=arr[i][j];
        }
    }
    mul(arr,arr);
    power(arr,k/2);
    if(k%2) mul(arr,brr);
    return;
}
int main()
{
    int i,j,t;
    boost;

    ll k;
    cin>>n>>k;
    ll arr[n][60];
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            cin>>arr[i][j];
        }
    }

    power(arr,k);

    ll ans=0;
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            ans+=arr[i][j];
            ans%=mod;
        }
    }
    cout<<ans;

    return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;


int main(){
  int A,B;
  cin>>A>>B;
  
  if(A==B) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <cstdio>

int main(void)
{
	int n[3], o[3];
	int sum;
	
	for (int i = 0; i < 3; i++){
		sum = 0;
		scanf("%d %d %d %d %d %d", &n[0], &n[1], &n[2], &o[0], &o[1], &o[2]);
		sum = (o[0] * 3600) + (o[1] * 60) + o[2];
//		printf("sum : %d %d %d\n", sum / 3600, sum / 60 % 60, sum % 60);
		sum -= (n[0] * 3600) + (n[1] * 60) + n[2];
		printf("%d %d %d\n", sum / 3600, sum % 3600 / 60, sum % 60);
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <stdio.h>

int main(){
  int n;
  scanf("%d", &n);
  int i = 1;

  for(;i <= n;i++){
    if(i%3 == 0){
      printf(" %d", i);
    }else{
      int temp = i;
      for(;temp >= 3;){
        if(temp%10 == 3){printf(" %d", i); break;}
        else{temp /= 10;}
      }
    }
  }
  printf("\n");
}

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

int main() {

  string S;
  cin >> S;

  int Q;
  cin >> Q;

  // Tの回数
  int countT = 0;

  string mae = "";
  string ushiro = "";

  for (int i = 0; i < Q; i++) {
    int T;
    cin >> T;
    if (T == 1) {
      countT++;
    } else {
      int F;
      cin >> F;
      string C;
      cin >> C;
      if (F == 1) {
        if (countT % 2 == 1){
          ushiro += C;
        } else {
          mae = C + mae;
        }
      } else {
        if (countT % 2 == 1){
          mae = C + mae;
        } else {
          ushiro += C;
        }
      }
    }
  }

  if (countT % 2 == 1) {
    reverse(S.begin(), S.end());
    reverse(mae.begin(), mae.end());
    reverse(ushiro.begin(), ushiro.end());
    cout << ushiro + S + mae << endl;
  } else {
    cout << mae + S + ushiro << endl;
  }

  return 0;

}

Measured memory_bytes: 1360
n, x, y = map(int, input().split())
result = [0]*n
for i in range(1, n):
    for j in range(i+1, n+1):
        a = j - i
        b = abs(i-x) + abs(j-y) + 1
        c = abs(i-y) + abs(j-x) + 1
        result[min(a,b,c)] += 1
for r in result[1:]:
    print(r)

Measured memory_bytes: 3444
N = int(input())
monsters = [int(m) for m in input().split(" ")]
heroes = [int(h) for h in input().split(" ")]

cnt = 0

for i in range(N):
  if monsters[i] <= heroes[i]:
    cnt += monsters[i]
    heroes[i] -= monsters[i]
    monsters[i] = 0
  else:
    cnt += heroes[i]
    monsters[i] -= heroes[i]
    heroes[i] = 0
    
  if heroes[i] != 0:
    if monsters[i + 1] <= heroes[i]:
      cnt += monsters[i + 1]
      heroes[i] -= monsters[i + 1]
      monsters[i + 1] = 0
    else:
      cnt += heroes[i]
      monsters[i + 1] -= heroes[i]
      heroes[i] = 0
      
print(cnt)
    
    

Measured memory_bytes: 25344
#include<stdio.h>
int main(){
  int n,i;
  scanf("%d",&n);
  for(i=3;i<=n;i++){
    if(i%3==0){
      printf(" %d",i);
    }
      else if(i%10==3)printf(" %d",i);
      else if(i/10%10==3)printf(" %d",i);
      else if(i/100%10==3)printf(" %d",i);
      else if(i/1000%10==3)printf(" %d",i);
    }
  printf("\n");       
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b;
    cin>>n>>a>>b;
    cout<<min(a,b)<<" "<<max(0LL,a+b-n);
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
 
	static Scanner scanner;
 
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);
 
        int N=gi();
        int M=gi();
        int X=gi();
        int[] A=new int[M];
        
        int mi=0;
        int ma=0;
        for (int i=0; i<M;i++) {
            int a=gi();
            if(X<a) {
            	ma++;
            } else {
            	mi++;
            }
        }
 
 
	    System.out.println(Math.min(mi, ma));
 
//	    if (isNumber(s1) && isNumber(s2) && s.charAt(a) == '-') {
//	    	System.out.print("Yes");
//	    }else {
//	    	System.out.print("No");
//	    }
 
 
 
	}
 
	public static long d(long n) {
		String a=String.valueOf(n);
		return (long)a.length();
	}
 
	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}
 
	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}
 
	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
 
	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35808
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/

	coding: utf-8
	lang: C (GCC 5.4.1)
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int main(int argc, char const *argv[])
{
	int n;
	char a[103], b[103], c[103];
	int cnt = 0;

	scanf("%d", &n);
	scanf(" %s", a);
	scanf(" %s", b);
	scanf(" %s", c);

	for (int i = 0; i < n; ++i)
	{
		if(a[i] == b[i] && b[i] == c[i])	continue;
		else{
			if(a[i] == b[i] || b[i] == c[i] || c[i] == a[i])	cnt += 1;
			else cnt += 2;
		}
	}
	printf("%d\n", cnt);
	return 0;
}


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

using namespace std;

int main(){
	int n;
	cin >> n;
	vector <int> v(n);
	for(int i=0;i<n;i++)
		cin >> v[i];
	int s=0;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			s+=v[i]*v[j];
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

//素因数
int main(){
	int a;
	char ls;
	int ans=1;
	scanf("%d\n",&a);
	scanf("%c",&ls);

	while(a>1){
		char cr;
		scanf("%c",&cr);
		if(ls==cr){
		}else{
			ans++;
		}
		ls=cr;
		a--;
	}
	printf("%d",ans);
} 

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


using P = complex<long double>;

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n; cin >> n;
  for (int _ = 0; _ < n; ++_) {
    V<P> p(3);
    for (int i = 0; i < 3; ++i) {
      long double x, y; cin >> x >> y;
      p[i] = {x, y};
    }
    P numer = 0;
    for (int i = 0; i < 3; ++i) {
      numer += p[i] * (norm(p[(i + 2) % 3]) - norm(p[(i + 1) % 3]));
    }
    P denom = 0;
    for (int i = 0; i < 3; ++i) {
      denom += p[i] * conj(p[(i + 2) % 3] - p[(i + 1) % 3]);
    }
    P r = numer / denom;
    cout << fixed << setprecision(3) << real(r) << ' ' << imag(r) << ' ' << abs(p[0] - r) << '\n';
  }
}


Measured memory_bytes: 3308
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   a = N//fractions.gcd(N,M)
   b =M // fractions.gcd(N,M)
   # print(a,b)
   for i in range(fractions.gcd(N,M)):
      # print(S[a * i],T[b * i])
      if(S [a * i] != T[b * i]):
         return -1
   else:
      return lcm(N,M)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()


Measured memory_bytes: 5360
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s[ohara];
bool fl;
struct edge{int to,cost;};
map<pair<ll,char>,ll> mp;

//-------------------------↓↓↓↓↓↓------------------------

//------ 自分を天才だと信じる ------

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

    cin>>n;
    rep(i,n)cin>>s[i];
    rep(i,n){
        string co=s[i];
        sort(all(co));
        s[i]=co;
    }
    sort(s,s+n);
    cnt=1;
    rep(i,n-1){
        if(s[i]==s[i+1])cnt++;
        else{
            ans+=(cnt)*(cnt-1)/2;
            cnt=1;
        }
    }
    ans+=(cnt)*(cnt-1)/2;
    Cout(ans);
    return 0;
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
     
#define ll long long
#define loop(i,a,n) for(ll i=a;i<n;++i)
#define revloop(i,a,b) for(ll i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 9999999999999999
#define MOD 1000000007

void func()
{
    ll n,k;
    cin>>n>>k;
    ll a[n+1]={0};
    loop(i,0,k)
    {
        ll d;
        cin>>d;
        loop(j,0,d)
        {
            ll t;
            cin>>t;
            a[t]=1;
        }
    }
    ll ans=0;
    loop(i,1,n+1)
    {
        if(a[i]==0)
            ++ans;
    }
    cout<<ans<<"\n";
}

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

    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r" , stdin);
    // freopen("output.txt", "w" , stdout);
    // #endif

    ll t=1;
    //cin>>t;
    while(t--)
    {
        func();
    }
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = 1LL<<60;
constexpr ll MOD = 1e9+7;
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}

signed main(){

  ll x;
  cin>>x;

  ll now = 100;
  ll cnt=0;
  while(now<x){
    now += now/100;
    cnt++;
  }
  cout<<(cnt)<<endl;
  
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;
constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,v.size())
#define all(v)(v).begin(),(v).end()
#define bit(n)(1ll<<(n))
#define uniq(v)sort(all(v));v.erase(unique(all(v)),v.end())
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
#ifndef LOCAL
struct osd{template<class T>osd&operator<(const T&t){return*this;}template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;template<class...T>void _print(osd&a,T&&...t){}
#define cerr cer_
#endif
template<class T>ostream&operator<(ostream&o,const T&t){return o<<t;}template<class T>istream&operator>(istream&i,T&t){return i>>t;}
void _print(ostream&s){}template<class T,class...U>void _print(ostream&s,T&&t,U&&...u){s<t<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(T&&...t){_print(cout,t...);}template<class...T>void dprint(T&&...t){_print(cerr,t...);}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(auto&&i:v)o<i<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<p.F<' '<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>p.F>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(auto&&i:v)o<i<' ';return o;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>queue<T>&operator<<(queue<T>&q,const T&t){q.push(t);return q;}template<class T>queue<T>&operator<<(T&t,queue<T>&q){t=q.front();q.pop();return q;}
template<class T>deque<T>&operator>>(const T&t,deque<T>&q){q.push_front(t);return q;}template<class T>deque<T>&operator<<(T&t,deque<T>&q){t=q.front();q.pop_front();return q;}
template<class T>deque<T>&operator<<(deque<T>&q,const T&t){q.push_back(t);return q;}template<class T>deque<T>&operator>>(deque<T>&q,T&t){t=q.back(t);q.pop_back();return q;}
template<class T>stack<T>&operator<<(stack<T>&s,const T&t){s.push(t);return s;}template<class T>stack<T>&operator>>(stack<T>&s,T&t){t=s.top();s.pop();return s;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int n,a,b;
    cin>n>a>b;
    cout<min(n*a,b)<endl;
    return 0;
}


Measured memory_bytes: 256
// C.

#include <iostream>
#include <sstream>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <set>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	int x, n, p, ans = -1;
	cin >> x >> n;
	set<int> s;
	for (int i = 0; i < n; ++i) {
		cin >> p;
		s.insert(p);
	}
	for (int i = 0; i <= 101; ++i) {
		if (s.find(i) == s.end()) {
			if (abs(x - i) < abs(ans - x)) {
				ans = i;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3624
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

    def Find_Root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

n,q=map(int,input().split())
uf=UnionFind(n)
l=[list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    p,x,y=l[i][0],l[i][1],l[i][2]
    if not p:
        uf.Unite(x,y)
    else:
        print(1 if uf.isSameGroup(x,y) else 0)



Measured memory_bytes: 24600
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dx[4]={1,0};
int dy[4]={0,1};
int vis[3][102];
int n;
//int dfs(){
//	for(int i=0;i<2;i++)
//		{
//			int x,y;
//			
//		}
//}
int main(){
		while(scanf("%d",&n)!=EOF){
			int mp[3][102];
			
			for(int i=1;i<=2;i++)
				for(int j=1;j<=n;j++){
					cin>>mp[i][j];
					vis[i][j] = mp[i][j];
				}
			
			for(int i=2;i>=1;i--)
				for(int j=n;j>=1;j--)
					{
						if(i == 2&& j ==n) continue;
						for(int k =0 ;k<2;k++)
							{
								int x = i + dx[k];
								int y = j + dy[k];
								if(x>=1&&x<=2&&y>=1&&y<=n){
									if(vis[x][y] + mp[i][j] > vis[i][j]) 
									{
										vis[i][j] = vis[x][y] + mp[i][j];
									}
								}
							}
					}
			cout<<vis[1][1]<<endl;
		}
}

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

N, Y = map(int, input().split())
for i in range(N+1):
    for j in range(N+1-i):
        if 10000 * (N - i - j) + 5000 * j + 1000 * i == Y:
            print(N - i - j , j, i)
            exit()
print(-1, -1, -1)

Measured memory_bytes: 3060
using System;

class S
{
	static void Main()
	{
		var M = 1000000007;
		var k = Console.ReadLine();
		var d = int.Parse(Console.ReadLine());
		var n = k.Length;

		var dp = new long[n + 1, d, 2];
		dp[0, 0, 0] = 1;

		for (int i = 1; i <= n; i++)
		{
			var c = k[i - 1] - '0';

			for (int x = 0; x <= c; x++)
				for (int j = 0; j < d; j++)
					dp[i, (j + x) % d, x == c ? 0 : 1] += dp[i - 1, j, 0];
			for (int x = 0; x <= 9; x++)
				for (int j = 0; j < d; j++)
					dp[i, (j + x) % d, 1] += dp[i - 1, j, 1];

			for (int j = 0; j < d; j++)
			{
				dp[i, j, 0] %= M;
				dp[i, j, 1] %= M;
			}
		}
		Console.WriteLine((dp[n, 0, 0] + dp[n, 0, 1] + M - 1) % M);
	}
}


Measured memory_bytes: 26592
// Problem : I - Coins
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_i
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define maxn 200005
#define ss second
#define ff first
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int inv(int a, int b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
void solve()
{
	int n;
	cin >> n;
	db dp[n+1][n+1];
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	db arr[n+1];
	repe(i,1,n)
		cin >> arr[i];
	rep(i,1,n+1)
		dp[i][0]=(1-arr[i])*dp[i-1][0];
	repe(i,1,n)
	{
		repe(j,1,i)
		{
			dp[i][j] = dp[i-1][j]*(1-arr[i]);
			dp[i][j] += dp[i-1][j-1]*arr[i];
		}
	}
	int cnt = n/2+1;
	db ans = 0;
	repe(i,cnt,n)
		ans += dp[n][i];
	cout<<fixed<<setprecision(15)<<ans ;
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 74072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define rrp(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc() ; !isdigit(tmp) ; tmp = gc())
    key = (tmp == '-');
  for ( ; isdigit(tmp) ; tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int MOD = (int)(1e9 + 7);
inline void Add(int& x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int& x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD;
    b >>= 1;
  }
  return ret;
}
const int N = 5010;
int dp[N][N], n, m, jc[N], ijc[N];
void prework(int sz) {
  jc[0] = 1;
  rep (i, 1, sz) jc[i] = (ll)jc[i-1] * i % MOD;
  ijc[sz] = power(jc[sz], MOD - 2);
  rrp (i, sz-1, 0) ijc[i] = (ll)ijc[i+1] * (i+1) % MOD;
}
int comb(int a,int b) {
  if (b < 0 || a < b) return 0;
  return (ll)jc[a] * ijc[b] % MOD * ijc[a-b] % MOD;
}
int main() {
  read(n), read(m);
  prework(max(n, m));
  dp[n][1] = 1;
  rrp (i, n, 1) {
    int tmp = 0;
    rep (j, 1, m) {
      Add(dp[i-1][j], (ll)(j+1) * dp[i][j] % MOD);
      Add(dp[i-1][j], tmp);
      Add(tmp, (ll)(2 * j) * dp[i][j] % MOD);
    }
  }
  int ans = 0;
  rep (j, 1, m) {
    Add(ans, (ll)dp[0][j] * comb(m - 1, j - 1) % MOD);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 101480
n, m, k = map(int, input().split())
aList = list(map(int, input().split()))
bList = list(map(int, input().split()))
abList = sorted(tuple(zip(aList, bList)), key=lambda x:-x[0])
ans = 0
#dp[y][x] ... y面x個の最大値
dp = [[0] * (m + 1) for _ in range(k + 1)]
for a, b in abList:
    for y in range(k - 1, -1, -1):
        for x in range(m - 1, -1, -1):
            use = min(b, m - x)
            dp[y + 1][x + use] = max(dp[y + 1][x + use], dp[y][x] + use * a)

ans = 0
for y in range(k + 1):
    for x in range(m + 1):
        ans = max(ans, dp[y][x] + m - x)
print(ans)


Measured memory_bytes: 6764
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()

using namespace std;

int N;

void func(int depth, char m, char str[11])
{
	if (depth == N - 1)
	{
		cout << "a" << str << endl;
		return;
	}

	for (char c = 'a'; c <= m + 1; c++)
	{
		str[depth] = c;
		func(depth + 1, max(c, m), str);
	}
}

signed main()
{
	cin >> N;
	char str[11] = {};
	func(0, 'a', str);
}




Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin() (a).end()
 
vector <int> g[2001];
int dis[2001];
int n, x, y;
void bfs(int s){
	bool visited[n+1];
	memset(visited,0,sizeof(visited));
	int distance[n+1];
	memset(distance,0,sizeof(distance));
	queue<int> q;
	q.push(s);
	visited[s] = true;
	while(q.size()!=0){
		int u = q.front();
		q.pop();
		for(int i = 0; i<g[u].size(); i++){
			int v = g[u][i];
			if(visited[v] == false){
				q.push(v);
				visited[v]= true;
				distance[v] = distance[u]+1;
				if(v>s){
					dis[distance[v]]++;
				}
			}
		}
	}
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
	memset(dis,0,sizeof(dis));
	cin >> n >> x >> y;
    for(int i = 1 ;i < n ;i++){
		g[i].pb(i+1);
		g[i+1].pb(i);
	}
	g[x].pb(y);
	g[y].pb(x);
	for(int i =1 ; i < n ; i++)
	    bfs(i);
    for(int i = 1; i< n ;i++)
	    cout<<dis[i]<<"\n";
}

Measured memory_bytes: 384
#! env/bin/local python3
# -*- coding:utf-8 -*-

# -- submit ----
import math

# --- fetch input ---
inputs: list = []
while True:
    try:
        inputs.append(input().strip('\n'))
    except EOFError:
        break

# --- write code below ---
a, b, n = (int(i) for i in inputs[0].split())

if b == 1:
    print(0)
else:
    if n == 1:
        print(math.floor(a * 1 / b) - a * math.floor(1 / b))
    else:
        x = min(b - 1, n)
        print(math.floor(a * x / b) - a * math.floor(x / b))


Measured memory_bytes: 9196
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力を取得
N = int(input())
L = list(map(int, input().split()))

# 求解処理
ans = 0
for L_i, L_j, L_k in itertools.combinations(L, 3):
    if (L_i == L_j) or (L_j == L_k) or (L_k == L_i):
        continue
    if L_i + L_j + L_k > 2 * max(L_i, L_j, L_k):
        ans += 1

# 結果出力
print(ans)


Measured memory_bytes: 8824
//*******Abhijit Burman***********//
//Jalpaiguri Government Engineering College//
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

#define pb push_back
#define mk make_pair
#define MAXX (1000000000000000000+7)
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)




int solve()
{
    ll h,w;
    cin>>h>>w;
    if(h==1 || w==1)
    {
        cout<<1<<endl;
    }
    else{
    cout<<((h*w)%2==0?(h*w)/2:((h*w)/2)+1)<<endl;
    }
}
int main()
{
    fio;

// 	#ifndef ONLINE_JUDGE
//     // for getting input from input.txt
//     freopen("input.txt", "r", stdin);
//     // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
// 	#endif


	
	ll t=1;
	//cin>>t;
	while(t--)
	{
	   
	    solve();
	}
	return 0;
}
    

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

#define all(x) (x).begin(), (x).end()


using namespace std;
void dout() { cerr << endl; }
typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

#define debug(x) cout << #x " = " << (x) << endl

using ll = long long;
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

template <typename T>
void do_uniq(vector<T> vec) {
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}

#define solvsh
//#define multi
#ifdef solvsh

const int MAXN = 2e5 + 20;

void solve() {

    int x;
    cin >> x;
    int n;
    cin >> n;

    set<int> s;

    for (int i = 0; i < n; ++i) {
        int curr;
        cin >> curr;
        s.insert(curr);
    }
    int diff = 0;
    while (1) {
        if (s.count(x - diff) == 0) {
            cout << x - diff;
            return;
        }

        if (s.count(x + diff) == 0) {
            cout << x + diff;
            return;
        }
        ++diff;
    }
}

#else

void solve() {

}

#endif


void multisolve() {

    int t;
    cin >> t;

    int i = 1;
    while (t--) {
//        cout << "Mission #" << (i++) << ": \n";

        solve();
        cout << "\n";
    }
}


#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);


#ifdef multi
    multisolve();
#else
    solve();
    //    gen();
#endif

}


Measured memory_bytes: 3672
using System;

namespace _165d
{
    class Program
    {
static void Main(string[] args)
        {
            long[] ABN = Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // int[] NMQ = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // long K = long.Parse(Console.ReadLine());
            // int[] AB = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int A = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // string A = Console.ReadLine();
            // string B = Console.ReadLine();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(int.Parse);
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // for(int i = 0; i<A_num.Length;i++){
            //     A_num[i] = 0;
            // }
 
            // for(int i = 0; i<NMQ[2];i++){
            //     var read = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            //     for(int j = 0; j< 4;j++){
            //         abcd[i,j] = read[j];
            //     }
            // }
            //NがBより大の時、かつABN[1]-1が0ではない時
            // float x = (ABN[2]>ABN[1])?ABN[1]-1:ABN[2];
            long x = ABN[2];//Nをいれる
            if(ABN[2]>=ABN[1]-1){
                x = ABN[1] -1;
            }
            long res = ABN[0]*x/ABN[1] - ABN[0]*(x/ABN[1]);
            Console.WriteLine(res);
        }
    }
}

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

int main()
{
	string word, sen;
	int i, count;

	cin >> word;
	
	i = 0;
	count = 0;
	while (cin >> sen) {
		if (sen == "END_OF_TEXT")break;

		for (i = 0; i < sen.size(); i++) {
			if ('A' <= sen[i] && sen[i] <= 'Z') {
				sen[i] += 'a' - 'A';
			}
		}
		if (word == sen)count++;
	}
	cout << count << endl;
	
    return 0;
}




Measured memory_bytes: 3212