akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;

#define endl '\n'

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int k,x;
	cin>>k>>x;
	if(k*500>=x) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,ans=0;
	cin>>a>>b>>c;
	if(a>b&&a>c) ans=b*c/2;
	else if(b>a&&b>c) ans=a*c/2;
	else if(c>a&&c>b) ans=a*b/2;
	else if(a==b&&b<c) ans=a*b/2;
	else if(a==c&&c<b) ans=a*c/2;
	else if(b==c&&c<a) ans=b*c/2;
	cout<<ans;
	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++)
#define REP(i, n) for(int i = 1; i < (int)(n); i++)
typedef long long ll;

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

int dp[100];

//最大公約数
int gcd(int x, int y){
  if(x % y == 0) return y;
  return gcd(y, x % y);
}
//最小公倍数
int lcm(int x, int y){
  return x * y / gcd(x, y);
}
//フィボナッチ数列
//配列dpを-1で初期化する
int fib(int n){
  if(n == 0 || n == 1) return dp[n] = 1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n - 1) + fib(n - 2);
}
//階乗計算(factorial)
int fact(int n){
  if(n = 1) return 1;
  return n * fact(n - 1);
}
//累乗計算(Exponentiation)
//x**y
ll expo(int x, int y){
  ll ans = 1;
  rep(i, y){
    ans *= x;
  }
  return ans;
}
//桁数
int keta(ll x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    x /= 10;
    res++;
  }
  return res;
}


int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if(a < b && b < c) cout << "Yes" << endl;
  else cout << "No" << endl;
}





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

#define int long long

int N, K;
int a[1111];
vector<int> cand;

// 渡されたbitを含む部分列の個数をカウントする
int countMask(int a) {
   int ret = 0;
   for (int x : cand) {
      if ((x & a) == a) { // これ頭良い
         ret++;
      }
   }
   return ret;
}

signed main() {
   // 入力
   cin >> N >> K;
   for (int i = 0; i < N; i++) {
      cin >> a[i];
   }

   // 部分列全列挙
   for (int i = 0; i < N; i++) {
      int sum = 0;
      for (int j = i; j < N; j++) {
         sum += a[j];
         cand.push_back(sum);
      }
   }

   int mask = 0; // これが答えになる。条件を満たすbitをここに付け加えてく
   for (int i = 40; i >= 0; i--) {
      if (countMask(mask | (1LL << i)) >= K) {
         mask |= (1LL << i);
      }
   }

   cout << mask << endl;

   return 0;
}

Measured memory_bytes: 6384
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>
#include <iterator>
#include <cassert>

using ll = long long;
using ull = unsigned long long;
constexpr ll mop = 1000000007;
constexpr ll mop2 = 998244353;

using namespace std;

constexpr ll NOT_SPECIFIED_VALUE_MIN = INT64_MIN;
constexpr ll NOT_SPECIFIED_VALUE_MAX = INT64_MAX;


int main()
{
	ll numNode, numEdge;
	cin >> numNode >> numEdge;
	vector<bool> discovered( numNode + 1, false );

	vector<vector<ll>> adjacentList(numNode + 1);
	for( ll i = 0; i < numEdge; i++ )
	{
		ll a, b;
		cin >> a >> b;
		adjacentList[a].push_back( b );
		adjacentList[b].push_back( a );
	}

	ll largestGroupSize = 0;
	for( ll i = 1; i <= numNode; i++ )
	{
		if( discovered[i] == true )
		{
			continue;
		}

		ll tmpGroupSize = 0;
		queue<ll> Q;
		Q.push( i );
		discovered[i] = true;
		tmpGroupSize++;
		while( !Q.empty() )
		{
			ll nowNode = Q.front();
			Q.pop();
			for( auto adjacent : adjacentList[nowNode] )
			{
				if( discovered[adjacent] == false )
				{
					Q.push( adjacent );
					discovered[adjacent] = true;
					tmpGroupSize++;
				}
			}
		}
		if( tmpGroupSize > largestGroupSize )
		{
			largestGroupSize = tmpGroupSize;
		}
	}
	cout << largestGroupSize << endl;

}


Measured memory_bytes: 17024
meshi = []
(0..4).each do |i|
  meshi[i] = gets.chomp.to_i
end

meshi.sort! do |a,b|
  ret = 0
  if a % 10 == 0
    ret = -1
  elsif a % 10 != 0 && b % 10 == 0
    ret = 1
  elsif (a % 10) > (b % 10)
    ret = -1
  elsif (a % 10) < (b % 10)
    ret = 1
  end
  ret == 0 ? a <=> b : ret
end

sumtime = 0

(0..4).each do |i|
  sumtime += meshi[i]
  sumtime += 10 - (meshi[i] % 10) if meshi[i] % 10 != 0 && i != 4
end

puts sumtime

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define mod 10e9+7

#define rep(i,n) for(int i=1;i<=n;i++)
int main(){
   int n;
   ll all=0;
   cin >> n;
   vector <int> a(n);
   for(int i=0;i<n;i++){
       cin >> a.at(i);
   }
   sort(a.begin(),a.end());
   a.at(n-1)=a.at(n-1)/2;
   for (int i=0;i<n;i++){
       all+=a.at(i);
   }
    cout << all << endl;
  }



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

