akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
  int h, r;
  cin >> h >> r;

  if(-h == r && h != 0) cout << 0 << endl;
  else if(h >= 0 && r >= 0) cout << 1 << endl;
  else if(h < 0 || r < 0) cout << -1 << endl;

  return 0;

}




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

int D;

int main() {
    cin >> D;
    
    switch (D) {
        case 25:
            cout << "Christmas" << endl;
            break;
        case 24:
            cout << "Christmas Eve" << endl;
            break;
        case 23:
            cout << "Christmas Eve Eve" << endl;
            break;
        case 22:
            cout << "Christmas Eve Eve Eve" << endl;
            break;
        default:
            break;
    }
}

Measured memory_bytes: 256
def slove():
    import sys
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    if a == b:
        print(a + b)
    elif a > b:
        print(a + (a - 1))
    elif a < b:
        print(b + (b - 1))


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
        String b = "Yes";
		if(s.equals("AAA") || s.equals("BBB")){b = "No";}
		System.out.println(b);
	}
}


Measured memory_bytes: 21716
# -*- coding: utf-8 -*-
import math

def combination(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r))

[N, M] = [int(i) for i in input().split()]

ans = combination(N, 2)
ans += combination(M, 2)

print(int(ans))

Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>
int hantei(int a);
int main(){
  int a,B[100000],z,count=0,i;
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%d",&B[i]);
    z=hantei(B[i]);
    if( z == 0 )count++;
  }
  printf("%d\n",count);
}
int hantei(int a){
  int i=3;
  if(a == 2)return 0;
  if(a < 2 || a % 2 == 0)return 1;
  while(i <= pow(a,0.5) ){
    if(a%i == 0 )return 1;
    i+=2;
  }
 return 0;
}


Measured memory_bytes: 2916
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree = 
//  tree<key, val, less<key>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = /*1'000'000'007;*/998244353;
const int base = 2187;
const double eps = 1e-8;
const int N = 200'001;

int n, m, k;

void solve(int test)
{
  int w, h;
  cin >> n >> w >> h;
  cout << (n - h + 1) * (n - w + 1) << '\n';
}

void precalc()
{
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i)
      solve(i);
  //cerr << endl << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

class MaxFlow{
public:
    struct edge{
        int to,cap,rev;
        edge(int t,int c,int r):to(t),cap(c),rev(r){}
    };
    const int inf = (1<<29);
    int N;
    vector<vector<edge>> G;
    vector<bool> used;

    MaxFlow(int n):N(n),G(n),used(n){}

    void add_edge(int from,int to,int cap){
        G[from].push_back(edge(to,cap,G[to].size()));
        G[to].push_back(edge(from,0,G[from].size()-1));
    }

