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

using namespace std;

bool checkNine(int n){
    if(n < 9) return false;
    if(n == 9 || n == 91){
        return true;
    }else{
        checkNine(n%10);
    }
}

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

    if(checkNine(N)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

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

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> A(N),B(N),C(M),D(M);
  for(int i=0;i<N;i++){
    cin >> A.at(i) >> B.at(i);
  }
  for(int i=0;i<M;i++){
    cin >> C.at(i) >> D.at(i);
  }
  for(int i=0;i<N;i++){
    int minP=1000000000;
    int minQ=1000000000;
    //Pは距離、Qは対応する番号
    for(int j=0;j<M;j++){
      int P=abs(A.at(i)-C.at(j))+abs(B.at(i)-D.at(j));
      if(P<minP){
        minP=P;
        minQ=j+1;
      }
    }
    cout << minQ << endl;
  }
}

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

#define ll long long
#define M 1000000007
#define deb(x) cout<<#x<<" "<<x<<endl;
#define foi(a,b) for(int i=a;i<b;i++)
#define foj(a,b) for(int j=a;j<b;j++)
#define fod(a,b) for(int i=a;i>b;i--)
#define MAX  1e9
#define MIN -1e9
#define nl cout<<"\n";
#define show(arr,a,b) for(int i=a;i<b;i++) cout<<arr[i]<<" "; cout<<endl;
#define  mp(a,b) pair<ll,ll> p(a,b)
#define pb push_back
typedef pair<ll,ll> p1;
typedef vector<ll> vecd;
typedef vector<string> vecsd;
typedef map<ll,ll> mpd;
typedef set<ll> setd;
typedef multiset<ll> msetd;
bool cmp(ll a,ll b){
    return a>b;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x,y,a,b,c; cin>>x>>y>>a>>b>>c;
    ll arr[a],brr[b],crr[c];
    foi(0,a) cin>>arr[i];
    foi(0,b) cin>>brr[i];
    foi(0,c) cin>>crr[i];
    sort(arr,arr+a,cmp);
    sort(brr,brr+b,cmp);
    sort(crr,crr+c,cmp);
    priority_queue<ll> pq;
    for(int i=0;i<(x>a?a:x);i++) pq.push(arr[i]);
    for(int i=0;i<(y>b?b:y);i++) pq.push(brr[i]);
    for(int i=0;i<((x+y)>c?c:(x+y));i++) pq.push(crr[i]);
    ll p=x+y,ans=0;
    while(p>0){
        ans+=pq.top();
        pq.pop();
        p--;
    }
    cout<<ans<<"\n";
    return 0;
}


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

int main() {
	string a,b,c;
  	cin >> a >> b >> c;
  
  	transform(a.begin(), a.end(), a.begin() ,::toupper);
  	transform(b.begin(), b.end(), b.begin() ,::toupper);
  	transform(c.begin(), c.end(), c.begin() ,::toupper);
  
  	cout << a.at(0) << b.at(0) << c.at(0) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int h, w;
    cin >> h >> w;
    string map[h];
    int ans[h][w];
    for(int i = 0; i < h; i++) cin >> map[i];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            ans[i][j] = -1;
            for(int k = 0; k <= j; k++) {
                if(map[i][j - k] == 'c') {
                    ans[i][j] = k;
                    break;
                }
            }
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(j != w - 1)
                cout << ans[i][j] << ' ';
            else
                cout << ans[i][j] << endl;
        }
    }
}


Measured memory_bytes: 3212
one = {}
two = {}
three = {}

8.times do
  s,t = gets.split.map(&:to_f)
one[s.to_i] = t
end

8.times do
  s,t = gets.split.map(&:to_f)
  two[s.to_i] = t
end

8.times do
  s,t = gets.split.map(&:to_f)
  three[s.to_i] = t
end
top_rank = []

one_ary = one.sort {|(k1,v1),(k2,v2)| v1 <=> v2}
two_ary =two.sort {|(k1,v1),(k2,v2)| v1 <=> v2}
three_ary = three.sort{|(k1,v1),(k2,v2)| v1 <=> v2}
 top_rank.push(one_ary[0],one_ary[1],two_ary[0],two_ary[1],three_ary[0],three_ary[1])

one_ary.slice!(0,2)
two_ary.slice!(0,2)
three_ary.slice!(0,2)
under_rank = one_ary.concat(two_ary,three_ary).sort{|a,b| a[1]<=>b[1]}

top_rank.each do |i|
  i[1] = sprintf("%.02f",i[1])
  puts i.join(" ")
  end
  under_rank.each_with_index do |v,i|
    v[1] = sprintf("%.02f",v[1])
    if i < 2
      puts v.join(" ")
    end
  end


Measured memory_bytes: 6896
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

struct Data {
  ll num;
  Data() : num(0x8000000000000000l) {;}
  Data(ll n) : num(n) {;}
};

inline Data Merge(Data left, Data right) {
  return Data(left.num > right.num ? left.num : right.num);
}

