akhauriyash/Code-Regression huggingface dataset:
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();
        String s=sc.next();
        try{
            Integer.parseInt(s.substring(0,a));
            if(s.charAt(a)!='-')throw new Exception();
            Integer.parseInt(s.substring(a+1));
            System.out.println("Yes");
        }catch(Exception e){
            System.out.println("No");
        }
    }

}

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

string s, t;
char idx[128];
vector<string> res;

void rec(int k) {
  if (k == t.size()) {
    res.push_back(t);
    return;
  }
  if (t[k] == 'a' || idx[t[k]] != -1) {
    rec(k + 1);
  }
  if (t[k] != 'z' && idx[t[k]+1] == -1) {
    ++t[k];
    idx[t[k]] = k;
    rec(k + 1);
    idx[t[k]] = -1;
    --t[k];
  }
}

int main() {
  for (; cin >> s && s != "#"; ) {
    res.clear();
    t = s;
    memset(idx, -1, sizeof(idx));
    rec(0);
    sort(res.begin(), res.end());
    cout << res.size() << endl;
    if (res.size() <= 10) {
      for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << endl;
      }
    } else {
      for (int i = 0; i < 5; ++i) {
        cout << res[i] << endl;
      }
      for (int i = res.size() - 5; i < res.size(); ++i) {
        cout << res[i] << endl;
      }
    }

  }
  return 0;
}

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

#define ll long long
#define ld long double

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rrep(i, a, b) for(ll i = a; i >= b; --i)

#define pii pair<int, int>
#define pll pair<ll, ll>

#define fi first
#define se second

#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()

#define endl '\n'
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
  
const ll MOD=1e9+7;
const ll INF=1e18;
const double PI=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
 
const int MAX=1000010;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
   
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  
  ll ans = 0;
  ll sum = 0;
  rep(i,n-1){
    sum += a[i];
    sum %= MOD;
    ll x = a[i+1]*sum;
    x %= MOD;
    ans += x;
    ans %= MOD;
  }
  while(ans<0)ans+=MOD;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4764
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 static List<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);

	        String S = sc.next();
	        char[] s = S.toCharArray();
	        String T = sc.next();
	        char[] t = T.toCharArray();
	        int cnt=0;
	        for(int i=0;i<s.length;i++) {
	        	if(s[i]!=t[i])cnt++;
	        }
	        System.out.println(cnt);
		 }
	}

Measured memory_bytes: 41984
package main

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

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt int

func main() {
	reader.Split(bufio.ScanWords)
	N, _ := strconv.Atoi(read())
	p := make([]int, N)
	p_bef := make([]int, N)
	for i := 0; i < N; i++ {
		t, _ := strconv.Atoi(read())
		p[i] = t
		p_bef[i] = t
	}
	sort.Ints(p_bef)

	for i := 0; i < N; i++ {
		if p[i] != p_bef[i] {
			cnt++
			if 2 < cnt {
				fmt.Println("NO")
				return
			}
		}
	}
	fmt.Println("YES")
}

/*  ----------------------------------------  */

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

func lcm(x, y int) int {
	return (x / gcd(x, y)) * y
}

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; i++ {
		fac[i] = fac[i-1] * i % mod
		inv[i] = mod - inv[mod%i]*(mod/i)%mod
		finv[i] = finv[i-1] * inv[i] % mod
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy [][]int

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i][0] < a[j][0] }

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] < h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


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

#define fo(i, a, b) for (i = a; i <= b; i++)
#define fd(i, a, b) for (i = a; i >= b; i--)

using namespace std;

const int maxn = 200000 + 10, lgn = 20;

int f[maxn * 5], g[maxn * 5], mi[maxn], left[maxn][lgn + 10];
int right[maxn][lgn + 10], v[lgn + 10], x[maxn];
int i, j, k, l, r, s, t, n, m, tot, top;

int main() {
  scanf("%d%d", &n, &t);
  fo(i, 1, n) scanf("%d", &x[i]);
  v[0] = t, t /= 2;
  while (t) v[++top] = t, t /= 2;
  v[++top] = 0, reverse(v, v + top + 1);
  fo(j, 0, top) {
    left[1][j] = 1;
    fo(i, 2, n) if (x[i] - x[i - 1] <= v[j]) left[i][j] = left[i - 1][j];
    else left[i][j] = i;
    right[n][j] = n;
    fd(i, n - 1, 1) if (x[i + 1] - x[i] <= v[j]) right[i][j] = right[i + 1][j];
    else right[i][j] = i;
  }
  f[0] = 0, g[0] = n + 1;
  fo(s, 1, (1 << (top + 1)) - 1) {
    f[s] = 0, g[s] = n + 1;
    fo(i, 0, top) if (s & (1 << i)) {
      r = s ^ (1 << i);
      if (f[r] == n)
        f[s] = n;
      else
        f[s] = max(f[s], right[f[r] + 1][i]);
      if (g[r] == 1)
        g[s] = 1;
      else
        g[s] = min(g[s], left[g[r] - 1][i]);
    }
  }
  fo(i, 0, n) mi[i] = n + 2;
  fo(i, 0, (1 << top) - 1) {
    r = ((1 << top) - 1) ^ i;
    mi[f[i]] = min(mi[f[i]], g[r]);
  }
  fd(i, n - 1, 0) mi[i] = min(mi[i], mi[i + 1]);
  fo(i, 1, n) {
    l = left[i][top];
    r = right[i][top];
    if (mi[l - 1] <= r + 1)
      printf("Possible\n");
    else
      printf("Impossible\n");
  }
  return 0;
}