int main() {
  int N,a;
  cin>>N;
  a=0;
  for(int i=1; i<N+1;i++){
    for(int j=1; i*j<N+1; j++){
      if(N-i*j>0)
        a++;
    }
  }
  cout<<a<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
using namespace std;

int main() {
    int H ,W;
    cin >> H >> W;
    vector<string> map;
    for(int i = 0; i < H; ++i)
    {
        string row;
        cin >> row;
        map.push_back(row);
    }
    vector<vector<int>> L(H, vector<int>(W, 0));
    vector<vector<int>> R(H, vector<int>(W, 0));
    vector<vector<int>> T(H, vector<int>(W, 0));
    vector<vector<int>> B(H, vector<int>(W, 0));
    for(int i = 0; i < H; ++i)
    {
        for(int j = 0; j < W; ++j)
        {
            int li = j - 1;
            if(li >= 0 && map[i][li] == '.')
            {
                L[i][j] =  L[i][li] + 1;
            }
        }
        for(int j = W - 1; j >= 0; --j)
        {
            int ri = j + 1;
            if(ri < W && map[i][ri] == '.')
            {
                R[i][j] = R[i][ri] + 1; 
            }
        }
    }

    for(int j = 0; j < W; ++j)
    {
        for(int i = 0; i < H; ++i)
        {
            int ti = i - 1;
            if(ti >= 0 && map[ti][j] == '.')
            {
                T[i][j] = T[ti][j] + 1;
            }
        }
        for(int i = H - 1; i >= 0; --i)
        {
            int bi = i + 1;
            if(bi < H && map[bi][j] == '.')
            {
                B[i][j] = B[bi][j] + 1;
            }
        }
    }

    int maxpoint = 0;
    for(int i = 0; i < H; ++i)
    {
        for(int j = 0; j < W; ++j)
        {
            if(map[i][j] == '#')
            {
                continue;
            }
            int point = 1 + L[i][j] + R[i][j] + T[i][j] + B[i][j];
            if(point > maxpoint)
            {
                maxpoint = point;
            }
        }
    }
    cout << maxpoint;
}

Measured memory_bytes: 67072
//“Make it work, make it right, make it fast.” – Kent Beck
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int siz = 1e6 + 5;
const int MOD = 1e9 + 7;
#define endl '\n'
#define deb(x) cout << #x << " = " << x << endl;

void solve(){
	ll n, k;
	cin >> n >> k;
	ll mod = n%k;
	if(n == 0)
		cout << 0;
	else if(abs(mod-k) < mod)
		cout << abs(mod-k);
	else
		cout << mod;
}

int main(){
	#ifndef RAY
		//freopen("input.txt", "r", stdin);
	#endif
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		int t = 1;
		//cin >> t;
		while(t--){
			solve();
		}
	return 0;
}	
	


Measured memory_bytes: 256
S = list(input())
ACGT = ["A", "C", "G", "T"]
count = 0
Max = 0
if len(S) == 1:
    if  S[0] in ACGT:
        print(1)
    else:
        print(0)
else:
    for s in S:
        if s in ACGT:
            count += 1
            if count > Max:
                Max = count
        else:
            if count > Max:
                Max = count
            count = 0
    print(Max)

Measured memory_bytes: 8924
//  Copyright 2020 Nikita Golikov

#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;
using ui64 = uint64_t;

template <class A, class B>
bool smin(A &x, B &&y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A &x, B &&y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

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

  int pw = 1;
  while (pw < m) pw *= 2;
  int const INF = (int) 1e9;
  struct node {
    int sum{};
    int min_sum{};
    int lazy = INF;

    node operator+(node const& other) const {
      return {sum + other.sum, min({0, min_sum, sum + other.min_sum}), INF};
    }
  };
  vector<node> tree(2 * pw);
  auto apply = [&](int v, int l, int r, int val) {
    if (val == INF) return;
    tree[v].sum = (r - l) * val;
    tree[v].min_sum = min(0, tree[v].sum);
    tree[v].lazy = val;
  };
  auto push = [&](int v, int l, int mid, int r) {
    apply(2 * v, l, mid, tree[v].lazy);
    apply(2 * v + 1, mid, r, tree[v].lazy);
    tree[v].lazy = INF;
  };
  auto Set = [&](int ql, int qr, int val) {
    auto go = [&](auto&& go, int v, int l, int r) -> void {
      if (l >= qr || ql >= r) return;
      if (ql <= l && r <= qr) {
        apply(v, l, r, val);
        return;
      }
      int mid = (l + r) / 2;
      push(v, l, mid, r);
      go(go, 2 * v, l, mid);
      go(go, 2 * v + 1, mid, r);
      tree[v] = tree[2 * v] + tree[2 * v + 1];
    };
    go(go, 1, 0, pw);
  };
  auto Get = [&](int ql, int qr) {
    auto go = [&](auto&& go, int v, int l, int r) -> node {
      if (ql >= r || l >= qr) return node();
      if (ql <= l && r <= qr) return tree[v];
      int mid = (l + r) / 2;
      push(v, l, mid, r);
      return go(go, 2 * v, l, mid) + go(go, 2 * v + 1, mid, r);
    };
    return go(go, 1, 0, pw);
  };

  int min_val = 0;
  int start = 0;
  auto Get_single = [&](int i) {
    assert(i >= start);
    return min_val + Get(start + 1, i + 1).sum;
  };
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    if (r >= start) {
      if (l <= start) {
        if (r + 1 == m) {
          start = m;
        } else {
          min_val = Get_single(r + 1);
          start = r + 1;
        }
      } else {
        if (r + 1 != m) {
          auto v_end = Get_single(r + 1);
          auto v_bef = Get_single(l - 1) + (r - (l - 1));
          Set(r + 1, r + 2, v_end - v_bef);
        }
        Set(l, r + 1, 1);
      }
    }
    ++min_val;
    cout << (start == m ? -1 : min_val + Get(start + 1, m).min_sum) << '\n';
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}


Measured memory_bytes: 9184
import heapq
X = list(map(int, input().split()))
# A = list(map(int, input().split()))
A = list(map(lambda x: int(x)*(-1), input().split())) # 最大値を取るために各要素を-1倍
heapq.heapify(A)

for i in range(X[1]):
  x = heapq.heappop(A) * (-1) # 最大値の取り出し
  heapq.heappush(A, int(x/2) * (-1))

ans = 0
for i in range(X[0]):
  ans -= A[i]

print(ans)

Measured memory_bytes: 14184
while(True):
    n,x = [int(i) for i in input().split()]
    if(n == 0 and x == 0):
        break
    t = 0
    for i in range(1,n + 1):
        for j in range(1,n + 1):
            for k in range(1,n + 1):
                if(i < j < k and i + j + k == x):
                    t += 1
    print(t)

Measured memory_bytes: 7720
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

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

    ll res = 0;
    for(ll i=0; i<=sqrt(n); i++){
       res = max(res, i*i); 
    }

    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProblemC
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var As = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var gcdFirstXNums = new int[N];
            var gcdLastXNums = new int[N];
            gcdFirstXNums[0] = As[0];
            gcdLastXNums[0] = As[N - 1];
            for (int i = 1; i < As.Length; i++)
            {
                gcdFirstXNums[i] = Gcd(gcdFirstXNums[i - 1], As[i]);
                gcdLastXNums[i] = Gcd(gcdLastXNums[i - 1], As[N - 1 - i]);
            }
            var gcds = new int[N];
            gcds[0] = gcdLastXNums[N - 2];
            gcds[N - 1] = gcdFirstXNums[N - 2];
            for (int i = 1; i < As.Length - 1; i++)
            {
                gcds[i] = Gcd(gcdFirstXNums[i - 1], gcdLastXNums[N - 1 - (i + 1)]);
            }
            Console.WriteLine(gcds.Max());
        }

        public static int Gcd(int a, int b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
    }
}


