akhauriyash/Code-Regression huggingface dataset:
H,W = map(int,input().split())
s = [input() for i in range(H)]
ans = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    count = 0
    if s[i][j] != '#':
      if i+1 < H and s[i+1][j] == '#':
        count+=1
      if j+1 < W and s[i][j+1] == '#':
        count+=1
      if i-1 >= 0 and s[i-1][j] == '#':
        count+=1
      if j-1 >= 0 and s[i][j-1] == '#':
        count+=1
      if i+1 < H and j+1 < W and s[i+1][j+1] == '#':
        count+=1
      if i+1 < H and j-1 >= 0 and s[i+1][j-1] == '#':
        count+=1
      if i-1 >= 0 and j+1 < W and s[i-1][j+1] == '#':
        count+=1
      if i-1 >= 0 and j-1 >= 0 and s[i-1][j-1] == '#':
        count+=1
      ans[i][j]=count
    else:
      ans[i][j] = '#'
for i in range(H):
  tmp=''
  for j in range(W):
    tmp+=str(ans[i][j])
  print(tmp)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const i64 INF = 1e18;

int main() {
    int N;
    cin >> N;
    vector<i64> a(3 * N);
    for (auto &x : a) cin >> x;
    vector<i64> L, R;
    priority_queue<i64> qR;
    rev_priority_queue<i64> qL;
    i64 SL = 0, SR = 0;
    for (int i = 0; i < 2 * N; i++) {
        int j = 3 * N - 1 - i;
        SL += a[i];
        qL.push(a[i]);
        SR += a[j];
        qR.push(a[j]);
        if (i >= N) {
            SL -= qL.top();
            qL.pop();
            SR -= qR.top();
            qR.pop();
        }
        if(i >= N - 1) {
            L.push_back(SL);
            R.push_back(SR);
        }
    }

    i64 ans = -INF;
    for(int i = 0; i <= N; i++) {
        ans = max(ans, L[i] - R[N - i]);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    string S;
    vector<char> cof;
    cin >> S;
    for (char x : S) cof.push_back(x);
    if (cof[2]==cof[3]&&cof[4]==cof[5]) cout << "Yes";
    else cout << "No";
}


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

const int MAX = 1e5 + 3;
int dp[MAX];
int N;

int main() {
  cin >> N;
  for (int n = 1; n <= 100000; n++) dp[n] = MAX;

  for (int n = 1; n <= 1e5; ++n) {
    int power = 1;
    while (power <= n) {
      dp[n] = min(dp[n], dp[n - power] + 1);
      power *= 6;
    }
    power = 1;
    while (power <= n) {
      dp[n] = min(dp[n], dp[n - power] + 1);
      power *= 9;
    }
  }
  cout << dp[N] << endl;
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 200001

typedef long long ll;
ll n, a[MAXN], ans;

int main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
	for (int i = 2; i <= n; ++i) {
		ans ^= a[i] ^ a[1];
	}
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", ans ^ a[i]);
	}
	return 0;
}

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

