akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

double t, x;
int main() {
  cin >> t >> x;
  printf("%.10f\n", t / x);
  
  return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S, T = input().split()
A, B = MAP()
U = input()
if U == S:
	print(A - 1, B)
if U == T:
	print(A, B - 1)


Measured memory_bytes: 5832
K, A, B = map(int, input().split())

if (B - A <= 2) or (K <= (A-1)):
    print(K+1)
else:
    if (K-A+1)%2 == 0:
        print((K-A+1)//2 * (B-A) + A)
    else:
        print((K-A+1)//2 * (B-A) + A+1)


Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var NK = ReadLine().Split().Select(int.Parse).ToArray();
        var N = NK[0];
        var K = NK[1];

        var ans = 0.0;
        for (int i = 1; i <= N; i++)
        {
            var d = 0;
            while (K > i << d)
            {
                d++;
            }
            ans += Pow(0.5,d)/N;
        }
        WriteLine(ans);
    }
}


Measured memory_bytes: 13268
n = int(input())
A = list(map(int, input().split()))

# m = 0
# t = 0

# for i in range(1, n):
#     count = A.count(i)
#     print(count)
#     m += count
#     t = i
#     if m == n - 1:
#         break
# for _ in range(t, n):
#     print(0)

B = [0] * n
for i in A:
    B[i-1] += 1
for i in B:
    print(i)


Measured memory_bytes: 32132
'use strict';

function main(stdin) {
  const input = stdin.split('\n')//.map(v => parseInt(v, 10));
  const N = Number(input[0]);
  const p = input[1].split(' ').map(v => parseInt(v, 10));

  let cnt = 0;

  for (let i = 1; i < N - 1; ++i) {
    const ary = [p[i - 1], p[i], p[i + 1]];
    if (p[i] === ary.sort((a, b) => a - b)[1]) ++cnt;
  }
  
  console.log(cnt);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

namespace ABC150
{
    class C
    {
        static void Main(string[] args)
        {
            int ans = 0;
            int a = 0, b = 0;
            int n = int.Parse(Console.ReadLine());
            int[] p = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] q = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i = 0; i < n; i++)
            {
                a += (p[0]-1)*Fanc2(n-i-1);
                p = Func1(p);
            }
            for (int i = 0; i < n; i++)
            {
                b += (q[0] - 1) * Fanc2(n-i-1);
                q = Func1(q);
            }
            Console.WriteLine(a > b ? a - b : b - a);
        }
        static int[] Func1(int[] a)
        {
            if (a.Length == 1) { return new int[1]{ 1 }; }
            int h = a[0];
            int[] ret = new int[a.Length - 1];
            for (int i = 0; i < a.Length-1; i++)
            {
                ret[i] = a[i + 1] > h ? a[i + 1] - 1 : a[i + 1];
            }
            return ret;
        }
        static int Fanc2(int n)
        {
            if (n == 0) { return 1; }
            return Fanc2(n - 1) * n;
        }
    }
}


Measured memory_bytes: 11348
//bismillahir rahmanir rahim
#include <iostream>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <iterator>
#define           ll                         long  long
#define           lf                         double 
#define           pb(x)                      push_back(x)
#define           ull                        unsigned long long
#define           sfl(a)                     scanf("%lld",&a)
#define           sf(a)                      scanf("%d",&a)
#define           pf(a)                      printf("%d\n",a)
#define           pfl(a)                     printf("%lld\n",a)
#define           pdl(a)                     printf("%llf\n",a)
#define           FOR(x,n)                   for(int x=1;x<=n;++x)
#define           vii                        vector< ll > v
#define           pi                         3.14159265359
#define           mex                        10000000
#define           pii                        pair< ll , ll >
#define           mem(m,a)                     memset( m, a,sizeof m)
#define           mp(a,b)                    make_pair(a,b)
#define           maxn                       100000
#define           mod                        1000000007
#define 		  INF						 1e17
#define 		  f1 						 first
#define 		  f2						 second
#define 		  all(v)					 v.begin(),v.end()
#define           PI                         acos(-1)
#define           printminusone              print("-1\n")

using namespace std;



int main(){
   
  ll x , y , a, b, r;

  sfl ( x ) , sfl ( y ), sfl ( a ), sfl ( b ), sfl ( r );

  if ( a <=0 or b <= 0 ){

  		printf("No\n");
  }

  else{

  	if ( a+r <= x and b+r <= y ){

  		printf("Yes\n");
  	}

  	else{

  		printf("No\n");
  	}
  }
}





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

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

    int l = s.size();
    if (k >= l){
        cout << s << endl;
    }else{
        cout << s.substr(0,k)+"...";
} 
}




