akhauriyash/Code-Regression huggingface dataset:
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ull unsigned long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); 
#define nl "\n"
#define sz(a) (int)(a).size() 
#define all(a) (a).begin(),(a).end()
#define fl(a,x) memset(a,x,sizeof(a));
#define pt(a,x) cout << get<x>(a) << " " ;  
#define mt make_tuple 
#define vec vector
 
#define int long long 
 
const int mod = (int) 1e9 + 7 ;
const int MOD = (int) 998244353 ;
const int INF = (int) 1e18 ;
 
typedef vector<int> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
typedef vector<vector<int> > vv;
 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); 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...);
}

const int N = 1e5 + 5;
int a[3][N], dp[3][N];

void solve(int test) {
	int n; cin >> n ;

	rep(i,0,n) cin >> a[0][i] >> a[1][i] >> a[2][i] ;
	dp[0][0] = a[0][0] , dp[1][0] = a[1][0] , dp[2][0] = a[2][0];

	rep(i,1,n) {
		dp[0][i] = a[0][i] + max(dp[1][i-1],dp[2][i-1]);
		dp[1][i] = a[1][i] + max(dp[0][i-1],dp[2][i-1]);
		dp[2][i] = a[2][i] + max(dp[0][i-1],dp[1][i-1]);
	}

	cout << max({dp[0][n-1],dp[1][n-1],dp[2][n-1]}) ;
}
 
int32_t main() {
 

    fast;
	int t=1;
	// cin>>t;
	rep(i,1,t+1) {
		solve(i) ;
	}
 
	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

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

//ユークリッドの互除法
ll gcd(ll x,ll y){
    if(x>y)swap(x,y);
    if(y%x==0)return x;
    return gcd(x,y%x);
};

//最小公倍数
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
};

int main(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll cntb=b-b/c-b/d+b/lcm(c,d);
    ll cnta= a-1-(a-1)/c-(a-1)/d+(a-1)/lcm(c,d);
    cout << cntb-cnta <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

const int N = 1000;
int a[N];

int main() {
	::ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, K;
	cin >> n >> K;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector <long long> sums;
	sums.reserve(n * (n + 1) / 2);
	for (int l = 0; l < n; ++l) {
		long long sum = 0;
		for (int r = l; r < n; ++r) {
			sum += a[r];
			sums.push_back(sum);
		}
	}
	long long answer = 0;
	for (int i = 60; i >= 0; --i) {
		vector <long long> filtered;
		long long bit = (1LL << i);
		for (auto x : sums) {
			if ((x & bit) != 0)
				filtered.push_back(x);
		}
		if (filtered.size() >= K) {
			answer |= bit;
			filtered.swap(sums);
		}
	}
	cout << answer << endl;

	return 0;
}


Measured memory_bytes: 5368
import java.util.Random;
import java.util.Scanner;

public class Main {
	private static final int K = 26;
	private static Random rand = new Random(System.currentTimeMillis());

	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var d = sc.nextInt();
		var c = new int[K];
		var s = new int[d][K];
		for (var i = 0; i < K; i++) {
			c[i] = sc.nextInt();
		}
		for (var i = 0; i < d; i++) {
			for (var j = 0; j < K; j++) {
				s[i][j] = sc.nextInt();
			}
		}
		sc.close();

		var t = create(c, s, d);
		var max = score(c, s, t, d);
		for (var i = 0; i < 1000; i++) {
			for (var j = 1; j < 200; j++) {
				var index = i % d;
				var t2 = new int[d];
				for (var k = 0; k < d; k++) {
					t2[k] = t[k];
				}
				t2[index] = (t2[index] + j) % K + 1;
				var sum = score(c, s, t2, d);
				//System.out.println(sum);
				if (max < sum) {
					t = t2;
					max = sum;
				}
			}
		}

		for (var i = 0; i < d; i++) {
			System.out.println(t[i]);
		}
	}

	private static int score(int[] c, int[][] s, int[] t, int d) {
		var sum = 0;
		var last = new int[K];
		for (var i = 0; i < d; i++) {
			var ti = t[i] - 1;
			sum += s[i][ti];
			last[ti] = i + 1;
			for (var j = 0; j < K; j++) {
				sum -= ((i + 1) - last[j]) * c[j];
			}
		}

		return sum;
	}

	private static int[] create(int[] c, int[][] s, int d) {
		var t = new int[d];
		var last = new int[K];
		for (var i = 0; i < d; i++) {
			var v = new int[K];
			for (var j = 0; j < K; j++) {
				v[j] = s[i][j] + (((i + 1) - last[j]) * c[j]);
			}
			t[i] = rand(v) + 1;
			last[t[i] - 1] = i + 1;
		}
		return t;
	}

	private static int rand(int[] v) {
		var sum = 0;
		for (var i = 0; i < v.length; i++) {
			sum += v[i];
		}
		var value = rand.nextInt(sum);
		var index = 0;
		sum = 0;
		for (var i = 0; i < v.length; i++) {
			sum += v[i];
			if (value < sum) {
				break;
			}
			index++;
		}
		//System.out.printf("%d %d %d\r\n", value, sum, index);
		return index;
	}
}


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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vll = V<ll>;
using VVll = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

