akhauriyash/Code-Regression huggingface dataset:
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(false);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  int N, M, K;
  cin >> N >> M >> K;
  vi A(N), B(M);
  cin >> A >> B;

  vi S;
  S.pb(0);
  rep(i, 0, N) S.pb(S.back() + A[i]);
  vi T;
  T.pb(0);
  rep(i, 0, M) T.pb(T.back() + B[i]);

  int ans = 0;
  rep(i, 0, sz(S)) {
    int r = K - S[i];
    if (r < 0) break;
    int j = prev(upper_bound(all(T), r)) - begin(T);
    chmax(ans, i + j);
  }
  cout << ans << endl;
  return (0 ^ _ ^ 0);
}



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

int N,Q;
ll A[100005];int len;
ll F[100005],c[100005];

void Solve(ll d,ll w){
	int j=upper_bound(A+1,A+len+1,d)-A-1;
	if(!j) c[1]+=w,c[d+1]-=w;
	else F[j]+=d/A[j]*w,Solve(d%A[j],w);
}

int main(){
	scanf("%d%d",&N,&Q);
	A[++len]=N;
	while(Q--){
		ll Ai;scanf("%lld",&Ai);
		while(len&&A[len]>=Ai) len--;
		A[++len]=Ai;
	}
	F[len]=1;
	for(int i=len;i>=2;i--) F[i-1]+=A[i]/A[i-1]*F[i],Solve(A[i]%A[i-1],F[i]);
	c[1]+=F[1];c[A[1]+1]-=F[1];
	for(int i=1;i<=N;i++) printf("%lld\n",c[i]+=c[i-1]);
}

Measured memory_bytes: 6116
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
using namespace std;

int main(){ 
  int n,x=0,y=0,ans=100000,c=0;
  cin>>n>>y;
  rep(i,0,n){
    cin>>x;
    if(x>=y) c++;
  }
  co(c);
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

const int INF = 1e9 + 239;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int ans = INF;
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &t : a) {
		cin >> t;
	}
	for (int p = 0; p <= 100; p++) {
		int c = 0;
		for (auto t : a) {
			c += (t - p) * (t - p);
		}
		ans = min(ans, c);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0;i <n;i++)
#define ALL(a) a.begin(), a.end()
int main(){
	ll n, v; cin >> n >> v; vector<ll> a(n), b(n), c(n), d(n);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	rep(i, n) cin >> c[i];
	rep(i, n) cin >> d[i];
	vector<ll> ab(n*n),cd(n*n);
	rep(i, n) {
		rep(j, n) {
			ab[i*n + j] = a[i] + b[j];
		}
	}sort(ALL(ab));
	rep(i, n) {
		rep(j, n) {
			cd[i*n + j] = c[i] + d[j];
		}
	}sort(ALL(cd));
	ll ans = 0;
	rep(i, ab.size()) {
		ans += (upper_bound(ALL(cd), v - ab[i]) - lower_bound(ALL(cd), v - ab[i]));
	}
	cout << ans << endl;
}


Measured memory_bytes: 18396
#include<bits/stdc++.h>
   using namespace std;
   int main()
   {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n;
   cin>>n;
  
   string str;
   int a=0,b=0,c=0,d=0;
   while(n--)
   {
       cin>>str;
       if(str=="AC")
       a++;
       else if(str=="WA")
       b++;
       else if(str=="TLE")
       c++;
       else if(str=="RE")
       d++;
   }

   cout<<"AC"<<" "<<"x"<<" "<<a<<endl;
   cout<<"WA"<<" "<<"x"<<" "<<b<<endl;
   cout<<"TLE"<<" "<<"x"<<" "<<c<<endl;
   cout<<"RE"<<" "<<"x"<<" "<<d<<endl;

   return 0;
   }

Measured memory_bytes: 3656
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    int d, n;
    cin >> d >> n;

    int ans = pow(100, d) * (n == 100 ? 101 : n);

    cout << ans << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int n,m,dp[202020],in[202020];
vector<int>v[202020];
queue<int>tpx;
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		v[a].push_back(b);
		in[b]++;
	}
	for(int i=0;i<n;i++)
	{
		if(!in[i])
		{
			tpx.push(i);
		}
	}
	while(tpx.size())
	{
        int i=tpx.front();
        tpx.pop();
        for(int j=0;j<v[i].size();j++)
		{
            dp[v[i][j]]=max(dp[i]+1,dp[v[i][j]]);
            in[v[i][j]]--;
            if(!in[v[i][j]])
			{
				tpx.push(v[i][j]);
			}
        }
    }
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9600
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
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 heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *

A, B = MAP()
a = Decimal(A)
b = Decimal(B)
# print(a, b)
print(floor(a * b))
exit()

