akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int n,m;
  cin>>n>>m;
  vector<vin> g(n);
  rep(i,0,m){
   int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int ans=0;
  vector<int> order(n-1);
  for (int i = 0; i < n-1; ++i) order[i] = i+1;
  do {
    //1とorder[0]の間に辺があるか。
    //order[0]とorder[1]の間の辺があるか。...
    bool ok=true;
    auto rs=find(g[0].begin(), g[0].end(), order[0]);
    if(rs==g[0].end()) continue;
    rep(i,0,n-2){
      rs=find(g[order[i]].begin(), g[order[i]].end(), order[i+1]);
      if(rs==g[order[i]].end()) ok=false;
    }
      if(ok)ans++;
    
  } while (next_permutation(order.begin(), order.end()));
          cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define rep(i, n)   for(int i = 0; i < (n); i++)
const int INF = 1e9;
using namespace std;

int n;
vector<int>len(3);
int ans = INF;
vector<pair<int, int> >now(4, pair<int, int>(0, 0));
void dfs(int depth, vector<int>&l){
    if(depth < n){
	rep(i, 4){
	    now[i].first += l[depth];
	    now[i].second++;
	    dfs(depth+1, l);
	    now[i].first -= l[depth];
	    now[i].second -= 1;
	}
    }else{
	int tmp = 0;
	rep(i, 3){
	    if(now[i].second == 0)  return;
	    tmp += abs(len[i]-now[i].first)+10*(now[i].second-1);
	}
	ans = min(ans, tmp);
    }
}

int main(){
    cin >> n;
    rep(i, 3)	cin >> len[i];
    vector<int>l(n);
    rep(i, n)	cin >> l[i];
    dfs(0, l);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* class */
class DisjointSet {
public:
    // d[i] is root => d[i] < 0 & d[i] is the size of tree
    // d[i] is child => d[i] >= 0 & d[i] = i.parent
    vector<int> d;

    DisjointSet() {}
    DisjointSet(int size) : d(size, -1) {}

    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if ( d[x] > d[y] ) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};
/* global variables */
/* function */
/* main */
int main(){
    int N, M;
    cin >> N >> M;
    DisjointSet ds = DisjointSet(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        ds.unite(a, b);
    }

    int mx = 0;
    for (int i = 0; i < N; i++) {
        mx = max(mx, ds.size(i));
    }
    cout << mx << '\n';
}


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

int main()
{
  int N,A,B;
  int res=0;
  cin >> N>>A>>B;

  for(int i=1;i<=N;i++){
    int sum=0;
    int num=i;
    rep(j,5){
      sum += num%10;
      num /= 10;
    }
    if(A<=sum && sum<=B) res+=i;
  }

  cout << res << endl;
}


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

int main(){
  uint64_t n;
  cin>>n;
  uint64_t r10=1;
  uint64_t r8=1;
  uint64_t r9=1000000005;
  rep(i,n){
    r10=(r10*10)%1000000007;
    r8=(r8*8)%1000000007;
    r9=(r9*9)%1000000007;
  }
  cout<<(r10+r8+r9)%1000000007<<endl;
}

Measured memory_bytes: 3640
import math
N=int(input())
tmp=N+1
for i in range(1,int(math.sqrt(N)+1)):
  if N%i==0:
    if i+(N/i)<=tmp:
      tmp=i+(N/i)
if tmp==N+1:
  print(int(N-1))
else:
  print(int(tmp-2))

Measured memory_bytes: 3060
import java.util.Scanner;

class Main
{ 
	int st[]; 
	int minVal(int x, int y) { 
		return (x < y) ? x : y; 
	} 

	 
	int getMid(int s, int e) { 
		return s + (e - s) / 2; 
	} 

	
	int RMQUtil(int ss, int se, int qs, int qe, int index) 
	{ 
		 
		if (qs <= ss && qe >= se) 
			return st[index]; 

		
		if (se < qs || ss > qe) 
			return Integer.MAX_VALUE; 

		 
		int mid = getMid(ss, se); 
		return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
				RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
	} 

	
	int RMQ(int n, int qs, int qe) 
	{ 
		
		if (qs < 0 || qe > n - 1 || qs > qe) { 
			System.out.println("Invalid Input"); 
			return -1; 
		} 

		return RMQUtil(0, n - 1, qs, qe, 0); 
	} 

	
	int constructSTUtil(int arr[], int ss, int se, int si) 
	{ 
		
		if (ss == se) { 
			st[si] = arr[ss]; 
			return arr[ss]; 
		} 

		
		int mid = getMid(ss, se); 
		st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
				constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
		return st[si]; 
	} 

	
	void constructST(int arr[], int n) 
	{ 
		 
		int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 

		
		int max_size = 2 * (int) Math.pow(2, x) - 1; 
		st = new int[max_size]; 

		 
		constructSTUtil(arr, 0, n - 1, 0); 
	} 

	 
	public static void main(String args[]) 
	{ 
		
		
		Scanner sc = new Scanner(System.in);
		String N = sc.next(); 
		String slide = sc.next();
		Main tree = new Main();
		int arr[] = new int[Integer.parseInt(N)];
		for(int i=0; i<Integer.parseInt(N); i++)
		{
			arr[i] = Integer.parseInt(sc.next());
		}
		
		tree.constructST(arr, Integer.parseInt(N));
		
		for(int i=0;i<=Integer.parseInt(N) - Integer.parseInt(slide);i++) {
			int result=tree.RMQ(Integer.parseInt(N), i, i+Integer.parseInt(slide)-1);
			if(i!= Integer.parseInt(N) - Integer.parseInt(slide)){
					System.out.print(result+" ");
				}else{
					System.out.println(result);
				}
		}
	} 
} 


Measured memory_bytes: 179404
#![allow(clippy::needless_range_loop)]
#![allow(unused_imports)]
use std::cmp::{max, min};

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut 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,
        edges: [(usize, usize); n - 1]
    }
    let ans = n * (n + 1) * (n + 2) / 6 - edges.iter().map(|(a, b)| min(a, b) * (n - max(a, b) + 1)).sum::<usize>();
    println!("{}", ans);
}


