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

/*#### modular_arithmetic */
class modular_arithmetic{
public:
	int mod, range;
	vector<int> fac, ifac;

	modular_arithmetic(){
		mod = 1000000007;
	}
	//No specific settings.
	void set_mod(int _mod){mod = _mod;}
	int add(int x,int y){return (x+y)%mod;}
	int sub(int x,int y){return (x-y+mod)%mod;}
	int mul(int x,int y){return (int)((long long int)x*y%mod);}
	int pw(int x,int y){
		int r = 1;
		while(1){
			if(y&1)r=mul(r,x);
			if(y>>=1)x=mul(x,x);else
				break;
		}
		return r;
	}
	//mod must be a prime.
	int inv(int x){
		return pw(x, mod-2);
	}
	int div(int x,int y){
		return mul(x, inv(y));
	}
	void init(int _range, int _mod = 1000000007){
		range = min(_range, _mod);
		set_mod(_mod);
		fac.resize(range);
		ifac.resize(range);
		fac[0] = ifac[0] = 1;
		for(int i=1; i<range; i++){
			fac[i] = mul(fac[i-1], i);
			ifac[i] = pw(fac[i], mod-2);
		}
	}
	int comb(int x, int y){
		if(x<y)return 0;
		return mul(fac[x], mul(ifac[y],ifac[x-y]));
	}
};
/*####*/
modular_arithmetic ma;

int n,m,dep[ran],maxdep[ran],cnt;
set<int> e[ran];
int d[ran][2];
void dfs(int x){
	maxdep[x] = dep[x];
	for(auto y : e[x]){
		dep[y] = dep[x] + 1;
		dfs(y);
		maxdep[x] = max(maxdep[x], maxdep[y]);
	}
}


int ace[ran];int ancestor(int x){return x-ace[x]?ace[x]=ancestor(ace[x]):x;}
int D;
void dfs2(int x){
	if(dep[x] == D){
		d[x][0] = 1;
		d[x][1] = 1;
		cnt++;
		return;
	}
	int part = 1, all = 1;
	d[x][1] = 0;
	set<int> to_erase;
	for(auto yy : e[x]){
		int y = ancestor(yy);
		if(maxdep[y] < D){to_erase.insert(yy);continue;}
		dfs2(y);
		part = ma.mul(part, d[y][0]);
		d[x][1] = ma.add(d[x][1], ma.div(d[y][1],d[y][0]));
		all = ma.mul(all, ma.add(d[y][0],d[y][1]));
	}
	d[x][1] = ma.mul(d[x][1], part);
	d[x][0] = ma.sub(all, d[x][1]);
	for(auto y : to_erase){
		e[x].erase(y);
	}
	if(e[x].size() == 1)
		ace[x] = ancestor(*e[x].begin());
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		int x;
		scanf("%d",&x);
		e[x].insert(i);
	}
	dep[0] = 0;
	dfs(0);
	for(int i=0; i<=n; i++)
		ace[i] = i;
	int out = 0, m = maxdep[0];
	for(int i=0; i<=m; i++){
		cnt = 0;
		D = i;
		dfs2(ancestor(0));
		out = ma.add(out, ma.mul(ma.pw(2, n+1-cnt), d[ancestor(0)][1]));
	}
	printf("%d\n",out);
	return 0;
}


Measured memory_bytes: 32384
def f_d():
    import math
    a, b, x = map(int, input().split())
    x2 = x/(a**2)
    if x2 >= b/2:
        print(math.degrees(math.atan((b-x2)/(a/2))))
    else:
        print(math.degrees(math.atan(b/((2*x)/(b*a)))))

if __name__ == "__main__":
    f_d()


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

int main() {
  int N;
  cin >> N;
  vector<int> M(N+1);
  for (long long i = 1; i <= N; i++) {
    for (long long j = 1; j <= N; j++) {
      if (i*j > N) break;
	  M.at(i*j)++;
    }
  }
  long long sum = 0;
  for (long long i = 1; i <= N; i++) {
    sum += M.at(i)*i;
  }
  cout << sum << endl;
}

Measured memory_bytes: 42308
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, V: "List[int]"):
    m = 0
    for k in range(0,min(K+1,N+1)):
        for l in range(k+1):
            r = k - l
            d = K - k
            arr = sorted(V[:l]+V[N-(k-l):])
            sum = 0
            n = []
            for a in arr:
                if a < 0 and d > 0:
                    d-=1
                    continue 
                sum += a
                n.append(a)
            m = max(sum,m)
    print(m)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, V)

if __name__ == '__main__':
    main()


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

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

typedef unsigned long ul;

using namespace std;

int main(){
	int n,count;
	while(cin >> n){
		REP(a, 10){
			REP(b, 10){
				REP(c, 10){
					REP(d, 10){
						if(a+b+c+d == n)
							count++;
					}
				}
			}
		}
		cout << count << endl;
		count = 0;
	}
}

Measured memory_bytes: 1160
#include <stdio.h>

using namespace std;
typedef long long llong;

#define MAX