Measured memory_bytes: 10708
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	int n;
	cin>>n;
	map<int, pll> m;
	vector<int> v(n+1, 0);
	rep(i, n) cin>>v[i];

	rep(i, n){
		if(m.count(-v[i])) m[-v[i]].fi++;
		else m[-v[i]] = {1LL,(ll)i};
	}
	vector<ll> ans(n+1, 0);

	while(m.size()>1){
		auto it = m.begin();
		auto nxt = m.begin();
		nxt++;
		int k = nxt->fi - it->fi;
		ll d = it->se.se;
		ll a = it->se.fi;
		ans[d] += (ll)k*a;

		int nf = nxt->fi;
		m[nf].se = min(d, m[nf].se);
		m[nf].fi += a;

		m.erase(it);
	}
	auto it = m.begin();
	int k = -it->fi;
	ans[it->se.se] += it->se.fi * k;
	rep(i, n){
		cout<<ans[i]<<endl;
	}
}


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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

int ceilDiv(int a, int b) {
	return (a+b-1) / b;
}

bool can(int a[], int n, int k, int m) {

	for (int i = 0; i < n; i++) {
		k -= ceilDiv(a[i], m) - 1;

		if (k < 0)
			return false;
	}

	return true;
}

int main() {

	IOS

	int n, k;
	cin >> n >> k;

	int a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int l = 1, r = 1000000001, mid;

	while (l < r) {
		mid = l + (r-l)/2;

		if (can(a, n, k, mid))
			r = mid;
		else
			l = mid+1;
	}

	cout << r;

	return 0;
}

Measured memory_bytes: 4372
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    if (t < a || b <= t) cnt++;
  }

  printf("%d\n", cnt);
  return 0;
}


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

int main(void){
    
    map<int,int> mp;
    
    for(int i = 1;i<=3;i++){
        mp[i]=0;
    }
    
    int A,B;
    cin >> A >> B;
    mp[A]=1;
    mp[B]=1;
    
    for(int i = 1;i<=3;i++){
        if(mp[i]==0)cout << i <<endl;
    }
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int D,N;
    cin >> D >> N;
    int base=1;
    for(int i=0; i<D; i++){
        base*=100;
    }
    if(N==100)
        cout << 101*base << endl;
    else
        cout << base*N << endl;
}

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

long gcd(long x, long y) {
    long a = y % x;
    if (a == 0) {
        return x;
    } else {
        return gcd(a, x);
    }
}

int main() {

    long a, b;
    while (cin >> a >> b) {
        long g = a < b ? gcd(a, b) : gcd(b, a);
        long l = a * b / g;
        cout << g << " " << l << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
let ($) f g = fun x -> g (f x)
let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n
let ab = Array.init (n - 1) @@ fun _ -> Scanf.sscanf (read_line ()) "%d %d" @@ fun a b -> (a - 1, b - 1)

module IntMap = Map.Make(struct type t = int let compare = compare end)

let edges = 
  let add k v idx map =
    let vs = try IntMap.find k map with Not_found -> [] in
    IntMap.add k ((idx, v) :: vs) map in
  fst @@ Array.fold_left (fun (map, i) (a, b) ->
    (add b a i @@ add a b i map, i + 1)
  ) (IntMap.empty, 0) ab

let () =
  let arr = Array.make (n - 1) 0 in
  let used = Array.make n false in
  let k = IntMap.bindings edges |> List.map (snd $ List.length) |> List.fold_left max 0 in
  let que = Queue.create () in
  Queue.add (0, k + 1) que;
  while not (Queue.is_empty que) do
    let node, col = Queue.pop que in
    let children = IntMap.find node edges |> List.filter (fun (_, v) -> not used.(v)) |> List.rev in
    used.(node) <- true;
    List.iteri (fun idx (i, v) -> 
      let c = idx + if idx < col - 1 then 1 else 2 in
      arr.(i) <- c;
      Queue.add (v, c) que;
    ) children;

  done;
  Printf.printf "%d\n" k;
  Array.iter (Printf.printf "%d\n") arr;


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

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int n;cin>>n;
  out(n*(n+1)/2);

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	char a;
	char hoge[21];
	int i, j;
	int A;
	
	scanf("%s", hoge);
	
	for (i = 0; i < 21; i++){
		a = hoge[i];
		if (a == '\0'){
			A = i;
			break;
		}
	}
	for (j = A-1; j > -1; j--){
		printf("%c", hoge[j]);
	}
	
	printf("\n");
	
	return (0);
}

Measured memory_bytes: 524
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
using namespace std;
#define INF 3e18+7
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

//http://kmjp.hatenablog.jp/entry/2016/10/10/0900

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

    int W,H;
    cin>>W>>H;
    vector<P> V;
    for(int i=0;i<W;i++){
        int x;
        cin>>x;
        V.push_back(P(x,0));
    }

    for(int i=0;i<H;i++){
        int x;
        cin>>x;
        V.push_back(P(x,1));
    }
    sort(V.begin(),V.end());
    ll ret=0;
    W++;
    H++;
    for(auto r:V){
        if(r.second==1) ret+=W*r.first,H--;
        else ret+=H*r.first,W--;
    }
    cout<<ret<<endl;

}

