akhauriyash/Code-Regression huggingface dataset:
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
import std.concurrency;
void times(alias fun)(int n) {
    foreach(i; 0..n) fun();
}
auto rep(alias fun, T = typeof(fun()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = fun();
    return res;
}

void main() {
    int N, M;
    readf("%d %d\n", &N, &M);

    bool[][] m = new bool[][](N, N);
    foreach(_; 0..M) {
        int a, b;
        readf("%d %d\n", &a, &b);
        a--; b--;
        m[a][b] = true;
        m[b][a] = true;
    }

    N.iota.permutations.filter!(
        a => a.front == 0
    ).map!(
        a => zip(a[0..$-1], a[1..$])
    ).filter!(
        a => a.all!(
            b => m[b[0]][b[1]]
        )
    ).count.writeln;
}

// ----------------------------------------------

// fold was added in D 2.071.0
static if (__VERSION__ < 2071) {
    template fold(fun...) if (fun.length >= 1) {
        auto fold(R, S...)(R r, S seed) {
            static if (S.length < 2) {
                return reduce!fun(seed, r);
            } else {
                return reduce!fun(tuple(seed), r);
            }
        }
    }
}

// minElement/maxElement was added in D 2.072.0
static if (__VERSION__ < 2072) {
    auto minElement(alias map, Range)(Range r)
    if (isInputRange!Range && !isInfinite!Range)
    {
        alias mapFun = unaryFun!map;
        auto element = r.front;
        auto minimum = mapFun(element);
        r.popFront;
        foreach(a; r) {
            auto b = mapFun(a);
            if (b < minimum) {
                element = a;
                minimum = b;
            }
        }
        return element;
    }
    auto maxElement(alias map, Range)(Range r)
    if (isInputRange!Range && !isInfinite!Range)
    {
        alias mapFun = unaryFun!map;
        auto element = r.front;
        auto maximum = mapFun(element);
        r.popFront;
        foreach(a; r) {
            auto b = mapFun(a);
            if (b > maximum) {
                element = a;
                maximum = b;
            }
        }
        return element;
    }
}


Measured memory_bytes: 256
n, k = map(int, input().split())
h = list(map(int, input().split()))
# h = [i for i in range(n)]
h = sorted(h)
# print(h[:-1], h)
if k > len(h):
    print(0)
else:
    if k != 0:
        del h[-k:]
    print(sum(h))

Measured memory_bytes: 26180
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<map>
using namespace std;

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

	string prev;
	cin >> prev;

	map<string, bool> mp;
	mp[prev] = true;

	string W;
	for(int i=1; i<N; i++){
		cin >> W;

		bool ok = (prev.back() == W.front());
		ok &= !mp[W];

		if(ok == true){
			mp[W] = true;
			prev = W;
		}
		else{
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 256
N,M=list(map(int,input().split()))
A=[]
for i in range(N):
    A.append(list(map(int,input().split())))
# print(A)
A.sort()
#print(A)
res,count=0,0
for i in range(N):
    res+=A[i][0]*A[i][1]
    count+=A[i][1]
    if(count==M):
        break 
    if(count>M):
        res-=A[i][0]*A[i][1]
        count-=A[i][1]
        for j in range(1,A[i][1]+1):
            res+=A[i][0]
            count+=1
            if(count==M):
                print(res)
                exit()

print(res)
exit()       


Measured memory_bytes: 27756
#include <iostream>
using namespace std;
int main(){
    int h,n,sum=0;
    cin >> h >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(h <= sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int a,b,c,d,l,r,n;
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	scanf("%d",&d);
	l=a+b;
	r=c+d;
	if(l>r){
		printf("Left\n");
	}
	else if(l<r){
		printf("Right\n");
	}
	else{
		printf("Balanced\n");
	}
	
	return 0;
}


Measured memory_bytes: 128
// +build ignore
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func gcd(x, y int) int {
	if x%y != 0 {
		return gcd(y, x%y)
	}
	return y
}

const D int = 60
const MAX_N int = 200005

var to [D][MAX_N]int

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	N := sc.nextInt()
	K := sc.nextInt()
	for i := 0; i < N; i++ {
		to[0][i] = sc.nextInt() - 1
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			to[i][j] = to[i-1][to[i-1][j]]
		}
	}

	p := 0
	for i := D; i >= 0; i-- {
		if K&(1<<i) != 0 {
			p = to[i][p]
		}
	}

	fmt.Println(p + 1)

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


Measured memory_bytes: 96908
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,c;
	cin>>a>>b>>c;
	if (c-a-b>0&&4*a*b<(c-a-b)*(c-a-b))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
#define fileinput(s) freopen(s,"r",stdin)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
typedef long long ll;

const ll mod = 1000000007;

vector<int> fact;
vector<int> inv;

void printArr(vector<int> arr,int n){
	cout<<"\n------------------------------------\n";

	for(int i=0;i<n;i++) cout<<arr[i]<<" ";
	
	cout<<"\n------------------------------------\n";
}

ll modpow(ll a, ll b){
    ll c = 1;
 
    while (b){
        if (b & 1)
            c = 1LL * c * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
 
    return c;
}

ll ncr(ll n, ll k){
    return 1LL * fact[n] * inv[k] % mod * inv[n - k] % mod;
}

void init(){
	int maxn = 2000000 + 10;
	
	fact.assign(maxn,1);
	inv.assign(maxn,1);
	
	for (int i = 1; i < maxn ; ++i)
        fact[i] = 1LL * fact[i-1] * i % mod;


    inv[maxn-1] = modpow(fact[maxn-1], mod-2);
    
    for (int i = maxn-2; i >= 0; --i)
        inv[i] = 1LL * inv[i + 1] * (i+1) % mod;


    //printArr(fact,10);


}
int main(){
	optimiza_io
	
	int r1,c1,r2,c2;
	cin>>r1>>c1>>r2>>c2;

	init();
	
	ll ans1=0;

	ll p1 = ncr(r2+c2+2,c2+1);
	ll p2 = ncr(r1+c2+1,c2+1);
	ll p3 = ncr(r2+c1+1,c1);
	ll p4 = ncr(c1+r1,c1);

	ans1 = p1+p4-p3-p2;

	while(ans1<=0) ans1+=mod;

	ans1=(ans1%mod);

	cout<<ans1<<endl;
	return 0;

}
	


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

int main(){
  int N, A;
  cin >> N >> A;
  int card[N];
  rep(i,N){
    cin >> card[i];
  }
  int B[A];
  int C[A];
  rep(i,A){
    cin >> B[i] >> C[i];
  }

  priority_queue <pair<int,int>> q;
  rep(i,N){
    q.push(make_pair(card[i],1));
  }
  rep(i,A){
    q.push(make_pair(C[i],B[i]));
  }

  ll ans = 0;

  rep(i,N){
    auto p = q.top();
    q.pop();
    ans += p.first;
    if(p.second>1){
      p.second--;
      q.push(p);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3572
//Never stop chasing!-MD.SOURAV.

// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

#include <bits/stdc++.h>

#define yes            cout<<"YES"<<endl
#define no             cout<<"NO"<<endl
#define sz(x)          x.size()
#define ll             long long int
#define li             long int
#define start          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#define test           int t;cin>>t;while(t--)
#define f(i, a, n)     for(int i=a; i<n;i++)
#define gcd(a,b)       __gcd(a,b)
#define lcd(a,b)       (a*b)/gcd(a,b)
#define pb             push_back
#define mp(x,y)        make_pair(x,y)
#define rsrt(v)        sort(v.begin(),v.end(),greater<int>())
#define srt(v)         sort(v.begin(),v.end())
#define basrt(a,n)     sort(a,a+n,greater<int>())
#define asrt(a,n)      sort(a,a+n)
#define fact(n)        ll x=1;for(ll i=1;i<=n;i++){x=(x*i);}
#define F              first
#define S              second
#define deb(x)         cout << #x << ": " << x << endl;
#define enter(v,n)     for(ll i=0;i<n;i++){ll x;cin>>x;v.pb(x);}
#define INF 	       1000000007
#define unique(v)      v.erase(unique(v.begin(),v.end()),v.end())

using namespace std;

double pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664 ;
typedef vector<ll> vll ;
typedef vector<int> vi ;
typedef vector<pair<ll,ll>> vpll;
typedef vector<pair<int,int>> vpii;
typedef map<ll,ll> mllll;
typedef map<char,ll> mchll;
typedef map<string,ll>msll;

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v)
{
    os << '{';
    for (const auto &x : v) os << " " << x;
        return os << '}';
}
int a[100005];
int dp[100005];

int fouzia(int ans,int n1)
{
	  if(ans==(n1-1))  return 0;
	  if(ans>=n1) return INT_MAX;

	  if(dp[ans]!=-1)
	  {
	  	//deb(dp[ans]);
	  	return dp[ans];
	  }
	  int left=abs(a[ans]-a[ans+1])+fouzia(ans+1,n1);
	  int right=INT_MAX;
	  if(ans+2<n1)
	  {
	  	right=abs(a[ans]-a[ans+2])+fouzia(ans+2,n1);
	  }
     // deb(left);
      //deb(right);
	  return dp[ans]=min(left,right);

}

void solve()
{

     int n;
     cin>>n;
     memset(dp,-1,sizeof(dp));
     for(int i=0;i<n;i++)
	 {
	 	cin>>a[i];
	 }
	 cout << fouzia(0,n);

}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    ll test_case=1;
    //cin>>test_case ;
    while(test_case--)
	{
		 solve();
	}

	return 0;
}


Measured memory_bytes: 10680
import java.util.*;
import java.util.stream.Collectors;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
      
        int n = sc.nextInt();
        int otoshidama = sc.nextInt();

        int x = -1;
        int y = -1;
        int z = -1;

        boolean isFinish = false;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (n - i - j >= 0 && i + j + (n - i - j) == n) {
                    if (i * 10000 + j * 5000 + (n - i - j) * 1000 == otoshidama) {
                        x = i;
                        y = j;
                        z = n - i - j;
                        isFinish = true;
                        break;
                    } else if(n - i - j < 0) {
                        break;
                    }
                }
            }
            if (isFinish) {
                break;

            }
        }
        System.out.println(x + " " + y + " " + z);
    }
}

Measured memory_bytes: 21972
#include<stdio.h>

int A[1000000],n;

int Binary(int key)
{
  int Left=0;
  int Right=n;
  int Middle;

  while(Left<Right)
    {
      Middle=(Left+Right)/2;
      if(key==A[Middle]) return 1;
      if(key<A[Middle]) Right=Middle;
      else if(key>A[Middle]) Left=Middle+1;
    }
  return 0;
}

int main()
{
  int i,q,key,cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
    }

  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&key);
      if(Binary(key)==1) cnt++;
    }
  printf("%d\n",cnt);

  return 0;
}

