akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n,m=LI()
g,c=GI(n,m)

v=[-1 for i in range(n)]

def IsBipartite():
    q=[0]
    v[0]=0
    while q:
        c=q.pop()
        for n in g[c]:
            if v[n]==-1:
                q.append(n)
                v[n]=1-v[c]
            elif v[n]==v[c]:
                return False
    return True

if IsBipartite():
    ans=sum(v)*(n-sum(v))-m
else:
    ans=n*(n-1)//2-m
print(ans)


Measured memory_bytes: 75496
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int main() {
	int N;
	cin >> N;
	int res = 0;
	int cnt = 0;
	rep(i,N) {
		int p;
		cin >> p;
		if(p == i+1) {
			cnt++;
		}
		else {
			res += cnt/2 + cnt%2;
			cnt = 0;
		}
	}
	res += cnt/2 + cnt%2;
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#define MAXN 100
#define MAXL 10
char wd[MAXN+5][MAXL+5];
int len[MAXN+5];
int n;
int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%s", wd[i]);
		len[i] = strlen(wd[i]);
	}
	for(int i = 1; i < n; i++){
		for(int j = 0; j < i; j++)
			if(strcmp(wd[j] ,wd[i]) == 0){
				printf("No\n");
				return 0;
			}
		if(wd[i][0] != wd[i-1][len[i-1]-1]){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
}

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

int main(){
    int N,ans1=0,ans2=0;
    cin >> N;
    int X[N];

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

    int sum1=0;

    for(int i=0; i<N; i++){
        sum1+=X[i];
    }

    ans1=sum1/N;
    ans2=ans1+1;

    int min1=0,min2=0;

    for(int i=0; i<N; i++){
        min1+=pow(X[i]-ans1,2);
    }
    for(int i=0; i<N; i++){
        min2+=pow(X[i]-ans2,2);
    }

    if(min1<=min2){
        cout << min1;
    }
    else{
        cout << min2;
    }



    
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cassert>

#include <unordered_set>
#include <unordered_map>
#include <random>
#include <thread>
#include <chrono>

using namespace std;

#define all(c) c.begin(), c.end()
#define repeat(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x) 
#endif

typedef complex<double> point;

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    for(auto it = v.begin(); it != v.end(); ++it) {
        if(it != v.begin())
            os << ",";
        os << *it;
    }
    return os << "}";
}

using ll = int64_t;

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

    string s;
    cin >> s;
    int k;
    cin >> k;

    int n = s.length();
    vector<string> subs;
    for (int i = 0; i<n; i++){
        for (int k = 1; k <= min(5, n-i); k++){
            subs.push_back(s.substr(i, k));
        }
    }
    sort(all(subs));
    subs.erase(unique(all(subs)), subs.end());

    cout << subs[k - 1] << endl;
    return 0;
}


Measured memory_bytes: 1660
using System;

class Program
{
    const int TYPE_NUM = 26;

    static void Main(string[] args)
    {
        int i, j;

        int d = int.Parse(Console.ReadLine());
        int[] c = new int[TYPE_NUM + 1];
        int[,] s = new int[d + 1, TYPE_NUM + 1];

        string[] strInput = Console.ReadLine().Split(' ');
        for(i = 1; i <= TYPE_NUM; i++)
        {
            c[i] = int.Parse(strInput[i - 1]);
        }

        for (i = 1; i <= d; i++) 
        {
            strInput = Console.ReadLine().Split(' ');
            for(j = 1; j <= TYPE_NUM; j++)
            {
                s[i, j] = int.Parse(strInput[j - 1]);
            }
        }

        int[] t = new int[d + 1];

        for (i = 1; i <= d; i++)
        {
            t[i] = int.Parse(Console.ReadLine());
        }

        int result = 0;
        int[] last = new int[TYPE_NUM + 1];
        int resultDiff;

        for(i = 1; i <= d; i++)
        {
            result += s[i, t[i]];
            last[t[i]] = i;

            resultDiff = 0;
            for (j = 1; j <= TYPE_NUM; j++)
            {
                resultDiff += c[j] * (i - last[j]);
            }
            result -= resultDiff;

            Console.WriteLine(result);
        }

        return;
    }
}

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

#define INF 1.1e9
#define LINF 1.1e18
#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 ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

