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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v)                                                            \
  do {                                                                         \
    x = max(x, v);                                                             \
  } while (0)
#define chmin(x, v)                                                            \
  do {                                                                         \
    x = min(x, v);                                                             \
  } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

// Segment Tree {{{
template <typename T> class SegTree {
 private:
  int _n;
  T _init_val;
  std::vector<T> _data;
  std::function<T(T, T)> _f;

  T _query(int a, int b, int k, int l, int r) {
    // [a b)と[l r]が交差しない
    if (r <= a || b <= l)
      return _init_val;

    // [a b)が[l r]を含む
    if (a <= l && r <= b)
      return _data[k];

    T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);

    return _f(vl, vr);
  }

 public:
  SegTree(int n, T init_val, std::function<T(T, T)> f) {
    _init_val = init_val;
    _n = 1;
    _f = f;

    while (_n < n)
      _n *= 2;
    _data.resize(2 * _n, init_val);
  }

  T get(int k) { return _data[k + _n - 1]; }

  void update(int k, T a) {
    k += _n - 1;
    _data[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      _data[k] = _f(_data[k * 2 + 1], _data[k * 2 + 2]);
    }
  }

  // [a b)の範囲でfを適用
  T query(int a, int b) { return _query(a, b, 0, 0, _n); }

  // 先頭からチェックし，はじめてxを満たしたインデックス
  int lower_bound(T x) { return _lower_bound(x, 0); }

  int _lower_bound(T x, int k) {
    if (k >= _n - 1) {
      return k - (_n - 1); // 葉
    } else if (_data[k] < x) {
      return _n; // 該当なし
    } else if (x <= _data[k * 2 + 1]) {
      return _lower_bound(x, k * 2 + 1);
    } else {
      return _lower_bound(x - _data[k * 2 + 1], k * 2 + 2);
    }
  }
};
// }}}

signed main() {
  ll N, D, A, ans = 0;
  cin >> N >> D >> A;
  vector<PLL> v(N); // {x, hp}
  vector<ll> x(N);
  SegTree<ll> st(300000, 0, [](ll x, ll y) { return x + y; });
  rep(i, N) { cin >> v[i].first >> v[i].second; }
  sort(begin(v), end(v));
  rep(i, N) { x[i] = v[i].first; }
  rep(i, N) {
    ll propDamage = st.query(i, 300000);
    v[i].second = max((ll)0, v[i].second - propDamage);
    ll nExplode = (v[i].second + A - 1) / A;
    ans += nExplode;

    // この爆発の右側 j
    auto it = upper_bound(begin(x), end(x), x[i] + 2 * D);
    it--;
    auto j = distance(begin(x), it);

    st.update(j, st.get(j) + A * nExplode);
    // printf("i=%d v[i].second=%d propDamage=%d j=%d nExplode=%d\n", i,
    //       v[i].second, propDamage, j, nExplode);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 13184
n = int(input())
alphabet = 'abcdefghij'

def ans(n):
    if n == 1:
        return ['a']
    ret = []
    for s in ans(n-1):
        l = len(set(s))
        for i in range(l+1):
            ret.append(s + alphabet[i])
    return ret

for s in ans(n):
    print(s)


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

int main() {
  int H, W;
  cin >> H >> W;
  string S[55];
  for (int i = 0; i < H; i++) {
    cin >> S[i];
  }
  vector<int> dx = {-1, 0, 1, -1, 1, -1, 0, 1};
  vector<int> dy = {-1, -1, -1, 0, 0, 1, 1, 1};
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (S[i][j] == '.') {
        int cnt = 0;
        for (int k = 0; k < 8; k++) {
          int X = j + dx[k];
          int Y = i + dy[k];
          if (0 <= X && X < W && 0 <= Y && Y < H && S[Y][X] == '#')
            cnt++;
        }
        S[i][j] = '0' + cnt;
      }
    }
  }
  for (int i = 0; i < H; i++) {
    cout << S[i] << endl;
  }
}


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

using ll=long long;



void solve(){
    int x,a,b;
    cin>>x>>a>>b;
    if(abs(x-a)>abs(x-b)){
        cout<<"B"<<endl;
    }else{
        cout<<"A"<<endl;
    }
}

signed main(){
    //while(1)
    solve();
}

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

using namespace std;

int main()
{
    
   int n,temp,ans=0;
   vector<int> v,c;

   cin >> n;
   for(int i=0;i<n;i++){
       cin >> temp;
       v.push_back(temp);
   }

      for(int i=0;i<n;i++){
       cin >> temp;
       c.push_back(temp);

       if(v[i]>c[i])ans+=v[i]-c[i];
   }
   
   
   cout << ans << endl; 
   
   return 0;
}


