akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main() {
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, m;
	cin >>n  >>m;
	
	vector<VI> r(n);
	VI cnd(n);
	vector<vector<bool>> aru(n, vector<bool>(n));
	rep(i, m){
		int a,b; cin >>a >>b; a--;b--;
		r[a].push_back(b);
		aru[a][b] = true;
		cnd[a] |=1; cnd[b] |=2;
	}
	auto bfs =[&](int s) -> vector<pii>{
		
		vector<pii>  dd(n, pii(MD, -1));
		queue< int > que;
		que.push(s); dd[s] = pii(0, -2);
		while(!que.empty()){
			int cr = que.front();
			que.pop();
			for(auto x: r[cr]){
				if(dd[x].second == -1){
					que.push(x);
					dd[x] = pii(dd[cr].first+1, cr);
				}
			}
		}
		return dd;
	};
	
	int mn = MD;
	pair<VI, int> bst =make_pair(VI{}, -1);
	rep(i, n){
		if((cnd[i]&3) !=3) continue;
		auto rv = bfs(i);
		VI wv(n);
		rep(j, n) wv[j] = rv[j].second;
		rep(j, n) if(j!=i && wv[j] >=0 && aru[j][i]){
			if(mn > rv[j].first){
				mn = rv[j].first;
				VI cz;
				rep(i, n)
				bst = make_pair(wv, j);
			}
		}
	}
	if(bst.second == -1) puts("-1");
	else{
		VI ans;
		int p = bst.second;
		while(p >=0){
			ans.push_back(p);
			p = bst.first[p];
		}
		reverse(all(ans));
		cout << sz(ans) <<"\n";
		for(auto z: ans) cout << z+1 <<"\n";
	}
	return 0;
	
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	ll X; cin >> X;
	ll cnt = 100;
	int ans = 0;
	while (cnt < X) {
		cnt += cnt / 100;
		++ans;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdlib>

using namespace std;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}


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

  int* in = new int[n];

  int count = 0;
  for(int i=0;i<n;i++){
    cin >> in[i];
    if( IsPrime( in[i]) ) count++;
  }

  cout << count << endl;

  
  
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

int w[101], v[101];
ll dp[101][100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, W; cin >> N >> W;
	for (int i = 1; i <= N; i++) cin >> w[i] >> v[i];
	dp[0][0] = 0; fill(dp[0] + 1, dp[0] + W + 1, -2e18);
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	ll ans = -2e18;
	for (int i = 0; i <= W; i++) ans = max(ans, dp[N][i]);
	cout << ans << '\n';
	return 0;
}

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

using namespace std;

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

  sort(a, a + n);

  int maxf = -1, maxs = -1;
  for(int i = n - 1; i >= 0; i--) {
    if(a[i] == a[i - 1]) {
      maxf = i;
      break;
    }
    else if(i == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  for(int i = maxf - 2; i >= 0; i--) {
    if(a[i] == a[i - 1]) {
      maxs = i;
      break;
    }
    else if(i == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  if(maxf == -1 || maxs == -1) {
    cout << 0 << endl;
  }

  cout << (long long int)a[maxf] * a[maxs] << endl;
}

Measured memory_bytes: 768
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int A = sc.nextInt();
    int ans = 0;
    if (H%A == 0) {
      ans = H / A;
    }else{
      ans = H / A + 1;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 35804
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr first
#define sc second
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=3e5+10;
int main()
{
    FASTINOUT;
    int x;
    cin>>x;
    int a[x];
    for (int i=0;i<x;i++)
        cin>>a[i];
    sort(a,a+x);
    reverse(a,a+x);
    ll k=-1,m=-1;
    bool b=false;
    for (int i=1;i<x;i++){
        if (a[i]==a[i-1]){
            if (!b){
            k=a[i];
            b=true;
            i++;
            }
            else{
                m=a[i];
                break;
            }

        }
    }
    if (m==-1)
        cout<<0<<endl;
    else
        cout<<k*m<<endl;
    return 0;
}


Measured memory_bytes: 640
require 'matrix'
loop do
  s = gets.chomp.chop
  break if s == ''

  #lookahead(?!  )
  s.gsub!(/([A-Z\)])(?![a-z\d])/, '\11')
  s.gsub!(/([A-Z][a-z])(?!\d)/, '\11')
  s.gsub!(/\((.+?)\)(\d*)/){
    as, n = $1, $2
    as.gsub(/([a-zA-Z])(\d+)/){"#{$1}#{$2.to_i * n.to_i}"}
  }
  atoms = s.scan(/[A-Z][a-z]?/)
  atoms.uniq!
  molecules = s.split('->').map{|ms| ms.split('+')}
  l = molecules[0].size
  molecules.flatten!
  m = molecules.size - 1
  n = atoms.size

  a = Matrix.build(n, m){|y, x|
    atom = atoms[y]
    k = 0
    molecules[x].scan(/#{atom}(\d+)/).each{|a|
      k += a[0].to_i
    }
    if k > 0
      (x >= l ? -k : k).to_r
    else
      0.to_r
    end
  }.to_a

  b = [0] * n
  atoms.each do |atom|
    molecules[-1].scan(/(#{atom})(\d+)/).each{|a, k|
      b[atoms.index(a)] = k.to_r
    }
  end
  # Gauss-Jordan elimination
  (0...[n,m].min).each do |i|
    pv = (i...n).max{|k| a[k][i].abs}
    a[i], a[pv] = a[pv], a[i]
    b[i], b[pv] = b[pv], b[i]
    (0...n).each do |j|
      next if i == j
      r = a[j][i] / a[i][i]
      (i...m).each do |k|
        a[j][k] -= r * a[i][k]
      end
      b[j] -= r * b[i]
    end
  end

  ans = (Matrix[*a[0,m]].inv * Vector[*b[0,m]]).to_a + [1.to_r]
  lcm = ans.map(&:denominator).reduce(&:lcm)
  puts ans.map{|x| (x * lcm).to_i} * ' '
end

Measured memory_bytes: 10060
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	A, B, C := nextInt(), nextInt(), nextInt()
	for i := 0; i < 1000; i++ {
		if A%2 == 1 {
			fmt.Println(i)
			return
		}
		if B%2 == 1 {
			fmt.Println(i)
			return
		}
		if C%2 == 1 {
			fmt.Println(i)
			return
		}

		ta := (B + C) / 2
		tb := (A + C) / 2
		tc := (A + B) / 2

		A = ta
		B = tb
		C = tc

	}

	fmt.Println(-1)
}


Measured memory_bytes: 640
if __name__ == "__main__":
    x1, y1, x2, y2 = map(int, input().split())

    x4 = x1 - (y2 - y1)
    y4 = y1 + (x2 - x1)

    x3 = x4 + (x2-x1)
    y3 = y4 + (y2-y1)

    print(x3, y3, x4, y4)


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

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

using namespace std;

using ll = long long;
using P = pair<int , int>;
  
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m; cin >> n >> m;
  vector<P> v(m);
  rep(i, m) {
    int x, y; cin >> x >> y;
    v[i] = make_pair(y, x);
  }
  sort(v.begin(), v.end());

  int ans = 1;
  int np = v[0].first;
  rep(i, m) {
    if(np <= v[i].second) {
      np = v[i].first;
      ++ans;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    ArrayList<Integer> points;
    String[] s;
    Integer[] pp;
    HashMap<Integer, Integer> t;
    int n, p;

    void run(){
	t = new HashMap<Integer, Integer>();
	points = new ArrayList<Integer>();
	while(sc.hasNext()){
	    s = sc.next().split(",");
	    n = Integer.parseInt(s[0]);
	    p = Integer.parseInt(s[1]);
	    if(!(n==0 && p==0)){
		t.put(n, p);
		if(!points.contains(p))
		    points.add(p);
	    }
	    else{
		pp = new Integer[points.size()];
		points.toArray(pp);
		Arrays.sort(pp);
		solve();
	    }
	}
    }

    void solve(){
	while(sc.hasNext()){
	    int x = sc.nextInt();
	    int y = t.get(x);

	    int ans=0;
	    while(pp[ans]!=y) ans++;

	    System.out.println(pp.length - ans);
	}
    }
}

Measured memory_bytes: 17216
#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

const ll mod = 998244353;
const int N = 1e2 + 10, M = 1e6 + 10;
const double INF = 1e20;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

#define pi acos(-1)


int main()
{
    int x;
    cin >> x;
    int ans = x / 500 * 1000 + x % 500 / 5 * 5;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

const int mod = 1e9 + 7;

int main(){
    int n; cin >> n;
    ll ans = 1;
    for(int i = 1; i <= n; i++){
        ans *= i;
        ans %= mod; 
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	int N; cin >> N;

	map<string, bool> mp;
	string p;
	cin >> p;
	mp[p] = true;

	for (int i = 1;i < N;i++){
		string s; cin >> s;
		if(p[p.size()-1] != s[0]){
			cout << "No" << endl;
			return 0;
		}
		if(mp[s]){
			cout << "No" << endl;
			return 0;
		}
		mp[s] = true;
		p = s;
	}

	cout << "Yes\n";

	return 0;

}


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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REPR(i,a,b) for(ll i=b;i>=a;i--)
#define repr(i,n) REPR(i,0,n)
#define all(v) (v).begin(), (v).end()
#define pb push_back

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

    ll n,ans=1;
    cin >> n;
    REP(i,1,n+1){
        ans *= i;
        ans %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

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

int main(){
    int h,w;
    cin>>h>>w;
    string s;
    for(int i=0;i<w+2;i++)cout<<"#";
    cout<<endl;
    for(int i=0;i<h;i++){
        cin>>s;
        cout<<"#"<<s<<"#"<<endl;
    }
        for(int i=0;i<w+2;i++)cout<<"#";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3604
def input_n
  gets.to_i               # 単一整数
end

def input_s
  gets.chomp              # 文字列。chompを付けないと改行文字がついてくる
end

def input_a
  gets.split.map(&:to_i)  # スペースで区切られた複数の整数
end

def input_o(num)
  num.times.map { gets.to_i }  # 縦に並んだ複数の整数。たまにある
end

def output_f(num)
  puts sprintf("%.12f", num)
end

a, b, n = input_a

# 問題文を式に直すと
# (a * x / b).floor - a * (x / b).floor
# となっていて、第二項「a * (x / b).floor」がマイナスであるため、この項の値が少なければ少ないほど嬉しい
# また、第一項「(a * x / b).floor」については、xが大きくなるほど大きくなる(a, bは入力によって固定されている)単調増加であることがわかる(floorに惑わされがちだが無視すればなんてことのない「a * x / b」なので)
# よって、以上の点から第二項を0にして、かつ第一項が最大の値をとるxは x = b - 1 となる。ただし、x <= n という条件があるため、b - 1 が n より大きい場合は x = n である。
x = [n, b - 1].min
# ruby では整数同士の計算であればfloorは要らない
puts (a * x / b)

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

int A,B,C,X;

int main() {
    cin >> A >> B >> C >> X;
    int count=0;
    
    for (int i=0; i<A+1;++i){
      for (int j=0;j<B+1;++j){
        for (int l=0;l<C+1;++l){
          if ((500*i+100*j+50*l)==X) ++count;
        }
      }
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>

using namespace std;

using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
const int inf = 1e+9;


int main() {
	ll n,m;
	cin >> n >> m;

	ll max_v = 1;
	for (ll i = 1; i * i <= m; i++) {
		if (m % i == 0) {
			if (m / i >= n) {
				max_v = max(i, max_v);
			}
			if (i >= n) {
				max_v = max(m / i, max_v);
			}
		}
	}
	cout << max_v << endl;

	return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << #x << '=' << x << '\n'
const long long MOD=1e9+7;
//const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<class T1,class T2> inline bool chmin(T1 &a,T2 b){
    if (a>b){a=b; return true;} return false;
}
template<class T1,class T2> inline bool chmax(T1 &a,T2 b){
    if (a<b){a=b; return true;} return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,X; cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N,vector<int>(M));
    for (int i=0;i<N;++i){
        cin >> C[i];
        for (int j=0;j<M;++j) cin >> A[i][j];
    }
    int ans=INF;
    for (int mask=0;mask<(1<<N);++mask){
        int cnt=0;
        vector<int> sum(M,0);
        for (int i=0;i<N;++i) if (mask&1<<i){
            cnt+=C[i];
            for (int j=0;j<M;++j) sum[j]+=A[i][j];
        }
        int ok=1;
        for (int i=0;i<M;++i) if (sum[i]<X) ok=0;
        if (ok) chmin(ans,cnt);
    }
    cout << (ans==INF?-1:ans) << '\n';
}

Measured memory_bytes: 3664
using System;
using System.Collections.Generic;

namespace AtCoderCpp
{
    // ABC-126
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var in1 = int.Parse(input.Substring(0, 2));
            var in2 = int.Parse(input.Substring(2, 2));

            var in1MM = in1 > 0 && in1 <= 12;
            var in2MM = in2 > 0 && in2 <= 12;

            if (in1MM && in2MM)
            {
                Console.WriteLine("AMBIGUOUS");
            }
            else if (in1MM && !in2MM)
            {
                Console.WriteLine("MMYY");
            }
            else if (!in1MM && in2MM)
            {
                Console.WriteLine("YYMM");
            }
            else
            {
                Console.WriteLine("NA");
            }
        }
    }
}


Measured memory_bytes: 13140
#include <stdio.h>

int main() {

    int a, b, c, d;

    scanf("%d%d%d%d", &a, &b, &c, &d);

    if (c > b || a > d) {
        printf("0\n");
    }

    else if (c < a  && d < b ) {
        printf("%d\n", d-a);
    }

    else if (c < a  && d > b ) {
        printf("%d\n", b-a);
    }

    else if (c > a && d > b ) {
        printf("%d\n", b-c);
    }

    else if (c > a && d < b ) {
        printf("%d\n", d-c);
    }

    else if (a > c && b == b) {
        printf("%d\n", d-a);
    }

    else if (a < c && b == d) {
        printf("%d\n", b-c);
    }

    else if (a == c && b == d) {
        printf("%d\n", b-c);
    }

    else if (a == c && b > d) {
        printf("%d\n", d-a);
    }

    else if (a == c && b < d) {
        printf("%d\n", b-c);
    }


    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		Scanner sc = null;
		try {
			sc = new Scanner(System.in);
			int countRectangle = 0;
			int countRhombus = 0;
			while (sc.hasNextLine()) {
				String[] input = sc.nextLine().split(",");
				int[] x = new int[3];
				for (int i = 0; i < 3; i++)
					x[i] = Integer.parseInt(input[i]);
				if (x[0] * x[0] + x[1] * x[1] == x[2] * x[2])
					countRectangle++;
				else if (x[0] == x[1])
					countRhombus++;
			}
			System.out.println(countRectangle);
			System.out.println(countRhombus);
		} finally {
			sc.close();
		}
	}
}

Measured memory_bytes: 17140
N = int(input())
count_ac = 0
count_wa = 0
count_tle = 0
count_re = 0
for i in range(N):
    s = input()
    if s == "AC":
        count_ac += 1
    elif s == "WA":
        count_wa += 1
    elif s == "TLE":
        count_tle += 1
    elif s == "RE":
        count_re += 1

s1 = "AC x " + str(count_ac)
s2 = "WA x " + str(count_wa)
s3 = "TLE x " + str(count_tle)
s4 = "RE x " + str(count_re)

print(s1)
print(s2)
print(s3)
print(s4)


Measured memory_bytes: 74012
function Main(input) {
    input = input.trim();
    input = input.split("\n");
    const s = input[0];
    const t = input[1];

    if(t.indexOf(s) === 0){
        console.log('Yes');
    }else{
        console.log('No');
    }
    
}
 
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29520
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();

    int ex = x - a;
    for (int i = 0;; i++) {
      ex -= b;
      if (ex < b) break;
    }
    System.out.println(ex);
  }

}


Measured memory_bytes: 23892
package main

import (
	"fmt"
)

func main() {
	var N, T int
	fmt.Scan(&N, &T)
	c := make([]int, N)
	t := make([]int, N)
	for i := range c {
		fmt.Scan(&c[i], &t[i])
	}
	minc := 1001
	for i := range t {
		if t[i] <= T {
			if minc > c[i] {
				minc = c[i]
			}
		}
	}
	if minc > 1000 {
		fmt.Println("TLE")
	} else {
		fmt.Println(minc)
	}
}


Measured memory_bytes: 512
#include <cstdio>

int main() {
  int N;
  scanf("%d", &N);

  int res=0;
  for (int i=1; i<=N; ++i) {
    res += 800;
    if (i % 15 == 0)
      res -= 200;
  }

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


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long

using namespace std;



int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    ll a, b, c, d, n;
    ios::sync_with_stdio(false);
    cin >> a >> b >> c >> d;
    cin >> n;
    ll c1 = min(min(4 * a, 2 * b), c), c2 = min(d, 2 * c1);
    cout << (n / 2) * c2 + c1 * (n % 2 == 1);
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 256
//containing t test cases
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define scan(n) ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(ll i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define pi 3.1415926535897932384626433832795028841971
#define mem(a,b) memset(a , b , sizeof a ) ;
//#define int long long
using namespace std;
//typedef vector<int>vi ;
typedef vector<ll>vi ;
typedef vector<vector<ll> >vvl ; 
typedef pair<ll,ll> pll ;
typedef vector<pair<ll,ll> > vpll;
//cout<<fixed<<setprecision(15);
/*vi adj[200005];
ll vis[200005];
ll parent[200005];
ll level[200005];
ll arr[200005];
ll size[200005];*/
//endl mut bhool!!
void solve()
{
	ll n,k;
	cin>>n>>k;
	scan(n);
	sort(a,a+n);ll sum=0;
	rep(i,0,k)sum+=a[i];
	cout<<sum;
}
int main()
{
	fast;
	ll test=1;
	//cin>>test;
	while(test--)
	{
		solve();
	}
	return 0;
}
/*
cout<<"YES"<<endl;
cout<<"NO"<<endl;
*/




Measured memory_bytes: 3664
#include<iostream>
#include<string>
#include<vector>

int countBomb(int pos, std::string &preS, std::string &nowS, std::string &nextS){
  int W = preS.size();
  int count = 0;
  for(int i = 0; i < 3; i++){
    if(preS.at(pos - 1 + i) == '#') count++;
    if(nowS.at(pos - 1 + i) == '#') count++;
    if(nextS.at(pos - 1 + i) == '#') count++;
  }
  return count;
}

int main(){
  int H, W;
  std::cin >> H >> W;
  std::vector<std::string> s(H+2);
  for(int i = 0; i < W + 2; i++){
    s.at(0).push_back('.');
    s.at(H + 1).push_back('.');
  }
  for(int i = 1; i < H + 1; i++){
    std::cin >> s.at(i);
    s.at(i) = "." + s.at(i);
    s.at(i).push_back('.');
  }
  int bomb;
  for(int i = 1; i < H + 1; i++){
    for(int j = 1; j < W + 1; j++){
      if(s.at(i).at(j) == '#') std::cout << '#';
      else{
        bomb = countBomb(j, s.at(i - 1), s.at(i), s.at(i + 1));
        std::cout << bomb;
      }
    }
    std::cout << std::endl;
  }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Rectangle
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] sides = new int[4];

		for (int i = 0; i < 4; i++) {
			sides[i] = parseInt(st.nextToken());
		}

		Arrays.sort(sides);

		if (sides[0] == sides[1] && sides[2] == sides[3]) {
			System.out.println("yes");
		} else {
			System.out.println("no");
		}

	} // end main
}

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

string s;

int main(){

	cin >> s;
	
  	//cout << s.find_first_of('A') << endl;
 	//cout << s.find_last_of('Z') << endl;
  	auto f = s.find_first_of('A');
    auto l = s.find_last_of('Z');
  	cout << l-f+1 << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
  	ll N, A, B;
  	cin >> N >> A >> B;

  	if(N==1 && A!=B){
  		cout << 0 <<endl;
  		return 0;
  	}
  	if(A > B){
  		cout << 0 <<endl;
  		return 0;
  	}

  	ll Max = (N-1)*B + A;
  	ll Min = (N-1)*A + B;

  	cout << Max - Min + 1 <<endl;

    
  	return 0;
}



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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rept(i,k,n) for(int i = (k); i < (int)(n); i++)
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define F first
#define S second

typedef long long ll;
typedef pair<double,double> Pdd;
const ll mod=998244353;
ll poww(ll a,ll b){
    if(b==0) return 1;
    else if(b%2==0) return poww((a*a)%mod,b/2)%mod;
    else return (poww((a*a)%mod,b/2)*a)%mod;
}


int main(){
    ll n;
    
    cin>>n;
    vector<ll> d(n);
    rep(i,n) cin>>d[i];
    if(d[0]!=0){cout<<0<<endl; return 0;}
    vector<ll> cnt(n);
    Sort(d);
    int s=-1,c=1;
    rep(i,n) cnt[d[i]]++;
    ll ans=1;
    if(cnt[0]!=1){cout<<0<<endl; return 0;}
    rep(i,n-1){
        ans*=poww(cnt[i],cnt[i+1]);
        ans%=mod;
    }
    cout<<ans<<endl;
  
    return 0;

}

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

static const int MAX_N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int N;
int G[MAX_N][MAX_N];
int color[MAX_N], d[MAX_N], f[MAX_N];
int t;

void bfs_visit(int u) {
    color[u] = GRAY;
    d[u] = ++t;
    for (int i = 0; i < N; i++) {
        if (G[u][i] && color[i] == WHITE) {
            bfs_visit(i);
        }
    }
    color[u] = BLACK;
    f[u] = ++t;
}

void dfs() {
    for (int i = 0; i < N; i++) {
        color[i] = WHITE;
    }
    t = 0;
    for (int i = 0; i < N; i++) {
        if (color[i] == WHITE) {
            bfs_visit(i);
        }
    }
    for (int i = 0; i < N; i++) {
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int u, k;
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            v--;
            G[u][v] = 1;
        }
    }

    dfs();
    return 0;
}





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

int main()
{
  int N, a, b, c, d;
  cin >> N;
  a = N / 1000;
  b = N / 100 % 10;
  c = N / 10 % 10;
  d = N % 10;
  if((a == b && b == c) || (b == c && c == d)){cout << "Yes" << endl;}
  else{cout << "No" << endl;}
}

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

using namespace std;

#define all(v)				((v).begin()), ((v).end())
#define allr(v)				((v).rbegin()), ((v).rend())
#define sz(v)				((int)((v).size()))
#define ll long long
#define pb					push_back
#define fIO ios_base::sync_with_stdio(0);cin.tie(0);

const ll oo = 1e8;
const double pi = 3.1415926535897;


const double EPS = (1e-7);
int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}


typedef vector<int>                vi;
typedef vector<pair<int,int>>      vii;
typedef vector<ll>                 vll;
typedef vector<double>             vd;
typedef vector< vi >               vvi;
typedef vector< vd >               vvd;
typedef vector<string>             vs;
typedef pair<int, int>             pii;

/**
    * PLEASEEE READDD PROBLEEEM CARFULLY ****
    * Always check for OVERFLOW ll vs int
    * Always check for array bounds
    * Check for function return
    * READ OUTPUT SECTION AGAIN!!!
**/

struct edge{
    int from, to, w;

    edge(){}
    edge(int x, int y, int we): from(x), to(y), w(we){}

    bool operator < (const edge &rhs) const{
        return w > rhs.w;
    }

};

const ll MOD = 1e9 + 7;
const int N = 1e3 + 5;

string grid[N];
int dp[N][N];
int n, m;

int sol(int i, int j) {
    if(i == n - 1 && j == m - 1) return 1;
    if(i >= n || j >= m || grid[i][j] == '#') return 0;

    int &ret = dp[i][j];
    if(ret != -1) return ret;

    ret = 0;

    ret = (sol(i + 1, j) % MOD) + (sol(i, j + 1) % MOD);
    ret %= MOD;
    return ret;
}

int main(){
    fIO

//    freopen("", "r", stdin);
//    freopen("", "w", stdout);

    memset(dp, -1, sizeof(dp));
    cin >> n >> m;

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

    cout << sol(0, 0);

}








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

int main()
{
int i,j,k,n,t;
string s[4]={"AC","WA","TLE","RE"},tmp;
int cnt[4];
memset(cnt,0,sizeof cnt);

cin>>n;
for(i=0;i<n;i++)
    {
        cin>>tmp;
        for(j=0;j<4;j++)
            if(tmp==s[j])cnt[j]++;
    }
for(i=0;i<4;i++)
    cout<<s[i]<<" x "<<cnt[i]<<endl;

return 0;
}


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

int main(){
  long long N, i, Sum = 0;
  cin >> N;
  vector<long long> A(N);
  queue<long long> nxt;
  for(i = 0; i < N; i++) cin>>A[i];
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  nxt.push(A[0]);
  
  for(i=1;i<N;i++){
    nxt.push(A[i]); nxt.push(A[i]);
    Sum += nxt.front(); nxt.pop();
  }
  cout << Sum << endl;
  return 0;
}

Measured memory_bytes: 6416
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	l2 := 2
	l1 := 1
	l := 0
	if n == 1 {
		fmt.Println(1)
		return
	}
	for i := 2; i <= n; i++ {
		l = l1 + l2
		l2 = l1
		l1 = l
	}
	fmt.Println(l)
}

Measured memory_bytes: 512
import Base.parse
import Base.StringVector

parse(::Type{String},  str::AbstractString) = str

isdelim(x::UInt8, xs::Set{UInt8}) = x in xs

function myreaduntil(s::IO, delims::Set{UInt8})::Vector{UInt8}
    out = StringVector(0)
    c::UInt8 = 0x00
    while !eof(s)
        c = read(s, UInt8)
        if !isdelim(c, delims)
            break
        end
    end
    push!(out, c)
    if eof(s)
        return out
    end
    while !eof(s)
        c = read(s, UInt8)
        if isdelim(c, delims)
            break
        end
        push!(out, c)
    end
    return out
end

delimset = Set([0x0a, 0x20])

function readword(io::IO = stdin, delims = delimset)::String
    word = myreaduntil(io, delims)
    i = length(word)
    if i == 0 || word[i] != 0x0a
        return String(word)
    elseif i < 2 || word[i-1] != 0x0d
        return String(resize!(word,i-1))
    else
        return String(resize!(word,i-2))
    end
end

pread(ty) = parse(ty, readword())

reads(tys...)::Tuple{tys...} = Tuple{tys...}(pread(ty) for ty in tys)

readvec(tys::Tuple , len::Signed)::Vector{Tuple{tys...}} = @inbounds Tuple{tys...}[reads(tys...) for i in 1:len]

readvec(ty::Type, len::Signed)::Vector{ty} = @inbounds ty[pread(ty) for i in 1:len]

function readmat(ty::Type, s...)::Matrix{ty}
    v = Matrix{ty}(undef, s...)
    @inbounds for i = 1:s[1]
        v[i,:] = readvec(ty, s[2])
    end
    v
end

function memo()
end

function main()
    K = pread(Int)
    m = zeros()
    c = 0
    for i in 1:K, j in i:K, k in j:K
        c += ((i==j==k) ? 1 : (i!=j && j!=k && k!=i) ? 6 : 3) * gcd(i,j,k)
    end
    println(c)

end

main()


Measured memory_bytes: 186424
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  int s = 0;
  int f = a.size();
  for(int i = 0;i < (f / 2);i++){
    if(a.at(i) != a.at(f-1-i)){s++;}}
  cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<(int)(n);i++)
#define FORR(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))
#define len(a) sizeof(a)
#define ll long long
#define pint pair<int,int>
#define INF 1<<29
#define MAX 501
using namespace std;
 
int R,W[2],H[2],X[2],Y[2],L[2][MAX][MAX],d[2][MAX][MAX],dd[4]={0,-1,0,1};
map<int,int> m[2];
map<int,int>::iterator ite;
vector<int> lev[2],sum[2];
 
void solve(){
 for(;;){
  cin>>R;
  if(!R) return;
  FOR(i,2){
   cin>>W[i]>>H[i]>>X[i]>>Y[i];
   X[i]--;
   Y[i]--;
   FOR(j,H[i]) FOR(k,W[i]) cin>>L[i][j][k];
   FOR(j,H[i]) FOR(k,W[i]) d[i][j][k]=INT_MAX/3;
   d[i][Y[i]][X[i]]=1;
   priority_queue<pint,vector<pint>,greater<pint>> pque;
   pque.push(mp(1,Y[i]*W[i]+X[i]));
   while(!pque.empty()){
    pint p=pque.top(); pque.pop();
    int x=p.second/W[i],y=p.second%W[i];
    if(d[i][x][y]<p.first) continue;
    FOR(j,4){
     int nx=x+dd[j],ny=y+dd[j^1];
     if(nx<0||ny<0||nx>=H[i]||ny>=W[i]) continue;
     if(d[i][nx][ny]>max(d[i][x][y],L[i][nx][ny])){
      d[i][nx][ny]=max(d[i][x][y],L[i][nx][ny]);
      pque.push(mp(d[i][nx][ny],nx*W[i]+ny));
     }
    }
   }
   FOR(j,H[i]) FOR(k,W[i]) m[i][d[i][j][k]]++;
   int tot=0;
   lev[i].pb(0);
   sum[i].pb(0);
   for(ite=m[i].begin();ite!=m[i].end();ite++){
    lev[i].pb(ite->first);
    tot+=ite->second;
    sum[i].pb(tot);
   }
  }
  sum[1].pb(INT_MAX);
  int mi=1<<30;
  FOR(i,lev[0].size()){
   int ind=lower_bound(ALL(sum[1]),R-sum[0][i])-sum[1].begin();
   if(sum[1][ind]==INT_MAX) continue;
   mi=min(mi,lev[1][ind]+lev[0][i]);
  }
  cout<<mi<<endl;
  FOR(i,2){
   m[i].clear();
   lev[i].clear();
   sum[i].clear();
  }
 }
}
 
int main(){
 solve();
 return 0;
}

Measured memory_bytes: 19496
#include<stdio.h>
#include<string.h>
int min(int a,int b){
  if(a > b)return b;
  return a;
}
int main(void){
  int n,cnt = 0,a = 0,b = 0,ab = 0;
  scanf("%d",&n);
  char s[12];
  for(int i = 0;i < n;i++){
    scanf("%s",&s);
    for(int j = 1;j < strlen(s);j++){
      if(s[j - 1] == 'A' && s[j] == 'B')cnt++;
    }
    if(s[strlen(s) - 1] == 'A' && s[0] == 'B'){
      ab++;
    }else if(s[strlen(s) - 1] == 'A'){
      a++;
    }else if(s[0] == 'B'){
      b++;
    }
  }
  if(ab > 0 && a + b < 1)ab--;
  printf("%d\n",cnt + min(a,b) + ab);
  return 0;
}

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

    int main (){
        int k,n;
        cin >> k >> n;
        vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }

    int ans =a[n-1]-a[0];

for(int i =0;i+1<n;i++){
    ans =  min(ans,k-(a[i+1]-a[i]));
}
cout << ans << endl;
return 0;

    }

