akhauriyash/Code-Regression huggingface dataset:
let n, q = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> a, b)

let g = Array.init n (fun _ -> [])
let () =
  Array.init (n - 1) (fun _ -> Scanf.sscanf (read_line ()) "%d %d" (fun a b -> a-1, b-1))
  |> Array.iter (fun (a, b) ->
      g.(a) <- b :: g.(a);
      g.(b) <- a :: g.(b)
  )

let sum = Array.init n (fun _ -> 0)
let () =
  Array.init q (fun _ -> Scanf.sscanf (read_line ()) "%d %d" (fun q x -> q - 1, x))
  |> Array.iter (fun (q, x) -> sum.(q) <- sum.(q) + x)

let ans = Array.init n (fun _ -> 0)

let rec cumsum now par acc =
  let acc = acc + sum.(now) in (
    ans.(now) <- acc;
    List.iter (fun child -> if child = par then () else cumsum child now acc) g.(now)
  )

let () = (
  cumsum 0 0 0;
  for i = 0 to n - 1 do
    Printf.printf "%d " ans.(i)
  done
)


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

using namespace std;

int main(){
    vector<int> vec; 
    // vector<int> change; 
    
    int x,a,num=1,change=0;
    cin>>x;
    for (int i = 0; i <x ; i++){
        cin>>a;
        vec.push_back(a);
    }
    for (int i = 0; i <x ; i++){
        if(vec[i]!=num){
            change++;
        }
        // else{
        //     cout<<vec[i]<<" wrong "<<endl;
        //     change++;
            
        // }
        num++;
        
    }
    if(change>2){
        cout<<"NO";
    }
    else{
        cout<<"YES";
    }
    
     return 0;   
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
struct Dice{
  int s[6];
  void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
    if(c=='R'){
      b=s[1];
      s[1]=s[2];
      s[2]=s[4];
      s[4]=s[3];
      s[3]=b;
    }    
  }
  int top() {
    return s[0];
  }
  int right(){
    return s[2];
  }
  int left(){
    return s[3];
  }
  int front(){
    return s[1];
  }
};
int main(){
  Dice d;
  for(int i=0;i<6;i++) cin >> d.s[i];
  int n;cin >> n;
  while(n--){
    int a,b;cin >> a >> b;
    if(d.left()==a) d.roll('E');
    if(d.right()==a) d.roll('W');
    while(d.top()!=a) d.roll('N');
    while(d.front()!=b) d.roll('R');
    cout << d.right() << endl;
  }
  return 0;
}


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


#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

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

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


int h=8,w=8;
vector<vector<char>> g(h,vector<char>(w));


bool bfs(int x,int y){

    //db2(x,y);
    if(g[y][x] == '.'){return false;}
    if(x == w-1&& y == h-1)return true;
    
    bool f1=false;
    bool f2=false;
    if(x < w-1){f1=bfs(x+1,y);}
    if(y < h-1){f2=bfs(x,y+1);}

    return f1 | f2;
}

int main(){
    bool flag=false;
    ll ans=0,sum=0;

    cin>>h>>w;

    int cnt=0;
    rep(i,h){
        rep(j,w){
            cin>>g[i][j];
            if(g[i][j]=='#')++cnt;
        }
    }

    if(cnt == h+w-1 && bfs(0,0)){
        cout<<"Possible"<<endl;
    }else{
        cout<<"Impossible"<<endl;
    }
    //cout <<fixed<<setprecision(16)<< << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();
        int[] w = new int[N], v = new int[N];
        for(int i = 0; i < N; i++){
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        long[][] x = new long[N][100001]; //i番目までの荷物から価値がjになるように選んだ時の重さの最小値
        x[0][0] = 0;
        for(int j = 0; j <= 100000; j++){
            for(int i = 0; i < N; i++){
                if(j == 0) x[i][0] = 0;
                else if(i == 0){
                    x[0][j] = (j == v[0]) ? w[0] : -1;
                }
                else if(j - v[i] >= 0 && x[i-1][j - v[i]] >= 0){
                    x[i][j] = (x[i-1][j] >= 0) ? Math.min(x[i-1][j - v[i]] + w[i], x[i-1][j]) : x[i-1][j - v[i]] + w[i];
                }
                else{
                    x[i][j] = x[i-1][j];
                }
           }
        }
        long ans = 0;
        for(int j = 0; j <= 100000; j++){
            if(x[N-1][j] <= W && x[N-1][j] >= 0){
                ans = j;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 129492
import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
INF = 10 ** 12

dp = np.array([0] + [INF for _ in range(N - 1)], dtype=np.int64)
for i in range(1, N):
    dp[i] = np.min(dp[max(0, i-K):i] + np.abs(h[i] - h[max(0, i-K):i]))

print(dp[N-1])

Measured memory_bytes: 22800
using System;

class D {
    public static void Main() {
        var s = Console.ReadLine();
        var start = s.Length;
        var end = s[0] == s[s.Length - 1] ? 1 : 0;
        Console.WriteLine(((start - end) & 1) != 0 ? "First" : "Second");
    }
}


Measured memory_bytes: 11232
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define INF 1000000007
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2)*pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int jo(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= 2;
	}
	return ans;
}
signed main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b && b == c) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
}

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

using namespace std;