Measured memory_bytes: 27356
N = gets.to_i
V = gets.split.map(&:to_i)

odd = Hash.new(0)
even = Hash.new(0)

V.each_with_index do |v, i|
  if i.even?
    even[v] += 1
  else
    odd[v] += 1
  end
end

odd = odd.sort_by { |v, cnt| -cnt }
even = even.sort_by { |v, cnt| -cnt }

def cnt(list1, list2)
  ans = 0
  n, cnt = list1.first

  ans += N / 2 - cnt

  d2 = list2.find { |m, cnt| m != n }

  if d2
    ans + N / 2 - d2.last
  else
    ans + N / 2
  end
end

ans = [cnt(odd, even), cnt(even, odd)].min
puts ans



Measured memory_bytes: 20332
def p(t):
    for r in t:
        for c in r:
            print(c,end="")
        print("")
        
a = int(input())
for j in range(a):
    n = int(input())
    t = [ [ " " for _ in range(n) ] for _ in range(n)]
    d = 1 # 0:up, 1:right, 2:down, 3:left

    for i in range(n):
        t[i][0] = "#"

    x = 0
    y = 0
    for m in range(n-1):
        l = n - 1 - (m//2)*2
        for i in range(l):
            if d == 0:
                y -= 1
            elif d == 1:
                x += 1
            elif d == 2:
                y += 1
            elif d == 3:
                x -= 1
                
            t[y][x] = "#"

        d = (d + 1) % 4
    p(t)
    if j != a-1:
        print("")

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

using namespace std;
typedef pair<int,int> ii;
int R,C,n;
stack<int> q;

int ID(int x,int y)
{
    if(y==0)
        return x;
    else if(x==R)
        return R + y;
    else if(y==C)
        return R + C + (R-x);
    return 2*R + C + (C-y);
}

signed main()
{
    cin>>R>>C>>n;
    vector<ii> vivukhue;

    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1!=0&&x1!=R&&y1!=0&&y1!=C)
            continue;
        if(x2!=0&&x2!=R&&y2!=0&&y2!=C)
            continue;
        vivukhue.push_back(ii(ID(x1,y1),i));
        vivukhue.push_back(ii(ID(x2,y2),i));
    }
    sort(vivukhue.begin(),vivukhue.end());

    for(ii i:vivukhue)
    {
        if(!q.empty())
        {
            if(q.top()==i.second)
            {
                q.pop();
            }
            else
                q.push(i.second);
        }
        else
            q.push(i.second);
    }

    if(q.empty())
        cout<<"YES";
    else
        cout<<"NO";
}