Measured memory_bytes: 3628
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	vector<string>c(3);
	rep(i, 3)cin >> c[i];
	rep(i, 3)rep(j, 3)if (i == j)cout << c[i][j];
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
//debug() << imie(x) imie(y);
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int main()
{
int n,x=0,max1=0;char s[100];
cin>>n>>s;
for(int i=0;i<n;i++)
{
	if(s[i]=='I')
	++x;
	else if(s[i]=='D')
	--x;
	max1=max(x,max1);
}

cout<<max1;
return 0;
}


Measured memory_bytes: 256
sx,sy,i,x,y,n;
xx[12],yy[12];
q[9999],t,h,p,ok,c,k;
char *d="22210/.../01";
main()
{
  for(;scanf("%d%d",&sx,&sy),sx;puts(ok?"OK":"NA")){
    for(ok=t=h=i=!scanf("%d",&n);i++<n;)scanf("%d%d",xx+i,yy+i);
    for(p=q[t++]=sx*10+sy;t!=h&!ok;p=q[h++]){
      c=p/100;
      if(c&&abs(xx[c]-p/10%10)>1|abs(yy[c]-p%10)>1)continue;
      ok=c==n;
      for(i=0;i<12;x>=0&x<10&y>=0&x<10?q[t++]=(c+1)*100+x*10+y:0)
        x=p/10%10+d[i]-48,y=p%10+d[11-i++]-48;
    }
  }
}

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

int main() {
    int N;
    int d[100];
    cin >> N;
    for (int i = 0; i < N; ++i) scanf("%d", &d[i]);

    set<int> values; // insert するときに重複を取り除いてくれます
    for (int i = 0; i < N; ++i) {
        values.insert(d[i]); // 挿入します
    }

    // set のサイズを出力します
    cout << values.size() << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int a,b=0,c,d=0,aa[220000];
string s;
signed main()
{
	cin>>a;
	rep(i,a){
		cin>>aa[i];
		if(aa[i]>b){
			d=b;
			b=aa[i];
			c=i;
		}else if(aa[i]>d){
			d=aa[i];
		}
	}
	rep(i,a){
		if(i!=c){
			cout<<b<<endl;
		}else{
			cout<<d<<endl;
		}
	}
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  char s[15];
  cin>>n;
  for(int i=1;i<=n;i++) cin>>s[i];
  cin>>k;
  for(int i=1;i<=n;i++) if(s[k]!=s[i]) s[i]='*';
  for(int i=1;i<=n;i++) cout<<s[i];
  cout<<'\n';
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

class ZEN{
    public:
    vector<ll>v;
    ll N, K;
    ZEN(ll n, ll k){
        v = vector<ll>(n + 1, 0);
        N = n;
        K = k;
    }
    void next(){
        v[0]++;
        for(ll i = 0; i < N; i++){
            if(v[i] == K){
                v[i] = 0;
                v[i + 1]++;
            }
        }
    }
    bool end(){
        return v[N] != 0;
    }
};

int main(){
    ll N;
    cin >> N;
    ll ans = 0;
    ll a[20];
    rep(i, N)cin >> a[i];
    for(ZEN zen(N, 3); !zen.end(); zen.next()){
        ll tmp = 1;
        rep(i, N)tmp *= a[i] + zen.v[i] - 1;
        if(tmp % 2 == 0)ans++;
    }
    cout << ans << endl;
    
    return 0;
}

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

using namespace std;

int main(void) {
  int N= 0;
  cin >> N;
  vector<int> A;
  int a;
  for (int i = 0; i < N ; i++){
    cin >> a;
    A.push_back(a);
  }
  int r = 0;
  int m = 1;
  while(m == 1) {
    int t = 0;
    for (int i = 0; i < N ; i++){
      t += A[i] % 2;
    }
    if (t == 0) {
      r++;
      for (int i = 0; i < N ; i++){
        A[i] /= 2;
      }
    } else {
      m = 0;
    }
  }
  cout << r << endl;
  return 0;
}

Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for a in A:
    s = 0
    for i in range(M):
        s += a[i] * B[i]
    if s + C > 0:
        ans += 1
print(ans)

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> vec(H);
    for (int vi = 0; vi < H; vi++) {
        cin >> vec[vi];
    }
    string line = "";
    for (int x=0; x < W+2; x++) {
        line += "#";
    }
    cout << line << endl;
    for (int each = 0; each < H; each ++) {
        cout << "#" << vec[each] << "#" << endl;
    }
    cout << line << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
const int INF=1001001001;

int main() {
  string s;
  cin>>s;
  int n=s.size();
  stack<char>k;
  for(int i=0;i<n;i++){
    if(k.empty()){k.push(s[i]);}
    else if(s[i]=='S'){k.push(s[i]);}
    else if(s[i]=='T'){
      if(k.top()=='T'){k.push('T');}
      else if(k.top()=='S'){k.pop();}
    }
    //cout<<k.top()<<endl;
  }
  cout<<k.size()<<endl;
  return 0;
}

Measured memory_bytes: 3720
package main

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

const BUFSIZE = 10000000

var rdr = bufio.NewReaderSize(os.Stdin, BUFSIZE)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	v := NextLineInt()
	c := NextLineInt()

	var ans int

	for i := 0; i < n; i++ {
		ans += Max(0, v[i]-c[i])
	}

	fmt.Println(ans)
}

func NextLineInt() []int {
	buf := make([]byte, 0, BUFSIZE)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}

		buf = append(buf, l...)

		if !p {
			break
		}
	}
	str := strings.Split(string(buf), " ")
	l := len(str)

	ret := make([]int, l)

	for i := range str {
		// ret[i], ok = strconv.Atoi(str[i])
		v, ok := strconv.Atoi(str[i])

		if ok == nil {
			ret[i] = v
		}
	}

	return ret
}

