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

template <class T, class Compare>
struct SegmentTree/*{{{*/
{
  vector<T>& mem;
  vector<int> indexes;
  Compare cmp;
  SegmentTree(vector<T>& cs)
    : mem(cs), indexes(4*cs.size(), -1)
  {
    build(0, 0, cs.size());
  }

  void build(int idx, int left, int right)
  {
    if (left+1 == right) {
      indexes[idx] = left;
    } else {
      const int mid = (left + right)/2;
      build(2*idx+1, left, mid);
      build(2*idx+2, mid, right);
      // minimum in [left, right)
      if (cmp(mem[indexes[2*idx+1]], mem[indexes[2*idx+2]])) {
        indexes[idx] = indexes[2*idx+1];
      } else {
        indexes[idx] = indexes[2*idx+2];
      }
    }
  }

  inline T query_value(int left, int right) const { return mem[query_index(left, right)]; }

  inline int query_index(int left, int right) const { return query_index(left, right, 0, 0, mem.size()); }

  int query_index(int left, int right, int i, int a, int b) const
  {
    // [a, b) is the range of indexes[i]
    if (b <= left || right <= a) {
      // does not intersect
      return -1;
    } else if (left <= a && b <= right) {
      // contains
      return indexes[i];
    } else {
      const int m = (a+b)/2;
      const int l = query_index(left, right, 2*i+1, a, m);
      const int r = query_index(left, right, 2*i+2, m, b);
      if (l == -1) {
        return r;
      } else if (r == -1) {
        return l;
      } else {
        if (cmp(mem[l], mem[r])) {
          return l;
        } else {
          return r;
        }
      }
    }
  }

  void update(int idx, const T& val)
  {
    mem[idx] = val;
    update_index(0, mem.size(), 0, idx);
  }

  void update_index(int left, int right, int i, int idx)
  {
    if (left+1 == right) {
      //indexes[i] = idx;
    } else {
      const int mid = (left+right)/2;
      if (idx < mid) {
        update_index(left, mid, 2*i+1, idx);
      } else {
        update_index(mid, right, 2*i+2, idx);
      }
      if (cmp(mem[indexes[2*i+1]], mem[indexes[2*i+2]])) {
        indexes[i] = indexes[2*i+1];
      } else {
        indexes[i] = indexes[2*i+2];
      }
    }
  }
};/*}}}*/

int main()
{
  int N;
  cin >> N;
  vector<long long> mem(N+1, 0);
  SegmentTree<long long, greater<long long> > segtree(mem);
  long long sum = 0, a = 0;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    sum += x;
    long long v = segtree.query_value(0, x);
    a = max(a, v+x);
    segtree.update(x, v+x);
  }
  cout << sum - a << endl;
  return 0;
}

Measured memory_bytes: 3380
a, b, k = map(int,input().split())
maximum = 0

if(a+k <= b):
    for i in range(a, a+k):
        print(i)
        maximum = i
    for j in range(b-k+1, b+1):
        if(maximum < j):
            print(j)
        
else:
    for i in range(a, b+1):
        print(i)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char N[3];
  cin >> N;
  if (N[0]=='7'||N[1]=='7'||N[2]=='7') {
    cout << "Yes" << endl;
  }else{
  cout << "No" << endl;
  }
}

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

