akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include<algorithm>
#include <cmath>
using namespace std;
int main(){
	while(1){
	double a,b,c;
	scanf("%lf %lf %lf",&a,&b,&c);
	if(a+b+c==0) break;
	int ans=0,u,w;
	for(int i=2;i<=(int)sqrt(a);i++){
		bool d=false;
			for(int k=2;k*k<=i;k++){
				if(i%k==0){
					d=true;
					break;
				}
			}
			if(d) continue;
		for(int j=2;j<=(int)i*c/b;j++){
			bool r=false;
			for(int k=2;k*k<=j;k++){
				if(j%k==0){
					r=true;
					break;
				}
			}
			if(r) continue;
			if(i*j<=a && ans<i*j){
				ans=i*j;
				u=i;
				w=j;
			}
		}
	}
	printf("%d %d\n",u,w);
	}
}

Measured memory_bytes: 1056
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1<<20;
int n, a, x;
ll sx[N], s0[N], z[N];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  fill(s0, s0+N, 1);
  scanf("%d", &n);
  FOR(i, 0, n){
    scanf("%d", &a);
    if(x^=a){
      (s0[x] += sx[x]*(z[0]-z[x])) %= MOD;
      (sx[x] += s0[x]) %= MOD;
      z[x] = z[0];
    }else{
      z[0]++;
    }
  }
  if(x){
    printf("%d\n", s0[x]);
    return 0;
  }
  ll ans = modPow(2, z[0]-1, MOD);
  FOR(i, 1, N) ans += sx[i];
  printf("%d\n", ans%MOD);
}

Measured memory_bytes: 24960
#include<bits/stdc++.h>
using namespace std;
int main(){
	int w,x,y,z,n;
	cin>>x>>y>>z;
	w=z;
	n=0;
	while(w<x){
		w+=y+z;
		if(w>x){
			break;
		}
		n++;
	}
	cout<<n<<endl;
}

Measured memory_bytes: 256
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1000000000
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>a>>b>>n;
    if(n>=b) n=b-1;
    cout<<floor(a*n/b)-a*floor(n/b)<<endl;
    
    return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 100;

int p[N];

void init() {
	for (int i = 2; i < N; i++) {
		if (p[i]) continue;
		for (int j = i; j < N; j += i) {
			p[j] = i;
		}
	}
}

int main() {
    init();
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	vector<set<int>> div(n);
	for (int i = 0; i < n; i++) {
		for (int j = a[i]; p[j] != 0; j /= p[j]) {
			div[i].insert(p[j]);
		}
	}
	bool pairwise = true;
	map<int, int> cnt;
	for (int i = 0; i < n; i++) {
		for (const auto &x : div[i]) {
			if (++cnt[x] >= 2)
				pairwise = false;
            //cout << x << ' ';
		}
		//cout << "\n";
	}
	bool setwise = false;
	int gcd = 0;
	for (int i = 0; i < n; i++)
		gcd = __gcd(gcd, a[i]);
	if (gcd == 1)
		setwise = true;
	if (pairwise)
		cout << "pairwise coprime" << "\n";
	else if (setwise)
		cout << "setwise coprime" << "\n";
	else
		cout << "not coprime" << "\n";
}


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

typedef long long int ll;

