akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <set>
#include <map>
#include <list>
#include <cstdlib>
#include <queue>
#include <stack>
#include <bitset>

using namespace std;

#define MOD 1000000007
#define PI 3.1415926535897932
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define repi(i, n) for (int i = 0; i <= n; i++)
#define repie(i, j, n) for (int i = j; i <= n; i++)
#define all(x) x.begin(), x.end()
#define println() cout << endl
#define P pair<int, int>
#define fi first
#define se second

typedef long long ll;

long long modinv(long long a, long long m)
{
    long long b = m, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}

void solve1()
{
    int n, k; cin >> n >> k;
    vector<int> h(n); rep(i, n) cin >> h[i];

    int dp[n]; dp[0] = 0;
    for(int i = 1; i < n; i++) {
        int minval = dp[i-1] + abs(h[i]-h[i-1]);
        for(int j = 1; j <= k && j - i <= 0; j++ ) {
            minval = min(minval, dp[i - j] + abs(h[i] - h[i - j]));
        }
        dp[i] = minval;
    }

    cout << dp[n-1] << endl;
}

int main()
{
    solve1();
}


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

using namespace std;

#define forn(i,n) for ( int i=0 ; i < n ; i++ )
#define all(a) (a).begin(), (a).end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int >
#define pii pair<int, int>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SQ(a) (a)*(a)
#define ll long long
#define lli long long int
#define ull unsigned long long
#define endl '\n'
#define Pi(a) printf("%d\n",a);
#define debug2(a,b) printf("%d\t%d\n",a,b);
#define debug1(a) printf("%d\n",a);
#define Si(a) scanf("%d",&a);
#define mod 1000000007
#define w(n) while(n--)


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	//code
	int n;
	cin >> n;
	int arr[n];
	forn(i,n) cin >> arr[i];
	sort(arr,arr+n);
	cout << arr[n-1]-arr[0] << endl;
}

Measured memory_bytes: 256
A, B, C, K = map(int, input().split())

total = 0
if K <= A:
    print(K)
else:
    total += A
    K = K - A
    if K <= B:
        print(total)
    else:
        K = K - B
        if K <= C:
            total -= K
            print(total)
        else:
            total -= C
            print(total)

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

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

typedef pair< long long, long long > P;
typedef pair< long long, P > PP;
typedef pair< P, P > PPP;

const double DINF = 5e14, eps = 1e-10;
const long long MOD = 1e9 + 7, INF = 5e18;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

int n, x[110], y[110], h[110], hh, cx, cy;
PP p[110];