int main() {
  int n;
  cin >> n;
  int max_height = 0;
  int viewable = 0;
  for (int i = 0; i < n; ++i) {
    int h;
    cin >> h;
    if (h >= max_height) {
      ++viewable;
      max_height = h;
    }
  }
  cout << viewable << endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double sum = 0;
            for(int i = 0; i < n; i++)
            {
                string[] In = Console.ReadLine().Split(' ');
                double x = double.Parse(In[0]);
                string u = In[1];
                if (u == "JPY") sum += x;
                else if (u == "BTC") sum += x * 380000.0;
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 27472
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
A = A[::-1]
B = B[::-1]

ans = 0
for i in range(N):
    tmp = (A[i] + ans) % B[i] 
    if tmp == 0:
        tmp = 0
    else:
        tmp = B[i] - tmp
    ans += tmp

print(ans)

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

using namespace std;

const int maxNumber = 1e5+5;

vector <int> distancePath(maxNumber);
vector <int> mat[maxNumber];

int dfs(int node)
{
    if (distancePath[node])
        return distancePath[node];

    for (auto i = 0; i < mat[node].size(); i++)
    {
        int childDistancePath = dfs(mat[node][i]) + 1;

        if (distancePath[node] < childDistancePath)
            distancePath[node] = childDistancePath;
    }

    return distancePath[node];
}

int main()
{
    int n, m;
    int answer = 0;

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        mat[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
        answer = max(answer, dfs(i));

    cout << answer;
    return 0;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
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;}

template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    using pii=pair<int,int>;
    int n,m;
    cin>>n>>m;
    vector<int> manage[n];
    vector<pii> pf(m);
    rep(i,m){
        int y,p;
        cin>>p>>y;
        p--;y--;
        manage[p].push_back(y);
        pf[i]=make_pair(p,y);
    }
    for(int i=0;i<n;i++){
        sort(manage[i].begin(),manage[i].end());
    }
    for(int i=0;i<m;i++){
        printf("%06d%06d\n",pf[i].first+1,lower_bound(manage[pf[i].first].begin(),manage[pf[i].first].end(),pf[i].second)-manage[pf[i].first].begin()+1);
    }
    return 0;
}




Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef long long int ll;
typedef vector<int> vi;
const int INF = 1 << 30;

int main(){
    int n;
    cin >> n;
    vi h(n);
    rep(i, n) cin >> h.at(i);
    vi d(n, INF);
    d.at(0) = 0;
    rep(i, n-1){
        if(d.at(i+1) > d.at(i) + abs(h.at(i+1)-h.at(i))){
            d.at(i+1) = d.at(i) + abs(h.at(i+1)-h.at(i));
        }
        if(i+2 <= n-1)
        if(d.at(i+2) > d.at(i) + abs(h.at(i+2)-h.at(i))){
            d.at(i+2) = d.at(i) + abs(h.at(i+2)-h.at(i));
        }
    }
    
    cout << d.at(n-1) << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int first=1000000,end,ans=0;
    for(int i=0;i<s.size();i++){
        if(s.at(i)=='A'){
            first=min(first,i);
        }else if(s.at(i)=='Z'&&first!=1000000){
            end=i;
            ans=max(ans,end-first+1);
            end=0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
package main

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

var scanner *bufio.Scanner

func printIt() {
	a := nextFloat()
	b := nextFloat()
	t := nextFloat()

	h := b * math.Sin(t/180*math.Pi)
	s := 0.5 * a * h
	c := math.Sqrt(a*a + b*b - 2*a*b*math.Cos(t/180*math.Pi))
	fmt.Println(s)
	fmt.Println(a + b + c)
	fmt.Println(h)
}

func nextFloat() float64 {
	scanner.Scan()
	num, err := strconv.ParseFloat(scanner.Text(), 10)
	if err != nil {
		panic(1)
	}
	return num
}

func main() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	printIt()
}



Measured memory_bytes: 1112
#include<cstdio>
using namespace std;
struct point{
public:
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
    point operator +(point a){
        return point(x+a.x,y+a.y);
    }
    point operator -(point a){
        return point(x-a.x,y-a.y);
    }
    point operator *(double a){
        return point(x*a,y*a);
    }
    double operator *(point a){
        return x*a.x+y*a.y;
    }
    void print(){
        printf("%.10lf %.10lf\n",x,y);
    }
};
struct segment{
    point p1,p2,base;
    segment(point a,point b){
        p1=a,p2=b,base=b-a;
    }
};
point project(segment s,point p){
    double r=(p-s.p1)*s.base/(s.base*s.base);
    return (s.p1+s.base*r);
}
int main(){
    int n;
    double x1,y1,x2,y2;
    point p;
    scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    segment s(point(x1,y1),point(x2,y2));
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf",&p.x,&p.y);
        ((project(s,p)-p)*2+p).print();
    }
    return 0;
}


Measured memory_bytes: 2756
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};




int main(){
    LL a,v,b,w;cin >> a >> v >> b >> w;
    LL t;cin >> t;
    LL dist = abs(a - b);
    if(v <= w){
        puts("NO");
    }
    else{
        LL vv = v - w;
        if(vv * t < dist){
            puts("NO");
        }
        else{
            puts("YES");
        }
    }
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 200000;
const int MAX_L = 100000000;
const int MAX_SQRT_B = 10000;
typedef int64_t ll;
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; }

ll N, A, B;

int main() {
	cin >> N >> A >> B;
	ll T = B - A-1;
	if (T % 2 != 0) {
		cout << (T + 1) / 2 << endl;
	}
	else {
		if (A - 1 < N - B) {
			cout <<  A+(T - 1 + 1) / 2 << endl;
		}
		else {
			cout << N - B +1+ (T - 1 + 1) / 2 << endl;
		}
	}
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(a, value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const int MAX = 1 << 10;

double x[MAX], y[MAX], r[MAX];
double c[MAX][MAX];
bool used[MAX];
double d[MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(10);
	int xs, ys, xt, yt, n;
	cin >> xs >> ys >> xt >> yt >> n;
	FOR(i, 0, n)
		cin >> x[i] >> y[i] >> r[i];
	x[n] = xs;
	y[n] = ys;
	x[n + 1] = xt;
	y[n + 1] = yt;
	FOR(i, 0, n + 2)
		FOR(j, 0, n + 2)
		{
			double dist = sqrt(pow(x[j] - x[i], 2) + pow(y[j] - y[i], 2));
			c[i][j] = max(0.0, dist - r[i] - r[j]);
		}
	FOR(i, 0, n + 2)
		d[i] = 1e18;
	d[n] = 0;
	FOR(i, 0, n + 2)
	{
		int v = -1;
		FOR(j, 0, n + 2)
			if(!used[j] && (v == -1 || d[j] < d[v]))
				v = j;
		used[v] = true;
		FOR(j, 0, n + 2)
			d[j] = min(d[j], d[v] + c[v][j]);
	}
	cout << d[n + 1] << "\n";
	return 0;
}

Measured memory_bytes: 8576
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

def dfs(n, i, pk, ans):
    if N - n >= (ans-i)*unit[pk]:
        return ans
    sk = bisect_right(unit, N-n, 0, pk+1) - 1
    for k in range(sk, -1, -1):
        c = n + unit[k]
        if c == N:
            if i + 1 < ans:
                return i + 1
        else:
            t = dfs(c, i+1, k, ans)
            if t < ans:
                ans = t
    return ans

print(dfs(0,0,Nu-1,N))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

#define MOD 1000000007

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

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m; cin>>n>>m;
	int cnt[3]={1,0,0};
	set<int> st;
	int tmp;
	while(m--)
	{
		cin>>tmp;
		st.insert(tmp);
	}
	For(i,1,n)
	{
		if(st.count(i)) cnt[i%3]=0;
		else cnt[i%3]=(cnt[0]+cnt[1]+cnt[2]-cnt[i%3])%MOD;
	}
	cout<<cnt[n%3]<<"\n";
}















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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin  >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    bool flag = true;
    for(int i=0;i<n;i++){
        if(a[i]==a[i+1]){
            flag = false;
            break;
        }
    }
    if(flag){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long 

// fact(n)
int fact(int n){
	if(n == 1)	return 1;
	else return (n * fact(n - 1));
}

// combination(n,r)
int combination(int n, int r){
	if(r == 0 || r == n)	return 1;
	else if(r == 1)	return n;
	return (combination(n - 1, r - 1) + combination(n - 1, r));
}

int gcd(int a,int b){
	if(!(a % b)) return b;
	return gcd(b,a % b);
}

// lcm(a.b)
int lcm(int a,int b){
	return (a * b) / gcd(a,b);
}

// qsort(array, size, sizeof(int),comp);
int comp(const int *a,const int *b){
	return (*a - *b);
}

// append(array,*size,addNum)
void append(int *array,int *size,int num){
	realloc(array, sizeof(int) * (*size + 1));
	array[(*size)] = num;
	++(*size);
}

// pop(array,*size) & nongetpop(array,*size)
int pop(int *array,int *size){
	int temp = array[(*size - 1)];
	nongetpop(array,&(*size));
	return temp;
}

void nongetpop(int *array,int *size){
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
}

int main(int argc, char const *argv[]){
	TLong n,k;
	scanf("%lld%lld",&n,&k);
	TLong ans = k;
	for(int i = 1;i < n; ++i) ans *= (k - 1);
	printf("%lld\n",ans);
	return 0;
}


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

int main()
{
  int n;
  cin >> n;
  vector<string> s(n);
  vector<int> t(n);
  rep(i, n) cin >> s[i] >> t[i];
  string x;
  cin >> x;
  
  bool flg = false;
  int res = 0;
  rep(i, n)
  {
    if(flg) res += t[i];
    if(s[i] == x) flg = true; 
  }
  
  cout << res << endl;
  
  return 0;
}

Measured memory_bytes: 256
import static java.lang.System.*;

import java.util.Scanner;

class Main {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
        	int n = sc.nextInt();
            int x = sc.nextInt();
            int count = 0;
            if(n == 0 && x == 0) {
            	break;
            }
            for(int a = 1; a <= n; a++) {
            	for(int b = a + 1; b <= n; b++) {
            		for(int c = b + 1; c <= n; c++) {
            			if(a + b + c == x) {
            				count++;
            			}
            		}
            	}
            }
            out.println(count);
        }
    }
}


Measured memory_bytes: 26436
<?php
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
list($K,$N)=sscanf(trim(fgets(STDIN)),"%d %d");
$A = array();
$max = 0;
$sc = new Scanner();
//$n = 
for($i=1;$i<=$N;$i++){
    $A[$i] = $sc->nextInt();
    if($i != 1){
        if(abs($A[$i] - $A[$i-1]) > $max){
            $max = abs($A[$i] - $A[$i-1]);
            $pos = $i;
        }
    }
}
if((($K - $A[$N]) + $A[1]) > $max){
    $pos = 1;
    $max = (($K - $A[$N]) + $A[1]);
}
$calc = 0;
for($i=1;$i<=$N-1;$i++){
    if($pos == $N){
        $calc +=(($K - $A[$N]) + $A[1]);
        
        $pos = 0;
    }else{
        $calc += ($A[$pos+1] - $A[$pos]);
    }

    $pos++;
}

print($calc);
//$n = $sc->nextInt();




Measured memory_bytes: 29292
/******************************************
* AUTHOR : SOMU KUMAR *
* INSTITUTION : IIT BHUBANESWAR *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//code here...............//
string n;
cin>>n;
int ans=0;
for(int i=0;i<n.length();i++){
	ans+=(n[i]-'0');
}
if(ans%9==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}

Measured memory_bytes: 3768
import java.util.*;

class Main{


     public static void main(String args[]){
     
       Scanner in = new Scanner(System.in);
       String s = in.next();
       char c= s.charAt(s.length()-1);
       if(c=='3'){
       System.out.println("bon");
       } else if(c=='1' || c=='0'|| c=='6' || c=='8'){
                System.out.println("pon");

       } else{
                         System.out.println("hon");

       }
     }

}


Measured memory_bytes: 35440
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int compare_char(const void *a, const void *b) {
  return strcmp((char *)a, (char *)b);
}
int main(void){
    char s[5050];
    int K;
    scanf("%s %d",s,&K);

    char substr[K+1][strlen(s)+1];
    char a[strlen(s)],b[K+1],tmp[K+1];
    int count = 0;
    strcpy(b,"z");
    for(int j=0;j<K;j++) strcat(b,"z");
    for(int i=0;i<K;i++){
        strcpy(substr[i],b);
    }
    a[0] = '\0';
    for(int i = 0; i < strlen(s); i++){
        for(int j = i; j < strlen(s);j++){
            if(j+1-i <= K){
                strncpy(a,s+i,j+1-i);
                a[j+1-i]='\0';
                strcpy(substr[K],a);
                if(strcmp(substr[K-1],substr[K])>=0){
                    for(int l=0;l<K;l++){
                            if(strcmp(substr[l], substr[K]) == 0){
                                strcpy(substr[K],b);
                            }
                    }
                    qsort((void *)substr,K+1,sizeof(substr[0]),compare_char);
                }
            }
        }
    }
    printf("%s\n",substr[K-1]);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,x,y) for(int i = x;i < y;i++)
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(a+b == 15)cout << "+" << endl;
  else if(a*b == 15)cout << "*" << endl;
  else cout << "x" << endl;
}


Measured memory_bytes: 768
# 01-BFS
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
# 01-BFSのちょっと丁寧な解説 - ARMERIA
# https://betrue12.hateblo.jp/entry/2018/12/08/000020

from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))
    gen_warp_can_reach = (
        (h, w, (h, w) in can_walk)  # 移動先，徒歩で行けるか
        for h in range(-2, 3) for w in range(-2, 3) if not h == 0 == w)
    warp_can_reach = set(gen_warp_can_reach)
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


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


Measured memory_bytes: 193384
#include <stdio.h>

int aaa[200000] = {};

int main()
{
	long n, m;
	long x, y;
	int ans = 0;
	scanf("%ld %ld", &n, &m);
	for (long i = 0; i < m; i++)
	{
		scanf("%ld %ld", &x,&y);
		if (x == 1)
		{
			aaa[y]++;
		}
		if (y == n)
		{
			aaa[x]++;
		}
	}
	for (long i = 0; i < 200000; i++)
	{
		if (aaa[i] >= 2)
		{
			ans = 1;
			break;
		}
	}
	if (ans == 1)
	{
		printf("POSSIBLE");
	}
	else
	{
		printf("IMPOSSIBLE");
	}
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
typedef long long unsigned int ll;
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,x,t;
    scanf("%llu%llu%llu",&n,&x,&t);
    ll temp= ceil(n/double(x))*t;
    printf("%llu\n",temp);
    return 0;
}

Measured memory_bytes: 3744
// Problem : D - FT Robot
// Contest : AtCoder - AtCoder Beginner Contest 082
// URL : https://atcoder.jp/contests/abc082/tasks/arc087_b
// Memory Limit : 512 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int short
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

vi xax,yax;
int x,y;

int dp[8001][8001*2];
int dp2[8001][8001*2];
int fun(int i,int x1)
{
	if(i==size(xax))
	return x1==x;
	if(dp[i][x1+8000]!=-1)
	return dp[i][x1+8000];
	return dp[i][x1+8000]=fun(i+1,x1+xax[i]) or fun(i+1,x1-xax[i]);
}

int fun2(int i,int x1)
{
	if(i==size(yax))
	return x1==y;
	if(dp2[i][x1+8000]!=-1)
	return dp2[i][x1+8000];
	return dp2[i][x1+8000]=fun2(i+1,x1+yax[i]) or fun2(i+1,x1-yax[i]);
}
void solve()
{
	string s;cin>>s;
	inin(dp);
	inin(dp2);
	cin>>x>>y;
	
	int cnt=0;
	int p=0;
	for(char c:s)
	{
		if(c=='F')
		{
			cnt++;
		}
		else
		{
			if(!p)
			xax.pb(cnt);
			else
			yax.pb(cnt);
			cnt=0;
			p^=1;
		}
	}
	if(cnt)
	{
		    if(!p)
			xax.pb(cnt);
			else
			yax.pb(cnt);
			cnt=0;
			p^=1;
	}
	int xt=0,yt=0;
	if(size(xax))
	{
	xt+=xax[0];
	
	bool b=fun(1,xt);
	//inin(dp);
	bool b2=fun2(0,0);
	
	if(b and b2)
	cout<<"Yes";
	else
	cout<<"No";
	}
	else
	{
		if(x==0 and y==0)
		cout<<"Yes";
		else
		cout<<"No";
	}
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 503992
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    var ary = Array<Long>(k){0}.toMutableList()
    var ans = 0L
    for (i in 1..n) ary[(i%k)] += 1
    for (a in 0 until k) {
        var b = (k-a) % k
        var c = (k-a) % k
        if ((b+c) % k != 0) continue
        ans += ary[a] * ary[b] * ary[c]
    }
    println(ans)
}

Measured memory_bytes: 42408
#include <bits/stdc++.h>
#define int long long
using namespace std;

int gcd_(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    return gcd_(b, a % b);
}

int gcd(int a, int b, int c) {
    return gcd_(gcd_(a, b), c);
}


signed main() {
    int k;
    cin >> k;
    int ans = 0;
    for (int a=1; a != k+1; a++) {
        for (int b=1; b != k + 1; b++) {
            for (int c = 1; c != k + 1; c++) {
                ans += gcd(a, b, c);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include<cstdio>
#include<cstring>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=305,mod=998244353;
char s[N]; int n,m,t,lim,a[N],f[N<<1][N][N<<1],ans; //f[x][y][z]: x turns; position y; delta z
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	RI i,j,k,p; for (scanf("%s%d",s+1,&t),n=strlen(s+1),m=i=1;i<=n;++i)
	if (s[i]=='0') ++m; else ++a[m]; if (!a[m]) --m;
	f[0][0][0]=1; lim=(min(t,n)<<1);
	for (j=0;j<m;++j) for (i=0;i<=lim;++i) for (k=0;k<=n;++k) if (f[i][j][k])
	{
		inc(f[i][j+1][k],f[i][j][k]); //do nothing
		for (p=1;i+p<=lim;++p) inc(f[i+p][j+1][k+p],f[i][j][k]); //addition
		for (p=1;p<=min(k,a[j+1])&&i+p<=lim;++p) inc(f[i+p][j+1][k-p],f[i][j][k]); //subtraction
	}
	for (i=0;i<=(min(t,n)<<1);++i) inc(ans,f[i][m][0]);
	return printf("%d",ans),0;
}

Measured memory_bytes: 220076
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000010;
constexpr ll INF= 1000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

ll RS(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P < 0) {
        return 0;
    }
    if(P%2==0){
        ll t = RS(N, P/2, M);
        return t*t % M;
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    ll N;
    cin >> N;
    vector<P> tree(N - 1);
    for(int i = 0;i < N - 1;i++) {
        ll u,v;
        cin >> u >> v;
        if(u > v) {
            swap(u,v);
        }
        tree.at(i) = P(u,v);
    }
    ll ret = N * (N + 1) * (N + 2) / 6;
    for(int i = 0;i < N - 1;i++) {
        ret -= (tree.at(i).first) * (N - tree.at(i).second + 1);
    }
    cout << ret << endl;
}

Measured memory_bytes: 6372
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

int main(void) {
    std::string s;
    std::cin >> s;
    int ans = 0;
    for (char c : s) {
        if (c == '1') {
            ans++;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

flg = False
for y in range(N-M+1):
  for x in range(N-M+1):
    res = True
    for i in range(M):
      if A[y+i][x+i:x+i+M] != B[i][i:i+M]: res = False
    if res: flg = True
    if flg: break
  if flg: break

print("Yes" if flg else "No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll int64_t
#define all(v) v.begin(), v.end()
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)
#define bitrep2(n) for(int bit2=0;bit2<(1<<n);bit2++)


int main() {

int A,B,C,D; cin >> A>>B>>C>>D;

cout << max(A*B,C*D) << endl;

return 0;
}

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

 int main(){
   int d, t, s;
   cin >> d >> t >> s;
   double ans = double(d)/s;
   if(ans <= t){
     cout << "Yes" << endl;
     return 0;
   }else{
     cout << "No" << endl;
          return 0;
   }
 }

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

int main()
{
    int n, m;
    int a[100][100];
    int b[100], c[100];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < m; i++)
        cin >> b[i];
    for (int i = 0; i < n; i++) {
        c[i] = 0;
        for (int j = 0; j < m; j++) {
            c[i] += a[i][j] * b[j];
        }
        cout << c[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 1200
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr int MOD = 1000000000 + 7;
//?¶????????????????????????????????????§??????????????????????¢????????????????
constexpr int INF = 2000000000;
const double PI = acos(-1);

string sum_string(string a, string b) {
	int al = a.size(), bl = b.size();
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	string ret;
	int tmp = 0;
	for (int i = 0; i < al || i < bl || tmp; i++) {
		tmp += (i < al ? a[i] - '0' : 0) + (i < bl ? b[i] - '0' : 0);
		ret.push_back('0' + tmp % 10);
		tmp /= 10;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

int main() {
	int n;
	cin>>n;
	string a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		string ans = sum_string(a, b);
		cout << (ans.size() > 80 ? string("overflow") : ans) << endl;
	}
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    int flag=0;
    for (int i=1;i<=1000000;i++) {
        if ((i*b+c)%a==0) {
            cout<<"YES"<<endl;
            flag=1;
            break;
        }
    }
    if (flag==0) {
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin>>S;
  int n=S.size();
  char a='a'-1,b='.';int count;
  for(int i=0;i<26;i++){
    a++;count=0;
    for(int j=0;j<n;j++){
      if(a!=S.at(j))count++;
      if(count==n){
        b=a;
        break;
      }
    }
    if(count==n)break;
  }
  if(b!='.')cout<<b<<endl;
  else cout<<"None"<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int n = 0, m = 0;
char mathx[3050][3050];
bool same[3050][3050];
int up[3050][3050];
int sta[3050][2], top = 0;
signed main()
{

	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%s", mathx[i] + 1);
	for(int i = n; i >= 1; i--)
		for(int j = 1; j <= m; j++)
		{
			same[i][j] = (mathx[i][j] == mathx[i][j + 1]);
			up[i][j] = (same[i][j] != same[i + 1][j]? 1: up[i + 1][j] + 1);
		}
	int ans = max(n, m);
	for(int i = 1; i <= n; i++)
	{
		top = 0;
		for(int j = 1; j <= m; j++)
		{
			if(top > 0)
			{
				#define aol(x, a, h) (h * (x - a + 1))
				int x = 1, y = top, z = 0;
				while(x < y)
				{
					z = x + ((y - x + 1) >> 1);
					if(z == 1 || aol(j, sta[z - 1][1], sta[z - 1][0]) < aol(j, sta[z][1], sta[z][0])) x = z;
					else if(aol(j, sta[z - 1][1], sta[z - 1][0]) > aol(j, sta[z][1], sta[z][0])) y = z - 1;
					else { x = y = z; break; }
				}
				ans = max(ans, aol(j, sta[x][1], sta[x][0]));
			}
			int u = j;
			while(top > 0 && (sta[top][0] > up[i][j] || (sta[top][0] < up[i][j] && (top > 1 && (aol(j, sta[top - 1][1], sta[top - 1][0]) > aol(j, sta[top][1], sta[top][0]) && aol(j, sta[top - 1][1], sta[top - 1][0]) <= aol(j, u, up[i][j]))))))
			{ if(sta[top][0] > up[i][j]) u = sta[top][1]; top--; }
			if(!top || sta[top][0] < up[i][j])
				top++, sta[top][0] = up[i][j], sta[top][1] = u;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 41088
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int n;
main()
{
    while(cin>>n,n){
        vector<int>a;map<int,int>M;
        vector<pair<int,pair<int,int> > >I;
        for(int i=0;i<n;i++)
        {
            int m,aa,b;cin>>m>>aa>>b;
            a.push_back(aa);a.push_back(b);
            I.push_back(make_pair(m,make_pair(aa,b)));
        }
        sort(a.begin(),a.end());
        a.erase(unique(a.begin(),a.end()),a.end());
        for(int i=0;i<a.size();i++)M[a[i]]=i+1;
        vector<int>sum(a.size()+1,0);
        for(int i=0;i<n;i++)
        {
            int m=I[i].first,A=I[i].second.first,B=I[i].second.second;
            sum[M[A]]+=m;
            sum[M[B]]-=m;
        }
        for(int i=1;i<sum.size();i++)sum[i]+=sum[i-1];
        bool ok=1;
        for(int i=0;i<sum.size();i++)ok&=sum[i]<=150;
        cout<<(ok?"OK":"NG")<<endl;
    }
}


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, b;
    cin >> n >> b;

    int cnt = 0;
    while (n){
        n /= b;
        cnt += 1;
    }

    cout << cnt << '\n';

    return 0;
}


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


int main()
{
	int n, a = 0, b = 0;
	string s, r;
	cin >> n;
	for (; n > 0; n--)
	{
		cin >> s >> r;
		if (s == r)
			(a++, b++);
		else if (s > r)
			a += 3;
		else 
			b += 3;
	}
	cout << a << " " << b << endl;
	return 0;
}



Measured memory_bytes: 3160
import math
n, k = (int(i) for i in input().split()) 
p = 0
for i in range(1,n+1):
  if i < k:
    x = math.ceil(math.log2(k/i))
    temp = 0.5 ** x / n
  else:
    temp = 1 / n
  p = p + temp
print(p)

Measured memory_bytes: 3188
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
int n;
char s;
ll c[300];
ll f[300][300];
ll sf[300][300];
ll ans=0;
ll M=1000000007;


int main()
{
    cin>>n;
    for (int i=0; i<n; ++i)
    {
        scanf("%c",&s);
        while (s=='\n')
            scanf("%c",&s);
        c[s]++;
    }
    for (int i=1; i<=26; ++i)
        for (int j='a'; j<='z'; ++j)
        {
            if (i==1)
            {
                f[i][j]=c[j];
                sf[i][j]=(sf[i][j-1]+f[i][j])%M;
            }
            else 
            {
                f[i][j]=(sf[i-1][j-1]*c[j])%M;
                sf[i][j]=(sf[i][j-1]+f[i][j])%M;
            }
            if (f[i][j]>0)
            {
       //         cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
            }
            ans+=f[i][j];
            ans%=M;
        }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 384
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int ones=n%10;
    if(ones==2||ones==4||ones==5||ones==7||ones==9){
        printf("hon\n");
    }
    else if (ones==0||ones==1||ones==6||ones==8){
        printf("pon\n");
    }
    else printf("bon\n");
    return 0;
}

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


int right(int iro[],int kazu[],int m,int len){
	int l=1;int r=3;
	while(true){
		if(iro[m-l]==iro[m+r] && 4<=kazu[m-l]+kazu[m+r]){
			l+=1;
			r+=1;
		}
		else{
			break;
		}
	}
	int w=0;
	for(int n=0;n<=m-l;n++){
		w+=kazu[n];
	}
	for(int aa=m+r;aa<=len;aa++){
		w+=kazu[aa];
	}
	return w;
}



int left(int iro[],int kazu[],int m,int len){
	int l=3;int r=1;
	while(true){
		if(iro[m-l]==iro[m+r]&&4<=kazu[m-l]+kazu[m+r]){
			l+=1;
			r+=1;
		}
		else{
			break;
		}
	}
	int w=0;
	for(int n=0;n<=m-l;n++){
		w+=kazu[n];
	}
	for(int aa=m+r;aa<=len;aa++){
		w+=kazu[aa];
	
	}
	return w;
}





int thright(int iro[],int kazu[],int m,int len){
	kazu[m]+=1;
	kazu[m+1]-=1;
	int l=1;
	int r=1;
	int w=0;
	while(true){
		if(iro[m-l]==iro[m+r]&&4<=kazu[m-l]+kazu[m+r]){
			l+=1;
			r+=1;
		}
		else{
			break;
		}
	}
	for(int n=0;n<=m-l;n++){
		w+=kazu[n];
	}
	for(int aa=m+r;aa<=len;aa++){
		w+=kazu[aa];
	}
	kazu[m]-=1;
	kazu[m+1]+=1;
return w;
}


int thleft(int iro[],int kazu[],int m,int len){
	kazu[m]+=1;
	kazu[m-1]-=1;
	int l=1;
	int r=1;
	int w=0;
	while(true){
		if(iro[m-l]==iro[m+r]&&4<=kazu[m-l]+kazu[m+r]){
			l+=1;
			r+=1;
		}
		else{
			break;
		}
	}
	for(int n=0;n<=m-l;n++){
		w+=kazu[n];
	}
	for(int aa=m+r;aa<=len;aa++){
		w+=kazu[aa];
	}
	kazu[m]-=1;
	kazu[m-1]+=1;
return w;
}




int main(){
	while(true){
		
		int kazu[10000]={};
		int iro[10000]={};
		int a,b,c;
		int len=1;
		cin >> a;
		if(a==0){
			break;
		}
		cin >> c;
		int z=0;
		iro[0]={c};
		kazu[0]={1};
		for(int n=0;n<a-1;n++){
			cin >> b;
			if(c!=b){
				z+=1;
				iro[z]={b};
				c=b;
				len+=1;
			}
			kazu[z]+=1;
		}
		int anser=a;
		for(int m=0;m<len;m++){
			if(kazu[m]>=2){
				if(m!=len&&iro[m]==iro[m+2]&&kazu[m+1]==1){
					anser=min(anser,right(iro,kazu,m,len));
				}
				if(m!=0&&iro[m]==iro[m-2]&&kazu[m-1]==1){
					anser=min(anser,left(iro,kazu,m,len));
				}
				if(kazu[m]==3){
					if(m!=len){
						anser=min(anser,thright(iro,kazu,m,len));
					}
					if(m!=0){
						anser=min(anser,thleft(iro,kazu,m,len));
					}
				}
			}	
		}
		printf("%d\n",anser);
	}
}


Measured memory_bytes: 3196
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int C = sc.nextInt();
		int[] b = new int[M];
		int soloutions = 0;
		
		for(int i = 0; i < M; i++)
		{
			b[i] = sc.nextInt();
		}
		
		for(int i = 0; i < N; i++)
		{
			int total = 0;
			for(int j = 0; j < M; j++)
			{
				total = total + b[j] * sc.nextInt(); 
			}
			total = total + C;
			if(total > 0)
			{
				soloutions++;
			}
		}
		
		System.out.println(soloutions);
		
	}
}


Measured memory_bytes: 29256
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def bs(ar,eq,n) en=(eq==1 ? :>= : :>); ar.bsearch_index{|x|x.send(en,n)} end
def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n=gi
a=gsmi
a.each do |x|
  h[x]+=1
end
#puts h.to_s

cnt=0
h.each do |k,v|
  c=v-k
  c=v if c<0
  cnt+=c
end

puts cnt

Measured memory_bytes: 15508
import math

N , M = map(int,input().split())#N:展望台の数、M:道の数
H = list(map(int,input().split()))#H:高さの配列

AB = [map(int, input().split()) for _ in range(M)]
A , B = [list(i) for i in zip(*AB)]

G = [1] * N #展望台の数

for i in range (M):
    if H[ A[i] -1 ] > H[B[i] -1 ]:
        G[ B[i] -1 ] = 0
    elif H[ A[i] -1] == H[ B[i] -1 ]:
        G[ A[i] -1 ] = 0
        G[ B[i] -1 ] = 0
    else:
        G[A[i] -1 ] = 0

print( G.count(1) )

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

using namespace std;

int main(void){
    int N,M;
    cin >> N >> M;
    
    vector<int> H(N);
    
    for(int i=0;i<N;i++){
        cin >> H.at(i);
    }
    
    vector<vector<int>> ab(N,vector<int>(0));
    
    for(int i=0;i<M;i++){
        int A,B;
        cin >> A >> B;
        A-=1;
        B-=1;
        ab.at(A).push_back(B);
        ab.at(B).push_back(A);
    }
    
    int ans=0;
    
    for(int i=0;i<N;i++){
        bool isgood=true;
        for(int j=0;j<ab.at(i).size();j++){
            if(H.at(ab.at(i).at(j))>=H.at(i)){
                isgood=false;
                break;
            }
        }
        
        if(isgood){
            ans++;
        }
    }
    
    cout << ans << endl;
    
}


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


using namespace std;

int main()
{
        int n; cin>>n;
        string s,t; cin>>s>>t;
        string out = "";
        for(int i = 0 ; i<n ;i++)
        {
            out+=s[i];
            out+=t[i];
        }
        cout<<out<<endl;
        return 0;
}


Measured memory_bytes: 256
def digits(x):
    ans = 0
    for i in range(4,-1,-1):
        ans += x//(10**i)
        x = x - ((10**i)*(x//(10**i)))
    return ans

[N,A,B] = list(map(int,input().split()))
data = []
for i in range(1,N+1):
    if A <= digits(i) <= B:
        data.append(i)

print(sum(data))

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

int main(void) {
  int A, B, Q;
  cin >> A >> B >> Q;
  vector<long long> s(A + 2), t(B + 2), x(Q);
  s[0] = t[0] = -1e18;
  s[A + 1] = t[B + 1] = 1e18;
  for (int i = 0; i < A; i++) {
    cin >> s[i + 1];
  }
  for (int i = 0; i < B; i++) {
    cin >> t[i + 1];
  }
  for (int i = 0; i < Q; i++) {
    cin >> x[i];
  }

  for (int i = 0; i < Q; i++) {
    long long ret = 1e18;
    auto it1 = lower_bound(s.begin(), s.end(), x[i]);
    auto it2 = lower_bound(t.begin(), t.end(), x[i]);
    cerr << *it1 << endl;
    cerr << *it2 << endl;
    {
      auto it1 = lower_bound(s.begin(), s.end(), x[i]);
      auto it2 = lower_bound(t.begin(), t.end(), x[i]);
      ret = min(ret, abs(max(*it1, *it2) - x[i]));
    }
    {
      auto it1 = lower_bound(s.begin(), s.end(), x[i]);
      auto it2 = lower_bound(t.begin(), t.end(), x[i]);
      it1--;
      it2--;
      ret = min(ret, abs(min(*it1, *it2) - x[i]));
    }
    {
      auto it1 = lower_bound(s.begin(), s.end(), x[i]);
      auto it2 = lower_bound(t.begin(), t.end(), x[i]);
      it2--;
      long long d = min(abs(*it1 - x[i]), abs(*it2 - x[i]));
      ret = min(ret, abs(*it1 - x[i]) + abs(*it2 - x[i]) + d);
    }
    {
      auto it1 = lower_bound(s.begin(), s.end(), x[i]);
      auto it2 = lower_bound(t.begin(), t.end(), x[i]);
      it1--;
      long long d = min(abs(*it1 - x[i]), abs(*it2 - x[i]));
      ret = min(ret, abs(*it1 - x[i]) + abs(*it2 - x[i]) + d);
    }
    cout << ret << endl;
  }

  return 0;
}

Measured memory_bytes: 3712
n, k = map(int, input().split())

l = [0 for _ in range(1000000)]

rui = 0

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


for i in range(len(l)):
    rui += l[i]

    if rui >= k:
        print(i)
        break

#print()


Measured memory_bytes: 12964
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
int n, k;
string s;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> k >> s;

  int d = 0;
  FOR(i, 1, n) {
    if(s[i] != s[i - 1]) d++;
  }

  cout << (n - 1 - d) + min(k * 2, d) << endl;
}


Measured memory_bytes: 3796
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in ll read()
    {
        ll x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
        x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
    }
    in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
    in int gs(char *s) {char c,*t=s;while(c=gc(),c<=32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
    in void flush() {if(C>1<<22) ot();}
    template <typename T>
    in void write(T x,char t)
    {
        int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
    }
    in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
#define pb push_back
const int N=1e3+5,p=1e9+7;
int n,m,res,fa[N],pw[N<<1];ll f[N<<1],k,ans;
struct did{int u,v,w;}e[N<<1];
in void M(int &x) {x-=p;x+=x>>31&p;}
in int find(int x) {return x^fa[x]?fa[x]=find(fa[x]):x;}
in ll kruskal(int c)
{
	ll s=0;
	for(int i=1,u,v;i<=m&&c<n-1;i++) if((u=find(e[i].u))^(v=find(e[i].v)))
	c++,s+=e[i].w,fa[u]=v;
	return s;
}
int main()
{
	n=read(),m=read(),k=read();pw[0]=1;for(int i=1;i<=m;i++) M(pw[i]=pw[i-1]<<1);
	for(int i=1;i<=m;i++) e[i]={(int)read(),(int)read(),(int)read()};
	sort(e+1,e+m+1,[](did a,did b){return a.w<b.w;});
	for(int i=1;i<=n;i++) fa[i]=i;
	ans=kruskal(0);if(ans>k) return write("0"),ot(),0;
	if(ans==k) M(res=1ll*(pw[n-1]+p-2)*pw[m-n+1]%p);
	for(int i=1;i<=m;i++) {for(int j=1;j<=n;j++)fa[j]=j;fa[e[i].u]=fa[e[i].v],f[i]=kruskal(1)+e[i].w;}
	sort(f+1,f+m+1);for(int i=n;i<=m;i++) if(f[i]==k) M(res+=pw[m-i+1]);
	write(res,'\n');
	return ot(),0;
}
//Author: disangan233


Measured memory_bytes: 3608
#include<stdio.h>
int main(){
    int a, b, c, p;
    scanf("%d %d %d",&a, &b, &c);
    if(a > b){
        p = a;
        a = b;
        b = p;
    }
    if(b > c){
        p = b;
        b = c;
        c = p;
    }
    if(a > b){
        p = a;
        a = b;
        b = p;
    }
    printf("%d %d %d\n", a, b, c);
    return 0;
}


Measured memory_bytes: 2100
def main():
    N, M, Q = map(int, input().split())
    items = []

    for i in range(Q):
        items.append(tuple(map(int, input().split())))

    # print(items)

    def list_a(a: list):
        if len(a) == N:
            return [a]
        else:
            arr = []
            if len(a) == 0:
                last = 1
            else:
                last = a[-1]

            for i in range(last, M + 1):
                arr += list_a(a + [i])
            return arr

    candidates = list_a([])
    # print(candidates)

    max_score = -100
    max_A = None

    for A in candidates:
        score = 0
        for a, b, c, d in items:
            if A[b-1] - A[a-1] == c:
                score += d

        if score > max_score:
            max_score = score
            max_A = A

    print(max_score)


if __name__ == '__main__':
    main()


Measured memory_bytes: 23264
import java.io.*;
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    try{
      String w=br.readLine();
      String line;
      int count=0;
      while((line=br.readLine())!=null){
        if(line.equals("END_OF_TEXT")) break;
        String lowerLine=line.toLowerCase();
        String[] text=lowerLine.split(" ");
        for(String t:text){
          if(t.endsWith(".")){
            t=t.substring(0,t.length()-1);
          }
          if(t.equals(w)) count++;
        }
      }
      System.out.println(count);
    }catch(IOException e){
      System.out.println(e);
    }
  }
}



Measured memory_bytes: 24268