akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

class SuffixArray {
public:
  string &s;
  vector<int> sa;
  int n;
  SuffixArray(string &str) : s(str){
    n = s.size();
  }
  void construct_sa(){
    sa.resize(n+1);
    vector<int> rank(n+1);
    rep(i,n+1){
      sa[i]=i;
      rank[i] = (i<n)?s[i]:(-1);
    }
    vector<int> tmp(n+1,0);
    for(int k=1; k<=n; k*=2){
      auto comp = [&](int i, int j){
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        int ri = (i+k<=n)?(rank[i+k]):-1;
        int rj = (j+k<=n)?(rank[j+k]):-1;
        return ri < rj;
      };
      sort(all(sa), comp);
      tmp[sa[0]]=0;
      repl(i,1,n+1){
        tmp[sa[i]] = tmp[sa[i-1]];
        if(comp(sa[i-1], sa[i])) tmp[sa[i]]++;
      }
      swap(tmp, rank);
    }
  }
  bool contain(const string &t){
    int m = t.size();
    int l = 0, r = n;
    while(r-l>1){
      int mid = (r+l)/2;
      if(s.compare(sa[mid], m, t) < 0) l = mid;
      else r = mid;
    }
    return s.compare(sa[r], m, t) == 0;
  }
};

int main(){
  string t;
  int q;
  cin>>t>>q;

  SuffixArray sa(t);
  sa.construct_sa();

  rep(_,q){
    string p;
    cin>>p;
    cout << sa.contain(p) << endl;
  }

  return 0;
}

Measured memory_bytes: 15844
x,y = map(int,input().split())
if y == x:
    print(0)
elif y == 0:
    if x > 0:
        print(x+1)
    else:
        print(-x)
else:
    if abs(y) >= abs(x):
        tmp = abs(y)-abs(x)
        if x>=0 and y>=0:
            print(tmp)
        elif x>=0 and y<0:
            print(tmp+1)
        elif x<0 and y>=0:
            print(tmp+1)
        else:
            print(tmp+2)
    else:
        if x>=0 and y>=0:
            print(-y+x+2)
        elif x>=0 and y<0:
            print(x+y+1)
        elif x<0 and y>=0:
            print(-y-x+1)
        else:
            print(y-x)

Measured memory_bytes: 61780
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <stack>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <iomanip>


int main()
{
	long long w, a, b;

	std::cin >> w >> a >> b;

	if (b < a) {
		std::swap(a, b);
	}

	std::cout << std::max(b - (a + w), 0LL) << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char st[100004],c;
int main()
{
    int i,l,cnt=0;
    scanf("%d\n",&l);
    cin>>st;
    for(i=1;i<l;i++){
        if(st[i]==st[i-1]){cnt++;}
    }
    printf("%d\n",l-cnt);

    return 0;
}


Measured memory_bytes: 384
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 2000100;



int main(){
        _
        ll n,k; cin >> n >> k;
        cout<<min(n%k, k-n%k)<<endl;
return 0;
}




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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int N;cin>>N;
    int T,A;cin>>T>>A;
    T*=1000;
    A*=1000;

    vpint lis;
    rep(i,N){
        int h;cin>>h;
        int t=T-6*h;
        lis.pb(pint(abs(t-A),i));
    }
    sort(all(lis));
    cout<<lis[0].se+1<<endl;
}


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

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
const int N = 1e5;

int n, m, s, t;

vector<int> conn[N];
int dist[N], ans = -1;
set<int> loc[N];

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		conn[a].push_back(b);
	}
	cin >> s >> t;
	--s, --t;
	queue<int> q;
	q.push(s);
	
	
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		
		queue<pair<int, int>> tq;
		tq.push({cur, 0});
		while (!tq.empty()) {
			pair<int, int> v = tq.front();
			tq.pop();
			if (v.second == 3) {
				if (!dist[v.first] && v.first != s) {
					dist[v.first] = dist[cur] + 1;
					q.push(v.first);
					if (v.first == t) {
						tq = {};
						q = {};
						break;
					}
				}
			} else {
				for (int u : conn[v.first]) {
					if (loc[u].insert(v.second + 1).second) tq.push({u, v.second + 1});
				}
			}
		}
	}
	
	dist[t] ? cout << dist[t] : cout << -1;
}


Measured memory_bytes: 28128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	cout << fixed << setprecision(10);
	long double a,b; cin>>a>>b;
	a/=100; b*=100;
	long double c=a*b; 
	ll ans=c;
	cout<<ans;
	return 0;
}


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

