akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

template <typename T> void print(T vec) { for (auto d : vec) cout << d << ' '; cout << '\n'; }
template<typename T> void print2D(T mat) { for (auto vec : mat) print(vec); }

int n;
class NumArray {
public:
    vector<ll> Seg;
    vector<ll> Lazy;
    vector<int> num;
    NumArray(vector<ll>& nums) {

        Seg.resize(4 * n + 1, 0);
        Lazy.resize(2 * n + 1);
        //build(nums, 1, 0, n - 1);

    }

    //void build(vector<int>& nums, int node, int start, int end) {
    //    if (start == end) {
    //        Seg[node] = nums[start];
    //        return;
    //    }
    //    else {
    //        int mid = start + (end - start) / 2;
    //        build(nums, 2 * node, start, mid);
    //        build(nums, 2 * node + 1, mid + 1, end);
    //        Seg[node] = max(Seg[2 * node], Seg[2 * node + 1]);
    //    }
    //}


    void updateRange(int node, int start, int end, int idx, ll val) {
        if (idx < start || idx > end) return;
        if (start == end) {
            if (start == idx) {
                Seg[node] = val;
                return;
            }
        }
        int mid = start + (end - start) / 2;
        updateRange(2 * node, start, mid, idx, val);
        updateRange(2 * node + 1, mid + 1, end, idx, val);
        Seg[node] = max(Seg[2 * node], Seg[2 * node + 1]);
    }


    void update(ll i, ll val) {
        updateRange(1, 0, n - 1, i, val);
    }


    ll query(int node, int start, int end, int l, int r) {
        if (r < start or end < l) return 0;
        if (l <= start and end <= r) return Seg[node];
        int mid = (start + end) / 2;
        ll p1 = query(2 * node, start, mid, l, r);
        ll p2 = query(2 * node + 1, mid + 1, end, l, r);

        return max(p1, p2);
    }

};


int main() {
    /*freopen("inp", "r", stdin);
    freopen("out", "w", stdout);*/
    cin >> n;
    vector<ll> height(n + 1), A(n + 1);
    vector<ll> dp(n + 1);
    for (int i = 0; i < n; i++) cin >> height[i];
    for (int i = 0; i < n; i++) cin >> A[i];
    ll answer = 0;
    NumArray Tree(height);
    for (int i = 0; i < n; i++) {
        ll max_value = Tree.query(1, 0, n - 1, 1, height[i] - 1);
        dp[i] = max_value + A[i];
        Tree.update(height[i], dp[i]);
        answer = max(answer, dp[i]);
    }
    //print(Tree.Seg);
    cout << answer << '\n';
    return 0;
}