Measured memory_bytes: 6512
#include<stdio.h>
int main()
{
  int A[100];
  int n,i,j,v;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);
    for(i = 0;i < n ;i++)
	{
	  if(i)
	    printf(" ");
	  printf("%d", A[i]);
	}
      printf("\n");
  
  for(i=1; i < n; i++)
    {
      v = A[i];//i番目の値をvに代入
      j = i-1;//i-1番目のindexをjに代入
      while(j >= 0 && A[j] > v)//jが正かつi番目の値がi-1番目の値より小さかったら繰り返す
	{
	  int a = A[j+1];
	  A[j+1] =  A[j];//i-1番目の値をi番目の値に
	  A[j] = a;
	  j--;//indexを1下げる
	}
      A[j+1] = v;
      for(j = 0;j < n ;j++)
	{
	  if(j)
	    printf(" ");
	  printf("%d", A[j]);
	}
      printf("\n");
    }
  return 0;
}



Measured memory_bytes: 2084
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int n,i,m1,m2,mi,a[200000];
	scanf("%d",&n);
	for(i=0;i<n;i++)	scanf("%d",&a[i]);
	m1=-1;
	for(i=0;i<n;i++)	
	{
		if(m1<a[i])	{
			m1=a[i];	mi=i;
		}
	}
	m2=-1;
	for(i=0;i<n;i++)	{
		if(mi!=i)	{
			m2=max(m2,a[i]);
		}
	}
	for(i=0;i<n;i++)	{
		if(i==mi)	{
			printf("%d\n",m2);
		}
		else {
			printf("%d\n",m1);
		}
	}
	return 0;
}

Measured memory_bytes: 2304
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
int a,b,c,d,i,j;
int n[105];
scanf("%d",&a);
i=0;d=0;
while(a--)
{
    scanf("%d",&b);
    if(b%2==0)
    n[i++]=b;
}
for(j=0;j<i;j++)
{
    if(n[j]%3==0||n[j]%5==0)
        continue;
    else
    {
        d=1;
        break;
    }
}
if(d)
{
    printf("DENIED\n");
}
else
{

    printf("APPROVED\n");
}
}


Measured memory_bytes: 128
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 INT_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 INT_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<int>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


ll power2(ll num)
{
	ll i=0;

	while(!(num%2))
	{
		num = num/2;
		++i;
	}

	return i;


}


int main()
{
	ll n,m,i,p2,tot=1,gc,lc,c1,x,c2,y,xo;

	cin>>n>>m;

	ll a[n];

		//cout<<"Here\n";


	rep(i,0,n)
	{
		cin>>a[i];
	}

	p2 = power2(a[0]);


	for(i=1;i<n;++i)
	{
		if(power2(a[i])!=p2)
			break;
	}
	if((i!=n))
	{
		cout<<0<<"\n";
		return 0;
	}

	lc = a[0];

	for(i=1;i<n;++i)
	{
		gc = __gcd(lc,a[i]);
		lc = (lc*a[i])/gc;
	}


	xo = lc/2;

	ll d1,d2;
	double dd1,dd2;

	dd1 = (-1.0*m + xo)/(lc);
	dd2 = (-1.0 + xo)/(lc);



	d1 = ceil(dd1);
	d2 = floor(dd2);


	//cout<<lc<<"\n";
	//cout<<d1<<" "<<d2<<"\n";

	//cout<<dd1<<" "<<dd2<<"\n";

	//cout<<(ll)(d1-d2)<<"\n";

	ll ans = abs(d1-d2) + (ll)1;

	if(d1>d2)
		cout<<"0"<<"\n";
	else
		cout<<ans<<"\n";

















	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15) //15桁まで表示
#define str string
typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui,ui> puu;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<str> vs;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int floor(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
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;};

int main() {
    int a,b;
    cin >> a>>b;
    if (a+b>=10) cout << "error" << endl;
    else cout << a+b << endl;
}

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

int n;
int a[100000];
int cnt[100000];

int log2(int x) {
	int i;
	for (i = 0; (1 << i) < x; i++);
	return i;
}

int main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	for (i = 0; i < n; i++) cnt[log2(a[i] & -a[i])]++;
	
	int x = 0;
	for (i = 0; i < n; i++) x ^= a[i];
	
	int ans = 0;
	for (i = 29; i >= 0; i--) {
		if ((x >> i) % 2 == 0) continue;
		if (cnt[i] == 0) { cout << -1 << endl; return 0; }
		ans++;
		x = x ^ ((1 << i) - 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));
 