int main(void){
  int n, a[100000];
  cin >> n;
  for(int i=0;i<n;++i){
    cin >> a[i];
  }
  sort(a,a+n,greater<int>());
  int sum1=0,sum2=0;
  for(int i=0;i<n;++i){
    sum1 += a[i];
    ++i;
    if(i==n) break;
    sum2 += a[i];
  }
  cout << sum1-sum2 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<deque>
#include<map>
#include<queue>
#include<cmath>

typedef long long ll;

#define debug(x) cout << #x << "=" << x << endl;
#define debug_arr(a, n) for(ll i = 0; i < n; i++)cout << a[i] << " "
#define inf 100000000000
#define loop(i,n) for(ll i = 0; i < n; i++)
#define graph vector<vector<ll>>
#define P pair<ll,ll>

using namespace std;

int charToInt(char a){
    return a - '0';
}

void updateModArray(int *a){
    loop(i,10){
        a[i] = (a[i] * 10) % 13;
    }
}

int main(){
    string s;
    ll MOD = 1000000007;
    int mod[10] = {0,1,2,3,4,5,6,7,8,9};
    vector<ll> ans(13,0);
    cin >> s;

    ans[0] = 1;
    for(int i = s.size()-1;i >= 0; i--){
        
        vector<ll> updatedAns(13,0);
        if(s[i] == '?'){
            loop(i,10){
                loop(j,13){
                    updatedAns[(j+mod[i]) % 13] += ans[j];
                }
            }
        }else{
            int num = charToInt(s[i]);
            loop(j,13){
                updatedAns[(j + mod[num]) % 13] += ans[j];
            }
        }

        loop(i,13){
            updatedAns[i] %= MOD;
        }

        ans = updatedAns;
        updateModArray(mod);

    }


    cout << ans[5] << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(void){
int n;
int x;
int num;
int min=1000001;
int max=-1000001;
long total=0;
scanf("%d",&n);
for(x=0;x<n;x++){
scanf("%d",&num);
if(min>num) min=num;
if(max<num) max=num;
total+=num;
}
printf("%d %d %ld\n",min,max,total);
return 0;
}

Measured memory_bytes: 600
#include <cstdio>
#include <vector>
using namespace std;

int main(){
    vector<int> A;
    int num_query; scanf("%d",&num_query);
    int command,tmp;
    for(int loop =0; loop < num_query; loop++){
        scanf("%d",&command);
        switch (command)
        {
        case 0:
            scanf("%d",&tmp);
            A.push_back(tmp);
            break;
        case 1:
            scanf("%d",&tmp);
            printf("%d\n",A[tmp]);
            break;
        case 2:
            A.pop_back();
            break;
          
        
        }        
    }
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
#define repi(n) for (long long i = 0; i < (n); ++i)
#define repj(n) for (long long j = 0; j < (n); ++j)
#define repk(n) for (long long k = 0; k < (n); ++k)
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = std::max(t, (v)))
#define updatemin(t, v) (t = std::min(t, (v)))

ll a[200100], ss[200100];
int main() {
  ll n, k;
  cin >> n >> k;
  repi(n) cin >> a[i];
  repi(n)-- a[i];
  repi(n) ss[i] = -1;
  ll current = 0;
  repi(n + 1) {
    ss[current] = i;
    current = a[current];
    if (ss[current] != -1) {
      ll pres = ss[current];
      ll looplen = (i + 1) - pres;
      if (k >= pres) k = pres + ((k - pres) % looplen);
      break;
    }
  }
  current = 0;
  repi(k) current = a[current];
  cout << current + 1 << endl;
}


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

#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<
#define pb push_back
#define ar array

typedef long long ll;
typedef long double ld;
//using ll = long long;

typedef vector<int> vi;

const ld EPS = 1e-9, PI = acos(-1.);
const int INF = 0x3f3f3f3f, MOD = 1e9+7;

// global to problem
int arr[200002];
int ans[200002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;
	for(int i=2; i<=n; i++){
		cin >> arr[i];
	}
	for(int i=2; i<=n; i++){
		ans[arr[i]]++;
	}
	for(int i=1; i<=n; i++){
		cout << ans[i] << "\n";
	}
}



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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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;}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	int n;cin>>n;
	vl c(n-1),s(n-1),f(n-1);
	rep(i,n-1){
		cin>>c[i]>>s[i]>>f[i];
	}
	rep(i,n-1){
		ll m=i,ans=s[i]+c[i];
		while(m<n-2){
			m++;
            if(s[m]>ans){ans+=s[m]-ans+c[m];continue;}
			if(ans%f[m]!=0){
				ans+=(f[m]-ans%f[m])+c[m];
				continue;
			}
			ans+=c[m];
		}
		cout<<ans<<endl;
	}
    cout<<0<<endl;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n,t;
int a[maxn];
map<int,int> ai;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>t;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    int buy=1e9;
    int mx=0;
    for (int i=0; i<n; i++) {
	if (a[i]-buy>mx) {
	    mx=a[i]-buy;
	}
	buy=min(buy,a[i]);
    }


    int ans=0;
    for (int i=0; i<n; i++) {
	if (ai.count(a[i]-mx)) {
	    ans++;
	}
	ai[a[i]]=i;
    }

    cout<<ans<<endl;

    return 0;
}


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

int main() {
    //freopen("input1.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, w;
    cin >> n >> w;
    vector<long long int> a(n), b(n);
    for (int i=0; i<n; i++)
        cin >> a[i] >> b[i];
    vector<long long int> dp(w+1, 0);
    for (int i=0; i<n; i++){
        for (int j=w; j>=a[i]; j--)
            dp[j] = max(dp[j], dp[j-a[i]]+b[i]);
    }
    cout << dp[w];
    return 0;
}

Measured memory_bytes: 3980
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
	vector<int> even(100001, 0), odd(100001, 0);
	int n;
	cin >> n;
	int v;
	for (int i = 0; i < n; ++i) {
		cin >> v;
		if (i % 2 == 0) ++even[v];
		else ++odd[v];
	}

	int firstEven = -1, secondEven = -1, firstOdd = -1, secondOdd = -1;
	int evenMaxIndice = -1, oddMaxIndice = -1;
	for (int i = 0; i < 100001; ++i)
		if (even[i] > firstEven)
			secondEven = firstEven, firstEven = even[i],
			evenMaxIndice = i;
		else if (even[i] > secondEven)
			secondEven = even[i];
	for (int i = 0; i < 100001; ++i)
		if (odd[i] > firstOdd)
			secondOdd = firstOdd, firstOdd = odd[i],
			oddMaxIndice = i;
		else if (odd[i] > secondOdd)
			secondOdd = odd[i];

	int evenRes = n / 2 - firstEven;
	int oddRes = n / 2 - firstOdd;
	int res = evenRes + oddRes;

	if (evenMaxIndice == oddMaxIndice) {
		int e2 = n / 2 - secondEven;
		int o2 = n / 2 - secondOdd;
		int res2 = evenRes + o2;
		int res3 = e2 + oddRes;
		res = min(res2, res3);
	}

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
   string S,T;
   cin>>S;
   
   if(S=="Sunny"){
       T="Cloudy";
   }
   else if(S=="Cloudy"){
       T="Rainy";
   }
   else{
       T="Sunny";
   }
    cout<<T<<endl;

}