#define INF (1ll << 62)
#define eb emplace_back
#define ii pair<int,int>
#define OK (cerr <<"OK"<< endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'
const int MOD = 1e9 + 7;

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

  string s;

  cin >> s;

  set<char> ss;
  for(char c: s) {
    ss.insert(c);
  }

  if(ss.size() > 1)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<cctype>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if ((a + b) % 2 == 0)
		cout << (a + b) / 2 << endl;
	else
		cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import Decimal
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub, itemgetter
# import numpy as np

import sys
sys.setrecursionlimit(10000)

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time
	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def read_int(input=None):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [int(x) for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret

def read_float(input):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [float(x) for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret
	
def read_str(input):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [x for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret
		
def read_int(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return int(read)

def read_int_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [int(x) for x in read.split()]

def read_float(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return float(read)

def read_float_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [float(x) for x in read.split()]

def read_str(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return str(read)

def read_str_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [str(x) for x in read.split()]	

@mt
def slv(*args):
	X.sort()
	
	Y = []
	for i in range(M-1):
		Y.append(X[i+1] - X[i])
	Y.sort(reverse=True)
	
	ans = X[-1] - X[0]
	for y in Y[:N-1]:
		ans -= y
	
	return ans

if __name__ == '__main__':
	t = '''3 7
-10 -3 0 9 -100 2 17'''.splitlines()
	
	N, M = read_int_n()
	X = read_int_n()
	
	print(slv(N,M,X))
	

Measured memory_bytes: 14956
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;

const ll MOD = 1e9 + 7;

// to container
template <class C>
void input(C &c)
{
    for_each(c.begin(), c.end(), [](auto &i) { cin >> i; });
}

// to number, string
template <class T>
T input()
{
    T data;
    cin >> data;
    return data;
}

ll mpow(ll a, ll n, ll p)
{
    ll x = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            x = a * x % p;
        }
        a = a * a % p;
        n >>= 1;
    }

    return x;
}

ll mfact(ll n, ll p)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
    {
        res = res * i % p;
    }
    return res;
}

ll mcomb(ll n, ll r, ll p)
{
    ll a = mfact(n, p);
    ll b = mfact(n - r, p);
    ll c = mfact(r, p);
    return (((a * mpow(b, p - 2, p)) % p) * mpow(c, p - 2, p)) % p;
}

int main()
{
    ll X = input<int>(), Y = input<int>();

    if ((X + Y) % 3 != 0)
    {
        cout << 0 << endl;
        return 0;
    }
    else
    {
        ll n = (2 * Y - X) / 3;
        ll m = (2 * X - Y) / 3;
        if (n < 0 || m < 0)
        {
            cout << 0 << endl;
            return 0;
        }
        else
        {
            cout << mcomb(n + m, m, MOD) << endl;
        }
        return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;

int main(){
  int N,T,E; cin >> N >> T >> E ;
  vector<int> x(N);
  cinf(N,x);
  for(int i=0;i<N;i++){
    int cnt=0;
    while(cnt <= T+E){
      cnt += x[i];
      if(cnt >= T-E && cnt <= T+E){
        cout << i+1 << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
}



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


using namespace std;


typedef long long LL;
typedef pair<LL,LL> pp;

int main()
{
	int A[101][101];

	int H, W;
	int N;
	cin >> H >> W;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	int cur = 0;
	int row = 0, col = 0;
	int dir = 1;
	while (row < H) {
		if (v[cur] > 0) {
			A[row][col] = 1+cur;
			v[cur]--;
		}
		else {
			cur++;
			A[row][col] = 1+cur;
			v[cur]--;
		}
		col += dir;
		if (row%2 == 0 && col == W) {
			row++;
			col = W-1;
			dir *= -1;
		}
		else if (row%2 == 1 && col == -1) {
			row++;
			col = 0;
			dir *= -1;
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << A[i][j];
			if (j != W-1) cout << " ";
		}
		cout << endl;
	}
	exit(0);
}



Measured memory_bytes: 384
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Stack, Queue, PriorityQueue, Set}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N, K, S = in.next().toInt


  //
  val max = 1e9.toInt

  val hoge =
    if (S == max) 1
    else max

  val ans = new Array[Int](N+1)

  for (i <- 1 to N) {
    if (i <= K) {
      ans(i) = S
    }
    else {
      ans(i) = hoge
    }
  }

  val fuga = ans.drop(1).mkString(" ")
  println(fuga)
}

object Sub {
  def print2DimArray[A](mat: Array[Array[A]]): Unit = {
    mat.foreach(lin => println(lin.deep))
  }
}

class InputReader(stream: InputStream) {
  private[this] val reader = new BufferedReader(new InputStreamReader(stream))
  private[this] var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 41060
#!/usr/bin/env ruby

n = gets.chomp.to_i
a = gets.chomp.split(/ /).map(&:to_i)
b = []
a.each_with_index do |num, idx|
  b[idx] = num - (idx + 1)
end
b.sort!
s = b.size
i = b[(n / 2)]

nums = 0
b.each do |n|
  nums += (n - i).abs
end
puts nums


Measured memory_bytes: 21576
hw = Hash.new(0)
cost = []
width = 10
result = 0
onecost = []
s = gets.chomp.split(" ")
hi = s[0].to_i
wi = s[1].to_i
width.times do |i|
  cost[i] = []
  s = gets.chomp.split(" ")
  width.times do |ii|
    cost[i][ii] = s[ii].to_i
  end
end
#探索
def getmin(arr,alist)
  rsco = 2000
  ridx = alist[0]
  alist.each do |idx|
    if(rsco > arr[idx])
      rsco = arr[idx]
      ridx = idx
    end
  end
  return ridx,rsco
end

width.times do |i|
  d = []
  width.times do |ij|
    d[ij] = cost[i][ij]
  end
  alist = [i]
  olist = []
  unfinish = true
  while(unfinish)
    v,s = getmin(d,alist)
    olist.push(v)
    if (v == 1)
      onecost[i] = s
      unfinish = false
    else
      width.times do |w|
        next if olist.include?(w)
        alist.push(w) unless alist.include?(w)
        if(d[w] > (d[v] + cost[v][w]))
          d[w] = d[v] + cost[v][w]
        end
      end
    end
    alist.delete(v)
  end
end
hi.times do |h|
  s = gets.chomp.split(" ")
  wi.times do |w|
    num = s[w].to_i
    next if (num == -1 || num ==1)
    result += onecost[num]
  end
end
print result,"\n"


Measured memory_bytes: 2300
package main

import (
	"fmt"
)

func main() {

	var A, B int
	fmt.Scanf("%d %d", &A, &B)

	var outlet int = 1
	var count int = 0
	for {
		if B > outlet {
			outlet += A - 1
			count++
		} else {
			break
		}
	}

	fmt.Println(count)
}


Measured memory_bytes: 1832
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
#define N 100007
#define INF 1000000007
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll fceil(ll a, ll b) { return (a % b == 0 ? a / b : a / b + 1); }
int main()
{
   ll n;
   cin >> n;
   vector<int> a(n + 1);
   vector<ll> s(n + 1);
   ll cmb = 0;
   FOR(i, 1, n + 1)
   {
      cin >> a[i];
      s[a[i]]++;
   }
   FOR(i, 1, n + 1)
   {
      cmb += s[i] * (s[i] - 1LL) / 2LL;
   }
   FOR(i, 1, n + 1)
   {
      // cout << (acc - s[a[i]] + 1LL) << endl;
      printf("%lld\n", cmb - s[a[i]] + 1LL);
   }
   return 0;
}


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

template <class T, class U>
inline bool chmax(T& t, const U& f) { return t < f ? t = f, true : false; }

template <class T>
inline T sqr(T&& x) { return x * x; }

int solve(int n, vector<int>& c, vector<int>& on) {
    vector<char> mem(1 << n, -1);
    function<char(int)> dfs = [&](int table) {
        char& t = mem[table];
        if (t != -1) return t;
        char T = __builtin_popcount(table);
        t = 0;
        for (int S = table; S > 0; S &= (S - 1)) {
            int i = __builtin_ctz(S);
            if (on[i]) continue;
            for (int U = table & ~((1 << (i + 1)) - 1); U > 0; U &= (U - 1)) {
                int j = __builtin_ctz(U);
                if (on[j] or c[i] != c[j]) continue;
                vector<int> nxt = on;
                rep(k, n) nxt[k] &= ~(1 << i | 1 << j);
                on.swap(nxt);
                chmax(t, dfs(table ^ 1 << i ^ 1 << j) + 2);
                on.swap(nxt);
                if (T == t) return t;
            }
        }
        return t;
    };
    return dfs((1 << n) - 1);
}

int main() {
    for (int n; cin >> n, n;) {
        vector<int> x(n), y(n), r(n), c(n), on(n);
        rep(i, n) {
            cin >> x[i] >> y[i] >> r[i] >> c[i];
            rep(j, i) {
                if (sqr(x[i] - x[j]) + sqr(y[i] - y[j]) >= sqr(r[i] + r[j])) continue;
                rep(k, j) if (on[i] >> k & 1 and on[j] >> k & 1) on[i] ^= 1 << k;
                on[i] |= 1 << j;
            }
        }
        cout << solve(n, c, on) << endl;
    }
}

Measured memory_bytes: 19540
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(void) {
    int a, b, c;
    int result = 0;
    cin >> a >> b >> c;
    if (a >= b && a >= c) {
        result = a * 10 + b + c;
    } else if (b >= c && b >= a) {
        result = b * 10 + c + a;
    } else {
        result = c * 10 + a + b;
    }
    cout << result << endl;
    return 0;
}


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


struct abhi
{

    long long int a,b;



};

bool func(abhi x,abhi y)
{
    return x.a<y.a;

}

int main()
{

long long int i,n;
abhi arr[200009];

cin>>n;

for(i=0;i<n;i++)
{
 cin>>arr[i].a;
 arr[i].b=i+1;

}

sort(arr,arr+n,func);

for(i=0;i<n;i++)
cout<<arr[i].b<<endl;
return 0;
}




Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int sums[N],sumt[N];
int ls,lt,q,t1,t2,t3,t4;
int main(){
	scanf("%s%s",s,t);
	ls=strlen(s),lt=strlen(t);
	for(int i=1;i<=ls;i++){
		sums[i]=s[i-1]=='A'?1:2;
		sums[i]+=sums[i-1];
	}
	for(int i=1;i<=lt;i++){
		sumt[i]=t[i-1]=='A'?1:2;
		sumt[i]+=sumt[i-1];
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
		if((sums[t2]-sums[t1-1])%3==(sumt[t4]-sumt[t3-1])%3) puts("YES\n");
		else puts("NO\n");
	}
	return 0;
}

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

const int N = 1e5+1;
int n,m;
vector<vector<int>> adj(N);
vector<int> dist(N);
vector<int> nbPere(N);
deque<int> q;

void bfs(){
	for (int start:q){
		dist[start] = 0;
	}
	while (!q.empty()){
		int f = q.front();
		q.pop_front();
		for (int i:adj[f]){
			dist[i] = max(dist[i],dist[f]+1);
			nbPere[i]--;
			if (nbPere[i] == 0) q.emplace_back(i);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i){
		int a,b;
		cin >> a >> b;
		a--; b--;
		adj[a].emplace_back(b);
		nbPere[b]++;
	}
	for (int i=0; i<n; ++i){
		if (nbPere[i] == 0) q.emplace_back(i);
	}
	bfs();
	cout << *max_element(dist.begin(),dist.end());
	return 0;
}



Measured memory_bytes: 9548
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>

using namespace std;

constexpr int INF = 1 << 29;

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

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

    int n;
    cin >> n;

    vector< vector<int> > g1(n);
    vector< vector<int> > g2(n);

    for(int i = 0 ; i < n ; ++i){
        int d;
        cin >> d;
        g1[i].emplace_back(min(i + d / 10, n - 1));
        g2[i].emplace_back(max(i - d / 10, 0));
        if(i > 0){
            g1[i].emplace_back(i - 1);
            g2[i - 1].emplace_back(i);
        }
    }

    vector<int> cost(n, INF);
    cost[0] = 0;
    queue< pair<int, int> > que;
    que.push({0, 0});

    while(!que.empty()){
        auto now = que.front();
        que.pop();

        if(cost[now.first] < now.second){
            continue;
        }

        for(auto to : g1[now.first]){
            if(chmin(cost[to], now.second + 1)){
                que.push({to, now.second + 1});
            }
        }
    }

    fill(cost.begin(), cost.end() - 1, INF);
    que.push({n - 1, cost[n - 1]});

    while(!que.empty()){
        auto now = que.front();
        que.pop();

        if(cost[now.first] < now.second){
            continue;
        }

        for(auto to : g2[now.first]){
            if(chmin(cost[to], now.second + 1)){
                que.push({to, now.second + 1});
            }
        }
    }

    if(cost[0] < INF){
        cout << "yes" << endl;
    }else{
        cout << "no" << endl;
    }

    return 0;
}


Measured memory_bytes: 37088
from collections import deque

S = []
for i in range(3):
    s = deque()
    for i in input():
        s.append(i)
    S.append(s)
now = 0
while True:
    if now == 0 and not S[0]:
        print("A")
        exit()
    elif now == 1 and not S[1]:
        print("B")
        exit()
    elif now == 2 and not S[2]:
        print("C")
        exit()
    card = S[now].popleft()
    if card == "a":
        now = 0
    elif card == "b":
        now = 1
    elif card == "c":
        now = 2


Measured memory_bytes: 3316
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  @scala.annotation.tailrec
  def loop(a: Int, b: Int, count: Int, acc: Int): Int = {
    if (count == 0) acc
    else if (a >= b) loop(a - 1, b, count - 1, acc + a)
    else  loop(a, b - 1, count - 1, acc + b)
  }
  println(loop(sc.nextInt(), sc.nextInt(), 2, 0))
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<ll> p(a), q(b), r(c);
    rep(i, a) cin >> p[i];
    rep(i, b) cin >> q[i];
    rep(i, c) cin >> r[i];
    
    sort(p.begin(), p.end(), greater<int>());
    sort(q.begin(), q.end(), greater<int>());
    sort(r.begin(), r.end(), greater<int>());
    
    vector<ll> s;
    rep(i, x) s.emplace_back(p[i]);
    rep(i, y) s.emplace_back(q[i]);
    rep(i, c) s.emplace_back(r[i]);
    sort(s.begin(), s.end(), greater<int>());
    
    ll ans = 0;
    rep(i, x+y){
        ans += s[i];
    }
    cout << ans << endl;
    return 0;
}




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

using namespace std;

#define ll long long 
#define Fastest ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

int main()
{
	Fastest
	
    char ch;
    
    cin >> ch;
    
    if(ch == 'A') cout << "T";
    else if(ch == 'T') cout << "A";
    else if(ch == 'C') cout << "G";
    else if(ch == 'G') cout << "C";
	
	cout << endl;
	
	return 0;
}


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

double get_radian(double x1, double y1, double x2, double y2) {
	if(fabs(x1-x2) < 0.00000001f) {
		if(y1 >= y2) {
			return 3 * M_PI / 2;
		}
		return M_PI / 2;
	} else if(fabs(y1-y2) < 0.00000001f) {
		if(x1 >= x2) {
			return M_PI;
		}
		return 0.0;
	}
	
	if(x2 >= x1) {
		if(y2 >= y1) {
			return atan((y2-y1)/(x2-x1));
		}
		return 2 * M_PI + atan((y2-y1)/(x2-x1));
	} else {
		if(y2 >= y1) {
			return M_PI - atan((y2-y1)/(x1-x2));
		}
		return M_PI + atan((y2-y1)/(x2-x1));
	}
}

int main(void) {
	double base_x, base_y, x, y;
	double base_rad, target_rad;
	double rad;
	double r;
	int i, n;
	
	scanf("%lf %lf %lf %lf\n", &base_x, &base_y, &x, &y);
	scanf("%d\n", &n);
	base_rad = get_radian(base_x, base_y, x, y);
	
	for(i=0;i<n;i++) {
		scanf("%lf %lf\n", &x, &y);
		target_rad = get_radian(base_x, base_y, x, y);
		r = sqrt((x-base_x)*(x-base_x)+(y-base_y)*(y-base_y));
		
		// 後はどっち側に振れるか
		rad = fmod(2*M_PI+target_rad-base_rad, 2*M_PI);

		x = x + (2*r*sin(rad)) * cos(fmod(base_rad+3*M_PI/2, 2*M_PI));
		y = y + (2*r*sin(rad)) * sin(fmod(base_rad+3*M_PI/2, 2*M_PI));
		
		if(fabs(x) < 0.00000001f) x = 0.0f;
		if(fabs(y) < 0.00000001f) y = 0.0f;
		
		printf("%.10lf %.10lf\n", x, y);
	}
	
	return 0;
}

Measured memory_bytes: 780
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

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

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

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

int main() {
    ll a, b, n;
    cin >> a >> b >> n;

    cout << a * min(b-1, n) / b << endl;

    return 0;
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;



int r;
int main () {
	cin >> r;
	cout << setprecision(9) << 2 * acos(-1) * r << endl;
}


Measured memory_bytes: 3788
a,b,c,d,e,k=[int(input()) for i in range(6)]
if b-a>k or c-a>k or d-a>k or e-a>k or c-b>k or d-b>k or e-b>k or d-c>k or e-c>k or e-d>k:
  print(":(")
else:
  print("Yay!")

Measured memory_bytes: 8892
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int a = scanner.nextInt();

        if (x < a) {
            System.out.println(0);
        } else {
            System.out.println(10);
        }
    }
}

Measured memory_bytes: 25172
#include <iostream>
#include <algorithm>
#include <string>
#define int long long
using namespace std;
signed main() {
	int a, b, k; cin >> a >> b >> k;
	for (int i = 0; i < k; i++) {
		if (i % 2) {
			b -= b % 2;
			a += b / 2;
			b /= 2;
		}
		else {
			a -= a % 2;
			b += a / 2;
			a /= 2;
		}
	}
	cout << a << ' ' << b << endl;
}

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

using namespace std;
#define int long long
const int INF = 200000000007;


  
signed main(){
    int n, m, r;
    cin>>n>>m>>r;
    int k[r];
    for(int i=0;i<r;i++)cin>>k[i];
    vector<pair<int,int>> q[n];
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        q[a-1].push_back(make_pair(b-1,c));
        q[b-1].push_back(make_pair(a-1,c));
    }
    priority_queue<pair<int,int>> que;
    int d[n],v;
    pair<int,int> p,w;
    int d2[r+1][r+1];
    for(int i=0;i<r+1;i++){
        d2[0][i]=0;
        d2[i][0]=0;
    }
 
    for(int i=0;i<r;i++){
        fill(d,d+n,INF);
        d[k[i]-1]=0;
        que.push(make_pair(0,k[i]-1));
        while(!que.empty()){
            p=que.top();que.pop();
            v=p.second;
            if(d[v]<p.first)continue;
            for(int j=0;j<q[v].size();j++){
                w=q[v][j];
                if(d[w.first]>d[v]+w.second){
                    d[w.first]=d[v]+w.second;
                    que.push(make_pair(d[w.first],w.first));
                }
            }
        }
        for(int j=0;j<r;j++){
            d2[i+1][j+1]=d[k[j]-1];
          //  cerr<<d2[i+1][j+1]<<' ';
        }
       // cerr<<endl;
    }

    int dp[(1<<(r+1))][r+1];
    for(int i=0;i<(1<<(r+1));i++)fill(dp[i],dp[i]+r+1,INF);
    dp[(1<<(r+1))-1][0]=0;
   
    for(int i=(1<<(r+1))-2;i>=0;i--){
        for(int j=0;j<r+1;j++){
            for(int l=0;l<r+1;l++){
                if(!(i >>l & 1)) {
                    dp[i][j]=min(dp[i][j],dp[i | (1<<l)][l]+d2[j][l]);
                    
                }
               
            }
        }
    }
   

    cout<<dp[0][0];

   
    
    
    
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl
#define dump(x)  cerr << #x << " => " << (x) << endl
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w)
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double EPS = 1e-10;
constexpr long MOD = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL,LL> pr;
typedef vector<bool> VB;
typedef vector<pr> VP;
typedef priority_queue<pr,vector<pr>,greater<pr>> pq;

void insertionSort(vector<int> &arr) {
    int n = arr.size();
    REP(i,n) {
        if (i != (n-1)) cout << arr[i] << " ";
        else cout << arr[i] << endl;
    }
    FOR(i,1,n) {
        int v = arr[i];
        int j = i - 1;
        // 後ろから決める.
        while (j >= 0 && arr[j] > v) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = v;
        REP(i,n) {
            if (i != (n-1)) cout << arr[i] << " ";
            else cout << arr[i] << endl;
        }
    }
}

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    insertionSort(a);
}




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

const int MAXN = 200010;
const int MAXE = MAXN * 20;
const int INF = 0x3f3f3f3f;
int head[MAXN], nxt[MAXE], to[MAXE], val[MAXE], tot = 1;
void addedge(int b, int e, int v) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e; val[tot] = v;
	nxt[++tot] = head[e]; to[head[e] = tot] = b; val[tot] = 0;
}
void addedge(int b, int e, int v, int v2) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e; val[tot] = v;
	nxt[++tot] = head[e]; to[head[e] = tot] = b; val[tot] = v2;
}
int dis[MAXN], S, T, idx;
std::queue<int> q;
bool bfs() {
	memset(dis, 0, idx + 1 << 2);
	q.push(S); dis[S] = 1;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (int i = head[t]; i; i = nxt[i])
			if (val[i] && !dis[to[i]])
				dis[to[i]] = dis[t] + 1, q.push(to[i]);
	}
//	for (int i = S; i <= T; ++i) std::cout << dis[i] << ' ';
//	std::cout << std::endl;
	return dis[T] > 0;
}
int dinic(int u, int minv) {
	if (u == T || !minv) return minv;
	int res = 0, t;
	for (int & i = head[u]; i; i = nxt[i])
		if (val[i] && dis[to[i]] == dis[u] + 1 && (t = dinic(to[i], std::min(minv, val[i])))) {
			val[i] -= t;
			val[i ^ 1] += t;
			res += t;
			minv -= t;
			if (!minv) break;
		}
	if (!res) dis[u] = -1;
	return res;
}
int maxflow() {
	int res = 0;
	static int th[MAXN];
	memcpy(th, head, idx + 1 << 2);
	while (bfs()) {
		res += dinic(S, INF);
		memcpy(head, th, idx + 1 << 2);
	}
	return res;
}
int n, P[MAXN], Q[MAXN];
int vis[MAXN];
struct EX {
	int a, b, c, d, e, f, g;
} ds[1 << 4];
int A[MAXN], B[MAXN];
int main() {
	for (int i = 0; i != (1 << 4); ++i) {
		static int g[4];
		g[0] = i & 1, g[1] = i >> 1 & 1;
		g[2] = i >> 2 & 1, g[3] = i >> 3 & 1;
		int t = g[0] + g[1] + g[2] + g[3];
		g[0] = t - g[0];
		g[1] = t - g[1];
		g[2] = t - g[2];
		g[3] = t - g[3];
		bool can = false;
		for (int a = 0; a <= g[0]; ++a) {
			int c = g[0] - a;
			for (int b = 0; b <= g[3]; ++b) {
				int d = g[3] - b;
				int e = g[2] - a - d;
				int f = g[1] - b - c;
				if (e >= 0 && f >= 0) {
					can = true;
					ds[i] = (EX) {a, b, c, d, e, f, t};
					break;
				}
			}
		}
		if (!can) ds[i].a = -1;
		// if (!can) std::cerr << "CANNOT " << i << std::endl;
	}
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	for (int i = 0; i < n; ++i) std::cin >> P[i];
	for (int i = 0; i < n; ++i) std::cin >> Q[i];
	S = 0, T = idx = 1;
	for (int i = 0; i < n; ++i) if (!vis[i]) {
		int now = i; ++idx;
		while (!vis[i] || now != i) {
			A[now] = idx;
			vis[now] = true, now = P[now];
		}
	}
	memset(vis, 0, n + 1 << 2);
	for (int i = 0; i < n; ++i) if (!vis[i]) {
		int now = i; ++idx;
		while (!vis[i] || now != i) {
			B[now] = idx;
			vis[now] = true, now = Q[now];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		static int f[4];
		f[0] = i != Q[i];
		f[1] = P[i] != Q[i];
		f[2] = i != i;
		f[3] = P[i] != i;
		EX t = ds[f[0] | f[1] << 1 | f[2] << 2 | f[3] << 3];
		if (t.a) addedge(S, A[i], t.a);
		if (t.b) addedge(A[i], T, t.b);
		if (t.c) addedge(S, B[i], t.c);
		if (t.d) addedge(B[i], T, t.d);
		if (t.e || t.f) addedge(B[i], A[i], t.e, t.f);
		ans += t.g;
	}
	ans -= maxflow();
	std::cout << ans << std::endl;
	return 0;
}


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

ll solve(ll num){
    switch(num%4){
        case 0: return num;
        case 1: return 1;
        case 2: return num+1;
        case 3: return 0;
    }
}

int main(){
    ll a, b; cin >> a >> b;
    cout << (solve(a-1) ^ solve(b)) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
#include <random>
#include <map>
#include <math.h>
#pragma warning(disable : 4996)


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

	printf("%d", n * 800 - (n / 15) * 200);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
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; }
const int64_t INF = 1LL << 60;

int main() {
	string s;
  cin>>s;
  int n=s.size();
  cout<<s.substr(0,n-8)<<endl;
  return 0;
}


Measured memory_bytes: 3588
/**
*    created: 13.06.2020 21:01:51
**/
#include <bits/stdc++.h>
#define int long long
#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++)
using namespace std;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;
    if (w > v) {
        cout << "NO" << endl;
        return 0;
    }
    
    if (abs(b-a) <= (v-w) * t) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

int n;
int x[1003], y[1003];

double dist(int i, int j) {
  double dx = x[i] - x[j];
  double dy = y[i] - y[j];
  return pow(dx * dx + dy * dy, 0.5);
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
  vector<int> v(n);
  double d = 0;
  for (int i = 0; i < n; ++i) v[i] = i;
  do {
    for (int i = 0; i < n - 1; ++i) d += dist(v[i], v[i + 1]);
  } while (next_permutation(v.begin(), v.end()));
  long long f = 1;
  for (int i = 2; i <= n; ++i) f *= i;
  cout << setprecision(19) << d / f << endl;
  return 0;
}


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

using namespace std;

int main(void)
{
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> D(M);
    vector<bool> is_rslvd(M, false);
    for (auto &i : D) cin >> i.first >> i.second;
    sort(D.begin(), D.end(), [](pair<int, int> p, pair<int, int> q){ return ((p.second == q.second) ? (p.first < q.first) : (p.second < q.second)); });
    int i = 0, ans = 0;
    while (i < M)
    {
        for (int j = i; j < M; j++)
        {
            if (D[j].first < D[i].second) is_rslvd[j] = true;
        }
        ans++;
        while (i < M && is_rslvd[i]) i++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define maxn 100000

int main(){
	Fio;
	int t=1;
	//cin >> t;
	while(t--){
		int n ,k;
		cin >> n >> k;
		int h[n], costs[n] = {0};

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

		costs[0] = 0;
		costs[1] = abs(h[1] - h[0]);

		for (int i = 2; i < n; ++i)
		{
			int mini = INT_MAX;
			for(int j = 1; j <= k; ++j)
			{
				if(i-j < 0)
					break;
				mini = min(mini, costs[i-j] + abs(h[i] - h[i-j]));
			}

			costs[i] = mini;
			//mini = min(costs[i-1] + abs(h[i] - h[i-1]), costs[i-2] + abs(h[i] - h[i-2]));
		}

		cout << costs[n-1];
	}

	return 0;
}

Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var t = make([]int, n)
	var sum = 0
	for i := 0; i < n; i++ {
		fmt.Scan(&t[i])
		sum += t[i]
	}
	var m int
	fmt.Scan(&m)
	var p, x = make([]int, m), make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scan(&p[i], &x[i])
		fmt.Println(sum - t[p[i]-1] + x[i])
	}
}


Measured memory_bytes: 512
import java.io.*;

class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        char charArray[] = str.toCharArray();
        
        for(int i=0; i<charArray.length; i++){
            if(Character.isUpperCase(charArray[i])){
                charArray[i] = Character.toLowerCase(charArray[i]);
            }else{
                charArray[i] = Character.toUpperCase(charArray[i]);
            }
        }
        System.out.println(charArray);
    }
}