Measured memory_bytes: 14336
#include <iostream>
#include <cstring>
int main()
{
	int number[31];
	memset(number,0,sizeof(number));
	for(int i=0; i<30; i++){
		int a; std::cin>>a;
		number[a] = 1;
	}
	for(int i=1; i<31; i++)
		if( !number[i] )printf("%d\n",i);
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void insertionSort(int A[],int N);
void echo(int A[],int N);

int main()
{
	int N;
	scanf("%d",&N);
	
	int A[N];
	
	char str[1024];
	for(;1;)
	{
		fgets(str,sizeof(str),stdin);
		if(strcmp(str,"\n")!=0)
		{
			break;
		}
	}
	
	A[0]=atoi(strtok(str," "));
	
	int i;
	for(i=1;i<N;i++)
	{
		A[i]=atoi(strtok(NULL," "));
	}
	
	insertionSort(A,N);
	
	return 0;
}

void insertionSort(int A[],int N)
{
	int key,i,j;
	echo(A,N);
	for(i=1;i<N;i++)
	{
		key=A[i];
		j=i-1;
		while(j>=0 && A[j]>key)
		{
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=key;
		echo(A,N);
	}
}

void echo(int A[],int N)
{
	int i;
	for(i=0;i<N-1;i++)
	{
		printf("%d ",A[i]);
	}
	printf("%d\n",A[N-1]);
}

Measured memory_bytes: 604
n = int(input())
x = [int(y) for(y) in input().split()]
mi = x[0]
ma = x[0]
total = 0

for z in x :
    if mi > z :
        mi = z
    if ma < z :
        ma = z
    total += z
    
print("%d %d %d" %(mi, ma, total))


Measured memory_bytes: 6604
// AOJ ALDS1_4_B Binary Search
// 2018.4.27 bal4u

#include <stdio.h>

// 数値のハッシュ関数
#define HASHSIZ 250007
int hash[HASHSIZ+3], *hashend = hash+HASHSIZ;

int lookup(int n)
{
	int *p;
	
	n++; p = hash + n % HASHSIZ;
	while (*p) {
		if (*p == n) return 1;
		if (++p == hashend) p = hash;
	}
	return 0;
}

void insert(int n)
{
	int *p;
	
	n++; p = hash + n % HASHSIZ;
	while (*p) {
		if (*p == n) return;
		if (++p == hashend) p = hash;
	}
	*p = n;
}

// バッファを経ずstdinから数値を得る
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int main()
{
	int n, q, C;

	n = in();
	while (n--) insert(in());

	C = 0;
	q = in();
	while (q--) if (lookup(in())) C++;
	
	printf("%d\n", C);
	return 0;
}



Measured memory_bytes: 2704
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	
	static ArrayList<Double> answerX = new ArrayList<Double>();
	static ArrayList<Double> answerY = new ArrayList<Double>();
	
	public static void main(String[] args) {
				
		try{
			setAnswerFromInputs();
		}catch(NoSuchElementException e){
			//üÍÌIíèðó¯æÁÄ½àµÈ¢ÅÌÖ
		}
		
		//x,yÌoÍ
		//üÍª³íÅ êÎx,yÌðXgÌ·³Í¯¶ÈÌÅ
		//±±ÅÍXgÌ·³ð`FbNµÈ¢
		for(int i = 0; i < answerX.size(); i++){
			System.out.printf("%.3f %.3f\n", answerX.get(i), answerY.get(i));
		}
	}
	
	private static void setAnswerFromInputs() throws NoSuchElementException{
		while(true){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int d = sc.nextInt();
			int e = sc.nextInt();
			int f = sc.nextInt();
			double x = getX(a, b, c, d, e, f);
			double y = getY(a, b, c, d, e, f);
			x = fixIncorrectNumber(x);
			y = fixIncorrectNumber(y);
			answerX.add(x);
			answerY.add(y);
		}
	}
	
	private static double getX(int a, int b, int c, int d, int e, int f){
		int denominator = a * e - b * d;
		int numerator = c * e - b * f;
		return (double)numerator / (double)denominator;
	}
	
	private static double getY(int a, int b, int c, int d, int e, int f){
		int denominator = b * d - a * e;
		int numerator = c * d - a * f;
		return (double)numerator / (double)denominator;
	}
	
	private static double fixIncorrectNumber(double x){
		if(x == (-0.0)){
			x = 0.0;
		}
		return x;
	}
}

Measured memory_bytes: 11000
#include<cstdio>
#include<iostream>
using namespace std;
const int MAX_N = 100;
char room[MAX_N][MAX_N];
int w,h;
int next[4][2] = {
	{0,1},{1,0},{0,-1},{-1,0}
};
void dfs(int x,int y,char c)
{
	room[x][y] = '.';
	for(int k = 0 ; k < 4 ; k++)
	{
		int dx = x + next[k][0];
		int dy = y + next[k][1];
		if(dx >= 0 && dx < h && dy >= 0 && dy < w && room[dx][dy] == c)
		{
			dfs(dx,dy,c);
		}
	}
}
int main()
{
	while(cin >> h >> w, w > 0)
	{
		int result = 0;
		for(int i = 0 ; i < h ; i++)
		{
			scanf("%s",room[i]);
		}
		for(int i = 0 ; i < h ; i++)
			for(int j = 0 ; j < w ; j++)
			{
				if(room[i][j] != '.')
				{
					dfs(i,j,room[i][j]);
					result++;
				}
			}
		printf("%d\n",result);
	}
	return 0;
}


Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        long N = scan.nextLong();
        long answer = 1;
        for (long i = 1; i * i <= N; i++) {
            answer = i * i;
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 23252
#include<iostream>
using namespace std;
int main(){
  string S, T;
  cin >> S >> T;
  int i=0;
  bool flag=true;
  while(S != T && i < S.length()){
    S = S.substr(S.length()-1,1) + S.substr(0, S.length()-1);
    i++;
  }
  if(i == S.length()){
    flag = false;
  }
  if(flag==true) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

int main() {
  int N;
  int count = 1;
  int type = 0;
  int b = 0;
  cin >> N;
  vector<long long> A(N);
  for(int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  for(int i = 0; i < N; i++) {
    if(A.at(i) == A.at(N-1)) {
      b++;
    }
  }
  if(N == 1) {
    cout << "1";
  }
  else {
    for(int i = 0; i < N-1; i++) {
      if(A.at(i) == A.at(i+1)) {
        count++;
      }
      else {
        if(count%2 == 1) {
          type++;
        }
        count = 1;
      }
    }
    if(b%2 == 1) {
      type++;
    }
    cout << type;
  }
}


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

const int maxn = 100010;
int n, f[maxn];
vector<int> G[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 2, a; i <= n; i++) {
        scanf("%d", &a), G[a].push_back(i);
    }
    function<void(int)> dfs = [&](int v) {
        vector<int> V;
        for (int u : G[v]) dfs(u), V.push_back(f[u]);
        sort(V.begin(), V.end(), greater<int>());
        for (int i = 0; i < V.size(); i++) {
            f[v] = max(f[v], V[i] + i + 1);
        }
    };
    dfs(1), printf("%d\n", f[1]);
    return 0;
}

Measured memory_bytes: 20552
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int gcd(int x,int y){
	
	if(x%y==0){
		return y;
	}else{
		return gcd(y,x%y);
	}
	
}

int main() {
	
	int A,B,C;
	cin>>A>>B>>C;
	int d=max({A,B,C});
  int ans=A*B*C/d/2;
  ce(ans)
}

Measured memory_bytes: 256
#include <iostream>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define sz(a) ((int)(a).size())
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
#define pii pair<int,int>
#define pdd pair<ld,ld> 
#define rep(i,a,b) for(int i=a; i<b; i++)
#define dec(i,a,b) for(int i=a; i>=b; i--)
#define ler freopen("inspection.in","r",stdin);freopen("inspection.out","w",stdout)
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define debug cout<<"!!?!!\n"
using namespace std;
#define PI 2*asin(1) 
#define EPS 1e-9
#define MOD 1000000007
#define MAXN 101002
#define INF 2e9

int cont[1000];

void decomp(int n){
	for(int i=2; i<=n && n>1; i++){
		while(n%i==0){
			cont[i]++;
			n/=i;
		}
	}
}

ll ans(){
	ll r=1;
	
	rep(i,0,1000){
		r*= (cont[i]+1);
		r%= MOD;
	}
	return r;
}

int main(){
	int n;
	cin >> n;
	
	rep(i,2,n+1) decomp(i);
	cout << ans() << endl;
}















Measured memory_bytes: 256
#include <stdio.h>
#define N 100

int main(){
  int n,u,k,v;
  int M[N][N];
  int i,j;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      M[i][j] = 0; 
    }
  }
  
  for(i = 0; i < n; i++){
    scanf("%d %d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d",&v);
      M[u-1][v-1] = 1;
    }
  }

  for(i = 0; i < n; i++){
    for(j = 0; j < n-1; j++){
     printf("%d ",M[i][j]);
    }
    printf("%d\n",M[i][j]);
  }
  return 0;
}