const ll MOD = 1e9+7;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int n;
    cin >> n;
    Vi l(n);
    REP(i, n) {
        cin >> l[i];
    }

    sort(ALL(l));

    ll cnt = 0;
    REP(i, n-2) REP2(j, i+1, n-1) {
        auto iter = upper_bound(ALL(l), l[i]+l[j]-1);
        cnt += (iter - l.begin()) - (j + 1);
    }

    std::cout << cnt << '\n';

    return 0;
}


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

void trace(int A[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( i > 0 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int count = 0;

void doMS(int A[], int head, int len)
{
    if (len < 2)
        return;
    int toplen = len / 2;
    int botlen = len - toplen;
    int tophead = head;
    int bothead = tophead + toplen;
    doMS(A, tophead, toplen);
    doMS(A, bothead, botlen);
    // merge top and bottom
    int res[len];
    int i = tophead;
    int j = bothead;
    int res_i = 0;
    while (i < tophead + toplen || j < bothead + botlen)
    {
        if (i >= tophead + toplen)
        {
            memcpy(res + res_i, A + j, sizeof(int) * (bothead + botlen - j));
            count += bothead + botlen - j;
            break;
        }
        if (j >= bothead + botlen)
        {
            memcpy(res + res_i, A + i, sizeof(int) * (tophead + toplen - i));
            count += tophead + toplen - i;
            break;
        }
        res[res_i++] = A[i] > A[j] ? A[j++] : A[i++];
        count++;
    }
    memcpy(A + head, res, sizeof(int) * len);
}

void heapify(int *A, int root, int end)
{
    int i = root;
    int temp = 0;
    while(i * 2 + 1 <= end)
    {
        int c = i * 2 + 1;
        if (c + 1 <= end && A[c + 1] > A[c])
            c++;
        if(A[c] > A[i])
        {
            temp = A[i];
            A[i] = A[c];
            A[c] = temp;
        }
        else
            break;
        i = c;
    }
}


void doHS(int *A, int n)
{
    for(int i = n / 2; i >= 0; i--)
    {
        heapify(A, i, n - 1);
    }
    
    for(int i = n - 1; i > 0 ; i--)
    {
        int temp = A[i];
        A[i] = A[0];
        A[0] = temp;
        heapify(A, 0, i - 1);
    }
}


int main(){
    int n, i, j, key, temp;
    int *A, *B;
    //extern count;
    scanf("%d", &n);
    A = malloc(sizeof(int) * n);
    B = malloc(sizeof(int) * n);

    for ( i = 0; i < n; i++ ) scanf("%d", &A[i]);
    memcpy(B, A, sizeof(int) * n);
    
    doMS(A, 0, n);
    
    doHS(B, n);
    trace(B, n);
    printf("%d\n", count);

    return 0;
}




/* 
8 5 9 2 6 3 7 1 10 4
*/

Measured memory_bytes: 7584
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

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

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

int main() {
    int N;
    cin >> N;
    vector<vector<int>> table(11, vector<int>(11, 0));
    string NUM;
    rep(i, 1, N + 1) {
        NUM = to_string(i);
        table.at(NUM[0] - '0').at(NUM.back() - '0')++;
    }

    int total = 0;
    rep(i, 10) rep(j, 10) total += table[i][j] * table[j][i];
    cout << total << endl;
}


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

void solve()
{
	int n;
	cin >> n;
	int sum = 100000;
	for(int i = 0; i < n; ++i)
	{
		sum *= 1.05;
		int remainder = sum % 1000;
		if(remainder)
		{
			sum = sum - remainder + 1000;
		}
	}
	cout << sum << endl;
}

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

Measured memory_bytes: 1160
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
const ll mod = 1e9 + 7;

ll N,K,ans;

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

	FOR(i,1,N+1) {
		if (i * 2 % K != 0)continue;
		ll mod = 0;
		if(i%K!=0)mod = K-i % K;
		ll cur = (N + mod) / K;
		ans += cur * cur;
	}



	ct(ans);
	return 0;
}

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

int main(){
  string str;
  string S[100];
  int n, abc[100][100] = {}, temp;
  cin>>n;

  for(int i = 0; i < n; i++){
       cin>>S[i];
        int s = S[i].size();
       // sort(S[i].begin(), S[i].end());
       // cout<<S[i]<<endl;
       for(int j = 0; j < s; j++){
	 temp = S[i][j] - 'a';//cout<<temp<<endl;
	 abc[i][temp]++; 
       }
  }
  for(int j = 0; j < 26; j++){
    int mi = 10000000;
    for(int i = 0; i < n; i++){
      mi = min(mi, abc[i][j]);
    }
    for(int i = 0; i < mi; i++){
      cout<<(char)('a'+j);
    }
  }
  
  cout<<endl;
  return 0;
}


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

int main(){
    int N;
    cin >> N;
    if(N%2==1){
        cout << N/2+1 << endl;
    }else{
        cout << N/2 << endl;
    }
    return 0;
}

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

typedef long long LL;
using namespace std;

const int cnt = 10;
int num[cnt];
vector<int> a, b;

bool DFS(int i)
{
	if (i == 10) return true;
	if (num[i] > a.back()) {
		// cout << i << " sum1 " << num[i] << endl;
		a.push_back(num[i]); if (DFS(i + 1)) return true; a.pop_back();
	}
	if (num[i] > b.back()) {
		// cout << i << " sum2 " << num[i] << endl;
		b.push_back(num[i]); if (DFS(i + 1)) return true; b.pop_back();
	}
	return false;
}


int main()
{
	int T;
	scanf("%d", &T);
	while(T--) {
		for (int i = 0; i < cnt; i++) scanf("%d", &num[i]);
		a.clear(); b.clear(); b.push_back(num[0]); a.push_back(0);
		if (DFS(1)) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define ALL(x) (x).begin(),(x).end()
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
using P=pair<int,int>;

signed _main(){
  int N,Y; cin >> N >> Y;
  for(int i=0;i<=2000;i++){
    for(int j=0;j<=2000;j++){
      if(i+j>N) continue;
      int k=N-i-j;
      if(10000*i+5000*j+1000*k==Y){
        cout << i << " " << j << " " << k << endl;
        return 0;
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << endl;
  return 0;
}


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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testcase=1;
    //cin>>testcase;
    for(int p=0;p<testcase;p++){
    ll n=0;
    cin>>n;
    int array[n]={0};
    for(int i=0;i<n;i++){
        cin>>array[i];
    }
    sort(array,array+n,greater<ll>());
    ll sum=0,sum1=0;
    for(int i=0;i<n;i+=2){
        sum1+=array[i];
    }
    for(int i=0;i+1<n;i+=2){
        sum+=array[i+1];
    }
    cout<<sum1-sum;

    }

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        mut h: u64
    };

    let mut c = 1_u64;
    let mut res = 0_u64;
    while h > 0 {
        res += c;
        c *= 2;
        h /= 2;
    }
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


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

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

int main()
{
  int N;
  cin >> N;
  int A[N];
  int min = INT_MAX;
  int flag = 0;
  for(int i=0;i<N;i++){
    cin >> A[i];
    if(A[i]<min){
      min = A[i];
    }
  }
  int result;
  sort(A,A+N);

  int tmp = 0;
  for(int i=0;i<N;i++){
    if(i==0){
      tmp = gcd(A[i],A[i+1]);
    }else if(i<N-1){
      tmp = gcd(tmp,A[i+1]);
    }
  }
  cout << tmp <<endl;
}

Measured memory_bytes: 4032
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{input, fastout};
use proconio::marker::{Chars, Bytes, Usize1};

#[fastout]
fn main() {
    input!{
        n:String
    }
    let mut res = 0;
    for x in n.chars() {
        res += x.to_digit(10).unwrap_or(0);
        res %= 9;
    }
    println!("{}", if res > 0 { "No" } else { "Yes" });
}


Measured memory_bytes: 2416
five_powers = []
x = 0
while x < 10 ** 3:
    five_powers.append(x)
    x += 1
x = int(input())
n = len(five_powers)
flag = False
for i in range(n):
    for j in range(n):
        a = five_powers[i]
        b = five_powers[j]
        if a ** 5 - b ** 5 == x:
            print('{} {}'.format(a, b))
            flag = True
            break
        if a ** 5 + b ** 5 == x:
            print('{} {}'.format(a, -1 * b))
            flag = True
            break
    if flag: break

Measured memory_bytes: 9244
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    for i in range(N):
        if A[i] % 2 == 1:
            count +=1 
    if count % 2 == 0:
        print('YES')
    else:
        print('NO')

if __name__ == "__main__":
    main()


Measured memory_bytes: 20472
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n;
    unsigned long long result = 1;
    bool over = false;
    cin >> n;
    for (int i=0;i<n;i++) {
        unsigned long long a;
        cin >> a;
        if (a == 0) {
            cout << 0 << endl;
            return 0;
        }
        if (1000000000000000000 / a < result) {
            over = true;
            continue;
        }
        result *= a;
    }
    if (over) {
        cout << -1 << endl;
        return 0;
    }
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<list>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<limits>
#include<cctype>
#include<fstream>
#include<unordered_map>
#include<complex>
#pragma warning(disable:4996)
using namespace std;

#define debug(i) cout<<"<debug> "<<#i<<" "<<i<<" <\\debug>"<<endl
#define mfor(i,a,b) for(int i=(a);i<=(b);i++)
#define mrep(i,a,b) for(int i=(a);i>=(b);i--)
#define lll __int128
#define Re register
#define mem(a,b) memset(a,(b),sizeof(a))
#define Design ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
typedef pair<ll, ll> llpair;
typedef long double ld;
const double pi = acos(-1);
const double eps = 1e-5;
const int INF = 0x3f3f3f3f;
const long long int INFLL = 0x3f3f3f3f3f3f3f3f;

int fa[100010];

int find(int x)
{
	//debug(fa[x] << " " << x);
	if (fa[x] == x) return x;
	fa[x] = find(fa[x]);
	return fa[x];
}

int main()
{
	Design;
	int n, m;
	cin >> n >> m;
	mfor(i, 1, n) fa[i] = i;
	mfor(i, 1, m)
	{
		int a, b;
		cin >> a >> b;
		if (find(a) != find(b))
		{
			fa[find(a)] = find(b);
		}
	}
	int cnt = 0;
	mfor(i, 1, n) if (fa[i] == i) cnt++;
	cout << cnt - 1 << endl;
}

Measured memory_bytes: 3584
s = input()
word = ['dream', 'dreamer', 'erase', 'eraser']

flag = True
while(len(s) > 0):
  if s[-7:] == word[1]:
    s = s[:-7]
  elif s[-6:] == word[3]:
    s = s[:-6]
  elif s[-5:] == word[0] or s[-5:] == word[2]:
    s = s[:-5]
  else:
    flag = False
    break
  
if flag:
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3188
#include <iostream>      // cout, endl, cin
	#include <string>        // string, to_string, stoi
	#include <vector>        // vector
	#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
	#include <utility>       // pair, make_pair
	#include <tuple>         // tuple, make_tuple
	#include <cstdint>       // int64_t, int*_t
	#include <cstdio>        // printf
	#include <map>           // map
	#include <queue>         // queue, priority_queue
	#include <set>           // set
	#include <stack>         // stack
	#include <deque>         // deque
	#include <unordered_map> // unordered_map
	#include <unordered_set> // unordered_set
	#include <bitset>        // bitset
	#include <cctype>        // isupper, islower, isdigit, toupper, tolower
	#include <memory>        // unique_ptr, shared_ptr, weak_ptr
	#include <cstring>
	#include <cmath>

	using namespace std;

	using ll = long long int;
	using vi = vector<int>;
	using vvi = vector<vi>;

	#define _LIBCPP_DEBUG 0
	#define rep(i, n) for(int i = 0; i < (int)(n); i++)
	#define all(v) v.begin(), v.end()

	int main() {
		int x, y; cin >> x >> y;
		if (x == 2 || y == 2) cout << "No" << endl;
		else if ((x == 4 || x == 6 || x == 9 || x == 11) && (y == 4 || y == 6 || y == 9 || y == 11)) cout << "Yes" << endl;
		else if ((x != 4 && x != 6 && x != 9 && x != 11) && (y != 4 && y != 6 && y != 9 && y != 11)) cout << "Yes" << endl;
		else cout << "No" << endl;

		return 0;
	}


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

int lastA, firstB;
int AB;
int main() {
  int n;
  int ans = 0;
  cin >> n;
  for(int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for(int j = 0; j < s.size(); j++) {
      if(s[j] == 'A') {
	if(j+1 < s.size() && s[j+1] == 'B') ans++;
      }
    }
    if(s[s.size() - 1] == 'A' && s[0] == 'B') AB++;
       
       else if(s[s.size() - 1] == 'A') lastA++;
       else if(s[0] == 'B') firstB++;
  }
  int tmp;
  if(AB > 0) {
  tmp = AB - 1;
  if(lastA > 0) tmp++, lastA--;
  if(firstB > 0) tmp++, firstB--;
  }
  else tmp = 0;
  cout << tmp + ans + min(firstB, lastA) << endl;
  return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
ll INF = 1e18;

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

int main() {
  //
  ll s;
  cin >> s;
  ll d = s / (ll)(1e9);
  ll r = s % (ll)(1e9);
  ll a, b;
  if (r == 0) {
    a = 0;
    b = d;
  } else {
    a = (ll)(1e9) - r;
    b = d + 1;
  }
  cout << 0 << " " << 0 << " " << (ll)1e9 << " " << 1 << " " << a << " " << b
       << endl;
  return 0;
}


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

#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int k;
    cin >> k;

    rep(i, k) {
        if (a >= b) b *= 2;
        else c *= 2;
    }

    if (a < b and b < c) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		int n = sc.nextInt();
		int[] nums = inpNum(n);
		int num_prime = judgePrime(nums);
		System.out.println(num_prime);

		sc.close();
	}

	private static int judgePrime(int[] nums) {
		int num_prime = 0;
		boolean isPrime = true;

		for(int i = 0; i < nums.length; i++) {

			int sqrt = (int)Math.sqrt(nums[i]);
			isPrime = true;

				for (int j = 2; j <= sqrt ;j++) {
					if (nums[i] % j == 0) {
						isPrime = false;
						break;
					}
				}

			if (isPrime == true) {
				num_prime++;
			}

		}



		return num_prime;
	}

	private static int[] inpNum(int n) {
		int[] nums = new int[n];

		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}
		return nums;
	}

}


Measured memory_bytes: 42012
def main():
    k, a, b = map(int, input().split())
    x = k+1
    y = 0
    if b > a:
        c = b-a
        k -= a-1
        y = c*(k//2-1) + b + (k%2)
    print(max(x, y))

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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













int main(){
    ll n;
    cin >> n;
    double s = 0;
    REP(i, n){
        double a;
        cin >> a;
        s += 1.0 / a;
    }
    printf("%.8lf\n", 1.0 / s);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	double s,ans=0;
	char c[5];
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %s",&s,c);
		if(c[0]=='J')
			ans+=s;
		else
			ans+=s*380000;
	}
	printf("%.5lf",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define MOD 1000000007
#define MOD2 1000000006
#define TEMPMOD1 998244353
#define TEMPMOD2 998244352
#define INF 1000000000000000001
#define NEGINF -1000000000000000007
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define plll pair<pll,ll>
#define vplll vector<plll>
#define vpll vector<pll>
using namespace std;
using namespace std::chrono; 
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);


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

    ll n;
    cin>>n;
    vll length(n);
    for(ll i=0;i<n;i++)
    {
        cin>>length[i];
    }
    sort(length.begin(),length.end());
    vector<ll>::iterator it1,it2;
    ll ans=0,store;
    ll sum,diff;
    for(ll i=0;i<n;i++)
    {
        for(ll j=i+1;j<n;j++)
        {
            diff=length[j]-length[i];
            sum=length[j]+length[i];
            it2=lower_bound(length.begin(),length.end(),sum);
            it2--;
            it1=upper_bound(length.begin(),length.end(),diff);
            store=(it2-length.begin());
          	store-=(it1-length.begin());
            if(length[i]+length[i]>length[j])
            {
                store--;
            }
            store=max(store,0LL);
          	ans+=store;
        }
    }
    ans/=3;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int val[15][15];
int use[15];
char str[15][30];
int len[15];
int dp[1<<14][15];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%s",str[i]);
		for(int i=0;i<a;i++)use[i]=1;
		for(int i=0;i<a;i++)len[i]=strlen(str[i]);
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)val[i][j]=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i==j)continue;
				if(len[i]<len[j]){
					for(int k=0;k<=len[j]-len[i];k++){
						bool ok=true;
						for(int l=0;l<len[i];l++)if(str[i][l]!=str[j][k+l])ok=false;
						if(ok)use[i]=0;
					}
				}
				for(int k=1;k<min(len[i],len[j]);k++){
					bool ok=true;
					for(int l=0;l<k;l++){
						if(str[i][len[i]-k+l]!=str[j][l])ok=false;
					}
					if(ok)val[i][j]=k;
				}
			}
		}
		for(int i=0;i<(1<<a);i++)for(int j=0;j<a;j++)dp[i][j]=999999999;
		for(int i=0;i<a;i++)if(use[i])dp[1<<i][i]=len[i];
		for(int i=0;i<(1<<a);i++){
			for(int j=0;j<a;j++){
				if(dp[i][j]>99999999)continue;
				for(int k=0;k<a;k++){
					if((i&(1<<k))||!use[k])continue;
					dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+len[k]-val[j][k]);
				}
			}
		}
		int goal=0;
		for(int i=0;i<a;i++)if(use[i])goal+=(1<<i);
		int ret=999999999;
		for(int i=0;i<a;i++)ret=min(ret,dp[goal][i]);
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 2000
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 100000
using namespace std;
typedef long long LL;
struct node
{
	int to;
	node *nxt;
}edges[MAXN*2+5];
node *ncnt,*Adj[MAXN+5];
int N,M,spx,spy;
LL sum[MAXN+5];
LL cirlen,dist[MAXN+5],xs[MAXN+5];
LL stk[MAXN+5],t;
bool vis[MAXN+5];
void Init()
{
	ncnt=&edges[0];
}
void AddEdge(int u,int v)
{
	node *p=++ncnt;
	p->to=v;
	p->nxt=Adj[u];
	Adj[u]=p;
	
	node *q=++ncnt;
	q->to=u;
	q->nxt=Adj[v];
	Adj[v]=q;
}
void DFS(int u,int fa)
{
	vis[u]=true;
	for(node *p=Adj[u];p!=NULL;p=p->nxt)
	{
		int v=p->to;
		if(v==fa)
			continue;
		if(vis[v]==true)
		{
			spx=u,spy=v;
			cirlen=dist[v]-dist[u]+1;
			continue;
		}
		dist[v]=dist[u]+1;
		DFS(v,u);
	}
}
void GetXs(int u,int fa)
{
	vis[u]=true;
	for(node *p=Adj[u];p!=NULL;p=p->nxt)
	{
		int v=p->to;
		if(v==fa||vis[v]==true)
			continue;
		GetXs(v,u);
		xs[u]+=xs[v];
		sum[u]+=sum[v];
	}
}
int main()
{
//	freopen("print.in","r",stdin);
//	freopen("print.out","w",stdout);
	Init();
	scanf("%d %d",&N,&M);
	int u,v;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d",&u,&v);
		AddEdge(u,v);
	}
	dist[1]=0;
	DFS(1,-1);
	LL ans=0,tot=0;
	for(int i=1;i<=N;i++)
	{
		if(dist[i]%2==0)
			sum[i]=1LL;
		else
			sum[i]=-1LL;
		tot+=sum[i];
	}
	if(N-1==M)
	{
		if(tot!=0)
		{
			printf("-1\n");
			return 0;
		}
	}
	else
	{
		if(cirlen%2==1)
		{
			if(tot%2==1)
			{
				printf("-1\n");
				return 0;
			}
			sum[spx]-=tot/2;
			sum[spy]-=tot/2;
			ans+=abs(tot)/2;
		}
		else
		{
			if(tot!=0)
			{
				printf("-1\n");
				return 0;
			}
			xs[spx]=1LL;
			xs[spy]=-1LL;
		}
	}
	memset(vis,0,sizeof(vis));
	GetXs(1,-1);
	for(int i=1;i<=N;i++)
	{
		if(xs[i]==0)	ans+=abs(sum[i]);
		else			sum[i]=-sum[i],stk[++t]=sum[i];
	}
	stk[++t]=0;
	sort(stk+1,stk+1+t);
	LL k=stk[(t+1)/2];
	for(int i=1;i<=t;i++)
		ans+=1LL*abs(stk[i]-k);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 12032
