akhauriyash/Code-Regression huggingface dataset:
class UnionFind:
    def __init__(self, n):
        self.v = [-1] * n

    def find(self, x):
        if self.v[x] < 0:
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

    ps = []
    xs = set()
    ys = set()
    for i in range(N):
        x, y = map(int, input().split())
        ps.append((x, y))
        xs.add(x)
        ys.add(y)

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, start):
        xes = []
        for i, (x0, x1) in enumerate(zip(xs, xs[1:]), start=start):
            xes.append((abs(x1 - x0), i, i + 1))
        return xes

    xes = make_edges(xs, start=0)
    yes = make_edges(ys, start=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 82388
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define all(a)                      a.begin(), a.end()
#define pb                          push_back
#define ll							long long
#define index(a)            		order_of_key(a)
#define value(a)					find_by_order(a)
#define count_1 					__builtin_popcount
#define mod(x, m)					((((x) % (m)) + (m)) % (m))
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
int mat[1005][1005];
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout<<setprecision(12);
	int n,m;
	cin>>n>>m;
	string s[n];
	for(int i=0;i<n;i++)cin>>s[i];

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i-1][j-1]=='#')mat[i][j]=0;
			else if(i==1 && j==1)mat[i][j]=1;
			else
			mat[i][j]=(mat[i-1][j]+mat[i][j-1])%int(1e9+7);
		}
	}

	cout<<mat[n][m];
	return 0;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
//#define vi vector<int>
#define vb vector<bool>
#define pii pair<int, int>
#define mii map<int, int>
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define tr(container, it) for (typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define inf (long long)1e18
#define F first
#define S second
#define SZ(x) ((int)(x).size())
//#define rep(i, n) for (int i = 0; i < n; i++)
//#define repd(i,n) for(int i=n-1;i>=0;i--)
//#define rep1(i,n) for(int i=1;i<=n;i++)
const int N = 1e9 + 7;

int pow(int x, int y)
{
    int res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = ((res) * (x));
        res %= N;
        y = y >> 1;
        x = ((x) * (x));
    }
    return res;
}
int powm(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

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

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

    ll mx = 0;
    ll p;
    ll sum = 0;
    for (ll i = 0; i < n; i++)
    {
        mx = max(a[i], mx);
        p = mx - a[i];
        if (p > 0)
            sum += p;
    }
    cout << sum;
}

int32_t main()

{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // int t;
    // cin >> t;
    // while (t--)
    // {
    solve();
    // }
}

Measured memory_bytes: 4768
S = input()
N = len(S)

def is_palindrome(s):
  return s == s[::-1]

if is_palindrome(S) \
and is_palindrome(S[:int((N-1)/2)]) \
and S[int((N+3)/2-1):] == S[:int((N-1)/2)]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
import scala.math._

object Main {
  val sc = new java.util.Scanner(System.in)
  def main(args: Array[String]) {
    val n = sc.nextInt()
    val p = new Array[Int](n+1)
    for(_ <- 1 to n*(n-1)/2) {
      val a, b, c, d = sc.nextInt()
      if(c < d) {
        p(b) += 3
      }
      if(c > d) {
        p(a) += 3
      }
      if(c == d) {
        p(a) += 1
        p(b) += 1
      }
    }
    for(i <- 1 to n) {
      println(p.filter(a => a > p(i)).size + 1)
    }
  }
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int N; cin >> N;
        string S; cin >> S;
        rep(i, S.size()) {
            int a = S[i] - 'A';
            a = (a + N) % ('Z' - 'A' + 1);
            S[i] = a + 'A';
        }
        cout << S << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>                                          
#include <cstdio>                                            
using namespace std;                                         
                                                             
int main(void) {                                             
  int H, W;                                                  
  while (true) {                                             
    cin >> H >> W;                                           
    if (H==0 && W==0) {                                      
      break;                                                 
    }                                                        
    for (int i=0; i<H; i++) {                                
      for (int j=0; j<W; j++) {                              
        if (i%2==0 && j%2==0 || i%2!=0 && j%2!=0) {          
          printf("#");                                       
        } else {                                             
          printf(".");                                       
        }                                                    
      }                                                      
      printf("\n");                                          
    }                                                        
    printf("\n");                                            
  }                                                          
  return 0;                                                  
}                                                            
                                                             
                       

Measured memory_bytes: 3044
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import math
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 一括読み
#N, K, *A = map(int, open(0).read().split())


# 整数の入力
#n = int(input())

# スペース区切り文字列の入力
#n, k = input().split()

# スペース区切りの整数の入力
n, k = map(int, input().split())
#n, x = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#a = [int(x) for x in input().split()]
#b = [int(x) for x in input().split()]
#print("a", a, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#b = []
#for x in range(m):
#  b.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#b = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def ton(n, k, x):
  s = ""
  while n > 0:
    s = str(n%k) + s
    n //= k
  return s


#print("a", a, file=sys.stderr)
#print("b", b, file=sys.stderr)

def getEnergy():
  for y in b:
    yield y

def doit():
  total = 0
  prev = " "
  for x in list(s):
    if prev == x:
      total += 1
    prev = x
  total += k*2
  if total >= n-1:
    return n-1
  return total

def yn():
  if doit():
    return "Yes"
  else:
    return "No"

#print(doit([0] * 4))
#doit()
#print(doit())
try:
  #doit()
  print(doit())
  #print(yn())
except Exception as e:
  print("e", e, file=sys.stderr)


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

long long min(long long x , long long y)
{
  if(x>y)
    return y;

  else
    return y;

}


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

