akhauriyash/Code-Regression huggingface dataset:
//
// Copyright 2018 Authors All Rights Reserved.
//
// FileName: D.cc
// Author: Beiyu Li <sysulby@gmail.com>
// Date: 2018-08-25
//
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;
typedef pair<int, int> Pii;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const int maxn = 100000 + 5;

int n;
int a[maxn], b[maxn];
int pre[maxn];
int c[maxn*2];

void update(int i)
{
  for (i += n; i <= 2 * n; i += i & -i) c[i] += 1;
}

int query(int i)
{
  int ret = 0;
  for (i += n; i; i -= i & -i) ret += c[i];
  return ret;
}

LL calc(int x)
{
  LL ret = 0;
  rep(i,n) {
    pre[i] = (i? pre[i-1]: 0) + (a[i] <= x? 1: -1);
    if (pre[i] > 0) ++ret;
  }
  memset(c, 0, sizeof(c));
  rep(i,n) {
    ret += query(pre[i] - 1);
    update(pre[i]);
  }
  return ret;
}

int main(int argc, char *argv[]) {
  scanf("%d", &n);
  rep(i,n) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(b, b + n);
  int l = 0, r = unique(b, b + n) - b - 1;
  LL tot = (LL)n * (n + 1) / 2;
  while (l < r) {
    int mid = (l + r) / 2;
    LL c = calc(b[mid]);
    if (c > tot - c) r = mid;
    else l = mid + 1;
  }
  printf("%d\n", b[r]);

  return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include <string>
#include <sstream>
using namespace std;
int main()
{
    int N;
    cin >> N;
    stringstream ss;
    ss << N;
    string strN = ss.str();

    int count = 1;
    bool flag = false;
    for(int i=1;i<4;i++){
      if(strN[i-1] == strN[i]){
        count += 1;
      }else{
        count = 1;
      }
      if(count >= 3) flag = true;
    }
    if(flag){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#undef int
#define mk make_pair
#define pb push_back
typedef pair<int, int> pii;
const int mod = 1000000007;
const int INF = 1000000009;
const long long INFL = 1000000000000000018ll;

int N;
vector<int> G[100100];
bool used[100100];
int dp[100100][2];

int dfs(int v)
{
    used[v] = true;
    dp[v][1] = 1;
    dp[v][0] = 1;
    vector<int> c;
    for(int i = 0; i < G[v].size(); i++){
        int to = G[v][i];
        if(!used[to]){
            int res = dfs(to);
            c.pb(to);
        }
    }
    for(int i = 0; i < c.size(); i++){
        int to = c[i];
        dp[v][0] = dp[v][0] * ((dp[to][0] + dp[to][1]) % mod) % mod;
        dp[v][1] = dp[v][1] * dp[to][0] % mod;
    }
    return (dp[v][0] + dp[v][1]) % mod;
}

signed main()
{
    cin >> N;
    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    cout << dfs(0) << endl;

    return 0;
}
/*



*/



Measured memory_bytes: 15744
# import sys
# import math #sqrt
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # deque
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    h,w = map(int,input().split())
    s = []
    for i in range(h):
        s.append(list(input()))
    ans = [[0 for i in range(w+2)] for j in range(h+2)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                ans[i][j] += 1
                ans[i+1][j] += 1
                ans[i+2][j] += 1
                ans[i][j+1] += 1
                ans[i+2][j+1] += 1
                ans[i][j+2] += 1
                ans[i+1][j+2] += 1
                ans[i+2][j+2] += 1
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                ans[i+1][j+1] = "#"
            else:
                ans[i+1][j+1] = str(ans[i+1][j+1])
    for i in range(1,h+1):
        print(''.join(ans[i][1:w+1]))
    return

if __name__=='__main__':
    main()

Measured memory_bytes: 3188
#include <stdio.h>
#define N 200000

int main(){

  int i,j,n,minv,maxv;
  int A[N];

  scanf("%d",&n);

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

  minv = A[0];
  maxv = A[1]-A[0];

  for(j=1; j<=n-1; j++){
    if(maxv < A[j]-minv)
      maxv = A[j]-minv;
    if(minv > A[j])
      minv = A[j];
  }
    printf("%d\n",maxv);
  return 0;
}

Measured memory_bytes: 1376
#include<stdio.h>

void set_data(int data[], int n){
    for(int i = 0; i < n; i++){
        scanf("%d", &data[i]);
    }
}

int calc(int data[], int n){
    int sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            sum += data[i] *data[j];
        }
    }
    return sum;
}

int main(void){
    int n;
    scanf("%d", &n);
    int takoyaki[n];
    set_data(takoyaki, n);
    printf("%d\n", calc(takoyaki, n));
    return 0;

}

Measured memory_bytes: 128
n,k=map(int,input().split())
a=list(map(int,input().split()))
if len(list(set(a)))<=k:
  print(0)
else:
  d={}
  for i in range(n):
    if a[i] in d:
      d[a[i]]+=1
    else:
      d[a[i]]=1
  d=sorted(d.items(),key=lambda x:x[1])
  m=len(d)
  cnt=0
  for i in range((len(list(set(a))))-k):
    cnt+=d[i][1]
  print(cnt)

Measured memory_bytes: 48180
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
static const double pi = 3.141592653589793;

int main(void){
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    h *= 5; //分に合わせる
    h += m/12;

    double theta = abs(h-m)*180;
    theta /= 30;
    if(theta>180) theta = 360-theta;

    //cout << theta << endl;
    double c = sqrt(a*a+b*b-2*a*b*cos(theta*pi/180));
    printf("%.15f\n", c);

    return 0;

}

Measured memory_bytes: 4228
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MX 100005
#define MOD 1000000007

using namespace std;

typedef long long ll;

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

struct MAT
{
	ll x[3][3];
	
	MAT () {memset(x, 0, sizeof(x));}
	
	void set1() {x[0][0] = x[1][1] = x[2][2] = 1;}
	
	MAT operator * (const MAT& t)
	{
		MAT c;
		for(int i=0; i<3; i++)
			for(int k=0; k<3; k++)
			{
				ll v = x[i][k];
				for(int j=0; j<3; j++)
					c.x[i][j] = (c.x[i][j] + v * t.x[k][j]) % MOD;
			}
		return c;
	}
} tr_ok, tr_ban;

MAT qpow(MAT x, int t)
{
	MAT ans; ans.set1();
	while(t)
	{
		if(t & 1) ans = ans * x;
		x = x * x;
		t >>= 1;
	}
	return ans;
}

int n, m, pos[MX];

int main()
{
	MAT a; a.set1();
	tr_ok.x[0][0] = 1;
	tr_ok.x[0][2] = 1;
	tr_ok.x[1][0] = 2;
	tr_ok.x[1][1] = 1;
	tr_ok.x[1][2] = 2;
	tr_ok.x[2][0] = 1;
	tr_ok.x[2][1] = 1;
	tr_ok.x[2][2] = 2;
	tr_ban.x[0][0] = 1;
	tr_ban.x[1][0] = 2;
	tr_ban.x[1][1] = 1;
	tr_ban.x[2][0] = 1;
	tr_ban.x[2][1] = 1;
	tr_ban.x[2][2] = 1;
	read(n); read(m);
	for(int i=1; i<=m; i++) read(pos[i]);
	for(int i=1; i<=m; i++)
	{
		a = a * qpow(tr_ok, pos[i] - pos[i-1] - 1);
		a = a * tr_ban;
	}
	a = a * qpow(tr_ok, n - pos[m]);
	printf("%lld\n", a.x[2][0]);
	return 0;
}

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

using namespace std;

int main(void)
{
  string s, t;
  cin >> s >> t;
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] != t[i]) ++res;
  }
  cout << res << endl;
}