func Bool2Int(b bool) int {
	if b {
		return 1
	} else {
		return 0
	}
}

func Abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

func Min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func Max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func Distance(a, b int) int {
	return Abs(a - b)
}


Measured memory_bytes: 5632
import java.util.*;
public class Main{


public static void main (String []args)
{
	Scanner scan=new Scanner(System.in);
	//long t=scan.nextLong();
	//long ways[]=new long[1000000000];
	//ways[1]=1;
	//ways[i]=ways[i-1]*2;
	
	//while(t-->0){
         int n=scan.nextInt();
         int k=scan.nextInt();
         int a[]=new int[n];
        // int dp[]=new int[n];
        for(int i=0;i<n;i++)
        a[i]=scan.nextInt();
       
	int dp[]=new int[n];
	for(int i=1;i<n;i++)
        dp[i]=Integer.MAX_VALUE;
	
	dp[0]=0;
	for(int i=0;i<n;i++)
	{  
		for(int j=i+1;j<n&&j<=i+k;j++)
		{
		dp[j]=Math.min(dp[j],dp[i]+Math.abs(a[j]-a[i]));
	     }
		}
         
         System.out.println(dp[n-1]);
//}//
}
}


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

int main(){
    int n,l,r;
    cin >> n;
    int sum = 0;
    for (int i = 0;i < n;i++){
        cin >> l >> r;
        sum += r - l + 1;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#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 isin(x,l,r) ((l) <= (x) && (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 = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int A, B, M;
    cin >> A >> B >> M;
    vector<int> a(A), b(B);
    cin >> a;
    cin >> b;
    int ans = INF;
    rep(i, M) {
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        ans = min(ans, a[x] + b[y] - c);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (a[0] + b[0] < ans)
        cout << a[0] + b[0] << endl;
    else
        cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>

int n,c;
int d[100][100];
int cc[510][510];

int f(int k,int s){
  int res=0;
  rep(i,c){
    res+=cc[k][i]*d[i][s];
  }

  return res;
}

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

  cin>>n>>c;
  rep(i,c){
    rep(j,c){
      cin>>d[i][j];
    }
  }

  rep(i,n){
    rep(j,n){
      int x;
      cin>>x;
      cc[(i+j)%3][x-1]++;
    }
  }

  int ans=INF;
  rep(i,c){
    rep(j,c){
      rep(k,c){
        if(i==j||j==k||k==i) continue;
        int res=0;
        res+=f(0,i);
        res+=f(1,j);
        res+=f(2,k);
        ans=min(ans,res);
      }
    }
  }

  cout<<ans<<endl;


}

Measured memory_bytes: 256
def solve(n, m, list1, listp):
    cnt = 0
    loopflag = 0
    for i in range(2**n):
        list2 = [(i%(2**(j+1)))//(2**j) for j in range(n)]  #スイッチリスト生成
        for j in range(m):  #j番目の電球について
            s = sum([list2[k] for k in list1[j][1:]])
            if s%2 != listp[j]:
                loopflag = 1
                break
        if loopflag == 0:
            cnt += 1
        loopflag = 0
    return cnt

n, m = map(int, input().split())
list1 = []
for i in range(m):
    list1 += [list(map(int, input().split()))]
    list1[i][1:] = list(map(lambda x: x-1, list1[i][1:]))
listp = list(map(int, input().split()))
print(solve(n, m, list1, listp))

Measured memory_bytes: 42352
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
typedef vector<int> vi;
typedef vector<ll> vl;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}


int main (){
    ll a,b,n;
    cin >> a >> b >> n;
    ll x=min(b-1,n);
    ll ans=floor(a*x/b);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3592
N, X = map(int, input().split())
A = list(map(int, input().split()))

ans = max(A[0] - X, 0)
B = [min(A[0], X)]
for i in range(1, N):
  var = max(A[i] + B[-1] - X, 0)
  ans += var
  B.append(A[i] - var)
  
print(ans)
#print(B)

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


int main(){
  int N ; 
  cin >> N ; 
  set<string> s ; 
  
  for (int i = 0 ; i <N ; i++){
    string k ; 
    cin >> k ; 
    s.insert(k) ; 
  }
  
  cout << s.size() << endl ;
}

Measured memory_bytes: 19212
package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	var n, v int
	if a < b {
		n = b
		v = a
	} else {
		n = a
		v = b
	}

	for i := 0; i < n; i++ {
		fmt.Print(v)
	}
	fmt.Println("")
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	int n;
	cin >> n;
	vector<int> m(100000, 0);
	rep(i, n){
		int temp;
		cin >> temp;
		m[temp-1]++;
	}
	
	int l = 0;
	rep(i, 100000) if(m[i] != 0) l++;

	if(l%2 == 1) cout << l << endl;
	else cout << l-1 << endl;
		
	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;

  vector<pair<int, int>> v;
  rep(i, N) {
    int a, b;
    cin >> a >> b;
    v.emplace_back(a, b);
  }

  sort(v.begin(), v.end());

  priority_queue<int> queue;

  ll ans = 0;
  int pos = 0;
  for (int m = 1; m <= M; ++m) {
    while (pos < N) {
      if (v[pos].first > m)
        break;
      queue.push(v[pos].second);
      pos++;
    }
    if (!queue.empty()) {
      ans += queue.top();
      queue.pop();
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1908
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int a, b, c;
	int tmp;

	scanf("%d%d%d", &a, &b, &c);
	if (a > b) tmp = a, a = b, b = tmp;
	if (b > c) {
		tmp = b, b = c, c = tmp;
		if (a > b) tmp = a, a = b, b = tmp;
	}
	printf("%d %d %d\n", a, b, c);
	return 0;
}


Measured memory_bytes: 2052
#include<stdio.h>
int f(int a){
return (0<a && a<13);
}
int main(){
  int n,m;
  scanf("%d",&n);
  m=n/100;n=n%100;
  int p=0;
  if(f(m))p+=2;
  if(f(n))p++;
  switch(p){
    case 0: {
      printf("NA");
      break;
    }
    case 1:{
      printf("YYMM");
      break;
    }
    case 2:{
      printf("MMYY");
      break;
    }
    case 3:{
      printf("AMBIGUOUS");
      break;
    }
  }
  return 0;
}



Measured memory_bytes: 128
import sys


INF = sys.maxsize

N, K = (int(x) for x in input().split())
heights = [int(x) for x in input().split()]

memo = [INF] * N

for i in range(N - 1, -1, -1):
  if i == N - 1:
    # ゴールからゴールの距離を0で初期化
    memo[i] = 0
    continue
  cost = INF
  for j in range(1, K + 1):
    # 範囲外
    if i + j >= N:
      continue
    cost = min(cost, memo[i + j] + abs(heights[i] - heights[i + j]))
  memo[i] = cost             

print(memo[0])


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

const ll MOD = 1000000007;

int main(){
	ll n,k;
	cin >> n >> k;
	vector<ll> plus;
	vector<ll> minus;
	rep(i,n){
		ll a;
		cin >> a;
		if(a < 0){
			minus.push_back(a);
		}else{
			plus.push_back(a);
		}
	}
	ll S = plus.size();
	ll T = minus.size();
	ll ans = 1;
	if(n == k){
		rep(i,S) {
			ans *= plus[i];
			ans %= MOD;
		}
		rep(i,T){
			ans *= minus[i];
			ans %= MOD;
		}
		if(ans < 0){
			cout << ans + MOD << endl;
		}else{
			cout << ans << endl;
		}
	} else if (S == 0 && k % 2 == 1){
		vector<ll> temp;
		rep(i,S) temp.push_back(plus[i]);
		rep(i,T) temp.push_back(-minus[i]);
		sort(temp.begin(),temp.end());
		rep(i,k){
			ans *= temp[i];
			ans %= MOD;
		}
		cout << (-ans % MOD) + MOD << endl;
	}else{
		sort(plus.begin(),plus.end());
		sort(minus.rbegin(),minus.rend());
		vector<ll> temp;
		if(k % 2 == 1){
			ans *= plus.back();
			plus.pop_back();
		}
		while(plus.size() >= 2){
			ll x = plus.back();
			plus.pop_back();
			x *= plus.back();
			plus.pop_back();
			temp.push_back(x);
		}
		while(minus.size() >= 2){
			ll x = minus.back();
			minus.pop_back();
			x *= minus.back();
			minus.pop_back();
			temp.push_back(x);
		}
		sort(temp.rbegin(),temp.rend());
		rep(i,k/2){
			ans *= temp[i] % MOD;
			ans %= MOD;
		}
		cout << ans << endl;
	}
	
    return 0;
}

Measured memory_bytes: 6540
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <sstream>
#include <cstring>
#include <bitset>
#include <climits>
 
using namespace std;
#define  AS(arr)  (sizeof(arr)/sizeof(arr[0]))
#define ALL(c) (c).begin(),(c).end() 
#define SIZE(a) int((a).size())
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define REP(i,n) for(int i=0;i<(int)n;++i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef long long LL;
int main(void){
    string s;
    cin >> s;
    string ret;
    EACH(it, s)
    {
        if(*it == 'B')
        {
            if(!ret.empty())
                ret.pop_back();
        }
        else
        {
            ret += *it; 
        }
    }
    
    cout << ret << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
ll a[200005];
ll b[200005];
ll h[200005];
ll dp[200005];
typedef pair<int, int> P;

int main() {
	ll n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	dp[0] = 0;
	dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	
	cout << dp[n -1] << endl;
	return 0;
}

Measured memory_bytes: 3584
#include<iostream>

using namespace std;

int main()
{
  int a,b;  //takahashi
  int c,d;  //aoki
  
  cin>>a>>b>>c>>d;
  
  int buf1=a;
  int buf2=c;
  
  bool flag1=false;
  bool flag2=false;
  
  while(true)
  {
    buf2-=b;
    
    if(buf2<=0)
    {
      flag1=true;
      break;
    }
    
    buf1-=d;
    
    if(buf1<=0)
    {
      flag2=true;
      break;
    }
  }
  
  if(flag1)
    cout<<"Yes"<<endl;
  else if(flag2)
    cout<<"No"<<endl;
  
  return 0;
}
      


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

void solve(){
    int n, x, y;
    cin >> n >> x >> y;
    
    map<int, int> mp; //(最短距離, 組み合わせ数)
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            //min((X,Yを通らない路), (i-X-Y-jの路), (i-Y-X-jの路))が最短距離になる
            int diff = min({abs(i-j), abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)});
            mp[diff]++;
        }
    }
    for(int k=1; k<n; k++) cout << mp[k] << endl;
}

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

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

vector<int> p, q, r, b;

int lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

int dfs(int v)
{
    if (v == -1) return 1;    
    int lw = dfs(r[v]), rw = dfs(b[v]);
    int l = lcm(p[v] * lw, q[v] * rw);
    return l / p[v] + l / q[v];
}
 
void init(int N)
{
    p.resize(N); q.resize(N);
    r.resize(N); b.resize(N);
}

int main()
{
    int N;
    while (cin >> N, N) {
        init(N);
        bool used[MAX_N] = {};
        for (int i = 0; i < N; i++) {
            cin >> p[i] >> q[i] >> r[i] >> b[i];
            r[i]--; b[i]--;
            if (r[i] >= 0) used[r[i]] = 1;
            if (b[i] >= 0) used[b[i]] = 1;
            int gcd = __gcd(p[i], q[i]);
            p[i] /= gcd;
            q[i] /= gcd;
        }
        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                cout << dfs(i) << endl;
                break;
            }            
        }
    }
    return 0;
}

Measured memory_bytes: 1216
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<iomanip>
#include<cstring>
#include<string>
#include<set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll = long long int;

const ll INF = 1<<30;
const ll LINF = 1LL<<60;
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; }

