akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int par[100010];
int s[100010];       // 同じ集合に属する頂点数

void init(int num);
int find(int num);
void unite(int a, int b);
bool same(int a, int b);

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for(int i = 0; i < M; ++i){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    
    init(N);
    
    vector<ll> ans(M);
    ans[M - 1] = (ll)N * (N - 1) / 2;
    for(int i = M - 1; i > 0; --i){
        if(same(A[i], B[i]))      ans[i - 1] = ans[i];
        else{
            ans[i - 1] = ans[i] - (ll)s[find(A[i])] * s[find(B[i])];
            unite(A[i], B[i]);
        }
    }
    
    for(int i = 0; i < M; ++i){
        cout << ans[i] << endl;
    }
}

void init(int num){
    for(int i = 0; i < num; ++i){
        par[i] = i;
        s[i] = 1;
    }
}


int find(int num){
    if(par[num] == num){
        return num;
    }
    else{
        return par[num] = find(par[num]);
    }
}

void unite(int a, int b){
    a = find(a);
    b = find(b);
    
    if(a == b){     // 元から連結
        return;
    }
    else{           // 非連結の場合
        if(s[a] < s[b]){
            swap(a, b);
        }
        par[b] = a;
        s[a] += s[b];
    }
}

bool same(int a, int b){
    return find(a) == find(b);
}

Measured memory_bytes: 3712
from collections import defaultdict, deque


def main():
    N, Q = map(int, input().split())

    tree = defaultdict(list)
    counter = defaultdict(int)
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p, x = map(int, input().split())
        counter[p] += x

    # bfs
    q = deque([1])
    visited = {1}

    while q:
        i = q.popleft()

        for j in tree[i]:
            if j not in visited:
                q.append(j)
                counter[j] += counter[i]
                visited.add(j)

    counts = [counter[i] for i in range(1, N+1)]
    ans = " ".join(map(str, counts))
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 103788
//#pragma GCC optimize ('O3')
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 1e5 + 5;
const int M = 5e5 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

int n,x,t;

void init() {}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> x >> t;

    cout << int(ceil(1.0*n/x)) * t << '\n';

    return 0;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    // sum[l,r] (r - l + 1)
    int64_t ans = n * (n * n + 3 * n + 2) / 6;

    for (auto _ : irange(0L, n - 1)) {
        int64_t u, v;
        cin >> u >> v;

        if (u > v) {
            swap(u, v);
        }

        ans -= u * (n - v + 1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3628
#[allow(unused_imports)]
use std::collections::HashSet;

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

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

//use lazy_static::lazy_static;

//lazy_static! {
//    static ref MOD :usize = 10usize.pow(9) + 7;
//}

use std::collections::HashMap;

static MOD: usize = 1000_000_007;

fn main() {
    let l: Vec<char> = read::<String>().chars().collect::<Vec<char>>();
    let n = l.len();

    let mut pow3 : Vec<usize> = vec![0; n];
    prepare(n, &l, &mut pow3);
    let answer = solve(n, &l, &pow3);
    println!("{}", answer);
}


fn prepare(n: usize, l: &[char], m3: &mut[usize]) {
    let mut x3 = 1;
    for i in 0..n { 
        m3[i] = x3;
        x3 = x3 * 3 % MOD;
    }
}


fn solve(n: usize, l: &[char], m3: &[usize]) -> usize {
    let mut count = 0;
    let mut c1 = 0;
    for i in 0..n {
        if l[i] == '0' {
            continue;
        }
        let remaining = n - i - 1;
        if c1 == 0 {
            c1 = 1;
        } else {
            c1 = c1 * 2 % MOD;
        }
        
        let c2 = m3[remaining];
        let c3 = c1 * c2 % MOD;

        count = (count + c3) % MOD;
    }
    c1 = c1 * 2 % MOD;
    count = (count + c1) % MOD;
    return count;
}


Measured memory_bytes: 4352
#include <bits/stdtr1c++.h>

using namespace std;

int main(){
    int n,j,k,l;
    cin >> n;
    vector <int> v;

    for(int i = 0; i < n; i++){
        cin >> j;
            if(j==0){
                cin >> k;
                v.push_back(k);
            }
            else if(j==2){
                v.pop_back();
            }
            else{
                cin >> l;
                cout << v[l] << "\n";
            }
    }



    return 0;
}


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

int main(){
	int n,x;
  	cin >> n >> x;
  	int k=x;
  	int a[n];
  	for (int i=0; i<n ;i++){
    	cin >> a[i];
      	k-=a[i];
    }
  	sort(a,a+n);
    cout << n+k/a[0] <<endl;
}

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

int main()
{
	int N;
	cin >> N;
	int ans = 1;
	int minus = 1;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		ans *= 3;
		if (A % 2 == 0) minus *= 2;
	}
	cout << ans - minus << endl;
}


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

typedef pair<long long, long long> pairll;

const int MOD = 1000000007;
vector<long long> Power2;

void initPower2(int expmax){
    long long power2buf = 1;
    for(int i=0; i<expmax; i++){
        Power2.push_back(power2buf);
        power2buf *= 2;
        power2buf %= MOD;
    }
}

long long GCD(long long former, long long latter){
    if(former%latter == 0)return latter;
    if(latter%former == 0)return former;
    return GCD(latter, former%latter);
}

pairll WhoItHates(pairll anchovy){
    if(anchovy.second > 0)return pairll(anchovy.second, -anchovy.first);
    if(anchovy.second < 0)return pairll(-anchovy.second, anchovy.first);
    return pairll(0, 1);
}

int main(void){

    int N;
    long long Abuf, Bbuf;
    vector<pairll>Sociability;
    vector<int> Hatred;
    vector<int> Friendship;
    int Gloomy = 0;
    initPower2(200001);

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> Abuf >> Bbuf;
        if((Abuf != 0LL)||(Bbuf != 0LL)){
            if(Abuf < 0){
                Abuf = -Abuf;
                Bbuf = -Bbuf;
                
            }
            if(Abuf == 0LL){
                Sociability.push_back(pairll(0LL, 1LL));
            }else if(Bbuf == 0LL){
                Sociability.push_back(pairll(1LL, 0LL));
            }else{
                long long gcdAB = GCD(abs(Abuf), abs(Bbuf));
                Sociability.push_back(pairll(Abuf/gcdAB, Bbuf/gcdAB));
            }
        }else{
            Gloomy++;
        }
    }

    sort(Sociability.begin(), Sociability.end());
    set<pairll> setSociability;

    for(size_t i=0; i<Sociability.size(); i++){
        pairll Hated = WhoItHates(Sociability[i]);
        if(setSociability.find(Sociability[i])!=setSociability.end())continue;
        setSociability.insert(Sociability[i]);
        setSociability.insert(Hated);
        int Hbuf = upper_bound(Sociability.begin(), Sociability.end(), Hated)
                 - lower_bound(Sociability.begin(), Sociability.end(), Hated);
        Hatred.push_back(Hbuf);
        int Fbuf = upper_bound(Sociability.begin(), Sociability.end(), Sociability[i])
                 - lower_bound(Sociability.begin(), Sociability.end(), Sociability[i]);
        Friendship.push_back(Fbuf);
    }
    long long res = 1;
    for(size_t i=0; i<Friendship.size(); i++){
        long long casebuf = Power2[Hatred[i]]+Power2[Friendship[i]]-1;
        casebuf %= MOD;
        res *= casebuf;
        res %= MOD;
    }

    cout << ((res + Gloomy)%MOD + MOD - 1)%MOD << endl;

    return 0;
}

