akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define inf 1000000007

int main() {
	int n;
	cin >> n;
	int all = 0;
	int ma = inf;
	rep(i, n) {
		int w;
		cin >> w;
		all += w;
		ma = min(ma, all / (i + 1));
	}
	cout << ma << endl;
}


Measured memory_bytes: 3124
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int ans;
int n, m;

int main(void) {
    cin >> n >> m;

    ans += n*(n-1)/2;
    ans += m*(m-1)/2;

    cout << ans << endl;

	return 0;
}


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

typedef long long ll;

ll dp[55][55][55];
ll LL_MAX = numeric_limits<ll>::max();

ll f(ll a, ll b, ll c, ll op) {
    if (a > 53 or b > 53 or c > 53) return LL_MAX;
    if (a == b and b == c) return op;
    if (dp[a][b][c] != -1) return dp[a][b][c];

    ll A = f(a+2, b, c, op+1);
    ll B = f(a, b+2, c, op+1);
    ll C = f(a, b, c+2, op+1);
    ll AB = f(a+1, b+1, c, op+1);
    ll BC = f(a, b+1, c+1, op+1);
    ll CA = f(a+1, b, c+1, op+1);
    dp[a][b][c] = min({A, B, C, AB, BC, CA});
    return dp[a][b][c];
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    memset(dp, -1, sizeof(dp));
    cout << f(a, b, c, 0) << endl;

    return 0;
}



Measured memory_bytes: 1536
N, M = map(int, input().split())
A = {}
for _ in range(M):
    a = int(input())
    A[a] = True

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1

for i in range(2, N+1):
    # 壊れた床がなく単純に求める場合
    #dp[i] = dp[i-1]+dp[i-2]

    if not i-1 in A:
        dp[i] += dp[i-1]
    if not i-2 in A:
        dp[i] += dp[i-2]

print(dp[N] % 1000000007)


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

int main() {
  int N, Y, yen_10000 = -1, yen_5000 = -1, yen_1000 = -1;
  cin >> N >> Y;

  for (int a = 0; a <= N; a++) {
    for (int b = 0; a + b <= N; b++) {
      int c = N - a - b;
      int sum = 10000 * a + 5000 * b + 1000 * c;
      if (sum == Y) {
        yen_10000 = a;
        yen_5000 = b;
        yen_1000 = c;
      }
    }
  }

  cout << yen_10000 << ' ' << yen_5000 << ' ' << yen_1000 << endl;
}

Measured memory_bytes: 3588
import java.util.*;

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

		String s = sc.next();
      
		int s0 = Integer.parseInt(s.substring(0, 1));
		int s1 = Integer.parseInt(s.substring(1, 2));
		int s2 = Integer.parseInt(s.substring(2, 3));

		int s_t = s0 + s1 + s2;
		System.out.print(s_t);

	}
}

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

typedef long long ll;
using namespace std;
const ll mod = 1000000007;
const ll mod998 = 998244353;
const ll intmax = 2147483647;
const ll llmax = 9223372036854775807;
const char sp = ' ';

int H, N, A[100000];
ll cnt;

int main() {
	cin >> H >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		cnt += A[i];
	}
	if (cnt >= H) {
		puts("Yes");
	}
	else {
		puts("No");
	}
}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> V(N);
  vector<int> C(N);
  for(int i=0; i<N; i++) cin >> V[i];
  for(int i=0; i<N; i++) cin >> C[i];
  int s=0;
  for(int i=0; i<N; i++) s += max(0, V[i]-C[i]);
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    private static int[] calcPrimes(int n) {
        boolean[] table = new boolean[n + 1];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (!table[i]) {
                for (int j = i + i; j <= n; j += i) {
                    table[j] = true;
                }
            }
        }
        int counter = 0;
        for (int i = 2; i <= n; i++) {
            if (!table[i]) {
                counter++;
            }
        }
        int[] result = new int[counter];
        int index = 0;
        for (int i = 2; i <= n; i++) {
            if (!table[i]) {
                result[index++] = i;
            }
        }
        return result;
    }

    private static void solve() {
        Scanner scanner = new Scanner(System.in);
        int[] primes = calcPrimes(10000 + 100);

        while (true) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            int counter = 0;
            for (int i = 0; i < primes.length && primes[i] <= n; i++) {
                int x = n;
                for (int j = 0; x > 0; j++) {
                    x -= primes[i + j];
                }
                if (x == 0) {
                    counter++;
                }
            }
            System.out.println(counter);
        }
    }

    public static void main(String... args) {
        solve();
    }
}

Measured memory_bytes: 12000
use std::collections::*;

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().split_whitespace()
        .map(|x| x.parse().ok().unwrap()).collect()
}

#[derive(Copy, Clone, Debug)]
struct edge(i64, i64, i64);

fn dfs(v : i32, g : &Vec<Vec<edge>>, ok : &mut Vec<i32>) {
    ok[v as usize] = 1;
    for &e in &g[v as usize] {
        if ok[e.2 as usize] == 0 {
            dfs(e.2 as i32, g, ok);
        }
    }
}