Measured memory_bytes: 3828
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

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

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll combination(ll n,ll r){
    ll sum=1;
    rrep(i,min(r,n-r)) (sum*=(n-i+1))%=mod;
    return sum;
}

//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    if(abs(a-b)>1e18) cout<<"Unfair"<<endl;
    else {
        if(k%2==0) cout<<a-b<<endl;
        else cout<<b-a<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
void main()
{
    long[] tmp = rdRow;
    long a = tmp[0], b = tmp[1], k = tmp[2];

    long c = min(a, k);
    a -= c;
    long d = min(b, k - c);
    b -= d;

    writeln(a, " ", b);
}

T rdElem(T = long)()
{
    //import std.stdio : readln;
    //import std.string : chomp;
    //import std.conv : to;

    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;

dchar[] rdDchar()
{
    //import std.conv : to;

    return rdStr.to!(dchar[]);
}

T[] rdRow(T = long)()
{
    //import std.stdio : readln;
    //import std.array : split;
    //import std.conv : to;

    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdRow!T).array;
}

void wrMat(T = long)(T[][] mat)
{
    //import std.stdio : write, writeln;

    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
#include <bits/c++io.h>
#include <cmath>
#define maxn 100000+5
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
  int a,b,ans=0;
  cin>>a>>b;
  int i=0;
  while(1)
  {
    a-=b;
    i++;
    if(a<= 0)
    {
      break;
    }
  }
  cout<<i<<endl;
 }

Measured memory_bytes: 256
import java.util.Scanner;

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

		if (b == 1) {
			System.out.println(0);
		} else {

			b = b - a;
			int cnt = 1;
			while (b > 0) {
				b = b - a + 1;
				cnt++;
			}
			System.out.println(cnt);
		}
	}
}

Measured memory_bytes: 21844
import math

def plot(x,y):
    print(f'{x:.8f} {y:.8f}')

def koch(n, x1,y1,x2,y2):
    if n==0:
        plot(x1,y1)
        return
    sx = ( 2*x1 + x2 ) /3
    sy = ( 2*y1 + y2 ) /3
    tx = ( x1 + 2*x2 ) /3
    ty = ( y1 + 2*y2 ) /3
    ux = (tx-sx)*(1/2) - (ty-sy)*(math.sqrt(3)/2) + sx
    uy = (tx-sx)*(math.sqrt(3)/2) + (ty-sy)*(1/2) + sy
    koch(n-1 ,x1,y1,sx,sy)
    koch(n-1 ,sx,sy,ux,uy)
    koch(n-1 ,ux,uy,tx,ty)
    koch(n-1 ,tx,ty,x2,y2)
    