Measured memory_bytes: 4028
# https://beta.atcoder.jp/contests/abc113/tasks/abc113_b

def solve():
    _ = input()
    T, A = map(int, input().split())
    x = list(map(int, input().split()))
    nearest = 10 ** 5
    ans = 0

    for index, elevation in enumerate(x):
        current = T - elevation * 0.006

        if abs(A - current) < nearest:
            nearest = abs(A - current)
            ans = index + 1

    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3060
#include <stdio.h>

int min(int a, int b, int c){
  if(a > b){
    return (b>c)? c: b;
  }else {
    return (a>c)? c: a;
  }
}

int main(){
  int n;
  while(1){
    scanf("%d", &n);
    if(n==0) break;

    int t[n+1][n+1];

    int i,j;
    int v=0;
    for(i=0;i<=n;i++) for(j=0;j<=n;j++){	
	if(j==0 || i==0) t[i][j] = 0;
	else {
	  char x;
	  scanf(" %c", &x);
	  if(x=='.') {
	    t[i][j] = min(t[i-1][j-1], t[i][j-1], t[i-1][j])+1;
	    v = (v>t[i][j])? v:t[i][j];
	  }
	  else t[i][j] = 0;
	}
      }

    printf("%d\n", v);
  }
}

Measured memory_bytes: 2764
n, m = map(int,input().split())
a = [input().split() for i in range(n)]
for i in range(0, n, 1):
  del a[i][0]
