akhauriyash/Code-Regression huggingface dataset:
//============================================================================
// Name        : ITP_1_2_D.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int W,H,x,y,r;
	cin >> W >> H >> x >> y >> r;
	if (x>= r && x <= W-r && y >= r && y <= H-r) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3088
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
#ifdef TEST
  freopen("input.txt", "r", stdin);
#endif
  int N;
  long long K;
  cin >> N >> K;
  vector<long long> A;
  for (int i = 0; i < N; i++) {
    long long a;
    cin >> a;
    A.push_back(a);
  }

  // 2^40 > 10^12
  const int MAX_DIGIT = 50;

  // 上からi桁目
  // j=0 => k未満であることが確定 (smaller)
  // j=1 => 今のところKと一致 (exact)
  long long dp[MAX_DIGIT + 1][2];
  memset(dp, -1, sizeof(dp));

  // 上から0桁目がKと一致するのを0に初期化
  dp[0][1] = 0;
  for (int i = 0; i < MAX_DIGIT; i++) {
    long long mask = 1LL << (MAX_DIGIT - i - 1);

    // cout << "start: " << i << endl;

    // i桁目が1の数
    int num = 0;
    for (int j = 0; j < N; j++) {
      if ( (A[j] & mask) != 0) {
        num++;
      }
    }

    // 上からi桁目を0にしたとき
    long long cost0 = num * mask;
    // 上からi桁目を1にしたとき
    long long cost1 = (N - num) * mask;

    // smaller -> smaller
    if (dp[i][0] != -1) {
      chmax(dp[i + 1][0], dp[i][0] + max(cost0, cost1));
    }
    // smaller -> exact (上の桁から決めているのでこの遷移はない)

    // exact -> smaller
    if (dp[i][1] != -1) {
      if ((K & mask) != 0) {
        chmax(dp[i + 1][0], dp[i][1] + cost0);
      }
    }

    // exact -> exact
    if (dp[i][1] != -1) {
      if ((K & mask) != 0) {
        chmax(dp[i + 1][1], dp[i][1] + cost1);
      } else {
        chmax(dp[i + 1][1], dp[i][1] + cost0);
      }
    }
  }

  // for (int i = 0; i < MAX_DIGIT + 1; i++) {
  //   for (int j = 0; j < 2; j++) {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]);
}

Measured memory_bytes: 1400
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=100005;
struct edge
{
	int x,y,c;
	int p,q;LL t1,t2;
}E[MAXN],lk[MAXN];int cnt;

int rt[MAXN],tot[MAXN],n,m,cal[MAXN];LL sum[MAXN];
int findrt(int x){return rt[x]==x?rt[x]:findrt(rt[x]);}
bool cmp(edge n1,edge n2){return n1.c<n2.c;}

int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)cal[i]=read();
	for(int i=1;i<=m;i++)E[i].x=read(),E[i].y=read(),E[i].c=read();
	sort(E+1,E+1+m,cmp);
	for(int i=1;i<=n;i++)sum[i]=cal[i],tot[i]=1,rt[i]=i;
	for(int i=1;i<=m;i++)
	{
		int p=findrt(E[i].x),q=findrt(E[i].y);
		if(p!=q)
		{
			if(tot[p]>tot[q])swap(p,q);
			rt[p]=q;
			
			lk[++cnt]=E[i];
			lk[cnt].p=p;lk[cnt].q=q;lk[cnt].t1=sum[p];lk[cnt].t2=sum[q];
			
			sum[q]+=sum[p];tot[q]+=tot[p];
		}
	}
	for(int i=cnt;i>=1;i--)
	{
		LL s=sum[findrt(lk[i].x)];
		if(s<lk[i].c)
		{
			rt[lk[i].p]=lk[i].p;rt[lk[i].q]=lk[i].q;
			sum[lk[i].p]=lk[i].t1;sum[lk[i].q]=lk[i].t2;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int p=findrt(E[i].x),q=findrt(E[i].y);
		if(p==q)
		{
			if(sum[p]>=E[i].c)ans++;
		}
	}
	pr2(m-ans);
	return 0;
}



Measured memory_bytes: 9984
#include<iostream>
using namespace std;
long long gcd(long long a,long long b){
if(b==0) return a;
else return gcd(b,a%b);
}

int main(){
int n;
  cin>>n;
  long long X;
  cin>>X;
  long long res=0;
  for(int i=0;i<n;i++){
    long long x;
    cin>>x;
    res=gcd(res,abs(x-X));
  }
  cout<<res<<endl;
  return 0;
}


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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