    int dfs(int v,int t,int f){
        if(v==t) return f;
        used[v]=true;
        for(edge &e : G[v]){
            if(!used[e.to] and e.cap>0){
                int d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int max_flow(int s,int t){
        int flow=0;
        while(1){
            used.assign(N,false);
            int f=dfs(s,t,inf);
            if(f==0) return flow;
            flow += f;
        }
    }
};

int main(){
    int N;
    cin >> N;
    vi a(N),b(N);
    rep(i,N) cin >> a[i] >> b[i];
    vi c(N),d(N);
    rep(i,N) cin >> c[i] >> d[i];

    MaxFlow flow(2*N+2);

    rep(i,N) flow.add_edge(2*N,i,1);
    rep(i,N) flow.add_edge(i+N,2*N+1,1);
    rep(i,N){
        rep(j,N){
            if(a[i] < c[j] and b[i] < d[j]){
                flow.add_edge(i,j+N,1);
            }
        }
    }

    int mf = flow.max_flow(2*N,2*N+1);

    cout << mf << endl;
}


Measured memory_bytes: 384
s = input()
t = ""
ans = 0
tmp = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if s[j] in ["A", "G", "C", "T"]:
            t += s[j]
            if j == len(s) - 1:
                tmp = max(tmp, len(t))
                t = ""
                ans = 0
        else:
            tmp = max(tmp, len(t))
            t = ""
            ans = 0

            break
print(tmp)

Measured memory_bytes: 3064
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>
#include <utility>
#include <numeric>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for (int i=0; i<(n); ++i)

using namespace std;
using ll = long long;

int main (){
    int N,K;
    cin >> N>>K;
    
    vector <int> p(N);
    int sum[N+1]={0};
    for (int i=0;i<N;i++){
        cin >> p[i];
        sum[i+1]=sum[i]+ (p[i]+1);
        // cout << sum[i+1];
    }
    int mx=0;
    for (int i=0;i+K<=N;i++){
        
        mx = max(mx,sum[i+K] - sum[i]);
        // cout << mx;
    }
    double ans = mx;

    printf("%.10f",ans/2);



    


}

Measured memory_bytes: 1792
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int A = sc.nextInt();
    int B = sc.nextInt();
    
    System.out.println(A <= 8 && B <= 8 ? "Yay!" : ":(");
  }
}

Measured memory_bytes: 21716
#include <cstdio>

/*
	<정리>
	p[1] ..., p[n]이 모든 k := 1, ..., n-1에 대하여
	swap(k, k + 1)이 가능한 수열일 때
	swap(1, n)도 가능하다.
	
	<증명>
	수학적 귀납법으로 증명한다.

	n = 2이면 자명하다.

	n = k일 때 성립한다고 가정하자.
	길이가 k + 1인 조건을 만족하는 수열에 대하여 swap(k, k + 1)은 가능하다. 
	가정에 의해서 swap(1, k)도 가능하다. 두 연산을 수행하면

	p[k+1], p[2], ..., p[1], p[k].

	이제 swap(k, k + 1)을 수행한다.
	
	p[k+1], p[2], ..., p[k], p[1]

	따라서 swap(1, k + 1)은 가능하다.
	따라서 수학적 귀납법에 의해, 모든 n >= 2에 대하여 명제를 만족한다.

	<풀이>
	위 정리에 의해서 x -> i로의 경로가 있으면 가능한 것으로 세면 된다.
	x = x인 경우 자동으로 연결된 것으로 간주되어 가능한 것으로 셀 수 있다.
	
	그런데 N, M이 10^5이라서 DFS나 Dijkstra를 돌리면 터진다. (N^2 lg M)
	따라서 Union and Find로 Disjoint Set을 형성하여, 두 원소 사이의 경로가
	있는지를 확인하여야 한다.

	Union and Find 코드는 https://en.wikipedia.org/wiki/Disjoint-set_data_structure
	에서 볼 수 있다.
*/
int N, M;
int nums[100001];
int root[100001];
int rank[100001];

void swap(int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

int find(int x)
{
	if (root[x] != x)
		root[x] = find(root[x]);
	return root[x];
}

void disjoint(int x, int y)
{
	int rx = find(x);
	int ry = find(y);
	if (rank[rx] < rank[ry])
		swap(rx, ry);
	root[ry] = rx;
	if (rank[rx] == rank[ry])
		++rank[rx];
}

int main(void)
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	for (int n = 1; n <= N; ++n)
	{
		scanf("%d", nums + n);
		root[n] = n;
	}
	for (int m = 1; m <= M; ++m)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		disjoint(x, y);
	}
	
