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

int main() {
	ll n, k;
    cin >> n >> k;
    ll w[n], d[n];
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> d[i];
    }

    ll lb = 0, rb = 2e18;
    while(rb - lb > 1) {
        ll mid = lb + (rb - lb) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; ++i) {
            if(w[i] > mid) continue;
            ll num = (mid - w[i]) / d[i];
            num++;
            cnt += num;
        }
        if(cnt < k) lb = mid;
        else rb = mid;
    }
    cout << rb << endl;
}



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


p=10**9+7

fuct=[1]
for i in range(2000):
  fuct.append((fuct[i]*(i+1))%p)

for i in range(1,min(k,n-k+1)+1):
  Ca=(fuct[k-1]*pow(fuct[i-1],p-2,p)*pow(fuct[k-i],p-2,p))%p
  Cb=(fuct[n-k+1]*pow(fuct[i],p-2,p)*pow(fuct[n-k+1-i],p-2,p))%p
  print((Ca*Cb)%p)
for i in range(min(k,n-k+1)+1,k+1):
  print(0)

Measured memory_bytes: 9264
#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) a^=b^=a^=b
#define lb(x) ((x)&(-(x)))
#define inf 0x3f3f3f3f
#define N 500010
using namespace std;
typedef long long ll;
int main(){
	int n,mi=0x3f3f3f,mx=0;
	cin>>n;
	for(int i=1,a;i<=n;i++)cin>>a,mi=min(mi,a),mx=max(mx,a);
	cout<<mx-mi;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int p[1001];
vector<int> pos;
int max(int a,int b){return a>b?a:b;}
int main(){
	int n,m;
	int i,j;
	while(1){
	scanf("%d %d",&n,&m);
	if(n==0)return 0;
	pos.clear();
	p[0]=0;
	for(i=1;i<=n;i++)scanf("%d",&p[i]);
	for(i=0;i<=n;i++){
		for(j=i;j<=n;j++)pos.push_back(p[i]+p[j]);
	}
	sort(pos.begin(),pos.end());
	int ans=0;
	for(i=0;i<=n;i++){
		for(j=i;j<=n;j++){
			int best=m-p[i]-p[j];
			int x=lower_bound(pos.begin(),pos.end(),best+1)-pos.begin();
			if(x==0)continue;
			ans=max(ans,p[i]+p[j]+pos[x-1]);
		}
	}
	printf("%d\n",ans);
	}
}

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

using namespace std;

#define endl "\n"
#define F first
#define S second
#define PB push_back
#define int long long

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;

const int maxn = 1e5;
const int OO = 1e18;
const int mod = 1e9 + 7;
const int maxp = 60;

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

//	freopen("name.in","r",stdin);
//	freopen("name.out","w",stdout);

    int n,k;
    cin >> n >> k;
    int a[n+1][maxp];
    memset(a,-1,sizeof(a));

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

    for(int i=1;i<maxp;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[j][i-1] != -1)
            a[j][i] = a[a[j][i-1]][i-1];
        }
    }
    int y = 1;
    for(int i=0;i<maxp;i++)
    {

        if(k & (1LL<<i))
        {
            y = a[y][i];
        }
    }

    cout << y;
	return 0;
}


Measured memory_bytes: 97340
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> given(n);
    for(int i=0;i<n;i++)
        cin>>given.at(i);
    vector<int> sorted(given);
    sort(sorted.begin(),sorted.end());
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(given.at(i)!=sorted.at(i))
            count++;
    }
    if(count > 2)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl;
    return 0;

}


Measured memory_bytes: 3588
#include<algorithm>
#include<cstdio>
#include<queue>
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;

inline int read(){
	int fl=1,sum=0;char w=getchar();
	while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}
	while(w>='0'&&w<='9'){sum=(sum*10)+(w^48);w=getchar();}
	return fl*sum;
}
const int N=100010;
int n,now,ans,cnt;
int fa[N];
struct nod{
	int num,id;
}a[N],b[N];
bool cmp(nod x,nod y){return x.num<y.num;}
bool cmp2(nod x,nod y){return x.id<y.id;}
bool vis[N],fl;
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);}
int main()
{
	//freopen("duliu.in","r",stdin);
	//freopen("duliu.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i].num=read(),a[n+1].num=a[n+1].num^a[i].num,a[i].id=i;
	for(int j=1;j<=n;j++)b[j].num=read(),b[n+1].num=b[n+1].num^b[j].num,b[j].id=j;
	n++;now=-1;a[n].id=b[n].id=n;
	sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{;
		if(a[i].num!=b[i].num){fl=1;break;}
		if(a[i].num!=now)
		{
			now=a[i].num;
			a[i].num=b[i].num=++cnt;
		}else a[i].num=b[i].num=cnt;
	}
	if(fl){printf("-1\n");return 0;}
	sort(a+1,a+n+1,cmp2);sort(b+1,b+n+1,cmp2);
	for(int i=1;i<=cnt;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		if(b[i].num!=a[i].num||i==n){
			if(i!=n)ans++;
			fa[find(b[i].num)]=find(a[i].num);
			vis[a[i].num]=1;vis[b[i].num]=1;
		}
	}
	for(int i=1;i<=cnt;i++)if(vis[i]&&fa[i]==i)ans++;
	ans--;cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2304
while True:
    m, f, r = [int(i) for i in input().split()]

    if m == f == r == -1:
        break

    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')

    elif total < 50 and r < 50:
        print('D')

    elif total < 65:
        print('C')
        
    elif total < 80:
        print('B')
        
    else:
        print('A')
        

Measured memory_bytes: 7716
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> acc_a(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> acc_a[i];
        if (i > 0)
            acc_a[i] += acc_a[i-1];
    }
    vector<ll> acc_b(m, 0);
    for(int i = 0; i < m; i++) {
        cin >> acc_b[i];
        if (i > 0)
            acc_b[i] += acc_b[i-1];
    }
    
    auto it = upper_bound(acc_a.begin(), acc_a.end(), k);
    ll a_most = distance(acc_a.begin(), it);
    ll ans = a_most;
    for(ll i = a_most-1; i >= 0; i--) {
        ll remain = k - acc_a[i];
        auto it2 = upper_bound(acc_b.begin(), acc_b.end(), remain);
        ll b_cnt = distance(acc_b.begin(), it2);
        ans = max(ans, i+1+b_cnt);
    }
    it = upper_bound(acc_b.begin(), acc_b.end(), k);
    ll b_most = distance(acc_b.begin(), it);
    ans = max(ans, b_most);
    cout << ans << endl;
    return 0;
}


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

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

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