n=int(input())
koch(n,0,0,100,0)
plot(100,0)


Measured memory_bytes: 5752
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair

bool stg(long long x, long long a, long long b)
{
    if (x == 4)
        cout << "";
    vector<long long> v;
    if (b <= x)
    {
        if (a - 1 > x - (b - 1))
        {
            v.push_back(x - (b - 1));
            v.push_back(a - 1 - (x - (b - 1)));
            v.push_back(x - (a - 1));
        }
        else
        {
            v.push_back(a - 1);
            v.push_back(x - (b - 1) - (a - 1));
            v.push_back(b - 1);
        }
    }
    else if (a <= x)
    {
        v.push_back(a - 1);
        v.push_back(x - (a - 1));
    }
    else
    {
        v.push_back(x);
    }
    long long ua = 1;
    long long ub = x;
    if (b <= x)
        ++ub;
    for (int i = 0; i < v.size(); ++i)
    {
        if (v[i] == 0)
            continue;
        if (ua == a)
            ++ua;
        if (ub == b)
            --ub;
        long long ra = ua + v[i] - 1;
        long long lb = ub - v[i] + 1;
        if (ua * ub >= a * b)
            return false;
        if (ra * lb >= a * b)
            return false;
        if (ra <= ub)
        {
            if (lb <= ra)
            {
                int d = (ra - lb + 1);
                if ((ra - (d / 2)) * (lb + (d / 2)) >= a * b)
                    return false;
            }
        }
        else
        {
            if (ua <= ub)
            {
                int d = (ub - ua + 1);
                if ((ua + (d / 2)) * (ub - (d / 2)) >= a * b)
                    return false;
            }
        }
        ua += v[i];
        ub -= v[i];
    }
    return true;
}

void solv()
{
    int aa, bb;
    scanf("%d%d", &aa, &bb);
    if (aa > bb)
        swap(aa, bb);
    long long l = 1, r = 2000000000;
    long long ans = 0;
    while (l <= r)
    {
        long long m = (l + r) / 2;
        if (stg(m, aa, bb))
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%lld\n", ans);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int tt;
    scanf("%d", &tt);
    while (tt--)
    {
        solv();
    }
    return 0;
    for (int i = 1; i <= 300; ++i)
    {
        set<int> s;
        for (int j = 1; j <= i; ++j)
            s.insert(i / j);
        printf("%d %d\n", i, s.size());
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>

using ll = long long;

using namespace std;

#define MAX_L 100010
#define MAX_N 262145

#define amax(a, b) a = max(a, b);

using P = pair<int, int>;
#define fi first
#define se second

int v[MAX_N], w[MAX_N];
vector<int> ans[256];

void dfs(int i, int n, vector<vector<int>> &dp) {
    ans[i].resize(MAX_L, 0);
    vector<int> &prev = dp.back();
    vector<int> &cur  = ans[i];
    for (int j=0; j<MAX_L; j++) {
        amax(cur[j], prev[j]);
        if (j + 1 < MAX_L)
            amax(cur[j+1], prev[j]);
        if (j + w[i] < MAX_L)
            amax(cur[j+w[i]], prev[j] + v[i]);
    }
    dp.push_back(cur);
    if (i * 2 <= n) dfs(i * 2, n, dp);
    if (i * 2 + 1 <= n) dfs(i * 2 + 1, n, dp);
    dp.pop_back();
}

int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> v[i] >> w[i];
    }
    vector dp(1, vector<int>(MAX_L, 0));
    dfs(1, min(n, 255), dp);
    int q; cin >> q;
    for (int i=0, vi, li; i<q; i++) {
        cin >> vi >> li;
        vector<int> check;
        while (vi >= 256) {
            check.push_back(vi);
            vi /= 2;
        }
        vector<P> search(1, {0, 0});
        for (auto &ci:check) {
            vector<P> buf;
            for (auto &si:search) {
                buf.push_back(si);
                buf.push_back({si.fi + v[ci], si.se + w[ci]});
            }
            search.swap(buf);
        }
        int best = 0;
        for (auto &si:search) {
            if (si.se <= li) {
                amax(best, si.fi + ans[vi][li - si.se]);
            }
        }
        cout << best << '\n';
    }
    return 0;
}

Measured memory_bytes: 108548
import sys
input = sys.stdin.readline
N, M= (int(i) for i in input().split())
A = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
count = 0

thre = sum(A)/(4*M)

for e in A:
    if thre <= e:
        count += 1

if M <=count :
    print("Yes")
else:
    print("No")


Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int d = sc.nextInt();
		int n = sc.nextInt();
		sc.close();

		int res = 0;
		for(int i=1;;i++) {
			if(calc(i) == d) {
				res++;
				if(res == n) {
					System.out.println(i);
					return;
				}
			}
		}
		
	}
	
	int calc(int x) {
		if(x%100 != 0) return 0;
		else return calc(x/100) + 1;
	}
}

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