  long long  n;
  cin>>n;

  vector<pair<int, int> >v;

  long long  x , y;
  long long min_moves = LLONG_MAX ;
  

  for(long long i=1 ; i<=sqrt(n) ; i++)
  {
    if(n%i == 0)
    {
      x = i;
      y = n/i;

      min_moves = min(min_moves , x+y-2);

    }
  }


  cout<<min_moves<<"\n";
 
  return 0;
} 



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

const ULL M = 1000000007;

ULL powm(ULL a, ULL i) {
    if (!i) return 1;
    if (i & 1) return powm(a * a % M, i >> 1) * a % M;
    return powm(a * a % M, i >> 1);
}

struct Problem {

    void Solve() {
        ULL N, K; cin >> N >> K;
        cout << powm(K, N) << endl;
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    p->Solve();
    return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<int, int> pii;
const int M = 2e5+7;
const ll MAX = 1e15;
const ll MOD = 1e9+7;

int n;
ii a[M];
ll b[M], c[M];

void solve() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1, a+1+n);
    reverse(a+1, a+1+n);
    b[n+1] = c[n+1] = MAX;
    for(int i=n; i>=1; i--) {
        b[i] = min(b[i+1], a[i].first + a[i].second);
        c[i] = min(c[i+1], a[i].first - a[i].second);
    }
    ll ans = 0;
    for(int i=1; i<=n; i++) {
        ans = max(ans, a[i].first + a[i].second - b[i+1]);
        ans = max(ans, a[i].first - a[i].second - c[i+1]);
    }
    cout<<ans;
}

int main() {
    ios::sync_with_stdio(0);
   // freopen("input.txt","r",stdin);
    if(0) {
        int t;
        cin>>t;
        for(int i=1; i<=t; i++) {
            solve();
            cout<<"\n";
        }
    } else solve();
    return 0;
}


Measured memory_bytes: 9908
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_f(const void *a, const void *b) {
	return *((size_t *)a) < *((size_t *)b) ? -1 : 1;
}

static size_t comb(const size_t n, const size_t r) {
	size_t result = 1;

	for (size_t i = 0; i < r; i++) {
		result *= n - i;
		result /= i + 1;
	}

	return result;
}

static uint64_t gcd(uint64_t m, uint64_t n)
{
	uint64_t temp;

	while (m%n != 0) {
		temp = n;
		n = m % n;
		m = temp;
	}

	return n;
}

int main(void) {
	uint64_t A, B;

	scanf("%"PRIu64" %"PRIu64, &A, &B);
	B++;

	uint64_t result = 0;

	while (A % 4 != 0 && A < B) {
		result ^= A;
		
		A++;
	}

	A += ((B - A) / 4) * 4;

	while (A < B) {
		result ^= A;

		A++;
	}

	printf("%"PRIu64, result);

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define show(x) cout << #x << " = " << (x) << endl;
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl;
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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

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

  ll nx = 1, ny = 1;
  rep(i,n) {
    ll t, a;
    cin >> t >> a;
    ll m = max(dup(nx,t), dup(ny,a));
    nx = m*t, ny = m*a;
  }

  cout << nx + ny << endl;
  return 0;
}

Measured memory_bytes: 256
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextFloat64() (float64, error) {
	return strconv.ParseFloat(nextString(), 64)
}

func main() {
	scanner.Split(bufio.ScanWords)

	a, _ := nextFloat64()
	b, _ := nextFloat64()
	theta, _ := nextFloat64()

	h := b * math.Sin(theta/180.0*math.Pi)

	fmt.Println(0.5 * a * h)
	fmt.Println(a + b + math.Sqrt(h*h+math.Pow(a-b*math.Cos(theta/180.0*math.Pi), 2)))
	fmt.Println(h)
}



Measured memory_bytes: 1160
# abc106_a.py
# https://atcoder.jp/contests/abc106/tasks/abc106_a

# A - Garden /
# 実行時間制限: 2 sec / メモリ制限: 1000 MB
# 配点: 100点

# 問題文
# 縦 Aヤード、横 B ヤードの畑がある. 
# 農夫ジョンは, 畑の内部に, 畑の上端と下端を結ぶ縦方向の幅 1 ヤードの道, 畑の左端と畑の右端を結ぶ横方向の幅 1ヤードの道を作った. 
# 畑は下図のようになっている. (灰色の部分が道)
# さて, 道を除いた畑の面積は, 何平方ヤードだろうか? 求めなさい.

# 注意
# 道の位置が変わっても, 道を除く畑の面積が変わらないことが証明できます.

# 制約
#     Aは 2 以上 100以下の整数
#     Bは 2 以上 100以下の整数

# 入力
# 入力は以下の形式で標準入力から与えられる.
# A B

# 出力
# 道を除いた畑の面積 (平方ヤード) を出力しなさい.