Measured memory_bytes: 7892
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define FORR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (e), i ## __begin = (b); i -- > i ## __begin;)
#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)
#define ALL(x) begin (x), end (x)
using namespace std;

template <typename T>
using reverse_priority_queue = priority_queue <T, vector <T>, greater <T>>;

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

  size_t n;
  cin >> n;

  reverse_priority_queue <double> q;
  rep (i, n)
  {
    double v;
    cin >> v;
    q.push (v);
  }

  while (q.size () >= 2)
  {
    auto v1 = q.top ();
    q.pop ();
    auto v2 = q.top ();
    q.pop ();
    auto v3 = (v1 + v2) / 2.0;
    q.push (v3);
  }
  cout << fixed << setprecision (15) << q.top () << endl;
}


Measured memory_bytes: 384
import Control.Monad
import Control.Monad.Primitive (PrimState)
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Data.IORef

main :: IO ()
main = do
    n <- fst . fromJust . B.readInt <$> B.getLine
    as <- V.fromList . B.words <$> B.getLine
    mv <- MV.unsafeNew (n + 1) :: IO (MV.MVector (PrimState IO) B.ByteString)
    l <- newIORef (n `div` 2)
    r <- newIORef (n `div` 2 + 1)
    forM_ [0..(n - 1)] $ \i ->
        if i `mod` 2 == (n - 1) `mod` 2
            then do
                m <- readIORef l
                MV.unsafeWrite mv m (as V.! i)
                modifyIORef l pred
            else do
                m <- readIORef r
                MV.unsafeWrite mv m (as V.! i)
                modifyIORef r succ
    j <- readIORef l
    v <- V.unsafeFreeze $ MV.slice (j + 1) n mv
    B.putStrLn $ B.unwords $ V.toList v


