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

int alpha[26];

int main(void){
    long n;
    string s;
    cin >> n >> s;
    for(auto c : s){
        alpha[c-'a']++;
    }
    long ans = 1;
    for(auto i : alpha){
        ans = ans * (i+1) % 1'000'000'007;
    }
    std::cout << ans-1 << std::endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[11];
    gets(s);
    if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I') cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    n, m = map(int, input().split())
    p = map(int, input().split())
    trans = []

    for _ in range(m):
        x, y = map(int, input().split())
        trans.append((x, y))
    
    ss = dict()

    for t in trans:
        x, y = t
        xs = ss.get(x, None)
        ys = ss.get(y, None)

        if xs is None and ys is None:
            zs = set([x, y])
            ss[x] = zs
            ss[y] = zs
        elif xs is not None and ys is None:
            xs.add(y)
            ss[y] = xs
        elif xs is None and ys is not None:
            ys.add(x)
            ss[x] = ys
        else:
            if id(xs) == id(ys):
                continue

            if len(xs) >= len(ys):
                for yy in ys:
                    ss[yy] = xs
                    xs.add(yy)
            else:
                for xx in xs:
                    ss[xx] = ys
                    ys.add(xx)

    c = 0
    for i, v in enumerate(p, 1):
        if i == v:
            c += 1
        elif i in ss and v in ss[i]:
            c += 1
    print(c)

main()

Measured memory_bytes: 45012
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    string S;
    ll Q;
    cin >> S >> Q;
    vector<ll> T(Q), F(Q);
    vector<char> C(Q);

    for(int i=0; i<Q; i++){
        cin >> T[i];
        if(T[i] == 2) cin >> F[i] >> C[i];
    }

    bool isrev = false;
    string pre;
    for(int i=0; i<Q; i++){
        if(T[i] == 1) isrev = !isrev;
        else{
            if((!isrev && F[i]==1) || (isrev && F[i]==2)) pre += C[i];
            else S += C[i];
        }
    }
    reverse(pre.begin(), pre.end());

    string ans = pre + S;
    if(isrev) reverse(ans.begin(), ans.end());
    cout << ans << endl; 
}

Measured memory_bytes: 4576
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+7;
int n, cnt;
int arr[MAX];
int srt[MAX];

int main() {
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>arr[i];
		srt[i]=arr[i];
	}
	sort(srt, srt+n);
	for(int i=0; i<n; i++) {
		if(arr[i]!=srt[i]) cnt++;
	}
	if(cnt>2) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}

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

using namespace std;
typedef long long ll;

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

void init(){

}

void solve(){
    int n, m;
    pair<int,int> A[N];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        scanf("%d%d", &A[i].first, &A[i].second);
    sort(A, A+n);
    int curr = 0;
    ll ans = 0;
    for(int i = 0; i < n && curr < m; i++){
        ll p = min(m-curr, A[i].second);
        ans += p*A[i].first;
        curr += p;
    }
    printf("%lld\n", ans);
}