Measured memory_bytes: 1988
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<pair<double,double>> xy(n);
    rep(i,n){
        double x,y;cin>>x>>y;
        xy[i]={x,y};
    }
    double ans = 10000;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double px, py;
            double a=xy[i].first,b=xy[i].second,c=xy[j].first,d=xy[j].second; 
            px = (a+c)/2,py=(b+d)/2;
            double r = sqrt((px-a)*(px-a)+(py-b)*(py-b));
            r *= 1.00000005;
            bool ff = true;
            for(int l = 0; l < n; l++){
                double x = px-xy[l].first,y=py-xy[l].second;
                if(x*x+y*y>r*r)ff=false;
            }
            if(ff)ans = min(ans,r);          
        }
    }


    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                double px, py;
                double a=xy[i].first,b=xy[i].second,c=xy[j].first,d=xy[j].second,e=xy[k].first,f=xy[k].second;
                py = ((e-a)*(a*a+b*b-c*c-d*d)-(c-a)*(a*a+b*b-e*e-f*f))/(2*(e-a)*(b-d)-2*(c-a)*(b-f));
                if(a!=c){
                    px = (2*(b-d)*py-a*a-b*b+c*c+d*d)/(2*(c-a));
                }
                else
                {
                    px = (2*(b-f)*py-a*a-b*b+e*e+f*f)/(2*(e-a));
                }
                double r = sqrt((px-a)*(px-a)+(py-b)*(py-b));
                r *= 1.00000005;
                bool ff = true;
                for(int l = 0; l < n; l++){
                    double x = px-xy[l].first,y=py-xy[l].second;
                    if(x*x+y*y>r*r)ff=false;
                }
                if(ff)ans = min(ans,r);
            }
        }
    }
    cout<<setprecision(12)<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

constexpr lli inf = 10000 * 10000;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	lli n, k;
	cin >> n >> k;

	lli Max = (n - 1) * (n - 2) / 2;

	if (k > (n - 1)* (n - 2) / 2) {
		cout << -1 << endl;
		return 0;
	}

	lli m = n - 1 + (Max - k);

	cout << m << endl;

	for (int i = 0; i < n - 1; i++) {
		cout << 1 << " " << i + 2 << endl;
	}


	int count = 0;
	for (int i = 2; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (count < Max - k) {
				count++;
				cout << i << " " << j << endl;
			}
			else {
				return 0;
			}
		}
	}




	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,tot,a[2010],in[2010],head[2010],nxt[10010],to[10010];
