akhauriyash/Code-Regression huggingface dataset:
N,M = `dd`.split.map &:to_i
pairs = []
O = (M+1)/2
(1..O).each{ |i| pairs << [i,2*O+1-i] }
(1..M/2).each{ |i| pairs << [2*O+i, 2*M+2-i] }
pairs.each{ |a,b| puts [a,b] * " " }


Measured memory_bytes: 20232
a = int(input())
b = int(input())
ans = 0

if a == 1:
  if b == 2:
    ans = 3
  else:
    ans = 2
elif a == 2:
  if b == 1:
    ans = 3
  else:
    ans = 1
elif a == 3:
  if b == 1:
    ans = 2
  else:
    ans = 1
print(ans)

Measured memory_bytes: 2940
n,x = map(int,input().split())
a = [1] # パン+パティ
p = [1] # パティ
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def f(n,x):
    #print(n,x)
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1
    elif x <= 1 + a[n-1]:
        return f(n-1, x-1)
    else:
        return p[n-1] + 1 + f(n-1, x-2-a[n-1])
print(f(n,x))

Measured memory_bytes: 38384
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int dp[5010][5010] = {};

int main() {
    int n;

    char s[5010];

    scanf("%d", &n);
    scanf("%s", s);

    int res = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (s[i] == s[j]) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
            }

            if (abs(i - j) >= dp[i][j]) {
                res = max(dp[i][j], res);
            }
        }
    }

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

    return 0;
}

Measured memory_bytes: 98048
#coding utf-8
N,M=map(int,input().split())
L=[0 for i in range(M)]
R=[0 for i in range(M)]
for i in range(M):
  L[i],R[i]=map(int,input().split())

l=max(L)
r=min(R)
ans=r-l+1
if ans<0:
  print(0)
else:
  print(ans)

Measured memory_bytes: 11048
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::input;
use proconio::marker::{Bytes, Chars};
use std::collections::*;

fn main() {
    input! {
        n:usize,
        abc:[(usize,usize,i64);n-1],
        q:usize,
        k:usize,
        xy:[(usize,usize);q],
    }
    let mut g = Graph::new(n);
    for e in abc {
        g.add_undirectional_edge(e.0 - 1, e.1 - 1, e.2);
    }
    let dist = bfs(&g, k - 1);
    let xy = xy.iter().map(|&(x, y)| (x - 1, y - 1)).collect::<Vec<_>>();
    for (x, y) in xy {
        let ans = dist[x] + dist[y];
        println!("{}", ans);
    }
}

fn bfs(g: &Graph, k: usize) -> Vec<i64> {
    let mut res = vec![std::i64::MAX; g.len()];
    res[k] = 0;
    let mut b = VecDeque::new();
    b.push_back(k);
    while let Some(now) = b.pop_front() {
        for next in g[now].iter() {
            if res[next.to] != std::i64::MAX {
                continue;
            }
            res[next.to] = res[now] + next.cost;
            b.push_back(next.to);
        }
    }
    return res;
}

#[derive(Debug, Copy, Clone)]
pub struct Edge {
    pub to: usize,
    pub cost: i64,
}
impl Edge {
    pub fn new(to: usize, cost: i64) -> Edge {
        Edge { to: to, cost: cost }
    }
}
pub struct Graph {
    adjacency: Vec<Vec<Edge>>,
}
impl Graph {
    pub fn new(size: usize) -> Self {
        Graph {
            adjacency: vec![vec![]; size],
        }
    }
    pub fn len(&self) -> usize {
        self.adjacency.len()
    }
    pub fn add_directional_edge(&mut self, from: usize, to: usize, cost: i64) {
        self.adjacency[from].push(Edge::new(to, cost));
    }
    pub fn add_undirectional_edge(&mut self, from: usize, to: usize, cost: i64) {
        self.add_directional_edge(from, to, cost);
        self.add_directional_edge(to, from, cost);
    }
}
impl std::ops::Index<usize> for Graph {
    type Output = Vec<Edge>;
    fn index(&self, vertex: usize) -> &Self::Output {
        &self.adjacency[vertex]
    }
}

Measured memory_bytes: 16760
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1e18;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

int f(ll x) {
  int res = 0;
  while (x) {
    res += x%10;
    x /= 10;
  }
  return res;
}

ll dec(ll x) {
  ll k = 1;
  while (x >= 10) {
    x /= 10; k *= 10;
  }
  return x*k-1;
}

int main() {
  ll n;
  scanf("%lld",&n);
  int ans = f(n);
  n = dec(n);
  maxs(ans, f(n));
  cout<<ans<<endl;
  return 0;
}






















