akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int X;
int main() {
    cin >> X;
    int ans = 0;
    int c_5, c_500;
    c_5 = 0;
    c_500 = 0;
    c_500 = X / 500;
    X = X % 500;
    c_5 = X / 5;
    cout << (1000*c_500 + 5 * c_5 ) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	//freopen("k.out","w",stdout);
	long long x,n=100;
	int y=0;
	scanf("%lld",&x);
	if(x==1000000000000000000) {y=3760;n=1004291331219645824;}
	else if(x>=1008771731668) {y=2372;n=1008771731668;}
	else if(x>=397713) {y=890;n=397713;}
	while(x>n)
		{
			n*=1.01;
			//printf("%lld\n",n);
			y++;
		}
	printf("%d\n",y);
	return 0;
}

Measured memory_bytes: 3824
import java.io.PrintWriter;
import java.util.*;

public class Main {

	static int c;
	static int[] w;
	static int[] v;
	static long[][] dp;
	static int n;

	public static long KnapSack(int idx, int remw) {
		if (remw < 0) {
			return -(int) 1e9;
		}
		if (idx == n) {
			return 0;
		}
		if (dp[idx][remw] != -1) {
			return dp[idx][remw];
		}
		long take = v[idx] + KnapSack(idx + 1, remw - w[idx]);
		long leave = KnapSack(idx + 1, remw);
		return dp[idx][remw] = Math.max(take, leave);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		n = sc.nextInt();
		c = sc.nextInt();
		w = new int[n];
		v = new int[n];
		dp = new long[n][c+5];
		for (long[] x : dp)
			Arrays.fill(x, -1);
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		pw.println(KnapSack(0, c));
		pw.flush();
	}

}

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

typedef long long ll;

using namespace std;

int main() {
	int arr[5] = {};
	int a,b;
	for(int i = 0; i < 3; i++) {
		cin >> a >> b;
		arr[a]++;
		arr[b]++;
	}

	bool ans = true;
	for(int i = 1; i <= 4; i++) {
		ans &= arr[i]<=2;
	}

  cout << ((ans)?"YES":"NO") << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define P 1000000007
#define PI pair <ll, ll>
#define f first
#define s second

using namespace std;

typedef long long ll;

ll powmod(ll x, ll y = P - 2, ll p = P) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}

int n, q, A[3333], X[3333], Y[3333];

ll F[3333][3333], tmp[3333][3333];

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for(int i = 1; i <= q; i++) scanf("%d%d", &X[i], &Y[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            F[i][j] = i > j ? 1 : 0;
    ll r2 = powmod(2);
    for(int i = q; i >= 1; i--) {
        for(int j = 1; j <= n; j++) if(j != X[i] && j != Y[i]) {
            ll o = (F[X[i]][j] + F[Y[i]][j]) * r2 % P;
            F[Y[i]][j] = o;
            F[X[i]][j] = o;
            o = (F[j][X[i]] + F[j][Y[i]]) * r2 % P;
            F[j][Y[i]] = o;
            F[j][X[i]] = o;
        }
        ll o = (F[X[i]][Y[i]] + F[Y[i]][X[i]]) * r2 % P;
        F[Y[i]][X[i]] = o;
        F[X[i]][Y[i]] = o;
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(A[i] < A[j]) {
                ans = (ans + F[i][j]) % P;
            }
    printf("%lld\n", (ans * powmod(2, q) % P + P) % P);
    return 0;
}

Measured memory_bytes: 80128
#include <stdio.h>

int main(void)
{
	int dataset;
	int X, Y, W, H;
	int N;
	int x, y;
	int count;
	
	scanf("%d", &dataset);
	for (; dataset > 0; dataset--){
		scanf("%d%d%d%d", &X, &Y, &W, &H);
		
		scanf("%d", &N);
		count = 0;
		for (; N > 0; N--){
			scanf("%d%d", &x, &y);
			
			if ((X <= x && x <= X + W) &&
			    (Y <= y && y <= Y + H)){
					
				count++;
			}
		}
		printf("%d\n", count);
	}
	
	return (0);
}

			
	

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

int main() {
	
  int N, A;
  string x;
  bool P, W, G, Y;
  P = W = G = Y = true;
  cin >> N;
  
  for(int i = 0; i < N; i++){
  	
    cin >> x;
    if(x == "P" && P){
      A += 1;
      P = false;
    }
    else if(x == "W" && W){
      A += 1;
      W = false;
    }
    else if(x == "G" && G){
      A += 1;
      G = false;
    }
    else if(x == "Y" && Y){
      A += 1;
      Y = false;
    }
  }
  if(A == 3){
  cout << "Three" << endl;
  }
  if(A == 4){
  cout << "Four" << endl;
  }
}

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

int main(){
    int a , b , c , t;
    cin >> a >> b >> c;
    
    if ( a > b ) { t = a; a = b; b = t;}
    if ( b > c ) { t = b; b = c; c = t;}
    if ( a > b ) { t = a; a = b; b = t;}

    cout << a << " " << b << " " << c << endl;

    return 0;
}


Measured memory_bytes: 3096
/**
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
 */
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static class LIS {

        int[] arr;

        public LIS(int[] arr) {
            this.arr = arr;
        }

        public int solve() {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int[] tailTable = new int[arr.length];
            tailTable[0] = arr[0];
            int len = 1;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > tailTable[len - 1]) {
                    // Case 2. Clone and extend
                    tailTable[len++] = arr[i];
                } else if (arr[i] < tailTable[len - 1]) {
                    // Case 3. Clone, extend and discard
                    int insertionIdx = Arrays.binarySearch(tailTable, 0, len, arr[i]);
                    if (insertionIdx < 0) {
                        insertionIdx = -(insertionIdx + 1);
                    }
                    tailTable[insertionIdx] = arr[i];
                }
            }
            return len;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        LIS lis = new LIS(arr);
        System.out.println(lis.solve());
    }
}

