akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s, t; cin >> s >> t;
  vector<int> pos[26];

  for(int i = 0; i < s.size(); i++) {
      pos[s[i] - 'a'].push_back(i);
  }
  long long cur = 0;
  long long full = 0;
  int n = t.size();
  for(int i = 0; i < t.size(); i++){
    //  cout << "Finding " << t[i] << endl;
      int v = t[i] - 'a';
      n = pos[v].size();
      int idx = lower_bound(pos[v].begin(), pos[v].end(), cur) - pos[v].begin();
    //   cout << "Found at" << idx << " " <<  pos[v][idx] << endl;
      if (idx == n) {
          if(cur == 0){
             
          }else  full+=1;
        //   cout << full <<endl;
          idx = lower_bound(pos[v].begin(), pos[v].end(), 0) - pos[v].begin();
          

          if(idx == n) {
              cout << -1;
              return 0;
          }
      }
      cur = pos[v][idx]+1;

  }

  cout << full*(int)s.size() + cur << endl;
}


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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for(int i = 0; i<s.size()-2; i++){
    if(s.at(i) == 'A' && s.at(i+1) == 'B' && s.at(i+2) == 'C')
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3588
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra() {
    int minv;
	int d[MAX], color[MAX];
	
	for(int i = 0; i < n; i++) {
		d[i] = INFTY;
		color[i] = WHITE;
	}
	
	d[0] = 0;
	color[0] =GRAY;	
    while(1) {
    	minv = INFTY;
    	int u = -1;
    	for(int i = 0; i < n; i++) {
	    	if(minv > d[i] && color[i] != BLACK) {
	    		u = i;
	    		minv = d[i];
	    	}
	    }
	    if(u == -1) break;
	    color[u] = BLACK;
	    for(int v = 0; v < n; v++) {
    		if(color[v] != BLACK && M[u][v] != INFTY) {
		    	if(d[v] > d[u] + M[u][v]) {
	    			d[v] = d[u] + M[u][v];
	    			color[v] = GRAY; 
	    		}
		    }
    	}
    }
    
    for(int i = 0; i < n; i++) {
    	cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
    }
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++ ) {
		for(int j = 0; j < MAX; j++) {
			M[i][j] = INFTY;
		}
	}
	
	int k, c, u, v;
	for(int i = 0; i < n; i++) {
		cin >> u >> k;
		for(int j = 0; j < k; j++) {
			cin >> v >> c;
			M[u][v] = c;
		}
	} 
	
	dijkstra();
	
	return 0;
} 

Measured memory_bytes: 3112
#include<iostream>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
int W, H, N;
vector<LL> sx, sy, x, y, rx, ry;
LL ansd = 1LL << 60, ansx, ansy;
int main(){
	cin >> W >> H >> N;
	for(int i = 0; i < N; i++){
		LL X, Y;
		cin >> X >> Y;
		x.push_back(X);
		rx.push_back(X);
		y.push_back(Y);
		ry.push_back(Y);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sx.push_back(x[N / 2 - 1]);
	sx.push_back(x[N / 2]);
	sy.push_back(y[N / 2 - 1]);
	sy.push_back(y[N / 2]);
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			LL sum = 0, maxd = 0;
			for(int k = 0; k < N; k++){
				sum += (abs(sx[i] - rx[k]) + abs(sy[j] - ry[k])) * 2;
				maxd = max(maxd, abs(sx[i] - rx[k]) + abs(sy[j] - ry[k]));
			}
			sum -= maxd;
			if(ansd > sum){
				ansd = sum;
				ansx = sx[i];
				ansy = sy[j];
			}
		}
	}
	cout << ansd << endl;
	cout << ansx << " " << ansy << endl;
	return 0;
}