int main() {
	cin>> n;
	for (int i = 0;i < n;i++) {
		cin >> p[i].sc.fr >> p[i].sc.sc >> p[i].fr;
	}
	sort(p, p + n);
	for (int i = 0;i <= 100;i++) {
		for (int j = 0;j <= 100;j++) {
			for (int k = 0;k < n;k++) {
				hh = p[k].fr + abs(p[k].sc.fr - i) + abs(p[k].sc.sc - j);
				bool fl = 0;
				for (int l = 0;l < n;l++) {
					if (p[l].fr == max(hh - abs(p[l].sc.fr - i) - abs(p[l].sc.sc - j),0LL)) {}
					else fl = 1;
				}
				if (!fl) {
					cout << i << ' ' << j << ' ' << hh << endl;
					return 0;
				}
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
N = int(input())
D,X = map(int,input().split(" "))
list = []
for i in range(N):
    list.append(int(input()))
#print(list)
ans = 0
for i in range(N):
    for j in range(D):
        #print(j * list[i]+1)
        if j * list[i]+1 <= D:
            ans += 1
print(ans+X)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  string s;
  cin >> s;
  int n = s.length();
  ll ans = 0;
  for(int i = n - 2; i >= 0; i -= 2){
    string left = s.substr(0, i / 2);
    string right = s.substr(i/2, i / 2);
    if(left == right) {
      string ans = left + right;
      cout << ans.length() << endl;
      return 0;
    }
  }
}


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

using namespace std;
using ll=long long;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int a,b,c,d;cin>>a>>b>>c>>d;
  while(1){
    c-=b;
    //cout<<"a"<<a<<endl;
    if(c<=0){
      cout<<"Yes"<<endl;
      break;
    }
    a-=d;
    //cout<<"c"<<c<<endl;
    if(a<=0){
      cout<<"No"<<endl;
      break;
    }
  }
}


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

using ll = long long;
using vi = vector<int>;
using vi2 = vector<vector<int>>;
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl;

#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl;

#define sz(x) (int)(x).size()
#define HOGE cout << "hoge" << endl;

template<typename T>inline istream& operator>>(istream&i,vector<T>&v)
{REP(j,sz(v))i>>v[j];return i;}

const int INF = 1e9;


    
int main(){
    int W, H, N;
    cin >> W >> H >> N;
    int max1=0, min2=W, max3=0, min4=H;
    int x, y, a;
    REP(i,N){
        cin >> x >> y >> a;
        if(a==1) max1 = max(max1,x);
        if(a==2) min2 = min(min2,x);
        if(a==3) max3 = max(max3,y);
        if(a==4) min4 = min(min4,y);
    }
    int ans = (min2-max1)*(min4-max3);
    if(max1<min2&&max3<min4) cout << ans << endl;
    else cout << 0 << endl;
}


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

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define ull unsigned long long
#define ld long double

#define mod 1000000007
#define EULER 2.7182818284
#define INF 1000000000

#define pb push_back
#define ins insert
#define IT iterator
#define PQ priority_queue
#define    nl           "\n"
#define fi first
#define se second
#define maxe max_element
#define mine min_element
#define er erase
#define lb lower_bound
#define ub upper_bound

#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mpi map<int,int>
#define mpl map<ll,ll>
#define umpi unordered_map<int,int>
#define umpl unordered_map<ll,ll>
#define si set<int>
#define sl set<ll>
#define msi multi_set<int>
#define msl multi_set<ll>

#define mem(v,i) memset(v,i,sizeof(v)) // v is array. To set all elements to 0 or -1 only. mem(arr,0);


#define repab(i,a,b) for(int i=(a);i<=(b);i++)
#define reprab(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i,a,b) for(ll i=(a);i<=(b);i++)
#define rep(i,n) for(int i=(0);i<(n);i++)
#define repr(i,n) for(int i=(n);i>=0;i--)
#define bs bitset
#define bpc(a) __builtin_popcount(a)
#define tc int t;cin>>t;while(t--)


int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

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

ll mypow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}

ll n,k;
vll a(200005);
bool isvalid(ll mid){
    int cnt=0;
    if(mid==0)
    return false;
    for(int i=0;i<n;i++){
            if(a[i]<=mid){
                continue;
            }
            else{
                cnt+=a[i]/mid;
            }
        }
        return cnt<=k;
}
ll bns(ll start,ll end){
    while(start<=end){
        ll mid=(start+end)/2;
        if(isvalid(mid)){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
        
    }
    return start;
}
int main()
{   
    
    fast
    cin>>n>>k;
    rep(i,n){
        cin>>a[i];
    }
    ll p=*max_element(all(a));
    if(k==0){
        cout<<p<<nl;
        return 0;
    }
    cout<<bns(0,p)<<nl;
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int>d(n);
  int count=0;
  int memo=1000;
  
  for(int i=0; i<n; i++){
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  reverse(d.begin(),d.end());
  
  for(int i=0; i<n; i++){
    if(d[i]<memo){
      count++;
      memo=d[i];
    }
  }
  cout << count << endl;
  
  
  
}

Measured memory_bytes: 256
N = gets.to_i

# 1! ～ (N-1)! までを計算する
$kai = [1]
(N-2).times do |i|
  $kai.unshift($kai[0] * (i+2))
end
#p $kai

A = gets.split(' ').map(&:to_i)
B = gets.split(' ').map(&:to_i)

def n_banme(x)
  indexes = []
  N.times do |i|
    indexes << i+1
  end
  #print 'indexes = '
  #p indexes
  #p x
  ans = 0
  
  (N-1).times do |i|
    # puts 'i = '+ i.to_s
    # 順番未確定の数値のなかで何番目に大きいか
    idx = indexes.index(x[i])
    # puts 'idx = ' + idx.to_s
    ans += idx * $kai[i]
    # puts 'ans = '+ ans.to_s
    indexes.delete_at(idx)
  end
  ans += 1
  # puts 'final_ans = '+ans.to_s
  return ans
end

a = n_banme(A)
b = n_banme(B)
# puts a,b
puts (a-b).abs

Measured memory_bytes: 1788
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	N := nextInt()

	m := map[rune]int{'M': 0, 'A': 1, 'R': 2, 'C': 3, 'H': 4}
	v := make([]int, 5)
	for i := 0; i < N; i++ {
		s := next()
		k, ok := m[rune(s[0])]
		if ok {
			v[k]++
		}
	}
	
	sum := 0
	for i := 0; i < 3; i++ {
		for j := i+1; j < 4; j++ {
			for k := j+1; k < 5; k++ {
				sum += v[i] * v[j] * v[k]
			}
		}
	}

	fmt.Println(sum)
}

Measured memory_bytes: 1536
main(a,b,c){for(a=b=0,getchar();(c=getchar())!='0';)if(c-'\n')c=='A'?a++:b++;else{printf("%d %d\n",a>b?a+1:a,a<b?b+1:b),a=b=0;if(getchar()=='0')break;}return 0;}

Measured memory_bytes: 524
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	std::string s;
	std::cin >> s;
	int n=s.length();
	std::vector<std::vector<int> > where(26,std::vector<int>());
	rep(i,n) where[s[i]-'a'].emplace_back(i);
	int min = n-1;
	for(auto v:where) {
		if(v.empty()) continue;
		std::vector<int> d(n,0);
		std::vector<int> p(n,0);
		if(v.size()==n) {
			print(0);
			return 0;
		}
		for(int i:v) d[i]=1;
		for(int i=1;i<n;i++) {
			int count = 0;
			for(int j=0;j<n-i;j++) {
				if(d[j]||d[j+1]) {
					p[j]=1;
					count++;
				} else p[j]=0;
			}
			if(count==n-i) {
				min = std::min(min, i);
				break;
			}
			std::swap(d,p);
		}
	}
	print(min);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
		cerr << (*i) << " ";
    }
    cerr << "\n";
}
const ll MOD = 1e9 + 7;
ll pw(ll a, ll b) {
	ll ans = 1;
	while (b) {
		while (!(b & 1))
			b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD;
		--b;
	}
	return ans;
}
const int MX = 222000;