Measured memory_bytes: 2420
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ll n; cin >> n;
    int s = 0;
    ll tmp = n;
    while (tmp > 0) {
        s += tmp % 10;
        tmp /= 10;
    }
    cout << ((n % s == 0)? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
# aで読む冊数を固定して、bで何冊読めるか考える
# 累積和にしておく、読めるbの冊数は2分探索で求める
# 計算時間はO(N*logM)


import itertools
import bisect

n, m, k = map(int, (input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.insert(0, 0)
b.insert(0, 0)

# aとbの累積和を計算
# accumulateオブジェクトをリストに変換
a_cumsum = list(itertools.accumulate(a))
b_cumsum = list(itertools.accumulate(b))


# 読める本の冊数を記録しておくリスト
books = []


# aの冊数を0冊~最大までそれぞれ固定して、bの冊数を求める
for i in range(len(a_cumsum)):
    minutes = 0
    numbers = 0

    a_minutes = a_cumsum[i]  
    minutes += a_minutes
    
    if minutes <= k:

        # aの冊数を計算
        numbers += i

        # 残り時間
        rest_minutes = k - a_minutes
        
        # bの冊数を計算
        if b_cumsum[-1] == rest_minutes:
            b_books = len(b_cumsum) - 1
        else:
            # bisect.bisect_rightは、リストのどこに数値を入れ込めるかのインデックスを返す（右の）
            b_books = bisect.bisect_right(b_cumsum, rest_minutes)
            b_books -= 1
    
        numbers += b_books
    
    books.append(numbers)

print(max(books))

Measured memory_bytes: 50780
//BROWNIE TK

#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front()

#define si size()
#define be begin()
#define en end()
#define all(v) v.be, v.en

#define le length()
#define mp make_pair
#define mt make_tuple
#define acc(v) accumulate(all(v), 0)
#define F first
#define S second

#define pll pair<lli, lli>
#define pii pair<int, int>
#define pil pair<int, lli>

#define forz(i, n) for (int i = 0; i < n; i++)
#define fore(i, m, n) for (int i = m; i <= n; i++)
#define rforz(i, n) for (int i = n - 1; i >= 0; i--)
#define rfore(i, m, n) for (int i = n; i >= m; i--)

#define deci(n) fixed << setprecision(n)
#define high(n) __builtin_popcount(n)
#define highll(n) __builtin_popcountll(n)
#define parity(n) __builtin_parity(n)
#define ctz(n) __builtin_ctz(n)

#define bset(a, p) ((a) | (1ll << (p)))
#define bchk(a, p) ((a) & (1ll << (p)))
#define bxor(a, p) ((a) ^ (1ll << (p)));
#define brem(a, p) (bchk(a, p) ? (bxor(a, p)) : (a))
/*SOME BITMASK KNOWLEDGE
1)x & (x - 1):sets the last one bit of x to zero
power of two exactly when x & (x − 1) = 0.
2)x & -x:sets all the one bits to zero, except last one bit
3)x | (x - 1):inverts all the bits after the last one bit*/

#define lb lower_bound
#define ub upper_bound
#define er equal_range

#define findnot find_first_not_of

#define maxe *max_element
#define mine *min_element

#define mod 1000000007
#define mod2 998244353
#define gcd __gcd
#define kira ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetlli tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements sbtriectly lesser than k
//2. find_by_order(k) : k-th element in the set
#define ofk order_of_key
#define fbo find_by_order
using namespace std;

/*STD funcions*/
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli modi(lli a, lli m) { return power(a, m - 2, m); }
/*CODE BEGINS*/
const int N=2e5+5;
lli cnt[N];
int main()
{
    kira;
    lli n;
    cin>>n;
    lli a[n];
    lli s=0,c=0;
    forz(i,n)
    {
        cin>>a[i];
    }
    forz(i,n)
    {
        lli t=(a[i]-1)*(a[i])/2;
        if(cnt[a[i]]==0&&s==t)
        {
            c++;
            s+=a[i];
            cnt[a[i]]++;
        }
    }
    if(c==0)
    {
        cout<<-1;
        return 0;
    }
    cout<<n-c;
    return 0;
}

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

#define f first
#define s second
#define mp make_pair
#define all(x) x.begin(), x.end()

#define EPS 1e-9

#define X real()
#define Y imag()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using point = pair<double, double>;
using Vector = complex<double>;
int main() {

	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll a, b, n;
	cin >> n >> a >> b;
	ll k = n / (a + b);
	cout << k * a + min(n % (a + b), a) << '\n'; 
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	int ans=0,ba=0;
	cin>>s;
	s+='S';
	for(int t=0;t<4;t++)
	{
		if(s[t]=='R')
		{
			ba++;
		}
		else
		{
			ans=max(ba,ans);
			ba=0;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3596
class BinaryTree
	class Node
		attr_accessor :parent, :left, :right, :depth, :height

	end

	def initialize
		@nodes = []
	end

	def add(id, left, right)
		@nodes[id] ||= Node.new
		@nodes[id].left  = left
		@nodes[id].right = right

		if left != -1
			@nodes[left] ||= Node.new
			@nodes[left].parent = id
		end

		if right != -1
			@nodes[right] ||= Node.new
			@nodes[right].parent = id
		end

		self
	end

	def preorder
		preorder_helper(find_root)
	end

	def inorder
		inorder_helper(find_root)
	end

	def postorder
		postorder_helper(find_root)
	end

	private
	def exist?(id)
		id && id != -1
	end

	def find_root
		@nodes.find_index { |node| node.parent == nil }
	end

	def preorder_helper(id)
		node = @nodes[id]
		result = [id]

		result.concat(preorder_helper(node.left)) if exist?(node.left)
		result.concat(preorder_helper(node.right)) if exist?(node.right)
		result
	end

	def inorder_helper(id)
		node = @nodes[id]
		result = []

		result.concat(inorder_helper(node.left)) if exist?(node.left)
		result << id
		result.concat(inorder_helper(node.right)) if exist?(node.right)
		result
	end

	def postorder_helper(id)
		node = @nodes[id]
		result = []

		result.concat(postorder_helper(node.left)) if exist?(node.left)
		result.concat(postorder_helper(node.right)) if exist?(node.right)
		result << id
	end

end

tree = BinaryTree.new
n = STDIN.gets.to_i
n.times do
	id, left, right = STDIN.gets.split[0..2].map(&:to_i)
	tree.add(id, left, right)
end

puts "Preorder"
puts " #{tree.preorder.join(" ")}"
puts "Inorder"
puts " #{tree.inorder.join(" ")}"
puts "Postorder"
puts " #{tree.postorder.join(" ")}"

Measured memory_bytes: 6132
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x, y;
	cin >> x >> y;
	int ans = 0;
	while(x <= y){
		x *= 2;
		++ans;
	}
	cout << ans << endl;
	return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll a,b;
    cin >> a >> b;
    if(a <= 9 && b <= 9) cout << a*b << endl;
    else  cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main(){
    int h,w;
    cin>>h>>w;
    vector<string>grid(h);
    vector<vector<ll>>d(h+5,vector<ll>(w+5,0));
    d[0][0]=1;
    rep(i,h)cin>>grid[i];
    rep(i,h)rep(j,w){
        if(i+1<h&&grid[i+1][j]!='#'){
            d[i+1][j]+=d[i][j];
            d[i+1][j]%=mod;
        }
        if(j+1<w&&grid[i][j+1]!='#'){
            d[i][j+1]+=d[i][j];
            d[i][j+1]%=mod;
        }
    }
    cout<<d[h-1][w-1]<<endl;
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>
using namespace std;
constexpr char nl = '\n';
using ll = long long;
using boost::irange;
namespace rng {
    using namespace boost;
    using namespace boost::range;
    using namespace boost::adaptors;
}

struct init_ { init_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } init_;

template<class C> auto operator>>(istream& in, C& c) -> typename enable_if<!is_void<decltype(c.begin())>::value && !is_same<C, string>::value, istream&>::type {
    for (auto& v : c) { in >> v; } return in; }
template<class C> auto operator<<(ostream& out, const C& c) -> typename enable_if<!is_void<decltype(c.begin())>::value && !is_same<C, string>::value, ostream&>::type {
    int i = 0; for (const auto& v : c) { if (i++) { out << ' '; } out << v; } return out; }
template<size_t N, class T, class R> using when_last = typename enable_if<N == tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N, class T, class R> using when_init = typename enable_if<N != tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_last<N, T, istream&> { return in >> get<N>(t); }
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_init<N, T, istream&> { return operator>><N + 1>(in >> get<N>(t), forward<T>(t)); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_last<N, T, ostream&> { return out << get<N>(t); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_init<N, T, ostream&> { return operator<<<N + 1>(out << get<N>(t) << ' ', t); }

#ifdef LOCAL
constexpr auto color_s_ = "\033[2m\033[33m", color_e_ = "\033[0m";
template<class T> void trace_(const T& v) { cerr << v; }
template<class T> void trace_(const vector<vector<T>>& m) { cerr << "\n"; for (const auto& v : m) { trace_(v); cerr << "\n"; } }
template<class T> void trace_(const char* s, const T& v) { cerr << color_s_ << s << "="; trace_(v); cerr << color_e_ << "\n"; cerr.flush(); }
template<class T, class... Ts> void trace_(const char* s, const T& v, const Ts&... vs) { cerr << color_s_; for (; *s != ','; ++s) { cerr << *s; } cerr << "="; trace_(v); cerr << ","; trace_(++s, vs...); }
#define TRACE(...) trace_(#__VA_ARGS__, __VA_ARGS__)
#else
#define TRACE(...)
#endif

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while (true) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << nl;
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << nl;
            return 0;
        }
    }
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const ll INF = 1010101010;
int dp[3][101010];

int max_3(int x, int y, int z){
  if(x>=y&&x>=z) return x;
  else if(y>=z&&y>=x) return y;
  else return z;
}

int main(){
  int n;
  cin >> n ;
  vector<int> a(n), b(n), c(n);
  rep(i,n) cin >> a[i] >> b[i] >> c[i];
  rep(i,n+1){
    rep(j,3){
      if(i==0) continue;
      dp[j][i] = INF;
    }
  }
  rep(i,n){
    dp[0][i+1] = max(dp[1][i],dp[2][i]) + a[i];
    dp[1][i+1] = max(dp[0][i],dp[2][i]) + b[i];
    dp[2][i+1] = max(dp[1][i],dp[0][i]) + c[i];
  }
  /*rep(i,n+1){
    rep(j,3){
      cout << dp[j][i] << " ";
    }
    cout << endl;
  }*/
  int ans = max_3(dp[0][n],dp[1][n],dp[2][n]);
  cout << ans << endl;
}

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

int main()
{
    long long int w, h;
    cin >> h >> w;

    long long int tot = w*h;

    long long int ans = tot/2;
    if(tot%2) ans++;

    if(h == 1 || w == 1) ans = 1;

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100015
#define INF 1000000005LL
#define MOD 1000000007

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

int N,M;

//Union-Find 頂点数SIZE
struct unode{
  int par,rank,size;
};
unode T[SIZE];

void init(int n){
  rep(i,0,n){
    T[i].par = i;
    T[i].rank = 0;
    T[i].size = 1;
  }
}

int find(int x){
  if(T[x].par == x){
    return x;
  }else{
    return T[x].par = find(T[x].par);
  }
}

ll unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x==y)return 0;

  ll u;
  if(T[x].rank < T[y].rank){
    T[x].par = y;
    u = ((ll)T[y].size * (ll)T[x].size);
    T[y].size += T[x].size;
  }else{
    T[y].par = x;
    if(T[x].rank == T[y].rank) T[x].rank++;
    u = ((ll)T[y].size * (ll)T[x].size);
    T[x].size += T[y].size;
  }
  return u;
}

bool same(int x,int y){
  return find(x) == find(y);
}

int getSize(int x){
  return T[T[x].par].size;
}

P E[SIZE];
ll a[SIZE];

int main(){
  cin >> N >> M;
  rep(i,0,M) cin >> E[i].first >> E[i].second;
  reverse(E,E+M);
  init(N+5);
  rep(i,0,M){
    a[i] = unite(E[i].first,E[i].second);
  }
  reverse(a,a+M);
  rep(i,0,M-1){
    a[i+1] += a[i];
  }
  rep(i,0,M) cout << a[i] << endl;

  return 0;
}


Measured memory_bytes: 4096
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2 + 2], R[MAX/2 + 2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    for(int i = 0; i < n1; ++i) L[i] = A[left + i];
    for(int i = 0; i < n2; ++i) R[i] = A[mid + i];
    L[n1] = R[n2] = SENTINEL;
    int i = 0, j = 0;
    for(int k = left; k < right; ++k){
         ++cnt;
         if(L[i] <= R[j]) A[k] = L[i++];
         else A[k] = R[j++];
    }
}

void MergeSort(int A[], int n, int left, int right){
     if(left + 1 < right){
          int mid = (left + right) / 2;
          MergeSort(A, n, left, mid);
          MergeSort(A, n, mid, right);
          merge(A, n, left, mid, right);
    }
}

int main(void){
    int A[MAX], n, i;
    cnt = 0;

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

    MergeSort(A, n, 0, n);

    for( i = 0; i < n; ++i){
       if( i ) cout << " ";
       cout << A[i];
    }
    cout << endl;

    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 6968
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
char s[MAX],t[MAX];
int main()
{
    int arr[3];
    int i;
    for(i=0;i<3;i++)
    {
        scanf("%d",&arr[i]);
    }
    int K;
    scanf("%d",&K);
    int ans=0;
    for(i=0;i<3&&K>0;i++)
    {
        if(K>=arr[i])
        {
            ans=ans+(1-i)*arr[i];
            K=K-arr[i];
        }
        else
        {
            ans=ans+(1-i)*K;
            K=0;
        }
    }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 3828
#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int N = 2e5 + 12;
ll a[N],b[N],mx = 1e18,sum;
int n;
int main()
{
   scanf("%d",&n);
   for(int i = 1;i <= n;i++)scanf("%lld %lld",&a[i],&b[i]),mx = a[i] > b[i] ? min(mx,b[i]) : mx,sum += a[i];
   printf("%lld\n",max(0LL,sum - mx));
}

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

typedef long long ll;
typedef pair<int,int> P;

#define fr first
#define sc second

int main(){
	static int n,k;
	static string s;
	cin >> n >> k >> s;
	
	char c = 'z';
	for(int i = 0 ; i < s.size() ; i ++){
		c = min( c , s[i] );
	}
	if(k >= 14){
		string ret = "";
		for(int i = 0 ; i < n ; i ++){
			ret += c;
		}
		cout << ret << endl;
		return 0;
	}
	
	int l = 0;
	vector<int> vec;
	string u = s;
	reverse(s.begin(),s.end());
	u += s;
	//cout << u << endl;
	for(int i = 0 ; i < u.size() ; i ++){
		int j = i;
		while(j < u.size() && u[j] == c)j ++;
		if(l < j-i){
			l = j-i;
			vec.clear();
			vec.push_back(i);
		}
		else if(l == j-i){
			vec.push_back(i);
		}
	}
	int x = (1<<(k-1))*l;
	if(x >= n){
		string ret = "";
		for(int i = 0 ; i < n ; i ++){
			ret += c;
		}
		cout << ret << endl;
		return 0;
	}
	
	/*cout << x << endl;
	for(int i = 0 ; i < vec.size() ; i ++){
		cout << vec[i] << endl;
	}*/
	
	string ret = "";
	for(int i = 0 ; i < vec.size() ; i ++){
		int id = vec[i];
		if(id < n-l)continue;
		string ret_ = "";
		for(int j = id-1 ; j >= id-(n-x) ; j --){
			ret_ += u[j];
		}
		if(ret == "")ret = ret_;
		else {
			for(int j = 0 ; j < n-x ; j ++){
				if(ret[j] < ret_[j])break;
				else if(ret[j] > ret_[j]){
					ret = ret_;
					break;
				}
			}
		}
	}
	for(int i = 0 ; i < x ; i ++){
		printf("%c",c);
	}
	cout << ret << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define X first
#define Y second
using namespace std;
pair<long long,int> d[200000];
int main(){
	int n,ans=0,cnt=0;
	cin>>n>>d[0].X;
	d[0].Y=0;
	for(int i=1;i<n;i++){
		cin>>d[i].X;
		d[i].X+=d[i-1].X;
		d[i].Y=i;
	}
	sort(d,d+n);
	for(int i=1;i<n;i++){
		if(d[i].X==0)ans=max(ans,d[i].Y+1);
		if(d[i-1].X==d[i].X)cnt+=d[i].Y-d[i-1].Y;
		else cnt=0;
		ans=max(cnt,ans);
	}
	if(d[0].X==0)ans=max(ans,d[0].Y+1);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6144
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int aa=0,bb=0;
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for(int i=0;i<n;i++){
        if(i%2==0) aa+=a[i];
        else bb+=a[i];
    }
    cout<<aa-bb<<endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll solve(void);

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

ll solve(void)
{
	ll N, K;
	cin >> N >> K;

	if (K > N * (N-1) / 2 - (N-1)) { cout << -1 << endl; return 0;}

	ll num = (N-1)*(N-2) / 2;
	ll d = num - K;

	cout << d + (N - 1) << endl;

	ll cnt = 0;

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

	for (int i = 1; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (cnt >= d) { break; }
			cout << i + 1 << " " << j + 1 << endl;
			cnt ++;
		}
	}

	return 0;
}



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

int main() {
    int n, a, ret = 1, bef, pmz = 0;
    scanf("%d", &n);
    scanf("%d", &a); bef = a;
    for (int i = 1; i < n; i++) {
        if (pmz == 0) {
            if (bef == a) {
                // do nothing
            } else if (bef > a) {
                pmz = -1;
            } else { // bef < a
                pmz = 1;
            }
        } else {
            if (bef == a) {
                // do nothing
            } else if (bef > a) {
                if (pmz != -1) {pmz = 0; ret++;}
            } else { // bef < a
                if (pmz != 1) {pmz = 0; ret++;}
            }
        }
        bef = a;
        scanf("%d", &a);
    }

    if (pmz ==  0 &&  (bef == a) && n != 1) ret++; // for subtask_1_10.txt
    if (pmz ==  1 && !(bef <= a)) ret++;
    if (pmz == -1 && !(bef >= a)) ret++;

    printf("%d\n", ret);
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;
using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "YES" << '\n'; exit(0); }
inline void no() { cout << "NO" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline bool isprime(i32 n) { if (n < 2) return 0; for (i32 i = 2; i * i <= n; i++) if (n % i == 0) return 0; return 1; }
inline vi32 plist(i32 n) { vi32 f(n, 1); f[0] = f[1] = 0; repi(i, 2, n) for (int j = i * 2; j < n; j += i) f[j] = 0; return f; }
inline void ioinit() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); }
template<class T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template<class T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template<class T> inline bool amax(T &x, T y) { if (x >= y) return 0; x = y; return 1; }
template<class T> inline bool amin(T &x, T y) { if (x <= y) return 0; x = y; return 1; }
template<class T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<class T> vector<T> make_v(int n, T v) { return vector<T>(n, v); }
template<class... Ts> auto make_v(int n, Ts... ts) { return vector<decltype(make_v(ts...))>(n, make_v(ts...)); }

int main() {
  ioinit();
  int h, w, n;
  cin >> h >> w >> n;
  int sr, sc;
  cin >> sr >> sc;
  string s, t;
  cin >> s >> t;
  {
    int ll = 0, rr = w + 1;
    rrep(i, n) {
      if (ll > 0 && t[i] == 'R') ll--;
      if (s[i] == 'L') ll++;
      if (ll == w) no();
    }
    rrep(i, n) {
      if (rr < w + 1 && t[i] == 'L') rr++;
      if (s[i] == 'R') rr--;
      if (rr == 1) no();
    }
    if (ll >= sc || rr <= sc) no();
  }
  {
    int ll = 0, rr = h + 1;
    rrep(i, n) {
      if (ll > 0 && t[i] == 'D') ll--;
      if (s[i] == 'U') ll++;
      if (ll == h) no();
    }
    rrep(i, n) {
      if (rr < h + 1 && t[i] == 'U') rr++;
      if (s[i] == 'D') rr--;
      if (rr == 1) no();
    }
    if (ll >= sr || rr <= sr) no();
  }
  yes();
  return 0;
}


Measured memory_bytes: 920
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }

int n;
char buf[114514];

int main() {
    scanf("%d", &n);
    vector<int> a(5);
    rep(i, n) {
        scanf("%s", buf);
        char c = buf[0];
        if (c == 'M') a[0]++;
        if (c == 'A') a[1]++;
        if (c == 'R') a[2]++;
        if (c == 'C') a[3]++;
        if (c == 'H') a[4]++;
    }

    ll ans = 0;
    rep(i, 1 << 5) {
        int pc = 0;
        rep(j, 5) if (i & (1 << j)) pc++;
        if (pc != 3) continue;
        ll x = 1;
        rep(j, 5) if (i & (1 << j)) x *= a[j];
        ans += x;
    }
    cout << ans << "\n";
    return 0;
}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  i64 n;
  cin >> n;

  vector<i64> a(n+1), b(n+1);
  reps(i, 1, n) cin >> a[i] >> b[i];

  i64 ans = 0;
  i64 v = 0;
  for (int i = n; i >= 1; --i) {
    a[i] += v;
    if (a[i] % b[i] == 0) continue;
    i64 tmp = b[i] * ((a[i] + b[i] - 1) / b[i]) - a[i];
    v += tmp;
    ans += tmp;
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <string.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 2147483647
#define LLINF 9223372036854775807
using namespace std;
int n,m,x;
long long c[20];
long long a[20][20];
long long mn=1e18;
long long p[20];
void dfs(vector<int> v){
	memset(p,0,sizeof(p));
	long long ppp=0;
	for(int i=0;i<v.size();i++){
		ppp+=c[v[i]];
		for(int j=0;j<m;j++){
			p[j]+=a[v[i]][j];
		}
	}
	bool flag=0;
	for(int i=0;i<m;i++){
		if(p[i]<x)flag=1;
	}
	if(!flag){
		mn=min(mn,ppp);
		return ; 
	}
	if(v.empty()){
		for(int i=0;i<n;i++){
			v.push_back(i);
			dfs(v);
			v.erase(v.begin()+v.size()-1);
		}
	}
	else{
		for(int i=v[v.size()-1]+1;i<n;i++){
			v.push_back(i);
			dfs(v);
			v.erase(v.begin()+v.size()-1);
		}
	}
}
int main(){
	cin>>n>>m>>x;
	for(int i=0;i<n;i++){
		cin>>c[i];
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<m;i++){
		bool flag=0;
		for(int j=0;j<n;j++){
			if(a[j][i]!=0)flag=1;
		}
		if(!flag){
			cout<<"-1"<<endl;
			return 0;
		}
	}
	vector<int> vvvvvvvvvvv;
	dfs(vvvvvvvvvvv);
	if(mn==1e18)cout<<"-1"<<endl;
	else cout<<mn<<endl;
	return 0;
}

Measured memory_bytes: 3636
# coding: utf-8

import sys
input = sys.stdin.readline

N = int(input())
# L = [int(x) for x in input().split()]
# N, K = map(int, input().split())

AB  = 0
xA = 0
BxA = 0
Bx = 0

for _ in range(N) :
    S = input()

    AB += S.count("AB")

    if S[0] + S[-2] == "BA" :
        BxA += 1
    elif S[-2] == 'A' :
        xA += 1
    elif S[0] == 'B' :
        Bx += 1

if BxA == 0 :
    print(AB + min(xA, Bx))
elif BxA == 1 and xA <= 1 and Bx <= 1 :
    print(AB + xA + Bx)
elif BxA == 1 and (xA == 0 or Bx == 0) :
    print(AB + 1)
elif BxA == 1 :
    print(AB + min(xA - 1, Bx - 1) + 2)
elif xA <= 1 and Bx <= 1 :
    print(AB + xA + Bx + (BxA - 1))
elif xA == 0 or Bx == 0 :
    print(AB + BxA)
else :
    print(AB + min(xA - 1, Bx - 1) + 2 + (BxA - 1))


Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := intScanner()
	s := "X" + Scanner()
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, n+1)
	}
	ans := 0
	for i := 1; i < n+1; i++ {
		for j := i + 1; j < n+1; j++ {
			if s[i] == s[j] {
				dp[i][j] = smaller(dp[i-1][j-1]+1, j-i)
			} else {
				dp[i][j] = 0
			}
			ans = larger(dp[i][j], ans)
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 121500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int N, ans = 1; cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];
    bool up = false, down = false;
    rep(i, N - 1){
        if(A[i] < A[i + 1]) up = true;
        if(A[i] > A[i + 1]) down = true;
        if(up && down){
            up = false, down = false, ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N =sc.nextInt();
      
      int max =0;//aの中の最大値
      int b = 0;//合計
      for(int i=0; i<N; i++){
      int a =sc.nextInt();
        b = b+a;//入力したであろう値を合計している
        max = Math.max(max,a);//aの中の最大値
      }
      if(max<b-max){
      System.out.println("Yes");
      }
      else{
      System.out.println("No");
      }
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  struct Edge { int to, d; };
  VV<Edge> g(n);
  for (int i = 0; i < m; ++i) {
    int s, t, d; cin >> s >> t >> d;
    g[s].push_back({t, d});
    g[t].push_back({s, d});
  }
  VV<> d; assign(d, n, n, (int) 1e9);
  for (int i = 0; i < n; ++i) d[i][i] = 0;
  for (int v = 0; v < n; ++v) for (const auto& e : g[v]) d[v][e.to] = min(d[v][e.to], e.d);
  for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  V<> vs;
  for (int v = 0; v < n; ++v) if (g[v].size() & 1) vs.push_back(v);
  int N = vs.size();
  VV<> w; assign(w, 1 << N, N);
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) w[u][v] = d[vs[u]][vs[v]];
  V<> dp; assign(dp, 1 << N, (int) 1e9);
  if (N) dp[0] = 0;
  for (int bit = 1; bit < 1 << N; ++bit) for (int i = 0; i < N; ++i) if (bit & 1 << i) for (int j = 0; j < N; ++j) if (bit & 1 << j) {
    dp[bit] = min(dp[bit], dp[bit ^ 1 << i ^ 1 << j] + w[j][i]);
  }
  int res = 0;
  for (int v = 0; v < n; ++v) for (const auto& e : g[v]) if (v < e.to) res += e.d;
  if (N) res += dp.back();
  cout << res << '\n';
}


Measured memory_bytes: 4384
#include <iostream>
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <climits>
#include <cmath>

int main(void) {
  long long int X,Y;
  std::cin >> X >> Y;

  int count = 0;
  while(X <= Y) {
    X = X * 2;
    count++;
  }

  std::cout << count << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vivi vector<vi>
const int INF = int(1e9);
typedef long long int ll;
/* -- template -- */

int main(){
    int X, Y, Z, K; cin >> X >> Y >> Z >> K;
    ll A[X], B[Y], C[Z];
    rep(i, X)cin >> A[i];rep(i, Y)cin >> B[i];rep(i, Z)cin >> C[i];
    sort(A, A + X, greater<ll>());sort(B, B + Y, greater<ll>());sort(C, C + Z, greater<ll>());
    ll sumAB[X * Y];
    int count = 0;
    rep(i, X){
        rep(j, Y){
            sumAB[count] = A[i] + B[j];
            ++count;
        }
    }
    count = 0;
    sort(sumAB, sumAB + X*Y, greater<ll>());
    ll sumABC[K * Z];
    for(int i = 0;i < ((K < X * Y) ? K : X * Y);++i){
        for(int j = 0;j < Z;++j){
            sumABC[count] = sumAB[i] + C[j];
            ++count;
        }
    }
    sort(sumABC, sumABC + ((K < X * Y) ? K : X * Y) * Z, greater<ll>());
    rep(i, K)cout << sumABC[i] << endl;
}


Measured memory_bytes: 31616