fn main() {
    let NMP = read_vec::<i64>();
    let (N, M, P) = (NMP[0], NMP[1], NMP[2]);
    let mut es = Vec::<edge>::with_capacity(M as usize);
    let mut g = Vec::<Vec<edge>>::with_capacity(N as usize);
    let mut ig = Vec::<Vec<edge>>::with_capacity(N as usize);
    let mut ok = Vec::<i32>::with_capacity(N as usize);
    let mut iok = Vec::<i32>::with_capacity(N as usize);
    for i in 0..N {
        g.push(Vec::<edge>::new());
        ig.push(Vec::<edge>::new());
        ok.push(0);
        iok.push(0);
    }
    for i in 0..M {
        let v = read_vec::<i64>();
        g[(v[0]-1) as usize].push(edge(P-v[2], v[0]-1, v[1]-1));
        ig[(v[1]-1) as usize].push(edge(P-v[2], v[1]-1, v[0]-1));
        es.push(edge(P-v[2], v[0]-1, v[1]-1));
    }
    dfs(0, &g, &mut ok);
    dfs((N-1) as i32, &ig, &mut iok);

    let mut pq = BinaryHeap::<(i64, usize)>::new();
    let mut d = Vec::<i64>::with_capacity(N as usize);
    let mut count = 0;
    let mut updated = true;
    for i in 0..N {
        d.push(std::i64::MAX);
    }
    d[0] = 0;

    while updated {
        updated = false;
        count += 1;
        if count > N {
            d[(N-1) as usize] = std::i64::MAX;
            break;
        }
        for &e in &es {
            if d[e.1 as usize] == std::i64::MAX {
                continue;
            }
            if ok[e.1 as usize] == 0 || ok[e.2 as usize] == 0 {
                continue;
            }
            if iok[e.2 as usize] == 0 || iok[e.1 as usize] == 0 {
                continue;
            }
            if d[e.1 as usize] + e.0 < d[e.2 as usize] {
                d[e.2 as usize] = d[e.1 as usize] + e.0;
                updated = true;
            }
        }
    }

    if d[(N-1) as usize] == std::i64::MAX {
        println!("-1");
    } else {
        println!("{}", std::cmp::max(-d[(N-1) as usize], 0));
    }
}


Measured memory_bytes: 4476
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    N = int(lines.pop(0))
    L = list(map(int, lines.pop(0).split(' ')))
    L.sort()
    longest = L.pop(-1)
    if longest < sum(L):
        print('Yes')
    else:
        print('No')

#
# main
#
lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)


Measured memory_bytes: 2940
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	char c;
	cin >> a >> c >> b;
	if(c=='+')
	{
		cout << a+b << endl;
	}
	if(c=='-')
	{
		cout << a-b << endl;
	}
	return 0;
}

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

int main(){
  int a,b,k=0,i,j=0;
  
  while(1){
    cin>>a>>b;
    if(a==0&&b==0)break;
   
    if(j) cout<<endl;
    k=0;
    for(i=a;i<=b;i++){
      if(i%4==0&&i%100!=0){cout<<i<<endl;k++;}
      if(i%400==0){cout<<i<<endl;k++;}
    }    
    if(k==0)cout<<"NA"<<endl;
    j=1;  
  }
return 0;
}

Measured memory_bytes: 0
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N,M = map(int,input().split())

A = [[] for i in range(N)]

for i in range(N):
    A[i] = list(map(int,input().split()))

B = [[0]*1 for i in range(M)]

for i in range(M):
    B[i] = int(input())


for row in range(N):
    tmp = 0
    for col in range(M):
        tmp += A[row][col]*B[col]
    print("%d"%(tmp))


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

const int N=1e5+5;
int A[N],B[N];
bool used[N];
int main() {
    int n;
    cin >> n;
    REP(i,n) scanf("%d %d", A+i,B+i);
    vector<int> a;
    long long sum=0;
    REP(i,n) {
        a.push_back(A[i]+B[i]);
        sum+=A[i];
    }
    sort(a.begin(),a.end());
    for ( int i=n-2; i>=0; i-=2 ) {
        sum-=a[i];
    }
    cout << sum << '\n';
    return 0;
}



Measured memory_bytes: 4760
import fractions

a,b,c,d = map(int,input().split())
#print(a,b,c,d)
gcd = int(fractions.gcd(c,d))
lcm = int(c*d / gcd)
#print(gcd,lcm)


