akhauriyash/Code-Regression huggingface dataset:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def divi(n):
    ans = {1}
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ans |= l[i]
            ans |= l[n//i]
    ans.add(n)
    return ans

n = N()
cnt = 1
l = [{} for _ in range(n)]
l[1] = {1}
tab = [0]*(n+1)
for i in range(1,n+1):
    for j in range(i, n + 1, i):
        tab[j] += 1
tab[n]=0
print(sum(tab))

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


int main(){
  int n,k;cin>>n>>k;
  int h[n],b[n],mi;
  for (int i=0;i<n;i++)
      cin>>h[i];
  int mat[n][k];
  for (int i=0;i<k;i++)
     mat[0][i]=0;
  b[0]=0;
  for (int i=1;i<n;i++){
    mi=INT_MAX;
    for (int j=0;j<k;j++){
       if (j<i){
         mat[i][j]=b[i-j-1]+abs(h[i]-h[i-j-1]);
         mi=min(mi,mat[i][j]);}
       else
         mat[i][j]=0;  
    }
     b[i]=mi;
  }
  
  cout<<b[n-1]<<endl;
  
  
  
  
  
  
return 0;  
}

Measured memory_bytes: 40064
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  6 23:39:24 2020

@author: liang
"""
#from scipy.special import comb

counter = [0]*2019
counter[0] = 1 # 0 = 0 (mod 2019)

S = input()
tmp = 0
"""
#大きい数を一気に掛けない
for i in range(1,len(S)+1):
    tmp += int(S[-i])*10**(i-1)    #スライスの方が早い（けど、漸化式的に累積和を出せ）
    #print(tmp%2019)
    tmp %= 2019                    #大きい数を割るな
    counter[tmp%2019] += 1

ans = 0
for i in range(2019):
    if counter[i] >= 2:
        #ans += comb(counter[i], 2, exact=True)
        ans += counter[i]*(counter[i]-1)//2
print(ans)
"""
MOD = 2019
#reversed(s) ?
t = 1
for i in range(1,len(S)+1):
    tmp += int(S[-i])*t
    #print("A", tmp)
    tmp %= MOD 
    t *= 10
    #print("B", tmp)
    t %= MOD
    #print(tmp)
    counter[tmp] += 1
    
print(sum(i*(i-1)//2 for i in counter))
      

Measured memory_bytes: 9272
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>

using namespace std;

int main(){

	int k,s,count=0;
	cin >> k >> s;

	for(int i = 0; i <= k; i++){
		for(int j = 0; j <=k; j++){
			if(s-i-j >= 0 && s-i-j <= k){
				count ++;
			}
		}
	}
	cout <<count << endl;

	return 0;
}

Measured memory_bytes: 256
n,*a=map(int,open(0).read().split())
c=0
while 1:
  m=max(a)
  if m<n:break
  t,f=m//n,1
  c+=t
  for i,b in enumerate(a):
    if b==m and f:
      a[i]%=n
      f=0
    else:
      a[i]+=t
print(c)

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

using namespace std;

int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(20);


    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0, max = 0, p_max = 0;
    for(int i = 0; i < n; i++){
        cnt += (s[i] == 'W') ? -1 : 1;
        if(cnt > max){
            max = cnt;
            p_max = i;
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(i<p_max) ans += s[i] == 'W';
        else if(i>p_max) ans += s[i] == 'E';
    }
    cout << ans << endl;
}
    

Measured memory_bytes: 720
n, k = [int(i) for i in input().split(' ')]
input_list = [int(i) for i in input().split(' ')]
 
maximum = sum(input_list[:k])
s = sum(input_list[:k])
for i in range(1, n-k+1):
  s = s - input_list[i-1] + input_list[i+k-1]
  maximum = max(maximum, s)

print( (maximum + k) / 2 )

Measured memory_bytes: 71520
package main

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

// Scan Standard Input
var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

type Dice struct {
	one   string
	two   string
	three string
	four  string
	five  string
	six   string
}

func (d *Dice) opN() *Dice {
	tmp := d.one // copy

	d.one = d.two
	d.two = d.six
	d.six = d.five
	d.five = tmp

	return d
}

func (d *Dice) opE() *Dice {
	tmp := d.one // copy

	d.one = d.four
	d.four = d.six
	d.six = d.three
	d.three = tmp

	return d
}

func (d *Dice) opS() *Dice {
	tmp := d.one // copy

	d.one = d.five
	d.five = d.six
	d.six = d.two
	d.two = tmp
	return d
}

func (d *Dice) opW() *Dice {
	tmp := d.one // copy

	d.one = d.three
	d.three = d.six
	d.six = d.four
	d.four = tmp
	return d
}

func main() {

	n, _ := strconv.Atoi(nextLine())

	base := strings.Split(nextLine(), " ")
	// create two dices
	base_dice := &Dice{base[0], base[1], base[2], base[3], base[4], base[5]}

	for i := 1; i < n; i++ {
		nums := strings.Split(nextLine(), " ")

		if reflect.DeepEqual(base, nums) {
			fmt.Println("No")
			return
		}

		dice := &Dice{nums[0], nums[1], nums[2], nums[3], nums[4], nums[5]}

		// dice2を回転させてdice1になるかチェック
		detectTop(base_dice, dice)
		detectFront(base_dice, dice)

		if base_dice.one == dice.one &&
			base_dice.two == dice.two &&
			base_dice.three == dice.three &&
			base_dice.four == dice.four &&
			base_dice.five == dice.five &&
			base_dice.six == dice.six {
			fmt.Println("No")
			return
		}
	}

	fmt.Println("Yes")
}

func detectTop(dice1, dice2 *Dice) {
	switch dice1.one {
	case dice2.two:
		dice2.opN()
	case dice2.three:
		dice2.opW()
	case dice2.four:
		dice2.opE()
	case dice2.five:
		dice2.opS()
	case dice2.six:
		{
			dice2.opN()
			dice2.opN()
		}
	}
	return
}

func detectFront(dice1, dice2 *Dice) {
	switch dice1.two {
	case dice2.one:
		dice2.opS()
	case dice2.three:
		{
			dice2.opN()
			dice2.opW()
			dice2.opS()
		}
	case dice2.four:
		{
			dice2.opN()
			dice2.opE()
			dice2.opS()
		}

	case dice2.five:
		{
			dice2.opS()
			dice2.opS()
			dice2.opE()
			dice2.opE()
		}
	case dice2.six:
		dice2.opN()
	}
	return
}



Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009

int n, t;
string s;
int main(){
    while(cin >> n){
        int a[6]={1, 2, 3, 4, 5, 6}, c=1;
        if (n==0) return 0;
        for (int l=0; l<n; ++l){
        cin >> s;
        if (s=="North"){
            t=a[0];
            a[0]=a[1];
            a[1]=a[5];
            a[5]=a[4];
            a[4]=t;
        }
        if (s=="East"){
            t=a[0];
            a[0]=a[3];
            a[3]=a[5];
            a[5]=a[2];
            a[2]=t;
        }
        if (s=="West"){
            t=a[0];
            a[0]=a[2];
            a[2]=a[5];
            a[5]=a[3];
            a[3]=t;
        }
        if (s=="South"){
            t=a[0];
            a[0]=a[4];
            a[4]=a[5];
            a[5]=a[1];
            a[1]=t;
        }
        if (s=="Right"){
            t=a[1];
            a[1]=a[2];
            a[2]=a[4];
            a[4]=a[3];
            a[3]=t;
        }
        if (s=="Left"){
            t=a[1];
            a[1]=a[3];
            a[3]=a[4];
            a[4]=a[2];
            a[2]=t;
        }
        c+=a[0];
        //cout << a[0] << ' ' << a[1] << ' ' << a[2] << ' ' << a[3] << ' ' << a[4] << ' ' << a[5] << endl;
        }
        cout << c << endl;
    }
    return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

struct edge {
	int to, cost;
	edge(int t, int c) {
		to = t;
		cost = c;
	}
};

template<typename T>
void dijkstra(int s, vector<vector<edge>>& path, vector<T>& d) {
	priority_queue<P, vector<P>, greater<P>> q;
	q.push(P(0, s));
	d[s] = 0;
	while (!q.empty()) {
		P p = q.top();
		q.pop();
		int v = p.second;
		if (d[v] < p.first)continue;
		REP(i, path[v].size()) {
			edge e = path[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				q.push(P(d[e.to], e.to));
			}
		}
	}
	return;
}

int main() {
	IOS;
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	s--;
	t--;
	vector<int> u(m), v(m), a(m), b(m);
	REP(i, m) {
		cin >> u[i] >> v[i] >> a[i] >> b[i];
		u[i]--;
		v[i]--;
	}
	vector<vector<edge>> patha(n),pathb(n);
	REP(i, m) {
		patha[u[i]].push_back(edge(v[i], a[i]));
		patha[v[i]].push_back(edge(u[i], a[i])); 
		pathb[u[i]].push_back(edge(v[i], b[i]));
		pathb[v[i]].push_back(edge(u[i], b[i]));
	}
	vector<ll> da(n, LLONG_MAX/2), db(n, LLONG_MAX /2);
	dijkstra(s, patha, da);
	dijkstra(t, pathb, db);
	vector<ll> dm(n);
	REP(i, n) {
		dm[i] = da[i] + db[i];
	}
	vector<ll> sm(n);
	sm.back() = dm.back();
	RREP(i, n-1) {
		sm[i] = min(sm[i + 1], dm[i]);
	}
	ll lim = 1e15;
	REP(i, n) {
		put(lim - sm[i]);
	}
	return 0;
}


Measured memory_bytes: 18428
#include <iostream>
using namespace std;
int main(void){
    int a, b, c, d, n, count;
    while(cin >> n){
        count = 0;
        for(a=0; a<=9; a++){
            for(b=0; b<=9; b++){
                for(c=0; c<=9; c++){
                    for(d=0; d<=9; d++){
                        if(a+b+c+d == n){
                            count++;
                        }
                    }
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}



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

int N, P;
vector<int> A;
vector<vector<long long>> mem(51, vector<long long>(2, -1));

long long rec(int idx, int sum){  
  if(idx == N)
    if(sum == P)return 1;
    else return 0;
  if(mem[idx][sum] != -1)return mem[idx][sum];
  if(A[idx] == 0)mem[idx][sum] = rec(idx + 1, sum) + rec(idx + 1, sum);
  else mem[idx][sum] = rec(idx + 1, sum) + rec(idx + 1, sum^1);
  return mem[idx][sum];
}

int main(){
  cin >> N >> P;
  A.resize(N);
  for(auto&&e:A){
    int x; cin >> x;
    e = x & 1;
  }
  long long ans = rec(0, 0);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;   
#define ll long long
#define ull unsigned long long
// #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> 
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define inf 9e18
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// Comment this out for interactice problem
// #define endl '\n'
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output

int main() 
{ 
    fastio;
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ll n;
    cin>>n;
    ll a[n];
    multiset<ll> s1;
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }

    for (int i = 0; i < n; ++i)
    {
        auto it = s1.lower_bound(a[i]);
        if(it==s1.begin()){
            s1.insert(a[i]);
        }
        else{
            it--;
            s1.erase(it);
            s1.insert(a[i]);
        }
    }
    cout<<s1.size();

    return 0;
}


Measured memory_bytes: 8972
/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (win, osx, linux)
 * Author: step_by_step
 * Time: 2020-03-19 17:35:03
**/

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 10;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
//const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    int n;
    cin >> n;
    map<int, int> mapa;
    ll tot = 0;
    int a[n];
    rep(i, 0, n) {
        cin >> a[i];
        tot += mapa[a[i]];
        mapa[a[i]]++;
    }
    rep(i, 0, n) {
        cout << tot - (mapa[a[i]] - 1) << " ";
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 8320
#!/usr/bin/ruby
require 'prime'
n=[0];cnt=1
Prime.each{|e|
	while cnt<e do n<<n.last;cnt+=1 end
	n<<n.last+1;cnt+=1
	break if e>10**6
}
while(m=gets.to_i)>0
	r=-m
	m.times{
		p,m=gets.split.map(&:to_i)
		j=p-m-1
		j=0 if j<0
		k=p+m
		k=10**6-1 if k>=10**6
		r+=n[k]-n[j]
	}
	p r
end

Measured memory_bytes: 16244
def inpl():
    return list(map(int, input().split()))


N = int(input())
A = inpl()
B = inpl()
C = inpl()

A = [(i, A[i]) for i in range(N)]
A.sort()

ans = sum(B)
for a, na in zip(A, A[1:]):
    if a[1] + 1 == na[1]:
        ans += C[a[1] - 1]

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
ll gg=0;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y = LLONG_MAX ){ll res=1;while(y>0){if(y&1)res=(res*x);y=y>>1;x=(x*x);}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}
void solve()
{
    ll  k;cin>>k;
    string s;
    cin>>s;
    if(s.size()<=k)
        cout<<s;
    else
    {
        for(ll i=0;i<k;++i)
        {
            cout<<s[i];
        }
        for(ll i=0;i<3;++i)
        {
            cout<<".";
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        solve();
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>
#include <type_traits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//constexpr long long MOD = 1e9 + 7;
//constexpr long long MAX = 1000000;

//long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;
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; }

ll h, w;
vector<ll> dx = { -1, 0, 1, 0 };
vector<ll> dy = { 0, -1, 0, 1 };


bool isInField(ll x, ll y) {
    bool f = x >= 0 && x < w && y >= 0 && y < h;
    return f;
}

bool compare_first(pair<ll, ll> x, pair<ll, ll> y)
{
    if (x.first != y.first) {
        return x.first < y.first;
    }
    else {
        return x.second < y.second;
    }
}

bool compare_second(pair<ll, ll> x, pair<ll, ll> y)
{
    if (x.second != y.second) {
        return x.second < y.second;
    }
    else {
        return x.first < y.first;
    }
}

struct {
    bool operator()(pair<string, int> x, pair<string, int> y) const
    {
        return x.second <= y.second && x.first < y.first;
    }
} compare_map;

const ll MAX = 500000000;
const ll MOD = 1000000007;


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

    int h, w, k, a, b, c;

    cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);

    cout << a << " " << b << " " << c << "\n";


    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int mod = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

// value
int N, K;
int a[100010], b[100010];
ll fact[100010], fact_inv[100010];
vii g;
bool err = false;

// 逆元を求める
long long mod_inv(long long value) {

	long long b = mod, u = 1, v = 0;

	while (b) {
		long long t = value / b;
		value -= t * b;
		swap(value, b);
		u -= t * v;
		swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;

	return u;
}

void calc_fact() {
	fact[0] = 1; fact_inv[0] = 1;
	for (int i = 1; i < 100005; i++) {
		fact[i] = i * fact[i - 1] % mod;
		fact_inv[i] = mod_inv(fact[i]);
	}
	return;
}

ll nPr(int n, int r) {
	if (n < r) {
		cout << 0 << endl;
		exit(0);
	}
	return fact[n] * fact_inv[n - r] % mod;
}

ll ans;

void dfs(int n, int p, int rank) {
	if (err) return;
	if (g[n].size() == 1 && p != -1) return;
	ans *= nPr(K - min(2, rank + 1), g[n].size() + (p == -1 ? 0 : -1));
	ans %= mod;
	for (int i = 0; i < g[n].size(); i++) {
		if (g[n][i] == p) continue;
		dfs(g[n][i], n, rank + 1);
	}
	return;
}

void solve() {

	cin >> N >> K;
	g.resize(N);
	for (int i = 0; i < N - 1; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		g[a[i]].eb(b[i]);
		g[b[i]].eb(a[i]);
	}

	calc_fact();
	ans = K;
	dfs(0, -1, 0);
	if (err) {
		cout << 0 << endl;
	}cout << ans << endl;

	return;

}

int main() {

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

	solve();

	return 0;

}

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

int main() {
  int N;
  cin>>N;
  vector<int> a(N);
for (int i = 0; i < N; i++) {
  cin >> a.at(i);
}
  vector<int> b(N);
for (int i = 0; i < N; i++) {
  cin >> b.at(i);
}
  vector<int> c(N);
for (int i = 0; i < N; i++) {
  cin >> c.at(i);
}
  sort(a.begin(), a.end());
  sort(c.begin(), c.end());
  int64_t Z=0;
  for(int i=0;i<N;i++){
    int64_t x=lower_bound(a.begin(),a.end(),b.at(i))-a.begin();
    int64_t y=lower_bound(c.begin(),c.end(), b.at(i)+1)-c.begin();
    Z+=x*(N-y);
  }
  cout<<Z<<endl;
}




Measured memory_bytes: 1536
#include <stdio.h>
int main(void)
{
  int i,n,t;
  for(i=0;i<4;i++)
    {scanf("%d%d" ,&t,&n);
      switch(t)
	{case 1:
	    n=n*6000; break;
	case 2:
	  n=n*4000; break;
	case 3:
	  n=n*3000; break;
	case 4:
	  n=n*2000; break;
	}

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

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

int main(){
    string S,T;
    cin >> S >> T;
    int cnt = 0;
    rep(i,3){
        if(S[i]==T[i]){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cassert>
#include<map>

using namespace std;

#define fi first
#define se second
#define rep(i,s,t) for(int i=(s),_t=(t);i<_t;++i)
#define per(i,s,t) for(int i=(t)-1,_s=(s);i>=_s;--i)
#define debug(x) cerr<<#x<<" == "<<(x)<<endl
#define bug(x) cerr<<#x<<" == "<<(x)<<" "

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

template<class T>inline void rd(T &x){
	static char c,f;
	x=0;f=1;
	while(c=getchar(),c<48)if(c=='-')f=-1;
	do x=x*10+(c&15);
	while(c=getchar(),c>47);
	x*=f;
}

template<class T>void pf(T x){
	if(x<0)putchar('-'),x=-x;
	else if(!x){putchar('0');return ;}
	static int stk[100],tp;
	for(tp=0;x;x/=10)stk[tp++]=x%10;
	while(tp)putchar(stk[--tp]^48);
}

template<class T>void ptn(T x){pf(x),putchar('\n');}
template<class T>void ptk(T x){pf(x),putchar(' ');}
template<class T>void Min(T &A,T B){if(A>B)A=B;}
template<class T>void Max(T &A,T B){if(A<B)A=B;}

const int N=(int)1e5+5;

int head[N],n,tot,SG[N];
pii G[N<<1];
void dfs(int x,int par){
	SG[x]=0;
	for(int i=head[x];i;i=G[i].se){
		int y=G[i].fi;
		if(y==par)continue;
		dfs(y,x);
		SG[x]^=SG[y]+1;
	}
}
int main(){
	rd(n);
	for(int x,y,i=1;i<n;++i){
		rd(x),rd(y);
		G[++tot]=pii(y,head[x]);head[x]=tot;
		G[++tot]=pii(x,head[y]);head[y]=tot;
	}
	dfs(1,0);
	if(SG[1])puts("Alice");
	else puts("Bob");
	return 0;
}

Measured memory_bytes: 7296
program prob2
    implicit none
    character(100) :: s
    integer :: h,w,i
    read(*,*) h, w
    do i = 1, h
        read(*,*) s
        write(*,'(a)') trim(adjustl(s))
        write(*,'(a)') trim(adjustl(s))
    end do


    stop
contains
end program prob2

Measured memory_bytes: 2832
#include "bits/stdc++.h"
using namespace std;

static const int INF = 0x3f3f3f3f;

int main() {
        int i, j;
        while (true) {
                int n, m;
                cin >> n >> m;
                if (n == 0 && m == 0) break;
                vector<int> a(n), b(m);
                int asum = 0, bsum = 0;
                for (i = 0; i < n; i ++) { 
                        cin >> a[i];
                        asum += a[i];
                }
                for (i = 0; i < m; i ++) { 
                        cin >> b[i];
                        bsum += b[i];
                }
                int diff = asum - bsum;
                bool f = true;
                if (abs(diff) & 1) f = false;
                int d = diff / 2;
                int s = INF;
                int ansA = -1;
                int ansB = -1;
                for (i = 0; i < a.size(); i ++) {
                        for (j = 0; j < b.size(); j ++) {
                                if (a[i] - b[j] == d) {
                                        if (a[i] + b[j] < s) {
                                                s = a[i] + b[j];
                                                ansA = a[i];
                                                ansB = b[j];
                                        }
                                }
                        }
                }
                if (ansA == -1 || !f) cout << -1 << endl;
                else cout << ansA << ' ' << ansB << endl;
        }
        return 0;
}

Measured memory_bytes: 2992
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
#define mod 1000000007
ll gcd(ll a, ll b){
    if(a % b == 0) return b ;
    ll k = a % b ;
    return gcd(b, k) ;
}
int main(){
    int n ;
    cin >> n ;
    vector<int> a (n) ;
    vector<int> c (1000005) ;
    rep(i, n) {
        cin >> a[i] ;
        c[a[i]]++ ;
    }
    bool can = true ;
    for(int i = 2; i < 1000005; i++){
        int cnt = 0 ;
        for(int j = i ; j < 1000005 ; j += i){
            cnt += c[j] ;
        }
        if(cnt > 1){
            can = false ;
            break ;
        }
    }
    if(can){
        cout << "pairwise coprime" << endl ;
        return 0 ;
    }
    int g = 0 ;
    rep(i, n) g = gcd(g, a[i]) ;
    if(g == 1) {
        cout << "setwise coprime" << endl ;
        return 0 ;
    }
    cout << "not coprime" << endl ;
    return 0 ;
}

Measured memory_bytes: 11136
#include<iostream>
#include<vector>
#include<map>
using namespace std;
typedef long long li;
#define chmin(a,b) (a>(b)?a=(b),1:0)
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
void print(vector<int> v){
  for(int x:v)printf("%d ",x); printf("\n");
} 
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }


int main(){
  int h,w,k; cin >>h >>w >>k;
  vector<string> v(h);
  rep(i,h){
    cin >> v[i];
  }
  li lim=1<<(h-1);
  int ans=h+w;

  auto f
    =[&](li bs){
       int cnt=__builtin_popcount(bs);
       if(df)print(bs,cnt);
       vector<vector<int>> vec(cnt+1,vector<int>(w,0));
       rep(j,w){
         int p=0;
         rep(i,h){
           if(i)if((bs & (1<<(i-1)))) {p++;}
           vec[p][j]+=v[i][j]-'0';
         }
       }
       int hh=cnt+1;
       if(df)rep(i,hh){
           print(vec[i]);
         }
       vector<int> wg(hh,0);

       rep(i,w){
         int flag=0;
         rep(j,hh){
           wg[j]+=vec[j][i];
           if(wg[j]>k){if(df)print("over",wg[j]);flag=1; break;}
         }
         if(!flag) continue;
         if(df){printf("wg "); print(wg);}
         cnt++;
         rep(j,hh){
           wg[j]=vec[j][i];
           if(vec[j][i]>k){
             if(df)print(j,i,":",vec[j][i],">",k);
             return w+h;
           }
         }
         if(df){print(wg);print("cnt++",i);}
         
       }
       if(df) print("cnt",cnt);
       return cnt;
     };
  
  rep(bs,lim){
    chmin(ans,f(bs));
  }
  print(ans);
}


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

using ll = long long;
using pii = pair<int, int>;

int main()
{
    int N, K; cin >> N >> K;
    vector<pii> dt(N); // fitst:d, second:t
    for (auto& e : dt) cin >> e.second >> e.first;
    sort(dt.begin(), dt.end(), greater<pii>());

    map<int, int> m; // key: t, value:count...
    auto compare = [&](const pii& a, const pii& b) {
        const int& at = a.second, ad = a.first;
        const int& bt = b.second, bd = b.first;
        if (at != bt) {
            int ca = m[at], cb = m[bt];
            if (ca >= 2 && cb >= 2) {
                return bd < ad;
            } else if (ca >= 2) {
                return false;
            } else if (cb >= 2) {
                return true;
            }
        }
        return bd < ad;
    };
    priority_queue<pii, vector<pii>, decltype(compare)> q(compare);

    ll ans = 0;
    ll s = 0;
    for (int i = 0; i < K; i++) {
        m[dt[i].second]++;
        q.push(dt[i]);
        s += dt[i].first;
    }
    int vars = m.size();
    ans = s + (ll)vars * vars;

    int ind = K;
    for (int v = vars + 1; v <= K; v++) {
        ll a = 0;

        pii p = q.top();
        if (m[p.second] < 2) break;

        while (ind < N) {
            if (m[dt[ind].second] == 0) break;
            ind++;
        }
        if (ind == N) break;

        m[p.second]--;
        q.pop();
        m[dt[ind].second]= 1;
        q.push(dt[ind]);
        s = s - p.first + dt[ind].first;

        a = s + (ll)v * v;
        ans = max(ans, a);
    }

    cout << ans << endl;
}


Measured memory_bytes: 7672
#include <bits/stdc++.h>
#define MAXS 202007
#define INF 2147483647
 
#define mp(a, b) make_pair(a,b)
#define pb(a) push_back(a)
#define INP freopen("input.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define STREE int bch = no*2, mid = (l+r)/2
#define all(a) a.begin(), a.end()
 
using namespace std;
typedef long long ll;
typedef vector < int > vi;
typedef pair < int, int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

int n, m;

pii arr[MAXS];
ll dp[107][MAXS];

bool func(pii a, pii b){
  if(a.first == b.first) return a.second > b.second;
  return a.first < b.first;
}

ll solve(int id, int p){
  if(dp[id][p] != -1) return dp[id][p];
  else if(p > m) return -arr[id].second;
  else if(id >= n+1) return 0;
  ll ans = 0;
  for(int i = id+1; i <= n; ++i){
    if(p+arr[i].first <= m) ans = max(solve(i, p+arr[i].first) + arr[i].second, ans);
  }
  return dp[id][p] = ans;
}

int main(){
  // clock_t wtf = clock();
  FASTIO;
  cin >> n >> m;
  int a, b;
  for(int i = 1; i <= n; ++i){
    cin >> a>>b;
    arr[i]={a, b};
  }
  sort(arr, arr+n, func);
  for(int i = 0; i <= n+1; ++i){
    fill(dp[i], dp[i]+m, -1);
  }
  // memset(dp, -1, sizeof dp);
  cout << solve(0, 0) << "\n";
  // cout << (double)wtf/(CLOCKS_PER_SEC);
}

Measured memory_bytes: 163328
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(long long h, long long w, std::vector<std::string> s){
    vector<vector<vector<int>>> dp(h, vector<vector<int>>(w, vector<int>(2, MOD)));
    dp[0][0][s[0][0] == '#'] = (s[0][0] == '#');
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(i != h - 1){
                if(s[i + 1][j] == '#'){
                    chmin(dp[i + 1][j][1], dp[i][j][0] + 1);
                    chmin(dp[i + 1][j][1], dp[i][j][1]);
                }
                else{
                    chmin(dp[i + 1][j][0], dp[i][j][0]);
                    chmin(dp[i + 1][j][0], dp[i][j][1]);
                }
            }
            if(j != w - 1){
                if(s[i][j + 1] == '#'){
                    chmin(dp[i][j + 1][1], dp[i][j][0] + 1);
                    chmin(dp[i][j + 1][1], dp[i][j][1]);
                }
                else{
                    chmin(dp[i][j + 1][0], dp[i][j][0]);
                    chmin(dp[i][j + 1][0], dp[i][j][1]);
                }
            }
        }
    }
    cout << min(dp.back().back()[0], dp.back().back()[1]) << endl;
}


signed main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    std::vector<std::string> s(W);
    for(int i = 0 ; i < W ; i++){
        std::cin >> s[i];
    }
    solve(H, W, std::move(s));
    return 0;
}


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

using namespace std;

map<string, int> dict; 
map<string, int> enter;

int main()
{
    //freopen("input.txt", "r" ,stdin);
    int n;
    while (scanf("%d", &n)==1)
    {
        if (n==0)
            break;
        dict.clear();
        enter.clear();
        int m, d, hours, minutes;
        char str[100];
        char flag[100];
        for (int i=1; i<=n; i++)
        {
            scanf("%d/%d", &m, &d);
            scanf("%d:%d", &hours, &minutes);
            scanf("%s%s", flag, str);

            //printf("%d %d %d %d %s %s\n", m, d, hours, minutes, flag, str);
            if (flag[0] == 'I')
            {
                if (string(str) == "000")
                {
                    enter["000"] = hours*60+minutes;
                    for (map<string, int>::iterator ite = enter.begin(); ite!=enter.end(); ite++)
                        if (ite->second!=0)
                            ite->second = hours*60+minutes;
                }
                else
                    enter[string(str)] = hours*60+minutes;
            }
            else
            {
                if (string(str) != "000")
                {
                    if (enter["000"])
                        dict[string(str)] += hours*60+minutes - enter[string(str)];
                    enter[string(str)] = 0;
                }
                else
                {
                    for (map<string, int>::iterator ite = enter.begin(); ite!=enter.end(); ite++)
                    {
                        if (ite->first!="000"&& ite->second!=0)
                        {
                            dict[ite->first] += hours*60+minutes - ite->second;
                            ite->second = hours*60+minutes;
                        }
                    }
                    enter["000"] = 0;
                }
            }
        }
        int ans = 0;
        for (map<string, int>::iterator ite = dict.begin(); ite!=dict.end(); ite++)
        {
            //printf("%s %d\n", ite->first.c_str(), ite->second);
            ans = max(ans, ite->second);
        }
        printf("%d\n", ans);
    }
    return 0;
}

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

int main(){
    long double N,K;cin >> N >> K;
    double res=0;
    for(double i=1.0;i<=N;i++){
        if(i<=K-1.0){
            long double tmp=i;
            long double y=0.0;
            while(K>tmp){
                tmp*=2;
                y++;
            }
            res+=(1.0/N)*pow((1.0/2.0),y);
        }else res+=(1/N);
    }
    cout << setprecision(11) << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}


signed main(void) {
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(a,b) << " ";
    if(n <= a+b)cout << a+b-n << endl;
    else cout << 0 << endl; 

}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max(p,q)((p)>(q)?(p):(q))

int a[1010];

int main(){
	int n;
	scanf("%d",&n);
	double d[9],df=0;
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d",&t);
		for(int j=1;j<=3;j++)d[j]+=pow(abs(a[i]-t),j);
		df=max(df,abs(a[i]-t));
	}
	for(int j=1;j<=3;j++)printf("%f\n",pow(d[j],1.0/j));
	printf("%f\n",df);
}



Measured memory_bytes: 2100
#include <iostream>

int main(){
    int H, N;
    std::cin >> H >> N;
    int A[N];
    for(int i = 0; i < N; i++){
        int t;
        std::cin >> t;
        H-=t;
    }
    if(H <= 0)std::cout << "Yes";
    else std::cout << "No";
    return 0;
}

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

	int main() {
	    int N,W; cin >> N >> W;
	    vector<vector<long long int> > K(N+1,vector<long long int>(W+1));
	    vector<int> wt(N);
	    vector<int> v(N);
	    for (int i = 0; i < N; ++i) cin >> wt[i] >> v[i];
	    for (int i = 0; i <= N; ++i)
	    {
	    	for (int j = 0; j <= W; ++j)
	    	{
	    		if (i==0|| j==0)
	    		{
	    			K[i][j]=0;
	    		}
	    		else if(wt[i-1]<=j)
	    			K[i][j] = max(v[i-1]+K[i-1][j-wt[i-1]],K[i-1][j]);
	    		else
	    			K[i][j] = K[i-1][j];
	    	}
	    }

	 	    cout << K[N][W];

	}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    int a[100];
    int sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        sum += a[i];
    }

    const double mean = sum / (double)N;
    double diff = abs(mean - a[0]);
    int index = 0;
    for (int i = 0; i < N; i++) {
        if (diff > abs(mean - a[i])) {
            diff = abs(mean - a[i]);
            index = i;
        }
    }
    cout << index << endl;
}


Measured memory_bytes: 256
import sys

a, b, c, x, y = map(int, input().split())

best_price = sys.maxsize


for i in range(0, max(x, y) * 2 + 1, 2):
    rest_a = x
    rest_b = y

    if i // 2 >= x:
        rest_a = 0
    else:
        rest_a = x - i // 2

    if i // 2 >= y:
        rest_b = 0
    else:
        rest_b = y - i // 2

    price = rest_a * a + rest_b * b + c * i
    if price < best_price:
        best_price = price
    # print("buy a = " + str(rest_a) + ", b = " + str(rest_b) + ", c = " + str(i) + ", price = " + str(price))

print(best_price)



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

using namespace std;

int main() {
	int n, k; cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	vector<bool> vec(n - k);
	for (int i = 0; i < n-k; ++i) {
		vec[i] = a[k + i] > a[i];
	}
	for (bool k : vec) {
		if (k) cout << "Yes";
		else cout << "No";
		cout << endl;
	}
}

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

typedef long long int LL;
typedef unsigned long long uLL;
typedef pair < int , int > ii;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 1e5 + 5;
const int mod = 1000000007;
const double eps = 1e-8;
const double pi = acos( -1.0 );

int n , k;
LL a[ N ] , neg[ N ];
LL ans = 2*INF;

int main( int argc , char const *argv[] ) {
        ios_base :: sync_with_stdio(false); cin.tie(NULL);
        cin >> n >> k;
        for( int i = 1; i <= n; i++ ) cin >> a[i];
        for( int i = 1; i <= n; i++ ) {
                neg[i] += neg[i-1] + ( a[i] < 0 );
        }
        for( int i = 1; i+k-1 <= n; i++ ) {
                int tn = neg[i+k-1] - neg[i-1];
                int tp = k - tn;
                //cout << tn << " " << tp << endl;
                if( tp == k ) {
                        ans = min( ans , abs( a[i+k-1] ) );
                        //continue;
                }
                else if( tn == k ) {
                        ans = min( ans , abs( a[i] ) );
                }
                else {
                        LL op1 = 0 , op2 = 0;
                        op1 = abs( a[i+k-1] ) + 2 * abs( a[i] );
                        op2 = abs( a[i] ) + 2 * abs( a[i+k-1] );
                        ans = min( ans , min( op1 , op2 ) );
                }
                //cout << "i : "<< ans << endl;
                /*
                int lo = i , hi = i+k-1 , pos = 0;
                while( lo <= hi ) {
                        int mid = ( lo + hi ) >> 1;
                        if( a[mid] >= 0 ) {
                                pos = mid;
                                hi = mid-1;
                        }
                        else lo = mid+1;
                }*/

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








Measured memory_bytes: 1792
A, B = list(map(int, input().split()))

if A < B:
  x = A
  y = B
  c = [".", "#"]
else:
  x = B
  y = A
  c = ["#", "."]
  
S = []

if x <= 50:
  y -= 1
elif x % 50 != 0:
  y += 50 - x % 50

cnt = 0
while x > 50:
  S.append([c[0] if (i + cnt) % 2 == 0 else c[1] for i in range(100)])
  x -= 50
  y -= 50
  cnt += 1

if x != 1:
  S.append([c[0] if (i + cnt) % 2 == 0 and i < (x - 1) * 2 else c[1] for i in range(100)])
  cnt += 1

S.append([c[1] for i in range(100)])
cnt += 1
S.append([c[0] for i in range(100)])
cnt += 1

while y >= 1:
  S.append([c[1] if (i + cnt * 2) % 4 == 0 and i < y * 4 else c[0] for i in range(100)])
  y -= 25
  cnt += 1
  
print(cnt, 100)
for i in S:
  print("".join(i))

Measured memory_bytes: 38768
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N; cin >> N;
	vector<int> cnt(1e4 + 1);
	for (int x = 1; x <= 100; x++) {
		for (int y = 1; y <= 100; y++) {
			for (int z = 1; z <= 100; z++) {
				int f = x * x + y * y + z * z + x * y + y * z + z * x;
				if (f > 1e4)continue;
				cnt[f]++;
			}
		}
	}
	
	for (int i = 1; i <= N; i++)
		cout << cnt[i] << endl;
}


Measured memory_bytes: 3628
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>

int main() {
  using std::vector;  
  int n;
  std::cin >> n;
  vector<vector<int>> a(2, vector<int>(n, 0));
  
  // input vectors x and y
  for (int i = 0; i < n; i++) std::cin >> a[0][i];
  for (int i = 0; i < n; i++) std::cin >> a[1][i];
  
  // p = 1, 2, 3
  for (int p = 1; p <= 3; p++) {
    double sum = 0;
    for (int i = 0; i < n; i++) {
      sum += pow(abs(a[0][i]-a[1][i]), p);
    }
    printf("%f\n", pow(sum, 1.0/p));
  }
  
  // p is infinite
  double maxd = 0;
  for (int i = 0; i < n; i++) {
    double d = abs(a[0][i] - a[1][i]);
    if (d > maxd) maxd = d;
  }
  printf("%f\n", maxd);
  
  return 0;
}

Measured memory_bytes: 1292
N = int(input())
A = list(map(int, input().split()))
ans = 10**9
for i in range(N):
    j = 0
    R = A[i] % 2
    B = A[i] // 2
    while(R==0):
        j += 1
        R = B % 2
        B = B // 2
    ans = min(j, ans)
    
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long a,n,b=0,c=0;
  cin>>n;  
  for(int i=0;i<n;i++){
    cin>>a;
  if(a%2==1)
    b=b+a;
  if(a%2==0)
    c=c+a;
}
  cout<<n*n*n<<endl;
  return(0);
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int n, k;
vector<int> a;

bool f(int m){
    bool dp[5010] = {};
    dp[0] = true;
    rep(i, 0, n){
        if(i == m) continue;
        repb(j, 5010, 0){
            if(j + a[i] > 5000) continue;
            dp[j + a[i]] |= dp[j];
        }
    }
    bool f = false;
    rep(i, max(0LL, k - a[m]), k){
        if(dp[i]) f = true;
    }
    return f;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    a.resize(n);
    rep(i, 0, n) cin >> a[i];
    sort(all(a));
    int ng = -1, ok = n;
    rep(i, 0, 30){
        int mid = (ng + ok) / 2;
        if(f(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 256
use std::io::{BufRead, Write};
use std::io;

fn solve<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut s = String::new();
    input.read_line(&mut s).unwrap();
    let n: i64 = s.trim().parse().unwrap();
    s.clear();
    input.read_line(&mut s).unwrap();
    let mut a: Vec<i64> = s.split_whitespace().map(|x| x.parse().unwrap()).collect();
    assert_eq!(n as usize, a.len());
    let mut result = 0;
    while *a.iter().max().unwrap() >= n {
        let mut delta = 0;
        for x in &mut a {
            let count = *x / n;
            delta += count;
            *x -= count * (n + 1);
        }
        for x in &mut a {
            *x += delta;
        }
        result += delta;
    }
    writeln!(output, "{}", result).unwrap();
}

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    solve(stdin.lock(), stdout.lock());
}

#[cfg(test)]
mod tests {
    fn test(input: &str, output: &str) {
        let mut v: Vec<u8> = Vec::new();
        ::solve(input.as_bytes(), &mut v);
        assert_eq!(String::from_utf8(v).unwrap(), output);
    }

    #[test]
    fn case1() {
        test(
            "4
3 3 3 3\n",
            "0\n",
        );
    }
    #[test]
    fn case2() {
        test(
            "3
1 0 3\n",
            "1\n",
        );
    }
    #[test]
    fn case3() {
        test(
            "2
2 2\n",
            "2\n",
        );
    }
    #[test]
    fn case4() {
        test(
            "7
27 0 0 0 0 0 0\n",
            "3\n",
        );
    }
    #[test]
    fn case5() {
        test(
            "10
1000 193 256 777 0 1 1192 1234567891011 48 425\n",
            "1234567894848\n",
        );
    }
}


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

bool f(int x){
  int keta=0;
  while(x){
    keta++;
    x/=10;
  }
  return keta%2==1;
}

int main() {
  int n;
  cin>>n;
  int ans=0;
  for(int i=1;i<=n;i++){
    if(f(i)) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int h,w;
cin>>h>>w;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
char buf[1005][1005];
int field[1005][1005];
for(int i = 0; i<h; i++){
    for(int j = 0; j<w; j++){
            field[i][j] = 1e5;
    }
}
queue<int>v;
for(int i = 0; i<h; i++){
    for(int j = 0; j<w; j++){
        cin>>buf[i][j];
        if(buf[i][j]=='#'){
            field[i][j] = 0;
            v.push(j); v.push(i);
        }
    }
}

while(v.size()){
    int x = v.front(); v.pop();
    int y = v.front(); v.pop();
    for(int k = 0; k<4; k++){
        int a = x + dx[k];
        int b = y + dy[k];
        if(a>=0&&a<w&&b>=0&&b<h&&field[b][a]==1e5&&buf[b][a]=='.'){
            field[b][a] = field[y][x] + 1;
            buf[b][a]='#';
            v.push(a); v.push(b);
        }
    }
}
int max = -100000;
for(int i = 0; i<h; i++){
    for(int j = 0; j<w; j++){
        if(field[i][j]>max){
            max = field[i][j];
        }
        
    }
}
cout<<max<<endl;
return 0;
}

Measured memory_bytes: 13328
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int a[225816];
ll cnt[225816];

int main(void){
	int n,i;
	ll ans = 0ll;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i]; --a[i];
		++cnt[a[i]];
	}
	for(i=0; i<n; ++i){
		ans += cnt[i]*(cnt[i]-1)/2;
	}
	for(i=0; i<n; ++i){
		cout << (ans-cnt[a[i]]+1) << endl;
	}
	return 0;
}


Measured memory_bytes: 3968
N = int(input())

if N == 1:
  print(0)
else:
  ALL = 10**N % (10**9 + 7)
  t = 2 * 9**N % (10**9 + 7)
  s = 8**N % (10**9 + 7)
  print((ALL - (t - s)) % (10**9 + 7))


Measured memory_bytes: 10728