akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int n,m;
vi s,c;

bool ok(string str){
    if(str.size() != n) return false;
    rep(i,m){
        if(str[s[i]] != (char)(c[i]+'0')) return false;     
    }
    return true;
}

string solve(){
    rep(i,1000){
        stringstream iss; iss << i;
        string str = iss.str();
        if(ok(str)) return str;
    }
    return "-1";
}

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

    cin >> n >> m;
    s.resize(m); c.resize(m);
    rep(i,m) {cin >> s[i] >> c[i]; --s[i];}
    cout << solve() << endl;
    return 0;
}


Measured memory_bytes: 256
import scala.annotation.tailrec
object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val exp = readLine.trim
    if (exp == "END") return
    val leaf = Array.tabulate(readInt){_ ⇒
      val Array(a, b, c, d) = readLine.trim.split(' ').map(_.toInt == 1)
      Leaf(CandySet(a, b, c, d))
    }
    Tree.parse(exp, leaf) match {
      case Some(r) ⇒ println(r.calPattern(CandySet(true, true, true, true)))
      case _ ⇒ ???
    }
    solve

  }
  object Tree {
    def parse(express: String, leaf: Array[Leaf]): Option[Node] = {
      implicit val l = leaf
      express.toList match {
        case n Tree Nil ⇒ Some(n)
        case _ ⇒ None
      }
    }
    def unapply(arg:List[Char])(implicit leaf: Array[Leaf]): Option[(Node, List[Char])] = {
      arg match {
        case n::t if n.isDigit ⇒ Some(leaf(n.asDigit - 1), t)
        case '('::(l Tree ' '::(r Tree ')'::t)) ⇒Some(new InterNode(l, r), t)
        case _ ⇒ None
      }
    }
  }
  sealed trait Node {
    def calPattern(candySet: CandySet): Long
  }
  class InterNode(val left: Node, right: Node) extends Node {
    override def calPattern(candySet: CandySet): Long = memo(candySet.toIndex) match {
      case Some(r) ⇒ r
      case None ⇒
        val and = CandySet.all.map{l ⇒
          CandySet.all.filter(r ⇒ l.and(r) == candySet).map(r ⇒ right.calPattern(r)).sum * left.calPattern(l)
        }.sum
        val or = CandySet.all.map{l ⇒
          CandySet.all.filter(r ⇒ l.or(r) == candySet).map(r ⇒ right.calPattern(r)).sum * left.calPattern(l)
        }.sum
        val xor = CandySet.all.map{l ⇒
          CandySet.all.filter(r ⇒ l.xor(r) == candySet).map(r ⇒ right.calPattern(r)).sum * left.calPattern(l)
        }.sum
        memo(candySet.toIndex) = Some(and + or + xor)
        and + or + xor
    }
    private val memo = Array.tabulate(16){_ ⇒ None: Option[Long]}
  }

  case class Leaf(state: CandySet) extends Node {
    override def calPattern(candySet: CandySet): Long = if (candySet == state) 1 else 0
  }
  object CandySet{
    val all: List[CandySet] = (0 until 4).map{_ ⇒ List(true, false)}.foldLeft(Nil::Nil:List[List[Boolean]]){case (a, b) ⇒ a.flatMap{l ⇒ b.map{r ⇒ r::l}}}.map{case a::b::c::d::Nil ⇒ CandySet(a, b, c, d); case _ ⇒ ???}
  }
  case class CandySet(a: Boolean, b: Boolean, c: Boolean, d: Boolean) {
    def toIndex: Int = List(a, b, c, d).map {if (_) 1 else 0}.foldLeft(0) { case (l, r) ⇒ l * 2 + r }
    def and(that: CandySet): CandySet = map(that)(_.&&)
    def or(that: CandySet): CandySet = map(that)(_.||)
    def xor(that: CandySet): CandySet = map(that)(_.^)
    @inline
    private def map(that: CandySet)(@inline func: Boolean ⇒ Boolean ⇒ Boolean): CandySet = CandySet(func(a)(that.a), func(b)(that.b), func(c)(that.c), func(d)(that.d))
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}



Measured memory_bytes: 256116
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  string s;
  cin >> s;
  rep(i, 1 << 3) {
    int n = s[0] - '0';
    rep(j, 3) {
      if(i >> j & 1)
        n += s[j + 1] - '0';
      else
        n -= s[j + 1] - '0';
    }
    if(n != 7) continue;
    cout << s[0];
    rep(j, 3) {
      if(i >> j & 1)
        cout << '+' << s[j + 1];
      else
        cout << '-' << s[j + 1];
    }
    cout << "=7" << endl;
    return 0;
  }
}

Measured memory_bytes: 256
//abc157_d.cpp
//Sun Mar  1 20:09:49 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

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

//Union-Find木
int par[100000]; //親
int treerank[100000]; //木の深さ

//n要素で初期化
void init(int n){
	for (int i=0;i<n;i++){
		par[i] = i;
		treerank[i] = 0;
	}
}