void Main() {
  ll n, a, b;
  cin >> n >> a >> b;
  COUT(min(b, a * n));
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*

3 2
*/


Measured memory_bytes: 3604
#include <stdio.h>



void swap(int* a, int* b){
    int c;
    c = *a;
    *a = *b;
    *b = c;
}

void arprint(int *a, int n){
    for( int i = 0; i < n-1; i++ ){
        printf ("%d ", *(a+i));
    }
    printf ("%d\n", *(a+n-1));
}

int main(){

    int data[100];
    int m;
    scanf("%d", &m);

    for (int i = 0; i < m; i++){
        scanf("%d", data+i);
    }

    int pre;
    for (int i = 1; i < m; i++){
        arprint(data, m);
        int j = i;
        while( j > 0 ){
            if( data[j-1] > data[j] ){
                swap(data+j-1, data+j);
                j--;
            }else{
                break;
            }
        }
    }

    arprint(data, m);

    return 0;

}


Measured memory_bytes: 2588
n = int(input())
d = [[0,0]]*n
flag = "No"
for i in range(n):
  d[i]=list(map(int,input().split()))
for i in range(2,n):
  if d[i-1][0]==d[i-1][1] and d[i-2][0]==d[i-2][1] and d[i][0]==d[i][1]:
    flag = "Yes"
print(flag)


Measured memory_bytes: 62344
//2020.1.18
//s1270188 xxxmk2
//alds1_10a

#include<stdio.h>
#define N 44

//prototype
int fib(int);

//global
int F[N];

int main(){
  int a;

  //reset
  for(a=0;a<N;a++) F[a]=0;
  
  //input
  scanf("%d",&a);

  //output
  printf("%d\n",fib(a));
  
  return 0;
}

int fib(int n){
  if(n==0 || n==1) return F[n]=1;
  if(F[n]) return F[n];
  else return F[n]=fib(n-1)+fib(n-2);
}



Measured memory_bytes: 2112
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <list>

using namespace std;
using ll = long long;

int main()
{
    int N, W;
    scanf("%d%d", &N, &W);

    vector<int> w(N), v(N);

    for(int i = 0; i < N; ++i)
        scanf("%d%d", &w[i], &v[i]);

    vector<ll> dp(W + 1, 0);

    /* Approach 1
    for(int item = 0; item <  N; ++item)
    {
        vector<ll> new_dp(W + 1, 0);
        for(int weight = 1; weight <= W; ++weight)
        {
            // check if value fits in the bag
            if(weight - w[item] >= 0)
                new_dp[weight] = max(dp[weight], dp[weight - w[item]] + v[item]);
            else
                new_dp[weight] = dp[weight];

            //cout << "adding item  " << item  << "  to bag " << weight << " : " << new_dp[weight] << "\n";
        }
        dp = new_dp;
    }*/

    for(int item = 0; item <  N; ++item)
    {
        // This reverse loop is used so that we do not count the item twice in same knapsack
        // when we start from high weight all lower weight value will still be from adding previous items
        // If we start with small to higher weight previous weights would have considered the current item in hand and hence we will double count
        for(int weight =  W; weight >= 0 ; --weight)
        {
            if(weight - w[item] >= 0)
                dp[weight] = max(dp[weight], dp[weight - w[item]] + v[item]);
        }
    }

    cout << dp[W] << "\n";

    return 0;
}


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

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

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}


ll expo( ll base, ll exp, ll m = MOD )
{
    ll res = 1;
    while( exp )
    {
        if( exp&1 )
            res = mod( res*base, m );
        base = mod( base*base, m );
        exp >>= 1;
    }
    return res;
}