Measured memory_bytes: 988
n,m,l = list(map(int, input().split()))

a = [[0 for j in range(m)] for i in range(n)]
b = [[0 for k in range(l)] for j in range(m)]
c = [[0 for k in range(l)] for i in range(n)]

for i in range(n):
    lst = list(map(int, input().split()))
    for j in range(m):
        a[i][j] = lst[j]

for j in range(m):
    lst = list(map(int, input().split()))
    for k in range(l):
        b[j][k] = lst[k]

for i in range(n):
    for k in range(l):
        for j in range(m):
            c[i][k] += a[i][j] * b[j][k]

for i in c:
    print(*i)



Measured memory_bytes: 7064
(* O(n) *)
let kInf = 1 lsl 60
let n = Scanf.scanf " %d" @@ (+) 0
let hs = Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let dp = Array.make n kInf
let cost i j = abs @@ hs.(i) - hs.(j)
let _ =
  dp.(0) <- 0;
  for i = 0 to n - 2 do
    dp.(i + 1) <- min dp.(i + 1) @@ dp.(i) + cost i (i + 1);
    if i < n - 2 then dp.(i + 2) <- min dp.(i + 2) @@ dp.(i) + cost i (i + 2) done;
  Printf.printf "%d\n" dp.(n - 1)

Measured memory_bytes: 5888
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
//void IO(){
//	#ifndef ONLINE_JUDGE
//	    freopen("input.txt", "r", stdin);
//	    freopen("output.txt", "w", stdout);
//	#endif
//}
// end of Template