struct SegmentTree {
  int n; vector<Data> data;
  SegmentTree(int N) : n(1 << N), data(n * 2) {}
  void update (int pos, Data value) {
    data[pos] = value;
    while (pos < 2*n-1) {
      int l = pos, r = pos^1;
      if (l > r) swap(l, r);
      pos = pos / 2 + n;
      data[pos] = Merge(data[l], data[r]);
    }
  }
  Data sub(int fr, int to, int node, int la, int ra) {
    if (ra<=fr || to<=la) return Data();
    if (fr<=la && ra<=to) return data[node];
    Data vl = sub(fr, to, (node-n)*2+0, la, (la+ra)/2);
    Data vr = sub(fr, to, (node-n)*2+1, (la+ra)/2, ra);
    return Merge(vl, vr);
  }
  Data query(int fr, int to) { return sub(fr, to, 2*n-2, 0, n); }
};

int main()
{
  int n;
  cin>>n;
  vector<pair<ll,ll>> vp;
  ll o = 1e9;
  for(auto&& i:irange(0,n)) {
    ll x,d;
    cin>>x>>d;
    x += o;
    vp.emplace_back(x,d);
  }
  boost::sort(vp);
  SegmentTree st(18);
  constexpr ll MOD = 998244353;
  vecll dp(n+1);
  dp[n] = 1;
  for(ll i=n-1; i>=0; --i) {
    ll x,d;
    tie(x,d) = vp[i];
    auto itr = boost::lower_bound(vp, make_pair(x+d, 0l));
    int idx = itr - begin(vp);
    ll mx = max(i, st.query(i+1, idx).num);
    st.update(i, mx);
    dp[i] = (dp[i+1] + dp[mx+1]) % MOD;
  }
  cout<<dp[0]<<endl;
  return 0;
}


Measured memory_bytes: 9836
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言
#define MAX_N 1000
bool judge(string);

int main() {
  int N;
  cin >> N;
  string n;

  for(int i=N; i>0; --i) {
    n = to_string(sqrt(i));
    
    if(judge(n) == true) {
      cout << i << endl;
      break;
    }
  }

  return 0;
}

bool judge(string n) {
  int n_size = (int)(n.length());
  int flag = 0;
  int j_flag = 1;

  for(int i=0; i<n_size; ++i) {
    if(n[i] == '.') {
      flag = 1;
    }
    if(flag) {
      if(n[i] == '.' || n[i] == '0') ;
      else {
        j_flag = 0;
        break;
      }
    }
  }

  if(j_flag) return true;
  else return false;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int D = sc.nextInt();
    if(A <= B){
      if(C <= D){
        System.out.println(A + C);
      }else{
        System.out.println(A + D);
      }
    }else{
      if(C <= D){
        System.out.println(B + C);
      }else{
        System.out.println(B + D);
      }
    }

  }
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> ans(n);
  for(ll i=0;i<n;i++) {
    cin >> a[i];
  }
  ll temp=1;
  for(ll i=0;i<n;i++) {
    ans[0]+=a[i]*temp;
    temp*=-1;
  }
  for(ll i=0;i<n-1;i++) {
    ans[i+1]=2*a[i]-ans[i];
  }
  for(ll i=0;i<n;i++) {
    if(i!=0) {
      cout << " ";
    }
    cout << ans[i];
  }
  cout << endl;
}

Measured memory_bytes: 2944
from collections import deque
n, m = list(map(int, input().split()))
al = [0] * n
bl = [0] * n
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
N = n
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

dist = [-1]*N
tag = [-1]*N
que = deque([0])
dist[0] = 0
pre = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        tag[w] = v + 1
        que.append(w)

print('Yes')
for t in tag[1:]:
    print(t)


Measured memory_bytes: 96164
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int mod =1e9+7;
const int N = (int)2e5 + 5;

void solve(){
	int n;
	cin>>n;
	double x[n];
	string u[n];
	double ans=0;
	rep(i,n){
		cin>>x[i]>>u[i];
		if(u[i]=="JPY")ans+=x[i];
		else ans+=x[i]*380000.0;
	}			
	printf("%.12f",ans);
	
    
}

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

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

void _139() {
    string s, t;
    cin >> s;
    cin >> t;

    int count = 0;
    for (int i = 0; i < 3; ++i) {
        if (s[i] == t[i])
            count++;
    }
    cout << count << endl;
}

void _138() {
    int a;
    string s;
    cin >> a;
    cin >> s;

    if (a >= 3200)
        cout << s << endl;
    else
        cout << "red" << endl;
}

void _137() {
    int a, b;
    cin >> a >> b;

    int add = a + b;
    int mult = a * b;
    int sub = a - b;

    cout << max(add, max(mult, sub)) << endl;
}

void _136() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(0, c - (a - b)) << endl;
}

void _135() {
    long long a, b;
    cin >> a >> b;

    if (abs(a - b) % 2 != 0)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << (a + b) / 2 << endl;
}

void _134() {
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

void _133() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a * n, b) << endl;
}