bool vis[2010];
inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
inline void add_edge(int u,int v){
	nxt[++tot]=head[u];
	to[tot]=v;
	head[u]=tot;
	return;
}
void dfs(int u){
	vis[u]=1;
	for(int i=1;i<=n;i++)
		if(!vis[i]&&gcd(a[u],a[i])!=1){
			add_edge(u,i);
			in[i]++;
			dfs(i);
		}
	return;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		for(int j=n;j;j--)
			if(!in[j]){
				printf("%d ",a[j]);
				for(int k=head[j];k;k=nxt[k])
					in[to[k]]--;
				in[j]=-1;
				break;
			}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<bool> vec){
    ll n = vec.size();
    rep(i,n) cout << i << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

int main(){
    ll d; cin >> d;
    vector<ll> c(26);
    rep(i,26) cin >> c.at(i);
    vector<vector<ll>> s(d,vector<ll>(26));
    rep(i,d) rep(j,26) cin >> s.at(i).at(j);
    vector<ll> last(26,0);

    ll bestsat = -1;

    srand(time(NULL));
    vector<ll> best(d,0);
    ll times = 100000;
    while(times--){
        ll sat = 0;
        vector<ll> ans(d,0);
        rep(i,d){
            ans.at(i) = (rand() % 26) + 1;
        }
        for(int i=1;i<=d;i++){
            ll t = ans.at(i-1);
            t--;
            last.at(t) = i;
            sat += s.at(i-1).at(t);
            for(int j=0;j<26;j++){
                sat -= c.at(j) * (i - last.at(j));
            }
            //cout << sat << endl;
        }
        if(sat>bestsat){
            bestsat = sat;
            best = ans;
        }
    }

    rep(i,d){
        cout << best.at(i) << endl;
    }
  
    //cout << bestsat << endl;

    /*
    for(int i=1;i<=d;i++){
        ll t; cin >> t;
        t--;
        last.at(t) = i;
        sat += s.at(i-1).at(t);
        for(int j=0;j<26;j++){
            sat -= c.at(j) * (i - last.at(j));
        }
        cout << sat << endl;
    }
    */
    return 0;
}

Measured memory_bytes: 3724
l = list(input())
count = 0
currStr = ""
nextStr = ""
if len(l) >= 2:    
    for i in range(len(l)-1):
        currStr = l[i]
        nextStr = l[i+1]
        if currStr == nextStr:
            count += 1
            if nextStr == "1":
                l[i+1] = "0"
            else:
                l[i+1] = "1"

print(count)

Measured memory_bytes: 3956
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

pll a[100000] = {};

int main(void) {

	lli N, M;
	cin >> N >> M;

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

	sort(a,a+N);

	lli ans = 0, count = 0;

	for (int i = 0; i < N; i++) {
		ans += a[i].first * min(M - count,a[i].second);
		count += min(M - count, a[i].second);
	}

	COUT(ans);

	return 0;
}

Measured memory_bytes: 1792
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
//#pragma GCC optimize("unroll-loops")

#ifdef __APPLE__
    # include <iostream>
    # include <cmath>
    # include <algorithm>
    # include <stdio.h>
    # include <cstdint>
    # include <cstring>
    # include <string>
    # include <cstdlib>
    # include <vector>
    # include <bitset>
    # include <map>
    # include <queue>
    # include <ctime>
    # include <stack>
    # include <set>
    # include <list>
    # include <random>
    # include <deque>
    # include <functional>
    # include <iomanip>
    # include <sstream>
    # include <fstream>
    # include <complex>
    # include <numeric>
    # include <immintrin.h>
    # include <cassert>
    # include <array>
    # include <tuple>
    # include <unordered_map>
    # include <unordered_set>
    # include <thread>
#else
    # include <bits/stdc++.h>
#endif

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;
#define int long long

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

const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
const ll inf=1e18+10;

///---program start---///

int h,w,n;

bool is_ok_start(int a,int b)
{
    return a>=1&&b>=1&&a+2<=h&&b+2<=w;
}

signed main()
{
    #ifdef __APPLE__
        files("barik");
        freopen("debug.txt","w",stderr);
    #endif

    cin>>h>>w>>n;

    vector<pii> black;
    vector<pii> interesting;
    for (int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        black.pb(mp(a,b));
        for (int dx=0;dx>=-2;dx--){
            for (int dy=0;dy>=-2;dy--){
                if (is_ok_start(a+dx,b+dy)){
                    interesting.pb(mp(a+dx,b+dy));
                }
            }
        }
    }
    sort(all(black));
    sort(all(interesting));
    interesting.resize(unique(all(interesting))-interesting.begin());

    vi ans(10);
    for (auto i:interesting){
        int cur=0;
        for (int dx=0;dx<=2;dx++){
            for (int dy=0;dy<=2;dy++){
                cur+=(binary_search(all(black), mp(i.fir+dx,i.sec+dy)));
            }
        }
        ans[cur]++;
    }
    ans[0]+=(w-2)*(h-2)-len(interesting);

    for (auto i:ans){
        cout<<i<<"\n";
    }
}


Measured memory_bytes: 20584
#include <stdio.h>



int main(void)
{
	//変数の宣言
	int n;
	signed int i=0;
	signed int array[50];
	int amari;
	
	//データの読み込み
	scanf("%d",&n);
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
	while(n!=0){
		i++;
		array[i]=n%-2;
		if(array[i]==-1){
			n=n/-2+1;
			array[i]=1;
		}else{
			n=n/-2;
		}
	}
		
	
//	printf("計算部分終了\n");
	
	//出力
	if(i==0){
		printf("0");
	}else{
		while(i>0){
			printf("%d",array[i]);
			i--;
		}
	}
	
//	printf("結果の出力終了\n");
	
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

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

    int k;
    cin >> k;

    int num = 7;
    rep (i, k)
    {
        if (num % k == 0)
        {
            cout << i + 1 << "\n";
            return 0;
        }
        num = (num * 10 + 7) % k;
    }

    cout << "-1\n";
    return 0;
}



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

int main(void){
    int N, X, Y;
    int diff, min_diff;
    int diffs[2000] = {0};
    int i, j;

    scanf("%d%d%d", &N, &X, &Y);
    for(i = 1; i <= N-1; i++){
        for(j = i+1; j <= N; j++){
            min_diff = j - i;
            diff = abs(X-i) + abs(Y-j) + 1;
            if(diff < min_diff)
                min_diff = diff;
            diff = abs(X-j) + abs(Y-i) + 1;
            if(diff < min_diff)
                min_diff = diff;
            diffs[min_diff-1]++;
        }
    }

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

    return 0;
}


Measured memory_bytes: 128
t = list(input())
for i in range(len(t)):
    if t[i]=="?":
        if i==0 and len(t)!=1:
            if t[i+1]=="D" or t[i+1]=="?":
                t[i] = "P"
                t[i+1] = "D"
            else:
                t[i] = "D"
        elif i!=len(t)-1:
            if t[i-1]=="P":
                t[i] = "D"
            elif t[i+1]=="D" or t[i+1]=="?":
                t[i] = "P"
                t[i+1] = "D"
            else:
                t[i] = "D"
        else:
            t[i] = "D"
print(*t,sep="")

Measured memory_bytes: 13612
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

opr = ["+++","++-","+--","---","+-+","-++","--+","-+-"]

ABCD = list(input())
for op in opr:
	ans = []
	ABCD_ = ABCD.copy()
	op = list(op)
	ans.append(ABCD_.pop(0))
	while ABCD_ != []:
		ans.append(op.pop(0))
		ans.append(ABCD_.pop(0))
	if eval("".join(ans)) == 7:
		print("".join(ans), "=7", sep="")
		sys.exit(0)


Measured memory_bytes: 3896
# include <iostream>
# include <string>
# include <algorithm>
# include <vector>
# include <cstring>
# include <stdio.h>
# include <map>
# include <queue>

# define ll long long
# define pii pair<int,int>
# define FOR(a,b) for(int a=1; a<=b; a++)
# define REP(a,b) for(int a=0; a<b; a++)
# define FORU(a,b,c) for(int a=b; a<=c; a++)
# define FORD(a,b,c) for(int a=b; a>=c; a--)

using namespace std;

int main(){

    ios :: sync_with_stdio(false);
    int N, x;
    cin >> N >> x;
    if(x == 1 || x == 2*N-1){
        cout << "No" << endl;
        return 0;
    }

    if(x <= N){
        cout<<"Yes"<<endl;
		FORU(i,N+x,2*N-1)cout<<i<<endl;
		FOR(i,x+N-1)cout<<i<<endl;
    }
    else{
        cout<<"Yes"<<endl;
		FORD(i,x-N,1)cout<<i<<endl;
		FORD(i,2*N-1,x-N+1)cout<<i<<endl;
    }
    return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv)
{
    int n, h, w;
    int a, b;
    int i;
    int c;

    scanf("%d %d %d", &n, &h, &w);

    c = 0;
    for (i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        if (a >= h && b >= w) {c++;}
    }

    printf("%d\n", c);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}

vector<pair<char, int>> run_length_compress(string S)
{
    vector<pair<char, int>> res;
    int n = S.size(), cnt = 1;
    for (int i = 0; i < n - 1; i++)
    {
        if (S[i] == S[i + 1])
        {
            cnt++;
        }
        else
        {
            res.push_back({S[i], cnt});
            cnt = 1;
        }
    }
    res.push_back({S.back(), cnt});
    return res;
}
int main()
{
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    auto c = run_length_compress(S);
    vll L, R, A(N + 1);
    int cnt = 0;
    for (auto &&i : c)
    {
        cnt += i.second - 1;
    }
    cout << min(cnt + 2 * K, N - 1);

    return 0;
}

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

using namespace std;

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

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

constexpr ll INF=1e18;
constexpr int MAX_V=2525;

struct edge{
	int to;
	ll cost;
};

int V;
// 頂点sからの最短距離
ll d[MAX_V];
vector<edge> g[MAX_V], g2[MAX_V];
bool can[2525], can2[2525];

void add_edge(int from, int to, ll cost){
	g[from].push_back({to, cost});
	return;
}

void add_edge2(int from, int to, ll cost){
	g2[from].push_back({to, cost});
	return;
}

struct edge2 {
	int from;
	int to;
 	ll cost;
};

// 辺
edge2 es[5252];

// 最短距離
// int d[MAX_V];
int E;

void add_edge3(int from, int to, int cost){
	es[E++]={from, to, cost};
	return;
}

// 負の閉路があるか判定
bool find_negative_loop(){
	memset(d, 0, sizeof(d));
	REP(i, V){
		REP(j, E){
			edge2 e=es[j];
			if(!can[e.to] || !can2[e.to] || !can[e.from] || !can2[e.from]){
				continue;
			}
			if(d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				if(i==V-1){
					return true;
				}
			}
		}
	}
	return false;
}

void dijkstra(int s){
	// piiのfirstは最短距離、secondは頂点の番号
	priority_queue<pll, vector<pll>, greater<pll>> que;
	fill(d, d+V, INF);
	d[s]=0;
	que.push({0, s});
	while(!que.empty()){
		pll p=que.top();
		que.pop();
		int v=p.second;
		if(d[v]<p.first){
			continue;
		}
		REP(i, g[v].size()){
			edge e=g[v][i];
			if(!can[e.to] || !can2[e.to]){
				continue;
			}
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push({d[e.to], e.to});
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n, m, a, b;
	ll p, c;
	cin>>n>>m>>p;
	REP(i, m){
		cin>>a>>b>>c;
		--a;--b;
		add_edge(a, b, p-c);
		add_edge2(b, a, p-c);
		add_edge3(a, b, p-c);
	}
	V=n;
	queue<int> q;
	q.push(n-1);
	can[n-1]=true;
	while(q.size()){
		int x=q.front();
		q.pop();
		for(auto & y : g2[x]){
			if(can[y.to]){
				continue;
			}
			can[y.to]=true;
			q.push(y.to);
		}
	}
	queue<int> q2;
	q2.push(0);
	can2[0]=true;
	while(q2.size()){
		int x=q2.front();
		q2.pop();
		for(auto & y : g[x]){
			if(can2[y.to]){
				continue;
			}
			can2[y.to]=true;
			q2.push(y.to);
		}
	}
	if(!can[0] || find_negative_loop()){
		cout<<-1<<'\n';
		return 0;
	}
	dijkstra(0);
	cout<<max(0ll, -d[n-1])<<'\n';
	return 0;
}


Measured memory_bytes: 896
s = list(input())

for i, code in enumerate(s):
    # if code == '?' and s[i-1] =='P':
    #     s[i] = 'D'
    # elif code == '?' and s[i-1] =='D':
    #     s[i] = 'P' 
    # elif code =='?' and i == 0:
    #     s[i] = 'D'
    if code =='?':
        s[i] = 'D'

ans = ''.join(s)
print(ans)


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

long long N, M;
vector<long long> L;
vector<long long> R;

int main(){
	cin >> N >> M;
	for(long long i = 0; i < M; i++){
		long long l,r;
		cin >> l >> r;
		L.push_back(l);
		R.push_back(r);
	}
	cout << max((long long)0, *(min_element(R.begin(), R.end())) - *(max_element(L.begin(), L.end())) + 1) << endl;
}

Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int x;
    in>>x;
    cout<<x/500*1000+(x%500)/5*5<<endl;
}

Measured memory_bytes: 256
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<int,int> point;
#define rep(i,n) for(i,0,n)

// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
 

int main() {
	// 入力
	ll N;
	cin >> N;
 
	// 解法
	ll a = (N-1)/111+1;
	cout << 111*a << endl;
}
 


Measured memory_bytes: 256
from decimal import *
x,y,z = map(int,input().split())
a=Decimal(x)
b=Decimal(y)
c=Decimal(z)
if Decimal((c-a-b)**Decimal(2)) > Decimal(Decimal(4)*a*b) and c-a-b > 0:
    print('Yes')
else:
    print('No')

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

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

double dp[100002][13] = {0};
int main(){
	//dp[i][j] := i??\??????j?????£?¶???????????¢????
	//????????????????????????1+?????¨?????£?¶??????°????¢??????????????¢???????????????????????????°OK
	//12?????£?¶????????????§?????????????????°??????
	//?????°???dp
	int n;
	while(cin >> n, n){
		REP(i,100002) REP(j,13) dp[i][j] = 0;
		dp[1][1] = 1.0;
		double ans = 1.0;
		FOR(i,1,n){
			REP(j,12){
				if(dp[i][j]==0) continue;
				double p = pow(0.5,j);
				if(j==0){
					//??£?¶??????°???0???????????¨???????????£??????????????????????????¨??????
					dp[i+1][1] += dp[i][0];
					ans += dp[i][0];
				}else{
					dp[i+1][j+1] += dp[i][j]*p;     //??¨??????
					dp[i+1][0] += dp[i][j]*(1.0-p); //??¨?????????
					ans += dp[i][j]*p;
				}
			}
		}
		cout << shosu(15) <<  ans << endl;
	}
}

Measured memory_bytes: 11392
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, sx, sy, tx, ty;
int x[1005][1005];
char y[1005][1005];
deque<pair<int, int>> q;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &tx, &ty);
	for (int i = 1; i <= n; i++)
		scanf("%s", y[i] + 1);
	x[sx][sy] = 1;
	q.emplace_back(sx, sy);
	while (!q.empty()) {
		tie(sx, sy) = q.front();
		q.pop_front();
		for (int i = 0; i < 4; i++) {
			int ta = sx + dx[i];
			int tb = sy + dy[i];
			if (y[ta][tb] == '.' && (!x[ta][tb] || x[sx][sy] < x[ta][tb])) {
				x[ta][tb] = x[sx][sy];
				q.emplace_front(ta, tb);
			}
		}
		for (int i = sx - 2; i <= sx + 2; i++)
			for (int j = sy - 2; j <= sy + 2; j++) {
				if (y[i][j] == '.' && (!x[i][j] || x[i][j]>x[sx][sy])) {
					x[i][j] = x[sx][sy] + 1;
					q.emplace_back(i, j);
				}
			}
	}
	// for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) printf("%d", x[i][j]); puts("");}
	printf("%d\n", x[tx][ty] ? x[tx][ty] - 1 : -1);
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    int n[4];
    rep(i, 4) { cin >> n[i]; }

    int memo[4] = {1, 9, 7, 4};
    sort(n, n + 4);
    sort(memo, memo + 4);

    rep(i, 4) {
        if (n[i] != memo[i]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

    return 0;
}



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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  int64_t ans=0;
  for(int i=0;i<1000;i++){
    vector<int> c(3);
    c.at(0) = i/100;
    c.at(1) = i/10%10;
    c.at(2) = i%10;
    int f=0;
  	for(int j=0;j<N;j++){
      int s = S.at(j) - '0';
      if (s == c.at(f)) f++;
      if (f == 3) break;
  	}
    if(f==3)ans++;
  }
  cout << ans << endl;
}

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

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL)
// #define int long long 