	int cnt = 0;
	for (int n = 1; n <= N; ++n)
	{
		if (find(n) == find(nums[n]))
			++cnt;
	}
	printf("%d", cnt);
	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
#include<map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)
#define FORR(i,n,m) for(ll i=n-1;i>=m;i--)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K

int main(){
    ll A,B,K;
    cin >> A >> B >> K;
    if(abs(A-B)>=K*2){
        FOR(i,A,A+K){cout << i << endl;}
        FOR(i,B-K,B){cout << i+1 << endl;}
    }else{
        FOR(i,A,B+1){
            cout << i << endl;
        }
    }
    return 0;
}

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

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

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 100005 ;

int n , a , b ;
char s[MAXN] ;

void solve () {
	int x = 0 , y = 0 ;
	for ( int i = 0 ; i < n ; ++ i ) {
		if ( s[i] == 'c' ) printf ( "No\n" ) ;
		else if ( s[i] == 'a' ) {
			if ( x + y < a + b ) {
				printf ( "Yes\n" ) ;
				if ( x < a ) ++ x ;
				else ++ y ;
			} else printf ( "No\n" ) ;
		} else {
			if ( y < b ) {
				printf ( "Yes\n" ) ;
				++ y ;
			} else printf ( "No\n" ) ;
		}
	}
}

int main () {
	while ( ~scanf ( "%d%d%d%s" , &n , &a , &b , s ) ) solve () ;
	return 0 ;
}

Measured memory_bytes: 768
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct ll
{
	int x,y;
	long long v;
}b[600000];
long long ans=0,n,q,a[300000],t=0,f[300000];
int cmp(ll a,ll b)
{
	return a.v<b.v;
}
int find(int x)
{
	if (x==f[x])
	return x;
	return f[x]=find(f[x]);
}
void un(int x,int y)
{
	int fx=find(x),fy=find(y);
	f[fx]=fy;
}
void add(int x,int y,int v)
{
	b[++t].x=x;
	b[t].y=y;
	b[t].v=v;
}
int main()
{
    scanf("%d%d",&n,&q);
	int x,y;
	long long v;
	for (int i=0;i<=n;++i)
	a[i]=1e17;
	for (int i=1;i<=q;++i)
	{
		scanf("%d%d%lld",&x,&y,&v);
	    add(x,y,v);
	    a[x]=min(a[x],v+1);
		a[y]=min(a[y],v+2); 
	}	
	for (int i=1;i<=2;++i)
	for (int j=1;j<=n;++j)
	a[(j%n)]=min(a[(j%n)],a[j-1]+2);
	for (int i=0;i<n;++i)
	add(i,(i+1)%n,a[i]);
	sort(b+1,b+t+1,cmp);
	for (int i=0;i<n;++i)
	f[i]=i;
	for (int i=1;i<=t;++i)
	if (find(b[i].x)!=find(b[i].y))
	{
		un(b[i].x,b[i].y);
		ans+=b[i].v;
		if (t==n-1)
		break;
	}
	printf("%lld\n",ans);
} 

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

const int mod = 1e9 + 7;

int N, M, K;
int fix[22][22], prec[1 << 19][22], dp[2][1 << 19];

int main() {
    scanf("%d %d %d", &N, &M, &K);
    N--;

    memset(fix, -1, sizeof(fix));
    for(int i = 0; i < K; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        fix[a][b] = c;
    }

    for(int i = 0; i < (1 << N); i++) {
        int la = N;
        for(int j = N - 1; j >= 0; j--) {
            if(i & (1 << j)) la = j;
            prec[i][j] = la;
        }
    }

    int c = (N * M) & 1;
    for(int i = 0; i < (1 << N); i++) {
        dp[c][i] = 1;
    }
    for(int i = M - 1; i >= 0; i--) {
        for(int j = N - 1; j >= 0; j--) {
            int c = (i * N + j) & 1;
            int p = c ^ 1;

            for(int k = 0; k < (1 << N); k++) {
                dp[c][k] = 0;

                if(fix[i][j] != 0) {
                    int t = prec[k][j];
                    if(t == N) {
                        dp[c][k] += dp[p][ k ^ (1 << j) ];
                        dp[c][k] %= mod;
                    }
                    else {
                        dp[c][k] += dp[p][ k ^ (1 << t) ^ (1 << j) ];
                        dp[c][k] %= mod;
                    }
                }
                if(fix[i][j] != 1 && !(k & (1 << j))) {
                    dp[c][k] += dp[p][k];
                    dp[c][k] %= mod;
                }

                //cout << i << ' ' << j << ' ' << k << ' ' << dp[c][k] << endl;
            }
        }
    }
    printf("%d", dp[0][0]);
}


Measured memory_bytes: 49536
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;



public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[1000003];
        a[0] = n;
        for (int i = 1 ; i < a.length ; i++) {
            if (a[i - 1] % 2 == 0) {
                a[i] = a[i - 1] / 2;
            } else {
                a[i] = 3 * a[i - 1] + 1;
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int x : a) {
            if (set.contains(x)) {
                System.out.println(set.size() + 1);
                return;
            } else {
                set.add(x);
            }
        }
    }

}

Measured memory_bytes: 26956
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