//木の根（親）を見つける
int find (int x){
	if (par[x] == x){
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

//xとyの属する集合の併合
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	} 

	if (treerank[x] < treerank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if (treerank[x] == treerank[y]){
			treerank[x]++;
		}
	}
}

//xとyが同じグループに属するか判定
bool same(int x, int y){
	return find(x) == find(y);
}

int main(){
	int n,m,k;
	cin >> n >> m >> k;

	init(n);

	vector<int> a,b;
	for (int i=0;i<m;i++){
		int e,f;
		cin >> e >> f;
		e--;f--;
		unite(e,f);
		a.push_back(e);
		b.push_back(f);
	}

	vector<int> c,d;
	for (int i=0;i<k;i++){
		int g,h;
		cin >> g >> h;
		g--;h--;
		c.push_back(g);
		d.push_back(h);
	}

	int group[n];
	fill(group,group+n,-1);
	for (int i=0;i<n;i++){
		group[i] = find(i);
	}

	int grouptotal[n];
	fill(grouptotal,grouptotal+n,0);
	for (int i=0;i<n;i++){
		grouptotal[group[i]]++;
	}

	int ans[n];
	fill(ans,ans+n,0);
	for (int i=0;i<n;i++){
		ans[i] = grouptotal[group[i]];
	}

	for (int i=0;i<m;i++){
		ans[a[i]]--;
		ans[b[i]]--;
	}
	for (int i=0;i<k;i++){
		if (group[c[i]]==group[d[i]]){
			ans[c[i]]--;
			ans[d[i]]--;
		}
	}

	for (int i=0;i<n;i++){
		cout << ans[i]-1 << " ";
	}
	printf("\n");
}

Measured memory_bytes: 4852
#include<iostream>

using namespace std;

int get2(int a) {
	int cnt = 0;
	while (a >= (1 << cnt))cnt++;
	return cnt - 1;
}