int n;
ll a[1010], odd_sum, even_sum;
bool flg = false;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] >= 0) {
			flg = true;
			if(i & 1) odd_sum += a[i];
			else even_sum += a[i];
		}
	}
	vector< int > ans;
	if (!flg) {
		int ma_idx = 1;
		for (int i = 1; i <= n; i++) {
			if (a[ma_idx] < a[i]) ma_idx = i;
		}
		for (int i = n; i > ma_idx; i--) {
			ans.pb(i);
		}
		for (int i = 1; i < ma_idx; i++) {
			ans.pb(1);
		}
		cout << a[ma_idx] << endl;
		cout << (int)ans.size() << endl;
		for (auto x : ans) {
			cout << x << endl;
		}
	}
	else {
		if (odd_sum > even_sum) {
			if (n % 2 == 1 && a[n] < 0) {
				ans.pb(n);
			}
			for (int i = n; i >= 1; i--) {
				if (i % 2 == 0) {
					if (a[i - 1] < 0) {
						ans.pb(i - 1);
					}
					else {
						ans.pb(i);
					}
				}
			}
			if (a[1] < 0) ans.pb(1);
		}
		else {
			if (n % 2 == 0 && a[n] < 0) {
				ans.pb(n);
			}
			for (int i = n; i >= 1; i--) {
				if (i % 2 == 1) {
					if (a[i-1] < 0) {
						ans.pb(i - 1);
					}
					else {
						ans.pb(i);
					}
				}
			}
		}
		cout << max(odd_sum, even_sum) << endl;
		cout << (int)ans.size() << endl;
		for (auto x : ans) {
			cout << x << endl;
		}
	}
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <stdexcept>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define debug(a) cout << (a) << endl
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;
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 (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}

ll M = 1000000007;

void solve()
{
	ll n;
	cin>>n;
	deque<char>ans;
	while(n>0){
		ll k=(n-1)%26;
		char tmp='a'+k;
		ans.push_front(tmp);
		n-=k;
		n/=26;
	}
	rep(i,size(ans)){
		cout<<ans[i];
	}
	cout<<endl;

}

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


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    vector<int>a;
    cin>>n>>k;
    int i;
    a.resize(n);
    for(i=0;i<n;i++)
        cin>>a[i];
    int dp[k+1];
    memset(dp,0,sizeof(dp));
    for(i=0;i<=k;i++)
    {
        for(auto x:a)
        if(i>=x&&dp[i-x]==0)
        dp[i]=1;
    }
    dp[k]?cout<<"First":cout<<"Second";
    return 0;
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr ll MOD = 2;

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> a(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
  }

  vector<int> ans(N);
  ll middle = N / 2;

  rrep(i, N, 0) {
    if (i >= middle) {
      ans[i] = a[i];
      continue;
    }

    int total = 0;
    for (int j = i; j < N; j += (i + 1)) {
      total += ans[j];
    }
    if (total % 2 == a[i]) continue;
    ans[i] = 1;
  }

  ll sum = 0;
  string s;
  rep(i, 0, N) {
    sum += ans[i];
    if (!ans[i]) continue;
    s += to_string(i + 1) + " ";
  }
  if (sz(s)) s.pop_back();
  cout << sum << endl;
  if (sz(s)) cout << s << endl;
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[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;
}

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}


Measured memory_bytes: 4100
#include<bits/stdc++.h>
#define mxn 200005
#define ll long long
using namespace std;
ll seg[4*mxn], lazy[4*mxn];
vector<int>adj[mxn];
void propagate(int n, int s, int e)
{
    lazy[n*2]+= lazy[n];
    lazy[n*2 +1]+= lazy[n];
    int mid= (s+e)>>1;
    seg[n*2]+= lazy[n]*(mid-s+1);
    seg[n*2 +1]+= lazy[n]*(e-mid);
    lazy[n]= 0;
    return;
}
void update(int n, int s, int e, int l, int r, int val)
{
    if(s>=l && e<=r)
    {
        seg[n] += val*(e-s+1);
        lazy[n]+= val;
        return;
    }
    if(s>r || e<l)return;
    if(lazy[n])propagate(n, s, e);
    int mid= (s+e)>>1;
    update(n*2, s, mid, l, r, val);
    update(n*2 +1, mid+1, e, l, r, val);
    seg[n]= seg[n*2]+seg[n*2 +1];
    return;
}
ll query(int n, int s, int e, int l, int r)
{
    if(s>=l && e<=r)return seg[n];
    if(s>r || e<l)return 0;
    if(lazy[n])propagate(n, s, e);
    int mid= (s+e)>>1;
    return query(n*2, s, mid, l, r)+query(n*2 +1, mid+1, e, l, r);
}
int main()
{
    int n, x, y;
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    ll res= 0;
    for(int i=1; i<=n; i++)
    {
        vector<int>vec;
        for(int j=0; j<adj[i].size(); j++)
        if(adj[i][j]<i)vec.push_back(adj[i][j]);
        sort(vec.begin(), vec.end());
        int lst= i, c= 1;
        for(int j=vec.size()-1; j>=0; j--)
        update(1, 1, n, vec[j]+1, lst, c), lst= vec[j], c--;
        update(1, 1, n, 1, lst, c);
        res+= query(1, 1, n, 1, n);
    }
    printf("%lld\n", res);
    return 0;
}