#include <stdio.h>
#define W 8
#define H 8

/*

¨ÅPA«ÅQ

A		B		C			D		E		F		G
¨ «		«		¨ ¨ ¨ *		  «		¨ «	 	«		  ¨ *
- *		«		-------		- *		  ¨	*	¨ «		- -	
---		«		    111		-		-----	  *		-----
@12		*					---		  121	---		    1
		---					2				212
		222

*/

#define A 12
#define B 222
#define C 111
#define D 2
#define E 121
#define F 212
#define G 1

int main(void){
	char a[W][H]; int x, y, t=0;
	
	while(1){
		t=0;
		for(y=0; y<H; y++){ for(x=0; x<W; x++) a[x][y]=getchar()-'0'; getchar(); }
		for(y=0; y<H; y++) for(x=0; x<W; x++) if(a[x][y]!=0) goto end; end:
		while(1){
			if(a[x+1][y]!=0 && x+1<W) x++, t=t*10+1;
			else if(a[x][y+1]!=0 && y+1<H) y++, t=t*10+2;
			else break;
		}
		switch(t){
			case A: printf("A\n"); break;	case B: printf("B\n"); break;
			case C: printf("C\n"); break;	case D: printf("D\n"); break;
			case E: printf("E\n"); break;	case F: printf("F\n"); break;
			case G: printf("G\n"); break;
		}
		if(getchar()==EOF) return 0;	/*ósðÇÝÌÄ*/
	}
}

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