# 入力例 1
# 2 2

# 出力例 1
# 1

# この場合, 面積は 1平方ヤードになる.

# 入力例 2
# 5 7

# 出力例 2
# 24

# この場合, 面積は 24平方ヤードになる. 


def calculation(lines):
    A, B = list(map(int, lines[0].split()))
    return [(A-1)*(B-1)]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 2']
        lines_export = [1]
    if pattern == 2:
        lines_input = ['5 7']
        lines_export = [24]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


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

int main (){
    int a, b, c ,d;
    cin >> a >> b >> c >>d;
    if((a+b)>(c+d)){
        cout << "Left";
    }else if((a+b)<(c+d)){
        cout << "Right";
    }else{
        cout << "Balanced";
    }
}


Measured memory_bytes: 256
n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    disxi = min(abs(x-1-i), abs(y-1-i))
    for j in range(i+1, n):
        a = j-i
        if a == 1:
            dist = 1
        else:
            b = disxi + 1 + min(abs(y-1-j), abs(x-1-j))
            dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)

Measured memory_bytes: 3444
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let it = stdin.lock().bytes().map(|c| c.unwrap() as char);
    let (fs, ft) = (|c: &char| c.is_whitespace(), |c: &char| !c.is_whitespace());
    let token = it.skip_while(fs).take_while(ft).collect::<String>();
    token.parse().ok().unwrap()
}
#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    f(std::io::BufWriter::new(out.lock()));
}
#[allow(unused_macros)]
macro_rules! debug {
    ($($var:expr),*) => { #[cfg(debug_assertions)] {
        $({ match &$var { v => eprint!("{}={:?} ", stringify!($var), v) } })*
        eprintln!();
    }};
}

fn main() {
    let n: usize = input();
    let a: Vec<i32> = (0..n).map(|_| input()).collect();

    let mut ans = 0;
    for mut a in a {
        while a % 2 == 0 {
            a /= 2;
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

static const int MAX_LEN = 36;

void output_array(array<string, MAX_LEN> arr, int arr_len)
{
  cout << arr.at(0);
  for (int i = 1; i < arr_len; ++i)
  {
    cout << ' ' << arr.at(i);
  }
  cout << endl;
}

bool card_greater(string card1, string card2)
{
  return ((int)(card1[1] - '0') < (int)(card2[1] - '0'));
}

void bubble_sort(array<string, MAX_LEN>& arr, int arr_len)
{
  bool rev_flag = true;

  for (int i = 0; i < arr_len; ++i)
  {
    rev_flag = false;

    for (int j = arr_len - 1; j > i; --j)
    {
      if (card_greater(arr.at(j), arr.at(j - 1)))
      {
        rev_flag = true;
        swap(arr.at(j - 1), arr.at(j));
      }
    }

    if (!rev_flag)
    {
      break;
    }
  }
}

void selection_sort(array<string, MAX_LEN>& arr, int arr_len)
{
  for (int i = 0; i < arr_len; ++i)
  {
    int min_index = i;

    for (int j = i; j < arr_len; ++j)
    {
      if (card_greater(arr.at(j), arr.at(min_index)))
      {
        min_index = j;
      }
    }

    if (i != min_index)
    {
      swap(arr.at(i), arr.at(min_index));
    }
  }
}

int main()
{
  // Initialize n
  int n = 0;
  cin >> n;

  // Initialize card lists of two
  array<string, MAX_LEN> cards_bs;
  for (int i = 0; i < n; ++i)
  {
    string a_card = "";
    cin >> a_card;
    cards_bs.at(i) = a_card;
  }
  array<string, MAX_LEN> cards_ss(cards_bs);

  // Excute bubble sort
  bubble_sort(cards_bs, n);
  output_array(cards_bs, n);
  cout << "Stable" << endl;

  // Excute selection sort
  selection_sort(cards_ss, n);
  output_array(cards_ss, n);
  if (equal(cards_bs.begin(), cards_bs.end(), cards_ss.begin()))
  {
    cout << "Stable" << endl;
  }
  else
  {
    cout << "Not stable" << endl;
  }

  return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    ll mi = min({a, b, c, d, e});
    cout << 5 + (n - 1) / mi;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		System.out.println(donuts(sc));
	}


	static int donuts(Scanner sc){
		int n = sc.nextInt();
		int m = sc.nextInt();


		int min = 999999;
		List<Integer> l = new ArrayList<Integer>();
		for(int i = 0 ; i < n ; ++i){
			int a = sc.nextInt();
			l.add(a);
			if(min > a){
				min = a;
			}
			m = m - a;
		}


		return  m/min + l.size();
	}
}

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

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

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

constexpr long long mod = 1000000007;

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

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

    int n;
    cin >> n;
    vll a(n);
    rep(i, n) cin >> a[i];

    vector<pair<ll, int>> v(n);

    rep(i, n) {
        v[i] = make_pair(a[i], i);
    }

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

    vll b(n, 0);
    rep(i, n) {
        if (i <= n / 2 - 1) {
            b[v[i].second] = v[n / 2].first;
        } else {
            b[v[i].second] = v[n / 2 - 1].first;
        }
    }

    rep(i, n) {
        cout << b[i] << endl;
    }
}

Measured memory_bytes: 8448
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long int ll;

vector<string> v;

ll solve(int x){
    int n=v[x].size();
    ll res=0;
    if(v[x][n-1]=='+'){
        x++;
        while(x<v.size()&&n+1<=v[x].size()){
            if(v[x].size()==n+1){
                res+=solve(x);
            }
            x++;
        }
    }
    else if(v[x][n-1]=='*'){
        res=1; x++;
        while(x<v.size()&&n+1<=v[x].size()){
            if(v[x].size()==n+1){
                res*=solve(x);
            }
            x++;
        }
    }
    else{
        res=v[x][n-1]-'0';
    }
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n,n){
        v.clear();
        for(int i=0;i<n;i++){
            string s; cin >> s;
            v.push_back(s);
        }
        cout << solve(0) << endl;
    }
}