int main()
{
  llong N;
  llong powered6[21];
  char name[21];
  scanf("%lld", &N);

  powered6[0] = 0;
  powered6[1] = 26;
  for (int i = 2; i < 21; i++)
  {
    powered6[i] = powered6[i - 1] * 26;
  }

  int cnt = 0;
  while (1)
  {
    if (powered6[cnt] >= N)
    {
      break;
    }
    N -= powered6[cnt];
    cnt++;
  }
  N--;

  name[cnt] = 0;
  for (int i = cnt - 1; i >= 0; i--)
  {
    name[i] = 'a' + N % 26;
    N /= 26;
  }

  printf("%s\n", name);

  return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //A*Bの行列とB*Cの行列、計A*B*C回の乗算をしてA*Cの行列になる
    int N; cin >> N;
    int R[N], C[N]; rep(i, N) cin >> R[i] >> C[i];
    int dp[N+1][N+1];
    rep(i, N+1) rep(j, N+1) dp[i][j] = INF;
    rep(i, N+1) dp[i][i+1] = 0;
    for(int haba = 2; haba <= N; haba++){
        for(int left = 0; left < N; left++){
            int right = left + haba;
            if(right > N) break;
            for(int boarder = left+1; boarder <= right-1; boarder++){
                dp[left][right] = min(dp[left][right], dp[left][boarder] + dp[boarder][right] + R[left]*C[boarder-1]*C[right-1]);
            }
        }
    }

    cout << dp[0][N] << endl;
    return 0;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> P;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#ifdef DEBUG
std::ostream& dout = cout;
#else
stringstream dout;
#endif
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
signed main(signed argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
    int n,k,c;
    cin>>n>>k>>c;
    string s;
    cin>>s;
    priority_queue<int> que;
    que.push(0);
    vector<int> memo(n,0);
    vector<vector<int>> cnt(k+1);
    rep(i,n){
        if(i-c>0){
            que.push(memo[i-c-1]);
        }
        if(s[i]!='x') {
			memo[i] = min(que.top() + 1, k);
			cnt[memo[i]].push_back(i);
		}
    }
    vector<int> ans;
    int before=LLONG_MAX;
    for(int i=k;i>0;i--){
        auto be=lower_bound(cnt[i].begin(),cnt[i].end(),before-c);
        if(be-cnt[i].begin()==1){
            ans.push_back(cnt[i][0]+1);
        }
        be--;
        auto e=lower_bound(cnt[i].begin(),cnt[i].end(),*be-c);
        if(e!=cnt[i].begin()){
            e--;
            cnt[i-1].push_back(*e);
        }
        before=*be;
    }
    reverse(ans.begin(),ans.end());
    rep(i,ans.size()){
        cout<<ans[i]<<endl;
    }
    if(ans.size()==0)cout<<endl;
}


Measured memory_bytes: 17544
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define ld long double
typedef pair<ll,ll> pll;
typedef pair<pll,pll> ppll;
typedef vector <ll> vi;
#define out(x) return cout<<x,0;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define lc(n) 2*n+1
#define rc(n) 2*n+2
# define INF 0x3f3f3f3f
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

int main(){
	FAST;
    ll n, k, m, z = 0, ans = 0, j, t = 0, x = 0, y = 0, c = 0, i;
    char ch , T;
    cin >> ch;
    T = ch  + 1;
    cout << T;
}

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

N=int(input())
A=[0]*N
B=[0]*N
C=[0]*N

for i in range(N):
  A[i],B[i] = map(int,input().split())
  C[i]=(A[i],B[i],A[i]+B[i])

t=0
a=0

C.sort(key= lambda x: x[2],reverse=True)
#print(C)
#C.sort(key= lambda x: x[0],reverse=True)
for i in range(N):
  if i%2==0:
    t += C[i][0]
  else:
    a += C[i][1]

print(t-a)

Measured memory_bytes: 23664
import numpy as np

n = int(input())
listn = [i+1 for i in range(n)]
t,a= (int(i) for i in input().split())  
listx = [int(i) for i in input().split()]
b=np.array(listx)
b= abs(a-(t-0.006*b))

dictz=dict(zip(listn,b))

print( min(dictz, key=(lambda x: dictz[x])))


Measured memory_bytes: 18932
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n, x;
    cin >> n >> x;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) cin >> v[i];
	sort(v.begin(), v.end());
	int sum = 0, cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (sum + v[i] > x) break;
		sum += v[i];
        cnt++;
	}
	if (cnt == n && sum < x) cnt--;
	cout << cnt << endl;
}


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

using namespace std;

using int64 = long long;

int main()
{
  string s;
  cin >> s;
  for(int i = 0; i < (1 << 3); i++) {
    int cur = s[0] - '0';
    string v;
    v += s[0];
    for(int j = 1; j < 4; j++) {
      if((i >> (j - 1)) & 1) {
        cur += s[j] - '0';
        v += "+";
        v += s[j];
      } else {
        cur -= s[j] - '0';
        v += "-";
        v += s[j];
      }
    }
    if(cur == 7) {
      cout << v << "=7" << endl;
      return(0);
    }
  }

}


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

using namespace std;

#define ll long long
#define ld long double

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