void p(long A[], long n) {
	for (int i = 0; i < n; ++i) {
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}

long insertionSort(long A[], long n, long g) {
	long cnt = 0;
	for (long i = g; i < n; ++i) {
		long v = A[i];
		long j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			++cnt;
		}
		A[j + g] = v;
	}
	return cnt;
}

const long gseries[] = {1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573};

long shellSort(long A[], long n) {
	long *G = new long[n];
	long m = 0;
	for (; m < 11; ++m) {
		if (gseries[m] >= n) {
			break;
		}
	}
	for (long i = 0; i < m; ++i) {
		G[i] = gseries[m - 1 - i];
	}
	if (m == 0) {
		m = 1;
		G[0] = 1;
	}

	cout << m << endl;
	p(G, m);

	long cnt = 0;
	for (long i = 0; i < m; ++i)
		cnt += insertionSort(A, n, G[i]);

	delete[] G;
	return cnt;
}

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

	long *A = new long[n];
	for (long i = 0; i < n; ++i) cin >> A[i];

	cout << shellSort(A, n) << endl;
	for (long i = 0; i < n; ++i) cout << A[i] << endl;

	delete[] A;
	return 0;
}

Measured memory_bytes: 8988
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctype.h>
#include <math.h>
using namespace std;

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x=c-a,y=d-b;
    cout<<c-y<<" "<<d+x<<" "<<a-y<<" "<<b+x<<endl;
}