Measured memory_bytes: 24552
package main

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

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

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

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)
	s := nextMega()

	rank := 0
	sum := 0
	for i := 0; i < n; i++ {
		ok := false
		if s[i] == 'a' && sum < a+b {
			sum++
			ok = true
		} else if s[i] == 'b' {
			rank++
			if sum < a+b && rank <= b {
				sum++
				ok = true
			}
		}
		if ok {
			fmt.Fprintln(wt, "Yes")
		} else {
			fmt.Fprintln(wt, "No")
		}
	}
	wt.Flush()
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long A,B,C,D,H,K,L,M,N,T,W,X;
  string S;
  cin >> N;
  vector<long long> vec(N);
  long long dp[N][5];
  for (int i=0;i<N;i++) {cin >> vec.at(i);}
  
  A=0;
  
  if (N%2==0) {
    dp[1][0]=vec[0];
	dp[1][1]=vec[1];
	if (N>2) {
	  for (int j=2;j<N/2+1;j++) {
	    dp[j][0]=dp[j-1][0]+vec[j*2-2];
	    dp[j][1]=max(dp[j-1][0]+vec[j*2-1],dp[j-1][1]+vec[j*2-1]);
	  }
	  cout << max(dp[N/2][0],dp[N/2][1]) << endl;
	  }
	else {cout << max(vec[0],vec[1]) << endl;}
	}
  else {
    dp[2][0]=max(vec[0],vec[1]);
	dp[2][1]=vec[2];
	dp[2][2]=vec[0]+vec[2];
	if (N>3) {
	  for (int i=3;i<(N+1)/2+1;i++) {
	    dp[i][0]=max(dp[i-1][0]+vec[i*2-3],dp[i-1][2]);
		dp[i][1]=max(dp[i-1][0]+vec[i*2-2],dp[i-1][1]+vec[i*2-2]);
		dp[i][2]=dp[i-1][2]+vec[i*2-2];
        //cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
	  }
	  cout << max(dp[(N+1)/2][0],dp[(N+1)/2][1]) << endl;
	}
	else {cout << max(max(vec[0],vec[1]),vec[2]) << endl;}
  }
  
}

Measured memory_bytes: 8804
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

void solve(){
    string s;
    cin >> s;
    if(s=="SSS") cout << "0\n";
    else if(s=="RSS"||s=="SRS"||s=="SSR"||s=="RSR") cout << "1\n";
    else if(s=="RRR") cout << "3\n";
    else cout << "2\n";
}

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

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
using namespace std;
using ll = long long;
const int MAX_N = 310;
const ll MAX_D = 1000000000;
int dis[MAX_N][MAX_N];

int best_d = MAX_D;
vector<int> r_city;

void dfs(int now, vector<int> visited, int d)
{
    bool update = false;
    rep(i, 0, visited.size())
    if (visited[i] == 0)
    {
        update = true;
        int next = r_city[i];
        visited[i] = 1;
        dfs(next, visited, d + dis[now][next]);
        visited[i] = 0;
    }

    if (! update)
        best_d = min(best_d, d);
}

