akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
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; cin >> n;
    vint t(n), a(n);
    rep(i, n) cin >> t[i]; 
    rep(i, n) cin >> a[i]; 

    vector<ll> ans(n);

    if(n==1) {
        if(a[0] != t[0]) pr(0);
        else pr(1);
        return 0;
    }
    if(a[0] > a[1] && t[0] != a[0]) {pr(0); return 0;}
    if(t[n-2] < t[n-1] && t[n-1] != a[n-1]) {pr(0); return 0;}

    if(n==2) {pr(1); return 0;}

    ans[0] = 1;
    ans[n-1] = 1;
    FOR(i, 1, n-1){
        if(t[i] < t[i-1] || a[i] < a[i+1]){pr(0); return 0;}
        if(t[i] > t[i-1] && a[i] > a[i+1]){
            if(a[i] != t[i]) {
                pr(0); 
                return 0;
                // pr('c');
                break;
                }
            ans[i] = 1;
        }else if(t[i] > t[i-1]){
            if(a[i] < t[i]) {pr(0); return 0;}
            ans[i] = 1;
        }else if(a[i] > a[i+1]){
            if(a[i] > t[i]) {pr(0); return 0;}
            ans[i] = 1;
        }else{
            ans[i] = (ll)min(a[i], t[i]);
        }
    }

    ll k = 1;
    rep(i, n){
        k *= ans[i];
        k %= MOD;
    }


    reverse(ALL(a));
    reverse(ALL(t));
    swap(a, t);
    if(n==1) {
        if(a[0] != t[0]) pr(0);
        else pr(1);
        return 0;
    }
    if(a[0] > a[1] && t[0] != a[0]) {pr(0); return 0;}
    if(t[n-2] < t[n-1] && t[n-1] != a[n-1]) {pr(0); return 0;}

    if(n==2) {pr(1); return 0;}

    ans[0] = 1;
    ans[n-1] = 1;
    FOR(i, 1, n-1){
        if(t[i] < t[i-1] || a[i] < a[i+1]){pr(0); return 0;}
        if(t[i] > t[i-1] && a[i] > a[i+1]){
            if(a[i] != t[i]) {
                pr(0); 
                // pr('c');
                break;
                }
            ans[i] = 1;
        }else if(t[i] > t[i-1]){
            if(a[i] < t[i]) {pr(0); return 0;}
            ans[i] = 1;
        }else if(a[i] > a[i+1]){
            if(a[i] > t[i]) {pr(0); return 0;}
            ans[i] = 1;
        }else{
            ans[i] = (ll)min(a[i], t[i]);
        }
    }

    ll p = 1;
    rep(i, n){
        p *= ans[i];
        p %= MOD;
    }
    if(p==k) pr(k);
    else pr(0);
    return 0;}

Measured memory_bytes: 4780
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define gcd __gcd
#define lcm(n, m) n * m / gcd(n, m)
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define ea(i, n) for(auto&& i: n)
#define so(n) sort(n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// rtsq ルート, int 2*10^9, __gcd

int main() {
  int H,W,h,w;
  ci(H,W,h,w);
  co((H-h)*(W-w));
}

Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, h, w = sc.nextInt()
    val list = List.fill(n)((sc.nextInt, sc.nextInt))
    println(list.foldLeft(0)((sum: Int, p: (Int, Int)) => sum + (if (p._1 >= h && p._2 >= w) 1 else 0)))
  }
}

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