Measured memory_bytes: 3260
n, w = map(int, input().split())
dp = [[-10 ** 9 for _ in range(w+1)] for _ in range(n)]
wn, vn = map(int, input().split())
dp[0][0] = 0
if wn <= w:
    dp[0][wn] = vn
for i in range(1, n):
    wn, vn = map(int, input().split())
    for j in range(w+1):
        if (j-wn) >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wn]+vn)
        else:
            dp[i][j] = dp[i-1][j]

#print(dp)
ans = 0
for val in dp[n-1]:
    if val > ans:
        ans = val
print(ans)

Measured memory_bytes: 171528
#include <stdio.h>
int main(void){
  int k,n,i,d,x;
  int a[200000];
  
  scanf("%d%d",&k,&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  d=a[0]+k-a[n-1];
  for(i=0;i+1<n;i++){
    if(d<a[i+1]-a[i])
      d=a[i+1]-a[i];
  }
  x=k-d;
  printf("%d",x);
  return 0;
}

Measured memory_bytes: 2468
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (ll i=j;i<=k;++i)
#define Forr(i,j,k) for (ll i=j;i>=k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T& a,T b) {return a<b?a=b,1:0;}
template<typename T>bool chkmin(T& a,T b) {return a>b?a=b,1:0;}

inline void file() {
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
}

int main() {
//	file();
	ll x,y; cin >> x >> y;
	if (x%y==0) {
		printf("-1");
		return 0;
	}
	ll xx=x; x+=x;
	while (x<=1e18) {
		if (x%y!=0) {
			cout << x << endl;
			return 0;
		}
		x+=xx;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(int, char**) {
        int a, b;
        cin >> a >> b;
        if (a + b == 15) {
                cout << '+' << endl;
        } else if (a * b == 15) {
                cout << '*' << endl;
        } else {
                cout << 'x' << endl;
        }
        return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, N, A[100001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));
	
	int k, l, r, max[100001] = {A[1]};
	for (i = 2, k = 1; i <= N; i++) {
		if (max[k-1] >= A[i]) max[k++] = A[i];
		else {
			for (l = 0, r = k - 1; l < r; ) {
				if (max[(l+r)/2] < A[i]) r = (l + r) / 2;
				else l = (l + r) / 2 + 1;
			}
			max[l] = A[i];
		}
	}
	
	printf("%d\n", k);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2476
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
for x in a:
  heapq.heappush(q, -x)
for i in range(m):
  x = heapq.heappop(q)
  x /= 2
  heapq.heappush(q, x)
ans = 0
for x in q:
  ans += -x // 1
print(int(ans))

Measured memory_bytes: 14180
#include<iostream>
using namespace std;
using ll = long long;
const ll mod = 998244353; 
ll dp[3030][3030][3];
int a[3030];
int main(){
    int n, k;
    cin >> n >> k;
    for(int i=0;i<n;i++)cin >> a[i];
    dp[0][0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            (dp[i+1][j][0] += dp[i][j][0]) %= mod;
            (dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]) %= mod;
            (dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) %= mod;
            if(j + a[i] <= k){
                (dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]) %= mod;
                (dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]) %= mod;
            }
        }
    }
    cout << dp[n][k][2] << endl;
}

Measured memory_bytes: 215168
n=int(input())
l=list(input())
c=0
for i in range(1,n):
  c1=0
  l2=[]
  for j in range(0,i):
    if (l[j] in l[i:n]) and not (l[j] in l2):
      c1+=1
      l2.append(l[j])
  if c1>c:
    c=c1
print(c)
  

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	ll n, m, k; cin >> n >> m >> k;
	VI a(n), b(m);
	REP(i,n) cin >> a[i];
	REP(i,m) cin >> b[i];
	VI sa(n+1,0), sb(m+1,0);
	REP(i,n) sa[i+1]=sa[i]+a[i];
	REP(i,m) sb[i+1]=sb[i]+b[i];
	int ans=0;
	REP(i,n+1){
		if(k-sa[i]<0)
			break;
		int p=upper_bound(ALL(sb),k-sa[i])-sb.begin()-1;
		ans=max(ans,p+i);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9592
#include <iostream>
#include <algorithm>
using namespace std;
int q, n, m, a[100000], b[99999];
int main() {
	cin >> q;
	for(int i = 0; i < q; i++) {
		cin >> n >> m;
		for(int i = 0; i < n; i++) cin >> a[i];
		for(int i = 1; i < n; i++) b[i - 1] = a[i] - a[i - 1];
		sort(b, b + n - 1);
		int ret = a[n - 1] - a[0];
		for(int i = n - 2; i >= n - m && i >= 0; i--) ret -= b[i];
		cout << ret << endl;
	}
}

Measured memory_bytes: 3912
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
    int a, b;
    cin >> a >> b;
    if (a + b == 3) {
        cout << 3 << endl;
    }
    else if (a + b == 4) {
        cout << 2 << endl;
    }
    else {
        cout << 1 << endl;
    }
}

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