int main()
{
    int n, m, r;
    cin >> n >> m >> r;
    rep(i, 0, r)
    {
        int rr;
        cin >> rr;
        rr--;
        r_city.push_back(rr);
    };

    rep(i, 0, n)
    rep(j, 0, n)
    {
        if (i == j) continue;
        dis[i][j] = MAX_D;
    }
    rep(i, 0, n)
        dis[n][i] = 0;

    rep(i, 0, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        dis[a][b] = c;
        dis[b][a] = c;
    }

    rep(k, 0, n)
    rep(i, 0, n)
    rep(j, 0, n)
    {
        if (dis[i][k] == MAX_D or dis[k][j] == MAX_D) continue;
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }
    
    vector<int> visited(r_city.size(), 0);
    dfs(n, visited, 0);

    cout << best_d << endl;
    return 0;
}

Measured memory_bytes: 512
// " --- IN THE NAME OF ALLAH --- " // ;)
// ------------sphr_agz------------ // ;)

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <list>
#include <stack>
#include <bitset>
#include <ctime>
using namespace std;

typedef long double ld;
typedef long long int lli;
#define pb(x) push_back(x)
#define recout(x) return cout << (x), 0
#define fr first
#define sc second
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define stp(x) cout << setprecision(x) << fixed
#define mk make_pair
const lli N = 1e6, N2 = 5e3, delta = 46639, mod = 1e9 + 7, oo = 1e16;
const ld PI = 3.141592653589793;

lli dp[N], a[N];

int main(){
	lli n, k;
	cin >> n >> k;
	for (lli i = 0; i < n; i++) {
		cin >> a[i];
		if (i == 0)
			dp[i] = 0;
		else if (i == 1)
			dp[1] = abs (a[1] - a[0]);
		else {
			lli o = k, mn = oo;
			for (lli j = i - 1; j >= 0 && o >= 1; j--, o--)
				mn = min (mn, dp[j] + abs (a[i] - a[j]));
			dp[i] = mn;
		}
	}
	cout << dp[n - 1];
	return 0;
}


Measured memory_bytes: 5120
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define F first
# define S second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define mset multiset
# define umap unordered_map
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)
# define lr(i,l,r) for(int i=l;(l>r?i>=r:i<=r);(l>r?--i:++i))

using namespace std;

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int dx[]={1,0,-1,0,-1,-1,1,1},dy[]={0,1,0,-1,-1,1,-1,1}; 
const int mod = 1e9+7;
const int N = 2e6+5;

vector<ll>v;

void calc(ll x){
	if(x>=1e10)return;
	v.pb(x);
	if(x%10!=0)calc(x*10+x%10-1);
	if(x%10!=9)calc(x*10+x%10+1);
	calc(x*10+x%10);
}

void solve(){
	int k;
	cin>>k;
	for(ll i=1;i<=9;++i)calc(i);
	sort(all(v));
	cout<<v[k-1];
}

int main(){
	Speed();
	int T=1; 
	//cin>>T;	
	while(T--)
		solve();
	return 0;
}

