akhauriyash/Code-Regression huggingface dataset:
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}


fn main() {
    let line: Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let n = line[0];
    let m = line[1];
    let mut g = vec![Vec::new(); n];
    let mut e = Vec::new();
    for i in 0..m {
        let line: Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();
        let a = line[0] - 1;
        let b = line[1] - 1;
        let c = line[2] as i64;

        g[a].push((b, i));
        g[b].push((a, i));
        e.push(c)
    }

    let mut used = vec![false; m+1];
    for i in 0..n {
        let mut que = BinaryHeap::new();
        que.push((0 as i64, i, m));
        let mut memo = vec![n; n];
        let mut cost = vec![1_000_010; n];
        while !que.is_empty() {
            let (cur, x, ei) = que.pop().unwrap();
            if cost[x] < -cur {
                continue;
            }
            used[ei] = true;
            if cost[x] == -cur {
                continue;
            }
            cost[x] = -cur;

            for i in 0..g[x].len() {
                let (nxt, ei) = g[x][i];
                que.push((cur - e[ei], nxt, ei));
            }
        }
    }
    let ans = used.iter().fold(0, |acc, val| if !*val { acc + 1 } else { acc });

    println!("{}", ans);
}


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


void solve(){
    ll n,x,t;
    cin>>n>>x>>t;
    if(n%x == 0){
        cout << t*(n/x);
    }
    else{
        cout << t*((n/x)+1);
    }


}


int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int q;
    q=1;
    // cin>>q;
    while(q--) solve();


    return 0;
}


Measured memory_bytes: 3632
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[1]*100010
for i in a:
    dp[i]=0
for i in range(2,n+1):
    if dp[i]:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Measured memory_bytes: 460004
import java.util.stream.IntStream;

class Main {
	public static void main(String[] argv){
		IntStream.rangeClosed(1, 9).forEach(n->{
			IntStream.rangeClosed(1, 9).forEach(m->{
				System.out.println(n+"x"+m+"="+(n*m));
			});
		});
	}
}

Measured memory_bytes: 30704
X = int(input())
# print(X)

count = 0
list = {}
for i in range(10**9):
    if (i * 500) > X:
        list["500"] = (i-1)
        X = X - 500 * (i - 1)
        break
for i in range(10**9):
    if (i * 5) > X:
        list["5"] = (i-1)
        X = X - 5 * (i - 1)
        break

# print(list)

a = list["500"]*1000
b = list["5"]*5

c = a+b


print(c)

Measured memory_bytes: 3064
s=input()
s=list(s)
n=len(s)
a=s[:(n-1)//2]
b=s[(n+2)//2:]
m=len(a)
yes=0
for i in range((n-1)//2):
    if s[i]==s[-(i+1)]:
        yes+=1
if n==3:
    if yes==1:
        print('Yes')
    else:
        print('No')
else:    
    if m%2==1:
        for i in range((m-1)//2):
            if a[i]==a[-(i+1)]:
                yes+=1
            if b[i]==b[-(i+1)]:
                yes+=1
    else:
       for i in range(m//2):
            if a[i]==a[-(i+1)]:
                yes+=1
            if b[i]==b[-(i+1)]:
                yes+=1
    if yes>=(m-1)+(n-1)//2:
        print('Yes')
    else:
        print('No')


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

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

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

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

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

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

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

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

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}
impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
    }
    let val1 = a * n;
    let val2 = b;
    if val1 < val2 {
        println!("{}", val1);
    } else {
        println!("{}", val2);
    }
}


Measured memory_bytes: 4352
import bisect,collections,copy,itertools,math,numpy,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
A,B,C = LI()
ans = 0
if A%2 or B%2 or C%2:
    ans = 0
elif A==B==C:
    ans = -1
else:
    while 1:
        if A%2 or B%2 or C%2:
            break
        A,B,C = (B+C)//2,(A+C)//2,(A+B)//2
        ans += 1
print(ans)


Measured memory_bytes: 12064
import java.util.Arrays;
import java.util.Scanner;

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

    char[] S = scanner.next().toCharArray();
    Arrays.sort(S);
    for (int i = 1; i < S.length; i++) {
      if (S[i] == S[i - 1]) {
        System.out.println("no");
        return;
      }
    }
    System.out.println("yes");
  }
}


Measured memory_bytes: 21844
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }




void main() {
  try {
    for (; ; ) {
      const T = readToken();
      const L = cast(int)(T.length);
      
      long ans;
      auto used = new bool[L];
      
      int len;
      foreach (i; 0 .. L) {
        if (T[i] == '1') {
          used[i] = true;
          ++len;
          ans += (len + 1) / 2;
        }
      }
      int num;
      foreach (i; 0 .. L) {
        if (T[i] == '1') {
          ++num;
        } else {
          if (num % 2 != 0) {
            used[i] = true;
            ++num;
            ++len;
            ans += (len + 1) / 2;
          }
        }
      }
      
      auto poss = new int[L];
      poss[] = -1;
      int pos;
      foreach (i; 0 .. L) {
        if (used[i]) {
          poss[i] = pos++;
        }
      }
      debug {
        writeln("T = ", T);
        writeln(ans, " ", used, " ", len, " ", num, " ", poss);
      }
      
      int head = (len + 1) / 2;
      int tail0, tail1;
      foreach_reverse (i; 0 .. L) {
        if (T[i] == '1') {
          if (poss[i] % 2 == 0) {
            --head;
            ++tail0;
          } else {
            ++tail1;
          }
        } else {
          if (!used[i]) {
            swap(tail0, tail1);
            debug {
              writeln(i, ": ", head, " ", tail0, " ", tail1);
            }
            ans += head + tail0;
          }
        }
      }
      writeln(ans);
      
      debug {
        int brt;
        auto perm = iota(L).array;
        do {
          int score;
          auto vis = new bool[L];
          foreach (i; perm) {
            vis[i] = true;
            int p;
            foreach (j; 0 .. L) {
              if (vis[j]) {
                if (T[j] == '1' && p % 2 == 0) {
                  ++score;
                }
                ++p;
              }
            }
          }
          chmax(brt, score);
        } while (perm.nextPermutation);
        writeln("brt = ", brt);
        assert(brt == ans);
      }
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 4068
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstdio>
#include <queue>

using namespace std;

typedef unsigned int uint;

const int INF = INT_MAX >> 1;
const int N = 505;
const int W = 32;
const int B = N / W + 2;
const int M = 200005;

typedef pair<int , int> data;

#define mkp(a , b) make_pair(a , b)
#define ft first
#define sd second

queue<data> q;

uint done[N][B] , graph[N][B];
int tov[M] , nxt[M];
bool vis[N];
int f[N][N];
int last[N];
int n , m , tot , cirlen , ans;

inline void set(uint *bits , int x){bits[x / W] |= 1 << x % W;}

inline void insert(int x , int y){tov[++ tot] = y , nxt[tot] = last[x] , last[x] = tot;}

int dfs(int x , int dep = 0)
{
	vis[x] = 1;
	for (int i = last[x] , y , ret;i;i = nxt[i])
	{
		if ((y = tov[i]) == 1) return dep + 1;
		if (!vis[y])
		{
			ret = dfs(y , dep + 1);
			if (ret) return ret;
		}
	}
	return 0;
}

void bfs()
{
	ans = INF;
	if (!cirlen) return;
	for (int i = 0;i < cirlen;++ i)
		for (int x = 1;x <= n;++ x)
			f[i][x] = INF;
	f[0][1] = 0 , q.push(mkp(0 , 1)) , set(done[0] , 0);
	for (data cur;!q.empty();)
	{
		cur = q.front() , q.pop();
		for (int i = 0 , nxti = cur.ft == cirlen - 1 ? 0 : cur.ft + 1;i <= (n - 1) / W;++ i)
		{
			uint state = ~done[nxti][i] & graph[cur.sd][i];
			if (state)
				for (int j = 0 , y = i * W + 1;j < W;++ j , ++ y)
					if ((state >> j) & 1)
					{
						f[nxti][y] = f[cur.ft][cur.sd] + 1;
						q.push(mkp(nxti , y)) , set(done[nxti], y - 1);
					}
		}
	}
	for (int i = 0 , ret;i < cirlen;++ i)
	{
		ret = 0;
		for (int x = 1;x <= n;++ x) ret = max(ret , f[i][x]);
		ans = min(ans , ret);
	}
}

int main()
{
	//freopen("f.in" , "r" , stdin) , freopen("f.out" , "w" , stdout);
	scanf("%d%d" , &n , &m);
	for (int i = 1 , x , y;i <= m;++ i) scanf("%d%d" , &x , &y) , insert(x , y) , set(graph[x] , y - 1);
	cirlen = dfs(1) , bfs() , printf("%d\n" , ans == INF ? -1 : ans);
	//fclose(stdin) , fclose(stdout);
	return 0;
}


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

int main() {
  string s,l="";
  int q,t,f,rev=0;
  char c;
  cin >> s >> q;
  for(int i=0;i<q;i++) {
    cin >> t;
    if(t==1){
      rev=(rev+1)%2;
    } else {
      cin >> f >> c;
      if(((f-1)+rev)%2==0) l.push_back(c);
      else s.push_back(c);
    };
  };
  if(rev==1) {
    reverse(s.begin(),s.end());
    cout << s << l << endl;
  } else {
    reverse(l.begin(),l.end());
    cout << l << s << endl;
  };
}

Measured memory_bytes: 960
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

// conversion
//------------------------------------------
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

// typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c)                                                             \
  for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

// clear memory
#define CLR(a) memset((a), 0, sizeof(a))

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                                               \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"                       \
       << " " << __FILE__ << endl;

void solve(long long S) {
  
}

int main() {
  string s;
  cin>>s;
  if(s[0]==s[1] ||s[1]==s[2] ||s[2]==s[3]){
    cout<<"Bad"<<endl;
  }
  else cout<<"Good"<<endl;
  return 0;
}


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

int main(){
  int A,N;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A;
    if(A%2==0 && (A%3)*(A%5)!=0){
      cout<<"DENIED"<<endl;
      return 0;
    }
  }
  cout<<"APPROVED"<<endl;
}

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

int main()
{
   string s;
   cin >> s;
   vector<int> cnt(s.length());
   for(int i = 0; i < s.length(); i++)
   {
      cnt[s[i] - '0']++;
   }
   int ans = min(cnt[0], cnt[1])*2;
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

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

using ll = long long int;
using pll = pair<ll, ll>;

const ll mod = static_cast<ll>(1e9) + 7;

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

    vector<ll> A(N + 1);
    for (auto& a : A) { cin >> a; }

    vector<ll> B(N);
    for (auto& b : B) { cin >> b; }

    ll ans = 0;
    ll rest = 0;

    rep (i, N + 1)
    {
        const ll x = min(A[i], rest);
        ans += x;

        if (i == N) { break; }

        const ll y = min(A[i] - x, B[i]);
        ans += y;

        rest = B[i] - y;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
#define ll long long
#include <cstdint>

int main() {
	string n;
	cin >> n;
	if (n[0] == '9' || n[1] == '9')cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int a[100010], b[100010];
int main()
{
	int A, B, M;
	cin >> A >> B >> M;
	int ans = 0;
	int num = mod;
	for (int i = 0; i < A; i++) {
		cin >> a[i];
		num = min(num, a[i]);
	}
	ans += num;
	num = mod;
	for (int i = 0; i < B; i++) {
		cin >> b[i];
		num = min(num, b[i]);
	}
	ans += num;
	for (int i = 0; i < M; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		x--; y--;
		ans = min(ans, a[x] + b[y] - c);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
import java.io.InputStream;
import java.util.NoSuchElementException;
public class Main {
	public static void main(String[] args)throws Exception{
		int A=nextInt();
		int V=nextInt();
		int B=nextInt();
		int W=nextInt();
		int T=nextInt();
		if(V-W<=0||A==B)
			System.out.println("NO");
		else
			if(Math.abs(A-B)/(V-W)<T){
				System.out.println("YES");
			}
			else
				if(Math.abs(A-B)%(V-W)==0&&Math.abs(A-B)/(V-W)<=T)
					System.out.println("YES");
				else
					System.out.println("NO");
	}
	//FastScanner
	static InputStream in = System.in;
	static  byte[] buffer = new byte[1024];
	static int length = 0, p = 0;
	public static boolean hasNextByte () {
		if (p < length) return true;
		else {
			p = 0;
			try {length = in.read(buffer);}
			catch (Exception e) {e.printStackTrace();}
			if (length == 0) return false;
		}
		return true;
	}
	public static int readByte () {
		if (hasNextByte() == true) return buffer[p++];
		return -1;
	}
	public static boolean isPrintable (int n) {return 33<=n&&n<=126;}
	public static void skip () {
		while (hasNextByte() && !isPrintable(buffer[p])) p++;
	}
	public static boolean hasNext () {skip(); return hasNextByte();}
	public static String next () {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int temp = readByte();
		while (isPrintable(temp)) {
			sb.appendCodePoint(temp);
			temp = readByte();
		}
		return sb.toString();
	}
	public static int nextInt () {return Math.toIntExact(nextLong());}
	public static int[] nextInts (int n) {
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = nextInt();
		return ar;
	}
	public static long nextLong () {
		if (!hasNext()) throw new NoSuchElementException();
		boolean minus = false;
		int temp = readByte();
		if (temp == '-') {
			minus = true;
			temp = readByte();
		}
		if (temp<'0' || '9'<temp) throw new NumberFormatException();
		long n = 0;
		while (isPrintable(temp)) {
			if ('0'<=temp && temp<='9') {
				n *= 10;
				n += temp - '0';
			}
			temp = readByte();
		}
		return minus? -n : n;
	}
}


Measured memory_bytes: 32524
#162C
#Sum of gcd of Tuples (Easy)

import math

k=int(input())+1
ans=0
for a in range(1,k):
    for b in range(1,k):
        g=math.gcd(a,b)
        for c in range(1,k):
            ans+=math.gcd(g,c)
print(ans)

Measured memory_bytes: 9116
#include <stdio.h>
#include <stdlib.h>

int main(){
	int N, i, j, k;
	scanf("%d", &N);
	int *a = (int *)malloc(sizeof(int) * N);
	int *b = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &b[i]);
		b[i]--;
	}
	for(i = 0; i < N; i++){
		if(b[i] > i){
			printf("-1\n");
			return 0;
		}
	}
	int *ans = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		ans[i] = -1;
	}
	for(i = N - 1; i >= 0; i--){
		for(j = 0, k = 0; ; j++){
			if(ans[j] == -1){
				k++;
			}
			if(k > b[i]){
				ans[j] = b[i];
				break;
			}
		}
	}
	for(i = 0; i < N; i++){
		printf("%d\n", ans[i] + 1);
	}
	return 0;
}

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


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a!=c){
        cout << "1" << endl;
    }
    else cout << 0 << endl;
}

Measured memory_bytes: 896
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define int long long
#define endl '\n'

const int N = 100005;
int n, p[N], P[N][20];
int get(int l, int r){
	int k = log2(r - l + 1);
	return max(P[l][k], P[r - (1 << k) + 1][k]);
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i];
	for(int i = 1 ; i <= n ; i ++)
		P[i][0] = p[i];
	for(int j = 1 ; (1 << j) <= n ; j ++)
		for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
			P[i][j] = max(P[i][j - 1], P[i + (1 << (j - 1))][j - 1]);
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		// find safe left
		int safe_l = i, L = 1, R = i;
		while(L <= R){
			int M = (L + R) >> 1;
			if(get(M, i) == p[i]) safe_l = M, R = M - 1;
			else L = M + 1;
		}
		// find safe right
		int safe_r = i;
		L = i, R = n;
		while(L <= R){
			int M = (L + R) >> 1;
			if(get(i, M) == p[i]) safe_r = M, L = M + 1;
			else R = M - 1;
		}
		// check over left
		//cout << "doing on i = " << i << endl;
		//cout << "safe_l = " << safe_l << endl;
		//cout << "safe_r = " << safe_r << endl;
		if(safe_l > 1){
			int over_l = safe_l - 1;
			L = 1, R = over_l - 1;
			while(L <= R){
				int M = (L + R) >> 1;
				if(get(M, safe_l - 2) < p[i]) over_l = M, R = M - 1;
				else L = M + 1;
			}
			//cout << "over_l = " << over_l << endl;
			ans += p[i]*(safe_r - i + 1)*(safe_l - over_l);
		}
		if(safe_r < n){
			int over_r = safe_r + 1;
			L = over_r + 1, R = n;
			while(L <= R){
				int M = (L + R) >> 1;
				if(get(safe_r + 2, M) < p[i]) over_r = M, L = M + 1;
				else R = M - 1;
			}
			//cout << "over_r = " << over_r << endl;
			ans += p[i]*(over_r - safe_r)*(i - safe_l + 1);
		}
	}
	cout << ans;
}


