akhauriyash/Code-Regression huggingface dataset:
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def lcm(a,b):
	p = a*b
	g = gcd(a,b);
	return p//g
MOD = int(10**9+7)
n = int(input())
a = list(map(int,input().split()))
lc = a[0];
for i in range(1,n):
	lc = lcm(a[i],lc)
ans = 0
for i in range(n):
	ans += (lc//a[i])
print(ans%MOD)

Measured memory_bytes: 4084
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
    string a,b;
    cin>>a>>b;
    int num = std::stoi(a+b);
    bool flag=true;
    rep(i,10000){
        if(num==i*i){
            flag=false;
        }
    }
    if(flag){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}



Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 30;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)

int w, h, c;
int field[8][8];
int field2[8][8];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

void change(int from, int to){
  if(from == to) return ;
  queue<P> que;
  int cnt = 0;
  que.push(P(0, 0));
  field2[0][0] = to;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    int x = p.first;
    int y = p.second;
  
    for(int i = 0; i < 4; i++){
      int x2 = x + dx[i];
      int y2 = y + dy[i];
      if(0 <= x2 && x2 < w && 0 <= y2 && y2 < h && field2[y2][x2] == from){
	field2[y2][x2] = to;
	que.push(P(x2, y2));
      }
    }
  }
}


int cntr(int c){
  int cnt = 1;
  queue<P> que;
  bool used[8][8];
  memset(used, false, sizeof(used));
  que.push(P(0, 0));
  used[0][0] = true;
  
  
  while(!que.empty()){
    P p = que.front();
    que.pop();
    int x = p.first;
    int y= p.second;
    for(int i = 0; i < 4; i++){
      int x2 = x + dx[i];
      int y2 = y + dy[i];
      if(0 <= x2 && x2 < w && 0 <= y2 && y2 < h){
	if(field2[y2][x2] == c && !used[y2][x2]){
	  cnt++;
	  used[y2][x2] = true;
	  que.push(P(x2, y2));
	}
      }
    }
  }
  
  return cnt;
}