char c[4][4];
int main(){
	//IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin>>c[i][j];
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(i==j)cout<<c[i][j];
        }
    }
    cout<<newl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
int N;
vector<pint> v;

int main()
{
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> v[i].first >> v[i].second;
    }

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

    double result = 0;
    double iter = 0;
    do
    {
        for (int i = 0; i < N - 1; ++i)
        {
            int a = ind[i];
            int b = ind[i + 1];
            result += sqrt((v[a].first - v[b].first) * (v[a].first - v[b].first) + (v[a].second - v[b].second) * (v[a].second - v[b].second));
        }
        ++iter;
    } while (next_permutation(ind.begin(), ind.end()));
    result /= iter;
    printf("%.13f", result);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b, c; cin >> a >> b >> c;
  cout << min({a, b, c}) << " " << max({a, b, c}) << endl;
}


Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	return (a %= p) >= 0 ? a : a + p;
}

int fact(int N){
	static vector<int> fac(1, 1);
	for(int i = fac.size(); i <= N; i++){
		fac.push_back(MOD(i * fac[i - 1]));
	}
	return fac[N];
}

int fact_inv(int N){
	static vector<int> inv(2, 1), fac_inv(2, 1);
	for(int i = inv.size(); i <= N; i++){
		inv.push_back(MOD(-(p / i) * inv[p % i]));
		fac_inv.push_back(MOD(inv[i] * fac_inv[i - 1]));
	}
	return fac_inv[N];
}

int comb(int N, int k){
	if(k < 0 || N < k || N < 0) return 0;
	else return MOD(fact(N) * MOD(fact_inv(N - k) * fact_inv(k)));
}

int solve(int N, int M, int K){
	int d, ans = 0;
	for(d = 1; d < N; d++){
		ans = MOD(ans + MOD(MOD(d * (N - d)) * MOD(M * M)) * comb(N * M - 2, K - 2));
	}
	return ans;
}

signed main(){
	int N, M, K, i;
	scanf("%lld%lld%lld", &N, &M, &K);
	printf("%lld\n", MOD(solve(N, M, K) + solve(M, N, K)));
	return 0;
}

Measured memory_bytes: 6768
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
	
	int a, b, a_sum, b_sum;
	
	a_sum = 0;
	b_sum = 0;
	
	for(int i = 0; i < 4; i++){
		cin >> a;
		a_sum += a;
	}
	
	for(int i = 0; i < 4; i++){
		cin >> b;
		b_sum += b;
	}
	
	if(a_sum > b_sum){
		printf("%d\n", a_sum);
	}else{
		printf("%d\n", b_sum);
	}
	
	return 0;
}