int main(void) {
    int x, n; cin >> x >> n;
    vector<int> p(n);
    REP(i, n) cin >> p[i];
    int range = 0, l, r;
    bool t1, t2;
    while (1) {
        t1 = true; t2 = true;
        for (int v : p) {
            if (x + range == v) {
                t1 = false;
            }
            if (x - range == v) {
                t2 = false;
            }
        }
        if (t1) r = x + range;
        if (t2) l = x - range;
        if (t1 || t2) break;
        range++;
    }
    if (t2) cout << l << endl;
    else if (t1) cout << r << endl;
}

Measured memory_bytes: 3624
using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		while(true){
			var l=long.Parse(Console.ReadLine());
			if(l==0)break;
			Sol mySol =new Sol(l);
			mySol.Solve();
		}
	}
}

class Sol{
	public void Solve(){
		if(L==1){
			Console.WriteLine(1);
			return;
		}
		
		Dictionary<long,long> pr=PrimDec(L);
		Dictionary<long,long> highest=new Dictionary<long,long>();
		foreach(long k in pr.Keys){
			highest.Add(k,(long)Math.Pow(k,pr[k]));
		}
		
		
		long Total=0;
		for(long i=1;i*i<=L;i++){
			if(L%i!=0)continue;
			long j=L/i;
			
			long cnt=1;
			foreach (long k in highest.Keys){
				if(i%highest[k]==0){
					cnt*=(pr[k]+1);
				}
			}
			Total+=cnt;
			
			if(j==i)continue;
			cnt=1;
			foreach (long k in highest.Keys){
				if(j%highest[k]==0){
					cnt*=(pr[k]+1);
				}
			}
			Total+=cnt;
		}
		
		long Ans=(Total-1)/2+1;//(L,L)以外は必ず2回カウントされる
		Console.WriteLine(Ans);
	}
	long L;
	public Sol(long l_){
		L=l_;
	}