void cop(){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      field2[i][j] = field[i][j];

    }

  }
}
int main(){
  while(cin >> h >> w >> c && (h || w || c)){
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
	cin >> field[i][j];

      }
    }
    int res = 0;
    for(int i = 1; i <= 6; i++){
      for(int j = 1; j <= 6; j++){
	for(int k = 1; k <= 6; k++){
	  for(int l = 1; l <= 6; l++){
	    cop();
	    change(field2[0][0], i);
	
	    change(field2[0][0], j);
	
	    change(field2[0][0], k);
	
	    change(field2[0][0], l);
	    //    cout << 4 << endl;
	    change(field2[0][0], c);
	    //	    cout << i << " " << j << " " << k << " " << l << endl;
	    res = max(res, cntr(c));
	  }		   
	}
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
#include<cstdlib>
#include<algorithm>

using namespace std;
#define pb push_back
#define mp make_pair
#define ls(x) (x << 1)
#define rs(x) (x<<1|1)
#define SZ(x) (int)(x).size()

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<LL, LL> pll;
typedef pair<bool, int> pbi;

const double eps = 1e-10;
const double PI = acos(-1.0);
//const double PI = 3.14159265358979323846264338327950288419716939937510
int dcmp(const double &x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; }
const int MOD = 1e9 + 7;
const int INF = 2147483647;
const double INF_d = 1e64;

template<class T>
T qmod(T a, T b){ T ret = 1; while (b){ if (b & 1) ret *= a; b >>= 1; a *= a; } return ret; }
template<class T>
T gcd(T a, T b){ return !b ? a : gcd(b, a % b); }
template<class T>
T ex_gcd(T a, T b, T &x, T &y){
    if (!b){ x = 1, y = 0; return a; }
    T t, ret;
    ret = ex_gcd(b, a % b, x, y);
    t = x, x = y, y = t - a / b * y;
    return ret;
}
template<class T>
T inv(T t, T p){ return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p; }

// head

const int N = 2e5 + 7;
struct node{
    int l, r, tag;
    LL val;
};

int n, m, op, x, y, w;
node T[N << 2];

void build(int rt, int l, int r){
    T[rt].l = l, T[rt].r = r, T[rt].val = 0, T[rt].tag = 1234;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
}

void push_down(int rt){
    if (T[rt].tag != 1234){
        T[ls(rt)].tag = T[rt].tag, T[rs(rt)].tag = T[rt].tag;
        T[ls(rt)].val = (LL)T[rt].tag * (T[ls(rt)].r - T[ls(rt)].l + 1);
        T[rs(rt)].val = (LL)T[rt].tag * (T[rs(rt)].r - T[rs(rt)].l + 1);
        T[rt].tag = 1234;
    }
}

void push_up(int rt){
    T[rt].val = T[ls(rt)].val + T[rs(rt)].val;
}

void update(int rt, int l, int r, int val){
    if (l > T[rt].r || r < T[rt].l) return;
    if (l <= T[rt].l && T[rt].r <= r){
        T[rt].val = (LL)val * (T[rt].r - T[rt].l + 1);
        T[rt].tag = val; return;
    }
    push_down(rt);
    int mid = (T[rt].l + T[rt].r) >> 1;
    if (l <= mid) update(ls(rt), l, r, val);
    if (r > mid) update(rs(rt), l, r, val);
    push_up(rt);
}

LL query(int rt, int l, int r){
    if (l > T[rt].r || T[rt].l > r) return 0;
    if (l <= T[rt].l && T[rt].r <= r) return T[rt].val;
    push_down(rt);
    LL ret = 0;
    int mid = (T[rt].l + T[rt].r) >> 1;
    if (l <= mid) ret += query(ls(rt), l, r);
    if (r > mid) ret += query(rs(rt), l, r);
    return ret;
}

int main(){
    //freopen("1.in", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for (int i = 0; i < m; i++){
        scanf("%d", &op);
        if (!op){
            scanf("%d%d%d", &x, &y, &w); x++, y++;
            update(1, x, y, w);
        }
        else{
            scanf("%d%d", &x, &y); x++, y++;
            printf("%lld\n", query(1, x, y));
        }
    }
    return 0;
}



Measured memory_bytes: 9368
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#define ll long long
#define inf  999999999
#define pa pair<int,int>

using namespace std;


struct segsum{
	//       1
	//   2        3
	// 4   5   6    7
	
	
	private:
	public:
	
	// (1<<15)=32768
	// 1<<16 = 65536
	// 1<<17 = 131072
	// 1<<18 = 262144
	
	int cor=(1<<17);
	
	vector<int> vec;

	void shoki1(){
		vec.resize(2*cor+3, 0);

	}
		void shoki2(){
			
		}
		
	void rangeadd(int a,int b,int w, int k=1,int l=0,int r=-3){
		//[a,b)に w加算
	if(r<0) r=cor;
		
		if(a<=l && r<=b){
			vec[k]+=w;
			return ;
		}
		if(r<=a || b<=l){
			return ;
		}
		
		rangeadd(a,b,w,k*2,l,(l+r)/2);
		rangeadd(a,b,w,k*2+1,(l+r)/2,r);
		return ;
	}
	
	// [a,b)
	// k-th node
	// k no kukanha [l,r)
	int getnum(int x){
		x+=cor;
		int ans=0;
		while(1){
			if(x==0) return ans;
			ans+=vec[x];
			
			x/=2;
		}
	}
	
};


int main(){
segsum SE;
	
	SE.shoki1();
//	for(int i=0;i<SE.cor;i++){
//		SE.vec[i+SE.cor]=i;
//	}
	SE.shoki2();
	
	
	int n,q;
	cin>>n>>q;
	
	for(int i=0;i<q;i++){
	int d,a,b,c;
		cin>>a;
		
		if(a==0){
			cin>>b>>c>>d;
			
			SE.rangeadd(b,c+1,d);
		}
		else{
			cin>>d;
			
			cout<<SE.getnum(d)<<endl;
		}
	}
	return 0;
}





Measured memory_bytes: 3704
/*
    AUTHOR : TANMAY SINHA
    INORMATION TECHNOLOGY
    BIT MESRA ,RANCHI
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ld long double
#define ull unsigned long long int
#define ll long long int
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define mp make_pair
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define rep(j,L,R) for(j=L;j<R;j++)
#define per(i,L,R) for(i=L;i>= R;i--)
#define all(con) (con).begin(),(con).end()
#define fi first
#define se second
#define foreach(iter,con) for(auto iter=(con).begin(); iter!=(con).end(); iter++)
#define DEBUG
#ifdef DEBUG
#define deb2(args...) {dbg,args; cerr<<endl;}
#else
#define deb2(args...)
#endif
struct debb{template<typename T> debb& operator,(const T &v){cerr<<v<<" ";return *this;}}dbg;
#define deb1(args...) do {cerr << #args << " : "; dbg,args; cerr << "\n";} while(0)
#define printa(a,L,R) rep(i,L,R) cout << a[i] <<' ';cout<<"\n";
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
template<typename T>T gcd(T a,T b){if(b==0)return a;else return gcd(b,a%b);}
template<typename T>T lcm(T a,T b){return a/gcd(a,b)*b;}
ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1)res=((res%p)*(x%p))%p;y=y>>1;x=(x*x)%p;}return res;}
ll power1(ll x,ll y){ll res=1;while(y>0){if(y&1)res=(res*x);y=y>>1;x=x*x;}return res;}
const ll INF = 1e18l+10;
const ll N = 1e5+10;

vl adj[N];
vector<bool> vis;
ll dp[N];
ll dfs(ll n)
{
    vis[n]=true;
    for(auto i = adj[n].begin();i!=adj[n].end();i++)
    {
        if(!vis[*i])
            dfs(*i);
        dp[n]=max(dp[n],1+dp[*i]);
    }
}

int main()
{
   SPEED
   ll n,m,i,j,a,b;
   cin>>n>>m;
   vis.assign(n+1,false);
   for(i=0;i<m;i++)
   {
       cin>>a>>b;
       adj[a].pb(b);
   }
   for(i=1;i<=n;i++)
    if(!vis[i])
    dfs(i);
    ll ans =0;
   for(i=1;i<=n;i++)
    ans = max(ans,dp[i]);
    cout<<ans;
}







Measured memory_bytes: 8576
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> A;
    rep (i, N) {
        ll a;
        cin >> a;
        A.pb(a);
    }
    sort(all(A));
    if (N % 2 == 0) {
        ll a = 1;
        rep (i, N / 2) {
            if (A[i * 2] != a || A[i * 2 + 1] != a) {
                cout << 0 << endl;
                return 0;
            }
            a += 2;
        }
    } else {
        if (A[0] != 0) {
            cout << 0 << endl;
            return 0;
        }
        ll a = 2;
        rep (i, N / 2) {
            if (A[(i + 1) * 2 - 1] != a || A[(i + 1) * 2] != a) {
                cout << 0 << endl;
                return 0;
            }
            a += 2;
        }
    }
    N /= 2;
    ll ans = 1;
    rep (i, N) {
        ans *= 2;
        ans %= mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1400
#include <stdio.h>
#include <math.h>

struct point{
	double x,y;
}; 

void koch(int n,struct point a,struct point b)
{
	struct point s,t,u;
	double th=M_PI*60.0/180.0;
	if(n==0)
	{
		return;
	}
	s.x=(2.0*a.x+1.0*b.x)/3.0;
	s.y=(2.0*a.y+1.0*b.y)/3.0;
	t.x=(1.0*a.x+2.0*b.x)/3.0;
	t.y=(1.0*a.y+2.0*b.y)/3.0;
	u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;//ラジアン表記で入力
	u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;//ラジアン表記で入力
	koch(n-1,a,s);
	printf("%.8f %.8f\n",s.x,s.y); 
	koch(n-1,s,u);
	printf("%.8f %.8f\n",u.x,u.y); 
	koch(n-1,u,t);
	printf("%.8f %.8f\n",t.x,t.y); 
	koch(n-1,t,b);
}

int main()
{
	struct point a,b;
	int n;
	scanf("%d",&n);
	a.x=0;
	a.y=0;
	b.x=100;
	b.y=0;
	printf("%.8f %.8f\n",a.x,a.y);
	koch(n,a,b);
	printf("%.8f %.8f\n",b.x,b.y);
	return 0;
}



Measured memory_bytes: 2108
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const ll inf = 4523372036854775807;
const ll Mod = 1000000007;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct S {//辺の情報を入れる変数
	int from, to, cost;
};
struct H {
	int x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(ld a, ld b, ld c, ld d) {
	return sqrt(pow(a - c, 2) + pow(b - d, 2));
}//rad＝座標上の2点間の距離
int ari(int a, int b, int c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int n, z, w, a[2001];
signed main() {
	cin >> n >> z >> w;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int sum2 = inf;
		if (i == n - 1) {
			sum2 = abs(w - a[n - 1]);
		}
		for (int j = i + 1; j < n; j++) {
			if (j == n - 1)
				sum2 = min(sum2, abs(a[j] - a[i]));
			else
				sum2 = min(sum2, abs(a[n - 1] - a[j]));
		}
		sum = max(sum, sum2);
	}
	cout << sum << endl;
	getchar(); getchar();
}

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

int main(){
	while(1){
		int n;
		cin >> n;
		if(n==0) break;
		
		vector<char> conv(128);
		for(int i=0; i<128; i++) conv[i]=i;
		for(int i=0; i<n; i++){
			char a,b;
			cin >> a >> b;
			conv[a] = b;
		}
		
		int m;
		cin >> m;
		string ret="";
		for(int i=0; i<m; i++){
			char a;
			cin >> a;
			ret += conv[a];
		}
		cout << ret << endl;
	}
    return 0;
}

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

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))
#define Rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define pb push_back

const int inf = 999999999;
const int mod = 1000000007;

int main(){
	int sum = 0; int a[3][3];
	Rep(i, 3){
		Rep(j, 3){
			cin >> a[i][j];
		}
	}
	bool flag = true;
	Rep(i, 2){
		Rep(j, 2){
			if(a[i][j+1] - a[i][j] != a[i+1][j+1] - a[i+1][j] 
				|| a[i+1][j] - a[i][j] != a[i+1][j+1] - a[i][j+1]){
					flag = false;
			}
		}
		
	}
	if(flag){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
//2013/11/15(Fri)

#include <iostream>
using namespace std;
int main()
{
	
	while(true){
		int n;
		int a,b,c;
		int INF = -1;
		int time[10][10];
		int m=0;
		int min=0,imin=0;
		cin >> n;
		if(n==0)
			break;
		for(int i=0; i<10; i++)
			for(int j=0; j<10; j++){
				if(i==j)
					time[i][j] = 0;
		
				else
					time[i][j] = INF;
			}

		for(int i=0; i<n; i++){
			cin >> a >> b >> c;
			time[a][b] = c;
			time[b][a] = c;
			if(m<a)
				m=a;
			if(m<b)
				m=b;
		}


		for(int h=0; h<m+1; h++)
			for(int i=0; i<m+1; i++)
				for(int j=0; j<m+1; j++)
					if(time[i][h]==INF||time[h][j]==INF)
                        continue;
                    else if(time[i][j]==INF)
                        time[i][j] = time[i][h]+time[h][j];
                    else if(time[i][j]>time[i][h]+time[h][j])
                        time[i][j] = time[i][h]+time[h][j];

									
		
		for(int i=1; i<m+1; i++)
			min += time[0][i];


		for(int i=1; i<m+1; i++){
            int sum = 0;
            for(int j=0; j<m+1; j++)
                sum += time[i][j];
            if(sum<min){
                imin = i;
                min = sum;
            }
        }

		cout << imin << ' ' << min << endl;
	}
	return 0;
	
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(2e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

struct SegmentTree {
    int N;
    vector<ll> node;
    const ll INF = LLINF;

    void init(int siz){
        N = 1;
        while (N < siz) N *= 2;
        node.resize(2*N-1, 0);
    }
    void build(vector<ll> &dat){
        for(int i=0; i<dat.size(); i++){
            node[i+N-1] = dat[i];
        }
        for(int i=N-2; i>=0; i--){
            node[i] = max(node[2*i+1], node[2*i+2]);
        }
    }
    void update(int k, ll x) {
        k += N - 1;
        node[k] = x;
        while (k > 0) {
            k = (k-1)/2;
            node[k] = max(node[k*2+1], node[k*2+2]);
        }
    }
    ll getMax(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -INF;
        if (a <= l && r <= b) return node[k];
        ll vl = getMax(a, b, k*2+1, l, (l+r)/2);
        ll vr = getMax(a, b, k*2+2, (l+r)/2, r);
        return max(vl, vr);
    }
    ll getMax(int a, int b) {return getMax(a, b, 0, 0, N);}
};

int n;
vector<ll> a, h;

int main() {
    cin >> n;
    SegmentTree rmq;
    rmq.init(n);
    a.resize(n);
    h.resize(n);
    REP(i,n) cin >> h[i];
    REP(i,n) cin >> a[i];
    REP(i,n){
        ll tmp = rmq.getMax(0,h[i]) + a[i];
        rmq.update(h[i]-1, tmp);
    }
    cout << rmq.getMax(0,n) << endl;
    return 0;
}

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

#define lli long long int
#define INF 1000000


lli n, k;
lli dp[INF];

lli h[INF];

lli f(int x) {
    if (x >= n) return 1000000000000;
    if (x == n-1)
        return 0;
    if (dp[x] != -1) return dp[x];

    lli ans = 1000000000000;
    for (int i = 1; i <= k; i++) {
            if (x + i >= n) break;
        ans = min(ans, abs(h[x] - h[x + i]) + f(x + i));
    }

    return dp[x] = ans;
}
int main()
{
    dp[0] = -1;
    for (int i = 1; i < INF; i++) {
        dp[i] = -1;
    }
    cin>>n>>k;
    for(int i=0; i<n; i++)
        cin>>h[i];
    lli ans = f(0);
    cout << ans << "\n";
}


Measured memory_bytes: 15232
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000000



int main(){
	
	int N,M;
	cin>>N>>M;
	
	vector<vector<int>> E(N,vector<int>());
	vector<vector<int>> p = E;
	vector<int> cnt(N,0);
	
	for(int i=0;i<N+M-1;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		cnt[v] ++;
		E[u].push_back(v);
		p[v].push_back(u);
	}
	
	queue<int> Q;
	vector<int> sorted;
	
	for(int i=0;i<N;i++){
		if(cnt[i]==0){
			Q.push(i);
			sorted.push_back(i);
		}
	}
	
	while(Q.size()!=0){
		int u = Q.front();
		Q.pop();
		for(int i=0;i<E[u].size();i++){
			int v = E[u][i];
			cnt[v]--;
			if(cnt[v]==0){
				Q.push(v);
				sorted.push_back(v);
			}
		}
	}
	
	vector<int> ind(N);
	for(int i=0;i<N;i++){
		ind[sorted[i]]=i;
	}
	
	vector<int> ans(N);
	for(int i=0;i<N;i++){
		int id = -1;
		int maxi = -1;
		for(int j=0;j<p[i].size();j++){
			int v = p[i][j];
			if(ind[v]>maxi){
				maxi = ind[v];
				id = v;
			}
		}
		ans[i] = id;
	}
	
	for(int i=0;i<N;i++){
		cout<<ans[i]+1<<endl;
	}
	
	
	
	return 0;
}

Measured memory_bytes: 13564
N=int(input())
A=list(map(int,input().split()))
ansa=sorted(A)
ans=0
for i in range(N-1):
  if ans==0:
    if A[i]>A[i+1]:
      ch=A[i]
      m=i
      ans=ans+1
  elif ans==1:
    if A[i]>A[i+1]:
      n=A[i+1]
      A[i+1]=ch
      A[m]=n
if A==ansa:
  print("YES")
else:
  print("NO")
    


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/15  Problem: 070_abc_d / Link: https://abc070.contest.atcoder.jp/tasks/abc070_d?lang=en  ----- */
/* ------問題------

N 頂点の木が与えられます。
木とはグラフの一種であり、頂点の数を N とすると、辺の数が N−1 本である閉路のない連結グラフです。
i(1≦i≦N−1) 番目の辺は 頂点 ai と 頂点 bi を距離 ci で結びます。

また、Q 個の質問クエリと整数 K が与えられます。
j(1≦j≦Q) 番目の質問クエリでは、頂点 xj から 頂点 K を経由しつつ、頂点 yj まで移動する場合の最短経路の距離を求めてください。

-----問題ここまで----- */
/* -----解説等-----

要はKからの距離を求めてと書いてあるので、d[K->x] + d[K->y]がわかれば良い。
一回ダイクストラすればいいよね

----解説ここまで---- */
void D(vector<vector<PLL>>& G, VL&dist, int s, int t) {

	const int INF = INT_MAX;
	const long long INIT_NUM = LLONG_MAX / 10;// dist の型
#define DijkV 200020

	priority_queue<PLL, vector<PLL>, greater<PLL>> que; //優先度付きqueue 降順(距離、頂点)
	que.push(PLL(0LL, s)); // push(距離,頂点)

	while (!que.empty()) {
		PLL p = que.top(); que.pop(); //queueのデータ構造
		int v; /* 頂点*/ long long d; /* 頂点vまでの距離 */
		tie(d, v) = p;

		if (d > dist[v]) continue; //最適でないならば考慮しない

		FOR(i, 0, (int)G[v].size()) { //頂点vからはi本の辺が存在
			int nv = G[v][i].first; // v->nv
			if (dist[nv] > dist[v] + G[v][i].second) {
				dist[nv] = dist[v] + G[v][i].second;
				que.push(PLL(dist[nv], nv)); //push(距離,頂点) 
			}
		}
	}

#undef DijkV
}

LL N;

LL ans = 0LL;

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

	cin >> N;
	vector<vector<PLL>> G(N);
	FOR(i, 0, N-1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		G[a].push_back(PLL(b, c));
		G[b].push_back(PLL(a, c));
	}

	int Q, K; cin >> Q >> K;
	K--;
	VL dist(N, LINF);
	dist[K] = 0;

	D(G, dist, K,N);
	FOR(i, 0, Q) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		ans = dist[x] + dist[y];
		cout << ans << "\n";
	}

	return 0;
}