Measured memory_bytes: 256
import sys
import os
import math
import bisect

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, Q = il()
    J = [-MAX] + [ii() for _ in range(A)] + [MAX]
    T = [-MAX] + [ii() for _ in range(B)] + [MAX]
    que = [ii() for _ in range(Q)]
    for q in que:
        a = bisect.bisect_left(J, q)
        b = bisect.bisect_left(T, q)
        ret = MAX
        for j in J[a - 1:a + 1]:
            for t in T[b - 1:b + 1]:
                ret = min(ret, abs(j - q) + abs(t - j), abs(t - q) + abs(j - t))
        print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 17680
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <utility>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, forall_a, forall_b) for (int i = (forall_a); i < (forall_b); ++i)
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

typedef pair<int, int> P;

bool ps1(const P &forall_a, const P &forall_b)
{ //first昇順
	return forall_a.first < forall_b.first;
}
bool ps2(const P &forall_a, const P &forall_b)
{ //first降順
	return forall_a.first > forall_b.first;
}
bool ps3(const P &forall_a, const P &forall_b)
{ //second昇順
	return forall_a.second < forall_b.second;
}
bool ps4(const P &forall_a, const P &forall_b)
{ //second降順
	return forall_a.second > forall_b.second;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	deque<int> c;
	rep(i, n) cin >> a[i];
	FOR(i, 1, n)
	{
		if (a[i] > a[i - 1])
		{
			c.pb(1);
		}
		else if (a[i] < a[i - 1])
		{
			c.pb(-1);
		}
	}
	int cnt = 0;
	//bool now=true;
	int cs = c.size();
	bool prev = false;
	FOR(i, 1, cs)
	{

		if (c[i] * c[i - 1] == -1)
		{
			if (prev == true)
			{
				prev = false;
			}
			else
			{
				prev = true;
				cnt++;
			}
		}else{
			if(prev){
				prev=false;
			}
		}
		//cout<<cnt<<" ";
	}
	cout << cnt + 1 << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>

using namespace std;
typedef long long ll;

int main() {
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> f(n);
  for (int i = 0; i < n; i++) {
    cin >> f[i];
  }
  vector<int> s(m);
  for (int i = 0; i < m; i++) {
    cin >> s[i];
  }
  sort(f.begin(), f.end());
  sort(s.begin(), s.end());
  
  bool ok = false;
  for (int z = x + 1; z <= y; z++) {
    if (f.back() < z && z <= s.front()) {
      ok = true;
    }
  }
  if (ok) {
    cout << "No War" << endl;
    
  } else {
    cout << "War" << endl;
  }
  return 0;
}


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

t = [-1] * N
for _ in range(M):
    s, c = map(int, input().split())
    s -= 1
    if t[s] != -1 and t[s] != c:
        print(-1)
        exit()
    t[s] = c

if N != 1:
    if t[0] == 0:
        print(-1)
        exit()

    if t[0] == -1:
        t[0] = 1

    for i in range(1, N):
        if t[i] == -1:
            t[i] = 0
else:
    if t[0] == -1:
        t[0] = 0

print(''.join(map(str, t)))

Measured memory_bytes: 9104
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
int main(){
	fast;
	ll h,w,k; cin>>h>>w>>k;
	char arr[h][w];
	for(auto i=0;i<h;++i){
		for(auto j=0;j<w;++j){
			cin>>arr[i][j];
		}
	} 
	ll cnt=0;
	for(auto i=0;i<(1<<h);++i){
		for(auto j=0;j<(1<<w);++j){
			ll black=0;
			for(auto k=0;k<h;++k){
				for(auto l=0;l<w;++l){
					if(((i>>k)&1)==0 && ((j>>l)&1)==0 && arr[k][l]=='#')++black;
				}
			}
			if(black==k)++cnt;
		}
	}
	cout<<cnt<<'\n';
	return 0;
}

Measured memory_bytes: 3556
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
using namespace std;

string toString(int a){
  ostringstream oss;
  oss << a;
  return oss.str();
}

int toInt(string s){
  istringstream iss(s);
  int a;
  iss >> a;
  return a;
}

int main(){
  vector<int> r;
  int t[10010] = {};
  int n, a;
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    scanf("%d", &a);
    r.push_back(a);
    t[a]++;
  }

  int tt[10010];
  for(int i = 0 ; i < 10010 ; i++){
    tt[i] = t[i];
  }
  
  vector<int> v;
  
  for(int i = 1 ; i <= 10000 ; i++){
    while(t[i] > 0){
      v.push_back(i);
      t[i]--;
      if(v.size() == 10) break;
    }
    if(v.size() == 10) break;
  }

  vector<int> v2;
  
  for(int i = 0 ; i < v.size() ; i++){
    for(int j = 0 ; j < v.size() ; j++){
      if(i == j) continue;
      string s1="", s2="", s="";
      s1 = toString(v[i]);
      s2 = toString(v[j]);
      s = s1 + s2;
      int b = toInt(s);
      v2.push_back(b);
    }
  }
  
  sort(v2.begin(), v2.end());
  
  cout << v2[2] << endl;
  return 0;
}

  