Measured memory_bytes: 70304
import bisect
from collections import defaultdict

N, M = map(int, input().split(' '))
cities = []
years = defaultdict(list)
for _ in range(M):
    p, y = map(int, input().split(' '))
    cities.append((p, y))
    years[p].append(y)

for p in years.keys():
    years[p].sort()

for p, y in cities:
    print('{:06}{:06}'.format(p, bisect.bisect_right(years[p], y)))


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

int main() {
	string s, t;
	while (cin >> s >> t) {
		int ans = 0;
		rep(i, s.size()) {
			int minl = min(s.size() - i, t.size());
			int cnt = 0;
			rep(j, minl) {
				if (s[i + j] == t[j])cnt++;
				else { ans = max(ans, cnt); cnt = 0; }
			}
			ans = max(ans, cnt);
		}
		rep(i, t.size()) {
			int minl = min(s.size(), t.size() - i);
			int cnt = 0;
			rep(j, minl) {
				if (s[j] == t[i + j])cnt++;
				else { ans = max(ans, cnt); cnt = 0; }
			}
			ans = max(ans, cnt);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
 

int main() {
  int N;cin>>N;
  vector<long long>A(N);
  long long max_length=0;
  long long ans=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
    max_length=max(max_length,A[i]);
    ans+=max_length-A[i];
  }
  cout<<ans<<endl;
}
 

Measured memory_bytes: 4816
#coding:utf-8

n = int(input())
string = input()
ecnt = 0
for i in range(n):
    if string[i] == "E":
        ecnt += 1
wcnt = 0
minv = 10000000000
for i in range(n):
    if string[i] == "E":
        ecnt -= 1
    if i >= 1 and string[i-1] == "W":
        wcnt += 1
    minv = min(minv,wcnt+ecnt)
    
print(minv)


Measured memory_bytes: 3704
#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
int main()
{
    int a[3],i;
    for(i=0;i<3;i++)cin>>a[i];
    sort(a,a+3);
    cout<<a[0]+a[1];
    return 0;
}


Measured memory_bytes: 256
import heapq

def main():
    N = int(input())
    C = list(input())
    R = []
    W = []
    for i, c in enumerate(C):
        if c == 'R':
            R.append(-i)
        else:
            W.append(i)
    if len(R) == 0 or len(W) == 0:
        print(0)
        exit()
    heapq.heapify(R)
    heapq.heapify(W)
    ans = 0
    while True:
        max_r = -1 * heapq.heappop(R)
        min_w = heapq.heappop(W)
        if max_r < min_w:
            break
        else:
            heapq.heappush(R, -min_w)
            heapq.heappush(W, max_r)
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 18824
import heapq

code_list = dict()

class Node():
    def __init__(self, alphabet, rate):
        self.alphabet = alphabet
        self.rate = rate
        self.left = None
        self.right = None

def create_code(node, target, code):
    
    if node == None:
        return 

    if node.alphabet == target:
        code_list[target] = code
        return
        
    create_code(node.left, target, code + "0")
    create_code(node.right, target, code + "1")

def Main():
    S = input().replace("\n", "")
    N = len(S)

    node_list = list()
    count_list = dict()

    character = set(S)
    character = sorted(character)

    for c in character:
        count = S.count(c)
        count_list[c] = count
        n = Node(c, float(count/N))
        node_list.append(n)

    huf_tree = None

    if len(node_list) == 1:
        n1 = node_list.pop()
        new = Node("", n1.rate)
        new.left = n1

        huf_tree = new

    else:
        while len(node_list) >= 2:
            node_list.sort(key = lambda x : x.rate, reverse = True)

            n1 = node_list.pop()
            n2 = node_list.pop()

            new = Node("", n1.rate + n2.rate)
            new.left = n1
            new.right = n2
            node_list.append(new)

            huf_tree = new

    code_length = 0

    for c in character:
        create_code(huf_tree, c, "")
        code_length += len(code_list[c]) * count_list[c]

    print(code_length)

Main()


Measured memory_bytes: 5868
parseint(x) = parse(Int, x)
parseintmap(x::Array{SubString{String},1}) = map(parseint, x)

function main()
    n, m = readline() |> split |> parseintmap
    l = 1
    r = n
    for _ in 1:m
        ll, rr = readline() |> split |> parseintmap
        l = max(l, ll)
        r = min(r, rr)
    end
    if r >= l
        println(r - l + 1)
    else
        println(0)
    end
end

main()


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

namespace abc061_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine(x[0] <= x[2] && x[2] <= x[1] ? "Yes" : "No");
        }
    }
}

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

namespace abc110_a
{
    class program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int ans;
            if (x[0]>=x[1] && x[0]>=x[2])
            {
                ans = 10 * x[0] + x[1] + x[2];
            }
            else
            {
                if (x[1]>=x[0] && x[1]>=x[2])
                {
                    ans = 10 * x[1] + x[0] + x[2];
                }
                else
                {
                    ans = 10 * x[2] + x[0] + x[1];
                }
            }
            Console.WriteLine(ans);
        }
    }
}


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