Measured memory_bytes: 16640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;

int R,C;
int main(){
  while(cin>>R>>C&&R&&C){
    int senbei[R][C];
    for(int i=0; i<R; i++) for(int j=0; j<C; j++) cin>>senbei[i][j];
    int ans=0;
    for(int bit=0; bit<(1<<R); bit++){
      int cnt=0;
      for(int i=0; i<C; i++){
        int c=0;
        for(int j=0; j<R; j++){
          if((bit>>j)&1) c+=1-senbei[j][i];
          else c+=senbei[j][i];
        }
        cnt+=max(c,R-c);
      }
      ans=max(ans,cnt);
    }
    cout<<ans<<en
  }
}


Measured memory_bytes: 3468
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let w = read_vec::<i64>();
    let mut w_sum = vec![0; n];
    w_sum[0] = w[0];
    for i in 1..n {
        w_sum[i] = w_sum[i - 1] + w[i];
    }
    debug!(w_sum);

    let mut ans = std::i64::MAX;
    for i in 0..n {
        ans = min(ans, (w_sum[i] - (w_sum[n - 1] - w_sum[i])).abs());
    }

    println!("{:?}", ans);
}

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void){
  char S[100000], a='a';
  char ans;
  int i,j,k;
  int flag=0;
  for(i=0;i<100000;i++)
    S[i]='\0';
  scanf("%s",S);

  for(j=0;j<26;j++){
    flag=0;
    for(i=0;i<100000;i++){
      if(S[i]==a+j){
	flag=1;
	break;
      }
    }
    if(flag==0){
      ans=a+j;
      printf("%c\n",ans);
      return 0;
    }
  }
  printf("None\n");   
  return 0;
}


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