Measured memory_bytes: 1400
S = input()
flag = True

if S[0] != 'A':
    flag = False

if S[2:-1].count('C') != 1:
    flag = False

c = 0
for s, s_lower in zip(S, S.lower()):
    if s != s_lower:
        c += 1

if c != 2:
    flag = False

if flag:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

#define x first
#define y second

pair<ll, ll> p[50];
pair<ll, ll> q[2500];

int main()
{
	int N, K;
	ll ans = (ll)4 * (ll)1e18;

	cin >> N >> K;
	rep(i, N) cin >> p[i].x >> p[i].y;

	rep(i, N) rep(j, N) {
		q[i * N + j].x = p[i].x;
		q[i * N + j].y = p[j].y;
	}

	repc(i, 0, N * N - 2) repc(j, i + 1, N * N - 1) {
		int cnt = 0;
		ll xmin = min(q[i].x, q[j].x);
		ll xmax = max(q[i].x, q[j].x);
		ll ymin = min(q[i].y, q[j].y);
		ll ymax = max(q[i].y, q[j].y);

		rep(s, N) {
			if ((xmin <= p[s].x && p[s].x <= xmax) &&
				(ymin <= p[s].y && p[s].y <= ymax)) cnt++;
		}

		if (cnt >= K) ans = min(ans, (xmax - xmin) * (ymax - ymin));
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = []
xy = []

for i in range(n):
    a += [int(input())]
    xy += [[list(map(int,input().split())) for i in range(a[i])]]

honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: #j番目は正直であるとき
            for person_state in xy[j]:
                if (i >> (person_state[0]-1) & 1) != person_state[1]:
                    flag = 1 #矛盾が生じるとflagを立てる
                    break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]

print(max(honest))

Measured memory_bytes: 9324
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var num string
	fmt.Scanf("%s\n", &num)
	fmt.Println(f(num, 0))
}

func f(s string, base uint64) uint64 {
	v := toNum(s)
	for i := 1; i < len(s); i++ {
		v += f(s[i:], toNum(s[:i])+base)
	}
	return v + base
}

func toNum(s string) uint64 {
	if s == "" {
		return 0
	}
	v, _ := strconv.ParseUint(s, 10, 64)
	return v
}


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll c[3][3];
    rep (i, 3) {
        rep (j, 3) {
            cin >> c[i][j];
        }
    }

    ll a[3], b[3];
    rep (i, 3) {
        b[i] = c[0][i];
        a[i] = c[i][0]-b[0];
    }

    bool flag = true;
    rep (i, 3) {
        rep (j, 3) {
            if (a[i]+b[j] != c[i][j]) {
                flag = false;
                break;
            }
        }
    }

    if (flag) {
        Yes;
    } else {
        No;
    }
    return 0;
}

Measured memory_bytes: 256
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if v<=w:
    print('NO')
elif a<b:
    if (a+v*t)>=(b+w*t):
        print('YES')
    else:
        print('NO')
else:
    if (a-v*t)<=(b-w*t):
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 9192
def fib(n):
    if n==1:
        ans=[1]
        return ans

    ans=[1,1]
    cnt=2
    while cnt <n:
        ans.append(ans[-2]+ans[-1])
        cnt+=1
    return ans

N,M=map(int,input().split())

mod=10**9+7

if N==1:
    print(1)
    exit()

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)[-1]
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)[-1]
ans=(ans*c)%mod

print(ans)




Measured memory_bytes: 460020
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			A();
		}

		public static void A()
		{
			Scanner cin = new Scanner();
			int a = cin.Int();
			int b = cin.Int();
			if (a > 12) {
				Console.WriteLine(b);

			} else if (a > 5) {
				Console.WriteLine(b / 2);
			} else {
				Console.WriteLine(0);
			}
		}
	}

	public class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int Int()
		{
			return int.Parse(Next());
		}
		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long Long()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double Double()
		{
			return double.Parse(Next());
		}


		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}


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

#define int long long

const int mod = 1e9+7;