ll gcd(ll x, ll y){
	if(x<y) swap(x,y);
	if(y==0) return x;
	return gcd(y,x%y);
}
 
ll lcm(ll x, ll y){
	return (x*y/gcd(x,y));
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
////////////////////////////////////////////
	int n,a,b;
	cin >> n >> a >> b;
	cout << min(n*a,b) << endl;
	
/////////////////////////////////////////////
}

Measured memory_bytes: 256
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
a, b = [int(x) for x in input().split()]
try:
    print(next(x for x in range(2000) if 8 * x // 100 == a and 10 * x // 100 == b))
except StopIteration:
    print(-1)

Measured memory_bytes: 9116
#include <bits/stdc++.h>
#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 main() {
	int n;
	cin >> n;
	map<string, int> s;
	rep(i, n){
		string tmp;
		cin >> tmp;
		s[tmp]++;
	}
	int mx = 0;
	for(auto p: s) {
		int value = p.second;
		if(mx < value) mx = value;
	}
	for(auto p: s) {
		string key = p.first;
		int value = p.second;
		if(value == mx) cout << key << endl;
	}
	
	return 0;
}

Measured memory_bytes: 26240
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))


def res(nA, i):
    for i in range(min_A, max_A+1):
        tmp = sum([ abs(Ai - i) for Ai in nA ])
    if tmp < ans:
        ans = tmp
    return ans

N = int(input())
A = list(map(int, input().split()))

nA = sorted([ Ai - (i+1) for i, Ai in enumerate(A)])
ans = 10e9

if len(nA) % 2 != 0:
    print(sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ]))