int main(){
    int test_cases_number = 1;
//    scanf("%d", &test_cases_number);
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    cin >> test_cases_number;
    for(int i = 0; i < test_cases_number; i++)
        solve();
}



Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main() {
    string s;
    cin >> s;
    int n=s.size();
    if(s[n-1]=='s') cout << s << "es" << endl;
    else cout << s << "s" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi a(n), b(n), c(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    ll ans = 0;
    rep(i, n) {
        int mid = b[i];
        ll ai = lower_bound(a.begin(), a.end(), mid) - a.begin();
        ll ci = upper_bound(c.begin(), c.end(), mid) - c.begin();
        ci = n - ci;
        ans += ai * ci;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
n, m = gets.chomp.split(" ").map(&:to_i)
cities = []

m.times do |i|
  pref, year = gets.split(" ").map(&:to_i)
  cities << [i, pref, year]
end

sorted = cities.sort{|a, b| a[2] <=> b[2]}

h = {}
sorted.each do |s|
  num = (h[s[1]] || 0) + 1
  s << "#{s[1].to_s.rjust(6, '0')}#{num.to_s.rjust(6, '0')}"
  h[s[1]] = num
end

sorted.sort!{|a,b| a[0] <=> b[0]}
ans = sorted.map{|s| s[3]}.join("\n")

puts ans

Measured memory_bytes: 42988
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef long long ll;

int max(int a, int b){
  if(a > b) return a;
  else return b;
}
int min(int a, int b){
  if(a < b) return a;
  else return b;
}

int sort(const void *a ,const void *b){
  return *(int*)a - *(int*)b;
}

  int ans[10];
  int p[9];
  int q[9];
  int n;
  int flag[10] = {0};
  int a,b;
  int count = 0;

void dfs(int digit){

  if(digit == n){
    count ++;
    int flaga = 1,flagb = 1;
    for(int i = 0; i < n; ++i){
      if(ans[i] != p[i]) flaga = 0;
      if(ans[i] != q[i]) flagb = 0;
    }
    if(flaga == 1) a = count;
    if(flagb == 1) b = count;
    return;
  }

  for(int i = 1; i <= n; ++i){
    ans[digit] = i;
    if(flag[i] == 0){
      flag[i] = 1;
      dfs(digit+1);
      flag[i] = 0;
    }
  }

}

int main(){

  scanf("%d",&n);
  for(int i = 0; i < n; ++i){
    scanf("%d",p+i);
  }
  for(int i = 0; i < n; ++i){
    scanf("%d",q+i);
  }

  dfs(0);

  printf("%d",abs(a-b));

  return 0;
}


Measured memory_bytes: 1728
// -----------------------------------
// Author     : MatsuTaku
// Country    : Japan
// Created    : 04/12/20 20:48:37
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int cnt[3]={0,0,0};
  map<char, int> cti;
  cti['R']=0;
  cti['G']=1;
  cti['B']=2;
  int n; cin>>n;
  string s; cin>>s;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (s[i]==s[j]) continue;
      int m=3;
      m-=cti[s[i]]; m-=cti[s[j]];
      ans += cnt[m];
      int k = i-(j-i);
      if (k>=0 and cti[s[k]]==m)
        ans--;
    }
    cnt[cti[s[i]]]++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

ll powmod(ll N, ll P){
    if(P<=0) return 1;
    if(P%2==0){
        ll t = powmod(N, P/2);
        return t*t % mod;
    }
    return N*powmod(N, P-1)%mod;
}

int main() {
    string s;
    cin >> s;
    int n=s.length();
    ll dpa[n][4];
    ll dpb[n][4];
    ll dpc[n][4];
    rep(i,n){
        rep(j,4){
            dpa[i][j]=0;
            dpb[i][j]=0;
            dpc[i][j]=0;
        }
    }
    int cnt=0;
    rep(i,n){
        if(i==0){
            if(s[i]=='A')dpa[i][0]++;
            if(s[i]=='?'){
                dpa[i][1]++;
                cnt++;
            }
            continue;
        }
        rep(j,4){
            dpa[i][j]=dpa[i-1][j];
            dpb[i][j]=dpb[i-1][j];
            dpc[i][j]=dpc[i-1][j];
        }
        if(s[i]=='A')dpa[i][0]++;
        if(s[i]=='B')rep(j,2)dpb[i][j]+=dpa[i-1][j];
        if(s[i]=='C')rep(j,3)dpc[i][j]+=dpb[i-1][j];
        if(s[i]=='?'){
            rep(j,3){
                dpa[i][j+1]++;
                dpb[i][j+1]+=dpa[i-1][j];
                dpc[i][j+1]+=dpb[i-1][j];
            }
            cnt++;
        }
        rep(j,4){
            dpa[i][j]%=mod;
            dpb[i][j]%=mod;
            dpc[i][j]%=mod;
        }
    }
    ll sum=0;
    sum+=dpc[n-1][0]*powmod(3,cnt);
    sum%=mod;
    sum+=dpc[n-1][1]*powmod(3,cnt-1);
    sum%=mod;
    sum+=dpc[n-1][2]*powmod(3,cnt-2);
    sum%=mod;
  	sum+=dpc[n-1][3]*powmod(3,cnt-3);
    sum%=mod;
    cout << sum;
}

/*



 */



Measured memory_bytes: 9856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int x = 0;
int y = 0;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] >= 'A' && s[i] <= 'M') y++;
        if(s[i] >= 'N' && s[i] <= 'Z') y--;
        if(s[i] >= 'a' && s[i] <= 'm') x++;
        if(s[i] >= 'n' && s[i] <= 'z') x--;
    }
    string ans = "";
    for(int i = 0; i < y; i++) {
        ans.push_back('A');
    }
    for(int i = y; i < 0; i++) {
        ans.push_back('N');
    }
    for(int i = 0; i < x; i++) {
        ans.push_back('a');
    }
    for(int i = x; i < 0; i++) {
        ans.push_back('n');
    }
    cout << ans.size() << endl;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3336
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef pair<int,int> P;
typedef long long ll;
const int INF = 1001001001;
const ll INFL = 1e17;
const int MOD = 1e9+7;

P freq(int x){
    int a = x%10;
    int b;
    while(x){
        b = x;
        x /= 10;
    }
    return P(a,b);
}