Measured memory_bytes: 5328
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n, X;
    cin >> n >> X;
    vi x(n);
    cin >> x;
    int g = 0;
    REP(i, n) g = __gcd(g, abs(X - x[i]));
    cout << g << endl;
    return (0^_^0);
}



Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int h,w,e[12][12],i,j,l,r,t,b,d,tmp,ans=0;
	bool flag = false;
	while(true){
		cin >> h >> w;
		if(!(h&&w)){
			break;
		}
		ans = 0;
		for(i=0; i<h; ++i){
			for(j=0; j<w; ++j){
				cin >> e[i][j];
			}
		}
		for(t=0; t<h; ++t){
			for(b=t+2; b<h; ++b){
				for(l=0; l<w; ++l){
					for(r=l+2; r<w; ++r){
						d = INF;
						for(i=t; i<=b; ++i){
							d = min(d,e[i][l]);
							d = min(d,e[i][r]);
						}
						for(j=l; j<=r; ++j){
							d = min(d,e[t][j]);
							d = min(d,e[b][j]);
						}
						tmp = 0;
						flag = true;
						for(i=t+1; i<b; ++i){
							for(j=l+1; j<r; ++j){
								if(e[i][j]>=d){
									flag = false;
									break;
								}
								tmp += (d-e[i][j]);
							}
							if(!flag){
								break;
							}
						}
						if(flag){
							ans = max(ans,tmp);
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3072
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Y = II()

for i in range(N+1):
    for j in range(N-i+1):
        y = Y-10000*i-5000*j
        if y == 1000*(N-i-j):
            print(i,j,N-i-j)
            exit()

print('-1 -1 -1')

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

#define debug(x) cerr << x << " = "(x) << endl;
#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
ll mod = 1e9+7;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n,m; cin >> n >> m;
    if(abs(n-m)>1){ cout << 0 << endl; return 0;}
    ll ans = 1;
    rep(i,2,n+1){
        (ans *= i) %= mod;
    }
    rep(i,2,m+1){
        (ans*=i) %= mod;
    }
    if(n==m) (ans*=2) %= mod;
    cout << ans << endl;
}

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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string s;
  cin >> s;
  int a = s.find("A"), z = s.rfind("Z");
  cout << z - a + 1 << endl;

  return 0;
}


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

int main(){
    string S;
    cin >> S;
    bool ok = true;
    for(int i=0;i<S.size();i++){
        if(i%2==0 && S[i]=='L') ok = false;
        if(i%2==1 && S[i]=='R') ok = false;
    }
    cout << (ok? "Yes":"No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, x;
	long long ans = 0;
	cin >> N >> x;

	vector<long long> A(N);
	vector<long long> B(N);

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		B[i] = A[i];
	}

	for (int i = 1; i < N; i++)
	{
		if (A[i - 1] + A[i] <= x)
			continue;

		A[i] = x - A[i - 1];
		if (A[i] < 0)
		{
			A[i - 1] += A[i];
			A[i] = 0;
		}

	}

	for (int i = 0; i < N; i++)
	{
		ans += B[i] - A[i];
	}

	cout << ans << endl;

	return 0;
}


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

int main(){
  long int i,array[200001]={},a,b=1,c;
  string s;
  cin>>a;
  
  for(i=1;i<=a;i++){
    b*=i;
    b%=1000000007;
    }
  cout<<b<<endl;
}

Measured memory_bytes: 256
#include <cstdio>

int divisor_count(int n)
{
    int count = 0;

    for(int i = 1; i*i <= n; i++)
    {
        if(n%i == 0)
        {
            count += (i*i == n ? 1 : 2);
        }
    }

    return count;
}

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

    int answer = 0;
    for(int i = 1; i <= n; i += 2)
    {
        if(divisor_count(i) == 8)
            answer++;
    }

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


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };


int A, B, C,K;

int main() {
	scanf("%d%d%d%d", &A,&B,&C,&K);

	for (int i = 0; i < K; i++) {
		if (A >= B && A >= C) {
			A *= 2;
		}
		else if (B >= C) {
			B *= 2;
		}
		else C *= 2;

	}

	printf("%d", A + B + C);

}



/*         提出前の確認事項

・デバッグ用の関数は＜＜コメント化＞＞しているか？
・すべての＜＜入力例＞＞は試したか？
・＜＜限界値分析＞＞はしたか？
・＜＜出力の改行＞＞の有無は確認したか？
・文字列の＜＜スペル＞＞は確認したか？
　　　　　　　　↓
	 ＜＜提出先＞＞に注意して提出！！
*/

Measured memory_bytes: 128
// Template
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace atcoder;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Union-Find
class UnionFind {
    vector<int> par;
public:
    UnionFind(int n) : par(n, -1) {}
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    bool unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return false;
        if (par[rx] > par[ry]) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
        return true;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    rep(i, n) {
        cin >> x[i] >> y[i];
        --x[i]; --y[i];
    }
    
    vector<int> vec(n);
    iota(all(vec), 0);
    sort(all(vec), [&](int a, int b) {return x[a] < x[b];});
    UnionFind uf(n);
    stack<pair<int, int>> st;
    int mn = inf;
    rep(i, n) {
        if (y[vec[i]] < mn) {
            st.push({y[vec[i]], vec[i]});
            mn = y[vec[i]];
        } else {
            auto memo = st.top();
            while (!st.empty()) {
                auto p = st.top();
                if (p.first < y[vec[i]]) {
                    st.pop();
                    uf.unite(vec[i], p.second);
                } else {
                    break;
                }
            }
            st.push(memo);
        }
    }
    
    rep(i, n) cout << uf.size(i) << "\n";
}


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

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



    bool is_prime[55556];
    is_prime[0] = is_prime[1] = false;

    for (int a=2; a<55556; a++) {
        is_prime[a]=true;
    }

    for (int a=2; a<55556; a++) {
        if(is_prime[a]) {
            for(int b=2; b*a<55556; b++) {
                is_prime[b*a] = false;
            }
        }
    }

    vector<int> five;
    for (int a=2; a<55556; a++) {
        if(is_prime[a] && a%10 == 3) {
            five.push_back(a);
        }
    }

    int n;
    cin >> n;

    for (int i=0; i<n; i++) {
        cout << five[i] << " ";
    }

}


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

int main(){
      int n;cin >> n;
      int k;cin >> k;
      string s;cin >> s;
      int t = s.length();
      for(int i = 0;i < t;i++){
            if(i + 1 == k)s[i] = tolower(s[i]);
      }
      cout << s;
}

Measured memory_bytes: 256
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[17][17],b[17][17];
int xx[17];
int num[17];
int n;
int check(int x){
    memset(num,0,sizeof(num));
    int ans=0;
    int cnt=1;
    while(x){
        if(x&1){
            num[cnt]=1;
            ++ans;
        }
        x/=2;
        ++cnt;
    }
    int flag=0;
    for(int i=1;i<=n;++i){
        if(num[i]){
            for(int j=1;j<=xx[i];++j){
                if(b[i][j]==1&&!num[a[i][j]])
                    flag=1;
                else if(b[i][j]==0&&num[a[i][j]])
                    flag=1;
            }
        }
    }
    if(!flag)
        return ans;
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>xx[i];
        for(int j=1;j<=xx[i];++j){
            cin>>a[i][j]>>b[i][j];
        }
    }
    int lastans=0;
    for(int i=0;i<=(1<<n)-1;++i)
        lastans=max(lastans,check(i));
    cout<<lastans;
    return 0;
}


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

b_small = int(B * 10)
b_big = int((B+1) * 10)
flag = True
for i in range(b_small, b_big):
    if int(i * 0.08) == A:
        print(i)
        flag = False
        break

if flag:
    print('-1')

Measured memory_bytes: 38384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
using namespace std;

#define MOD 1000000007
#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, b;
    cin >> a >> b;
    cout << a * b << " " << (a * 2) + (b * 2) << endl;
}