vector< int > dp;
void calc(int i, vector<int> &to_use, int cost,int mask, int group){
    if(i == to_use.size()){
        dp[mask] = max(dp[mask], cost+ dp[group]);
        return;
    }
    calc(i+1, to_use, cost, mask, group);
    calc(i+1, to_use, cost, mask | (1<<(to_use[i])), group | (1<<(to_use[i])));
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector< vector<int> > ve(n+1, vector<int>(n+1));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> ve[i][j];
        }
    }
    dp.resize(1<<n);
    for(int curr = 1; curr < (1<<n); curr++){
        vector<int> v(0);
        vector<int> vi(0);
        for(int i = 0; i < n; i++){
            if(!((1<<i) & curr)){
                v.push_back(i);
            }else vi.push_back(i+1);
        }
        int cost = 0;
        for(int i = 0; i < vi.size(); i++){
            for(int j = i+1; j < vi.size(); j++){
                cost += ve[vi[i]][vi[j]];
            }
        }
        calc(0,v,cost,curr,0);
    }

    cout << dp[(1<<n)-1] << endl;
}


Measured memory_bytes: 768
#include <iostream>

using namespace std;

int A, B;
int ans;

int main()
{
    cin >> A >> B;

    if(B == 1)
    {
        cout << 0 << '\n';
        return 0;
    }

    for(int i = 1; ; i++)
        if(B <= i * A - (i - 1))
        {
            ans = i;
            break;
        }

    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

char S[55][55];

int main() {
  int N, M, i, j, k, c, cnt, row;
  scanf("%d%d", &N, &M);
  for (i = 0; i < N; i++) {
    scanf("%s", S[i]);
  }
  int ans = 999999;
  for (i = 1; i <= N-2; i++) {
    for (j = 1; i+j <= N-1; j++) {
      cnt = 0;
      row = 0;
      for (k = 0; k < i; k++) {
        for (c = 0; c < M; c++) {
          if (S[row][c] != 'W') cnt++;
        }
        row++;
      }
      for (k = 0; k < j; k++) {
        for (c = 0; c < M; c++) {
          if (S[row][c] != 'B') cnt++;
        }
        row++;
      }
      for (k = 0; k < N-i-j; k++) {
        for (c = 0; c < M; c++) {
          if (S[row][c] != 'R') cnt++;
        }
        row++;
      }
      if (cnt < ans) ans = cnt;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2764
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll A[100000];
int n, a, b;

bool fil(ll z) {
    ll r = z * b;
    ll c = a - b;
    for(int i = 0; i < n; ++i)
        if(A[i] - r > 0)
            z -= (A[i] - r) / c + ((A[i] - r) % c != 0);

    return z >= 0;
}

int main() {
    cin >> n >> a >> b;
    for(int i = 0; i < n; ++i)
        cin >> A[i];
    
    int lo = 1, hi = 1e9;
    while(lo < hi) {
        int mx = (lo + hi) / 2;
        if(fil(mx)) hi = mx;
        else lo = mx + 1;
    }
    
    cout << lo;
    
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#define ll long long 
int cmp(const void*a,const void*b){return *(long long*)a-*(long long*)b;}
int main(){
    ll n;
    ll k;
    scanf("%lld%lld",&n,&k);
    ll p[n];
    for(int i=0;i<n;i++)
        scanf("%lld",&p[i]);
    qsort(p,n,sizeof(long long),cmp);
    ll amin,amid,amax;
    amin=-1000000000000000018;
    amax=-1*amin;
    ll min,max,mid,count;
    while(amax-amin>1){
        amid=(amin+amax)/2;
        count=0;
        for(int i=0;i<n;i++){
            min=-1;
            max=n;
            while(max-min>1){
                mid=(max+min)/2;
                if(p[i]>=0){
                    if(p[mid]*p[i]<=amid)
                        min=mid;
                    else
                        max=mid;
                }
                else{
                    if(p[mid]*p[i]<=amid)
                        max=mid;
                    else
                        min=mid;
                }
            }
            if(p[i]>=0)
                count+=max;
            else
                count+=n-max;
                if(p[i]*p[i]<=amid)
                    count--;
        }
        count/=2;
        if(count<k)
            amin=amid;
        else
            amax=amid;
    }
    printf("%lld\n",amax);
    return 0;
}

Measured memory_bytes: 3324
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define modul 998244353
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll a,b,c,d,e;
int32_t main(){
CODE_START;
cin>>a>>b>>c>>d>>e;
if(a!=1){
    cout<<1<<endl;
}else if(b!=2){
cout<<2<<endl;
}else if(c!=3){
cout<<3<<endl;
}else if(d!=4){
cout<<4<<endl;
}else cout<<5<<endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MAX_N 100000
#define MAX_M 100000
const int MAX = 100100;
const int MOD = 1000000007;
#define vec vector<int>
#define vecll vector<ll>
#define vecllvec vector<vector<ll>>
#define vecb vector<bool>
#define vecBvec vector<vector<bool>>
#define vecst vector<string>
#define vecch vector<char>
#define vecd vector<double>
#define vecvec vector<vector<int>>
#define vecDvec vector<vector<double>>
#define vecHvec vector<vector<char>>
#define all(x) (x).begin(),(x).end()
const long long INF = 1LL<<60;
const string YES = "Yes";
const string NO = "No";
#define PI 3.141592653589793
// cout << setprecision(15) << std::fixed;

// テレンス「もしかしてACですかーッ!?」　ジョセフ「Yse! Yse! Yse!」


int main() {
  vecch S={'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 n;
  string a;
  cin>>n>>a;
  for(int i=0;i<a.size();i++){
    int num=0;
    for(int j=0;j<S.size();j++){
      if(S[j]==a[i]){
        num=j;
        num+=n;
        if(num>=S.size()) num-=S.size();
        break;
      }  
    }
    a[i]=S[num];
  }
  cout<<a<<endl;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

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

	ll a;cin >> a;
	string str;cin >> str;
	cout << (a >= 3200 ? str : "red") << endl;
	return 0;
}


Measured memory_bytes: 256
//
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    t = 1;
    while (t--)
    {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << max(max(a * c, a * d), max(b * c, b * d)) << " " << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int main(){
 long double X,Y,Z;
 int long long N,D;
 int c=0;
 cin>>N>>D;
 while(N--){
    cin>>X>>Y;
 Z=sqrt(X*X+Y*Y);
 if(Z<=D){
    c++;
 }
 }

 cout<<c;
}


Measured memory_bytes: 3800
import sys
s = input()
a, b, c, k = s.split()

a = int(a)
b = int(b)
c = int(c)
k = int(k)


ans = 0
if k <= a:
	print(k)
	sys.exit()
ans += a
k -= a

if k <= b:
	print(ans)
	sys.exit()
k -= b

print(ans - k)


Measured memory_bytes: 9080
# AOJ 0515: School Road
# Python3 2018.6.30 bal4u

while True:
	a, b = map(int, input().split())
	if a == 0: break
	arr = [[0 for b in range(b+1)] for a in range(a+1)]
	p = [[0 for b in range(b+1)] for a in range(a+1)]
	for i in range(int(input())):
		x, y = map(int, input().split())
		arr[x][y] = 1
	for x in range(1, a+1):
		if arr[x][1]: break
		p[x][1] = 1
	for y in range(1, b+1):
		if arr[1][y]: break
		p[1][y] = 1
	for y in range(2, b+1):
		for x in range(2, a+1):
			if arr[x][y]: continue
			if arr[x-1][y] == 0: p[x][y] += p[x-1][y]
			if arr[x][y-1] == 0: p[x][y] += p[x][y-1]
	print(p[a][b])


Measured memory_bytes: 5608
N = input()
K = int(input())
L = len(N)

dp0 = [[0] * (K + 1) for _ in range(L + 1)]
dp1 = [[0] * (K + 1) for _ in range(L + 1)]

dp0[0][0] = 1

n = []
for i in N:
    n.append(int(i))

for i in range(L):
    D = n[i]
    for j in range(K + 1):
        if D == 0:
            dp0[i + 1][j] += dp0[i][j]
            dp1[i + 1][j] += dp1[i][j]
            if j < K:
                dp1[i + 1][j + 1] = dp1[i][j] * 9
        else:
            dp1[i + 1][j] += (dp0[i][j] + dp1[i][j])
            if j < K:
                dp0[i + 1][j + 1] += dp0[i][j]
                dp1[i + 1][j + 1] += (D - 1) * dp0[i][j]
                dp1[i + 1][j + 1] += 9 * dp1[i][j]

print(dp0[L][K] + dp1[L][K])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i= a ; i < b ; ++i)
#define rep(i,n) fo(i,0,n)
#define pln(n) printf("%lld\n",n)
#define sll(n) scanf("%lld",&n)
#define ss(n) scanf("%s",n)
#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define dbg3(x,y,z) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) <<" , "<< #z <<": "<<(z)<<endl; }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define vll vector<long long>
#define vvi vector<vector<int>>
#define si set<int>
#define tr(c, it) \
for(decltype(c.begin()) it = c.begin(); it!= c.end(); it++)
#define pis pair<int,string>
#define present(c, x) (c.find(x) != c.end())
#define cpresent(c, x) (find(all(c),x) != c.end())
#define mod (int)(1e9 + 7) 

using namespace std;
long long dp[3001][3001][2];

int main(){
	int n;
	cin >> n;
	vector<long long> a(n);
	long long S = 0;
	for(int i = 0;i < n; i++){
		cin >> a[i];
		S += a[i];
		dp[i][i][0] = a[i];
		dp[i][i][1] = a[i];
	}
	for(int len = 2; len <= n; len++){
		for(int i = 0; i + len - 1 < n; i++){
			int j = i + len -1;
			if(len == 2){
				dp[i][j][0] = max(a[i], a[j]);
				dp[i][j][1] = max(a[i], a[j]);
			}
			else{
				long long sum = 0;
				for(int ind = i; ind <= j; ind++){
					sum += a[ind];
				}
				// for first player
				dp[i][j][0] = max(sum - dp[i+1][j][1], sum - dp[i][j-1][1]);
				dp[i][j][1] = max(sum - dp[i+1][j][0], sum - dp[i][j-1][0]);
			}
		}
	}
	cout << 2 * dp[0][n-1][0] - S << endl;
	
}

Measured memory_bytes: 85332
def ABC139B_PowerSocket():
    A, B = map(int, input().split())

    taps = 1
    sock = 1

    if B == 1:
        print(0)

    else:
        sock = A
        while (sock) < B:
            taps = taps + 1
            sock = sock + A - 1

        print(taps)

ABC139B_PowerSocket()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin);i>(end);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}

#define ll long long
#define f first
#define s second
using namespace std;

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;

int main()
{
	// 入力
	ll N;
	cin >> N;
	vec A(N);
	REP(i, N) {
		cin >> A[i];
	}

	SORT(A);

	ll sum = 0;
	ll starti = 0;
	REP(i, N) {
		sum += A[i];
		// debug(i);
		// vdebug(A);
		// debug(sum);
		if (i<N-1 && sum * 2 < A[i + 1]) starti = i+1;
		// debug(starti);
	}

	// cout<<starti<<endl;

	ll ans = N - starti;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
// time-limit: 2000
#include <bits/stdc++.h>

using namespace std;

#define fo(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define lli long long int
#define all(c) c.begin(),c.end()
#define lower(c) tolower(c)
#define upper(c) toupper(c)
#define MAX(c) *max_element(c.begin(),c.end())
#define MIN(c) *min_element(c.begin(),c.end())
#define len(c) c.size()
const int MOD = 1000000007;
const int MX = 2e5 + 5;
const int INF = 1e9 + 10;
const lli LINF = 1e18;

void solve() {
	lli n;
	cin >> n;
	if(n>=30)cout << "Yes";
	else cout << "No";

}


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


Measured memory_bytes: 3648
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main(void)
{

    string R;
    char onec;
	bool komoji = false;
	int countC = 0;

    cin >> R;

	onec = R[0];

	if(onec=='A'){
		for (int i=1; i<(R.length()); i++){
			onec = R[i];
			if(onec=='C' && i>1 && i<(R.length()-1)){
				countC++;
			}else if(onec>='a' && onec<='z'){
				komoji = true;
			}else{
				komoji = false;
				break;
			}
		}
	}


	if(komoji && countC ==1) {
		printf("AC");
	} else {
		printf("WA");
	}
		
	
	return 0;
}



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

int main(void){
    int n[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51}, k;
    cin >> k;

    cout << n[k-1] << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int N;
int H[114514];

int main(void) {
	int i;
	int mikakosi;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &H[i]) != 1) return 1;
	}
	mikakosi = H[N - 1];
	for (i = N - 2; i >= 0; i--) {
		if (H[i] <= mikakosi) {
			mikakosi = H[i];
		} else if (H[i] - 1 <= mikakosi) {
			mikakosi = H[i] - 1;
		} else {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
using namespace std;

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

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acosl(-1.0);

ll mod_pow(ll x, ll n, ll m = mod) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % m;
		x = x * x % m; n >>= 1;
	}
	return res;
}
struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n % mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 21;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

void solve() {
	string s; cin >> s;
	if (s.back() == 's')s += "es";
	else s += "s";
	cout << s << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(15);
	//init_f();
	//init();
	//expr();
	//int t; cin >> t; rep(i, t)
	solve();
	return 0;
}




Measured memory_bytes: 36432
while True:
    try:
        n = int(input())
    except EOFError:
        break
    answer = 0
    for a in range(10):
        for b in range(10):
            for c in range(10):
                for d in range(10):
                    if a+b+c+d == n:
                        answer += 1
    print(answer)


Measured memory_bytes: 5596
#include<iomanip>
#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long double ll;
typedef pair<ll,ll> pll;
vector<pll> list;
pll operator-(pll a,pll b){
return pll(a.first-b.first,a.second-b.second);
}
ll dist(pll a){
return sqrt(a.first*a.first + a.second*a.second);
}
ll cal(pll a,pll b,pll c){
ll ab = dist(a-b);
ll bc = dist(b-c);
ll ca = dist(c-a);
ll z = (ab+bc+ca)/2;
return sqrt(z*(z-ab)*(z-bc)*(z-ca));
}
ll solve(){
ll ans=0;
for(int i=2;i<list.size();i++){
ans+=cal(list[0],list[i-1],list[i]);
}
return ans;
}
int main(){
char c;
ll x,y;
while(cin>>x>>c>>y){
list.push_back(pll(x,y));
}
cout<<solve()<<endl;
}

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

int main(){
	int n,m,p[1000];
	while(scanf("%d%d",&n,&m), n != 0){
		for(int i=0; i<n;i++){
			scanf("%d",&p[i]);
		}
		sort(p,p+n);
		int sum = 0;
		int it = 0;
		for(int i = n-1; i >= 0; i--,it++){
			if(it % m != m-1)
				sum += p[i];
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 2620
n=10**5
a=[1]*(n+1)
for x in range(2,int(n**0.5)+1):
    if a[x]:
        for i in range(x*x,n+1,x):
            a[i]=0
a[0]=a[1]=0
for x in range((n+1)//2,0,-1):
    if a[x] == 0:
        a[2*x-1] = 0
m=a[2]=0
for x in range(n+1):
    m += a[x]
    a[x] = m

lr=[input() for _ in [0]*int(input())]
for x in lr:
    l,r = map(int,x.split())
    print(a[r]-a[l-1])

Measured memory_bytes: 13984
#pragma Grem optimize ("O3")
#include <bits/stdc++.h>

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

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

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

int msg() {
    srand( time( 0 ) ) ;
    vector < string > st = {
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!",
        "Go Go fight!"
    } ;
    cerr << st[ rand() % sz( st ) ] ;
    return 0 ;
}


void FastInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}

int n ;
int sum = 0 ;
int tmp ;

int main(){
   cin >> n ;
   tmp = n ;
   while( tmp ){
     sum += tmp % 10 ;
     tmp /= 10 ;
   }
   cout << ( n % sum ? "No" : "Yes" ) ;
   return 0 ;
}




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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

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

    ll n = s.size();

    ll z[26] = {};
    REP(i, n) z[(int)(s[i] - 'a')]++;
    
    ll ans = n * (n - 1) / 2 + 1;
    REP(i, 26) {
        ll zn = z[i];
        ans -= zn * (zn - 1) / 2;
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    int N;
    cin >> N;
    ve<int> P(N);
    in(N,P);
    rep(i,N) P[i]--;
    
    ve<int> A(N);
    rep(i,N) A[P[i]] = i;
    
    int a = -1;
    int b = 0;
    int an = 0;
    rep(i,N){
        if(a < A[i]) b++;
        else an = max(an,b),b = 1;
        
        if(i == N-1) an = max(an,b);
        else a = A[i];
    }
 
    out(N-an);


    return 0;
}


Measured memory_bytes: 1792
def main():

    K = int(input())
    cur = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    if K <= len(cur):
        return cur[K-1]
    K -= 9
    # add = cur
    while True:
        temp = []
        for v in cur:
            if v % 10 == 0:
                temp.append(v*10 + v % 10)
                temp.append(v*10 + 1)
            elif v % 10 == 9:
                temp.append(v*10 + 8)
                temp.append(v*10 + v % 10)
            else:
                temp.append(v * 10 + v % 10 - 1)
                temp.append(v * 10 + v % 10)
                temp.append(v * 10 + v % 10 + 1)
        # add += temp
        if len(temp) >= K:
            # break
            return temp[K-1]
        cur = temp
        K -= len(temp)
    return -1

if __name__ == '__main__':
    print(main())

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n;
int a[200000], b[200000];
int c[200000], d[200000];

int main() {
    if (0) {
        mt19937 mt(123);
        n = 200000;
        forn(i, n) a[i] = mt() % (1 << 28);
        forn(i, n) b[i] = mt() % (1 << 28);
    } else {
        scanf("%d", &n);
        forn(i, n) scanf("%d", a + i);
        forn(i, n) scanf("%d", b + i);
    }
    int mask = 0;
    int ans = 0;
    forn(i, 29) {
        int res = 0;
        int bit = 1 << i;
        mask |= bit;
        forn(i, n) {
            c[i] = a[i] & mask;
            d[i] = b[i] & mask;
        }
        sort(c, c + n);
        sort(d, d + n);
        int p = 0, q = 0, r = 0;
        for (int i = n - 1; i >= 0; --i) {
            while (p < n && c[i] + d[p] < bit) {
                ++p;
            }
            while (q < n && c[i] + d[q] < 2 * bit) {
                ++q;
            }
            while (r < n && c[i] + d[r] < 3 * bit) {
                ++r;
            }
            res += (q - p + n - r) & 1;
        }
        if (res & 1) {
            ans |= bit;
        }
    }
    cout << ans << endl;
    return 0;
}



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

typedef pair<string,string> P;

int main() {
    int n;
    long long ans = 0;
    string s;
    map<P,long long> cnt;
    cin >> n >> s;

    for (int i = 0;i < 1 << n;++i) {
        string a = "",b = "";
        for (int j = 0;j < n;++j) {
            if (i & (1 << j)) {
                a += s[j];
            } else b = s[j]+b;
        }
        cnt[P(a,b)]++;
    }

    for (int i = 0;i < 1 << n;++i) {
        string a = "",b = "";
        for (int j = 0;j < n;++j) {
            if (i & (1 << j)) {
                a += s[n+j];
            } else b = s[n+j]+b;
        }
        ans += cnt[P(b,a)];
    }

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

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

int main(){
  int N;
  string s;
  
  cin >> N;
  cin >> s;
  
  char c_old = s.at(0);
  int slimeCount = 1;
  for( int i = 1; i < N; ++i ){
    if( s.at(i) != c_old ){
      ++slimeCount;
      c_old = s.at(i);
    }
  }
  
  cout << (int)slimeCount;
}


Measured memory_bytes: 512
#!/usr/bin/env python

N = int(input())
H = list(map(int, input().split()))
ans = 0
for j in range(max(H)):
    for i in range(N-1):
        if H[i] != 0 and H[i+1] == 0:
            ans += 1
        if H[i] != 0:
            H[i] -= 1
    if H[N-1] != 0:
        H[N-1] -= 1
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;
 
#define ll long long
 
int Mod;
 
typedef class Zi {
    public:
        int v;
 
        Zi() : v(0) {   }
        Zi(int v) : v(v) {  }
        Zi(ll x) : v(x % Mod) { }
 
        friend Zi operator + (Zi a, Zi b) {
            return ((a.v += b.v) >= Mod) ? (a.v - Mod) : a;
        }
        friend Zi operator - (Zi a, Zi b) {
            return ((a.v -= b.v) < 0) ? (a.v + Mod) : a;
        }
        friend Zi operator * (Zi a, Zi b) {
            return 1ll * a.v * b.v;
        }
} Zi;
 
const int N = 5e3 + 5;
 
int n;
Zi f[N][N], g[N][N];
 
void work(Zi (*f)[N], int lim) {
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++)
            f[i][j] = f[i - 1][j];
        for (int j = i; j <= n; j++) {
            f[i][j] = f[i - 1][j] + f[i][j - i];
        }
    }
    for (int i = n; i; i--) {
        Zi sum = 0;
        for (int j = lim + 1; j <= n; j++) {
            sum = sum + f[i - 1][j - lim - 1];
            f[i][j] = f[i][j] - sum;
        }
    }
}
 
int main() {
    scanf("%d%d", &n, &Mod);
    int hn = (n + 1) >> 1;
    Zi ans = 0;
    if (n & 1) {
        work(f, hn - 1);
        work(g, hn - 1);
    } else {
        work(f, hn);
        work(g, hn - 1);
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = g[i][j] + g[i][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            ans = ans + f[i - 1][j] * g[n - i][i - j - 1];
        }
    }
    printf("%d\n", ans.v);
    return 0;
}

Measured memory_bytes: 196096
#include <iostream>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = std::vector<int>;
using Vlli = std::vector<lli>;
using Wint = std::vector<Vint>;
using Wlli = std::vector<Vlli>;
using Vbool = std::vector<bool>;
using pii = std::pair<int, int>;
using pll = std::pair<lli, lli>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {std::make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
constexpr char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



int main(void){
  int n, k; cin >> n >> k;
  Vint A(n, 0);
  REP(_, n){
    int u; cin >> u;
    A.at(u-1)++;
  }
  sort(A.begin(), A.end(), greater<int>());
  int ans = n;
  REP(i, k) ans -= A.at(i);
  std::cout << ans << BR;
  return 0;
}

Measured memory_bytes: 1024