Measured memory_bytes: 11120
// 753

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int x;
    cin >> x;
    if (x == 7 || x == 5 || x == 3) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF int(1e9+1)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
ll A,B,C,D,N;
int main(void){
    scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&D,&N);
    B=min(B,2*A);
    C=min(C,2*B);
    D=min(D,2*C);
    printf("%lld\n",N/2*D+N%2*C);
    return 0;
}


Measured memory_bytes: 764
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,m,l,q,s,t,a,b,c,d[305][305]={},T[305][305]={};
  cin >> n >> m >> l;
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(i!=j) {
        d[i][j]=INF,T[i][j]=INF;
      }
    }
  }
  for(int i=0; i<m; i++) {
    cin >> a >> b >> c;
    a--,b--;
    d[a][b]=d[b][a]=c;
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      for(int k=0; k<n; k++) {
        if(i!=j&&i!=k&&j!=k) {
          d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
        }
      }
    }
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(i!=j&&d[i][j]<=l) {
        T[i][j]=1;
      }
    }
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      for(int k=0; k<n; k++) {
        if(i!=j&&i!=k&&j!=k) {
          T[j][k]=min(T[j][k],T[j][i]+T[i][k]);
        }
      }
    }
  }
  cin >> q;
  while(q--) {
    cin >> s >> t;
    s--,t--;
    cout << (T[s][t]==INF?-1:T[s][t]-1) << endl;
  }
}



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