using namespace std;

int32_t main()
{
	fio;
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if(a>=k)
	{
		cout<<k<<endl;
	}
	else if(a+b>=k)
	{
		cout<<a<<endl;
	}
	else
	{
		cout<<a-(k-(a+b))<<endl;
	}
	return 0;
}

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

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

  vector<int> h(n);
  for (int i = 0; i < n; ++i)
    cin >> h[i];

  vector<int> dp(n);
  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);
  for (int i = 2; i < n; ++i) {
    int c1 = dp[i - 1] + abs(h[i - 1] - h[i]);
    int c2 = dp[i - 2] + abs(h[i - 2] - h[i]);
    dp[i] = min(c1, c2);
  }
  cout << dp.back() << endl;
}

Measured memory_bytes: 1024
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]
#a = [int(input()) for _ in range(n)]

s = input()

print(s.count("+") - s.count("-"))


Measured memory_bytes: 9020
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
void pr(){ln;}
template<Z A,Z...B>void pr(const A &a,const B&...b){cout<<a<<' ';pr(b...);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  ll a[n];
  rep(i,n) R a[i];
  ll b[n];
  rep(i,n) b[i]=a[i];
  map<ll,ll> m;
  rrep(i,n) {
    b[i]+=b[0];
    b[i]-=i;
  }
  rep(i,n) m[b[i]]++;
  ll ans=0,x=0;
  rep(i,n-1) {
    m[b[i]]--;
    ans+=m[x];
    x-=a[i+1]-a[i]+1;
  }
  pr(ans);
}

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