int main(int , char **)
{
	int N,maxW;
	cin >> N >> maxW;

	int W = 0;
	// 制約: w1<=wi<=w1+3 より 重みは４段階
	vector<int> wArr[4];

	for(int i=0;i<N;i++){
		int w,v;
		cin >> w >> v;
		if (i==0){W=w;}
		wArr[w-W].push_back(v);
	}

	vector<ll> vSum[4]; // 各 重みで 使用個数->累積価値 のテーブルを作る
	for(int i=0;i<4;i++){
		stable_sort(wArr[i].begin(),wArr[i].end() ,greater<int>());
		ll s=0;
		vSum[i].push_back(0);
		for(auto v: wArr[i]){
			s+=v;
			vSum[i].push_back(s);
		}
	}

	// 各 重みを 何個使うかで 全探索
	ll maxV = 0;
	ll WW[4]={};
	for(size_t i0=0; i0<=wArr[0].size(); ++i0 ){
		WW[0] = W*i0;
		if (maxW < WW[0]){break;}

		for(size_t i1=0; i1<=wArr[1].size(); ++i1){
			WW[1] = (W+1)*i1 + WW[0];
			if ( maxW < WW[1]){break;}

			for(size_t i2=0; i2<=wArr[2].size(); ++i2){
				WW[2] = (W+2)*i2 + WW[1];
				if ( maxW < WW[2]){break;}

				for(size_t i3=0; i3<=wArr[3].size(); ++i3){
					WW[3] = (W+3)*i3 + WW[2];
					if( maxW < WW[3] ){break;}

						ll v = vSum[0][i0] + vSum[1][i1] + vSum[2][i2] + vSum[3][i3];
						maxV = max(maxV,v);
				}
			}
		}
	}
	printf("%ld\n",maxV);

	return 0;
}


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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n;
  cin >> n;
  char s[n][n];
  REP(i, n) REP(j, n) cin >> s[i][j];
  int ans = 0;
  REP(k, n) {
    char t[n][n];
    REP(i, n) REP(j, n) t[i][j] = s[i][(j + k) % n];
    bool ok = true;
    REP(i, n) REP(j, n) {
      if (t[i][j] != t[j][i]) ok = false;
    }
    if (ok) ans++;
  }
  cout << ans * n << endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
const long long mod = 1000000007;
const long long inf = 1145141919810;
typedef pair<int, int> P;
typedef pair<P, P> PP;
struct edge {int to, cost;};
int a[200005];
signed main() {
	int n; cin >> n;
	rep(i, n)cin >> a[i];
	int ans = 0;
	int f = a[0];
	if (a[0] != 0) {
		cout << -1 << endl; return 0;
	}
	for (int i = 1; i < n; i++) {
		if (i < a[i] || a[i] - f>1) {
			cout << -1 << endl;
			return 0;
		}
		if (f < a[i]) {
			f = a[i];
		}
		else {
			ans += f;
			f = a[i];
		}
	}
	ans += f;
	cout << ans << endl;
}

Measured memory_bytes: 1792
//
//  main.cpp
//  b
//
//  Created by h3037178 on 2017/07/31.
//  Copyright ?? 2017??´ ?????£?????????. All rights reserved.
//

#include <iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int main(){
    int a,b,c,i;
    cin >> i;
    for(int n = 0;n < i;n++){
        cin >> a >> b >> c;
        if(a*a == b * b + c * c){
            cout << "YES" << endl;
        } else if(b*b == a * a + c * c){
            cout << "YES" << endl;
        } else if(c*c == b * b + a * a){
            cout << "YES" << endl;
        } else {cout <<"NO" << endl;} 
    }
}

Measured memory_bytes: 3084
x,n = map(int,input().split())
if n == 0:
  print(x)
  quit()
lis = list(map(int,input().split()))
ans = 9999999
for y in range(x-101,x+101):
  if not(y in lis) and abs(x - y) < abs(x - ans):
    ans = y
  if not(y in lis) and abs(x - y) == abs(x - ans):
    if ans > y:
      ans = y
print(ans)

Measured memory_bytes: 9192
#![allow(unused_imports)]
// use itertools::Itertools;
use proconio::{input, marker::*};

fn main() {
    input! {
        n: usize,
        mut aa: [u128; n]
    };
    aa.sort();
    let mut sum = 1u128;
    for a in aa {
        let (tmp, tf) = sum.overflowing_mul(a);
        if tf || tmp > (1e18 as u128) {
            dbg!(tmp, tf);
            println!("-1");
            return;
        }
        sum = tmp;
    }
    println!("{}", sum);
}