else:
    print(min(sum([ abs(Ai - nA[len(nA)//2-1]) for Ai in nA ]), sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ])))


Measured memory_bytes: 36644
#include<cstdio>
#include<cmath>
#define For(i,A,B) for(i=(A);i<=(B);++i)
typedef long long ll;
const int P=200003;
const double pi=acos(-1.0);
const int Lim=1<<19;
int g[P],p[P],r[Lim+50];
struct cnum{
	double x,y;
	cnum(double x=0,double y=0):x(x),y(y){}
	inline cnum operator+(const cnum&b)const{return cnum(x+b.x,y+b.y);}
	inline cnum operator-(const cnum&b)const{return cnum(x-b.x,y-b.y);}
	inline cnum operator*(const cnum&b)const{return cnum(x*b.x-y*b.y,x*b.y+y*b.x);}
}a[Lim+50];
inline int Shl(int a){return (a<<=1)>=P?a-P:a;}
inline void FFT(short type){
	int i,j,M,R;
	cnum w,wn,t,tt;
	For(i,0,Lim-1)if(i<r[i]){t=a[i];a[i]=a[r[i]];a[r[i]]=t;}
	for(M=1,R=2;M<Lim;M<<=1,R<<=1){
		wn=cnum(cos(pi/M),sin(pi/M)*type);
		for(i=0;i<Lim;i+=R){
			w=cnum(1);
			For(j,0,M-1){
				t=a[i+j];tt=a[i+M+j]*w;
				a[i+j]=t+tt;a[i+M+j]=t-tt;
				w=w*wn;
			}
		}
	}
}
int main(){
	int n,i,x;
	ll ans=0ll;
	scanf("%d",&n);
	g[0]=1;
	For(i,1,P-2)p[g[i]=Shl(g[i-1])]=i;
	For(i,1,n){
		scanf("%d",&x);
		if(x){
			ans-=(ll)x*x%P;
			a[p[x]].x+=1;
		}
	}
	For(i,0,Lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<18);
	FFT(1);
	For(i,0,Lim-1)a[i]=a[i]*a[i];
	FFT(-1);
	For(i,0,P-2)ans+=(ll)((a[i].x+a[i+P-1].x)/Lim+0.5)*g[i];
	printf("%lld\n",ans>>1);
	return 0;
}

Measured memory_bytes: 14252
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        int gakuseiCount = inpt[0];
        int pointCount = inpt[1];

        for (int i = 0; i < gakuseiCount; i++)
        {
            this.Gakusei.Add(i + 1, new Pos(Reader.ReadLine()));
        }
        for (int i = 0; i < pointCount; i++)
        {
            this.CheckPoint.Add(i + 1, new Pos(Reader.ReadLine()));
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < gakuseiCount; i++)
        {
            int moyori = CheckPoint.OrderBy(a => Math.Abs(a.Value.X - Gakusei[i + 1].X) + Math.Abs(a.Value.Y - Gakusei[i + 1].Y)).ThenBy(a => a.Key).First().Key;
            ans.AppendLine(""+moyori);
        }
        Console.Write(ans.ToString());
    


    }

    private Dictionary<int, Pos> Gakusei = new Dictionary<int, Pos>();
    private Dictionary<int, Pos> CheckPoint = new Dictionary<int, Pos>();

    public struct Pos
    {
        public int X;
        public int Y;
        public Pos(string init)
        {
            int[] tmp = init.Split(' ').Select(a => int.Parse(a)).ToArray();
            this.X = tmp[0];
            this.Y = tmp[1];
        }
    }



    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"



3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5


";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 11488
#include <iostream>
using namespace std;
long long a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;
char A,B,C,D;
int main()
{
	cin>>A>>B>>C>>D;
	a=A-48;
	b=B-48;
	c=C-48;
	d=D-48;
	if(a+b+c+d==7)
	{
		cout<<a<<'+'<<b<<'+'<<c<<'+'<<d<<"=7"<<endl;
		return 0;
	}
	if(a-b+c+d==7)
	{
		cout<<a<<'-'<<b<<'+'<<c<<'+'<<d<<"=7"<<endl;
		return 0;
	}
	if(a+b-c+d==7)
	{
		cout<<a<<'+'<<b<<'-'<<c<<'+'<<d<<"=7"<<endl;
		return 0;
	}
	if(a+b+c-d==7)
	{
		cout<<a<<'+'<<b<<'+'<<c<<'-'<<d<<"=7"<<endl;
		return 0;
	}
	if(a-b-c+d==7)
	{
		cout<<a<<'-'<<b<<'-'<<c<<'+'<<d<<"=7"<<endl;
		return 0;
	}
	if(a-b+c-d==7)
	{
		cout<<a<<'-'<<b<<'+'<<c<<'-'<<d<<"=7"<<endl;
		return 0;
	}
	if(a+b-c-d==7)
	{
		cout<<a<<'+'<<b<<'-'<<c<<'-'<<d<<"=7"<<endl;
		return 0;
	}
	if(a-b-c-d==7)
	{
		cout<<a<<'-'<<b<<'-'<<c<<'-'<<d<<"=7"<<endl;
		return 0;
	}
/*	for(i='+';i<='-';i+=2)
	{
		for(k='+';k<='-';k+=2)
		{
			for(j='+';j<='-';j+=2)
			{
				
			}
		}
	}*/
}

Measured memory_bytes: 256
n = int(input())

v = list(map(int, input().split( )))
##
v1 = v[0::2]
v2 = v[1::2]
##

##
from  collections import Counter

n1 = len(v1)
n2 = len(v2)
v11 = Counter(v1)
v21 = Counter(v2)

##
#c1 = Counter.most_common(v11)
#c2 = Counter.most_common(v21)
c1 = v11.most_common(2)
c2 = v21.most_common(2)

#print(c2)
#print(v21)
#print(v11[c1])　エラー

###
###
if c1[0][0]!=c2[0][0]:
    print(n1-c1[0][1]+n2-c2[0][1])
else:
    try:
        ans1 = n1-c1[1][1]+n2-c2[0][1]
        ans2 = n1-c1[0][1]+n2-c2[1][1]
        print(min(ans1,ans2))
    except:
        try:
            ans1 = n1-c1[1][1]+n2-c2[0][1]
            #ans2 = n1-c1[0][1]+n2-c2[1][1]
            print(ans1)
        except:
            try:
                ans2 = n1-c1[0][1]+n2-c2[1][1]
                print(ans2)
            except:
                print(len(v2))


Measured memory_bytes: 18936
from sys import stdin
from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)

def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    t=[int(readline()) for _ in range(n)]

    ans=1
    for i in range(n):
        ans=lcm(ans,t[i])

    print(ans)

if __name__=="__main__":
    main()

Measured memory_bytes: 5500
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0

for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i-1] + dp[i-2]
  dp[i] %= mod
  
print(dp[n])

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

const int MX = 100005;
int main() {
  int N;
  cin >> N;

  vector<int> v(MX, 0);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    // 0 から 1 を引くケースを 0 以上の要素数で管理するために加算
    a++;

    v.at(a - 1)++;
    v.at(a)++;
    v.at(a + 1)++;
  }

  int ans = 0;
  for (int i = 0; i < MX; i++) {
    ans = max(ans, v.at(i));
  }

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

Measured memory_bytes: 3784
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <queue>
using namespace std;
using ll = long long;
using Lf = long double;
using plong = pair<ll,ll>;
const int mod = 1000000007;
 
vector<bool> res;
string S;
ll N;
bool ok(bool fir,bool sec,vector<bool> res){
    bool flag = true;
    if(res[1]&&fir){
        if(res[0]!=res[2])flag = false;
    }else if(!res[1]&&fir){
        if(res[0]==res[2])flag = false;
        
    }else if(res[1]&&!fir){
        if(res[0]==res[2])flag = false;
        
    }else{
        if(res[0]!=res[2])flag = false;
        
    }

    if(res[2]&&sec){
        if(res[1]!=res[3])flag = false;
    }else if(!res[2]&&sec){
        if(res[1]==res[3])flag = false;
    }else if(res[2]&&!sec){
        if(res[1]==res[3])flag = false;
    }else{
        if(res[1]!=res[3])flag = false;
    }
    return flag;

}

bool sw(bool fir,bool sec){
    res[0] = fir;
    res[1] = sec;
    for(ll i=1;i<N-1;i++){
        if(res[i]){
            if(S[i]=='o'){
                res[i+1]=res[i-1];
            }else{
                res[i+1]=!res[i-1];
            }
        }else{
            if(S[i]=='o'){
                res[i+1]=!res[i-1];
            }else{
                res[i+1]=res[i-1];
            }
        }
    }
    vector<bool> tmp;
    tmp.push_back(res[N-2]);
    tmp.push_back(res[N-1]);
    tmp.push_back(res[0]);
    tmp.push_back(res[1]);
    return ok(S[N-1]=='o',S[0]=='o',tmp);

}

int main(){
 
    cin>>N>>S;
    res.resize(N); //true:Sheep, false: Wolfe
    if(sw(true,true))goto END;
    if(sw(true,false))goto END;
    if(sw(false,false))goto END;
    if(sw(false,true))goto END;
    cout<<-1<<endl;
    return 0;
END:
    for(ll i=0;i<N;i++){
        cout<<(res[i]?"S":"W");
    }
    cout<<endl;

}

Measured memory_bytes: 512
import math

menu = [int(input()) for i in range(5)]
remain = [l % 10 for l in menu]

if sum(remain) == 0:
    print(sum(menu))
else:
    cost = [math.ceil(l / 10) for l in menu]
    for i in range(5):
        if remain[i] == 0:
            remain[i] = 10
    print(10 * sum(cost) - 10 + remain[remain.index(min(remain))])

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, K, A = 1;
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        if (A * 2 < A + K) A *= 2;
        else {
            for (; i < N; i++) A += K;
            break;
        }
    }

    cout << A << endl;
}

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

int euclidean(int, int);

int main(int argc, char const *argv[])
{
	int a, b;
	cin >> a >> b;

	printf("%d\n", euclidean(a, b));

	return 0;
}


int euclidean(int a, int b)
{
	int r = 0, q = 0;

	if (a == 0) return b;
	if (b == 0) return a;

	if (a >= b)
	{
		do
		{
			q = a / b;
			r = a % b;
			if (r == 0) break;
			a = b;
			b = r;
		} while(r != 0);
		return b;
	}
	else
	{
		do
		{
			q = a / b;
			r = b % a;
			if (r == 0) break;
			b = a;
			a = r;
		} while(r != 0);
		return a;

	}
}

Measured memory_bytes: 1144
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = sc.nextInt();
        }
        int count = BubbleSort(A, N);
        for(int i = 0; i < N; i++){
            if(i < N - 1){
                System.out.print(A[i] + " ");
            }else{
                System.out.print(A[i]);
            }
        }
        System.out.println("");
        System.out.println(count);
    }

    public static int BubbleSort(int[] a, int n){
        boolean TF = true;
        int i = 0;
        int c = 0;
        while(TF){
            TF = false;
            for(int j = n - 1; j >= i + 1; j--){
                if(a[j] < a[j - 1]){
                    int x = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = x;
                    TF = true;
                    c++;
                }
            }
            i++;
        }
        return c;
    }
}


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