int main()
{
    ll n, m;
    cin >> n;
    vector<ll> d(n);
    for(ll i = 0;i < n;i++){
        cin >> d[i];
    }
    cin >> m;
    vector<ll> t(m);
    for(ll i = 0;i < m;i++){
        cin >> t[i];
    }

    sort(d.begin(),d.end());
    sort(t.begin(),t.end());

    ll dc = 0;
    for(ll i = 0;i < m;i++){
        if(d[dc] == t[i]){
            dc++;
        }
        else if(d[dc] < t[i]){
            dc++;
            i--;
        }
        else{
            cout << "NO";
            return 0;
        }
        if(dc > n){
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";
    return 0;
}

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

N, M = map(int, input().split())
num = [0] * N
seen = {}
for i in range(M):
	s, c = map(int, input().split())
	if s in seen:
		if seen[s] != c:
			print(-1)
			exit()
	if s == 1 and c == 0:
		if N == 1:
			print(0)
			exit()
		else:
			print(-1)
			exit()
	num[s-1] = c
	seen[s] = c
if N != 1 and num[0] == 0:
	num[0] = 1
print(int(''.join(map(str, num))))




Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
static const ll INF = 1000000000000000000ll;

int main(){
	ios_base::sync_with_stdio(false);
	int n, k, q;
	cin >> n >> k >> q;
	vector<ll> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	ll answer = INF;
	for(int i = 0; i < n; ++i){
		vector<vector<ll>> b;
		b.emplace_back();
		for(int j = 0; j < n; ++j){
			if(a[j] >= a[i]){
				b.back().push_back(a[j]);
			}else if(!b.back().empty()){
				b.emplace_back();
			}
		}
		if(b.back().empty()){
			b.pop_back();
		}
		vector<ll> c;
		for(auto& v : b){
			const int m = v.size();
			sort(v.begin(), v.end());
			for(int j = 0; j + k <= m; ++j){
				c.push_back(v[j]);
			}
		}
		sort(c.begin(), c.end());
		if(c.size() >= q){
			answer = min(answer, c[q - 1] - c[0]);
		}
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll n, m;

	cin>>n>>m;

	if(n==1||m==1){
		if(n==1&&m==1){
			cout<<1<<endl;
		}else if(n==1){
			ll ans=(m>2)?(m-2):0;
			cout<<ans<<endl;
		}else{
			ll ans=(n>2)?(n-2):0;
			cout<<ans<<endl;
		}
	}else if(n==2||m==2){
		cout<<0<<endl;
	}else{
		cout<<(n-2)*(m-2)<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll a[3];
int main(){
    int k;
    rep(i,3) cin>>a[i];
    cin>>k;
    int cur=max_element(a,a+3)-a;
    ll mx=a[cur];
    rep(i,k){
        mx*=2;
    }
    ll sum=0;
    rep(i,3){
        if(cur==i) sum+=mx;
        else sum+=a[i];
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int []a = new int[N];
    int []b = new int[N];
    int sum=0;
    for(int i=0;i<N;i++){
      a[i]=sc.nextInt();
    }
    for(int i=0;i<N;i++){
        b[i]=sc.nextInt();
    }
    for(int i =0;i<N;i++)
        if(a[i]>b[i]){
            sum= sum + a[i]-b[i];
        }
    System.out.println(sum);
    } 
}

Measured memory_bytes: 21844
from copy import deepcopy

def multiply(A, B):
	new_a = [[0 for i in range(len(B[0]))] for j in range(len(A))]

	for i in range(len(A)):
		for j in range(len(B[0])):
			for k in range(len(A[i])):
				new_a[i][j] += A[i][k] * B[k][j]

	return new_a

def exponentiate(table, times):
	new_table = deepcopy(table)
	identity = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

	curr_pow = 1
	while curr_pow <= times:
		if curr_pow & times:
			identity = multiply(new_table, identity)

		new_table = multiply(new_table, new_table)
		curr_pow *= 2

	return identity

a, b, c, k = map(int, raw_input().split(' '))
table = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]

table_expand = exponentiate(table, min(k, 16384 + k % 2))
resultant_array = multiply(table_expand, [[a], [b], [c]])

if abs(resultant_array[0][0] - resultant_array[1][0]) > 10**18:
	print 'Unfair'
else:
	print resultant_array[0][0] - resultant_array[1][0]

Measured memory_bytes: 2780
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <array>
#include <climits>
#include <cassert>

using namespace std;

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

const ll MOD = ll(1e9) + 7;
const ll INF = LLONG_MAX;
const ll MAX_N = ll(1e5) + 5;
const double EPS = 10e-8;
const double PI = 3.14159265359;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)

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

int main() {
    int n, a, b, c, x, y[105];
    while (1) {
        cin >> n >> a >> b >> c >> x;
        if (n == 0) break;
        REP(i, n) cin >> y[i];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if(i>0&&y[i]==y[i-1]){
                x = (a * x + b) % c;
                cnt++;
            }
            while (x != y[i] && cnt <= 10000) {
                x = (a * x + b) % c;
                cnt++;
            }
        }
        if (cnt > 10000)
            cout << -1 << endl;
        else
            cout << cnt << endl;
    }
    return 0;
}



Measured memory_bytes: 3052
// https://atcoder.jp/contests/abc051/tasks/abc051_c
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)

void printmap(pii diff) {
    if (diff.second > 0) {
        REP(i, diff.second) cout << "U";
    } else {
        REP(i, -diff.second) cout << "D";
    }
    if (diff.first > 0) {
        REP(i, diff.first) cout << "R";
    } else {
        REP(i, -diff.first) cout << "L";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    pii from, to, diff;
    cin >> from.first >> from.second >> to.first >> to.second;
    diff.first = to.first - from.first;
    diff.second = to.second - from.second;
    printmap(diff);
    diff.first = -diff.first;
    diff.second = -diff.second;
    printmap(diff);
    cout << "L";
    diff.first = -diff.first + 1;
    diff.second = -diff.second + 1;
    printmap(diff);
    cout << "DR";
    diff.first = -diff.first;
    diff.second = -diff.second;
    printmap(diff);
    cout << "U\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
using namespace std;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pci pair<char, int>
#define pic pair<int, char>
#define plvl pair<long long, vector<long long> >
#define pcvc pair<char, vector<char> >


using namespace std;

const int mod = 1e9 + 7;

ll gcd(ll a, ll b) {
	if(b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

template <typename T>
void show1(vector<T> dp) {
	for(auto d : dp) {
		cout << d << " ";
	}
	cout << endl;
}

template <typename T>
void show2(vector<vector<T> > dp) {
	for(auto d : dp) {
		for(auto dd : d) {
			cout << dd << " ";
		}
		cout << endl;
	}
}

void executeCode() {
	int n, k;
	cin >> n >> k;
	set<int> st;
	while(k--) {
		int d;
		cin >> d;
		while(d--) {
			int x;
			cin >> x;
			st.insert(x);
		}
	}
	cout << n - st.size() << endl;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int tt = 1;
	// cin >> tt;
	while(tt--) {
		executeCode();	
	}
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

#define fill(a,x) memset(a,x,sizeof(a)) 
#define pb push_back
#define sz(x) (int)x.size() 
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 1e5+10; 

int main(){
  fast;
  ll a,b,c;
  cin>>a>>b>>c;

  ll ans=0;
  ans= min(b,c);
  b-=ans;
  c-=ans;
  ans*=2;

  if(c==0)
  {
  	ans+=b;
  	cout<<ans<<endl;
  	return 0;
  }
  else
  {
  	ans+=min(a,c);
  	c-=min(a,c);
  	if(c)
  	ans++;
  	cout<<ans<<endl;
  	return 0;
  }
  return 0;
}

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

int main(){
  long long N, K; cin >> N >> K;
  if(N==1){
    cout << 0 << endl;
    return 0;
  }
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  long long count=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(A[i]>A[j]){
        count++;
      }
    }
  }
  long long in=0;
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      if(A[i]>A[j]){
        in++;
      }
    }
  }
  long long wa;
  if(K%2==0){
    wa=(1+K)*(K/2)%1000000007;
  }
  else wa=(K*((K-1)/2)+K)%1000000007;
  long long ans=0;
  long long kake=(K*K-wa)%1000000007;
  ans+=count*kake%1000000007;
  ans+=in*K;
  cout << ans%1000000007 << endl;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int n; cin >> n;
	string s, t; cin >> s >> t;
	string u;
	for(Int i=0; i<n; ++i){
		u += s[i];
		u += t[i];
	}
	cout << u << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define ff           first
#define ss           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

// Most important thing in CP - Have Fun :)

void solve(){
	//write here
    int temp;
    cin>>temp;
    if (temp>=30)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
	return;
}

int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	//insert code
	
		solve();
	return 0;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll N,M,X,Y;
    cin >> N >> M;

    vector<ll> C(N);
    for(int i=0;i<N;i++)
        cin >> C[i];

    vector<pair<ll,ll> > B(M);
    for(int i=0;i<M;i++)
    {
        cin >> X >> Y;
        B[i].second = X;
        B[i].first = Y;
    }

    sort(C.begin(),C.end());
    sort(B.begin(),B.end());

    ll sum = 0,ind = 0,temp=0;
    for(int i=M-1;i>=0;i--)
    {
        if(temp==0)
            temp = B[i].second;

        if(C[ind] >= B[i].first)
        {
            sum = sum + C[ind];
            ind++;
            //cout << sum <<" " << ind<<" " << i<< " a "<<endl;
            i++;
        }
        else
        {
            sum = sum + B[i].first;
            ind = ind + 1;
            temp--;
            if(temp!=0)
                i++;
            //cout << sum <<" " << ind<<" " << i<< " b "<<endl;
        }
        if(ind>=N)
            break;
    }
    if(ind<N)
    {
        for(int i=ind;i<N;i++)
            {
                sum += C[i];
                //cout << sum << " c "<<endl;
            }
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 2560
#include<stdio.h>
#include<string.h>
int main(void){
char s[100];
  scanf("%s",&s);
  char mae[50],ato[50];
  for(int i=0;i<50;i++){
	mae[i]=0;
    ato[i]=0;
  }
  for(int i=0;i<strlen(s)/2;i++){
	mae[i]=s[i];
    ato[i]=s[i+strlen(s)/2+1];
    //printf("%c %c\n",mae[i],ato[i]);
  }
  //printf("%d\n%d\n%d\n",strlen(s),strlen(mae),strlen(ato));
  for(int i=0;i<strlen(s)/2;i++){
    if(s[i]!=s[strlen(s)-1-i]){
      printf("No");
      return 0;
    }
    }
     for(int i=0;i<strlen(mae)/2;i++){
    if(mae[i]!=mae[strlen(mae)-1-i]){
      printf("No");
      return 0;
    }} 
       for(int i=0;i<strlen(ato)/2;i++){
    if(ato[i]!=ato[strlen(ato)-1-i]){
      printf("No");
      return 0;
    }}
         printf("Yes");
    //  printf("%d\n%d\n",strlen(mae),strlen(ato));
      return 0;
      }


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

using namespace std;

int nax = 30;
int n;
int dp[30][(1<<23)];
int vec[30][30];
const int mod = 1e9 + 7;

long long func(int k, int mask){
	if(mask == (1 << n) - 1 || k == n) return dp[k][mask] = 1;
	if(dp[k][mask] != -1) return dp[k][mask];
	long long ans = 0;
	for(int i = 0; i < n; i++){
		if(vec[k][i] == 1 && ((mask & (1 << i)) == 0)){
			ans += func(k + 1, mask | (1 << i));
			ans %= mod;
		}
	}
	return dp[k][mask] = ans;
	
}

int
main(void){
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> vec[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < (1 << n); j++){
			dp[i][j] = -1;
		}
	}
	
	cout << func(0, 0);
	
}

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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<ll, ll>;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  vector<P> lowHigh;
  int low = INT_MAX;
  int high = INT_MIN;
  int lowIndex = -1;
  int highIndex = -1;
  rep(i, n) {
    int x = a.at(i);
    if (low == INT_MAX && high == INT_MIN) {
      low = x;
      lowIndex = i;
      high = x;
      highIndex = i;
      continue;
    }
    int y = a.at(i - 1);
    if (x < y) {
      if (low != high && highIndex > lowIndex) {
        lowHigh.emplace_back(lowIndex, highIndex);
        low = INT_MAX;
        high = INT_MIN;
      }
    } else {
      if (x < low) {
        low = x;
        lowIndex = i;
      } else if (x >= high) {
        high = x;
        highIndex = i;
      }
      if (i == n - 1 && high != low) {
        lowHigh.emplace_back(lowIndex, highIndex);
        break;
      }
    }
    if (x < low) {
      low = x;
      lowIndex = i;
    } else if (x > high) {
      high = x;
      highIndex = i;
    }
  }
  ll res = 1000;
  for (auto lh : lowHigh) {
    ll buyCount = res / a.at(lh.first);
    res -= buyCount * a.at(lh.first);
    res += a.at(lh.second) * buyCount;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3596
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using ll = long long;
const ll mod = 1e9 + 7;
char c[100005];
ll dp[100005][2];
int main() {
	scanf("%s", c);
	int n = strlen(c);
	dp[0][0] = 1, dp[0][1] = 2;
	repl(i, 1, n) {
		if (c[i] == '1') {
			dp[i][0] = dp[i - 1][0] * 3 + dp[i - 1][1];
			dp[i][1] = dp[i - 1][1] * 2;
		} else {
			dp[i][0] = dp[i - 1][0] * 3;
			dp[i][1] = dp[i - 1][1];
		}
		dp[i][0] %= mod;
		dp[i][1] %= mod;
	}
	printf("%lld\n", (dp[n - 1][0] + dp[n - 1][1]) % mod);
	return 0;
}


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

using namespace std;

typedef long long ll;

int num[5005],pos[5005],cnt[5005];
ll f[5005][5005];

int main() {
  memset(f,0x3f,sizeof(f));
  int n,a,b;
  scanf("%d%d%d",&n,&a,&b);
  for(int i=1;i<=n;i++) {
  	scanf("%d",&num[i]);
  	pos[num[i]]=i;
  }
  for(int i=0;i<=n;i++) f[i][0]=f[0][i]=0;
  for(int i=1;i<=n;i++) {
  	for(int j=num[i]+1;j<=n;j++)
  	  if (pos[j]<i) cnt[j]++;
    for(int j=1;j<=n;j++)
      if (pos[j]<=i) {
      	if (!cnt[j]) f[i][j]=f[i][j-1];
      	else f[i][j]=min(f[i][j-1]+a,f[pos[j]-1][j]+(ll)b*cnt[j]);
	  }
      else f[i][j]=f[i][j-1];
  }
  printf("%lld\n",f[n][n]);
  return 0;
}

Measured memory_bytes: 196096
def check_weather(weathers: str) -> int:
    count = 0
    l_n = [0]
    for index, i in enumerate(weathers):
        if weathers[-1] == 'R' and index == len(weathers) - 1:
            count += 1
            l_n.append(count)
            break

        if i == 'R':
            count += 1
        else:
            if max(l_n) <= count:
                l_n.append(count)
            count = 0
    return max(l_n)


if __name__ == '__main__':
    print(check_weather(input()))

Measured memory_bytes: 9136
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long int ll;

bool canPay(int num,set<int> banList){
	while(num > 0){
		int digit = num % 10;
		if( banList.count(digit) != 0) return false;
		num /= 10;
	}
	return true;
}

int main()
{
	int N,K;
	cin>>N>>K;
	set<int> banNum;
	for(int i = 0; i < K; i++){
		int num;
		cin>>num;
		banNum.insert(num);
	}
	while(canPay(N,banNum) == false){
		N++;
	}
	cout<<N<<endl;

	return 0;
}


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

bool judge(string&s){
	for(int i=0,j=s.size()-1;i<j;++i,--j){
		if(s.at(i)!=s.at(j))return true;
	}
	return false;
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s;
	cin>>s;
	bool yes=true;
	int n=s.size(),n2;
	if(judge(s))yes=false;
	string s2=s.substr(0,(n-1)/2);
	n2=s2.size();
	if(yes==true&&judge(s2))yes=false;
	s2=s.substr((n+3)/2-1,n2);
	if(yes==true&&judge(s2))yes=false;
	cout<<(yes?"Yes":"No")<<"\n"s;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v, s; cin >> u >> v >> s; u--, v--;
        G[u].emplace_back(v, s);
        G[v].emplace_back(u, s);
    }
    Int xmin = 1, xmax = 1e18;
    vector<bool> visited(N);
    vector<Int> A(N), B(N);
    auto recur = [&](auto rec, int node, Int a, Int b) -> void {
        if (!visited[node]) {
            A[node] = a;
            B[node] = b;
            visited[node] = true;
        } else {
            if (A[node] == a && B[node] != b) {
                xmin = 1e18, xmax = 0;
            } else if (A[node] != a) {
                Int x = (B[node]-b)/(a-A[node]);
                xmin = max(xmin, x);
                xmax = min(xmax, x);
            }
            return;
        }
        if (a > 0) {
            xmin = max(xmin, 1-b);
            for (auto &p : G[node]) {
                int next, sum; tie(next, sum) = p;
                xmax = min(xmax, sum-1-b);
            }
        } else {
            xmax = min(xmax, -(1-b));
            for (auto &p : G[node]) {
                int next, sum; tie(next, sum) = p;
                xmin = max(xmin, -(sum-1-b));
            }
        }
        for (auto &p : G[node]) {
            int next, sum; tie(next, sum) = p;
            rec(rec, next, -a, sum-b);
        }
    };
    recur(recur, 0, 1, 0);
    cout << max(0LL, xmax - xmin + 1) << endl;
    return 0;
}

Measured memory_bytes: 15616
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        // 200^5 - 199^5 = 7920399001 > 10^9 であることから、200まで全探索すればOKっしょ、と考えてたら甘かったが、よくわからん🙉
        for(long a=-200; a<=200; a++) {
            for(long b=-200; b<=200; b++) {
                long a5 = a*a*a*a*a;
                long b5 = b*b*b*b*b;
                if(x==a5-b5) {
                    System.out.print(a);
                    System.out.print(" ");
                    System.out.println(b);
                    return;
                }
            }
        }
        throw new RuntimeException("could not find");
    }
}


Measured memory_bytes: 35836
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int n;
long long s[2000006],ans,x;
bool cmp(long long x,long long y)
{
	return x<y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&x);
		s[i]=s[i-1]+x;
	}