int main(){
    int n;
    cin >> n;
    map<P,int> fr;

    for(int i=1; i<=n; i++){
        P p = freq(i);
        fr[p]++;
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        P p = freq(i);
        P q(p.second,p.first);
        ans += fr[q];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3516
import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String [] Args)
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		for(int i=n;;i++)
		{
			int flag=0;
			for(int j=2;j*j<=i;j++)
			{
				if(i%j==0)
				{
					flag=1;
					j=i;
				}
			}
			if(flag==0)
			{
				System.out.println(i);
				break;
			}
		}
	}
}
	

Measured memory_bytes: 23764
#include <cstdio>
#include <algorithm>
using namespace std;

int a;
int b;
int anna[5000];
int bruno[5000];

int main() {
    int ans;

    scanf("%d %d", &a, &b);
    for (int i=0; i<a; i++) {
        scanf("%d", &anna[i]);
    }

    for (int i=0; i<b; i++) {
        scanf("%d", &bruno[i]);
    }

    ans = 0;
    for (int i=0; i<b; i++) {
        int idx = i;
        int cost = 0;

        for (int j=0; j<a; j++) {
            if (anna[j] == bruno[idx]) {
                cost++;
                idx++;
            }
            if (idx >= b) break;
        }

        ans = max(ans, cost);
    }

    printf("%d\n", ans);
}