Measured memory_bytes: 57600
fn main() {
    let _: i64 = read_line();
    let v: Vec<i64> = read_vec();

    let mut ans = 0;
    for a in v {
        ans += a - 1;
    }

    println!("{}", ans);
}

fn read_line<T: std::str::FromStr>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().split_whitespace().map(|e|
        e.parse().ok().unwrap()
    ).collect()
}



Measured memory_bytes: 4352
import java.util.ArrayList;
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String inputs[] = new String[input.length()];

        ArrayList<Character> kotae = new ArrayList<Character>();

        for(int i = 0; i < input.length(); i++){
            inputs[i] = String.valueOf(input.charAt(i));
        }

        for (int i = 0; i < input.length() ; i++){

            if(inputs[i].equals("0")){
                kotae.add('0');
            }

            if(inputs[i].equals("1")){
                kotae.add(('1'));
            }

            if(inputs[i].equals("B") && kotae.size() > 0){
                kotae.remove(kotae.size() -1);
            }

        }

        for(Character an : kotae){
            System.out.print(an);
        }

    }
}


Measured memory_bytes: 25044
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n = input()
            if n == 0:
                break
            p = []
            for i in range(n):
                p.append(input())
            print (sum(p) - min(p) - max(p)) / (n - 2)
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

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

ll ar[200005];

int main()
{
  ll  n, i, ans=0, k, mx=0;

  cin>>n;

  for(i=1; i*i<=n; i++)
  {
    for(int j=1; j*j<=n; j++)
    {
      for(int k=1; k*k<=n; k++)
      {
        ans=(i*i+k*k+j*j+(i*k)+(i*j)+(k*j));
        ar[ans]++;
      }
    }
  }

  for(i=1; i<=n; i++)
  {
    cout<<ar[i]<<endl;
  }
}

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