using namespace std;

int main(){
  string s;

  cin >> s;

  int a = -1;
  int z = -1;
  bool isSetting = false;
  for(int i=0; i<s.size(); i++){
    if(s.at(i) == 'A' && !isSetting){
      a = i;
      isSetting = true;
    }
    if(s.at(i) == 'Z'){
      z = i;
    }
  }

  cout << z - a + 1;

  return 0;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
    int n = 0, m = 0;
    cin>>n>>m;
    int *A = new int[m];
    for(int i = 0; i < m; ++i){
        cin>>A[i];
    }
    int sum = 0;
    for(int i=0;i<m;++i){
        sum+=A[i];
    }
    cout<<((n-sum) >= 0? (n-sum):-1)<<endl;

    return 0;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int n;
  cin >> n;
  int ans = 0;
  int l, r;
  REP(i,n){
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(){
    int N,*a,i,j,M=100,m=-100,sum,ans;
    scanf("%d",&N);
    a=(int*)malloc(N*sizeof(int));
    if(a==NULL){
        printf("error\n");
        return 1;
    }
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
        if(M<a[i]){
            M=a[i];
        }
        if(m>a[i]){
            m=a[i];
        }
    }
    ans=pow(M-m,2)*N;
    for(i=m;i<=M;i++){
        sum=0;
        for(j=0;j<N;j++){
            sum+=pow(a[j]-i,2);
        }
        if(ans>sum){
            ans=sum;
        }
    }
    printf("%d\n",ans);
    free(a);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
#endif

	ll n;
	cin>>n;
	n=n%1000;
	cout<<(1000-n)%1000<<endl;
	return 0;
}

Measured memory_bytes: 3644
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)*}
    };
}

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)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

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")
    };
}
const MOD: i64 = 1e9 as i64 + 7;
use std::collections::HashMap;
use std::cmp::{max,min};
fn main(){
    input!{
        s:chars,
    }
    let mut n = s.len();
    let mut dp = vec![0;13];
    dp[0] = 1;
    for i in 0..n {
        let mut next = vec![0;13];
        let c = s[i];
        for j in 0..13 {
            if c == '?' {
                for c in 0..10 {
                    let next_r = (j * 10 + c) % 13;
                    next[next_r] += dp[j];
                    next[next_r] %= MOD;
                }
            } else {
                let c = c as  usize - '0' as usize;
                let next_r = (j * 10 + c) % 13;
                next[next_r] += dp[j];
                next[next_r] %= MOD;
            }
        }
        dp = next;
    }
    println!("{}",dp[5]);
}


fn is_prime(x:i64) -> bool {
    if x == 2 {return true;}
    if x < 2 || x % 2 == 0 {return false;}
    let mut j = 3;
    while j <= (x as f64).sqrt() as i64 {
        if x % j == 0 {
            return false;
        }
        j += 2;
    }
    true
}


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

const int maxn = 55;
int n, p;
long long f[maxn][2];

int main() {
    scanf("%d %d", &n, &p), f[0][0] = 1;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x & 1) f[i][0] = f[i][1] = f[i - 1][0] + f[i - 1][1];
        else f[i][0] = f[i - 1][0] * 2, f[i][1] = f[i - 1][1] * 2;
    }
    printf("%lld\n", f[n][p]);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1500005;
int n,k,a[N];
int main() {
	read(n);read(k);
	static char S[N];scanf("%s",S+1);
	rep(i,1,n)a[i]=S[i]=='B';
	int off=1,lzy=0;
	rep(t,1,k){//[off..off+n-1]
		if(!(a[off]^lzy))a[off]^=1;
		else{
			a[off+n]=a[off];off++;lzy^=1;
		}
		if(t>n*2&&k>1e6)k-=(k-t)/2*2,k+=2;
	//	printf("%d:",t);rep(i,off,off+n-1)printf("%c",'A'+(a[i]^lzy));puts("");
	}
	rep(i,off,off+n-1)printf("%c",'A'+(a[i]^lzy));
	return 0;
}


Measured memory_bytes: 4480
n = int(input())
A = list(map(int,input().split()))

D={}
for i in range(n):
      D.update({i+1:A[i]})

D_sorted = sorted(D.items(),key=lambda x:x[1])

D2=[]
for i in range(n):
  D2.append(str(D_sorted[i][0]))


print(' '.join(D2))


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