Measured memory_bytes: 256
n = int(raw_input())
a = map(int, raw_input().split())

def CountingSort(A, B, k):
    C = [0 for i in range(0, k+1)]
    
    for i in range(n):
        C[A[i]] += 1

    for i in range(1, k+1):
        C[i] += C[i-1]

    for i in range(n):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1


b = [0 for i in range(n)]
k = max(a)
CountingSort(a, b, k)
print ' '.join(map(str, b))

Measured memory_bytes: 256412
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

//#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int gcd(int x, int y)
{
	int a = x, b = y, t = a%b;
	while (t > 0)
	{
		a = b;
		b = t;
		t = a%b;
	}
	return b;
}

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

	int n;
	cin >> n;

	int t = n;
	double ans = n;

	for (int i = 2; i <= (int)sqrt(n); i += (i == 2 ? 1 : 2))
	{
		if (t%i == 0)
		{
			ans *= (1.0 - 1.0 / i);
			t /= i;
		}
		while (t%i == 0)
		{
			t /= i;
		}
	}
	if (t != 1)
	{
		ans *= (1.0 - 1.0 / t);
	}
	cout << (int)ans << endl;
	return 0;
}


Measured memory_bytes: 3236
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

long double pi = 3.141592653589793238462643;
vector<pair<int, int>>p;
long double len(vector<int>num){
	ll x = 0;
	ll y = 0;
	fore(z, num) {
		x += p[z].first;
		y += p[z].second;
	}
	return sqrt(x*x + y * y);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	p.resize(N);
	for (int i = 0; i < N; i++)cin >> p[i].first >> p[i].second;

	long double ans = 0.0;
	for (int i = 0; i < 10000; i++) {
		long double c = cos((2.0*(long double)i*pi)/(long double)10000);
		long double s = sin((2.0*(long double)i*pi)/(long double)10000);
		vector<int>temp;
		for (int j = 0; j < N; j++) {
			long double x = p[j].first;
			long double y = p[j].second;
			if (x*c + y*s >= 0.0)temp.pb(j);
		}
		ans = max(ans, len(temp));
	}
	cout << setprecision(20) << ans << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		double r =  new Scanner(System.in).nextDouble();		
		double cir = 2 * Math.PI * r;
		double vol = Math.PI * Math.pow(r, 2);
		System.out.printf("%.6f %.6f", vol, cir);
	}
}

Measured memory_bytes: 28412
// Copyright 2017 wu_qing
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 2e5 + 10;
struct node {
    int x, y, id;
} a[N];
struct edge {
    int x, y, d;
    explicit edge(int x = 0, int y = 0, int d = 0) : x(x), y(y), d(d) {
    }
};
std::vector<edge> e;
bool cmpx(node a, node b) {
    return a.x < b.x;
}
bool cmpy(node a, node b) {
    return a.y < b.y;
}
bool cmpe(edge a, edge b) {
    return a.d < b.d;
}
int n, cnt, ans, f[N];
inline int getf(int x) {
    return f[x] == x ? x : (f[x] = getf(f[x]));
}
inline void merge(int x, int y) {
    f[getf(x)] = getf(y);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].id = i;
    }
    std::sort(a + 1, a + n + 1, cmpx);
    for (int i = 1; i < n; i++)
        e.push_back(edge(a[i].id, a[i + 1].id, a[i + 1].x - a[i].x));
    std::sort(a + 1, a + n + 1, cmpy);
    for (int i = 1; i < n; i++)
        e.push_back(edge(a[i].id, a[i + 1].id, a[i + 1].y - a[i].y));
    std::sort(e.begin(), e.end(), cmpe);
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (edge i : e) {
        if (cnt == n - 1)
            break;
        if (getf(i.x) != getf(i.y)) {
            merge(i.x, i.y);
            ans += i.d;
            cnt++;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 6132
#include<iostream>
using namespace std;
int main(){
  int n,y;
  cin>>n>>y;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      int k=y-i*10000-j*5000;
      if(k%1000==0){
        int q=k/1000;
        if(i+j+q==n&&q>=0){
          cout<<i<<" "<<j<<" "<<q<<endl;
          return 0;
        }
      }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
  return 0;
}

Measured memory_bytes: 3620
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();

    int x = a + a - 1;
    int y = b + b - 1;
    int z = a + b;
    int s = 0;
    
    if ( y > x ) {
      s = y;
    } else {
      s = x;
    }
    
    if ( z > s ) {
      s = z;
    }
    
    System.out.println(s);
  }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
struct Point{
    double x,y;
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);  
    double a,b,x;
    const double PI=3.14159265358979323846;
    cin >> a >> b >> x;
    if(2*x<=a*a*b){
        cout << fixed << std::setprecision(10) << (atan2(a*b*b,(2*x))*180/PI) << endl;
    }else if(x==a*a*b){
        cout << 0 << endl;
    }else{
        // cout << 0 << endl;
        cout << fixed << std::setprecision(10) << (atan2(2*(b-x/(a*a)),a)*180/PI) << endl;
    }
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, m) = readIntList()
    var a = Array(n) { -1 }

    repeat(m) {
        val (s, c) = readIntList()
        if (a[s - 1] != -1 && a[s - 1] != c) {
            println(-1)
            return
        }
        if (s > n) {
            println(-1)
            return
        }
        a[s - 1] = c
    }

    var ans = ""
    ans += when {
        n == 1 && a[0] == -1 -> 0
        n > 1 && a[0] == -1 -> 1
        else -> a[0]
    }
    for (i in 1 until n) {
        ans += if (a[i] == -1) 0 else a[i]
    }

    for (i in 0..999) {
        if (i.toString().length != n) continue
        if (i.toString() == ans) {
            println(i)
            return
        }
    }

    println(-1)
    return
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

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