bool check(int N, string S, string s) {
    int j = 0;
    rep(i, N) {
        if(S[i] == s[j]) {
            j++;
            if(j == 3)
                return true;
        }
    }
    return false;
}

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    int res = 0;
    for(int i = 0; i <= 9; i++) {
        for(int j = 0; j <= 9; j++) {
            for(int k = 0; k <= 9; k++) {
                string s = "";
                s += (char)('0' + i);
                s += (char)('0' + j);
                s += (char)('0' + k);
                if(check(N, S, s))
                    res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

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

int main() {
  int N, A, m = 0, M = 30;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> A;
    while (A % 2 == 0) {
      A /= 2;
      m++;
    }
    if (m < M) {
      M = m;
    }
    m = 0;
  }
  cout << M << endl;
}

Measured memory_bytes: 3592
function Main(input) {
  var array = input.split("\n");
  var array1 = array[0].split(" ");
  var N = array1[0] - 0;
  var D = array1[1] - 0;
  var count = 0;

  for (var i = 1; i <= N; i++) {
    var XY = array[i].split(" ");
    var X = XY[0] - 0;
    var Y = XY[1] - 0;
    var des = Math.sqrt(Math.pow(X, 2) + Math.pow(Y, 2));

    if (des <= D) {
      count++;
    }
  }
  console.log(count)
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 62836
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n-2):
    if p[i+1] < max(p[i],p[i+1],p[i+2]):
        if p[i+1] > min(p[i],p[i+1],p[i+2]):
            ans+=1

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define INF 2000000000

int main(){
    int W,H,N;
    cin >> W >> H >> N;
    int x,y,a;
    int xM,yM,xm,ym;
    xM = W;
    yM = H;
    xm = 0;
    ym = 0;
    REP(i,N) {
        cin >> x >> y >> a;
        switch (a){
            case 1:
                xm = max(xm, x);
                break;
            case 2:
                xM = min(xM, x);
                break;
            case 3:
                ym = max(ym, y);
                break;
            case 4:
                yM = min(yM, y);
                break;
        }
    } 
    cout << max(0, xM-xm)*max(0, yM-ym) << endl;
}

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

int main(){
    int N;
    map<int,int> m;
    cin>>N;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        m[a]++;
    }

    for(const auto& x:m){
        if(x.second>=2){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t r;
    cin >> r;
    double pi = 2*acos(0);
    cout << 2*pi*r << endl;
}

Measured memory_bytes: 3784
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,p[1001],q[1002001],t,k,ans;
int main(){
	while(cin>>n>>m,n){
		rep(i,n)cin>>t,p[i+1]=-t; ans=0,k=(n+1)*(n+1);
		rep(i,n+1)rep(j,n+1)q[i*n+j]=p[i]+p[j]; sort(q,q+k);
		rep(i,k)if(q[i]>=-m){
			int *j=lower_bound(q,q+k,-m-q[i]);
			if(ans>q[i]+*j)ans=q[i]+*j;
		}
		cout<<-ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 4784
package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	if a == b && b == c {
		fmt.Printf("No")
	} else if a == b || b == c || c == a {
		fmt.Printf("Yes")
	} else {
		fmt.Printf("No")
	}

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
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 (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  string s;
  cin >> s;
  if (s[0] == s[2]) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }
}


Measured memory_bytes: 256
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int N;
vi h;
vi dp;

signed main(){

    in(N);
    resz(N,h);
    in(h);

    resize(dp,N);
    fill(all(dp),INF);
    dp[0]=0;
    rep(i,N){
        if(i+1<N) dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]));
        if(i+2<N) dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]));
    }
    out(dp[N-1]);

    return 0;
}


Measured memory_bytes: 1792
package main

import (
   "fmt"
)

func solution(n string) int {
   l := len(n)
   nums := make([]int, l)
   sum := 0
   for i := range n {
        nums[i] = int(n[i] - '0')
        sum += nums[i]
   }

   for i := l - 1; i > 0; i-- {
        nums[i] = 9
        nums[i-1] = nums[i-1] - 1
        tmp := 0
        for j := range nums {
                tmp += nums[j]
        }
        sum = max(sum, tmp)
   }
   return sum
}

func max(x, y int) int {
   if x > y {
        return x
   }
   return y
}

func main() {
   var n string
   fmt.Scan(&n)
   fmt.Println(solution(n))
}