class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int c = scanner.nextInt();
		String s = String.format("%.5f", a * b * Math.sin(Math.toRadians(c)) / 2);
		String l = String.format("%.5f", a + b + Math.sqrt(a*a + b*b - 2*a*b*Math.cos(Math.toRadians(c))));
		String h = String.format("%.5f", b * Math.sin(Math.toRadians(c)));
		
		System.out.println(s + " " + l + " " + h);
	}
}

Measured memory_bytes: 26556
n=gets.to_i
ab_count=0
b_front=0
a_tail=0
bf_at=0
n.times do|i|
	str=gets.chomp
	ab_count+=str.scan("AB").length
	if(str[str.length-1]=="A")
		if(str[0]=="B")
			bf_at+=1	
		else
			a_tail+=1
		end
	elsif(str[0]=="B")
		b_front+=1
	end
end
flag=false
if(bf_at>0 and a_tail>0)
	bf_at-=1
	a_tail-=1
	ab_count+=1
	ab_count+=bf_at
	flag=true
else
	if(bf_at>0)
		ab_count+=(bf_at-1)
		flag=true
	end
end
if(flag and b_front>0)
	ab_count+=1
	b_front-=1
end
if a_tail>b_front
	ab_count+=b_front
else
	ab_count+=a_tail
end
puts ab_count


Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const int MAX = 1100000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long FINV(int n){
    if (n < 0) return 0;
    return finv[n];
}