//	for(int i=1;i<=n;++i)
//	 cout<<s[i]<<" ";
	// cout<<endl;
	 sort(s+1,s+1+n,cmp);
	 for(int i=1;i<=n;++i)
	 {
	 	long long num=1;
	 	while(s[i+1]==s[i]&&i<n) ++i,++num;
	 	if(s[i]==0) ++num;
	 	ans+=1ll*num*(num-1)/2;
	 }
	// for(int i=1;i<=n;++i)
	// cout<<s[i]<<" ";
	printf("%lld",ans);
	return 0;
 } 

Measured memory_bytes: 1792
//2017-10-8
//miaomiao
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define pb push_back
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)

#define N (500000+5)

const int oo = 0x3f3f3f3f;

int n, a[N], ql, qr;

#define lc (o<<1)
#define rc (o<<1|1)
#define mid ((L+R)>>1)

namespace Seg_tree{
	int mn[N<<2];

	void Pushup(int o){
		mn[o] = min(mn[lc], mn[rc]);
	}

	void Build(int o, int L, int R){
		if(L == R){
			mn[o] = oo; return;
		}

		Build(lc, L, mid); Build(rc, mid+1, R);
		Pushup(o);
	}

	void Modify(int o, int L, int R, int p, int pv){
		if(L == R){
			mn[o] = pv; return;
		}

		if(p <= mid) Modify(lc, L, mid, p, pv);
		else Modify(rc, mid+1, R, p, pv);
		Pushup(o);
	}