int a, b, now = 1, bb;

int main() {
  cin >> a >> b;
  bb = b;
  while(bb > 0) {
    now *= 10;
    bb /= 10;
  }
  a = a * now + b;
  for(int i = 1; i <= a; ++i) {
    if(i * i == a) {
      cout << "Yes" << endl;
      break;
    }
    if(i == a) cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String A = sc.next();
		String B = sc.next();

		System.out.println(A.compareTo(B) < 0 ? "<" : (A.compareTo(B) == 0 ? "=" : ">"));

	}
}


Measured memory_bytes: 21460
/***** TheAnshul *****/

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vii         vector<pair<ll int, ll int>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
#define N  3005
ll n;
ll dp[N][N];
// bool dp1[N][N];
ll a[N];
ll fun(ll i,ll j)
{
	if(i==j)
	{
		return a[i];
	}
	if(dp[i][j]!=LLONG_MAX)
	{
		return dp[i][j];
	}
	ll v1,v2;
	dp[i][j]=max(-fun(i+1,j)+a[i],-fun(i,j-1)+a[j]);
	return dp[i][j];
}
void solve()
{
	cin>>n;
	rep(i,1,n+1)
	cin>>a[i];
	rep(i,1,n+1)
	{
		rep(j,1,n+1)
		{
			dp[i][j]=LLONG_MAX;
		}
	}
	cout<<fun(1,n);
	// ll x=0,y=0,l=1,r=n,i=0;
	// while(l!=r)
	// {
	// 	cout<<dp1[l][r];
	// 	if(dp1[l][r])
	// 	{
	// 		if(i&1)
	// 			y+=a[l];
	// 		else
	// 			x+=a[l];
	// 		l++;
	// 	}
	// 	else
	// 	{
	// 		if(i&1)
	// 			y+=a[r];
	// 		else
	// 			x+=a[r];
	// 		r--;	
	// 	}
	// 	i++;
	// }
	// if(i&1)
	// {
	// 	y+=a[l];
	// }
	// else
	// {
	// 	x+=a[l];
	// }
	// cout<<x-y;
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	time
	return 0;
}