int main() {
    ll n, m;
    cin >> n >> m;
    COMinit();

    ll ans = 0;
    for(ll i = 0; i <= n; i++){
        ll tmp = COM(m,i) * COM(n,i) % MOD * fac[i] % MOD * (COM(m-i,n-i) * fac[n-i] % MOD) % MOD * (COM(m-i,n-i) * fac[n-i] % MOD) % MOD;
        if(i % 2 == 0){
            ans += tmp;
        }else{
            ans += MOD - tmp;
        }
        ans %= MOD;
    }

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




Measured memory_bytes: 29364
#include <iostream>
#include <algorithm>

using namespace std;

const int DIM = 2010;

int n, i, v[DIM], nr, p, u;

int main(){
    cin >> n;
    for (i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for (i = n; i > 0; --i){
        p = 1;
        u = i - 1;
        while (p < u){
            if (v[p] + v[u] > v[i]) {
                nr += u - p;
                u--;
            } else {
                p++;
            }
        }
    }
    cout << nr << "\n";
    return 0;
}

Measured memory_bytes: 256
// contest.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include "bits/stdc++.h"
//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#define YES "Yes"
#define NO "No"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define eb emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<int> VI;
typedef vector<VI> VII;
typedef pair < ut, ut > pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr, Vpr, greater<pr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 5 * 1e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 400;
const int SIZE = 1<<18;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut D,F,T,N, M, K, X, L, Y;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
LL vals[SIZE], nums[SIZE], maps[SIZE2][SIZE2], answer = zero;
////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////
//LL L;
string s;
vector<pr> outputs;

bool isable(int x) {
	return s[x - 1] == '1';
}
LL solve(){
	cin >> s;
	N = s.size();
	if (s.size() == 2) {
		outputs.eb(1, 2);
		if (s == "10") return true;
		return false;
	}
	if (!isable(1)) return false;
	if (!isable(N - 1)) return false;
	if (isable(N)) return false;
	FOR(i,1,N) {
		if (isable(i) != isable(N - i)) return false;
	}
	int last = 1;
	EFOR(i,2,N) {
		outputs.eb(last,i);
		if (isable(i-1)) {
			last = i;
		}
	}

	return true;
}
signed main() {
	if (solve()) {
		REP(i, outputs.size()) {
			cout << outputs[i].first << " " << outputs[i].second << endl;
		}
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3312
#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() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    cout << a[n-1] - a[0];
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
//#define ll __int128
//#define int ll
//#define int ll
//#define char ll
#define double ld
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<vvc> vvvc;
typedef pair<int, int> pii;
typedef pair<pii, pii> piii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define SZ(a) ((int)((a).size()))
#define triple(T) tuple<T, T, T>
#define quad(T) tuple<T, T, T, T>
#define watch(x) cerr << (#x) << " = " << (x) << endl;

#ifdef MAX_HOME
#define cerr cout
#else
#define cerr if (false) cerr
#endif

const double PI = 2 * acos(0.0);
#define rand shittttty_shit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";


template<class T0, class T1>
inline ostream &operator<<(ostream &out, pair<T0, T1> &a) {
    return out << "{" << a.first << ", " << a.second << "}";
}

template<class T0, class T1>
inline istream &operator>>(istream &in, pair<T0, T1> &a) {
    return in >> a.first >> a.second;
}

template<class T0, class T1, class T2>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
}

template<class T0, class T1, class T2, class T3>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2, T3> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " << get<3>(a) << "}";
}

template<class T>
inline ostream &operator<<(ostream &out, vector<T> &a) {
    out << "[";
    fori (i, a.size())out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
    return out;
}


void smain();


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#endif
    cout << setprecision(12) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\nTOTAL EXECUTION TIME: " << float(clock() - start) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

void smain() {

    ll a, v, b, w;
    cin >> a >> v >> b >> w;
    ll t;
    cin >> t;
    if (a == b) {
        cout << "YES";
        return;
    }
    ll d = abs(a - b);
    ll vel = v - w;

    if (d <= vel * t) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}

Measured memory_bytes: 3680
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mo = 10**9+7

def main():
	n = II()
	a = LI()
	ans=[]
	for i,x in enumerate(a,1):
		ans.append([i,x])
	ans.sort(key=lambda x: x[1])
	printH(row[0] for row in ans)

if __name__ == '__main__':
	main()

Measured memory_bytes: 27556
import math

N = int(input())

x = [0] * N
y = [0] * N

for n in range(N):
    x[n], y[n] = map(int, input().split())

dis = 0.0

for n1 in range(N-1):
    for n2 in range(n1 + 1, N):
        xd = x[n1] - x[n2]
        yd = y[n1] - y[n2]
        dis += math.sqrt(xd * xd + yd * yd)

print(dis * 2 / N)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 #define rep(i , n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  long long int N, kekkaA, kekkaB;
  kekkaA = 0;
  kekkaB = 0;
  cin >> N;
  vector<long long int> A(N + 1);
  vector<long long int> B(N);
    vector<long long int> C(N + 1);
  vector<long long int> D(N);
  rep(i , N+1)
    cin >> A[i];
  rep(i , N)
    cin >> B[i];
  C = A;
    D=B;
  rep(i , N){
    if(A[i] >= B[i])
      kekkaA += B[i];
    else{
      if(A[i] + A[i + 1] >= B[i]){
        kekkaA += B[i];
      A[i + 1] += A[i] - B[i];
      }
      else{
        kekkaA += A[i] + A[i + 1];
      A[i + 1] = 0;
      }
  }
  }
    long long int i = N;
 
  while (i >= 1) {
        if(C[i] >= D[i-1])
      kekkaB += D[i - 1];
    else{
      if(C[i] + C[i - 1] >= D[i-1]){
        kekkaB += D[i-1];
      C[i - 1] += C[i] - D[i-1];
      }
      else{
        kekkaB += C[i] + C[i - 1];
      C[i - 1] = 0;
      }
  }   
    i--;
  }
  if (kekkaA >= kekkaB)
    cout << kekkaA << endl;
  else
    cout << kekkaB << endl;
}

Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
typedef long long int ll;
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<string> s(n);
	vector<string> sorted(n);
	vector<int> p(n);
	vector<int> copy(n);
	vector<int> ans(n);
	for(int i=0; i<n; i++){
		cin >> s.at(i) >> p.at(i);
	//	sorted.at(i) = s.at(i);
		ans.at(i)=i;
		copy.at(i) = p.at(i);
	}
	//sort(sorted.begin(), sorted.end());

	int changed=1;
	while(changed==1){
		changed=0;
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				if(s.at(i)>s.at(j)){
					string tmp=s.at(i);
					s.at(i)=s.at(j);
					s.at(j)=tmp;
					int num=p.at(i);
					p.at(i) = p.at(j);
					p.at(j)=num;
					num=ans.at(i);
					ans.at(i) = ans.at(j);
					ans.at(j) = num;
					//	i--;
					changed=1;
					break;
				}else if(s.at(i)==s.at(j)){
					if(p.at(i)<p.at(j)){
						int num = p.at(i);
						p.at(i)=p.at(j);
						p.at(j)=num;
						num=ans.at(i);
						ans.at(i) = ans.at(j);
						ans.at(j) = num;
						changed=1;
						//		i--;
						break;
					}
				}
			}
		}
	}
	for(int i=0; i<n; i++){
//		cout << s.at(i) << " " <<p.at(i) << endl;
//		cout << ans.at(i) << endl;
		for(int j=0; j<n; j++){
			if(copy.at(j)==p.at(i)){
				cout << j+1 << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: u32 = read();
    let mut an: Vec<u32> = (0..n).map(|_| read()).collect();
    let mut mn = an.iter().fold(0, |acc, n| n - acc);
    print!("{}", mn);
    an.pop();
    for a in an.iter() {
        mn = 2 * a - mn;
        print!(" {}", mn)
    }
}


Measured memory_bytes: 2200
// #include {{{
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <utility>
#include <random>
#include <limits>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <cassert>
// }}}

using namespace std;

// macros {{{
template<typename T, size_t N>
constexpr size_t NELEMS(T (&)[N]) { return N; }

template<typename InputIt>
void PRINT_RANGE(InputIt first, InputIt last)
{
    for(; first != last; ++first)
        cout << *first << (first==last ? "" : " ");
    cout << "\n";
}

template<typename T>
void PRINT_MATRIX(T mat, size_t nr, size_t nc)
{
    for(size_t r = 0; r < nr; ++r) {
        for(size_t c = 0; c < nc; ++c) {
            cout << mat[r][c] << (c==nc-1 ? "" : " ");
        }
        cout << "\n";
    }
}

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
// }}}

// types {{{
using ll  = long long;
using ull = unsigned long long;
// }}}

struct Edge {
    int to;
    int cost;
    Edge(int to_arg, int cost_arg) : to(to_arg), cost(cost_arg) {}
};

constexpr int INF = numeric_limits<int>::max();

int N;
vector<Edge> G[10000];

void solve()
{
    vector<int> cost(N);
    deque<bool> done(N);

    fill(begin(cost), end(cost), INF);
    cost[0] = 0;

    for(;;) {
        int mincost = INF;
        int minv    = -1;

        REP(v, N) {
            if(done[v]) continue;
            if(cost[v] < mincost) {
                mincost = cost[v];
                minv    = v;
            }
        }

        if(minv == -1) break;

        done[minv] = true;

        for(const Edge& e : G[minv]) {
            if(done[e.to]) continue;
            int cost_new = cost[minv] + e.cost;
            if(cost_new < cost[e.to]) {
                cost[e.to] = cost_new;
            }
        }
    }

    REP(v, N) {
        cout << v << " " << cost[v] << "\n";
    }
}

int main()
{
    cin >> N;
    REP(_, N) {
        int from, k;
        cin >> from >> k;
        REP(_, k) {
            int to, cost;
            cin >> to >> cost;
            G[from].emplace_back(to, cost);
        }
    }

    solve();

    return 0;
}

Measured memory_bytes: 7876
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  int a, b;
  cin >> a >> b;
  if(a>=13) cout << b << endl;
  else if(a>=6) cout << b/2 << endl;
  else cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 3476
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

int main()
{
	int n;cin >> n;
	int res = 0;
	while(n)
	{
		int a = n % 10;
		if(a == 3)
		{
			res = 3;
			break;
		}
		else if(a == 0 || a == 1 || a == 6 || a== 8)
		{
			res = 2;
			break;
		}
		else
		{
			res = 1;
			break;
		}
	}
	if(res == 1)	cout << "hon";
	if(res == 2)	cout << "pon";
	if(res == 3)	cout << "bon";
    return 0;
}


Measured memory_bytes: 3100
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; long long k; cin >> n >> k;
  vector<pair<int, int> > ab(n); REP(i, n) cin >> ab[i].first >> ab[i].second;
  sort(ALL(ab));
  long long cnt = 0;
  REP(i, n) {
    cnt += ab[i].second;
    if (cnt >= k) {
      cout << ab[i].first << '\n';
      return 0;
    }
  }
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main ()
{
    int n,m,min,max=1-1000000000;
    cin>>n;
    cin>>m;
    min = m;
    while(--n)
    {
        cin>>m;
        if(m-min>max)
            max = m-min;
        if(m<min)
            min = m;
    }
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 3092
//
// Created by yamunaku on 2019/12/01.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CYESA cout<<"Yay!"<<endl
#define CNOA cout<<":("<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << (a==c?0:1) << endl;
    return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
l = list(int(input()) for i in range(n))

left = max(l)-1; right = sum(l)

while left+1 < right:  #最大値と合計値の間のどこかに考えるべき値が存在する
    mid = (left + right) // 2
    cnt = 1; cur = 0  #初期化
    for a in l:
        if mid < cur + a:
            cur = a
            cnt += 1
        else:
            cur += a

    if cnt <= k:
        right = mid
    else:
        left = mid

print(right)


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

#define fa(x,v) for(auto x:v)
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define spc " "
#define endl '\n'
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(s) (ll)int(s.length())
#define sz(v) (ll)int(v.size())
#define MOD 1000000007

void Fast_IO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    freopen("debug.out","w",stderr);
    #endif
} 

// Code Here

int main()
{
    // Fast_IO();
    ll a, b, c, k; cin >> a >> b >> c >> k;
    ll ans = min(a,k);
    k -= min(a,k);
    if(k > b) {
        k -= b;
        ans -= k;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3636
_N, _M, X, Y = gets.split.map(&:to_i)
xs = gets.split.map(&:to_i)
ys = gets.split.map(&:to_i)
z = xs.max + 1
z = X + 1 if z <= X
if (X < z && z <= Y) && (xs.max < z) && (z <= ys.min)
  puts 'No War'
else
  puts "War"
end

Measured memory_bytes: 1788
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define register
using namespace std;

inline int read()
{
	int X=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int MAXN=600000+10;
const int mod=924844033;
inline int qpow(int a,int b)
{
	int c=1;
	for(; b; b>>=1,a=1ll*a*a%mod) if(b&1) c=1ll*c*a%mod;
	return c;
}
int fac[MAXN],ifac[MAXN];
int cnt[MAXN],sz[MAXN];
int rev[MAXN],f[MAXN],g[MAXN];
int n;

struct edge {int v,nxt;} e[MAXN<<1];
int head[MAXN];
inline void addEdge(int u,int v)
{
	static int c=0;
	e[++c]=(edge) {v,head[u]},head[u]=c;
}


inline void init(int n)
{
	fac[0]=1;
	for(int i=1; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;
}

inline int C(int n,int m)
{return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}


inline void dfs(int u,int fa)
{
	sz[u]=1;
	for(int i=head[u]; i; i=e[i].nxt)
	{
		int v=e[i].v; if(v==fa) continue;
		dfs(v,u),sz[u]+=sz[v],++cnt[sz[v]];
	}
	++cnt[n-sz[u]];
}

inline void ntt(int *a,int n,int op)
{
	for(int i=0; i<n; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1; i<n; i<<=1)
	{
		int rot=qpow(op==1?5:554906420,(mod-1)/(i<<1));
		for(int j=0; j<n; j+=i<<1)
			for(int k=0,w=1; k<i; ++k,w=1ll*w*rot%mod)
			{
				int x=a[j+k],y=1ll*w*a[j+k+i]%mod;
				a[j+k]=(x+y)%mod,a[j+k+i]=(x-y+mod)%mod;
			}
	}
	if(op==-1)
	{
		int inv=qpow(n,mod-2);
		for(int i=0; i<n; ++i) a[i]=1ll*a[i]*inv%mod;
	}
}

int main()
{
	n=read();
	for(int i=1; i<n; ++i)
	{
		int u=read(),v=read();
		addEdge(u,v),addEdge(v,u);
	}
	dfs(1,0); init(n);
	for(int i=1; i<=n; ++i) f[i]=1ll*cnt[i]*fac[i]%mod;
	reverse(f,f+n+1);
	for(int i=0; i<=n; ++i) g[i]=ifac[i];
	int lim=1,l=0;
	for(; lim<=n<<1; lim<<=1,++l);
	for(int i=0; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	ntt(f,lim,1),ntt(g,lim,1);
	for(int i=0; i<lim; ++i) f[i]=1ll*f[i]*g[i]%mod;
	ntt(f,lim,-1);
	reverse(f,f+n+1);
	for(int i=1; i<=n; ++i)
		printf("%lld\n",(1ll*n*C(n,i)%mod
		                 -1ll*ifac[i]*f[i]%mod+mod)%mod);
	return 0;
}

Measured memory_bytes: 30136
def solve():
    answers = []
    def square(ans, rest, limit):
        if rest == 0:
            print(*ans)
        else:
            for i in range(rest, 0, -1):
                if i > limit:
                    continue
                square(ans + [i], rest - i, i)
    
    import sys
    for n in map(int, sys.stdin):
        if n == 0:
            break
        square([], n, n)

solve()


Measured memory_bytes: 6304
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
lst = [A, B, C, D, E]
roundupped = [(x + 9) // 10 * 10 for x in lst]
diff = [y - x for x, y in zip(lst, roundupped)]
last = diff.index(max(diff))
sums = 0
for i, x in enumerate(lst):
    if i == last:
        sums += x
    else:
        sums += roundupped[i]
print(sums)

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


int main(){
  int n;
  bool p[110][110];
  int l[110],m,t;

  while(cin >> n ,n){
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)p[i][j] = false;
    for(int i=1;i<=n;i++)l[i] = false;

    for(int i=1;i<=n;i++){
      cin >> m;
      for(int j=0;j<m;j++){
	cin >> t;
	p[i][t] = true;
      }
    }

    cin >> m;
    for(int i=0;i<m;i++){
      cin >> t;
      l[t] = true;
    }

    int ans = -1;
    for(int i=1;i<=n;i++){
      bool f = true;
      for(int j=1;j<=n;j++){
	if(l[j] && !p[i][j]){
	  f = false;
	  break;
	}
      }
      if(f){
	if(ans < 0)ans = i;
	else{
	  ans = -1;
	  break;
	}
      }
    }
    cout << ans << endl;
  }
}

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

typedef long long ll;

/*
const ll M = 1000000007;
vector<ll> fac(3001);
vector<ll> ifac(3001);
ll mpow(ll x, ll n){
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}
 
ll comb(ll a, ll b){
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0 || b < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}
*/


ll lcm(ll a,ll b){
 
  ll r, x, tmp;
  x = a * b;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return x/b;
}

ll gcd(ll a ,ll b){
    if(a==0){return b;}
    else if(b==0){return a;}
    else{
    ll tmp,r;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    
    r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
    }
}

bool sosu(ll p){
    bool ans = true;
    double psqrtd = pow(p, 0.5);
    ll psqrt = psqrtd;
    for(ll i = 2; i <= psqrt; i++){
        if(p%i==0)ans = false;
    }
    if(p==1)ans = false;
    return ans;
}

vector< bool > prime_table(ll n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}

int main(void){
    ll a,b;
    ll ans = 0;
    cin >> a >> b;
    ans = a - 2 * b;
    if(ans<=0)ans = 0;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/*  ex5_4
    takafumi_ueki*/
#include <stdio.h>
#include <string.h>
int main(void){
    char string[11];
    int i;
    int max = 0;
    int count = 0;
    scanf("%s",string);
    for(i=0;i<strlen(string);i++){
        if((string[i]=='A')||(string[i]=='T')||(string[i]=='G')||(string[i]=='C')){
            while((string[i]=='A')||(string[i]=='T')||(string[i]=='G')||(string[i]=='C')){
                count++;
                i++;
            }
            if(max<count){
                max = count;
            }
            //reset
            count = 0;
        }
    }
    //output the result
    printf("%d\n",max);
    return 0;
}


Measured memory_bytes: 1708
#include<stdio.h>
int main(){
	int a;
	scanf("%d",&a);
	int ret=0;
	for(int i=0;i<a;i++){
		long long b;
		scanf("%d",&b);
		b=b*2+1;
		bool ok=false;
		for(int j=1;(long long)(2*j+1)*(2*j+1)<=b;j++){
			if(b%(2*j+1)==0)ok=true;
		}
		if(!ok)ret++;
	}printf("%d\n",ret);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int H, W;
    cin >> H >> W;
    auto C = make_vec<char>(H, W);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> C[i][j];
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << C[i][j];
        }
        cout << "\n";
        for (int j = 0; j < W; j++) {
            cout << C[i][j];
        }
        cout << "\n";
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N];
#define mst(a) memset(a,0,sizeof a)
int main(){
	ll k,n;
	while(~scanf("%lld%lld",&k,&n)){
		ll mx=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
				scanf("%lld",&a[i]);
				int f=0;
					ll ans=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
		{
			 if(i==1) ans=min(ans,min(k-(a[2]-a[1]),a[n]-a[1])); 
			 else if(i==n) ans=min(ans,min(k-(a[n]-a[n-1]),a[n]-a[1]));
			 else  ans=min(ans,k-max(a[i]-a[i-1],a[i+1]-a[i]));
		}
		cout<<ans<<endl;
	} 
	return 0;
} 

Measured memory_bytes: 1792
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** (N - 1)):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N - 1):
        if height - A[i + 1] < 0:
            cnt += 1
            height = A[i + 1]
        elif (b >> i) & 1:
            cnt += 1
            cost += height - A[i + 1] + 1
            height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main() {
	int n,k;
	cin>>n>>k;
	if((n-k)%(k-1)==0){
		cout<<1+(n-k)/(k-1)<<endl;
	}
	else{
		cout<<2+(n-k)/(k-1)<<endl;
	}
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    
    
    n, q = map(int, input().split())
    u = UnionFind(n)

    ans_list = []
    for _ in range(q):
        com, x, y = map(int, input().split())

        if com == 1:
            ans = u.same_check(x, y)
            ans_list.append(ans)
        else:
            u.union(x, y)

    for num in ans_list:
        print(int(num))




Measured memory_bytes: 7192
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;

using ll = long long;
using Bint = mp::cpp_int;
ll mod = 1000000007;

int main() {
    // input
    ll n;
    cin >> n;
    ll a[2][n];
    rep(i, n) { cin >> a[0][i]; }
    rep(i, n) { cin >> a[1][i]; }

    ll sum[2][n];
    sum[0][0] = a[0][0];
    sum[1][n - 1] = a[1][n - 1];

    repd(i, 1, n) { sum[0][i] = sum[0][i - 1] + a[0][i]; }
    repd(i, 1, n) {
        ll index = n - i - 1;
        sum[1][index] = sum[1][index + 1] + a[1][index];
    }

    ll ans[n];
    rep(i, n) { ans[i] = sum[0][i] + sum[1][i]; }

    ll ans_max = 0;
    rep(i, n) { ans_max = max(ans_max, ans[i]); }

    cout << ans_max << endl;

    // calculate
    return 0;
}



Measured memory_bytes: 256
/**
 *
 * @author Daipayan Mukherjee
 * @Jadavpur University,Information Technology
 *
 */
import java.io.*;
import java.util.*;

public class Main {
    public static long MOD = 1000000007;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        int n = Integer.parseInt(st[0]);
        int k = Integer.parseInt(st[1]);
        String[] s = br.readLine().split(" ");
        int[] cap = new int[n];
        for(int i=0;i<n;i++){
            cap[i] = Integer.parseInt(s[i]);
        }
        long[][] dp = new long[n][k+1];
        
        long last = 0;
        for(int i=0;i<=k;i++){
            long consumed =  k-i;
            if(consumed<=cap[0])
                dp[0][i] = (last+1)%MOD;
            else
                dp[0][i] = last;
            
            last = dp[0][i];
        }
   
        for(int i=1;i<n;i++){
            for (int j = 0; j <=k; j++) {
                long low = j>0?dp[i-1][j-1]:0;
                long high = dp[i-1][Math.min(k,j+cap[i])];
                dp[i][j] = ((j>0?dp[i][j-1]:0) + (high-low+MOD)%MOD)%MOD;
                
            }
        }
        System.out.println(dp[n-1][0]);
    }
}


Measured memory_bytes: 124756
#include <bits/stdc++.h>
const int N=1e3+5,M=2e5+5;
using namespace std;
struct Edge{
	int u,v;
}e[M];
bool g1[N][N],g2[N][N],used[N];
int n,m,Mark[N];
bool flag;
vector<int>to[N];
void DFS(int p,int s){
	g1[s][p]=used[p]=1;
	register int i;
	for(i=0;i!=to[p].size();++i)
		if(!used[to[p][i]]) DFS(to[p][i],s);
}
void _DFS(int p,int col,int s){
	//cout<<p<<
	if(flag) g2[s][p]=Mark[p]!=col;
	else Mark[p]=col;
	register int i;used[p]=1;
	for(i=0;i!=to[p].size();++i)
		if(!used[to[p][i]]) _DFS(to[p][i],col,s);
}
int main(){
	
	register int i,j,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		to[x].push_back(y);
		e[i]=(Edge){x,y};
	}
	for(i=1;i<=n;++i) DFS(i,i),memset(used,0,sizeof used);
	for(i=1;i<=n;++i){
		for(j=0;j<=n;++j) Mark[j]=0;
		for(j=1;j<=n;++j) used[j]=0;used[i]=1;flag=0; 
		for(j=0;j!=to[i].size()  ;++j) if(!used[to[i][j]]) _DFS(to[i][j],j,i);
		for(j=1;j<=n;++j) used[j]=0;used[i]=1;flag=1;
		for(j=to[i].size()-1;j>=0;--j) if(!used[to[i][j]]) _DFS(to[i][j],j,i);
	}
	for(i=1;i<=m;++i)
		puts((g1[e[i].v][e[i].u]^g2[e[i].u][e[i].v])?"diff":"same");
	return 0;
}

Measured memory_bytes: 6272