akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 5;
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
int n, a[N];
inline bool cmp(const int &a, const int &b) {
	return a > b;
}
int main() {
	n = Get();
	for (int i = 1; i <= n; ++i) a[i] = Get();
	std :: sort(a + 1, a + n + 1, cmp);
	
	int id = 0;
	while (id + 1 < n && id + 1 < a[id + 2]) ++id;
	
	int flagA = (a[id + 1] - id) & 1;
	int flagB = 1, rev = id;
	while (id + 1 < n && rev < a[id + 2]) ++id, flagB ^= 1;
	
	int flag = !(flagA & flagB);
	puts(flag ? "First" : "Second");
}

Measured memory_bytes: 512
N=int(input())
huga = list(map(int, input().split()))
huga.sort(reverse=True)
s=0
if N%2==1:
    for i in range(1,(N-1)//2):
        s+=huga[i]
    print(huga[0]+huga[N//2]+2*s)
else:
    for i in range(1,N//2):
        s+=huga[i]
    print(huga[0]+2*s)

Measured memory_bytes: 31628
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;



int main(){

	int n,count;

	while(true){
		scanf("%d",&n);
		if(n == 0)break;

		count = 0;

		while(n != 1){
			if(n % 2 == 0)n /= 2;
			else{
				n = 3*n + 1;
			}
			count++;
		}

		printf("%d\n",count);
	}

    return 0;
}

Measured memory_bytes: 2676
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#define MOD 1000000007
#define INT long long int
#define REP(i,n) for(int(i)=0;(i)<(n);(i)++) 
using namespace std;
const long long INF = numeric_limits<long long>::max();



int main()
{
  int N,M,Q;
  cin >>N>>M>>Q;
  vector<pair<int,int>> LR(M,{0,0});
  int p[Q],q[Q];
  REP(i,M) cin>>LR[i].first>>LR[i].second;
  REP(i,Q) cin>>p[i]>>q[i];
  vector<vector<int>> mapping(N+1,vector<int>(N+1,0));
  vector<vector<int>> rmap(N+1,vector<int>(N+1,0));
  
  REP(i,M){
    mapping[LR[i].first][LR[i].second] += 1;
  }

  REP(i,N+1){
    REP(j,N){
      rmap[i][j+1] = rmap[i][j] + mapping[i][j+1];
    }
  }
  REP(j,N+1){
    REP(i,N){
      rmap[i+1][j] += rmap[i][j];
    }
  }
  // REP(i,N+1){
  //   REP(j,N+1){
  //     cout<<rmap[i][j]<<' ';
  //   }
  //   cout<<endl;
  // }

  REP(i,Q){
    int x = p[i],y = q[i];
    int ans = rmap[y][y] - rmap[x-1][y]-rmap[y][x-1]+rmap[x-1][x-1];
    cout<<ans<<endl;
  }


  return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

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

	int ans = 0, cnt = 0;
	for(auto x : s){
		if(x == 'A' || x == 'C' || x == 'G' || x == 'T')
			cnt++;
		else
			ans = max(ans, cnt), cnt = 0;
	}

	cout << max(ans, cnt) << endl;

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;



int main(){
  string s;
  cin >> s;
  if (s[0] == s[2]) cout << "Yes\n";
  else cout << "No\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int MAX = 1000005;


int main(void){
    bool tmp_table[MAX], prime_table[MAX];
    int f[MAX];
    for(int i=0; i<MAX; i++){
        tmp_table[i] = true;
        prime_table[i] = false;
        f[i] = 0;
    }

    for(int i=2; i<MAX; i++){
        if(tmp_table[i]){
            prime_table[i] = true;
            int j = 2*i;
            while(j < MAX){
                tmp_table[j] = false;
                j += i;
            }
        }
    }

    for(int i=1; i<MAX; i++){
        if(i%2 == 0) f[i] = f[i-1];
        else{
            if(prime_table[i] == true && prime_table[(i+1)/2] == true) f[i] = f[i-1]+1;
            else f[i] = f[i-1];
        }
    }

    int q; cin >> q;
    for(int i=0; i<q; i++){
        int l, r; cin >> l >> r;
        cout<< f[r] - f[l-1] << endl;
    }
}

Measured memory_bytes: 6528
#include<iostream>
using namespace std;
#define N 100005
#define LL long long
#define rep(i,n) for((i)=0;(i)<(n);(i)++)

int n;
LL ans,mn;
LL a[N];
bool ok;

int main()
{
	
	int i;
	cin>>n;
	rep(i,n) cin>>a[i];
	mn=max(a[0],-a[0]);
	rep(i,n)
	{
		if(a[i]<0) ok^=1;
		if(a[i]<0) a[i]=-a[i];
		mn=min(mn,a[i]);
		ans+=a[i];
	}
	if(ok) ans-=2*mn;
	cout<<ans<<'\n';
	
	return 0;
}

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

#define ll long long
#define dd double
#define scl(n)    scanf("%lld",&n)
#define scd(n)    scanf("%lf",&n)
#define ptl(n)    printf("%lld",n)
#define ptd(n)    printf("%lf",n)
#define nline     printf("\n")
#define vld       vector<ll>
#define vbd       vector<bool>
#define eb        emplace_back
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define pi        2*acos(0.0)

using namespace std;

int main()
{
    ll n,x;
    vld a;
    scl(n);
    FOR(i,n)
    {
        scl(x);
        a.eb(x);
    }
    sort(a.begin(),a.end(),greater<ll>());
    x=0;
    n--;
    if(n%2!=0)
    {
        x+=a[0];
        n--;
        ll j=1;
        while(n>0)
        {
            x+=(2*a[j]);
            n-=2;
            j++;
        }
    }
    else
    {
        x+=a[0];
        n--;
        ll j=1;
        while(n>1)
        {
            x+=(2*a[j]);
            n-=2;
            j++;
        }
        x+=a[j];
    }
    ptl(x);
    return 0;
}


Measured memory_bytes: 5380
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <istream>
#include <set>
#include <queue>
#define rep0(i,n) for (long long int i = 0; i <= (n); ++i)
#define rep1(i,n) for (long long int i = 1; i <= (n); ++i)
#define REP(a,b) for (long long int i = a; i <= (b); ++i) 
#define ps push_back 
#define MOD 1000000007
using namespace std;
typedef long long ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int a, b, c;
	cin >> a >> b >> c;
	a -= b;
	cout << a % c << endl;
	return 0;
}

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

int gcd(int a, int b) {
    int c;
    while(a != 0) {
        c = a;
        a = b % a;
        b = c;
    }
    return b;
}

int lcm(int a, int b) {
    if ( ( 0 == a ) || ( 0 == b ) )
         return 0;
    return ((a / gcd(a, b)) * b);
}

int main(void) {
    int a, b;
    while(cin >> a >> b) {
        cout << gcd(a, b) << " " << lcm(a, b) << endl;
    }
}

Measured memory_bytes: 3088
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def inv(x):
  r=[1,0,x]
  w=[0,1,mod]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return w[0]

import collections

P=collections.defaultdict(int)
ans=0
for a in A:
  ans=(ans+inv(a))%mod
  pf={}
  for i in range(2,int(a**0.5)+1):
    while a%i==0:
      pf[i]=pf.get(i,0)+1
      a//=i
  if a>1:
    pf[a]=1
  for p in pf.keys():
    P[p]=max(P[p],pf[p])
for p in P.keys():
  ans=(ans*pow(p,P[p],mod))%mod

print(ans)

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


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

void wcut(ll s, int idx, ll cw, ll cd, vector<pair<ll,PLL>>& arr){
  cw -= s;
  arr.erase(arr.begin() + idx);
  if(cw*cd < s*cd){
    arr.push_back( make_pair( cw*cd , make_pair( cw , cd ) ));
    arr.push_back(make_pair( s*cd , make_pair( s , cd ) ));
  }else{
    arr.push_back(make_pair( s*cd , make_pair( s , cd ) ));
    arr.push_back(make_pair( cw*cd , make_pair( cw , cd ) ));
  }

}

void dcut(ll s, int idx, ll cw, ll cd, vector<pair<ll,PLL>>& arr){
  cd -= s;
  arr.erase(arr.begin() + idx);
  if(cw*cd < s*cw){
    arr.push_back(make_pair( cw*cd , make_pair( cw , cd ) ));
    arr.push_back(make_pair( cw*s , make_pair( cw , s ) ));
  }else{
    arr.push_back(make_pair( cw*s , make_pair( cw , s ) ));
    arr.push_back(make_pair( cw*cd , make_pair( cw , cd ) ));
  }

}


int main(){
  int n,w,d;
  int idx,s;
  while(true){
    cin >> n >> w >> d;
    vector<pair<ll,PLL>> arr;
    arr.push_back(make_pair( w*d , make_pair( w , d ) ));
    if(n==0 && w==0 && d==0) break;
    rep(i,n){
      cin >> idx >> s;
      idx --;
      ll cw = arr[idx].second.first;
      ll cd = arr[idx].second.second;

      s %= (2LL*(cw+cd));

      if(s < cw){//wカット
        wcut(s, idx, cw, cd, arr);
      }else if(s < (cw+cd)){// dカット
        s -= cw;
        dcut(s, idx, cw, cd, arr);
      }else if(s < (cw*2LL + cd)){// wカット
        s -= (cw+cd);
        wcut(s, idx, cw, cd, arr);
      }else{//dカット
        s -= (cw+cw+cd);
        dcut(s, idx, cw, cd, arr);
      }
      // rep(j,arr.size()){
      //   if(j != arr.size()-1) cout << arr[j].first << ' ';
      //   else cout << arr[j].first << endl;
      // }
    }

    sort(all(arr));
    rep(i,arr.size()){
      if(i != arr.size()-1) cout << arr[i].first << ' ';
      else cout << arr[i].first << endl;
    }
    arr.clear();
  }
  return 0;
}



Measured memory_bytes: 3076
#include <stdio.h>

#define NMAX 100000

int main(void)
{
	long A[NMAX] = {}, B[NMAX] = {};
	long i, n;
	long max = 0, max_B = 0;
	
	scanf("%ld", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%ld %ld",&A[i],&B[i]);
		if(A[i] > max)
		{
			max = A[i];
			max_B = B[i];
		}
	}
	
	printf("%ld\n", max+max_B);

	return 0;
}

Measured memory_bytes: 1664
n, k = map(int, input().split())
k = min(k, n - 1)

MOD = 1000000007

fact = [1] * (n + 1)
ifact = [0] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n, 0, -1):
    ifact[i - 1] = ifact[i] * i % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * ifact[k] * ifact[n - k] % MOD

ans = 0
for i in range(k + 1):
    ans += comb(n, i) * comb(n - 1, i)
    ans %= MOD
print(ans)

Measured memory_bytes: 18804
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

const MAX: i64 = 1000000000000;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let N: usize = sc.get();
    let K: usize = sc.get();
    let mut A: Vec<usize> = sc.vec(N);
    A.sort_by_key(|&i| Reverse(i));
    let mut F: Vec<usize> = sc.vec(N);
    F.sort();
    let mut q = BinaryHeap::new();
    for i in 0..N {
        q.push((A[i] * F[i], A[i]));
    }
    let mut ok = MAX;
    let mut ng = -1;
    while (ok - ng).abs() > 1 {
        let mid = (ok + ng) / 2;
        let mut qc = q.clone();
        let mut cnt = 0;
        while let Some((t, a )) = qc.pop() {
            let mid = mid as usize;
            if t > mid {
                let f = t / a;
                cnt += (t - mid + (f - 1)) / f;
            }
        }
        if cnt <= K {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    println!("{}", ok);
}


Measured memory_bytes: 11944
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;
int dx[] = {-1,0,0,1};
int dy[] = {0,1,-1,0};
int xs,ys,tx,ty,kx,ky;


int main(){
    while(true){
	cin >> xs >> ys;
	if(xs == 0 && ys == 0) break;
	cin >> tx >> ty;
	cin >> kx >> ky;
	tx--;
	ty--;
	kx--;
	ky--;
	if(tx==kx&&ty==ky){
	    cout << 0 << endl;
	    continue;
	}
	vector< vector<int> > map(ys,vector<int>(xs));
	REP(i,ys)REP(j,xs) cin >> map[i][j];

	queue<int> qtx;
	queue<int> qty;
	queue<int> qkx;
	queue<int> qky;
	queue<int> qn;
	set< pair< pair<int,int> , pair<int,int> > > used;
	int ans = 100;
	qtx.push(tx);
	qty.push(ty);
	qkx.push(kx);
	qky.push(ky);
	qn.push(1);
	while(!qtx.empty()){
	    int x1 = qtx.front();
	    int y1 = qty.front();
	    int x2 = qkx.front();
	    int y2 = qky.front();
	    int n = qn.front();
	    if(n >= 100){
		ans = min(ans,100);
		break;
	    }
	    qtx.pop();
	    qty.pop();
	    qkx.pop();
	    qky.pop();
	    qn.pop();
	    REP(i,4){
		int ntx = x1 + dx[i];
		int nty = y1 + dy[i];
		int nkx = x2 - dx[i];
		int nky = y2 - dy[i];
		if(ntx<0 || xs <= ntx) ntx = x1;
		if(nty<0 || ys <= nty) nty = y1;
		if(nkx<0 || xs <= nkx) nkx = x2;
		if(nky<0 || ys <= nky) nky = y2;
		if(map[nty][ntx] == 1) {
		    ntx = x1;
		    nty = y1;
		}
		if(map[nky][nkx] == 1) {
		    nkx = x2;
		    nky = y2;
		}
		pair< pair<int,int> , pair<int,int> > pp(pair<int,int>(ntx,nty),pair<int,int>(nkx,nky));
		if(used.find(pp) != used.end()) continue;
		used.insert(pp);

		if(ntx==nkx&&nty==nky){
		    ans = min(ans,n);
		    break;
		}
		qtx.push(ntx);
		qty.push(nty);
		qkx.push(nkx);
		qky.push(nky);
		qn.push(n+1);
	    }
	    if(ans < 100) break;
	}
	if(ans>=100) cout << "NA" << endl;
	else cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 12176
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
int N,Q;
int d[200000]={0};
vector<vector<int> > v;
void calc(int now, int point, int pre){
  d[now] += point;
  for(auto j : v[now]){
    if(j==pre) continue;
    calc(j, d[now], now);
  }
}
int main(){
  cin>>N>>Q;
  v.resize(N);
  rep(i,0,N-1){
    int x,y;  cin>>x>>y;
    --x;  --y;
    v[x].pb(y);
    v[y].pb(x);
  }
  rep(i,0,Q){
    int x,y;  cin>>x>>y;
    --x;
    d[x] += y;
  }
  calc(0,0,-1);
  rep(i,0,N) cout<<d[i]<<" ";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 23424
#include <bits/stdc++.h>
#define rep(begin, end) for (i=begin;i<end;i++)
#define repj(begin, end) for (j=begin;j<end;j++)
#define init(arr, end, val) for (i=0;i<end;i++) arr[i] = val;
#define printint(i0, i1) printf("%d %d\n", i0, i1)

using namespace std;
typedef long long int ll;
const int inf = 1000000000;
const int mod = 1000000007;
const int nil = -1;
ll a, b, n;
ll ans;

int main() {
    scanf(" %lld %lld %lld", &a, &b, &n);
    if (n >= b) {
        ans = a * (b-1) / b;
    } else {
        ans = a * n / b;
    }

    printf("%lld\n", ans);
}

Measured memory_bytes: 3832
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
using namespace std;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// C - たくさんの数式 / Many Formulas
int main(){
    string S;
    cin >> S;
    int L = S.size() - 1;
    
    long long ans = 0;
    for(int i=0;i<1<<L;++i){
        int l = 0;
        long long tmp = 0;
        int r;
        for(r=0;r<L;++r){
            if((i & (1 << r)) != 0){
                string t = S.substr(l, r - l+1);
                long long num = stoll(t);
                ans += num;
                l = r+1;
            }
        }
        string t = S.substr(l, r - l+1);
        long long num = stoll(t);
        tmp += num;
        ans += num;
    }
    cout << ans << endl;
    return 0;
}




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

main() {
  int N; cin >> N;
  vector<int> A(N); for (int i = 0; i < N; i++) cin >> A[i];
  int even = 1; for (int i = 0; i < N; i++) even <<= (~A[i] & 1);
  cout << pow(3, N) - even << endl;
}


Measured memory_bytes: 640
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4
import sys
 
class LazySegmentTree:
    def __init__(self,n):
        n2=1<<n.bit_length()
        self.n=n2
        self.offset=n2
        self.data=[0]*(n2<<1)
        self.lazy=[0]*(n2<<1)
 
        update_base=[0]*n
        propagate_indices=[[] for _ in [0]*n]
        update_indices=[[] for _ in [0]*n]
        for i in range(n):
            j=i+n2+1
            b=(j>>(-j&j).bit_length()-1)-1
            update_base[i]=b
            while b>1:
                b>>=1
                propagate_indices[i].append(b)
        for i in range(n):
            k=i+1
            while k:
                update_indices[i].append(update_base[k-1])
                k-=-k&k
        self.propagate_indices=propagate_indices
        self.update_indices=update_indices
 
    def _push(self,k):
        for i in reversed(self.propagate_indices[k]):
            v=self.lazy[i]
            if v==0:
                continue
            j=i<<1
            self.data[j]+=v
            self.data[j+1]+=v
            self.lazy[j]+=v
            self.lazy[j+1]+=v
            self.lazy[i]=0
 
    def add(self,k,x):
        for i in self.update_indices[k]:
            self.data[i]+=x
            self.lazy[i]+=x
        for i in self.propagate_indices[k]:
            self.data[i]=max(self.data[i*2],self.data[i*2+1])+self.lazy[i]
 
    def get(self,k):
        self._push(k)
        ret=max(map(self.data.__getitem__, self.update_indices[k]))
        i=k+self.offset+1
        self.data[i]+=ret
        tmp=self.data[i]
        while i>1:
            parent=i>>1
            sibling=i^1
            tmp=self.data[parent]=max(tmp, self.data[sibling])+self.lazy[parent]
            i=parent
        return ret
 
 
 
 
n,m=map(int,input().split())
range_ls=[0 for _ in [0]*n]
range_rs=[[] for _ in [0]*n]
 
for line in sys.stdin.readlines():
    l,r,a=map(int, line.split())
    range_ls[l-1]+=a
    range_rs[r-1].append((l-1,a))
 
lst=LazySegmentTree(n)
ans=0
 
for i, (la,rs) in enumerate(zip(range_ls,range_rs)):
    if la!=0:
        lst.add(i,la)
    ans=max(ans,lst.get(i))
    for l,a in rs:
        lst.add(l,-a)
print(ans)
 

Measured memory_bytes: 154304
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

ll gcd(ll a, ll b) {
    while (b) {
        ll c = a % b;
        a = b;
        b = c;
    }
    return a;
}

ll po(ll a, ll b) {
    ll c = 1;
    while (b) {
        if (b % 2) c = c * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

ll f[2000006], g[2000006];

void comb() {
    f[0] = 1;
    for (int i = 1; i <= 2000000; i++) f[i] = f[i - 1] * i % mod;
    g[2000000] = 407182070;
    for (int i = 1999999; i >= 0; i--) g[i] = g[i + 1] * (i + 1) % mod;
}

int p[200005];

int root(int x) {return p[x] < 0 ? x : p[x] = root(p[x]);}

void mer(int x, int y) {
    if ((x = root(x)) == (y = root(y))) return;
    if (p[x] > p[y]) swap(x, y);
    p[x] += p[y];
    p[y] = x;
}

int main() {
    ios::sync_with_stdio(false);
    comb();
    int n;
    ll z = 0;
    cin >> n;
    for (int i = 1; i <= n / 3; i++) {
        z = (z + f[n - i * 3 + i - 1] * g[n - i * 3] % mod * g[i - 1]) % mod;
    }
    cout << z;
}


Measured memory_bytes: 34904
n = int(input())
p = list(map(int, input().split()))
sorted_p = sorted(p)
ng_count = 0

for i in range(n):
  if p[i] != sorted_p[i]:
    ng_count += 1

if ng_count == 0 or ng_count ==2:
  print('YES')
else:
  print('NO')

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

using namespace std;

map<long long, long long> primeFactorize(long long n) {
    map<long long, long long> ret;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ret.insert(make_pair(i, 0LL));
        }
        while (n % i == 0) {
            ret[i] += 1;
            n /= i;
        }
    }
    if (n > 1LL) {
        ret.insert(make_pair(n, 1LL));
    }
    return ret;
}

long long nCk(long long n, long long k) {
    map<long long, long long> pFac;
    for (long long i = n - k + 1; i <= n; ++i) {
        map<long long, long long> fac_i = primeFactorize(i);
        for (auto e : fac_i) {
            if (pFac.count(e.first) == 0) {
                pFac.insert(make_pair(e.first, 0LL));
            }
            pFac[e.first] += e.second;
        }
    }
    for (long long i = 2; i <= k; ++i) {
        map<long long, long long> fac_i = primeFactorize(i);
        for (auto e : fac_i) {
            pFac[e.first] -= e.second;
        }
    }
    long long ret = 1LL;
    for (auto e : pFac) {
        for (long long i = 0; i < e.second; ++i) {
            ret *= e.first;
        }
    }
    return ret;
}

void sameElements(long long N, long long A, long long B, long long v) {
    long long ret = 0LL;
    for (long long i = A; i <= B; ++i) {
        ret += nCk(N, i);
    }
    cout << (double)v << endl << ret << endl;
}

void Main() {
    long long N, A, B;
    cin >> N >> A >> B;
    vector<long long> v(N, 0LL);
    for (long long i = 0; i < N; ++i) {
        cin >> v[i];
    }

    sort(v.begin(), v.end(), greater<long long>());

    map<long long, long long> elements;
    long long minElement = v.front();
    long long numMinElements = 1LL;
    for (long long i = 0; i < A; ++i) {
        if (elements.count(v[i]) == 0) {
            elements.insert(make_pair(v[i], 0LL));
        }
        elements[v[i]] += 1;
        if (v[i] < minElement) {
            minElement = v[i];
            numMinElements = 1LL;
        }
        else {
            ++numMinElements;
        }
    }

    long long numMinElements_inV = 0LL;
    for (long long i = 0; i < N; ++i) {
        if (v[i] == minElement) {
            ++numMinElements_inV;
        }
    }
    if (minElement == v.front()) {
        sameElements(numMinElements_inV, A, min(B, numMinElements_inV), v.front());
        return;
    }


    double ans_avg = 0.0;
    for (auto e : elements) {
        ans_avg += e.first * e.second;
    }
    ans_avg /= (double)A;
    long long ans_nComb = nCk(numMinElements_inV, numMinElements);
    cout << ans_avg << endl << ans_nComb << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

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

    vector<int> A(S.size()+1,-1);
    vector<int> idx;

    if (S[0]=='<') {
        A[0]=0;
        idx.push_back(0);
    }
    if (S[S.size()-1]=='>') {
        A[S.size()]=0;
        idx.push_back(S.size());
    }

    for (int i=1; i<S.size(); i++) {
        if (S[i-1]=='>' && S[i]=='<') {
            A[i]=0;
            idx.push_back(i);
        }
    }

    rep(i,idx.size()) {
        int tmp = idx[i];
        while (idx[i]>0 && S[tmp-1]=='>') {
            A[tmp-1] =  max(A[tmp-1],A[tmp] + 1);
            tmp--;
        }
        tmp = idx[i];
        while (idx[i]<S.size() && S[tmp]=='<') {
            A[tmp+1] = max(A[tmp+1],A[tmp] + 1);
            tmp++;
        }
    }
    ll ans = 0;
    rep(i,S.size()+1) {
        ans += A[i];
    }
    cout << ans  << endl;
}


Measured memory_bytes: 3460
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include <iomanip>
#include<deque>
#include<stack>
#include<set>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
const int INF = 10000000;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const int DIV = 1000000007; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;



ll comb(ll n, ll m);


ll memo1[INF], memo2[INF], memo3[INF];

int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	//==================================

	

	int X, Y;
	cin >> X >> Y;

	if ((X + Y) % 3 != 0) {
		cout << 0;
		return 0;
	}
	else {

		ll moveX = X - (X + Y) / 3;
		ll moveY = Y - (X + Y) / 3;


		/*ll bunbo = 1;
		ll bunsi = 1;

		for (int i = 0; i < moveX; i++) {
			bunsi *= (moveX + moveY) - i;
			bunbo *= moveX -i;

			ll g = gcd(bunsi, bunbo);
			bunsi /= g;
			bunbo /= g;

			
		}


		ll ans = bunsi / bunbo;*/


		memo1[0] = 1;
		memo1[1] = 1;
		memo2[0] = 1;
		memo2[1] = 1;
		memo3[1] = 1;

		for (int i = 2; i < INF; i++) {
			memo1[i] = memo1[i - 1] * i % DIV;
			memo3[i] = DIV - memo3[DIV%i] * (DIV / i) % DIV;
			memo2[i] = memo2[i - 1] * memo3[i] % DIV;
		}

		ll ans = comb(moveX + moveY, min(moveX, moveY));

		ans %= DIV;
		cout << ans;
	}




}	



ll comb(ll n, ll m) {
	if (n < m) {
		return 0;
	}
	if (n < 0 || m < 0) {
		return 0;
	}
	return memo1[n] * (memo2[m] * memo2[n - m] % DIV) % DIV;


}

Measured memory_bytes: 234624
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long A = sc.nextLong();
    long B = sc.nextLong();
    
    long C = A+B;
    long ansA = A*(N/C);
    long ansB = N%C < A ? N%C : A; 
    System.out.println(ansA + ansB);
  }
}


Measured memory_bytes: 22736
//
//  main.cpp
//  20190808homework
//
//  Created by Priscilla Leang on 8/9/19.
//  Copyright © 2019 Priscilla Leang. All rights reserved.
//

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int a, b, c, d, f, m;
    bool b1 = false;
    
    //first problem --> sucess
    /*
    
    cin>> a >> b>> c>> d;
    f = 0;
    if ((c<=a && a<=d )){
        f++;
    }
    if (c<=b && b<=d){
        f++;
    }
    
    
    
    
    if (f == 1){
        cout << "Yes";
    }
    if (f != 1){
        cout << "No";
    }
    */
    
    //second problem
    
    
    /*
    cin>> a;
    int a1[a];
    for (int i = 0; i< a; i++){
        cin>> a1[i];
    }
    f = 0;
    b1 = false;
    m = 0;
    for (int i = 0; i< a; i++){
        
        if (a1[f] == 2){
            m++;
            b1 = true;
            break;
        }
        f = a1[f] -1;
        m++;
    }
    if (b1 == true){
        cout << m;
    }
    else if (b1 == false){
        cout << "-1";
    }
    */
    //third problem
    b1 = false;
    
    cin>> a >> b;
    char a2[a][a];
    char a3[b][b];
    for (int i= 0; i< a; i++){
        for (int j = 0; j< a; j++){
            cin>> a2[i][j];
        }
    }
    for (int i= 0; i< b; i++){
        for (int j = 0; j< b; j++){
            cin>> a3[i][j];
        }
    }
    
    for (int i= 0; i< a; i++){
        for (int j = 0; j< a; j++){  //for each of a2
            f = 0;
            if (a2[i][j] == a3[0][0]){
                for (int k= 0; k< b; k++){
                    for (int l = 0; l< b; l++){ //for each of a3
                        if (a3[k][l] == a2[i+k][j+l]){
                            f++;
                        }
                    }
                }
            }
            if (f == b*b){
                b1 = true;
            }
        }
    }
    
    if (b1 == true){
        cout << "Yes";
    }
    if (b1 == false){
        cout << "No";
    }
    
    
    
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;


int main(){
 long long N;
 cin>>N;
 long long a;
 long long max_num,second_num;
 max_num=0;
 second_num=0;
 long long num_list[N];
 for(int i=0;i<N;++i){
   cin>>a;
   num_list[i]=a;
   if(a>max_num){
     second_num=max_num;
     max_num=a;
   }
   else if(a>second_num){
     second_num=a;
   }
 }
 for(int i=0;i<N;++i){
   if(num_list[i]==max_num){
     cout<<second_num<<"\n";
   }
   else{
     cout<<max_num<<"\n";
   }
 }
return 0;
}

Measured memory_bytes: 3200
#input = raw_input
#import numpy as np

from heapq import heappush, heappop

N, M = map(int, input().split())

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)

Measured memory_bytes: 17604
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S =  input()

ans = 1
for i in range(1, N):
	if S[i-1] != S[i]:
		ans += 1

print(ans)


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

int main(){
    long N;
    long A;
    long B;
    long Q;
    long R;
    long Ans;
    cin>>N>>A>>B;
    Q=N/(A+B);
    R=N%(A+B);
    Ans = Q*A+min(A,R);
    cout<<Ans<<endl;
}

Measured memory_bytes: 256
n, x = [int(w) for w in input().split()]
a_li = [int(w) for w in input().split()]
a_li.sort()
 
ans = 0
for a in a_li:
    x -= a
    if x >= 0:
        ans += 1
    else:
        break
 
if x == 0:
    pass
else:
    if x > 0:
        ans = max(ans - 1, 0)
 
print(ans)

Measured memory_bytes: 9176
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>

using namespace std;

int main(){

	int n;
	
	while(cin >> n, n){
		
		vector<int> vc;
		
		for(int i=0; i<n; ++i){
			int a;
			cin >> a;
			vc.push_back(a);
		}
		
		sort(vc.begin(), vc.end());
		
		int sum = 0;
		
		for(int i=1; i<vc.size()-1; ++i){
			sum += vc[i];
		}
		
		cout << sum/(n-2) << endl;
	}
	
	return 0;
}
			

Measured memory_bytes: 1220
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 55;
const int maxm = 10005;
const int mod = 1000000007;

ll f[maxn][maxm];
bool in[maxn][maxm];

vector<int>ev[maxn];
vector<int>ea[maxn];
vector<int>eb[maxn];
int c[maxn],d[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n,m,s;
  cin>>n>>m>>s;
  for(int i=0;i<m;i++){
    int x,y,a,b;
    cin>>x>>y>>a>>b;
    ev[x].push_back(y);
    ea[x].push_back(a);
    eb[x].push_back(b);
    ev[y].push_back(x);
    ea[y].push_back(a);
    eb[y].push_back(b);
  }
  for(int i=1;i<=n;i++){
    cin>>c[i]>>d[i];
  }
  memset(f,-1, sizeof(f));
  f[1][min(s,maxm-1)] = 0;
  in[1][min(s,maxm-1)] = 1;
  queue<int>qx,qy;
  qx.push(1);
  qy.push(min(s,maxm-1));
  while(!qx.empty()){
    int x = qx.front();
    qx.pop();
    int y = qy.front();
    qy.pop();
    in[x][y] = 0;
    int tmp = min(maxm-1,y+c[x]);
    if(tmp>y&&(f[x][tmp]==-1||f[x][tmp]>f[x][y]+d[x])){
      f[x][tmp] =f[x][y]+d[x];
      if(!in[x][tmp]){
        in[x][tmp]=1;
        qx.push(x);
        qy.push(tmp);
      }
    }
    for(int i=0;i<ev[x].size();i++){
      int v = ev[x][i];
      int a = ea[x][i];
      int b = eb[x][i];
      if(y<a)continue;
      if(f[v][y-a]==-1||f[v][y-a]>f[x][y]+b){
        f[v][y-a]=f[x][y]+b;
        if(!in[v][y-a]){
          in[v][y-a]=1;
          qx.push(v);
          qy.push(y-a);
        }
      }
    }
  }
  for(int i=2;i<=n;i++){
    ll mi = 1LL<<60;
    for(int j=0;j<maxm;j++){
      if(f[i][j]!=-1){
        mi=min(mi, f[i][j]);
      }
    }
    cout<<mi<<endl;
  }
  return 0;
}

Measured memory_bytes: 9012
#include <stdio.h>
#include <string.h>
 
int main(void){
  int i,j,k,n,s;
  char ca[201],can[201];
 
  while(1){
    scanf("%s\n%d", ca, &n);
    if(!strcmp(ca, "-")) break;
    
    for(i=0;i<n;i++){
      scanf("%d", &s);
      for(j=s;ca[j]!='\0';j++)
        can[j-s] = ca[j];
      for(k=0;k<s;k++)
        can[j-s+k] = ca[k];
      
      for(j=0;ca[j]!='\0';j++)
        ca[j] = can[j];
    }
 
    printf("%s\n", ca);
  }
 
  return 0;
}


Measured memory_bytes: 2108
import numpy as np
import sys

N, M, Q = map(int, input().split())

I = sys.stdin.read().split()

L,R = np.array(I[:2*M], np.int32).reshape([2,-1], order='F')
p,q = np.array(I[2*M:], np.int32).reshape(2,-1, order='F')
d = np.zeros([N+1, N+1], np.int32)

d = np.zeros([1+N, 1+N], np.int32)
np.add.at(d, (N-L,R), 1)

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = d[N-p,q]

for a in ans:
	print(a)

Measured memory_bytes: 68936
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string str,ans,tmp,out="AIZUNYAN",x="AADINNUY";
int main(){
  cin>>str;
  ans=str;
  for(int i=0;i<(int)str.size()-7;i++){
    tmp=str.substr(i,8);
    sort(tmp.begin(),tmp.end());
    if(tmp==x)ans.replace(i,8,out);
  }
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

int main(){
    int x = 0, ans = 0;
    string s;
    cin >> s;
    for(auto c : s){
        if(c == 'S') ans++, x++;
        else{
            ans++;
            if(x) x--, ans -= 2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
package main

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

func main() {
	var N, max int
	fmt.Scan(&N)
	a := make([]int, N)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := range a {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
	}
	max = abs(a[0])
	for i := 0; i < N-1; i++ {
		max += abs(a[i+1] - a[i])
	}
	max += abs(a[len(a)-1])
	for i := 0; i < N; i++ {
		x := 0
		if i > 0 {
			x = a[i-1]
		}
		y := a[i]
		z := 0
		if i < N-1 {
			z = a[i+1]
		}
		r := max
		r -= abs(x - y)
		r -= abs(y - z)
		r += abs(x - z)
		fmt.Println(r)
	}
}
func abs(a int) int {
	return int(math.Abs(float64(a)))
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, K; cin >> n >> K;
    vi h(n); for(auto& e : h) cin >> e;
    sort(_all(h));

    int res = inf;
    rep(i, n - (K-1)){
        chmin(res, h[i + (K-1)] - h[i]);
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
typedef long long ll;
using namespace std;

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main() {
	string s; cin >> s;
	vector<int> v;
	for(int i = 0; i < s.size(); i++){
		if (s.size() <= (i+1)*2) break;
		if (s.substr(0,i+1) == s.substr(i+1,i+1)){
			v.push_back((i+1)*2);
		}
	}
	cout << *max_element(all(v)) << endl;
}

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

int main()
{
    string s;
    cin >> s;
    int ans = 0;
    if (s[0] == 'R')
    {
        ans += 1;
        if (s[1] == 'R')
        {
            ans += 1;
            if (s[2] == 'R')
                ans += 1;
        }
    }
    else if(s[1]=='R')
    {
        ans += 1;
        if (s[2] == 'R')
            ans += 1;
    }
    else if(s[2]=='R')
        ans += 1;
    cout << ans << endl;
}

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

typedef long long ll;
using namespace std;

const int MAX_N = 200000;

vector<int> G[MAX_N + 1];
bool used[MAX_N + 1];
ll counter[MAX_N + 1];
ll ans[MAX_N + 1];

//void dfs(int v) {
//  if(used[v]) return;
//  for(int i = 0; i < G[v].size(); i++) {
//    int u = G[v][i];
//    if(used[u]) return;
//    used[u] = true;
//    par[u] = v;
//    chil[v].push_back(u);
//    dfs(u);
//  }
//}

void dfs_ans(int v, ll val) {
  if(used[v]) return;
  used[v] = true;
  //cout << "coming to: " << v << " value is: " << val << "\n";
  ans[v] = val + counter[v];
  for(int i = 0; i < G[v].size(); i++) {
    int u = G[v][i];
    if(used[u]) continue;
    dfs_ans(u, ans[v]);
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  for(int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  fill(counter, counter + n + 1, 0);
  fill(ans, ans + n + 1, 0);
  fill(used, used + n + 1, false);
  for(int i = 0; i < q; i++) {
    int p;
    ll x;
    cin >> p >> x;
    counter[p] += x;
  }
  dfs_ans(1, 0LL);
  for(int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";

  return 0;
}



Measured memory_bytes: 25984
n,m=map(int,input().split())
l,r=map(int,input().split())
s=[l,r]
for i in range(1,m):
    l,r=map(int,input().split())
    if s[0]<l:
        s[0]=l
    if s[1]>r:
        s[1]=r

    if s[1]-s[0]<0:
        s=[0,-1]
        break
print(s[1]-s[0]+1)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int main()
{
  vector<ll>arr;
  vector<ll>cost;
  ll n,g,i,j,k;
  cin>>n>>k;
  for(i=0;i<n;i++)
  {
    cost.push_back(-1);
  }
  cost[0]=0;
  for(i=0;i<n;i++)
  {
    cin>>g;
    arr.push_back(g);
  }
  for(i=0;i<n-1;i++)
  {
    for(j=i+1;j<i+k+1;j++)
    {
        if(cost[j]!=-1)
        {cost[j]=min(cost[j],abs(arr[j]-arr[i])+cost[i]);}
        else if(cost[j]==-1)
        {
          cost[j]=abs(arr[j]-arr[i])+cost[i];
        }
        if(j==n-1)
        {
          break;
        }
    }
  }
  cout<<cost[n-1]<<endl;
}

Measured memory_bytes: 5512
#include <bits/stdc++.h>
#include <map> // pair
using namespace std;
int main(){
  string S;
  cin>>S;
  int zero,one,ans;
  zero=0;
  one=0;
  for(int i=0;i<S.size();i++){
    if(S.at(i)=='0')zero++;
    else one++;
  }
  if(one<zero)ans = one*2;
  else ans =zero*2;

  cout<<ans<<endl;
}


Measured memory_bytes: 512
using System;

namespace ABC139A
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            int a = 0;
            if (s.Substring(0, 1) == t.Substring(0, 1))
                a += 1;
            if (s.Substring(1, 1) == t.Substring(1, 1))
                a += 1;
            if (s.Substring(2, 1) == t.Substring(2, 1))
                a += 1;
            Console.WriteLine(a);
            Console.ReadKey();
            

            

        }
    }
}

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

class Program {
  static void Main() {
    var s = Console.ReadLine();
    var d = new Stack<int>();
    var p = new Stack<KeyValuePair<int, int>>();
    int a = 0;
    for (int i = 0; i < s.Length; i++) {
      if (s[i] == '\\') {
        d.Push(i);
      } else if (s[i] == '/' && d.Count > 0) {
        int b = d.Pop();
        int t = i - b;
        a += t;
        while (p.Count > 0 && b < p.Peek().Key) {
          t += p.Pop().Value;
        }
        p.Push(new KeyValuePair<int, int>(b, t));
      }
    }
    Console.WriteLine(a);
    Console.Write(p.Count);
    foreach (var item in p.Select(x => x.Value).Reverse()) {
      Console.Write(" " + item);
    }
    Console.WriteLine();
  }
}


Measured memory_bytes: 18668
#pragma comment(linker, "/STACK:10240000")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200020;

map<string, int> p;

struct tnode
{
    int num;
    string str;
}a[MAXN];

bool cmp(tnode a, tnode b)
{
    if (a.num == b.num)
    {
        return a.str < b.str;
    }
    return a.num > b.num;
}

int main()
{
    int n;
    scanf("%d", &n);
    string s;
    int k = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        if (!p[s])
        {
            k ++;
            p[s] = k;
            a[k].num = 1;
            a[k].str = s;
        }
        else
        {
            a[p[s]].num ++;
        }
    }
    sort(a + 1, a + k + 1, cmp);
    for (int i = 1; i <= k; i ++)
    {
        if (a[i].num == a[1].num)
        {
            cout<< a[i].str<<endl;
        }
        else
        {
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 28288