Measured memory_bytes: 29476
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    int num;
    cin >> num;
    long long ans=0;
    for(int i=0;i<=num;i++){
        if((i%3!=0)&&(i%5!=0)){
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n,k; cin >> n>>k;
    vint a(n);
    rep(i,n) cin>>a[i];
    int res=INF;
    for(int i=0; i+k<n+1; i++){
        int l=a[i],r=a[i+k-1];
        chmin(res,min(abs(r)+abs(r-l),abs(l)+abs(r-l)));
    }   
    cout<<res<<endl;
}

Measured memory_bytes: 4000
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=2333333;
const int MAXM=2333333;
int n,a[MAXN+10],id[MAXN+10];
int fir[MAXN+10],nxt[MAXM+10],to[MAXM+10],tote;
void adde(int u,int v){to[++tote]=v;nxt[tote]=fir[u];fir[u]=tote;}
bool cmp(const int x,const int y){return a[x]<a[y];}
bool flag[MAXN+10];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",a+i),id[i]=i;
	for(int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	sort(id+1,id+n+1,cmp);
	for(int cc=1,u;u=id[cc],cc<=n;++cc)
	{
		for(int i=fir[u],v;v=to[i],i;i=nxt[i])
		{
			if(a[v]>=a[u])continue;
			flag[u]|=!flag[v];
		}
	}
	for(int i=1;i<=n;++i)if(flag[i])printf("%d ",i);
	return 0;
}

Measured memory_bytes: 10496
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i=1,a;
    while(scanf("%d",&a)!=EOF)
    {
        if(a!=0)
        {
            cout<<"Case "<<i<<": "<<a<<endl;
            i++;
        }

        else if(a==0)
        {
            break;
        }
    }
}



Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	int r=n%10;
	if(r==3){
		cout << "bon" <<endl;
	}
	else if(r==0||r==1||r==6||r==8){
		cout <<"pon" << endl;
	}
	else{
		cout << "hon" << endl;
	}
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).rbegin(), (x).rend())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
#define SP << " " <<
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    ll a,b,c; cin>>a>>b>>c;
    if(c-a-b<=0) {
        cout<< "No"<<"\n"; return;
    }
    cout<< ( a*b*4<(c-a-b)*(c-a-b) ? "Yes" : "No" )<<"\n";

}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


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