Measured memory_bytes: 70912
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL; 

 

//ここから書き始める
int main(int argc, char const *argv[])
{
	int X,Y;
	cin >> X >> Y;

	cout << X + Y/2 << endl;


}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a, b;
    cin >> a >> b ;
    cout << (a*b % 2 == 0 ? "No" : "Yes") << endl;
    return 0;
}


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

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

template<typename T, typename U>
istream &operator >> (istream &istr, pair<T,U> &p){
    istr >> p.first >> p.second;
    return istr;
}

template<typename T>
ostream &operator << (ostream &ostr, vector<T> &v){
    if(!v.empty()){
        ostr << v.front();
        for(auto itr = ++v.begin(); itr != v.end(); itr++)
            // ostr << *itr;
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream &operator << (ostream &ostr, pair<T,U> &p){
    // ostr << p.first << p.second;
    // ostr << p.first << ", " << p.second;
    ostr << "(" << p.first << ", " << p.second << ")";
    return ostr;
}

template<typename T>
ostream &operator << (ostream &ostr, vector<vector<T>> &vv){
    if(!vv.empty()){
        ostr << vv.front();
        for(auto itr = ++vv.begin(); itr != vv.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream &operator << (ostream &ostr, vector<pair<T,U>> &vp){
    if(!vp.empty()){
        ostr << vp.front();
        for(auto itr = ++vp.begin(); itr != vp.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<double> vd;
// vll v(n); v[i]=x;
typedef vector<vll> vvll;
typedef vector<vc> vvc;
typedef vector<vd> vvd;
// vvll v(m,vll(n)); v[i][j]=x;
typedef pair<ll,ll> pll;
typedef pair<double,double> pd;
typedef vector<pll> vpll;
typedef vector<pd> vpd;
// vpll v(n); v[i]=make_pair(x,y); v[i].first/second;
// v.front() : v[0]
// v.back()  : v[v.size()-1]

#define PI 3.1415926535897932
#define EPS 1e-12
#define INF ((ll)1e+12)
#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<=(b); i++)
#define FORR(i,a,b) for(ll i=(b); i>=(a); i--)
#define fix(x) cout << fixed << setprecision(x)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()

template<typename T> T sum(vector<T> &v){return accumulate(all(v), (T)0);}
template<typename T> inline void sort(vector<T> &v){sort(all(v));}
template<typename T> inline void rsort(vector<T> &v){sort(all(v), greater<T>());}
template<typename T> inline void chmin(T &a, T b){if(a>b) a=b;}
template<typename T> inline void chmax(T &a, T b){if(a<b) a=b;}

int main(){
    ll n, k, ans = 0, p = 0, mod = 0;
    cin >> n >> k;
    vll a(n), b(n, 0);
    cin >> a;
    REP(i,n) a[i]--;
    b[0] = 0;

    REP(i,n){
        p = a[p];
        b[p] = i+1;
        k--;
        if(!k){
            cout << p+1 << endl;
            return 0;
        }
        if(a[p] == 0 || b[a[p]] > 0){
            mod = b[p] - b[a[p]] + 1;
            break;
        }
    }
    k %= mod;
    REP(i,k) p = a[p];
    cout << p+1 << endl;
    return 0;
}


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

const int inf=1e9+5;
int main () {
    int n;
    cin>>n;
    vector<int> v(n);
    for(int &i:v)cin>>i;
    
    vector<int> dp(n,inf);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j:{i+1,i+2})
        {
            if(j<n){
            dp[j]=min(dp[j],dp[i]+abs(v[i]-v[j]));
            }
        }
    }
   
      cout<<dp[n-1];
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
 int a,b,r,ans,a1,b1;
  double c;
  while(scanf("%d %d",&a,&b)!=EOF){

  a1=a,b1=b;

  while(1){
    r=a%b;
    if(r==0){
      ans=b;
      break;
    }else{
      a=b;
      b=r;
    }
  }

  
  c=(double)(a1)*(double)(b1)/(double)(ans);




  printf("%d %.0f\n",ans,c);
  }
  return 0;
}

Measured memory_bytes: 632
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
ll n,m;
double x,y;
int main()
{
    ll f=0,res=-1;
    scanf("%lld",&n);
    for(ll i=1;i;i++)
    {
        double temp=i*1.08;
        if((ll)temp==n)
        {
            res=i;
            break;
        }
        else if((ll)temp>n) break;
    }
    if(res==-1ll) printf(":(\n");
    else printf("%lld\n",res);
    return 0;
}

/**

**/



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int a[100][100];
int n;
int tmp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin >> n,n){
		int x[100];
		rep(i,100) x[i] = 0;
		int sum;
		rep(i,n){
			sum = 0;
			rep(j,n){
				cin >> a[i][j];
				tmp = 10000;
				rep(k,4){
					if(a[i][j]/tmp!=0) break;
					cout << " ";
					tmp /= 10;
				}
				cout << a[i][j];
				sum += a[i][j];
				x[j] += a[i][j];
			}
			tmp = 10000;
			rep(k,4){
				if(sum/tmp!=0) break;
				cout << " ";
				tmp /= 10;
			}
			cout << sum << endl;
		}
		sum = 0;
		rep(i,n){
			sum += x[i];
			tmp = 10000;
			rep(k,4){
				if(x[i]/tmp!=0) break;
				cout << " ";
				tmp /= 10;
			}
			cout << x[i];
		}
		tmp = 10000;
		rep(k,4){
			if(sum/tmp!=0) break;
			cout << " ";
			tmp/=10;
		}
		cout << sum << endl;
	}
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define INF 1000000007
// cin.eof() 入力個数の問題
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    long long N;
    cin >> N;
    const auto &res = prime_factorize(N);
    map<long long, int> m;
    long long arr[200];
    arr[0]=0;
    for(int i=1;i<200;i++){
      arr[i]=arr[i-1]+i;
    }
    for (auto p : res) {
        for (int i = 0; i < p.second; ++i) m[p.first]++;
    }
    ll count=0;
    for(auto p:m){
      for(int i=1;i<200;i++){
        if(arr[i]>p.second){
          if(arr[i-1]==p.second){
            count+=i-1;
            break;
          }else
          {
            count+=i-1;
            break;
          }
          
        }
      }
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

int upper_bound(vector<int>& a, int x){
    int n = a.size();

    int lo = -1;
    int hi = n - 1;
    while(hi - lo > 1){
        int mid = (lo + hi) / 2;
        if(a[mid] >= x){
            hi = mid;
        }else{
            lo = mid;
        }
    }
    return a[hi];
}

int lower_bound(vector<int>& a, int x){
    int n = a.size();

    int lo = 0;
    int hi = n;
    while(hi - lo > 1){
        int mid = (lo + hi) / 2;
        if(a[mid] <= x){
            lo = mid;
        }else{
            hi = mid;
        }
    }
    return a[lo];
}

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

    int a, b, q;
    cin >> a >> b >> q;
    vector<int> s(a+2), t(b+2);
    rep(i, a) cin >> s[i+1];
    rep(i, b) cin >> t[i+1];
    s[0] = t[0] = -INF;
    s[a+1] = t[b+1] = INF;

    rep(i, q){
        int x;
        cin >> x;

        int sH = upper_bound(s, x);
        int sL = lower_bound(s, x);
        int tH = upper_bound(t, x);
        int tL = lower_bound(t, x);

        int ans = INF;
        ans = min(ans, max(sH, tH) - x);
        ans = min(ans, x - min(sL, tL));
        ans = min(ans, sH * 2 - x - tL);
        ans = min(ans, tH * 2 - x - sL);
        ans = min(ans, sH + x - tL * 2);
        ans = min(ans, tH + x - sL * 2);
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 2944
class DisjointSet 
	def initialize()
		@rank = []
		@p = []
	end

	def initialize(size)
		@rank = Array.new(size){0}
		@p = Array.new(size){0}

		size.times do |i|
			@p[i] = i
		end
	end

	def same(x, y)
		return findSet(x) == findSet(y)
	end

	def unite(x, y)
		link(findSet(x), findSet(y))
	end

	def link(x, y)
		if @rank[x] > @rank[y]
			@p[y] = x
		else
			@p[x] = y
			@rank[y] += 1 if @rank[x] == @rank[y]
		end
	end

	def findSet(x)
		@p[x] = findSet(@p[x]) unless x == @p[x] 
		return @p[x]
	end

end


n,q = gets.split.map(&:to_i)

ds = DisjointSet.new(n)

q.times do |i|
	t, a, b = gets.split.map(&:to_i)
	
	if t == 0
		ds.unite(a, b)
	elsif t == 1
		if ds.same(a, b)
			puts 1
		else
			puts 0
		end
	end
end

Measured memory_bytes: 8996
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#if __cplusplus >= 201103L
#include <chrono>
using namespace std::chrono;
#endif
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#ifdef LOCAL
#define prln(x) (cout << #x << ' ' << x << endl)
#define pr(x) (cout << #x << ' ' << x << ' ' )
#define prv(x) (cout << x << ' ')
#else
#define prln(x) 
#define pr(x)
#define prv(x)
#endif
#define clr(x) memset((x), 0, sizeof((x)))
#define clr1(x) memset((x), -1, sizeof((x)))
#define endl "\n"
#define pi acos(-1)
#define rep(i, st, ed) for (int i = (st); i <= (ed); ++i)
#define rep0(i, st, ed) for (int i = (st); i < (ed); ++i)
#define per0(i, st, ed) for (int i = (st); i > ed; --i)
#define per(i, st, ed) for (int i = (st); i >= ed; --i)
#define chmin(a, b) (a = a > b ? b : a)
#define chmax(a, b) (a = a < b ? b : a)
template<class T> void _sf(T &x) {cin >> x;}
void _sf(int &x) {scanf("%d", &x);}
void _sf(ll &x) {scanf("%lld", &x);}
void _sf(double &x) {scanf("%lf", &x);}
void _sf(char &x) {scanf(" %c", &x);}
void _sf(char *x) {scanf("%s", x);}
void sf() {}
template <class T, class...U> void sf(T & head, U&... tail) { _sf(head); sf(tail...);}
template<class T> void _out(const T &x) { cout << x; }
void _out(const int &x) { printf("%d", x); }
void _out(const ll &x) { printf("%lld", x); }
void _out(const double &x) { printf("%.16f", x); }
void _out(const char &x) { putchar(x); }
void _out(const char *x) { printf("%s", x); }
template<class T,class U> void _out(const pair<T,U> &x) {_out(x.F); putchar(' '); _out(x.S);}
template<class T> void _out(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _out(*i++)) if (i != x.cbegin()) putchar(' '); }
void out() {}
template<class T, class... U> void out(const T &head, const U &... tail) { _out(head); putchar(sizeof...(tail) ? ' ' : '\n'); out(tail...); }
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

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 * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll gao(ll n) 
{ 
	ll count = 0; 
	for (ll i = 5; n / i >= 1; i *= 5) 
		count += n / i; 

	return count; 
} 

int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    ll n;
    sf(n);
    if (n & 1) {
        out(0);
        return 0;
    }
    n /= 2;
    out(gao(n));
    return 0;
}

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

using namespace std;

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    int c[n], a[n][m];
    int allp = 1;
    for (int i = 0; i < n; i++)
    {
        allp *= 2;
        cin >> c[i];
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int tempp[m];
    int nedan = 0;
    int maxnedan = 0;
    int indexn;
    int ok = 0;
    for (int i = 0; i < allp; i++)
    {
        indexn = i;
        nedan = 0;
        ok = 0;

        for (int j = 0; j < m; j++)
        {
            tempp[j] = 0;
        }
        for (int j = 0; j < n; j++)
        {
            if (indexn % 2 == 1)
            {
                nedan += c[j];
                for (int k = 0; k < m; k++)
                {
                    tempp[k] += a[j][k];
                }
            }
            indexn = indexn / 2;
        }
        for (int j = 0; j < m; j++)
        {
            if (tempp[j] < x)
            {
                ok = -1;
            }
        }
        if (ok == -1)
        {
            continue;
        }
        else
        {
            if (nedan < maxnedan || maxnedan == 0)
            {
                maxnedan = nedan;
            }
        }
    }
    if (maxnedan == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << maxnedan << endl;
    }
}


Measured memory_bytes: 3636
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int N,C[501],S[501],F[501],t;
  cin >> N;
  REP(i,N-1){
    cin >> C[i] >> S[i] >> F[i];
  }
  REP(i,N-1){
    int d = S[i];
    for(int j=i;j<N-1;j++){
      d += C[j];
      if(j == N - 2)
        break;
      if(S[j+1] >= d){
        d = S[j+1];
      }else{
        d = F[j+1]*(d % F[j+1] == 0 ? (d/F[j+1]) : 1 + d/F[j+1]);
      }
    }
    cout << d << endl;
  }
  cout << 0 << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


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

int main()
{
	while(1){
		vector<vector<int> > all;
		bool endflg = false;
		vector<int> vbuf = vector<int>(13, 0);
		all.push_back(vbuf);
		for(int i=0; i<8; i++){
			string buf;
			if(!(cin>>buf)) endflg = true;
			if(endflg) break;

			vector<int> vb;
			vb.push_back(0);
			for(int j=0; j<12; j++){
				if(j<8) vb.push_back(buf[j]-'0');
				else    vb.push_back(0);
			}
			all.push_back(vb);
		}
		if(endflg) break;
		for(int i=0; i<4; i++){
			all.push_back(vbuf);
		}

		/*
		for(int i=0; i<all.size(); i++){
			for(int j=0; j<all[i].size(); j++){
				cout<<all[i][j];
			}
			cout<<endl;
		}
		cout<<endl;
		*/

		string ans = "NG";
		for(int i=1; i<9; i++){
			bool breakflg = false;
			for(int j=1; j<9; j++){
				if(all[i][j]==1){
					if(all[i][j+1]&&all[i+1][j]&&all[i+1][j+1]){
						ans = "A";
					} else if(all[i+1][j]&&all[i+2][j]&&all[i+3][j]){
						ans = "B";
					} else if(all[i][j+1]&&all[i][j+2]&&all[i][j+3]){
						ans = "C";
					} else if(all[i+1][j]&&all[i+1][j-1]&&all[i+2][j-1]){
						ans = "D";
					} else if(all[i][j+1]&&all[i+1][j+1]&&all[i+1][j+2]){
						ans = "E";
					} else if(all[i+1][j]&&all[i+1][j+1]&&all[i+2][j+1]){
						ans = "F";
					} else if(all[i][j+1]&&all[i+1][j-1]&&all[i+1][j]){
						ans = "G";
					}
					breakflg = true;
					break;
				}
			}
			if(breakflg) break;
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
char s[1000005];
int y[1000005];
int x[1000005][12];
int d, t;
int main() {
	scanf(" %s", s);
	while (s[d] != NULL)d++;
	for (int i = 0; i < d; i++) {
		y[d - 1 - i] = s[i] - '0';
	}
	for (int i = 0; i < d; i++) {
		if (y[i] > 5) {
			y[i] -= 10;
			y[i + 1]++;
		}
	}
	for (int i = 0; i <= d + 1; i++) {
		for (int j = 0; j < 12; j++) {
			x[i][j] = 100000000;
		}
	}
	x[0][y[0] + 5] = 0;
	for (int i = 0; i <= d; i++) {
		for (int j = 0; j < 12; j++) {
			if (j < 5) {
				t = 5 - j + x[i][j];
				if (x[i + 1][y[i + 1] + 5] > t)x[i + 1][y[i + 1] + 5] = t;
			}
			if (5 <= j && j < 11) {
				t = j - 5 + x[i][j];
				if (x[i + 1][y[i + 1] + 5] > t)x[i + 1][y[i + 1] + 5] = t;
			}
			if (j == 0) {
				t = 5 + x[i][j];
				if (x[i + 1][y[i + 1] + 4] > t)x[i + 1][y[i + 1] + 4] = t;
			}
			if (j == 10) {
				t = 5 + x[i][j];
				if (x[i + 1][y[i + 1] + 6] > t)x[i + 1][y[i + 1] + 6] = t;
			}
			if (j == 11) {
				t = 4 + x[i][j];
				if (x[i + 1][y[i + 1] + 6] > t)x[i + 1][y[i + 1] + 6] = t;
			}
		}
	}
	printf("%d\n", x[d + 1][5]);
}

Measured memory_bytes: 51968