int main()
{
    char ch;

    cin >> ch;

    switch(ch) {
        case 'A':
            cout << 'T';
            break;
        case 'T':
            cout << 'A';
            break;
        case 'C':
            cout << 'G';
            break;
        case 'G':
            cout << 'C';
            break;
    }

    return 0;
}

Measured memory_bytes: 256
/**
  @date Time-stamp: <2019-06-09 21:10:55 tagashira>
  @file b.cpp
  @title B - Balance
  @brief https://atcoder.jp/contests/abc129/tasks/abc129_b
**/

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  vector<int> W(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> W[i];
  }

  int S1, S2;
  int ans = 1000;
  for (int T = 0; T < N; T++) {
    S1 = std::accumulate(W.begin(), W.begin() + T, 0);
    S2 = std::accumulate(W.begin() + T, W.end(), 0);

    ans = abs(S1 - S2) < ans ? abs(S1 - S2) : ans;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
lines = $stdin.read
array = lines.split("\n")

def ceil_index(array, l, r, key)
  while r-l > 1
    m = l + (r-l)/2
    if array[m] >= key
      r = m
    else
      l = m
    end
  end
  r
end

def get_lis(arr)

  tail = Array.new(arr.length)
  len = 1
  tail[0] = arr.first

  for i in 1...arr.length
    #puts tail.to_s

    if arr[i] < tail[0]
      # new smallest value
      tail[0] = arr[i]
    elsif arr[i] > tail[len-1]
      # arr[i] extends largest subsequence
      tail[len] = arr[i]
      len = len + 1
    else
      # option(a): use binary search
      # but, ruby's Array#bsearch_index requires
      # all array's elements sorted
      #idx = tail[0..i].compact.bsearch_index do |x|
      #  x >= arr[i]
      #end

      # option(b): implement binary search yourself
      idx = ceil_index(tail, -1, len-1, arr[i])
      tail[idx] = arr[i]
    end
  end

  #puts tail.to_s
  len
end

N = array[0].to_i
a = array[1..N].map(&:to_i).to_a

puts get_lis(a)

Measured memory_bytes: 15688
n= int(input())
l_s= list(map(int, input().split()))
l_s.sort()
count=0
for a in range(len(l_s)):
	for b in range(a+1, len(l_s)):
		for c in range(b+1, len(l_s)):
			if l_s[a]==l_s[b]:
				pass
			elif l_s[b]==l_s[c]:
				pass
			else:
				if l_s[a]+l_s[b]>l_s[c]:
					count+=1

print(count)

Measured memory_bytes: 9192
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define INF 1 << 30

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

int main(void) {
	ll num, i, a, b, ans;
	cin >> num >> a >> b;
	ans = num / (a + b) * a;
	num %= a + b;
	ans += min(a, num);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll N; cin >> N;

  for(ll x = 1; x <= 3500; x++){
    for(ll y = 1; y <= 3500; y++){
      if( 4*x*y - N*(x+y) <= 0){ continue;}
       long double res = (long double)(N*x*y)/(4*x*y - N*(x+y));
      if(res < 1){ continue;}
      if( res == (ll)floor(res)){ cout << x << " " << y << " " << (ll)floor(res) << endl; return 0;}
    }
  }
  
  cout << -1 << endl; return 0;}
  

Measured memory_bytes: 384
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int MOD=1000000007;

int main(){
    std::string s,c,r,l;
    cin>>s;
    int rev=1;
    int t,f,i,q;
    cin>>q;
    rep(i,q){
        cin>>t;
        if(t==1){
            rev*=-1;
        }else{
            cin>>f>>c;
            if((rev==1 && f==1) || (rev==-1 && f==2)){
                r=c+r;
            }else{
                l=l+c;
            }
        }
    }
    s=r+s+l;
    if(rev==-1){
        reverse(s.begin(),s.end());
    }
    cout<<s;
    return 0;
}

Measured memory_bytes: 1464
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    int N;
    cin >> N;
    int cnt = 0;
    for (int i = 1; i <= N; ++i) {
        int a;
        cin >> a;
        if ((i & 1) && (a & 1))
            cnt++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3632
//*
#include <bits/stdc++.h>
//*/
/*
#include <iostream>
#include <vector>
#include <string.h>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

struct SegmentTree
{
private:
    int n;
    vector<int> node;

public:
    //?????????v(vector)????????°???????????¨??§??¨?????????
    SegmentTree(vector<int> v)
    {
        //???????????????????????°??????????????????????????\????????????????°??????????????????????n??¨??????
        //?????°???????????¨??¨?????§????????????????????°???2n-1??§??????
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2 * n - 1, INF);

        //????????????????????\???????????¨????????????????????????????????????
        //?????????????????¨??????????????????????????????????????°??????
        REP(i,sz) node[i+(n-1)] = v[i];
        for (int i=n-2; i>=0; i--) {
            //????????°??¨?????????????????????????????¨??????????????????????????????
            node[i] = min(node[2*i+1], node[2*i+2]);
        }
    }

    void update(int x, int val)
    {
        //??????????????????????????¢???????????????
        x += n - 1;

        //??????????????????????????´??°?????????????????¨??????????????£?????´??°????????????
        node[x] = val;
        while (x > 0) {
            //x=0??§????????????????????????
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }

    //????±???????[a,b)???????´????????°????????????????
    //k:=?????????????????????????????????????????????
    //????±??????????[l,r)????????????
    int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        //?????????????????????????????¨??????????±??????????[0,n)
        if (r < 0) r = n;

        //????±?????????¨????±???????????????????????????????????????±??????????????????????????????
        //????????°??¨?????????????????£????????????
        if (r <= a || b <= l) return INF;

        //????±??????????????±???????????????¨????¢???????????±????????????????????¨?????????????
        if (a <= l && r <= b) return node[k];

        //????±??????????????±???????????????¨????¢????????????????????????¢?´¢?????????
        //????????????vl???????????????vr??¨????????????
        //??°??????????±???????????????¨???????±???????????????????????????????
        int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

signed main()
{
    int n, q;

    cin >> n >> q;
    vector<int> a(n, (1LL << 31) - 1);

    SegmentTree st(a);
    REP(i,q) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            st.update(x, y);
        } else {
            cout << st.getmin(x, y + 1) << endl;
        }
    }
}

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

#define endl "\n"
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define watch(x) cout << (#x) << " is " << (x) << endl
#define watch_vector(x) FOR(i,0,(v).size(),1) cout<<v[i]<<" ";
#define yo cout<<"yo"

typedef long long int LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;

int frogJump(VI &v){
	int n=v.size();
	VI dp(n,INT_MAX);
	dp[n-1]=0;
	for(int i = n-2;i >= 0;i--){
		if(i <= n-2) dp[i] = abs(v[i] - v[i+1]) + dp[i+1];
		if(i <= n-3) dp[i] = min(dp[i],abs(v[i] - v[i+2]) + dp[i+2]);
	}
	return dp[0];
}
int main()
{
   ios_base:: sync_with_stdio(false); cin.tie(0);
   
   #ifndef ONLINE_JUDGE
		//for getting input from input.txt
		freopen("input.txt","r", stdin);
		//for writing output to output.txt
		freopen("output.txt","w", stdout);
	#endif

	int n;cin>>n;
	VI v(n,0);
	FOR(i,0,n,1){
		cin>>v[i];
	}
	cout<<frogJump(v);
        
        
   return 0;
}

Measured memory_bytes: 3960
package main

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

//const mod = 998244353
const mod = 1000000000000007
const facNum = 300001

func main() {
	sc := newScanner(os.Stdin)
	L := sc.i()
	ans := float64(Pow(L, 3)) / 27
	fmt.Printf("%.10f", ans)
}

// fmt.Println("Yes")
// fmt.Println("No")

// I/O
type scanner struct {
	sc *bufio.Scanner
}

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

func (s *scanner) s() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *scanner) i() int {
	i, e := strconv.Atoi(s.s())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *scanner) f() float64 {
	f, e := strconv.ParseFloat(s.s(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

func (s *scanner) is(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.i()
	}
	return res
}

func (s *scanner) fs(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.f()
	}
	return res
}

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

//const factorial = new
func Pow(a, n int) int {
	ans := 1
	for n > 0 {
		if (n & 1) == 1 {
			ans = ans * a % mod
		}
		a = a * a % mod
		n = n >> 1
	}
	return ans
}

// a^{-1} (mod) を計算
func Inv(a int) int {
	return Pow(a, mod-2)
}

func Gcd(a, b int) int {
	if a < b {
		return Gcd(b, a)
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func combination(n, k int, fac, ifac []int) int {
	if n < k || n < 0 {
		return 0
	}
	if k == 0 {
		return 1
	}
	//while n != 0
	ans := ifac[k] * ifac[n-k] % mod
	return ans * fac[n] % mod
}

func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}

// 階乗: factorial
// コンビネーションを計算する際に前もって計算しておく
// fac[k] => k! (mod M)
// ifac[k] => k!^(M-2) (mod M)
// n: ex. 2 * 10^5 => 200001
// fac, ifac := factorial()
func factorial() (fac []int, ifac []int) {
	fac = make([]int, facNum)
	fac[0] = 1
	ifac = make([]int, facNum)
	ifac[0] = 1
	for i := 1; i < facNum; i++ {
		fac[i] = fac[i-1] * i % mod
		ifac[i] = ifac[i-1] * Pow(i, mod-2) % mod
	}
	return
}

// vs: sorted slice int value
func lowerBound(vs []int, v int) (index int) {
	n := len(vs) / 2
	m := len(vs)
	for m != n {
		if vs[n] < v {
			n = (m-n+1)/2 + n
			//m = m
		} else {
			m = n
			n = n / 2
		}
	}
	return n
}

func IntSlice(n, init int) []int {
	r := make([]int, n)
	for i := range r {
		r[i] = init
	}
	return r
}


Measured memory_bytes: 1772
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    ll n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    rep(i, 0, m) cin >> a[i] >> b[i], a[i]--, b[i]--;

    UnionFind uf(n);
    ll cur = n * (n-1) / 2;
    vector<ll> ans;
    rep(i, 0, m) {
        ans.push_back(cur);

        int ta = a[m-1-i], tb = b[m-1-i];
        if (uf.issame(ta, tb)) continue;

        ll sa = uf.size(ta), sb = uf.size(tb);
        cur -= sa * sb;
        uf.merge(ta, tb);
    }
    for (int i = m-1; i >= 0; i--) cout << ans[i] << endl;
}

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

using namespace std;

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

int main() {
    string S;
    cin >> S;

    for (int i = S.size(); i >= 0; i-=2) {
        S.erase(i-2,2);
        if (S.substr(0, S.size() / 2) == S.substr(S.size() / 2, S.size())) {
            cout << S.size() << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
# solution
import math
import io
import string

data = int(input())
array = [input().rstrip() for _ in range(data)]
sets = {c: [] for c in string.ascii_lowercase}
for i in range(data):
    for c in string.ascii_lowercase:
        k = array[i].count(c)
        sets[c].append(k)
strs = ''
for c in string.ascii_lowercase:
    strs += c * min(sets[c])
print(strs)

Measured memory_bytes: 4024
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int main(){
    long long int s, c;
    cin >> s >> c;

    long long int ans = 0;
    long long int count = 0;

    long long int sn = 0;
    long long int diff = 0;
    if(2*s <= c){
        c -= 2*s;
        ans += s;
    }
    else {
        sn = c/2;
        s -= sn;
        c -= sn * 2;
        ans += sn;
        //cout << s << " " << c << endl;
    }
    
    ans += c / 4;

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc=new Scanner(System.in);
		Reader reader=new Reader();
		int t=1;//sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			long mod=(long)1e9+7;
			//System.out.println();
			long[] arr=new long[n];
			long[] pre=new long[n];
			for(int i=0;i<n;i++) {
				arr[i]=sc.nextLong();
			}
			pre[0]=arr[0];
			for(int i=1;i<n;i++) {
				pre[i]=pre[i-1]+arr[i];
				//pre[i]%=mod;
			}
			long ans=0;
			for(int i=0;i<n-1;i++) {
				ans+=(arr[i]*((pre[n-1]-pre[i])%mod));
				ans%=mod;
			}
			System.out.println(ans);
		}
	}
}
class Reader{
	BufferedReader reader;
	Reader(){
		reader=new BufferedReader(new InputStreamReader(System.in));
	}
	int nextInt() throws IOException{
		String in=reader.readLine().trim();
		return Integer.parseInt(in);
	}
	long nextLong() throws IOException{
		String in=reader.readLine().trim();
		return Long.parseLong(in);
	}
	String next() throws IOException{
		return reader.readLine().trim();
	}
	String[] stringArray() throws IOException{
		return reader.readLine().trim().split("\\s+");
	}
	int[] intArray() throws IOException{
		String[] inp=this.stringArray();
		int[] arr=new int[inp.length];
		int i=0;
		for(String s:inp) {
			arr[i++]=Integer.parseInt(s);
		}
		return arr;
	}
}


Measured memory_bytes: 64984
#include<iostream>
#include<string>
using namespace std;
int main(){
  string input;
  cin >> input;
  if(input == "Sunny"){
    cout << "Cloudy";
    cout << "\n";
  }
  else if(input == "Cloudy"){
    cout << "Rainy";
    cout << "\n";
  }
  else{
    cout << "Sunny";
    cout << "\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void insertionSort(int A[],const int N);

int main(void) {

    int i, N;
    scanf("%d", &N);
    int A[N];
    for(i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for( i = 0; i < N; i++ ){
        printf("%d", A[i]);
        if( i != N-1 ) printf(" ");
    }
    printf("\n");
    insertionSort(A, N);

    return 0;
}


void insertionSort(int A[],const int N){
    int i, j, v;
    for (i = 1; i < N; i++){
        v = A[i];
        j = i - 1;
        while (j >= 0 && A[j] > v){ 
            A[j+1] = A[j];
            j--;
            A[j+1] = v;
        }
        for( j = 0; j < N; ++j ){
            printf("%d", A[j]);
            if( j != N-1 ) printf(" ");
        }
        printf("\n");
    }
}


Measured memory_bytes: 1992
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    for(int i=0;i<n;++i){
        cout<<s[i]<<t[i];
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;

int main() {
    long ans = 0;
    long n, k;
    cin >> n >> k;
    
    if (k == 0) {
        cout << n * n << endl;
        return 0;
    }
    
    for (long b = k + 1; b <= n; b++) {
        long c = b - k;
        long m = (n + 1) / b;
        ans += c * m;
        if (k + b * m <= n) {
            ans += n - (k + b * m) + 1;
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
//id:miiifa (AOJ,PEどちらも)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
vector<int>A;
int n,k;
bool isok(int t){
    int x=0,cnt=1;
    REP(i,n){
        if(t<A[i]) return 0;
        x+=A[i];
        // cout << x << " " << cnt << endl;
        if(x>t){
            i--;
            x=0;
            cnt++;
        }
    }
    if(cnt>k) return 0;
    else return 1;
}
int binary_meguru(int ok, int ng){
    while(abs(ok-ng)>1){
        int t= (ok+ng)/2;
        if(isok(t)){
            ok= t;
        }else{
            ng= t;
        }
    }
    return ok;
}
int main(){
    cin >> n >> k;
    A.resize(n);
    int sum=0;
    REP(i,n){
        cin >> A[i];
        sum+= A[i];
    }
    // cout << isok(9) << endl; 
    cout << binary_meguru(sum, 0) << endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
#define F(i,x,n) for(int i=x;i<=n;++i)
#define F_(i,x,n) for(int i=x;i>=n;--i)
using namespace std;
inline void read(ll &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline int  Rem() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
inline void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
const int N=2e5+5;
ll n,k,a[N],f[N];
/**/
inline bool check(ll maxx)
{
    ll sum=k;
    for(int i=1;i<=n;i++)//ÈË
    {
        ll nd=maxx/f[i];
        if(a[i]>nd) sum-=(a[i]-nd);
        if(sum<0) return 0;
    }
    return 1;
}
inline bool cmp(ll x,ll y){return x>y;}
int main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    read(n);read(k);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(f[i]);
    sort(a+1,a+1+n);
    sort(f+1,f+1+n,cmp);
    ll l=0,r=a[n]*f[1];
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l;
}  

Measured memory_bytes: 3328
#define _USE_MATH_DEFINES
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int W, N;

	for (int h = 1; cin >> W&& W; h++) {
		cin >> N;
		int v, w;
		int dp[1001] = {};
		for (int i = 0; i < N; i++) {
			char c;
			cin >> v >> c >> w;
			for (int j = W; j > 0; j--) {
				if (j - w < 0)continue;
				dp[j] = max(dp[j], dp[j - w] + v);
			}
		}
		int a = 0, b = 0;
		for (int i = 0; i <= W; i++) {
			if (a < dp[i]) {
				a = dp[i];
				b = i;
			}
		}
		cout << "Case " << h << ":" << endl;
		cout << a << endl;
		cout << b << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define REP(i, n) for(long long i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;

int main(){
  string s;
  int ans = 0;
  cin >> s;
  for(int i = 0;i < s.length();i++) {
    for(int j = 0;j < s.length();j++) {
      if(i == j) {
        continue;
      } else if (s[i] == s[j]) {
        ans = 1;
      }
    }
  }
  if (ans == 1) {
    cout << "no";
  } else {
    cout << "yes";
  }
}

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

int n, x[10], y[10];

int facto(int n){
  return (n == 1)? n : n * facto(n - 1);
}

int main(){
  cin >> n;
  rep(i, n) cin >> x[i] >> y[i];
  vector<int> seq(n);
  rep(i, n) seq[i] = i;
  double res = 0;
  do{
    rep(i, n - 1){
      res += sqrt(pow(x[seq[i + 1]] - x[seq[i]], 2) + pow(y[seq[i + 1]] - y[seq[i]], 2));
    }
  }while(next_permutation(seq.begin(), seq.end()));
  res /= facto(n);
  cout << setprecision(10) << res << endl;
  return 0;
}

Measured memory_bytes: 256
str = gets.rstrip
q = gets.to_i

q.times do
	cmd, a, b, _p = gets.split
	a = a.to_i
	b = b.to_i

	case cmd
	when 'print'
		puts str[a..b]
	when 'reverse'
		str[a..b] = str[a..b].reverse
	when 'replace'
		str[a..b] = _p
	end
end

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

const ll INF=1e11;
struct F { ll c, d; };
ll N, N1, N2, T;
vector<F> g1, g2;
// log_2 (10^9) < 40
vector<vector<ll>> dp(202020, vector<ll>(40, INF)); // dp[i][j]: 先頭からi個までみて、j個を選んだ後の時刻

signed main() {
  cin >> N >> T;
  rep(i, N) {
    ll a, b, c, d;
    cin >> a >> b;
    c = a + 1;
    d = a + b + 1;
    if (c -1 > 0) {
      g1.push_back(F{c, d});
    } else {
      g2.push_back(F{c, d});
    }
  }
  N1 = g1.size();
  N2 = g2.size();
  sort(begin(g1), end(g1), [](const F &f1, const F &f2) {
      ll c1 = f1.c, d1 = f1.d, c2 = f2.c, d2 = f2.d;
      return (c2-1)*d1 < (c1-1)*d2;
      });
  sort(begin(g2), end(g2), [](const F &f1, const F &f2) {
      ll c1 = f1.c, d1 = f1.d, c2 = f2.c, d2 = f2.d;
      return d1 < d2;
      });

  dp[0][0] = 0;
  rep(i, 202020) rep(j, 40) {
    if (dp[i][j] == INF)
      continue;
    ll ni = i + 1;
    // 次の店（i = i）を追加する
    if (ni < 202020 && i < N1) chmin(dp[ni][j+1], g1[i].c * dp[i][j] + g1[i].d);
    // 次の店（i = i）を追加しない
    if (ni < 202020) chmin(dp[ni][j], dp[i][j]);
  }

  ll ans = 0;
  rep(j, 40) {
    ll n = j, t = dp[202020-1][j];
    for (auto f : g2) {
      if (t + f.d <= T) {
        n++;
        t += f.d;
      }
    }
    if (t <= T) {
      chmax(ans, n);
    }
  }
  cout << ans << endl;
  return 0;
}


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

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

  mean = (a + b) / 2;
  
  if((a+b) % 2 == 0)
    cout << mean << endl;
  else
    cout << mean + 1 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
  long long X, Y;
  cin >> X >> Y;

  long long ret = 1;
  long long cur = X;
  while (true) {
    cur *= 2;
    if (cur > Y)
      break;
    ++ret;
  }

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAX = 200000;
const ll MOD = 1000000007;
ll n;
//string s;

ll battle(ll k){
    if(k==1){
        return 1;
    }else{
        return 1 + 2 * battle(k/2);
    }
}

int main() {
    cin >> n;
    ll ans = battle(n);
    cout << ans << endl;
    return 0;
}

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

int main() {
	int n, ac{ 0 }, wa{ 0 }, tle{ 0 }, re{ 0 };
	string s;

	cin >> n;
	for (int i{ 0 }; i < n; i++) {
		cin >> s;
		if (s == "AC") {
			ac++;
		}
		else if (s == "WA") {
			wa++;
		}
		else if (s == "TLE") {
			tle++;
		}
		else {
			re++;
		}



	}

	cout << "AC" << " " << "x" << " " << ac << endl;
	cout << "WA" << " " << "x" << " " << wa << endl;
	cout << "TLE" << " " << "x" << " " << tle << endl;
	cout << "RE" << " " << "x" << " " << re<<endl;
	return 0;
}

Measured memory_bytes: 3604
let l=require("fs").readFileSync("/dev/stdin","utf8").split("\n")
let i=0
while(true){
  let [h,w]=l[i++].split(" ").map(Number)
  if (!h&&!w)break
  let s="#".repeat(w)
  console.log(`${s}\n${`#${".".repeat(w-2)}#\n`.repeat(h-2)}${s}\n`)
}



Measured memory_bytes: 15196
/*
ID: yzshang1
LANG: C++11
TASK:
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pb push_back
#define mp make_pair
#define lsh(i) (1 << (i))
#define lshll(i) (1LL << (i))
#define repn(i, n) for (int (i) = 1; (i) <= (int)n; (i)++)
#define rep(i, n) for (int (i) = 0; (i) < (int)n; (i)++)
const int INF = 0x3f3f3f3f;
const long double EPS = 1e-6;
const int N = 100010;
const int MOD = 1e9 + 7;
LL a[N], n, fact[N], k;
LL qpow(LL a, LL b, LL p = MOD) {
	LL ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
	}
	return ans;
}
void prework() {
	fact[0] = 1;
	for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
}
LL getInv(LL x) {
	return qpow(x, MOD - 2);
}
LL C(int m, int n) {
	return fact[n] * (getInv(fact[m]) * getInv(fact[n - m]) % MOD) % MOD;
}
int main() {
	prework();
	cin >> n >> k;
	repn(i, n) cin >> a[i]; sort(a + 1, a + n + 1);
	LL mx = 0, mn = 0;
	repn(i, n) {
		if (i >= k) // can be used as maximum element
			//cerr << C(k - 1, i - 1) << ' ' << i << endl,
		    mx += a[i] * C(k - 1, i - 1) % MOD, mx %= MOD;
 	}
 	//cerr << mx << endl; 
 	repn(i, n) {
 		if (i + k - 1 <= n) { // can be used as minimum element
 			mn += a[i] * C(k - 1, n - i) % MOD, mn %= MOD;
		}
	}
	//cerr << mn << endl;
	cout << (mx - mn + 1LL * 19260817 * MOD) % MOD << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
static const int MAX=10e5,INF=10e9;
int main(void)
{
	int N,K;
		cin >> N >> K;
	int A[MAX];
	for(int i=0;i<N;i++)
		cin >> A[i];
	
	int ans=INF;
	for(int i=0;i<N-K+1;i++)
		ans=min(ans,A[i+K-1]-A[i]+min(abs(A[i+K-1]),abs(A[i]) ) );
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

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

int main(){
    int n,k; cin>>n>>k;
    string s;
    cin>>s;
    
    vector<int> Nums;
    
    int now = 1;  //今見ている数
    int cnt = 0;//nowがいくつ並んでいるか

    rep(i, n){
        if(s[i] == (char)('0' + now)) cnt++;
        else{
            Nums.push_back(cnt);
            now ^=1;  //０と１を切り替えるときの計算
            cnt = 1;
        }
    }
    if(cnt!=0) Nums.push_back(cnt);
    
    
    if(Nums.size() % 2 == 0) Nums.push_back(0);
    
    int Add = 2*k+1;
    
    int ans = 0;
    
    for(int i=0; i < Nums.size(); i += 2){
        int tmp = 0;
        
        int left = i;
        int right = min((int)Nums.size(),i + Add);
        
        for(int j = left; j<right;j++){
            tmp += Nums[j];
        }
        ans = max(tmp,ans);
        
        
        
        
        
    }
    
    
    cout << ans <<endl;
    

    
    
}


Measured memory_bytes: 1020
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i] >> y[i];
typedef long long int ll;
using namespace std;

int main(){
	int n; cin >>n;
	int cnt[200010]={};
	int ans=1e8;
	string s; cin >>s;
	for(int i=0;i<n;i++){
		cnt[i+1]=cnt[i];
		if(s[i]=='#')cnt[i+1]++;
	}
	for(int i=0;i<n+1;i++){
		ans=min(ans,cnt[i]+n-i-cnt[n]+cnt[i]);
	}
	cout << ans << endl;
}

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

int main() {
  long N, K;
  cin >> N >> K;
  vector<long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  vector<long> F(N);
  for (int i = 0; i < N; i++) cin >> F.at(i);
  sort(A.begin(), A.end());
  sort(F.rbegin(), F.rend());
  long ok = 1e18, ng = -1;
    while (ok - ng > 1) {
      long mid = (ok + ng) / 2;
      long sum = 0;
      for (int i = 0; i < N; i++) {
        if (A.at(i) * F.at(i) > mid) {
          long tmp = A.at(i) * F.at(i) - mid;
          sum += (tmp + F.at(i) - 1) / F.at(i);
        }
      }
      (sum <= K) ? ok = mid : ng = mid;
    }
  cout << ok << "\n";
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i = a:i<b;i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

const string D_blue    = "\x1b[36m";
const string D_green   = "\x1b[32m";
const string D_red     = "\x1b[31m";
const string D_yellow  = "\x1b[33m";
const string Db_red    = "\x1b[41m";
const string Db_yellow = "\x1b[43m";
const string D_end     = "\x1b[39m";
const string Db_end    = "\x1b[49m";

int main (){
  int A[3];
  while (cin >> A[0] >> A[1] >> A[2]){
    sort(A,A+3);
    int odd = 0, ans = 0;
    REP(i,3){
      if(A[i] % 2 == 1) odd++;
    }
    if(odd == 1){
      REP(i,3){
	if(A[i] % 2 != 1)A[i]++;
      }
      ans++;
    }else if(odd == 2){
      REP(i,3){
	if(A[i] % 2 == 1)A[i]++;
      }
      ans++;
    }

    ans += (A[2] - A[1]) / 2;
    ans += (A[2] - A[0]) / 2;
    
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define sz(a) (int)(a.size())
#define pb push_back
#define all(c) c.begin(),c.end()
#define tr(it,c) for(auto it=c.begin();it!=c.end();it++)
#define fr(i,n)	for(int i=0;i<n;i++)
#define present(c,x) (c.find(x)!=c.end()) //for set/map etc.
#define cpresent(c,x) (find(all(c),x)!=c.end())
typedef pair<int,int> pi;
	typedef vector<int> vi;
	typedef vector<vector<int>> vvi;
	typedef vector<long long> vll;
	typedef vector<pair<int,int>> vp;
int N=100001;
int mod=1e9+7;
int min(int a,int b){if(a<b) return a; else return b;}
int max(int a,int b){if(a>b) return a; else return b;}
int power(int a,int b){int res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int p, int q){if(p%q==0) return q; else{return gcd(q,p%q);}} 
bool comp(int a, int b) 
{ 
    return (a > b); 
} 

// string s,t,s1,t1;
// int ans()
// {
// 	// string s1,t1;
// 	s1.erase(all(s1));
// 	t1.erase(all(t1));
// 	int n= s.size();
// 	char c = s[0];
// 	if(n==1)return 0;
// 	// int n_s= s.size(),n_t = t.size();
// 	fr(i,n-1)
// 	s[i]=s[i+1];
// 	s[n-1]=c;
// 	fr(i,n)
// 	{
// 		if(t[i]!=s[i])
// 		{
// 			s1.pb(s[i]);
// 			t1.pb(t[i]);
// 		}
// 	}
// // 	s.clear();
// // 	t.clear();
// 	s=s1;
// 	t=t1;
// 	if(s1.size()==0)return 0;
// 	else
// 	{
// 		return ans()+1;
// 	}
// }

void solve()
{
	int n;
	cin>>n;
	vi v(n);
	int c=0;
	fr(i,n)
	{
		cin>>v[i];
		if(v[i]%2==1&&i%2==0)c++;
	}
	cout<<c;

}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	// int t;
	// cin>>t;
	// while(t--)
	// {
	// 	solve();
	// 	cout<<endl;
	// }
	solve();
	return 0;
	
}



Measured memory_bytes: 3628
/*
 *  Author  : StelaYuri
 * Language : GNU G++ 14
 */

//#pragma comment(linker,"/STACK:1024000000,1024000000")
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
//#include<unordered_map>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define pb push_back
#define eb emplace_back
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const double angcst=PI/180.0;
const ll mod=998244353;
ll max_3(ll a,ll b,ll c){if(a>b&&a>c)return a;if(b>c)return b;return c;}
ll min_3(ll a,ll b,ll c){if(a<b&&a<c)return a;if(b<c)return b;return c;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}



void solve()
{
    int x;
    cin>>x;
    cout<<(x^1)<<'\n';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3572
#include <stdio.h>
#define MN 200000
int n,m,cnt[MN+5],p[MN+5],a[MN+5],ans;
void add(int x){
	cnt[x]++;
	if(x-cnt[x]+1>0){
		if(p[x-cnt[x]+1]==0)ans--;
		p[x-cnt[x]+1]++;
	}
}
void rem(int x){
	if(x-cnt[x]+1>0){
		if(p[x-cnt[x]+1]==1)ans++;
		p[x-cnt[x]+1]--;
	}
	cnt[x]--;
}
int main(){
	scanf("%d%d",&n,&m);
	ans=n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(a[i]);
	}
	while(m--){
		int x,y; scanf("%d%d",&x,&y);
		rem(a[x]);
		add(y);
		a[x]=y;
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 3712
#include<stdio.h>
int main(void)
{
		int n,t[1000],i,j[1000],y[1000],x[1000],P,Q,R,C,w[1000],e,h,flg;
	while(1)	{
		scanf("%d",&n);
		if(n==0)	break;
		for(i=0;i<n;i++){
			scanf("%d %d %d %d",&t[i],&j[i],&y[i],&x[i]);
			w[i]=4*j[i]+9*y[i]+4*x[i];
//		printf("%d\n",w);	
			}
		scanf("%d %d %d %d",&P,&Q,&R,&C);
		flg=0;
		for(i=0;i<n;i++){
			if(j[i]<=P&&y[i]<=Q&&x[i]<=R&&w[i]<=C){
				printf("%d\n",t[i]);
				flg=1;
			}
//		printf("%d\n",flg);	
		}	
		if(flg==0){
		printf("NA\n");
		}
	}	
	return 0;
}

Measured memory_bytes: 1060