int main() {
	int N;

	cin >> N;

	if (N == (1 << get2(N))) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;

	cout << 1 << " " << 2 << endl;
	cout << 2 << " " << 3 << endl;
	cout << 3 << " " << N + 1 << endl;
	cout << N + 1 << " " << N + 2 << endl;
	cout << N + 2 << " " << N + 3 << endl;

	for (int i = 4; i < N; i += 2) {
		cout << i + 1 << " " << i << endl;
		cout << i << " " << 1 << endl;
		cout << 1 << " " << N + i + 1 << endl;
		cout << N + i + 1 << " " << N + i << endl;

	}
	
	if (N % 2 == 0) {
		cout << N << " " << N + ((1 << get2(N)) + 1) << endl;
		cout << (N ^ (1 << get2(N))) << " " << N + N << endl;
	}

	return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


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

	ll i, o, t, j, l, s, z;
	cin >> i >> o >> t >> j >> l >> s >> z;
	
	ll ans = 0;
	ans += o;
	if (i > 0 && j > 0 && l > 0) {
		ll temp = 2 * (i / 2 + j / 2 + l / 2);
		i--, j--, l--;
		temp = max(temp, 2 * (i / 2 + j / 2 + l / 2) + 3);
		ans += temp;
	}
	else ans += 2 * (i / 2 + j / 2 + l / 2);
	puts(ans);

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;
  vector<int> vl(n);
  for (int i = 0; i < n; i++) {
    cin >> vl[i];
  }

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

  int ans = 0;
  for (int i = 0; i < n - 2; i++) {
    for (int j = i + 1; j < n - 1; j++) {
      int a = vl[i], b = vl[j];
      int lower = abs(a - b), upper = a + b;
      auto lower_it = upper_bound(vl.begin() + j + 1, vl.end(), lower);
      auto upper_it =
          upper_bound(vl.rbegin(), vl.rend() - j - 1, upper, greater<int>());
      if (lower_it != vl.end() && upper_it != vl.rend()) {
        int upper_idx = distance(vl.rbegin(), upper_it);
        int lower_idx = distance(vl.begin(), lower_it);
        ans += max(0, n - upper_idx - lower_idx);
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
 
int main()
{
    std::string s;
    int slong, tmp;
    bool flag[28];

    std::cin >> s;
    slong = s.size();
    for(int i = 0;i < 26;i++){
        flag[i] = false;
    }

    for(int i = 0;i < slong;i++){
        tmp = s[i] - 'a';
        flag[tmp] = true;
    }


    int k = 0;
    while(flag[k]){
        k++;
    }

    if(k == 27){
        std::cout << "None";

        return 0;
    }

    std::cout << (char)(k + 'a');

    return 0;
}

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

int main(void) 
{
    ll n, q;
    cin >> n;
    vector<ll> a(n);
    map<ll,ll> table;
    ll ans = 0;
    rep(i,n) 
    {
        cin >> a[i];
        table[a[i]]++;
        ans += a[i];
    }
    cin >> q;
    rep(i,q)
    {
        ll b, c;
        cin >> b >> c;
        ll num = c - b;
        ans = ans + table[b] * num;
        table[c] += table[b];
        table[b] = 0;
       
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 10040
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  string s;
  cin >> s;
  bool flag = true;

  int n = 0;
  for (char i: s){
    n++;
    if (n % 2 == 0 && i == 'R') {
      flag = false;
      break;
    }
    if (n % 2 == 1 && i == 'L') {
      flag = false;
      break;
    }
  }
  
  if (flag) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        while(true){
            int h = scan.nextInt();
            int w = scan.nextInt();
            if(h == 0 && w == 0) break;
            for(int i = 0; i < h; i++){
                if(i % 2 == 0){
                    for(int j = 0; j < w; j++){
                        if(j % 2 == 0){
                            System.out.printf("#");
                        }else{
                            System.out.printf(".");
                        }
                    }
                }else
                {
                    for(int j = 0; j < w; j++){
                        if(j % 2 == 0){
                            System.out.printf(".");
                        }else{
                            System.out.printf("#");
                        }
                    }
                }
                System.out.printf("\n");
            }
            System.out.printf("\n");
        }
        scan.close();
    }
}


Measured memory_bytes: 63236
def atc_153b(a: str, b: str) -> str:
    HN = a.split(" ")
    H = int(HN[0])
    N = int(HN[1])

    A = b.split(" ")
    A_int = [int(ai) for ai in A]
    damage = sum(A_int)

    if (H - damage) <= 0:
        return "Yes"
    else:
        return "No"


a = input()
b = input()
print(atc_153b(a, b))

Measured memory_bytes: 20964
N, K, Q = map(int, input().split())

point_list = []
for i in range(N):
  point_list.append(K)

for i in range(Q):
  num = int(input()) - 1
  point_list[num] += 1

res = []
for i in point_list:
  i -= Q
  res.append(i)

for i in res:
  if i > 0:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 10568
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
      n: usize,
      aa: [i64; n],
    }
    let mut s = vec![0; n+1];
    for i in 0..n {
        s[i+1] = s[i] + aa[i]
    }
    s.sort();

    let mut ans = 0;
    let mut cnt = 1 as u64;
    for i in 1..s.len() {
        if s[i] == s[i-1] {
            cnt += 1;
        } else {
            ans += cnt * (cnt-1) / 2;
            cnt = 1;
        }
    }
    ans += cnt * (cnt-1) / 2;
    println!("{}", ans);
}


Measured memory_bytes: 8444
#include <atcoder/all>
#include <bits/stdc++.h>

#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

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

void solve() {
    int K; cin >> K;
    REP(_,K) cout << "ACL";
    cout << endl;
}

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

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

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
 
    int xa = min(a, k);
    k -= xa;
    int xb = min(b, k);
    k -= xb;
    int xc = k;
    int ans = xa - xc;
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
from math import factorial
n = int(input())
ans = 1
col = {"R":0,"G":0,"B":0}
mod = 998244353
for i in input():
	bef = sorted(col.values())
	col[i] += 1
	if col[i] > bef[2]:		# 選択肢は増加しない
		pass
	elif col[i] > bef[1]:	# 元の中央値-最小値の分だけ、選択肢が増加する
		ans *= bef[2] - bef[1]
	else:					# 中央値-元の最小値の分だけ、選択肢が増加する
		ans *= bef[1] - bef[0]
	ans %= mod
print(factorial(n)*ans%mod)

Measured memory_bytes: 47704
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
int  main(){
	lli  n,m;
	cin>>n>>m;
	vector<lli > w(n);
	vector<lli > v(n);
	for(lli  i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	vector<lli >dp(m+1,0);
	dp[0]=0;
	for(lli  i=0;i<n;i++){
		for(lli  j=m ;j>0;j--){
			if((j-w[i])>=0)dp[j]=max(dp[j-w[i]]+v[i],dp[j]);	
		}
	}
	cout<<dp[m];
	
}

Measured memory_bytes: 3976
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;

bool doesBalance(std::string s){
    std::stack<char> stack;
    REP(i, s.size()){
        if(s[i] == '(' || s[i] == '['){
            stack.push(s[i]);
        }else if(s[i] == ')'){
            if(stack.empty() || stack.top() != '('){return false;}
            stack.pop();
        }else if(s[i] == ']'){
            if(stack.empty() || stack.top() != '['){return false;}
            stack.pop();
        }
    }

    return stack.empty();
}

int main(){
    std::string s;
    while(std::getline(std::cin, s), s != "."){
        if(doesBalance(s)){puts("yes");}
        else{puts("no");}
    }
}

Measured memory_bytes: 1180
using System;

public class Test
{

	public static void Main()
	{
		string line = Console.ReadLine();
		string[] buffer = line.Split(' ');
		int n = int.Parse(buffer[0]);
		int k = int.Parse(buffer[1]);
		
		string line2 = Console.ReadLine();
		string[] buf2 = line2.Split(' ');
		int[] nums = new int[n];
		for(int i=0;i<buf2.Length;i++){
			nums[i] = int.Parse(buf2[i]);
		}
		Array.Sort(nums);

		int ans = 0;
		for(int x=nums.Length-1;x>(nums.Length-1)-k;x--){
			ans = ans + nums[x];
		}
		
		Console.WriteLine(ans);
	}
}	

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,x;
    cin>>n>>x;
    vector<ll>a(n);
    ll ans=0;
    rep(0,i,n)cin>>a[i];
    sort(a.begin(),a.end());
    rep(0,i,n){
        if(x>=a[i]){
            if(i==n-1){
                if(a[i]==x)++ans;
            }else{
                x-=a[i];
                ++ans;
            }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>

using int64 = long long;

int64 computeCumXOR(int64 n) {
    n++;

    int64 exor = 0;
    for (int i = 0; i <= 50; i++) {
        int64 x = (1LL << (i + 1)),
              num = (1LL << i) * (n / x) + std::max(0LL, n % x - (1LL << i));
        exor ^= (1LL << i) * (num & 1);
    }
    return exor;
}

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

    int64 A, B;
    std::cin >> A >> B;

    std::cout << (computeCumXOR(B) ^ computeCumXOR(std::max(0LL, A - 1))) << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
 
bool codejam = 0;
 
typedef long long li;
typedef long double ld;
 
void solve();
int32_t main () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);
	#ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
	#endif
	int t = 1; 
	// cin >> t;
	int tt = t;
	while (t--) { 
		if (codejam) cout << "Case #" << tt - t << ": ";
		solve();
	}
	return 0;
}

const int N = 1005;
int n, k;
int pre[N] = {0};
bool possible (int num, int n, int k) {
	int cnt = 0;
	for (int l = 1; l <= n; ++l) {
		for (int r = l; r <= n; ++r) {
			int s = pre[r] - pre[l - 1];
			if ((s & num) == num) ++cnt;
		}
	}
	return cnt >= k;
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> pre[i];
		pre[i] += pre[i - 1];
	}
	int have = 0;
	for (int bit = 42; bit >= 0; --bit) {
		if (possible(have + (1LL << bit), n, k)) have += (1LL << bit);
	}
	cout << have;
}	

Measured memory_bytes: 256
N, M =      map(int, input().split())
S    = list(map(int, input().split()))
T    = list(map(int, input().split()))

modulo = 10 ** 9 + 7

# tab[j][i] = S[i] == T[j]
tab = [[s == t for s in S] for t in T]

# 番兵
for t in tab:
    t.append(1)
tab.append([1] * (len(S) + 1))

# 右下から計算
# tab[j][i] = S[i:]とT[j:]の等しい部分列の個数
for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        n  = tab[j+1][i] + tab[j][i+1] - tab[j+1][i+1]  # 包除原理
        n += tab[j+1][i+1] if tab[j][i] else 0  # S[i]とT[j]をマッチさせたとき
        tab[j][i] = n % modulo

print(tab[0][0])


Measured memory_bytes: 136028
x = [int(i) for i in input().split()]
n = x[0]
a = x[1]
b = x[2]
if (b - a) % 2 == 0:
    ans = b - (a + b) // 2
else:
    if a - 1 <= n - b:
        tmp = b - a
        ans = tmp - (1 + tmp) // 2 + a
        if b - 1 <= a:
            ans = b - 1
    else:
        tmp = a + n - b + 1
        ans = n - (n + tmp) // 2 + (n - b + 1)
        if n - a <= n - b + 1:
            ans = n - a
print(ans)

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

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

Measured memory_bytes: 256
if __name__ == '__main__':
    N, A, B = map(int,input().split())
    count = 0
    for n in range(1, N+1):
        n = str(n)
        n_sum = 0
        for a in n:
            n_sum += int(a)
        if n_sum >= A and n_sum <= B:
            count += int(n)
    print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,x,n) for(int i=x;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N;cin>>N;
        vector<int> A(N);
        int ans=-1;
        
        for(int i=0;i<N;i++) cin>>A[i];
        
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                int a=A[i]*A[j];
                string S=to_string(a);
                
                bool ok=true;
                
                for(int k=1;k<S.size();k++){
                    if(S[k-1]+1!=S[k]) ok=false;
                }
                
                if(ok) ans=max(ans,a);
            }
        }
        
        cout<<ans<<endl;
        return 0;
    }
}