Measured memory_bytes: 6264
#include<bits/stdc++.h>
#include<vector>
#include<string>
using namespace std;
#define l long long
#define pb push_back
#define mem(a,n) memset(a,n,sizeof(a))
#define find(v,n) find(v.begin(),v.end(),n)
#define sort1(v) sort(v.begin(),v.end())
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mod 998244353
#define reverse(s) reverse(s.begin(),s.end())
//#define pi pair<l,l> 
const double pi=3.141592653589793;
bool isprime(l n)
{
	for(l i=2;i<=n;i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}
/*bool fact(l n)
{
	vector<l> v;
	for(l i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			if(i%2==1||(n/i)%2==1)
			{
				return true;
			}
		}
	}
	return false;
}*/
l power(l a,l b)
{
	l ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=(ans*a)%mod;
		}
		b>>=1;
		a=(a%mod*a%mod)%mod;
	}
	return ans;
}//prefixsums
void frooty()
{
	l n;
	cin>>n;
	vector<l> v;
	l xo=0;
	for(l i=0;i<n;i++)
	{
		l a;
		cin>>a;
		xo^=a;
		v.pb(a);
	}
	for(l i=0;i<n;i++)
	{
		l in=xo^v[i];
		cout<<in<<" ";
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q=1;
//	cin>>q;
	while(q--)
	{
		frooty();
	}
}

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

using namespace std;

#define local
#ifdef local

template<class T>
void _E(T x) { cerr << x; }

void _E(double x) { cerr << fixed << setprecision(6) << x; }

void _E(string s) { cerr << "\"" << s << "\""; }

template<class A, class B>
void _E(pair<A, B> x) {
    cerr << '(';
    _E(x.first);
    cerr << ", ";
    _E(x.second);
    cerr << ")";
}

template<class T>
void _E(vector<T> x) {
    cerr << "[";
    for (auto it = x.begin(); it != x.end(); ++it) {
        if (it != x.begin()) cerr << ", ";
        _E(*it);
    }
    cerr << "]";
}

void ERR() {}

template<class A, class... B>
void ERR(A x, B... y) {
    _E(x);
    cerr << (sizeof...(y) ? ", " : " ");
    ERR(y...);
}

#define debug(x...) do { cerr << "{ "#x" } -> { "; ERR(x); cerr << "}" << endl; } while(false)
#else
#define debug(...) 114514.1919810
#endif
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f3f
#define ll long long
#define db long double
#define eps 1e-3
#define bin(x) cerr << bitset<10>(x) << endl
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define endl "\n"
const ll mod = 1e9 + 7;
const ll maxn = 2e5 + 10;
const db pi = acos(-1.0);

ll qpow(ll a, ll b) {
    ll ret = 1;
    for (; b; a = a * a % mod, b >>= 1) {
        if (b & 1) {
            ret = ret * a % mod;
        }
    }
    return ret;
}

vector<ll> f(maxn), invf(maxn);

ll inv(ll a) {
    return qpow(a, mod - 2);
}

void prework() {
    f[0] = 1;
    _rep(i, 1, maxn - 1) {
        f[i] = f[i - 1] * i % mod;
    }
    invf[maxn - 1] = qpow(f[maxn - 1], mod - 2);
    for (ll i = maxn - 2; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }
}

ll C(ll n, ll m) {
    if (n > m || m < 0)return 0;
    if (n == 0 || m == n) return 1;
    ll res = (f[m] * invf[m - n] % mod * invf[n]) % mod;
    return res;
}

ll dp[maxn][2];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int on = 0, mx = 0, len = 0;
    _for(i, 0, s.size()){
        if(s[i] == 'R'){
            len++;
        } else{
            mx = max(mx, len);
            len = 0;
        }
    }
    mx = max(mx, len);
    cout << mx << endl;
}

Measured memory_bytes: 6236
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int gcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int k,s,cnt=0;
  cin>>k>>s;
  for(int x=0;x<=k;x++){
    for(int y=0;y<=k;y++){
      if(0<=s-x-y && s-x-y<=k){
        cnt++;
      }
    }
  }
  cout<<cnt<<endl;
  
  
}
///////////////////////////

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

struct edge{
	int to,weight;
	edge(){};
	edge(int _v,int _w){
	to=_v;weight=_w;
};
};


struct graph{
	int n;
	vector<vector<edge>> g;
	vector<int> clr;
	graph(){};
	void init(int _n){
	n=_n;
	g.resize(n);
	clr.resize(n);
	};
	void add_edge(int a,int b,int c){
		g[a].push_back(edge(b,c));
		g[b].push_back(edge(a,c));
	}
};

	graph g;

void dfs(int cur,int pre=-1,int cl=0){
		g.clr[cur]=cl;
		for(auto&& x:g.g[cur]){
		if(x.to==pre)continue;
		int c;
		if(x.weight%2==0)c=cl;
		else c=1-cl;
		dfs(x.to,cur,c);
		}
	}	

signed main(){
	int n;cin>>n;
	g.init(n);

	for(int i=0;i<n-1;i++){
		int x,y,z;cin>>x>>y>>z;
		x--;y--;
		g.add_edge(x,y,z);
	}	
	dfs(0);
	for(auto&& x:g.clr)cout<<x<<endl;
}
;
	

Measured memory_bytes: 10752
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


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