int main(){
    string s;
    cin >> s;

    vector<bool> a(26);

    
    for(int i = 0; i < s.size(); i++){
        a[s[i] - 'a'] = true;
    }
    
    int flag = 0;
    for(int i = 0; i < 26; i++){
        if(a[i] == false){
            flag = 1;
            char c = i + 'a';
            cout << c;
            break;
        }
    }
    if(flag == false) cout << "None";
}


Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
#define LENGHTH 200100
  typedef struct{

    char pname[100];
    int runtime;

  }process;

process runprocess[LENGHTH];

int head,tail;
void enqueue(int);
int dequeue();

int main(){


  int sumdata,rtime,i,data,sumtime;

  sumtime = 0;
  head = 0;
  tail =0;

  scanf("%d%d",&sumdata,&rtime);


  for(i = 0; i < sumdata; i++){

    scanf("%s%d",runprocess[i].pname,&runprocess[i].runtime);

  }

  tail =  sumdata;

  while(head != tail){

    data = dequeue();

    data = data  - rtime;

    if(data > 0){

      enqueue(data);
      sumtime = sumtime + rtime;

	}

    else{

      sumtime = sumtime + runprocess[head-1].runtime;
      printf("%s %d\n",runprocess[head -1].pname,sumtime);

	}

  }

  return 0;
}