Measured memory_bytes: 3160
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
const long long INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    REP(i,n){
        cin >> p[i];
    }

    int a1, a2, a3, ans = 0;
    REP(i,n-2){
        a1 = p[i];
        a2 = p[i + 1];
        a3 = p[i + 2];
        if(a1<a2 && a2<=a3){
            ans++;
        }
        else if(a3<a2 && a2<=a1){
            ans++;
        }

    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int x=1,y=1;
   int N=s.size();
  if(N==3){
    if(s.at(0)==s.at(2)){
      x=1;
      y=1;
    }
  }
  else{
  for(int i=0;i<(N-1)/2;i++){
    if(s.at(i)==s.at(N-1-i)){
      continue;
    }
    else 
      x=0;
      break;
  }
  for(int i=0;i<(N-1)/4;i++){
    if(s.at(i)==s.at((N-1)/2-1-i)
       &&s.at((N+3)/2-1+i)==s.at(N-1-i)){
      continue;
    }
    else
      y=0;
      break;
  }
  }
  if(x*y>=1) cout<<"Yes"<<endl;
  else if(x*y==0) cout<<"No"<<endl;
}


Measured memory_bytes: 256
/*
 *  AUTHOR : MANAV PATEl
*/
#include<bits/stdc++.h>
#include<functional>
//#include<boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

namespace fastio {

	template <class T> istream &operator>>(istream &os, vector<T> & vec) {
		for (auto &u : vec)os >> u;
		return os;
	}
	template <class T> ostream &operator<<(ostream &os, const vector<T> & vec) {
		for (auto &u : vec)os << u << " ";
		return os;
	}
	template<class T1, class T2> inline istream& operator>>(istream& os, pair<T1, T2>& p) {
		return os >> p.first >> p.second;
	}
	template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
		return os << p.first << " " << p.second;
	}
	template <class T> ostream &operator<<(ostream &os, set<T> & con) {
		for (auto &u : con) os << u << " ";
		return os;
	}
	void re() {}
	template <typename T, typename... args> void re(T& x, args&... tail) {
		cin >> x;
		re(tail...);
	}
	void pr() {}
	template <typename T> void pr(const T& x) {
		cout << x;
	}
	template <typename T, typename... args> void pr(const T& x, const args&... tail) {
		cout << x << " ";
		pr(tail...);
	}
	template <typename... args> void prln(const args&... tail) {
		pr(tail...);
		cout << "\n";
	}
}
using namespace fastio;