Measured memory_bytes: 55036
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    ll n,p;
    cin >> n >> p;

    ll ans = 1;
    if (n == 1) {
        ans = p;
    } else {
        ll x = pow(p,1.0/n)+1;
        while(x > 1) {
            ll y = pow(x,n);
            if (p % y == 0) {
                p /= y;
                ans *= x;
            } else {
                x--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  int a, b;
  cin >> a >> b;

  cout << a * b << '\n';




  
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define int long long

using namespace std;

const int N = 2e5 + 5;



signed main()
{/*
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    int n;
    string s;
    int k1 = 0, k2 = 0;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        if (s[i] == 'R')
            k1++;
        else
            k2++;
    int bad1 = 0;
    for (int i = 0; i < k1; i++)
        if (s[i] == 'W')
            bad1++;
    cout << bad1;
    return 0;
}


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

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

void dfs(vvvi& g, vi& v, int k)
{
    if(v[k]) return;

    v[k] = 1;

    for(auto& e : g[k]) if(e[1])
        dfs(g, v, e[0]);
}

int main()
{
    ios_base::sync_with_stdio(0);

    int n, m; cin >> n >> m;

    vvvi g(n + 1);

    for(int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;

        g[a].push_back({b, 1});
        g[b].push_back({a, 1});
    }

    int ans = 0;

    for(int i = 1; i <= n; i++)
    for(auto& e : g[i])
    {
        e[1] = 0;

        vi v(n + 1);

        dfs(g, v, 1);

        int cnt = 0;
        for(int j = 1; j <= n; j++) cnt += v[j];

        ans += cnt < n;

        e[1] = 1;
    }

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

Measured memory_bytes: 256
s = input()
a = int(s[0])
b = [int(s[1]), - int(s[1])]
c = [int(s[2]), - int(s[2])]
d = [int(s[3]), - int(s[3])]
e = 0
f = 0
g = 0
sign = ["+", "-"]
for i in range(2):
    for j in range(2):
        for k in range(2):
            if a+b[i]+c[j]+d[k] == 7:
                e = i
                f = j
                g = k
print(str(a)+sign[e]+str(b[0])+sign[f]+str(c[0])+sign[g]+str(d[0])+"=7")

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

using namespace std;

typedef long long ll;

ll sum1[100010], sum2[100010];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		ll a;
		cin >> a;
		sum1[i] = a;
		if (a > 0) sum2[i] = a;
		sum1[i] += sum1[i - 1];
		sum2[i] += sum2[i - 1];
	}

	ll ans = 0;
	for (int i = 0; i <= N - K; i++) {
		ans = max(ans, sum2[N] + sum2[i] - sum2[i + K] + max(sum1[i + K] - sum1[i], 0LL));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int nbElem; cin >> nbElem;
	ll dpt, prev;
	vector<ll> diff;
	for (int i = 0; i < nbElem; ++i) {
		ll cur; cin >> cur;
		if (i == 0) dpt = cur;
		else diff.push_back(cur-prev);
		prev = cur;
	}
	vector<ll> id(nbElem-1);
	iota(all(id), 0);
	auto perm = id;
	int nbSwap; ll expo;
	cin >> nbSwap >> expo;
	for (int iSwap = 0; iSwap < nbSwap; ++iSwap) {
		int idx; cin >> idx;
		swap(perm[idx-2], perm[idx-1]);
	}
	auto comp = [&] (vector<ll> p, vector<ll> q) {
		vector<ll> r = p;
		for (int i = 0; i < len(p); ++i) {
			r[i] = q[p[i]];
		}
		return r;
	};
	auto get = [&] (ll x, auto self) {
		if (x == 0) return id;
		vector<ll> r = self(x/2, self);
		r = comp(r,r);
		if (x & 1) r = comp(perm, r);
		return r;
	};
	diff = comp(get(expo, get), diff);
	for (int i = 0; i < nbElem; ++i) {
		if (i) dpt += diff[i-1];
		cout << dpt << "\n";
	}
}


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

signed main() {
	int n;
	cin >> n;
	if(n % 2 == 0) {
		cout << n << endl;
	}
	else {
		cout << n * 2 << endl;
	}
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int[] a = new int[n];
        long sum = 0;
        
        for(int i = 0; i < a.length; i++){
            a[i] = scan.nextInt();
        }
        
        int max = a[0];
        int min = a[0];
        
        for(int i = 0; i < a.length; i++){
            sum += a[i];
            if(max < a[i])
            max = a[i];
            if(min > a[i])
            min = a[i];
        }
        System.out.printf("%d %d %d\n", min,max,sum);
    }
}


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

 int main(){
  long double h, w;
  cin >> h >> w;
  if(h == 1 || w == 1) cout << 1 << endl;
  else{
    ll ans = ceil((h * w)/2); 
    cout << ans << endl;
  }
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)


// 区間加算　一点取得 RAQ 平方分割で実装
template <typename T>
struct RAQ{// 0-index
	int n,rn,bn; // rn個のかたまりをbn個
	vector<T> data,bucket;
	RAQ(int n_){init(n_);}
	void init(int n_){
		n = n_;
		rn = sqrt(n);
		bn = ceil((double)n/rn);
		data.resize(n,0);
		bucket.resize(bn,0);
	}
	T get(int i){
		return data[i]+bucket[i/rn];
	}
	void add(int s,int t,T x){ // s~tにxを加算
		for(int i=s;i<=t;++i){
			if(i%rn==0 && (i+rn-1)<=t){
				bucket[i/rn] += x;
				i += rn-1;
			}else{
				data[i] += x;
			}
		}
	}
};


vector<int> child[100001];

// 頂点iの部分木にあるの頂点のRAQ上の番号が
// (data1[i],data2[i])になるようにするdfs
vector<int> data1(100001),data2(100001);
int a=0;
void dfs(int i = 0){
	data1[i] = a++;
	for(auto c:child[i]){
		dfs(c);
	}
	data2[i] = a-1;
}


int main(){
	int n,k,c,q;
	cin >> n;
	FOR(i,0,n){
		cin >> k;
		FOR(j,0,k){
			cin >> c;
			child[i].push_back(c);
		}
	}
	dfs();
	cin >> q;

	RAQ<ll> raq(100003);
	FOR(qq,0,q){
		int qu,u,v;
		ll w;
		cin >> qu;
		if(qu){//getsum
			cin >> u;
			cout << raq.get(data1[u]) << "\n";
		}else{
			cin >> v >> w;
			raq.add(data1[v],data2[v],w);
		}
	}
}



Measured memory_bytes: 12748
N = int(input())
A = list(input())
B = list(input())
C = list(input())
cnt = 0
for a, b, c in zip(A, B, C):
    if (a != b and a != c and b != c):
        cnt += 2
    elif (a == b != c):
        cnt += 1
    elif (a == c != b):
        cnt += 1
    elif (c == b != a):
        cnt += 1
print(cnt)


Measured memory_bytes: 3060
def gcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a <= b:
        return gcd(b % a, a)
    elif b < a:
        return gcd(a % b, b)


n = int(input().strip())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n, 1):
    ans = gcd(ans, a[i])
print(ans)


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

int main()
{
    int n;
    cin>>n;
    int a[n];//i番目の料理
    int b[n];//i番目の料理で得る満足度
    int c[n-1];//iを食べた直後にi+1を食べると追加で上がる満足度
    int i;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]--;
    }
    for(i=0;i<n;i++)
    {
        cin>>b[i];
    }
    for(i=0;i<n;i++)
    {
        cin>>c[i];
    }
    /*
    int ans=b[a[0]];
    i=1;
    while(1)
    {
        ans += b[a[i]];
        if(a[i]==a[i-1]+1)
        {
            ans += c[a[i-1]];
        }
        i++; 
      if(i>=n)break;
    }
    */
   int ans =0;
    for(i=0;i<n;i++)
    {
        ans+=b[a[i]];
        if(i>0 && a[i]==a[i-1]+1)
        {
            ans+=c[a[i-1]];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> vec;
bool dp[2][5005];
bool judge(int pos){
  for(int i=0;i<2;i++){
    for(int j=0;j<5005;j++){
      dp[i][j]=false;
    }
  }
  dp[0][0]=true;
  for(int i=0;i<=n;i++){
    for(int j=0;j<5005;j++){
      if(i!=pos){
        if(j+vec[i]<5005&&dp[0][j]) dp[1][j+vec[i]]=true;
      }
      if(dp[0][j]) dp[1][j]=true;
    }
    for(int j=0;j<5005;j++) {
      dp[0][j]=dp[1][j];
    }
  }
  if(k-vec[pos]<=0) return true;
  for(int j=k-vec[pos];j<k;j++){
    if(dp[0][j]) return true;
  }
  return false;
}
int main(){
  cin>>n>>k;
  vec.push_back(0);
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    vec.push_back(a);
  }
  sort(vec.begin(),vec.end());
  int lb=0,rb=n+1;
  while(rb-lb>1){
    int mid=(lb+rb)/2;
    if(!judge(mid)) lb=mid;
    else rb=mid;
  }
  cout<<lb<<endl;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll solve(){
    ll res = 0;
    ll H,W; cin >> H >> W;
    vector<vector<ll>> dp(H+1,vector<ll>(W+1));
    for(int i = 1; i <= H;i++){
        for(int j = 1; j <= W;j++){
            ll c; cin >> c;
            dp[i][j] = c==0;
        }
    }
    for(int i = 1; i <= H;i++){
        for(int j = 1; j <= W;j++){
            if(dp[i][j] == 0) continue;
            dp[i][j] = min({
                dp[i-1][j-1],
                dp[i-1][j],
                dp[i][j-1]
            }) + 1;
            res = max(res,dp[i][j]);
        }
    }
    return res*res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}



Measured memory_bytes: 18088
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	int n;
	cin>>n;
	vector<int> a(10);
	for(int i=0;i<n;i++){
		queue<int>b,c,d;
for(int j=0;j<10;j++){
	cin>>a[j];
}
for(int j=0;j<10;j++){
	if(b.empty()){
		b.push(a[j]);
	}else if(b.back()<a[j]){
		b.push(a[j]);
	}else if(c.empty()){
		c.push(a[j]);
	}else if(c.back()<a[j]){
		c.push(a[j]);
	}else{
		d.push(a[j]);
	}

}
if(d.empty()){
	cout<<"YES"<<endl;
}else{
	cout<<"NO"<<endl;
}
	}
	return 0;
}

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

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

const int mxN = 200010;
const int inf = mxN<<1;
int dpm[(1<<26)];
int dp[mxN];
int msk[mxN];

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

	int N;
	string s;
	cin>>s;
	N = s.size();
	msk[N] = dp[N] = dpm[0] = 0;
	
	for(int i = 1;i < (1<<26);i++) dpm[i] = inf;
	
	for(int i = N-1;i >= 0;i--) {
		msk[i] = msk[i+1] ^ (1<<(s[i]-'a'));
		dp[i] = dpm[msk[i]] + 1;
		for(int j = 0;j < 26;j++) {
			dp[i] = min(dp[i],dpm[msk[i]^(1<<j)]+1);
		}
		dpm[msk[i]] = min(dpm[msk[i]],dp[i]);
	}
	cout<<dp[0]<<'\n';
	return 0;
}


Measured memory_bytes: 264400
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Dice dice = new Dice();
        for (int i = 0; i < 6; i++) {
            dice.generateDice(i, scan.nextInt());
        }
        dice.roll(scan.next());
        System.out.println(dice.getTop(1));
    }
}

class Dice {
    private int[] num = new int[6];
    void generateDice(int count, int n) {
        num[count] = n;
    }

    void roll(String direction) {
        for (int i = 0; i < direction.length(); i++) {
            int top = num[0];
            switch (direction.charAt(i)) {
                case 'N':
                    num[0] = num[1];
                    num[1] = num[5];
                    num[5] = num[4];
                    num[4] = top;
                    break;
                case 'S':
                    num[0] = num[4];
                    num[4] = num[5];
                    num[5] = num[1];
                    num[1] = top;
                    break;
                case 'W':
                    num[0] = num[2];
                    num[2] = num[5];
                    num[5] = num[3];
                    num[3] = top;
                    break;
                case 'E':
                    num[0] = num[3];
                    num[3] = num[5];
                    num[5] = num[2];
                    num[2] = top;
                    break;
            }
        }
    }

    int getTop(int i) {
        return num[i -1];
    }
}

Measured memory_bytes: 26208
#include <stdio.h>

int main(void){
	int N, A, B, C, D;
	int num = 0, money = 0, min_money = 0;
	
	scanf("%d %d %d %d %d", &N, &A, &B ,&C, &D);
	while(N > num){
		num += A;
        money += B;
	}

    min_money = money;

    num = 0;
    money = 0;
    while(N > num){
		num += C;
        money += D;
	}

    if(min_money > money){
        min_money = money;
    }

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

	return 0;
}


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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

ll inf = 1000000000;

deque<ll> dq;
int g[100005];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  ll k;cin>>k;

  for(int i=0;i<100005;i++)g[i] = inf;

  g[1] = 1;
  dq.push_front(1);
  while(!dq.empty()){
    int t = dq.front();dq.pop_front();
    int nx = (t + 1) % k;
    if(g[nx] > g[t] + 1){
      g[nx] = g[t] + 1;
      dq.push_front(nx);
    }

    nx = (t * 10) % k;

    if(g[nx] > g[t]){
      g[nx] = g[t];
      dq.push_back(nx);
    }
  }

  cout<<g[0]<<endl;

  return 0;
}


Measured memory_bytes: 1152
#include<cstdio>
#include<algorithm>
using namespace std;

int a[200010];
long long s[200010];
int main(){
    int n;
    long long ans=0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", a+i);
    for(int i=1; i<=n; i++) s[i] = s[i-1] + a[i];
    sort(s, s+n+1);
    for(int i=0, j; i<=n; i=j){
        for(j=i; j<=n && s[i]==s[j]; j++);
        ans += 1ll*(j-i)*(j-i-1)/2;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 2560
#include<stack>
#include<cstdio>
inline int in();
inline void wr(int);
const int N=(int)1e5+5;
int ju[N][N/100],_in[N],sum[N];
inline int mx(int,int);
int main(int argc,char**argv){
	register int n=in(),m=in();
	for(register int i=1;i<=m;++i){
		register int u=in(),v=in();
		ju[u][++ju[u][0]]=v,++_in[v];
	}
	std::stack<int>stack;
	for(register int i=1;i<=n;++i)
		if(!_in[i])stack.push(i);
	while(!stack.empty()){
		register int u=stack.top();
		stack.pop();
		for(register int i=1;i<=ju[u][0];++i){
			if(sum[ju[u][i]]<sum[u]+1)
				sum[ju[u][i]]=sum[u]+1;
			if(!--_in[ju[u][i]])stack.push(ju[u][i]);
		}
	}
	register int ans=0;
	for(register int i=1;i<=n;++i)
		ans=mx(ans,sum[i]);
	wr(ans);
}
inline int mx(int x,int y){
	return x>y?x:y;
}
inline int in(){
	register char c=getchar();
	register int x=0,f=1;
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c&15);
	return x*f;
}
inline void wr(int x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)wr(x/10);
	putchar(x%10+'0');
}


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

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  ll d = c - a - b;
  if (d > 0 && 4 * a * b < d * d) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3636
/* 
 * File:   main.cpp
 * Author: Sebastian Hall
 * Created on August 20, 2020, 3:29 PM
 * Purpose: https://atcoder.jp/contests/dp/tasks/dp_a
 */

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

typedef long long ll;
typedef long double triple;

int main() {
    ios::sync_with_stdio(false);
    //Declare variables
    int n = 0; 
    
    //Create arrays and read input
    cin>>n;
    int arr[n], dp[n];
    for(int i = 0; i < n; ++i) cin>>arr[i];
    
    //Create dp array
    dp[0] = 0, dp[1] = abs(arr[1] - arr[0]);
    for(int i = 2; i < n; ++i) {
        dp[i] = min(dp[i - 1] + abs(arr[i] - arr[i - 1]), dp[i - 2] + abs(arr[i] - arr[i - 2]));
    }

    //Output answer
    cout<<dp[n - 1]<<endl;
    //A Sebastian Production
    return 0;
}

Measured memory_bytes: 4372
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<stack>
#include<iostream>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define MOD 1000000007
#define vec(a) vector<int>a
using namespace std;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
	ll n,i,j,k;
	cin>>n;
	k=n;
	string str;
	cin>>str;
	j=str.length();
	n=min(n,j);
	for(i=0;i<n;i++)
		cout<<str[i];
	if(j>k)
	cout<<"..."<<"\n";
}
	