void enqueue(int data){

  

  strcpy(runprocess[tail].pname,runprocess[head -1].pname);
  runprocess[tail].runtime = data;
  tail = (tail + 1) % LENGHTH;

  /*  if(tail >= LENGHTH){

      tail = 0;*/


  //  }
}

int dequeue(){

  head = (head + 1) % LENGHTH;

  /*  if(head >= LENGHTH){

      head = 0;*/
  // }
 
  return runprocess[head -1].runtime;

}

Measured memory_bytes: 19836
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <tuple>
#include <ctime>
#include <cmath>
#include <fstream>
#include <sstream>
using namespace std;
#define INF 1000000007
#define PB push_back
#define MP make_pair
#define X first
#define Y second

typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef queue<int> QI;
typedef queue<PII> QII;
typedef map<int,int> MII;
typedef map<string,int> MSI;
typedef set<int> SI;
typedef set<PII> SII;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);
	ll N;
	cin >> N;
	if(!(N%2))
		cout << N << endl;
	else
		cout << 2*N << endl;
return 0;
}


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

int main()
{
	int Aslc[4] ;
	int Bslc[4] ;

	int hit = 0 ;
	int blow = 0 ;

	while( cin >> Aslc[0] >> Aslc[1] >> Aslc[2] >> Aslc[3] >> Bslc[0] >> Bslc[1] >> Bslc[2] >> Bslc[3] )
	{
		for( int i = 0 ; i < 4 ; i ++ )
		{
			for( int j = 0 ; j < 4 ; j ++ )
			{
				if( Aslc[i] == Bslc[j] )
				{
					if( i == j )
					{
						hit ++ ;
					}
					else
					{
						blow ++ ;
					}
				}
			}
		}

		cout << hit << " " << blow << endl ;
		hit = 0 ;
		blow = 0 ;
	}

	return 0 ;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  int a, b, c=0, d=0, e, f, g, n;
  string s, k, t={};
  cin >> n >> s >> k;
  rep(i,0,n){
    t+=s[i];
    t+=k[i];
  }
  co(t);
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main()
{
	int n;cin >> n;
	vector<int> a(n);
	rep(i,n)cin >> a[i];

	deque<int> dq;
	rep(i,n)
	{
		if(i%2) dq.push_front(i);
		else dq.push_back(i);
	}

	if(n%2==0)
	rep(i,n)cout<<a[dq[i]]<<endl;
	else
	{
		for(int i=n-1;i>=0;i--)
		{
			cout<<a[dq[i]]<<endl;
		}
	}
	
	return 0;
}

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

int main(){

        for(int i = 1; i < 10; ++i)
        {
            for(int j = 1; j < 10; ++j)
            {
                cout << i << "x" << j << "=" << i * j << endl;
            }
        }

        return 0;
}

Measured memory_bytes: 3068
import java.io.InputStream
import java.math.BigDecimal
import java.math.BigInteger

private val MOD = 1e9.toLong() + 7

val input = FastScanner()

fun main(args: Array<String>) = input.run {
    val s = nextString()!!.toCharArray()
    val ans = ('a'..'z').map { c ->
        generateSequence(s.map { it == c }.toBooleanArray()) {
            t -> BooleanArray(t.size - 1) { t[it] || t[it + 1] }
        }.indexOfFirst { it.all { it } }
    }.min()
    println(ans)
}

fun String.toBigInteger() = BigInteger(this)
fun String.toBigDecimal() = BigDecimal(this)

class FastScanner(private val input: InputStream = System.`in`) {
    private val sb = StringBuilder()
    private val buffer = ByteArray(4096)
    private var pos = 0
    private var size = 0

    fun nextString(): String? {
        var c = skipWhitespace()
        if (c < 0) return null

        return sb.run {
            setLength(0)

            do {
                append(c.toChar())
                c = read()
            } while (c > ' '.toInt())

            toString()
        }
    }

    fun nextLine(): String? {
        var c = read()
        if (c < 0) return null

        return sb.run {
            setLength(0)

            while (c >= 0 && c != '\n'.toInt()) {
                append(c.toChar())
                c = read()
            }

            toString()
        }
    }

    fun nextLong(): Long {
        var c = skipWhitespace()

        val sign = if (c == '-'.toInt()) {
            c = read()
            -1
        } else 1

        var ans = 0L

        while (c > ' '.toInt()) {
            ans = ans * 10 + c - '0'.toInt()
            c = read()
        }

        return sign * ans
    }

    fun nextInt() = nextLong().toInt()
    fun nextDouble() = nextString()?.toDouble() ?: 0.0
    fun nextBigInteger(): BigInteger = nextString()?.toBigInteger() ?: BigInteger.ZERO
    fun nextBigDecimal(): BigDecimal = nextString()?.toBigDecimal() ?: BigDecimal.ZERO

    fun nextStrings(n: Int) = Array<String>(n) { nextString() ?: "" }
    fun nextInts(n: Int) = IntArray(n) { nextInt() }
    fun nextLongs(n: Int) = LongArray(n) { nextLong() }
    fun nextDoubles(n: Int) = DoubleArray(n) { nextDouble() }
    fun nextBigIntegers(n: Int) = Array<BigInteger>(n) { nextBigInteger() }
    fun nextBigDecimals(n: Int) = Array<BigDecimal>(n) { nextBigDecimal() }

    fun nextStrings(n: Int, m: Int) = Array(n) { nextStrings(m) }
    fun nextInts(n: Int, m: Int) = Array(n) { nextInts(m) }
    fun nextLongs(n: Int, m: Int) = Array(n) { nextLongs(m) }
    fun nextDoubles(n: Int, m: Int) = Array(n) { nextDoubles(m) }
    fun nextBigIntegers(n: Int, m: Int) = Array(n) { nextBigIntegers(m) }
    fun nextBigDecimals(n: Int, m: Int) = Array(n) { nextBigDecimals(m) }

    private fun skipWhitespace(): Int {
        while (true) {
            val c = read()
            if (c > ' '.toInt() || c < 0) return c
        }
    }

    private fun read(): Int {
        while (pos >= size) {
            if (size < 0) return -1
            size = input.read(buffer, 0, buffer.size)
            pos = 0
        }
        return buffer[pos++].toInt()
    }
}


Measured memory_bytes: 31784
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int m;
int d, c;

signed main() {
	
	cin >> m;
	int i;
	int x = 0;
	int ketasuu = 0;
	for (i = 0; i < m; i++) {
		cin >> d >> c;
		x += d * c;
		ketasuu += c;
	}
	
	//0-9 ; 0
	//10-18 :1
	//19-27 ;2
	//(x - 9) / 9の小数点切り上げ
	int ans = 0;
	if (x > 0) ans += (x - 1) / 9;
		
	cout << ans + ketasuu - 1 << endl;
	return 0;
}

Measured memory_bytes: 256
# c = list(map(int, input().split()))
# a, b, c = map(int, input().split())
# a = [list(map(int, list(input()))) for i in range(n)]
import sys
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
n = int(input())
v = 0

for i in range(0, n):
    v = int(input())
    if v in a1:
        a1[a1.index(v)] = 0
    if v in a2:
        a2[a2.index(v)] = 0
    if v in a3:
        a3[a3.index(v)] = 0


if sum(a1) == 0:
    print('Yes')
    sys.exit()

if sum(a2) == 0:
    print('Yes')
    sys.exit()

if sum(a3) == 0:
    print('Yes')
    sys.exit()

if a1[0] == a2[0] == a3[0] == 0:
    print('Yes')
    sys.exit()

if a1[1] == a2[1] == a3[1] == 0:
    print('Yes')
    sys.exit()

if a1[2] == a2[2] == a3[2] == 0:
    print('Yes')
    sys.exit()

if a1[0] == a2[1] == a3[2] == 0:
    print('Yes')
    sys.exit()

if a3[0] == a2[1] == a1[2] == 0:
    print('Yes')
    sys.exit()
    
print('No')    


Measured memory_bytes: 3064
year,month,day = input().split('/')

if int(year) >= 2019 :
	if int(month) >= 5 :
		print('TBD')
		exit()
	else:
		print('Heisei')
		exit()
	print('TBD')
	exit()
else:
	print('Heisei')
	exit()


Measured memory_bytes: 2940
use std::io::stdin;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let first_line: Vec<usize> = buf.trim().split_whitespace().map(|iter| iter.parse::<usize>().unwrap()).collect();
    let k = first_line[0];
    let n = first_line[1];

    buf.clear();
    stdin().read_line(&mut buf).unwrap();
    let mut houses: Vec<i32> = buf.trim().split_whitespace().map(|iter| iter.parse::<i32>().unwrap()).collect();
    houses.sort();
    let mut distances: Vec<i32> = Vec::new();
    for index in 0..n-1{
        let distance = houses[index + 1] - houses[index];
        distances.push(distance)
    }
    distances.push(k as i32 - *houses.last().unwrap() + *houses.first().unwrap());
    distances.sort();
    println!("{}", k as i32 - *distances.last().unwrap())
}