	Dictionary<long,long> PrimDec(long A){
	 	Dictionary<long,long> D=new Dictionary<long,long>();
	 	if(A==1)return null;
	 	long rem=A;
	 	for(long i=2;i<=(long)Math.Sqrt((double)A);i++){
	 		if(rem%i==0){
	 			long cnt=0;
	 			while(rem%i==0){cnt++;rem/=i;}
	 			D.Add(i,cnt);
	 		}
	 		if(rem==1)break;
	 	}
	 	if(rem!=1)D.Add(rem,1);
	 	return D;
	}



	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}

Measured memory_bytes: 6352
#include <bits/stdc++.h>
using namespace std;
int flag[101];
 
int main() {
  int N;
  cin>>N;

  for(int i=0;i<N;i++){
  	int d;
    cin>>d;
    flag[d]=1;
  }
  
  int sum=0;
  for(int i=0;i<101;i++){
   sum+=flag[i];
  }
  
  cout<<sum<<endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    rep(i, 0, n) {
        int a;
        cin >> a;
        while (a % 2 == 0) {
            a /= 2;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;


}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
	int N = Integer.parseInt(scan.next());
	int K = Integer.parseInt(scan.next());
	int[] D = new int[K];
	for (int i = 0; i < K; i++) {
	    D[i] = Integer.parseInt(scan.next());
	}

	int money = N;
	for (; money <= 100000; money++) {
	    if(contains(money, D)) continue;
	    else break;
	}

	System.out.println(money);
	scan.close();
    }

    private static boolean contains(int x, int[] D) {
	boolean ans = false;
	while(x / 10 > 0) {
	    int r = x % 10;
	    x = x / 10;
	    for (int i = 0; i < D.length; i++) {
		if(r == D[i]) {
		    ans = true;
		    break;
		}
	    }
	    if(ans) break;
	}
	if(ans == false) {
	    for (int i = 0; i < D.length; i++) {
		if(x == D[i]) {
		    ans = true;
		    break;
		}
	    }
	}
	return ans;
    }
}


