akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)n;i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1e9*2; const long long INFLL=1e18*2;
template<class T> ostream& operator << (ostream &os, const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is, vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.second >> p.first; return is; }
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;}
//------------------------------------------------------------------------------

struct union_find {
    vector<int> data;
    union_find(int size) : data(size, -1) { }
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(x != y) {
            if(data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
signed main() {
    int N,K,L;
    cin>>N>>K>>L;
    union_find a(N),b(N);
    REP(i,K) {
        int p,q;
        cin>>p>>q;
        p--,q--;
        a.unite(p,q);
    }
    REP(i,L) {
        int p,q;
        cin>>p>>q;
        p--,q--;
        b.unite(p,q);
    }
    vi ar(N),br(N);
    REP(i,N) ar[i]=a.root(i), br[i]=b.root(i);
    map<pii,int> m;
    REP(i,N) {
        if(m.find({ar[i],br[i]})==end(m)) m[{ar[i],br[i]}]=1;
        else m[{ar[i],br[i]}]++;
    }

    vi ans(N);
    REP(i,N) {
        ans[i]=m[{a.root(i),b.root(i)}];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 19584
from heapq import heappush, heappop


n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
heap = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
        heappush(heap, x)
    elif working:
        while not heap[0] in working:
            heappop(heap)
        dist[x] = heap[0]

for d in dist:
    print(d)

Measured memory_bytes: 196080
#!/usr/bin/env python3
import sys


def solve(N: int, L: int):
    sum = 0
    minAbs = 10**16
    minVal = 10**16
    for i in range(N):
        c = L + i
        sum += c
        if abs(c) < minAbs:
            minAbs = abs(c)
            minVal = c
    print(sum - minVal)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    solve(N, L)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int bingo[] = new int[9];
        for(int i = 0; i < 9; i++){
        	bingo[i] = sc.nextInt();
        }
    	int n = sc.nextInt();
        int num[] = new int[n];
        for(int i = 0; i < n; i++){
        	num[i] = sc.nextInt();
            for(int j = 0; j < 9; j++){
            	if(bingo[j] == num[i]){
                	bingo[j] = 101;
                }
            }
        }
        String ans = "No";
        //横一列bingo
        if((bingo[0] == bingo[1] && bingo[0] == bingo[2]) || (bingo[3] == bingo[4] && bingo[3] == bingo[5]) ||
          (bingo[6] == bingo[7] && bingo[6] == bingo[8])){
        	ans = "Yes";
        //縦一列bingo  
        }else if((bingo[0] == bingo[3] && bingo[0] == bingo[6]) || (bingo[1] == bingo[4] && bingo[1] == bingo[7]) ||
          (bingo[2] == bingo[5] && bingo[2] == bingo[8])){
        	ans = "Yes";
        //斜め一列bingo
        }else if((bingo[0] == bingo[4] && bingo[0] == bingo[8]) || (bingo[2] == bingo[4] && bingo[2] == bingo[6])){
        	ans = "Yes";
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35644
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=2000+100;
int par[maxn],rankl[maxn];

void init(int n){
    for(int i=0;i<=n;i++){
        par[i]=i;
        rankl[i]=0;
    }
}

int findl(int x){
    if(x==par[x])
        return x;
    else{
        return par[x]=findl(par[x]);
    }
}

void unite(int x,int y){
    x=findl(x);
    y=findl(y);
    if(x==y)  return;
    if(rankl[x]<rankl[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rankl[x]==rankl[y])  rankl[x]++;
    }
}

bool same(int x,int y){
    return findl(x)==findl(y);
}
bitset<maxn*maxn>num;
int n,a[maxn];
int main()
{
	scanf("%d",&n);
	int sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	sum=(sum+1)/2;
	num[0]=1;
	for(int i=1;i<=n;i++){
		num=num|(num<<a[i]);
	}
	for(int i=sum;i<=sum*2;i++){
		if(num[i]==1){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 2432
n = int(input())
a_s = [int(input()) for _ in range(n)]
button = 1
count = 0
for _ in range(len(a_s)):
    button = a_s[button-1]
    count += 1
    if button == 2:
        print(count)
        break
if count == len(a_s):
    print(-1)

Measured memory_bytes: 7084
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a;
    while(cin>>a)
    {
        int digit=a%10;
        if(digit==2 || digit==4 || digit==5 || digit==7 || digit==9)
        {
            cout<<"hon"<<endl;
        }
        else if(digit==0 || digit==1 || digit==6 || digit==8)
        {
            cout<<"pon"<<endl;
        }
        else
        {
            cout<<"bon"<<endl;
        }
    }
}

Measured memory_bytes: 3580
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::HashMap;
#[allow(unused_imports)]
use std::collections::VecDeque;
#[allow(unused_imports)]
use std::usize;

#[allow(unused_macros)]
macro_rules! read_cols {
    ($($t:ty),+) => {{
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();

        let mut it = line.trim()
            .split_whitespace();

        ($(
            it.next().unwrap().parse::<$t>().ok().unwrap()
        ),+)
    }}
}

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

#[allow(dead_code)]
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn execute(red: &Vec<(usize, usize)>, blue: &Vec<(usize, usize)>, used_blue: &mut Vec<bool>) -> usize {
    let mut ans = 0;
    for r in red {
        let mut candidate = blue.iter()
            .map(|&p| p)
            .enumerate()
            .skip_while(|&(_, (x, _))| x < r.0)
            .filter(|&(i, _)| !used_blue[i])
            .filter(|&(_, (_, y))| y > r.1)
            .min_by(|&(_, (_, y1)), &(_, (_, y2))| y1.cmp(&y2));
        match candidate {
            Some((i, _)) => {
                used_blue[i] = true;
                ans += 1;
            }
            None => {}
        }
    }

    ans
}

fn main() {
    let n = read::<usize>();
    let mut red = Vec::new();
    for _ in 0..n {
        let (a, b) = read_cols!(usize, usize);
        red.push((a, b));
    }
    let mut blue = Vec::new();
    for _ in 0..n {
        let (a, b) = read_cols!(usize, usize);
        blue.push((a, b));
    }

    // 右から左
    red.sort_by(|&(x1, _), &(x2, _)| x2.cmp(&x1));
    // 左から右
    blue.sort_by(|&(x1, _), &(x2, _)| x1.cmp(&x2));

    let mut used_blue = Vec::new();
    used_blue.resize(n, false);

    println!("{}", execute(&red, &blue, &mut used_blue));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin>>n;
  int b[n-1];
  for(int i=0;i<n-1;++i){
    cin>>b[i];
  }
  int ans=b[0]+b[n-2];
  for(int i=0;i<n-2;++i){
    ans+=min(b[i],b[i+1]);
  }
  cout<<ans<<endl;
  return 0;
}

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

int rev(int n){
  int r=0;
  while(n>0){
    r=r*10+n%10;
    n/=10;
  }
  return r;
}

int main() {
  int A, B, blw, abv,len;
  cin >> A >> B;
  blw=A/100;
  abv=B/100;
  len = abv-blw+1;
  if(A%1000>rev(blw))len--;
  if(B%1000<rev(abv))len--;
  cout <<len<<endl;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int H,W;
    Scd2(H,W);

    vector<vi> a(H,vi(W));
    vector<vi> b(H,vi(W));
    vector<vi> c(H,vi(W));
    Rep(i,H){
        Rep(j,W){
            Scd(a[i][j]);
        }
    }
    Rep(i,H){
        Rep(j,W){
            Scd(b[i][j]);
            c[i][j] = abs(a[i][j]-b[i][j]);
        }
    }

    static int dp[81][81][30000] = {};
    int offset = (W+H)*80+2;
    dp[0][0][offset+c[0][0]] = 1;
    dp[0][0][offset-c[0][0]] = 1;

    Rep(di,W+H)Rep(wi,W){
        int hi = di-wi;
        if( hi>=H ) continue;
        if( hi<0 ) break;
        Rep(ai,((W+H)*160+10)){
            // dp[hi][wi][ai];
            if( dp[hi][wi][ai] == 0 ) continue;
            if( hi != H-1 ) {
                dp[hi+1][wi][ai+c[hi+1][wi]] = 1;
                dp[hi+1][wi][ai-c[hi+1][wi]] = 1;
            }
            if( wi != W-1 ) {
                dp[hi][wi+1][ai+c[hi][wi+1]] = 1;
                dp[hi][wi+1][ai-c[hi][wi+1]] = 1;
            }
        }
    }

    int ans = INF;

    for( int ai = 0; ai < 30000; ai++ )
        if( dp[H-1][W-1][ai] ) ans = min(ans,abs(offset-ai));

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

    return 0;
}



Measured memory_bytes: 758272
<?php
fscanf(STDIN, "%d%d", $n, $k);
$aArray = array_map("intval", explode(" ", trim(fgets(STDIN))));

$gcd = gcdAll($aArray);

echo (($k-$aArray[0])%$gcd == 0) && $k <= max($aArray)? "POSSIBLE" : "IMPOSSIBLE";

//配列の最大公約数
function gcdAll($array){
    $gcd = $array[0];
    for($i = 1; $i < count($array); $i++){
        $gcd = gcd($gcd, $array[$i]);
    }
    return $gcd;
}

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

Measured memory_bytes: 16884
#include<iostream>
#include<string>
#include<algorithm>

int main(){
  long a,b,c,d;
  
  std::cin >> a >> b >> c >> d;
  
  auto productMax = std::max({ 
  	a * c,
  	a * d,
  	b * c,
  	b * d
  });
  
  std::cout << productMax;
}


Measured memory_bytes: 3220
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define fi first 
#define se second

#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VD vector<double>
#define VVD vector<vector<double>>
#define VVVD vector<vector<vector<double>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VVVL vector<vector<vector<ll>>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VVVB vector<vector<vector<bool>>>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVVS vector<vector<vector<string>>>

#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define VPII vector<pair<int,int>>
#define VVPII vector<vector<pair<int,int>>>
#define VVVPII vector<vector<vector<pair<int,int>>>>
#define VPLL vector<pair<ll,ll>>
#define VVPLL vector<vector<pair<ll,ll>>>
#define VVVPLL vector<vector<vector<pair<ll,ll>>>>

const ll MOD = (ll)998244353;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;


void YN(bool flag) {
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Yn(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void yn(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

const int MAX = 10000;

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;
}

int main() {
	int K, N; cin >> K >> N;
	COMinit();

	VL pow2(2000 + 1, 1);
	FOR(i, 1, 2001) (pow2[i] = 2 * pow2[i - 1]) %= MOD;

	if (K == 1) {
		cout << 0 << endl;
		return 0;
	}
	
	for (ll i = 2; i <= 2 * K; ++i) {
		ll cnt = i / 2 - ((i <= K + 1) ? 0 : i - (K + 1));
		ll sum = 0;
		if (i & 1) {
			for (int j = 0; j <= cnt; ++j) {
				(sum += ((COM(cnt, j) * pow2[j]) %MOD) * COM(N - j + K - 2 * cnt + j - 1, N - j)) %= MOD;
			}
		}
		else {
			cnt--;
			for (int j = 0; j <= cnt; ++j) {
				(sum += ((COM(cnt, j) * pow2[j]) %MOD) * COM(N - j + K - 2 * cnt - 1 + j - 1, N - j))%=MOD;
				(sum += ((COM(cnt, j) * pow2[j])%MOD) * COM(N - j - 1 + K - 2 * cnt - 1 + j - 1, N - j - 1))%=MOD;
			}
		}
		cout << sum << endl;
	}
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
int n, k, x, res;
int main(void){
    // Your code here!
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> x;
        res += min(abs(x - k), x);
    }
    cout << res * 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e5+10;
char ar[maxn];
char br[maxn];
int main(void)
{
    int N,M;
    cin>>N>>M;
    cin>>(ar+1);
    cin>>(br+1);
    int d = gcd(N,M);
    int n = N/d,m = M/d;
    LL i = 1,j = 1;
    LL L = 1ll*n*m*d;
    
    
    while(i <= N&& j <= M){
        if(ar[i] != br[j]) return 0*puts("-1");
        i += n;

        j += m;
    }
    printf("%lld\n",L);

   return 0;
}

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

long long gcd(long long a, long long b){ return b ? gcd(b,a%b) : a; }
long long lcm(long long a, long long b){ return a/gcd(a,b)*b; }

void solve(long long A, long long B){
    cout << lcm(A, B) << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 3748
// WA

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

int dp[100001];
vector<int> ar(100);

// ll solve(ll index, ll x) {
//     // cout << "0\n";
//     if(dp[index][x] != -1)
//         return dp[index][x];
//     ll ansl = 0;
//     // cout << "1\n";
//     if(x == 0)
//         return dp[index][x] = 1;
//     // cout << "2\n";
//     if(index == 0) {
//         if(ar[0] >= x)
//             return dp[index][x] = 1;
//         else return dp[index][x] = 0;
//     }
//     // cout << "3\n";
//     for(int i = 0; i <= min(ar[index], x); i++) {
//         ansl = (ansl + solve(index-1, x-i)) % 1000000007;
//     }
//     // cout << "ansl = " << "\n";
//     return dp[index][x] = ansl;
// }

void sub(int &a, int b) {
    a -= b;
    if(a < 0)
        a += 1000000007;
}

void add(int &a, int b) {
    a += b;
    if(a >= 1000000007)
        a -= 1000000007;
}

ll solve_bottom_up(int n, int k) {
    dp[0] = 1;
    for(int child = 0; child < n; child++) {
        vector<int> pf(k+1, 0);
        for(int used = k; used >= 0; used--) {
            int l = used+1;
            int r = used + min(ar[child], k-used);
            if(l <= r) {
                add(pf[l], dp[used]);
                if(r+1 <= k)
                    sub(pf[r+1], dp[used]);
            }
        }
        int prf_sum = 0;
        for(int i = 0; i <= k; i++) {
            add(prf_sum, pf[i]);
            add(dp[i], prf_sum);
        }
    }
    return dp[k];
}

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> ar[i];
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j <= k; j++)
    //         dp[i][j] = -1;
    // }
    cout << solve_bottom_up(n, k) << "\n";
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j <= k; j++)
    //         cout << dp[i][j] << " ";
    //     cout << "\n";
    // }
}

Measured memory_bytes: 1024
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

const int N = 1e5 + 5;
long long inv[N], fact[N], ifact[N];
void pre()
{
	inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
	for (int i = 2; i < N; i++)
	{
		inv[i] = mul(MOD - MOD / i, inv[MOD % i], MOD);
		fact[i] = mul(i * 1ll, fact[i - 1], MOD);
		ifact[i] = mul(inv[i], ifact[i - 1], MOD);
	}
	return;
}

long long nCr(long long n, long long r)
{
	if (n >= 0 && r >= 0 && n >= r)
		return mul(fact[n], mul(ifact[r], ifact[n - r], MOD), MOD);
	return 0;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	ll ans = 0;
	v64 arr(n + 1, 0);
	for (int i = 1; i < n + 1; i++)
		cin >> arr[i];
	sort(arr.begin() + 1, arr.end());
	pre();
	for (int i = 1; i < n + 1; i++)
	{
		ll temp = mul(arr[i], nCr(i - 1, k - 1), MOD);
		temp = add(temp, MOD - mul(arr[i], nCr(n - i, k - 1), MOD), MOD);
		ans = add(ans, temp, MOD);
	}
	cout << ans << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t start, stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for (int tc = 1; tc < t + 1; tc++)
		solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


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

char g[101][101];
int w,h,n;
int x,y,a;

int main() {

    cin >> w >> h >> n;

    for(int i=0; i<w; i++){
        for(int j=0; j<h; j++){
            g[i][j] = 'W';
        }
    }

    for(int i=0; i<n; i++){
        cin >> x >> y >> a;
        if(a == 1){
            for(int i=0; i<x; i++){
                for(int j = 0; j<h; j++){
                    g[i][j] = 'B';
                }
            }
        }
        else if(a == 2){
            for(int i=x; i<w; i++){
                for(int j = 0; j<h; j++){
                    g[i][j] = 'B';
                }
            }
        }
        else if(a == 3){
            for(int i=0; i<w; i++){
                for(int j = 0; j<y; j++){
                    g[i][j] = 'B';
                }
            }
        }
        else if(a == 4){
            for(int i=0; i<w; i++){
                for(int j = y; j<h; j++){
                    g[i][j] = 'B';
                }
            }
        }
    }

    int count = 0;

    for(int i=0; i<w; i++){
        for(int j=0; j<h; j++){
            if(g[i][j] == 'W'){
                count++;
            }
        }
    }

    cout << count << endl;


    return 0;
}

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

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    int N;
    cin >> N;
    set<string> st;
    while (N--) {
        string S;
        cin >> S;
        st.insert(S);
    }
    cout << (int)st.size() << endl;
    return 0;
}

Measured memory_bytes: 19128
/**
 *      ABC 48 C
 *      author  : kyomukyomupurin
 *      created : 2018-10-01 16:44:57
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, x; cin >> N >> x;
    int a[N] = {};
    for (auto i = 0; i < N; ++i) {
        cin >> a[i];
    }
    int64_t count = 0;

    for (auto i = 0; i < N - 1; ++i) {
        if (a[i] + a[i + 1] > x){
            int temp = a[i + 1];
            int64_t diff = a[i] + a[i + 1] - x;
            if (diff <= a[i + 1]){
                a[i + 1] -= (a[i] + temp - x);
                count += diff;
            }
            else {
                a[i + 1] = 0;
                count += diff;
            }
        }
    }
    cout << count << '\n';
    
    return 0;
}

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

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		int[] H = new int[N];
		for (int i = 0; i < N; i++) {
			H[i] = sc.nextInt();
		}
		int[] dp = new int[N];
		Arrays.fill(dp, (int)2e9);
		dp[0] = 0;
		for (int i = 0; i < N; i++) {
			if (i + 1 < N && dp[i] + Math.abs(H[i] - H[i + 1]) < dp[i + 1]) {
				dp[i + 1] = dp[i] + Math.abs(H[i] - H[i + 1]);
			}
			if (i + 2 < N && dp[i] + Math.abs(H[i] - H[i + 2]) < dp[i + 2]) {
				dp[i + 2] = dp[i] + Math.abs(H[i] - H[i + 2]);
			}
		}
		System.out.println(dp[N - 1]);
	}

}


Measured memory_bytes: 50100
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))

a = max(A)
b = None
used = False
for i in A:
    if i == a and not used:
        used = True
    elif not b or abs(a // 2 - b) > abs(a // 2 - i):
        b = i

print(a, b)

Measured memory_bytes: 14692
import java.util.Scanner;

public class Main {
     public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int x = sc.nextInt();
	    int y = sc.nextInt();
	    int z = sc.nextInt();
	    int t = 0;
	    for (int i = x; i <= y; i++) {
	    	if (z % i == 0)
	    		t++;
	    } System.out.println(t);
     }
}



Measured memory_bytes: 26388
map{*I=-$_;<>=~$",vec($I,$`-1,8)=$'+49for 1..<>;$Z.='{0,2}'}1..<>;
printf sort{$b-$a}map{
	map{$i=0;$t=$_;$i--,/2/&&($t|=$$i)for/./g;$_=$t}($_)x5;
	!/3/*y/2//
}glob$Z

Measured memory_bytes: 6832
import java.io.*;
import java.util.*;

class Main {
  static final Scanner in = new Scanner(System.in);
  static int N, K;

  static int[] a,b,c;
  // static int dp[][];
  static int dp[][];
  static final int MOD = 1000000007;
  static int[] pre;
  static char[][] t;
  static char[] s;
  static Set<Character> set;

  public static void main(String[] args) throws Exception {
    N = in.nextInt();
    a = new int[N];
    b = new int[N];
    c = new int[N];
    dp = new int[N][3];
    for(int i = 0;i < N;i++){
      a[i] = in.nextInt();
      b[i] = in.nextInt();
      c[i] = in.nextInt();
      Arrays.fill(dp[i],-1);
    }

    int ans = Math.max(F(N-1,0),F(N-1,1));
    ans = Math.max(ans,F(N-1,2));

    System.out.println(ans);
    
  }

  static int F(int i,int jobType){
    
    if(i < 0)
      return 0;

      if(dp[i][jobType] != -1)
        return dp[i][jobType];

    int bugs = 0;
    int swim = 0;
    int homework = 0;

    if(jobType == 0){
      bugs = F(i-1,1) + a[i];
      homework = F(i-1,2) + a[i];
    }

    if(jobType == 1){
      homework = F(i-1,2) + b[i];
      swim = F(i-1,0) + b[i];
    }

    if(jobType == 2){
      swim = F(i-1,0) + c[i];
      bugs = F(i-1,1) + c[i];
    }

    int max = Math.max(swim,bugs);
    max = Math.max(max,homework);

    dp[i][jobType] = max;
    return dp[i][jobType];
  
  }

  static int finalise(int k,boolean flag,int count){
    if(flag){
      return 1 + (s.length - count);
    }
    return 1 + s.length + count;
  }

  static void print() {
    System.out.println("t--> ");
    for (int i = 0; i < t.length; i++) {
      for (int j = 0; j < t[i].length; j++) {
        System.out.print(t[i][j]);
      }
      System.out.print(" ");
    }
    System.out.println();
    System.out.println("s--> ");
    for (int i = 0; i < s.length; i++) System.out.print(s[i]);
    System.out.println();

    System.out.println("set --> " + set);
  }
}

/**
 experience was ultimate
ew
 */

 /**
  supreme court is the highest judicial court
  su
  */


Measured memory_bytes: 68500
package main

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

func main() {
	sc := NewScanner()

	k := sc.ReadInt()

	a := sc.ReadInt()
	b := sc.ReadInt()

	if b-b%k >= a {
		fmt.Println("OK")
	} else {
		fmt.Println("NG")
	}
}

// util
// *   math/simple

func Abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

func Min(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	min := values[0]
	for _, v := range values {
		if v < min {
			min = v
		}
	}
	return min
}

func Max(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	max := values[0]
	for _, v := range values {
		if v > max {
			max = v
		}
	}
	return max
}

func Pow(base int, exponent uint) int {
	answer := 1
	for i := uint(0); i < exponent; i++ {
		answer *= base
	}
	return answer
}

// *   io

type Scanner struct {
	bufScanner *bufio.Scanner
}

func NewScanner() *Scanner {
	bufSc := bufio.NewScanner(os.Stdin)
	bufSc.Split(bufio.ScanWords)
	bufSc.Buffer(nil, 100000000)
	return &Scanner{bufSc}
}

func (sc *Scanner) ReadString() string {
	bufSc := sc.bufScanner
	bufSc.Scan()
	return bufSc.Text()
}

func (sc *Scanner) ReadInt() int {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}


Measured memory_bytes: 1756
h,w,n=map(int,input().split())
dic={}
INF=10**10
for i in range(n):
  y,x=map(int,input().split())
  for j in range(max(2,x-1),min(w-1,x+1)+1):
    for k in range(max(2,y-1),min(h-1,y+1)+1):
      if j*INF+k in dic:
        dic[j*INF+k]+=1
      else:
        dic[j*INF+k]=1
ans=[0]*10
ans[0]=(h-2)*(w-2)
for i in dic:
  ans[0]-=1
  ans[dic[i]]+=1
for i in ans:
  print(i)


Measured memory_bytes: 238704
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
using lint=long long;
using lubl=long double;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n;std::cin>>n;
    lint m=1'000'000'000;
    lint q=n/m,r=n%m;
    lint x=q+1,y=m-r;
    if(n==m*m){
        x=m,y=0;
    }
    std::cout<<0<<' '<<0<<' '<<x<<' '<<y<<' '<<1<<' '<<m<<'\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	double x[101],y[101];
	double p1,p2,p3,p4;
	int i;
	cin>>n;
	for(i=0;i<n;i++)	cin>>x[i];
	for(i=0;i<n;i++)	cin>>y[i];
	
	p1=0;
	for(i=0;i<n;i++)	p1+=abs(x[i]-y[i]);
	
	p2=0;
	for(i=0;i<n;i++)	p2+=pow(abs(x[i]-y[i]),2);
	p2=sqrt(p2);
	
	p3=0;
	for(i=0;i<n;i++)	p3+=pow(abs(x[i]-y[i]),3);
	p3=cbrt(p3);
	p4=0;
	for(i=0;i<n;i++)	p4=max(abs(x[i]-y[i]),p4);
	pow(p4,n);
	printf("%.10f\n",p1);
	printf("%.10f\n",p2);
	printf("%.10f\n",p3);
	printf("%.10f\n",p4);
	return 0;
}


Measured memory_bytes: 3468
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double N;
int K;

double function(int n);

int main(void){
  int i;
  double ans;
  char str[100],*p;
  
  fgets(str,sizeof(str),stdin);
  p=strtok(str," \n");
  N=atof(p);
  p=strtok(NULL," \n");
  K=atoi(p);
  
  for(i=1,ans=0;i<=N;i++){
    ans+=(1/N)*function(i);
  }
  
  printf("%13.12lf\n",ans);
  
  
  return 0;
}

double function(int n){
  double f=1.0;
  
  while(n<K){
    n*=2;
    f/=2.0;
  }
  
  return f;
}  

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N, M; cin >> N >> M;
    int A[N]; rep(i, N) cin >> A[i];
    // Mが偶数の時,mod MがM/2なら,好きに組ませていい mod Mが0の時も同様(Mは奇数でもいい) cnt[M]/2 + cnt[0]/2
    // それ以外はmod Kとmod M-Kの個数を考える 同じ数字はなるべく残すようにするのが最適
    sort(A, A+N);
    int mod_cnt[M] = {};
    int same_card[M] = {};

    rep(i, N){
        if(i == N-1) mod_cnt[A[i] % M]++;
        else if(A[i] == A[i+1]){
            mod_cnt[A[i] % M] += 2;
            same_card[A[i] % M]++;
            i++;
        }
        else{
            mod_cnt[A[i] % M]++;
        }
    }
    int ans = 0;
    if(M % 2 == 0) ans += mod_cnt[M/2]/2;
    ans += mod_cnt[0]/2;
    int loop = M/2;

    //cout << "before loop: " << ans << endl;

    for(int i = 1; i <= loop; i++){
        int a = i, b = M-i;
        if(a == b) break;
        //cout << i << ": " << mod_cnt[a] << ", " << mod_cnt[b] << endl;

        int add = min(mod_cnt[a], mod_cnt[b]);
        ans += add;

        int is_larger;
        if(add == mod_cnt[a]) is_larger = b;
        else is_larger = a;
        int rem = mod_cnt[is_larger] - add;
        ans += min(rem/2, same_card[is_larger]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1408
N,K=map(int,input().split())
ans=0
a=[]
number=0

def maxcount(n,k):
    if n>=K:
        return k
    else:
        k+=1
        return maxcount(2*n,k)
    
for i in range(1,N+1):
    if i<K:
        ans+=(1/N)*((1/2)**maxcount(i,0))
    else:
        ans+=1/N
print('{:.12f}'.format(ans))

Measured memory_bytes: 46064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        try(Scanner scn = new Scanner(System.in)) {
            int sum = 0;
            for(int i = 0; i < 5; i++) {
                int scr = scn.nextInt();
                sum += scr > 40 ? scr : 40;
            }
            System.out.println(sum / 5);
        }
    }
}

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

const int MAX = 1e5 + 10;;

typedef long long ll;

int main()
{
	int n; cin>>n;
	int c[MAX]={0};
	int ones=0,twos=0;
	for(int i=0;i<n;i++) {int x; cin>>x; c[x]++;}

	for(int i=1;i<MAX;i++) {
		if(c[i]>=3){
			int t = (c[i]-3)/2;
			c[i] -= t*2;

			while(c[i]>=3) c[i] -= 2;
		}
		if(c[i]==1) ones++;
		if(c[i]==2) twos++;
	}	

	//for(int i=1;i<12;i++) cout<<c[i]<<" "; cout<<endl;

	int ans=ones+twos;

	if(twos%2 == 1) ans--;

	cout<<ans;

}

Measured memory_bytes: 640
#include <cstdio>

int main() {
  long N, h = 0, n = 0, w = 0;
  scanf("%ld", &N);
  for (h = 1; h <= 3500; h++) {
    for (n = 1; n <= 3500; n++) {
      if ((4 * h * n - N * n - N * h) > 0 && (N * h * n) % (4 * h * n - N * n - N * h) == 0) {
        w = (N * h * n) / (4 * h * n - N * n - N * h);
        printf("%ld %ld %ld\n", h, n, w);
        return 0;
      }
    }
  }
}


Measured memory_bytes: 128
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static List<Long> getStrings(Scanner sc, int num) {
		List<Long> stringList = new ArrayList<>();
		while(num>0) {
			long nextInt = sc.nextLong();
			stringList.add(nextInt);
			num--;
		}
		return stringList;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Long> array = getStrings(sc, n);
		BigInteger result = BigInteger.ONE;
		BigInteger max = BigInteger.valueOf(1000000000000000000L);
		for(int i = 0;i<n;i++) {
			if (array.get(i) == 0L) {
				System.out.println(0);
				return;
			}
		}
		for(int i = 0;i<n;i++) {
			result = result.multiply(BigInteger.valueOf(array.get(i)));
			if (result.compareTo(max) > 0) {
				System.out.println(-1);
				return;
			}
		}
		System.out.println(result);
	}

}


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

         
                    
using namespace std;
                     
#define rep(i,a,b); for(long long int i=a;i<b;i++)
#define mk make_pair        
#define LIMIT 100007
#define MOD 1000000007
#define ll long long int
#define endl '\n'
#define min3(a,b,c) ((a>b)?((b>c?c:b):(a>c?c:a)))
#define max3(a,b,c) ((a<b)?((b<c?c:b):(a<c?c:a)))
#define min(a,b) (a>b?b:a)
// #define x.first x.f
// #define x.second x.s
#define max(a,b) (a<b?b:a)
#define pb push_back
#define FAST std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

vector<ll> v;

void SieveOfEratosthenes(int n) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          v.pb(p); 
} 

ll smallestDivisor(ll n) 
{ 
    // if divisible by 2 
    if (n % 2 == 0) 
        return 2; 
  
    // iterate from 3 to sqrt(n) 
    for (ll i = 3; i * i <= n; i += 2) { 
        if (n % i == 0) 
            return i; 
    } 
  
    return n; 
}

int main() 
{ 
    FAST
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int x,y;
    cin>>x>>y;
    int a=(y-2*x)/2;
    int b=(4*x-y)/2;

    if(a>=0 && b>=0 && a+b==x) cout<<"Yes";
    else cout<<"No";

    return 0; 
}  


Measured memory_bytes: 3644
import java.util.*;

public class Main{
  static int[] ans;
  static Map<Integer, Integer> map;
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.nextLine());
    int ans = 0;
    int now = 0;
    for(int i = 0; i < N; i++){
      int n = Integer.parseInt(sc.next());
      if(i == 0){
        now = n;
        ans++;
      }else{
        if(n >= now){
          now = n;
          ans++;
        }
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
const ll MOD=1000000007;
const ll INF=1000000000;

int main(){
    int N;
    cin >> N;
    vector<int> b(N+1);
    b[0]=0;
    rep (i,N){
        cin >> b[i+1];
    }
    vector<int> ans(N);
    int c=0;
    bool can=true;
    while (c<N){
        int j=0;
        for (int i=1;i<=N-c;i++){
            if (b[i]==i){
                j=i;
            }
        }
        if (j==0){
            can=false;
            break;
        }
        ans[N-1-c]=j;
        c++;
        for (int i=j;i<=N-c;i++){
            b[i]=b[i+1];
        }
    }
    if (can){
        rep (i,N){
            cout << ans[i] << endl;
        }
    }
    else {
        cout << -1 << endl;
    }
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v,ind_num):
	if v == bef_v :
		seen[v] = 0;
	else :
		#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
		if G[bef_v][1][ind_num] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for i in range(len(G[v][0])) :
		next_v = G[v][0][i];
		if seen[next_v]==-1 :
			dfs(G,next_v,v,i);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0,0);

for i in range(n):
	print(seen[i]);
	


Measured memory_bytes: 86260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const ll INF = 1e14;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;

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

int main() {
    ll N,M;
    cin >> N >> M;
    vector<ll> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    ll cnt = vec.at(0) / 2;
    for(int i = 1;i < N;i++) {
        ll cnt2 = gcd(cnt,vec.at(i) / 2);
        cnt2 = cnt * (vec.at(i) / 2) / cnt2;
        ll A = cnt2 / cnt;
        ll B = cnt2 / (vec.at(i) / 2);
        if(A % 2 == 0 || B % 2 == 0) {
            cout << 0 << endl;
            return 0;
        }
        else {
            cnt = cnt2;
        }
    }
    ll G = 1;
    for(int i = 0;i < N;i++) {
        ll count = gcd(G,vec.at(i));
        G = G * vec.at(i) / count;
    }
    if(M == cnt) {
        cout << 1 << endl;
    }
    else if(M < cnt) {
        cout << 0 << endl;
    }
    else {
        cout << (M - cnt) / G + 1 << endl;
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  
  ll sum = 0;
  
  rep(i, N) {
    cin >> A.at(i);
  }
  
  for ( int i = 1; i < N; i++ ) {
    if( A.at(i-1) > A.at(i) ) {
      ll dif = A.at(i-1) - A.at(i);
      sum += dif;
      A.at(i) += dif;
    }
  }
  
  cout << sum << endl;
      
}

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

using namespace std;

typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)


signed main(){

	int n, q;
	set<int> ss;
	int ans = 0;

	cin >> n;
	for (int i = 0; i < n; i++){
		int s;
		cin >> s;
		ss.insert(s);
	}
	cin >> q;
	for (int i = 0; i < q; i++){
		int t;
		cin >> t;
		if (ss.find(t) != ss.end())
			ans++;
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3112
n = int(input())
a, b = [[int(el) for el in input().split(' ')] for _ in range(2)]
print(sum(abs(a[i] - b[i]) for i in range(n)))
print(sum((a[i] - b[i]) ** 2 for i in range(n)) ** 0.5)
print(sum(abs(a[i] - b[i]) ** 3 for i in range(n)) ** (1/3))
print(max(abs(a[i] - b[i]) for i in range(n)))

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

int main()
{
  vector<int> PQR(3);
  for (int i = 0; i < 3; i++)
  {
    cin >> PQR.at(i);
  }

  sort(PQR.begin(), PQR.end());
  cout << PQR.at(0) + PQR.at(1) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int N,L;

  scanf("%d %d",&N,&L);

  if(L>0)
    printf("%d\n",(N-1)*(N+2*L)/2);
  else if(L+N-1<0)
    printf("%d\n",(N-1)*(N-2+2*L)/2);
  else
    printf("%d\n",N*(N-1+2*L)/2);
    
  
  return 0;

}


Measured memory_bytes: 128
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { //Partition babyyyyyyyyy
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int N = I.nextInt();
		int[] cnts = new int[N+1];
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int x = I.nextInt();
			if (x>N) ans++; //Can't have more occurrences than length of whole array...
			else cnts[x]++;
		} 
		for (int i = 1; i <= N; i++) {
			if (cnts[i]<i) ans+=cnts[i]; //Just set occurrences of i to 0 if so
			else if (cnts[i]>i) ans+=cnts[i]-i; //Otherwise truncate to exactly i occurrences
		}
		O.pln(ans);
	}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
	}
}


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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

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

    int cnt = 0;
    int m = 0;
    for (char c : s) {
        if (c == 'I') cnt++;
        if (c == 'D') cnt--;
        m = max(m, cnt);
    }

    cout << m << endl;

    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = [LIST() for _ in range(N)]
zw = [[x+y, x-y] for x, y in xy]
z, w = zip(*zw)
print(max(max(z)-min(z), max(w)-min(w)))


Measured memory_bytes: 92188
#include <bits/stdc++.h>
using namespace std;
int main() {
    // your code goes here
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    long long ans=a*c;
    ans=max(ans,b*c);
    ans=max(ans,a*d);
    ans=max(ans,b*d);
    cout<<ans;
    return 0;
}

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

int main() {
  int n, m;
  cin >> n;
  vector<long int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  cin >> m;
  vector<long int> b(m);
  for(int i = 0; i < m; i++){
    cin >> b.at(i);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  int i = 0;
  int j = 0;
  int count = 0;
  while(i < n & j < m){
    if(i == n - 1){
      if(a.at(i) == b.at(j)){
        count++;
        break;
      }else{
        j++;
        continue;
      }
    }
    if(j == m - 1){
      if(a.at(i) == b.at(j)){
        count++;
        break;
      }else{
        i++;
        continue;
      }
    }
    if(a.at(i) == b.at(j)){
      count++;
      i++;
      j++;
    }else if(a.at(i) < b.at(j)){
      i++;
    }else{
      j++;
    }
  }
  if(n == 1 & m == 1){
    if(a.at(0) == b.at(0)){
      count++;
    }
  }
  if(count == m){
    cout << "YES";
  }else{
    cout << "NO";
  }
}

Measured memory_bytes: 3328
def d_transit_tree_path(N, E, Q, K, V):
    # 頂点数、辺とそのコスト、クエリの数、経由する頂点、出発/到達頂点

    # 隣接リストの作成
    edge = [[] for _ in range(N)]
    for a, b, c in E:
        edge[a - 1].append([b - 1, c])
        edge[b - 1].append([a - 1, c])

    # Kから各節点への距離を求める
    dist = [0 for i in range(N)]  # 頂点Kからの距離
    is_visit = [False for i in range(N)]  # ある頂点が探索済か
    is_visit[K - 1] = True  # 頂点Kは探索済とする
    queue = [K - 1]  # 幅探索用キュー

    while queue:
        u = queue.pop()
        for v, c in edge[u]:
            if not is_visit[v]:
                is_visit[v] = True
                dist[v] = dist[u] + c
                queue.append(v)

    ans = ''
    for q1, q2 in V:
        ans += '{}\n'.format(dist[q1 - 1] + dist[q2 - 1])
    ans = ans[:-1]
    return ans

N = int(input())
E = [[int(i) for i in input().split()] for j in range(N-1)]
Q,K = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(Q)]
print(d_transit_tree_path(N, E, Q, K, V))

Measured memory_bytes: 88688