typedef long long int ll;
typedef long double ld;

const ll mod = 1e9+7;
const ll mod1 = 998244353;

#define fill(a)  memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back

int main()
{
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	cin.tie(0);
	string s;
	re(s);
	map <char,int> mp1;
	mp1[s[0]]++;
	mp1[s[1]]++;
	mp1[s[2]]++;
	mp1[s[3]]++;
	if(mp1.size() == 2) cout<<"Yes\n";
	else cout<<"No\n";
}


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

const int N = 1e5 + 5;
const int K = 105;

int dp[N], s[K];


int main () {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, k;
  cin >> n >> k;
  int mnk = 1e9;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    mnk = min(s[i], mnk);
  }
  for (int i = mnk; i <= k; i++) {
    int win = 0;
    for (int j = 0; j < n; j++) {
      if (i-s[j] >= 0) {
        if (dp[i-s[j]] == 0) {
          win = 1;
          break;
        }
      }
    }
    dp[i] = win;
  }
  if (dp[k] == 1)
    cout << "First\n";
  else
    cout << "Second\n";
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){


#ifndef ONLINE_JUDGE   
freopen("input.txt", "r", stdin); 
// freopen("output.txt", "w", stdout);    
#endif 
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

string str1,str2;
cin>>str1>>str2;

int p=str1.size();
int q=str2.size();

p=p-q+1;

int count =0,count1=0;
for(int i=0;i<p;i++){
	count=0;
	for(int j=0;j<q;j++){
		if(str1[j+i]==str2[j])
			count++;
		
	}

	if(count>=count1)
		count1=count;
}
if(count>=count1)
count1=count;

cout<<q-count1;

	


}





Measured memory_bytes: 3608
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
#include <iomanip>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fcout cout << fixed << setprecision(10)
#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define all(x) x.begin(), x.end()
const ll inf = 1e18;
const ll mod = 1e9 + 7;

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

int main(){
    int n, max_w;
    cin >> n >> max_w;
    vector<vint> dp(n+1, vint(max_w+1, 0));
    // dp[i][j] = v; において、i番目までの品物で、重さjいかにおいてvの価値を持つ。
    rep(i,n){
        int v, w;
        cin >> v >> w;
        rep(j, max_w+1){
            if(j < w){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v);
            }
        }
    }
    cout << dp[n][max_w] << endl;
}



Measured memory_bytes: 6804
//https://www.youtube.com/watch?v=nQWFzMvCfLE
#include<bits/stdc++.h>
using namespace std;
long f[100005][5],n;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for (long i=1;i<=n;i++)
    {
        long a,b,c;
        cin>>a>>b>>c;
        f[i][1]=max(f[i-1][2],f[i-1][3])+a;
        f[i][2]=max(f[i-1][1],f[i-1][3])+b;
        f[i][3]=max(f[i-1][1],f[i-1][2])+c;
    }
    cout<<max(f[n][1],max(f[n][2],f[n][3]));
}
/*
2
0 0
10 10
1 5 5 2
6 10 8 7
*/


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