Measured memory_bytes: 1768
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n) 
{ v = vector<T>(n); for (lli i=0; i<n; ++i) cin >> v[i]; }
template<class T, class U> void read_n(vector<pair<T, U>>& v, size_t n)
{ v = vector<pair<T, U>>(n); 
  for (lli i=0; i<n; ++i) cin >> v[i].first >> v[i].second; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct P { lli x, y, d; 
  P(lli x, lli y, lli d) : x(x), y(y), d(d) {}
};

lli h, w;
vector<string> bd;
int main() {
  cin >> h >> w;
  bd.emplace_back(w+2, '#');
  for (lli i=0; i<h; ++i) {
    string s;
    cin >> s;
    bd.push_back('#' + s + '#');
  }
  bd.emplace_back(w+2, '#');
  queue<P> que;
  que.emplace(1, 1, 1);
  bd[1][1] = '*';
  lli gd = -1;
  while(!que.empty()) {
    auto p = que.front();
    lli x = p.x, y = p.y, d = p.d;
    que.pop();
    if (x == w && y == h) { gd = d; break; }
    lli vx = 1, vy = 0;
    for (lli i=0; i<4; ++i) {
      if (bd[y+vy][x+vx] == '.') {
	bd[y+vy][x+vx] = '*';
	que.emplace(x+vx, y+vy, d+1);
      }
      lli t = vx; vx = -vy; vy = t;
    }
  }
  if (gd >= 0) {
    lli sum = 0;
    for (auto&& s : bd) sum += count(begin(s), end(s), '#');
    cout << ((w+2) * (h+2) - sum - gd) << endl;
  } else {
    cout << -1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;
	
	char buf[L], *S , *T, c;
	 
	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}
	
	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}
	
	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	char B[25], *outs=B+20, *outr=B+20;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;
		
		if(!a)*--outs = '0';
		else 
			while(a)
				*--outs = (a % 10) + 48, a /= 10;
		
		if(x)
			*--outs = x;
		
		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

const int MAXN = 100010;
const int MAXP = 10000000;
const u64 MOD = 1000000007;
const f80 MI = f80(1)/MOD;
const ll INF = 10000000000000000LL;
const ll inf = 5000000000000LL;

int n;
int a[MAXN], b[MAXN];
ll sa[MAXN], sb[MAXN];

int main()
{
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%d", &a[i]);
		sa[i] = sa[i-1]+a[i];
	}
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%d", &b[i]);
		sb[i] = sb[i-1]+b[i];
	}
	if (sa[n] < sb[n])
	{
		puts("-1");
		return 0;
	}
	for (int i = 1; i <= n; ++ i)
		a[i] -= b[i];
	sort(a+1, a+n+1);
	
	int ans = 0;
	ll sum = 0;
	for (int i = 1; i <= n; ++ i)
		if (a[i] < 0)
		{
			ans ++;
			sum += a[i];
		}
	for (int i = n; i >= 1; -- i)
	{
		if (sum < 0)
		{
			sum += a[i];
			ans ++;
		}
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 2560
from sys import stdin
import numpy as np
N, Q=map(int,input().split())
S=input()
L =[list(map(int, stdin.readline().split())) for _ in range(Q)]
c = [0]*(N)  
s = [0]*(N)  
for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    c[i+1] = 1
s = np.cumsum(c)
for i in range(Q):
  print(s[L[i][1]-1]-s[L[i][0]-1])


Measured memory_bytes: 39576
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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


int main(void) {
	long long int n, k;
	long long int count1, count2;

	cin >> n >> k;

	count1 = n / k;
	if (k % 2 == 0) {
		count2 = (n / (k / 2) )- count1;
	}
	else {
		count2 = 0;
	}

	printf("%lld\n", (long long int)(pow(count1, 3) + pow(count2, 3)));

	return 0;
}

Measured memory_bytes: 256
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
exlr.sort(key=lambda x: x[1])
exlr.sort()

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

    





Measured memory_bytes: 110804
R,G,B,N = list(map(int, input().split()))

ans = 0
for r in range((N//R) + 1):
  ngb = (N - r*R)
  for g in range(ngb//G + 1):
    if (ngb - g*G)%B ==0:
      ans += 1
      
print(ans)
    

Measured memory_bytes: 2940
s = raw_input()
t = raw_input()

def last_match(s, t):
    l, r = -1, -1
    for i in range(len(s)):
        if s[i] == "?" or s[i] == t[0]:
            match = True
            #print i, s[i]
            for j in range(len(t)):
                if i + j >= len(s) or (s[i+j] != '?' and s[i+j] != t[j]):
                    match = False
                    break
                #print j, s[i+j], t[j]
            if match:
                l, r = i, i + j
    return l, r
l, r = last_match(s, t)
if l == -1 and r == -1:
    print "UNRESTORABLE"
    exit()
res = ""
for i in range(len(s)):
    if i == l:
        match = True
        j = i
        res += t[0]
    elif i >= l and i <= r:
        res += t[i-j]
    elif s[i] == "?":
        res += "a"
    else:
        res += s[i]
print res

Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
int main() {
  int g,n,m,k,y=0;
  int x[101];
  cin >> n >>k;
  for(int i=1;i<=n;i++){
    x[i]=0;
  }
  for(int i=1;i<=k;i++){
    cin >> g;
    for(int ii=1;ii<=g;ii++){
      cin >> m;
      x[m]=1;
    }
  }
  for(int i=1;i<=n;i++){
    if(x[i]==0){
      y++;
    }
  }
  cout << y << endl;
  return 0;
}

Measured memory_bytes: 3536
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""
N, K = tuple(map(int,input().split()))
ans = 0

for i in range(1, N+1):
    tmp = 1
    while i * tmp < K:
        tmp *= 2
    ans += 1 / tmp
print(ans/N)

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int INF = 1 << 30;

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

    vector<string> s(n);
    rep(i, n) cin >> s[i];

    vector<map<int, int> > ma(n);
    rep(i, n) {
        rep(j, s[i].size()) {
            ma[i][s[i][j]-'a']++;
        }
    }

    for (char w = 'a'; w <= 'z'; w++) {
        int cnt = INF;
        rep(i, n) {
            cnt = min(cnt, ma[i][w-'a']);
        }
        rep(i, cnt) {
            cout << w;
        }
    }

    cout << endl;



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    vector<int> a(3);
    rep(i,3) cin >> a[i];
    sort(a.begin(), a.end());
    cout << a[0] + a[1] << endl; 
    return 0;
}

Measured memory_bytes: 3604
s = input()
n = len(s)

def dfs(i, l):
    if i == n-1:
        return sum(list(map(int, l.split("+"))))
    return dfs(i+1, l+s[i+1])+dfs(i+1, l+"+"+s[i+1])

print(dfs(0, s[0]))


Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
    int x,y;
    while(1){
        cin >> x >> y;
        if(x == 0 && y == 0)break;
        if(x < y){
            cout << x << " " << y << endl;
        }else{
            cout << y << " " << x << endl;
        } 
    }
}


Measured memory_bytes: 3000
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll x1,x2,y1,y2;
  cin>>x1>>y1>>x2>>y2;
  ll x3,x4,y3,y4;
  x3=x2+(y1-y2);
  x4=x1+(y1-y2);
  y3=y2-(x1-x2);
  y4=y1-(x1-x2);
  cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
}

Measured memory_bytes: 3636
#include <stdio.h>
int main(void) {
  int n, data[100], j, tmp, i, count;
  while(scanf("%d",&n),n) {
    count = 0;
    for(i = 0; i < n; i++ ) {
      scanf("%d",&data[i]);
    }
    for(i = 0; i < n - 1; i++ ) {
      for(j = 1; j < n - i; j++ ) {
	if(data[j] < data[j-1]) {
	  tmp = data[j];
	  data[j] = data[j-1];
	  data[j-1] = tmp;
	  count++;
	}
      }
    }
    printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 600
#include<iostream>

using namespace std;

int main ()
{
    int n,k,i;
    long long res=0;

    cin>>n>>k;

    for(i=k+1;i<=n;i++)
    {
        res+=(i-k)*(n/i);
        if(n%i>=k)
        {
            res+=n%i-k+1;
            if(k==0)res--;
        }
        //cout<<res<<endl;
    }

    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void)
{
    int t, h;
    int n;
    char s1[128], s2[128];
    int c;

    scanf("%d", &n);
    t = h = 0;
    while (n--){
        scanf("%s %s", s1, s2);
        c = strcmp(s1, s2);
        if (c > 0) t += 3;
        else if (c < 0) h += 3;
        else ++t, ++h;
    }
    printf("%d %d\n", t, h);

    return 0;
}

Measured memory_bytes: 604
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<iomanip>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI = 4.0 * atan(1.0);

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

int main() {
    double A, B, H, M; cin >> A >> B >> H >> M;
    
    double thetaB = 2.0 * PI * M / 60.0;
    double thetaA = 2.0 * PI * (H / 12.0 + M / (60.0 * 12.0));
    double theta = abs(thetaB - thetaA);
    // if (theta > PI) theta = 2.0 * PI - theta;
    
    // double c = sqrt(A * A + B * B - 2.0 * A * B * cos(theta));
    double c = pow(A * A + B * B - 2.0 * A * B * cos(theta), 0.5);

    cout << setprecision(18) << c << endl;
    return 0;
}


Measured memory_bytes: 4248
/* 
 * Project: AtCoder Beginners Contest 072 A - Sandglass2
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/06/10
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
using namespace std;

int x, t;

void solve() {

    if (x > t) {
        printf("%d\n", x - t);
        return;
     } else {
        printf("%d\n", 0);
        return;
     }

}

int main() {

    scanf("%d", &x);
    scanf("%d", &t);

    solve();

}

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

int main(){
	string a,b,c;
	while(cin >> b >> a >> c && a != "-"){
		a += "                                                                                                                                  ";
		b += "                                                                                                                                  ";
		char mid = '-';
		string ans;
		while(a.size() > 1 && b.size() > 1){
			//cout << a << " " << b << " " << mid << " " << c << "|" << count(c.begin(),c.end(),mid) << endl;
			if( mid == '-' ){
				mid = a[0];
				a = a.substr(1);
			
			}else{
				if( count(c.begin(),c.end(),mid) ){
					mid = b[0];
					b = b.substr(1);
				}else{
					if( mid != ' ' ) ans += mid;
					mid = a[0];
					a = a.substr(1);
				}
			}
		}
		cout << ans << endl;
	}
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int all_xor = 0;
    int A[N]; rep(i, N) cin >> A[i];
    rep(i, N) all_xor ^= A[i];
    if((N-1) % 2){
        rep(i, N) cout << (A[i]^all_xor) << " "; cout << endl;
    }
    return 0;

}

Measured memory_bytes: 4368
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
#define mod 1000000007
LL l[200006],r[200006];
int main(){
	int n=read(),k=read();
	LL ans=0;
	for(reg int i=k;i<=n+1;i++) ans=(ans+(LL)i*(n-i+1)+1)%mod;
	std::printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
#define MAXN 200001
#define INF 1000000000

using namespace std;

struct Aint {
    int val;
    int pos;
}aint[4 * MAXN + 1];

int sp[MAXN + 1];
pair <int, int> v[MAXN + 1];

bool cmp(pair <int, int> a, pair <int, int> b) {
    return a.second - a.first > b.second - b.first;
}

void build(int nod, int left, int right) {
    if(left == right) {
        aint[nod].val = sp[left];
        aint[nod].pos = left;
    }
    else {
        int med = (left + right) / 2;
        build(2 * nod, left, med);
        build(2 * nod + 1, med + 1, right);
        if(aint[2 * nod].val < aint[2 * nod + 1].val) {
            aint[nod].val = aint[2 * nod].val;
            aint[nod].pos = aint[2 * nod].pos;
        }
        else {
            aint[nod].val = aint[2 * nod + 1].val;
            aint[nod].pos = aint[2 * nod + 1].pos;
        }
    }
}

void update(int nod, int left, int right, int pos) {
    if(left == right)
        aint[nod].val = INF;
    else {
        int med = (left + right) / 2;
        if(pos <= med)
            update(2 * nod, left, med, pos);
        else
            update(2 * nod + 1, med + 1, right, pos);
        if(aint[2 * nod].val < aint[2 * nod + 1].val) {
            aint[nod].val = aint[2 * nod].val;
            aint[nod].pos = aint[2 * nod].pos;
        }
        else {
            aint[nod].val = aint[2 * nod + 1].val;
            aint[nod].pos = aint[2 * nod + 1].pos;
        }
    }
}

int ans, p;

void query(int nod, int left, int right, int l, int r) {
    if(l <= left && right <= r) {
        if(ans > aint[nod].val) {
            ans = aint[nod].val;
            p = aint[nod].pos;
        }
    }
    else {
        int med = (left + right) / 2;
        if(l <= med)
            query(2 * nod, left, med, l, r);
        if(med < r)
            query(2 * nod + 1, med + 1, right, l, r);
    }
}

int main() {
   // fstream cin("A.in");
   // ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
        sp[0]++;
        sp[v[i].first + 1]--;
        sp[v[i].second]++;
        sp[m + 1]--;
    }
    for(i = 1; i <= m; i++)
        sp[i] += sp[i - 1];
    for(i = 1; i <= 4 * m; i++)
        aint[i].val = INF;
    build(1, 1, m);
    sort(v + 1, v + n + 1, cmp);
    int cnt = 0;
    for(i = 1; i <= n; i++) {
        ans = INF;
        if(v[i].first >= 1)
           query(1, 1, m, 1, v[i].first);
        if(v[i].second <= m)
          query(1, 1, m, v[i].second, m);
        if(ans == INF)
            cnt++;
        else
            update(1, 1, m, p);
    }
    cout << cnt << endl;
   // cin.close();
   // cout.close();
    return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=INT_MAX,MOD=1e9+7;

int main(){
    int d,g; cin>>d>>g;
    int p[d],c[d]; rep(i,d) cin>>p[i]>>c[i];
    int ans=INF;
    for(int i=0;i<(1<<d);i++){
        int point=0,solve=0;
        rep(j,d){
            if(i>>j&1){
                point+=p[j]*(j+1)*100+c[j];
                solve+=p[j];
            }
        }
        if(point>=g) ans=min(ans,solve);
        else{
            bool flg=1;
            for(int j=d-1;j>=0;j--){
                if(!(i>>j&1)){
                    int k=p[j]-1;
                    while(k--){
                        point+=(j+1)*100;
                        solve++;
                        if(point>=g){
                            flg=0; break;
                        }
                    }
                }
                if(!flg) break;
            }
            if(point>=g) ans=min(ans,solve);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
    int n, cnt = 0;
    string s;
    map<string, int> dict;

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s;
        dict[s];
    }

    cout << dict.size() << endl;

    return 0;
}

Measured memory_bytes: 19232
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
// #include<C:\Users\J\Desktop\AC\athead.h>
#define showa(v) for(int iii = 0; iii < v.size(); iii++){ cout << v[iii] << " ";} cout << endl;
#define show(iiii) cout << iiii << endl; 
#define shows(iiiii) cout << iiiii << " ";
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include<tuple>
#include <utility>
#include <map>
#include<stack>
#include<queue>
using namespace std;

 
int main(){
    int n;
    cin >> n;
    if(n%2==0){
        cout << (n/2)-1;
    }
    else{
        cout << n/2;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
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;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


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

int n;
multiset<ll> a;
vector<ll> v1;

int main(){
	cin>>n;
	REP(i,n){
		int ta;
		cin>>ta;
		a.insert(ta);
	}
	ll t1=1;
	for(t1=1;t1<=3*1e9;t1*=2){
		v1.push_back(t1);
	}
	int ans=0;
	while(a.size()){
		int t1=*a.rbegin();
		a.erase(--a.end());
		int t2=*upper_bound(v1.begin(),v1.end(),t1);
		auto itr=a.find(t2-t1);
		if(itr!=a.end()){
			ans++;
			a.erase(itr);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define OUT(a) cout<<(a)<<endl;
#define ALL(v) (v).begin(), (v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
const LL LINF=1ll<<62; const int INF=1ll<<30; const LL MOD=1E9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k,t,s=0;
    cin >> k >> t;
    vector<int> v(t);
    REP(i,t){
        cin >> v[i];
        s+=v[i];
    }
    sort(ALL(v));
    int d=s-v[t-1];
    cout << max(0,v[t-1]-d-1)<<endl;





    return 0;
}


Measured memory_bytes: 256
H,W = list(map(int,input().split()))

min_score = 10**27

for i in range(1,H):
    if W%2==0:
        S1 = i*W/2
        S2 = (H-i)*W
        min_score = min(abs(S1-S2),min_score)
    else:
        S1 = i*(W-1)/2
        S2 = i*(W+1)/2
        S3 = (H-i)*W
        S4 = max(S1,S2,S3)
        S5 = min(S1,S2,S3)
        min_score = min(S4-S5,min_score)

for i in range(1,W):
    if H%2==0:
        S1 = i*H/2
        S2 = (W-i)*H
        min_score = min(abs(S1-S2),min_score)
    else:
        S1 = i*(H-1)/2
        S2 = i*(H+1)/2
        S3 = (W-i)*H
        S4 = max(S1,S2,S3)
        S5 = min(S1,S2,S3)
        min_score = min(S4-S5,min_score)

s1=int(H/3)
s2=int((H-s1)/2)
s3=H-s1-s2
S1 = max(s1*W,s2*W,s3*W)
S2 = min(s1*W,s2*W,s3*W)
min_score = min(S1-S2,min_score)

s1=int(W/3)
s2=int((W-s1)/2)
s3=W-s1-s2
S1 = max(s1*H,s2*H,s3*H)
S2 = min(s1*H,s2*H,s3*H)
min_score = min(S1-S2,min_score)

print(int(min_score))

Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>//cout << fixed << setprecision() <<
#include <set>
#include <list>
#include <string>
#include <map>
using ll = long long;
using namespace std;

double Mcos(double k){return cos(k*atan(1.0)*4/180);}
double Msin(double k){return sin(k*atan(1.0)*4/180);}

int main(void){
    list<string> L;
    string s,s1;
    int q,n1,n2;
    int GYAKU=0;
    cin>>s>>q;
    L.push_back(s);
    for(int i=0;i<q;i++){
        cin>>n1;
        if(n1==1){
            GYAKU++;
        }else{
            cin>>n2>>s1;
            if(GYAKU%2==0){
                if(n2==1){
                    L.push_front(s1);
                }else{
                    L.push_back(s1);
                }
            }else{
                if(n2==1){
                    L.push_back(s1);
                }else{
                    L.push_front(s1);
                }
            }
        }
    }
    list<string>::iterator itr;
    list<string>::reverse_iterator itr2;
    if(GYAKU%2==0){
        for(itr=L.begin();itr!=L.end();itr++){
            cout<<*itr;
        }
    }else{
        for(itr2=L.rbegin();itr2!=L.rend();itr2++){
            reverse(itr2->begin(),itr2->end());
            cout<<*itr2;
        }
    }
}


Measured memory_bytes: 16256