Measured memory_bytes: 34408
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int main(){
    char s[100010];
    int n,ll,rr,ans=0;
    //vector<char> l(100000),r(100000);
    scanf("%s",s);
    n=strlen(s);
    ll=0;
    rr=n-1;
    while(ll<rr){
        if(s[ll]==s[rr]){
            ll++;
            rr--;
        }
        else if(s[ll]=='x'){
            ll++;
            ans++;
        }
        else if(s[rr]=='x'){
            rr--;
            ans++;
        }
        else{
            printf("-1\n");
            return 0;
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 256
# 二分探索
from bisect import bisect_left

N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

t = [[] for _ in range(N)]
for P, Y in PY:
    t[P - 1].append(Y)

for i in range(N):
    t[i].sort()

for P, Y in PY:
    print("%06d%06d" % (P, bisect_left(t[P - 1], Y) + 1))


Measured memory_bytes: 36748
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main()
{
	long long int n, k, a[200020], i, j = 0, star, b[200020] = { 0 }, h=0, c = 0;
	scanf("%lld%lld", &n, &k);
	for (i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
	star = 1;
	while (1)
	{
		b[star]++;
		if (b[star] == 3)
		{
			break;
		}
		star = a[star];
	}
	for (i = 0; i <= n; i++)
	{
		if (b[i] == 1)
		{
			h++;
		}
		if (b[i] == 2 || b[i] == 3)
		{
			c++;
		}
	}
	if (k > h)
	{
		k = (k - h) % c;
	}
	else
	{
		star = 1;
	}
	for (i = 0; i < k; i++)
	{
		star = a[star];
	}
	printf("%lld", star);
	return 0;
}

Measured memory_bytes: 4860
function main(input){
  input = input.trim();
  var list1 = input.split("\n")[0].split(" ");
  var list = input.split("\n")[1].split(" ");
  for(var i=0; i<list.length; i++){
    list[i] = parseInt(list[i]);
  }
  var nissuu = parseInt(list1[0]);
  var sKei = 0;
  
  for(var i=0; i<list.length; i++){
    sKei += list[i];
  }
  var answer = nissuu - sKei;
  if(answer < 0){answer = -1;}
  console.log(answer);
  
}
main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 30620
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}

#[allow(unused_macros)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn a() {
    let (a, b) = read!(i32, i32);
    println!("{}", max(0, a - 2 * b));
}

fn b() {
    let n = read!(usize);
    let d: Vec<usize> = read![[usize]];

    let mut ans = 0;
    for i in 0..(n - 1) {
        for j in (i + 1)..n {
            ans += d[i] * d[j];
        }
    }
    println!("{}", ans);
}

fn c() {
    let n = read!(usize);
    let s: String = read!(String);

    let c: Vec<char> = s.chars().collect();

    let mut prev = c[0];
    let mut ans = 0;
    for i in 0..n {
        if prev == c[i] {
            continue;
        } else {
            ans += 1;
            prev = c[i];
        }
    }
    println!("{}", ans + 1);
}

fn d() {
    let n = read!(usize);
    let mut l: Vec<usize> = read![[usize]];
    l.sort();
    l.reverse();

    let mut dp = vec![0; 3000]; // lから2つ選んで和がxになるような組合せの数

    for i in 0..(n - 1) {
        for j in (i + 1)..n {
            let s = l[i] + l[j];
            dp[s] += 1;
        }
    }

    let mut under = vec![0; 3000];
    under[0] = 0;
    under[1] = 0;
    for i in 2..dp.len() {
        let t = under[i - 1];
        under[i] = t + dp[i];
    }

    let mut ans = n * (n - 1) * (n - 2) / 6;
    for i in 0..n {
        let max_v = l[i];
        ans -= under[max_v];
    }
    println!("{}", ans);
}

fn e() {
    unimplemented!();
}

fn f() {
    unimplemented!();
}

fn main() {
    d();
}


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

using namespace std;

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

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MAX=100005;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

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

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    Vec w(n);
    Vec b(n);
    ll ans=INF;

    rep(i,n){
        if(i>0){
            if(s[i]==*"."){
                b[i]=b[i-1];
                w[i]=w[i-1]+1;
            }else{
                b[i]=b[i-1]+1;
                w[i]=w[i-1];
            }
        }else {
            if(s[i]==*"."){
                w[i]=1;
            }else{
                b[i]=1;
            }
        }
    }

    REP(i,-1,n+1){
        if(i==-1) {
            ans = min(ans,b[n-1]);
        }else if(i==n){
            ans = min(ans,w[n-1]);
        }else {
            ans = min(ans,b[i] + w[n-1] - w[i]);
        }
    }

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


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

int main(){
    int a,b,k;  cin>>a>>b>>k;

    for(int i=a;i<=min(b,a+k-1); i++)cout<<i<<endl;

    for(int i=max(b-k+1,a+k); i<=b; i++)cout<<i<<endl;


    return 0;
}


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

int fun(vector<long long int> X, int N){
    
    int size = X.size();
    int min = 0;
    int max = size - 1;
    int mid;
    
    if (X[min] > N) return 0;
    if (X[max] <= N) return (max + 1);
    
    while(max - min > 1){
        mid = (max + min) / 2;
        
        if (X[mid] > N){
            max = mid;
        } else {
            min = mid;
        }
    }
    
    if (X[max] > N){
        return (min + 1);
    } else {
        return (max + 1);
    }
    
    return 0;
}

int main(){
    
    int i, j, N, M, K, x, ans;
    cin >> N >> M >> K;
    
    vector< long long int > A(N, 0);
    vector< long long int > B(M, 0);
    vector< long long int > A_sum(N, 0);
    vector< long long int > B_sum(M, 0);
    
    for (i = 0; i < N; i++){
        cin >> A[i];
        if (i == 0){
            A_sum[i] = A[i];
        } else {
            A_sum[i] = A_sum[i - 1] + A[i];
        }
    }
    
    for (i = 0; i < M; i++){
        cin >> B[i];
        if (i == 0){
            B_sum[i] = B[i];
        } else {
            B_sum[i] = B_sum[i - 1] + B[i];
        }
    }
    
    x = fun(B_sum, K);
    
    if (x == 0){
        ans = fun(A_sum, K);
        cout << ans << "\n";
        return 0;
    }
    
    ans = x;
    
    for (i = 0; i < N; i++){
        
        int t = K - A_sum[i];
        if (t < 0) break;
        
        while(B_sum[x - 1] > t && x > 0) x--;
        
        if (i + 1 + x > ans) ans = i + 1 + x;
    }
    
    cout << ans << "\n";
    
    return 0;
}



Measured memory_bytes: 10736
def shuffle(arr, p, c):
    p -= 1
    cut = arr[p: p + c]
    top = arr[:p]
    bot = arr[p + c:]
    return cut + top + bot

if __name__ == '__main__':
    while True:
        N, R = list(map(int, input().split()))
        if N == 0 and R == 0:
            break

        arr = [ N - x for x in range(N) ]

        for _ in range(R):
            p, c = list(map(int, input().split()))
            arr = shuffle(arr, p, c)
        
        print(arr[0])


Measured memory_bytes: 5616
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int n,A[N],in[N];
vector <LL> e[N],v[N];
LL solve(int x,int pre){
	vector <LL> &a=v[x];
	for (auto y : e[x])
		if (y!=pre)
			a.push_back(solve(y,x));
	if (a.empty())
		return A[x];
	sort(a.begin(),a.end());
	if (!~a[0])
		return -1;
	reverse(a.begin(),a.end());
	LL tot=0;
	for (auto y : a)
		tot+=y;
	LL mx=min((LL)A[x],min(tot/2,tot-a[0])),Need=tot-A[x];
	return Need>mx||Need<0?-1:(A[x]-Need);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&A[i]);
	for (int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
		in[a]++,in[b]++;
	}
	if (n==2)
		return puts(A[1]==A[2]?"YES":"NO"),0;
	for (int i=1;i<=n;i++)
		if (in[i]>1)
			return puts(solve(i,0)==0?"YES":"NO"),0;
}

Measured memory_bytes: 19968
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

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

int main(){
    int n;
    cin >> n;
    int l[n];
    int mx = 0;
    int sm = 0;
    rep(i, n) {
        cin >> l[i];
        sm += l[i];
        mx = max(l[i], mx);
    }
    
    if (sm - mx > mx){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, c) for(int i = 0; i < (int)c; i++)
const int inf = 1000000000; // 10^9

int main(){
    int l;
    cin >> l;

    cout << setprecision(15) << (double)l*l*l/27 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define ENDL '\n'
#define FOR(i, n) for (int i = 0; i < n; i++)
#define FOR_EACH(i, v) for (auto&& i : v)

string S;
string T;

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

	cin >> S;
	cin >> T;

	int ans = -1;
	for (int i = S.length() - T.length(); i >= 0; i--) {
		FOR(j, T.length()) {
			if (S[i + j] != '?' && S[i + j] != T[j]) {
				break;
			}
			if (j == T.length() - 1) {
				ans = i;
				goto find;
			}
		}
	}
find:;

	if (ans == -1) {
		cout << "UNRESTORABLE" << ENDL;
	}
	else {
		string originalS = "";
		FOR(i, S.length()) {
			if (i == ans) {
				originalS += T;
				i += T.length() - 1;
			}
			else {
				originalS += S[i] == '?' ? 'a' : S[i];
			}
		}
		cout << originalS << ENDL;
	}

	return 0;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a,b,c,d,cmp[10],cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
      cin>>cmp[0]>>cmp[1]>>cmp[2];
      sort(cmp,cmp+3);
      Cout(cmp[2]-cmp[0]);
    
       
return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC044_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var t = scan;
            long N = t[0]; long A = t[1];
            var x = scan;
            var y = new long[N];
            for (long i = 0; i < N; i++)
            {
                y[i] = x[i] - A;
            }
            var X = x.Max();
            var NX = N * X;
            var dp = new long[N + 1, 2 * NX + 1];
            
            dp[0, NX] = 1;

            for (long i = 1; i <= N ; i++)
            {
                for (long  j = 2 * NX; j >= 0; j--)
                {
                    //Console.WriteLine(i+" "+j);
                    dp[i, j] = dp[i - 1, j];
                    if (j - y[i - 1] < 0 || j - y[i - 1] > 2 * NX) continue;
                    dp[i, j] += dp [i - 1, j - y[i - 1]];
                    //Console.WriteLine(dp[i, j]);
                }
            }
            Console.WriteLine(dp[N, NX] - 1);
        }

        static long[] scan { get { return Array.ConvertAll(Console.ReadLine().Split(), long.Parse); } }
    }
}