void _132() {
    string s;
    cin >> s;

    char    c[2];
    memset(c, 0, sizeof(c));
    int count[2];
    memset(count, 0, sizeof(count));
    c[0] = s[0];
    count[0] = 1;
    for (int i = 1; i < 4; ++i) {
        if (s[i] == c[0])
            count[0]++;
        else {
            if (c[1] == 0) {
                c[1] = s[i];
                count[1] = 1;
            }
            else {
                if (s[i] == c[1]){
                    count[1]++;
                }
                else {
                    cout << "No" << endl;
                    return;
                }
            }
        }
    }

    if (count[0] == 2 && count[1] == 2)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

void _131() {
    string s;
    cin >> s;

    char prev = s[0];
    for (int i = 1; i < 4; ++i) {
        if (s[i] == prev) {
            cout << "Bad" << endl;
            return;
        }
        else 
            prev = s[i];
    }
    cout << "Good" << endl;
}

void _130() {
    int x, a;
    cin >> x >> a;
    if (x < a)
        cout << 0 << endl;
    else
        cout << 10 << endl;
}

int main()
{
    _130();
    return 0;
}



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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

signed main() {
	int n, q;
	cin >> n >> q;
	int a[100005];
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, q) {
		int x;
		cin >> x;
		int ans = 0, s = 0, f = 0, sum = 0;
		for (;;) {
			while (f < n && sum <= x) {
				sum += a[f++];
				if (sum > x) {
					f--;
					sum -= a[f];
					break;
				}
			}
			ans += f - s;
			if (s == n - 1) {
				break;
			}
			sum -= a[s++];
		}
		cout << ans << endl;
	}

	return 0;
}



Measured memory_bytes: 3864
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..n)
        .map(|_| itr.next().unwrap().parse::<usize>().unwrap() - 1)
        .collect();

    let mut b = vec![0usize; n + 1];
    for i in 0..n {
        b[a[i]] += 1;
    }
    let mut ans = 0;
    for i in 0..n {
        if b[i] > 1 {
            ans += b[i] * (b[i] - 1) / 2;
        }
    }

    let mut out = Vec::new();
    for i in 0..n {
        if b[a[i]] > 1 {
            let tans = ans - b[a[i]] * (b[a[i]] - 1) / 2 + (b[a[i]] - 1) * (b[a[i]] - 2) / 2;
            writeln!(out, "{}", tans).ok();
        } else {
            writeln!(out, "{}", ans).ok();
        }
    }
    stdout().write_all(&out).unwrap();
}


Measured memory_bytes: 8508
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	int k,n; cin>>k>>n;
  	int a[n];
  	int till = 0;
  	int maxi = -1;
  	for(int i = 0 ; i < n ; i++)
    {
      cin>>a[i];
      int x = till;
      till = a[i];
      a[i] -= x;  
      maxi = max(maxi,a[i]);
    }
    maxi = max(maxi, k+ a[0] - till);
  	cout<<k-maxi<<endl;
  	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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 ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector <ll> v(n, 0);
  rep(i, m) {
    ll a, b;
    cin >> a >> b;
    a--; b--;
    v.at(a)++; v.at(b)++;
  }
  rep(i, n) cout << v.at(i) << endl;
}

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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 110;
int cnt[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    int n, k;
    cin >> n >> k;
    while (k--)
    {
        int d;
        cin >> d;
        for (int i = 1; i <= d; i++)
        {
            int x;
            cin >> x;
            cnt[x] = 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!cnt[i])
            ans++;
    }
    cout << ans << "\n";
    return 0;
}

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

ans_tmp = 0
targ = 1
for i, ai in enumerate(a):
    if ai == targ:
        ans_tmp += 1
        targ += 1

if ans_tmp == 0:
    print(-1)
else:
    print(N - ans_tmp)

Measured memory_bytes: 26140
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>

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