Measured memory_bytes: 256
N = int(input())
red = {}
for i in range(N):
    s = input()
    if s in red:
        red[s] += 1
    else:
        red[s] = 1
M = int(input())
for i in range(M):
    s = input()
    if s in red:
        red[s] -= 1
    else:
        red[s] = -1

if max(red.values()) <= 0:
    print(0)
else:
    print(max(red.values()))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "YES" << endl
#define pyes cout << "Yes" << endl
#define POK cout << "OK" << endl
#define PNO cout << "NO" << endl
#define pno cout << "No" << endl
#define PNG cout << "NG" << endl
#define ret return 0

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  ll n;cin >> n;
  ll res = 0;
  repz(x,1,n+1){
    ll y = n/x;
    res += y*(y+1)*x/2; 
  }
  cout << res << endl;
  ret;
}


Measured memory_bytes: 3628
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = int_fast64_t;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n,m;
    cin >> n >> m;
    VI ys;
    for (int i = 1; i * i <= m; ++i) {
        if (m % i == 0) {
            ys.push_back(i);
            ys.push_back(m/i);
        }
    }
    sort(all(ys));
    for (auto y: ys) {
        if (y >= n) {
            cout << m / y << endl;
            return;
        }
    }
}

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

Measured memory_bytes: 256
D, G = map(int, input().split())
P, C = [-1] * D, [-1] * D
ans = float('inf')