Measured memory_bytes: 22612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String ans = null;

		if(n>=1000) {
			ans="ABD";
			n=n-1000;
		}

		else {
			ans="ABC";
		}


System.out.println(ans);






	}
}

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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 100 + 5 , K = 1e5 + 5 , mod = 1e9 + 7;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);


int n , k;
int dp[N][K];
int  a[N];


void solve(int testCase){

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

    for(int i = 1 ; i <= n ; i ++){
            scanf("%d" , &a[i]);
    }

    dp[0][0] = 1;

    for(int i = 1 ; i <= n ; i ++){

            for(int rem = 1 ; rem <= k ; rem ++){
                    dp[i-1][rem] += dp[i-1][rem-1];
                    dp[i-1][rem] %= mod;
            }

            for(int rem = 0 ; rem <= k ; rem ++){

                    int take = min(rem , a[i]);
                            dp[i][rem] += ((dp[i-1][rem] - dp[i-1][rem - take - 1])%mod + mod) %mod;

                    dp[i][rem] %= mod;
            }
    }

    printf("%d\n" , dp[n][k]);

}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 41216
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		int w, n;
		w = n = 0;

		Main main = new Main();
		ArrayList<Lane> lanes = new ArrayList<Main.Lane>();
		ArrayList<Rule> rules = new ArrayList<Main.Rule>();

		try {
			w = Integer.parseInt(br.readLine());
			n = Integer.parseInt(br.readLine());

			for (int i = 1; i <= w; i++) {
				lanes.add(main.new Lane(i));
			}

			while ((s = br.readLine()) != null) {
				rules.add(main.new Rule(s));
			}
		} catch (IOException e) {
			e.printStackTrace();
		}

		for (Lane l : lanes) {
			for (Rule r : rules) {
				l.applyRule(r);
			}
		}
		for (int i = 1; i <= w; i++) {
			for (Lane l : lanes) {
				if (l.getCurrentLane() == i)
					System.out.println(l.getInitialLane());
			}
		}
	}

	class Lane {
		private int initial;
		private int current;

		Lane(int lane) {
			this.initial = this.current = lane;
		}

		int getInitialLane() {
			return initial;
		}

		int getCurrentLane() {
			return current;
		}

		void applyRule(Rule rule) {
			current = rule.getNewLane(current);
		}
	}

	class Rule {
		private ArrayList<Integer> pair = new ArrayList<Integer>();

		Rule(int a, int b) {
			pair.add(a);
			pair.add(b);
		}

		Rule(String s) {
			int a = Integer.parseInt((s.split(",")[0]));
			int b = Integer.parseInt((s.split(",")[1]));
			pair.add(a);
			pair.add(b);
		}

		int getNewLane(int lane) {
			if (pair.contains(lane)) {
				return (lane == pair.get(0) ? pair.get(1) : pair.get(0));
			} else {
				return lane;
			}

		}
	}
}

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