int main()
{
	int P,Q,R;

	cin>>P>>Q>>R;
	cout<<min(P+Q,min(Q+R,R+P))<<endl;;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <deque>
using namespace std;
using ll = long long;
using itn = int;
const ll MOD = 2019;
const ll INF = 9223372036854775807;

int main() {

    ll L, R;
    cin >> L >> R;

    ll min = INF;
    
    for (int i = L; i <= R - 1; i++) {
        for (int j = i+1; j <= R; j++) {
            if (((i % MOD) * (j % MOD) % MOD) < min){
                min = ((i % MOD) * (j % MOD) % MOD);
                if (min == 0) {
                    cout << 0 << endl;
                    return 0;
                }
            }
        }       
    }

    cout << min << endl;
    return 0;

    /*

    if ((L < 2019 && 2019 < R)) {
        if (L == 1) cout << 0 << endl;
        else cout << L << endl;
        return 0;
    }
    if (L == 2019 || R == 2019) {
        cout << 0 << endl;
        return 0;
    }
    

    L %= MOD;
    R %= MOD;

    if (L > R) {
        cout << L << endl;
        return 0;
    }
    
    if (L == R) {
        cout << L << endl;
        return 0;
    }

    ll mod = INF;
    
    if (L == 0) {
        cout << 0 << endl;
        return 0;
    }

    for (ll i = L; i <= R-1; i++) {
        for (ll j = i+1; j <= R; j++) {

            if (mod > ((i % MOD) * (j % MOD)) % MOD) {
                mod = (i * j) % MOD;
            }
        }
    }

    cout << mod << endl;

    */
    
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>

using namespace std;
/*
int find(int x, vector<int> &p) {
if (p[x] == x)return x;
return p[x] = find(p[x], p);
}

void uni(int x, int y, vector<int> &p) {
x = find(x, p);
y = find(y, p);
p[x] = y;
}

int same(int x, int y, vector<int> p) {
if (find(x, p) == find(y, p))return 1;
return 0;
}
*/

//long long a[1002];


int main()
{
	long long N, cnt = 0, tmp, ans = 1;
	string S;
	cin >> S;

	for (int i = 0; i < S.size(); i++) {
		if (!((S[i] >= 'a' && S[i] <= 'z') || S[i] == 'A' || S[i] == 'C')) ans = 0;
	}
	if (S[0] != 'A') ans = 0;
	for (int i = 2; i < S.size() - 1; i++) {
		if (S[i] == 'C') cnt++;
	}
	if (cnt != 1) ans = 0;

	if (ans == 0) cout << "WA" << endl;
	else cout << "AC" << endl;

	char qq;
	cin >> qq;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int S[100000],T[50000],count=0,n,q,i,j,left,mid,right,key;

  scanf("%d",&n);
  scanf("%d",&S[0]);
  for(i=1,j=1;j<n;i++){
    scanf("%d",&S[i]);
    if(S[i]==S[i-1])i--;
    j++;
  }
  n=i;
  scanf("%d",&q);
  for(i=0;i<q;i++) 
    scanf("%d",&T[i]);
   
  for(i=0;i<q;i++){
    key=T[i];
    left=0;
    right=n;
    while(left<right){
      mid=(left+right)/2;
      if(key==S[mid]){
	count++;
	break;
      }
      else if(key<S[mid])right=mid;
      else left=mid+1;
    }
  }

    printf("%d\n",count);

    return 0;
  }

Measured memory_bytes: 968
#include <iostream>

using namespace std;

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

   int rem = N % 10;

   switch(rem){
   case 2:

   case 4:

   case 5:
    case 7:


    case 9:
    cout<<"hon";
    break;

    case 0:

    case 1:

    case 6:
    case 8:
        cout<<"pon";
        break;
    case 3:
        cout<<"bon";

   }
}


Measured memory_bytes: 3604
N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

dp = [0] * N

for i in range(1, N):
    dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    for j in range(2, min(i, K) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])


Measured memory_bytes: 84300
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector <ll>
#define vii vector <int>
#define vpii vector <pii>
#define vpll vector <pll>
#define ff first
#define ss second
#define vvll vector <vll>
#define vvii vector <vii>
#define all(v) v.begin(),v.end()
#define PQ priority_queue
using namespace std;
ll mod = 1000000007;
ll pow(ll a, ll b){
	ll res = 1;
	while(b > 0){
		if(b&1) res*=a;
		b/=2;
		a*=a;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
  	int n;
  	cin >> n;
  	string arr[n];
  	for(int i = 0; i < n; i++) {
        cin >> arr[i];
    	sort(all(arr[i]));
    }
  	map <string,ll> m;
  	for(int i = 0; i < n; i++) m[arr[i]]++;
  	ll cnt = 0;
  	for(auto p: m){
    	cnt+=((p.ss)*(p.ss-1))/2;
    }
  	cout << cnt << "\n";
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include <string>
using namespace std;
#define ll long long

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ll n, m; cin >> n >> m;
	string a, b; cin >> a >> b;
	ll ai = 0, bi = 0, l = n * m / gcd(n, m);
	while (ai < n && bi < m) {
		ll al = ai * (l / n) + 1, bl = bi * (l / m) + 1;
		if (al == bl) {
			if (a[ai] != b[bi]) {
				cout << -1 << '\n';
				return 0;
			}
			ai++; bi++;
		}
		else if (al < bl)
			ai++;
		else
			bi++;
	}
	cout << l << '\n';
	return 0;
}

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

main() {
  int n; cin >> n;
  int cnt[n][26]{};
  string S[n];
  rep(i, n) {
    cin >> S[i];
    rep(j, S[i].length()) rep(k, 26) {
      if (S[i][j] != 'a' + k) continue;
      cnt[i][k]++;
      break;
    }
  }
  int ans;
  rep(i, 26) {
    rep(j, n) {
      if (j == 0) {
        ans = cnt[j][i];
      } else {
        ans = min(ans, cnt[j][i]);
      }
    }
    rep(j, ans) cout << (char)('a' + i);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define N 200005
typedef long long ll;

ll a[N];


int main(){
    ll n,i,x;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    x^=a[1];
    for(i=2;i<=n;i++){
        x^=a[i];
    }
    for(i=1;i<=n;i++){
        cout<<(x^a[i]);
        if(i!=n)
            cout<<" ";
    }
    return 0;
}


Measured memory_bytes: 5164
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

int main(void) {
  int n;
  std::cin >> n;
  std::cout << ((n + 1) >> 1) << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

using ll = long long;

int main()
{
    int h,w;
    cin >> h >> w;
    char a[52][52];
    int b[52][52];
    for(int i = 1; i <= h; ++i) for(int j = 1; j <= w; ++j){ cin >> a[i][j]; b[i][j] = 0;}

    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= w; ++j){
            if(a[i][j] == '#'){
                for(int k = -1; k <= 1; ++k){
                    for(int l = -1; l <= 1; ++l){
                        b[i+k][j+l]++;
                    }
                }
            }
        }
    }
    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= w; ++j){
            if(a[i][j] == '#') cout << '#';
            else cout << b[i][j];
        }
        cout << endl;
    }
    return 0;
}


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

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

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

    vector<int> a(m);
    int sum = 0;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        sum += a[i];
    }

    if(sum > n) {
        cout << -1 << endl;
        return 0;
    }

    cout << n - sum << endl;

}