Measured memory_bytes: 6224
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int h, a, b;
	cin >> h >> a >> b;
	int cnt = 0;
	for(int i = a; i <= b; i++) if(h % i == 0) cnt++;
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3088
using System;
using System.Collections.Generic;
namespace aizu
{
    class OnlineJudge
    {
        static void Main()
        {
            int count;
            while((count = int.Parse(Console.ReadLine())) != 0) {
                int[] input = new int[count];
                for(int i=0; i < count; input[i++] = int.Parse(Console.ReadLine())) ;
                long total = 0, max = 0;
                int index = 0;
                for(int i=0; i < input.Length; ++i) {
                    total += input[i];
                    if(max <= total || i == 0) {
                        max = total;
                        index = i;
                    }
                }
                total = max;
                for(int i=0; i < index; ++i) {
                    total -= input[i];
                    if(max <= total) {
                        max = total;
                    }
                }
                Console.WriteLine(max);
            }
        }
    }
}

Measured memory_bytes: 5708
#include <stdio.h>
static long dp[100100][3];
static long h[100100][3];

long chmax(long A, long B){
	if(A>B)return A;
	else A=B;
	
	return B;
}
int main(){

int N;
int i,k;
	long a[3];
	scanf("%d",&N);
for(i=0;i<N;i++){
	scanf("%ld%ld%ld",&a[0],&a[1],&a[2]);
	
	if(i==0){
		for(k=0;k<3;k++)dp[i][k]=a[k];
	}
	else{
			dp[i][0] = chmax(dp[i-1][1]+a[0],dp[i-1][2]+a[0]);
			dp[i][1] = chmax(dp[i-1][0]+a[1],dp[i-1][2]+a[1]);
			dp[i][2] = chmax(dp[i-1][0]+a[2],dp[i-1][1]+a[2]);
	}
}
				
	long max;
				for(k=0;k<3;k++)
				max = chmax(dp[N-1][k],max);
	
				printf("%ld\n",max);
	

return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
  
using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b;
	c = a*b;
	if ( c % 2 == 0 ) {
		cout << "Even" << endl;
	} else {
		cout << "Odd" << endl;
	}
	return 0;	
}

Measured memory_bytes: 256
import math
def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+(n%b)
N=int(input())
S=int(input())
if N==S:
    print(N+1)
else:
    for b in range(2,int(math.sqrt(N))+2):
        if f(b,N)==S:
            print(b)
            exit()
    ans=10**13
    for p in range(1,int(math.sqrt(N))+2):
        if (N-S)%p!=0:
            continue
        b=(N-S)//p+1
        if b<=1:
            continue
        if f(b,N)==S:
            ans=b
    if ans==10**13:
        print(-1)
    else:
        print(ans)



Measured memory_bytes: 3064
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>

typedef long long ll;
#define MIN(x, y) (x < y ? x : y)
#define MAX(x, y) (x > y ? x : y)

using namespace std;

int main(){
	int A, B;
	cin >> A >> B;

	
	if(A > 8 || B > 8) cout << ":(" << endl;
	else cout << "Yay!" << endl;
}


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

int main() {
  bool flag = true;
  int san = 0, cho = 0, ei = 0, don = 0;
  while (flag) {
    int a, b, c; cin >> a >> b >> c;
    // sankakkei
    if (a + b > c && b + c > a && c + a > b) {
      san++;
      vector<int> v = {a, b, c};
      sort(v.begin(), v.end(), greater<int>());
      //chokkaku
      if (v.at(0) * v.at(0) == v.at(1) * v.at(1) + v.at(2) * v.at(2)) {
        cho++;
      }
      //eikaku
      if (v.at(0) * v.at(0) < v.at(1) * v.at(1) + v.at(2) * v.at(2)) {
        ei++;
      }
      //donkaku
      if (v.at(0) * v.at(0) > v.at(1) * v.at(1) + v.at(2) * v.at(2)) {
        don++;
      }
    } else {
      flag = false;
    }
  }
  cout << san << " " << cho << " " << ei << " " << don << endl;
}



Measured memory_bytes: 3152
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    B = input_int_list()
    ans = 0
    for i in range(n):
        ans = max(ans, sum(A[:i + 1]) + sum(B[i:]))
    print(ans)

    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 63408
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[9];
        for(int i = 0; i < n; i++){
            int k = sc.nextInt() / 400;
            if(k > 8) k = 8;
            a[k]++;
        }
        int ans1 = 0;
        for(int i = 0; i < 8; i++)
            if(a[i] > 0) ans1++;
        int ans2;
        if(ans1 == 0){
            ans1 = 1;
            ans2 = a[8];
        }else
            ans2 = ans1 + a[8];
        System.out.print(ans1 + " " + ans2);
    }
}

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

using namespace std;


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define int long long

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second

template <typename T>
void print(T x)
{
	std::cout << x <<" " ;
}


template <typename T>
void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int A;
	int B;
	int C;
	cin >> A;
	cin >> B;
	cin >> C;

	cout << max((long long)0,C-(A-B)) << endl;

}

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