	int Query(int o, int L, int R){
		if(ql <= L && qr >= R) return mn[o];

		int ret = oo;
		if(ql <= mid) ret = min(ret, Query(lc, L, mid));
		if(qr > mid) ret = min(ret, Query(rc, mid+1, R));
		return ret;
	}
};

#undef lc
#undef rc
#undef mid

using namespace Seg_tree;

int k, in[N], id[N], ans[N];
vector<int> G[N];

void EdgeInit(){
	int mv, qp;

	Forr(i, n, 1){
		mv = a[i];

		ql = max(mv-k+1, 1);  qr = max(mv-1, 0);
		if(ql <= qr){
			qp = Query(1, 1, n);
			if(qp != oo){
				G[a[qp]].pb(mv); ++in[mv];
			}
		}

		ql = min(mv+1, n); qr = min(mv+k-1, n+1);
		if(ql <= qr){
			qp = Query(1, 1, n);
			if(qp != oo){
				G[a[qp]].pb(mv); ++in[mv];
			}
		}

		Modify(1, 1, n, a[i], i);
	}
}

priority_queue<int> q;

void Solve(){
	For(i, 1, n) if(!in[i]) q.push(i);
	int now, v, an = 0;

	while(!q.empty()){
		now = q.top(); q.pop();
		id[++an] = now;

		For(i, 0, G[now].size()-1){
			v = G[now][i]; --in[v];
			if(!in[v]) q.push(v);
		}
	}

	reverse(id+1, id+n+1);
	For(i, 1, n) ans[id[i]] = i;

	For(i, 1, n) printf("%d\n", ans[i]);
}