Measured memory_bytes: 10620
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 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;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            long N = in.nextLong();
            StringBuilder sb = new StringBuilder();
            while (N > 0)
            {
                N--;
                sb.append((char) ((N % 26) + 'a'));
                N /= 26;
            }
            out.println(sb.reverse().toString());
        }

    }
}



Measured memory_bytes: 27156
main(){
    int i,n,m,k,a,b,A,B,dist[101][101];
    scanf("%d%d",&n,&k);
m=k;
        /*initialize*/
        memset(dist,11,sizeof(dist));
        for(i=1;i<=n;i++)dist[i][i]=0;
        for(;k>0;k--){
            scanf("%d,%d,%d,%d",&a,&b,&A,&B);
            dist[a][b]=A,dist[b][a]=B;
        }
  
        {/*warshall-floyd*/
            int k,i,j;
for(;m>0;m--)
            for(k=1;k<=n;k++)
                for(i=1;i<=n;i++)
                    for(j=1;j<=n;j++)
                        if(dist[i][j]>dist[i][k]+dist[k][j])
                            dist[i][j]=dist[i][k]+dist[k][j];
        }
  
        {/*query*/
            scanf("%d,%d,%d,%d",&a,&b,&A,&B);
            printf("%d\n",A-B-dist[a][b]-dist[b][a]);
        }
    exit(0);
}