ll a, b;
int main(){
	cin >> a >> b;
	
	for ( int i = b*10; i < b*10+9; i++ ){
		if ( (i*8)/100 == a ){
			cout << i << endl;
			return 0;
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}



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

const int mod = 998244353;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	map<int, int> pos;
	long long n;
	int x, m;
	cin >> n >> x >> m;
	long long a[m + 1];
	a[0] = x;
	pos[x] = 0;
	int st = -1;
	for(int i = 1; ;i++) {
		a[i] = (a[i - 1] * a[i - 1]) % m;
		if(pos.find(a[i]) != pos.end()) {
			st = i;
			break;
		}
		pos[a[i]] = i;
	}
	assert(st != -1);
	long long ans = 0;
	for(int i = 0; i < min(n, 1ll * st); i++) ans += a[i];
	long long per = 0;
	for(int i = pos[a[st]]; i < st; i++) per += a[i];
	n -= st;
	if(n >= st - pos[a[st]]) {
		long long need = n / (st - pos[a[st]]);
		ans += need * per;
		n %= (st - pos[a[st]]);
	}
	for(int i = pos[a[st]]; i < st and n > 0; i++) ans += a[i], n--;
	cout << ans << endl;
	return 0;
}

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

int gcd(int a, int b) {
  int p, q;
  if(a < b)
    swap(a, b);
  p = a;
  q = b;
  for(int i=0; i<100000; i++) {
    int temp = q;
    q = p % q;
    p = temp;
    if(q == 0) {
      return p;
      break;
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> y(n+1);
  for(int i=0; i<n+1; i++)
    cin >> y.at(i);
  sort(y.begin(), y.end());
  for(int i=0; i<n; i++)
    y.at(i) = y.at(i+1) - y.at(i);
  y.pop_back();
  
  if(n == 1) 
    cout << y.at(0) << endl;
  
  else {
    int g = gcd(y.at(0), y.at(1));
    for(int i=0; i<n; i++) {
      g = gcd(g, y.at(i));
    } 
    cout << g << endl;
  }
}

Measured memory_bytes: 640
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int N = sc.nextInt();
		int X = sc.nextInt();
		
		long[] map = new long[N+1];
		map[N] = X;
		for (int i = 0; i < N; i++) {
			map[i] = sc.nextLong();
		}
		
		Arrays.sort(map);
		
		long[] sa = new long[N];
		for (int i = 1; i <= N; i++) {
			sa[i-1] = map[i] - map[i-1];
		}
		
		long ans = sa[0];
		for (int i = 1; i < N; i++) {
			ans = gcd(ans, sa[i]);
			if(ans == 1) {
				break;
			}
		}
		
		System.out.println(ans);
	}
	
	static long gcd (long a, long b) {
		long temp;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return b;
	}
 
}

Measured memory_bytes: 55196
// https://atcoder.jp/contests/abc156/tasks/abc156_e

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define FORR(i,b,e) for(int i=(b); i>=(int)(e); i--)
#if DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

//------------------------------------------------------------------------------
int extgcd(int a, int b, int &x, int &y) {
  int ret = a;
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    ret = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
  return ret;
}

int mod_inverse(int a, int m) {
  int x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}

//------------------------------------------------------------------------------
const int F_MAX = 2*1e5;

ll fact[F_MAX + 1];
ll fact_inv[F_MAX + 1];

void init_fact(int m) {
  fact[0] = 1;
  FOR(i, 1, F_MAX) fact[i] = fact[i - 1] * i % m;
  fact_inv[F_MAX] = mod_inverse(fact[F_MAX], m);
  FORR(i, F_MAX - 1, 0) fact_inv[i] = fact_inv[i + 1] * (i + 1) % m;
}

ll mod_comb_fast(ll n, ll k, ll mod) {
  if (n < 0 || k < 0 || n < k) return 0;
  ll a = fact[n];
  ll b = fact_inv[k] * fact_inv[n - k] % mod;
  ll ret = a * b % mod;
  // printf("%lld_C_%lld = %lld\n", n, k, ret);
  return ret;
}

//------------------------------------------------------------------------------

const int N_MAX = 2*1e5;
const int K_MAX = 1e9;
const int MOD = 1e9+7;

int n, k;

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

  init_fact(MOD);
  int m = max(1, n - k);
  ll ans = 0;
  FOR(i, m, n) {
    ll tmp = mod_comb_fast(n, i, MOD) * mod_comb_fast(n - 1, i - 1, MOD) % MOD;
    ans = (ans + tmp) % MOD;
 }
  cout << ans << endl;
}


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

vector<ll> value(1000000);
vector<vector<ll>> edge(1000000);

// v:探索中の頂点　p:vの親
void dfs(int v , int p){
    if(p != -1){
        value[v] = value[p] + value[v];
    }
    for(int next_v : edge[v]){
        if(next_v == p) {
            continue;
        }
        dfs(next_v, v);
    }
}