Measured memory_bytes: 3300
# -*- coding: utf-8 -*-
s = list(input())

cand = []

#bit全探索
n = len(s) - 1
arr = [0] * n
for i in range(2 ** n):
    diff = 0
    for j in range(n):
        if((1&i>>j) == 1):
            arr[j] = 1
        else:
            arr[j] = 0
    #ここに処理
    s_copy = s[:]
    diff = 0
    for j in range(len(arr)):
        if arr[j] == 1:
            s_copy = s_copy[:(j+diff+1)] + ["+"] + s_copy[(j+diff+1):]
            diff += 1
    cand.append(s_copy)

cand_sum = []

for i in range(len(cand)):
    t = "".join(cand[i])
    tt = []
    tt = t.split("+")
    tt = list(map(int,tt))
    cand_sum.append(sum(tt))

print(sum(cand_sum))


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

long long nextnum(long long n1, long long n2){
   	long long next = n1 + n2;
    return next;
}

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

    vector<long long> nums={2, 1};
	//cout << nums[0] << " " << nums[1] << endl;
    int cnt = 1;
    while(1){
        if (cnt == N) {
            cout <<nums[cnt] << endl;
            break;
        }
      	cnt++;
        long long ln = nextnum(nums[cnt-1], nums[cnt-2]);
        nums.push_back(ln);
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int i,j,k;
  int N,tmp;
  scanf("%d",&N);
  int A[N],B[N];
  for(i=0;i<N;i++){
    scanf("%d ",&A[i]);
  }
  
  for(i=N-1;i>(N/2);i--){
    B[i]=A[i];
  }
  for(;i!=-1;i--){
    k=2;
    tmp=0;
    while((i+1)*k <= N){
      tmp+=B[(i+1)*k-1];
      k++;
    }
    if(tmp%2 == A[i])
      B[i]=0;
    else
      B[i]=1;
  }
  int ans=0;
  for(i=0;i<N;i++)
    ans+=B[i];
  printf("%d\n",ans);
  for(i=0;i<N;i++){
    if(B[i]==1)
      printf("%d ",i+1);
  }
  puts("");
  return 0;
}
    


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