int main() {
	int a, b;
	cin >> a >> b;
	int c = a + b;
	if (a % 3 == 0 || b % 3 == 0 || c % 3 == 0) {
		cout << "Possible";
	}
	else {
		cout << "Impossible";
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    string s, t;
    cin >> s >> t;

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

    // cout << dp[s.size()][t.size()] << endl;
    string ans;
    for(int i=s.size(), j=t.size(); i>0 && j>0;){
        if(s[i-1]==t[j-1] && dp[i][j]==dp[i-1][j-1]+1){
            ans += s[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] < dp[i][j-1]) j--;
        else i--;
    }

    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

Measured memory_bytes: 35584
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll m,n,yy[3005],money[3005],dp[10005],vis[20]; 

int main()
{
    std::ios::sync_with_stdio(0); std::cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=5000;++i) dp[i]=1e15;
    ll a=1<<m,b,c;
    for(int i=0;i<n;++i)
    {
    	cin>>money[i]>>yy[i];
    	ll s=0;
    	for(int j=1;j<=yy[i];++j) 
    	{
    		cin>>b;vis[b]=1;
    		s+=1<<(b-1);
		}
		yy[i]=s;
	}
	for(int i=1;i<=m;++i) if(!vis[i]) {cout<<-1; return 0;} 
	for(int i=0;i<a-1;++i)
	{
		for(int j=0;j<n;++j)
		{
			dp[i|yy[j]]=min(dp[i|yy[j]],dp[i]+money[j]);
		}
	}
	cout<<dp[a-1];
	return 0;
}

Measured memory_bytes: 3720
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,a,b=mi()

if(a == 0):
    print(0)
elif(n == 0):
    print(0)
else:
        
    ans = (n//(a+b)) * a

    tmp = n%(a+b) 

    if(tmp >0):
        ans += min(tmp,a)

    print(ans)

Measured memory_bytes: 3064
/////////////////////////   _LeMur_
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stack>
#include <string>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

const int N = 200005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int n;
int mas[N];

void query(int x){
    if(mas[x])return ;
    string s;
    cout<<x<<endl;
    cin>>s;
    cout.flush();
    if(s[0] == 'V'){
        exit(0);
    }
    mas[x] = (s[0] == 'M') ? 1 : 2;
}

int main(){
    cin>>n;
    int l = 0 , r = n - 1;
    query(0);
    while(l <= r){
        if(l + 1 == r)break;
        int mid = (l + r) / 2;
        query(mid);
        if(abs(mid - (l % n)) % 2 == 0){
            if(mas[mid] == mas[l % n])
                l = mid;
            else
                r = mid;
        }
        else{
            if(mas[mid] == mas[l % n])
                r = mid;
            else
                l = mid;
        }
    }
    query(r);
	return 0;
}


Measured memory_bytes: 852
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;

int main(){ 
    int n,res=0;
    cin >> n;
    while(n>=1){
        res += n;
        n--;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tuple>
#include <queue>
#include <bitset>
#include <unordered_map>
#include <tuple>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sys/time.h>

using namespace std;

void solve(long long H, long long W, vector<string> S){
  vector< vector<long long> > r(H, vector<long long>(W, 0));
  vector< vector<long long> > l(H, vector<long long>(W, 0));
  vector< vector<long long> > u(H, vector<long long>(W, 0));
  vector< vector<long long> > d(H, vector<long long>(W, 0));
  for (int i = 0; i < H; i++) {
    r[i][W-1] = S[i][W-1]=='#' ? -1 : 0;
    for (int j = 1; j < W; j++) {
      r[i][W-1-j] = S[i][W-1-j]=='#' ? -1 : r[i][W-j] + 1;
    }
  }
  for (int i = 0; i < H; i++) {
    l[i][0] = S[i][0]=='#' ? -1 : 0;
    for (int j = 1; j < W; j++) {
      l[i][j] = S[i][j]=='#' ? -1 : l[i][j-1] + 1;
    }
  }
  for (int j = 0; j < W; j++) {
    u[H-1][j] = S[H-1][j]=='#' ? -1 : 0;
    for (int i = 1; i < H; i++) {
      u[H-1-i][j] = S[H-1-i][j]=='#' ? -1 : u[H-i][j] + 1;
    }
  }
  for (int j = 0; j < W; j++) {
    d[0][j] = S[0][j]=='#' ? -1 : 0;
    for (int i = 1; i < H; i++) {
      d[i][j] = S[i][j]=='#' ? -1 : d[i-1][j] + 1;
    }
  }
  long long ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      ans = max(ans, r[i][j] + l[i][j] + u[i][j] + d[i][j]);
    }
  }
  std::cout << ans + 1 << std::endl;
}

int main(){
  long long W;
  long long H;
  scanf("%lld",&H);
  vector<string> S(H);
  scanf("%lld",&W);
  for(int i = 0 ; i < H ; i++){
    cin >> S[i];
  }
  solve(H, W, S);
  return 0;
}


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

int main()
{
    int N;
    cin>>N;
    vector<int> A(N), B(N);
    for (int &a: A)
        cin>>a;
    for (int &b: B)
        cin>>b;

    vector<pair<int,int>> T;
    for (int i=0; i<N; i++)
        T.push_back(make_pair(B[i], A[i]));
    sort(T.begin(), T.end());
    for (int i=0; i<N; i++)
        A[i] = T[i].second,
        B[i] = T[i].first;

    vector<int> I(N);
    for (int i=0; i<N; i++)
        I[i] = i;
    sort(I.begin(), I.end(), [&](int a, int b){return A[a]<A[b];});

    int c = 1;
    int p = I[0];
    while (p!=0)
    {
        p = I[p];
        c++;
    }

    bool ok = true;
    for (int i=0; i<N; i++)
        if (A[I[i]]>B[i])
            ok = false;
    if (!ok)
    {
        cout<<"No"<<endl;
        return 0;
    }

    if (c<N)
    {
        cout<<"Yes"<<endl;
        return 0;
    }

    for (int i=0; i<N-1; i++)
        if (A[I[i+1]]<=B[i] && A[I[i]]<=B[i+1])
        {
            cout<<"Yes"<<endl;
            return 0;
        }

    cout<<"No"<<endl;
}


Measured memory_bytes: 2168
a, b = [int(i) for i in input().split()]
c = []
for i in range(a):
    c.append(int(input()))

c.sort()

temp = 999999999999999999999999999999999999999999999999999999999999999999999999999999999
for a in range(len(c) - b + 1):
    s = c[a + b - 1]
    t = c[a]
    if s - t < temp:
        temp = s - t

print(temp)

Measured memory_bytes: 7384
#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll ans=0;
const int MAX=1<<18;
int t[2*MAX];
vi pos[26];

void update(int u,int c)
{
  for (t[u+=MAX]+=c;u>1;u>>=1)t[u>>1]=t[u]+t[u^1];
}

int query(int u,int v)
{
	int sum=0;
	for (u+=MAX,v+=MAX;u<v;u>>=1,v>>=1)
	{
		if (u&1)sum+=t[u++];
		if (v&1)sum+=t[--v];
	}
	return sum;
}

vector<pii>pairs;

int32_t main()
{
  BOOST;
  string s;
  cin>>s;
  int n=sz(s);
  int wsk=-1;
  for (int i=0;i<n;i++)pos[s[i]-'a'].pb(i);
  for (int i=0;i<26;i++)
  {
  	if (sz(pos[i])&1)
  	{
  		if (wsk!=-1)cout<<"-1",exit(0);
  		wsk=i;
  	}
  }
  
  if (wsk!=-1)
  {
  	int mid=pos[wsk][sz(pos[wsk])>>1];
  	for (int i=0;i<26;i++)
  	  for (int j=0;j<sz(pos[i])>>1;j++)
  	    {
  	    	if (pos[i][j]>mid)ans++;
  	    	if (pos[i][sz(pos[i])-j-1]<mid)ans++;
  	    }
  }
  
  for (int i=0;i<26;i++)
  	for (int j=0;j<sz(pos[i])/2;j++)
  	  pairs.pb(mp(pos[i][j],pos[i][sz(pos[i])-j-1]));
  sort(pairs.begin(),pairs.end());
  
  for (auto it:pairs)
  {
  	//cout<<"TERAZ "<<it.st<<" "<<it.nd<<"\n";
  	int a=it.st+1,b=it.nd+1;
  	ans+=query(1,a)*2+query(a,b);
  	update(b,1);
  }
  
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3852
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 500;

typedef long long ll;

int A[N], dp[N][2], n;
ll sol = 0;

int f(int x, int lst){
	if(!A[x] && lst) return -N;
	if(x == n) return 0;
	if(dp[x][lst] != -1) return dp[x][lst];
	return dp[x][lst] = max((A[x] == 2 && !lst) ? f(x + 1, 0) + 1 : 0, max(f(x + 1, 0), (A[x] > lst ? f(x + 1, 1) + 1 : 0)));
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		if(A[i] > 2){
			sol += (A[i] - 1) / 2;
			A[i] %= 2; 
			if(!A[i])
				A[i] = 2;
		}
		if(A[i] == 2 && (i == 0 || i == n - 1)){
			sol++; A[i] = 0;
		}
	}	
	printf("%lld\n", sol + f(0, 0));
}

Measured memory_bytes: 7552
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

ll five(ll A) {
    return A * A * A * A * A;
}

int main() {
    ll X;
    cin >> X;
    unordered_map<ll, ll> power;
    ll A = 0;
    while (true) {
        ll A5 = five(A);
        power[A5] = A;
        ll B5 = A5 - X;
        if (power.find(B5) != power.end()) {
            ll B = power[B5];
            cout << A << " " << B << endl;
            return 0;
        }
        A++;
        // overflow?
        if (five(A) - five(A-1) > X) {
            break;
        }
    }
    A = 0;
    while (true) {
        ll A5 = five(A);
        power[A5] = A;
        ll B5 = X - A5;
        if (power.find(B5) != power.end()) {
            ll B = power[B5];
            cout << A << " " << (-B) << endl;
            return 0;
        }
        A++;
    }
}


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

int main() {
  int n,x1,x2;
  cin >> n;
  
  x1 = n / 100;
  //cout << x1 << endl;
  x2 = n - x1 * 100;
  //cout << x2 << endl;
  
  if(x1 * 5 >= x2){
    cout << 1 << endl;
  }
  else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int N; cin >> N;
  string A,B,C; cin >> A >> B >> C;
  int c = 0;
  for(int i = 0; i < N; i++){
    vector<int> cnt(26,0);
    cnt[A[i]-'a']++; cnt[B[i]-'a']++; cnt[C[i]-'a']++;
    
    char w = A[i];
    for(int j = 0; j < 26; j++){ 
      if(cnt[j] >= 2){  w = (char)(j+'a'); break;}}
    
    if(w!=A[i]){ c++;} if(w!= B[i]){ c++;} if( w!= C[i]){ c++;}
  }
  
  cout << c << endl; return 0;}

Measured memory_bytes: 256
import java.util.*;
// import java.io.*;
// import java.time.*;

public class Main {
    static StringBuilder sb;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();

        int a = sc.nextInt();

        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < a; i++) {
            array.add(sc.nextInt());
        }

        int b = sc.nextInt();

        int index = 0;
        for (int i = 0; i < b; i++) {
            int tmp = sc.nextInt();
            while (index < a && array.get(index) < tmp) {
                index++;
            }
            if (index == a || array.get(index) != tmp) {
                System.out.println(0);
                return;
            }
        }

        System.out.println(1);
        
        sc.close();
    }
}