Measured memory_bytes: 3560
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  int a,b,c,x,ans=0;
  cin>>a>>b>>c>>x;
  int i,j,k;
  i=0;
  while(i*500<=x && i<=a){
    j=0;
    while(j*100+i*500<=x && j<=b){
      k=0;
      while(k*50+j*100+i*500<=x && k<=c){
	if(k*50+j*100+i*500==x) ans++;
	k++;
      }
      j++;
    }
    i++;
  }
  cout<<ans<<endl;   
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    int m;
    cin >> m;
    cout << 48-m << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep(i,n) FOR(i,0,n-1)
#define int long long
#define MOD 998244353
#define MAXN  100005
#define P pair<int,int>

signed main(){
	
	int n,m,k;cin>>n>>m>>k;
	
	rep(i,n+1)rep(j,m+1)
	{
		if((n-i)*j+(m-j)*i == k)
		{
			cout << "Yes"<<endl;
			return 0;
		}
	}
	
	cout << "No" << endl;
	return 0;
}

//cout << ans << endl;

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

int a[100];

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

	int N;
	cin >> N;
	for(int i = 0; i < N; i++) {
		cin >> a[i];
	}

	int ans = 100000000;
	for(int i = -100; i <= 100; i++) {
		int sum = 0;
		for(int j = 0; j < N; j++) {
			sum += (i - a[j]) * (i - a[j]);
		}
		ans = min(ans, sum);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN =  + 15;

int main() {
#ifdef CitricAcid
    freopen ("input.txt", "rt", stdin);
#endif

    ll n;
    scanf("%lld", &n);
    ll res = 0;
    for(int i = 1; i <= n; i++) {
        res += (n + 1 - i) * i;
    }
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        if(u > v) swap(u, v);
        res -= 1ll * u * (n - v + 1);
    }
    printf("%lld\n", res);

#ifdef CitricAcid
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
/*
# author : CitricAcid
# date : 2020/07/26
*/

Measured memory_bytes: 3800
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define print_vec(v) rep(i,v.size()){if(i!=0)cout<<" ";cout<<v[i];}cout<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<'\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pi=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void yes(bool c) { if (c)print("Yes"); else print("No"); };

void solve() {
    int N,M; cin >> N >> M;
    vi a(M), b(M);
    vector<pair<int, int>> ps;
    rep(i,M){
        // cin >> a[i] >> b[i];
        // a[i]--;b[i]--;
        int a,b; cin >> a >> b;
        a--;b--;
        ps.pb(mp(a,b));
    }
    sort(ALL(ps));
    // for(auto x : ps){
    //     DEBUG(x.fi);
    //     DEBUG(x.sc);
    // }
    // int l = ps[0].fi;
    int r = ps[0].sc;
    ll ans = 1;
    rng(i,1,ps.size()){
        if(ps[i].fi >= r) {
            ans++;
            r = ps[i].sc;
        }else{
            r = min(r, ps[i].sc);
        }
    }
    print(ans);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


Measured memory_bytes: 2168
import math
N,H=map(int,input().split())
a=[0]*N
b=[0]*N
for i in range(N):
  a[i],b[i] = map(int,input().split())
  
p=0
cnt=0
nokori=0
b.sort(reverse=True)
maxi=max(a)

for th in b:
  if p>=H:
    break
  else:
    if th>maxi:
      p += th
      cnt+=1
else:
  nokori= math.ceil((H-p)/maxi)
print(cnt+nokori)

Measured memory_bytes: 11312
n=int(input())
dlist=[]
for _ in range(n):
    s = input()
    dict={}
    for char in s:
        if char not in dict:
            dict[char]=1
        else:
            dict[char]+=1
    dlist.append(dict)
first=dlist[0]
for i in range(1,n):
    for key in first:
        if key not in dlist[i]:
            first[key]=0
        else:
            first[key]=min(first[key],dlist[i][key])
first=sorted(first.items(),key=lambda x: x[0])
ans=""
for (key,value) in first:
    ans+=key*value
print(ans)

Measured memory_bytes: 3064
//gauravsinghh
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define ffo(i, a, b) for(int i = a; i >= b; i--)
#define MAX 100005
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

bool comp(const pair < ll, ll >&a, const pair < ll, ll >&b){
    return ((a.ss < b.ss) || (a.ss == b.ss && a.ff < b.ff));
}

signed main(){ 
    IOS
    //io_set();
    ll tt;
    string u;
    ld x, s = 0;
    w(tt){
        cin >> x >> u; 
        if(u == "JPY"){
            s += x;
        }
        else{
            s += (x * 380000.0);
        }
    }
    cout << fixed << setprecision(8) << s << endl;
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int N;
  cin >> N;
  int A[N][N];
  bool cand[N][N];
  REP(i, N) REP(j, N) {
    cin >> A[i][j];
    cand[i][j] = true;
  }
  REP(k, N) REP(i, N) REP(j, N) {
    if (A[i][j] > A[i][k] + A[k][j]) {
      cout << -1 << endl;
      return 0;
    }
    if (A[i][j] == A[i][k] + A[k][j] && 0 < A[i][k] && 0 < A[k][j]) {
      cand[i][j] = false;
    }
  }
  ll ans = 0;
  REP(i, N) REP(j, N) {
    if (cand[i][j]) ans += A[i][j];
  }
  cout << ans / 2 << endl;
  return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn for(int i=0;i<n;i++)
#define pb push_back
#define pob pop.back()
int main()
{
    int a,b;
    cin>>a>>b;
    if(a%2!=0 && b%2!=0) cout<<"Yes";
    else cout<<"No";
    return 0;
    
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/2
Solved on 2019/3/
@author: shinjisu
"""


# ABC 102 C Linear Approximation
import statistics


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC_WA_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.mean(a))
    dmp(m, 'mean')
    s = int(statistics.pstdev(a)) + 2
    dmp(s, 'std dev')
    minSum = sum([abs(a[j]) for j in range(N)])
    dmp(minSum, 'minSum')
    for i in range(1, s):
        aSum = sum([abs(a[j]-m+i) for j in range(N)])
        dmp((aSum, -m+i), 'aSum, -m+i')
        minSum = min(minSum, aSum)
        aSum = sum([abs(a[j]-m-i) for j in range(N)])
        minSum = min(minSum, aSum)
        dmp((aSum, -m-i), 'aSum, -m-i')
        dmp(minSum, 'minSum')
    dmp(minSum, 'minSum')
    return minSum


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.median(a))
    dmp(m, 'median')
    minSum = sum([abs(a[i]-m) for i in range(N)])
    dmp(minSum, 'minSum')
    return minSum


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)


Measured memory_bytes: 29696
import math
#(Xの)素数判定
#nが素数なら1,そうでないなら0を返す関数
def is_prime(X):
  if (X == 1): 
    return 0
  for i in range(2, int(math.sqrt(X)) + 1):
   if (X % i) == 0: return 0
  return 1

#(Xの)素因数分解
def prime_factorization(X,Factoring):
 #Factoring = {} #要素[ai,ti] -> X = (a1^t1)*...*(an^tn)
 p,P = 2,X
 if(is_prime(P) == 1): Factoring[P] = 1
 else:
  while(1):
   if(P <= p+1):
     break
   count = 0
   while(X%p == 0):
     X = X//p
     count += 1
   if(count != 0):
    if(p in Factoring): Factoring[p] += count
    else: Factoring[p] = count
   p += 1   
 return Factoring


N = int(input())
A = {}
ans = 1
for i in range(2,N+1):
 A = prime_factorization(i,A)
for k, v in A.items():
 ans = ans*(v+1)
 #k:key, v:value
print(ans%(10**9+7))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
	if (a == 0)return b;
	else return gcd(b%a, a);
}

bool used[30001];
vector<int>primes;

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

	for (int i = 2; i < 30001; i++) {
		bool flag = true;
		for (int j = 2; j*j <= i; j++) {
			if (i%j == 0) {
				flag = false;
				break;
			}
		}
		if (flag)primes.push_back(i);
	}

	vector<int>ans;
	ans.push_back(2); used[2] = true;
	ans.push_back(3); used[3] = true;
	if (N % 2)used[4] = true;
	ll sum = 5;
	int cnt = N-2;
	ll pro = 6;
	for (int i = 0; i < primes.size(); i++) {
		if (cnt == 1)break;

		int x = primes[i];
		for (int j = x; j < 30001; j += x) {
			if (used[j])continue;
			sum += j;
			cnt--;
			ans.push_back(j); used[j] = true;
			if (cnt == 1)break;
		}
		if (i > 1)pro *= x;
	}

	ll a = pro - (sum % pro);

	for (int i = a; i < 30001; i+=pro) {
		if (used[i])continue;

		if (gcd(sum, i) != 1) {
			ans.push_back(i);
			for (int j = 0; j < ans.size(); j++) {
				if (j)cout << " ";
				cout << ans[j];
			}
			cout << endl;
			return 0;
		}
	}


	for (int c = 2; c < primes.size(); c++) {
		int x = primes[c];
		ll tmppro = pro * x;
		used[ans.back()] = false;
		used[x] = true;
		sum += x - ans.back();
		ans.back() = x;

		a = tmppro - (sum % tmppro);
		for (int j = a; j < 30001; j += tmppro) {
			if (used[j])continue;

			if (gcd(sum, j) != 1) {
				ans.push_back(j);
				for (int k = 0; k < ans.size(); k++) {
					if (k)cout << " ";
					cout << ans[k];
				}
				cout << endl;

				return 0;
			}
		}
	}

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int f(int x,int k)
{
	if(x%k==0)return x/k;
	int t=x%k;
	int haha=max(1,t/((x/k)+1));
	return f(x-haha*((x/k)+1),k);
}
int main()
{
	int ans=0;
	scanf("%d",&n);
	int x,y;
	while(n--)
	{
		scanf("%d%d",&x,&y);
		ans^=f(x,y);
	}
	printf("%s\n",ans==0?"Aoki":"Takahashi");
}

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

int main(void)
{
    int a[3],b,c,i,j,k,n;

    cin >> a[0] >> a[1] >> a[2];
    sort(a,a+3);


    cout << a[2] - a[0];

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod = 1000000007;
struct UnionFind{
    vector<long long> par,height,size;
    UnionFind(ll N): par(N),height(N),size(N){
        for(ll i=0;i<N;i++){
            par.at(i)=i;
            height.at(i)=1;
            size.at(i)=1;
        }
    }

    ll root(ll x){
        if(par.at(x)==x)return x;
        return root(par.at(x));
    }

    void unite(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        if(rx!=ry){
            if(height.at(rx)<height.at(ry)) swap(rx,ry);
            size.at(rx)+=size.at(ry);
            height.at(rx)=max(height.at(ry)+1,height.at(rx));
            par.at(ry)=rx;
        }
    }

    bool same(ll x,ll y){
        if(root(x)==root(y))return true;
        else return false;
    }
    
};
int main(){
    
    ll N,K,L;
    cin>>N>>K>>L;

    vector<ll> a(K),b(K),c(L),d(L);
    for(ll i=0;i<K;i++)cin>>a.at(i)>>b.at(i);
    for(ll i=0;i<L;i++)cin>>c.at(i)>>d.at(i);

    UnionFind road(N), railway(N);

    for(ll i=0;i<K;i++){
        road.unite(a.at(i)-1,b.at(i)-1);
    }

    for(ll i=0;i<L;i++){
        railway.unite(c.at(i)-1,d.at(i)-1);
    }

    vector<ll> roro(N);
    for(ll i=0;i<N;i++){
        roro.at(i)=road.root(i);
    }

    vector<ll> raro(N);
    for(ll i=0;i<N;i++){
        raro.at(i)=railway.root(i);
    }
    map<P,ll> roots;
    for(ll i=0;i<N;i++){
        if(roots.count(P(roro.at(i),raro.at(i))))roots[P(roro.at(i),raro.at(i))]++;
        else roots[P(roro.at(i),raro.at(i))]=0;
    }
    for(ll i=0;i<N;i++){
        cout<<1+roots[P(roro.at(i),raro.at(i))]<<" ";
    }
}

Measured memory_bytes: 27136
#include <bits/stdc++.h>
#include <limits>
#include <math.h>
#include <cmath>
#include <cctype>
#include <cstdio>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll> ;
using vs = vector<string>;
using vb = vector<bool>;
using vll = vector<long long>;
using vvll = vector<vector<long long >>;
#define PI  3.1415926535
#define rep(i, k, n) for(ll i = k; i < n; i++)

int main(){
  ll a, b; cin >> a >> b;
  if(a > 9 || b > 9){cout << -1 << endl;}
  else{cout << a*b << endl;}
}
      


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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
int n, a[N], p[N];
ll k;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = -1;
  }
  int i = 1, cur = 0;
  while (p[i] == -1) {
    p[i] = cur;
    cur++;
    i = a[i];
  }
  if (k < cur) {
    for (int i = 1; i <= n; i++) {
      if (p[i] == k) {
        cout << i << "\n";
      }
    }
  } else {
    k -= p[i];
    k %= (cur - p[i]);
    k += p[i];
    for (int i = 1; i <= n; i++) {
      if (p[i] == k) {
        cout << i << "\n";
      }
    }
  }
  return 0;
}


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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define db(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define MOD 1000000007
using namespace std;
const long long INF = 3*1e18;

bool isPalin(string S){
    int left = 0, right = S.size() - 1;
    while(left < right){
        if(S[left++] != S[right--]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string S;
    cin >> S;
    ll N = S.size();
    string left = S.substr(0, (N-1)/2);
    string right = S.substr((N+1)/2, (N-1)/2);
    bool ans = isPalin(S) && isPalin(left) && isPalin(right);
    if(ans) cout << "Yes\n";
    else cout << "No\n";
}

Measured memory_bytes: 256
import sys, math
sys.setrecursionlimit(10 ** 6)
from collections import deque, defaultdict, Counter
from operator import itemgetter

def main():
    N = int(input())
    A = list(map(int, sys.stdin.readline().rstrip().split()))

    n = max(A)
    a = -1
    d = n
    for e in A:
        if e == n:
            continue
        if abs(e - n/2) < d:
            a = e
            d = abs(e - n/2)
    
    print(n, a)


if __name__ == '__main__':
    main()

Measured memory_bytes: 14932
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll a,b,c,k;
    ll Ans=0;
    cin>>a>>b>>c>>k;
    ll temp=min(a,k);
    Ans+=temp;
    k-=temp;
    temp=min(b,k);
    k-=temp;
    temp=min(c,k);
    Ans-=temp;
    cout<<Ans<<endl;
    return 0;
}


Measured memory_bytes: 3636