using namespace std;

typedef long long ll;

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

int main() {
  ll n, a, b; read(n, a, b);
  ll blue = (n / (a + b)) * a;
  blue += min(a, (n % (a + b)));
  print(blue);
}

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

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var graph = new List<int>[N].Select(x => new List<int>()).ToArray();
            for (var i = 0; i < N - 1; i++)
            {
                var ab = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
                var a = ab[0] - 1;
                var b = ab[1] - 1;
                graph[a].Add(b);
                graph[b].Add(a);
            }
            var queue = new Queue<Tuple<int, int>>();
            queue.Enqueue(new Tuple<int, int>(0, 1));
            queue.Enqueue(new Tuple<int, int>(N - 1, 2));
            var depths = Enumerable.Repeat(-1, N).ToArray();
            depths[0] = 0;
            depths[N - 1] = 0;
            var colors = new int[N];
            while (queue.Any())
            {
                var current = queue.Dequeue();
                foreach (var next in graph[current.Item1])
                {
                    if (colors[next] != 0) continue;
                    depths[next] = depths[current.Item1] + 1;
                    colors[next] = current.Item2;
                    queue.Enqueue(new Tuple<int, int>(next, colors[next]));
                }
            }
            var fennec = colors.Count(x => x == 1);
            var snuke = N - fennec;

            Console.WriteLine(fennec > snuke ? "Fennec" : "Snuke");
        }
    }
}


Measured memory_bytes: 54832
package main

import(
    "fmt"
)



func main() {
    var a,b,c,d int
    fmt.Scan(&a,&b,&c,&d)
    fmt.Println(max32(a*b,c*d))
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}


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

struct S {
	int d, x, y, v;
	S(int d, int x, int y, int v) :
			d(d), x(x), y(y), v(v) {
	}
};
auto cmp = [](S x, S y) {
	return x.d > y.d;
};
priority_queue<S, vector<S>, decltype(cmp)> q(cmp);

int h, w, k, sx, sy, gx, gy, dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
bool inside(int x, int y) {
	return x >= 0 && x < h && y >= 0 && y < w;
}

int main() {
	cin >> h >> w >> k >> sx >> sy >> gx >> gy;
	--sx, --sy, --gx, --gy;
	bool b[h][w], c[h][w][4];
	fill(b[0], b[h], 0);
	for (int i = 0; i < h; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < w; ++j)
			if (s[j] == '.')
				b[i][j] = 1;
	}

	fill(c[0][0], c[h][0], 0);
	for (int i = 0; i < 4; ++i)
		q.emplace(0, sx, sy, i);

	while (!q.empty()) {
		S s = q.top();
		q.pop();
		if (s.x == gx && s.y == gy) {
			cout << (s.d + k - 1) / k << endl;
			return 0;
		}
		if (c[s.x][s.y][s.v])
			continue;
		c[s.x][s.y][s.v] = 1;
		for (int i = 0; i < 4; ++i) {
			int nx = s.x + dx[i];
			int ny = s.y + dy[i];
			if (!inside(nx, ny) || !b[nx][ny] || c[nx][ny][i])
				continue;
			int nd = (s.v == i ? s.d + 1 : (s.d + k - 1) / k * k + 1);
			q.emplace(nd, nx, ny, i);
		}

	}
	cout << -1 << endl;
	return 0;

}


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

//Function Macros:
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

//Type Definitions:
typedef long long ll;
typedef unsigned long long ull;

//Constants:
const int INF = 2e9;
const int MOD = 1e9 + 7;

//Global Variables:

//Prototype Declarations:
ull gcd(ull, ull);
bool isPrime(ull);