a_and_list = a[0]
for i in range(0, n - 1, 1):
  a_and_list = set(a_and_list) & set(a[i + 1])
print(len(a_and_list))


Measured memory_bytes: 3064
# require 'pry'
k = gets.to_i

if k <= 9
  puts k
  exit
end

lists = []
1.upto(9) do |t|
  lists << t
end
# p lists
count = 9
loop do
pre = []
lists.each do |lis|
  10.times do |t|
    if ((lis % 10) - t).abs <= 1
      pre << lis * 10 + t
      count += 1
      if count == k
        puts pre[-1]
        exit
      end
    end
  end
end
# binding.pry
lists = pre
# p lists
end


Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, k;
    cin >> n >> k;
    ll mc = (n - 1) * (n - 2) / 2;
    if (k > mc) {
        cout << -1 << endl;
        return 0;
    }
    vector<pair<ll, ll>> ans;
    reps(i, 1, n) ans.push_back(make_pair(0, i));
    ll cut = mc - k;
    reps(i, 1, n) {
        reps(j, i + 1, n) {
            if (cut == 0) break;
            ans.push_back(make_pair(i, j));
            cut--;
        }
        if (cut == 0) break;
    }
    printf("%lld\n", sz(ans));
    rep(i, sz(ans)) {
        printf("%lld %lld\n", ans[i].first + 1, ans[i].second + 1);
    }
    return 0;
}