int main() {
	//cin.tie(0); ios_base::sync_with_stdio(false);
	string s;
	cin >>s;
	
	string cc[] ={"SUN","MON","TUE","WED","THU","FRI","SAT"}; 
	int rdy =-1, ans;
	rep(i, 7) if(cc[i]==s) rdy=i;
	if(rdy==0) ans = 7;
	else ans = 7 - rdy;
	cout << ans <<"\n";
	return 0;
}


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

using namespace std;

typedef long long 		ll;
typedef vector<ll> 		vll;
typedef pair<ll,ll> 	pll;
typedef vector<pll> 	vpll;
typedef vector<int> 	vi;
typedef pair<int,int> 	pii;
typedef vector<pii> 	vpii;

#define fi				first
#define se 				second
#define pb 				push_back
#define mp 				make_pair
#define all(v)			v.begin(),v.end()
#define sz(v)			s.size()
#define rep(i,a,b) 		for(int i=a;i<=b;i++)
#define per(i,a,b) 		for(int i=a;i>=b;i--)
#define fill(a,v)		memset(a,v,sizeof(a))
#define tc				int T;cin>>T;while(T--)
#define nl				printf("\n")
#define aya				printf("yaha aya\n")
#define debug(x,y)		printf("%d %d\n",x,y)
#define fast_io			ios_base::sync_with_stdio(false);cin.tie(NULL);
#define grt				greater<int>()

const int mod = 1e9+7;
const int mod2= 1e9+9;

inline int pow_(ll a, int n, int p=mod){
	int r=1;while(n){if(n&1)r=r*a%p;n>>=1;a=a*a%p;}return r;
}

int main(void)
{
	int R,G,B,N;cin>>R>>G>>B>>N;
	int ans = 0;
	rep(i,0,N)
		rep(j,0,N)
		{
			// i*R + j*G
			int rem = N - i*R - j*G;
			if(rem >=0 and rem%B == 0) ans++;
		}
	cout<<ans<<"\n";
}

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

int main(){
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    int ans=0;
    if(k<=a)cout<<k<<endl;
    else if(k>a&&k<=a+b)cout<<a<<endl;
    else cout<<a-(k-(a+b))<<endl;
    return 0;
}

Measured memory_bytes: 3636
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h = sorted(h)

ans = 10 ** 9
for j in range(n-k+1):
    if h[j+k-1] - h[j] < ans:
        ans = h[j+k-1] - h[j]

print(ans)



    







        



Measured memory_bytes: 8280
sx, sy, tx, ty = gets.split.map(&:to_i)

print [
  "U"*(ty-sy),
  "R"*(tx-sx),
  "D"*(ty-sy),
  "L"*(tx-sx+1),

  "U"*(ty-sy+1),
  "R"*(tx-sx+1),
  "DR",
  "D"*(ty-sy+1),
  "L"*(tx-sx+1),
  "U"
].join

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

const int mod = 1000000007;
int arr[100010];
int fac[100010];
int caf[100010];

int ipow(int x, int y)
{
    if(y == 0)
        return 1;
    if(y % 2)
        return 1LL * ipow(x, y - 1) * x % mod;
    int t = ipow(x, y / 2);
    return 1LL * t * t % mod;
}

int inv(int x)
{
    assert(x != 0);
    return ipow(x, mod - 2);
}

