akhauriyash/Code-Regression huggingface dataset:
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
# C[hCX][w]
ans = 10 ** 20
for s in range(2 ** (h - 1)):
    yoko = bin(s).count("1")
    white = [0] * (yoko + 2)
    cnt = 0
    # 横分割を足しておく
    cnt += yoko
    outflag = 0
    for j in range(w):
        now = 0
        for i in range(h):
            if outflag:
                break
            white[now] += int(C[i][j])
            if white[now] > k:
                # 縦分割をする時はkを超えた時。
                # kを超えたら1つ前で割ったことにするので、
                # その列をもう1回やり直す必要あり
                cnt += 1
                # 同じjのところをi=[0,i]までやり直す
                # 初期化
                white = [0] * (yoko + 2)
                now = 0
                # 0からiまでやり直す
                for t in range(i + 1):
                    white[now] += int(C[t][j])
                    if white[now] > k:
                        outflag = 1
                        break
                    if (s >> t) & 1 == 1:
                        now += 1
                continue
            if (s >> i) & 1 == 1:
                now += 1
        if outflag:
            break
    if outflag:
        outflag = 0
        continue
    ans = min(cnt, ans)
print(ans)


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

#define int long long

signed main() {
	int m, d;
	cin >> m >> d;
	int count = 0;
	for(int i = 2; i <= 9; i++) {
		for(int j = 2; j <= 9; j++) {
			int val = 10*i+j;
			if(val<=d && i*j<=m) count++;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))
#define Rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define pb push_back

const int inf = 999999999;
const int mod = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main(){
	int a, b; cin >> a >> b;
	int answer = 0;
	if(a <= 8 && b <= 8){
		cout << "Yay!" << endl;
	}else{
		cout << ":(" << endl;
	}
}

Measured memory_bytes: 256
s = input()
ans = 0
k = len(s)
def search(formulas, n,count):
    global k
    if count >= k:
        cal(formulas)
    else:
        search(formulas,n+1,count + 1)
        search(formulas[:n] + "+" + formulas[n:],n+2,count + 1)
def cal(formulas):
    global ans
    ans += sum(map(int, list(formulas.split("+"))))
search(s,1,1)
print(ans)

Measured memory_bytes: 38768
#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>

using namespace std;

int main(){
    int N;
    cin >> N;
    int a[200010];
    for(int i = 0; i < N; i++) cin >> a[i];
    int counter = 1;
    for(int i = 0; i < N; i++){
        if(a[i] == counter) counter++;
    }
    if(counter == 1) cout << -1 << endl;
    else cout << N - counter +1 << endl;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
const int p = 1000005;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	vector<int> a(p);
	a[1] = 1;
	repl(i, 2, p) {
		if (a[i]) continue;
		for (int j = i; j < p; j += i) {
			if (a[j] == 0) a[j] = i;
		}
	}
	int n;
	cin >> n;
	vector<int> vec(n);
	rep(i, n) cin >> vec[i];
	set<int> s;
	bool flag = 0;
	rep(i, n) {
		set<int> t;
		int k = vec[i];
		while (true) {
			if (k == 1) break;
			t.insert(a[k]);
			if (k == a[k]) break;
			k /= a[k];
		}
		for (auto nt : t) {
			if (s.count(nt)) {
				flag = 1;
				i = n;
				break;
			}
			s.insert(nt);
		}
	}
	if (flag == 0) {
		cout << "pairwise coprime\n";
		return 0;
	}
	int g = vec[0];
	rep(i, n) g = gcd(g, vec[i]);
	if (g == 1)
		cout << "setwise coprime\n";
	else
		cout << "not coprime\n";
	return 0;
}

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

using namespace std;

typedef long long int ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    for(ll a = 0; a < n; a++) {
        if(m*a % n == 0) {
            ll b = (m*a)/n;
            if(s[a] != t[b]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << (n*m)/gcd(n, m) << endl;

}


Measured memory_bytes: 640
// ABC064B - 

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

int main() {
	int N;
	cin >> N;
	int a[N];
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	sort(a, a + N);

	cout << a[N-1] - a[0] << endl;

	return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	n, x := nextInt(), nextInt()
	a := nextInts(n)
	sort.Sort(sort.IntSlice(a))

	for i := 0; i < n; i++ {
		x -= a[i]
		if x < 0 {
			puts(i)
			break
		} else if x == 0 {
			puts(i + 1)
			break
		} else if i == n-1 {
			puts(n - 1)
		}
	}
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 640
import sys
sys.setrecursionlimit(1000000)

def solve(A, B, C, D):
    while A > 0 or C > 0:
        C -= B
        if C <= 0:
            break
        A -= D

    if A <= 0:
        return "No"
    return "Yes"

if __name__ == "__main__":
    A, B, C, D = tuple(map(int, input().split(" ")))
    print(solve(A, B, C, D))


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

int N;
int A[210]; 

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i];

    int res = 0;
\
    while (true) {
        bool exist_odd = false; 
        for (int i = 0; i < N; ++i) {
            if (A[i] % 2 != 0) exist_odd = true; 
        }

        if (exist_odd) break;  
        for (int i = 0; i < N; ++i) {
            A[i] /= 2;
        }
        ++res;  
    }

    cout << res << endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define ll long long int
#define ld double
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const ll inf64 = 1e18;
int main()
{
	boost;
	ll n, i, j;
	cin >> n;
	ll ans = inf64;
	for(i = 1; i <= sqrt(n); i++){
		if(n % i == 0){
			ll x = n / i;
			ans = min(ans, i + x - 2);
		}
	}
	cout << ans;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
int main() 
{string s;cin>>s;
 long long q,ch=0;cin>>q;
 while(q--)
 {long long f;cin>>f;if(f==1)ch++;
  else
  {
  long long a;cin>>a;
  char c;cin>>c;
  if(a==2){
    if(ch%2==0)
    s+=c;
  else s.insert(s.begin(),c);
  }
    else{if(ch%2==0)s.insert(s.begin(),c);
        else s+=c;
        }
  }
 }if(ch%2!=0)reverse(s.begin(),s.end());
 cout<<s;
 return 0; 
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    int n, l;
    cin >> n >> l;
    vector<string> vs(n);
    fo(i, n) cin >> vs[i];

    sort(all(vs));
    fo(i, n) cout << vs[i];
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
int A,B;
cin>>A>>B;
int sum,subtract,multiply;
sum=A+B;
subtract=A-B;
multiply=A*B;
if(sum>=subtract&&sum>=multiply)
  cout<<sum;

else if (subtract>=sum&&subtract>=multiply)
  cout<<subtract;

else
  cout<<multiply;

  return 0; 
}

Measured memory_bytes: 256
#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6) and mx-mn>10**(-7)*mx:#mx大きい時に安易に設定すると到達しない？
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)


Measured memory_bytes: 60376
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scan(&N)

	for h := 1; h <= 3500; h++ {
		for n := 1; n <= 3500; n++ {
			// w = Nhn / (4hn - Nn - Nh)
			a := (N * h * n)
			b := (4*h*n - N*n - N*h)
			if b < 0 || a*b <= 0 || a%b != 0 {
				continue
			}
			w := a / b
			if w <= 3500 {
				fmt.Println(h, n, w)
				return
			}
		}
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////

ll N;
vector<vector<ll>> g;

ll dfs(ll u, ll v) {
	vector<ll> vec;

	for (ll w : g[v]) {
		if (u == w) { continue; }
		
		vec.push_back(dfs(v, w));
	}

	sort(vec.begin(), vec.end(), greater<ll>());
	
	ll ret = 0;
	rep(i, vec.size()) {
		if (i == vec.size() - 1) { ret += vec[i]; }
		else { ret += max(1, vec[i]); }
	}

	return ret;




}

int main() {
	cin >> N;
	g.resize(N);
	repn(i, N - 1) {
		ll a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	ll ans = dfs(-1, 0);
	if (g[0].size() == 1) { ans++; }
	if (g[0].size() == 2) {
		ll c = 0;
		for (ll v : g[0]) {
			if (dfs(0, v) == 0) { c++; }
		}
		if (c == 1) { ans++; }
	}

	cout << ans << endl;
	
	system("PAUSE");
}


Measured memory_bytes: 15224
#include <iostream>
#include <vector>
#include <iomanip>
#define REP(i, n) for(int i = 0; i < n; i++)
template<class T> inline void chmin(T& a, T b) {if (a>b) a=b; }
template<class T> inline void chmax(T& a, T b) {if (a<b) a=b; }
using namespace std;
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;

int main() { 
    string S, T;
    cin >> S >> T;
    int ct=0;
    REP(i, 3) {
        if (S[i]==T[i]) ct++;
    }
    cout << ct << endl;
    
    return 0;
}

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

bool seen[51];
void dfs(int target, map<int, vector<int>> graph){
    seen[target] = true;
    for (auto adjacent : graph[target]){
        if (seen[adjacent] == false){
            dfs(adjacent, graph);
        }
    }
}

int main(){
    int n, m;cin>>n>>m;
    vector<pair<int, int>> connections(m);
    int l,r;
    for (int i=0;i<m;i++){
        cin >> l >> r;
        connections[i] = make_pair(l, r);
    }

    int acc = 0;    
    for (int i=0;i<m;i++){
        map<int, vector<int>> graph;
        for (int j=0;j<m;j++){
            if (j != i){
                graph[connections[j].first].push_back(connections[j].second);
                graph[connections[j].second].push_back(connections[j].first);
            }
        }

        memset(seen, false, sizeof(seen));
        dfs(1, graph);
        
        for (int k=1;k<=n;k++){
            if (seen[k] == false){
                acc++;
                break;
            }
        }

    }
    cout << acc << endl;
}

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

int main(void){
    char num_str[1002];
  int num;
  long sum;
  int i;
  char tmp;
    while(1){
   fgets(num_str,sizeof(num_str),stdin);
      if(num_str[0]=='0') break;
      for(i=0;i<strlen(num_str)-1;i++){
    tmp=num_str[i];
    num=atoi(&tmp);
    sum=sum+num;
   }
      printf("%ld\n",sum);
      sum=0;
   memset(num_str,1002,0);
  }
    return 0;
 }

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

int main()
{
	int a,zd=-1,t=0;
	char b;
	cin>>a;
	for(int i=0;i<a;i++){
		cin>>b;
		if(b=='I'){
			t++;
		}else{
			t--;
		}
		zd=max(zd,t);
	}
	if(zd==-1){
		cout<<0<<endl;
	}else{
		cout<<zd<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import math
import collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
flag=False
for i in range(n):
    #print(i,a[i])
    if flag:
        flag=False
        continue
    if s[a[i]]==0: continue
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    #print("pair",pair)
    if pair in s.keys() and s[pair]>0:
        s[a[i]]-=1
        s[pair]-=1
        r+=1
        continue
    if i<n-1 and pair==0 and a[i+1]==a[i] and s[a[i]]>=2:
        s[a[i]]-=2
        r+=1
        flag=True
print(r)

Measured memory_bytes: 33416
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

    int main(){
      ll n;
      cin >> n;
      string s;
      cin >> s;
      ll ans=1;
      ll cnt[27]={};
      for(int i=0;i<27;i++)cnt[i]++;
      for(int i=0;i<n;i++){
        for(char j='a';j<='z';j++){
         if(s[i]==j)cnt[j-'a']++;
        }
      }
      for(ll i=0;i<27;i++){
       ans*=cnt[i];
        ans%=mod;
      }
      cout << ans-1 << endl;
      return 0;}

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

int main()
{
    map<string, int> ball;
    string S, T, U;
    int A, B;
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;

    if (U == S)
    {
        A--;
    }
    else
    {
        B--;
    }
    cout << A << " " << B << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int a,p;
int main(){
	cin>>a>>p;
	cout<<(3*a+p)/2<<endl;
	return 0;
}

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

namespace CompetitiveProgramming
{
  class Solve
  {
    public Solve()
    {
      int N = Scanner.nextInt();
      int L = Scanner.nextInt();
      string[] S = new string[N];
      for (int i = 0; i < N; i++) 
      {
        S[i] = Scanner.nextString();
      }
      Array.Sort(S);
      for (int i = 0; i < N; i++)
      {
        Console.Write(S[i]);
      }
      Console.WriteLine("");
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
        new Solve();
    }
  }

  public class Pair<T, U>
  {
    public Pair()
    {

    }
    public Pair(T first, U second)
    {
      this.first = first;
      this.second = second;
    }
    public T first { get; set; }
    public U second { get; set; }
  }

  class Scanner
  {
    private static List<string> buf = new List<string>();

    private static void next()
    {
      if (buf.Count == 0)
      {
        buf = Console.ReadLine().Split().ToList();
      }
    }

    private static string pop()
    {
      string ret = buf[0];
      buf.RemoveAt(0);
      return ret;
    }

    public static int nextInt()
    {
      next();
      return int.Parse(pop());
    }
    public static long nextLong()
    {
      next();
      return long.Parse(pop());
    }
    public static string nextString()
    {
      next();
      return pop();
    }
    public static double nextDouble()
    {
      next();
      return double.Parse(pop());
    }
  }
}


Measured memory_bytes: 3416
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    vector<long long> x(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];

    long long ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += min((x[i + 1] - x[i]) * a, b);
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    int h;
    cin >>h;
    int w;
    cin >>w;
    vector<string> a(h);
    for (int i = 0 ; i < h; i++) {
        cin >> a[i];
    }
    
    vector<bool> row(h,false);
    
    vector<bool> col(w,false);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w ; j++) {
            if (a[i][j] == '#') {
                row[i] = true;
                col[j] = true;
            }
        }
    }
    
    for (int i = 0;i<h;i++) {
        if (row[i]){
            for (int j = 0; j < w; j++) {
                if (col[j]) {
                    cout << a[i][j];
                }
            }
            cout << endl;
        
    }
    
}
}



Measured memory_bytes: 256
use std::io::stdin;

fn main() {
    let result:Vec<i64> = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692].to_vec();
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let k = st.trim().parse::<usize>().unwrap();
    println!("{}",result[k-1]);
}

Measured memory_bytes: 2176
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
typedef long long ll;
//using ll = long long;
//using R = double;

//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

const int INF = int(1e9);

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

//const int DAT_SIZE = (1 << 18) - 1;
const int MAX_SIZE = 1 << 17;
//const int MAX_SIZE = 4;

int N, Q;

ll data[2 * MAX_SIZE - 1], datb[2 * MAX_SIZE - 1];

void add(int a, int b, int x, int k, int l, int r)
{
    if (a <= l && r <= b) {
        data[k] += x;
    }
    else if (l < b && a < r) {
        datb[k] += (min(b, r) - max(a, l)) * x;
        add(a, b, x, k * 2 + 1, l, (l + r) / 2);
        add(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
}

ll sum(int a, int b, int k, int l, int r)
{
    if (b <= l || r <= a) {
        //printf("a = %d, b = %d, k = %d, l = %d, r = %d, ret = 0\n", a, b, k, l, r);
        return 0;
    }
    else if (a <= l && r <= b) {
        //printf("a = %d, b = %d, k = %d, l = %d, r = %d, ret = %d\n", a, b, k, l, r, data[k] * (r - l) * datb[k]);
        //return data[k] * (r - l) * datb[k];
        return data[k] * (r - l) + datb[k];
    }
    else {
        ll res = (min(b, r) - max(a, l)) * data[k];
        res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
        res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
        //printf("a = %d, b = %d, k = %d, l = %d, r = %d, ret = %d\n", a, b, k, l, r, res);
        return res;
    }
}

signed main()
{
    cin >> N >> Q;

    //int n_ = 1;
    //while (n_ < N) n_ *= 2;
    N = MAX_SIZE;
    int com, s, t, x;
    REP(i,Q) {
        cin >> com;
        if (com == 0) {
            cin >> s >> t >> x;
            //printf("s = %d, t = %d, x = %d\n", s, t, x);
            //s--; t--;
            add(s, t + 1, x, 0, 0, N);
        } else {
            cin >> s >> t;
            //printf("s = %d\n", s);
            //s--;
            cout << sum(s, t + 1, 0, 0, N) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 5452
#include<vector>
#include<queue>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<string>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<29
#define MAX 30
using namespace std;
int n,m,p,a,b;

int main(){
  int tes,x,y;
  double tk;
  int d[31][31];
  double dp[1<<9][31]; // [ticketの残り枚数][今いる街]
  vector<double> ticket;
  while(true){
    
    scanf("%d %d %d %d %d",&n,&m,&p,&a,&b);
    if(n+m+p+a+b == 0)break;
    ticket.clear();   
    rep(i,31)rep(j,31)d[j][i] = INF;

    rep(i,n){
      cin >> tk;
      ticket.push_back(tk);
    }
    rep(i,p){
      cin >> x >> y >> tes;
      d[x][y] = d[y][x] = tes;
    }
  
    for(int i=0;i<(1<<9);i++){
      for(int j=0;j<31;j++)dp[i][j] = INF;
    }
    dp[(1<<n)-1][a] = 0;

    double ans = INF;
    for(int S = (1<<n)-1; S>=0 ;S--){
      ans = min(ans,dp[S][b]);
      for(int v = 1; v<=m ;v++){
	for(int t = 0; t<n ;t++){
	  if(!(S>>t &1))continue;//tを既に使っていたなら戻る
	  for(int u = 1; u<=m;u++){
	    if(d[v][u] == INF)continue; //（ vからuまでの道は？ ） ないんだな、それが	    
	    dp[S & ~(1<<t)][u] = min(dp[S & ~(1<<t)][u],dp[S][v] + (double)(d[v][u]/ticket[t]) );	    
       
	  }
	}
      }
    }
    if(ans == INF)printf("Impossible\n");
    else printf("%.3f\n",ans);
 
  }
  return 0;
}

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

using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)


struct edge{
  int from,to,cost;
  bool operator < (edge &b){
    return cost<b.cost;
  }
};


class UF {
private:
    int sz; vector<int> par,nrank,size;
public:
    UF(){}
    UF(int node_size){ sz = node_size; par.resize(sz),nrank.resize(sz),size.resize(sz);
        rep(i,sz){ par[i] = i; nrank[i] = 0; size[i] = 1;} }
    int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } }
    void unite(int x,int y)
    { x = find(x),y = find(y); if(x == y) return; if(nrank[x] < nrank[y]) swap(x,y);
        par[y] = x; size[x] += size[y]; if(nrank[x] == nrank[y]) nrank[x]++; }
    int query(int x){ x = find(x); return size[x]; }
    bool same(int x,int y){ return find(x) == find(y); }
};

template<typename T> class Kruskal{
public:
  struct edge{
    int u,v;
    T cost;
    bool operator<(const edge& another) const {
      return cost < another.cost;
    }
  };
  vector<edge> es;
  vector<int> par,rrank;
  int V;
    Kruskal(int node_size){
        V = node_size;
    par.resize(node_size), rrank.resize(node_size);
  }
  void add_edge(int u,int v,T cost){
    es.push_back((edge){u,v,cost});
  }
  T solve(){
    UF uf(V);
    T mini = 1e9;
    T maxi = 0;
    T size = 0;
    T res = 0;
    int cnt = 0;
    sort(es.begin(),es.end());
    rep(i,es.size()){
      edge e = es[i];
      if(!uf.same(e.u,e.v)){
        uf.unite(e.u,e.v);
        res += e.cost;
        size += 1;
        if (mini>e.cost)mini = e.cost;
        if (maxi<e.cost)maxi = e.cost;
        cnt++;
        if(cnt == V-1){
          break;
        }
      }
    }
    if (size < V-1){
      //cout << "V: " << V << " size: " << size << endl;
      return 1e9;
    } else {
      return maxi-mini;
    }
  }
};

int main(){

  int n,m;
  while (1){
    cin >> n >> m;
    if (n==0)break;
    if (n>2 && m==0){
      cout << "-1" << endl;
      continue;
    }
    vector<edge> e(m);
    for (int i=0;i<m;i++){
      cin >> e[i].from >> e[i].to >> e[i].cost;
    }
    sort(e.begin(),e.end());
    for (auto ed:e){
      //cout << ed.cost << endl;
    }
    long long mini = 1e10;
    for (int i=0; i<m; i++){
      Kruskal<int> kl(n);
      for (int j=i; j<m; j++) {
        kl.add_edge(e[j].from-1,e[j].to-1,e[j].cost);
      }
      //cout << "edges: " << kl.es.size() << endl;
      int res = kl.solve();
      //cout << res << endl;
      if (mini > res) mini = res;
    }
    if (mini==1e9){ //|| mini==1e10){
      cout << "-1" << endl;
    } else {
      cout << mini << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3228
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long double ld;
typedef long long int ll;
const ll INF = (1LL << 63);
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
#define rep(i,n) for(int i = 0; i < n;i++)
const int MAX = 1000000010;
const ll MOD = 1000000007;
ll h, w, t,n,q,x,sum = 0;
vector<vector<ll>> dp;
vector<ll> a;
ll rec(int l, int r) {
    if (r == l) return 0;
    ll &ret = dp[l][r];
    if (ret != INF) return ret;
    if ((n - r + l) % 2 == 0) {
        ret = max(a[l] + rec(l + 1, r), rec(l, r - 1) + a[r - 1]);
    }
    else {
        ret = min(-a[l] + rec(l + 1, r), rec(l, r - 1) - a[r - 1]);
    }return ret;
}
int main() {
    cin >> n;
    a.resize(n);
    dp.resize(n + 5, vector<ll>(n + 5, INF));
    rep(i, n + 1)dp[i][i] = 0;
    rep(i, n) cin >> a[i];
    cout << rec(0, n) << endl;
}

Measured memory_bytes: 71040
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}  
int D;
vector<int> c(26);
vector<vector<int>> s;
int score(vector<int> t) {
  int ans = 0;
  vector<int> last(26);
  REP(i, D) {
    ans += s[i][t[i]];
    last[t[i]] = i + 1;
    REP(j, 26) ans -= c[j] * (i + 1 - last[j]);
  }
  return ans;
}
double TIME_LIMIT = 1980;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> D;
  REP(i, 26) cin >> c[i];
  s = vector<vector<int>>(D, vector<int>(26));
  REP(i, D) REP(j, 26) cin >> s[i][j];

  vector<int> t(D);
  REP(i, D) t[i] = i%26;
  
  clock_t start_time = clock();
  int now = score(t);
  int loop = 0;
  double start_temp = 1000, end_temp = 10;
  int max = 0;
  vector<int> tmax(t);
  while(true) {
    loop++;
    clock_t now_time = clock();
    double time = static_cast<double>(now_time - start_time) / CLOCKS_PER_SEC * 1000.0;
    if(time > TIME_LIMIT) break;
    vector<int> tnew(t);
    int mode = rand() % 10;
    if(mode == 0) {
      int idx = rand() % D;
      int type = rand() % 26;
      tnew[idx] = type;
    } else {
      int idx = rand() % (D-1);
      swap(tnew[idx], tnew[idx+1]);
    }
    int next = score(tnew);
    double temp = start_temp + (end_temp - start_temp) * time / TIME_LIMIT;
    double prob = exp((next-now)/temp);
    if(next > now || prob > (rand()%INF)/(double)INF) {
      t = tnew;
      now = next;
    }
    if(now > max) {
      tmax = t;
      max = now;
    }
    //cout << next << "\n";
    //if(next < now) cout << prob << "\n";
  }
  REP(i, D) cout << (tmax[i]+1) << "\n";
  //cout << max << "\n";
  //cout << loop << "\n";
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

int H, W;
char B[60][60];
int dist[60][60];
const int INF =  1e8;

int dfs(int y, int x, int cnt) {
   if (dist[y][x] <= cnt) return dist[y][x];

   dist[y][x] = cnt;
   rep (i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= W || ny < 0 || ny >= H || B[ny][nx] == '#') continue;
      dfs(ny, nx, cnt+1);
   }
}

int main() {
   cin >> H >> W;
   int black = 0;
   rep (i, H) { 
      cin >> B[i]; 
      rep (j, W) {
         if (B[i][j] == '#') {
            black++;
         }
      }
   }

   rep (i, H) { rep(j, W) { dist[i][j] = INF; } }
   dfs(0, 0, 0);

   int n = dist[H-1][W-1];
   if (n == INF) {
      cout << -1 << endl;
   } else {
      cout << H*W - black - dist[H-1][W-1] -1 << endl;
   }

   return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

int main (void) {
  int N;
  cin >> N;
  int a[N];
  for (int i=0; i<=N-1; i++) cin >>  a[i];
  int ans=0;

  while(true) {
    bool exist_odd =false;
    for (int i=0; i<=N-1; i++) {
      if (a[i]%2 != 0) exist_odd = true;
    }
    if (exist_odd) break;
    
    for (int i=0; i<=N-1; i++) {
      a[i]=a[i]/2;
    }
    ans=ans+1;
    
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end
n, m = gets_i_list

ab = []

n.times do
  ab.push gets_i_list
end
ab.sort!
total = 0
ab.each do |a, b|
  if m >= b
    total += a * b
    m -= b
  else
    total += m * a
    break
  end
end

puts total

Measured memory_bytes: 22120
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define MAX 2000000
#define MOD 1000000007
#define endl "\n"
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli t;
    t = 1;
    while(t--){
        lli A,B,C;
        cin>>A>>B>>C;
        lli K;
        cin>>K;
        lli sum = 0;
        sum += min(A,K);
        K -= sum;
        sum += min(B,K)*0;
        K -= min(B,K);
        sum -= min(C,K);
        cout<<sum<<endl;

    }

}

Measured memory_bytes: 3652
#include <stdio.h>
#include <string.h>

int main(void)
{
	int i,a;
	char moji[21];
	
	scanf("%s",&moji);
	a=strlen(moji);
	for(i=1;i<=a;++i)
	{ 
		printf("%c",moji[a-i]);
	}
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 932
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        String B = sc.next();
        char[] bc = B.toCharArray();
        long b = (bc[0]-'0');
        if(bc.length <= 2){
            System.out.println(A*b);
        }else if(bc.length == 3){
            long b1 = (bc[2]-'0');
            String str = String.valueOf(A*(b*10+b1));
            if(str.length() < 2){
                System.out.println("0");
                return;
            }
            System.out.println(str.substring(0, str.length()-1));
        }else if(bc.length == 4){
            long b1 = (bc[2]-'0');
            long b2 = (bc[3]-'0');

            String str = String.valueOf(A*(b*100+b1*10+b2));
            if(str.length() < 3){
                System.out.println("0");
                return;
            }
            System.out.println(str.substring(0, str.length()-2));
        }
    }
}


Measured memory_bytes: 35780
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define INF 100000000000
#define MOD 100000007 //10^9+7
using namespace std;
using ll = long long;
using P = pair<int, int>;

char s[50][50];
int h, w;

int main()
{
    int n, m, k, j;
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    int turn = 0;
    while (a > 0 && c > 0) {
        if (turn == 0) {
            c -= b;
            turn++;
        } else {
            a -= d;
            turn--;
        }
    }

    if (a <= 0) {
        cout << "No" << endl;
    } 
    if (c <= 0) {
        cout << "Yes" << endl;
    }


    return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    
    vi ruiseki = {0, 0};
    
    rep(i, n){
        if(i == n-1 || s[i] != s[i+1]){
            ruiseki.pb(i+1);
        }
    }
    
    ruiseki.pb(n);
    
    int r = ruiseki.size();
    int d = 2 * k + 1;
    int ans = 0;
    int p = (s[0] == '0') ? 0 : 1;
    
    if(d >= r - 2) ans = n;
    else{
        for(int i = p; i + d < r; i += 2){
            int temp = ruiseki[i + d] - ruiseki[i];
            ans = max(ans, temp);
        }
    }
    
    cout << ans << endl;
    return;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 4012
def isOKL(index):
    now = s[index]
    for w, d in magic:
        if w == now:
            if d == "L":
                index -= 1
                if index < 0:
                    return True
                now = s[index]
            else:
                index += 1
                if index >= N:
                    return False
                now = s[index]
    return False


def isOKR(index):
    now = s[index]
    for w, d in magic:
        if w == now:
            if d == "L":
                index -= 1
                if index < 0:
                    return False
                now = s[index]
            else:
                index += 1
                if index >= N:
                    return True
                now = s[index]
    return False


N, Q = map(int, input().split(" "))
s = input()
magic = [input().split(" ") for _ in range(Q)]

left_drop_ng = N
left_drop_ok = -1
right_drop_ng = -1
right_drop_ok = N

# search left
while abs(left_drop_ok - left_drop_ng) > 1:
    mid = (left_drop_ng + left_drop_ok) // 2
    res = isOKL(mid)
    if res:
        left_drop_ok = mid
    else:
        left_drop_ng = mid

while abs(right_drop_ok - right_drop_ng) > 1:
    mid = (right_drop_ng + right_drop_ok) // 2
    res = isOKR(mid)
    if res:
        right_drop_ok = mid
    else:
        right_drop_ng = mid
if right_drop_ok <= left_drop_ok:
    print(0)
else:
    print(N - (left_drop_ok+1) - (N-right_drop_ok))


Measured memory_bytes: 39356
#include <stdio.h>

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  for ( ; ; )
  {
    int a, b;
    int e100, e500, e1000;

    scanf ( "%d%d", &a, &b );
    if ( !( a | b ) ) break ;

    a     = b - a;
    e1000 = a / 1000;
    a    %= 1000;
    e500  = a / 500;
    a    %= 500;
    e100  = a / 100;

    printf ( "%d %d %d\n", e100, e500, e1000 );
  }

  return ( 0 );
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <boost/range/algorithm/max_element.hpp>
#include <boost/range/algorithm/min_element.hpp>
using namespace std;


int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<int> xs(n);
    vector<int> ys(m);
    for (int i = 0; i < n; i++) cin >> xs.at(i);
    for (int i = 0; i < m; i++) cin >> ys.at(i);

    int max_x = *boost::max_element(xs);
    int min_y = *boost::min_element(ys);

    if (max_x < min_y && max_x < y && x < min_y) {
        cout << "No War" << endl;
    } else {
        cout << "War" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class d{
  public static void Main(){
    long n = long.Parse(Console.ReadLine());
    long[] c = new long[n+1];
    long ans = 0;
    for(long i=1; i<=n; i++){
      for(long j=i; j<=n; j+=i){
        c[j]++;
      }
    }
    for(long i=1; i<=n; i++){
      ans += c[i]*i;
    }
    Console.WriteLine(ans);
  }
}


Measured memory_bytes: 94812
#include<iostream>
using namespace std;
#include<vector>
#include<functional>
template<typename T>
struct lazysegtree{
	using F=function<T(T,T)>;
	using G=function<T(T,T,int,int)>;
	const F calcfn,lazycalcfn;
	const G updatefn;
	int n;
	T defvalue;
	vector<T>dat,lazy;
	vector<bool>lazyflag;
	lazysegtree(int n_=0,T defvalue_=0,
		const F calcfn_=[](T a,T b){return a+b;},
		const F lazycalcfn_=[](T a,T b){return a+b;},
		const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);}
	):defvalue(defvalue_),
		calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
		lazy.assign(2*n-1,T());
		lazyflag.assign(2*n-1,false);
	}
	void copy(const vector<T>&v)
	{
		for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
		for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
	}
	void eval(int i,int l,int r)
	{
		if(lazyflag[i])
		{
			dat[i]=updatefn(dat[i],lazy[i],l,r);
			if(r-l>1)
			{
				lazy[2*i+1]=lazyflag[2*i+1]?lazycalcfn(lazy[2*i+1],lazy[i]):lazy[i];
				lazy[2*i+2]=lazyflag[2*i+2]?lazycalcfn(lazy[2*i+2],lazy[i]):lazy[i];
				lazyflag[2*i+1]=lazyflag[2*i+2]=true;
			}
			lazyflag[i]=false;
		}
	}
	void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]=lazyflag[k]?lazycalcfn(lazy[k],x):x;
			lazyflag[k]=true;
			eval(k,l,r);
		}
		else
		{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k]=calcfn(dat[2*k+1],dat[2*k+2]);
		}
	}
	T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return defvalue;
		else if(a<=l&&r<=b)return dat[k];
		else return calcfn(
			query(a,b,2*k+1,l,(l+r)/2),
			query(a,b,2*k+2,(l+r)/2,r)
		);
	}
};
int N,Q;
const long mod=998244353;
long p10[3<<17];
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
long inv9;
main()
{
	cin>>N>>Q;
	inv9=power(9,mod-2);
	p10[0]=1;
	for(int i=1;i<3<<17;i++)p10[i]=p10[i-1]*10%mod;
	lazysegtree<pair<long,long> >P(N,make_pair(0,1),
		[](pair<long,long>a,pair<long,long>b){
			return make_pair((a.first*b.second+b.first)%mod,a.second*b.second%mod);
		},
		[](pair<long,long>a,pair<long,long>b){
			return b;
		},
		[](pair<long,long>a,pair<long,long>b,int l,int r){
			int w=r-l;
			return make_pair((p10[w]+mod-1)%mod*inv9%mod*b.first%mod,p10[w]);
		});
	vector<pair<long,long> >A(N,make_pair(1,10));
	P.copy(A);
	for(int i=0;i<Q;i++)
	{
		int l,r,d;cin>>l>>r>>d;
		P.update(l-1,r,make_pair(d,0));
		cout<<P.query(0,N).first<<endl;
	}
}


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

#define REP(i, a, b) for (ll i = (a); i <= (b); ++i)
#define REV(i, a, b) for (ll i = (a); i >= (b); --i)

using namespace std;

using ll = long long;

const ll MAX = 3000;
const int MOD = 1E9 + 7;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
   fac[0] = fac[1] = 1;
   finv[0] = finv[1] = 1;
   inv[1] = 1;
   for (ll i = 2; i < MAX; 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;
   }
}

long long COM(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;
}

void Main()
{
   ll N, K;
   cin >> N >> K;
   ll ans;
   COMinit();
   REP(i, 1, K)
   {
      ans = (COM(N - K + 1, i) * COM(K - 1, i - 1)) % MOD;
      cout << ans << endl;
   }
}

int main()
{
   std::cin.tie(nullptr);
   std::ios_base::sync_with_stdio(false);
   std::cout << std::fixed << std::setprecision(15);
   Main();
   return 0;
}


Measured memory_bytes: 384
s = list(reversed(input()))
t = list(reversed(input()))

match = True

for i in range(len(s)):
    match = True
    if len(s) < len(t) + i:
        match = False
        break

    if s[i] == t[0] or s[i] == '?':

        for j in range(len(t)):
            if not (s[i + j] == t[j] or s[i + j] == '?'):
                match = False

        if match:
            for j in range(len(t)):
                s[i + j] = t[j]
            break

if match:
    print(''.join(reversed(s)).replace('?', 'a'))
else:
    print('UNRESTORABLE')


Measured memory_bytes: 3064
from bisect import bisect_left, bisect_right

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

OKs = []
for i, S in enumerate(Ss):
    if S == '0':
        OKs.append(i)
#print('OKs:', OKs)

dp = [0] * (N+1)
for i in range(N+1):
    j = bisect_left(OKs, i-M)
    dp[i] = OKs[j]
#print('dp:', dp)

anss = []
i = N
while True:
    iPrev = dp[i]
    if iPrev == i:
        anss = []
        break
    if iPrev < 0:
        iPrev = 0
    anss.append(i-iPrev)
    if iPrev == 0:
        break
    i = iPrev

if not anss:
    print(-1)
else:
    print(' '.join(map(str, anss[::-1])))


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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, y, k;
  bool result = false;
  cin >> n >> y;
  rep(i, n + 1) {
    rep(j, n + 1) {
      k = (n - i - j);
      if (y == 10000 * i + 5000 * j + 1000 * k && 0 <= (n - i - j)) {
        cout << i << " " << j << " " << k << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
object Main {
    def isPrime(n: Int) = n > 1 && (2 to math.sqrt(n).toInt).forall(n % _ != 0)

    def main(args: Array[String]) = {
        val in = io.Source.stdin.getLines.map(_.toInt).toSeq.tail
        println(in.count(isPrime))
    }
}

Measured memory_bytes: 120908
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;


public class Main {

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

		char[] A = sc.next().toCharArray();

		Map<Character, Integer> maplst = new TreeMap<Character, Integer>() ;

		for (char c : A) {
			if (maplst.containsKey(c)) {
				maplst.put(c, maplst.get(c) + 1);
			}else {
				maplst.put(c, 1);
			}
		}
		boolean judge = true;
		if (maplst.keySet().size() == 2) {
			for (char c : maplst.keySet()) {
				if (maplst.get(c) != 2) {
					judge = !judge;
					break;
				}
			}
		}else {
			judge = !judge;
		}

		if (judge) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}
}


Measured memory_bytes: 35960