template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int SIZE_R;
    vector<Monoid> dat;
    
    SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, UNITY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update a, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get [a, b), a and b are 0-indexed */
    Monoid get(int a, int b) {
        Monoid vleft = UNITY, vright = UNITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }
        return F(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            cout << (*this)[i];
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    SegTree<int> RMQ(n,
                    [](int a,int b){return min(a,b);},INT_MAX);
    REP(i,q){
        int c,x,y;
        cin>>c>>x>>y;
        if(c) cout<<RMQ.get(x,y+1)<<endl;
        else RMQ.update(x,y);
    }
}



Measured memory_bytes: 3736
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int[] x={scan.nextInt(),scan.nextInt()};
        
        System.out.println(x[0]/x[1]+" "+x[0]%x[1]+" "+String.format("%f", 1.0*x[0]/x[1]));
    }
}


Measured memory_bytes: 26600
import os
import sys
from io import BytesIO, IOBase
import math


def inputIntArray():
    return list(map(int, input().rstrip().split()))


def inputArray():
    return input().rstrip().split()


def inputVars():
    return map(int, input().rstrip().split())


def inputNum():
    return int(input())


def main():
    arr = inputIntArray()
    for pos in range(5):
        if arr[pos] == 0:
            print(pos+1)
            break





#.........................................FAST INPUT OUTPUT.......................................
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#....................................END OF FAST I/O............................................

if __name__ == "__main__":
    main()

Measured memory_bytes: 63052
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;
int main() {
  string s;
  long long k;
  cin >> s >> k;
  for (int i = 0; i < min((long long)s.length(), k); i++) {
    if (s[i] != '1') {
      cout << s[i] << endl;
      return 0;
    }
  }
  cout << 1 << endl;
  return 0;
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

void solve() {
  int n; cin >> n;
  set<string> s;
  for (int i = 0; i < n; ++i) {
    string q; cin >> q;
    s.insert(q);
  }
  cout << s.size();
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 19256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; i++)
    {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        A[i].first = tmp1;
        A[i].second = tmp2;
    }
    //for (int i = 0; i < N; i++)
    //{
    //    cout << i << "th" << A[i].first << endl;
    //}
    sort(A.begin(), A.end());
    //    for (int i = 0; i < N; i++)
    //    {
    //        cout << i << "th" << A[i].first << endl;
    //    }
    //    reverse(A.begin(), A.end());
    //    for (int i = 0; i < N; i++)
    //    {
    //        cout << i << "th" << A[i].first << endl;
    //    }
    int i = -1;
    long long cnt = 0;
    while (M > 0)
    {
        i++;
        int M_tmp = M;
        M_tmp -= A[i].second;
        if (M_tmp <= 0)
        {
            cnt += (long long)M * A[i].first;
        }
        else
        {
            cnt += (long long)A[i].second * A[i].first;
        }
        M -= A[i].second;
    }
    cout << cnt << endl;
    return 0;
}

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