int main(void){
    int n;
    cin>>n;
    int s_count[n][26] = {};

    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(char c: s){
            s_count[i][c-'a'] ++;
        }
    }

    string ans = "";
    for(int i=0;i<26;i++){
        int min_count = 100;
        for(int j=0;j<n;j++){
            min_count = min(min_count,s_count[j][i]);
        }
        if(min_count<100){
            ans += string(min_count, char('a'+i));
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;

void gen() {exit(0);}
int main() {
    #ifdef DEBUG
    freopen("input", "r", stdin);
//    freopen("output", "w", stdout);
//    gen();
    #endif
    
    int N = 100005;
    vector<int> cur = {1};
    for (int x = 6; x < N; x *= 6)
        cur.push_back(x);
    for (int x = 9; x < N; x *= 9)
        cur.push_back(x);
    int dp[N];
    fill(dp, dp + N, -1);
    dp[0] = 0;
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= N; i++) {
        if (dp[i] > -1) {
            for (int x : cur) {
                if ((i + x) < N) {
                    if (dp[i + x] == -1) dp[i + x] = dp[i] + 1;
                    else dp[i + x] = min(dp[i + x], dp[i] + 1);
                }
            }
        }
    }
    
//    for (int n = 1; n <= 100000; n++) {
        printf("%d\n", dp[n]);
//    }
    
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
ll strtoint(string str);
int main(){
	fast;
	ll k,a,b; cin>>k>>a>>b;
	bool ok=0;
	for(auto i=a;i<=b;++i){
		if(i%k==0){ok=1;break;}
	}
	(ok)?cout<<"OK\n":cout<<"NG\n";
	return 0;
}
ll strtoint(string str){
	ll x=0;
	stringstream ss;
	ss<<str;
	ss>>x;
	return x;
}

Measured memory_bytes: 3536
package main

import (
	"fmt"
)

func main() {
  var a, b int
  var op string
  
  fmt.Scanf("%d", &a)
  fmt.Scanf("%s", &op)
  fmt.Scanf("%d", &b)
  
  ans := 0
  if op == "+" {
    ans = a + b
  }
  if op == "-" {
    ans = a - b
  }
  
  fmt.Printf("%d\n", ans)
}

Measured memory_bytes: 1832
<?php
define('MOD', 10**9+7);

//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$M) = explode(" ",trim(fgets(STDIN)));
//$a[] = array_map('intval',explode(" ",trim(fgets(STDIN))));
//function chmax(&$a,$b) {if ($a<$b){$a=$b;return true;}return false;}
//function chmix(&$a,$b) {if ($a>$b){$a=$b;return true;}return false;}
//

$res = str_pad("",$N,"-");
for($i=0;$i<$M;$i++) {
  list($s,$c) = explode(" ",trim(fgets(STDIN)));
  if ($res[$s-1]!="-" && $res[$s-1]!=$c) {
    printf("-1\n");exit;
  }
  $res[$s-1]=$c;
}
if ($N>1 && $res[0]=="-") $res[0]=1;
$res = str_replace("-","0",$res);
if (strlen((String)(int)$res)!=$N) {
  $res = -1;
}
printf("%d\n",$res);


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

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

int msg() {
    srand( time( 0 ) ) ;
    vector < string > st = {
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!",
        "Go Go fight!"
    } ;
    cerr << st[ rand() % sz( st ) ] ;
    return 0 ;
}

void FastInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}



int n , m ;
char a[ 200 ][ 200 ] ;
int main() {
    cin >> n >> m ;
    forn( int , i , 0 , n ){
      forn( int , j , 0 , n ){
        cin >> a[ i ][ j ] ;
      }
    }

    string d , b ;
    forn( int , i , 0 , m ){
      cin >> d ;
      b += d ;
    }

    forn( int , i , 0 , n - m + 1 ){
      forn( int , j , 0 , n - m + 1 ){
         string t = "" ;
         forn( int , c , i , i + m ){
           forn( int , f , j , j + m ){
                t += a[ c ][ f ] ;
           }
         }
         if( t == b ){
            cout << "Yes\n" ;
            return 0 ;
         }
      }
    }

    cout << "No" ;

    return 0 ;
}



Measured memory_bytes: 256
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}