Measured memory_bytes: 3728
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let ab: Vec<u64> = read_vec();
    let mut a: u64 = 0;
    let mut b: u64 = 0;

    // 小さい方をAで固定する
    if ab[0] > ab[1]
    {
        a = ab[1];
        b = ab[0];
    }
    else
    {
        a = ab[0];
        b = ab[1];
    }

    let sqrt_a = ((a as f64).sqrt()) as usize + 1;
    let sqrt_b = ((b as f64).sqrt()) as usize + 1;

    let mut p_factor_a: Vec<u64> = Vec::with_capacity(sqrt_a);
    let mut p_factor_b: Vec<u64> = Vec::with_capacity(sqrt_b);

    // 1を追加する
    p_factor_a.push(1);
    p_factor_b.push(1);

    // Aの試し割り
    let mut i: u64 = 2;
    let mut is_added = false;
    loop
    {
        // 割り切れるなら素因数vecに追加し、iで割った値で次の試行へ進む
        if a % i == 0 
        {
            // 既に追加した場合はpushしない
            if !is_added 
            {
                p_factor_a.push(i);
                is_added = true;
            }
            a /= i;
            continue;
        }
        // 割り切れない場合はiをインクリメントする
        i += 1;
        is_added = false;
        // iがaの平方根を切り上げた整数値を超えたら終了。現在の値を加える。
        if i > sqrt_a as u64 
        {
            if a != 1 { p_factor_a.push(a); }
            break;
        }
    }

    // Bの試し割り
    i = 2;
    loop
    {
        // 割り切れるなら素因数vecに追加し、iで割った値で次の試行へ進む
        if b % i == 0 
        {
            // 既に追加した場合はpushしない
            if !is_added 
            {
                p_factor_b.push(i);
                is_added = true;
            }
            b /= i;
            continue;
        }
        // 割り切れない場合はiをインクリメントする
        i += 1;
        is_added = false;
        // iがbの平方根を切り上げた整数値を超えたら終了。現在の値を加える。
        if i > sqrt_b as u64 
        {
            if b != 1 { p_factor_b.push(b); }
            break;
        }
    }

    //素因数配列のANDを取る
    let previous_sum_len = p_factor_a.len() + p_factor_b.len();
    p_factor_a.append(&mut p_factor_b);
    p_factor_a.sort();
    p_factor_a.dedup();

    println!("{}", previous_sum_len - p_factor_a.len());
}


Measured memory_bytes: 8444
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

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

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll N, M;
    cin >> N >> M;
    vector<ll> x(M), y(M);
    rep(i, M) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    vector<ll> cnt(N, 1);
    vector<bool> prob(N, false);
    prob[0] = true;

    rep(i, M) {
        if (prob[x[i]]) prob[y[i]] = true;
        cnt[x[i]]--;
        cnt[y[i]]++;

        if (cnt[x[i]] == 0) prob[x[i]] = false;
    }

    ll ans = 0;
    rep(i, N) {
        if (prob[i]) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;

const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T>
inline void chkmin(T&a, T b) { a = a < b ? a : b; }

const int MAXN = 200010;
const int mod = 1e9 + 7;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int&x, int y) { x = Mod(x + y); }

inline int ksm(int x, int k = mod - 2) {
	int s = 1;
	while(k) {
		if(k & 1) s = 1LL * s * x % mod;
		x = 1LL * x * x % mod, k >>= 1;
	} return s;
}

int fac[8010];
int ifac[8010];
int f[4010][4010];
int X[MAXN];
int Y[MAXN];