bool f(P a, P b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main() {
  int n;
  cin >> n;
  vp r(n,P(0,0));
  rep(i,n) {
    int x,y;cin >> x >> y;
    r.at(i)=(P(x,y));
  }
  vp b(n,P(0,0));
  rep(i,n) {
    int x,y;cin >> x >> y;
    b.at(i) = P(x,y);
  }

  sort(rng(b));
  sort(rrng(r),f);

  vi rp(n,1);
  int ans = 0;
  rep(i,n) {
    int bx,by;
    bx=b.at(i).fi;by=b.at(i).se;
    rep(j,n) {
      if(rp.at(j)) {
        int rx,ry;
        rx=r.at(j).fi;ry=r.at(j).se;
        if(rx < bx and ry < by) {
          ans++;
          rp.at(j)=0;
          break;
        }
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
    void print() {
        cout << fixed << setprecision(8) <<
            this->x << " " << this->y << endl;
    }
};


void koch(const int& depth, const Point& a, const Point& b) {
    if (depth == 0) { return; }
    const double theta = M_PI / 3.0;

    Point s(
        (2.0 * a.x + b.x) / 3.0,
        (2.0 * a.y + b.y) / 3.0
    );

    Point t(
        (a.x + 2.0 * b.x) / 3.0,
        (a.y + 2.0 * b.y) / 3.0
    );

    Point u(
        (t.x - s.x) * cos(theta) - (t.y - s.y) * sin(theta) + s.x,
        (t.x - s.x) * sin(theta) + (t.y - s.y) * cos(theta) + s.y
    );

    koch(depth - 1, a, s);
    s.print();
    koch(depth - 1, s, u);
    u.print();
    koch(depth - 1, u, t);
    t.print();
    koch(depth - 1, t, b);
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    Point a(0, 0);
    Point b(100, 0);

    a.print();
    koch(n, a, b);
    b.print();

    return 0;
}

Measured memory_bytes: 3284
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <climits>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define FILL(mat, x) memset(mat, x, sizeof(mat))
#define BIT(n, b) ((n>>b) & 1)

#define INF 1e+20

using namespace std;

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

int n = 0;
double boxsz, rc[16], dp[1<<16][16];

double rad2(double r1, double r2){
	return sqrt(pow(r1+r2,2) - pow(r1-r2,2));
}

double rec(int stat, int v){
	
	if( dp[stat][v] != -1 )
		return dp[stat][v];
	
	if( stat == (1<<n)-1 )
		return dp[stat][v] = rc[v];
		
	double res = INF;
	
	for(int i = 0; i < n; ++i){
		if( !BIT(stat, i) ){
			if(stat==0)
				res = min(res, rec(stat|(1<<i), i) + rc[i]);
			else 
				res = min(res, rec(stat|(1<<i), i) + rad2(rc[v], rc[i])); 
		}
	}
	
	return dp[stat][v] = res;
}

string solve(){

	for(int i = 0; i < (1<<16); ++i){
		for(int j = 0; j < n; ++j){
			dp[i][j] = -1;
		}
	}
	
	return (rec(0, 0)<=boxsz?"OK":"NA");
}

int main(){

	string str;
	
	while(getline(cin, str)){
		
		stringstream ss(str);
		ss >> boxsz;
		
		n = 0;
		while(ss >> rc[n]){
			n++;
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 9428
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
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 (a>b) { a=b; return 1; } return 0; }
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
    ll n;
    cin >> n;
    mint a = 10, b = 8, c = 9;
    mint ans;
    ans = a.pow(n) + b.pow(n) - (mint)2 * c.pow(n);
    cout << ans << endl;
    return 0;
}

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

int main() {
  int n; cin >>n;
  vector<int> a(100001);
  for (int i=0; i<n; i++){
    int buf; cin >>buf;
    a.at(buf)++;
  }
  
  int maxcnt = 0;
  for (int i=0; i<100001-2; i++){
    maxcnt = max(maxcnt, a.at(i)+a.at(i+1)+a.at(i+2));
  }
  
  cout <<maxcnt <<endl;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();
		if(b-a == c-b) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}

	}

}

Measured memory_bytes: 22740
def prime_factorize(n):
    result = []
    if n % 2 == 0:
        t = 0
        while n % 2 == 0:
            n //= 2
            t += 1
        result.append((2, t))
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


N = int(input())

m = 1000000007

t = [0] * (N + 1)
for i in range(2, N + 1):
    for p, e in prime_factorize(i):
        t[p] += e

result = 1
for i in range(2, N + 1):
    if t[i] == 0:
        continue
    result = result * (t[i] + 1) % m
print(result)


Measured memory_bytes: 9392
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-5
#define MAX_N 10

using namespace std;
typedef pair<int, int> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int N, D, X[MAX_N][MAX_N], res;
int main(int argc, char **argv) {
    cin >> N >> D;

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < D; ++j)
            cin >> X[i][j];

    int res = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < i; ++j) {
            double d = 0;
            for(int k = 0; k < D; ++k) {
                d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }

            double sqrtd = sqrt(d) + EPS;
            int intsqrtd = (int)sqrtd;
            if(intsqrtd * intsqrtd == d)
                res++;
        }

    cout << res << endl;
}

Measured memory_bytes: 256