fn main() {
    let mut ans:usize = 0;
    let n: usize;
    input!(n);
    let mut v: Vec<usize> = input_vector();
    v.sort();
    let mut i = v.iter();

    for _ in 0..n {
        let a = i.next().unwrap();
        let b = i.next().unwrap();

        ans += *a;
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <iostream>
using namespace std;
typedef long long int ll;
int main(){
 ll n,k;
 cin >>n>>k;
 ll a[n];
 for(ll i=0;i<n;i++)  cin >>a[i];
 if((n-1)%(k-1)==0) cout <<(n-1)/(k-1) <<endl;
 else cout << ((n-1)/(k-1))+1<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
 
int main(void){
 
int S;
int h, m, s, ms;

scanf("%d",&S);

h = S / 3600;
ms = S % 3600;
m = ms / 60;
s = ms % 60;

printf("%d:%d:%d\n", h, m, s);
 
return 0;
 
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((int)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;

void print(Vl v){
    rep(i, 0, sz(v)){
        if(i) cout << " ";
        cout << v[i];
    }
    cout << endl;
}

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

ll dp[105][100005];
// 価値jをを得るための重さの最小値

int main() {
    ll n, W; cin >> n >> W;
    Vl w(n), v(n);
    rep(i, 0, n) cin >> w[i] >> v[i];

    rep(i, 0, 104) rep(j, 0, 100004) dp[i][j] = INF;
    dp[0][0] = 0;

    Rep(i, 1, n){
        Rep(j, 0, 100000){
            chmin(dp[i][j], dp[i-1][j]);
            if(j-v[i-1] >= 0) chmin(dp[i][j], dp[i-1][j-v[i-1]]+w[i-1]);
        }
    }

    for(int i = 100000; i >= 0; i--){
        if(dp[n][i] <= W){
            co(i);
            return 0;
        }
    }

    // Rep(i, 0, n){
    //     cout << dp[i][30] << " " << dp[i][80] << " " << dp[i][140];
    //     cout << endl;
    // }


    return 0;
}


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

#define ll   long long int
#define PI 3.14159265358979

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s, t;
    cin>>s;
    for(char b:s)
    {
        if(b=='B')
        {
            if(!t.empty())
                t.pop_back();
        }
        else
            t+=b;
    }
    cout<<t;
    return 0;
}


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

struct RSQ {
	using type = int;
	static const type id() { return 0; }
	static type op(const type& l, const type & r) { return l + r; }
};

template <typename M>
class PersistentSegmentTree {
	using T = typename M::type;
	struct node {
		T val;
		node *l, *r;
		node() {}
		node(T val, node *left = nullptr, node *right = nullptr) : val(val), l(left), r(right) {}
		void init(T v, node *left, node *right) {
			val = v;
			l = left;
			r = right;
		}
	};
	const int n;
	vector<node*> root;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	node *new_node(int val = 0, node *l = nullptr, node *r = nullptr) {
		return new node(val, l, r);
	}
	node *fix(node *x, int p, T val, int lb, int ub) {
		if (p < lb || ub <= p) return x;
		if (lb + 1 == ub) return new_node(M::op(x == nullptr ? M::id() : x->val, val));
		if (x == nullptr) x = new_node(M::id());
		else x = new_node(x->val, x->l, x->r);
		int c = (lb + ub) / 2;
		x->l = fix(x->l, p, val, lb, c);
		x->r = fix(x->r, p, val, c, ub);
		x->val = M::op(x->l == nullptr ? M::id() : x->l->val, x->r == nullptr ? M::id() : x->r->val);
		return x;
	}
	T sub(node *x, int l, int r, int lb, int ub) {
		if (x == nullptr || ub <= l || r <= lb) return M::id();
		if (l <= lb && ub <= r) return x->val;
		int c = (lb + ub) / 2;
		return M::op(sub(x->l, l, r, lb, c), sub(x->r, l, r, c, ub));
	}
public:
	PersistentSegmentTree(int n_) : n(size(n_)) {
		root.push_back(nullptr);
	}
	void add(int p, T val, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		root.push_back(fix(root[rt], p, val, 0, n));
	}
	T find(int l, int r, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		return sub(root[rt], l, r + 1, 0, n);
	}
	int getversion() {
		return root.size() - 1;
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q, com, x, y;
	cin >> n >> q;
	PersistentSegmentTree<RSQ> st(n);
	while (q--) {
		cin >> com >> x >> y;
		if (com) {
			printf("%d\n", st.find(x - 1, y - 1));
		}
		else {
			st.add(x - 1, y);
		}
	}
	return 0;
}

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

int main(){
  string S;
  bool b = 1;
  cin >> S;
  set<char> c;
  for(int i=0;i<S.size();++i){
    if(!c.count(S.at(i))){
      c.insert(S.at(i));
    }
  }
  char t = 'a';
  for(int i=0;i<26;++i){
    if(!c.count(t)){
      cout << t << endl;
      b = 0;
      break;
    }else{
      t += 1;
    }
  }
  if(b){
    cout << "None" << endl;
  }
}


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

typedef long long ll;
#define MAX 100005
#define MAX_H 10000 * 1000000

int main(){
  ll  N,K;
  int h[MAX];
  ll cost[MAX];
  scanf("%lld", &N); scanf("%lld", &K);
  for(ll i=0;i<N;i++){
    int k;
    scanf("%d", &k);
    h[i] = k;
  }

  cost[0] = 0;
  for(ll i=1;i<K;i++){
    ll mini = MAX_H;
    for(ll l=0;l<i;l++){
      mini = min(mini, abs(h[i]-h[i-l-1])+cost[i-l-1]);
    }
    cost[i] = mini;
  }
  for(ll i=K;i<N;i++){
    ll mini = MAX_H;
    for(int l=0;l<K;l++){
      mini = min(mini, abs(h[i]-h[i-l-1])+cost[i-l-1]);
    }
    cost[i] = mini;
  }
  cout  << cost[N-1];
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
#define Mod 1000000007ll
#define pow ksm
inline int ksm(int a,int x){
	LL ans=1,w=a;
	while(x){
		if(x&1)ans=ans*w%Mod;
		x>>=1;
		w=w*w%Mod;
	}
	return ans;
}
#define MN 4000005
#define mn 2005
int fac[MN],dfac[MN],n,k,f[mn][mn];
inline int C(int n,int m){
	return 1ll*fac[m]*dfac[n]%Mod*dfac[m-n]%Mod;
}
void init(int N){
	fac[0]=1;
	for(int i=1;i<=N;++i)
		fac[i]=fac[i-1]*i%Mod;
	dfac[N]=ksm(fac[N],Mod-2);
	for(int i=N-1;i>=0;--i){
		dfac[i]=(LL)dfac[i+1]*(LL)(i+1)%Mod;
	}
}
signed main(){
	scanf("%lld%lld",&n,&k);
	if(k==1){
		puts("1");
		return 0;
	}
	init(n*k);
	f[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=i;++j){
			f[i][j]=(f[i][j]+f[i-1][j])%Mod;
			if(j)f[i][j]=(f[i][j]+(f[i][j-1]*(n-j+1)%Mod*C(k-2,n-i+(k-1ll)*(n-j+1ll)-1ll)+Mod))%Mod;	
		}
	printf("%lld",f[n][n]);
	return 0;
}


Measured memory_bytes: 92672
#include <bits/stdc++.h>
using namespace std;
#define lli long long int


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);



    int n;
    cin >> n;
    vector<double> dp(n + 1);
    dp[0] = 1;

    for(int i = 1 ; i <= n ; ++i){
        double p;
        cin >> p;
        for(int j = i ; j >= 0 ; --j){
            if(j == 0) dp[j] = dp[j]*(1-p);
            else dp[j] = dp[j-1]*p + dp[j]*(1-p);
        }
    }
    double ans = 0 ;
    for(int i = 0 ; i <= n ; ++i){
        if(i > n - i)   ans += dp[i];
    }
    cout.precision(10);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int beki(int K){
  if(K==0) return 1;
  else return 2*beki(K-1);
}

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

    int A[N];
    int left = 0, right = 0;

    for(int i=0;i<M;i++){
      cin >> A[i];
      if(A[i]<X) left++;
      else right++;
    }
    cout << min(left,right) <<endl;
  	

  return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N = int(input())
  S = input()
  ans = 0
  for i in range(N-2):
    if S[i]=='A' and S[i+1] == 'B' and S[i+2]=='C':
      ans += 1
  print(ans)
  
  
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll a[6];
  rep(i, 6)cin >> a[i];
  bool ans = true;
  rep(i, 4){
    for(ll j=i+1;j<=4;j++){
      ans = ans and (abs(a[j]-a[i])<=a[5]);
    }
  }
  cout << (ans?"Yay!":":(");
  return 0;
}


Measured memory_bytes: 256
// #include C/C++ {
#include <bits/stdc++.h>
// }
using namespace std;
// #typedef {
typedef long long int64;
typedef pair <int, int> PII;
typedef pair <int64, int64> PLL;
// }

// #parameter{
#ifdef _DEBUG

#define TYPE decltype
#define RF(filename) {freopen((filename), "r", stdin);}
#define WF(filename) {freopen((filename), "w", stdout);}
#define DF(filename) {freopen((filename), "w", stderr);}
#define eprintf printf

#else

#define TYPE __typeof
#define RF(filename) {;}
#define WF(filename) {;}
#define DF(filename) {;}
#define eprintf(...)
#define fprintf(...)

#endif

// #define {
#define SZ(a) ((int)(a).size())
#define X first
#define Y second
#define MP make_pair
#define L(x) ((x)<<1)
#define R(x) ((x)<<1 | 1)
#define max3(x, y, z) (max(max((x), (y)), (z)))
#define min3(x, y, z) (min(min((x), (y)), (z)))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(it) (it).begin(), (it).end()
#define FILL(__space, __val) memset(__space, __val, sizeof(__space))
#define MOVE(__spaceTo, __spaceFrom) memmove(__spaceTo, __spaceFrom, sizeof(__spaceTo))
#define UNIQUE(__vector) sort(ALL(__vector)), __vector.resize(unique(ALL(__vector)) - __vector.begin())
#define FOR(it, c) for( TYPE((c).begin()) it = (c).begin(); it != (c).end(); it++)
/////////////////////////////////////////////////////////////
const double PI = acos(-1.0);
const double EPS = 1e-6;

#define MAX_N 100005
#define MAX_M 55
#define MOD (int)(1e9+7)
#define INF ((1 << 30) - 1)
#define BINF ((1LL << 62) - 1LL)
#define NONE -1
#define NIL 0
// }

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

/////////////////////////////////////////////////////////////
int main() {
	RF("input.txt");
	//  WF("output.txt");
	DF("err.txt");
	
	int N;
	scanf("%d", &N);
	int d[MAX_N];
	for (int i = 0; i < N; i++) scanf("%d", d + i);
	sort(d, d + N);
	printf("%d\n", d[N >> 1] - d[(N - 1) >> 1]);
	return 0;
}

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

using namespace std;

using Weight=long long;

struct Edge{
    int src,dst;
    Weight weight;
    Edge(int src,int dst,Weight weight):
    src(src),dst(dst),weight(weight){}
};

auto operator < (const Edge &e,const Edge &f){
    if(e.weight!=f.weight)return e.weight>f.weight;
    else if(e.src!=f.src)return e.src<f.src;
    else return e.dst<f.dst;
}

using Edges=vector<Edge>;
using Graph=vector<Edges>;

template<typename T>
struct UnionFind{
    vector<T>data;
    UnionFind(T n):data(n,-1){}
    bool unite(T x,T y){
        x=root(x);y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];data[y]=x;
        }
        return x!=y;
    }
    T root(T x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    bool same(T x,T y){
        return root(x)==root(y);
    }
    T size(T x){
        return -data[root(x)];
    }
};

pair<Weight,Edges>kruskal(const Graph &g){
    int n=g.size();
    UnionFind<int> uf(n);
    priority_queue<Edge>q;
    for(int i=0;i<n;++i){
        for(auto e:g[i]){
            if(i<e.dst)q.push(e);
        }
    }
    Weight total=0;
    Edges forest;
    while(forest.size()<n-1 && !q.empty()){
        Edge e=q.top();q.pop();
        if(uf.unite(e.src,e.dst)){
            forest.push_back(e);
            total+=e.weight;
        }
    }
    return pair<Weight, Edges>(total,forest);
}

int main(){
	int n;
	cin>>n;
	vector<pair<Weight,int>>px(n),py(n);
	for(int i=0;i<n;++i){
		int x,y;
		cin>>x>>y;
		px[i]=make_pair(x,i);
		py[i]=make_pair(y,i);
	}
	sort(px.begin(),px.end());
	sort(py.begin(),py.end());
	Graph g(n);
	for(int i=0;i<n-1;++i){
		g[px[i].second].emplace_back(px[i].second,px[i+1].second,px[i+1].first-px[i].first);
		g[px[i+1].second].emplace_back(px[i+1].second,px[i].second,px[i+1].first-px[i].first);
		g[py[i].second].emplace_back(py[i].second,py[i+1].second,py[i+1].first-py[i].first);
		g[py[i+1].second].emplace_back(py[i+1].second,py[i].second,py[i+1].first-py[i].first);
	}
	cout<<kruskal(g).first<<endl;
}


Measured memory_bytes: 22252
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int a = in.nextInt();
            out.println(a + a * a + a * a * a);
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
            this.bufPointer = 0;
            this.bufLength = 0;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int nextInt() {
            int n = 0;

            int b = readByte();
            while (isSpaceChar(b))
                b = readByte();

            boolean minus = (b == '-');
            if (minus)
                b = readByte();

            while (b >= '0' && b <= '9') {
                n *= 10;
                n += b - '0';
                b = readByte();
            }

            if (!isSpaceChar(b))
                throw new NumberFormatException();

            return minus ? -n : n;
        }

    }
}



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

using namespace std;
using ll = long long;
 
#define rep(i, n)      for (int i = 0; i < (n); i++)
#define repr(i, n)     for (int i = (n) - 1; i >= 0; i--)
#define repe(i, l, r)  for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define repi(i, l, r)  for (int i = (l); i <= (r); i++)
#define repir(i, l, r) for (int i = (r); i >= (l); i--)
#define range(a) a.begin(), a.end()
void initio() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

int main() { initio();
  int N; cin >> N;
  string S; cin >> S;
  rep(i, S.size()) {
    S[i] = (S[i] - 'A' + N) % 26 + 'A';
  }
  cout << S << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <tuple>
#include <string>
using namespace std;

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    char begin_char = S[0];

    // Count initial happy
    int happy = 0;
    int swap = 0;
    bool final_swap = S[0] != S[N-1];
    if (S[0] == 'R' && S[1] == 'R') {
        happy++;
    }
    if (S[N-1] == 'L' && S[N-2] == 'L') {
        happy++;
    }
    for (int i = 1; i < N-1; i++) {
        if (S[i] == 'L' && S[i-1] == 'L') {
            happy++;
        }
        if (S[i] == 'R' && S[i+1] == 'R') {
            happy++;
        }
    }

    bool detect_diff = false;

    for (int i = 1; i < N ; i++) {
        if (!detect_diff && S[i] != begin_char) {
            detect_diff = true;
        } else if (detect_diff && S[i] == begin_char) {
            detect_diff = false;
            swap++;
        }
    }

    if (K >= swap) {
        K -= swap;
        happy += 2 * swap;
    } else {
        happy += 2*K;
        K = 0;
    }
    // Check if left over
    if (K > 0 && final_swap) {
        happy++;
    }
    cout << happy << "\n";

}

Measured memory_bytes: 512
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE LambdaCase            #-}
{-# LANGUAGE MagicHash             #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE MultiWayIf            #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE ViewPatterns          #-}

import           Control.Applicative
import           Control.Exception
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString             as B
import qualified Data.ByteString.Builder     as B
import qualified Data.ByteString.Char8       as C
import qualified Data.ByteString.Internal    as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import qualified Data.Foldable               as F
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import qualified Data.List                   as L
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Storable         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           GHC.Exts
import qualified System.IO                   as IO
import           Unsafe.Coerce

main :: IO ()
main = do
    [h, w] <- map read.words <$> getLine :: IO [Int]
    B.PS p 0 l <- C.filter (\c -> c == '#' || c == '.')
      <$> C.hGet IO.stdin (h*(w+1))
    let mat = U.unsafeFromForeignPtr0 p l
    print $ solve h w mat

solve :: Int -> Int -> U.Vector Word8 -> Int
solve h w mat = subtract 3 . U.maximum $ U.zipWith (+) lr ud
  where
    trans :: U.Vector Int -> U.Vector Int
    trans m = U.unsafeBackpermute m $ U.generate (h * w) $ \ij ->
        let (i, j) = quotRem ij w
        in j * h + i

    lr :: U.Vector Int
    lr = U.concatMap (\i ->
        let row = U.unsafeSlice (i * w) w mat
        in U.zipWith (+)
            (U.postscanl' (\acc c -> if c == B.c2w '#' then 0 else acc + 1) 0 row)
            (U.postscanr' (\c acc -> if c == B.c2w '#' then 0 else acc + 1) 0 row)
        )
        $ U.generate h id

    ud :: U.Vector Int
    ud = trans
        . U.concatMap (\j ->
            let column = U.map (U.unsafeIndex mat) $ U.iterateN h (+w) j
            in U.zipWith (+)
                (U.postscanl' (\acc c -> if c == B.c2w '#' then 0 else acc + 1) 0 column)
                (U.postscanr' (\c acc -> if c == B.c2w '#' then 0 else acc + 1) 0 column)
        )
        $ U.generate w id


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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int N, K;
    cin >> N >> K;
    double ans = 0;
    for(int i = 1; i <= N; i++){
        int k = 0;
        while(1){
            double a = i * powl(2, k);
            if(a >= K) break;
            else k++;
        }
        ans += (1.0/N) * powl(0.5, k);
    }
    printf("%.12f\n", ans);
    return 0;
}

Measured memory_bytes: 512
#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

int n,k;
vector<int> a,b;
bool f(int x){
    b=a;
    b.erase(b.begin()+x);
    bool dp[5010][5010]={};
    dp[0][0]=1;
    rep(i,0,n-1){
        rep(j,0,k+1)if(dp[i][j]){
            dp[i+1][j]=1;
            dp[i+1][min(k,j+b[i])]=1;
        }
    }
    bool res=0;
    rep(i,max(0,k-a[x]),k)if(dp[n-1][i])res=1;
    return res;
}

int main(){
    scanf("%d%d",&n,&k);
    a.resize(n);
    rep(i,0,n)scanf("%d",&a[i]);
    sort(ALL(a)); reverse(ALL(a));
    int l=-1,r=n,mid;
    while(r-l>1){
        mid=(l+r)/2;
        if(f(mid))l=mid;
        else r=mid;
    }
    printf("%d\n",n-r);
    return 0;
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

ll mod = 1e9+7;


int main(){
    int N;
    cin >> N;
    Vd p(N+1,0);
    vector<Vd> dp(N+1, Vd(N+1,0.0));
    REP(i,N) {
        cin >> p[i+1];
        }

    dp[0][0] = 1;
    FOR(i,1,N+1) {
        dp[i][0] = dp[i-1][0]*(1-p[i]);
        //cout << dp[i][0] << endl;
        FOR(j,1,N+1) {
            dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i];
            //cout << dp[i][j] << endl;
        }
    }
    double ans = 0;
    FOR(i,N/2+1,N+1) ans += dp[N][i];
    printf("%.10f\n",ans);
}

Measured memory_bytes: 70656
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
from fractions import gcd
def resolve():
    N,=pin()
    A=lispin()
    temp=A[0]
    for i in range(1,N):
        temp=(temp*A[i])//(gcd(temp,A[i]))
    x=(temp-1)
    ans=0
    for a in A:
        ans+=x%a
    print(ans)
#%%submit!
resolve()

Measured memory_bytes: 66536
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
typedef long long ll;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main() {
	string x, y;
	cin >> x >> y;
	int m = x.size(), n = y.size();
	int dp[1005][1005];
        memset(dp,0,sizeof(dp));
	repp(i, 0, m+1)dp[i][0] = i;
	repp(i, 0, n+1)dp[0][i] = i;
	repp(i, 0, m)repp(j, 0, n) {
		dp[i + 1][j + 1] = min(dp[i][j] + (x[i] != y[j]), dp[i][j + 1] + 1);dp[i+1][j+1]=min(dp[i+1][j+1], dp[i + 1][j]+1 );//コピー（置換）,削除、挿入
	}
	cout << dp[m][n] << endl;
	return 0;
}


Measured memory_bytes: 7172
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
#include<utility>
#include<cmath>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
#include<cstring>
#include<iterator>
#include<bitset>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
static const int MOD = 1000000007;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const int INF = 1000010000;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define UB upper_bound
#define LB lower_bound
#define all(x) (x).begin(),(x).end()
#define SZ(a) int((a).size())
#define LEN(a) int((a).length())
#define MAX(a,b,c) max((a),max((b),(c)))
#define MIN(a,b,c) min((a),min((b),(c)))
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REP1(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREP1(i,x) for(int i=((int)(x));i>0;i--)
#define int ll

int power(int x, int n){
    int tmp = 1;
  
    if(n>0){
      tmp = power(x, n/2);
      if(n%2==0) tmp = tmp*tmp;
      else tmp = (((tmp*tmp))*x);
    }
    return tmp;
}

signed main(){
    int x,y;
    scanf("%lld%lld",&x,&y);

    if(x==y){
        puts("1");
        return 0;
    }

    int z = y/x;
    int ans = 0;
    while(power(2,ans)<=z) ans++;

    printf("%lld\n",ans);
    return 0;
}

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

int main(int argc ,char *const argv[]){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int am=min(b,d);
    int amm=max(a,c);
    if(am<amm) cout<<"0"<<endl;
    else cout<<abs(am-amm)<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char pre = s.charAt(0);
        String ans = "Good";
        for (int i = 1; i < 4; i++) {
            if(pre == s.charAt(i)) ans = "Bad";
            pre = s.charAt(i);
        }
        System.out.println(ans);
        sc.close();

    }

}


Measured memory_bytes: 21332
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,k,a[100005],g,A;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",a+i),A=max(A,a[i]);
    g=a[1];
    for(int i=2;i<=n;++i)g=__gcd(g,a[i]);
    if(k<=A&&k%g==0)puts("POSSIBLE");
    else puts("IMPOSSIBLE");
    //system("pause");
    return 0;
}


Measured memory_bytes: 640
N,x=map(int,input().split())
a=list(map(int,input().split()))

ans=0
for i in range(N-1):
    if a[i]+a[i+1]>x:
        if a[i]+a[i+1]-x<=a[i+1]:
            ans+=(a[i]+a[i+1]-x)
            a[i+1]-=(a[i]+a[i+1]-x)
        else:
            ans+=(a[i]+a[i+1]-x)
            a[i+1]=0
print(ans)

Measured memory_bytes: 14132
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int T;
LL n,a,b,c,d;
map<LL,LL> M;
LL cal(LL n){
	if (n==0) return 0;
	if (n==1) return d;
	if (M.find(n)!=M.end()) return M[n];
	LL t=cal(n/2)+a+n%2*d;
	if (d<=t/n) t=n*d;
	if (n%2!=0) t=min(t,cal(n/2+1)+a+(2-n%2)*d);
	if (n%3<2) t=min(t,cal(n/3)+b+n%3*d);
	else t=min(t,cal(n/3+1)+b+(3-n%3)*d);
	if (n%5<3) t=min(t,cal(n/5)+c+n%5*d);
	else t=min(t,cal(n/5+1)+c+(5-n%5)*d);
	M[n]=t;
	return t;
}
void doit(){
	cin>>n>>a>>b>>c>>d;
	M.clear();
	cout<<cal(n)<<endl;
}
int main(){
	cin>>T;
	while (T--) doit();
	return 0;
}

Measured memory_bytes: 4356
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 100000;
const int MAXK = 100000;
const int nullvalue = -12345678;
typedef long long LL;
vector<pair<int, int>> edgelist;
vector<int> adj[MAXN + 1];

bool visited[MAXN + 1];
int ancestor[MAXN + 1];
int possible[MAXN + 1];
int n, k;

void bfs(){
	memset(visited, 0, sizeof visited);
	for (int i = 0; i < MAXK + 1; i++){
		possible[i] = nullvalue;
	}
	possible[1] = k;
	visited[1] = true;
	visited[0] = true;

	queue<int> frontier;
	int temp_k = k - 1;
	for (int v : adj[1]){		
		possible[v] = temp_k;
		--temp_k;
		frontier.push(v);
	}

	while (not frontier.empty()){
		int u = frontier.front(); frontier.pop();
		visited[u] = true;
		if (adj[u].size() <= 2){
			if (possible[u] == nullvalue){
				possible[u] = k - 2;
			}
			for (int v : adj[u]){
				if (not visited[v]){
					frontier.push(v);
				}
			}
		}
		else{
			int temp_k = k - 2;
			if (possible[u] == nullvalue){
				possible[u] = k - 2;
			}
			for (int v : adj[u]){
				if (not visited[v]){
					possible[v] = temp_k;
					--temp_k;
					frontier.push(v);
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++){
		int a, b; cin >> a >> b;
		edgelist.push_back(make_pair(a, b));
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	adj[0].push_back(1);
	adj[1].push_back(0);
	memset(visited, 0, sizeof visited);
	LL ans = 1;
	bfs();
	for (int i = 1; i <= n; i++){
		cerr << possible[i] << ' ';
		ans *= possible[i]; ans %= MOD;
	}
	if (ans < 0) ans = 0;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 7796
//
//AtCoder Beginner Contest 172
//AS
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#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 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 ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

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


Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int main(){
    int N, M; cin >> N >> M;
    vector<int> x, y;
    x.push_back(-1000000007);
    y.push_back(-1000000007);
    x.push_back(0);
    y.push_back(0);
    x.push_back(1000000007);
    y.push_back(1000000007);
    vector<int> A(N), B(N), C(N);
    vector<int> D(M), E(M), F(M);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i] >> C[i];
        x.push_back(A[i]);
        x.push_back(B[i]);
        y.push_back(C[i]);
    }
    for(int i=0;i<M;i++){
        cin >> D[i] >> E[i] >> F[i];
        x.push_back(D[i]);
        y.push_back(E[i]);
        y.push_back(F[i]);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    map<int, int> xidx, yidx;
    for(int i=0;i<x.size();i++) xidx[x[i]] = i;
    for(int i=0;i<y.size();i++) yidx[y[i]] = i;
    const int dx[] = {-1, 0, 1, 0};
    const int dy[] = {0, -1, 0, 1};
    vector canMove(x.size()-1, vector(y.size()-1, vector(4, 1)));
    vector visit(x.size()-1, vector(y.size()-1, 0));
    for(int i=0;i<N;i++){
        int a = xidx[A[i]];
        int b = xidx[B[i]];
        int c = yidx[C[i]];
        for(int j=a;j<b;j++){
            canMove[j][c-1][3] = canMove[j][c][1] = 0;
        }
    }
    for(int i=0;i<M;i++){
        int d = xidx[D[i]];
        int e = yidx[E[i]];
        int f = yidx[F[i]];
        for(int j=e;j<f;j++){
            canMove[d-1][j][2] = canMove[d][j][0] = 0;
        }
    }
    queue<pair<int, int>> qu; qu.emplace(xidx[0], yidx[0]);
    visit[xidx[0]][yidx[0]] = 1;
    bool ok = true;
    while(!qu.empty()){
        auto pr = qu.front(); qu.pop();
        auto cx = pr.first;
        auto cy = pr.second;
        if(cx == 0 || cx == x.size() - 2 || cy == 0 || cy == y.size() - 2){
            ok = false;
            break;
        }
        for(int i=0;i<4;i++){
            if(!canMove[cx][cy][i]) continue;
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(visit[nx][ny]) continue;
            visit[nx][ny] = 1;
            qu.emplace(nx, ny);
        }
    }
    if(ok){
        long long res = 0;
        for(int i=0;i<x.size()-1;i++){
            for(int j=0;j<y.size()-1;j++){
                if(!visit[i][j]) continue;
                long long dx = x[i+1] - x[i];
                long long dy = y[j+1] - y[j];
                res += dx * dy;
            }
        }
        cout << res << endl;
    } else {
        cout << "INF" << endl;
    }
}

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

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int>  keta(N, -1);
  bool flag = true;
  REP(i, M){
    int s, c;
    cin >> s >> c;
    s--;
    if(keta[s] == -1){
      keta[s] = c;
    }
    else if(keta[s] != c){
      flag = false;
    }
  }
  if(N != 1){
    if(keta[0] == -1){
      keta[0] = 1;
    }
    else if(keta[0] == 0){
      flag = false;
    }
  }
  if(N==1 && keta[0] == -1){
    keta[0] = 0;
  }
  if(flag == false){
    cout << -1 << endl;
    return 0;
  }
  REP(i, N){
    if(keta[i] == -1){
      keta[i] = 0;
    }
    cout << keta[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
 
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vvvi> vvvvi;

ll k;

ll f(string s) {
    int ans = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (s[i] == s[i-1]) {
            ans++;
            s[i] = 0;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s >> k;
    ll a = f(s), b = f(s+s), c = f(s+s+s);
    if (b == a+a) cout << k*a << "\n";
    else if (c-b == a) {
        cout << a*(k/2 + k%2) + (b-a)*(k/2) << "\n";
    } else cout << a + (k-1)*(b-a) << "\n";
    return 0;
}

Measured memory_bytes: 256