akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define DEBUG

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 1; i <= n; i++)
#define REPR(i, n) for(ll i = n; i >= 1; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define INF 1e9+123
#define VEC(type,A,N) vector<type> A(N+10)
#define VECi(type,A,N,i) vector<type> A(N+10,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N+10,vector<type>(M+10))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N+10,vector<type>(M+10,i))
#define ALL(v) v.begin()+1, v.end()-9
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
int main(){
    ll N,M;
    cin>>N>>M;
    
    cout<<(N*(N-1))/(2)+(M*(M-1))/(2);
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int ans=0,s=S.size();
    for (int i=0;i<s-1-i;++i) if (S[i]!=S[s-1-i]) ++ans;
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
f=0
for s in sys.stdin:
    f=1-f
    b=map(int,s.split())
    if f:
        a=b
        continue
    c1=0
    c2=0
    for i,e in enumerate(b):
        if e==a[i]: c1+=1
        elif e in a: c2+=1
    print c1, c2

Measured memory_bytes: 4204
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def update(self, l, r, x):
        """
        半開区間 [l, r) の値を x に更新 （ 1-indexed ）　（ O(logN) ）
        """
        l += self.size
        r += self.size
        self.propagate(l)
        self.propagate(r-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = x
            if l&1:
                self.lazy[l] = x
                l += 1
            l = l // 2
            r = r // 2

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        for k in range(self.depth,0,-1):
            x = i>>k
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)+1] = self.lazy[x]
            self.lazy[x<<1] = self.lazy[x]
            self.lazy[x] = self.e

    def get(self, i):
        """
        i 番目の値を取得（ 1-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)+1] = self.lazy[x]
            self.lazy[x<<1] = self.lazy[x]
            self.lazy[x] = self.e
        for a in self.lazy[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)+1] = self.lazy[x]
            self.lazy[x<<1] = self.lazy[x]
            self.lazy[x] = self.e
        return str(self.lazy[self.size:self.size + self.n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

N, Q = map(int, input().split())

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

D = [int(input()) for _ in range(Q)]

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(*st, sep="\n")

Measured memory_bytes: 145992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		System.out.println(jadge());
	}

	public static int jadge() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();
		int count = 0;
		int jadge = 0;

		while(true) {
			for(int j = 0; j < n; j++) {
				if(a[j] % 2 == 0) {
					a[j] /= 2;
					jadge++;
				} else {
					return count;
				}
			}
			if(jadge == n) {
				count++;
			}
			jadge = 0;
		}
	}

}

Measured memory_bytes: 22228
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int main(){
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if(a[0]==5&&a[1]==5&&a[2]==7)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]

H = set([])
N = int(input())
a = inpl()
sugoi = 0

for i in range(N):
    if a[i] < 400:
        H.add('gray')
    elif a[i] < 800:
        H.add('brown')
    elif a[i] < 1200:
        H.add('green')
    elif a[i] < 1600:
        H.add('sky')
    elif a[i] < 2000:
        H.add('blue')
    elif a[i] < 2400:
        H.add('yellow')
    elif a[i] < 2800:
        H.add('orange')
    elif a[i] < 3200:
        H.add('red')
    else:
        sugoi += 1

ans = [max(len(H),1),max(len(H)+sugoi,1)]
print(*ans)

Measured memory_bytes: 3064
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()

A=many_int()

def color_check(num):
    if 1<=num<=399:
        return "hai"
    elif 400<=num<=799:
        return "tya"
    elif 800<=num<=1199:
        return "midori"
    elif 1200<=num<=1599:
        return "mizu"
    elif 1600<=num<=1999:
        return "ao"
    elif 2000<=num<=2399:
        return "ki"
    elif 2400<=num<=2799:
        return "dai"
    elif 2800<=num<=3199:
        return "aka"
    return ""

output = []
overs = 0
for a in A:
    if a >= 3200:
        overs+=1
    else:
        output.append(color_check(a))

cols = len(set(output))
if cols==0:
    cols = 1 
    overs -= 1 
print(cols, cols+overs)

Measured memory_bytes: 38256
#include <stdio.h>
#include <iostream>

using namespace std;

int main(void){
	int r, g, b;
	int ans;
	string out = "NO";
	cin >> r >> g >> b;
	ans = g*10+b;
	if(ans%4 == 0){
		out = "YES";
	}
	cout << out << endl;
	
	return 0;
}

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

main(){
  ios_base::sync_with_stdio(false);
  int n,a,b,sum=0;
  cin >> n;
  
  for(int i=0;i<n;i++){
    cin >> a >> b;
    sum += (b-a+1);
  }
  
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){

    int a, b, sum = 0 , cnt = 0;
    cin >> a >> b ;
    
    vector<int> vote(a);
    for(int i = 0; i < a; i++){
        cin >> vote.at(i) ;
        sum += vote.at(i);
    }

    for(int i = 0; i < a; i++){
        if(sum <= vote.at(i) * 4 * b){
            cnt++;
        }
    }

    if(cnt >= b){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const N=2e5+500;
ll INF=0x3f3f3f3f;
map<string,ll>mp;
int main()
{
    string str[N],str1[N];
    ll n,a[N],b,c,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>str[i];
        mp[str[i]]++;
    }
    ll k=0,kk=0;
    for(int i=1;i<=n;i++)
    {
        if(mp[str[i]]>k)
        {
            k=mp[str[i]];
            kk=i;
        }
    }
    for(int i=1;i<=n;i++)
        if(mp[str[i]]==k)
        {
            str1[++cnt]=str[i];
            //cout<<str[i]<<endl;
            mp[str[i]]=0;
        }
    sort(str1+1,str1+1+cnt);
    for(int i=1;i<=cnt;i++)
        //if(mp[str[i]]==k)
    {
         //   str1[++cnt]=str[i];
            cout<<str1[i]<<endl;
           // mp[str[i]]=0;
    }
    return 0;
}


Measured memory_bytes: 29440
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define lop(i,s,t) for(int i=s;i<(t);++i)
using namespace std;

const int N=105;

int n,eu[N],ev[N],ans1,a[N],deg[N];
vector<int> g[N]; 
long long ans2;

void dfs(int v,int p,int dep){
	int son=0; 
	for(int d:g[v])if(d!=p){
		dfs(d,v,dep+1); 
		++son;
	}
	cmax(a[dep],son); 
}

void chk(){
	int res1=0; 
	long long res2=1;
	for(;a[res1];++res1)res2*=a[res1];
	if(res1<ans1||(res1==ans1&&res2<ans2)){
		ans1=res1,ans2=res2;
	}
}

int main(int argc,char *argv[]){
	scanf("%d",&n); 
	rep(i,1,n-1){
		scanf("%d%d",eu+i,ev+i); 
		g[eu[i]].pb(ev[i]); 
		g[ev[i]].pb(eu[i]); 
		++deg[eu[i]],++deg[ev[i]];
	}
	ans1=1e9; 
	rep(i,1,n){
		mem(a,0);
		a[0]=1;
		dfs(i,0,1); 
		chk(); 
	}	
	rep(i,1,n-1){
		mem(a,0);
		a[0]=2;
		dfs(eu[i],ev[i],1); 
		dfs(ev[i],eu[i],1); 
		chk();
	}
	printf("%d %lld\n",ans1,ans2);
}


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

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

    int total = 0;
    if(s[0] == '1') total++;
    if(s[1] == '1') total++;
    if(s[2] == '1') total++;
    
    cout << total << endl;
}

Measured memory_bytes: 3552
n = int(input())
a = list(map(int, input().split()))
cnt = 0

def bubble_sort(a):
    global cnt
    for i in range(len(a)):
        l = 0
        r = 1

        while r < len(a):
            if a[l] > a[r]:
                a[l], a[r] = a[r], a[l]
                cnt += 1
            l += 1
            r += 1


    # for i in range(len(a)):
    #     for j in range(i + 1, len(a)):
    #         if a[i] > a[j]:
    #             a[i], a[j] = a[j], a[i]

bubble_sort(a)
print(*a)
print(cnt)



Measured memory_bytes: 5604
def s():
	n, k = map(int, input().split())
	ans = ["1 {}".format(i) for i in range(2, n + 1)]
	c = (n - 1) * (n - 2) // 2
	if k > c:
		print(-1)
		exit()
	for i in range(2, n):
		for j in range(i + 1, n + 1):
			if c == k:
				break
			ans += ["{} {}".format(i, j)]
			c -= 1
		else:
			continue
		break
	print(len(ans))
	print(*ans)

if __name__=="__main__":
	s()

Measured memory_bytes: 3716
x=int(input())

if x>=400 and x<=599:
    print(8)
elif x>=600 and x<=799:
    print(7)
elif x>=800 and x<=999:
    print(6)
elif x>=1000 and x<=1199:
    print(5)
elif x>=1200 and x<=1399:
    print(4)
elif x>=1400 and x<=1599:
    print(3)
elif x>=1600 and x<=1799:
    print(2)
elif x>=1800 and x<=1999:
    print(1)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,ans=0,cnt=1;
  cin >> n;
  long long a[n],sum[n+1]={};
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum[i+1]+=sum[i]+a[i];
  }
  sort(sum,sum+n+1);
  for(int i=1;i<=n;i++){
    if(sum[i]==sum[i-1]){
      cnt++;
    }else{
      ans+=(cnt*(cnt-1))/2;
      cnt=1;
    }
  }
  ans+=(cnt*(cnt-1))/2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<fstream>
#include<map>
#include<bitset>
#include<unordered_map>
#include<cstring>
#include<cctype>
using namespace std;
#define  ll long long
#define  ull unsigned long long
#define  ul unsigned long
#define all(v) v.begin(),v.end()
#define sz(n) (int)n.size()
#define pb(s) push_back(s);
#define format(n) fixed<<setprecision(n)
#define finl "\n"
#define Mohammed_Atef_Hassan fast();
#define mod 1000000007
#define INF LLONG_MAX
#define PI acos(-1)
#define clr(dp,n) memset(dp,n,sizeof dp)
#define ex(n) return cout<<n<<finl,0;
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
ll fix_mod(ll x, ll y)
{
	return (y + x % y) % y;
}
void fast() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

}
int main()
{
	Mohammed_Atef_Hassan
		int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i <n; i++)
	{
		v[i] = i + 1;
	}
	vector<int>a(n), b(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	pair<ll, ll>ans;
	int idx = 1;
	do {
		if (a == v)ans.first = idx;
		if (b == v)ans.second = idx;
		idx++;
	} while (next_permutation(all(v)));
	cout << abs(ans.first - ans.second) << finl;
}

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

int main()
{
	char str[21];
	int i;
	scanf("%s",str);
	for(i = (strlen(str)-1);i >= 0;i--)
	{
		putchar(str[i]);
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;

using namespace std;
typedef long long ll;

int main()
{
    int m;
    cin >> m;
    loop(m, i) {
        string t;
        cin >> t;

        set<string> set;
        set.insert(t);
        for (int j = 1; j < t.length(); j++) {
            string f1, f2, b1, b2;
            f1 = f2 = t.substr(0,j);
            b1 = b2 = t.substr(j);
            reverse(all(f2));
            reverse(all(b2));
            set.insert(f1+b2);
            set.insert(f2+b1);
            set.insert(f2+b2);
            set.insert(b1+f1);
            set.insert(b1+f2);
            set.insert(b2+f1);
            set.insert(b2+f2);
        }
        cout << set.size() << endl;
    }
    return 0;
}

Measured memory_bytes: 3164
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 14000;
int G[MAX][MAX];
int dp[MAX][MAX];
int main()
{
	int H, W;
	cin >> H >> W;
	int flag = 0;
	int maxWidth = 0;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
		{
			cin >> G[i][j];
			dp[i][j] = (G[i][j] + 1) % 2;
			if (dp[i][j])
			{
				maxWidth = 1;
				flag = 1;
			}
		}
	for (int i = 1; i < H; i++)
		for (int j = 1; j < W; j++)
			if (G[i][j])
				dp[i][j] = 0;
			else
			{
				dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
				maxWidth = max(maxWidth, dp[i][j]);
			}
	cout << maxWidth * maxWidth << endl;
}


Measured memory_bytes: 29508
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	string s,t;
	cin >> s >> t;
	bool flg=true;
	for(int i=0;i<s.size();i++)
		if(s[i]!=t[i])
			flg=false;
	cout << (flg ? "Yes":"No") << endl;
	




}

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

int main () {
	int S;
	int a;
	int b;
	cin >> S;
	a = S/3600;
	b = (S-a*3600)/60;
	cout << a << ":" << b << ":" << S-a*3600-b*60 << endl;
	return 0;
}


Measured memory_bytes: 3112
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define int long long


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

    int n; cin >> n;
    vector<int> t(n+1),x(n+1),y(n+1);

    for(int i = 1;i < n+1;i ++){
        cin >> t.at(i) >> x.at(i) >> y.at(i);
    }

    bool ans = true;

    for(int i = 1;i < n+1;i ++){
        int dt = abs(t.at(i)-t.at(i-1));
        int dx = abs(x.at(i)-x.at(i-1));
        int dy = abs(y.at(i)-y.at(i-1));

        if((dx+dy)%2 != dt%2 || dx+dy > dt) ans = false;
    }

    if(ans == true) cout << "Yes" << endl;
    else cout << "No" << endl;
}



Measured memory_bytes: 2560
/**
 * Step Aerobics
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {

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


		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = parseInt(line);
			if (n == 0) break;

			int count = 0;
			int steps = 0;

			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				String step = st.nextToken();
				if (step.charAt(0) == 'l') {
					if (step.charAt(1) == 'u') {
						steps += 2;
					} else {
						steps -= 2;
					}
				} else {
					if (step.charAt(1) == 'u') {
						steps += 1;
					} else {
						steps -= 1;
					}
				}
				if (steps == 3) {
					steps += 4;
					count++;
				} else if (steps == 4) {
					steps -= 4;
					count++;
				}
			}
			System.out.println(count);
		}
	} //end while
} //end main

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

using namespace std;

const int N = 55;
//51min!!
const int mod = 1e9+7;

int h;
int w;
int n;
long long ans[11];
set < pair < int , int > > grid , points;

int main(){
    scanf("%d%d%d" , &h , &w , &n);
    long long subgrids = 1LL * (h - 2) * (w - 2);
    //cout << subgrids << "\n";
    for(int i = 1; i <= n; i++){
        int x , y;
        scanf("%d%d" , &x , &y);
        points.insert({x , y});
        for(int a = -2; a <= 0; a++)
            for(int b = -2; b <= 0; b++)
                    grid.insert({x + a , y + b});
    }
    long long sum = 0;
    auto it = grid.begin();
    for(; it != grid.end(); it++){
        int cnt = 0;
        int x = it->first;
        int y = it->second;
        if(x < 1 || x > h-2 || y < 1 || y > w - 2)
            continue;
        for(int i = 0; i <= 2; i++)
            for(int j = 0; j <= 2; j++)
                if(points.find({x+i , y+j}) != points.end()){
                    cnt++;
                }
        //if(x + 2 <= h && y + 2 <= w){
            sum ++;
            ans[cnt]++;
        //}
    }
    ans[0] = subgrids - sum;
    for(int i = 0; i <= 9; i++){
        printf("%lld\n" , ans[i]);
    }
}


Measured memory_bytes: 50712
#include <iostream>

using namespace std;

int main() {
  int K, A, B;
  cin >> K >> A >> B;
  auto f = [&](int x) { return x / K; };
  cout << (f(B) - f(A - 1) > 0 ? "OK" : "NG") << endl;
  return 0;
}


Measured memory_bytes: 3040
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int N;
    cin >> N;

    cout << N * N * N << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >>N;
  int a[N];
  for(int i=0;i<N;i++){
    cin >> a[i];
  }
  int min=a[0];
  int c=1;
  for(int i=1;i<N;i++){
    if(a[i]<=min){
      min = a[i];
      c++;
    }
  }
  cout <<c<<endl;
}

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

N, M = MAP()
path = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]

for a, b in path:
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

for i in range(len(graph[0])):
	a = sorted(graph[graph[0][i]])
	if a[len(a) - 1] == N - 1:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

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

int main() {
    string in; cin >> in;
    int check[26] = {0};
    int n = in.size();
    for (int i = 0; i < n; i++)
        check[in[i] - 'a'] = true;

    if (n != 26) {
        for (int i = 0; i < 26; i++) {
            if (check[i]) continue;
            cout << in + char(i + 'a') << endl;
            break;
        }
    } else {
        string in2 = in;
        int permutable  = next_permutation(in2.begin(), in2.end());
        if (!permutable) {
            cout << -1 << endl;
        } else {
            for (int i=0; i<n; i++) {
                if (in[i] == in2[i]) {
                    cout << in[i];
                } else {
                    cout << in2[i] << endl;
                    break;
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
int n,a[100009];
void END(){
  cout<<-1<<endl;
  exit(0);
}
main(){
  cin>>n;
  r(i,n)cin>>a[n-i-1];
  if(a[0]!=2)END();
  int l=2,r=3;
  for(int i=1;i<n;i++){
    int x=a[i];
    if(!(x<=r)||(l/x==r/x&&(l%x!=0)&&(r%x!=0)))END();
    if(l>=x&&(l%x==0))l=((l-1)/x+1)*x;
    else l=(l/x+1)*x;
    r=(r/x)*x+(x-1);
  }
  cout<<l<<' '<<r<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <stack>
#include <iomanip>
#include <cmath>


using namespace std;


typedef long long ll;
typedef long double ld;


const ll MOD = 1000000007ll;


ll modSum(ll a, ll b) {
  return ((a % MOD) + (b % MOD)) % MOD;
}


ll modSubtract(ll a, ll b) {
  return (((a % MOD) - (b % MOD)) + MOD + MOD) % MOD;
}


ll modProd(ll a, ll b) {
  return ((a % MOD) * (b % MOD)) % MOD;
}


ll getPowMod(ll x, ll e) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPowMod(x, e/2);
    return modProd(tmp, tmp);
  } else {
    ll tmp = getPowMod(x, e-1);
    return modProd(tmp, x);
  }
}


ll getPow(ll x, ll e) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPow(x, e/2);
    return tmp * tmp;
  } else {
    ll tmp = getPow(x, e-1);
    return tmp * x;
  }
}


ll getInverse(ll x) {
  return getPowMod(x, MOD-2);
}


bool isEven(ll x) {
  ll tmp = ((x % 2) + 2) % 2;
  return tmp == 0;
}


ll getSumOfDigitsInBase(ll n, ll b) {
  ll ret = 0;
  while (n > 0) {
    ret += n % b;
    n /= b;
  }
  return ret;
}


vector<int> getKMP(string &s) {
  int len = (int)s.size();
  vector<int> ret (len, 0);
  for (int i = 1 ; i < len ; i++) {
    int at = ret[i-1];
    while (at > 0 && s[i] != s[at]) {
      at = ret[at-1];
    }
    if (s[i] == s[at]) {
      at++;
    }
    ret[i] = at;
  }
  return ret;
}


string getSubstring(string &s, int from, int to) {
  int l = to-from+1;
  if (l <= 0) {
    return "";
  }
  return s.substr(from, l);
}

ll gcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}












const int MAXN = 100001;


int N, T;
ll maxDiff;
ll ar[MAXN], rlMax[MAXN];
map<ll, int> freq;


void input() {
  cin >> N >> T;
  for (int i = 1 ; i <= N ; i++) {
    cin >> ar[i];
  }
}


void preprocess() {
  for (int i = 1 ; i <= N ; i++) {
    freq[ar[i]]++;
  }
  rlMax[N] = ar[N];
  for (int i = N-1 ; i >= 1 ; i--) {
    rlMax[i] = max(rlMax[i+1], ar[i]);
  }
  maxDiff = 0;
  for (int i = 1 ; i <= N ; i++) {
    maxDiff = max(maxDiff, rlMax[i] - ar[i]);
  }
}


void solve() {
  //cerr << "maxDiff = " << maxDiff << "\n";
  int ans = 0;
  for (int i = 1 ; i <= N ; i++) {
    if (freq[ar[i]] > 0 && freq[ar[i]+maxDiff] > 0) {
      freq[ar[i]+maxDiff]--;
      ans++;
    }
    freq[ar[i]]--;
  }
  cout << ans;
}


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

  int T;
//  cin >> T;
  T = 1;

  for (int i = 0 ; i < T ; i++) {
    input();
    preprocess();
    solve();
  }

  return 0;
}


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

int main() {
    string s; cin >> s;
    int cnt=0;
    rep(i, s.size()) {
        if (s[i] == '+') cnt ++;
        else cnt--;
    }
    cout << cnt << endl;
    return 0;
}

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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

typedef long long lint;
typedef double Double;
typedef pair< int, int > pii;

typedef vector< int > Array;
typedef vector< Array > Matrix;

int N, Q;
int C[300030];
int mod_table[300030];

void solve() {
	minit(mod_table, 0);
	sort(C, C + N + 2);
	
	for_(q,1,300001) {
		for (int j = q; j <= C[N] + q; j += q) {
			int i = lower_bound(C, C + N + 2, j) - C;
			if (i == 0) continue;
			--i;
			mod_table[q] = max(mod_table[q], C[i] % q);
		}
	}
	
	for_(i,0,Q) {
		int q; cin >> q;
		cout << mod_table[q] << endl;
	}
}

int main() {
	cin >> N >> Q;
	C[0] = 0;
	for_(i,0,N) cin >> C[i + 1];
	C[N + 1] = (int)1e9;
	solve();
	return 0;
}

Measured memory_bytes: 3528
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;

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

template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

int main() {
	int n;
	cin >> n;
	VV<int> h(n, V<int>(3, 0));
	VV<int> dp(n+1, V<int>(3, 0));
	rep(i, n) {
		rep(j,3)
			cin >> h[i][j];
	}
	rep(i,n)rep(j, 3)rep(k,3) {
		if (j == k)continue;
		chmax(dp[i + 1][j], dp[i][k] + h[i][j]);
	}
	int r=0;
	rep(i, 3) {
		r = max(r, dp[n][i]);
	}
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 11136
# _*_ coding:utf-8 _*_
#  Atcoder_Grand_Contest029-B
#  https://agc029.contest.atcoder.jp/tasks/agc029_b
from collections import Counter

def  maxCountPair(n_ballCount,a_ballDatas):
	a_ballDatas.sort(reverse=True)
	ballDictBox = Counter(a_ballDatas)
	ballCountRange = range(0,n_ballCount)
	pairCount = 0
	for i in ballCountRange:
		getBallNumber = a_ballDatas[i]
		getBallNumberBin = getBallNumber.bit_length()
		nextTwoPower = 2**getBallNumberBin
		diffNumber = nextTwoPower - getBallNumber
		if ( 1 <= ballDictBox[diffNumber] and 1<= ballDictBox[getBallNumber]):
			if getBallNumber != diffNumber:
				pairCount = pairCount + 1
				ballDictBox[getBallNumber]=ballDictBox[getBallNumber]-1
				ballDictBox[diffNumber] = ballDictBox[diffNumber]-1
			else:
				if 2 <= ballDictBox[diffNumber]:
					pairCount = pairCount + 1
					ballDictBox[diffNumber]=ballDictBox[diffNumber]-2
	answer = pairCount
	return answer


if __name__ == '__main__':
	n_ballCount=int(input())
	a_ballDatas=list((map(int,input().split(" "))))
	solution=maxCountPair(n_ballCount,a_ballDatas)
	print(solution)


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

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define PF push_front
#define PB push_back
#define FST first
#define SEC second
#define sz(obj) ((int)(obj).size())
#define ALL(v) (v).begin(), (v).end()

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int gcd(int a, int b){ int c; while (a != 0){ c = a; a = b % a; b = c; } return b; }

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

  int n;
  cin >> n;
  int a[n];
  int sum = 0, cost = 0;
  double ave;

  REP(i, n) cin >> a[i];
  REP(i, n) sum += a[i];
  ave = sum / (double)n;
  ave += (int)(ave * 10) % 10 > 4 ? 1 : 0;

  REP(i, n) cost += (a[i] - (int)ave) * (a[i] - (int)ave);

  cout << cost << endl;

  return (0);
}


Measured memory_bytes: 256
n, k = map(int, input().split())

no_rem = 0
rem_half = 0

for i in range(1,n+1):
    no_rem += 1 if i % k == 0 else 0

    rem_half += 1 if k%2 == 0 and i%k == k//2 else 0

print(no_rem ** 3 + rem_half**3)
    

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    ll n, m;
    cin >> n >> m;
    dsu d(n);
    REP(i, m){
        ll ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        d.merge(ai, bi);
    }

    set<ll> s;
    REP(i, n){
        s.insert(d.leader(i));
    }

    cout << s.size() - 1 << endl;
    return 0;
}


Measured memory_bytes: 7540
n = gets.to_i
a = gets.split.map(&:to_i)
inv = 0
b = 100000000
a.each do |num|
    inv += b/num
end
puts (b*b/inv)/b.to_f

=begin
n,m = gets.split.map(&:to_i)
puts ">"*(m*7+3)+"<<<<<<<[#{">"*(n*7)}+#{"<"*(n*7)}-]"*m+">"*(n*7-3)+"+"*n+"[-[<<<<<<<+>>>>>>>-]<<<<"+">>>>>>>[<<<<<<<+>>>>>>>-]"*m+"<"*(m*7+2)+"+[>+>"+"[>+>>+<<<-]>>>[<<<+>>>-]<<[->[>>+<]>[<]>-[>>>>+<<<<<<++++++++++>>+]<<-<]>>>>>>"*(m+1)+">["+"<"*(m*7+10)+"->->"+"[>+>>+<<<-]>>>[<<<+>>>-]<<[->---------[>>+<]>[<]>-[>>>>+<<<<<<---------->>+]<<++++++++++<]>>>>>>"*(m+1)+">[-]]"+"<"*(m*7+10)+"]<]"


# a/b
# n = ceil(log_10 a)
# m = ceil(log_10 b)
# 
# a = a_0+a_1*10+......a_(n-1)*10**(n-1)
# b = b_0+b_1*10+......b_(n-1)*10**(m-1)
#
# 7 cells = 1 digit
# [*][][][b_0][][a_0][] [][][][b_1][][a_1][] ......
# 
# [*][][quo_0][][][mod_0][] [][][quo_1][][][mod_1][] ......

=end

Measured memory_bytes: 1788
#include<stdio.h>
#include<math.h>
int main()
{
  int number[10000];
  int n,i,j,flag=0;
  scanf("%d",&n);
  for(i=0;i<n && i<=10000;i++)
    {
      scanf("%d",&number[i]);
      if (number[i] < 2) continue;
      else if (number[i] == 2 || number[i]==3 || number[i]==5 ||
	       number[i]==7)
	{
	  flag++;
	  continue;
	}
      
      else if (number[i] % 2 == 0) continue;
      for(j=3;j<=sqrt(number[i]);)
	{
	  if(number[i]%j==0) break;
	  j+=2;
	  if(j>sqrt(number[i])) flag++;
	}
    }
  printf("%d\n",flag);
  return 0;
}



Measured memory_bytes: 2108
import java.util.*;

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

		int N = sc.nextInt();
		long ans = 0;
		
		long rest = 0;
		for(int i=0; i<N; i++) {
			long A = sc.nextLong();
			ans += (A+rest)/2;
			if(A>0 && (A+rest)%2==1)
				rest = 1;
			else
				rest = 0;
		}
		
		
		System.out.println(ans);
		
		sc.close();
	}
}


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


typedef long long ll;
const int maxn = (int)1e6 + 5;
const int mod = (int)1e9 + 9;
using namespace std;

ll x[maxn];
int v[maxn];
ll c[maxn], cc[maxn];
/*
  cmx[maxn]:時計回りに進んだときの最大値
  ccmx[maxn]:反時計回りに進んだときの最大値
*/
ll cmx[maxn], ccmx[maxn];

int main()
{
	int n; ll C; 
	cin >> n >> C;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> v[i];
	}
	//時計回りに進んだときの最大値を求める
	for (int i = 1; i <= n; i++) {
		c[i] = c[i - 1] + v[i] - (x[i] - x[i - 1]);
		cmx[i] = max(cmx[i - 1], c[i]);
	}
	//半時計回りに進んだときの最大値を求める
	x[n + 1] = C;
	for (int i = n; i >= 1; i--) {
		cc[n - i + 1] = cc[n - i] + v[i] - (x[i + 1] - x[i]);
		ccmx[n - i + 1] = max(ccmx[n - i], cc[n - i + 1]);
	}
	/*
	  時計回りに進んだときの、反時計回りの最大値と
	  反時計回りに進んだときの、時計回りの最大値を比較して
	  で大きいほうが答え
	*/
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		ans = max(ans, c[i] - x[i] + ccmx[n - i]);
		ans = max(ans, cc[i] - (C - x[n - i + 1]) + cmx[n - i]);
	}

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


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

int main() {
    int N, P, W, G, Y;
    P = W = G = Y = 0;  
    cin >> N;
    
    rep(i, N) {
        string Arare;
        cin >> Arare;
        if (Arare == "P") P += 1;
        if (Arare == "W") W += 1; 
        if (Arare == "G") G += 1; 
        if (Arare == "Y") Y += 1; 
    }

    if (P == 0 || W == 0 || G == 0 || Y == 0) {
        cout << "Three" << endl;
    }
    else {
        cout << "Four" << endl;
    }
}


Measured memory_bytes: 256
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<string>
#include<utility>
#include<vector>
using namespace std;

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

int main() {
	long res = INT_MAX;
	long N; cin >> N;
	long x[100], y[100]; for (int i = 1; i <= N; i++) cin >> x[i] >> y[i];
	long DX[100][100] = {}, DY[100][100] = {}; //index m < n

	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { DX[i][j] = x[i] - x[j]; DY[i][j] = y[i] - y[j]; }
	long p, q , myres;
	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
        if (i == j) continue;
		p = DX[i][j]; q = DY[i][j];
		myres = 0;
		for (int m = 1; m <= N; m++) for (int n = 1; n <= N; n++) {
			if (DX[m][n] == p && DY[m][n] == q) myres++;
		}
		if (N - myres == 0) cout << p << " " << q << endl;
        res = min(res, N - myres);
        
	}
if (N == 1) res = 1;
	cout << res << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
using namespace std;
int main()
{
  int n,i,res=0;
  string s;
  cin >> s;
  n=s.size();
  for(i=0;i<n/2;i++){
    if(s.substr(i,1)!=s.substr(n-1-i,1))
      res++;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7


def cmb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    # pow(den,MOD-2,MOD)はdenの逆元
    return num * pow(den, MOD - 2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    R = N - K
    for i in range(K):
        A = cmb(R + 1, i + 1)
        if i >= 1:
            B = cmb(K - 1, i)
        else:
            B = 1
        print(A * B % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3940
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)
#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;--i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define dbg(x) cerr<<#x" = "<<x<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge *i=G[x];i;i=i->nxt)
typedef long long ll;
typedef pair<int,int> pii;
const int inf=~0u>>1,MOD=1e9+7;
inline int rd() {
    int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';
    while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;
}
const int N=1e5+11;
struct Edge{int v;Edge*nxt;}pl[N<<1],*cur=pl,*G[N];
inline void ins(int u,int v){*cur=(Edge){v,G[u]},G[u]=cur++;}
int n;
int dfs(int x,int f=-1){
	int p=1;
	Es(x,i)if(i->v!=f)p-=dfs(i->v,x);
	if(p<0)puts("First"),exit(0);
	return p;	
}
int main(){
#ifdef flukehn
	freopen("test.txt","r",stdin);
#endif
	n=rd();
	if(n&1)puts("First"),exit(0);
	For(i,1,n){
		int u=rd(),v=rd();
		ins(u,v),ins(v,u);
	}
	dfs(1);
	puts("Second");
}

Measured memory_bytes: 4096
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').let {
        it[0].toInt() to it[1].toLong()
    }
    val a = readLine()!!.split(' ').map { it.toInt() }.sorted().toIntArray()
    val f = readLine()!!.split(' ').map { it.toInt() }.sortedDescending().toIntArray()

    var l = 0L
    var r = 1e12.toLong()
    while (l < r) {
        val x = l + (r - l) / 2

        val s = (0 until n).map { Math.max(a[it] - (x / f[it]), 0) }.sum()

        if (s <= k) {
            r = x
        } else {
            l = x + 1
        }
    }

    println(l)
}


Measured memory_bytes: 156912
module IO = struct

  (* @since 4.04.0 *)
  let split_on_char sep s =
    let open String in
    let r = ref [] in
    let j = ref (length s) in
    for i = length s - 1 downto 0 do
      if get s i = sep then begin
        r := sub s (i + 1) (!j - i - 1) :: !r;
        j := i
      end
    done;
    sub s 0 !j :: !r

  let read_ns () = read_line () |> split_on_char ' ' |> List.map int_of_string

end

let solve h w c =
  let s = Array.make w 0 in
  let t = Array.make w 0 in
  let r = ref 0 in
  for i = 0 to h - 1 do
    if c.(i).(0) = 0 then r := 1
  done;
  for j = 0 to w - 1 do
    if c.(0).(j) = 0 then begin
      s.(j) <- 1;
      r := 1
    end
  done;
  for i = 1 to h - 1 do
    if c.(i).(0) = 0 then t.(0) <- 1;
    for j = 1 to w - 1 do
      if c.(i).(j) = 1 then t.(j) <- 0
      else begin
        let d = if s.(j) < t.(j-1) then s.(j) else t.(j-1) in
        t.(j) <- 1 + if s.(j-1) < d then s.(j-1) else d;
        if t.(j) > !r then r := t.(j)
      end
    done;
    Array.iteri (fun i e -> s.(i) <- e) t
  done;
  !r * !r

let () =
  match IO.read_ns () with
  | [h; w] ->
    let c = Array.make_matrix h w 0 in
    for i = 0 to h - 1 do
      IO.read_ns () |> List.iteri (fun j e -> c.(i).(j) <- e);
    done;
    solve h w c |> Printf.printf "%d\n"
  | _ -> assert false

Measured memory_bytes: 25336
N,K=map(int,input().split())
S=input()
L=[0]
#even:1
#odd:0
tmp="1"
for i in range(N):
    if tmp!=S[i]:
        L.append(1)
    else:
        L[-1]+=1
    tmp=S[i]
if tmp=="0":
    L.append(0)
#print(L)
M=len(L)
if M<=2*K+1:
    print(N)
    exit()
X=[0 for i in range(M+1)]
for i in range(M):
    X[i+1]=L[i]+X[i]
#print(X)
ans=0
for i in range(0,M-2*K,2):
    #print(X[i],X[i+2*K+1])
    ans=max(ans,X[i+2*K+1]-X[i])
print(ans)

Measured memory_bytes: 7880
#include <stdio.h>
 
using namespace std;
 
int main(){
    int a,b;
    while(true){
        scanf("%d %d",&a,&b);
        if(a == 0 && b == 0) break;
        if(a > b) printf("%d %d\n",b,a);
        else{
            printf("%d %d\n",a,b);
        }
    }
}



Measured memory_bytes: 2572
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		ULL N; cin >> N;
		int A[3], B[3];
		rep(i, 3) cin >> A[i];
		rep(i, 3) cin >> B[i];
		rep(t, 2) {
			vector<ULL> dp(N + 1);
			ULL ans = 0;
			rep(i, N + 1) {
				ULL &p = dp[i];
				rep(j, 3) {
					if (A[j] <= i)
						p = max(p, dp[i - A[j]] + B[j]);
				}
				ans = max(ans, dp[i] + N - i);
			}
			N = ans;
			rep(i, 3) swap(A[i], B[i]);
		}
		cout << N << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}

Measured memory_bytes: 195584
n = int(input())
w = list(map(int, input().split()))
i = 0
j = n - 1
s1 = w[i]
s2 = w[j]

while j - i > 1:
    if s1 < s2:
        i += 1
        s1 += w[i]
    else:
        j -= 1
        s2 += w[j]

print(abs(s1 - s2))


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

class Program
{
    static void Main(string[] args)
    {
        string S = Console.ReadLine();
        byte O = 0;

        switch (S)
        {
            case "SUN": O = 7; break;
            case "MON": O = 6; break;
            case "TUE": O = 5; break;
            case "WED": O = 4; break;
            case "THU": O = 3; break;
            case "FRI": O = 2; break;
            case "SAT": O = 1; break;
        }
        Console.WriteLine(O);
    }
}


Measured memory_bytes: 11104
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std ;
#define int                 long long
#define ull                 unsigned long long int
#define ld                  long double
#define vi                  vector<int>
#define vii                 vector<pair<int,int>>
#define vvi                 vector<vector<int>>
#define pii                 pair<int,int>
#define pb                  push_back
#define prec(x)             fixed<<setprecision(15)<<x
#define all(x)              x.begin(),x.end()
#define rall(x)             x.rbegin(),x.rend()
#define rev(x)              reverse(x.begin(),x.end())
#define mset(a,b)           memset(a,b,sizeof(a))
#define mcpy(a,b)           memcpy(a,b,sizeof(a))
#define fo0(i,n)            for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n)            for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b)           for(int i=a,i##end=b;i<=i##end;i++)
#define foe(i,x)            for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)            for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)
#define mk(arr,n,type)      type *arr=new type[n];
#define dbg(x) cerr << #x << " is " << x << endl;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
clock_t beg = clock();
const int inf=1e18;const int mod=1e9+7;const int N=2e5+9;
const double pi = 3.1415926535897932384626433;
void FILE_IO(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}

void JH(){
    int d=0,e=0,f=0,g=0,p=0,w=0,flag=0,ans=0,res=0,cnt=0,sum=0;double f1=0.0,f2=0.0,f3=0.0;
    string s;cin>>s;
    fo0(i,s.length()){
        int res=s[i]-'0';
        sum=(sum+res)%9;

    }
    if(sum==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}

int32_t main()
{
    FILE_IO();FAST_IO;int t=1;
    // cin>>t;
    while(t--){JH();}cerr<<fixed<<setprecision(3)<<(double)(clock()-beg)/1000<<"s ";
}

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

int main()
{
    int n; cin>>n;
    char ch[n];
    scanf("%s", ch,n);
    
    int ans = n;
    for(int i=1;i<n;++i){
        if(ch[i]==ch[i-1])ans-=1;
    }

	cout<<ans<<endl;

}

Measured memory_bytes: 384
s = input()

ans = 0
def dfs(s,f=0):
  global ans
  for i in range(len(s)):
    if i == 0:
      ans += int(s)
    else:
      ans += int(s[:i]) + f
      dfs(s[i:],int(s[:i])+f)
  return ans

print(dfs(s))

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

// #define DEBUG
#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

int H, W, h, w;

int count_use(int i, int j){
    return min(i+1, H-i) * min(j+1, W-j);
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> H >> W >> h >> w;

    if(H % h == 0 && W % w == 0){
        cout << "No" << endl;
        return 0;
    }

    ll ans[H][W];
    ll a = (10e8-1)/(h*w-1);
    rep(H){
        repp(j, W){
            if((i+1)%h == 0 && (j+1)%w == 0){
                ans[i][j] = -a*(h*w-1)-1;
            }else{
                ans[i][j] = a;
            }
        }
    }

    cout << "Yes" << endl;
    rep(H){
        repp(j, W) cout << ans[i][j] << " ";
        cout << endl;
    }
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; 
int main(void){
    
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
    			cin >> A.at(i);
  	}
  	
  	int counter =0; // 今までBに書き込まれたマス目の数
  	vector<ll> B(N);
  	
  	for(int i=0; i<N; i++){
  	    if( i ==0 ){
  	        B.at(0)= A.at(0);
  	        counter =1; 
  	    }else if(B.at(counter-1) >= A.at(i) ){
  	           B.at(counter) = A.at(i); 
  	           counter++; 
  	    }else{
  	    // メインループ    
  	      int a = A.at(i); 
  	      int left = 0;
  	      int right = counter-1; 
  	      while(right - left > 1){
  	        int pointer = (left + right)/2;
  	        if( a > B.at(pointer) ){
  	            right = pointer; 
  	        }else{
  	            left = pointer; 
  	        } 
  	      }
  	      if(a>B.at(0)){
  	          B.at(0) = a;
  	      }else{
  	        B.at(right) = a;
  	      }
  	    }
  	    
  	}
  	
/*  	for(int i=0; i<N; i++){
  	    cout<< B.at(i) << endl; 
  	}
*/
  	cout<< counter << endl; 

}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define mx 1000000000000000000
#define ll long long int
//ll a[40001000];
//ll number[20],used[20];
int main()
{
   //char s[100],t[100],u[100];
   string s,t,u;
   ll x,y;
   cin >> s >> t;
   cin >> x >> y;
   cin >> u;
   ll count =0;
   for(ll i=0;i<s.size();i++)
   {
       if(s[i]==u[i])
        count =0;
       else
       {
           count =1;
           break;
       }
   }
   if(count ==0)
    cout << x-1 << " " << y << endl;
   else
    cout << x << " " << y-1 << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
	// ABC161-D, 1045, 
	ll k;
	cin >> k;
	queue<ll> que;
	for (int i = 1; i < 10; ++i) que.push(i);
	ll c = 0;
	ll ans = 0;
	while (c != k) {
		ans = que.front(); que.pop();
		if (ans % 10 != 0) {
			que.push(ans*ll(10) + ans % ll(10) - ll(1));
		}
		que.push(ans*ll(10) + ans % ll(10));
		if (ans % 10 != 9) {
			que.push(ans*ll(10) + ans % ll(10) + ll(1));
		}
		c++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5088
#include<bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    bool flag = true;
    int ans = 10000;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if(a % 2 == 1) {
            flag = false;
            break;
        }
        int binary = 0;
        while(a % 2 == 0) {
            binary++;
            a /= 2;
        }
        ans = min(ans, binary);
    }
    if(flag) cout << ans << endl;
    else cout << 0 << endl;
}

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

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

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

	cout << number << endl;
}


Measured memory_bytes: 256