Measured memory_bytes: 512
N, K = list(map(int, input().split()))
S = input()

runlength_one = []
runlength_zero = []
counter = 0
prev = '1'
for s in S:
    if s == prev:
        counter += 1
    else:
        if s == '1':
            runlength_zero.append(counter)
        else:
            runlength_one.append(counter)
        counter = 1
        prev = s
if S[-1] == '1':
    runlength_one.append(counter)
else:
    runlength_one.append(0)
    runlength_zero.append(counter)

max = 0
sum_one = 0
sum_zero = 0
for i in range(len(runlength_one)):
    if i + K >= len(runlength_one):
        break

    if i == 0:
        sum_one = sum(runlength_one[0:K + 1])
        sum_zero = sum(runlength_zero[0:K])
    else:
        sum_one = sum_one - runlength_one[i - 1] + runlength_one[i + K]
        sum_zero = sum_zero - runlength_zero[i - 1] + runlength_zero[i + K - 1]
        
    length = sum_one + sum_zero
    max = length if max < length else max

if max == 0:
    max = sum(runlength_one) + sum(runlength_zero)

print(str(max))


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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 60;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll A, B, C, X, Y; cin >> A >> B >> C >> X >> Y;
    int ulim = max(X, Y)*2;
    ll ans = LLINF;
    for(int ab = 0; ab <= ulim; ab++){
        ll remA = max(0ll, X - ab/2);
        ll remB = max(0ll, Y - ab/2);
        ans = min(ans, remA*A + remB*B + ab*C);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#ifndef aa
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
#define double long double
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define deb(x) cout << x << endl
#define done(x) {cout << x << endl;return;}
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
//const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
typedef map<int, int> mii;
typedef set<int> si;
typedef set<pair<int,int>> spii;
typedef queue<int> qi;


const int N = 3e2+5;
int dp[N][N][N];


void solve() {

  int k,one=0;
  string s;
  cin>>s>>k;
  vi pre = {0};
  frev(i,0,sz(s)-1){
    if(s[i]=='0')
      pre.pb(one);
    else
      one++;
  }
  pre.pb(one);
  int n = sz(pre);
  k=min(k,one);
  dp[0][0][0]=1;

  rep(i,0,n-1){
    fr(sum,0,pre[i]){
      fr(op,0,k){
         if(!dp[i][sum][op])
            continue;
         fr(x,0,pre[i+1]-sum){
      int new_op = op + max(0ll,x-pre[i+1]+pre[i]);
      if(new_op<=k)
      (dp[i+1][sum+x][new_op]+=dp[i][sum][op])%=mod;
          }
      }
    }
  }
  int ans = 0;
  fr(op,0,k)
    (ans+=dp[n-1][one][op])%=mod;
  cout<<ans;

}


signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout << fixed << setprecision(15);
    int t = 1;
   //cin >> t;

    while (t--)
        solve();
#ifdef aa
    cout << endl << endl << endl << endl << "Time elapsed: " << (double)(clock() - clk) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}