vector<int>	calc_digits(int	num)
{
	vector<int>	digits;
	while (num > 0) {
		digits.push_back(num % 10);
		num /= 10;
	}
	return digits;
}

int	main()
{
	int	A, B;
	cin >> A >> B;
	auto d_A = calc_digits(A);
	auto d_B = calc_digits(B);
	int	bgn = A / 100;
	int	end = B / 100;
	if (d_A.at(1) > d_A.at(3) ||
		(d_A.at(1) == d_A.at(3) && d_A.at(0) > d_A.at(4)))
		++bgn;
	if (d_B.at(1) > d_B.at(3) ||
		(d_B.at(1) == d_B.at(3) && d_B.at(0) >= d_B.at(4)))
		++end;
	cout << end - bgn << endl;
}


Measured memory_bytes: 256
/*input
3
xyx


*/
 
 
 
#include <bits/stdc++.h>
using namespace std;
 
 
 
#define int long long int
#define rep(i,n) \
    for(int i = 0; i < n; i++)
#define rep2(i, a, b) \
    for(int i = a; i < b; i++)
#define all(c) \
    c.begin(), c.end()
#define init(arr, num) \
    memset(arr, num, sizeof(arr))
#define fast\
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inputFile \
    freopen("input.txt", "r", stdin); 
#define outputFile \
    freopen("output.txt", "w", stdout);
#define modM 1000000007
#define PI 3.1415926535897932
#define F first
#define S second  
#define pb push_back  
#define INF 3e18
#ifdef gaviria
#define TRACE
#endif
#ifdef TRACE
#define trace(...) _f(#VA_ARGS, __VA_ARGS_)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std::endl;
 
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< ll, ll > ii;
typedef unordered_set<int> usi;
 
 
 
ll n,i,j,k,m,c;

void solve()
{
cin>>n;

if(n>=30)
{
    cout<<"Yes";
}
else cout<<"No";
}
 
 
 
 
 
signed main()
{// inputFile;


    fast;
    int T = 1;
    // cin >> T;
    ll h=T;
    while(T--){
 
        solve();
        cout<<endl;
 
     
        
        
 
    }
    
    
    return 0;
 
}

Measured memory_bytes: 3644
import Control.Monad
import Data.Function
import Data.Char
import Data.List
import Text.Read
import Text.ParserCombinators.ReadPrec

newtype Pair a b = Pair { getPair :: (a, b) }

instance (Read a, Read b) => Read (Pair a b) where
  readPrec = Pair `dot` (,) <$> readPrec <* get <*> readPrec

instance (Show a, Show b) => Show (Pair a b) where
  show (Pair (a, b)) = show a ++ " " ++ show b

readPair :: IO (Int, Int)
readPair = getPair <$> readLn

infixr 8 `dot`
dot :: (c -> d) -> (a -> b -> c) -> a -> b -> d
dot = ((.).(.))

main :: IO ()
main = do
  s <- getLine
  print $ solve s

solve :: String -> Int
solve "RRR" = 3
solve "RRS" = 2
solve "SRR" = 2
solve "SSS" = 0
solve _     = 1    



Measured memory_bytes: 3908
#include <bits/stdc++.h>
using namespace std;
#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 _GLIBCXX_DEBUG
static const int MAX = 100000;