for i in range(D):
    P[i], C[i] = map(int, input().split())


for i in range(2**D):
    comb = list(map(int, format(i, 'b').zfill(D)))
    count = 0
    score = 0
    not_max_indx = -1
    for j, buy_max in enumerate(comb):
        if buy_max:
            count += P[j]
            score += 100 * (j + 1) * P[j]
            score += C[j]
        else:
            not_max_indx = j

    if score >= G:
        ans = min(ans, count)
        continue

    # find max_index
    if not_max_indx == -1:
        continue

    rest = G - score
    price = 100 * (not_max_indx + 1)
    count_tmp = rest // price if rest % price == 0 else (rest // price) + 1
    if count_tmp >= P[not_max_indx]:
        continue
    count += count_tmp
    ans = min(ans, count)
print(ans)

Measured memory_bytes: 40944
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
	int a, b,count=0;
	cin >> a >> b;
	for (int i = a; i <= b; i++) {
		string a = to_string(i);
		if (a[0] == a[4] && a[1] == a[3]) {
			count++;
		}
	}
	cout << count << "\n";
}

Measured memory_bytes: 256
import math
a=[1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049, 100000, 161051, 248832, 371293, 537824, 759375, 1048576, 1419857, 1889568, 2476099, 3200000, 4084101, 5153632, 6436343, 7962624, 9765625, 11881376, 14348907, 17210368, 20511149, 24300000, 28629151, 33554432, 39135393, 45435424, 52521875, 60466176, 69343957, 79235168, 90224199, 102400000, 115856201, 130691232, 147008443, 164916224, 184528125, 205962976, 229345007, 254803968, 282475249, 312500000, 345025251, 380204032, 418195493, 459165024, 503284375, 550731776, 601692057, 656356768, 714924299, 777600000, 844596301, 916132832, 992436543, 1073741824, 1160290625, 1252332576, 1350125107, 1453933568, 1564031349, 1680700000, 1804229351, 1934917632, 2073071593, 2219006624, 2373046875, 2535525376, 2706784157, 2887174368, 3077056399, 3276800000, 3486784401, 3707398432, 3939040643, 4182119424, 4437053125, 4704270176, 4984209207, 5277319168, 5584059449, 5904900000, 6240321451, 6590815232, 6956883693, 7339040224, 7737809375, 8153726976, 8587340257, 9039207968, 9509900499, 10000000000, 10510100501, 11040808032, 11592740743, 12166529024, 12762815625, 13382255776, 14025517307, 14693280768, 15386239549, 16105100000, 16850581551, 17623416832, 18424351793, 19254145824, 20113571875, 21003416576, 21924480357, 22877577568, 23863536599, 24883200000]
x=int(input())
p=0
if x==1:
    print(0,-1)