int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = (res*a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int divide(int a, int b) {
    return (a % mod) * powm(b, mod - 2) % mod;
}

int norm(int a) {
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return a;
}


int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}


Measured memory_bytes: 57072
n=int(input())
l1=list(input().split())
l2=l1.copy()
 
def bubble(L,N):
    c=0
    for i in range(N):
        j=N-1
        while j>0:
            if int(L[j][1])<int(L[j-1][1]):
                L[j],L[j-1]=L[j-1],L[j]
            j-=1
    print(" ".join(L))

bubble(l1,n)
print("Stable")

def select(L,N):
    for i in range(N):
        L2=[int(L[k][1]) for k in range(N)]
        j = L2[i:].index(min(L2[i:])) + i
        L[i], L[j] = L[j], L[i]
    print(" ".join(map(str,L)))

select(l2,n)
if l1==l2:
    print("Stable")
else:
    print("Not stable")


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

int sosu(int a){
	if(a==1) return 0;
	for(int i=2;i*i<=a;i++){
		if(a%i==0) return 0;
	}
	return a;
}

int main(){
	int a,d,n;
	while(cin>>a>>d>>n and a){
		int cnt=0;
		a-=d;
		while(cnt<n){
			a+=d;
			if(sosu(a)) cnt++;
		}
		cout<<a<<endl;
	}
	return 0;
}