#define int long long

using namespace std;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int cnt = (n + 1) / 2;
  if (cnt >= k) {
    cout << "YES" << "\n";
  }
  else {
    cout << "NO" << "\n";
  }
  return 0;
}


Measured memory_bytes: 256
const inputText = require("fs")
  .readFileSync("/dev/stdin", "utf8")
  .split(/\s/)
  .map((i) => parseInt(i, 10));

const left = inputText[0] + inputText[1];
const right = inputText[2] + inputText[3];

if (left < right) {
  console.log("Right");
} else if (left > right) {
  console.log("Left");
} else {
  console.log("Balanced");
}

Measured memory_bytes: 11468
#include <bits/stdc++.h>
#define EPS 1e-9
#define PI acos(-1)
using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
ll a[maxn];
ll n,A,B;

bool check(ll res)
{
    ll num = 0;
    for(int i = 1; i <= n; i++)
    {
        ll tmp = a[i]-res*B;
        if(tmp>0)
        {
            num += (tmp-1)/(A-B)+1;
        }
    }
    if(num>res) return false;
    else return true;
}

int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>A>>B;
    ll l = 1;
    ll r = 0;
    for(int i = 1; i <=n ;i++ )
    {
        cin>>a[i];
        r += a[i]/B+1;
    }

    //ll ans;
    while(l<r)
    {
        ll mid = l+r>>1;
        if(check(mid))
        {
            r = mid;
            //ans = mid;
        }
        else
        {
            l = mid+1;
        }
    }
    cout<<l<<"\n";
}


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