int main(){
  int N, H[MAX], count = 0, ans = 0;
  cin >> N;
  rep(i, N) cin >> H[i];
  
  rep(i, N-1){
    if(H[i] >= H[i+1]) count++;
    else count = 0;
    ans = max(count, ans); 
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define now edge[i].v
#define go(x) for(int i=head[x];i;i=edge[i].nxt)
using namespace std;
const int sz=1e5+7;
const int inf=1<<30;
int n,k;
int u,v,cnt;
bool flag;
int val[sz];
int head[sz];
int l[sz],r[sz];
struct Edge{
	int v,nxt;
}edge[sz<<1];
void make_edge(int u,int v){
	edge[++cnt]=(Edge){v,head[u]};head[u]=cnt;
	edge[++cnt]=(Edge){u,head[v]};head[v]=cnt;
}
void dfs(int x,int fa){
	go(x) if(now!=fa){
		dfs(now,x);
		if(l[now]==-inf&&r[now]==inf) continue;
		if(l[x]!=-inf&&r[x]!=inf&&((l[x]&1)^(l[now]&1)==0||(r[x]&1)^(r[now]&1)==0)) flag=1;
		l[x]=max(l[x],l[now]-1);
		r[x]=min(r[x],r[now]+1);
	}
	flag|=l[x]>r[x];
}
void Dfs(int x,int fa){
	if(fa==0) val[x]=l[x];
	else{
		if(val[fa]-1>=l[x]) val[x]=val[fa]-1;
		else val[x]=val[fa]+1;
	}
	go(x) if(now!=fa) Dfs(now,x);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		make_edge(u,v);
	}
	for(int i=1;i<=n;i++) l[i]=-inf,r[i]=inf;
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&u,&v);
		l[u]=r[u]=v;
	}
	dfs(1,0);
//	for(int i=1;i<=n;i++) printf("%d %d %d\n",i,l[i],r[i]);
	if(flag) return printf("No\n"),0;
	Dfs(1,0);
	printf("Yes\n");
	for(int i=1;i<=n;i++) printf("%d\n",val[i]);
}

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

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

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 main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);

    rep(i, n - 1) {
        int t;
        cin >> t;
        t--;
        a[t]++;
    }

    rep(i, n) { cout << a[i] << endl; }
    return 0;
}


Measured memory_bytes: 3996
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PiL(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)
#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

const int N = 2006;

int a[N];
int dp1[N],dp2[N];

int n,z,w;

int solve1(int opposite,int can);
int solve2(int opposite,int can);

int solve1(int opposite,int can) {
    if (dp1[can] != -1) return dp1[can];
    dp1[can] = abs(a[1] - opposite);
    if (can == 1) return dp1[can];
    for (int i=can;i>1;i--) {
        dp1[can] = max(dp1[can],solve2(a[i],i-1));
    }
    return dp1[can];
}

int solve2(int opposite,int can) {
    if (dp2[can] != -1) return dp2[can];
    dp2[can] = abs(a[1] - opposite);
    if (can == 1) return dp2[can];
    for (int i=can;i>1;i--) {
        dp2[can] = min(dp2[can],solve1(a[i],i-1));
    }
    return dp2[can];
}

int main () {
    srand(time(NULL));
    Siii(n,z,w);
    REP1(i,n) {
        Si(a[i]);
    }
    reverse(a+1,a+n+1);
    MEM1(dp1);
    MEM1(dp2);
    Pi(solve1(w,n));
}



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

int main() {
	int n; cin >> n;
	vector<pair<int, int>>xy(n); for (auto&& i : xy)cin >> i.first >> i.second;
	vector<int>gene;
	for (int i = 0; i < n; i++) { gene.push_back(i); }

	vector<vector<int>>perm;
	do {
		perm.push_back(gene);
	} while (next_permutation(gene.begin(), gene.end()));

	double ans = 0;
	for (int i = 0; i < perm.size(); i++) {
		for (int j = 0; j < perm[i].size()-1; j++) {
			double x, y;
			x = xy[perm[i][j]].first - xy[perm[i][j + 1]].first;
			y = xy[perm[i][j]].second - xy[perm[i][j + 1]].second;
			ans += sqrt(x * x + y * y);
		}		
	}
	printf("%.10f", ans / perm.size());

	return 0;
}

Measured memory_bytes: 3256
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    ll N,M;
    cin >> N >> M;
    vector<int> A(N);
    ll tot = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        tot += A[i];
        A[i] *= M*4;
    }   
    SORT(A);
    int ans = 0;
    REP(i, N){
        if(A[i] >= tot) ans++;
    }
    Yes(ans >= M);
}

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

int main()
{
    std::string s;

    std::cin >> s;

    if (s.at(0) == s.at(1) && s.at(2) == s.at(3) && s.at(1) != s.at(2)) // AABB
        std::cout << "Yes" << std::endl;
    else if (s.at(0) == s.at(2) && s.at(1) == s.at(3) && s.at(0) != s.at(1)) // ABAB
        std::cout << "Yes" << std::endl;
    else if (s.at(0) == s.at(3) && s.at(1) == s.at(2) && s.at(0) != s.at(1)) // ABBA
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int dp[n + 3][2];
    dp[0][0] = 0, dp[0][1] = 1;
    for(int i = 0; i < s.size(); i++){
        int d = s[i] - '0';
        dp[i + 1][0] = min(dp[i][0] + d, dp[i][1] + 10 - d);
        dp[i + 1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10 - d - 1);
    }
    cout << dp[n][0];
    return 0;
}