Measured memory_bytes: 3060
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

const size_t SIZE = 210;
const ll mod = 1e9 + 7;

// space, people to down
ll dp_buf[2][SIZE];
ll *dp[] = { dp_buf[0], dp_buf[1] };

int main() {
    ll N;
    cin >> N;
    string S(N, '.');
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        S[i] = c;
    }

    dp[0][0] = 1;
    for (ll i = 0; i < N; i++) {
        fill(dp[1], dp[1] + SIZE, 0);
        for (ll j = 0; j <= i; j++) {
            if (S[i] == '-') {
                dp[1][j] = dp[0][j];
            } else if (S[i] == 'D') {
                if (j == 0) continue;
                (dp[1][j] += j * dp[0][j] % mod) %= mod;
                if (0 < j) (dp[1][j - 1] += j * j * dp[0][j]) %= mod;
            } else {
                (dp[1][j + 1] += dp[0][j]) %= mod;
                if (0 < j) (dp[1][j] += j * dp[0][j] % mod) %= mod;
            }
        }
        swap(dp[0], dp[1]);
    }

    cout << dp[0][0] << endl;
    return 0;
}



Measured memory_bytes: 3232
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  int ans = n * (n-1)/2;
  ans += m * (m-1) / 2;

  cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner sc = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
      	int N = Integer.parseInt(sc.next());
      	int Y = Integer.parseInt(sc.next());
      	
      	int x = 0;
      	int y = 0;
      	int z = 0;
      	boolean judge = false;
      	outside:for(int i = 0; i <= N; i++){
        	for(int j = 0; j <= N - i; j++){
            	z = N - i - j;
              	if(10000 * i + 5000 * j + 1000 * z == Y){
                	x = i;
                  	y = j;
                  	judge = true;
                  	break outside;
                }
            }
        }
      	if(judge){
          	out.println(x + " " + y + " " + z);
        }else {
        	out.println("-1 -1 -1");
        }
        out.close();
    }
}

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