else:
    for i in range(len(a)):
        for j in range(len(a)):
            if a[j]-a[i]==x :
                print(j+1,i+1)
                p+=1
                break
            elif a[j]+a[i]==x:
                print(j+1,-i-1)
                p+=1
                break
        if p>0:
            break

Measured memory_bytes: 63968
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>
  
using namespace std;
  
const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;
  
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

LL a[100005],b[100005];
int i,j,k,l,m,n;
LL ans=0;

int main()
{
    while(scanf("%d",&n)==1)
    {
        ans=0;
    for(i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
    for(i=n;i>=1;i--)
    {
        a[i]+=ans;
        if(a[i]%b[i]==0)continue;
        LL t=a[i]%b[i];
        ans+=b[i]-t;
    }
    printf("%lld\n",ans);
    }
    return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
const int N=2005,mo=1000000007;
int f[N][N],fac[N],inv[N];
int ksm(int x,int y){
	int i=1;
	for (;y;y>>=1,x=1ll*x*x%mo)
		if (y&1) i=1ll*i*x%mo;
	return i;
}
long long C(int n,int m){
	return 1ll*fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	f[0][0]=1;
	for (int i=0;i<=k;i++)
		for (int j=0;i+j<=k;j++){
			if (j) f[i][j]=f[i][j-1];
			if (i) (f[i][j]+=f[i-1][j+1])%=mo;
		}
	int ans=0;
	if (k==n) ans=f[n-1][0];
	else{
		fac[0]=1;
		for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo;
		inv[n]=ksm(fac[n],mo-2);
		for (int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mo;
		for (int m=n-k+1;m<=n;m++)
			ans=(ans+C(m-2,n-k-1)*f[n-m][k-1-n+m])%mo;
	}
	for (int i=1;i<n-k;i++) (ans<<=1)%=mo;
	printf("%d\n",ans);
}

Measured memory_bytes: 15232
#include<bits/stdc++.h>
#define eps 0.000001;
using namespace std;
typedef long long ll;
const int inf = 0xfff;
const int maxn = 200005;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
int flag1;
ll chufa(ll k)
{
    ll cnt = 0;
    int flag = 1;
    ll a=0, b=0, c=0;
    while(true)
    {
        ll mid = b;
        a = b * 10 + 7;
        cnt++;
        if(a/k>0||a==0)
        {
            b = a % k;
            flag = 0;
        }
        else
            b = a;

        if(!flag){
            if(mid==b)
            {
                flag1 = 0;
                return cnt;
            }
            if (b == 0)
            {
                flag1 = 1;
                return cnt;
            }
        }
    }
    return 0;
}
int main()
{
    ll k;
    cin >> k;
    int judge = 0;
    int d = k % 10;
    for (int i = 1; i <= 9;i++)
    {
        if(i*d%10==7)
            judge = 1;
    }
    if(!judge)  
    {
        cout << "-1" << endl;
        return 0;
    }
    ll cnt = chufa(k);
    if(flag1==1||cnt==1)
        cout << cnt << endl;
    else
        cout << "-1" << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define int long long
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }

class UnionFind
{
 public:
    vector<int> par,sz;
    UnionFind(int N):par(N),sz(N){
        for(int i=0;i<N;i++){
            par[i]=i; sz[i]=1;
        }
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x); y=find(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
    }
    bool same(int x,int y){ return find(x)==find(y); }
    int size(int x){ return sz[find(x)]; }
    bool root(int x){ return par[x]==x; }
};

struct edge{
    int u,v,cost;
    bool operator<(edge &e){
        return cost<e.cost;
    }
};

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

    int N,M; cin>>N>>M;
    vector<edge> es;
    for(int i=0;i<M;i++){
        int a,b,c; cin>>a>>b>>c;
        a--; b--;
        es.push_back({a,b,c});
    }
    sort(es.begin(),es.end());

    vector<int> cand;
    auto calc=[&](int ng)
    {
        int res=0;
        UnionFind tree(N);
        for(int i=0;i<M;i++) if(i!=ng){
            edge e=es[i];
            if(!tree.same(e.u,e.v)){
                res+=e.cost;
                tree.unite(e.u,e.v);
                if(ng==-1) cand.push_back(i);
            }
        }
        return res;
    };

    int weight=calc(-1);
    int cnt=0,sum=0;
    for(int i:cand){
        if(calc(i)!=weight){
            cnt++;
            sum+=es[i].cost;
        }
    }
    cout<<cnt<<' '<<sum<<endl;
    return 0;
}


Measured memory_bytes: 4576
#!/usr/bin python3
# -*- coding: utf-8 -*-

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
s1 = a1 - b1
s2 = a2 - b2

# a1 が先行にする
if s1<0:
    s1*=-1
    s2*=-1

d = s1*t1 + s2*t2
mxd = s1*t1

if d>0:
    print(0)
elif d==0:
    print('infinity')
else:
    if mxd%abs(d)==0:
        print(mxd//abs(d)*2)
    else:
        print(mxd//abs(d)*2+1)


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

const int N = 200006; 
string str; 
int dp[N][3];
int main() {
    cin >> str;
    str = "%" + str;
    int len = str.length() - 1; 
    dp[1][1] = dp[2][2] = 1; 
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++)
                if (i >= j && i - j >= k && str.substr(i - j + 1, j) != str.substr(i - j - k + 1, k))
                    dp[i][j] = max(dp[i][j], dp[i - j][k] + 1); 
    }
    cout << max(dp[len][1], dp[len][2]) << endl; 
    return 0; 
}

Measured memory_bytes: 2880
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll rec(vector<int> v, string const &S, size_t n)
{
    if (n == 0)
    {
        ll sum{};
        ll temp{(int)S[0] - (int)'0'};
        for (size_t i = 0; i < v.size(); i++)
        {
            if (v[i] == 1)
            {
                sum += temp;
                temp = (int)S[i + 1] - (int)'0';
            }
            else
            {
                temp *= 10;
                temp += (int)S[i + 1] - (int)'0';
            }
        }
        sum += temp;
        return sum;
    }
    else
    {
        ll in{}, ex{};
        v[n - 1] = 0;
        in = rec(v, S, n - 1);
        v[n - 1] = 1;
        ex = rec(v, S, n - 1);
        return in + ex;
    }
}

int main()
{
    string S;
    cin >> S;
    vector<int> v(S.size() - 1, -1);
    ll sum;
    sum = rec(v, S, S.size() - 1);
    cout << sum << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#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;
ll const INF = 1LL << 60;

ll calc_div1(ll n, ll p) {
  if (n == 0) return 0;
  return n / p + calc_div1(n / p, p);
}

ll calc_div2(ll n, ll p) {
  if (n % 2 == 1) {
    return calc_div1(n, p) - calc_div2(n - 1, p);
  }
  ll res = calc_div1(n / 2, p);
  if (p == 2) res += n / 2;
  return res;
}

int main() {
  ll N;
  cin >> N;
  ll ans = min(calc_div2(N, 2), calc_div2(N, 5));
  cout << ans << endl;
  return 0;
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ld eps = 1e-9;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

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

  ll k, n; cin >> k >> n;
  vll a(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());

  ll ma = (k-a[n-1]) + a[0];
  for(int i=0;i<n-1;++i) {
    ma = max(ma, a[i+1] - a[i]);
  }
  cout << k - ma << endl;

}


Measured memory_bytes: 1792
#include <iostream>
#include <string>

using namespace std;

bool IsEcho(const string& s) {
  int n = s.size();
  if (n % 2 == 1) {
    return false;
  }
  int m = n / 2;
  for (int i = 0; i < m; i++) {
    if (s[i] != s[m + i]) return false;
  }
  return true;
}

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  if (IsEcho(s))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256