c_div1 = int((a-1) // c)
c_div2 = int(b // c)
d_div1 = int((a-1) // d) 
d_div2 = int(b // d)
lcm_div1 = int((a-1) // lcm)
lcm_div2 = int(b // lcm)

ans = int(c_div2 - c_div1) + int(d_div2 - d_div1) - int(lcm_div2 - lcm_div1)
#print(c_div1,c_div2,d_div1,d_div2,lcm_div1,lcm_div2)
print(int(b - a - ans + 1))

Measured memory_bytes: 5048
#include<stdio.h>

int main(void)
{
    int X, N ,T, c=0;
    scanf("%d %d %d", &N ,&X, &T);

    while(N > 0)
    {
        N -= X;
        c++;
    }

    printf("%d\n", c*T);

    return 0;
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
typedef long long ll;

using namespace std;

int main(){

    int N;
    cin>>N;
    int ans=0;
    for(int i=1;i<=N;i++){
        string s=to_string(i);
        if(s.length()%2==1)ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3712
c=3.times.map{gets.split.map(&:to_i)}
total_sum=c.map{|r|r.inject(:+)}.inject(:+)
daig_sum=[*0..2].map{|i|c[i][i]}.inject(:+)
skew_daig_sum=[*0..2].map{|i|c[i][2-i]}.inject(:+)
flag1=total_sum==3*daig_sum
flag2=daig_sum==skew_daig_sum
puts flag1&&flag2 ? "Yes" : "No"

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

int main() {
        int n;
        cin >> n;
        vector<pair<string, pair<int, int>>> p(n);
        rep(i, n) {
                cin >> p[i].first >> p[i].second.first;
                p[i].second.second = i;
                p[i].second.first *= -1;
        }
        sort(p.begin(), p.end());
        rep(i, n) {
                cout << p[i].second.second + 1 << endl;
        }
        return 0;
}


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

using namespace std;

int main(){
  long long int N, power = 1;

  cin >> N;

  for(long long int i = 1; i <= N; i++) power = i * power % (1000000000 + 7);

  cout << power << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#include <vector>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> color{399, 799, 1199, 1599, 1999, 2399, 2799, 3199};
  vector<int> colorNum(8,0);
  int minNum = 0;
  int free = 0;
  rep(i,n){
    int temp;
    cin >> temp;
    rep(m, 8){
      if(color[m] >= temp){
        colorNum[m]++;
        break;
      }
    }
    if(temp >= 3200) free++;
  }
  rep(m,8){
    if(colorNum[m] > 0){
      minNum++;
    }
  }
  cout << max(minNum, 1) << " " << minNum + free << endl;
  return 0;
}

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

int main()
{
    int N;
    vector<int> a;
    cin >> N;
    a.resize(N);

    rep(i,N)cin >> a[i];

    bool check=true;
    rep(i,N){
        if(a[i]%2==0){
            if(a[i]%3!=0&&a[i]%5!=0){
                check=false;
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    if(true){
        cout << "APPROVED" << endl;
    }



}

Measured memory_bytes: 256
public class Main {
    public static void main(String[] args) {

        java.util.Scanner sc = new java.util.Scanner(System.in);
        String s = sc.next();
        String p = sc.next();

        boolean tf = false;
        String x = "";
        for (int i = 0; i < s.length(); i ++) {
            x = "";
            for (int j = 0; j < p.length(); j ++) { x += s.charAt((i + j) % s.length()); }
            if (x.equals(p)) { tf = true; }
        }
        if (tf == true) { System.out.println("Yes"); }
        else { System.out.println("No"); }
    }
}

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

using namespace std;

int main(){

  string a, b;
  cin >> a >> b;

  if (a == "H"){
    cout << b << endl;
  }
  else {
    if (b == "H"){
      cout << "D" << endl;
    }
    else {
      cout << "H" << endl;
    }
  }

  return 0;
}


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

int main(){
    int n; cin>>n;
    vector<int> t(n+1,0),x(n+1,0),y(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>x[i]>>y[i];
    }

    for(int i=0;i<n;i++){
        int dt=t[i+1]-t[i];
        int dx=abs(x[i+1]-x[i]);
        int dy=abs(y[i+1]-y[i]);
        if((dx+dy)%2!=dt%2||dx+dy>dt){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

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

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr int INF = 1001001001;

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

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    
    ll ans = max(max(a*c, a*d), max(b*c, b*d));
    cout << ans << endl;
    
    return 0;
}


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

void search(int y, int x, int h, int w, int** field) {
    field[y][x] = 0;
    for (int ny = y - 1; ny <= y + 1; ny++) {
        for (int nx = x - 1; nx <= x + 1; nx++) {
            if (0 <= ny && ny < h && 0 <= nx && nx < w && field[ny][nx] == 1) {
                search(ny, nx, h, w, field);
            }
        }
    }
}

int main() {
    while (true) {
        int w, h;
        cin >> w >> h;
        if ((w | h) == 0) {
            break;
        }
        int** field = new int* [h];
        for (int i = 0; i < h; i++) {
            field[i] = new int [w];
        }
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                cin >> field[y][x];
            }
        }
        int count = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                if (field[y][x] == 1) {
                    search(y, x, h, w, field);
                    count++;
                }
            }
        }
        cout << count << endl;
        for (int i = 0; i < h; i++) {
            delete[] field[i];
        }
        delete[] field;
    }
}

Measured memory_bytes: 0
#include <cstdio>
#include <cmath>

using namespace std;

int main(){

    int n;

    scanf("%d", &n );

    int judge, count, flag, j;
    double x;

    count = 0;

    for( int i = 0; i < n ; i++ ){

        scanf("%d", &judge );

        if( judge == 2 ){

            count++;

        }else if( judge > 2 && judge % 2 == 0 ){

        }else if( judge > 2 ){

            x = sqrt( judge );

            if( x < 3 ){

                flag = 1;

            }

            for( j = 3; j < x + 1 ; j = j + 2 ){

                if( judge % j == 0){

                    flag = 0;

                } else {

                    flag = 1;

                }

                if( flag == 0 ){

                    break;

                }

            }

            if( flag == 1 ){

                count++;

            } else {

            }

        }

    }

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

    return 0;

}

Measured memory_bytes: 2728
def myAnswer(N:int,A:list) -> int:
   counter = 0
   free = 0
   rate = [0 for _ in range(8)]
   for a in A:
      if(a <= 399):
         rate[0] += 1
      elif(a <= 799):
         rate [1] += 1
      elif(a <= 1199):
         rate[2] += 1
      elif(a <= 1599):
         rate[3] += 1
      elif(a <= 1999):
         rate[4] += 1
      elif(a <= 2399):
         rate[5] += 1
      elif(a <= 2799):
         rate[6] += 1
      elif(a <= 3199):
         rate[7] += 1
      else:
         free += 1
   for r in rate:
      if(r > 0):
         counter += 1
   if(free == N):
      print(1,free)
   else:
      print(counter,counter+free)


def modelAnswer():
   return
def main():
   N = int(input())
   A = list(map(int,input().split()))
   myAnswer(N,A[:])
if __name__ == '__main__':
   main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define int ll
int mod=1000000007;
int fact[3000];
int factinv[3000];

ll modpow(ll x, ll y, ll p)
{
	ll res = 1;
	x = x % p;
	while (y > 0)
	{
		if (y & 1)
			res = (res*x) % p;
		y = y>>1;
		x = (x*x) % p;
	}
	return res;
}

ll binom(int n, int r)
{
	if (r > n)
		return 0;
	if (r < 0)
		return 0;
	if (r == 0 || r == n)
		return 1;
	int a, b, c;
	a = fact[n];
	b = factinv[r];
	c = factinv[n-r];
	return ((((a*b)%mod)*c)%mod);
}

int32_t main()
{
	usecppio
	int n, k, r;
	fact[0] = 1;
	factinv[0] = 1;
	for (int i = 1; i<=2500; i++)
	{
		fact[i] = fact[i-1] * i;
		fact[i] %= mod;
		factinv[i] = modpow(fact[i],mod-2,mod);
	}
	cin >> n >> k;
	r = n-k;
	for (int i = 1; i<=k; i++)
	{
		int a = binom(r+1,i);
		int b = binom(k-1,i-1);
		cout << (a*b)%mod << '\n';
	}
}


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

def devide2(n):
    return n / 2

ans = 0
while True:
    a = list(map(devide2, a))
    if all([n.is_integer() for n in a]):
        ans += 1
    else:
        break

print(ans)

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

vector<int64_t> par(100000);
vector<int64_t> r(100000);

int find(int64_t n){
  if(par.at(n)==n){
    return n;
  }else{
    return par.at(n)=find(par.at(n));
  }
}
void unite(int64_t a,int64_t b){
  int64_t x=find(a);
  int64_t y=find(b);
  if(x==y){
    return;
  }
  if(r.at(x)>r.at(y)){
    par.at(y)=x;
  }else{
    par.at(x)=y;
    if(r.at(x)==r.at(y)){
      r.at(y)++;
    }
  }
}

int main(){
  int64_t N,M,K;
  cin >> N >> M >> K;
  vector<pair<int64_t,int64_t>> A(100000),C(100000);
  vector<int64_t> block(100000,0),num(100000,0);
  for(int64_t i=0;i<N;i++){
    r.at(i)=0;
    par.at(i)=i;
  }
  for(int64_t i=0;i<M;i++){
    cin >> A.at(i).first >> A.at(i).second;
    unite(A.at(i).first-1,A.at(i).second-1);
    block.at(A.at(i).first-1)++;
    block.at(A.at(i).second-1)++;
  }
  for(int64_t i=0;i<K;i++){
    cin >> C.at(i).first >> C.at(i).second;
    if(find(C.at(i).first-1)==find(C.at(i).second-1)){
      block.at(C.at(i).first-1)++;
      block.at(C.at(i).second-1)++;
    }
  }
  for(int64_t i=0;i<N;i++){
    num.at(find(i))++;
  }

  for(int64_t i=0;i<N;i++){
    cout << num.at(find(i))-1-block.at(i) << " ";
  }
  cout << endl;
}

Measured memory_bytes: 7040
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    n = ii()
    A = lmi()

    m = 1000
    for i in range(n-1):
        if A[i] < A[i+1]:
            cnt = m // A[i]
            m += (A[i+1] - A[i]) * cnt

    print(m)

    return

main()


Measured memory_bytes: 9216
module WeightedDirectedGraph
  (Vertex : sig
    type t
    val compare : t -> t -> int
  end)
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  val dijkstra :
    (* 隣接リスト *)
    (Vertex.t -> (Vertex.t * Weight.t) list) ->
    (* 始点 *)
    Vertex.t ->
    (* 始点から辿り着けなければNoneを返す *)
    (Vertex.t -> Weight.t option)
end =
struct
  module WMap = Map.Make (Weight)
  module VMap = Map.Make (Vertex)

  let dijkstra e s =
    (* 始点sからの距離 *)
    (* d に入っていない頂点への距離は無限大とみなす *)
    let d = ref @@ VMap.singleton s Weight.zero in
    (* 優先度付きキュー *)
    let q = ref @@ WMap.singleton Weight.zero [s] in
    (* ダイクストラ法のメインループ *)
    let rec dijkstra_aux t =
      match WMap.min_binding !q with
      | exception Not_found ->
          (try Some (VMap.find t !d) with Not_found -> None)
      | (w, us) ->
          if
            (* 現時点で終点までの距離が分かっているか *)
            try Weight.compare (VMap.find t !d) w <= 0
            with Not_found -> false
          (* 既に終点までの距離が分かっているので返す *)
          then Some (VMap.find t !d)
          else begin
            (* 終点までの距離が分かっていないので，ダイクストラ法を続行 *)
            q := WMap.remove w !q;
            List.iter (fun u ->
              if 0 <= Weight.compare (VMap.find u !d) w then
                (* 未だ頂点uを訪れていない *)
                List.iter (fun (v, c) ->
                  let open Weight in
                  if
                    try 0 < Weight.compare (VMap.find v !d) (w + c)
                    with Not_found -> true  (* d.(v) は無限大 *)
                  then begin
                    d := VMap.add v (w + c) !d;
                    q := WMap.add (w + c) (v :: try WMap.find (w + c) !q with Not_found -> []) !q
                  end) (e u)) us;
            dijkstra_aux t
          end in dijkstra_aux
end

module Int = struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare = compare
end

module G = WeightedDirectedGraph (Int) (Int)

let () = Scanf.scanf "%d %d %d %d\n" @@ fun n m s t ->
  let uvab = Array.init m @@ fun _ -> Scanf.scanf "%d %d %d %d\n" @@ fun u v a b -> u, v, a, b in
  let es_yen = Array.make n [] in
  let es_snuke = Array.make n [] in
  Array.iter (fun (u, v, a, b) ->
    es_yen.(u - 1) <- (v - 1, a) :: es_yen.(u - 1);
    es_yen.(v - 1) <- (u - 1, a) :: es_yen.(v - 1);
    es_snuke.(u - 1) <- (v - 1, b) :: es_snuke.(u - 1);
    es_snuke.(v - 1) <- (u - 1, b) :: es_snuke.(v - 1)) uvab;
  let d_yen = G.dijkstra (fun u -> es_yen.(u)) (s - 1) in
  let d_snuke = G.dijkstra (fun u -> es_snuke.(u)) (t - 1) in
  let ans = Array.make (n + 1) max_int in
  for i = n - 1 downto 0 do
    ans.(i) <- min ans.(i + 1) @@
      match d_yen i, d_snuke i with
      | None, _ -> max_int
      | _, None -> max_int
      | Some d, Some d' -> d + d'
  done;
  for i = 0 to n - 1 do
    Printf.printf "%d\n" @@
      (( - ) 1000000000000000) ans.(i)
  done


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF = 1e18+18;
const ll MAX = 100005;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a, b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n, m, arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n, arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

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

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

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len = v.size();
    for(int i = 0; i < len; ++i) {
        s<<v[i];
        if(i < len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len = vv.size();
    for(int i = 0; i < len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

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

    ll n, m;
    cin>>n>>m;
    Vec a(n);
    rep(i, n)cin>>a[i];
    sort(ALL(a));
    Vec s(n+1);

    rep(i, n) {
        s[i+1] = s[i]+a[i];
    }

    ll L = -1;
    ll R = a[n-1]+a[n-1]+1;

    ll ans = 0;
    while (L+1 < R) {
        ll c = (L+R)/2;
        ll x = 0;
        bool ok = [&] {
            //x c未満合計
            rep(i, n) {
                ll itr = lower_bound(ALL(a), c-a[i])-a.begin();
                x += n-itr;
            }
            return x >= m;
        }();
        if(ok) {
            L = c;
        } else {
            R = c;
        }
    }

    //合計L以下で考える

    ll cnt = 0;
    rep(i,n){
        //L未満の個数はitr
        ll itr = lower_bound(ALL(a), L-a[i])-a.begin();
        ans += s[n]-s[itr];
        ans += a[i]*(n-itr);
        cnt += n-itr;
    }
    ans -= (cnt-m)*L;

    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 123456;
vector<pii> G[MAXN];
bool visit[MAXN];
int dis[MAXN];

bool dfs(int cur, int ds) {
     visit[cur] = 1;
     dis[cur] = ds;
     // printf("cur = %d dis = %d\n", cur, dis[cur]);
     bool OK = true;
     for (auto i : G[cur]) {
         int to = i.first;
         int w = i.second;
         if (visit[to] && dis[to] != dis[cur] + w) {
            // printf("cur = %d to = %d dis[to] = %d outw = %d\n", cur, to, dis[to], dis[cur] + w);
            OK = false;
         }
         else if (!visit[to] && !dfs(to, dis[cur] + w)) OK = false;
     }
     return OK;
}


int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d);
        G[x].push_back(make_pair(y, d));
        G[y].push_back(make_pair(x, -d));
    }
    bool OK = true;
    for (int i = 1; i <= N; i++) {
        if (!visit[i] && !dfs(i, 0)) OK = false;
    }
    puts(OK ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 12672
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int ans = 0;
            if (b + c <= a)
                ans = 0;
            else
                ans = b + c - a;
            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 22996
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = n - 1; i > 0; i--) {
		cout << a[i] << " ";
	}
	cout << a[0] << endl;
	return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
using namespace std;

int main(void) {
    int N,M;cin>>N>>M;
    vector<int> A(M);
    for (int i = 0; i < M; i++) {
        int b;
        cin>>A[i]>>b;
    }
    sort(all(A));
    reverse(all(A));
    int result = 0;
    for (int i = 0; i < M - 1; i++) {
        if (A[i] < N) result += N - A[i];
    }
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 3148
a,b,c=map(int,input().split())
# 奇数があったら0回
if any([q%2==1 for q in (a,b,c)]):
  print(0)
  exit()
# 全部偶数で等しいと終わらない
if a==b==c:
  print(-1)
  exit()
# ではなければシミュレーションでOK
cnt=0
while all([q%2==0 for q in (a,b,c)]):
  cnt+=1
  s=a+b+c
  a=s-a
  a//=2
  b=s-b
  b//=2
  c=s-c
  c//=2
print(cnt)


Measured memory_bytes: 61628
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

int w,h;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int f[100][100];
int ans = 0;

bool can(int y,int x) {
	if(0 <= y && y < h && 0 <= x && x < w) return true;
	return false;
}

void dfs(set<int> S, int y, int x) {
	bool flag = true;
	rep(i, 4) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		int id = ny * h + nx;

		if(can(ny, nx) && f[ny][nx] == 1 && S.find(id) == S.end() ) {
			flag = false;
			S.insert(id);
			dfs(S, ny, nx);
			S.erase(id);
		}
	}

	if(flag) {
		ans = max(ans, (int)S.size());
	}
}

int main() {
	while(cin >> w >> h) {
		if(w == 0 && h == 0) break;

		rep(i, h) {
			rep(j, w) cin >> f[i][j];
		}

		ans = 0;
		rep(i, h) {
			rep(j, w) {
				if(f[i][j]){
					set<int> S;
					S.insert(i * h + j);
					dfs(S, i, j);
				}
			}
		}

		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1260
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int N=1e6;

int main(){
	int a,b,c;
	int i;
	scanf("%d%d%d",&a,&b,&c);
	for(i=0;i<N;i++){
		if((a*i%b)==c){ 
			printf("YES\n");
					break;
		}
	}
	if(i==N) printf("NO\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int MAXN = 200005;
const int MAXS = (1 << 18) + 5;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

template <typename T> inline void cmax(T &x, T y) {
	if (x < y) x = y;
}

int n, V, x[MAXN], ok[MAXN];
int v[20], m, S;

struct Work {
	int lbd[MAXN], rbd[20][MAXN], cnt[20];
	int dp[MAXS];
	
	void work() {
		for (int i = 0; i <= m; ++i) {
			for(int j = 1, lst = 0; j <= n; ++j){
		        if (j < n && abs(x[j + 1] - x[j]) <= v[i]) continue;
		        for (int k = lst + 1; k <= j; ++k) {
		        	rbd[i][k] = j;
		        	if (i == m) lbd[k] = lst + 1;
		        }
		        lst = j;
		    }
		}
		for (int s = 0; s < S; ++s) {
			for (int i = 0; i < m; ++i) {
				if ((s >> i) & 1) continue;
				cmax(dp[s | (1 << i)], rbd[i][dp[s] + 1]);
			}
		}
	}
} L, R;

void init() {
	read(n); read(V);
	for (int i = n; i >= 1; --i) {
		read(x[i]);
	}
	for (; V; V /= 2) {
		v[m++] = V;
	}
	v[m] = 0;
	reverse(v, v + m + 1);
	S = (1 << m);
}

void solve() {
	R.work();
	reverse(x + 1, x + n + 1);
	L.work();
	for (int s = 0; s < S; ++s) {
		int l = min(n, L.dp[s] + 1), r = max(1, n - R.dp[(S - 1) ^ s]);
		if (l > r) {
			mset(ok, -1); break;
		} else if (L.rbd[m][l] == L.rbd[m][r]) {
			ok[L.rbd[m][r]] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		puts(ok[L.rbd[m][i]]? "Possible" :"Impossible");
	}
}

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



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

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    int n;
	cin >> n;
	vector<int> a(n + 2);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	a[0] = 0;
	a[n + 1] = 0;
	int64_t tot = 0;
	for (int i = 1; i <= n + 1; i++) {
		tot += abs(a[i] - a[i - 1]);
	}
	for (int i = 1; i <= n; i++) {
		cout << tot - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]) << endl;
	}
    return 0;
}

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

void pt(char a,int k){
  for(int i=0;i<k;i++)cout<<a;
}

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int x=c-a;
  int y=d-b;
  pt('U',y);
  pt('R',x+1);
  pt('D',y+1);
  pt('L',x+1);
  cout<<"UL";
  pt('U',y+1);
  pt('R',x+1);
  pt('D',y+1);
  pt('L',x);
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	int r;
	r=a%b;
	while(r!=0)
	{
		a=b;
		b=r;
		r=a%b;
	}
	if(c%b==0)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

Measured memory_bytes: 128
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))

ans = []
def chr(a,l,r):
    global ans
    if a == n:
        ans.append(r-l)
    else:
        chr(a+1,l+c[a],r+v[a])
        chr(a+1,l,r)
chr(0,0,0)
print(max(ans))

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

int a, b;

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

	cin >> a >> b;
	if (a<=0 and b>=0) {
		cout << "Zero";
	}
	else if (a>0 and b>0) {
		cout << "Positive";
	}
	else if (a<0 and b<0) {
		int x=b-a+1;
		if (x%2==0) {
			cout << "Positive";
		}
		else {
			cout << "Negative";
		}
	}

}

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

int main(){
    vector<int> x(5);
    rep(i, 5) cin>>x[i];

    rep(i,5){
        if(x[i]==0){
            cout << i+1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3588
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))

using lint = long long;
using pii = pair< int, int >;

template< typename T > using Vec = vector< T >;

template< typename T > bool in_range(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool in_range(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }

template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }

int bitCount(int x) { return __builtin_popcount(x); }
int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double EPS = 1e-9;
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//

int N, A[200005], B[200005];

int main() {
	cin >> N;
	
	bool flag = true;
	for_(i,0,N) {
		cin >> A[i] >> B[i];
		flag &= (A[i] == B[i]);
	}
	
	if (flag) {
		puts("0");
		return 0;
	}
	
	lint ans = 0;
	vector< lint > rem;
	for_(i,0,N) {
		if (A[i] <= B[i]) {
			ans += B[i];
		} else {
			rem.push_back(B[i]);
		}
	}
	
	sort(allof(rem));
	ans += accumulate(rem.begin() + 1, rem.end(), lint());
	cout << ans << endl;
}
//--------------8---------------->> coding space <<-----------------8-------------//


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
int u[1100000];
vector<int> y;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d=0,e=0,f=0,g=0;
  cin >>a;
  for(int n=0;n<a;n++){
    cin >>u[n];
  }
  sort(u,u+a);
  b=u[0],e=1;
  for(int n=1;n<a;n++){
    if(b!=u[n]){
      if(b<=e) d+=e-b;
      else d+=e;
      e=1,b=u[n];
    }
    else e++;
  }
  if(b<=e) d+=e-b;
  else d+=e;
  cout <<d<<'\n';
  return (0);
}


Measured memory_bytes: 640
# coding: utf-8
# Your code here!

N = int(input())
numbers_753 = dict({3: 0, 5: 1, 7: 2})

count = 0
x = 1
while True:
    if x > N:
        break
    
    count_char = [0, 0, 0]
    temp_x = x
    digit = 0
    while True:
        char = temp_x % 10
        temp_x = temp_x // 10
        
        if char in numbers_753:
            count_char[numbers_753[char]] += 1
            digit += 1
        elif digit > 0:
            x += 10 ** digit
            x -= 2
            break
        else:
            break
        
        if temp_x == 0:
            if count_char[0] * count_char[1] * count_char[2] > 0:
                count += 1
            break
    x += 2
        
print(count)

Measured memory_bytes: 3064
package main

import (
  "fmt"
)

func num(n int) int {
   count := 1
  for n >= 10 {
    n = n / 10
    count += 1
  }
  return count
}

func main(){
  var N int
  fmt.Scan(&N)
  
  result := 0
  for i := 1; i <= N; i++ {
    if num(i) % 2 != 0 {
      result += 1
    }
  }
  fmt.Println(result)
}

Measured memory_bytes: 1772
#pragma GCC optimize("Ofast")

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int maxn = 1 << 20;

template <typename T>
struct qqueue {
	T arr[maxn];
	int l, r;
	qqueue() { l = r = 0; }
	void push(T x) { arr[r] = x; r = (r + 1) & (maxn - 1); }
	T front() { return arr[l]; }
	void pop() { l = (l + 1) & (maxn - 1); }
	bool empty() { return l == r; }
};

qqueue <int> que;
int n, m, dis[maxn];
vector <int> g[maxn], all[maxn];
unordered_map <int, vector <int> > g1[maxn];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		u --; v --;
		g1[u][c].push_back(v);
		g1[v][c].push_back(u);
		all[c].push_back(u);
		all[c].push_back(v);
	}
	int cc = n;
	for (int c = 1; c <= 1000000; c ++) {
		sort(all[c].begin(), all[c].end());
		all[c].erase(unique(all[c].begin(), all[c].end()), all[c].end());
		for (int i = 0; i < (int) all[c].size(); i ++) {
			if (dis[all[c][i]] == c) continue;
			que.push(all[c][i]);
			dis[all[c][i]] = c;
			while (!que.empty()) {
				int u = que.front(); que.pop();
				g[u].push_back(cc);
				g[cc].push_back(u);
				for (int i = 0; i < (int) g1[u][c].size(); i ++) {
					int v = g1[u][c][i];
					if (dis[v] != c) {
						dis[v] = c;
						que.push(v);
					}
				}
			}
			cc ++;
		}
	}
	memset(dis, -1, sizeof dis);
	dis[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		for (int i = 0; i < (int) g[u].size(); i ++) {
			int v = g[u][i];
			if (!~dis[v]) {
				dis[v] = dis[u] + 1;
				que.push(v);
			}
		}
	}
	printf("%d\n", !~dis[n - 1] ? -1 : dis[n - 1] / 2);
	return 0;
}



Measured memory_bytes: 168064
use std::io::{Read};
use std::io::{stdout, Write};
use std::str::{SplitWhitespace, FromStr};
use std::collections::{VecDeque, HashMap};

struct IO<'a> {
    sw: SplitWhitespace<'a>,
    out: Vec<u8>,
}

impl IO<'_> {
    pub fn read<T: FromStr>(&mut self) -> T where
        <T as std::str::FromStr>::Err: std::fmt::Debug {
        self.sw.next().unwrap().parse().unwrap()
    }
}

// AtCoder Beginner Contest 146 D - Coloring Edges on Tree
fn main() {
    /* BEGIN TEMPLATE */
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let sw = buf.split_whitespace();
    let _stdout = stdout();
    let mut io = IO{sw, out: Vec::new()};
    /* END TEMPLATE */
    solve(&mut io);
    stdout().write_all(&io.out).unwrap();
}

fn solve(io: &mut IO) {
    let n: usize = io.read();
    let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n+1];
    let mut edges: Vec<(usize, usize)> = Vec::with_capacity(n-1);
    let mut edge_colors: HashMap<(usize, usize), usize> = HashMap::new();
    (0..n-1).for_each(|_| {
        let (a, b): (usize, usize) = (io.read(), io.read());
        tree[a].push(b);
        tree[b].push(a);
        if a < b {
            edges.push((a, b));
        } else {
            edges.push((b, a));
        }
    });
    let mut colors: Vec<usize> = vec![0; n+1];
    let mut done = vec![false; n+1];
    done[1] = true;
    colors[1] = 0;
    let mut count = colors[1];
    let mut queue: VecDeque<usize> = VecDeque::new();
    queue.push_back(1);
    while !queue.is_empty() {
        let length = queue.len();
        (0..length).for_each(|_|{
            let mut color: usize = 0;
            let front = queue.pop_front().unwrap();
            tree[front].iter().for_each(|&t|{
                if !done[t] {
                    color += 1;
                    if color == colors[front] {
                        color += 1;
                    }
                    colors[t] = color;
                    if color > count {
                        count = color;
                    }
                    done[t] = true;
                    queue.push_back(t);
                    if front < t {
                        *edge_colors.entry((front, t)).or_default() = color;
                    } else {
                        *edge_colors.entry((t, front)).or_default() = color;
                    }
                }
            });
        })
    }
    writeln!(io.out, "{}", count).unwrap();
    edges.iter().for_each(|&edge| {
        writeln!(io.out, "{}", *edge_colors.entry(edge).or_default()).unwrap();
    })
}

Measured memory_bytes: 16636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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; }
ll mod = 1e9+7;


int main(){
    int a,b,c; cin >> a >> b >> c;
    int ans=a+b+c;
    if(ans>=22){
        cout << "bust"  << endl;
    }else{
        cout << "win"<< endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) > (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define R cin>>
#define i64 unsigned long long
#define repr(i, n) REPR(i, n, 0)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define in(a) insert(a)
#define P(p) cout<<(p)<<endl;
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SORT(a) sort((a).begin(), (a).end())
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long int> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll mod = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;
template<typename T> void co(T e){cout << e << "\n";}
template<typename T> void co(const vector<T>& v){for(const auto& e : v)
    { cout << e << " "; } cout << "\n";}
ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0) return a;
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}
ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return a * b / g;
}
bool prime(ll n) {
    for (ll i = 2; i <= sqrt(n); i++) {
        if (n%i == 0)return false;
    }
    return n != 1;
}


int pow(ll x, ll y, ll mod){
    ll ret=1;
    for(;y;y>>=1,x=1ll*x*x%mod){
        if(y&1) ret=1ll*ret*x%mod;
    }
    return ret;
}
void kill()
{
    cout << "No" << endl;
    exit(0);
}

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

void  twice(int& a){
    std::cout << a << std::endl;
    a *= 2;
    std::cout << a << std::endl;
}

int dp[5000][5002];
char s[5010];

int main(){
    sonic();
    int n, ss;
    scanf("%d %s", &n, s);
    ss = strlen(s);
    dp[0][0]=1;
    dp[0][1]=2;
    REP(i,1,n)rep(j,n+1){
        if(j!=0)dp[i][j]=(dp[i][j]+dp[i-1][j-1]*2)%mod;
        else dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
        dp[i][j]=(dp[i][j]+dp[i-1][j+1])%mod;
    }
    co(1ll*dp[n-1][ss]*pow(pow(2,ss,mod),mod-2,mod)%mod);
}


Measured memory_bytes: 101368
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,num=0,t;
	scanf("%d",&n);
	int a[100000];
	for (int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	printf("%d",a[n/2] - a[n/2 - 1]);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	int A, B, C; cin >> A >> B >> C;
	cout << (((A + B) >= C) ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256