using namespace std;

typedef long long ll;

void swap(char &a,char &b)
{
    char tmp =a;
    a = b;
    b = tmp;
}

int main()
{
    ios_base::sync_with_stdio(0);
    
    int n;
    cin>>n;
    string str;
    cin>>str;
    int i,j;
    i=0,j=n-1;
    int cnt=0;
    while(i<j){
        if(str[i]=='W'&&str[j]=='R'){
            swap(str[i],str[j]);
            ++cnt;
            ++i;
            --j;
        }
        else if(str[i]=='R'){
            ++i;
        }
        else{
            --j;
        }
    }
    cout<<cnt;
}



Measured memory_bytes: 3764
<?php
// 標準入力取得
  $line1 = fgets(STDIN);
  $line1 = str_replace(PHP_EOL, '', $line1);

  // $nums = preg_split('/\s+/', $line);
  // $line2 = fgets(STDIN);
  // $line2 = str_replace(PHP_EOL, '', $line2);
  echo substr($line1, 0, 3);

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()

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

const long long INF = 1LL << 60;

int main()
{
    int M;
    cin >> M;

    cout << 24 + (24 - M) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int *A = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    int l = 0;
    int r = 1;

    long long sum = 0;
    int bits = A[l];
    while (l < n) {
        while (r < n && ((bits & A[r]) == 0)) {
            bits |= A[r];
            r++;
        }
        sum += r - l;
        bits &= ~A[l];
        l++;
        if (r == l) {
            bits |= A[l];
            r++;
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main() {
	int n, r, min_r, profit;

	cin >> n;
	cin >> min_r >> r;
	profit = r - min_r;
	min_r = min(min_r, r);

	for (int i = 2; i < n; i++) {
		cin >> r;
		profit = max(profit, r - min_r);
		min_r = min(min_r, r);
	}
	cout << profit << endl;
	return 0;
}

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

const int MAX_N = 1e5 + 5;
int n, ans;
int Arr[MAX_N];
unordered_map <int, int> cnt[2][2], Mark;
unordered_map <int, int>::iterator it;

void calc(int x) {
	for (int i = 0; i < n; i++)
		cnt[x][i & 1][Arr[i]]++;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &Arr[i]);
		Mark[Arr[i]]++;
	}

	calc(0);
	sort(Arr, Arr + n);
	calc(1);

	for (it = Mark.begin(); it != Mark.end(); it++)
		ans += abs(cnt[0][0][it->first] - cnt[1][0][it->first]);

	printf("%d", ans >> 1);
	return 0;
}

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

const int Nmax=200010;

int main() {
	int Q,flag;
	ll A,B,C;
	
	cin >> Q;
	for(int i=0;i < Q;i++){
		cin >> A >> B;
      	flag=0;
	  	
		if(A==B){ cout << 2*A-2 << endl;flag=1;}
		if(abs(A-B)==1){ cout << 2*min(A,B)-2 << endl;flag=1;}
		
		if(flag==0){
			C = sqrt(A*B);//C^2 < ABを満たす最大の整数C
      		if(C*C==A*B) C=C-1;
			if(C*(C+1) >= A*B) cout << 2*C-2 << endl;
			else cout << 2*C-1 << endl;
       	}
	}
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second

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

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);

  int n, M, Q;
  cin >> n >> M >> Q;
  vector<vector<int>> v(n+1, vector<int>(n+1,0));
  for(int i = 0; i < M; i++){
    int l, r;
    cin >> l >> r;
    v[l][r]++;
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
    }
  }
  for(int qq = 0; qq < Q; qq++){
    int p, q;
    cin >> p >> q;
    cout << v[q][q] - v[q][p-1] - v[p-1][q] + v[p-1][p-1] << "\n";
  }

  return 0;
}



Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size()){cout << a[i];cout << (i == a.size() - 1 ? "\n":" ");}
#define rep(i,x) for(int i = 0;i<x;i++)
#define REP(i,x) for(ll i = 1;i<=x;i++)
#define mp make_pair
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const dou pi = 3.14159265358;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a / gcd(a,b) * b;
}