Measured memory_bytes: 12132
N,M = map(int, input().split())

H=list(map(int,input().split()))

graph=[[0] for _ in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(H[B-1])
    graph[B-1].append(H[A-1])

ans=0

for i in range(N):
    if H[i]>max(graph[i]):
        ans+=1
        
print(ans)

Measured memory_bytes: 26112
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int len = (int)1e6 + 1;
	
	void doIt() {
		String S = sc.next();
		String T = sc.next();
		System.out.println((S.equals(T.substring(0, T.length() - 1)))?"Yes":"No");
		
	}
	
	public static void main(String[] args) {
		new Main().doIt();
	}

}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define repp(i, n) rep(i, n)
#define reppp(i, n) repp(i, n)
#define rrepp(i, n) rrep(i, n)
#define repss(i, n) reps(i, n)
#define repcc(i, n) repc(i, n)
#define repii(i, a, b) repi(i, a, b)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

void solve() {
  int n; cin >> n;
  vi32 p(n); cin >> p;
  int ans = 0;
  for (int i = 0; i + 3 <= n; i++) {
    if (p[i] > p[i + 1] && p[i + 1] > p[i + 2]) {
      ans++;
    } else if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) {
      ans++;
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main(){
  int n;
  cin >> n;
  set<int> s;
  REP(i,n){
    int tmp;
    cin >> tmp;
    s.insert(tmp);
  }
  int m;
  cin >> m;
  set<int> t;
  REP(i,m){
    int tmp;
    cin >> tmp;
    t.insert(tmp);
  }
  set<int> ans;
  set_intersection(ALL(s),ALL(t),inserter(ans,ans.end()));
  for(auto i:ans){
    cout << i << endl;
  }
}



Measured memory_bytes: 23640
import java.util.Scanner;
public class Main {
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int k = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			System.out.println(Math.min(k,n) * x + Math.max(n - k, 0) * y);
			
		}

		

}


Measured memory_bytes: 9932
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

    int k, a, b;
    cin >> k >> a >> b;
    int ans= 0;
    for(int i = 1; i *k <= b;i++){
        if(i*k<a) continue;
        else {
            ans = 1;
        }
    }
    if(ans) cout << "OK";
    else cout << "NG";


    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double dlb;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef pair<ll, pair<ll,ll> > iii;

const int kn = 2e5 + 5;
const ll mod = 1e9 + 7;

#define x first
#define y second
#define _it iterator
#define pb push_back
#define pf push_front
#define ms(val,a) memset(a,val,sizeof(a))
#define ff(i,n) for(int i=1;i<=n;i++)
#define _ff(i,n) for(int i=n;i>=1;i--)
#define f(i,a,b) for(int i = a; i <=b; i++)
#define _f(i,a,b) for(int i = b; i>=a;i--)
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll n, par[kn];
ll ans = 0;

struct data{
	int x, y;
	int id;
};

bool option(data cac, data lon)
{
	if(cac.x != lon.x) return cac.x < lon.x;
	return cac.y < lon.y;
}

data a[2][kn];

int Find(int i)
{
	if(par[i] == i) return i;
	return par[i] = Find(par[i]);
}

void dj(int i, int j, int cost)
{
	int pi = Find(i), pj = Find(j);
	if(pi == pj) return;
	par[pi] = pj;
	ans += cost;
}

int la[2][kn], ra[2][kn];

set< iii > pq;

int main() {
	//freopen("a.inp","r",stdin);
	//freopen("a.out","w",stdout);
	cin >> n;
	ff(i,n) par[i] = i;
	ff(i,n)
	{
		cin >> a[0][i].x >> a[0][i].y;
		a[1][i].x = a[0][i].y; a[1][i].y = a[0][i].x;
		a[0][i].id = a[1][i].id = i;
		la[0][i] = la[1][i] = i-1;
		ra[0][i]=ra[1][i] = i+1;
	}
	la[0][1] = la[1][1] = -1;
	ra[0][n] = ra[1][n] = -1;
	sort(a[0]+1,a[0]+n+1,option);
	sort(a[1]+1,a[1]+n+1,option);
	for(int i = 2; i<=n; i++)
	{
		pq.insert(iii(a[0][i].x - a[0][i-1].x, ii(i,0)));
		pq.insert(iii(a[1][i].x - a[1][i-1].x, ii(i,1))); // 0 la day 1, 1 la day 2
	}
	while(pq.size())
	{
		iii tmp = *pq.begin();
		pq.erase(pq.begin());
		dj(a[tmp.y.y][tmp.y.x].id, a[tmp.y.y][tmp.y.x-1].id, a[tmp.y.y][tmp.y.x].x - a[tmp.y.y][tmp.y.x-1].x);
	}
	cout << ans;
}
//hahahahahahahahahhahahahahahaahahahahhahahahahahahah

Measured memory_bytes: 20480
def main():
    N, M = list(map(int, input().split(' ')))
    N, M = min([N, M]), max([N, M])
    if N == 1:
        if M == 1:
            print(1)
        elif M == 2:
            print(0)
        else:
            print(M - 2)
    elif N == 2:
        print(0)
    else:
        print((N - 2) * (M - 2))


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <iostream>
#include<cstring>
using namespace std;
int ways(int n,int k,int stones[]){
    bool dp[k+1];
    memset(dp,false,sizeof dp);
    dp[0]=false;
    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){
            if(stones[j]<=i&&dp[i-stones[j]]==false){
                dp[i]=true;
                
            }
        }
    }
    return dp[k];
}
int main() {
    int n,k;
    cin>>n>>k;
   int stones[n];
    for(int i=0;i<n;i++){
        cin>>stones[i];
    }
    bool ans=ways(n,k,stones);
    if(ans){
        cout<<"First";
    }
else
cout<<"Second";
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.141592653589793238
#define dcout cout<<fixed<<setprecision(20)

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long
#define double long double

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

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

  int A; cin >> A; cout << (A-1)/2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#define llint long long
#define mod 1000000007
#define rep(x, s, t) for(llint x = s; x <= t; x++)

using namespace std;

llint n;
string s[55];
llint memo[55][55][25][30];

llint calc(llint l, llint r, llint k, llint c)
{
  //cout << l << ' ' << r << ' ' << k << ' ' << c << endl;
  if(l > r) return 1;
  if(c == 27) return 0;
  if(memo[l][r][k][c] != -1) return memo[l][r][k][c];

  if(c == 0){
    bool flag = false;
    rep(i, l, r){
      if(s[i].size() >= k+1) flag = true;
    }
    if(!flag){
      if(l == r) return memo[l][r][k][c] = 1;
      else return memo[l][r][k][c] = 0;
    }
  }

  llint ret = calc(l, r, k, c+1);
  for(int i = l; i <= r; i++){
    if(c == 0 && s[i].size() >= k+1) break;
    if(c > 0 && s[i].size() <= k) break;
    if(c > 0 && s[i][k] != '?' && s[i][k] != c-1+'a') break;
    ret += calc(l, i, k+1, 0) * calc(i+1, r, k, c+1) % mod;
    ret %= mod;
  }
  //cout << l << ' ' << r << ' ' << k << ' ' << c << ' '<< ret << endl;
  return memo[l][r][k][c] = ret;
}

int main(void){
  cin >> n;
  rep(i, 1, n) cin >> s[i];

  rep(i, 1, n){
    rep(j, 1, n){
      rep(k, 0, 25){
        rep(l, 0, 26){
          memo[i][j][k][l] = -1;
        }
      }
    }
  }

  cout << calc(1, n, 0, 0) << endl;
  return 0;
}



Measured memory_bytes: 18092
#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>
#include<queue>
int al[30];
int need[5];
int main() {
	int H, W;
	std::cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char tmp;
			std::cin >> tmp;
			al[tmp - 'a']++;
		}
	}
	if (H % 2 == 0 && W % 2 == 0) {
		need[4] = (H*W) / 4;
	}
	if (H % 2 == 0 && W % 2 == 1) {
		need[4] = (H*(W - 1)) / 4;
		need[2] = H / 2;
	}
	if (H % 2 == 1 && W % 2 == 0) {
		need[4] = ((H - 1)*W) / 4;
		need[2] = W / 2;
	}
	if (H % 2 == 1 && W % 2 == 1) {
		need[1] = 1;
		need[4] = ((H - 1)*(W - 1)) / 4;
		need[2] = ((H - 1) / 2) + ((W - 1) / 2);
	}
	for (int i = 0; i < 30 ; i++) {
		if (al[i]) {
			int m = al[i] / 4;
			if (need[4] >= m) {
				need[4] -= m;
			}
			else {
				m = need[4];
				need[4] = 0;
			}
			al[i] -= m * 4;
			if (al[i]) {
				m = al[i] / 2;
				if (need[2] >= m) {
					need[2] -= m;
				}
				else {
					m = need[2];
					need[2] = 0;
				}
				al[i] -= m * 2;
				if (al[i]) {
					if (need[1] >= al[i]) {
						need[1] -= al[i];
					}
				}
			}
		}
	}
	for (int i = 0; i <= 4; i++) {
		if (need[i]) {
			std::cout << "No" << std::endl;
			return 0;
		}
	}
	std::cout << "Yes" << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
 
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
 
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