int main() 
{
    #ifdef gupta_samarth
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fastio();

    int n;
    cin>>n;

    if( n == 1 )
    {
        cout<<0,nl;
        return 0;
    }

    ll ans = 0;
    for(int i=0;i<n-1;i++)
    {
        ll ways = expo(8,i);

        ll total = expo(10,n-1-i);
        sub( total, expo(9,n-1-i) );

        ways = mod( ways * total );
        add( ans, ways );
    }
    ans = mod( 2 * ans );
    cout<<ans,nl;

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    if(s.size()==2){
        cout << s << endl;
    }
    else if(s.size()==3){
        for(int i=2;i>=0;--i){
            cout << s[i];
        }
        cout << "\n";
    }
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <string>
#include <cctype>
#include <cstdio>
#include <math.h>
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
const int AMAX = 100000; 
using namespace std;
#define rep(i, n) for (i64 i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (i64 i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define fst first
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sw swap
#define UP(x) transform(x.begin(), x.end(), x.begin(), ::toupper);
#define down(x) transform(x.begin(), x.end(), x.begin(), ::tolower);
using LL = long long;
using ULL = unsigned 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 (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main(void) {
    string a;
    cin >> a;
    LL ans=0;
    rep(i, a.size())
   {
    if (a[i]=='p')
    {
     ans++;
    }
   }
    cout << a.size()/2-ans;
    return 0;
}

Measured memory_bytes: 512
H,N = map(int,input().split())
inf = 1000000000
dp = [inf for _ in range(20001)]
magics = []
dp[0] = 0
for i in range(N):
    magic = list(map(int,input().split()))
    magics.append(magic)
for j in range(10001):
    for k in magics:
        dp[j+k[0]] = min(dp[j]+k[1],dp[j+k[0]])
ans = dp[H:]
print(min(ans))

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

int main() {
    int n;
    cin >> n;
    n %= 1000;
    if(n!= 0) n = 1000 - n;
    cout << n << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 100000005
#define MAX 5001
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

pair<ll, int> p[100002];
ll x[1002], d[100002];
int main(){
	ll n, T, Q, t1, t2;
	scanf("%lld%lld%lld", &n, &T, &Q);
	for(int i = 0;i < n;i++){
		scanf("%lld%d", &p[i].fi, &p[i].se);
	}
	for(int i = 0;i < Q;i++)scanf("%lld", &x[i]);
	
	ll f[2] = {0, 0}, tt;
	for(int i = 0;i < n;i++){
		if(p[i].se == 1 && f[0] == 0)f[0] = 1;
		if(p[i].se == 2 && f[0] == 1){
			f[1] = (p[i-1].fi+p[i].fi)/2;
			tt = i-1;
			while(tt != -1 && p[tt].se == 1){
				d[tt] = f[1];
				tt--;
			}
			tt = i;
			while(tt < n && p[tt].se == 2){
				d[tt] = f[1];
				tt++;
			}
			i = tt;
		}
		if(i == n-1){
			tt = i;
			while(tt != -1 && p[tt].se == 1){
				d[tt] = p[i].fi+T;
				tt--;
			}
		}
		if(p[i].se == 2 && f[0] == 0)d[i] = p[i].fi-T;
	}
	
	//for(int i = 0;i < n;i++)printf("%d ", d[i]);
	ll tmp = 0;
	for(int i = 0;i < Q;i++){
		tmp = x[i]-1;
		if(p[tmp].fi < d[tmp])d[tmp] = min(p[tmp].fi+T, d[tmp]);
		if(p[tmp].fi > d[tmp])d[tmp] = max(p[tmp].fi-T, d[tmp]);
		printf("%lld\n", d[tmp]);
	}
	return 0;
}

Measured memory_bytes: 5576
def main():
    w=[input() for _ in range(int(input()))]
    sumi=set()
    p=w[0][0]
    for s in w:
        if s in sumi or p != s[0]:
            print("No")
            return
        sumi.add(s)
        p = s[-1]
    print("Yes")
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 9172
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try{
			String str = br.readLine();

				String[] st = str.split(" ",0);
				int a =  Integer.parseInt(st[0]);
				int b = Integer.parseInt(st[1]);
				int c = Integer.parseInt(st[2]);
			if(c>=a && c<=b){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}catch(Exception ex){
			System.exit(0);
		}
	}
}

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

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define all(x) begin(x),end(x)

#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP (i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector <vector<int>>;
using vvll = vector <vector<ll>>;

#define inf(T) (numeric_limits<T>::max() / 2)
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (;;) {
        int n, m, p, a, b;
        cin >> n >> m >> p >> a >> b;
        --a, --b;
        if (n == 0) break;
        vector<double> t(n);
        REP(i, n) cin >> t[i];
        struct edge {
            int to, cost;
        };
        vector<vector<edge>> G(m);
        REP(i, p) {
            int u, v, c;
            cin >> u >> v >> c;
            --u, --v;
            G[u].push_back((edge){ v, c });
            G[v].push_back((edge){ u, c });
        }

        const double INF = inf(double);
        vector<vector<double>> dp(1<<n, vector<double>(m, INF));
        dp[0][a] = 0;
        REP(s, 1<<n) {
            REP(i, m) {
                if (dp[s][i] == INF) continue;
                for (edge e : G[i]) {
                    REP(j, n) {
                        if (s >> j & 1) continue;
                        chmin(dp[s | 1<<j][e.to], dp[s][i] + e.cost / t[j]);
                    }
                }
            }
        }

        double ans = INF;
        REP(s, 1<<n) chmin(ans, dp[s][b]);

        if (ans == INF) cout << "Impossible" << endl;
        else cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 3384
int main(){
  int n,i;
  int h[100001];
  int max = -1;
  int flag = 0;
 
  scanf("%d", &n);
 
  for(i = 0;i < n;i++){
    scanf("%d", &h[i]);
    if(max < h[i]) max = h[i];
 
    if(max - h[i] >= 2) flag = 1;
  }
 
  if(flag == 1) printf("No\n");
 
  else printf("Yes\n");
 
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using pll=pair<ll,ll>;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

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

int main() {
	int N,K;
	cin >> N >> K;
	double ans = 0;
	rep(i,N) {
		int n = i+1;
		double p = 1;
		while(n < K) {
			n *= 2;
			p *= 0.5;
		}
		ans += p / N;
	}
	cout << setprecision(10) << ans << endl;

  return 0;
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
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<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end

#define pd pair<double,double>

int main(){
    int n,k; scanf("%d%d",&n,&k);
    vector<P> p(n);
    rep(i,0,n)scanf("%lld%lld",&p[i].first,&p[i].second);
    vector<pd> a; int cnt[10010]={};
    rep(i,0,n)rep(j,i+1,n){
        int xa=p[i].first,xb=p[j].first;
        int ya=p[i].second,yb=p[j].second;
        if(xa==xb){
            cnt[xa]++; continue;
        }
        double x=(ya-yb)*1.0/(xa-xb),y=(xa*yb-xb*ya)*1.0/(xa-xb);
        a.push_back({x,y});
    }
    sort(ALL(a));
    int maxx=0,pre=1;
    rep(i,0,a.size()-1){
        if(a[i]==a[i+1]){
            pre++; chmax(maxx,pre);
        }
        else pre=1;
    }
    chmax(maxx,pre);
    rep(i,0,10010)chmax(maxx,cnt[i]);
    printf(maxx>=k*(k-1)/2?"1\n":"0\n");
    return 0;
}


Measured memory_bytes: 134160
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n - 1):
    if p[i] == i + 1:
        (p[i], p[i + 1]) = (p[i + 1], p[i])
        ans += 1
if p[-1] == n:
    ans += 1
print(ans)

Measured memory_bytes: 54316
#include <bits/stdc++.h>
#define cinf(n,x,y,z) for(int i=0;i<(n);i++) cin >> x[i]>>y[i]>>z[i];
typedef long long int ll;
using namespace std;

int main(){
	int n; string s;
	cin >>n >>s;
	int ans=0;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(s[i]=='I')cnt++;
		if(s[i]=='D')cnt--;
		ans=max(ans,cnt);
	}
	cout << ans << endl;
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
using namespace std;

int main(int argc, char const *argv[])
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--) {
        int n,k;
        cin>>n>>k;
        ll arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        sort(arr,arr+n);
        ll dp[k+1];
        dp[0]=1;
        for(int i=1;i<arr[0];i++){
            dp[i]=1;
        }
        dp[arr[0]]=0;
        for(int i=arr[0]+1;i<=k;i++){
            vector<int> res;
            for(int j=0;j<n;j++){
                if(arr[j]>i){
                    break;
                }
                else {
                    res.push_back(dp[i-arr[j]]);
                }
            }
            if(find(res.begin(),res.end(),1)!=res.end()){
                dp[i]=0;
            }
            else dp[i]=1;
        }
        if(dp[k]==0){
            cout<<"First"<<endl;
        }
        else cout<<"Second"<<endl;

    }
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main() {int RB[15],t,p,f,l,i;while (scanf("%d",&t)!=EOF) {for (i=0;i<15;RB[i++]=0);RB[t]++;for (i=1;i<5;i++) scanf(",%d",&t),RB[t]++;t=p=f=l=0;for (i=0;i<15;i++) if (RB[i]==4) f++; else if (RB[i]==3) t++; else if (RB[i]==2) p++;RB[14]=RB[1];for (i=1;i<11;i++) if (RB[i]*RB[i+1]*RB[i+2]*RB[i+3]*RB[i+4]) l=1;if (l) puts("straight"); else if (f) puts("four card"); else if (t && p) puts("full house"); else if (t) puts("three card"); else if (p==2) puts("two pair"); else if (p) puts("one pair"); else puts("null");}return 0;}

Measured memory_bytes: 0
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		int x=s.nextInt();
		int y=s.nextInt();
		int z=1;
		while(z!=0){
			z=x%y;
			x=y;
			y=z;
		}
		System.out.println(x);
	}
}


Measured memory_bytes: 26248
#pragma GCC optimize("Ofast")

//インクルード
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

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

int main() {
  // 高速化
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);


    ll K;
    cin >> K;

    cout << K * 2 *  M_PI  << "\n"; 

    return 0;



}


Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
  vector<ll> vec(N);
  for(ll i=0;i<N;i++) {
cin>>vec[i];
  }
  
  sort(all(vec));
  reverse(all(vec));
  ll ans=0;
  
  
  ans+=vec[0];
  ll i=1;
  ll count=1;
  while(count<N-1) {
ans+=vec[i]*2;
    count+=2;
    i++;
  }
  
  if(count>N-1) {
ans-=vec[i-1];
  }
  
  cout<<ans<<endl;
}
  
  
  
  
  
  
  