vector<ull> enum_div(ull n)
{
	vector<ull> ret;
	for(ull i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

//================ Main Loop ================
int main()
{
    ull a, b;
    cin >> a >> b;
    vector<ull> x, y, cd;
    x = enum_div(a);
    y = enum_div(b);
    x.push_back(a);
    y.push_back(b);

    sort(all(x));
    sort(all(y));
    
    ull i=0, j=0;
    while(i<x.size()&&j<y.size()){
        if(x[i]==y[j]){
            cd.push_back(x[i]);
            i++; j++;
        }else if(x[i]>y[j]){
            j++;
        }else{
            i++;
        }
    }
    ull ans = 1;
    for(auto i:cd){
        if(isPrime(i)){
            ans++;
        }
    }
    cout << ans << endl;

    //dbg
    /*
    for(auto i:x) cout << i << endl;
    for(auto i:y) cout << i << endl;
    for(auto i:cd) cout << i << endl;
    */
    return 0;
}
//===========================================

//Functions:
ull gcd(ull a, ull b)
{
    return b ? gcd(b, a % b) : a;
}

bool isPrime(ull num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (ull i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            
            return false;
        }
    }

    return true;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

ll modPow(ll a, ll b) {
	if (b & 1) return a * modPow(a, b-1) % MOD;
	if (b == 0) return 1;
	return modPow(a*a % MOD, b / 2);
}

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

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

	ll h, w, t;
	cin >> h >> w >> t;
	ll hh = h / gcd(h, t);
	ll ww = w / gcd(w, t);

	// How many ways to place to cover the (hh, ww) grid?
	// Every robot moves either one square down, right or doesn't move at every step
	// -> Every cycle has both height h and width w, or all cycles have width 1 or height 1
	// Say some position has a non-moving robot. Then there can be no D-robots on its column, or R robots on its row
	// one S-robot forces the entire structure to be stills or 1-width cycles

	// Now assume there are no S-robots. Then for every position, the robots diagonally to it must have the same direction.
	// Hence we must have a stripe pattern. A stripe pattern only works if we have even width and height

	ll res = (modPow(2, hh) + modPow(2, ww) - 1);
	res += (modPow(2, gcd(hh, ww)) - 2);
	res %= MOD;
	if (res < 0) res += MOD;

	res = modPow(res, gcd(h, t) * gcd(w, t));
	res %= MOD;
	if (res < 0) res += MOD;

	cout << res << '\n';
}


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

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

#define INF 1e9

int main(){
  int A, B;
  cin >> A >> B;
  A--, B--;
  vector<string> grid(100, string(100, '.'));
  REP(i, 50){
    grid[i] = string(100, '#');
  }
  int x = 0, y = 0;
  REP(i, A){
    grid[y][x] = '.';
    if(x == 98){
      x = 0;
      y+=2;
    }
    else{
      x +=2;
    }
  }
  x = 0, y = 51;
  REP(i, B){
    grid[y][x] = '#';
    if(x == 98){
      x = 0;
      y+=2;
    }
    else{
      x+=2;
    }
  }
  cout << 100 << " " << 100 << endl;
  REP(i, 100){
    cout << grid[i] << endl;
  }
  return 0;
}


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

map <string, string> ats;

int main()
{
    string s;
    cin >> s;
    ats["Sunny"] = "Cloudy";
    ats["Cloudy"] = "Rainy";
    ats["Rainy"] = "Sunny";
    cout << ats[s] << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
 
            int count = 0;
            for (int i = 1; i <= N; i++)
            {
                if (i % 2 == 1 && HasEightDivisors(i))
                {
                    count++;
                }
            }
 
            Console.WriteLine(count);
        }
 
        public static bool HasEightDivisors(int N)
        {
            int count = 0;
            for (int i = 1; i <= N; i++)
            {
                if(N%i == 0)
                {
                    count++;
                }
                if(count > 8) return false;
            }
            
            if(count ==8) return true;
            else return false;
        }
    }
}

Measured memory_bytes: 27472
N = int(input())
cardlist = input().split()
cardlist = [int(n) for n in cardlist]
cardlist_s = sorted(cardlist, reverse=True)

Alice = 0
Bob = 0
for i in range(N):
    if(i%2==0):
        Alice = Alice + cardlist_s[i]
    else:
        Bob = Bob + cardlist_s[i]
print(Alice-Bob)


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

#define ll long long
#define ull unsigned long long
#define BUG printf("************\n")
using namespace std;

const ull mod = 1e8 + 7;
const int maxn = 4e5 + 10;
const int maxm = 1e6 + 10;
const double eps = 1e-8;

ll n, m;
ll a[maxn], b[maxn], s[maxn], f[maxn] ,c[maxn], r[maxn];

inline int lb(int x) {
    return x & -x;
}

void add(ll num, int x) {
    for (int i = x; i <= n; i+=lb(i))
        c[i] += num;
}

ll read(int x) {
    ll tot = 0;
    for (int i = x; i; i -= lb(i))tot += c[i];
    return tot;
}

const int cmp(const int i, const int j) {
    return f[j] == f[i] ? i < j : f[i] < f[j];
}