Measured memory_bytes: 4696
N, Q = map(int, input().split())
union = [x for x in range(N)]
answer_list = []

def fetch_root(idx) :
    if idx == union[idx] :
        return idx
    else :
        union[idx] = fetch_root(union[union[idx]])
        return union[idx]

for i in range(Q) :
    q, a, b = map(int, input().split())
    
    # uinon
    if q == 0 :
        min_root_idx = max(fetch_root(a), fetch_root(b))
        union[min_root_idx] = min(fetch_root(a), fetch_root(b))
        
    # evaluate
    else :
        if fetch_root(union[a]) == fetch_root(union[b]) :
            answer_list.append(1)
        else :
            answer_list.append(0)
            
for i in answer_list :
    print(i)


Measured memory_bytes: 6984
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC086A
{
    class Program
    {
        static void Main(string[] args)
        {
            var X = int.Parse(Console.ReadLine());
            if (X >= 30)
                System.Console.WriteLine("Yes");
            else
                System.Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 27544
class PriorityQueue
  def initialize(&comp)
    @heap = []
    @node_num = 0
    if block_given?
      @comp = comp
    else
      @comp = Proc.new { |x, y| x <= y }
    end
  end
  attr_reader :heap
 
  def push(x)
    i = @node_num # self node number
    @node_num += 1
    while i > 0
      par = (i - 1) / 2 # parent's node number
      break if @comp.call(@heap[par], x) # 逆転してないなら抜ける
      # 親ノードを下ろして自分を上に
      @heap[i] = @heap[par]
      i = par
    end
    @heap[i] = x
  end
 
  alias_method(:<<, :push)
 
  def pop
    # 最(小|大)値
    ret = @heap[0]
    # 根にもってくる値
    @node_num -= 1
    x = @heap[@node_num]
    # 根から下ろしていく
    i = 0
    while i * 2 + 1 < @node_num
      # 子どうしを比較
      a, b = i * 2 + 1, i * 2 + 2
      a = b if b < @node_num && @comp.call(@heap[b], @heap[a])
      break unless @comp.call(@heap[a], x)
      @heap[i] = @heap[a]
      i = a
    end
    @heap[i] = x
    ret
  end
 
  def get
    @node_num == 0 ? nil : @heap[0]
  end
 
  def empty?
    get.nil?
  end
end



#
# dijkstra
#   O(|E|log|V|)
#   隣接表現グラフgraph, 始点start, inf
#
def dijkstra(graph, start, inf = Float::INFINITY)
  vertex_num = graph.size
  que = PriorityQueue.new { |x, y| x[0] <= y[0] }
  dist = Array.new(vertex_num, inf)
  dist[start] = 0
  que.push([0, start])
  while !que.empty?
    d, v = que.pop
    next if dist[v] < d
    graph[v].size.times do |i|
      # e is an instance of Edge
      #   Edge = Struct.new(:to, :cost)
      e = graph[v][i]
      if dist[e.to] > dist[v] + e.cost
        dist[e.to] = dist[v] + e.cost
        que.push([dist[e.to], e.to])
      end
    end
  end
  return dist
end



Edge = Struct.new(:to, :cost)
v, e, r = gets.split.map(&:to_i)
g = Array.new(v) { [] }
e.times do |i|
  s, t, d = gets.split.map(&:to_i)
  g[s] << Edge.new(t, d)
end
puts dijkstra(g, r).map { |x| x == Float::INFINITY ? "INF" : x }


Measured memory_bytes: 56192
n,l = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
for i in range(n-1):
  if a[i]+a[i+1] >= l:
    print('Possible')
    for j in range(n,i+2,-1):
      print(j-1)
    for k in range(1,i+2):
      print(k)
    exit()
print('Impossible')

Measured memory_bytes: 14052
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

struct point
{
    int x;
    int y;
    int id;
};

int val = 0;
int e() {return -1;}
int op(int a, int b) {return max(a,b); }
bool f(int x) {return x < val;}


int main()
{
    int n;
    cin >> n;
    vector<point> a(n);
    rep(i,n)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        a[i] = point{x, y, i};
    }
    sort(a.begin(), a.end(), [](point lh, point rh) {return lh.x < rh.x; });
    segtree<int, op, e> seg(n);
    rep(i,n)
    {
        seg.set(i,a[i].y);
    }
    dsu d(n);
    vector<int> memo(n, 0);
    rep(i,n-1)
    {
        if(memo[i]) continue;
        val = a[i].y;
        int p = seg.max_right<f>(i+1);
        while(p != n)
        {
            d.merge(i, p);
            memo[p] = 1;
            p = seg.max_right<f>(p+1);
        }
    }
    vector<int> ans(n);
    rep(i,n) ans[a[i].id] = d.size(i);
    rep(i,n) cout << ans[i] << "\n";

    return 0;
}


Measured memory_bytes: 9904
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;

int main(){
  
  int n; cin>>n;
  vector<int> a(n);
  int sum{};
  for(auto &i:a) {
    cin>>i;
    sum ^= i;
  }
  for(int i=0; i<n; i++){
    cout << (sum^a.at(i)) << endl;
  }
  
  
}

Measured memory_bytes: 4048
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        m: usize,
        am: [usize; m]
    }
    let match_nums = [6,2,5,5,4,5,6,3,7,6];
    let mut dp: Vec<Answer> = vec![None; n + 1];
    dp[0] = Some(String::from(""));
    for i in 0..n {
        if dp[i] == None {
            continue;
        }
        for &a in &am {
            let num = match_nums[a];
            if i + num <= n {
                let dpi = dp[i].clone();
                let dpinum = dp[i+num].clone();
                let a = a.to_string();
                let right = if let Some(r) = dpi {
                    format!("{}{}", r, a)
                } else {
                    a
                };
                dp[i + num] = Some(max_answer(dpinum, Some(right)));
            }
        }
    }
    println!("{}", dp[n].clone().unwrap());
}