Measured memory_bytes: 4776
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;
 
// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;

int main ()
{
  prep();
  long long n, x;
  cin >> n >> x;
  int arr[n];
  long long tot = 0;
  for (int i=0; i<n; i++){
      cin >> arr[i];
      tot += arr[i];
  }
  int minels[n];
  for (int i=0; i<n; i++){
      minels[i] = 2000000000;
  }
  long long minnest = 1000000000000000000LL;
  for (int i=0; i<=n; i++){
      // search rotations
      long long cost = i*x+tot;
      for (int j=0; j<n; j++){
          minels[j] = min(minels[j], arr[(j-i+n)%n]);
          cost += min(0, minels[j]-arr[j]);
      }
      minnest = min(minnest, cost);
  }
  cout << minnest;
  return 0; 
}


Measured memory_bytes: 256
S = input()
N = len(S)
db = [[0]*N for _ in range(400)]
db[0] =  [i+1 if S[i]=='R' else i-1 for i in range(N)]
for i in range(1,400):
  for j in range(N):
    db[i][j] = db[i-1][db[i-1][j]]
ans = [0]*N
for i in range(N):
  K = 10**5
  p = 0
  pos = i
  while K:
    if K%2:
      pos = db[p][pos]
    p += 1
    K >>= 1
  ans[pos] += 1