Measured memory_bytes: 644
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int NIL = -1;
const int INF = (1<<21);
const long long MOD = 1e9+7;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};

int main() {
  int r, D, x; cin >> r >> D >> x;
  for (int i = 1; i <= 10; ++i) {
    int new_x = r * x - D;
    cout << new_x << endl;
    x = new_x;
  }
}


Measured memory_bytes: 3636
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

# 最小公倍数
def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

def LI(): return list(map(int, sys.stdin.readline().split()))

A,B,C,D = LI()
A -= 1
upper_cnt = B - (B // C + B // D - B //lcm(D,C))
lower_cnt = A - (A // C + A // D - A //lcm(C,D))


print(upper_cnt-lower_cnt)


Measured memory_bytes: 5576
#include <stdio.h>

int main(void) {
	int a, b;
	scanf("%d", &a);
	scanf("%d", &b);
	if (a < b)
	printf("a < b\n");
	else if (a > b)
	printf("a > b\n");
	else
	printf("a == b\n");
	return 0;
}

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

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; }
#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__)

int main(){
    int h,w;
    cin>>h>>w;
    int n;
    cin>>n;
    int a[n];
    rep(i,n) cin>>a[i];
    int ans[h][w];
    int cur=0;
    bool isreverse=0;
    rep(i,h) rep(j,w){
        if(a[cur]==0)++cur;
        if(!isreverse){
            ans[i][j]=cur+1;
            a[cur]--;
            if(j==w-1&&a[cur]!=0){
                isreverse=1;
            }
        }
        else{
            ans[i][w-1-j]=cur+1;
            a[cur]--;
            if(j==w-1&&a[cur]!=0){
                isreverse=0;
            }
        }
    }
    rep(i,h){
        rep(j,w){
            if(j)cout<<" ";
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}


Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

public class Main {
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		final int q = sc.nextInt();
		
		LinkedList<String>  name_queue = new LinkedList<String>();
		LinkedList<Integer> time_queue = new LinkedList<Integer>();
		
		for(int i = 0; i < n; i++){
			name_queue.add(sc.next());
			time_queue.add(sc.nextInt());
		}
		
		int total_time = 0;
		while(!time_queue.isEmpty()){
			final String name = name_queue.poll();
			final int time = time_queue.poll();
			
			if(time > q){
				total_time += q;
				name_queue.add(name);
				time_queue.add(time - q);
			}else{
				total_time += time;
				System.out.println(name + " " + total_time);
			}
			
		}
		
		
		
	}
}

Measured memory_bytes: 66932
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

  int a, b;
  cin >> a >> b;
  for(int i=1; i<4; i++){
    if(i!=a && i!=b){
      cout << i << endl;
    }
  }

	return 0;
}

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

using namespace std;

int main(){
	string s;
	cin>>s;
	
	for(int i=0;i<s.size();i++)
	{
		if((i+1)%2==0){
			if(s[i]!='L'&&s[i]!='U'&&s[i]!='D'){
					cout<<"No";
					return 0;
				}
			}else
			{
				if(s[i]!='R'&&s[i]!='U'&&s[i]!='D'){
					cout<<"No";
					return 0;
				}
			}
	}
	
	cout<<"Yes";
	
	return 0;
	}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int main() {
	int n;
	
	while (cin >> n, n) {
		vector< int > ii(n), p(n), q(n), r(n);
		for_(i,0,n) cin >> ii[i] >> p[i] >> q[i] >> r[i];
		
		int P, Q, R, C;
		cin >> P >> Q >> R >> C;
		
		vector< int > ans;
		for_(i,0,n) {
			if (p[i] > P || q[i] > Q || r[i] > R || 4 * p[i] + 9 * q[i] + 4 * r[i] > C) continue;
			ans.push_back(ii[i]);
		}
		
		if (ans.size() == 0) cout << "NA" << endl;
		else for_(i,0,(int)ans.size()) cout << ans[i] << endl;
	}
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
using namespace std;
// URDL
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
long long mod = 1e9+7;
//

int main(){
  long long w, h, x, y;
  cin >> w >> h >> x >> y;
  cout << w * h * 1.0 / 2 << " " << ((x*2 == w && y*2 == h)?1:0) << endl;

  return 0;
}


// EOF


Measured memory_bytes: 256
from functools import reduce

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n=int(input())
l=list(map(int,input().split()))

m=lcm_list(l)
f=0

for i in range(n):
  f+=(m-1)%l[i]
  
print(f)

Measured memory_bytes: 3812
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using ll = long long;

void PrintV(const vector<ll> v) {

    for(int i = 0; i < v.size(); ++i)
        cout << v[i] << "\t";
    cout << endl;

}

int main() {

    int n;

    cin >> n;

    vector<ll> v(n);

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

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

    vector<ll> sumV(n, 0);

    sumV[0] = v[0];

    for(int i = 1; i < n; ++i) 
        sumV[i] += sumV[i - 1] + v[i];

 //   PrintV(v);
 //   PrintV(sumV);

    int count = 1;

    for(int i = n - 2; i >= 0; --i) {

        if(v[i + 1] > 2 * sumV[i])
            break;
        
        count++;

    }

    cout << count << endl;

    return 0;

}

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

int main(void) {
  int N;
  string S;
  cin >> N >> S;
  vector<int> west(N);
  vector<int> east(N);
  west[0] = (S[0] == 'W' ? 1 : 0);
  east[0] = 1 - west[0];
  for (int i = 1; i < N; i++) {
    west[i] = west[i - 1] + (S[i] == 'W' ? 1 : 0);
    east[i] = i + 1 - west[i];
  }

  int ans = east[N - 1] - east[0];
  for (int i = 1; i < N - 1; i++) {
    ans = min(ans, west[i - 1] + east[N - 1] - east[i]);
  }
  ans = min(ans, west[N - 2]);

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

Measured memory_bytes: 3076
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) {
#if DEBUG
        //MyDebugger.MakeTestCase("../TextFile2.txt"); return;
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static long mod = 1000000000 + 7;

    static object process(TextReader input) {
        var spl   = input.ReadLine().Split(' ');
        var x     = int.Parse(spl[0]);
        var y     = int.Parse(spl[1]);

        if ((x + y) % 3 != 0) return 0;

        //n+2m=x
        //2n+m=y
        var n = (2 * y - x) / 3;
        var m = y-2*n;

        if (n < 0 || m < 0) return 0;

        return CombinationMod(n+m, n);
    }
    
    static long CombinationMod(long m, long n) {
        Func<long, long, long> ModPow = (x1, x2) => {
            long ans = 1;
            while (x2 > 0) {
                if (x2 % 2 == 1) {
                    ans = (ans * x1) % mod;
                }
                x1 = (x1 * x1) % mod;
                x2 /= 2;
            }
            return ans % mod;
        };
        Func<long, long> ModFact = (x1) => {
            long ans = 1;
            for (long i = x1; i > 0; i--)
                ans = (ans * i) % mod;
            return ans;
        };

        var a = ModFact(m);
        var b = (ModFact(n) * ModFact(m-n)) % mod;
        long bb = ModPow(b, mod - 2);
        return (a * bb) % mod;
    }
}


Measured memory_bytes: 13140
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
end = A[-1] * F[0] + 1
start = -1


def decision(n):
    k = K
    for a, f in zip(A, F):
        if a * f > n:
            k -= a - n // f
        if k < 0:
            return False
    return True

def calc():
    e = end
    s = start
    while e - s > 1:
        mid = (e + s)//2
        if decision(mid):
            e = mid
        else:
            s = mid
    return e


print(calc())

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

int n;
int x[100005];
int total = 0;

int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    x[0] = x[n+1] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x[i]);
        total += abs(x[i] - x[i-1]);
    }
    total += abs(x[n+1] - x[n]);

    for (int i = 1; i <= n; ++i) {
        printf("%d\n", total - abs(x[i] - x[i-1]) - abs(x[i+1] - x[i]) +
               abs(x[i-1] - x[i+1]));
    }
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define space " "
#define MOD (long long) 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename T> void __f(const char* variable_name, T&& value){cout << variable_name << ": " << value << endl;}
template <typename T1, typename... T2> void __f(const char* names, T1&& arg1, T2&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}

const ll N = 5e5 + 5;
ll *v;
ll n, k, q, m;
string s;

void solve(){
    cin >> n;
    ll arr[n];
    for(auto &i : arr)  cin >> i;
    for(auto i : arr){
        if(i % 2 == 0){
            if(i % 3 == 0 || i % 5 == 0)
                continue;
            else{
                cout << "DENIED" << endl;
                return;
            }
        }
    }
    cout << "APPROVED" << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    // cout << "\n\nBLAH BLAH BLAH\n\n";
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
N,M = map(int, input().split())
edge = [[] for _ in range(N)] #edge[x]:xから到達できる頂点のリスト
deg = [0]*N #deg[v]:頂点vに入ってくる辺の数
for _ in range(M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1

#topological sort (order:V+E)
from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            deq.append(t)
            ans.append(t)
            
#ans:topological sort された頂点

dp = [0]*N
ans.reverse()
for i in range(N):
    if edge[ans[i]]:
        for v in edge[ans[i]]:
            dp[ans[i]] = max(dp[ans[i]], dp[v]+1)
            
print(max(dp))

Measured memory_bytes: 67616