ll fc[MX];
ll bfc[MX];


void init() {
	fc[0] = 1;
	bfc[0] = 1;
	for (int i = 1; i < MX; ++i)
		fc[i] = (fc[i - 1] * i) % MOD, bfc[i] = pw(fc[i], MOD - 2);
}

ll cnk(int n, int k) {
	if (k > n)
		return 0;
	return fc[n] * bfc[k] % MOD * bfc[n - k] % MOD;
}

int h, w, a, b;
int main() {
	cin >> h >> w >> a >> b;
	init();
	ll ans = 0;
	for (int i = b + 1; i <= w; ++i) {
		ans = (ans + cnk(i - 1 + h - a - 1, i - 1) * cnk(a - 1 + w - i, a - 1)) % MOD;
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 3712
a, b, c, x, y =map(int,input().split())
if a + b <= 2*c :
  print(a*x +b*y)
else:
  if x <= y :
    print(min(2*x*c+(y-x)*b,2*y*c))
  else :
    print(min(2*y*c+(x-y)*a,2*x*c))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct Kruskal{

  struct UnionFind{
    int n;
    vector<int> r,p;
    UnionFind(){}
    UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
    int find(int x){
      return (x==p[x]?x:p[x]=find(p[x]));
    }
    bool same(int x,int y){
      return find(x)==find(y);
    }
    void unite(int x,int y){
      x=find(x);y=find(y);
      if(x==y) return;
      if(r[x]<r[y]) swap(x,y);
      r[x]+=r[y];
      p[y]=x;
    }
  };
  
  struct edge{
    int from,to,cost;
    edge(){}
    edge(int from,int to,int cost):from(from),to(to),cost(cost){}
    bool operator<(const edge& e) const{
      return cost<e.cost;
    }
  };

  int n;
  vector<edge> edges;

  Kruskal(){}
  Kruskal(int sz):n(sz){}
  
  void add_edge(int u,int v,int c){
    edges.push_back(edge(u,v,c));
  }

  void input(int m,int offset=0){
    int a,b,c;
    for(int i=0;i<m;i++){
      cin>>a>>b>>c;
      add_edge(a+offset,b+offset,c);
    }
  }
  
  int build(){
    sort(edges.begin(),edges.end());
    UnionFind uf(n+1);
    int res=0;
    for(int i=0;i<(int)edges.size();i++){
      edge e=edges[i];
      if(!uf.same(e.from,e.to)){
	res+=e.cost;
	uf.unite(e.from,e.to);
      }
    }
    return res;
  }
};
//END CUT HERE
int main(){
  int V,E;
  cin>>V>>E;
  Kruskal kruskal(V);
  kruskal.input(E);
  cout<<kruskal.build()<<endl;
  return 0;
}

/*
verified on 2017/04/26
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp
*/

Measured memory_bytes: 4484
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <tuple>
#include <functional>
#include <cstring>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i < n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i < n; i++)

typedef long long ll;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::pair<ll, ll> pll;

using namespace std;


int main() 
{
    int n;
    int ans = 0, cnt = 0;
    cin >> n;
    v_int s;

    irep(i, n) {
        int tmp;
        cin >> tmp;
        ans += tmp;
        if(tmp % 10 == 0) { 
            cnt++; 
        } else {
            s.push_back(tmp);
        }
    }

    if(cnt == n) { 
        cout << 0 << endl; 
        return 0; 
    }

    if(ans % 10 == 0) {
        sort(s.begin(), s.end());
        irep(i, s.size()) {
            ans -= s[i];
            if(ans % 10 != 0) {
                break;
            }
        }
    }

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


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 9 * (long long int)pow(10, 13);

long long int N;
bool flag;
long long int box;
long long int ans;

int main() {
	cin >> N;
	for (long long int i = (long long int)sqrt(N); i >= 1; i--) {
		if (!(N%i)) {
			box = max(N / i, i);
			break;
		}
	}
	while (box) {
		box /= 10;
		ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int d = sc.nextInt();
			int t = sc.nextInt();
			int s = sc.nextInt();

			if (d <= t * s) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
}


Measured memory_bytes: 35660
#include <cstdio>

int main(){
  int n;

  while(scanf("%d" ,&n) ,n){
    int p,d1,d2;
    int ans = 0,num;

    while(n--){
      scanf("%d %d %d" ,&p ,&d1 ,&d2);
      d1 += d2;
      if(ans < d1){
	ans = d1;
	num = p;
      }
    }
    printf("%d %d\n" ,num ,ans);
  }

  return 0;
}

Measured memory_bytes: 1028
N, K, Q = map(int,input().split())

A_list = [int(input()) for i in range(Q)]
Point_list = [K-Q for i in range(N)]

for j in range(Q):
    Point_list[A_list[j]-1] += 1

for j in range(N):
    if Point_list[j] <= 0:
        print("No")

    else:
        print("Yes")


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

int main() {
  int N,k;
  cin >> N;
  
  k=1;
  int j;
  j=0;
  while(j<9){
    if(N/10!=0){
      k++;
      j++;
    }
    else {
      break;
    }  
  }
  
  int f,M;
  f=0;
  M=N;
  for (int i=0;i<k;i++){
    int a=M%10;
    f+=a;
    M=(M-a)/10;
  }
  
  if(N%f==0){
    cout << "Yes" << endl;
  }
  else{
   cout << "No" << endl; 
  }
}

Measured memory_bytes: 256
n,m = map(int,input().split())

H = list(map(int,input().split()))
G = [1]*n
for _ in range(m):
    a,b = map(int,input().split())
    if H[a-1] <= H[b-1]:
        G[a-1] = 0
    if H[a-1] >= H[b-1]:
        G[b-1] = 0

print(sum(G))

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

using namespace std;

int main()
{
   int h,n,sum=0;
   cin>>h>>n;
   int arr[n];
   for(int i=0;i<n;i++)
   {
       cin>>arr[i];
       sum=sum+arr[i];
   }
   if(sum>=h)
   {
       cout<<"Yes"<<endl;
   }
   else
   {
       cout<<"No"<<endl;
   }


    return 0;
}


Measured memory_bytes: 768
solve :: Int -> Bool
solve n = not . null $ [(n4, n7)| n4 <- [0..(n `div` 4)], n7 <- [0..(n `div` 7)], n4 * 4 + n7 * 7 == n]

main :: IO ()
main = do
  n <- readLn
  putStrLn $ if solve n then "Yes" else "No"

Measured memory_bytes: 508
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 1000005;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

char ss[MAXN];
int n, s[MAXN], dsum;

void Mul9() {
	int jw = 0;
	for (int i = 1; i <= n; ++i) {
		s[i] = s[i] * 9 + jw;
		jw = s[i] / 10;
		s[i] %= 10;
	}
	if (jw) s[++n] = jw;
	for (int i = 1; i <= n; ++i) {
		dsum += s[i];
	}
}

void Add9() {
	int jw = 9;
	for (int i = 1; i <= n; ++i) {
		dsum -= s[i];
		s[i] += jw;
		jw = s[i] / 10;
		s[i] %= 10;
		dsum += s[i];
		if (!jw) return;
	}
	if (jw) s[++n] = jw;
	dsum += jw;
}

void solve() {
	scanf("%s", ss + 1);
	n = strlen(ss + 1);
	reverse(ss + 1, ss + n + 1);
	for (int i = 1; i <= n; ++i) {
		s[i] = ss[i] - '0';
	}
	Mul9();
	for (int ans = 1; ; ++ans) {
		Add9();
		if (ans * 9 >= dsum) {
			printf("%d\n", ans);
			break;
		}
	}
}

int main() {
	solve();
	return 0;
}



Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
int calDigits(long long n)
{
	if(n==0)
		return 0;
	else
		return 1+calDigits(n/10);
}
int main() {
	long long n;
	cin >> n;
	int ans=calDigits(n);
	for(int i=sqrt(n);i>0;i--)
		if(n%i==0&&max(calDigits(i),calDigits(n/i))<ans)
			ans=max(calDigits(i),calDigits(n/i));
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ul;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef pair<bool, bool> pbb;
#define fi first
#define se second
#define pb push_back
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
#define enum(i, j, k) for(int i = j; i <= k; i ++) // loop structure abbreviations are here
#define open(i, j, k) for(int i = j; i < k; i ++)
#define dec(i, j, k) for(int i = j; i >= k; i --)
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define maxx 1e6+7

int main() {
	off;
	int a,b,c;
	cin >> a >> b >> c;
	if(a*b<c)
	{
		cout << a*b << endl;
	}
	else
	{
		cout << c << endl;
	}

  	return 0;
}

Measured memory_bytes: 896
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j,k;
  int a[5140];
  a[0]=2;
  k=1;
  for(i=3;i<50000;i+=2){
    for(j=3;j<(int)sqrt(i)+1;j+=2){
      if(i%j==0)
	break;
    }
    if(j>=(int)sqrt(i)+1){
      a[k]=i;
      k++;
    }
  }
  a[k]=50001;
  int m,p,q;
  while(cin>>m>>p>>q&&m+p+q){
    int mx=0,my=0;
    for(i=0;a[i]*a[i]<=m;i++){
      for(j=i;(double)a[i]/a[j]>=(double)p/q&&a[i]*a[j]<=m;j++){
	if(mx*my<a[i]*a[j]){
	  mx=a[i];
	  my=a[j];
	}
      }
    }
    cout<<mx<<" "<<my<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
dic = {}

N = int(input())

S = input()

for i in range(N):

    if S[i] not in dic:
        dic[S[i]] = 1

    else:
        dic[S[i]] += 1
        
ans = 1

for i in dic:

    ans *= dic[i] + 1

print ((ans-1) % (10**9 + 7) )

Measured memory_bytes: 39280
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include<iomanip>
using namespace std;

int mod = 1e9 + 7;

int N;

int main() {
    cin >> N;
    vector<int> cnt(N + 1);
    cnt[0] = 3;
    int a;
    long long ans = 1;
    for (int i = 0; i < N; i++) {
        cin >> a;
        cnt[a + 1]++;
        ans = ans * cnt[a] % mod;
        cnt[a]--;
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

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

    vector<int> x(n), y(n), h(n);
    for(int i=0;i<n;i++)cin >> x.at(i) >> y.at(i) >> h.at(i);

    int ax, ay, ah;
    for(int i=0;i<n;i++){
        if(h.at(i)!=0){
            ax = x.at(i);
            ay = y.at(i);
            ah = h.at(i);
            break;
        }
    }

    int px, py, ph;
    bool flag;
    flag = false;
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            ph = ah + abs(i-ax) + abs(j-ay);
            for(int k=0;k<n;k++){
                if(h.at(k)!=0){
                    if(ph != h.at(k)+abs(i-x.at(k))+abs(j-y.at(k)))break;
                }
                else{
                    if(ph > h.at(k)+abs(i-x.at(k))+abs(j-y.at(k)))break;
                }
                if(k == n-1){
                    flag = true;
                    px = i;
                    py = j;
                }
            }

            if(flag)break;
        }
        if(flag)break;
    }

    cout << px << " " << py << " " << ph << endl;

    return 0;
}

Measured memory_bytes: 256
if __name__ == '__main__':
    n = int(input())
    a = [int(s) for s in input().split()]
    b = [0] * n
    for i in range(n, 0, -1):
        b[i - 1] = a[i - 1]
        j = i + i
        while j <= n:
            b[i - 1] ^= b[j - 1]
            j += i
    m = b.count(1)
    print(m)
    if m:
        print(*(i + 1 for i, x in enumerate(b) if x))


Measured memory_bytes: 13112
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;
struct edge { int to, cost; };
typedef std::pair<int, int> P;

int N, M, a[212345], b[212345];
int d[212345];
std::vector<edge>G[212345];

void dijkstra(int s)
{
	std::priority_queue<P, std::vector<P>, std::greater<P>>que;
	std::fill(d, d + N + 1, 212345);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		LL v = p.second;
		if (d[v] < p.first) { continue; }
		rep(i, G[v].size())
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	in >> N >> M;
	rep(i, M) { in >> a[i] >> b[i]; }

	rep(i, M)
	{
		G[a[i]].push_back({ b[i],1 });
		G[b[i]].push_back({ a[i],1 });
	}
	dijkstra(1);

	if (d[N] == 2) { out << "POSSIBLE" << std::endl; }
	else { out << "IMPOSSIBLE" << std::endl; }
	return 0;
}

Measured memory_bytes: 17000
a, b = map(int, input().split())
num = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            c = 10000 * i + 1000 * j + k * 100 + 10 * j + i
            if a <= c <= b:
                num += 1

print(num)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k; cin >> n >> k;
  int ans = 0;
  for(int i = 0; i < n; i++){
    int x; cin >> x;
    ans +=min(2 * x, 2 * abs(k - x));
  }
  cout << ans;
}
  

Measured memory_bytes: 3536
#include <stdio.h>

int main(){
    int N, i, kisu = 0, cnt = 0;
    long long int num[10000];

    scanf("%d\n", &N);
    for(i = 0; i < N; i++){
        scanf("%lld ", &num[i]);

    }
    for(i = 0; i < N; i++){
        while(num[i]%2 == 0){
            num[i] = num[i]/2;
            cnt++;
        }
    }
    printf("%d\n", cnt);

    return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/

#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 INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int N, M, k, p[10], result = 0;
bool s[10][10];

bool checkLL(bool on[10])
{
  REP(i, M)
  {
    int cnt = 0;
    REP(j, N)
    {
      if (on[j] && s[i][j])
        cnt++;
    }
    if (cnt % 2 != p[i])
      return false;
  }
  return true;
}

int main()
{

  cin >> N >> M;

  REP(i, M)
  {
    int t;
    cin >> k;
    REP(j, k)
    {
      cin >> t;
      s[i][t - 1] = true;
    }
  }
  REP(i, M)
  {
    cin >> p[i];
  }

  REP(bit, 1 << N)
  {
    bool on[10];
    REP(i, N)
    {
      on[i] = bit & (1 << i);
    }
    if (checkLL(on))
      result++;
  }

  cout << result << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main(){
    int R[MAX],n;

    cin >> n;
    for(int i = 0; i < n; i++) cin >> R[i];

    int maxv = -2000000000;
    int minv = R[0];

    for(int i = 1; i < n; i++) {
        maxv = max(maxv,R[i]-minv);
        minv = min(minv,R[i]);
    }

    cout << maxv << endl;

    return 0;
}


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

int main() {
    int N;
  	int L[101];
  	int sum = 0;
  	int max = 0;
  	bool flg = false;
    cin >> N;
  	for(int i = 0; i < N; i++){
      cin >> L[i];
      if(max < L[i]){
        max = L[i];
      }
    }
  	
  	for(int i = 0; i < N; i++){
      if(L[i] == max && flg == false){
  		flg = true;
        continue;
      }
      sum += L[i];
    }
	if(sum > max){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int main(){
    ll a,b,c,k;cin>>a>>b>>c>>k;
    ll ans;
    if(k<=a){
        ans=k;
    }
    if(a<k&&k<=a+b){
        ans=a;
    }
    if(a+b<k&&k<=a+b+c) {
        ans=a-(k-(a+b));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()

#define pb push_back
#define mp make_pair

#define F first
#define S second

using ll = long long;
using namespace std;

void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }

const int mod = 1000000007;
const int INF = 1e+9;

int main() {
    int n; cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int ans = 0;
    for (int i = 1; i <= 100; i++) {
        int cnt = 0;
        bool f = false;
        for (int j = 0; j < n; j++) {
            if (f) {
                if (h[j] < i) {
                    f = false;
                }
            } else {
                if (h[j] >= i) {
                    f = true;
                    cnt++;
                }
            }
        }
        ans += cnt;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	if(x-r>=0 && x+r<=w && y-r>=0 && y+r<=h){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 2096
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, K;
	cin >> N >> K;
	VI A(N);
	REP(i, N)cin >> A[i];
	SORT(A);

	int ans;
	int L = -1e+18, R = 1e+18, M;

	while (L <= R) {
		M = (L + R) / 2;

		int a;
		int cnt = 0;//M以下の数
		REP(i, N - 1) {
			a = A[i];

			if (a == 0) {
				if (M >= 0)cnt += (N - i - 1);
			}
			else if (a < 0) {
				int LL = i + 1, RR = N - 1, MM;
				while (LL <= RR) {
					MM = (LL + RR) / 2;

					if (A[MM] * A[i] <= M) {
						RR = MM - 1;
					}
					else {
						LL = MM + 1;
					}
				}
				if (A[i] * A[MM] <= M)cnt += (N - MM);
				else cnt += (N - MM - 1);
			}
			else {
				int LL = i + 1, RR = N - 1, MM;
				while (LL <= RR) {
					MM = (LL + RR) / 2;

					if (A[MM] * A[i] > M) {
						RR = MM - 1;
					}
					else {
						LL = MM + 1;
					}
				}
				if (A[i] * A[MM] <= M)cnt += (MM - i);
				else cnt += (MM - i - 1);
			}
		}
		if (cnt >= K) {
			R = M - 1;
			/*if (cnt == K) {
				cout << M << endl;
				return 0;
			}*/
			ans = M;
		}
		else {
			L = M + 1;
		}

		//cout << M << " " << cnt << endl;
		
	}
	cout << ans << endl;



	return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
void generate(vector<vector<int> > &comb, int n, vector<int> &curr)
{
	if(curr.size() == n)
	{
		comb.push_back(curr);
		return;
	}
	curr.push_back(1);
	generate(comb, n, curr);
	curr.pop_back();
	curr.push_back(0);
	generate(comb, n, curr);
	curr.pop_back();
	return;
}

int correct(vector<int> &v, vector<vector<pair<int,int> > > &comb)
{
	for(int i = 0; i<(int)v.size(); i++)
	{
		if(v[i] == 1)
		{
			for(int j = 0; j<(int)comb[i].size(); j++)
			{
				pair<int,int> temp = comb[i][j];
				if(temp.second == 1)
				{
					if(v[temp.first-1] == 0)
					return 0;
				}
				else
				{
					if(v[temp.first-1] == 1)
					return 0;
				}
			}
		}
	}
	return 1;
}
int main()
{
	int n, i, j;
	cin>>n;
	unsigned long long int a[n];
	
	for(i = 0; i<n; i++)
	cin>>a[i];

	unsigned long long int mem[n+1][64];
	memset(mem, 0, sizeof(mem));

	for(i = 0; i<n; i++)
	{
		for(j = 0; j<64; j++)
		{
			unsigned long long num = (1LL)<<j;
			mem[i+1][j] = mem[i][j] + ((num&a[i]) > 0);
		}
	}
	long long ans = 0;
	for(i = 0; i<n; i++)
	{
		for(j = 0; j<62; j++)
		{
			unsigned long long now = (1LL)<<j, game = now;
			if((now&a[i]) == 0)
			{
				ans = (ans + ((mem[n][j]-mem[i+1][j])*((game)%mod)%mod))%mod;
			}
			else
			{
				ans = (ans + ((n-i-1 - (mem[n][j] - mem[i+1][j]))*((game)%mod)%mod))%mod;
			}
		}
	}
	cout<<ans<<endl;
}


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

using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
//#define int ll

const int md = 1000000007;
const int INF = 1<<30;

int main(){
    int n,m; cin >> n >> m;
    vi a(m);  cin >> a;

    int sum = 0;
    rep(i,m){
        sum += a[i];
    }

    cout << max(-1,n-sum) << endl;
}


Measured memory_bytes: 3632
S=input()
if S=="SUN":
  print(7)
elif S=="MON":
  print(6)
elif S=="TUE":
  print(5)
elif S=="WED":
  print(4)
elif S=="THU":
  print(3)
elif S=="FRI":
  print(2)
elif S=="SAT":
  print(1)

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
	
char input[25];
	
scanf("%s",input);
	for(int i = 0; input[i] != '\0'; i++){
		if(input[i] >= 'a' && input[i] <= 'z'){
			printf("%c", input[i]);
		}
		else{
			printf(" ");
		}
	}
    return 0;
}


Measured memory_bytes: 1620
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	int N;
	scanf("%d", &N);

	//vector<char> S;
	//for (int i = 0; i < N; i++)
	//{
	//	char tmp;
	//	scanf("%c", &tmp);
	//	S.push_back(tmp);
	//}
	string S;
	cin >> S;

	vector<char> A;
	int depth = 0;
	for (int i = 0; i < N; i++)
	{
		if (S[i] == '(')
			depth++;
		else if (S[i] == ')' && depth == 0)
			A.push_back('(');
		else if (S[i] == ')')
			depth--;
	}
	for (int i = 0; i < N; i++)
	{
		A.push_back(S[i]);
	}

	if (depth >= 1)
	{
		for (int i = 0; i < depth; i++)
		{
			A.push_back(')');
		}
	}

	int sizeA = A.size();
	for (int i = 0; i < sizeA; i++)
	{
		printf("%c", A[i]);
	}
	printf("\n");
}

Measured memory_bytes: 256
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>
#include <unordered_map>
 
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(ll i = 0; i<n; i++)
#define rep_s(i, start, n) for(ll i= start;  i<n; i++)
#define rep_down(i, n) for(ll i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(ll i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()
#define print(ans) cout << ans << endl;
 
string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";
/*
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;
 
}
*/
/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];
 
void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}
 
ll keta_num(ll num){
  ll total = 0;
  while(num){
    num /= 10;
    total++;
  }
}
 
ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}
 
bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}
 
ll gcd(ll a, ll b){
  ll tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
 
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
 
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
 
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
 
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
 
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
 
int main(void){
  ll N, M, A, B, C, D, E, F, K,L, W, H, P, Q, R, X, Y;
  ll ans;
  string S, T;
  cin >> N;
  vector<ll> d;
  rep(i, N){
    cin>>D;
    d.push_back(D);
  }
  sort(ALL(d));
  cout << d[N/2]-d[(N/2)-1] << endl;
  
  
 
}

Measured memory_bytes: 1400
import java.util.Scanner;
public class Main{
	static int n;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		n =sc.nextInt();
		int[] num = new int[101];
		for(int i=2; i<=n; i++){
			int tmp = i;
			for(int j=2; j<=i;j++){
				while(tmp%j==0){
					num[j]++;
					tmp/=j;
				}
			}
		}
		int ans=0;
		ans+=count(74,num);
		ans+=count(24,num)*(count(2,num)-1);
		ans+=count(14,num)*(count(4,num)-1);
		ans+=count(4,num)*(count(4,num)-1)*(count(2,num)-2)/2;
		System.out.println(ans);
	}
	public static int count(int a,int[] num){
		int count=0;
		for(int i=2; i<=n; i++){
			if(num[i]>=a){
				count++;
			}
		}
		return count;
	}
}


Measured memory_bytes: 21844
//https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_9_B
//p239.cpp

#include<iostream>
using namespace std;
#define MAX 2000000

int H, A[MAX+1];

void maxHeapify(int i){
	int l, r, largest;
	l = 2 * i;
	r = 2 * i + 1;

	//左の子、自分、右の子で値が最大のノードを選ぶ
	if ( l <= H && A[l] > A[i] ) largest = l;
	else largest = i;
	if ( r <= H && A[r] > A[largest] ) largest = r;

	if ( largest != i ){
		swap(A[i], A[largest]);
		maxHeapify(largest);
	}
}

int main(){
	cin >> H;

	for ( int i = 1; i <= H; i++ ) cin >> A[i];

	for ( int i = H / 2; i >= 1; i-- ) maxHeapify(i);

	for ( int i = 1; i <= H; i++ ){
		cout << " " << A[i];
	}
	cout << endl;

	return 0;
}




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

typedef long long ll;

ll mod_pow(ll x, ll n){ //べき乗
    ll ans=1;
    x%=2019;
    while(n!=0){
        if(n&1) ans=ans*x%2019;
        x=x*x%2019;
        n=n>>1;
    }
    return ans%2019;
}

int main(){
    string s; cin >> s;
    reverse(s.begin(),s.end());
    ll ans=0;
    ll tmp=0;
    map<ll,ll> ma;
    ma[0]++;
    for(int i=0;i<s.size();i++){
        ll d=s[i]-'0';
        tmp=(d*mod_pow(10,i)+tmp)%2019;
        tmp%=2019;
        //cout << tmp << endl;
        ans+=ma[tmp];
        ma[tmp]++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3696
package main

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

func main() {
	M := ReadInt()
	fmt.Println(48 - M)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


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

using namespace std;
using llong = long long;
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(){
	int N, M, X;
	vector<int> A;

	cin >> N >> M >> X;
	A.resize(N+1);
	for(int i = 1; i <= M; i++){
		int in;
		cin >> in;
		A[in]++;
	}

	vector<int> rui(N+1);
	rui[0] = A[0];
	for(int i = 1; i <= N; i++){
		rui[i] = rui[i-1] + A[i];
	}

	cout << min(rui[X], rui[N] - rui[X]) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(int i=1,i##_len=(n); i<=i##_len; ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define srep(i,s,t) for(int i=(s);i<(t);++i)
#define rng(obj) (obj).begin(), (obj).end()
#define maxs(x,y) (x=max((x),(y)))
#define mins(x,y) (x=min((x),(y)))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x=max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T>>
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vp = vector<P>;
template <class T> inline istream& operator>>(istream&i,v(T)&v)
{ rep(j,sz(v))i>>v[j];return i;}
template <class T> string join(const v(T)&v)
{ stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template <class T> inline ostream& operator<<(ostream&o,const v(T)&v)
{ if(sz(v))o<<join(v); return o;}
template <class T1,class T2> inline istream& operator>>(istream&i ,pair<T1,T2>&v)
{ return i>>v.fi>>v.se;}
template <class T1,class T2> inline ostream& operator<<(ostream&o ,pair<T1,T2>&v)
{ return o<<v.fi<<","<<v.se;}
template <class T> inline ll suma(const v(T)& a) 
{ ll res(0); for(auto&& x:a) res += x; return res;}
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double eps = 1e-10;
const int MX = 200005;
//----------------------------------------------------------------

#define fileio ifstream fio; if(argc>=2){fio.open(argv[1]); std::cin.rdbuf(fio.rdbuf());}
#define fastio ios_base::sync_with_stdio(false);
#define MOD 1000000007

//----------------------------------------------------------------
template <class T>
map< T, int > prime_factor(T n) {
    map< T, int > ret;
    for(T i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}
ll fac(ll n){
  ll ret=1;
  while(n>1){
    ret*=n;
    if(ret>MOD)ret%=MOD;
    n--;
  }
  return ret;
}


void Main(){
  int n;
  cin>>n;
  vl a(n);
  deque<ll> b;
  cin>>a;
  int now=1,next=0;
  if(n%2==1){swap(now,next);}
  rep(i,n){
    if(now) b.pb(a[i]);
    else b.push_front(a[i]);
    swap(now,next);
  }
  for(auto i:b){
    cout<<i<<" ";
  }
} int main(int argc,char* argv[]){ 
    fastio; fileio; Main();}

Measured memory_bytes: 5376
N,K=map(int,input().split())
S=input()+'E'

# Initial values
ans=1
l=0
r=0
edge=[]

# 立っているグループのカウント
# 最初の文字が0なら1
if S[l]=='0':
    count=1
else:
    count=0    

# ｒがNまでループ
while(r < N-1):
    r+=1
    #　もし1=>0の境目だと、countを追加
    if ( S[r-1]=='1') & (S[r]=='0'):
        count+=1

    #　countがKを超すとlのループに入る(Break)
    while(count>K):
        l+=1
        # lを更新したとき0=>1の境目だと、l~r間の0グループが減るので、countを減らす
        if (S[l-1]=='0') & (S[l]=='1'):
            count-=1
        #lがrを追い越さないように
        if l==r:
            r+=1
        #print(r,l,count,ans)

    #何事もなく 進んだ場合は答えの更新
    ans=max(ans,r-l+1)
    #print(r,l,count,ans) 

print(ans)

Measured memory_bytes: 3316
package main

import (
	"fmt"
	"strings"
)

func main() {
	var rs string

	fmt.Scanf("%s", &rs)
	if strings.Contains(rs, "RRR") {
		fmt.Println(3)
	} else if strings.Contains(rs, "RR") {
		fmt.Println(2)
	} else if strings.Contains(rs, "R") {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}


Measured memory_bytes: 1836
#include<bits/stdc++.h>
using namespace std;
long long dp[109][100009];

int main(){
  int n,s;
  int w[109],v[109];
  cin>>n>>s;
  for(int i=0;i<n;i++){
    cin>>w[i]>>v[i];
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<=s;j++){
      if(j-w[i]<0){
	dp[i+1][j]=dp[i][j];
      }
      else{
	dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }
    }
  }
  cout<<dp[n][s]<<endl;
  return(0);
}


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


int main(){
    long long int n;
    cin>>n;
    long long int A;
    cin>>A;
    long long int B;
    cin>>B;
	cout<< ((n/(A+B))*A + min(A , n%(A+B)));
    cout<<endl;                         		 


    return 0;

}

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

const int N = 1e5 + 5;
typedef long long LL;

int n, ok;
LL a[N], L;

int main() {
	cin>>n>>L;
	for(int i = 1; i <= n; i++) {
		cin>>a[i];
		if(i == 1) continue;
		if(a[i] + a[i - 1] >= L) ok = i - 1;
	} 
	if(!ok) cout<<"Impossible"<<endl;
	else {
		cout<<"Possible"<<endl;
		for(int i = 1; i < ok; i++)
			cout<<i<<endl;
		for(int i = n - 1; i > ok; i--)
			cout<<i<<endl;
		cout<<ok<<endl;
	}
	return 0;
}

Measured memory_bytes: 4420