using namespace std;

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

    long long a[200000 + 5];
    long long tot = 0;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        tot += a[i];
    }

    long long ans = tot, tmp = 0;
    for (int i = 1; i <= N; i++) {
        tmp += a[i];
        ans = min(ans, abs(tmp - (tot - tmp)));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX(X, Y) ((X > Y)? X : Y)
#define MIN(X, Y) ((X < Y)? X : Y)
//　45min
int main(void){
  int n;
  int a = 0, b = 0, c = 0;;
  
  scanf("%d", &n);

  scanf("%d", &b);
  if(n > 1){
    for(int i = 2; i <= n; i++){
      scanf("%d", &c);

      if(b <= c - 1){
	c = c - 1;
      }

      if(b > c){
	printf("No\n");
	return 0;
      }
      
      else if(b == c && a > c){
	printf("No\n");
	return 0;
      }
      a = b;
      b = c;
    }
  }
  
  printf("Yes\n");

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

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

    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    int match = 0;
    rep(i, n) {
        if (s.substr(n - 1 - i, i + 1)== t.substr(0, i + 1)) {
            match = i + 1;
        }
    }
    cout << 2 * n - match << endl;
}


Measured memory_bytes: 256
import * as fs from "fs"


function Main(input: any) {
    const args = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    console.log(args[input as number - 1])
}

Main(fs.readFileSync("/dev/stdin", "utf8"));


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

using namespace std;

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

    int k;
    cin >> k;

    int ans;

    if(k&1){
        ans = (k/2)*(k/2+1);
    }
    else {
        ans = (k/2)*(k/2);
    }

    cout << ans << '\n';

    return 0;
}



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

void insertion_sort(vector<int> &vec) {
    int len = (int) vec.size();

    for (int i = 0; i < len - 1; ++i) 
        printf("%d ", vec[i]);
    printf("%d\n", vec[len - 1]);


    int i = 1;
    while( i < len ) {
        int j = i - 1, elem = vec[i];
        while ( j >= 0 && vec[j] > elem ) {
            vec[j + 1] = vec[j];
            j--;
        }

        vec[j + 1] = elem;

        for (int i = 0; i < len - 1; ++i) 
            printf("%d ", vec[i]);
        printf("%d\n", vec[len - 1]);
        ++i;
    }
}


int main() {
    int n;
    scanf("%d", &n);
    vector<int> res(n);
    for (auto &el: res) scanf("%d", &el);
    insertion_sort(res);
    return 0;
}



Measured memory_bytes: 3172
#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

bool four;
int n;
int main(){
	//IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        char temp;
        cin>>temp;
        if(temp=='Y'){four=true;}
    }
    if(four){cout<<"Four\n";}
    else {cout<<"Three\n";}
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

bool is_binary(int S[],int n,int T){
    
    int left=0;
    int right=n-1;
    int mid=(left+right)/2;
    
    
    bool flag=false;
    while(left<right){
       /*
        cout<<"T:"<<T<<endl;
        cout<<"left:"<<left<<":"<<S[left]<<endl;
        cout<<"right:"<<right<<":"<<S[right]<<endl;
        cout<<"mid:"<<mid<<":"<<S[mid]<<endl;
        */
        if(S[left]<=T&&T<=S[mid]){
            right=mid;
        }else if(S[mid+1]<=T&&T<=S[right]){
            left=mid+1;
        }else{
            break;
        }
        mid=(left+right)/2;
        
        if(S[left]==T||S[right]==T){
            flag=true;
            break;
        }
    }
    /*
    if(flag){
        cout<<T<<endl;
    }
     */
    return flag;
    
}

int main(){
    
    int n;
    cin>>n;
    int S[n];
    
    for(int i=0;i!=n;++i){
        cin>>S[i];
    }
    
    int q;
    cin>>q;
    int T[q];
    
    for(int i=0;i!=q;++i){
        cin>>T[i];
    }
    int count=0;
    for(int i=0;i!=q;++i){
        if(is_binary(S, n, T[i])){
            ++count;
        }
    }
    cout<<count<<endl;
}







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

/*
*/

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    int ans1,ans2;
    ans1=-1;
    ans2=-1;
    for(int i=1; i<n; i++){
        if(s[i-1]==s[i]) {
            ans1=i;
            ans2=i+1;
        }
    }
    for(int i=2; i<n; i++){
        if(s[i-2]==s[i]){
            ans1=i-1;
            ans2=i+1;
        }
    }
    cout << ans1 << " " << ans2 << endl;
}

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



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