ll inversed_pair() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i)r[i] = i;
    sort(r + 1, r + 1 + n, cmp);
    ll tot = 0;
    for (int i = 1; i <= n; ++i) {
        tot += read(r[i]);
        add(1, r[i]);
    }
    return tot;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= x)b[i] = 1;
        else b[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + b[i];
    }
    int t = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 2 * s[i] - i;
        if (f[i] >= f[0])++t;
    }
    return (2 * (inversed_pair() + t) >= m);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << a[1] << endl;
        return 0;
    }
    int l = 1, r = 1e9+10;
    m = (n + 1) * n / 2;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (!check(mid))r = mid - 1;
        else l = mid;
    }
    cout << l << endl;
    return 0;
}
/*
9
7 12 4 18 3 16 18 5 9
*//*
10
16 18 12 17 15 8 10 9 16 4
 */

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

#define rep(i, N) for (ll i = 0; i < N; i++)
#define rep1(i, N) for (ll i = 1; i <= N; i++)
#define repr(i, N) for (ll i = N-1; i >= 0; i--)
#define repr1(i, N) for (ll i = N; i > 0; i--)

#define MOD 1000000007

using ll = long long;
using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<P> vpi;
typedef pair<ll,ll> Pl;
typedef vector<ll> vl;
typedef vector<Pl> vpl;

ll gcd(ll a, ll b){
    if(a < b) swap(a, b);
    if(b <= 0) return -1;
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll a, ll b){
    return (a/gcd(a,b)*b);
}


int main() {
    int N,M,Q;
    cin >> N>>M>>Q;
    vector<int> a(Q),b(Q),c(Q),d(Q);
    rep(i,Q) cin >> a[i] >> b[i] >> c[i] >> d[i];
    vi A(N, 1),NM(N, M);
    ll ans = 0;
    
    while(1){
        ll sum = 0;
        rep(i,Q){
            if(A[(b[i]-1)] - A[(a[i]-1)] == c[i]) sum += d[i];
        }
        ans = max(sum, ans);

        A[N-1]++;
        rep(i,N-1){
            if(A[N-1-i] > M){
                A[N-2-i]++;
            }else break;
        }
        rep1(i,N-1){
            if(A[i] == M+1){
                A[i] = A[i-1];
            }
        }

        if(A[0] > M) break;
    }

    //string ans = ( flag ? "OK":"NG");
    cout << ans;
    //printf("%.8lf", ans);
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>

int main()
{
  unsigned W, a, b;
  std::cin >> W >> a >> b;
  
  if (a + W < b) {
    std::cout << (b - (a + W)) << std::endl;
  } else if (b + W < a) {
    std::cout << (a - (b + W)) << std::endl;
  } else {
    std::cout << 0 << std::endl;
  }

  return 0;
}

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

typedef long long ll;

const long long MOD = 1000000007;
long long modpow(long long a, long long n, long long m)
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = (ans * a) % m;
        }
        a = (a * a) % m;
        n >>= 1;
    }
    return ans;
}
long long combi(long long n, long long a)
{
    long long ans = 1, ans1 = 1;
    for (long long i = n - a + 1; i <= n; i++)
    {
        ans *= i % MOD;
        ans %= MOD;
    }

    for (long long i = 2; i <= a; i++)
        ans1 = (ans1 * i) % MOD;
    ans1 = modpow(ans1, MOD - 2, MOD);
    return ((ans % MOD) * ans1) % MOD;
}

void dfs(string s, char mx, ll N)
{
    if (s.length() == N)
    {
        cout << s.c_str() << endl;
    }
    else
    {
        for (char c = 'a'; c <= mx; c++)
        {
            dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx), N);
        }
    }
}

int bfs(int a, int b, int h, int w, char tmp[][101])
{
    int ans[101][101] = {0};
    char c[101][101] = {0};
    queue<pair<int, int>> s;

    for (int i = 0; i <= h; i++)
    {
        for (int j = 0; j <= w; j++)
        {
            c[i][j] = tmp[i][j];
        }
    }

    s.push(make_pair(a, b));

    while (s.size() > 0)
    {

        pair<int, int> tmp = s.front();
        s.pop();
        c[tmp.first][tmp.second] = '#';
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (tmp.first + i < 1 || tmp.first + i > h)
                {
                    continue;
                }
                if (tmp.second + j < 1 || tmp.second + j > w)
                {
                    continue;
                }
                if (i != 0 && j != 0)
                {
                    continue;
                }
                if (i == 0 && j == 0)
                {
                    continue;
                }
                if (c[tmp.first + i][tmp.second + j] == '#')
                {
                    continue;
                }
                c[tmp.first + i][tmp.second + j] = '#';
                if (ans[tmp.first + i][tmp.second + j] == 0)
                {
                    ans[tmp.first + i][tmp.second + j] = ans[tmp.first][tmp.second] + 1;
                }
                else
                {
                    ans[tmp.first + i][tmp.second + j] = min(ans[tmp.first + i][tmp.second + j], ans[tmp.first][tmp.second] + 1);
                }
                s.push(make_pair(tmp.first + i, tmp.second + j));
            }
        }
    }

    int asd = 0;

    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            asd = max(a, ans[i][j]);
        }
    }

    return asd;
}

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;

    if(a > b){
        cout << 0 << endl;
        return 0;
    }

    if(n==1 && a==b){
        cout << 1 << endl;
        return 0;
    }
    else if(n==1){
        cout << 0 << endl;
        return 0;
    }

    cout << (b-a)*(n-2) + 1 << endl;

    return 0;
}

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