type Answer = Option<String>;

fn max_answer(left: Answer, right: Answer) -> String {
    match (left, right) {
        (None, None) => unimplemented!(),
        (None, Some(r)) => r,
        (Some(l), None) => l,
        (Some(ref l), Some(ref r)) if l.len() < r.len() => r.to_string(),
        (Some(ref l), Some(ref r)) if l.len() > r.len() => l.to_string(),
        (Some(ref l), Some(ref r)) if l < r => r.to_string(),
        (Some(ref l), Some(_)) => l.to_string(),
    }
}


Measured memory_bytes: 30972
#include<stdio.h>
#define N 3
void ascendingSort(int,int[]);
void printArray(int,int[]);
int main(void)
{
  int i;
  int arr[N];
  for(i=0;i<N;i++) scanf("%d",&arr[i]);
  ascendingSort(N,arr);
  printArray(N,arr);
  return 0;
}
void ascendingSort(int n,int arr[])
{
  int i,j;
  int key;
  for(i=1;i<n;i++)
    {
      key=arr[i];
      for(j=i-1;j>=0;j--)
        {
          if(key<arr[j]) arr[j+1]=arr[j];
          else break;
        }
      arr[j+1]=key;
    }
}
void printArray(int n,int arr[])
{
  int i;
  for(i=0;i<n;i++)
    {
      if(i>0) printf(" ");
      printf("%d",arr[i]);
    }
  printf("\n");
}



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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