Measured memory_bytes: 3592
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple
{
    int N, C, K;
    int[] T;
    void Solve() {
        //input
        N = io.Int;
        C = io.Int;
        K = io.Int;
        T = new int[N];
        for (int i = 0; i < N; ++i)
            T[i] = io.Int;
        //cal
        Array.Sort(T);
        var time = T[0] + K;
        var mem = 1;
        var ans = 0;
        for (int i = 1; i < N; ++i) {
            if (T[i] <= time && mem++ < C) continue;
            ans++;
            mem = 1;
            time = T[i] + K;
        }
        ans++;
        //ret
        Console.WriteLine(ans);

    }
    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() { Solve(); io.writeFlush(); }
}
class SimpleIO
{
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


Measured memory_bytes: 17208
/**-------------------------
|--------From A.R.A--------|
-------------------------**/

#include <bits/stdc++.h>

#define ll            long long int
#define pb            push_back
#define ull           unsigned long long int
#define endl          "\n"
#define sz(c)         (c).size()
#define sall(c)       sort((c).begin(),(c).end())
#define rsall(c)      sort((c).rbegin(),(c).rend())
#define rev(c)        reverse((c).begin(),(c).end())
#define FOR(i,n)      for(ll i=0;i<n;i++)
#define max3(a,b,c)   max(max(a,b),c)
#define min3(a,b,c)   min(min(a,b),c)
#define input(a,i,n)  for(ll i=0;i<n;i++){      cin>>a[i];}
#define output(a,i,n) for(ll i=0;i<n;i++){cout<<a[i]<<" ";}

using namespace std;
int64_t R=1;
void solution(){
    int64_t n,h,c=0,mx=0;
    cin>>n;
    cin>>h;
    for(int64_t i=1,x;i<n;i++){
        cin>>x;
        if(h>=x){c++;}
        else{c=0;}
        h=x;
        mx=max(c,mx);
    }
    cout<<mx<<endl;
}
int main()
{
    FOR(i,R){solution();}
    return 0;
}


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

int main(){
  long long x, y;
  vector<long long> v;
  cin >> x >> y;

  v.push_back(x);
  for(long long i=x; i<=y;){
    if(i*2<=y){
      v.push_back(x*2);
    }
    i *= 2;
  }

  cout << v.size() <<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
long long s1[100005],s2[100005];
long long sum;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	s1[2]=a[1]*2;
	for(int i=3;i<=n;i+=2)
		s1[i+1]=s1[i-1]+a[i]*2;
	s2[n-1]=a[n-1]*2;
	for(int i=n-3;i>=1;i-=2)
		s2[i]=s2[i+2]+a[i]*2;
	for(int i=1;i<=n;i++)
		if(i%2==1)
			printf("%lld ",sum-(s1[i-1]+s2[i+1]));
		else
			printf("%lld ",s1[i]+s2[i]-sum);
}


Measured memory_bytes: 3328
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1: #素数の場合はここ
        arr.append([temp, 1])
 