int ncr(int n, int r)
{
    if(r < 0 || r > n)
        return 0;
    return 1LL * fac[n] * caf[r] % mod * caf[n - r] % mod;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    fac[0] = 1;
    for(int i = 1; i <= n; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;

    for(int i = 0; i <= n; i++)
        caf[i] = inv(fac[i]);

    sort(arr, arr + n);

    int r = 0;
    for(int i = k - 1; i < n; i++)
        r = (r + 1LL * ncr(i, k - 1) * arr[i]) % mod;

    for(int i = 0; i < n - k + 1; i++)
        r = (r - 1LL * ncr(n - i - 1, k - 1) * arr[i]) % mod;

    r = (r % mod + mod) % mod;
    printf("%d\n", r);
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>

using namespace std;

int main(void) {
	int a[5],  d,p=9,b,sum=0,q;
	double c ;

	for (int i = 0; i < 5; i++) {
		cin >> a[i];
		d = 0;
		d = a[i] % 10;
		if (d <= p&&d!=0) {
			p = d;
			b = i;
		}
	}

	for (int j = 0; j < 5; j++) {
		if (b != j) {
			if (a[j] % 10 == 0) {
				sum= sum+a[j];
			}
			else {
				c = a[j];
				q = (int)((c + 9) / 10)*10;
				sum = sum+q;
				q = 0;
			}
			
		}

	}

	sum =sum +a[b];
	
	cout << sum << endl;

	return 0;


}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

const int INF = 1e9;
const long long LINF = 1e18;

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

    map<string, int> m;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        ++m[s];
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        string s;
        cin >> s;
        --m[s];
    }

    int ans = 0;
    for (map<string, int>::iterator itr = m.begin(); itr != m.end(); ++itr) {
        ans = max(ans, itr->second);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())


n=int(input())
ar=[]
for i in range(n):
    a,b=sep()
    if a==b:
        ar.append(1)
    else:
        ar.append(0)


for i in range(2,n):
    if ar[i]==1 and ar[i-1]==1 and ar[i-2]==1:
        print("Yes")
        quit()
print("No")



Measured memory_bytes: 62652
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <numeric>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const int mod = 1000000007;
const ll MOD = 1000000007;
const ll INF = 1LL << 60;
#define PI (acos(-1))

struct BIT
{
    int n;
    vector<int> bit;
    BIT()
    {
        init();
    }
    BIT(int n) : n(n)
    {
        init();
    }
    void init()
    {
        bit.clear();
        bit.resize(n + 1, 0);
    }
    int sum(int i)
    {
        int s = 0;
        while (i > 0)
        {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    int sum(int x, int y)
    {
        return sum(y) - sum(x - 1);
    }
    void add(int i, int x)
    {
        while (i <= n)
        {
            bit[i] += x;
            i += i & -i;
        }
    }
    int lower_bound(int w)
    {
        if (w <= 0)
            return 0;
        int x = 0, r = 1;
        while (r < n)
            r <<= 1;
        for (int k = r; k > 0; k >>= 1)
        {
            if (x + k <= n && bit[x + k] < w)
            {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

vector<ll> compress(vector<ll> r){
    //1-indexed
    set<ll> se;
    for (int i = 0; i < r.size(); i++)
    {
        se.insert(r[i]);
    }

    map<ll, ll> m;
    ll cnt = 1;
    for (auto t : se)
    {
        m[t] = cnt;
        cnt++;
    }

    for (int i = 0; i < r.size(); i++)
    {
        r[i] = m[r[i]];
    }

    return r;
}


//全てのa[i]からkを引くと非負の部分列を数え上げる問題になる
//これは累積和をとって、転倒（してない）数を数え上げるとできる。
//a[i]は大きいので座標圧縮が必要

ll a[202020];
int solve()
{
    ll n, k;
    cin >> n >> k;
    BIT bit(n);
    vector<ll> r(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i] -= k;
    }
    r[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        r[i] = r[i - 1] + a[i];
    }

    ll ans = 0;
    vector<ll> v = compress(r);
    for (int i = 0; i < n; i++)
    {
        if(r[i] >= 0)
            ans++;
        ans += bit.sum(v[i]);
        bit.add(v[i], 1);
    }
    cout << ans << endl;

    return 0;
}

int main()
{
    //cout.precision(10)
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();
}

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

signed main(){
    string s;
    cin >> s;
    if(s == "Sunny") cout << "Cloudy\n";
    if(s == "Cloudy") cout << "Rainy\n";
    if(s == "Rainy") cout << "Sunny\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

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

    int n, m;
    cin>>n>>m;

    vector<vector<LP>> vs(n);
    rep(i, m) {
        ll p, y;
        cin>>p>>y; p--;
        vs[p].emplace_back(LP(y, i));
    }
    rep(i, n) {
        sort(vs[i].begin(), vs[i].end());
    }
    vector<ll> ans(m);
    rep(i, n) {
        rep(j, vs[i].size()) {
            ans[vs[i][j].second] = (ll)(i + 1) * 1000000 + j + 1;
        }
    }
    rep(i, m) {
        printf("%012lld\n", ans[i]);
    }
}

Measured memory_bytes: 7808
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    c = ac = 0
    for v in a:
        c += v
        if v == 0:
            ac += c // 2
            c = 0
    print(ac + c // 2)


if __name__ == '__main__':
    solve()


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

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
 
typedef long long i64;
typedef char str255[256];

#define BIG_PRIME 1'000'000'007
#define BP_remainder(x) ((x) % BIG_PRIME)

const int INF = 1 << 30;
const int INF_NEG = INF * -1;
const i64 INF_LONG = 1LL << 62;
const i64 INF_LONG_NEG = INF_LONG * -1;

int main()
{
    i64 N; cin >> N;
    vector<i64> A(N+9);
    vector<i64> pointer(4*100010, -1);
    vector<i64> count(4*100010, 0);
    i64 next_pointer = 0;
    rep(i, N){
        i64 tmp;
        cin >> tmp;
        A[i] = tmp;
        if (pointer[tmp] == -1) { pointer[tmp] = next_pointer; ++count[pointer[tmp]]; ++next_pointer; }
        else ++count[pointer[tmp]];
    }
    i64 total = 0;
    rep(j, next_pointer){
        total += (count[j] * (count[j] - 1)) / 2;
    }
    rep(k, N){
        i64 num = A[k];
        i64 cnt = count[pointer[num]];
        i64 ans = total - (cnt - 1);
        cout << ans << endl;
    }

    return 0;
}


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

int main () {
  long long x;
  cin >> x;
  if (x % 11 == 0){
    cout << (x/11)*2 << endl;
  }
  else if (x % 11 <= 6){
    cout << (x/11)*2 + 1 << endl;
  }
  else {
    cout << (x/11)*2 + 2 << endl;
  }
}
  
    
  

Measured memory_bytes: 3628
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <queue>
#include <stdarg.h>
#include <map>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <numeric>
#include <set>

#define ll long long

using namespace std;

void
solve() {
  int n;
  cin>>n;

  vector<pair<int, int>> up;
  vector<pair<int, int>> down;
  string s;
  int total = 0;
  for (int i=0; i<n; i++) {
    cin>>s;

    int bottom = 0;
    int change = 0;
    for (auto & c : s) {
      if (c == '(')
        change++;
      else
        change--;

      bottom = min(bottom, change);
    }

    if (change >= 0)
      up.push_back({bottom, change});
    else
      down.push_back({bottom-change, -change});
    total += change;
  }

  bool valid = true;
  int now = 0;
  sort(up.begin(), up.end());
  for (int i=up.size()-1; i>=0; i--) {
    if (up[i].first + now >= 0)
      now += up[i].second;
    else {
      valid = false;
      break;
    }
  }

  if (valid) {
    now = 0;
    sort(down.begin(), down.end());
    for (int i = down.size()-1; i>=0; i--) {
      if (down[i].first + now >= 0)
        now += down[i].second;
      else {
        valid = false;
        break;
      }
    }
  }

  if (valid && total == 0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

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

  int t = 1;
  //cin>>t;

  while (t > 0) {
    t--;
    solve();
  }

  return 0;
}




Measured memory_bytes: 11272
/**
 *    author:  FromDihPout
 *    created: 2020-05-26
**/

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


long long kill(long long health) {
    if (health == 1) {
        return 1;
    }
    return 1 + kill(health / 2) * 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long h;
    cin >> h;
    cout << kill(h) << '\n';
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, m, a, b;

char s[1000][1005];

int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    forn(i, n) forn(j, m) {
        s[i][j] = '.';
    }
    forn(i, n) s[i][m] = '\0';
    if (m % 2 == 1) {
        for (int i = 0; i + 1 < n; i += 2) {
            if (b == 0) continue;
            --b;
            s[i][m - 1] = '^';
            s[i + 1][m - 1] = 'v';
        }
    }
    if (n % 2 == 1) {
        for (int i = m % 2; i + 1 < m; i += 2) {
            if (a == 0) continue;
            --a;
            s[n - 1][i] = '<';
            s[n - 1][i + 1] = '>';
        }
    }
    if (n > 1 && m > 1 && n % 2 == 1 && m % 2 == 1 && a % 2 == 1 && b % 2 == 1) {
        s[n - 2][0] = '^';
        s[n - 1][0] = 'v';
        s[n - 3][0] = '<';
        s[n - 3][1] = '>';
        --a;
        --b;
    }
    for (int i = 0; i + 1 < n; i += 2) {
        for (int j = 0; j + 1 < m; j += 2) {
            if (s[i][j] != '.' || s[i][j + 1] != '.') continue;
            if (s[i + 1][j] != '.' || s[i + 1][j + 1] != '.') continue;
            if (a > 0) {
                s[i][j] = '<';
                s[i][j + 1] = '>';
                if (--a > 0) {
                    s[i + 1][j] = '<';
                    s[i + 1][j + 1] = '>';
                    --a;
                }
            } else if (b > 0) {
                s[i][j] = '^';
                s[i + 1][j] = 'v';
                if (--b > 0) {
                    s[i][j + 1] = '^';
                    s[i + 1][j + 1] = 'v';
                    --b;
                }
            }
        }
    }
    if (a > 0 || b > 0) {
        puts("NO");
        return 0;
    }
    puts("YES");
    forn(i, n) printf("%s\n", s[i]);
    return 0;
}


Measured memory_bytes: 2176
import java.util.Scanner;

public class Main {

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

		if (a == b && b == c && a % 2 == 0) {
			System.out.println(-1);
			return;
		}

		int ans = 0;
		while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0 ) {
			int x = a;
			int y = b;
			int z = c;
			a = y / 2 + z / 2;
			b = x / 2 + z / 2;
			c = x / 2 + y / 2;
			ans++;
		}

		System.out.println(ans);

		sc.close();
	}

}


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

using namespace std;

int main(){
    string s; cin >> s;
    while(3 < s.size()){
        int f = s.size();
        for(int i=1; i < s.size()-3; i++){
            string mew = s.substr(i, 3);
            if(mew == "mew") s = s.substr(0, i) + s.substr(i+3);
        }
        if(f == s.size()) break;
    }
    cout << (s=="mew"?"Cat":"Rabbit") << endl;
}

Measured memory_bytes: 1200
#include<cstdio>
#include<string.h>
using namespace std;

int main() {
  int people,need;
  int pmeet[100];
  while(scanf("%d %d", &people, &need), people||need) {
    memset(pmeet, 0, sizeof(pmeet));
    int k,t;
    for(int j=0; j<people; ++j) {
      scanf("%d", &k);
      for(int i=0; i<k; ++i) {
	scanf("%d ", &t);
	pmeet[t-1]++;
      }
    }

    int maxday = 0,maxpeople = 0;
    bool flag = false;
    for(int i=0; i<100; ++i)
      if(pmeet[i] >= need)
	if(pmeet[i] > maxpeople) {
	  maxpeople = pmeet[i];
	  maxday = i+1;
	}
	printf("%d\n",maxday);
  }
}

Measured memory_bytes: 0
//OPTIMIZATONS
#pragma GCC optimize("02")
//CODE
#include<bits/stdc++.h>
#define int long long
#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

const int inf = 1e17 + 7;
const int MOD = 1e7 + 9;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n,k;
	cin>>n>>k;
	int ans = min(n%k,(k-(n%k)));
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
def main(A,N):
    A = [0] + A
    for a in range(N-1,0,-1):
        #print(inds[ind::ind+1])
        if sum(A[a::a]) %2== 0:
            A[a] = 0
        else:
            A[a] = 1
        
    res = [x for x in range(0,N+1) if A[x]]
    print(len(res))
    print(*res)

N = int(input())
A = [int(x) for x in input().split()]
    
main(A,N)

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

int main()
{
    string s = "Sunny" , c = "Cloudy" , r = "Rainy" , in ;
    cin >> in ;
    if(in == s)
        cout << c ;
    else if (in == c)
        cout << r ;
    else if (in == r)
        cout << s ;

    return 0;
}


Measured memory_bytes: 256
_item_num, coupon_num = gets.chomp.split(' ').map(&:to_i)
item_price_list = gets.chomp.split(' ').map(&:to_i).sort!

temp_item_list = []
coupon_num.times do |i|
  price = temp_item_list[-1].to_i >= item_price_list[-1].to_i ? temp_item_list.pop : item_price_list.pop
  discount_price = (price.to_i / 2).floor
  temp_item_list.unshift(discount_price)
end

puts (item_price_list + temp_item_list).inject(:+)

Measured memory_bytes: 10864
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> cnt(1000001);
    rep(i,n) cnt[a[i]]++;
    bool ok = true;
    repr(i,2,1000001){
        if(cnt[i] > 1) ok = false;
        int now = i;
        int cnt2 = 1;
        int cnt3 = 0;
        while(now*cnt2 <= 1000000){
            if(cnt[now*cnt2]) cnt3++;
            cnt[now*cnt3] = 0;
            cnt2++;
            if(cnt3 > 1) ok = false;
        }  
    }
    if(ok){
        cout << "pairwise coprime" << endl;
        return 0;
    }
    int now = a[0];
    rep(i,n) now = gcd(now,a[i]);
    if(now == 1){
        cout << "setwise coprime" << endl;
        return 0;
    }
    cout << "not coprime" << endl;


}



Measured memory_bytes: 11152
a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if (x == (500 * i + 100 * j + 50 * k)):
                ans += 1
print(ans)


Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.IO;

namespace Contest
{
    class Scanner
    {
        private string[] line = new string[0];
        private int index = 0;

        public string Next()
        {
            if (line.Length <= index)
            {
                line = Console.ReadLine().Split(' ');
                index = 0;
            }

            var res = line[index];
            index++;
            return res;
        }

        public int NextInt()
        {
            return int.Parse(Next());
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public string[] Array()
        {
            line = Console.ReadLine().Split(' ');
            index = line.Length;
            return line;
        }

        public int[] IntArray(int n)
        {
            var array = Array();
            var result = new int[n];
            for (int i = 0; i < n; i++)
            {
                result[i] = int.Parse(array[i]);
            }

            return result;
        }

        public int[] IntArray()
        {
            var array = Array();
            var result = new int[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = int.Parse(array[i]);
            }

            return result;
        }


        public long[] LongArray()
        {
            var array = Array();
            var result = new long[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = long.Parse(array[i]);
            }

            return result;
        }

        public uint NextUint()
        {
            return uint.Parse(Next());
        }
    }

    class Program
    {
        private int N;
        private int[] A;
        private void Scan()
        {
            var sc = new Scanner();
            N = sc.NextInt();
            A = sc.IntArray();
        }
        public void Solve()
        {
            Scan();
            Console.WriteLine(A.Sum(i => i - 1));
        }

        static void Main() => new Program().Solve();
    }
}

Measured memory_bytes: 11312
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll w, h, x, y;
    cin >> w >> h >> x >> y;
    cout << (double)w * h / 2 << ' ';
    if(x * 2 == w && y * 2 == h) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, buf, dpmod[10], dpmodbuf[10];

int main(){
	cin >> n;
	dpmod[0] = 0;
	for(ll j = 1; j <= 9; j++){dpmod[j] = -1;}
	for(ll i = 1; i <= n; i++){
		cin >> buf;
		for(ll j = 0; j <= 9; j++){dpmodbuf[j] = dpmod[j];}
		for(ll j = 0; j <= 9; j++){
			if(dpmod[j] != -1){
				dpmodbuf[(j+buf)%10] = max(dpmod[j]+buf, dpmod[(j+buf)%10]);
			}
		}
		for(ll j = 0; j <= 9; j++){dpmod[j] = dpmodbuf[j];}
		//for(ll j = 0; j <= 9; j++){cout << dpmod[j];}cout << endl;
	}
	
	ll ans = 0;
	for(ll j = 1; j <= 9; j++){ans = max(dpmod[j], ans);}
	
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int n;

void d(string s, char last, int len)
{
    if (len == n)
        cout << s << "\n";
    else
    {
        for (int i = 'a'; i <= last; i++)
            d(s + (char)i, last, len + 1);
        d(s + (char)(last + 1), last + 1, len + 1);
    }
}

int main()
{
  	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;

    d("a", 'a', 1);

	return 0;
}

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

int n;
int p[30], l[30], r[30];

void preParse(int i){
  if(i == -1) return ;

  cout << " " << i;
  if(l[i] != -1) preParse(l[i]);
  if(r[i] != -1) preParse(r[i]);
}

void inParse(int i){
  if(i == -1) return ;

  if(l[i] != -1) inParse(l[i]);
  cout << " " << i;
  if(r[i] != -1) inParse(r[i]);
}

void postParse(int i){
  if(i == -1) return ;

  if(l[i] != -1) postParse(l[i]);
  if(r[i] != -1) postParse(r[i]);
  cout << " " << i;
}

int main(){

  cin >> n;
  for(int i = 0;i < n;i++) p[i] = l[i] = r[i] = -1;
  for(int i = 0;i < n;i++){
    int id, left, right;

    cin >> id >> left >> right;
    l[id] = left;
    r[id] = right;
    p[left] = p[right] = id;
  }

  for(int i = 0;i < n;i++){
    if(p[i] == -1){
      cout << "Preorder" << endl;
      preParse(i);
      cout << endl;

      cout << "Inorder" << endl;
      inParse(i);
      cout << endl;

      cout << "Postorder" << endl;
      postParse(i);
      cout << endl;
    }
  }

  return 0;
}



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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long a,b,k,nb;
    cin>>a>>b>>k;
    nb=a;
    a-=min(a,k);
    if (a==0)
        b-=min(b,k-nb);
    cout<<a<<" "<<b;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   cin>>s;
    int sizestr = s.size();
    char a= s.at(sizestr-1);
    if(a != 's')
    {
        s+="s";
    }
    else
    {
        s+="es";
    }
    cout<<s;
}


Measured memory_bytes: 3628
N = int(input())
C = [int(input()) for _ in range(N)]

MOD = 10 ** 9 + 7
recent = [-1 for _ in range(max(C))]
hist = []

ans = 1
for i in range(N):
    c = C[i] - 1
    if recent[c] >= 0 and recent[c] != i-1:
        ans = (ans + hist[recent[c]]) % MOD
    recent[c] = i
    hist.append(ans)
    
print(ans)

Measured memory_bytes: 20524
#include <stdio.h>

int main(){
  int k;
  scanf("%d",&k);
  
  if(k % 2 == 0){
    printf("%d\n", (k / 2) * (k / 2));
  }else{
    printf("%d\n", (k / 2) * (k / 2 + 1));
  }
  return 0;
}

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


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

  int a, b;
  cin >> a >> b;
  if(a > b) cout << a -1 << endl;
  else cout << a << endl;

}


Measured memory_bytes: 256
#include<stdio.h>
int m,a,i,n;int main(void){while(scanf("%d",&m),m){while(!(m%2))m/=2;a=1
;for(i=3;m!=1;i+=2){n=1;while(!(m%i))m/=i,n++;a*=n;}printf("%d\n",--a);}
return 0;}

Measured memory_bytes: 600
a = list(map(int,input().split()))
h = list(map(int,input().split()))

n = a[0]
m = a[1]

all_kind = {i for i in range(1, n+1)}

for i in range(m):
    comb = list(map(int,input().split()))

    if(h[comb[0]-1] > h[comb[1]-1]):
        all_kind.discard(comb[1])
    elif(h[comb[0]-1] == h[comb[1]-1]):
        all_kind.discard(comb[0])
        all_kind.discard(comb[1])
    else:
        all_kind.discard(comb[0])

print(len(all_kind))


Measured memory_bytes: 22356
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>
#include <functional>
#include <cmath>
#include <set>
#include <map>


//マクロ
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
#define All(a) (a).begin(),(a).end()
#define RAll(a) (a).rbegin(),(a).rend()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define INFL 1e18
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
using Graph = vector<vector<int>>;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数

//使用する関数
template<class T>bool chmax(T &a, const T &b) {
	if (a < b) { a = b; return 1; }
	return 0;
}
template<class T>bool chmin(T &a, const T &b) {
	if (a > b) { a = b; return 1; }
	return 0;
}

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

	int n;
	cin >> n;

	vi c = vi(4,0);
	REP(i, n) {
		string s;
		cin >> s;
		if (s == "AC") {
			c[0]++;
		}
		else if (s == "WA") {
			c[1]++;
		}
		else if (s == "TLE") {
			c[2]++;
		}
		else {
			c[3]++;
		}
	}
	cout << "AC x " << c[0] << endl;
	cout << "WA x " << c[1] << endl;
	cout << "TLE x " << c[2] << endl;
	cout << "RE x " << c[3] << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
string s,w="keyence";
 
int main(){
	cin>>s;
	string a,b;
	for(int i=0;i<w.size();i++){
		a=s.substr(0,i+1);
		b=s.substr(s.size()-(7-i-1));
		if(a+b==w){
			cout<<"YES";
			return 0;
		} 
	}

	cout<<"NO";
	return 0;
}


Measured memory_bytes: 256
import collections

n=int(input())
a=list(map(int,input().split()))
q=int(input())

cnt_dict=collections.Counter(a)
sum=sum(a)

for i in range(q):
    b,c=map(int,input().split())
    cnt=cnt_dict[b]
    sum=sum-b*cnt+c*cnt
    cnt_dict[b]=0
    cnt_dict[c]+=cnt
    print(sum)

Measured memory_bytes: 87964
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
vector<int>v;
signed main(){
	int l,r;
	cin>>l>>r;
	for(int i=l;i<=min(r,l+4038);i++){
		v.push_back(i%2019);
	}
	int ans=2019;
	sort(all(v));
	rep(i,v.size()){
		for(int j=i+1;j<v.size();j++){
			ans=min(ans,v[i]*v[j]%2019);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAX 5000001
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
const ll INF = 10010010010001;

int main(){
    int k,tmp,res = 0;
    string s,t;
    cin >> s >> k;

    set<string> lw;
    vector<string> cg;
    ll sz = s.size();
    for(int i=0;i<sz;i++){
        for(int j=1;j<k+1;j++){
            lw.insert(s.substr(i,j));
        }
    }

    for(string a : lw) cg.push_back(a);
    sort(cg.begin(),cg.end());
    cout << cg[k-1] << endl;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	double a[1010], avg, ans;
	while(cin >> n){
		if(n==0)
			break;
		avg = ans = 0;
		for(int i=1; i<=n; i++){
			cin >> a[i];
			avg += a[i];
		}
		avg = 1.0*avg/n;
		for(int i=1; i<=n; i++)
			ans += 1.0*(avg-a[i])*(avg-a[i]);
		ans = sqrt(ans/n);
		cout << fixed << setprecision(5) << ans << endl;
	} 
	return 0;
}


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

int a[100005];

int main()
{
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n <= 2)
    {
        cout << "1\n";
        return 0;
    }

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

    for (int i = 2; i < n; i++)
    {
        int ns = a[i] - a[i - 1];

        if (sign == 0) sign = ns;
        if (sign * 1ll * ns < 0)
        {
            ++ans;
            sign = 0;
        }
    }

    cout << ans << endl;
}



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

#define IOS  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int  long long

const int N = 105;
int v[N], w[N];
int n, W;
int cache[N][100005];

int dp(int idx, int wt)
{
    if(idx == n) 
    {
        if(wt < 0) return -1e15;
        return 0;
    }
    if(wt == 0) return 0;
    if(wt < 0) return -1e15;
    int &ans = cache[idx][wt];
    if(ans != -1) return ans;
    ans = 0;
    ans = max(dp(idx + 1, wt), v[idx] + dp(idx + 1, wt - w[idx]));
    return ans;
}

int32_t main()
{   
    IOS
    cin >> n >> W;
    for (int i = 0; i < n; ++i)
    {
        cin >> w[i] >> v[i];
    }
    memset(cache, -1, sizeof(cache));
    int ans = dp(0, W);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 85672
n,k = [int(i) for i in input().split()]

s = input()

il = []

qt = 1
ilz = 0
for i in range(1,len(s)):
    if(s[i-1] == s[i]):
        qt+=1
    else:
        if(s[i-1] == '0'):
            ilz+=1
        il.append([s[i-1],qt])
        qt = 1
        
if(qt>0):
    if(s[len(s)-1] == '0'):
        ilz+=1
    il.append([s[len(s)-1],qt])

if(s.count('1') == n):
    print(n)
elif(k>=ilz):
    print(n)
else:

    l = r = 0
    so = 0
    mso = 0
    for i in range(len(il)):

        if(il[r][0] == '1'):
            so+=il[r][1]
        elif(k>0):
            so+=il[r][1]
            k-=1
        else:
            mso = max(mso,so)
            
            while l<len(il) and il[l][0]!='0':
                so -= il[l][1]
                l+=1
            if(l<len(il)):
                so -= il[l][1]
                l+=1
            
            so+=il[r][1]
            
        r+=1
    mso = max(mso,so)
    print(mso)

    



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

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

typedef long long ll;

const int INF = 1e9;

int main(){
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  REP(i,N) cin >> w[i] >> v[i];

  int w0 = w[0];
  REP(i,N) w[i] -= w0;

  vector<vector<vector<int>>> dp(N + 1, vector<vector<int>> (3 * N + 1, vector<int> (N + 1, -INF)));
  dp[0][0][0] = 0;
  REP(i,N)REP(j, 3 * N + 1)REP(k,N + 1) {
    if(dp[i][j][k] == -INF) continue;
    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
    if(j + w[i] <= 3 * N && k + 1 <= N) {
      dp[i + 1][j + w[i]][k + 1] = max(dp[i + 1][j + w[i]][k + 1], dp[i][j][k] + v[i]);
    }
  }

  int res = 0;
  REP(i, N + 1) {
    for(int j = 0; (j <= 3 * N) && (j <= (ll)W - (ll)w0 * i); ++j) {
      res = max(res, dp[N][j][i]);
    }
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 13440
# abc139_a.py
# https://atcoder.jp/contests/abc139/tasks/abc139_a

# A - Tenki /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 100点

# 問題文
# ある 3日間の天気予報が、長さ 3 の文字列 Sとして与えられます。
# Sの i (1≤i≤3) 文字目が S のとき、i日目の天気予報が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
# また 3日間の実際の天気が、長さ 3 の文字列 Tとして与えられます。
# Tの i (1≤i≤3) 文字目が S のとき、i日目の実際の天気が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
# 3日間で天気予報が的中した日が何日あるかを出力してください。

# 制約
#     Sおよび T は長さ 3の文字列である。
#     Sおよび Tは S, C, R のみからなる。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# S
# T

# 出力
# 3日間で天気予報が的中した日が何日あるかを出力せよ。

# 入力例 1
# CSS
# CSR

# 出力例 1
# 2

#     1日目の天気予報は曇り、実際の天気は曇りなので、この日の天気予報は的中している。
#     2日目の天気予報は晴れ、実際の天気は晴れなので、この日の天気予報は的中している。
#     3日目の天気予報は晴れ、実際の天気は雨なので、この日の天気予報は的中していない。

# 以上より、このケースでは 3日間で天気予報が的中した日が 2日あります。

# 入力例 2
# SSR
# SSR

# 出力例 2
# 3

# 入力例 3
# RRR
# SSS

# 出力例 3
# 0


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    S = lines[0]
    T = lines[1]
    # N = int(lines[0])
    # X, A = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    result = 0

    for s, t in zip(S, T):
        if s == t:
            result += 1

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['CSS', 'CSR']
        lines_export = [2]
    if pattern == 2:
        lines_input = ['SSR', 'SSR']
        lines_export = [3]
    if pattern == 3:
        lines_input = ['RRR', 'SSS']
        lines_export = [0]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9144
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q;
	vector<int> A(2 * N), B(2 * N);
	for (int i = 0; i < 2 * N; ++i) cin >> A[i];
	for (int i = 0; i < 2 * N; ++i) cin >> B[i];
	long long sum = 0;
	vector<int> diff(2 * N);
	int bcnt = 0;
	for (int i = 0; i < 2 * N; ++i) {
		if (i == 0 || i == 2 * N - 1) {
			sum += A[i];
		}
		else {
			sum += max(A[i], B[i]);
			diff[i] = abs(A[i] - B[i]);
			if (A[i] < B[i]) bcnt ^= 1;
		}
	}
	priority_queue<pair<int, int> > que;
	for (int i = 1; i < 2 * N - 1; ++i) {
		que.push(make_pair(-diff[i], i));
	}
	for (int i = 0; i < Q; ++i) {
		int P, X, Y;
		cin >> P >> X >> Y; --P;
		if (P == 0 || P == 2 * N - 1) {
			sum -= A[P];
			A[P] = X;
			B[P] = Y;
			sum += A[P];
		}
		else {
			sum -= max(A[P], B[P]);
			if (A[P] < B[P]) bcnt ^= 1;
			A[P] = X;
			B[P] = Y;
			diff[P] = abs(A[P] - B[P]);
			sum += max(A[P], B[P]);
			if (A[P] < B[P]) bcnt ^= 1;
			que.push(make_pair(-diff[P], P));
		}
		long long ans = sum;
		if (bcnt == 1) {
			while (diff[que.top().second] != -que.top().first) {
				que.pop();
			}
			ans += que.top().first;
		}
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 8048
N = int(input()) 
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

manzokudo = 0
before = A[0]
for i in range(N):
	manzokudo += B[A[i]-1]
	if A[i] - before == 1:
		manzokudo += C[A[i]-2]
	before = A[i]

print(manzokudo)
	


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll a[4020],b[2020][2020];
int main(){
	ll n,x;
	cin>>n>>x;
	ll ans=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		ans+=a[i];
	}
	for(int i=n;i<2*n;i++)a[i]=a[i-n];
	for(int i=0;i<n;i++)b[0][i]=a[i];
	for(int i=1;i<n;i++){
		ll sum=x*i;
		for(int j=0;j<n;j++){
			b[i][j]=min(b[i-1][j],a[j+i]);
			sum+=b[i][j];
		}
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 35168
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
//priority_queue<int, vector<int>, greater<int> > pq;
const int N = 300030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =  1e9+7;
int n,m,a,b;
bool vis[100003];
vector<int>v[100003],path,path2;
void dfs(int x)
{
    vis[x]=1;
    path.push_back(x);
  	for(int i=0;i<v[x].size();i++)
		if(!vis[v[x][i]])
		{
			dfs(v[x][i]);
			return ;
		}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
rep(i,0,m)
{
    cin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);
}
dfs(1);
swap(path,path2);
dfs(1);
cout<<path2.size()+path.size()-1<<endl;
for(int i=path2.size()-1;i>0;i--)
    cout<<path2[i]<<' ';
    for(int i=0;i<path.size();i++)
        cout<<path[i]<<' ';
}







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

// 小数点以下桁数
// fixed << setprecision(i)

int gcd(int a,int b){return (a%b==0?b:gcd(b, a%b));}
int lcm(int a,int b){return a*b/gcd(a, b);}

int main()
{
  int n, k, ans = 0;
  vector<int> p(1000);

  cin >> n >> k;
  for (int i = 0; i < n; i++)
    cin >> p[i];
  sort(p.begin(), p.begin() + n);
  for (int i = 0; i < k; i++)
    ans += p[i];
  cout << ans << endl;
}

Measured memory_bytes: 3632