Measured memory_bytes: 1064
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
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*b/gcd(a, b);
}
int main()
{
  ll n, x;
  cin >> n>> x;
  vector<ll > p(n + 1,0);
  p[0] = x;
  REP(i, n){
    cin >> p[i + 1];
  }
  sort(all(p));
  if(n == 1){
    cout << p[1] - p[0] << endl;
    return 0;
  }

  vector<ll > d(n,0);
  REP(i,n){
    d[i] = p[i + 1] - p[i];
  }
  // REP(i, n){
  //   cout << d[i] << endl;
  // }
  ll tmp = d[0];
  // cout << gcd(4, 2) << endl;
  REP(i, n - 1){
    tmp = gcd(tmp,d[i + 1]);
    if(tmp == 1){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << tmp << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	int t = 1;
	int[] in;
	int[] out;
	Scanner sc = new Scanner(System.in);
	public void run() {
		while(sc.hasNext()){
			int n = sc.nextInt();
			in = new int[n];
			out = new int[n];
			calc(n);
		}
		
	}
	public void calc(int n){
		int[][] gyouretsu = new int[n][n];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				gyouretsu[i][j] = 0;
			}
		}
		for(int i = 0; i < n; i++){
			int u = sc.nextInt();
			int k = sc.nextInt();
			for(int j = 0; j < k; j++){
				int v = sc.nextInt();
				gyouretsu[u-1][v-1] = 1;
			}
		}
		
		for(int i = 0; i < n; i ++){
			in[i] = 0;
			out[i] = 0;
		}
		
			for(int i = 0; i < n; i++){
				if(in[i] == 0)  rec(gyouretsu, in, out, i);
			}
			
		for(int i = 0; i < n; i++){
			System.out.println(i+1 + " " + in[i] + " " + out[i]);
		}
	}
	public void rec(int[][] gyouretsu, int[] in, int[] out, int now){
		in[now] = t;
		t = t + 1;
		for(int i = 0; i < gyouretsu[now].length; i++){
			if(gyouretsu[now][i] == 1){
				if(in[i] == 0){
					rec(gyouretsu, in, out, i);
				}
			}
		}
		out[now] = t;
		t = t + 1;
	}
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 20796
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=309;
int h[N];
int n,K;
ll dp[N][N];
int main(){
  cin>>n>>K;
  for(int i=1;i<=n;i++)cin>>h[i];
  memset(dp,0x3f,sizeof(dp));
  dp[0][0]=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
      for(int k=0;k<i;k++){
        dp[i][j]=min(dp[i][j],dp[k][j-1]+max(0,h[i]-h[k]));
      }
  ll ans=0x3f3f3f3f3f3f3f3f;
  for(int i=0;i<=n;i++)ans=min(ans,dp[i][n-K]);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int  long long int
#define fi first
#define se second
#define pb push_back
#define soo(v) sort(v.rbegin(),v.rend())
#define so(v) sort(v.begin(),v.end())
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
//#define endl '\n'
#define dbv(v) cout<<endl;cout<<#v<<"-->> ";for(auto it:v){cout<<it<<" ";}cout<<endl;
#define dbm(m)cout<<endl;cout<<#m<<"-->> ";for(auto it:m){cout<<it.fi<<" "<<it.se<<endl;}
#define dbs(s)cout<<endl;cout<<#s<<"-->> ";for(auto it:s){cout<<it<<" ";}cout<<endl;
#define mod 1000000007
#define db1(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<endl;
#define mx 1e18
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v)  *min_element(v.begin(),v.end())
#define double long double
#define io std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

int32_t main()
{
  io
 int x;
 cin>>x;
 if(x>=30)cout<<"Yes"<<endl;
 else cout<<"No"<<endl;

}

Measured memory_bytes: 3648
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int prime_table[1000];
int prime_top;
int table[1121][15];

int init()
{
	prime_table[0] = 2;
	prime_table[1] = 3;
	prime_top = 2;

	for (int i = 4; i < 1121; i++)
	{
		for (int j = 0; j < prime_top; j++)
		{
			if (i % prime_table[j] == 0)
				goto POINT_1;
		}
		prime_table[prime_top] = i;
		prime_top++;
	POINT_1:
		continue;
	}

	table[0][0] = 1;
	for (int i = 0; i < prime_top; i++)
	{
		for (int j = 13; j >= 0; j--)
		{
			for (int k = 0; k <= 1120 - prime_table[i]; k++)
			{
				table[k + prime_table[i]][j + 1] += table[k][j];
			}
		}
	}
}

int main()
{
	init();
	for (int in1, in2, out1; (scanf("%d %d", &in1, &in2)) && in1 != 0; printf("%d\n", out1))
	{
		out1 = table[in1][in2];
	}
}



Measured memory_bytes: 2052
h, w = map(int, input().split())

l = []

for i in range(h):
  l.append(input())

  
# 端の#を作成
el = ''

for i in range(w+2):
  el += '#'
  
  
# すでにある行ごとに#を足していく作業
for i in range(h):
  l[i] = ("#"+ l[i] + "#")

  
# 端の#をlに足し合わせる
l.insert(0, el)
l.append(el)


# 行ずつに分けて表示
for i in range(len(l)):
  print(l[i])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, a[100008], c[100008], del[100008];
priority_queue<ll> dep[100008];
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	memset(c, 0, sizeof(c));
	cin >> n;
	rep(i, 2, n){
		cin >> a[i];
		c[a[i]]++;
	}
	
	priority_queue<ll> q;
	rep(i, 1, n){
		if(c[i] == 0){
			q.push(i);	
		}
		dep[i].push(0);
	}
	
	priority_queue<ll> one;
	memset(dep, 0, sizeof(dep));
	rep(i, 2, n){
		ll ind = q.top(); q.pop();
		ll win = a[ind];
		del[win]++;
		if(del[win] == c[win]){
			q.push(win);
		}
		ll buf = 0;
		while(!dep[ind].empty()){
			buf = max(-dep[ind].top(), buf+1);
			dep[ind].pop();
		}
		dep[win].push(-(buf+1));
	}
	
	ll ans = 0;
	while(!dep[1].empty()){
		ans = max(-dep[1].top(), ans+1);
		dep[1].pop();
	}
	print(ans)
	return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

string s, t;

int main()
{
	cin >> s >> t;
	map<char, char> mp1, mp2;
	int n = s.size();
	for (int i = 0; i < n; i++)
	{
		mp1[s[i]] = t[i];
		mp2[t[i]] = s[i];
	}
	bool flag = true;
	for (int i = 0; i < n; i++)
	{
		if (mp1[s[i]] != t[i] || mp2[t[i]] != s[i])
			flag = false;
	}
	cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 776
def solve(n, m, xl):
    s = sorted(xl)
    l = s[:-1]
    r = s[1:]
    diff = []
    for i in range(len(l)):
        diff.append(r[i] - l[i])
    max_list = list(reversed(sorted(diff)))
    all_length = s[-1] - s[0]
    cur = all_length
    for i in range(n-1):
        if i >= len(max_list):
            break
        cur = cur - max_list[i]

    if cur < 0:
        cur = 0
    print(cur)

def main():
    n, m = map(int, input().split())
    xl = list(map(int, input().split()))
    solve(n, m, xl)        

main()    

Measured memory_bytes: 14216
#include <iostream>
#include <cstring>

using namespace std;

int main() {
    int l;
    cin >> l;

    int tl = l;
    int dl = 0;
    bool te[20];
    int ce = 0;
    memset(te, 0, sizeof(te));
    while (l) {
        if (l & 1) {
            te[dl] = true;
            ce++;
        }
        l >>= 1;
        dl++;
    }

    cout << dl << " " << (dl-1)*2+ce-1 << endl;
    l = tl;
    int t = 1;
    for (int i = 1; i < dl; i++) {
        cout << i << " " << i+1 << " " << 0 << endl;
        cout << i << " " << i+1 << " " << t << endl;
        if (te[i-1]) {
            cout << i << " " << dl << " " << l - t << endl;
            l -= t;
        }
        t <<= 1;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n,i,j=0;
    int a[100000];
    int b[3]={1000000001,1000000001,1000000001},count[3]={0,0,0};
    int ans=1;
    
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
        
        if(b[0]==a[i])
        {
            count[0]++;
        }
        else if(b[1]==a[i])
        {
            count[1]++;
        }
        else if(b[2]==a[i])
        {
            count[2]++;
        }
        else if(j<3)
        {
            if(b[0]!=a[i]&&b[1]!=a[i])
            {
                b[j]=a[i];
                count[j]++;
                j++;
            }
        }
        else
        {
            ans=0;
            break;
        }
        
        if(j==3)
        {
            if((b[0]^b[1])!=b[2])
            {
                ans=0;
                break;
            }
            j++;
        }
        
    }
    if(j==1)
    {
        if(b[0]!=0)
        {
            ans=0;
        }
    }
    else if(j==2)
    {
        if(count[0]>=count[1])
        {
            if(count[0]!=count[1]*2||(b[0]^b[1])!=b[0])
            {
                ans=0;
            }
        }
        else
        {
            if(count[1]!=count[0]*2||(b[0]^b[1])!=b[1])
            {
                ans=0;
            }
        }
    }
    else if((b[0]^b[1])!=b[2]||count[0]!=count[1]||count[0]!=count[2])
    {
        ans=0;
    }
    
    if(ans==1)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


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

int gcd(int p, int q){
	if (p % q == 0) return q;
  	return gcd(q, p % q);
}

int main(){
	int K;
  	cin >> K;
  	int64_t sum = 0;
  	for (int a = 1;a <= K; a++){
		for (int b = 1;b <= K; b++){
        	  	for (int c = 1;c <= K; c++){
                	sum = gcd(gcd(a,b),c) + sum ;
        	}
        }
    }
  	cout << sum << endl;
}

Measured memory_bytes: 3592
#include<stdio.h>
int f(int n)
{
	int i = 0;
	while (i * i < n)
		i++;
	if (i * i == n)
		return 1;
	return 0;
}
int main()
{
	int n, d;
	scanf("%d %d", &n, &d);
	int i, j, k;
	int x[20][20];
	for (i = 0; i < n; i++)
		for (j = 0; j < d; j++)
			scanf("%d", &x[i][j]);
	int ans = 0, p;
	for (i = 0; i < n - 1; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			p = 0;
			for (k = 0; k < d; k++)
				p += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
			if (f(p) == 1)
				ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(int argc, char const *argv[]) {
  int n,x;
  cin>>n>>x;
  int tmp,distance=0,count=1;
  for(int i=0;i<n;i++){
    cin>>tmp;
    distance+=tmp;
    if(distance<=x){
      count++;
    }else{
      break;
    }
  }
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let dd: Vec<(usize, usize)> = (0..n)
        .map(|_| {
            let d1: usize = rd.get();
            let d2: usize = rd.get();
            (d1, d2)
        })
        .collect();
    let found = dd.windows(3).any(|x| {
        let (d, e, f) = (x[0], x[1], x[2]);
        d.0 == d.1 && e.0 == e.1 && f.0 == f.1
    });
    println!("{}", if found { "Yes" } else { "No" });
}

pub struct ProconReader<R: std::io::Read> {
    reader: R,
}

impl<R: std::io::Read> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self { reader }
    }
    pub fn get<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r')
            .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf)
            .unwrap()
            .parse()
            .ok()
            .expect("Parse Error.")
    }
}

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

using P = pair<int, int>;
int H, W, D;
vector<vector<int>> A;
vector<P> idx;
vector<int> cost;

int dist(P p1, P p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

int main() {
    cin >> H >> W >> D;
    idx.resize(H * W + 1);
    A.resize(H, vector<int>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
            idx[A[i][j]] = P(i, j);
        }
    }

    cost.resize(H * W + 1);
    for (int i = D + 1; i <= H * W; ++i) {
        cost[i] = cost[i - D] + dist(idx[i], idx[i - D]);
    }
    // DUMP(cost);

    int Q;  cin >> Q;
    for (int _ = 0; _ < Q; ++_) {
        int l, r;  cin >> l >> r;
        cout << cost[r] - cost[l] << endl;
    }
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
#define SIZE 200010
#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%d",&t)
#define p(t) printf("%d\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define print(x) for(auto el: x) cout<<el<<" ";cout<<endl
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<int>
#define pqsmall priority_queue<int,vector<int>,greater<int> >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define mitr map<int,int>:: iterator
 
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 

int32_t main()
{
    fast;
    int n;cin>>n;
    priority_queue<double,vector<double>,greater<double> > pq;
    for(int i=0;i<n;i++)
    {
        int x;cin>>x;
        pq.push(x);
    }
    while(pq.size()!=1)
    {
        double x=pq.top();
        pq.pop();
        double y=pq.top();
        pq.pop();
        double val=(x+y)/2.0;
        //trace3(x,y,val);
        pq.push(val);
    }
    cout<<PSET(pq.top(),6);
}

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

int main() {

 int n,m,c;
  cin >> n >> m >> c;

  vector<int> times(m);
  for(int i = 0; i < m; i++) {
    cin >> times.at(i);
  }
  
  int ans = 0;
  for(int i = 0; i < n; i++) {
    int sum = 0;
    for(int j =0; j < m; j++) {
      int temp;
      cin >> temp;
      sum += temp * times.at(j);
    }
    if(sum + c > 0) {
      ans ++;
    }
  }
 cout << ans << endl;
  
 return 0; 
}

Measured memory_bytes: 3608
#include <iostream>

int main(){
   std::string S, T, U;
   int A, B;
   std::cin >> S >> T >> A >> B >> U;

   if(S==U) std::cout << A - 1 << ' ' << B << std::endl;
   else if(T==U) std::cout << A << ' ' << B - 1 << std::endl;

   return 0;
}


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

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadInt();
        var H = sc.ReadIntArray(N);
        for (int i = N - 2; i >= 0; i--)
        {
            if (H[i] - H[i + 1] > 1)
            {
                Console.WriteLine("No");
                return;
            }
            if (H[i] - H[i + 1] == 1)
            {
                H[i]--;
            }
        }
        Console.WriteLine("Yes");
    }

    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}


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