int main()
{
    int s, w; cin >> s >> w;

    if (s > w) {
        cout << "safe" << endl;
    }else{
        cout << "unsafe" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3636
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
//typedef long long int LL;
//typedef __int64 LL;

int main()
{
	int K, T;
	int a[1004];
	scanf("%d %d", &K, &T);
	int sum = 0, max = 0;
	for (int i = 0; i < T; i++) {
		int u;
		scanf("%d", &u);
		sum += u;
		max = MAX(max, u);
	}

	if (T == 1) {
		printf("%d\n", sum - 1);
		return 0;
	}

	sum -= max;
	if (sum >= max - 1) {
		printf("0\n");
		return 0;
	}
	max -= sum + 1;
	printf("%d\n", max);
	return 0;
}


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

using namespace std;

//各桁の和を計算する
int findSumOfDigits(int n) {
    int sum = 0;
    while(n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    int total = 0;

    for(int i = 1; i <= N; ++i) {
        int sum = findSumOfDigits(i);
        if(sum >= A && sum <= B) { //iの各桁の和がA以上B以下の場合
            total += i;
        }
    }
    cout << total << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
const int MAXN=2e5+7;
int s[MAXN],t[MAXN];
long long merge (int l,int r,int mid) {
	int t1=l,t2=mid,pos=l;
	long long ret=0;
	while (pos<r) {
		if (t2==r||(t1<mid&&s[t1]<s[t2])) t[pos++]=s[t1++];
		else {
			t[pos++]=s[t2++];
			ret+=mid-t1;
		}
	}
	for (int i=l;i<r;i++) {
		s[i]=t[i];
	}
	return ret;
}
long long mergeSort (int l,int r) {
	if (r-l<2) return 0;
	int mid=(l+r)>>1;
	long long ret=0;
	ret+=mergeSort (l,mid);
	ret+=mergeSort (mid,r);
	ret+=merge (l,r,mid);
	return ret;
}
int main () {
	int n;
	scanf ("%d",&n);
	for (int i=0;i<n;i++) {
		scanf ("%d",&s[i]);
	}
	printf ("%lld\n",mergeSort (0,n));
    return 0;
}


Measured memory_bytes: 4304
#include <stdio.h>

int check(int n, int *h) {
  int i;

  for (i = 0; i < n ; i++) {
    if (h[i] != 0) {
      return 0;
    }
  }

  return 1;
}

int solv(int n) {
  int i, j, h[100];

  for (i = 0; i < n; i++) {
    scanf("%d", h + i);
  }

  for (i = 0; check(n, h) == 0; i++) {
    for (j = 0; j < n && h[j] == 0; j++) {}
    // j は最初の水やり花壇
    for (; j < n && h[j] != 0; j++) {
      h[j]--;
    }
  }

  return i;
}

int main(int argc, char **argv) {
  int n;

  while (scanf("%d\n", &n) != EOF) {
    printf("%d\n", solv(n));
  }

  return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  // cout << (long double)sqrt(static_cast<long double>(a)) << endl;
  // cout << (long double)sqrt(a) << endl;
  // cout << (long double)sqrt(a) << endl;
  // cout << -(a + b - c)/2.0 << endl;
  // if ( -(a + b - c)/2.0 > sqrt(static_cast<long double>(a)) *
  // sqrt(static_cast<long double>(b)) ){
  if (a + b - c < 0) {
    if ((a + b - c) * (a + b - c) > 4 * a * b) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = [int(x)-48 for x in read().rstrip()]

ans = 0

dp = [[0]*(len(N)+1) for i in range(2)]


dp[1][0] = 1
dp[0][0] = 0


for i in range(1, len(N)+1):
    dp[0][i] = min(dp[0][i-1] + N[i-1],
                   dp[1][i-1] + (10 - N[i-1]))

    dp[1][i] = min(dp[0][i-1] + N[i-1] + 1,
                   dp[1][i-1] + (10 - (N[i-1] + 1)))


print(dp[0][len(N)])



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

using namespace std;
typedef long long ll;
ll mod = 1e9+7;

int main(void)
{
  ll N,K,S;cin>>N>>K>>S;
  for(ll i=0;i<K;i++){
    cout<<S<<" ";
  }
  
  ll out;
  if(S==1e9)out=1e9-1;
  else out=S+1;
  for(ll i=K;i<N;i++){
    if(i==N-1)cout<<out<<endl;
    else cout<<out<<" ";
  }

  return 0;
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;  // 2次元配列
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
//    cout << fixed << setprecision(15);

    string s, t;
    i32 n,m,x,y;
    cin >> n;
    vi a(n+1);
    for(int i = 2; i <= n; ++i) cin >> a[i];

    vi b(n+1);
    for(auto aa : a) {
        ++b[aa];
    }

    for(int i = 1; i <= n; ++i) cout << b[i] << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 6412
n = int(input())

ans = list()

for i in range(2, n // 2):
    a = sum([int(j) for j in str(i)])
    b = sum([int(j) for j in str(n - i)])
    ans.append(a + b)

if len(ans) > 0:
    print(min(ans))
else:
    print(2)

Measured memory_bytes: 3480
#include<iostream>

int main(){
	int n;
	int count = 0;
	while (std::cin >> n){
		count = 0;
		if (n <= 36){
			for (int a = 0; a <= 9; ++a){
				for (int b = 0; b <= 9; ++b){
					for (int c = 0; c <= 9; ++c){
						if (a + b + c >= n - 9 && a + b + c <= n)++count;
					}
				}
			}
		}
		std::cout << count << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1160
use std::collections::VecDeque;

fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

type Graph = Vec<Vec<usize>>;

fn bfs(graph: &Graph, dist: &mut Vec<i64>, queue: &mut VecDeque<usize>, result: &mut Vec<usize>) {
    while !queue.is_empty() {
        let v = queue.pop_front().unwrap();
        for next_v in &graph[v] {
            if dist[*next_v] == -1 {
                dist[*next_v] = dist[v] + 1;
                queue.push_back(*next_v);
                result[*next_v] = v;
            }
        }
    }
}

fn check(graph: &Graph, dist: &Vec<i64>) -> bool {
    let mut queue: VecDeque<usize> = VecDeque::new();

    while !queue.is_empty() {
        let v = queue.pop_front().unwrap();
        for next_v in &graph[v] {
            if dist[*next_v] == -1 {
                return false;
            }
        }
    }
    return true;
}

fn main() {
    let (n, m) = {
        let nm = get_line().split_whitespace()
            .map(|e| e.parse().unwrap())
            .collect::<Vec<usize>>();
        (nm[0], nm[1])
    };

    let mut graph: Graph = vec![Vec::new(); n];

    for _ in 0..m {
        let (a, b) = {
            let ab = get_line().split_whitespace()
                .map(|e| e.parse().unwrap())
                .collect::<Vec<usize>>();
            (ab[0], ab[1])
        };
        // index
        let a = a - 1; let b = b - 1;
        graph[a].push(b);
        graph[b].push(a);
    }

    let mut dist = vec![-1; n];
    let mut queue: VecDeque<usize> = VecDeque::new();
    let mut result: Vec<usize> = vec![0; n];

    // スタートから各部屋までの最短距離
    dist[0] = 0;
    queue.push_back(0);
    bfs(&graph, &mut dist, &mut queue, &mut result);
    
    if !check(&graph, &dist) {
        println!("No");
    } else {
        println!("Yes");
        for x in &result[1..] {
            println!("{}", x + 1);
        }
    }
}


Measured memory_bytes: 12592
#include<iostream>
using namespace std;
int a[100001];
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]%4==0)ans+=2;
else if(a[i]%2==0)ans++;

}
if(ans>=n/2*2)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}


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


int main()
{
	long long k, a, b;
	cin >> k >> a >> b;
	if (a%k == 0)
	{
		cout << "OK" << "\n";
	}
	else if ((a / k + 1)*k <=b)
	{
		cout << "OK" << "\n";
	}
	else
	{
		cout << "NG" << "\n";
	}
	
    return 0;
}

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

int main() {
    int n,k,q,num;
    cin>>n>>k>>q;
    vector<int> a(n,k);

    rep(i,q) {
        cin>>num;
        a[num-1]++;
    }

    rep(i,n) {
        a[i]-=q;
        if (a[i] <= 0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}


Measured memory_bytes: 1024
def main():
    import heapq
    n, m, *a = map(lambda x: -int(x), open(0).read().split())
    heapq.heapify(a)
    while m:
        x = heapq.heappop(a)
        heapq.heappush(a, x / 2)
        m += 1
    ans = -sum(map(lambda x: int(x), a))
    print(ans)
    


if __name__ == '__main__':
    main()


Measured memory_bytes: 14180
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().rstrip().split())
    # K -= 1
    dp = [[0] * W for _ in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for k in range(2**(W-1)):
                b = bin(k)[2:].zfill(W-1)
                # 2つの横線がつながってないか調べる
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    # 左方向に横線を辿るケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[j] == '1':
                    # 右方向に横線を辿るケース
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    # 横線を辿らないケース
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD

    print(dp[H][K-1])
    

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188