Measured memory_bytes: 24236
N = int(input())
A = input().split(" ")
A = [int(i) for i in A]
list = [min(A)]
A = sorted(A)
iii = 0
while True:
    iii += 1
    if A[N-1] % A[N-2] != 0:
        A[N-1] = A[N-1] % A[N-2]
    elif N >= 3 and A[N-1] % A[N-3] != 0:
        A[N-1] = A[N-1] % A[N-3]
    elif N >= 4 and A[N-1] % A[N-4] != 0:
        A[N-1] = A[N-1] % A[N-4]
    elif N >= 5 and A[N-1] % A[N-5] != 0:
        A[N-1] = A[N-1] % A[N-5]
    elif N >= 6 and A[N-1] % A[N-6] != 0:
        A[N-1] = A[N-1] % A[N-6]
    elif N >= 7 and A[N-1] % A[N-7] != 0:
        A[N-1] = A[N-1] % A[N-7]
    elif N >= 8 and A[N-1] % A[N-8] != 0:
        A[N-1] = A[N-1] % A[N-8]
    elif N >= 9 and A[N-1] % A[N-9] != 0:
        A[N-1] = A[N-1] % A[N-9]
    elif N >= 10 and A[N-1] % A[N-10] != 0:
        A[N-1] = A[N-1] % A[N-10]
    elif N >= 11 and A[N-1] % A[N-11] != 0:
        A[N-1] = A[N-1] % A[N-11]
    elif N >= 12 and A[N-1] % A[N-12] != 0:
        A[N-1] = A[N-1] % A[N-12]
    elif N >= 13 and A[N-1] % A[N-13] != 0:
        A[N-1] = A[N-1] % A[N-13]
    elif N >= 14 and A[N-1] % A[N-14] != 0:
        A[N-1] = A[N-1] % A[N-14]
    elif N >= 15 and A[N-1] % A[N-15] != 0:
        A[N-1] = A[N-1] % A[N-15]
    elif N >= 16 and A[N-1] % A[N-16] != 0:
        A[N-1] = A[N-1] % A[N-16]
    elif N >= 17 and A[N-1] % A[N-17] != 0:
        A[N-1] = A[N-1] % A[N-17]
    elif N >= 18 and A[N-1] % A[N-18] != 0:
        A[N-1] = A[N-1] % A[N-18]
    elif N >= 19 and A[N-1] % A[N-19] != 0:
        A[N-1] = A[N-1] % A[N-19]
    elif N >= 20 and A[N-1] % A[N-20] != 0:
        A[N-1] = A[N-1] % A[N-20]
    elif N >= 21 and A[N-1] % A[N-21] != 0:
        A[N-1] = A[N-1] % A[N-21]
    elif N >= 22 and A[N-1] % A[N-22] != 0:
        A[N-1] = A[N-1] % A[N-22]
    elif N >= 23 and A[N-1] % A[N-23] != 0:
        A[N-1] = A[N-1] % A[N-23]
    elif N >= 24 and A[N-1] % A[N-24] != 0:
        A[N-1] = A[N-1] % A[N-24]
    elif N >= 25 and A[N-1] % A[N-25] != 0:
        A[N-1] = A[N-1] % A[N-25]
    elif N >= 26 and A[N-1] % A[N-26] != 0:
        A[N-1] = A[N-1] % A[N-26]
    elif N >= 27 and A[N-1] % A[N-27] != 0:
        A[N-1] = A[N-1] % A[N-27]
    elif N >= 28 and A[N-1] % A[N-28] != 0:
        A[N-1] = A[N-1] % A[N-28]
    elif N >= 29 and A[N-1] % A[N-29] != 0:
        A[N-1] = A[N-1] % A[N-25]
    elif N >= 30 and A[N-1] % A[N-30] != 0:
        A[N-1] = A[N-1] % A[N-30]
    elif N >= 31 and A[N-1] % A[N-31] != 0:
        A[N-1] = A[N-1] % A[N-31]
    elif N >= 32 and A[N-1] % A[N-32] != 0:
        A[N-1] = A[N-1] % A[N-32]
    elif N >= 33 and A[N-1] % A[N-33] != 0:
        A[N-1] = A[N-1] % A[N-33]
    elif N >= 34 and A[N-1] % A[N-34] != 0:
        A[N-1] = A[N-1] % A[N-34]
    elif N >= 35 and A[N-1] % A[N-35] != 0:
        A[N-1] = A[N-1] % A[N-35]
    elif N >= 36 and A[N-1] % A[N-36] != 0:
        A[N-1] = A[N-1] % A[N-36]
    A = sorted(A)
    list.append(min(A))
    if iii > 128:
        break       