int main(){
    string S;
    cin >> S;
    int ans = 753;
    for(int i = 0; i <= S.size()-3; ++i){
        int buf = (S[i]-'0')*100 + (S[i+1]-'0')*10 + (S[i+2]-'0');
        ans = min(ans, abs(buf-753));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
#define rep(i,n) for(int i=0;i<((int)(n));i++)
typedef long long int lli;

#define MOD ((lli)(1000000007))
int n;
lli dp[45][1<<20]={};
int main(void){
	int x,y,z,s,ch;
	scanf("%d%d%d%d",&n,&x,&y,&z);
	s = 1<<(x+y+z+1);
	ch = ((((1<<x)+1)<<y)+1)<<(z-1);
	
	dp[0][0]=1;
	rep(i,n){
		rep(j,s){
			if((j&ch)==ch)continue;
			rep(k,10){
				int tj=(j*2+1)<<k;
				tj &= (s-1);
				if((tj&ch)==ch)continue;
				dp[i+1][tj] = (dp[i+1][tj] + dp[i][j])%MOD;
			}
		}
	}
	
	lli ans=1;
	rep(i,n)ans=(ans*10)%MOD;
	
	rep(j,s){
		ans = (ans+MOD-dp[n][j])%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}






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

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    ll K,S; cin >> K >> S;
    ll ans = 0;
    for(int i  =  0; i <=K;i++){
        for(int j = 0; j <=K;j++){
            ll k =  S - i- j;
            if(k < 0 || k > K) continue;
            if(i + j + k == S){
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

int a, b, t;

int main() {

	cin >> a >> b >> t;

	cout << (t / a) * b << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int n, k;
string s;
vector<int> order;
vector<int> tmp;
vector<int> sa;
 
bool compare_sa(const int &i, const int &j)
{
  if(order[i] != order[j]) return order[i] < order[j];
  else
  {
    int ri = i + k <= n ? order[i+k] : -1;
    int rj = j + k <= n ? order[j+k] : -1;
    return ri < rj;
  }
}
 
void construct_sa()
{
  for(int i = 0; i <= n; i++)
  {
    sa[i] = i;
    order[i] = i < n ? s[i] : -1;
  }
  for(k = 1; k <= n; k*=2)
  {
    sort(sa.begin(),sa.end(),compare_sa);
    tmp[sa[0]] = 0;
    for(int i = 1; i <= n; i++)
      tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1],sa[i])?1:0);
    for(int i = 0; i <= n; i++)
      order[i] = tmp[i];
  }
}
 
void init()
{
  n = s.size();
  order.resize(n+1);
  tmp.resize(n+1);
  sa.resize(n+1);
  construct_sa();
}
 
bool contain(string t)
{
  int l=0, r=n;
  while(r-l>1)
  {
    int m = (l+r)/2;
    if(s.compare(sa[m],t.size(),t)<0) l = m;
    else r = m;
  }
  return s.compare(sa[r],t.size(),t) == 0;
}
 
int main(){
 
    cin >> s;
    string t;
    int q ; cin >> q;
    init();
    construct_sa ();
    for (int i = 0; i < q; ++i)
     {
        cin >> t;
        cout << contain(t) << endl;
     } 
     return 0;
}

Measured memory_bytes: 15828
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,k;;
  cin>>n;
  char s[n];
  cin>>s>>k;
  char tem=s[k-1];
  for(int i=0;i<n;++i){
    if(s[i]!=tem){
      s[i]='*';
    }
  }
  cout<<s;
  return 0;
}


Measured memory_bytes: 256
// ProblemURL : https://atcoder.jp/contests/abc122/tasks/abc122_c
// ---------------------------------------------
package main

import "fmt"

func main() {
	var n, q int
	var s string
	fmt.Scan(&n, &q, &s)

	c := make([]int, n+1)
	for i := 0; i < n; i++ {
		c[i+1] = c[i]
		if i+1 < n && s[i] == 'A' && s[i+1] == 'C' {
			c[i+1]++
		}
	}

	for i := 0; i < q; i++ {
		var l, r int
		fmt.Scan(&l, &r)
		l--
		r--
		fmt.Println(c[r] - c[l])
	}
}


Measured memory_bytes: 6144
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
using namespace std;
int main(){
    Fast;
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    ll sum=0LL;
    for(int i=0;i<k;i++){
        sum+=v[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3608
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
B = [list(map(int,input().split())) for j in range(m)]
C = [[0]*l for k in range(n)]
for s in range(n):
    for t in range(l):
        for u in range(m):
            C[s][t] += A[s][u] * B[u][t]
for v in range(n):
    print(*C[v])


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

int main(){
    string S, T;
    cin >> S;
    cin >> T;
    if(S==T){
        cout << "Yes" << endl;
        return 0;
    }

    for(int i=0; i<S.size(); i++){
        char tmp = S[S.size()-1];
        for(int j=S.size()-1; j>=1; j--){
            S[j] = S[j-1];
        }
        S[0] = tmp;
        if(S==T){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		Stack<Integer> s = new Stack<Integer>();
		int y = cin.nextInt();
		if(y==0){
			return;
		}
		s.add(y);
		while(cin.hasNext()){
			int x = cin.nextInt();
			if(x==0){
				System.out.println(s.pop());
			}
			else{
				s.add(x);
			}
		}
	}

}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
typedef long long ll;
int main(int argc, char const *argv[]) {
    int a, b, c;
    std::cin >> a >> b >> c;
    if (a == 5 && b == 5 && c == 7) {
        std::cout << "YES" << '\n';
    } else if (a == 5 && b == 7 && c == 5) {
        std::cout << "YES" << '\n';
    } else if (a == 7 && b == 5 && c == 5) {
        std::cout << "YES" << '\n';
    } else {
        std::cout << "NO" << '\n';
    }

    return 0;
}


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

typedef long long int ll;

const int MOD = 1e9 + 7;
ll factorial(ll n){
    ll res = 1;
    for(ll i = n; i > 0; --i){
        (res *= i) %= MOD;
    }
    return res;
}

int main(){

    ll N; string S; cin >> N >> S;
    vector<bool> d(2*N, false); // let L = false & R = true

    for(int i = 0; i < 2*N; ++i) 
        if((i % 2 == 0 && S[i] == 'W') || (i % 2 && S[i] == 'B')) 
            d[i]  = true;
    
    ll ans = 1, lsum = 0;
    for(int i = 0; i < 2*N; ++i)
        if(d[i]){
            if(lsum == 0){
                cout << 0 << endl;
                return 0;
            }
            (ans *= lsum) %= MOD;
            --lsum;
        }else ++lsum;
    
    if(lsum > 0) cout << 0 << endl;
    else cout << ans*factorial(N)%MOD << endl;

    return 0;
}

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

ll mod = 1000000007;
ll modpow(ll a, ll n){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll com(ll a, ll b){
	ll res = 1;
	b = min(b, a-b);
	ll n = b;
	for(int i=0; i<n; i++){
    	res *= a;
    	if(res >= mod) res %= mod;
    	res *= modpow(b, mod-2);
    	if(res >= mod) res %= mod;
    	a--;
    	b--;
    }
	return res;
}

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	int ans = modpow(2, a);
	ans--;
	if(ans < 0) ans += mod;
	ans -= com(a, b);
	if(ans < 0) ans += mod;
	ans -= com(a, c);
	if(ans < 0) ans += mod;
	cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

unsigned char D[252004];
bool E[252004];
unsigned int Q[300000];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N;
	cin >> N;
	int n = N + 2;
	rep1(i, N) {
		int ij = n * i + 1;
		unsigned char kari = min(i - 1, N - i) + 2;
		unsigned char kari2 = 2;
		rep1(j, N / 2) {
			D[ij++] = min(kari, kari2++);
		}
		if (N % 2 == 0) kari2--;
		for (int j = N / 2 + 1; j <= N; j++) {
			D[ij++] = min(kari, kari2--);
		}
	}

	int kotae = 0;
	rep(k, N * N) {
		int ij;
		cin >> ij;
		ij += (ij - 1) / N * 2 + N + 2;

		kotae += D[ij]--;
		E[ij] = 1;

		int p = 0, q = 0;
		Q[p++] = ij;

		while (p > q) {
			int ij = Q[q++];
			int d =	D[ij] + 1;

			if (D[ij - n] > d - E[ij - n]) {
				D[ij - n] = d - E[ij - n];
				Q[p++] = ij - n;
			}
			if (D[ij + n] > d - E[ij + n]) {
				D[ij + n] = d - E[ij + n];
				Q[p++] = ij + n;
			}
			if (D[ij - 1] > d - E[ij - 1]) {
				D[ij - 1] = d - E[ij - 1];
				Q[p++] = ij - 1;
			}
			if (D[ij + 1] > d - E[ij + 1]) {
				D[ij + 1] = d - E[ij + 1];
				Q[p++] = ij + 1;
			}
		}
	}

	co(kotae - 2 * N * N);



	Would you please return 0;
}

Measured memory_bytes: 5016
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
 
  ll N = input();
  map<string, int> data;
  for(int i=0;i<N;i++){
    string s = input<string>();
    data[s]++;
  }
  output(data.size());

  return 0;
}

Measured memory_bytes: 19224
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
 
using namespace std;
 
const double eps=1e-10;

int main()
{
	long long l[10];
	while(cin>>l[0]){
		l[0]*=1000;
		long long sum=l[0];

		char dummy;
		for(int i=1;i<10;i++){
			cin>>dummy>>l[i];
			l[i]*=1000;
			sum+=l[i];
		}
		double v1,v2;
		cin>>dummy>>v1>>dummy>>v2;

		v1/=3.6; v2/=3.6;

		//x1=v1*t x2=-v2*t+sum
		double x=v1*sum/(v1+v2);

		int L=0;
		for(int i=0;i<10;i++){
			L+=l[i];
//			cout<<"x="<<x<<endl<<"l="<<L<<endl;
			if(x<=L){
				cout<<i+1<<endl;
				break;
			}
		}


	}

	return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint h,w;
    cin >> h >> w;
    lint ans=0;
    vector<vector<int>> v(h, vector<int>(w));
    vector<vector<int>> v2(h, vector<int>(w));
    REP(i,h){
        REP(j,w){
            cin >> v[i][j];
            v2[i][j] = v[i][j];
        }
    }
    REP(i, h)
    {
        REP(j, w)
        {
            int x = v2[i][j];
            if(x%2==1){
                int y,z;
                // y = v[i + 1][j];
                if (j != w - 1)
                {
                    z = v2[i][j + 1];
                    if (z%2==1)
                    {
                        v2[i][j + 1]++;
                        //cout << i << " " << j << " " << i << " " << j+1 << "\n";
                        ans++;
                        continue;
                    }
                    //ans++;
                }
                if (i != h - 1)
                {
                    v2[i + 1][j]++;
                    //cout << i << " " << j << " " << i + 1 << " " << j << "\n";
                    ans++;
                    continue;
                }
                if (j != w - 1)
                {
                    v2[i][j + 1]++;
                    ans++;
                }
            }else{
            }
        }
    }
    cout << ans << endl;
    REP(i, h)
    {
        REP(j, w)
        {
            int x = v[i][j];
            if (x % 2 == 1)
            {
                int y, z;
                // y = v[i + 1][j];
                if (j != w - 1)
                {
                    z = v[i][j + 1];
                    if (z % 2 == 1)
                    {
                        v[i][j + 1]++;
                        cout << i+1 << " " << j+1 << " " << i+1 << " " << j+2 << "\n";
                        continue;
                    }
                    //ans++;
                }
                if (i != h - 1)
                {
                    v[i + 1][j]++;
                    cout << i+1 << " " << j+1 << " " << i + 2 << " " << j +1 << "\n";
                    ans++;
                    continue;
                }
                if (j != w - 1)
                {
                    v[i][j + 1]++;
                    cout << i + 1 << " " << j + 1 << " " << i + 1 << " " << j + 2 << "\n";
                    ans++;
                }
            }
            else
            {
                ans++;
            }
        }
    }
    return 0;
}

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

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

    int taroScore = 0;
    int hanakoScore = 0;

    for(int i=0; i<n; i++) {
        string taro;
        string hanako;
        cin >> taro;
        cin >> hanako;

        if(taro > hanako) {
            taroScore += 3;
        } else if(taro < hanako) {
            hanakoScore += 3;
        } else {
            taroScore++;
            hanakoScore++;
        }
    }

    cout << taroScore << " " << hanakoScore << endl;

    return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int 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 ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int n;cin >> n;
    int p[n];
    REP(i,n)cin>>p[i];
    int count = 0,num = 0;
    for(int i=0;i<n;){
        while(i+1==p[i]){
            i++;
            num++;
        }
        count+=(num+1)/2;
        num=0;i++;
    }
    COUT(count);
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <set>

using namespace std;

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    int temp = 0;
    temp = x;
    x = y;
    y = temp;

    temp = x;
    x = z;
    z = temp;

    cout << x << " " << y << " " << z;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
high = [int(i) for i in input().split()]
dp = [0]*n
dp[0] = 0
dp[1] = abs(high[0]-high[1])

for i in range(2,n):
    dp[i] = min([dp[i-1]+abs(high[i-1]-high[i]),dp[i-2]+abs(high[i-2]-high[i])])

print(dp[n-1])

Measured memory_bytes: 13928
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define sc second
#define inf    1000000000LL
#define MP make_pair
#define N 
#define MOD 1000000007
#define orta ((a+b)/2)
using namespace std;
typedef long long int lint;
typedef pair<int,int> ii;



/*
   A!
---------
B! * (A-B)!

*/
int n,t;
pair <int,int> d[30004];
int main()
{
	scanf("%d %d",&n,&t);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d",&d[i].first,&d[i].second);
	}
	sort(d,d+n);
	int dp[t+5+3005*2],mx=0;;
		memset(dp,-1,sizeof dp);
		dp[0]=0;
	for (int i = 0; i < n; ++i)
		for (int j = t-1; j >= 0; --j)
			if(dp[j]!=-1)
				if(dp[j+d[i].first]==-1 || dp[j+d[i].first]<dp[j]+d[i].second)
				{
					dp[j+d[i].first]=dp[j]+d[i].second;
					mx=max(mx,dp[j+d[i].first]);
				}

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

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  map <int,int> mp;
  ll ans = 0;
  rep(i,n){
      int sa = i-a[i];
      ans += mp[sa];
      int wa = a[i]+i;
      mp[wa]++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 21140
import collections
N = int(input())
S = [input() for i in range(N)]

c = collections.Counter(S)
value,count = zip(*c.most_common())

s = sorted(value)
ans = []
if len(set(count)) == 1 :
    for i in s:
        print(i)
else: 
    for i in range(len(value)):
        ans.append(value[i])
        if count[i] > count[i+1]:
            [print(i) for i in sorted(ans)]
            exit()

Measured memory_bytes: 59508
s = input()
s_l = []
s_dif_abs = []
for i in range(len(s)-2):
    tmp = s[i]+s[i+1]+s[i+2]
    s_l.append(tmp)

for j in range(len(s_l)):
    s_dif_abs.append(abs(753-int(s_l[j])))

print(min(s_dif_abs))

Measured memory_bytes: 3060
n = int(input())
lst = list(map(int, input().split()))
for i in range(n):
	key = lst[i]
	j = i-1
	while j>=0 and lst[j]>key:
		lst[j+1] = lst[j]
		j -= 1
	lst[j+1] = key
	print(" ".join(map(str,lst)))

Measured memory_bytes: 6724
#include <stdio.h>
int main(void) {
	int a, i, max, mini, n;
        long long int sum;
	max = -1000000;
	mini = 1000000;
	sum = 0;
	scanf("%d", &n);

	for (i = 1; i <= n; i = i + 1)
	{
		scanf("%d", &a);
		if (mini>a) mini = a;
		if (max<a) max = a;
		sum = sum + a;
	}
	printf("%d %d %lld\n", mini, max, sum);
	return 0;
}


Measured memory_bytes: 2116
// 2011/01/15 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int X, Y;
		cin >> X >> Y;
		if(X==0&&Y==0)
			break;

		if(X<Y){
			int tmp = X;
			X = Y;
			Y = tmp;
		}

		int cnt = 0;
		do{
			X = X%Y;

			int tmp = X;
			X = Y;
			Y = tmp;

			cnt++;
		}while(Y!=0);

		cout << X << ' ' << cnt << endl;
	}

	return 0;
}

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


int main(){
  
  ll a;
  double b;
  cin>>a>>b;
  long long b100 = round(b*100);
  cout<<a*(b100)/100<<endl;
}


Measured memory_bytes: 3776
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    flag = True
    for j in range(m):
        cnt = 0
        for k in range(1, len(ks[j])):
            if (i >> (ks[j][k]-1)) & 1:
                cnt += 1
        if cnt % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Measured memory_bytes: 9164
def main():
    s = input()

    rs, ls = 0, 0
    prev = ''
    A = [0] * len(s)
    for ci, c in enumerate(s):
        if c == 'R':
            if prev == 'l':
                A[ci - ls - 1] = (rs + 1)//2 + ls//2
                A[ci - ls] = rs//2 + (ls + 1)//2
                rs, ls = 0, 0

            rs += 1
            prev = 'r'
        else:
            ls += 1
            prev = 'l'

    A[-ls - 1] = (rs + 1)//2 + ls//2
    A[-ls] = rs//2 + (ls + 1)//2

    print(*A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 47292
#include <iostream>

using namespace std;

static int N;

bool search(int cost, int diff, int level) {
    if (level == 5)
        return (N - cost) % (100 + diff) == 0;

    for (int i = 0; i * (100 + diff) + cost <= N; i++) {
        bool a = search(i * (100 + diff) + cost, diff + 1, level + 1);
        if (a) return true;
    }

    return false;
}

int main() {
    cin >> N;

    cout<<search(0,0,0)<<endl;

    return 0;
}

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

ll gcd(ll a, ll b){
  if(a < b) return gcd(b, a);
  ll r = a % b;
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int main(){
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a, b);
  if(g == 1){
  	cout << 1 << endl;
    return 0;
  }
  ll d = 2;
  ll cnt = 1;
  while(d <= sqrt(g)){
  	if(g % d == 0){
      g /= d;
      while(g % d == 0){
      	g /= d;
      }
      cnt++;
    }
    d++;
  }
  if(g != 1) cnt++;
  cout << cnt << endl;
}

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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define MSGF(x, n) MSG(fixed << setprecision(n) << x)
#define END(x) cout << x << endl; exit(0);
#define IPT(v, n) REP(i, 0, n){ cin >> v[i]; }
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<ull> vul;
typedef vector<vector<ull>> vvul;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
const static ll INF = 1LL << 30;

ll a, b, c, d, k, l, m, n, h, w, q, x, y;
string s, t;

ll ans = 0;
ll sum = 0;
ll cnt = 0;
ll cur = 0;
ll tmp = 0;
ll mini = INF;
ll maxi = 0;

double ave = 0.0;

ll mod_pow(ll base, ll power) {
    if (power == 0) return 1;
    if (power == 1) return base % MOD;
    if (power % 2 == 0) return ((mod_pow(base % MOD, (power / 2)) % MOD) * (mod_pow(base, (power / 2)) % MOD)) % MOD;
    return (base % MOD * (mod_pow(base % MOD, power - 1) % MOD)) % MOD;
}

ll mod_fact(ll number) {
    ll ret = 1;
    ll count = 1;
    while (count <= number) {
        ret *= (count % MOD);
        ret %= MOD;
        count++;
    }
    return ret % MOD;
}

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

int main() {
    cin >> n;
    vl a(n + 10);
    NREP() {
        cin >> a[i];
        if (i == 0) {
            sum += abs(a[i]);
        } else {
            sum += abs(a[i] - a[i - 1]);
        }
    }
    sum += abs(a[n - 1]);
    a[n] = 0;

    NREP() {
        if (i == 0) {
            MSG(sum - abs(a[i]) - abs(a[i] - a[i + 1]) + abs(a[i + 1]))
        } else {
            MSG(sum - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1]))
        }
    }
}


Measured memory_bytes: 2048