ll dp[200010];
 
int main(){
	int N; cin >> N;
	vector<int> C(N);
	rep(i,N) cin >> C[i];
	C.erase(unique(C.begin(),C.end()),C.end());
	int M = C.size();
	dp[0] = 1;
	vector<int> before(200010,-1);
	rep(i,M){
		if(before[C[i]] == -1){
			dp[i+1] = dp[i];
			dp[i+1] %= MOD;
		}
		else{
			dp[i+1] = dp[i] + dp[before[C[i]]+1];
			dp[i+1] %= MOD;
		}
		before[C[i]] = i;
	}
	cout << dp[M] << endl;
}


Measured memory_bytes: 3328
#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 = 1e9;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  int ans = min(a, b) + min(c, d);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import numpy as np

N, A, B = list(map(int, input().split()))
h = np.array([int(input()) for i in range(N)], dtype='int64')

left, right = 0, np.ceil(np.max(h)/B)

while left+1 < right:
    mid = np.ceil((left + right) / 2)
    x = h - mid*B
    x[x<0] = 0
    x = np.ceil(x / (A - B))

    if np.sum(x) <= mid:
        right = mid
    else:
        left = mid

print(int(right))

Measured memory_bytes: 17056
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, n) for(int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<62);
const double inf=pow(10,10);
const ld pi=acosl(1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

int main(){
	ll n,m;cin>>n>>m;
	vector<pair<ll,ll>>v;
	rep(i,m){
		ll a,b;cin>>a>>b;
		v.emplace_back(b,a);
	}
	sort(all(v));
	ll nowF=-1*INF;
	ll ans=0;
	rep(i,m){
		if(nowF<v[i].second){
			ans++;
			nowF=v[i].first-1;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <functional>
#include <set>
#include <iterator>

#define INPUT_FROM_FILE (0) 
#if INPUT_FROM_FILE
#include <fstream>
#endif


int main(){
	int n, m, tmp;
	std::vector<int> a, b;
	std::vector<int> result;

#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
#endif

#if INPUT_FROM_FILE
	ifs >> n;
#else
	std::cin >> n;
#endif
	
	for(int i = 0; i < n; i++){
#if INPUT_FROM_FILE
		ifs >> tmp;
#else
		std::cin >> tmp;
#endif
		a.push_back(tmp);
	}

#if INPUT_FROM_FILE
	ifs >> m;
#else
	std::cin >> m;
#endif
	
	
	for(int i = 0; i < m; i++){
#if INPUT_FROM_FILE
		ifs >> tmp;
#else
		std::cin >> tmp;
#endif
		b.push_back(tmp);
	}

	std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(result, result.end()));

	for(int i = 0; i < result.size(); i++){
		std::cout << result[i] << std::endl;
	}
	return 0;
}


Measured memory_bytes: 5160
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

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

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

vi G[N];
int n, X[N], Y[N], ind[N], par[N], sz[N];
ll ans;
vector<pair<int, pii>> E;

bool cmp(int x, int y){
	return (X[x] < X[y]);
}

bool cmp2(int x, int y){
	return (Y[x] < Y[y]);
}

int getpar(int v){
	return (par[v] == v?v:par[v] = getpar(par[v]));
}

void merge(int v, int u, int w){
	v = getpar(v), u = getpar(u);
	if (v == u) return;
	ans += w;
	if (sz[v] < sz[u]) swap(v, u);
	sz[v] += sz[u];
	par[u] = v;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> X[i] >> Y[i];
		ind[i] = i;
	}
	sort(ind + 1, ind + n + 1, cmp);
	for (int i = 2; i <= n; i++){
		E.pb({X[ind[i]] - X[ind[i - 1]], {ind[i - 1], ind[i]}});
	}
	sort(ind + 1, ind + n + 1, cmp2);
	for (int i = 2; i <= n; i++){
		E.pb({Y[ind[i]] - Y[ind[i - 1]], {ind[i - 1], ind[i]}});
	}
	sort(all(E));
	for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
	for (auto u:E){
		merge(u.S.F, u.S.S, u.F);
	}
	cout << ans;




	return 0;
}


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

#define mod 1000000007
#define modd 998244353
#define PI 3.1415926
#define ll long long
#define ld long double
#define pb push_back
#define popb pop_back
#define beg begin()
#define en end()
#define sz(v) (int)((v).size())
#define all(v) (v).begin(),(v).end()
#define ub upper_bound
#define lb lower_bound
#define ff first
#define ss second
#define endl "\n"
#define forn(i,a,n) for(int i=a;i<int(n);++i)
#define forb(i,a,n) for(int i=int(n)-1;i>=a;--i)
#define cout(ans) cout<< ans << "\n"
#define couts(ans) cout<< ans <<" "
#define maxx *max_element
#define minn *min_element


void speed()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
}



void solve()
{
    ll n;cin>>n;
    ll a[n];
    map<ll,ll>m;
    ll sum=0;
    forn(i,0,n)
    {
        cin>>a[i];
        sum+=a[i];
        m[a[i]]++;
    }
    int q;cin>>q;
    while(q--)
    {
        ll x,y;cin>>x>>y;
        sum=sum-m[x]*x;
        sum=sum+m[x]*y;
        m[y]=m[y]+m[x];
        m[x]=0;
        cout(sum);

    }


}


int main()
{   
    speed();
    int tc=1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
}

Measured memory_bytes: 10316
#include<bits/stdc++.h>
#define fo(i,w,n) for(int i=(int) w;i<(int) n;i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
using namespace std;
inline ll read(){
	ll x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	return x*f;
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int r,x;
	cin>>r>>x;
	cout<<(r+2*x)/(2*x+1)<<endl;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
h = list(map(int,input().split()))

dp= [0]*N

for i in range(N):
  if i == 0:
    continue
  if i == 1:
    dp[1] = abs(h[0] - h[1])
  else:
    dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]),dp[i-2]+abs(h[i] - h[i-2]))