int main() {
	string o, e, ans = "";
	cin >> o >> e;
	for (int i = 0; i < e.length(); i++) {
		ans += o[i];
		ans += e[i];
	}
	if (o.length() - e.length()) {
		ans += o[o.length() - 1];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int righta = 0;
int rightb = 0;
int rightc = 0;
int rightd = 0;
int lefta = 0;
int leftb = 0;
int leftc = 0;
int leftd = 0;

int leftcounter(double left){
    if (left >= 1.1) lefta++;
    else if (left >= 0.6) leftb++;
    else if (left >= 0.2) leftc++;
    else leftd++;
    
    return 0;
}

int rightcounter(double right){
    if (right >= 1.1) righta++;
    else if (right >= 0.6) rightb++;
    else if (right >= 0.2) rightc++;
    else rightd++;
    
    return 0;
}



int main(int argc, const char * argv[])
{

    double right;
    double left;
    
    while (scanf("%lf %lf",&left ,&right) != EOF) {
        rightcounter(right);
        leftcounter(left);
    }
    
    printf("%d %d\n",lefta ,righta);
    printf("%d %d\n",leftb ,rightb);
    printf("%d %d\n",leftc ,rightc);
    printf("%d %d\n",leftd ,rightd);
    
    
        
    return 0;
}

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

int main() {
  int n;
  string w;
  cin >> n >> w;
  
  vector<int> dp (n);
  dp[n - 1] = (w[n - 1] == '.' ? 1 : 0);
  for (int i = n - 2; i >= 0; i--) {
    dp[i] += dp[i + 1];
    if (w[i] == '.') dp[i]++;
  }
  int ans = INT_MAX;
  int atual = 0;
  for (int i = 0; i < n; i++) {
    if (w[i] == '.') continue;
    // We either paint all # till the end
    ans = min (ans, atual + dp[i]);
    // Or we color our # back
    for (int j = i; j >= 0 && w[j] == '#'; j++) {
      w[j] = '.';
      atual++;
    }
  }
  cout << min(ans, atual) << '\n';

  return 0;
}

Measured memory_bytes: 1412
N, M = map(int, input().split())
p, S = [], []

if M == 0:
    print(0, 0)
    exit()

wacount = [0]*(N+1)
wa = [0]*(N+1)
ac = [0]*(N+1)

for _ in range(M):
    pi, Si = map(str, input().split())
    pi = int(pi)
    if Si == "WA":
        wacount[pi] += 1
    elif ac[pi] == 0:
        wa[pi] = wacount[pi]
        ac[pi] += 1

print(sum(ac), sum(wa))


Measured memory_bytes: 5364
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <map>
#include <tuple>
#include <vector>

// lib/quo.hpp
#ifndef QUO_H
#define QUO_H

/*
a == tools:quo(a, b) * b + tools::mod(a, b)
0 <= tools::mod(a, b) < std::abs(b)
*/

namespace tools {
  template <typename T>
  constexpr T quo(const T lhs, const T rhs) {
    return lhs > 0 ? lhs / rhs : rhs > 0 ? -((-lhs - 1 + rhs) / rhs) : (-lhs - 1 + -rhs) / -rhs;
  }
}

#endif

// lib/prime_factorization.hpp
#ifndef PRIME_FACTORIZATION_HPP
#define PRIME_FACTORIZATION_HPP


namespace tools {
  template <typename T>
  ::std::map<T, T> prime_factorization(T n) {
    ::std::map<T, T> result;

    const T floor_sqrt_n = static_cast<T>(::std::sqrt(n));
    for (T i = static_cast<T>(2); i <= floor_sqrt_n; ++i) {
      while (n % i == static_cast<T>(0)) {
        ++result[i];
        n /= i;
      }
    }

    // if n is a prime
    if (n > static_cast<T>(1)) {
      ++result[n];
    }

    return result;
  }
}

#endif

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// lib/extgcd.hpp
#ifndef EXTGCD_HPP
#define EXTGCD_HPP


/*
usage:

std::tuple<int, int, int> result = tools::extgcd(4, 5);
int gcd = std::get<0>(result);
int x0 = std::get<1>(result);
int y0 = std::get<2>(result);
*/

namespace tools {
  template <typename T>
  std::tuple<T, T, T> extgcd(T prev_r, T r) {
    T prev_s = 1;
    T prev_t = 0;
    T s = 0;
    T t = 1;
    while (r != 0) {
      const T q = quo(prev_r, r);
      const T next_r = prev_r - q * r;
      prev_r = r;
      r = next_r;
      const T next_s = prev_s - q * s;
      prev_s = s;
      s = next_s;
      const T next_t = prev_t - q * t;
      prev_t = t;
      t = next_t;
    }
    return std::make_tuple(std::abs(prev_r), prev_s, prev_t);
  }
}

#endif

// main.cpp

int main() {
  i64 A, B;
  std::cin >> A >> B;

  std::cout << static_cast<i64>(tools::prime_factorization(std::get<0>(tools::extgcd(A, B))).size()) + 1 << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

int main(void) {

	long long n, num;
	cin >> n;

	for (int i = 1; (long long)(pow(i, 2)) <= n; i++)
	{
		num = (long long)(pow(i, 2));

	}
	cout << num << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>

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

using namespace std;

int main(){
	int n,a[100];
	scanf("%d",&n);
	rep(i,n) scanf("%d",a+i);

	sort(a,a+n);

	printf("%d\n",a[n-1]-a[0]);

	return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	int k = 1;
	while (k * (k + 1) / 2 < n) k++;
	if (k * (k + 1) / 2 != n) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	k++;
	cout << k << endl;
	vector<vector<int>> ans(k);
	int c = 1;
	for (int i = 1; i < k; i++) {
		int t = 0;
		for (int j = i; j >= 1; j--) {
			ans[t].push_back(c);
			ans[t + j].push_back(c);
			t++;
			c++;
		}
	}
	for (int i = 0; i < k; i++) {
		cout << ans[i].size() << " ";
		for (int j = 0; j < (int) ans[i].size(); j++) {
			if (j > 0) cout << " ";
			cout << ans[i][j];
		}
		cout << endl;
	}
	return 0;	
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }
 
int main(){
    ll L, R;
    cin >> L >> R;
    ll ans = 2019;
    if(R-L+1>2019){
        cout << 0 << endl;
        return 0;
    }
    else{
        for(ll i=L; i<R; ++i){
            for(ll j=i+1; j<=R; ++j){
                ans = min(ans, (i*j)%2019);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	// your code goes here
	string s;
	string r;
	cin >> s >> r;
	int count=0;
	for(int i=0 ; i<3 ;i++)
	{
	    if(s[i]==r[i])
	    count++;
	}
	cout << count;
	return 0;
}


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

#define f(i,x,y)			for(int i=x; i<y; i++)
#define ll 					long long 
#define mp 					make_pair
#define F 					first
#define S 					second
#define N 					100005
#define mod 				1000000007

int main()
{
	int n;
	cin>>n;
	int a[n+1];
	f(i,1,n+1)
		cin>>a[i];

	ll pr[n+1];
	pr[0] = 0;
	f(i,1,n+1)
		pr[i] = a[i]+pr[i-1];

	ll dp[n+1][n+1];
	memset(dp,0,sizeof(dp));

	f(l,1,n)
	{
		f(i,1,n-l+1)
		{
			int j = i+l;
			ll v = dp[i][i]+dp[i+1][j];
			for(int k=i+1; k<j; k++)
			 	v = min(v,dp[i][k]+dp[k+1][j]);
			dp[i][j] = pr[j]-pr[i-1] + v;
		}
	}

	cout<<dp[1][n];


	return 0;
}

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

using namespace std;

const int num[] = {1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};

int main() {
  int x, y;
	cin >> x >> y;
  x--;y--;
	if (num[x] == num[y]) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
// #define DEBUG_IS_VALID 

#ifdef DEBUG_IS_VALID
#define DEB 1 
#define _LIBCPP_DEBUG 0
#else
#define DEB 0
#define NDEBUG
#endif

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#pragma GCC optimize ("-O3")

using namespace std;

#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline bool chmax(T& a,T const& b){if(a>=b) return false; a=b; return true;}
template<class T> inline bool chmin(T& a,T const& b){if(a<=b) return false; a=b; return true;}
void _main();
int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); return 0;}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const int mod=1e9+7,INF=1<<29;
const double EPS=1e-5,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<59; 


void _main(){
  int L; cin >> L ;
  L--;
  int N = 0;
  while(true){
    if((1LL<<(N+1))-1>L) break;
    N++;
  }
  N++;
  using vp = vector<P>;
  vector<vp> g(N);
  rep(i,N-1) g[i].pb(P(i+1,0));
  rep(i,N-1) g[i].pb(P(i+1,(1<<i)));
  if(L!=(1<<(N-1))-1) rrep(i,N){
    if(((L>>i)&1)==0) continue;
    int mask = (1<<i)-1;
    int s = (~mask)&L;
    int s2 = L - s;
    int from = N-1;
    while(true){
      if((1<<from)-1>s2){
        from--; continue;
      }
      break;
    }
    dump(s,s2,from);
    g[from].pb(P(N-1,s));
    if((1<<from)-1==s2) break;
  }
  dump(g);
  int M = 0;
  rep(i,N) for(auto&& p:g[i]) M++;
  cout << N << " " << M << endl;
  rep(i,N) for(auto&& p:g[i]){
    cout << i+1 << " " << p.first+1 << " " << p.second << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
using namespace std;
int main(){
  vector<bool> a(26,false);
  string s;
  cin>>s;
  REP(i,s.size()){
    a[s[i]-'a'] = true;
  }
  char c;
  REP(i,26){
    if(!a[i]){
      c = 'a'+i;
      cout<<c<<endl;
      return 0;
    }
  }
  cout<<"None"<<endl;
  return 0;
}

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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int Z = 4e2 + 10;
int n, ma,mb;
int dp[Z][Z];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> ma >> mb;

    memset(dp, INF, sizeof dp);
    dp[0][0] = 0;
    while(n--) {
        int a,b,c; cin >> a >> b >> c;
        for(int j = Z-1; j-a >= 0; j--)
            for(int k = Z-1; k-b >= 0; k--) {
                dp[j][k] = min(dp[j][k], dp[j-a][k-b]+c);
            }
    }

    int ans = INF;
    for(int i = 1; i*ma < Z and i*mb < Z; i++) ans = min(ans,dp[i*ma][i*mb]);
    cout << (ans == INF? -1 : ans) << endl;
    return 0;
}



Measured memory_bytes: 896
import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int,input().split()))

d = dict()

res = 0
for e in a:
    if e in d:
        d[e] += 1
    else:
        d[e] = 1
    res += e

q = int(input())

for _ in range(q):
    b,c = map(int,input().split())
    if b in d:
        res += d[b]*(c-b)
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d[b] = 0
    print(res)

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

using namespace std;

typedef long long int lli;

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

    int x, a;

    cin >> x >> a;

    cout << ((x<a) ? 0 : 10) << endl;

    return 0;
}


Measured memory_bytes: 256
S = input()
lo,ol = 0,0

if len(S)==0:
    print(0)
    exit()

for i in range(len(S)//2):
    #print(lo,ol)
    #print(S[i*2:(i+1)*2])
    if S[i*2:(i+1)*2]=="10":
        ol += 2
    elif S[i*2:(i+1)*2] =="01":
        lo += 2
    else:
        ol += 1
        lo += 1
else:
    
    if len(S)%2!=0:
        if S[-1] == "1":
            ol += 1
        else:
            lo += 1
    
    print(min(lo,ol))


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

using lint = long long;
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s, t;
  cin >> s;
  cin >> t;

  lint dp[s.size() + 1][t.size() + 1];
  for (int i = 0; i < s.size() + 1; i++) {
    dp[i][0] = 0;
  }
  for (int i = 0; i < t.size() + 1; i++) {
    dp[0][i] = 0;
  }

  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < t.size(); j++) {
      if (s[i] == t[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
      }
    }
  }

  int i = (int)s.size();
  int j = (int)t.size();
  string ans = "";
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i - 1][j]) {
      i--;
    } else if (dp[i][j] == dp[i][j - 1]) {
      j--;
    } else {
      ans = s[i - 1] + ans;
      i--, j--;
    }
  }

  if (ans.size() > 0) {
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int n;
    cin >> n;
    map<int, int> s;
    vector<bool> ok(1001000, true);
    rep(i, n) {
        int a;
        cin >> a;
        s[a]++;
        if(s[a] > 1) ok[a] = false;
    }
    int ans = 0;
    for(auto u : s) {
        int p = u.first;
        if(ok[p]) ans++;
        for(int i = p + p; i <= 1000000; i+=p) {
            ok[i] = false;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 13100
s = input()
flg = 0
for i in range(len(s)//2):
  if s[i] == s[-i-1]:
    pass
  else:
    flg = 1
s = s[:len(s)//2]
for i in range(len(s)//2):
  if s[i] == s[-i-1]:
    pass
  else:
    flg = 1
if flg == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
import numpy as np
b = abs
n, *a = map(int, open(0).read().split())
a = np.array([0] + a + [0])
s = sum(map(b, a[1:] - a[:-1]))
for i in range(n):
    print(s + b(a[i+2] - a[i]) - b(a[i+1] - a[i]) - b(a[i+2] - a[i+1]))

Measured memory_bytes: 23000
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define FFOR(i, a, b) for(int (i)=a;(i)>(b);--(i))
#define rrep(i,n) FFOR(i,0,n)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define lb long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define mod 1000000007LL
#define INF 1234567890123456
typedef pair<int, int> P;
typedef pair<int, P> PP;

const int maxn =1e5 + 10;

//initialization here
//

//
//initialization finish


// your function is here
//

//
// your function finished

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// your code is here
	//

	int n,d,x;cin>>n>>d>>x;
	int ans = x;

	rep(i,n)
	{
		int a;cin>>a;
		ans += 1 + (d-1)/a;
	}
	Print(ans);
	//
	// your code finished


	return 0;
}

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

#define ll long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define rel(i,x,y) for(ll i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
int hi,wi;
int G[1410][1410];
int hist[1410][1410];
ll histgram(int hig){
    ll h[wi+1];
    rep(i,0,wi) h[i] = hist[hig][i];
    h[wi] = 0; 
    stack<pair<ll,ll>> S; //height, locate
    ll ma = 0;
    rep(i,0,wi+1){
        if(S.empty()){ S.push(make_pair(h[i],i)); continue; }
        if(S.top().first == h[i]) continue;
        if( S.top().first < h[i]) S.push(make_pair(h[i],i)); //大きいのはstack
        else{
            ll LocateCheck = S.top().second;
            while((!S.empty()) && S.top().first >= h[i] ){
                ma = max(ma,S.top().first * (i-S.top().second));
                LocateCheck = S.top().second;
                S.pop();
            }
            S.push(make_pair(h[i],LocateCheck));
        }
    }
    
    return ma;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cin >> hi >> wi; //histgramのhとかぶるのでhi
    ll ma=0;
    rep(i,0,hi){
        rep(j,0,wi){
            cin >> G[i][j];
        }
    }
    //各行までのヒストグラムを作成
    rep(i,0,wi) hist[0][i] = abs(1-G[0][i]); /*0,1逆転*/// cout << hist[0][i] << " "; }
    rep(i,1,hi){
        rep(j,0,wi){
            if(G[i][j]==0) hist[i][j] = hist[i-1][j]+1;
            else hist[i][j] = 0;
          //  cout << hist[i][j] << " ";
        }
        //cout << endl;
    }
    rep(i,0,hi) ma = max(ma,histgram(i));
    cout << ma << endl;
}


Measured memory_bytes: 18560
#include<bits/stdc++.h>
using namespace std;
int main(){
  string x;
  x="SUNMONTUEWEDTHUFRISAT";
  string y;
  cin>>y;
  for(int i=0;i<7;i++){
    if(y.at(0)==x.at(i*3)&&y.at(1)==x.at(i*3+1)){
      cout<<7-i<<endl;
      break;
    }
  }
}

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

using namespace std;
using ll = long long;

int main() {

    int N;
    cin >> N;

    int ans = INT_MAX;
    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;

        int cnt = 0;
        while (!(x & 1)) {
            x /= 2;
            ++cnt;
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
  int x, y;
  cin >> x >> y;

  cout << x + y / 2 << ln;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {
    int N, D;
    cin >> N >> D;
    int X[N][D];
    rep(i,N) rep(j,D) cin >> X[i][j];

    long long count = 0;

    rep(i,N) {
        for (int j = i + 1; j < N; j++) {
            long long d = 0;
            rep(k,D) d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            long long e = (long long)floor(sqrt(d));
            if (d == e * e) count++;
        }
    }

    cout << count << endl;

    return 0;
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int main(){
    int n,m,ans=0;
    cin>>n>>m;
    vector<int> x(m),d(m-1);
    
    for(int i = 0; i < m; i++)
    {
        cin>>x[i];
    }
    if(n>=m)
    {
        ans = 0;
    }
    else
    {
        sort(all(x));
        for(int i = 0; i < m-1; i++)
        {
            d[i]=x[i+1]-x[i];
        }
        sort(all(d));
        reverse(all(d));
        ans = x[m-1] - x[0];
        for(int i = 0; i < n-1; i++)
        {
            ans-=d[i];
        }

    }
    

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug(x) cerr<<#x<<" -> "<<x<<'\n'
#define debug2(x,y) cerr<<#x<<" -> "<<x<<" "<<#y<<" -> "<<y<<'\n'
#define debug3(x,y,z) cerr<<#x<<" -> "<<x<<" "<<#y<<" -> "<<y<<" "<<#z<<" -> "<<z<<'\n'

 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

using ordered_set = tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
struct CMP {
	bool operator() (const T& lhs, const T& rhs) const{
		return lhs < rhs;
	}
};

template <typename T>
T power(T a, T n){
	T res = 1;
	while(n > 0){
		if(n & 1) res = (res * a);
		a = (a * a);
		n >>= 1;
	}
	
	return res;
}

template <typename T>
T power(T a, T n, long long mm){
	T res = 1;
	while(n > 0){
		if(n & 1) res = (res * a) % mm;
		a = (a * a) % mm;
		n >>= 1;
	}
	
	return res;
}

const ll N = 2e5+7;
const ll MOD = 1e9+7;
const ll INF = 2e14+7;

ll height[N], dp[N];

ll get_height(int i){
	if(i < 0) return INF;
	
	return height[i];
}

ll solve(int n){
	if(n <= 0) return 0;
	
	if(dp[n] != -1) return dp[n];
	
	return dp[n] = min(solve(n - 1) + abs(get_height(n) - get_height(n - 1)), solve(n - 2) + abs(get_height(n) - get_height(n - 2)));
}

void testcase(){
	int n;
	cin>>n;
	
	for(int i = 0; i < n; i++){
		cin>>height[i];
	}
	
	memset(dp, -1, sizeof(dp));
	
	ll ans = solve(n - 1);
	
	cout<<ans<<'\n';
	
}

signed main(){
	fast;
	
	int t = 1;
	//cin>>t;
	while(t--){
		testcase();
	}
	
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){

  int n;
  cin >> n;
  for (int i = 7; 0 <= i; i--){
    if (pow(2, i) <= n){
      cout << pow(2, i) << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(void){
    int x, h; //正方形の１辺の長さ、四角錐の高さ

    while(true){
        cin >> x >> h;
        if(x == 0 && h == 0) break;

        double S, s1, s2; //四角錐の表面積、底面の面積、三角形の面積

        s1 = x * x;
        s2 = x * sqrt(pow(0.5 * x, 2) + pow(h, 2)) * 0.5;
        S = s1 + s2 * 4;

        cout << fixed << setprecision(6) << S << endl;
    }
}


Measured memory_bytes: 3264
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <numeric>
#include <iostream>

using namespace std;

#define FOR(i, a, b)   for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)  for(int i = (a); i > (b); --i)
#define rep(i, n)      for(int i = 0; i < (n); ++i)
#define all(c)         begin(c), end(c)
#define rall(c)        rbegin(c), rend(c)
#define SZ(a)          ((ll) a.size())

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int main() {
  int N;
  cin >> N;
  double tmp1;
  string tmp2;
  double sum  = 0;
  rep(i,N){
    cin >> tmp1 >> tmp2;
    if(tmp2=="JPY"){
      sum+=tmp1;
    }
    else{
      sum+=tmp1*380000;
    }
  }
  cout << sum;
  return 0;
}


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

using namespace std;


int main(){
    int a,b,sa,sb,n;
    
    
    while(1){
    scanf("%d",&n);
    if(n==0) break;
    sa=0;sb=0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        if(a>b)
            sa+=a+b;
        else if(a<b)
            sb+=a+b;
        else{
            sa+=a;
            sb+=b;
        }
    }
    
    printf("%d %d\n",sa,sb);
    }
    return 0;
    
}

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

using namespace std;

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

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

int main(){
	long long A = 0, B = 0, C = 0, D = 0;
	
	cin >> A >> B >> C >> D;
	
	long long ans = 0;
	
	//C && D
	long long E = lcm(C, D);
	
	ans -= (B / E - A / E);
	if(A % E == 0){
		ans--;
	}
	
	//C
	ans += (B / C - A / C);
	if(A % C == 0){
		ans++;
	}
	
	//D
	ans += (B / D - A / D);
	if(A % D == 0){
		ans++;
	}
	
	cout << B - A - ans + 1 << endl;
	
	return 0;
}


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

int main(void){
    int a,b,q;
    cin >> a >> b >> q;
    vector<ll> s;
    vector<ll> t;
    vector<ll> x;
    s.push_back(-999999999999);
    rep(i,a){
        ll num;
        cin >> num;
        s.push_back(num);
    }
    s.push_back(999999999999);
    t.push_back(-999999999999);
    rep(i,b){
        ll num;
        cin >> num;
        t.push_back(num);
    }
    t.push_back(999999999999);
    rep(i,q){
        ll num;
        cin >> num;
        x.push_back(num);
    }
    ll ans = 0;
    ll splace[2];
    ll tplace[2];
    rep(i,q){
        splace[1] = s[lower_bound(s.begin(), s.end(), x[i])-s.begin()];
        splace[0] = s[lower_bound(s.begin(), s.end(), x[i])-s.begin()-1];
        tplace[1] = t[lower_bound(t.begin(), t.end(), x[i])-t.begin()];
        tplace[0] = t[lower_bound(t.begin(), t.end(), x[i])-t.begin()-1];
        ll num1=0,num2=0,num3=0;
        num1 = max(abs(splace[1]-x[i]),abs(tplace[1]-x[i]));
        num2 = max(abs(splace[0]-x[i]),abs(tplace[0]-x[i]));
        ll mn1=0,mn2=0;
        
        if(abs(splace[1]-x[i]) > abs(tplace[0]-x[i])){
            mn1 = abs(tplace[0]-x[i]);
        }
        else{
            mn1 = abs(splace[1]-x[i]);
        }
        if(abs(splace[0]-x[i]) > abs(tplace[1]-x[i])){
            mn2 = abs(tplace[1]-x[i]);
        }
        else{
            mn2 = abs(splace[0]-x[i]);
        }
        num3 = min(mn1+splace[1]-tplace[0],mn2+tplace[1]-splace[0]);
        
        num2 = min(num1,num2);
        ans = min(num2,num3);
        
        cout << ans <<endl;
    }
    
    
    
    
    return 0;
}









































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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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;
}

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


vector<ll> divisor(ll x) {
	vector<ll> result;
	ll i=1;
	for( ; i*i<x; i++) {
		if(x%i) continue;
		result.push_back(i);
		result.push_back(x/i);
	}
	if(i*i==x&&x%i==0)
		result.push_back(i);
	
	sort(result.begin(),result.end());
	return result;
}

ll N,ans;

void input() {
	cin>>N;
}

void solve() {
	llvec v=divisor(N);
	for(int i=0; i<v.size(); i++) {
		ll m=N/v[i]-1;
		if(v[i]>=m) break;
		ans+=m;
	}
	cout<<ans<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


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

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b, k;
    cin >> a >> b >> k;
    if (k <= a) {
		cout << a - k << " " << b;
	} else {
		k -= a;
		a = 0;
		b -= k;
		cout << 0 << " " << max(b, 0LL);
	}
    return 0;
}


Measured memory_bytes: 3560