Measured memory_bytes: 1148
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //b
  int h, n;
  cin >> h >> n;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    tot += a;
  }
  cout << (tot >= h ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter

n, m = map(int, input().split())
dic = Counter(map(int, input().split()))
lis = sorted(dic.items(), key=lambda x: x[1], reverse=True)

res = 0
for i, x in enumerate(lis):
    if i < m:
        continue
    else:
       res += x[1]
print(res)


Measured memory_bytes: 41500
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;

int a,b,c;

int main()
{
	IO
	cin>>a>>b>>c;
	
	int mod = a%b;
	
	for(int i = 0; i < b; ++i){
		if(((i*mod)%b)==c){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int main(){
  double A, B, T;
  cin >> A;
  cin >> B;
  cin >> T;
  T = T + 0.5;

  int c = floor(T/A);
  cout << c * B << endl;

}
 


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
  #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
int digsum(int n){
	if(n==0)return 0;
	return n%10+digsum(n/10);
}
void solve(){
  int n;
  cin>>n;
  cout<<(n%digsum(n)==0?"Yes":"No")<<endl;
}
int32_t main(){
   IOS;
   solve();
   //debug();
  #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
  #endif	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
//g++ -std==c++14
//setprecision(10)
int main(){
    int n;
    cin >> n;
    int p[n];
    for(int i = 0; i < n; i++)
        cin >> p[i];
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(i == p[i] - 1){
            cnt ++;
            swap(p[i], p[i + 1]);
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

int main(void){
        char s[1001],check[12],targ[11],bg;
        int len,i,j,count=0,bre=0;
        scanf("%s",targ);
        scanf("%c",&bg);
        len = strlen(targ);
        while(1){
                scanf("%[^\n]",s);
                scanf("%c",&bg);
                i=0;
                while(s[i]){
                        if(s[i]=='E'){
                                for(j=0;j<11;j++)
                                        check[j]=s[i+j];
                                check[11]='\0';
                                if(strcmp(check,"END_OF_TEXT")==0){
                                        bre=1;
                                        break;
                                }
                        }
                        if(s[i]>='A'&&s[i]<='Z')
                                s[i]+=('a'-'A');
                        i++;
                }
                if(bre==1)
                        break;
                i=0;
                while(s[i]){
                        if((i!=0&&s[i-1]==' ')||i==0){
                                if(s[i]==targ[0]&&(s[i+len]==' '||s[i+len]=='\0')){
                                        for(j=0;j<len;j++){
                                                check[j]=s[i+j];
                                                if(s[i+j]=='\0')
                                                        break;
                                        }
                                        check[len]='\0';
                                        if(strcmp(check,targ)==0)
                                                count++;
                                }
                        }
                        i++;
                }

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

Measured memory_bytes: 552
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll c = 0 , x = 0 , ans = 1000000000000000000 , a[n];
    for( int i = 0 ; i < n ; i++ ) {
        cin >> a[i];
        c += a[i];
    }
    for( int i = 0 ; i < n ; i++ ) {
        x += a[i];
        if( i + 1 < n ) ans = min( ans , abs( c - 2 * x ) );
    }
    cout << ans << endl;
}



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

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

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

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

    string s;
    cin >> s;

    int64_t m = s.size();

    vector a(1, 0L);
    int64_t t = 0;
    for (auto c : s) {
        if (c == '0') {
            a.push_back(t);
        } else {
            ++t;
        }
    }
    a.push_back(t);

    int64_t k;
    cin >> k;
    k = min(k, a.back());

    int64_t n = a.size();

    constexpr auto M = 998244353L;

    vector dp(vector(k + 1, vector(a.back() + 1, 0L)));
    int64_t mk = 0;
    dp[0][0] = 1;
    for (auto i : irange(0L, n - 1)) {
        for (auto j : irange(mk, -1L, -1L)) {
            auto r = min(k - j, a[i + 1] - a[i]);
            for (auto c : irange(0L, a.back() - a[i + 1] + 1)) {
                for (auto b : irange(c + 1, c + r + 1)) {
                    auto w = j + b - c;
                    dp[w][c] += dp[j][b];
                    if (dp[w][c] >= M) {
                        dp[w][c] -= M;
                    }
                }
            }

            for (auto c : irange(1L, a.back() - a[i + 1] + 1)) {
                dp[j][c] += dp[j][c - 1];
                if (dp[j][c] >= M) {
                    dp[j][c] -= M;
                }
            }
        }
        mk = min(k, mk + a[i + 1] - a[i]);
    }

    int64_t ans = 0;
    for (auto i : irange(0L, mk + 1)) {
        ans += dp[i][0];
        if (ans >= M) {
            ans -= M;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3856
#include <stdio.h>
#include <string.h>
struct data{
	char card[101];
	int pnt;
};
typedef struct data Data;
int main(){
	char word[201];
	Data taro,hana;
	int i,n,k,j,idx,len;
	taro.pnt=0;
	hana.pnt=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s",taro.card);
		scanf("%s",hana.card);
		if(strcmp(taro.card,hana.card)>0){
			taro.pnt+=3;
		}else if(strcmp(taro.card,hana.card)<0){
			hana.pnt+=3;
		}else{
			taro.pnt++;
			hana.pnt++;
		}
	}
	printf("%d %d\n",taro.pnt,hana.pnt);
	return 0;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
#define ll long long
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
using namespace std;
const int MAXN=1e5+9;
map<ll,int> mp;
const ll INF=2e18;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	if(s=="ABC")
	{
		cout<<"ARC"<<endl;
		return 0;
	}
	cout<<"ABC"<<endl;
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e5+5;
const int mod=1e9+7;
int pow(int,int,int);
int fac[N],inv[N];
int a[N];
int f[N],dp[N];
int C(int n,int m){
    return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

void init();
void work();
int ca=1;
int main(){
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//    init();
//    int T;cin>>T;
//    while(T--)
    work();
    return 0;
}
void work(){
    fac[0]=inv[0]=1;
    for(int i=1;i<N;i++) fac[i]=1LL*fac[i-1]*i%mod;
    inv[N-1]=pow(fac[N-1],mod-2,mod);
    for(int i=N-2;i;i--) inv[i]=1LL*(i+1)*inv[i+1]%mod;

    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=(f[i-1]+a[i])%mod;
    }
    dp[n]=f[n];
    for(int i=n-1;i;i--){
        dp[i]=(1LL*dp[i+1]+f[i]-f[n-i])%mod;
        if(dp[i]<0) dp[i]+=mod;
    }
    int ans=1LL*fac[n]*f[n]%mod;
    for(int i=1;i+2<=n;i++){
        dp[i]=(1LL*dp[i]-f[i]-(1LL*f[n]-f[n-i]))%mod;
        if(dp[i]<0) dp[i]+=mod;
        ans=(ans+2LL*dp[i]*fac[i]%mod*fac[n-i-2]%mod*C(n,i+2)%mod)%mod;
    }
    for(int i=1;i<n;i++){
        int t=(1LL*f[i]+f[n]-f[n-i])%mod;
        ans=(ans+1LL*t*fac[i]%mod*fac[n-i-1]%mod*C(n,i+1)%mod)%mod;
    }
    ans=(ans+mod)%mod;
    cout<<ans<<'\n';
}
int pow(int a,int p,int m){
    int re=1;
    for(;p;p>>=1){
        if(p&1) re=1LL*re*a%m;
        a=1LL*a*a%m;
    }
    return re;
}


Measured memory_bytes: 5608
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <iomanip>

#define SIZE 101
#define INF 100000000

using namespace std;


typedef pair<int, int> P;




int main()
{
	int n;
	pair<int, P> p;
	vector<pair<int, P>> v;

	for (int i = 1; i <= 150; i++) {
		for (int j = 1; j < i; j++) {
			v.push_back(pair<int, P>(i * i + j * j, P(j, i)));
		}
	}

	sort(v.begin(), v.end());

	while (true) {
		int h, w, rh, rw;
		int d; 
		cin >> h >> w;
		if (h == 0 && w == 0) break;
		d = h * h + w * w;

		pair<int, P> q(d, P(h, w));

		for (int i = 0; i < v.size(); i++) {
			if (v[i] > q) {
				//if(v[i].first == d) i += 1;
				cout << v[i].second.first << " " << v[i].second.second << endl;
				break;
			}
			// cerr << v[i].second.first << " " << v[i].second.second << endl;
		}
	}
	return (0);
}

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


using namespace std;


#define ll long long
#define mk make_pair
#define pb push_back
#define ff first
#define sc second
#define all(x) x.begin(), x.end()
#define sz(x) (x).size()


ll sum(int n);

void go(){
	int n;cin>>n;
	int s=0;
	for(int i=1;i<=n;i+=2){
		s++;
	}
	double ans = (double) s / n;
	cout << ans;
}
int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   go();

   return 0;
}

ll sum(int n){                
   if(n == 0){
      return n;
   }else{
      return sum(n/10) + n%10;
   }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
struct Seg{
	int a,b;
	friend bool operator < (Seg a,Seg b){
		if(a.a!=b.a)
			return a.a<b.a;
		return a.b<b.b;
	}
};
multiset<Seg> lr,rl,LR,RL;
int n;
ll ans,ANS;
bool flag;
int main(){
	ios::sync_with_stdio(false);
	int l,r,cur=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l>>r;
		lr.insert((Seg){l,r});
		rl.insert((Seg){r,l});
	}
	LR=lr;
	RL=rl;
	flag=1;
	while(!lr.empty()){
		l=(*rl.begin()).a;
		r=(*--lr.end()).a;
		if(r-cur>=cur-l||flag){
			flag=0;
			ans+=max(0,r-cur);
			if(r-cur>0)
				cur=r;
			l=(*--lr.end()).a;
			r=(*--lr.end()).b;
		}
		else{
			ans+=max(0,cur-l);
			if(cur-l>0)
				cur=l;
			l=(*rl.begin()).b;
			r=(*rl.begin()).a;
		}
		lr.erase(lr.find((Seg){l,r}));
		rl.erase(rl.find((Seg){r,l}));
	}
	ANS=ans+(cur>0?cur:-cur);
	lr=LR;
	rl=RL;
	flag=1;cur=0;ans=0;
	while(!lr.empty()){
		l=(*rl.begin()).a;
		r=(*--lr.end()).a;
		if(r-cur>=cur-l&&!flag){
			ans+=max(0,r-cur);
			if(r-cur>0)
				cur=r;
			l=(*--lr.end()).a;
			r=(*--lr.end()).b;
		}
		else{
			flag=0;
			ans+=max(0,cur-l);
			if(cur-l>0)
				cur=l;
			l=(*rl.begin()).b;
			r=(*rl.begin()).a;
		}
		lr.erase(lr.find((Seg){l,r}));
		rl.erase(rl.find((Seg){r,l}));
	}
	ANS=max(ANS,ans+(cur>0?cur:-cur));
	cout<<ANS;
	return 0;
}

Measured memory_bytes: 22404
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
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;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pll> ab(n);
    for (int i = 0; i < n; ++i) {
        cin >> ab[i].first >> ab[i].second;
    }
    sort(ab.begin(), ab.end());
    ll ret = 0;
    int abidx = 0;
    priority_queue<ll> pq;
    for (int i = 0; i <= m; ++i) {
        while (abidx < n && ab[abidx].first <= i) {
            pq.push(ab[abidx].second);
            abidx++;
        }
        if (pq.size() != 0) {
            ret += pq.top();
            pq.pop();
        }
    }
    cout << ret << "\n";
    return 0;
}

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

int main() {
    int X; cin >> X;
    int now = 0;
    for (int i = 1; i < 1e9; i++){
        now += i;
        if(now >= X){
            cout << i << endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint x, k;
    cin >> x >> k;
    vector<lint> r(k + 1, 0);
    for (int i = 1; i <= k; ++i) {
        cin >> r[i];
    }
    lint q;
    cin >> q;
    vector<lint> t(q), a(q);
    for (int i = 0; i < q; ++i) {
        cin >> t[i] >> a[i];
    }
    int ridx  = 1;
    lint mini = 0;
    lint maxi = x;
    lint lo   = 0;
    lint hi   = x;
    bool flip = false;
    lint sum  = 0;
    for (int i = 0; i < q; ++i) {
        while (ridx <= k && r[ridx] < t[i]) {
            if (!flip) {
                lint decl = r[ridx] - r[ridx - 1];
                sum -= decl;
                mini -= decl;
                maxi -= decl;
                if (mini < 0) {
                    lo += -mini;
                }
                mini = max(mini, 0LL);
                maxi = max(maxi, 0LL);
            } else {
                lint incl = r[ridx] - r[ridx - 1];
                sum += incl;
                mini += incl;
                maxi += incl;
                if (maxi > x) {
                    hi -= maxi - x;
                }
                mini = min(x, mini);
                maxi = min(x, maxi);
            }
            ridx++;
            flip = !flip;
        }
        if (!flip) {
            if (a[i] <= lo) {
                cout << max(0LL, mini - (t[i] - r[ridx - 1])) << "\n";
            } else if (a[i] >= hi) {
                cout << max(0LL, maxi - (t[i] - r[ridx - 1])) << "\n";
            } else {
                cout << max(0LL, mini + (a[i] - lo) - (t[i] - r[ridx - 1])) << "\n";
            }
        } else {
            if (a[i] <= lo) {
                cout << min(x, mini + (t[i] - r[ridx - 1])) << "\n";
            } else if (a[i] >= hi) {
                cout << min(x, maxi + (t[i] - r[ridx - 1])) << "\n";
            } else {
                cout << min(x, mini + (a[i] - lo) + (t[i] - r[ridx - 1])) << "\n";
            }
        }
    }
    return 0;
}

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

int main() {
  int h,w;
  cin >> h >> w;
  
  vector<vector<char>> pict(h,vector<char>(w));
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      cin >> pict.at(i).at(j);
    }
  }
  
  for (int i=0; i<h; i++) {
    bool sharp = false;
    for (int j=0; j<w; j++) {
      if (pict.at(i).at(j)=='#') {
        sharp = true;
      }
    }
    if (!sharp) {
      pict.at(i) = vector<char>(w,'0');
    }
  }
  
  for (int j=0; j<w; j++) {
    bool sharp = false;
    for (int i=0; i<h; i++) {
      if (pict.at(i).at(j)=='#') {
        sharp = true;
      }
    }
    if (!sharp) {
      for (int k=0; k<h; k++) {
        pict.at(k).at(j) = '0';
      }
    }
  }
  
  for (int i=0; i<h; i++) {
    bool output = false;
    for (int j=0; j<w; j++) {
      if (pict.at(i).at(j) != '0') {
        cout << pict.at(i).at(j);
        output = true;
      }
    }
    if (output) {
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
#define yn(f) cout<<(f?"yes":"no")<<endl
#define Yn(f) cout<<(f?"Yes":"No")<<endl
#define YN(f) cout<<(f?"YES":"NO")<<endl
#define COUT(x) cout<<(x)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

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

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================

// Template End ======================================================

constexpr int MOD=1e9+7;

int main(void){
  string a,b,c; cin>>a>>b>>c; cout<<a[0]<<b[1]<<c[2]<<endl;
}













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

int main(void){
	double x1, x2, y1, y2;

	cin >> x1 >> y1 >> x2 >> y2;

	cout << setprecision(10) << sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)) << "\n";

	return 0;
}

Measured memory_bytes: 1284
#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ll long long
#define ALL(a)  (a).begin(),(a).end()

#define pb(a) push_back(a)
#define MOD 1000000007

ll now,n,k;


int main(){
  ll ans=0;
  cin>>n;
  if (n==1){
    cout<<(1)<<endl;
    return 0;
  }
  vector<ll> x(n);
  vector<ll> y(n);
  REP(i,n){
    cin>>x[i]>>y[i];
  }

  vector<ll> ma((n)*(n-1));
  ll tmp;
  int w=0;
  REP(i,n){
    REP(j,n){
      if (i!=j){
        tmp=x[i]-x[j]+1000000001LL+(y[i]-y[j]+1000000001LL)*2000000002LL;
        ma[w]=tmp;
        //cout<<tmp<<endl;
        w++;
      }
    }
  }
  
sort(ma.begin(), ma.end(),greater<ll>());
  
tmp=ma[0];
int du=0;
int maxdup=0;
for(int i=0;i<(n)*(n-1)-1;i++){
  if (ma[i+1]==tmp){
    du++;
    maxdup=max(maxdup,du);
    }else{
      du=0;
      tmp=ma[i+1];
    }
}


//cout<<(maxdup)<<endl;
cout<<(n-maxdup-1)<<endl;
return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Arrays;
import java.util.Set;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int[]a=new int[3];
        for(int i=0;i<3;i++){
            a[i]=sc.nextInt();
        }
        int sum=0;
    Arrays.sort(a);
    for(;;){
        if((a[0]==a[1])&&(a[1]==a[2])){
            System.out.println(sum);
            break;
        }
        if(a[1]-a[0]<2){
            a[0]++;
            a[1]++;
        }else{
            a[0]+=2;
        }
        Arrays.sort(a);
        sum++;
        if((a[0]==a[1])&&(a[1]==a[2])){
            System.out.println(sum);
            break;
        }
    }
}
        
        
    }


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

#define ii pair<int, int>
#define lli long long int
#define ll pair<lli, lli>
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, a[3005], b[3005], memo[3005][3005], bt[3005][3005];

int dp(int pos, int sisa) {
	int ret;
	if (pos == n)
		return 0;
	if (memo[pos][sisa] != -1)
		return memo[pos][sisa];
	ret = dp(pos + 1, sisa);
	if (a[pos] <= sisa)
		ret = max(ret, dp(pos + 1, sisa - a[pos]) + b[pos]);
	memo[pos][sisa] = ret;
	return ret;
}

int backtrack(int pos, int sisa, int hasil) {
	int ret = 0;
	if (pos == n)
		return 0;
	if (bt[pos][sisa] != -1)
		return bt[pos][sisa];
	if (dp(pos + 1, sisa) == hasil) {
		ret = max(ret, b[pos]);
		ret = max(ret, backtrack(pos + 1, sisa, hasil));
	}
	if (sisa >= a[pos])
		if (dp(pos + 1, sisa - a[pos]) == hasil - b[pos])
			ret = max(ret, backtrack(pos + 1, sisa - a[pos], hasil - b[pos]));
	bt[pos][sisa] = ret;
	return ret;
}

int main() {
	int t, ans, temp;
	scanf("%d %d", &n, &t);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &a[i], &b[i]);
	memset(memo, -1, sizeof memo);
	memset(bt, -1, sizeof bt);
	ans = dp(0, t - 1);
	temp = backtrack(0, t - 1, ans);
	ans = max(ans + temp, dp(0, t));
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 71040
parseInt(x) = parse(Int, x)
parseFloat(x) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
    n,k=parseMap(split(readline()))
    h=sort([parseInt(readline()) for i in 1:n])
    ans=10^9+1
    for i in 1:n-k+1
        ans=min(ans,h[i+k-1]-h[i])
    end
    println(ans)
end
main()

Measured memory_bytes: 171988
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int N=5e6; 
const int INF=0x3f3f3f3f;
int n,m,cnt;
int len=0;
int lin[N]; 
int dis[N];
bool vis[N];
map<pair<int,int>,int> id;
struct edge
{
	int next,y,v;
}e[N];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int Getid(int x,int y)
{
	if(id.find(mp(x,y))!=id.end()) return id[mp(x,y)];
	return id[mp(x,y)]=++cnt;
}
void insert(int xx,int yy,int v)
{
	e[++len].next=lin[xx];
	lin[xx]=len;
	e[len].y=yy;
	e[len].v=v;
}
void add(int xx,int yy,int val)
{
	insert(xx,yy,val),insert(yy,xx,val);
}
void SPFA()
{
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[1]=0,vis[1]=true;
	q.push(1);
	while(!q.empty())
	{
		int x=q.front(); 
		q.pop();
		vis[x]=false;
		for(int i=lin[x];i;i=e[i].next)
		{
			int v=e[i].y;
			if(dis[v]>dis[x]+e[i].v) 
			{
				dis[v]=dis[x]+e[i].v;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
}
int main()
{
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
	n=read(),m=read();
	cnt=n;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),c=read();
		int xx=Getid(u,c);
		int yy=Getid(v,c);
		add(xx,yy,0);
		add(u,xx,1);
		add(v,yy,1);
	}
	SPFA();
	printf("%d",dis[n]!=INF?dis[n]/2:-1);
	return 0;
}


Measured memory_bytes: 68736
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define inf std::numeric_limits<int>::max();
#define highest_2_pow(n)  __builtin_clzll((long long)0)- __builtin_clzll((long long)n) - 1
//-----------------------------------------------------------------------------------------------------
#define lli long long int 
#define int long long
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi vector<int>
#define vlli vector<long long int>
#define si set<int>
#define slli set<long long int>
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
//---------------------------------------------------
using namespace std;
// GCD and LCM are available
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}

void faster(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
void solve(){
    int a,b,x;
    cin>>a>>b>>x;
    //cout<<(int)(ceil((1.0*(b+1))/x) - ceil((1.0*a)/x))<<endl;
    cout<<(((b/x)*x)/x)+1 - ((((a/x)*x)/x)+(a%x==0?0:1))<<endl;
}
signed main()
{
    faster();
    int t=1;
    //cin>>t;
    while(t--) solve();
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

#define tate 3
#define yoko 3
#define Total (tate*yoko)
#define TryCnt 45

extern inline void down_0(void);
extern inline void up_0(void);
extern inline void right_0(void);
extern inline void left_0(void);

extern int  serch(int x, int y, int MaxCnt, int pre);

int num = 0;
int val[Total] ={};

int main( void )
{
    int i = 0;
    int x,y = 0;

    for(i=0; i<Total; i++)
    {
        scanf("%d",&val[i]);

        if(val[i] == 0)
        {
            num = i;
        }
    }

    x = tate - (num/yoko) -1;
    y = yoko - (num%yoko) -1;

    for(i=0; i<TryCnt; i++)
    {
        if( serch(x,y,i,4) == 1 )
        {
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}

int serch(int x, int y, int MaxCnt, int pre)
{
    int result;
    int i=0;

    if(MaxCnt < (x + y) )
    {
        return 0;
    }

    if(MaxCnt==0)
    {
        for(i=0; i<Total-1; i++)
        {
            if(val[i] != (i+1))
            {
                // ゴールと不一致
                return 0;
            }
        }
        // ゴールと一致！！
        return 1;
    }


    // 0 の移動
    for(i=0; i<4; i++)
    {
        result = 0;

        switch(i)
        {
            case 0:
                if( (x > 0) && (pre != 3) )
                {
                    down_0();

                    result = serch(x-1, y, MaxCnt-1, 0);

                    up_0();
                }
                break;

            case 1:
                if( (y > 0) && (pre != 2) )
                {
                    right_0();

                    result = serch(x, y-1, MaxCnt-1, 1);

                    left_0();
                }
                break;

            case 2:
                if( (y < yoko -1 ) && (pre != 1) )
                {
                    left_0();

                    result = serch(x, y+1, MaxCnt-1, 2);

                    right_0();
                }
                break;

            case 3:
                if( (x < tate -1 ) && (pre != 0) )
                {
                    up_0();

                    result = serch(x+1, y, MaxCnt-1, 3);

                    down_0();
                }
                break;

            default:
                // 何もしない。
                break;
        }

        if(result)
        {
            return 1;
        }
    }

    return 0;
}


inline void down_0()
{
    val[num] = val[num + yoko];
    num = num + yoko;
}

inline void up_0()
{
    val[num] = val[num - yoko];
    num = num - yoko;
}

inline void right_0()
{
    val[num] = val[num +1];
    num = num + 1;
}

inline void left_0()
{
    val[num] = val[num -1];
    num = num - 1;
}



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

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i=0;i<n;++i)
	{
		cin >> a[i];
	}
	int q;
	cin >> q;
	vector<int> b(q),c(q);
	for (int i=0;i<q;++i)
	{
		cin >> b[i] >> c[i];
	}

	int64_t sum=0;
	map<int,int> mm;
	for (int i=0;i<n;++i)
	{
		mm[a[i]]++;
		sum+=a[i];
	}

	for (int i=0;i<q;++i)
	{
		int beforecount=mm[b[i]];
		mm.erase(b[i]);
		mm[c[i]]+=beforecount;
		sum-=((int64_t)b[i])*beforecount;
		sum+=((int64_t)c[i])*beforecount;
		cout << sum << endl;
	}
}







Measured memory_bytes: 7388
n,m = map(int,input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]
ans = 'No'

for i in range(n-m+2):
	c = a[i:i+m]
	for j in range(n-m+2):
		d = [e[j:j+m] for e in c]
		if b == d:
			ans = 'Yes'
print(ans)

Measured memory_bytes: 3060
/*
  AOJ 2524
  Title:Mysterious Operator
  @kankichi573
*/
#include <stdio.h>
#include <string.h>
char buf[11]; 

main()
{
  int i,j,len,ret,parity,fm,lt;
  char buf2[11];
  scanf("%s",&buf[0]);
  len=strlen(buf);
  ret=((buf[len-1]&1)?0:1);
  //printf("ret1=%d\n",ret);
  //count digits whose parity is same as last digit 
  if(len>1)
    {
      parity=(buf[len-1] & 1);
      for(j=len-2;j>=((buf[0]=='-')?1:0);j--)
	{
	  if(buf[j+1]=='0')
	    continue;
	  if(parity==(buf[j]&1))
	    if(buf[0]=='-')
	      ret++;
	    else
	      {
		lt=atoi(&buf[j+1]);
		strcpy(buf2,buf);
		buf2[j+1]='\0';
		fm=atoi(buf2);
		//printf("fm=%d lt=%d\n",fm,lt);
		if(fm<=lt)
		  ret++;
	      }
	}
    }
  printf("%d\n",ret);
      
  return(0);
}

Measured memory_bytes: 560