Measured memory_bytes: 128772
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func nextFloat64() (float64, error) {
	return strconv.ParseFloat(nextString(), 64)
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	t := make([][]int, n)
	for i := 0; i < n; i++ {
		t[i] = []int{
			nextInt(),
			nextInt(),
		}
	}

	sort.Slice(t, func(i, j int) bool {
		return t[i][1] < t[j][1]
	})

	// fmt.Println(t)

	tMax := -1
	nActivities := 0
	for i := 0; i < n; i++ {
		if tMax < t[i][0] {
			tMax = t[i][1]
			nActivities++
		}
	}

	fmt.Println(nActivities)
}



Measured memory_bytes: 7412
n, m = map(int, input().split())
if m > n:
    n, m = m, n

if m == 1:
    if n == 1:
        print(1)
    else:
        print(n - 2)
elif m == 2:
    print(0)
else:
    print((n - 2) * (m - 2))


Measured memory_bytes: 2940
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], b[N], c[N], fir[N], ach[N]; LL ans, pre[N];

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline void init() {
	in(n);
	for (int i = 1; i <= n; ++i) in(a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) in(b[i]);
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; ++i) in(c[i]);
	sort(c + 1, c + n + 1);
}

inline void work() {
	int pos = 1;
	for (int i = 1; i <= n; ++i) {
		for (; pos <= n && a[pos] < b[i]; ++pos);
		fir[i] = pos - 1, pre[i] = pre[i-1] + (LL)fir[i];
	}
	pos = 1;
	for (int i = 1; i <= n; ++i) {
		for (; pos <= n && b[pos] < c[i]; ++pos);
		ans += pre[pos - 1];
	}
	printf("%lld\n", ans);
}