vector<ll> calc_divisor(ll n) {
    vector<ll> res;

    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            ll j = n / i;
            if (j != i) res.push_back(j);
        }
    }

    sort(res.begin(), res.end());
    return res;
}

int main() {

    ll n; cin >> n;

    ll ans = 0;

    for (ll x : calc_divisor(n)) {
        if (x == 1) continue; //問題の制約で1は除外

        ll tmp = n;
        while (tmp % x == 0) tmp /= x;

        tmp %= x;
        if (tmp == 1) ++ans;
    }

    ans += calc_divisor(n - 1).size() - 1; //1は除外

    cout << ans << endl;
}

Measured memory_bytes: 384
#include <stdio.h>

int main()
{
	int N, ans, a=0, b=0, as=0, bs=0, i, j, k=0;
	int x[100];

	scanf("%d", &N);

	for(i=0; i<N; i++){
		scanf("%d", &x[i]);
	}
	for(i=0; i<=N/2; i++){
		for(j=0; j<N; j++){
			if(a<x[j]){
				a=x[j];
				k=j;
			}
		}
		as=as+a;
		x[k]=0;
		a=0;
		for(j=0; j<N; j++){
			if(b<x[j]){
				b=x[j];
				k=j;
			}
		}
		bs=bs+b;
		x[k]=0;
		b=0;
	}
	ans=as-bs;
	printf("%d\n", ans);

	
	return 0;
}

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