int main() {
#ifdef LOCAL
	FILE("");
#endif
	int n = ri;
	int res = 0, t = 2001;

	fac[0] = ifac[0] = 1;
	for(int i = 1; i <= 8000; i++)
		ifac[i] = ksm(fac[i] = 1LL * fac[i - 1] * i % mod);

	for(register int i = 1; i <= n; i++) {
		int x = X[i] = ri, y = Y[i] = ri, s = x + y;
		res = (res + 1LL * fac[s << 1] * ifac[y << 1] % mod * ifac[x << 1]) % mod;
		f[t - x][t - y]++;
	}

	for(register int i = 1; i <= 4001; i++)
		for(register int j = 1; j <= 4001; j++)
			f[i][j] = Mod(Mod(f[i][j] + f[i - 1][j]) + f[i][j - 1]);

	res = Mod(mod - res);
	for(register int i = 1; i <= n; i++) Add(res, f[t + X[i]][t + Y[i]]);
	res = 500000004LL * res % mod;
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 64768
#include <stdio.h>
#include <stdlib.h>
int cmpint(const void *x, const void *y) { return *(int *)y - *(int *)x; }
int main() {
	int n, k, numA[200000] = {0}, a, cnt = 0, ans = 0;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		numA[a]++;
	}

	qsort(numA, n + 1, sizeof(int), cmpint);
	for (int i = 0; i <= n; i++) {
		if (numA[i] != 0) {
			cnt++;
		}
		if (k < cnt) {
			ans += numA[i];
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1660
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

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

template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

int main() {
	ll n, k;
	cin >> n >> k;
	V<int> va(n);
	rep(i, n)
		cin >> va[i];
	V<int> vacnt(n, 0);
	int cur = 0;
	ll loopcnt = 0;
	while (1) {
		++vacnt[cur];
		//cout << "machi" << cur << endl;
		cur = va[cur]-1;
		++loopcnt;
		if (vacnt[cur] >= 1) {
			break;
		}
		if (loopcnt == k) {
			cout << cur+1 << endl;
			return 0;
		}
	}
	//cout << loopcnt << endl;
	ll start = loopcnt;
	ll startID = cur;
	//cout << "startID" << startID<<endl;
	while (1) {
		++vacnt[cur];
		//cout << "machi" << cur << endl;
		cur = va[cur] - 1;
		++loopcnt;
		if (vacnt[cur] >= 2) {
			break;
		}
		if (loopcnt == k) {
			cout << cur + 1 << endl;
			return 0;
		}
	}
	ll end = loopcnt;
	//cout << "loopnum"<<end - start << endl;
	ll kmod = (k-start) % (end - start);
	//cout << "mod"<<kmod << endl;
	rep (i, kmod) {
		++vacnt[cur];
		//cout << "machi" << cur << endl;
		cur = va[cur] - 1;
		++loopcnt;
	}
	cout << cur + 1 << endl;
	return 0;
}

Measured memory_bytes: 4844
#include <iostream>
#define int64 long long
using namespace std;
int main()
{
	int64 nn, mm;
	cin >> nn >> mm;
	nn = nn * (nn - 1) / 2;
	mm = mm * (mm - 1) / 2;
	cout << nn + mm << endl;
	return 0;
}


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

vector<long long>  dis;
int main() {
    long long s = 0;
    int n,m,a,i;
    cin>>n>>m;

    for(i=0;i<n;i++){
        cin>>a;
        s += a;
        while(a>0){
            dis.push_back(a-a/2);
            a /= 2;
        }
    }

    sort(dis.rbegin(),dis.rend());

    for(i=0;i<m && i<dis.size();i++) s -= dis[i];

    cout<<s;

    return 0;
}

Measured memory_bytes: 35044
#ifndef Local
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  Long r, g, b, n;
  cin >> r >> g >> b >> n;

  Long res = 0;

  for (Long i = 0; i <= n; ++i) {
    for (Long j = 0; j <= n; ++j) {
      Long rem = n - i * r - j * g;
      res += (rem >= 0 && rem % b == 0);
    }
  }

  cout << res;

}


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

int main(){
    string s; cin >> s;
    int n = s.size();
    rep(i,n){
        if((i%2 == 0 && s[i] == 'L') || (i%2 == 1 && s[i] == 'R')){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

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

int main()
{
	int N,Y ;
	cin >> N >> Y;
	bool bFound = false ;

	for(int i=0; i<=N; i++){
		for(int j=0; j<=N; j++){
			int k = N-(i+j);
			if( k >= 0 && 10000*i+5000*j+1000*k == Y){
				printf("%d %d %d\n",i,j,k) ;
				return 0;
			}
		}
	}
	printf("-1 -1 -1");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define db long double
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
#define Nmax 1000005
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
 
using namespace std;

db dp[3001][3001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tests=1,t=1;
    // cin>>tests;
    while(tests--)
    {	
    	ll i,j,n;
    	cin>>n;
    	vector<db>p(n+1);
    	rep(i,1,n) cin>>p[i];
    	memset(dp,0,sizeof(dp));
    	// i tosses j heads
    	dp[0][0]=1;
    	rep(i,1,n) dp[i][0]=dp[i-1][0]*(1-p[i]);
    	rep(i,1,n)
    	{
    		rep(j,1,n)
    		{
    			dp[i][j]+=dp[i-1][j-1]*(p[i]);
    			dp[i][j]+=dp[i-1][j]*(1-p[i]);
    		}
    	}
    	db ans=0.0;
    	rep(i,n,n)
    	{
    		rep(j,n/2 +1,n) ans+=dp[i][j];
    	}
    	cout<<setprecision(12)<<ans;

    }
    	return 0;
    
}

Measured memory_bytes: 144496
n = int(input())
ans = []
for i in range(1, n+1):
    if i%3 == 0:
        ans.append(str(i))
        continue
    x = i
    while x:
        if x%10 == 3:
            ans.append(str(i))
            break
        x //= 10
print(" " + " ".join(ans))


Measured memory_bytes: 5932
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define maxn 3000006
#define mod 1000000007
#include <bits/stdc++.h>
using namespace std;


vector<int> a, b, v;
int p, q, cnt;

bool same(vector<int> s1, vector<int> s2){
    for(int i=0;i<s1.size();i++){
        if(s1[i] != s2[i]) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        v.pb(i+1);
    }

    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        a.pb(x);
    }

    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        b.pb(x);
    }

    do{
        cnt++;
        if(same(v, a)) p = cnt;
        if(same(v, b)) q = cnt;
    }while(next_permutation(v.begin(), v.end()));

    cout << abs(p-q) << endl;

    return 0;
}


Measured memory_bytes: 256
import java.math.BigDecimal;
import java.util.*;

public class Main {

    private static Scanner sc = new Scanner(System.in);

    private static final BigDecimal mod = new BigDecimal(1000000007);

    public static void main(String[] args) {

        int n = sc.nextInt();
        int m = sc.nextInt();

        PrimeFact p = new PrimeFact(m);

        System.out.println(ans(p, n));
    }

    private static long ans(PrimeFact p, int n) {
        BigDecimal ret = new BigDecimal(1);
        for (Map.Entry<Long, Integer> e : p.factorization.entrySet()) {
            ret = ret.multiply(
                    combination(n + e.getValue() - 1, e.getValue())
            );

            ret = ret.remainder(mod);
        }
        return ret.longValue();
    }

    public static BigDecimal combination(int a, int b) {
        BigDecimal ret = new BigDecimal(1);
        for (int i=a; i > a-b; i--) {
            ret = ret.multiply(new BigDecimal(i));
        }
        for (int i=1; i <= b; i++) {
            ret = ret.divide(new BigDecimal(i));
        }
        return ret;
    }

    public static class PrimeFact {
        private final Long orig;
        private LinkedHashMap<Long, Integer> factorization;

        public PrimeFact(long num) {
            orig = num;
            factorization = factorize(num);
        }

        public PrimeFact(int num) {
            orig = (long) num;
            factorization = factorize(num);
        }
    }

    private static LinkedHashMap<Long, Integer> factorize(long num) {

        LinkedHashMap<Long, Integer> fact;

        if (num == 1L) return new LinkedHashMap<>();

        long sqrt = (long) Math.floor(Math.sqrt(num));

        for (long p : getPrimes(sqrt)) {
            if (num % p == 0) {
                fact = factorize(num/p);
                if (fact.containsKey(p)) fact.put(p, fact.get(p) + 1);
                else fact.put(p, 1);
                return fact;
            }
        }

        fact = new LinkedHashMap<>();
        fact.put(num, 1);
        return fact;
    }

    private static LinkedList<Long> primes;

    static {
        primes = new LinkedList<>();
        primes.add(2L);
    }

    public static List<Long> getPrimes(long min) {

        if (primes.getLast() < min)
            genPrime(min);

        int index = 0;
        for (long p : primes) {
            if (p > min) break;
            index++;
        }

        return primes.subList(0, index);
    }

    private static void genPrime(long min) {
        for (long biggestKnown = primes.getLast() + 1; biggestKnown <= min; biggestKnown++) {
            if (isPrime(biggestKnown)) primes.add(biggestKnown);
        }
    }

    private static boolean isPrime(long num) {
        int sqrt = (int) Math.floor(Math.sqrt(num));

        for (long p : primes) {
            if (p > sqrt) break;
            if (num % p == 0) return false;
        }

        return true;
    }

}


Measured memory_bytes: 24628
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main(){
  int N;
  scanf("%d", &N);
  string head;
  if(N<=999) printf("ABC\n");
  else printf("ABD\n");
  return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::stack;
using std::priority_queue;
using std::pair;
using std::make_pair;

using std::min;
using std::max;
using std::sort;
using std::abs;

using std::fixed;
using std::setprecision;
using std::setw;

using ll = long long int;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 373;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> init_vector2(size_t n0, size_t n1, T e = T()) {
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> init_vector3(size_t n0, size_t n1, size_t n2, T e = T()) {
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    vector<ll> a(k);
    for (ll i = 0; i < k; i++) {
        cin >> a[i];
    }

    // [s, t)
    ll s = 2;
    ll t = 3;
    for (ll i = k - 1; i >= 0; i--) {
        const ll m = (t - 1) / a[i] - (s - 1) / a[i];
        if (m == 0) {
            cout << -1 << endl;
            return 0;
        }

        ll ss = -1;
        if (s % a[i] == 0) {
            ss = s;
        } else {
            ss = s + (a[i] - s % a[i]);
        }

        ll tt = ss + a[i] * m;

        // cout << a[i] << " " << ss << " " << tt << endl;
        s = ss;
        t = tt;
    }

    cout << s << " " << t - 1 << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int i,j,a,b,c,n,m,k,l;
int main(){
  for(cin>>a>>b,i=a;i<=b;i++){
    if(i==0)return cout<<"Zero",0;
    if(i<0)c++;
  }
  cout<<(c&1?"Negative":"Positive");
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int l;
    int sum = 0, cnt = 1;
    for(int i=0; i<n; i++) {
        cin >> l;
        sum += l;
        if(x<sum) {
            cout << cnt << endl;
            return 0;
        }
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define INFLL 0x3fffffffffffffffLL
#define INF 0x3fffffff
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
/////////////////// DEBUG MODE ///////////////////////////////////
#define D(x) cerr<<"\nDEBUG: "<<#x<<" is: "<<x<<'\n'
#define error(args...) {string _s=#args; replace(all(_s),',',' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
/////////////////// GLOBAL VARIABLES /////////////////////////////
vector<vector<int>> adj; vector<bool> vis; vector<int> color;
bool pos=true;
#define red 1
#define blue 2
/////////////////// FUNCTIONS ////////////////////////////////////
template<class T>
T maxx(T a, T b) {return a>b?a:b;}
template<typename T, typename... Args>
T maxx(T a, T b, Args... args){return maxx(a>b?a:b, args...);}
ll mexp(ll x, ll n, ll m){
  ll res=1;  while(n){if(n&1) res=(res*x)%m;n>>=1; x=((x%m)*(x%m))%m;}
  return res;
}
double pow(double a, int n) {
  if(n == 0) return 1;if(n == 1) return a;
  double t = pow(a, n/2);return t * t * pow(a, n%2);
}
void DFS(ll u){
	vis[u]=true;
	for(auto v: adj[u]){
		if(vis[v]){
			if(color[v]==color[u]) pos=false;
		}
		else{
			if(color[u]==red) color[v]=blue; else color[v]=red;
			DFS(v);
		}
	}
}
/////////////////// MAIN STARTS //////////////////////////////////
int main(){
  ios::sync_with_stdio(0);  cin.tie(0);   cout<<fixed; cerr<<fixed;
  cout<<setprecision(3); cerr<<setprecision(3);
  #ifdef DEBUG
  freopen("ip.txt","r",stdin); //freopen("op.txt","w",stdout);
  clock_t tStart = clock();
  #endif

	ll x,y; cin>>x>>y;
	cout<<1LL+(ll)floor(log2((ld)y/x))<<'\n';

	#ifdef DEBUG
	cerr<<"\nExecution time: "<<(((double)clock() - tStart)/CLOCKS_PER_SEC)*1000<<"ms.\n";
	#endif
  return 0;
}


Measured memory_bytes: 384
list = gets.chomp.split(' ')
k = list[0].to_i
s = list[1].to_i


count = 0
for l in 0..k do
    x = l
  	if x > s then
      break
    end
 
	for m in 0..k do
  		y = m
    	subsum = x + y
    	z = s - subsum
    	if subsum > s then
      		break
    	end
    	if z >= 0 && z <= k then
      		count += 1
    	end
  	end
end
p count

Measured memory_bytes: 3836
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Console.WriteLine(A.Max() - A.Min());
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t

// dp digit
// SUM=a+b, XOR=a^b
// SUM=((a&b)<<1)+XOR
//    =AND*2+XOR
//    =OR+AND (AND+XOR=OR)

const ll mod=1e9+7;
ll n,dp[65][2][2];

ll dfs(int i,int carry,bool ok){
	if(i==60) return carry==0&&ok;
	ll& res=dp[i][carry][ok];
	if(~res) return res;
	res=0;
	ll curbit=n>>i&1ll;
	for(int a=0;a<2;++a)
		for(int b=0;b<=a;++b){
			int bit=(a+b+carry)&1;
			bool isOk=ok;
			if(bit>curbit) isOk=false;
			if(bit<curbit) isOk=true;
			(res+=dfs(i+1,(a+b+carry)/2,isOk))%=mod;
		}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	memset(dp,-1,sizeof dp);
	cout<<dfs(0,0,true)<<'\n';
}



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

int main(){
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  double pi = 3.14159265358979;
  double x1 = a * cos((h+m/60.0)*30.0*pi/180.0);
  double y1 = a * sin((h+m/60.0)*30.0*pi/180.0);
  double x2 = b * cos(m*6.0*pi/180.0);
  double y2 = b * sin(m*6.0*pi/180.0);
  double d = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  printf("%.12lf\n",d);
  return 0;
}


Measured memory_bytes: 4160
#include <bits/stdc++.h>
#define int long long
#define gcd            __gcd
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x,y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;

int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
int modi(int a, int m)
{
    return power(a, m - 2, m);
}
int32_t main()
{
    nitin;
    int cnt=0;
    w(n){
        int a;
        cin>>a;
        if(a&1)
            cnt++;
    }
    if(cnt%2==0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 3620
/******************************************
* AHAM BRAHMASHMI ;) *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second


void solve()
{
	ll n;
	cin >> n;
	vll arr(n);
	map<ll, ll> mp;
	for (ll i = 0; i < n; i++)
	{
		cin >> arr[i];
		mp[arr[i]] = 0;
	}
	ll sum = 0;
	for (ll i = 0; i < n; i++)
	{
		sum += arr[i];
		mp[arr[i]]++;
	}
	ll q;
	cin >> q;
	ll b, c;
	while (q--)
	{
		cin >> b >> c;
		ll new_sum;
		if (mp.find(b) != mp.end())
		{
			new_sum = sum - mp[b] * (b - c);
			cout << new_sum << "\n";
			if (mp.find(c) == mp.end())
				mp[c] = mp[b];
			else
				mp[c] += mp[b];
			mp[b] = 0;
			sum = new_sum;
		}
		else
		{
			cout << sum << "\n";
		}
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	// ll t;
	// cin >> t;
	// while (t--)
	// {
	solve();
	// }

	return 0;
}

Measured memory_bytes: 9176