int main(){
	int rt;

	scanf("%d%d", &n, &k);
	For(i, 1, n) scanf("%d", &rt), a[rt] = i;
	Build(1, 1, n);

	EdgeInit(); Solve();

	return 0;
}

Measured memory_bytes: 45056
#include <iostream>

int main() {
  int N, M;

  std::cin >> N >> M;

  int max_l = 0;
  int min_r = N+1;

  for (int i=0; i<M; i++) {
    int l, r;
    std::cin >> l >> r;

    max_l = std::max(max_l, l);
    min_r = std::min(min_r, r);
  }

  int ans = std::max(0, min_r - max_l + 1);

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
long double f1[200001], f2[200001];
int N, d1, x;
int main()
{
	scanf("%d%d%d", &N, &d1, &x);
	for (int i = 1; i <= N; i++)
	{
		f1[i] = f1[i - 1] * (i + 1) / i + 1;
		f2[i] = (f2[i - 1] * (i + 2) + f1[i - 1] * 2.5) / i + i - 0.5;
	}
	printf("%.10Lf\n", d1 * f1[N] + x * f2[N]);
	return 0;
}


Measured memory_bytes: 6400
K,T = map(int,input().split())
A = list(map(int, input().split()))

dom = max(A)
other = sum(A) - dom

if K%2 >0:
  print(max(0, (dom-(K+1)//2)*2))
else:
  print(max(0, (dom-K//2)*2 -1))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <math.h>
#include <deque>
#include <queue>
#include <map>
#include <iterator>
#include <set>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }
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; }

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

	int n, k;
	cin >> n >> k;
	vector<int> p, m;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a >= 0) p.push_back(a);
		else m.push_back(a);
	}

	reverse(m.begin(), m.end());

	int ps = p.size();
	int ms = m.size();
	ll ans = 1e18;
	int u = min(k, ps);
	int v = min(k, ms);

	for (int i = k - v; i <= u; i++) {
		ll now = 0;
		if (i > 0) now += p[i - 1];
		if (k - i > 0) now += now - m[k - i - 1];
		chmin(ans, now);
	}

	for (int i = k - v; i <= u; i++) {
		ll now = 0;
		if (k - i > 0) now += abs(m[k - i - 1]);
		if (i > 0) now += now + p[i - 1];
		chmin(ans, now);
	}


	cout << ans << endl;
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <stdio.h>
#include <unistd.h>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define PI 3.14159265359

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

vector<ll> dist;
map<pair<int, int>, int> mp;
map<int, vector<int>> v;

void solveDist(int now, int before, ll count) {
  rep (i, v[now].size()) {
    if (v[now][i] == before) continue;
    ll newCount = count + mp[make_pair(now, v[now][i])];
    dist[v[now][i]] = newCount;
    solveDist(v[now][i], now, newCount);
  }
}

int main() {
  int n;
  cin >> n;
  rep (i, n - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
    mp[make_pair(a, b)] = c;
    mp[make_pair(b, a)] = c;
  }

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

  dist = vector<ll>(n);
  dist[k] = 0;
  solveDist(k, -1, 0);

  rep (i, q) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    P(dist[x] + dist[y]);
  }

  // rep (i, n) {
  //   P(dist[i]);
  // }

  return 0;
}



Measured memory_bytes: 38528
//edit  fork	 download
 #include <iostream>
using namespace std;
typedef long long ll;
ll len[51]={1};
ll p[51]={1};
ll sol(ll N, ll X){
    if(X==0){return 0;}
    if(N==0) return X?1:0;
    ll ret=0;
    if(X<=len[N-1]+1){
        ret+=sol(N-1,X-1);
    }
    else{
        ret+=p[N-1];
        X-=len[N-1]+1;
        if(X>0) X--,ret++;
        ret+=sol(N-1,X);
    }
    return ret;
}
int main() {
	ll N,X;
    cin>>N>>X;
    for(int i=1;i<=50;i++){
        p[i]=p[i-1]*2+1;
        len[i]=len[i-1]*2+3;
    }
    cout<<sol(N,X);
	return 0;}

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

using namespace std;

size_t allocation_load_capcity(vector<uint32_t> baggages, int64_t capacity, uint32_t tracks)
{
  uint32_t num = 0;

  for (uint32_t i = 0; i < tracks; i++) {
    int64_t track_capacity = 0;
    while ((track_capacity + baggages[num]) <= capacity) {
      track_capacity += baggages[num];
      num++;
      if (num == baggages.size()) return num;
    }
  }

  return num;
}

size_t allocation_max_load_capcity(vector<uint32_t> baggages, uint32_t tracks)
{
  int64_t lindex = 0;
  int64_t rindex = 100000 * 10000;
  while (rindex - lindex > 1) {
    int64_t capacity = (lindex + rindex) / 2;
    uint32_t num = allocation_load_capcity(baggages, capacity, tracks);
    if (num >= baggages.size()) {
      rindex = capacity;
    } else
      lindex = capacity;
  }

  return rindex;
}

#if !defined(TEST)

#include <iostream>
static vector<uint32_t> baggages;

int32_t main(void)
{
  uint32_t num, tracks;
  cin >> num >> tracks;

  for (uint32_t i = 0; i < num; i++) {
    uint32_t weight;
    cin >> weight;
    baggages.push_back(weight);
  }

  cout << allocation_max_load_capcity(baggages, tracks) << endl;

  return 0;
}
#endif

Measured memory_bytes: 4188
use std::error::Error;
use std::io::{self, BufReader};
use std::io::prelude::*;
use std::str::{self, FromStr};

fn exec() {
    let mut sc = Scanner::new(io::stdin());
    type Int = i64;
    fn __gcd(a: Int, b: Int) -> Int {
        match b {
            0 => a,
            _ => __gcd(b, a % b),
        }
    }
    fn lcm(a: Int, b: Int) -> Int {
        a / __gcd(a, b) * b
    }
    let n: usize = sc.ne();
    let ans = (0..n - 1).fold(sc.ne::<i64>(), |acc, _| lcm(acc, sc.ne::<i64>()));
    println!("{}", ans);
}

fn main() {
    const STACK: usize = 16 * 1024 * 1024;
    let _ = std::thread::Builder::new()
        .stack_size(STACK)
        .spawn(|| { exec(); })
        .unwrap()
        .join()
        .unwrap();
}

#[allow(dead_code)]
pub struct Scanner<R> {
    bufread: BufReader<R>,
    id: usize,
    buf: Vec<u8>,
}
impl<R: Read> Scanner<R> {
    pub fn new(resource: R) -> Scanner<R> {
        Scanner {
            bufread: BufReader::new(resource),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.bufread.read_line(&mut res) {
            Ok(0) => None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    pub fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.is_empty() {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert_ne!(self.buf[l], b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!(
                    "parse error, {:?}",
                    String::from_utf8(self.buf[l..r].to_owned())
                )
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    pub fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Measured memory_bytes: 8572
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>
#include <map>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

int n;

void solve(){
  cin >> n;
  if(n==1)cout << "Hello World" << endl;
  else{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		if(a % 2 == 0) {
			System.out.println(a / 2);
		} else {
			System.out.println(a / 2 + 1);
		}
	}
}


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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int X, A;
  cin >> X >> A;
  if (X < A) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
N, K = gets.chomp.split(" ").map(&:to_i)

def combi_upper(n, k)
  return 1 if k.zero?
  @combi_u ||= {}
  @combi_u[n] ||= {}
  @combi_u[n][k] ||= (n - k + 1) * combi_upper(n, k - 1)
end

def factorial(n)
  return 1 if n.zero?
  @fac ||= {}
  @fac[n] ||= n * factorial(n - 1)
end

def combination(n, k)
  combi_upper(n, k) / factorial(k)
end

def count(m)
  combination(N-K+1, m) * combination(K-1, m-1)
end

1.upto(K) do |i|
  puts count(i) % (10**9 + 7)
end


Measured memory_bytes: 7676
comparison = 0

def merge(A,left,mid,right):
    global comparison
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)

    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    
    L[n1] = 1e12
    R[n2] = 1e12

    i = 0
    j = 0

    for k in range(left,right):
        comparison += 1
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergesort(A,left,right):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(A,left,mid)
        mergesort(A,mid,right)
        merge(A,left,mid,right)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mergesort(A,0,n)
    print(*A)
    print(comparison)

if __name__ == "__main__":
    main()


Measured memory_bytes: 63448
// SeeAlso: https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_a

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

int m, d;

int main() {
    cin >> m >> d;

    ll ans = 0;
    
    if (m < 4 || d < 22) {
        print(ans);
        return 0;
    } 

    for(int i=4; i<=m;i++) {
        for(int j=22; j<=d;j++) {
            int d1 = j%10;
            int d2 = (j-d1)/10;

            if (d1*d2==i&& d1>=2 && d2>=2) {
                ans++;
            }
        }
    }

    print(ans);    
    return 0;
}


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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n,a[81];

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

void process()
{
    int i=1;
    long long s=1000;
    while (i<n)
    {
        int j=i+1;
        while (j<=n && a[j]>=a[j-1])
            j++;
        j--;
        long long t=s/a[i];
        s=s-t*a[i]+t*a[j];
        i=j+1;
    }
    cout<<s;
}

int main()
{
    nhap();
    process();
    return 0;
}


Measured memory_bytes: 3724
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x

#ループの始まりを特定
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch #ループの開始している配列の初めの数字
        break
    ch *= ch
    ch %= mod

stnum = num.index(st)

if 0 in num:
    ans = sum(num[:n])
else:
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum) #余り
        qu = (n-stnum)//(len(num)-stnum)  #商
    else:
        rest = n
        qu = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*qu
print(ans)

Measured memory_bytes: 68316
n,m = map(int,input().split())
if m%n==0:
    print(int(m//n))
    exit()
else:
  a = m/n
  l = []
  for i in range(int(m**0.5),0,-1):
    if m%i==0:
      l.append(i)
      l.append(m//i)
  l = sorted(l)[::-1]
  for j  in l:
    if j<=a:
      print(j)
      exit()
  else:
    print(1)

Measured memory_bytes: 9248
#include <iostream>
#include <string>
using namespace std;
int main(void) {
  int K;
  string S;
  cin >> K >> S;
  if (S.length() <= K) {
    cout << S << endl;
  } else {
    cout << S.substr(0, K) << "..." << endl;
  }
  return 0;
}


Measured memory_bytes: 3628
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		int[] a = new int[3];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 3; j++) {
				a[j] = sc.nextInt();
			}
			Arrays.sort(a);
			if(a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) {
				sb.append("YES");
			}else {
				sb.append("NO");
			}
			sb.append("\n");
		}
		sc.close();
		System.out.print(sb.toString());
	}
}


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

using namespace std;
typedef long long ll;

const ll mod=1000000007;
ll n;
vector<ll> primes;
ll x=0;

ll fpow(ll b,ll e)
{
    ll res=1;
    while(e)
    {
        if(e&1) res=(res*b)%mod;
        b=(b*b)%mod;
        e/=2;
    }
    return res;
}

void solve(int idx,int cnt,ll now,ll lim)
{
    if((cnt%2)==0) x=(x+fpow(lim/now,n))%mod;
    else x=(x-fpow(lim/now,n)+mod)%mod;
    for(int i=idx+1;i<(int)primes.size();i++)
    {
        if(now*primes[i]<=lim) solve(i,cnt+1,now*primes[i],lim);
        else break;
    }
}

int main()
{
    ll k;
    cin >> n >> k;
    vector<bool> sieve(k+1,1);
    for(ll o=2;o<=k;o++)
    {
        if(sieve[o]==0) continue;
        primes.push_back(o);
        for(ll i=o*o;i<=k;i+=o) sieve[i]=0;
    }
    ll res=0;
    for(ll i=1;i<=k;i++)
    {
        x=0;
        solve(-1,0,1,k/i);
        res=(res+i*x)%mod;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  vector<vector<int>> c(3,vector<int>(3));
  rep(i,0,3) cin >> c[0][i];
  rep(i,1,3) rep(j,0,3) {
    cin >> c[i][j];
    c[i][j] -= c[0][j];
  }
  if (c[1][0] == c[1][1] && c[1][1] == c[1][2]) {
    if (c[2][0] == c[2][1] && c[2][1] == c[2][2]) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3640
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main() {
    int n;
    double s;
    int x[1001];
    int y[1001];
    double z[1001];
    scanf(" %d", &n); 
    for(int i=0; i<n; ++i)
        scanf(" %d", &x[i]); 
    for(int i=0; i<n; ++i)
        scanf(" %d", &y[i]);
    for(int j = 0;j < n; j++) {
        z[j] = fabs(x[j]-y[j]);
    }
   
    for(int p = 1; p <= 3; p++) {
        s = 0;
        for(int k = 0; k < n; k++) {
            s += pow(fabs(x[k] - y[k]), p);
        }
        printf("%lf\n",pow(s,1.0/p));     
    } 
    double max = z[0];

    for(int t = 1; t < n; t++){
        if(max < z[t]){
            max = z[t];
        }
    }
    printf("%lf\n",max);
    return 0;
}


Measured memory_bytes: 2916
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int K = in.nextInt();
            StringBuilder S = new StringBuilder(in.next());
            S.replace(K - 1, K, S.substring(K - 1, K).toLowerCase());
            System.out.println(S);
        }
    }
}


Measured memory_bytes: 21204
#include<iostream>
#include<cmath>
#include<string>
#include<cstdlib>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<string.h>
#include<iomanip>
using namespace std;
int main()
{
	string a,b;//??????????????????????????\????????????????????\????????????
	int sum=0;
		cin>>a;
		while(cin>>b)//????????\??¨cin????°±?????¨??????????????????????\????
		{
			if(b=="END_OF_TEXT")
			break;
			for(int i=0;i<b.length ();i++)
				b[i]=tolower(b[i]);
			if(b==a)
				sum++;
		}

				
			



		cout<<sum<<endl;//???????????????????????¬???
		
		
		
		
		
		}
		

Measured memory_bytes: 3152