int solve() {
    int N, M;
    bool flag = false;
    vector<string> ids;
    cin >> N;
    for(int i=0; i<N; i++) {
        string s;
        cin>>s;
        ids.push_back(s);
    }

    cin >> M;
    for(int i=0; i<M; i++) {
        string s;
        cin >> s;
        auto result = find(ids.begin(), ids.end(), s);
        if(result == ids.end()) {
            cout << "Unknown " << s << endl;
        } else {
            flag = !flag;
            if(flag) cout << "Opened by " << *result << endl;
            else cout << "Closed by " << *result << endl;
        }
    }
    return 0;
}

int main() {
    return solve();
}



Measured memory_bytes: 3228
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////




int main() {

	char b;
	cin >> b;

	if (b == 'A') { cout << 'T'; }
	if (b == 'T') { cout << 'A'; }
	if (b == 'C') { cout << 'G'; }
	if (b == 'G') { cout << 'C'; }


	system("PAUSE");
}

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

int main(int argc, const char * argv[]) {
    vector<vector<int>> c(3, vector<int>(3));
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            int inp; cin >> inp;
            c[i][j] = inp;
        }
    }
    
    vector<int> x(3), y(3);
    x[0] = 0;
    for(int i = 0; i < 3; i++) y[i] = c[0][i] - x[0];
    for(int i = 0; i < 3; i++) x[i] = c[i][0] - y[0];
    
    bool good = true;
    for(int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if(x[i] + y[j] != c[i][j]) {
                good = false;
            }
        }
    }
    
    if(good) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fill(name, val) memset(name, val, sizeof(name));
#define get(a, n)    for(ll it = 0; it < n; it++)    cin>>a[it];

/*	Author: 🆉🅴🅽🅾🅻🆄🆂	*/

ll n, a[401];
ll dp[401][401];
ll calc(ll l, ll r){
	if(l >= r)	return 0;
	if(dp[l][r] != -1)	return dp[l][r];
	ll ans = 1000000000000000000, sum = a[r]; 
	for(ll i = l ; i < r; i++)
		ans = min(ans, calc(l, i) + calc(i+1, r)), sum += a[i];
	return dp[l][r] = ans + sum;
}
int main(){
	fill(dp, -1);
	cin>>n;	get(a, n);
	cout<<calc(0, n-1);
}

// Time: O(N*N*N)
// Space: O(N*N)

Measured memory_bytes: 4900
#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, m; cin >> n >> m;
  vector<vector<int> > a(n);
  REP(i, n) {
    int k; cin >> k;
    REP(j, k) {
      int aa; cin >> aa;
      a[i].emplace_back(aa);
    }
  }
  int ans = 0;
  FOR(i, 1, m+1) {
    bool ok = true;
    REP(j, n) if (find(ALL(a[j]), i) == a[j].end()) ok = false;
    if (ok) ++ans;
  }
  cout << ans << '\n';
  return 0;
}


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