#print(list)
for i in range(N-1):
    if A[i+1]-A[i] > 0:
        list.append(A[i+1]-A[i])
#print(list)
print(min(list))

Measured memory_bytes: 14348
N=int(input())
A=list(map(int,input().split()))
S=sum(A)-A[0]
T=A[0]
ans=abs(S-T)
for i in range(1,N-1):
    S-=A[i]
    T+=A[i]
    ans=min(ans,abs(S-T))
print(ans)


Measured memory_bytes: 76880
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
const ll mod = 1e18 + 7;
const int M = 2e6 + 5;
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll base,ll pow){ll ans = 1;
   if(pow < 0) return 0;
   while(pow!=0){if(pow&1==1){ans = ans*base;ans = ans%mod;}
   base *= base;base%=mod;pow/=2;}return ans;}
ll inv(ll x){return expo(x,mod-2);}
ll mult_mod(ll a , ll b){a = a%mod; b = b%mod;ll c = (a * b)%mod;return c;}
ll add_mod(ll a , ll b){a = (a + mod)%mod;b = (b + mod)%mod;ll c = (a + b)%mod;return c;}
ll fac[(int)(2e6 + 7)] , inv_fac[(int)(2e6 + 7)];
void precomp_factorial(){fac[0] = 1;for(ll i = 1 ; i <= M ; i++) fac[i] = mult_mod(i , fac[i - 1]);
    inv_fac[M] = inv(fac[M]);for(ll i = M - 1 ; i >= 0 ; i--) inv_fac[i] = mult_mod(i + 1 , inv_fac[i + 1]);}