print(*ans)

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

class Main{
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long input = Long.parseLong(scanner.next());
    scanner.close();

    long ans = input;
    int input_length = (int)Math.log10(input);

    if(input_length == 0){
      System.out.println(input);
    }else{
      for(int i=1; i<(int)Math.pow(2, input_length); i++){
        ans += cal(addHere(i, input_length), input);
      }
      System.out.println(ans);
    }
  }

  private static boolean[] addHere(int count, int length){
    boolean[] bools = new boolean[length];
    for(int i=0; i<length; i++){
      if(count%2 == 1){
        bools[i] = true;
      }
      count /= 2;
    }
    return bools;
  }

  private static long cal(boolean[] bools, long in){
    int jackPot = 1;
    long ans = 0;
    for(int i=0; i<bools.length; i++){
      if(bools[i]){
        ans += in % (long)Math.pow(10, jackPot);
        in /= (long)Math.pow(10, jackPot);
        jackPot = 1;
      }else{
        jackPot ++;
      }
    }
    ans += in;
    return ans;
  }
}


Measured memory_bytes: 23764
#include<stdio.h>

int main(void){
	int a,b;
	char op;
	op= '+';
	while(op!='?'){
	scanf("%d %c %d",&a,&op,&b);
	 if(op=='?'){
		break;
	}
	else if(op=='+'){
		printf("%d\n",a+b);
	}else if(op=='-'){
		printf("%d\n",a-b);
	}else if(op=='*'){
		printf("%d\n",a*b);
	}else if(op=='/'){
		printf("%d\n",a/b);
	}
	}
	
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int d[100000];

signed main() {
	int i;

	cin >> n;
	rep(i, n) cin >> d[i];
	sort(d, d + n);
	
	cout << d[n / 2] - d[n / 2 - 1] << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int x = sc.nextInt();
			if ((n | a | b | c | x) == 0)
				break;
			int s[] = new int[n];
			for (int i = 0; i < n; i++) {
				s[i] = sc.nextInt();
			}
			int f = 0;
			int i = 0;
			while (true) {
				if (f > 10000) {
					f = -1;
					break;
				}
				if (x == s[i]) {
					i++;
				}
				if (i == n)
					break;
				x = (a * x + b) % c;
				f++;
			}
			System.out.println(f);
			// x' = (A × x + B) mod C
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;


int main(){
	while (1) {
		int x, y;
		cin >> x >> y;
		if (x == 0 && y == 0) {
			break;
		}
		if (x > y) swap(x, y);
		cout << x << " " << y << endl;
	}
}


Measured memory_bytes: 3068
#include<iostream>

using namespace std;

bool cant[20][20];
int a,b,ans;

void dfs(int x,int y)
{
	if(cant[x][y])return;
	
	if(x == a-1 && y == b-1)
	{
		ans++;
		return;
	}
	
	if(x < a-1)
	{
		dfs(x+1,y);
	}
	if(y < b-1)
	{
		dfs(x,y+1);
	}

}

int main()
{
	
	while(cin >> a >> b,a)
	{
		for(int i = 0;i < 20;i++)for(int j = 0;j < 20;j++)
		{
			cant[i][j] = false;
		}
		
		ans = 0;
		int n;
		cin >> n;
		
		for(int i = 0;i < n;i++)
		{
			int x,y;
			cin >> x >> y;
			cant[x-1][y-1] = true;
		}
		
		dfs(0,0);
		
		cout << ans << endl;
	}
		
	
	
	return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAX 200000
#define NIL -1
using namespace std;
struct Node{
  int parent;
  int right;
  int left;
};

struct Node T[MAX];
//write the depth of each node
int D[MAX];

void print(int u){
  int i,c;
  cout << "node " << u << ": ";
  cout << "parent = " << T[u].parent << ", ";
  cout << "depth = " << D[u] << ", ";        

  if(T[u].parent==NIL) cout << "root, ";   
  else if(T[u].left==NIL) cout << "leaf, ";
  else cout << "internal node, ";

  cout << "[";
  for(i=0,c=T[u].left;c!=NIL;i++,c=T[c].right){
    if(i) cout << ", ";
    cout << c;
  }
  cout << "]" << endl;
}
//setting the depth of node
int rec(int u, int p){
  D[u]=p;
  if(T[u].right!=NIL) rec(T[u].right,p);
  if(T[u].left!=NIL)  rec(T[u].left,p+1);
}

int main(){
  int n,r,deg,c,id,pre=0;
  cin >> n;
  for(int i=0;i<n;i++)
    T[i].parent=T[i].right=T[i].left=NIL;

  for(int i=0;i<n;i++){
    cin >> id >> deg;
    for(int j=0;j<deg;j++){
      cin >> c;
      if(j==0) T[id].left=c;
      else T[pre].right=c;
      pre=c;
      T[c].parent=id;
    }
  }
  for(int i=0;i<n;i++)
    if(T[i].parent==NIL) r=i;
  rec(r,0);

  for(int i=0;i<n;i++) print(i);

  return 0;
}


Measured memory_bytes: 7676
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000



int main(){
	
	int sx,sy,tx,ty;
	cin>>sx>>sy>>tx>>ty;
	
	for(int i=0;i<tx-sx;i++)cout<<'R';
	for(int i=0;i<ty-sy;i++)cout<<'U';
	for(int i=0;i<tx-sx;i++)cout<<'L';
	for(int i=0;i<ty-sy;i++)cout<<'D';
	
	cout<<'D';
	for(int i=0;i<tx-sx+1;i++)cout<<'R';
	for(int i=0;i<ty-sy+1;i++)cout<<'U';
	cout<<'L';
	
	cout<<'U';
	for(int i=0;i<tx-sx+1;i++)cout<<'L';
	for(int i=0;i<ty-sy+1;i++)cout<<'D';
	cout<<'R';
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,l,r;char s[100010];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int l,r,len=0;
    if (n&1) l=r=(n+1)>>1;else l=n>>1,r=l+1;
    while (len<l&&s[l-len]==s[l]&&s[r+len]==s[l]) len++;
    printf("%d\n",(n+(r+len-1)-(l-len+1)+1)/2);
    return 0;
}


Measured memory_bytes: 384
// Created by ...Lusifer
#include<bits/stdc++.h>
using namespace std;
 
#define pb 		push_back
#define mp 		make_pair
#define prior   priority_queue
#define MOD 	1000000007
#define INF64 	(long long)1e18
#define INF 	(int)1e9
#define PI 		3.1415926535897932384626433832795 
#define ll      long long
#define ld		long double
#define ret     return
#define NUM 	1000001
const int SIZE = 2e5+4;
void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void solveTest(){
	string s;
	cin>>s;
	int x = 753;
	int diff = INT_MAX;
	for(int i=0;i<s.size()-2;i++){
		string a=s.substr(i,3);
		diff = min(diff,abs(x-stoi(a)));
	}
	cout<<diff<<endl;
	return ;
}
 
int main(){
	fastio();

	int t=1;
	//cin>>t;
	while(t--){
		solveTest();
 
	}
	return 0;
}

Measured memory_bytes: 256
MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]
  
  if len(cdic[c])<5:
    for j in reversed(cdic[c]):
      if j<i:
        dp[i]+=dp[j]
        break
  else:
    l,r=0,len(cdic[c])
    while(l<=r):
      mid=(l+r)//2
      if cdic[c][mid]<i and cdic[c][mid+1]>=i:
        dp[i]+=dp[cdic[c][mid]]
        break
      elif cdic[c][mid]>=i:
        r=mid-1
      elif cdic[c][mid+1]<i:
        l=mid+1
      else:
        print("error")
    
#print(dp)
print(dp[-1]%MOD)

Measured memory_bytes: 761912
# -*- coding: utf-8 -*-

def main():
    n, k = map(int, input().split())
    ans = 1

    # n を k 進表示
    while(n >= k):
        # print(n)
        n = int(n / k)
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
s=input()
r=[0]
ans=[0]*len(s)
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        r.append(i+1)
r.append(len(s))

for i in range(len(r)-1):
    if i%2==1:
        ans[r[i]]=(r[i]-r[i-1])//2+(r[i+1]-r[i]+1)//2
        ans[r[i]-1]=(r[i+1]-r[i])//2+(r[i]-r[i-1]+1)//2
print(*ans)


Measured memory_bytes: 47932
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, string> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int main(){
    int q, t, f, cnt = 0, now = 0;
    string s, c, front, back; cin >> s; sc(q);
    vector<int> qr(q);
    vector<P> fc; 
    rep(i, 0, q){
        sc(qr[i]);
        if (qr[i]==2) sc(f), cin >> c, fc.push_back(P(f, c));
        else cnt++;
    }

    bool check = false;
    if (cnt%2) check = true;
    if (check) reverse(s.begin(), s.end());
    rep(i, 0, q){
        if (qr[i]==1) {
            if (check) check = false;
            else check = true;
        }else{
            P x = fc[now++];
            if (check){
                if (x.first==1) back = back + x.second;
                else front = x.second + front;
            }else{
                if (x.first==1) front = x.second + front;
                else back = back + x.second;
            }
        }
    }
    cout << front + s + back << endl;
    return 0;
}

Measured memory_bytes: 16240
from collections import deque
import sys
sys.setrecursionlimit(4000)

def validCordinate(x, y, dist, Grid):
    if x < 0 or x >= len(Grid[0]):
        return False
    if y < 0 or y >= len(Grid):
        return False

    if dist[y][x] != -1:
        return False

    if Grid[y][x] != '.':
        return False

    return True

def bfs(x, y, q, dist, Grid):
    # 隣接点を検証
    if validCordinate(x + 1, y, dist, Grid):
        q.append((x+1, y))
        dist[y][x+1] = dist[y][x] + 1
    if validCordinate(x, y + 1, dist, Grid):
        q.append((x, y + 1))
        dist[y+1][x] = dist[y][x] + 1
    if validCordinate(x - 1, y, dist, Grid):
        q.append((x-1, y))
        dist[y][x-1] = dist[y][x] + 1
    if validCordinate(x, y - 1, dist, Grid):
        q.append((x, y-1))
        dist[y-1][x] = dist[y][x] + 1


    # finish
    if x == len(Grid[0]) - 1 and y == len(Grid) - 1:
        return dist
    if len(q) == 0:
        return False

    cx, cy = q.popleft()

    return bfs(cx, cy, q, dist, Grid)
    

def main():
    # input
    H, W = map(int, input().split())
    Grid = []
    dist = [[-1 for j in range(W)] for i in range(H)]
    q = deque()

    for i in range(H):
       Grid.append(input()) 


    dist[0][0] = 0
    res = bfs(0, 0, q, dist, Grid)

    if res:
        whiteNumber = 0
        for i in range(H):
            for j in range(W):
                if Grid[i][j] == ".":
                    whiteNumber += 1
        print(whiteNumber - res[-1][-1] - 1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 5484
#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>
#include <bitset>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define debug(x) #x << " = " << (x) << " "
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr int mod = 1e9+7;
constexpr int MAX_M = 300;
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> l(m), r(m), x(m); repeat (i,m) { scanf("%d%d%d", &l[i], &r[i], &x[i]); -- l[i]; } // [l, r)
    assert (m <= MAX_M);
    // dp
    unordered_map<bitset<3*MAX_M>, int> cur;
    unordered_map<bitset<3*MAX_M>, int> prv;
    cur[bitset<3*MAX_M>()] += 1;
    vector<int> queries;
    repeat (i,n) {
        cur.swap(prv);
        cur.clear();
        repeat (j,m) if (l[j] == i) {
            queries.push_back(j);
        }
        whole(sort, queries);
        repeat (c,3) { // RGB
            for (auto && it : prv) {
                bitset<3*MAX_M> s; int cnt; tie(s, cnt) = it;
                for (int j : queries) {
                    s[3*j+c] = true;
                    if (s[3*j+0] + s[3*j+1] + s[3*j+2] > x[j]) {
                        cnt = 0;
                        break;
                    }
                }
                if (cnt) {
                    cur[s] += cnt;
                    cur[s] %= mod;
                }
            }
        }
        cur.swap(prv);
        cur.clear();
        for (auto && it : prv) {
            bitset<3*MAX_M> s; int cnt; tie(s, cnt) = it;
            for (int j : queries) if (r[j]-1 == i) {
                if (s[3*j+0] + s[3*j+1] + s[3*j+2] != x[j]) {
                    cnt = 0;
                    break;
                }
                s[3*j+0] = false;
                s[3*j+1] = false;
                s[3*j+2] = false;
            }
            if (cnt) {
                cur[s] += cnt;
                cur[s] %= mod;
            }
        }
        repeat (j,m) if (r[j]-1 == i) {
            queries.erase(whole(remove, queries, j), queries.end());
        }
    }
    assert (queries.size() == 0);
    ll result = 0;
    for (auto && it : cur) {
        result += it.second;
    }
    result %= mod;
    // output
    printf("%lld\n", result);
    return 0;
}


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

int main(){
	string a,b;
	cin >> a >> b;
	int al = (int) a.size(), bl = (int) b.size();
	if (al > bl) {cout << "GREATER"; return 0;}
	else if (bl > al) {cout << "LESS"; return 0;}
	else {
		for (int i=0; i<al; i++){
			if (a[i] > b[i]) {cout << "GREATER"; return 0;}
			else if (b[i] > a[i]) {cout << "LESS"; return 0;}
		}
	}
	cout << "EQUAL";
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<limits>
#include<list>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0;i < (n); ++i)


int main(){
	int n;
	cin >> n;
	vector<int>a(n);
	rep(i, n)cin >> a[i];
	int count = 0;
	for (int i = 0; i < n; i += 2) {
		if (a[i] % 2 == 1)count++;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define eps DBL_EPSILON
#define moder 10007
#define int long long
#define ll long long
#define INF LLONG_MAX/3
#define P std::pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
string s;
int n;
signed main(){
	cin>>s>>n;
	rep(i,s.size()){
		if(s[i]=='a')continue;
		if('z'-s[i]+1<=n){
			n-='z'-s[i]+1;
			s[i]='a';
		}
	}
	int k=s[s.size()-1]-'a';
	k+=n;
	k%=26;
	s[s.size()-1]='a'+k;
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 512
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextLong()
    val a = (0 until n).map { sc.next().toInt() }
    println(problem167d(n, k, a))
}

fun problem167d(n: Int, k: Long, a: List<Int>): Int {
    data class LoopPoint(val range: Int, val point: Int)
    val visited = hashMapOf<Int, Int>()
    visited[1] = 0
    var loopPoint = LoopPoint(-1, -1)
    var current = 1
    for (i in 0 until n) {
        val next = a[current - 1]
        if (i.toLong() >= k - 1) {
            return next
        }
        if (visited.contains(next)) {
            loopPoint = LoopPoint(i + 1 - visited[next]!!, next)
            break
        }
        visited[next] = i + 1
        current = next
    }

    val loopIndex = (k - visited[loopPoint.point]!!) % loopPoint.range
    current = loopPoint.point
    for (i in 0 until loopIndex) {
        current = a[current - 1]
    }
    return current
}

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

int main(){
    long long int a,b,c,d,e,f;
    cin>>a>>b;
    c=max(a,b);
    d=min(a,b);
    while(d!=0){
        e=c/d;
        f=c%d;
        c=d;
        d=f;
    }
    cout<<a*b/c<<endl;
    return 0;
}





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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll n,k;

int main(){
  cin>>n>>k;
  ll cntk=0;
  ll cntr=0;
  repl(i,1,n+1)if(i%k==0)cntk++;
  if(k%2==0){
    ll r=k/2;
    repl(i,1,n+1)if(i%k==r)cntr++;
  }
  cout<<(ll)pow(cntk,3LL)+(ll)pow(cntr,3LL)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;


struct UnionFind {
	VI par;
	UnionFind(int N) :par(N) {
		REP(i, N)par[i] = i;
	}
	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}
	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

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

	int N; cin >> N;
	VI A(N);
	REP(i, N)cin >> A[i];
	SORT(A);
	cout << A[N - 1] - A[0] << endl;
	return 0;
}



Measured memory_bytes: 256