using namespace std;

int h, w, d1 = 0, vx, vy, d2 = 0, vx2, vy2;
vector<vector<bool>> vis1(21, vector<bool>(21, true)), vis2(21, vector<bool>(21, true));
vector<vector<int>> dir = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

bool isValid(int a, int b){
    return a >= 0 && a < h && b >= 0 && b < w;
}

void dfs1(int x, int y, int &d, vector<vector<bool>> &vis){
    vis[x][y] = true;
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(x, y), 0));
    while(!q.empty()){
        auto nd = q.front();
        q.pop();
        if( nd.second > d ){
            d = nd.second;
            vx = nd.first.first;
            vy = nd.first.second;
        }
        for(int i = 0; i < dir.size(); i++){
            int tx = nd.first.first + dir[i][0], ty = nd.first.second+dir[i][1];
            if( isValid(tx, ty) && vis[tx][ty] == false ){
                vis[tx][ty] = true;
                q.push(make_pair(make_pair(tx, ty), nd.second+1));
            }
        }
    }
}

int main(){

    cin >> h >> w;
    vector<vector<char>> maze(h, vector<char>(w));

    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            cin >> maze[i][j];

    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            if( maze[i][j] == '.' )
                vis1[i][j] = vis2[i][j] = false;

    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            if( maze[i][j] == '.' ){
                dfs1(i, j, d1, vis1);
                for(int i = 0; i < h; i++)
                    for(int j = 0; j < w; j++)
                        if( maze[i][j] == '.' )
                            vis1[i][j] = vis2[i][j] = false;
            }


    cout << d1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include"math.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std; 
int main(){
int n;cin >>n;
  vector<long long> a(n+1),b(n);
 for(long long i=0;i<n+1;i++) cin>>a[i];
  for(long long i=0;i<n;i++)cin>>b[i];
    long long sum=0;
  
    for(long long i=0;i<n;i++){
    if(a[i]-b[i]<0){
      

    if(a[i+1]-(b[i]-a[i])<=0){
      sum+=a[i]+a[i+1];
       a[i+1]=0;
      
                }
      else sum+=b[i];
      a[i+1]=a[i+1]-(b[i]-a[i]);
      if(a[i+1]<0){a[i+1]=0;}
    }
      
    
    else{a[i]=a[i]-b[i];
                     sum+=b[i];
                    }}
  
  cout <<sum<<endl;}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int l = 0, r = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') {
      r++;
    } else if (r) {
      r--;
    } else {
      l++;
    }
  }
  cout << string(l, '(') << s << string(r, ')') << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

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

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

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

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

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};
vector<int>G[10010];
vector<int>c(10010,0);
int num[10010];
bool used[10010];
int now_c=0;
int dfs(int s){
    if(used[s]){
        return 0;
    }else{
        used[s]=true;
    }
    
    num[s]=c[now_c];
    now_c++;

    for(int i=0; i<G[s].size(); i++){
        dfs(G[s][i]);
    }
    return 0;
}
int main() {
    int N; cin >> N;
    int a,b;
    int sum=0;
    int maximum=0;
    rep(i,N-1){
         cin >> a >> b;
         a--, b--;
         G[a].push_back(b);
         G[b].push_back(a);
    }
    rep(i,N){
        cin >> c[i];
        sum+=c[i];
        maximum = max(maximum,c[i]);
    }
    cout << sum-maximum << endl;

    sort(c.begin(), c.end(), greater<int>());
    dfs(0);
    rep(i,N){
        cout << num[i] << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1408
// finish date: 2019/2/24

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


struct segment_tree_max {
    vector<ll> nodes;
    int sz; //木の一番下のノード数
    int N; //セグメント木の全部のノード数

    //初期化(Aに値を入れると、木をすべて構築してくれる
    segment_tree_max(int n, vector<ll> A = {}) {
        sz = 1 << (int) (ceil(log2(n)));
        N = 1;
        while (N < sz) N *= 2;
        N = N * 2 - 1;
        nodes = vector<ll>(N);
        rep(i, N) nodes[i] = -INFll;
        if (!A.empty()) {
            rep(i, sz) {
                update_tree(A[i], i);
            }
        }
    }

    //木の更新
    void update_tree(ll v, int i) {
        int idx = N / 2 + i;
        while (true) {
            if (v <= nodes[idx]) break;
            nodes[idx] = v;
            if (idx == 0) break;
            idx = (idx - 1) / 2;
        }
    }


    //範囲指定してクエリを処理する
    ll get_query(int a, int b) {
        return get_query(a, b, 0, 0, sz - 1);
    }

private:
    ll get_query(int a, int b, int idx, int l, int r) {
        if (N <= idx) {
            return -INFll;
        }
        if (a <= l && r <= b) {
            return nodes[idx];
        }
        ll valL = -INF;
        ll valR = -INF;
        if ((l + r) / 2 >= a && b >= l) {
            valL = get_query(a, b, idx * 2 + 1, l, (l + r) / 2);
        }
        if (r >= a && b >= (l + r) / 2 + 1) {
            valR = get_query(a, b, idx * 2 + 2, (l + r) / 2 + 1, r);
        }
        return max(valL, valR);
    }
};

int main() {
    int N;
    cin >> N;
    N++;
    vi h(N), a(N);
    h[0] = a[0] = 0;
    FOR(i, 1, N) cin >> h[i];
    FOR(i, 1, N) cin >> a[i];

    segment_tree_max st(N);
    st.update_tree(a[0], h[0]);
    FOR(i, 1, N) {
        st.update_tree(st.get_query(0, h[i] - 1) + a[i], h[i]);
    }
    cout << st.get_query(0, N) << endl;

    return 0;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
using namespace std;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
#define lld long double
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> vp;
typedef vector<tuple<ll, ll, ll>> vt;
//vector<vector<ll>> vv(n, vector<ll>(n));

int main()
{
	ll a, b;
	cin >> a >> b;
	if (a <= 0 && b >= 0) cout << "Zero" << endl;
	else if (a > 0 && b > 0) cout << "Positive" << endl;
	else if (b < 0) {
		if ((b - a) % 2 == 0)	cout << "Negative" << endl;
		else cout << "Positive" << endl;
	}
	else
	{
		if ((-a) % 2 == 0)	cout << "Negative" << endl;
		else cout << "Positive" << endl;
	}
}

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

int main() {
	int x, y;
    cin >> x >> y;
  
  	if (x*2>y || x*4<y) {
      cout << "No" << endl;
    } else if (y%2==1) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  
    return 0;
}

Measured memory_bytes: 3636
x = int(input())

## まず、1000以下のべき乗数のリストを作る
# print(2**9) -> 512
beki_list = []
for i in range(1, 101): # ベース
    for j in range(2, 10): # ベースにべき乗する数
        beki = i**j
        if beki <= 1000:
            beki_list.append(beki)

# 存在する1000以下のべき乗数を、大きい順に比較していく
beki_list.sort(reverse=True)

for beki in beki_list:
    if beki <= x:
        print(beki)
        exit()

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
  double i,n,k,j,t;
  double ans=0.0;
  cin >> n >> k;
  for(i=1;i<=n;i++){
    t=i;
    while(1){
      if(k<=t)break;
      t*=2;
    }
    t/=i;
    ans+=(1/n)*(1/t);
  }
  cout << setprecision(12) <<ans <<endl;
}


Measured memory_bytes: 256
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
            
    A[i+1], A[r] = A[r], A[i+1]
    return i+1
    
n = int(input())
A = [int(x) for x in input().split()]

p = partition(A, 0, n-1)

for i in range(n):
    if i:
        print(" ", end = "")
    if i == p:
        print("[", end = "")
    print(A[i], end = "")
    if i == p:
        print("]", end = "")
print()


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

int main(){
  int K;
  cin >> K;
  int A[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << A[K - 1] << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <functional>
#define SIZE 505
#define MX 250005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int A[MX],B[MX];
int X[SIZE];

int main()
{
	int n;
	scanf("%d",&n);
	memset(A,-1,sizeof(A));
	memset(B,-1,sizeof(B));
	for(int i=0;i<n;i++)
	{
		scanf("%d",&X[i]);
		X[i]--;
		A[X[i]]=B[X[i]]=i;
	}
	int sz=n*n;
	for(int i=sz-1;i>=0;i--)
	{
		if(A[i]==-1) continue;
		int v=A[i];
		int zan=n-(v+1);
		int pos=sz-1;
		while(pos>i&&zan>0)
		{
			if(B[pos]==-1)
			{
				zan--;
				B[pos]=v;
			}
			pos--;
		}
		//printf("%d %d\n",v,zan);
		if(zan>0)
		{
			puts("No");
			return 0;
		}
	}
	for(int i=0;i<sz;i++)
	{
		if(A[i]==-1) continue;
		int v=A[i];
		int zan=v;
		int pos=i-1;
		while(pos>=0&&zan>0)
		{
			if(B[pos]==-1)
			{
				zan--;
				B[pos]=v;
			}
			pos--;
		}
		if(zan>0)
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	for(int i=0;i<sz;i++)
	{
		if(i!=0) printf(" ");
		printf("%d",B[i]+1);
	}puts("");
	return 0;
}


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

int main(){
  int i,j,index,n,m,ns[1501],ew[1501],data[1000001],data2[1000001];
  while(1){
    cin >> n >> m;
    if( n == 0 && m == 0 ) break;
    for( i = 1; i <= 1000000; i++ ){
      data[i] = 0;
      data2[i] = 0;
    }
    for( i = 1; i <= n; i++ ){
      cin >> ns[i];
      data[ ns[i] ]++;
    }
    for( i = 1; i <= m; i++ ){
      cin >> ew[i];
      data2[ ew[i] ]++;
    }
    
    while( n >= 2 ){
      for( i = 1; i < n; i++ ){
	index = 0;
	for( j = i; j <= n; j++ ){
	  index += ns[j];
	}
	data[index]++;
      }
      n--;
    }
    
    
    while( m >= 2 ){
      for( i = 1; i < m; i++ ){
	index = 0;
	for( j = i; j <= m; j++ ){
	  index += ew[j];
	}
	data2[index]++;
      }
      m--;
    }
    
    int cnt = 0;
    for( i = 1; i <= 1000000; i++ ){
      cnt += data[i] * data2[i];
    }
         
    cout << cnt << endl;
    
  }
  
  return 0;
}

Measured memory_bytes: 8984
#include <stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[N][N];
int color[N], d[N], f[N], tt;
/*
 * n : the number of input
 * M[][] : store the Graph
 * color[] : 
 *  * WHITE this vertex has not been visited
 *  * GRAY this vertex is being visited
 *  * BLACK this vertex has been visited
 * d[] : the beginning time of this vertex visited
 * f[] : the finised time of this vertex visited
 * tt : time 
 */

void dfs_visit(int u)
{
    int v;
    color[u] = GRAY;
    d[u] = ++tt;
    for (v = 0; v < n; v++) {
        if (M[u][v] == 0) continue;
        if (color[v] == WHITE) {
            dfs_visit(v);
        }
    }
    color[u] = BLACK;
    f[u] = ++tt;
}

void dfs()
{
    int u;
    for (u = 0; u < n; u++) {
        color[u] = WHITE;
    }
    tt = 0;
    
    for (u = 0; u < n; u++) {
        if (color[u] == WHITE)
            dfs_visit(u);
    }

    for (u = 0; u < n; u++) {
        printf("%d %d %d\n", u + 1, d[u], f[u]);
    }

}

int main(int argc, char const *argv[])
{
    int u, v, k, i, j;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            M[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        scanf("%d %d", &u, &k);
        u--;
        for (j = 0; j < k; j++) {
            scanf("%d", &v);
            v--;
            M[u][v] = 1;
        }
    }

    dfs();

    return 0;
}



Measured memory_bytes: 2048
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(max(a,c)-min(a,c)<=d or max(a,b)-min(a,b)<=d and max(b,c)-min(b,c)<=d)cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int a, b;
    cin >> a >> b;
    cout << max(a+b, max(a-b, a*b)) << endl;
    return 0;
}

Measured memory_bytes: 3624
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def find(self, a, b, k=0, l=0, r=0):
        if r <= a or b <= l:
            return float('inf')

        if a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.find(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for _, each in enumerate(cmd_list):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            res = case.find(a=ele_1, b=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Measured memory_bytes: 19576
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define pi 3.14159265
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int> 
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
void shikhar7s(int cas)
{
    int n,i,d;
    cin>>n>>d;
    d*=d;
    int x,y,ans=0;
    fr(i,n)
    {
        cin>>x>>y;
        if((x*x)+(y*y)<=d)
            ans++;
    }
    cout<<ans;
}
signed main()
{
    fast;
    int t=1;
    //cin>>t;
    int cas=1;
    while(cas<=t)
    {
    shikhar7s(cas);
    cas++;
    }
    return 0;
}

Measured memory_bytes: 3648