int main() {
    int X;
    cin >> X;
    int sum = 0, ans = 0;
    for (int i = 1; i <= X; i++) {
        sum += i;
        if (sum >= X) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
#define pii pair<int ,int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005


int main()
{
    _FastIO;
    int n;
    cin >> n;
    vector<int> a(n + 5 , 0);
    int s = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        s += a[i];
    }
    cout << s - n << endl;
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
 
using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;

int main(void) {
    Int a, b;
    cin >> a >> b;
    if (a <= b) {
        cout << a << endl;
    } else {
        cout << a - 1 << endl;
    }
    return 0;
}


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

int main() {
  long long A, B, C, K;
  cin >> A >> B >> C >> K;
  if (K < A) {
    cout << K << endl; 
  }
  else if (K <= A + B) {
    cout << A << endl;
  }
  else {
    cout << A - (K - A - B) << endl;
  }
}

Measured memory_bytes: 3596
#include<map>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<string.h>
#define mp make_pair
using namespace std;
int in[100005][2];
int u[100005];
int r[100005];
inline int root(int x){
	if(x==r[x]) return x;
	else return r[x]=root(r[x]);
}
vector<pair<long long,pair<int,int> > >v;
inline bool cmp1(int x,int y){return in[x][0]<in[y][0];}
inline bool cmp2(int x,int y){return in[x][1]<in[y][1];}
int main(){
	int n,i,x,y;
	cin>>n;
	for(i=0;i<n;i++) cin>>in[i][0]>>in[i][1];
	for(i=0;i<n;i++) u[i]=r[i]=i;
	sort(u,u+n,cmp1);
	for(i=0;i<n-1;i++) v.push_back(mp(in[u[i+1]][0]-in[u[i]][0],mp(u[i],u[i+1])));
	sort(u,u+n,cmp2);
	for(i=0;i<n-1;i++) v.push_back(mp(in[u[i+1]][1]-in[u[i]][1],mp(u[i],u[i+1])));
	sort(v.begin(),v.end());
	long long ans=0;
	for(i=0;i<v.size();i++){
		pair<long long,pair<int,int> > it;
		it=v[i];
		if(root(it.second.first)==root(it.second.second)) continue;
		ans+=it.first;
		r[root(it.second.first)]=root(it.second.second);
	}
	cout<<ans<<endl;
	return 0;
}

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

const long long INF = 1LL << 60;

int main() {
    long long N, K;  cin >> N >> K;
    vector<long long> A(N), F(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> F[i];
    sort(A.begin(), A.end());
    sort(F.begin(), F.end(), greater<long long>());

    long long lb = -1, ub = INF;
    while (ub - lb > 1) {
        long long mid = (lb + ub) / 2;
        bool ok = true;
        long long cnt = K;
        for (int i = 0; i < N; ++i) {
            if (A[i] * F[i] <= mid) continue;
            cnt -= A[i] - mid / F[i];
            if (cnt < 0) ok = false;
        }
        if (ok) ub = mid;
        else lb= mid;
    }
    cout << ub << endl;
}


Measured memory_bytes: 3328