int main() {init(), work(); return 0;}

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

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int main(){
    string str;
    cin >> str;
    int N = str.size();
    vector<int> S(N);
    for(int i=0; i<N; i++) S[i] = str[i] - '0';

    static int64_t dp[310][310][310];
    dp[N][0][0] = 1;
    for(int i=N; i>0; i--) for(int j=0; j<N; j++) for(int k=0; k<N; k++){
        int64_t v = dp[i][j][k];
        if(S[i-1]){
            add(dp[i][j+1][k], v);
            add(dp[i-1][j][k], v);
        }else{
            add(dp[i][j][k+1], v);
            add(dp[i-1][j][k], v);
        }
    }

    static bool can[310][310][310];
    can[0][0][0] = true;

    int64_t ans = 0;
    for(int i=0; i<=N; i++) for(int j=0; j<N; j++) for(int k=0; k<N; k++) if(can[i][j][k]){
        //cerr<<i<<j<<k<<" "<<dp[i][j][k]<<endl;
        add(ans, dp[i][j][k]);
        can[i+1][j][k] = true;
        if(i<N-1){
            if(S[i] || S[i+1]) can[i+2][j][k+1] = true;
            if(!S[i] || !S[i+1]) can[i+2][j+1][k] = true;
        }
        if(i<N && j && S[i]) can[i+1][j-1][k+1] = true;
        if(i<N && k && !S[i]) can[i+1][j+1][k-1] = true;
    }
    add(ans, MOD-1);

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 231956
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int H, W, sh, sw;
bool Win[2][510][510];
int dh[4] = {1, -1, 0, 0};
int dw[4] = {0, 0, 1, -1};
bool Wall[510][510][4];

void Horz(int h) {
    for(int w = 1; w <= W; w++) {
        cin >> Wall[h][w][1];
        Wall[h-1][w][0] = Wall[h][w][1];
    }
}

void Vert(int h) {
    for(int w = 1; w <= W + 1; w++) {
        cin >> Wall[h][w][3];
        Wall[h][w-1][2] = Wall[h][w][3];
    }
}

void solve() {
    for(int h = 1; h <= H; h++) {
        for(int w = 1; w <= W; w++) {
            Win[0][h][w] = false;
            Win[1][h][w] = false;
        }
    }
    for(int h = 1; h <= H; h++) {
        Horz(h);
        Vert(h);
    }
    Horz(H+1);
    /*
    for(int h = 0; h <= H + 1; h++) {
        for(int w = 0; w <= W + 1; w++) {
            cerr << Wall[h][w][1] << " ";
        }
        cerr << endl;
    }
    */
    queue<i_i> que;
    for(int w = 0; w <= W + 1; w++) {
        Win[0][0][w] = true;
        Win[1][0][w] = true;
        que.push({0, w});
        Win[0][H+1][w] = true;
        Win[1][H+1][w] = true;
        que.push({H+1, w});
    }
    for(int h = 0; h <= H + 1; h++) {
        Win[0][h][0] = true;
        Win[1][h][0] = true;
        que.push({h, 0});
        Win[0][h][W+1] = true;
        Win[1][h][W+1] = true;
        que.push({h, W+1});
    }
    while(!que.empty()) {
        auto now = que.front();
        que.pop();
        int nowh = now.first;
        int noww = now.second;
        for(int k = 0; k < 4; k++) {
            int newh = nowh + dh[k];
            int neww = noww + dw[k];
            if(newh <= 0 or newh > H) continue;
            if(neww <= 0 or neww > W) continue;
            int newstate = 1 - Wall[nowh][noww][k];
            //cerr << k << ": " << "(" << nowh << ", " << noww << ") -> (" << newh << ", " << neww << ") with state " << newstate << endl;
            //cerr << Wall[nowh][noww][k] << " " << newstate << endl;
            if(Win[newstate][newh][neww]) continue;
            Win[newstate][newh][neww] = true;
            if(Win[1-newstate][newh][neww]) {
                que.push({newh, neww});
            }
        }
    }
    /*
    cerr << "------------------------" << endl;
    for(int h = 1; h <= H; h++) {
        for(int w = 1; w <= W; w++) {
            cerr << (Win[0][h][w]) << " ";
        }
        cerr << endl;
    }
    cerr << endl;
    for(int h = 1; h <= H; h++) {
        for(int w = 1; w <= W; w++) {
            cerr << (Win[1][h][w]) << " ";
        }
        cerr << endl;
    }
    return;
    */
    if(Win[1][sh][sw]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    //cout.precision(10);
    while(cin >> H >> W >> sh >> sw) {
        if(H == 0) break;
        solve();
    }
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    signed long long int tmp = 1, tmp2 = 1, tmp3 = 1, ans = 0;
    for(int i = 0; i<n; i++){
        tmp *= 10;
        tmp2 *= 9;
        tmp3 *=8;
        tmp %= 1000000007;
        tmp2 %= 1000000007;
        tmp3 %= 1000000007;
    }
    ans = tmp - 2*tmp2 + tmp3;
    ans%=1000000007;
    if(ans < 0) ans+=1000000007;
    
    cout << ans;
}

Measured memory_bytes: 3632
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    ans = 0
    for i in range(60):
        s = 0
        for a in A:
            if a & (1 << i):
                s += 1
        tmp = 0
        for j in range(N):
            if A[j] & (1 << i):
                s -= 1
                tmp += (N - j - 1) - s
            else:
                tmp += s
        ans = (ans + tmp * pow(2, i, MOD)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return b/gcd(a,b)*b;}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> s(m);
  vector<int> c(m);
  vector<int> a(n+1);
  a[0] = 0;
  rep(i, m) {
    cin >> s[i] >> c[i];
  }
  bool zero = false;
  rep(i, m){
    if (s[i] == 1 && c[i] == 0 && n > 1) {
      cout << -1 << endl;
      return 0;
    } 
    if (a[s[i]] == 0 || a[s[i]] == c[i]) {
      a[s[i]]=c[i];
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  if (n == 1 && a[1] == 0) {
    cout << 0 << endl;
    return 0;
  }
  if (a[1] == 0) a[1]=1;
  
  int ans = 0;
  ll k = pow(10, n-1);
  for(int i = 1; i <= n; i++) {
    ans += k * a[i];
    k /= 10;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n, h, *A = map(int, open(0).read().split())
a = max(A[::2])
b = sorted(A[1::2])[::-1]
for i in range(n):
    if h <= 0:
        n = i
        h = 0
        break
    if b[i] < a:
        n = i
        break
    h -= b[i]
print(n - (-h // a))


Measured memory_bytes: 110436
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,l1=0,l2=0,len=0;
    char x;
    string o="0",e="0";
    cin>>o>>e;

    l1=o.size();
    l2=e.size();
    len=l1+l2;
    char a[len+1];
    for(i=0,j=0;i<len,j<l1;i+=2,j++)
    {
        a[i]=o[j];

    }

    for(i=1,j=0;i+2<len,j<l2;i+=2,j++)
    {
        a[i]=e[j];
    }
    for(i=0;i<len;i++)
    {
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
n, c = gets.to_s.split.map{|t| t.to_i }

d = [[]] + Array.new(c){ [0] + gets.to_s.split.map{|t| t.to_i } }
grid = Array.new(n){ gets.to_s.split.map{|t| t.to_i } }

counters = Array.new(3){ Hash.new(0) }

# O(N^2)
n.times do |i|
  n.times do |j|
    counters[(i+j)%3][grid[i][j]] += 1
  end
end

# O(cP3)
ans = n * n * 1000
(1..c).to_a.permutation(3) do |colors|
    
  cost = 0
  3.times do |i|
    color = colors[i]
    counter = counters[i]
    
    counter.each do |(col, cnt)|
      
      next if col == color
      cost += d[col][color] * cnt
    end
  end
  
  ans = cost if ans > cost
end

puts ans

Measured memory_bytes: 4476
/*
 Templatka c++ Kacper Fis																							   																											   //
*/

#include <iostream>
#include <cstdio>
#include <limits>
#include <cstdlib>
#include <utility>
#include <iterator>
#include <bitset>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>
#include <time.h>
#include <iomanip>
#include <sstream>
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000001;
const float PI = 3.14;
typedef long long LL;

typedef vector<int> vi;
typedef list<int> li;
typedef queue<int> qi;
typedef pair<int,int> ii;
typedef map<string,int> msi; //np msi['nazwa'] = 'liczba'
typedef vector<ii> vii; //vector par<int>, do tworzenia tablicy dla grafów wagowych #dijkstra #Bellman_Ford
typedef priority_queue< ii, vector<ii>, greater<ii> > pq; //kolejka priorytetowa vectorów par(top()=min) #dijkstra


#define print_list(x) for(it = (x).begin(); it != (x).end(); it++) {cout << *it << " ";}
#define print_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++) {cout << *it2 << " ";}
#define search_list(x) for(it = (x).begin(); it != (x).end(); it++)
#define search_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++);
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x, y) make_pair(x, y)
///////////////////////////////////////////////GLOBAL DEFINITIONS////////////////////////////////////////////////////////


///////////////////////////////////////////////////FUNCTIONS/////////////////////////////////////////////////////////////



/////////////////////////////////////////////////////MAIN////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{ios_base::sync_with_stdio(false); cin.tie(NULL);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
	int n;
	cin >> n;
	int ans = 0;
	int liczba = 0;
	
	for(int i = 1; i <= n; i++){
		int licznik = 0;
		int temp = i;
		while(temp){
			if(temp % 2 == 0){
				temp /= 2;
				licznik++;
			}
			else break;
		}
		
		if(licznik >= liczba){
			liczba = licznik;
			ans = i;
		}
	}
	
	cout << ans << endl;
	
	
	
	
	
	
	
	return 0;
}


Measured memory_bytes: 256
N, W = map(int, input().split())
ws = []
vs = []

for i in range(N):
	w, v = map(int, input().split())
	ws.append(w)
	vs.append(v)

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	if (k+1)*w1 > W:
		break
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)

Measured memory_bytes: 45644
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<<n<<":";
    int j=n;
    for(int i=2;i*i<=j;i++){
        while(n%i==0){
            cout<<" "<<i;
            n=n/i;
        }
    }
    if(n!=1){
        cout<<" "<<n;
    }
    cout<<endl;
    return 0;
}


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

int main() {
    int n; cin >> n;
    vector<int> b(n - 1);
    for (int &bi: b) cin >> bi;
    int sum = b[0] + b[n - 2];
    for (int i = 0; i + 1 < n - 1; i++) sum += min(b[i], b[i + 1]);
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
x=list(map(int,input().split()))
ans=10**10
for i in range(n-k+1):
    ans=min(ans,abs(x[i])+abs(x[i]-x[i+k-1]))
    ans=min(ans,abs(x[i+k-1])+abs(x[i]-x[i+k-1]))
print(ans)

Measured memory_bytes: 14380
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

const ll inf = 5e15;
V<ll> ans;

bool solve() {
    ll N, M;
    cin >> N >> M;
    string S;
    cin >> S;

    V<ll> dists(N + 1, inf);
    ll idx = inf;
    dists.back() = 0;
    for(ll i = 1; i <= M; i++) {
        if(N - i < 0) break;
        if(S[N - i] == '1') continue;
        dists[N - i] = 1;
        idx = N - i;
    }

    if(idx == inf) return false;

    for(ll i = N - M - 1; 0 <= i; i--) {
        if(S[i] == '1') continue;
        while(M < idx - i) idx--;
        while(i < idx && dists[idx] == inf) idx--;
        if(i == idx) return false;
        dists[i] = dists[idx] + 1;
    }

    if(dists[0] == inf) return false;
    DEBUG(dists);

    ll cur_d = dists[0];
    ll cur = 0;
    while(cur < N) {
        ll tmp = cur;
        while(dists[cur] != cur_d - 1) cur++;
        ans.push_back(cur - tmp);
        cur_d--;
    }

    return true;
}

int main() {
    if(solve()) {
        for(ll e : ans) cout << e << ' ';
        cout << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
struct Edge{ll from, to, cost;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, M;
  vector<P> bridge;
  cin >> N >> M;
  rep(i, M){
    ll a, b;
    cin >> a >> b;
    bridge.push_back({a,b});
  }

  sort(ALL(bridge), [](P a, P b){return a.second < b.second;} );

  ll ind = 0;
  ll ans = 1;
  /*
  cout << endl;
  rep(i, M){
    cout <<i <<" "<< bridge[i].first << " " << bridge[i].second << endl;
  }
  */

  ll val = bridge[ind].second;
  rep(i, M){
    if(bridge[i].first>=val){
      ans ++;
      val = bridge[i].second;
    }
  }
  /*
  while(ind < M){
    P tmp = bridge[ind];
    ind = lower_bound(ALL(bridge), tmp.second, [](P a, ll num){return num > a.first;}) - bridge.begin();
    ans++ ;
    cout << ind << endl;
    }
*/
  cout << ans;
  
  return 0;
}


Measured memory_bytes: 1400
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import operator

N,H,W = map(int,readline().split())
m = map(int,read().split())
RCA = sorted(zip(m,m,m),key=operator.itemgetter(2),reverse=True)

root = list(range(H+W))
size = [0] * (H+W)
no_cycle = [True] * (H+W)

def find_root(x):
    path = []
    while True:
        y = root[x]
        if x == y:
            break
        path.append(x)
        x = y
    for p in path:
        root[p] = x
    return root[x]

def merge(x,y):
    x,y = find_root(x),find_root(y)
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    no_cycle[x] = no_cycle[x] and no_cycle[y]

answer = 0
for R,C,A in RCA:
    x,y = R-1,H+C-1
    rx,ry = find_root(x),find_root(y)
    if rx == ry:
        if not no_cycle[rx]:
            continue
        no_cycle[rx] = False
    else:
        if (not no_cycle[rx]) and (not no_cycle[ry]):
            continue
        merge(rx,ry)
    answer += A

print(answer)

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int count = 0;
    for(int i = 0; i <= a; i++)
    {
        for(int j = 0; j <= b; j++)
        {
            for(int k = 0; k <= c; k++)
            {
                int sum = i * 500 + j * 100 + k * 50;
                //cout << sum << endl;
                if(sum == x)
                {
                    count++;
                }
                /*0 + 0 + 0 = 50
                  0 + 0 + 100 = 100
                  0 + 100 + 0 = 100
                  0 + 100 + 50 = 150
                  0 + 200 + 50 = 250
                */
            }
        }
    }
    cout << count << endl;

    return 0;
}


Measured memory_bytes: 256
import math
from bisect import bisect_left as bl
from itertools import accumulate

n,h = map(int,input().split())
A = []
B = []
ans = 0

for _ in range(n):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)

A.sort(reverse=1)
B.sort()

index = bl(B, A[0])
B = B[index:]
B = list(accumulate(B[::-1]))
if B[-1] >= h:
  print(bl(B,h)+1)
  exit()
  
h -= B[-1]
ans += len(B)
ans += math.ceil(h/A[0])
print(ans)

Measured memory_bytes: 16532
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v):
    if v > 3234566667:
        return
    ans.append(v)
    d = v % 10
    if d - 1 >= 0:
        dfs(v * 10 + d - 1)
    dfs(v * 10 + d)
    if d + 1 < 10:
        dfs(v * 10 + d + 1)


K = int(input())
ans = []
[dfs(i) for i in range(1, 10)]
print(sorted(ans)[K - 1])


Measured memory_bytes: 14524
#include<iostream>
#include<string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <algorithm>
#include <cstdlib>
using namespace std;
int ctoi(char c) {
	switch (c) {
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return 0;
	}
}

int main() {
	int R, G , B ,N;
	cin >> R >> G >> B >> N;
	int ans = 0;
	int i, j;
	for (i = 0; i <= N / R; i++) {
		for (j = 0; j <= (N - R * i) / G; j++) {
			if ((N - R * i - G * j) % B == 0) {
				ans++;
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
//In th name of ALLAH\\

// m    m  mmmm  mmmmm          mmmm   mmmm
// #    # m"  "m   #           "   "# m"  "m
// #mmmm# #    #   #             mmm" #    #
// #    # #    #   #     """       "# #    #
// #    #  #mm#  mm#mm         "mmm#"  #mm#

#include <bits/stdc++.h>
#define cn const int
#define ll long long
#define pq priority_queue
#define enter cout << endl
#define pb push_back
#define ff first
#define ss second
#define pii pair <int, int>
#define vi vector <int>
#define msi map <string, int>
#define Qi queue <int>
#define dQi deque <int>
#define str string
#define int ll
#define FOR(v, i, j) for (int v = i; v < j; v ++)
#define ROF(v, i, j) for (int v = i; v > j; v --)
using namespace std;

//START hh : mm \\// ET mm + mm
//	       END hh : mm

cn mod = 1e9 + 7;
cn inf = 2e9 + 9e2;
const ll linf = 2e18 + 18e2;
cn MAXN = 2e5 + 5e2;

int a[MAXN];

void f(int n) {
    if (n == 0) {cout << a[0] << ' '; return;}
    if (n < 0) return;
    cout << a[n] << ' ';
    f(n-2);
    cout << a[n-1] << ' ';
}

main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i =0 ;i < n;i ++)
        cin >> a[i];
    f(n - 1);
    return 0;
}

//Sea do not have any space for unmanned ships
//This region of city is safe, i have been tried to stay alive
//I used to be good till this city makes me bad with its drought

// m    m mmmmmm m      m      mmmmm         mmmmm     mm
// #    # #      #      #        #           #        m"#
// #mmmm# #mmmmm #      #        #           """"mm  #" #
// #    # #      #      #        #     """        # #mmm#m
// #    # #mmmmm #mmmmm #mmmmm mm#mm         "mmm#"     #
//	        	   H-54703802904130102


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

int main()
{
  int N,X,Y;
  cin >> N >> X >> Y;

  int A[N];
  for(int i=0;i<N;i++){A[i] = 0;}
   
  for(int i=0;i<N;i++)
  {
    for(int j=i+1;j<N;j++)
    {
      int dis=abs(i-X+1)+abs(j-Y+1)+1;
//      if( i<X && j<X){ dis= N;}
//      else if(i<X &&        X<j && j<Y){ dis = (X-i)+(Y-j)}
//      else if(i<X        &&        Y<j){ dis = (X-i)+(j-Y)}
//      else if(X<i && i<Y && X<j && j<Y){ dis = (i-X)+(Y-j)}
//      else if(X<i && i<Y        && Y<j){ dis = (i-X)+(j-Y)}
//      else // if(Y<X)
//      { dis =      }      
      A[ min(j-i,dis) ]++;
//      cout << j-i << ' ' << dis  << ' ';
    }
//    cout << endl;
  }
  
  for(int i=1;i<N;i++)
  {
    cout <<A[i]<<endl;
  }
  
  return 0; 
}

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

using namespace std;

int main(){
  vector<int> a;
  int n,num;

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> num;
    a.push_back(num);
    //cout << num << endl;
  }

  int q,k;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> k;
    auto itr_b = a.begin();
    auto itr_e = a.end();
    auto itr = lower_bound(itr_b, itr_e, k);
    size_t pos = distance(itr_b, itr);
    cout << pos << endl;
  }

  return 0;
}



Measured memory_bytes: 3548