ll nCk(ll n , ll k){ll ans = fac[n];ans = mult_mod(ans , inv_fac[n - k]);ans = mult_mod(ans , inv_fac[k]);return ans;}
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};

int main()
{
    int n;
    cin >> n;
    vector <ll> vec(n);
    map <ll,ll> mp;
    for(int i = 0; i < n; i++){
        cin >> vec[i];
        mp[vec[i]]++;
    }
    ll cnt = n;
    ll prev = 0;
    ll ans = 0;
    for(auto x:mp){
        ll cnt1 = (x.first-prev)%2;
        ll val = cnt*cnt1;
        //cout << val << " " << endl;
        ans = ans^val;
        cnt -= x.second;
        prev = x.first;
    }
    if(ans) cout << "first";
    else cout << "second";
    return 0;
}


Measured memory_bytes: 7296
N,M=map(int,input().split())
A=list(map(int,input().split()))
weight=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0
for i in range(N+1):
    for a in A:
        if i+weight[a]<N+1:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[N])

Measured memory_bytes: 50908
#!/bin/ruby
prime=[true]*1000001
prime[0..1]=[false]*2
(2..1000000).each do |i|
  if prime[i] then
    j=i*2
    while j<=1000000
      prime[j]=false
      j+=i
    end
  end
end
g=Array.new(1001){Array.new(1001,1e9)}
x,y=500,500
dy=[-1,0,1,0]
dx=[0,1,0,-1]
d=1
(1..1000000).each do |i|
  g[y][x]=i
  x+=dx[d]
  y+=dy[d]
  nx=x+dx[(d+3)%4]
  ny=y+dy[(d+3)%4]
  d=(d+3)%4 if g[ny][nx]>i
end

loop do
  m,n=gets.split.map(&:to_i)
  break if m==0&&n==0
  dp=Array.new(1001){Array.new(1001,-1e99)}
  nc,lc=0,0
  (0..1000).each do |i|
    (0..1000).each do |j|
      next if g[i][j]>m
      dp[i][j]=0 if g[i][j]==n
      if prime[g[i][j]] then
        dp[i][j]+=1
        nc,lc=dp[i][j],g[i][j] if dp[i][j]>nc||dp[i][j]==nc&&lc<g[i][j]
      end
      (-1..1).each do |k|
        ni=i+1
        nj=j+k
        next if ni>1000||nj<0||1000<nj||g[i][j]>m
        dp[ni][nj]=dp[i][j] if dp[ni][nj]<dp[i][j]
      end
    end
  end
  puts "%d %d"%[nc,lc]
end

Measured memory_bytes: 42312