void solve(){
    int n,k,q;
    cin >> n >> k >> q;
    int a[q+5];
    int ans[n+10];
    int x[n+10];
    rep(i,n){
      ans[i] = 0;
    }
    rep(i,q){
      cin >> a[i];
      ans[a[i]-1]++;
    }
    //それぞれの参加者が正解した回数をベクトルで保持

    rep(i,n){
      x[i] = k - q + ans[i];
    }
    rep(i,n){
      if(x[i]>0) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
}

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

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<utility>
using namespace std;
int main() {
	int x, y;
	cin >> x >> y;
	cout << (x - 1)*(y - 1) << endl;
	
    
}

Measured memory_bytes: 256
n= int(input())
t,a = map(int, input().split())
h=[int(i) for i in input().split()]
mini=[1,abs(t-(h[0]*0.006)-a)]
for i in range(n):
    dh=abs(t-(h[i]*0.006)-a)
    if mini[1]>dh:
        mini[0]=i+1
        mini[1]=dh
print(mini[0])    

Measured memory_bytes: 3064
import collections

n = int(input())
a = [int(i) for i in input().split()]
a_i = [i - aa for i, aa in enumerate(a)]
a_j = [j + aa for j, aa in enumerate(a)]

ci = collections.Counter(a_i)
cj = collections.Counter(a_j)
ans = 0
for item, value in ci.items():
    if item in cj.keys():
        ans += cj[item] * ci[item]
print(ans)

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

int main(){
	int k,x;
	scanf("%d%d",&k,&x);
	
	for(int i=k-1;i>=0;i--){
		printf("%d ",x-i);
	}
	
	for(int i=1;i<k;i++){
		printf("%d ",x+i);
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	private BufferedReader br;
	private BufferedWriter bw;
	private StringTokenizer st;
	private String a;
	private String b;
	private String c;
	public static void main(String[] args) throws IOException {
		new Main().start();
	}

	void start() throws IOException {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		
			a=st.nextToken();
			b=st.nextToken();
			c=st.nextToken();
		
			if((a.charAt(a.length()-1)==b.charAt(0))&&(b.charAt(b.length()-1)==c.charAt(0))){
				bw.write("YES");
			}
			else{
				bw.write("NO");
			}
			
		bw.flush();
		br.close();
		bw.close();
	}

}


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


// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef complex<int> ci;
typedef complex<double> cd;
typedef complex<long double> cld;

// macros
#define rep(i, a, b) for(int i=a; i<b; i++)
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define tr(c, it) for(auto it=(c).begin(); it!=c.end(); it++)
#define pb push_back
#define mp make_pair
#define bitcount __builtin_popcount
#define ispresent(c, x) ((c).find(x) != (c).end())
#define watch(x) cout<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// template functions
template <typename T>
inline void printV(vector<T>& a) { rep(i, 0, sz(a)) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printV(vector<T>& a, int n) { rep(i, 0, n) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printVV(vector<vector<T>>& a)
{
	rep(i, 0, sz(a)) {
		printV(a[i]);
	}
	cout<<"\n";
}

template <typename T>
inline void clearVV(vector<vector<T>>& a)
{
	for(auto& x:a) {
		x.clear();
	}
	a.clear();
}
template <typename T>
inline void assignVV(vector<vector<T>> &a, T val)
{
	for(int i=0; i<sz(a); i++) {
		for(int j=0; j<sz(a[i]); j++) {
			a[i][j]=val;
		}
	}
}


// constants
const long double eps = 1e-9;
const int inf = 5e8;
const int modn = 1e9+7;
const int MAX = 1e5;

inline int add(int a, int b)
{
	return ((ll)a+b+modn)%modn;
}

inline int mul(int a, int b)
{
	return ((ll)a*b)%modn;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
    int n, k;
	cin>>n>>k;
	vector<int> a(n+1);
	vector<vector<int>> psum(n+1, vector<int>(k+1));
	vector<vector<int>> dp(n+1, vector<int>(k+1));
	
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for(int j=0; j<=k; j++) {
		dp[1][j]=(j<=a[1]?1:0);
		if(j>0)
			psum[1][j]=add(psum[1][j-1], dp[1][j]);
		else 
			psum[1][j]=dp[1][j];
	}
	//~ printV(psum[1]);
	
	for(int i=2; i<=n; i++) {
		for(int j=0; j<=k; j++) {
			if(j>a[i]) {
				dp[i][j]=add(psum[i-1][j], -psum[i-1][j-a[i]-1]);
				psum[i][j]=add(psum[i][j-1], dp[i][j]);
				continue;
			}
			dp[i][j]=psum[i-1][j];
			if(j>0)
				psum[i][j]=add(psum[i][j-1], dp[i][j]);
			else
				psum[i][j]=dp[i][j];
		}
	}
	cout<<dp[n][k]<<"\n";
	//~ printV(dp[n]);
	//~ printVV(dp);
	//~ printVV(psum);
    return 0;
}



Measured memory_bytes: 79736
object Main {
  def main(args: Array[String]) {
    val sc = new java.util.Scanner(System.in);
    val fh = (0 to sc.nextInt()).map(_*500).toList;
    val oh = (0 to sc.nextInt()).map(_*100).toList;
    val fi = (0 to sc.nextInt()).map(_*50).toList;
    val sum = sc.nextInt();
    println(fh.flatMap(x=>oh.flatMap(y=>fi.map(_+y+x)))
      .count(_ == sum).toString());
  }
}

Measured memory_bytes: 37728
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
int main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll ans=((n/500)*1000)+((n%500)/5)*5;
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int p[110000];
int main(){
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	for(int i=0;i<n;i++)scanf("%d",p+i);
	if(a>b){
		bool ok=false;
		for(int i=0;i<n;i++)if(p[i]>b)ok=true;
		if(ok)printf("Hanako\n");
		else{
			int tmp=0;
			for(int i=0;i<n;i++)tmp^=p[i];
			if(tmp)printf("Hanako\n");
			else printf("Jiro\n");
		}
	}else if(a==b){
		int tmp=0;
		for(int i=0;i<n;i++)tmp^=p[i]%(a+1);
		if(tmp)printf("Hanako\n");
		else printf("Jiro\n");
	}else{
		int at=-1;
		for(int i=0;i<n;i++){
			if(p[i]>a){
				if(at!=-1){
					printf("Jiro\n");return 0;
				}
				at=i;
			}
		}
		if(at==-1){
			int tmp=0;
			for(int i=0;i<n;i++)tmp^=p[i]%(a+1);
			if(tmp)printf("Hanako\n");
			else printf("Jiro\n");
		}else{
			int tmp=0;
			for(int i=0;i<n;i++)if(at!=i)tmp^=p[i]%(a+1);
			int req=p[at]-tmp;
			if(req<0||req>a||tmp>a)printf("Jiro\n");
			else printf("Hanako\n");
		}
	}
}

Measured memory_bytes: 1396
#include <iostream>
#include <cmath>
// #include<bits/stdc++.h>

using namespace std;

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

	int up = floor((double)B / (double)K);
	int down = ceil((double)A / (double)K);

	if (down <= up) {
		cout << "OK" << endl;
	} else {
		cout << "NG" << endl;
	}
}


Measured memory_bytes: 3100
/*
title:

url:

よくわからなかったので解説をみた。
なんとなくの理解を明晰に言葉で表すのって難しい
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

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

typedef pair<int, int> pint;
typedef long long ll;

int main()
{
    string s;
    cin >> s;
    int ans = s.size();
    rep(i, s.size() - 1)
    {
        if (s[i] != s[i + 1])
        {
            ans = min(ans, max(i + 1, (int)s.size() - i - 1));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}


int main(){
  int x;
  cin >> x;

  ll lcm = x / gcd(360, x) * 360;
  cout << lcm / x << endl;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)



//*
//プラキュー（二分ヒープ）（最低限バージョン）
//int PQhikaku(int i,int j);//jの方が優先度が高いならtrueを返す
int PQhikaku(ll*heap,int i,int j){return heap[i]<heap[j];}
void heap_utod(ll*heap,int n){
	if(2*n>heap[0])return;
	int rflag=(2*n+1<=heap[0])&&(PQhikaku(heap,2*n,2*n+1));
	if(PQhikaku(heap,n,2*n+rflag)){
		ll temp=heap[2*n+rflag];
		heap[2*n+rflag]=heap[n];
		heap[n]=temp;
		heap_utod(heap,2*n+rflag);
	}
}
void heap_dtou(ll*heap,int n){
	if(n==1||PQhikaku(heap,n,n/2))return;
	ll temp=heap[n];
	heap[n]=heap[n/2];
	heap[n/2]=temp;
	heap_dtou(heap,n/2);
}
ll PQpop(ll*heap){
	ll rr=heap[1];
	heap[1]=heap[heap[0]--];
	heap_utod(heap,1);
	return rr;
}
void PQpush(ll*heap,ll n){
	heap[++heap[0]]=n;
	heap_dtou(heap,heap[0]);
}
//*/


typedef struct edge{ll s,g;}E;
int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g>(*q).g)return -1;
	return 1;
}

E e[100010];
ll h[100010];
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,n){
		ll s,g;
		scanf("%lld%lld",&s,&g);
		e[i].s=s;
		e[i].g=g;
	}
	qsort(e,n,sizeof(E),esort);
//	rep(i,0,n)printf("%d %d\n",e[i].s,e[i].g);
	
	ll ans=0,crr=0;
	rep(i,1,m+1){
		while(crr<n&&e[crr].s<=i)PQpush(h,e[crr++].g);
		if(h[0])ans+=PQpop(h);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 3324
import math
def main():
    a, b, h, m = map(int, input().split(" "))
    r1 = h*30 + m / 2
    r2 = 6 * m
    r3 = abs(r1-r2)
    print(math.sqrt(a **2 + b **2 -2*a*b*math.cos(math.radians(r3))))

if __name__ == "__main__":
    main()

Measured memory_bytes: 9500