print(dp[N-1])

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

#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
#define OMAZINAI cin.tie(0); ios::sync_with_stdio(false);
typedef long long int ll;
ll n, t, u;
ll s = 0, r, r2, ret = (1LL << 62), c1 = 0, c2 = 0, c3 = 0, MIN, MAX;
vector<ll> v;
int main() {
	OMAZINAI;
	cin >> n;
	loop(i, n) {
		cin >> t;
		u = t - i - 1;
		v.push_back(u);
		s += u;
	}
	std::sort(v.begin(), v.end());
	r = v[n / 2];
	r2 = v[n / 2 - 1];
	for (auto h : v) {
		c1 += abs(h - r);
		c2 += abs(h - r2);
	}
	cout << min(c1, c2) << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
int pr[30002],n,i,vis[30002];
int main(){
	
	vector <int> v;
	int sum=0;
	cin>>n;
	if(n==3){
		cout<<"2 5 63"<<endl;
		return 0;
	}
	for(i=30000;i>=2;i=i-2){
		if(n>2){
			v.push_back(i);
			vis[i]=1;
			n--;
			sum+=i;
			
			if(i==12 && n%2==0 && sum%3==0)
			break;
			if(i==10 && n%2==0 && sum%3==0)
			break;
			if(i==8 && n%2==0 && sum%3==0)
			break;
			if(i==6 && n%2==0 && sum%3==0)
			break;
			if(i==4 && n%2==0 && sum%3==0)
			break;
		}
		else
		break;
	}
	int j=3;
	while(n){
		if(sum%j==0 && vis[j]==0){
			for(i=j;i<30000 && n!=0 ;i=i+j)
				if(vis[i]==0 && i%2==1){
					v.push_back(i);
					vis[i]=1;
					n--;
					sum+=i;
				}
		}
		j=j+2;
	}
	for(i=0;i<v.size();i++)
		cout<<v[i]<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>

using namespace std;

int main() {
    string s;
    cin >> s;
    if (s == "Sunny")
        cout << "Cloudy" << endl;
    else if (s == "Cloudy")
        cout << "Rainy" << endl;
    else
        cout << "Sunny" << endl;
    return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

bool check(string a,string b){
  rep(i,a.size()){
    if(a[i] != '*' && a[i] != b[i]){
      return false;
    }
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;
  while(cin >> n && n){
    cin >> m;
    vector<pair<string,ll>> vsl(n);
    rep(i,n){
      cin >> vsl[i].fi >> vsl[i].se;
    }
    string s;
    ll ans = 0;
    rep(i,m){
      cin >> s;
      rep(j,n){
        if(check(vsl[j].fi,s)){
          ans += vsl[j].se;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3180
h, w, a, b = map(int, input().split())

N = h + w

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

mod = 10 ** 9 + 7

factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod



ans = 0
for i in range(1, h - a + 1):
    ans += comb(b + i - 2, b - 1) * comb(h - i + w - b - 1, w - b - 1)
    # print(i, ans)
    ans %= mod
print(ans)


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

int main() {
  char c;
  
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
  {
    cout << "vowel" << endl;
  }
  else
  {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 256