//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logm)
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}
ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}

ll num(ll n){//10^n~10^1
    ll res = 0;
    rep(i,n){
        res += mypow(10,i);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll H,W;
    cin >> H >> W;
    if(H % 3 == 0 || W % 3 == 0){
        cout << "0\n";
        return 0;
    }
    ll ans = INF;
    rep(i,H + 1){
        vector<ll> sq(3);
        sq[0] = i * W;sq[1] = (H - i) * (W / 2);
        sq[2] = (W % 2 == 0 ? sq[1]:(H - i) * (W / 2 + 1));
        sort(all(sq));
        chmin(ans,sq[2] - sq[0]);
    }
    rep(i,W + 1){
        vector<ll> sq(3);
        sq[0] = i * H;sq[1] = (W - i) * (H / 2);
        sq[2] = (H % 2 == 0 ? sq[1]:(W - i) * (H / 2 + 1));
        sort(all(sq));
        chmin(ans,sq[2] - sq[0]);
    }
    chmin(ans,H);
    chmin(ans,W);
    cout << ans << endl;
}

Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {

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

	    String s=gs();
	    
	    for (int i=0; i<16;i++) {
	    	StringBuilder sb=new StringBuilder();
	    	if ((i>>0&1)==1) {
	    		sb.append('A');
	    	}
	    	sb.append("KIH");
	    	if ((i>>1&1)==1) {
	    		sb.append('A');
	    	}
	    	sb.append("B");
	    	if ((i>>2&1)==1) {
	    		sb.append('A');
	    	}
	    	sb.append("R");
	    	if ((i>>3&1)==1) {
	    		sb.append('A');
	    	}
	    	if (sb.toString().equals(s)) {
	    		System.out.print("YES");
	    		return;
	    	}
	    }
//	    if (s>x) {
//	    	System.out.println(n-1);
//	    } else {
//	    	Arrays.parallelSort(a);
//
//	    	System.out.println(c);
//	    }
	    System.out.println("NO");
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35600
#include <bits/stdc++.h>
using namespace std;
struct dat{
  int T,t,f,lap;
  dat(){T=t=f=lap=0;}
  vector<dat> V;
  bool operator > (const dat &a)const{return T-t>a.T-a.t;}
};

bool onFront(const dat &a,const dat &b){return a.f==b.f&&1.0*a.t/a.T<1.0*b.t/b.T;}
bool checkJam(const dat &a,const dat &b){return onFront(a,b)&&a.T-a.t<b.T-b.t;}

int merge(vector<dat>&A,int idx){
  dat &a = A[idx];
  for(int i=0;i<(int)A.size();i++){
    dat &b = A[i];
    if(!checkJam(a,b))continue;
    a.t=0, a.lap-=a.f, a.f=!a.f;
    b.V.push_back(a);
    A.erase(A.begin()+idx);
    return 1e9;
  }
  return a.T-a.t;
}

void Push(vector<dat>&A,dat &a){
  for(int i=0;i<(int)a.V.size();i++)Push(A,a.V[i]);
  a.V.clear();
  if(a.lap) A.push_back(a);
}

int sim(vector<dat> A){
  int res=0;
  while(!A.empty()){
    sort(A.begin(),A.end(),greater<dat>());
    int mn = 1e9;
    for(int i=A.size()-1;i>=0;i--)mn=min(mn,merge(A,i));

    vector<dat>nA;
    for(int i=0;i<(int)A.size();i++)
      if(A[i].t+mn<A[i].T) A[i].t+=mn,nA.push_back(A[i]);
      else A[i].t=0, A[i].lap-=A[i].f, A[i].f=!A[i].f,Push(nA,A[i]);

    A=nA;
    res+=mn;
  }
  return res;
}

int main(){
  int n;
  while(cin>>n,n){
    vector<dat> A(n);
    for(int i=0;i<n;i++)cin>>A[i].T>>A[i].lap;
    cout<<sim(A)<<endl;
  }
  return 0;
}

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

using namespace std;

typedef unsigned long long ull;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int n; cin>>n;
    cin.ignore();
    while(n--){
        string s; getline(cin,s);
        size_t beg;
        while(beg=s.find("Hoshino"), beg!=string::npos){
            s[beg+6]='a';
        }
        cout<<s<<endl;
    }
}

Measured memory_bytes: 1208