ll INF = (ll) 1e20;
int iINF = (int) 1e20;
ll mod = (ll) 1e9 + 7;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, l;
    cin >> n >> m >> l;
    vector <vector <pair <ll, ll>>> nodes(n);
    for(int i = 0; i < m; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        if(c <= l) {
            nodes[a].push_back({b, c});
            nodes[b].push_back({a, c});
        }
    }
    pair <ll, ll> d[n][n];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            d[i][j] = {INF, INF};
        }
        d[i][i] = {0, l};
        vector <bool> used(n, false);
        for(int j = 0; j < n; ++j) {
            pair <pair <ll, ll>, ll> now = {{INF, INF}, INF};
            for(int k = 0; k < n; ++k) {
                if(!used[k]) {
                    if(d[i][k].first != INF) {
                        if(now.first.first > d[i][k].first) {
                            now = {d[i][k], k};
                        }
                        else if(now.first.first == d[i][k].first) {
                            if(now.first.second < d[i][k].second) {
                                now = {d[i][k], k};
                            }
                        }
                    }
                }
            }
            if(now.first.first == INF)
                break;
            used[now.second] = true;
            ll v = now.second;
            for(auto k : nodes[v]) {
                if(!used[k.first]) {
                    ll left_here = now.first.second;
                    left_here -= k.second;
                    ll num = now.first.first;
                    if(left_here < 0) {
                        num++;
                        left_here = l - k.second;
                    }
                    if(d[i][k.first].first > num) {
                        d[i][k.first] = {num, left_here};
                    }
                    else if(d[i][k.first].first == num) {
                        if(d[i][k.first].second < left_here) {
                            d[i][k.first] = {num, left_here};
                        }
                    }
                }
            }
        }