using namespace std;

bool ok(long long cnt, long long a, long long b)
{
    long long c = a * b;
    if (cnt < b)
    {
        long long F = 1 * cnt;
        long long L = (cnt + 1) * 1;
        long long p1 = cnt / 2;
        for (int i = max(1LL, p1 - 3); i <= min(cnt + 1, p1 + 3); i++)
        {
            long long p2 = 0;
            if (i == a) continue;
            if (i < a) p2 = cnt + 1 - i;
            if (i > a) p2 = cnt + 2 - i;
            if (i * p2 >= c) return 0;
        }
        return 1;
    }
    else
    {
        for (int i = max(1LL, cnt / 2 - 5); i <= min(cnt / 2 + 5, cnt + 1); i++)
        {
            if (i == a) continue;
            long long skipped = i - 1;
            if (i > a) skipped--;
            long long p2 = cnt + 1;
            p2 -= skipped;
            if (p2 <= b) p2--;
            if (i * p2 >= c) return 0;
        }
        return 1;
    }
}

void solve()
{
    long long a, b;
    cin >> a >> b;
    long long c = a * b;
    if (a > b)
        swap(a, b);
    long long l = a - 1, r = 2e9;
    while (l + 1 < r)
    {
        long long mid = (l + r) / 2;
        if (ok(mid, a, b))
            l = mid;
        else
            r = mid;
    }
    cout << l << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    while (q--) solve();
}


Measured memory_bytes: 256
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;
import std.ascii;


void main()
{
  auto s = readln.chomp;
  auto a = "AKIHABARA";
  int i;
  auto f = false;
  foreach (e; s) {
    if (i < a.length && e == a[i]) {
      i++;
    } else if (i < a.length && a[i] == 'A') {
      i++;
      if (i < a.length && e == a[i]) {
        i++;
      } else {
        f = true;
        break;
      }
    } else {
      f = true;
      break;
    }
  }
  if (i == a.length - 1) {

  } else if (i != a.length) {
    f = true;
  }
  if (f) {
    writeln("NO");
  } else {
    writeln("YES");
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] upper = new int[n];
        int[] lower = new int[n];

        for(int i = 0; i < n; i++){
            upper[i] = sc.nextInt();
        }
        int maxSum = upper[0];
        for(int j = 0; j < n; j++){
            lower[j] = sc.nextInt();
            maxSum += lower[j];
        }

        int tmpSum = maxSum;
        for(int k = 1; k < n; k++){
            tmpSum +=  (upper[k] - lower[k-1]);
            if(tmpSum > maxSum){
                maxSum = tmpSum;
            }
        }
        System.out.println(maxSum);
    }

}

Measured memory_bytes: 25300
a=map(int, raw_input().split())
a.sort()
a.reverse()

cnt=0
diff=a[0]-a[1]
cnt+=diff
a[1]=a[0]
a[2]=a[2]+diff

if (a[1]-a[2])%2==0:
	cnt+=(a[1]-a[2])/2
else:
	cnt+=(a[1]-a[2])/2+1
	cnt+=1	

print cnt

Measured memory_bytes: 2568
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<utility>

using namespace std;

typedef long long int64;

int main(void){
    int64 N,M;
    cin>>N>>M;
    vector<int64> A(M);
    int64 sum=0;
    for (int64 i = 0; i < M; i++)
    {
        cin>>A[i];
        sum+=A[i];
    }
    if(sum>N){
        cout<<-1<<endl;
    }else{
        cout<<N-sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 3632
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    q,h,s,d=map(int,input().split())
    n=int(input())
    weight=[(0.25,q,q/0.25),(0.5,h,h/0.5),(1,s,s),(2,d,d/2)]
    weight.sort(key=itemgetter(2))
    cost=0
    for w in weight:
        kosu=n//w[0]
        cost+=int(w[1]*kosu)
        n-=w[0]*kosu
    print(cost)
if __name__=='__main__':
    main()

Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>

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

        int dp[n+1][5][5][5];
        memset(dp, 0, (n+1)*500);
        dp[0][0][0][0] = 1;
        for(int i=1; i<=n; i++){
                for(int a=0; a<5; a++){
                        for(int b=0; b<5; b++){
                                for(int c=0; c<5; c++){
                                        for(int d=1; d<5; d++){
                                                if(b==1 && c==3 && d==2) continue;
                                                if(b==1 && c==2 && d==3) continue;
                                                if(b==3 && c==1 && d==2) continue;

                                                if(a==1 && c==3 && d==2) continue;
                                                if(a==1 && b==3 && d==2) continue;

                                                dp[i][b][c][d] += dp[i-1][a][b][c];
                                                dp[i][b][c][d] %= 1000000007;
                                        }
                                }
                        }
                }
        }

        int ans = 0;
        for(int i=1; i<5; i++) for(int j=1; j<5; j++) for(int k=1; k<5; k++){
                ans += dp[n][i][j][k];
                ans %= 1000000007;
        }
        printf("%d\n", ans);
        return 0;
}


Measured memory_bytes: 256