int pw[110][11000];
int qw[110][11000];
int f[110], g[110];
int dp[2][110][110];
int ex[11000];

int a[110][110];
int b[110][110];

int fast_exponentiation(int a, int n, int p) {
	int ret = 1;
	for (; n; n >>= 1, a = 1LL * a * a % p) if (n & 1) ret = 1LL * ret * a % p;
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, k, mod; cin >> n >> m >> k >> mod;
	for (int x = 0; x <= k; x++) {
		for (int j = 0; j <= n * m; j++) {
			pw[x][j] = j == 0 ? 1 : pw[x][j - 1] * 1LL * x % mod;
		}
		int y = fast_exponentiation(x, mod - 2, mod);
		for (int j = 0; j <= n * m; j++) {
			qw[x][j] = j == 0 ? 1 : qw[x][j - 1] * 1LL * y % mod;
		}
	}
	for (int i = 0; i <= max(n, m); i++) {
		f[i] = i == 0 ? 1 : f[i - 1] * 1LL * i % mod;
		g[i] = fast_exponentiation(f[i], mod - 2, mod);
	}
	int M = 2 * m + 1, N = 2 * n + 1;
	dp[0][0][0] = 1;
	int now = 0;
	for (int i = 1; i < k; i++) {
		now ^= 1;
		int alpha = (1 + qw[k - i][1]) % mod;
		for (int j = 0; j <= n * m; j++) {
			ex[j] = j == 0 ? 1 : ex[j - 1] * 1LL * alpha % mod;
		}
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				a[r][c] = dp[!now][r][c] * 1LL * pw[i][(n - r) * (m - c)] % mod;
			}
		}
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				b[r][c] = 0;
				for (int x = 0; x <= r; x++) {
					b[r][c] = (b[r][c] + a[x][c] * 1LL * g[r - x]) % mod;
				}
			}
		}
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				a[r][c] = 0;
				for (int x = 0; x <= c; x++) {
					a[r][c] = (a[r][c] + b[r][x] * 1LL * g[c - x]) % mod;
				}
				a[r][c] = a[r][c] * 1LL * ex[r * c] % mod;
			}
		}
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				b[r][c] = 0;
				for (int x = 0; x <= r; x++) {
					if (r - x & 1) b[r][c] = (b[r][c] + a[x][c] * 1LL * (mod - g[r - x])) % mod;
					else b[r][c] = (b[r][c] + a[x][c] * 1LL * (g[r - x])) % mod;
				}
			}
		}
		for (int r = 0; r <= n; r++) {
			for (int c = 0; c <= m; c++) {
				a[r][c] = 0;
				for (int x = 0; x <= c; x++) {
					if (c - x & 1) a[r][c] = (a[r][c] + b[r][x] * 1LL * (mod - g[c - x])) % mod;
					else a[r][c] = (a[r][c] + b[r][x] * 1LL * (g[c - x])) % mod;
				}
				dp[now][r][c] = a[r][c] * 1LL * qw[i][(n - r) * (m - c)] % mod;
			}
		}
	}
	int ans = 0;
	for (int r = 0; r <= n; r++) {
		for (int c = 0; c <= m; c++) {
			ans = (ans + g[n - r] * 1LL * g[m - c] % mod * dp[now][r][c] % mod * pw[k][(n - r) * (m - c)]) % mod;
		}
	}
	ans = 1LL * ans * f[n] % mod * f[m] % mod;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9600