    if arr==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr

N,P = map(int,input().split())
A = factorization(P)
#print(A)
ans = 1
for X in A:
  p,q = X
  ans *= p**(q//N)
print(ans)

Measured memory_bytes: 9460
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct NODE{
	int to, cost, ticket;
	NODE(int to, int cost, int ticket) : to(to), cost(cost), ticket(ticket) {}
	NODE() {}
};

// 小さい順になる（らしい
bool operator < (const NODE &a, const NODE &b)
{
	return a.cost > b.cost;
}

int main(void)
{
	int c, n, m, s, d;
	while (cin >> c >> n >> m >> s >> d, n){
		s--;
		d--;
		vector <NODE> edge[100];
		for (int i = 0; i < m; i++){
			int a, b, f;
			cin >> a >> b >> f;
			a--;
			b--;
			// むこうぐらふ
			edge[a].push_back(NODE(b, f, -1));
			edge[b].push_back(NODE(a, f, -1));
		}
		// done[町][チケット]
		// その町でチケットが n 残ってるときに訪れたかどうか
		bool done[110][15] = {};
		priority_queue <NODE> Q;
		// すたーと，こすと0，ちけっと
		Q.push(NODE(s, 0, c));
		while (Q.size()){
			NODE q = Q.top();
			Q.pop();
			if (done[q.to][q.ticket]) continue;
			else done[q.to][q.ticket] = true;
			if (q.to == d){
				cout << q.cost << endl;
				break;
			}
			for (int i = 0; i < edge[q.to].size(); i++){
				Q.push(NODE(edge[q.to][i].to, q.cost + edge[q.to][i].cost, q.ticket));
				if (q.ticket) Q.push(NODE(edge[q.to][i].to, q.cost + (edge[q.to][i].cost / 2), q.ticket-1));
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1312
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Rep(i, N) for(int i = 0; i < N; i++)
#define Reps(i, x, N) for(int i = x; i < N; i++)

signed main()
{
  int N;
  string S;
  bool flag = false;
  
  cin >> N >> S;
  
  Rep(p, 4) {
    string T;
    Rep(i, 2) {
      if((p >> i) & 1) T += 'W';
      else T += 'S';
    }

    Reps(i, 2, N) {
      bool mask = false;
      if(T[i - 2] == 'W') mask ^= true;
      if(T[i - 1] == 'W') mask ^= true;
      if(S[i - 1] == 'x') mask ^= true;

      if(mask) T += 'W';
      else T += 'S';
    }

    int enf = T.size() - 1;

    if((p & 1) && S[0] == 'x' || !(p & 1) && S[0] == 'o') {
      if(T[1] != T[enf]) continue;
    } else {
      if(T[1] == T[enf]) continue;
    }
    if(S[enf] == 'o' && T[enf] == 'S' || S[enf] == 'x' && T[enf] == 'W') {
      if(T[enf - 1] != T[0]) continue;
    } else if(T[enf - 1] == T[0]) continue;

    cout << T << endl; flag = true;
    break;
  }

  if(!flag) cout << -1 << endl;
  return 0;
}

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

int main() {
  vector<char> a(3);
  cin >> a.at(0) >> a.at(1) >> a.at(2);
  sort(a.begin(), a.end());
  vector<char> b = {'a', 'b', 'c'};
  if (a == b) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   f(i,1,10){
      f(j,1,10){
         if(n==i*j){
            cout << "Yes\n";
            return 0;
         }
      }
   }
   cout << "No\n";
   return 0;
} 

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

int main()
{
  int N;
  cin >> N;
  long A[N + 1], B[N];
  for (int i = 0; i < N + 1; i++) cin >> A[i];
  for (int i = 0; i < N; i++) cin >> B[i];

  long res = 0;
  for (int i = 0; i < N; i++)
  {
    if (A[i] >= B[i])
    {
      res += B[i];
      continue;
    }
    else
    {
      res += A[i];
      B[i] -= A[i];
    }
    if (A[i + 1] >= B[i])
    {
      res += B[i];
      A[i + 1] -= B[i];
    }
    else
    {
      res += A[i + 1];
      A[i + 1] = 0;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 5152
gets
x=gets.split.map(&:to_f)
y=gets.split.map(&:to_f)
da=[]
x.each_with_index{|v,i| da[i]=(v-y[i]).abs}
d1=0.0
da.each{|i| d1+=i}
puts d1
d2=0.0
da.each{|i| d2=d2+i**2}
puts Math.sqrt(d2)
d3=0.0
da.each{|i| d3+=i**3}
puts Math.cbrt(d3)
puts da.max

Measured memory_bytes: 6208
N = int(input())
s = [int(input()) for _ in range(N)]

ans = sum(s)
if ans % 10 != 0:
  print(ans)
else:
  s.sort()
  for i in range(N):
    if s[i] % 10 != 0:
      print(ans - s[i])
      exit()
  print(0)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int N = sc.nextInt();
        double[] p = new double[N + 1];
        double[][] f = new double[N + 1][N + 1];
        for(int i = 1; i <= N;  i++)p[i] = sc.nextDouble();

        // 投i次，向上次数为j;
//        f[0][0] = 1;
//        for(int i = 1; i <= N; i ++){
//            f[i][0] = f[i - 1][0] * (1 - p[i]);
//            for(int j = 1; j <= i; j ++){
//                f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);
//            }
//        }
//        int cnt;
//        if((N&1) == 1) cnt = N + 1 >> 1;
//        else cnt = (N >> 1) + 1;
//        double res = 0.0;
//        for(int i = cnt; i <= N; i++)res += f[N][i];
//        System.out.println(res);
//         向上次数为i，投j次
        f[0][0] = 1;
        for(int j = 1; j <= N; j ++) {
            f[0][j] = f[0][j - 1] * (1 - p[j]);
        }
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j ++){
//                f[0][j] = f[0][j - 1] * (1 - p[j]);
                f[i][j] = f[i - 1][j - 1] * p[j] + f[i][j - 1] * (1 - p[j]);
            }
        }
        double res = 0.0;
        for(int i = 0; i <= N; i ++){
            if(i > (N - i))res += f[i][N];
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 133776
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int N,K;
    int n;
    cin>>N>>K;
    vector<int> v(N,0);
    for(int i=0;i<N;i++){
        cin>>n;
        v[n-1]++;
    }
    sort(v.begin(),v.end());
    int z=0;
    for(int i=0;v[i]==0;i++){
        z++;
    }
    N-=z;
    K=N-K;
    int ans=0;
    for(int i=0;K>0;i++){
        K--;
        ans+=(v[z+i]);
    }
    cout<<ans;
}


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

using namespace std;
int main()
{
	ll l,r,d;
	cin >> l >> r >> d;
	if(l%d==0)
	{
		cout << (r-l)/d + 1 << endl;
	}
	else
	{
		if((l/d+1)*d<r)
		{
			if(r%d==0)
			{
				cout << (r-l)/d + 1 << endl;
			}
			else
			{
				cout << (r-l)/d << endl;
			}
		}
		else
		{
			cout << 0 << endl;
		}
	}
}

Measured memory_bytes: 3600
using System;
using System.Linq;
using System.Collections.Generic;

namespace ConsoleApp2
{
    public class Program
    {
        private static string[] enki = new string[2] { "AT", "GC" };
        public static void Main(string[] args)
        {
            string S = Console.ReadLine();

            for (int i = 0; i < S.Length; i++)
            {
                if (S[i] != 'A' && S[i] != 'T' && S[i] != 'G' && S[i] != 'C')
                {
                    S = S.Replace(S[i],',');
                }
            }
            string[] newS = S.Split(',');

            int ans = 0;

            foreach (string item in newS)
            {
                //Console.WriteLine(item);
                ans = ans < item.Length ? item.Length : ans;
            }

            Console.WriteLine(ans);

        }



        private static long[] Read(string input)
        {
            string[] inputs = input.Split(' ');
            long num = inputs.Length;
            long[] longs = new long[num];
            for (long i = 0; i < num; i++)
            {
                longs[i] = long.Parse(inputs[i]);
            }
            
            return longs;
        }


    }
}


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

typedef pair<int, int> pii;

bool cmp(pii l, pii r){
  return (l.first > r.first);
}

int main()
{
  vector<pii> vpii;
  int a, b;
  while (scanf("%d,%d", &a, &b), a || b){
    vpii.push_back(make_pair(b, a));
  }
  sort(vpii.begin(), vpii.end(), cmp);
  map<int, int> mii;
  int j = 1;
  int m = vpii.size();
  for (int i = 0; i < m; i++){
    if (i != m - 1 && vpii[i].first == vpii[i + 1].first){
      mii[vpii[i].second] = j;
    }
    else {
      mii[vpii[i].second] = j++;
    }
  }

  int c;
  while(cin >> c){
    cout << mii[c] << "\n";
  }
}

Measured memory_bytes: 3060
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = True
show_flg = False


def is_prime(n):
    """
    nの素数判定
    :param int n:
    :rtype: Bool
    """
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(is_prime(i) and is_prime((i+1)//2)))
        else:
            arr.append(0)

    ARR = list(accumulate([0] + arr))
    # print(arr[:100])
    # print(ARR[:100])

    for i in range(Q):
        # print(r[i]+1, l[i], ARR[r[i]+1], ARR[l[i]])
        # print(ARR[:r[i]+1])
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()


Measured memory_bytes: 80728
#include <bits/stdc++.h>
using namespace std;
int h, w, k;
const int INF = 1e9;
const int N = 850;
string A[N]; int vis[N][N];
int ans = INF; queue <int> Q;
int check(int i, int j)
{
    return ans = min(ans, (min(min(i, h - 1 - i), min(j, w - 1 - j)) + k - 1) / k + 1);
}
int main()
{
    cin >> h >> w >> k;
    for (int i = 0; i < h; ++ i)
        cin >> A[i];
    for (int i = 0; i < h; ++ i)
        for (int j = 0; j < w; ++ j)
            if (A[i][j] == 'S')
                Q.push(i), Q.push(j), Q.push(k),
                vis[i][j] = 1;
    while (!Q.empty())
    {
        int i = Q.front(); Q.pop();
        int j = Q.front(); Q.pop();
        int k = Q.front(); Q.pop();
        if (check(i, j) == 1) break;
        if (k == 0) continue;
        for (int di = -1; di <= 1; ++ di)
            for (int dj = -1; dj <= 1; ++ dj)
                if (abs(di) + abs(dj) == 1) if (A[i + di][j + dj] == '.' && !vis[i + di][j + dj])
                    Q.push(di + i), Q.push(dj + j), Q.push(k - 1),
                    vis[i + di][j + dj] = 1;
    }

    cout << ans << endl;
}


Measured memory_bytes: 2176
#include<iostream>

using namespace std;

int main(){
    long N, K ,Q;
    cin >> N >> K >> Q;
    long A[N];
    for(int i=0; i<N; i++){
        A[i] = K - Q;
    }
    int a;
    for(int i = 0; i<Q; i++){
        cin  >> a;
        A[a-1] += 1;
    }
    for(int i=0; i<N; i++){
        if(A[i] <= 0) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}

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

ban = [[False] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            ban[i][j] = True
def solve(i, j):
    for dy, dx in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        if 0 <= i + dy < H and 0<= j + dx < W:
            if s[i+dy][j+dx] == "#":
                ban[i][j] = True
                ban[i+dy][j+dx] = True
    return

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            solve(i, j)

for h in range(H):
    if not all(ban[h][i] for i in range(W)):
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i;i<n;i++)
#define ALL(a) (a).begin(),(a).end()

bool compare_by_b(pair<long, long> a, pair<long, long> b){
    return a.second < b.second;
}

int main(){
    ll n;
    cin >> n;
    vector<int> a(n+1);
    rep(i, n)cin >> a[i+1];
    vector<int> count(200010, 0);
    vector<int> res;

    
    for(int i = n; i > 0; i--){ 
        ll p = i*2;
        ll c = 0; 
        while(p <= n){
            if(count[p] == 1)c++;
            p+=i;
        }
        if(c%2 != a[i]){
            count[i] = 1;
            res.push_back(i);
        }
    }

    if(res.size() == 0){
         cout << 0;
         return 0;
    }
    cout << res.size() << endl;
    rep(i, res.size())cout << res[res.size()-1-i] << " ";

}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
struct rbtree: tree<T,null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>{};
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;

const int N = 20;
int res[N];
int c[N];
int a[N][N];

int main(){
    IOS;
    //IN;
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = -1;
        }
    }
    for(int i = 1; i <= n; i++){
        cin>>c[i];
        for(int j = 1; j <= c[i]; j++){
            int y, z; cin>>y>>z;
            a[i][y] = z;
        }
    }
    int ans = 0;
    for(int i = 1; i <= (1<<n)-1; i++){
        bool f = 0;
        int cnt=0;
        for(int j = 1; j <= n; j++)res[j] = 0;
        for(int j = 0; j < n; j++){
            if(i&(1<<j)){
                cnt++;
                res[j+1]++;
            }
        }
        for(int j = 1; j <= n; j++){
            if(!res[j])continue;
            for(int z = 1; z <= n; z++){
                if(z==j)continue;
                if(a[j][z] == -1)continue;
                if((a[j][z] == 0 && res[z]) || (a[j][z] == 1 && !res[z])){
                    f=1;
                    break;
                }
            }
            if(f)break;
        }
        //cout<<"1===="<<cnt<<endl;
        if(!f)ans = max(ans, cnt);
    }
    cout<<ans;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=9e5+5,mo=1e9+7;

typedef long long LL;

int n,m,K,ans,Fac[N],Inv[N],p[N];

int C(int n,int m)
{
    return (LL)Fac[n]*Inv[m]%mo*Inv[n-m]%mo;
}

int main()
{
    p[0]=Fac[0]=Inv[0]=Fac[1]=Inv[1]=1; p[1]=3;
    for (int i=2;i<N;i++) Inv[i]=(LL)Inv[mo%i]*(mo-mo/i)%mo;
    for (int i=2;i<N;i++)
    {
        p[i]=p[i-1]*3ll%mo; Fac[i]=(LL)Fac[i-1]*i%mo; Inv[i]=(LL)Inv[i-1]*Inv[i]%mo;
    }
    scanf("%d%d%d",&n,&m,&K); n--;
    if (m<K) swap(m,K);
    for (int i=0,j=1;i<=m+K;i++)
    {
        ans=(ans+(LL)C(n+i,n)*p[m+K-i]%mo*j)%mo;
        if (i<K) j=j*2%mo;
        else if (i>=m) j=(j*2ll-C(i,K)-C(i,i-m))%mo;
        else j=(j*2ll-C(i,K))%mo;
    }
    if (ans<0) ans+=mo;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 10752
H,W = map(int,input().split())

table = [[0]*(W+1) for i in range(H+1)]


for row in range(H):
    work = list(map(int,input().split()))
    for col in range(W):
        table[row][col] = work[col]


for row in range(H):
    for col in range(W):
        table[row][W] += table[row][col]


for col in range(W+1):
    for row in range(H):
        table[H][col] += table[row][col]

for row in range(H+1):
    for col in range(W+1):
        if(col == W):
            print("{}".format(table[row][col]),end="\n")
        else:
            print("{}".format(table[row][col]),end=" ")




Measured memory_bytes: 6204
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 500010
#define mod 1000000007
struct cv{
    int x,y,z,d;
}a[maxn];
bool cmp(cv p,cv q){
    if(p.x!=q.x) return p.x>q.x;
    return p.y<q.y;
}
bool cmp1(cv p,cv q){
    return p.y<q.y;
}
int main(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i].x);
        a[i].y=i;
    }
    sort(a,a+n,cmp);
    for(int i=1;i<n;i++){
        if(a[i].x==a[i-1].x) a[i].z=a[i-1].z;
        else a[i].z=i;
    }
    sort(a,a+n,cmp1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n-1;j++){
            if(a[j].x>a[j+1].x){
                a[j].d++;
                swap(a[j],a[j+1]);
            }
        }
    }
    sort(a,a+n,cmp1);
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=k*a[i].d%mod;
        ans%=mod;
        ans+=(((k-1)*k/2)%mod)*a[i].z%mod;
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

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

def floor_sum(n, m, a, b):  # (a*i+b)//m の i=0～n-1 の和を求める。O(log(n+m+a+b))
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans

t = int(input())
for i in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Measured memory_bytes: 79132
N, L = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7


if L>=1:
	a = L
elif L<=(-1*N):
	a = L+N-1
else:
	a = 0

ans=-1*a
for i in range(1,N+1):
	ans += L+i-1

print(ans)



Measured memory_bytes: 3068
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

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

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

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

    long long ans = 0;
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            auto it = lower_bound(L.begin() + j, L.end(), L[i] + L[j]);

            ans += it - L.begin() - j - 1;
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

#define endl "\n"
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1n(i, n) for (int i = 1; i < (int)(n); ++i)
#define forln(i, n) for (long long i = 0; i < (long long)(n); ++i)
#define forl1n(i, n) for (long long i = 1; i < (long long)(n); ++i)


const ll maxLONG = 9223372036854775807;
const int maxINT = 2147483647;
const ll mod = 1000000007;
const ld EPS = 1e-9;
const int N = 1e2 + 9;
const int N2 = 1e5 + 9;
const ll INF = LONG_LONG_MAX;

ll GetMod(ll n, ll z) { // func to get mod for positive num and negitive nums
    return (n % z + z) % z;
}

//          U   R  D  L
int dx[] = {-1, 0, 1, 0, -1, +1, +1, -1}; // dx for the 8 adjacent places in matrix
int dy[] = {0, 1, 0, -1, +1, +1, -1, -1};// dy for the 8 adjacent places in matrix

pair<ll, ll> p[N];
ll n, w;
ll dp[N][N2];

ll check(ll i, ll sum) {

    if (i == n) {
        if (sum != 0) {
            return 1e17;
        }
        return 0;
    }

    if (dp[i][sum] != -1)return dp[i][sum];

    ll a = 1e17;

    if (sum - p[i].second >= 0)
        a = min(a, check(i + 1, sum - p[i].second) + p[i].first);

    a = min(a, check(i + 1, sum));

    dp[i][sum] = a;
    return a;

}

void clear() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N2; j++)
            dp[i][j] = -1;
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    cin >> n >> w;
    ll maxsum = 0;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        maxsum += p[i].second;
    }

    clear();

    ll ans = 1e17;
    ll f = 1e17;


    for (ll i = maxsum; i >= 1; i--) {
        ans = check(0, i);

        if (ans <= w) {
            f = i;
            break;
        }

    }
    if (ans == 1e17)
        cout << 0 << endl;
    else
        cout << f << endl;
}


Measured memory_bytes: 88824
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////


int main() {
	ll N;
	cin >> N;

	if (N == 3) {
		cout << 2 << " " << 5 << " " << 63;
	}
	if (N >= 4) {
		ll M = min(N / 2, 7500);

		ll t = min(M / 2,2500);
		ll s = M - t;
		ll u = N - 2 * M;

		rep(i, s) {
			cout << 6 * i + 2 << " " << 6 * i + 4 << " ";
		}

		rep(i, t) {
			cout << 12 * i + 3 << " " << 12 * i + 9<<" ";
		}

		repn(i, u) { cout << 6 * i<<" "; }
	}

	system("PAUSE");
}


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

int main(){
  int N, M;
  cin >> N >> M;
  multiset<int> A;
  for (int i=0; i<N; i++){
    int n;
    cin >> n;
    A.insert(n);
  }

  for (int i=0; i<M; i++){
    auto itr = A.end();
    itr--;
    int half = *itr / 2;
    A.erase(itr);
    A.insert(half);
  }

  long long ans = 0;
  auto itr = A.begin();
  for (int i=0; i<N; i++){
    ans += *itr;
    ++itr;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 5120
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

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

  ll K;
  cin >> K;

  int N = 50;

  vector<ll> ans(N, 0);
  for (int j = 0; j < N; j++) {
    ans[j] = j + K / N;
  }
  ll remain = K % N;
  for (int j = 0; j < remain; j++) {
    ans[j] += N;
    for (int k = 0; k < N; k++) {
      if (k != j) {
        ans[k] -= 1;
      }
    }
  }
  cout << N << endl;
  for (int i = 0; i < N; i++) {
    cout << ans[i];
    if (i < N - 1) {
      cout << " ";
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
n = STDIN.gets.chomp.to_i
a = STDIN.gets.chomp.split(" ").map{|x| x.to_i}

max_cnt = 0
cnt = 0
for i in 0..(n-1) do
  while (a[i] & 1) == 0 do
    a[i] >>= 1
    cnt += 1
  end
  if cnt > max_cnt
    max_cnt = cnt
  end
end
puts max_cnt

Measured memory_bytes: 4476
N = int(input())
S = input()
res = []
for i in range(1,N):
    X=S[:i]
    Y=S[i:]
    count = 0
    o=set()
    for j in X:
        
        if (not j in o) and j in Y:
            count+=1
            o.add(j)
    res.append(count)
print(max(res))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define C(n,m) ((LL)fac[n]*ifac[m]%mo*ifac[(n)-(m)]%mo)
#define CC(a,b) C((a)+(b)-2,(a)-1)

const int N=2e5;
const int maxn=N+10;
const int mo=1e9+7;

int H,W,A,B,fac[maxn],ifac[maxn],Ans;

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

int main()
{
#ifdef h10
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
#endif
	int i;
	scanf("%d%d%d%d",&H,&W,&A,&B);
	fac[0]=1;
	for (i=1;i<=N;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	ifac[N]=power(fac[N],mo-2);
	for (i=N;i>=1;i--)
		ifac[i-1]=(LL)ifac[i]*i%mo;
	for (int i=1;i<=H-A;i++)
		(Ans+=(LL)CC(B,i)*CC(H-i+1,W-B)%mo)%=mo;
	printf("%d\n",Ans);
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	double a = 0.0;
	if (n % 2 == 0) {
		a = 1.0 / 2.0;
	}
	else a = (n + 1.0) / (n * 2. - 0);
	cout << a << endl;
}

Measured memory_bytes: 256
from functools import lru_cache

@lru_cache(maxsize=1000)
def add(a,b):
  return a + b ;

N = int(input())

ans = [0] * (N+2)
ans[0] = 2
ans[1] = 1

for i in range(N):
    ans[i+2] = add(ans[i],ans[i+1])

print(ans[N])

Measured memory_bytes: 3572
unittest
{
	assert( [ "3 5 4", "11100", "10001", "00111" ].solve == 2 );
	assert( [ "3 5 8", "11100", "10001", "00111" ].solve == 0 );
	assert( [ "4 10 4", "1110010010", "1000101110", "0011101001", "1101000111" ].solve == 3 );
}



import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto h = 0L;
	auto w = 0L;
	auto k = 0L;
	input.front.formattedRead!"%s %s %s"( h, w, k );
	auto sss = new dchar[][]( h, w );
	foreach( ref ss; sss )
	{
		input.popFront;
		ss = input.front.to!( dchar[] );
	}
	
	// 横に割るところをbit全列挙
	auto ans = long.max;
	LOOP: foreach( b; 0L .. 1L << ( h - 1 ) )
	{
		// 横に割るところを境にしてy座標ごとにグルーピング
		auto n = 0L;
		auto ps = new long[ h ];
		foreach( y, ref p; ps )
		{
			p = n;
			if( b & ( 1L << y ) ) n++;
		}
		
		// 縦に割るところを貪欲法で判定
		auto d = n;
		auto ts = new long[ n + 1 ];
		foreach( x; 0L .. w )
		{
			auto dd = false;
			auto cs = new long[ n + 1 ];
			foreach( y, p; ps )
			{
				if( sss[ y ][ x ] == '1' )
				{
					cs[ p ]++;
					if( k < cs[ p ] ) continue LOOP;			// 一列でkを超えるので無理
					if( k < cs[ p ] + ts[ p ] ) dd = true;		// kを超えるのでこの列の手前で割る
				}
			}
			d += dd;
			if( dd ) ts[]  = cs[];
			else     ts[] += cs[];
		}
		ans = min( ans, d );
	}
	return ans;
}


Measured memory_bytes: 4128
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound, __gcd, count, find, next_permutation
#include <bitset>    // bitset
#include <deque>     // deque
#include <iomanip>   // setprecsion
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <utility>   // pair, make_pair
#include <vector>    // vector

#include <cassert> // assert
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>  // abs, sin, cos, tan
#include <ctime> // clock

// __builtin_popcountll

using namespace std;
using Graph = vector<vector<int>>;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

void Main()
{
  ll n; cin >> n;
  vll h(n); rep(i, n) cin >> h[i];
  vll dp(n, MAX);
  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);
  for(ll i = 2;i < n;i++)
  {
    dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
  }
  fin(dp[n - 1]);
  return;
}

//前処理
int main()
{
  int ti = clock();
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  //cout << fixed << setprecision(20); //高精度少数表示
  //cout << setfill('0') << internal << setw(4); 0埋め４桁
  Main();
  printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
  return 0;
}

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

int main(){
int n;cin>>n;
vector <double> v;
vector <string> str;
while(n--){
    double a;string s;
    cin>>a>>s;
    v.push_back(a);
    str.push_back(s);
}
double ans=0;
    for(int i=0;i<v.size();i++){
        if(str[i]=="JPY")ans+=v[i];
        else if(str[i]=="BTC"){
            ans+=v[i]*380000;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 888
n = int(input())

def solve(s):
    if int(s) > n:
        return 0
    if '7' in s and '5' in s and '3' in s:
        count = 1
    else:
        count = 0
    count += solve(s + '7')
    count += solve(s + '5')
    count += solve(s + '3')
    return count

print(solve('0'))

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

const int MAX = 100001;

int main(){
    int N,M;
    int table[MAX] = {0};
    int cnt = 0;
    int ans = 0;

    cin >> N >> M;
    for(int i = 0;i < M;i++){
        int l,r;
        cin >> l >> r;
        table[l-1]++;
        table[r]--;
    }

    for(int i = 0;i < N;i++){
        cnt += table[i];
        if(cnt >= M)ans++;
    }

    cout << ans << endl;

    return 0;
}

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

//昇順にソート
int compare(const void *a, const void * b){
  return *(int *)a - *(int *)b;
}

int main(){
  int N;
  int a[110] = {};
  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    scanf("%d", &a[i]);
  }
  qsort(a, N, sizeof(int), compare);
  printf("%d\n", a[N-1] - a[0]);
  return 0;
}


Measured memory_bytes: 128
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

L = [0]*(N+1)
R = [0]*(N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N-i+1], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i],R[i+1]))

print(ans)

Measured memory_bytes: 63856
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    s=S()
    if s=="ABC":
        print("ARC")
    else:
        print("ABC")

if __name__ == "__main__":
    main()

Measured memory_bytes: 9604