//        cout << i << '\n';
//        for(int j = 0; j < n; ++j) {
//            cout << d[i][j].first << ' ' << d[i][j].second << '\n';
//        }
    }
    ll q;
    cin >> q;
    while(q--) {
        ll a, b;
        cin >> a >> b;
        --a;
        --b;
        if(d[a][b].first == INF) {
            cout << -1 << '\n';
        }
        else {
            cout << d[a][b].first << '\n';
        }
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  constexpr int MAX = 50;
  auto valid = [&](long long bs) {
    for (int i = 0; i < n; i++) {
      vector<int> reach(MAX + 1, false);
      reach[a[i]] = true;
      for (int j = MAX; j >= 1; j--) if ((bs >> j) & 1) {
        for (int k = 0; k <= MAX; k++) if (reach[k]) {
          reach[k % j] = true;
        }
      }
      if (!reach[b[i]]) return false;
    }
    return true;
  };
  long long bs = (1LL << MAX + 1) - 1;
  if (!valid(bs)) {
    cout << -1 << endl;
    return 0;
  }
  for (int j = MAX; j >= 0; j--) {
    if (valid(bs ^ (1LL << j))) {
      bs ^= (1LL << j);
    }
  }
  cout << bs << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX_N 100

int main(){
  int n,max,min,i,arr[MAX_N],sum;
  int use_max,use_min;
  while(1){
    use_max = use_min = 0;
    max = sum = 0; min = 1000;
    scanf("%d",&n);
    if(n == 0){ break; }
    for(i = 0 ; i < n ; i++){
      scanf("%d",&arr[i]);
      if(max < arr[i]){ max = arr[i]; }
      if(min > arr[i]){ min = arr[i]; }
    }
    for(i = 0 ; i < n ; i++){
      if(max == arr[i]){
        if(use_max == 0){
          use_max = 1;
          continue;
        }
      }
      if(min == arr[i]){
        if(use_min == 0){
          use_min = 1;
          continue;
        }
      }
      sum += arr[i];
    }
    printf("%d\n",sum/(n-2));
  }
  return 0;
}

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

#define N_MAX 100
#define MOD 2019

int main() {
    long L, R;
    cin >> L >> R;
    long Ldiv = L / MOD;
    long Rdiv = R / MOD;

    long ans = 3000;

    if (Ldiv != Rdiv) {
        ans = 0;
    }
    else {
        for (long i = L % MOD; i < (R % MOD); i++) {
            for (long j = (L % MOD) + 1; j <= (R % MOD); j++) {
                ans = min(ans, ((i * j) % MOD));
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n;
    cin >>n;
    int p[n]={};

    for (int i = 0; i < n; i++){
        cin  >>p[i];
    }

    for (int i = 0; i < n; i++){
        if(i==n-1 && p[i]==n){
            int pi=p[i];
            p[i]=p[i-1];
            p[i-1]=pi;
            ++ans;
        }

        if(p[i] == i+1){
            
            int pi = p[i];
            p[i]=p[i+1];
            p[i+1]=pi;

            ++ans;
        }
    }
    
    

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 640
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] h = new Integer[n];
        Arrays.setAll(h, i -> Integer.parseInt(sc.next()));

        // 主処理
        h[0]--;
        for (int i = 1; i < h.length; i++) {
            if (h[i - 1] < h[i]) {
                h[i]--;
            }
        }
        boolean judge = true;
        for (int i = 1; i < h.length; i++) {
            if (h[i - 1] > h[i]) {
                judge = false;
                break;
            }
        }
        String result = judge ? "Yes" : "No";

        // 出力
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 50680
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
using namespace std;


int main(void) {
  long long int inf = 1000000000000;
  long long int h, w;
  cin >> h >> w;
  if( h % 3 == 0 || w % 3 == 0 ){
    cout << 0 << endl;
    return 0;
  }



  long long int ans = inf;
  long long int bh = h/2, ch = h/2;
  if( h % 2 == 1 ) bh++;
  long long int a = h;

  for(int i=1; i<=w; i++){
    long long int b = (w - i) * bh;
    long long int c = (w - i) * ch;
    long long int tmp = max(a, max(b, c)) - min(a, min(b, c));

    long long int d = (w - i)/2, e = (w - i)/2;
    if( (w-i) % 2 == 1 ) d++;
    d *= h; e *= h;
    long long int tmp2 = max(a, max(d, e)) - min(a, min(d, e));

    // cerr << a << " " << b << " " << c << " " << tmp << endl;
    ans = min( ans, tmp );
    ans = min( ans, tmp2 );
    a += h;
  }

  long long int bw = w/2, cw = w/2;
  if( w % 2 == 1 ) bw++;
  a = w;

  for(int i=1; i<=h; i++){
    long long int b = (h - i) * bw;
    long long int c = (h - i) * cw;
    long long int tmp = max(a, max(b, c)) - min(a, min(b, c));

    long long int d = (h - i)/2, e = (h - i)/2;
    if( (h-i) % 2 == 1 ) d++;
    d *= w; e *= w;
    long long int tmp2 = max(a, max(d, e)) - min(a, min(d, e));

    // cerr << a << " " << b << " " << c << " " << tmp << endl;
    ans = min( ans, tmp );
    ans = min( ans, tmp2 );
    a += w;
  }


  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
s = gets.chomp

ans = 0
if s =="SUN"
  ans = 7
elsif s == "MON"
  ans = 6
elsif s == "TUE"
  ans = 5
elsif s == "WED"
  ans = 4
elsif s == "THU"
  ans = 3
elsif s == "FRI"
  ans = 2
elsif s == "SAT"
  ans = 1
end

puts ans


Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        int[] AN = new int[N];
        for (int i = 0; i < N; i++) {
            AN[i] = Integer.parseInt(sc.next());
        }
        int[] BN = new int[N];
        for (int i = 0; i < N; i++) {
            BN[i] = Integer.parseInt(sc.next());
        }
        int[] CN = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            CN[i] = Integer.parseInt(sc.next());
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            int choice = AN[i];
            if (i + 1 < N && choice + 1 == AN[i + 1]) {
                ans += CN[choice - 1];
            }
            ans += BN[choice - 1];
        }
        System.out.println(ans);
    }

}


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

int a, b;

int GCD(int a, int b){
	if(a < b) swap(a, b);
	if(b == 0) return a;
	return GCD(b, a % b);
}

int main(){
	while(cin >> a >> b){
		cout << GCD(a, b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3036
use std::str::FromStr;
use std::fmt::Debug;

fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

struct CombMod{
    fac: Vec<u64>,
    inv: Vec<u64>,
    finv: Vec<u64>,
    mmod: u64,
}

impl CombMod{
    pub fn new(max: u64, m: u64) -> CombMod{
        let max: usize = max as usize;
        let mut fac: Vec<u64> = vec![0;max+1];
        let mut finv: Vec<u64> = vec![0;max+1];
        let mut inv: Vec<u64> = vec![0;max+1];

        fac[0] = 1;
        fac[1] = 1;
        finv[0] = 1;
        finv[1] = 1;
        inv[1] = 1;

        for i in 2..max+1{
            fac[i] = fac[i-1] * i as u64 % m;
            inv[i] = m - inv[m as usize %i] * (m/(i as u64)) % m;
            finv[i] = finv[i-1] * inv[i] % m;
        }
        
        CombMod{
            fac: fac,
            finv: finv,
            inv: inv,
            mmod: m,
        }
    }

    fn get(&self, n: u64, m: u64) -> u64{
        assert!(n >= m && n != 0 && m != 0);
        self.fac[n as usize] * self.finv[m as usize] % self.mmod * self.finv[(n-m) as usize] % self.mmod
    }

    
}

fn factorize(m: u64) -> Vec<u64>{
    let mut v: Vec<u64> = Vec::new();
    let mut target = m;
    for x in 2..(m as f64).sqrt().ceil() as u64{
        let mut counter = 0;
        while target % x == 0{
            target /= x;
            counter += 1;
        }
        if counter != 0{
            v.push(counter);
        }
    }
    if target > 1{
        v.push(1);
    }
    
    v
}

fn main(){
    let line: Vec<u64> = read_as_vec();
    let (n, m) = (line[0], line[1]);
    let f = factorize(m);
    let mut ans = 1;
    let comb = CombMod::new(1000000, 1000000007);
    for x in &f{
        ans *= comb.get(*x+n-1, *x);
        ans %=1000000007;
    }
    println!("{}", ans);
}


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    
    int n=s.size();
    int m=t.size();
    
    int nmax=3000,mmax=3000;
    VVi dp(nmax+1,Vi(mmax+1,0));
    REP(i,0,n){
        REP(j,0,m){
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    
    string res = "";
    int i=n,j=m;
    while (i>0 && j>0)
    {
        if (dp[i][j] == dp[i-1][j]) {
            --i;
        }
        else if (dp[i][j] == dp[i][j-1]) {
            --j;
        }

        else {
            res = s[i-1] + res;
            --i; --j;
        }
    }
    
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 70784
N,K=map(int, input().split())
R,S,P=map(int, input().split()) 
T = list(input())

ten = [0] * N
for i in range(N):
    if (T[i] == 'r'):
        ten[i] = P
    elif(T[i] == 's'):
        ten[i] = R
    else:
        ten[i] = S
 

for i in range(N-K):
    if(T[i] == T[i+K]):
        ten[i+K] = 0
        T[i+K] = 'o'


print(sum(ten))

Measured memory_bytes: 4792
#include<iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

string field[2160];
int l[2160][2160];
int r[2160][2160];
int d[2160][2160];
int u[2160][2160];

int  main(){
    int h, w;
    cin >> h >> w;
    for (int i= 0 ;i<h; i ++){
        cin >> field[i];
    }
    for(int i = 0;i < h; i ++){
        for(int j= 0;j < w; j++){
            if(field[i][j] == '#'){
                l[i][j] = 0;
                u[i][j] = 0;
            }
            else{
                u[i][j] = (i==0)?1:u[i-1][j] + 1;
                l[i][j] = (j==0)?1:l[i][j-1] + 1;
            }
        }
    }
    for(int i = h-1;i >=0; i --){
        for(int j= w-1;j >= 0 ; j--){
            if(field[i][j] == '#'){
                r[i][j] = 0;
                d[i][j] = 0;
            }
            else{
                d[i][j] = (i==h-1)?1:d[i+1][j] + 1;
                r[i][j] = (j==w-1)?1:r[i][j+1] + 1;
            }
        }
    }
    int res = 0;
    for (int i = 0;i < h ;i++){
        for(int j = 0; j < w; j++){
            if(field[i][j] == '#')continue;
            res = max(res, r[i][j]+ l[i][j]+d[i][j]+ u[i][j]-3);
        }
    }
    cout << res << endl;

    return 0;

}

Measured memory_bytes: 76032
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;
public class Main{
	public static void main(final String[] args){
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s = sc.next();
    int count = 0;

    if(n % 2 == 1){
        count++;
    }
    char[] work = new char[s.length()];

    for(int i = 0; i < n; i++){
            work[i] = s.charAt(i);
            }
    
    for(int i = 0; i < n/2; i++){
        if(work[i] == work[i+n/2]){
        }else{
            count++;
        }
    }      

    if(count == 0){
        System.out.println("Yes");
    }else{
        System.out.println("No");
    }
    
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;

class UnionFind
{
private:
  vector<int> parent, rank;
  
public:
  UnionFind(int n)
  {
    for (int i = 0; i < n; ++i) {
      parent.push_back(i);
      rank.push_back(0);
    }
  }
  
  int find(int x)
  {
    if (parent[x] == x)
      return x;
    else
      return parent[x] = find(parent[x]);
  }
  
  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if (x == y)
      return;
    
    if (rank[x] < rank[y]) {
      parent[x] = y;
    } else {
      parent[y] = x;
      if (rank[x] == rank[y])
        ++rank[x];
    }
  }
  
  bool same(int x, int y)
  {
    return find(x) == find(y);
  }
};

class Edge
{
public:
  int a, b, c, idx;
  Edge() {}
  Edge(int a_, int b_, int c_, int idx_)
    :a(a_), b(b_), c(c_), idx(idx_) {}
  bool operator < (const Edge& edge) const
  {
    return this->c > edge.c;
  }
};

void dfs(int v, deque<bool>& visited, const vector<Edge>& edge, const deque<bool>& sinking)
{
  if (visited[v])
    return;

  visited[v] = true;
  for (unsigned int i = 0; i < edge.size(); ++i) {
    const Edge& e = edge[i];
    if (e.a == v && !sinking[e.b])
      dfs(e.b, visited, edge, sinking);
    else if (e.b == v && !sinking[e.a])
      dfs(e.a, visited, edge, sinking);
  }
}

int main()
{
  int N, M;
  while (cin >> N >> M) {
    if ((N|M) == 0)
      break;

    vector<int> h(N), next;
    next.push_back(0);
    next.push_back(1000001);
    for (int i = 0; i < N; ++i) {
      cin >> h[i];
      next.push_back(h[i]);
    }
    sort(next.begin(), next.end());
    next.erase(unique(next.begin(), next.end()), next.end());

    vector<Edge> edge;
    for (int i = 0; i < M; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      edge.push_back(Edge(a-1, b-1, c, i));
    }

    unsigned int i = 0;
    deque<bool> sinking(N, false);
    for (; i < next.size(); ++i) {
      int v = -1;
      for (int j = 0; j < N; ++j) {
        if (h[j] == next[i])
          sinking[j] = true;
        if (!sinking[j])
          v = j;
      }
      
      if (v == -1)
        break;

      deque<bool> visited(N, false);
      dfs(v, visited, edge, sinking);

      if (count(visited.begin(), visited.end(), true) +
          count(sinking.begin(), sinking.end(), true) != N)
        break;
    }

    int ans = 0;
    UnionFind uf(N);
    deque<bool> used(M, false);
    for (; i > 0; --i) {

      for (int j = 0; j < N; ++j) {
        if (h[j] == next[i])
          sinking[j] = false;
      }

      priority_queue<Edge> que;
      for (int j = 0; j < M; ++j) {
        if (used[j])
          continue;
        const Edge& e = edge[j];
        if (sinking[e.a] || sinking[e.b])
          continue;
        que.push(e);
      }

      while (!que.empty()) {
        const Edge& e = que.top();
        if (!uf.same(e.a, e.b)) {
          uf.unite(e.a, e.b);
          used[e.idx] = true;
          ans += e.c;
        }
        que.pop();
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2428
#include <bits/stdc++.h>
#define xx first
#define yy second
#define ll long long
using namespace std;

struct _in {
	const _in operator , (int &a) const {
		a = 0; char k = getchar (); int f = 1;
		while (k > '9' || k < '0') { if (k == '-') f = -1; k = getchar (); }
		while (k >= '0' && k <= '9') { a = a * 10 + k - '0'; k = getchar (); }
		a *= f;
		return*this;
	}
}in;

//const int N = ;
/*const int mod = ;
inline int add (int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
inline int sub (int u, int v) { return u - v < 0 ? u - v + mod : u - v; }
inline int mul (int u, int v) { return 1LL * u * v % mod; }
inline int qpow (int base, int v) {
	int tot = 1;
	while (v) {
		if (v & 1) tot = mul (tot, base);
		base = mul (base, base);
		v >>= 1;
	}
	return tot;
}*/

const int N = 5000 + 5;
int info[N], n, nxt[N];
char a[N];

int main () {
	in, n;
	scanf ("%s", a + 1);
	for (int i = 1; i <= n; ++i)
		info[i] = a[i] - '0';
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		memset (nxt, 0, sizeof nxt);
		int* p = info + i - 1;
		int cur = 0, sz = n - i + 1;
		for (int k = 1; k <= sz; ++k) {
			while (cur && p[k + 1] != p[cur + 1])
				cur = nxt[cur];
			nxt[k + 1] = cur + (p[k + 1] == p[cur + 1]);
			cur += p[k + 1] == p[cur + 1];
		}
		cur = 1;
		for (int k = 1; k <= sz; ++k) {
			while (cur && cur > k / 2) cur = nxt[cur];
			ans = max (ans, cur);
			while (cur && p[cur + 1] != p[k + 1])
				cur = nxt[cur];
			cur += p[cur + 1] == p[k + 1];
		}
	}
	printf ("%d\n", ans);
	return 0;
}






























Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	lli N,M;
	cin>>N>>M;
	lli ans=min(M/2,(2*N+M)/4);
	cout<<ans;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9+5
#define INT long long
using namespace std;
int main(){
    int n;
    int a[100005];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    
    int cnt=0,mn=INF;
    INT sum=0;
    for(int i=0;i<n;i++){
        if(a[i]<0) cnt++;
        mn = min(mn,abs(a[i]));
        sum+=abs(a[i]);
    }
    if(cnt%2==1) sum-=mn*2;
    cout<<sum<<endl;
    return 0;
}



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

#pragma GCC optimize("O3")

using namespace std;

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

typedef long long ll;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

int main() {
    ll n;
    cin >> n;
    unordered_set<ll> data;
    for(int i = 0; i < n; ++i) {
		ll value;
		cin >> value;
		data.insert(value);
	}
	
	if((ll)data.size() != n) {
		cout << "NO";
	}  else {
		cout << "YES";
	}
    
    return 0;
}


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

int main() {
	long long X;
	cin >> X;

	long long A,B;
	int i_tmp,j_tmp,j_max;

	for(int i=-120;i<120;i++){
		for(int j=-120;j<120;j++){
			if( pow(i,5) - pow(j,5) == X){
				cout << i << " " << j << "\n";
				return 0;
			}
		}
	}
}

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

int f(int x) {
    if(x == 0) return 0;
    return f(x % __builtin_popcount(x)) + 1;
}

int main()
{
    int n;
    string s;
    cin >> n >> s;
    vector<int> x(n);
    for(int i = 0; i < n; i++) x[i] = s[i] - '0';
    int pc = 0;
    for(int i = 0; i < n; i++) pc += x[i];
    vector<int> ans(n);
    for(int b = 0; b < 2; b++) {
        int npc = pc;
        if(b == 0) npc++;
        else npc--;
        if(npc <= 0) continue;
        int r0 = 0;
        for(int i = 0; i < n; i++) {
            r0 = (r0 * 2) % npc;
            r0 += x[i];
        }
        int k = 1;
        for(int i = n - 1; i >= 0; i--) {
            if(x[i] == b) {
                int r = r0;
                if(b == 0) r = (r + k) % npc;
                else r = (r - k + npc) % npc;
                ans[i] = f(r) + 1;
            }
            k = (k * 2) % npc;
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 5192
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main() {
	int K, T, a, ans = 0, b = -1;
	cin >> K >> T;
	priority_queue<pair<int, int>> c;
	for (int i = 0; i < T; i++) {
		cin >> a;
		c.emplace(a, i);
	}
	while (!c.empty()) {
		pair<int, int> d = c.top();
		c.pop();
		if (b == d.second) {
			if (c.empty()) {
				ans++;
				b = d.second;
				d.first--;
				if (d.first) c.push(d);
			}
			else {
				pair<int, int> e = c.top();
				b = e.second;
				c.pop();
				c.push(d);
				e.first--;
				if (e.first) c.push(e);
			}
		}
		else {
			b = d.second;
			d.first--;
			if (d.first) c.push(d);
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int gcd(int a,int b){
    int c = a%b;
    while(c!=0){
        a = b;
        b = c;
        c = a%b;
    }
    return b;
}
int sumgcd(int a,int b,int c){
    int s[3];
    s[0]=a;
    s[1]=b;
    s[2]=c;
    int ans = s[0];
    for(int i=1;i<3;i++){
        ans = gcd(ans,s[i]);
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    long long sum = 0ll;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
             for(int k=1;k<=n;k++){
                int temp = sumgcd(i,j,k);
                sum += temp;
                //printf("i:%d,j:%d,k:%d  %d\n",i,j,k,temp);
             }
        }
    }
    printf("%lld\n",sum);
}


Measured memory_bytes: 1728
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BeginnerContest157
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = int.Parse(Console.ReadLine());
            var result = input % 2 == 0 ? input / 2 : (input / 2) + 1;

            Console.WriteLine(result);
        }
    }
}


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


int main() {
    int A, B;
    cin >> A >> B;

    int digit[5];
    int result = 0;

    for (int x=A; x<=B; x++) {
        int X=x;
        for (int d=0; d<5; d++) {
            digit[d] = X%10;
            X = X/10;
        }
//cout << digit[4] << digit[3] << digit[2] << digit[1] << digit[0] << endl;
        if (digit[0]==digit[4] && digit[1]==digit[3]) {
            result++;
//cout << "hit" << endl;
        }
    }

    cout << result << endl;

}


Measured memory_bytes: 256
def merge(l, r, a):
    l1 = len(l)
    r1 = len(r)
    i,j,k=0,0,0
    while j<l1 and k<r1:
        if l[j]<=r[k]:
            a[i]=l[j]
            j+=1
        else:
            cnt[0] += l1-j
            a[i]=r[k]
            k+=1
        i+=1
    while j<l1:
        a[i]=l[j]
        j+=1
        i+=1
    while k<r1:
        a[i]=r[k]
        k+=1
        i+=1
    return a
def merge_sort(a):
    n = len(a)
    if n==1:
        return a
    else:
        mid = n//2
        left = [0]*mid
        right = [0]*(n-mid)
        for i in range(mid):
            left[i] = a[i]
        for i in range(mid,n):
            right[i-mid]=a[i]
    merge_sort(left)
    merge_sort(right)
    merge(left,right,a)
    return a

n,k = map(int,input().split())
a = list(map(int,input().split()))
cnt = [0,0]
ans4 = 0
a = merge_sort(a)
for i in range(1,n):
    if a[i]==a[i-1]:
        cnt[1]+=1
        if i == n-1:
            ans4+=(1+cnt[1])*cnt[1]//2
    else:
        ans4+=(1+cnt[1])*cnt[1]//2
        cnt[1]=0

ans2 = (n*(n-1))//2 - cnt[0]-ans4
print((cnt[0]*(1+k)*k//2+ans2*k*(k-1)//2)%(10**9+7))

Measured memory_bytes: 3188
n = gets.to_i
a = []
n.times do
  a << gets.to_i
end
migi_a = []
migi_max = 0
a.size.times do |i|
  migi_max = [migi_max, a[i]].max
  migi_a << migi_max
end
# p migi_a

hidari_a = []
hidari_max = 0
a.size.times do |i|
  hidari_max = [hidari_max, a[(a.size) - 1 - i]].max
  hidari_a << hidari_max
end
hidari_a.reverse!
# p hidari_a

p hidari_a[1]
(a.size - 2).times do |i|
  p [migi_a[i], hidari_a[i+2]].max
end
p migi_a[-2]

=begin
4
3
4
#
5
5
=end


Measured memory_bytes: 8500
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
#include<ctime>
#include<locale>
using namespace std;
int main()
{
    bool c[26];
    char s[50];
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    fgets(s,50,stdin);
    for(long i=0;s[i]<='z'&&s[i]>='a';i++)
    {
        if(c[s[i]-'a']==0)c[s[i]-'a']=1;
        else {cout<<"no";return 0;}
    }
    cout<<"yes";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  
int main(){
  
  long long i, N, Souwa = 0;
  cin >> N;
  vector<long long> B(N - 1);
  
  for(i = 0; i < N - 1; i++){
    
    cin >> B.at(i);
  }
  
  Souwa += B.at(0) + B.at(N - 2);
  for (i = 0; i < N - 2; i++){
    Souwa += min(B.at(i), B.at(i + 1));
  }
  
  cout << Souwa << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
  bool x[10] = {};
  for(int i = 0; i < 4; ++i){
    int tmp;
    cin >> tmp;
    x[tmp] = true;
  }
  if (x[1] && x[9] && x[7] && x[4])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin >>s;
    int f = 0;
    int b = s.size()-1;
    int count = 0;
    while (f<b){
        if(s.at(f) != s.at(b)){
            count++;
        }
        f++;
        b--;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define N 200100
#define mod 1000000007
#define fn(i,n) for(int i=0;i<n;i+=1)
#define rep(i,l,r) for(int i=l;i<=r;i+=1)
#define INF 100000000000000
#define pii pair<int,int>
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

signed main()
{
    
    speed
    int n;cin>>n;
    map<string,int> mp;
    rep(i,1,n){
      string x;cin>>x;
      mp[x]++;
    }
    cout<<mp.size()<<endl;

 
 
    return 0;
}

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

using namespace std;
const int n = 100010;

int a[n];
int N,L,T;

int main() {
  cin >> N >> L >> T;
  long long tr = 0;
  for(int i = 0, w; i < N; i++) {
    cin >> a[i] >> w;
    if(w == 1) {
      a[i] += T;
      tr += a[i] / L;
      a[i] %= L;
    }
    else {
      a[i] -= T;
      tr += a[i] / L;
      a[i] %= L;
      if(a[i] < 0) {
	a[i] += L;
	tr--;
      }
    }
  }
  sort(a,a+N);
  tr %= N;
  tr = (tr + N) % N;
  for(int i = 0; i < N; i++) {
    cout << a[(i+tr) % N] <<endl;
  }
  return 0;
}

  

  
    
  


Measured memory_bytes: 1536
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

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

int main() {
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll n_c=b/c-(a-1)/c;
  ll n_d=b/d-(a-1)/d;
  ll l=c/gcd(c,d)*d;
  ll n_cd=b/l-(a-1)/l;
  cout<<b-a+1-(n_c+n_d-n_cd)<<endl;
  return 0;
}



Measured memory_bytes: 256
//https://cs.stackexchange.com/questions/84426/find-a-node-with-maximum-distance-from-given-node-in-a-tree
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
//#include <ext/rope> //header with rope
//using namespace __gnu_cxx;
//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
// find_by_order tells index pr kon hai..
// order_by_key  tells ki us element se kitne strictly smaller element hai...
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Senky_Bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{   
    Senky_Bansal
    IIIT_ALLAHABAD
    
    ll n;
  cin>>n;
  vector<pair<ll,ll>>v;
  ll a[n],b[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
    cin>>b[i];
    v.pb(mpr(a[i],b[i]));
  }
  sort(v.rbegin(),v.rend());
  ll ans=0;
  for(int i=0;i<v.size();i++)
  {
      if(v[i].fr>=v[i].se)
      {
          ans+=v[i].fr-v[i].se;
      }
  }
  cout<<ans<<endl;
    




}








Measured memory_bytes: 256
s = gets.chomp.to_i
a = [s]
i = 2

while i >= 0
    if a[-1] % 2 == 0
        if a.include?(a[-1]/2)
            puts i
            exit
        else
            a << a[-1]/2
            i += 1
        end
    else
        if a.include?(a[-1]*3 +1)
            puts i
            exit
        else
            a << a[-1]*3 +1
            i += 1
        end
    end
end


Measured memory_bytes: 1788
#include <stdio.h>


int main()
{
	int n,m;
	int i;
	int x;
	int daisu;
	int count=0;
	int data[1000];
	x=0;
	while(1){
		scanf("%d %d", &n, &m);
		if(n==0&&m==0){
			break;
		}
		for(i=0; i<n; i++){
			while(1){
				scanf("%d", &data[i]);
				if(data[i]>=-999&&data[i]<=999){
					break;
				}
			}
		}
		for(i=0; i<m; i++){
			scanf("%d", &daisu);
			if(x>=n-1){										//既にゴールしていたら、残りの処理をスキップ。
				continue;
			}
			count++;
			x+=daisu;
			if(x>=n-1){										//既にゴールしていたら、残りの処理をスキップ。
				continue;
			}
			x+=data[x];
			
		}
		printf("%d\n", count);
		count=0;
		x=0;
	}
	return 0;
}

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

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef long double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


int main() {

    int N;
    cin >> N;
    vector<ll> H;
    forn(i, N) {
        ll h; cin >> h;
        H.pb(h);
    }
    ll max = H[0];
    string ans;

    for (int i = 1; i < N; i++) {
        if (max < H[i]) max = H[i];
        if (max - H[i] >= 2) {
            cout << "No" << endl;
            return 0;
        }
        
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 1400
#
# File    : B.rb
# Author  : Kazune Takahashi
# Created : 2019-5-26 21:03:02
# Powered by Visual Studio Code
#

n = gets.to_i
ary = []
for i in 1..n
  s, q = gets.chomp.split(" ").map{|x| x.to_s}
  q = q.to_i
  ary << [s, -q, i]
end
ary.sort.each{|s, q, i|
  puts i
}

Measured memory_bytes: 1788
#include <iostream>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    string S;
    cin >> S;
    
    int E[N], W[N];
    if(S[0] == 'W'){
        E[0] = 0;
        W[0] = 1;
    } else{
        E[0] = 1;
        W[0] = 0;
    }
    
    for(int i = 1; i < N; i++){
        if(S[i] == 'W'){
            W[i] = W[i-1] + 1;
            E[i] = E[i-1];
        } else{
            W[i] = W[i-1];
            E[i] = E[i-1] + 1;
        }
    }
    
    int tmp = N;
    for(int i = 1; i < N; i++){
        tmp = min(tmp, W[i-1] + E[N-1] - E[i]);
    }
    
    cout << min(tmp, E[N-1] - E[0]) << endl;
}


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

using ll = long long;
using G = vector<vector<int>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;

ll GCD(ll x, ll y){
	return y ? GCD(y, x%y) : x;	
}

int main() {
	string s; cin >> s;
	if(s=="ABC"){
		cout << "ARC" << endl;
		return 0;
	}else{
		cout << "ABC" << endl;
	}
	
	return 0;
}

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

    dp = [False] * (10000 + 1)
    dp[0] = True

    for x in s:
        for score in range(10000 - x, -1, -1):
            dp[score + x] |= dp[score]

    for score in range(10000, -1, -1):
        if dp[score] and score % 10 != 0:
            print(score)
            return
    print(0)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    try(Scanner sc = new Scanner(System.in)){
      while(true){
        int n = sc.nextInt();
        if(n == 0)break;
        int[] scores = new int[n];
        int sum = 0;
        for(int i=0;i<scores.length;i++){
          scores[i] = sc.nextInt();
          sum += scores[i];
        }
        double average = (double)sum / n,variance = 0;
        for(int i=0;i<scores.length;i++){
          variance += (double)((scores[i] - average)  * (scores[i] - average));
        }
        variance = (double)variance / n;
        System.out.printf("%.10f\n",Math.sqrt(variance));
      }
    }
  }
}



Measured memory_bytes: 31840