int main(void){
    ll N,Q;
    cin >> N >> Q;
    
    //隣接リスト表現でグラフを持つ　0-index
    ll a,b;
    for(int i = 0; i < N-1; i++){
        cin >> a >> b;
        edge.at(a-1).push_back(b-1);
        edge.at(b-1).push_back(a-1);
    }
    
    //各頂点自身を基準にして加えられるカウンター値を求める　0-index
    ll p,x;
    for(int i = 0; i < Q; i++){
        cin >> p >> x;
        value.at(p-1) += x;
    }
    
    
    dfs(0, -1);
    
    for(int i = 0; i < N; i++){
        printf("%lld ",value[i]);
    }
    
}

Measured memory_bytes: 49280
#include<stdio.h>
int main(){

  int a[100]={0},i,j,k,v,n;
  
  scanf("%d",&n);

  for(i=0;i<n;i++) scanf("%d",&a[i]);
  
  for(k=0;k<n-1;k++) printf("%d ",a[k]);printf("%d\n",a[n-1]);

  for(i=1;i<=n-1;i++){
    v = a[i];
    j = i - 1;
    while(j>=0 && a[j]>v){
      a[j+1] = a[j];
      j--;
      a[j+1]=v;
    }
    for(k=0;k<n-1;k++) printf("%d ",a[k]);printf("%d\n",a[n-1]);
  }
}


Measured memory_bytes: 2044
/**
 *    author:  FromDihPout
 *    created: 2020-07-25
**/

#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<double> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    
    vector<double> prev(n + 1);
    prev[0] = 1 - p[0];
    prev[1] = p[0];
    for (int coin = 1; coin < n; coin++) {
        vector<double> curr(n + 1);
        curr[0] = prev[0] * (1 - p[coin]);
        for (int i = 1; i <= coin + 1; i++) {
            curr[i] = prev[i-1] * p[coin]
                + prev[i] * (1 - p[coin]);
        }
        prev = curr;
    }
    
    double ans = 0;
    for (int i = n / 2 + 1; i <= n; i++) {
        ans += prev[i];
    }
    printf("%.12f", ans);
    return 0;
}

Measured memory_bytes: 3908
//BELIEVE IN YOURSELF
//next_permutation

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define pob pop_back
#define vi vector<ll>
#define mp make_pair
#define sz size()
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define rep(i,n) for(ll i=0;i<n;i++)
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define maxx 205
#define se second
#define fi first
#define be begin()
#define en end()
#define sortv(v) sort(v.begin(),v.end());
#define sortr(v) sort(v.rbegin(),v.rend());
#define w() ll _;cin>>_;while(_--)
#define edge pair<ll,ll>
#define pq priority_queue<ll>
#define mod 1000000007
#define Endl "\n"
#define cy cout<<"YES"<<endl;
#define cn cout<<"NO"<<endl;
#define lb(v,x) std::lower_bound(v.begin(),v.end(),x)
#define ub(v,x) std::upper_bound(v.begin(),v.end(),x)

using namespace std;

//------BEAST MODE ON------------
//-----fuck rating

int main()
{
	fast;
	ll n;
	cin>>n;
	ll i;
	ll a[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	ll ma=a[0];
	ll ans=0;
	for(i=1;i<n;i++)
	{
		if(a[i]>=ma)
		{
			ma=a[i];
		}
		else
		{
			ans+=(ma-a[i]);
		}
	}
	cout<<ans<<endl;
	
	return 0;	
}

Measured memory_bytes: 5192
#include<bits/stdc++.h>
using namespace std;
  
  
int main(){
  
    int dp[100][200],row = 0,tmp,index,width[100],max_width = 0, max_width_row;
    char buf[200];
  
    while(scanf("%s",buf)!=EOF){
        index = tmp = 0;
        for(int i=0;buf[i] != '\0'; i++){
            if(buf[i] >= '0' && buf[i] <= '9'){
                tmp = tmp*10 + (buf[i] - '0');
                if(buf[i+1] == '\0'){
                    dp[row][index++] = tmp;
                }
            }else{
                dp[row][index++] = tmp;
                tmp = 0;
            }
        }
        if(max_width < index){
            max_width = index;
            max_width_row = row;
        }
  
        width[row] = index;
        row++;
    }
  
    for(int i=1; i <= max_width_row; i++){
        for(int k=0; k < width[i]; k++){
            if(k == 0){
                dp[i][0] += dp[i-1][0];
            }else if(k == width[i]-1){
                dp[i][k] += dp[i-1][width[i-1]-1];
            }else{
                dp[i][k] += max(dp[i-1][k-1],dp[i-1][k]);
            }
        }
    }
  
    for(int i = max_width_row+1;i < row; i++){
        for(int k=0; k < width[i]; k++){
            dp[i][k] += max(dp[i-1][k],dp[i-1][k+1]);
        }
    }
  
    cout << dp[row-1][0] << "\n";
  
    return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) ((int)(x).size())
#define fill(v, h) memset((v), h, sizeof(v))
using namespace std;
const int MOD = 1000000007;

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

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

int main(void)
{
    int n, k;
    cin >> n >> k;
    vector<int> snuke(n);
    for (int i = 0; i < k; i++)
    {
        int d;
        cin >> d;
        for (int ii = 0; ii < d; ii++)
        {
            int a;
            cin >> a;
            snuke[a - 1]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (snuke[i] == 0)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632