akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{
    class Point
    {
        public bool move = false;
        public int next_num = 0;
    }
    

    class Program
    {
        

        static void Main(string[] args)
        {
            
            
            while (true)
            {

               
                string[] input = Console.ReadLine().Split(' ');
                int num_h = int.Parse(input[0]);
                int num_w = int.Parse(input[1]);
                int start_num = int.Parse(input[2]);

                if(num_h == 0 && num_w == 0 && start_num == 0)
                {
                    break;
                }

                start_num--;  //0スタート配列用

                Point[,] amida = new Point[1001, num_h];

                for(int i = 0; i < 1001; i++)
                {
                    for(int j = 0; j < num_h; j++)
                    {
                        amida[i, j] = new Point();
                    }
                }

                //横線を引く
                for(int i = 0; i < num_w; i++)
                {
                    input = Console.ReadLine().Split(' ');
                    int h = int.Parse(input[0]) - 1;
                    int p = int.Parse(input[1]) - 1;
                    int q = int.Parse(input[2]) - 1;

                    amida[h, p].move = true;
                    amida[h, p].next_num = q;
                    amida[h, q].move = true;
                    amida[h, q].next_num = p;
                }            
                 
                //start_numから調べる
                int now_num = start_num;
                for(int i = 1000; i >= 0; i--)
                {
                    if(amida[i, now_num].move)
                    {
                        now_num = amida[i, now_num].next_num;
                    }
                }

                now_num++;  //1スタート出力用

                Console.WriteLine(now_num);
                

            }
            
            
        }
    }
}


Measured memory_bytes: 45052
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String x = sc.next();
        sc.close();

        // 主処理
        int result = 0;
        while (x.contains("ST")) {
            String[] array = x.replace("TS", "T,S").split(",");
            List<String> list = new ArrayList<>();
            for (String st : array) {
                int countS = st.replaceAll("[^S]", "").length();
                int countT = st.replaceAll("[^T]", "").length();
                if (countS == 0 || countT == 0) {
                    result += Math.max(countS, countT);
                } else if (countS < countT) {
                    list.add("T".repeat(countT - countS));
                } else if (countT < countS) {
                    list.add("S".repeat(countS - countT));
                }
            }
            x = String.join("", list);
        }
        result += x.length();

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 63940
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<ll, ll>;

const ll INF = 5e15;
const ll MOD = 1e9 + 7;

ld memo[310][310][310];
bool calced[310][310][310];
ll N;
ll cnt[3];

void init(){
    cin >> N;
    for(ll i = 0; i < N; i++){
        ll a;
        cin >> a;
        cnt[a - 1]++;
    }
}

ld search(ll i, ll j, ll k){
    if(!i && !j && !k) return 0;
    if(calced[i][j][k]) return memo[i][j][k];
    memo[i][j][k] = N;
    if(i) memo[i][j][k] += i * search(i - 1, j    , k    );
    if(j) memo[i][j][k] += j * search(i + 1, j - 1, k    );
    if(k) memo[i][j][k] += k * search(i    , j + 1, k - 1);
    calced[i][j][k] = 1;
    memo[i][j][k] /= (i + j + k);
    return memo[i][j][k];
}

int main(){
    init();
    printf("%.10Lf\n", search(cnt[0], cnt[1], cnt[2]));
    return 0;
}


Measured memory_bytes: 481536
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;

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 (b < a) { a = b; return 1; } return 0; }
void SWAP(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
void SWAP(int& a, int& b) { a ^= b; b ^= a; a ^= b; }


class C {
	int n;
	vi a;
public:
	C()
	{
		cin >> n;
		a.resize(n);
		REP(i, n)
			cin >> a[i];
		sort(ALL(a));
	}
	void solve()
	{
		int p{ -1 }, q{ -1 }, c{ -1 };

		REP(i, n)
		{
			if (a[i] == c)
			{
				if (p < 0)
					chmax(p, c);
				else if (q < 0)
					chmax(q, c);
				
				if (q < p)
					chmax(q, c);
				else
					chmax(p, c);

				c = -1;
			}

			else
			{
				c = a[i];
			}
		}

		if (p == -1 ||  q == -1)
			cout << 0 << endl;
		else
			cout << (ll)p* q << endl;

//		cout << p << " " << q << endl;
	}
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> P;
typedef pair<ll,pair<ll,ll>> p;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define FOR(x,to) for(x=0;x<to;x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
static const int MAX_SIZE = 1 << 17; //segment tree のサイズ。この実装では2べきにする必要がある。 2^17 ≒ 1.3 * 10^5

int N;
set<int> S[100010];
int T[110000];
vector<int> C;

int main(){
   int i,j,k,l,r,x,y;
   string s;
   cin>>N;

   FOR(i,N-1){
       cin>>x>>y;
       S[x-1].insert(y-1);
       S[y-1].insert(x-1);
   }

   FOR(i,N){
       cin>>x;
       C.push_back(x);
   }
   sort(ALL(C));
   set<P> cand;
   FOR(i,N) cand.insert({(int)S[i].size(),i});
   ll ret=0;
   FORR(c,C){
       x=cand.begin()->second;
       cand.erase(cand.begin());
       T[x]=c;
       ret+=1LL*c*S[x].size();
       FORR(s,S[x]){
           cand.erase({(int)S[s].size(),s});
           S[s].erase(x);
           cand.insert({(int)S[s].size(),s});
       }
   }
   cout<<ret<<endl;
   FOR(i,N) cout<<T[i]<<" ";
   cout<<endl;
}



Measured memory_bytes: 6528
#include <iostream>
#include <map>

using namespace std;

int main(){
    int N;
    cin >> N;
    map<int, int> mp;
    int a[100000];
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        if(mp.count(a[i]) == 0){
            mp[a[i]] = 1;
        }else{
            mp[a[i]]++;
        }
    }
    if(mp.size() == 1){
        auto p = mp.begin();
        if(p->first == 0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }else if(mp.size() == 2){
        auto p = mp.begin();
        int a = p->first;
        p++;
        int b = p->first;
        if(a > b) swap(a, b);
        if(a == 0){
            if(2*mp[a] == mp[b]){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else{
            cout << "No" << endl;
        }
    }else if(mp.size() == 3){
        auto p = mp.begin();
        int a = p->first;
        p++;
        int b = p->first;
        p++;
        int c = p->first;
        if((a == (b^c)) && (b == (c^a)) && (c == (a^b))){
            if((mp[a] == mp[b]) && (mp[b] == mp[c])){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }      
        }else{
            cout << "No" << endl;
        }
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 4224
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node{
  int key;
  struct node *right;
  struct node *left;
  struct node *parent;
};

typedef struct node *NodePointer;

NodePointer root;
NodePointer nil;

NodePointer find(NodePointer u,int k){
  while(u!=nil&&k!=u->key){
    if(k<u->key)u=u->left;
    else u=u->right;
  }
  return u;
}

void insert(int k){
  NodePointer y,x,z;
  y=nil;
  x=root;
  z=(NodePointer)malloc(sizeof(struct node));
  z->key=k;
  z->left=nil;
  z->right=nil;

  while(x!=nil){
    y=x;
    if(z->key < x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  
  if(y==nil)root=z;
  else{
    if(z->key < y->key)y->left=z;
    else y->right=z;
  }
}

void inorder(NodePointer u){
  if(u==nil)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(NodePointer u){
  if(u==nil)return;
  printf(" %d",u->key);
  preorder(u->left);  
  preorder(u->right);
}

int main(){
int n,i,x;
  char c[7];
  NodePointer t;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",c);
    if(strcmp(c,"find")==0){
      scanf("%d",&x);
      t=find(root,x);
      if(t!=nil)printf("yes\n");
      else printf("no\n");
    }
    else if(strcmp(c,"insert")==0){
      scanf("%d",&x);
      insert(x);
    }
    else if(strcmp(c,"print")==0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}



Measured memory_bytes: 20528
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  lint N, K;
  cin >> N >> K;
  vector<lint> A(N);
  lint Asum = 0;
  REP(i, N) {
    cin >> A[i];
    Asum += A[i];
  }
  vector<lint> div;
  for(lint i=1; i*i<=Asum; i++) {
    if(Asum%i == 0) {
      div.push_back(i);
      if(i != Asum/i) div.push_back(Asum/i);
    }
  }
  sort(ALL(div));
  IREP(i, div.size()) {
    vector<lint> Amod(N);
    lint Amodsum = 0;
    REP(j, N) {
      Amod[j] = A[j]%div[i];
      Amodsum += Amod[j];
    }
    if(Amodsum%div[i] != 0) continue;
    lint x = Amodsum / div[i];
    sort(ALL(Amod), greater<lint>());
    lint sum = 0;
    REP(i, x) sum += Amod[i];
    if(x*div[i] - sum <= K) {
      cout << div[i] << endl;
      return 0;
    }
  }

}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }
        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            if((a + b) % 2 == 1)
            {
                WriteLine("IMPOSSIBLE");
                return;
            }
            var k = (a + b) / 2;
            WriteLine(k);

        }
    }
    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 13268
import sys
input = sys.stdin.readline

n = int(input())
mod = 10**9+7
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

dp = [[1, 1] for _ in range(n)]
# dp[v][0]: white
# dp[v][1]: black

s = []
order = []
par = [-1]*n
s.append(0)
while s:
    v = s.pop()
    order.append(v)
    flag = True
    for u in g[v]:
        if u == par[v]:
            continue
        flag = False
        par[u] = v
        s.append(u)

order.reverse()
for v in order:
    if par[v] == -1:
        continue
    dp[par[v]][0] *= (dp[v][0]+dp[v][1])%mod
    dp[par[v]][1] *= dp[v][0]%mod
ans = dp[0][0]+dp[0][1]
#print(dp)
print(ans%mod)

Measured memory_bytes: 75312
N=int(input())
B=list(map(int,input().split()))
#print(B)

A=[0 for i in range(N)]
A[0]=B[0]
for i in range(1,N-1):
  A[i]=min(B[i-1],B[i])
A[N-1]=B[N-2]
print(sum(A))

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

using ld = long double;
using point = complex<ld>;

int main() {
    vector<point> ps(3);
    for(int i = 0; i < 3; ++i) {
        ld x, y; cin >> x >> y;
        ps[i] = point(x, y);
    }
    vector<ld> len(3);
    for(int i = 0; i < 3; ++i) {
        len[i] = abs(ps[i] - ps[(i + 1) % 3]);
    }

    const ld s = (len[0] + len[1] + len[2]) * 0.5;
    const ld S = sqrt(s * (s - len[0]) * (s - len[1]) * (s - len[2]));
    const ld inR = 2 * S / (len[0] + len[1] + len[2]);
    const ld m = *max_element(begin(len), end(len));

    cout << fixed << setprecision(12) << inR / (2 * inR / m + 1) << endl;
}


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

int main(void){
    int m, n;
    int coin[30];
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>coin[i];
    }
    
    vector<int> dp (100000,1000000);

    dp[0] = 0;

    for(int i=0;i<=n;i++){
        for(int k=0;k<m;k++){
            dp[i+coin[k]]=min(dp[i]+1,dp[i+coin[k]]);
        }
    }

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

}


Measured memory_bytes: 3112
#include<cstdio>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100005
int n,t[MAXN];
vector<int> G[MAXN];
void dfs(int u,int f)
{
	map<int,int> cnt;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==f) continue;
		dfs(v,u);
		cnt[t[v]]++;
	}
	map<int,int>::iterator it;
	for(it=cnt.begin();it!=cnt.end();it++)
		if(it->second>1)
			cnt[(it->first)+1]+=it->second-1;
	if(it!=cnt.begin())
		it--,t[u]=it->first+1;
}
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		G[i].push_back(x);
		G[x].push_back(i);
	}
	dfs(1,0);
	printf("%d\n",t[1]);
}

Measured memory_bytes: 20096
#include<iostream>
#include<stdio.h>
using namespace std;

void change(char cup[3], int ball[3]){
	char enter;
	int num;
	if(cup[0] > cup[2]){
		enter = cup[2];
		cup[2] = cup[0];
		cup[0] = enter;
	}
	num =  ball[ cup[0] - 'A' ];
	ball[ cup[0] - 'A' ] = ball[ cup[2] - 'A'];
	ball[ cup[2] - 'A'] = num;
}

int main(){
	char cup[3];
	int ball[3] = {1, 0, 0};
	int i;

	while(cin >> cup)
		change(cup, ball);
	for(i = 0; i < 3; i++){
		if(ball[i] == 1)
			printf("%c\n",'A' + i);
	}
}

Measured memory_bytes: 1124
#include<stdio.h>
#include <iomanip>
#include <iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include <random>
#include <chrono>

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


int main() {
	int k, x;
	cin >> k >> x;
	for (int i = -k + 1; i < k;i++ ) {
		cout << x + i << " ";
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define F(i,j,k,in) for(int i=j;i<k;i+=in)
#define DF(i,j,k,in) for(int i=j;i>=k;i-=in)
#define feach(it,l) for (auto it = l.begin(); it != l.end(); ++it)
#define fall(a) a.begin(),a.end()
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define eq equal_range
#define fs first
#define ss second
#define ins insert
#define mkp make_pair
#define endl "\n"
using namespace std;
typedef vector<ll> vll;
typedef vector<int> vin;
typedef vector<char> vch;
typedef vector<string> vst;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvin;
typedef vector<pair<ll,ll>> vpll;
typedef vector<pair<int,int>> vpin;
typedef set<ll> sll;
typedef set<int> sint;
typedef set<char> sch;
typedef set<string> sst;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef queue<int> qin;
typedef priority_queue<int> pqin;
typedef map<ll,ll> mpll;
typedef map<int,int> mpin;
typedef pair<ll,ll> pll;
typedef pair<int,int> pin;
const ll MOD=1000000007;
const long double PI=3.1415926535897932384626433832795;
ll pwr(ll b,ll p){ll res=1;while(p){if(p&1) {res*=b; p--;}else{b*=b; p>>=1;}}return res;}
const int maxn = 2e5;
vin adj[maxn];
bool vis [maxn];
int sz;
void dfs (int a) {
  ++sz;
  vis [a] = true;
  for (auto v  : adj[a]) if (!vis[v]) dfs (v);
}
int main()
{
ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
int n,m; cin>>n>>m;
F (i,0,m,1) {
  int a, b; cin>>a>>b;
  --a; --b;
  adj[a].pb(b); adj[b].pb(a);
}
int maxi=-1;
F (i,0,n,1) vis[i]=false;
F (i,0,n,1) {
  sz=0;
  if (!vis[i]) dfs(i);
  maxi=max (maxi , sz);
}
cout<<maxi;
return 0;
}


Measured memory_bytes: 20920
#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main(){
  priority_queue<int> PQ;
  while(1){
    string str;
    cin >> str;
    if(str=="insert"){
      int x; cin >> x;
      PQ.push(x);
    }else if(str=="extract"){
      cout << PQ.top() << endl;
      PQ.pop();
    }else if(str=="end"){
      break;
    }
  }
}

Measured memory_bytes: 7012
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read();
    let x = read();
    let l: Vec<u32> = (0..n).map(|_| read()).collect();

    let mut last = 0;
    let mut ans = 1;
    for i in 0..n {
        let d = last + l[i];
        if d <= x {
            ans += 1;
        }
        last = d;
    }

    println!("{}", ans);
}

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

using namespace std;

int main(void) {
  int r,d,x;
  int x_a = 0;
  cin >> r >> d >>x;
  
  for (int i = 0;i < 10;i++) {
    x_a = (r*x -d);
    cout << x_a << endl;
    x = x_a;
  }
}

Measured memory_bytes: 384
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	auto notPrime = new bool[](123456*2+1);
	notPrime[0] = notPrime[1] = true;
	for(int i; i < notPrime.length; ++i) {
		if(!notPrime[i]) {
			for(int j = 2; i*j < notPrime.length; ++j) {
				notPrime[i*j] = true;
			}
		}
	}

	while(true) {
		auto n = readInt();
		if(n == 0) {
			return;
		}
		int ans;
		for(int i = n+1; i <= 2*n; ++i) {
			if(!notPrime[i]) {
				++ans;
			}
		}
		writeln(ans);
	}
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

int n, m, p;
vector<vector<int>> h(7, vector<int>(7, 0));
int v[7][7][7];
int dx[] = {1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1};
int dy[] = {0, 1, 0, 1, -1, 0, 0, 1, 1, 1, 1, -1, -1};
int dz[] = {0, 0, 1, 0, 0, 1, -1, 1, -1, 1, -1, 1, -1};

bool check()
{
    bool res = false;
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            for (int z = 0; z < n; z++)
            {
                if (v[x][y][z] == -1)
                    continue;
                for (int k = 0; k < 13; k++)
                {
                    int mx = x + dx[k] * (m - 1), my = y + dy[k] * (m - 1), mz = z + dz[k] * (m - 1);
                    if (mx < 0 || n <= mx || my < 0 || n <= my || mz < 0 || n <= mz)
                        continue;
                    bool f = true;
                    for (int i = 1; i < m; i++)
                    {
                        int nx = x + dx[k] * i, ny = y + dy[k] * i, nz = z + dz[k] * i;
                        if (v[nx][ny][nz] != v[x][y][z])
                            f = false;
                    }
                    if (f)
                        res = true;
                }
            }
        }
    }
    return res;
}

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

    while (cin >> n >> m >> p, n || m || p)
    {
        for (int i = 0; i < 7; i++)
            for (int j = 0; j < 7; j++)
                h[i][j] = 0;
        for (int i = 0; i < 7; i++)
            for (int j = 0; j < 7; j++)
                for (int k = 0; k < 7; k++)
                    v[i][j][k] = -1;
        bool b = false, w = false;
        bool pass = false;
        int turn = 0;
        for (int i = 0; i < p; i++)
        {
            int x, y;
            cin >> x >> y;
            if (pass)
                continue;
            x--;
            y--;
            int z = h[x][y];
            v[x][y][z] = i % 2;
            h[x][y]++;
            if (check())
            {
                if (i % 2 == 0)
                {
                    b = true;
                    pass = true;
                    turn = i + 1;
                }
                else
                {
                    w = true;
                    pass = true;
                    turn = i + 1;
                }
            }
        }
        if (b)
            cout << "Black " << turn << endl;
        else if (w)
            cout << "White " << turn << endl;
        else
            cout << "Draw" << endl;
    }
}



Measured memory_bytes: 3088
#include <algorithm>
#include <cmath>
#include <climits>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
constexpr int kMod = 1000000007;

int main() {
  int H, W, K; std::cin >> H >> W >> K;
  std::vector<std::vector<long long>> d(H+1, std::vector<long long>(W, 0));

  int countup[8] = {};
  for (int i = 0; i < 9; ++i) {
    if (i == 0)      countup[i] = 1;
    else if (i == 1) countup[i] = 2;
    else if (i == 2) countup[i] = 3;
    else countup[i] = countup[i-2] + countup[i-1];
  }

  d[H][K-1] = 1;
  for (int l = H - 1; l >= 0; --l) {
    for (int w = 0; w < W; ++w) {
      // left
      long long pattern1 = 1;
      int left1 = w-1;
      int right1 = w;
      if (left1>=0) {
        int left_num_edge = left1 - 1;
        if (left_num_edge > 0) pattern1 *= countup[left_num_edge];

        int right_num_edge = W - right1 - 2;
        if (right_num_edge > 0) pattern1 *= countup[right_num_edge];

        d[l][w] += static_cast<long long>(pattern1*d[l+1][left1]);
      }

      // middle
      long long pattern2 = 1;
      int left2 = w;
      int right2 = w;
      {
        int left_num_edge = left2 - 1;
        if (left_num_edge > 0) pattern2 *= countup[left_num_edge];

        int right_num_edge = W - right2 - 2;
        if (right_num_edge > 0) pattern2 *= countup[right_num_edge];

        d[l][w] += static_cast<long long>( pattern2*d[l+1][w]);
      }

      // right
      long long pattern3 = 1;
      int left3 = w;
      int right3 = w + 1;
      if (right3 < W) {
        int left_num_edge = left3 - 1;
        if (left_num_edge > 0) pattern3 *= countup[left_num_edge];

        int right_num_edge = W - right3 - 2;
        if (right_num_edge > 0) pattern3 *= countup[right_num_edge];

        d[l][w] += static_cast<long long>(pattern3*d[l+1][right3]);
      }
     d[l][w] %= kMod;
    }
  }
  std::cout << d[0][0] << std::endl;
}


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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
  cerr << endl;
  rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
    if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
      cerr << "INF";
    } else
      cerr << v[i][j];
    cerr << (j == v[i].size() - 1 ? '\n' : ' ');
  }
  cerr << endl;
}
/*
   typedef __int128_t Int;
   std::ostream &operator<<(std::ostream &dest, __int128_t value) {
   std::ostream::sentry s(dest);
   if (s) {
   __uint128_t tmp = value < 0 ? -value : value;
   char buffer[128];
   char *d = std::end(buffer);
   do {
   --d;
 *d = "0123456789"[tmp % 10];
 tmp /= 10;
 } while (tmp != 0);
 if (value < 0) {
 --d;
 *d = '-';
 }
 int len = std::end(buffer) - d;
 if (dest.rdbuf()->sputn(d, len) != len) {
 dest.setstate(std::ios_base::badbit);
 }
 }
 return dest;
 }

 __int128 parse(string &s) {
 __int128 ret = 0;
 for (int i = 0; i < s.length(); i++)
 if ('0' <= s[i] && s[i] <= '9')
 ret = 10 * ret + s[i] - '0';
 return ret;
 }
 */

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

signed main(signed argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int M = 1e6 + 10;
  vector<int> dp(M, INF);
  vector<int> dp2(M, INF);
  dp2[0] = dp[0] = 0;
  rep(i, 1, M) {
    for (int n = 1, x = 1; x <= i;) {
      chmin(dp[i], dp[i - x] + 1);
      if (x & 1) {
        chmin(dp2[i], dp2[i - x] + 1);
      }
      n++;
      x = n * (n + 1) * (n + 2) / 6;
    }
  }

  int x;
  while (cin >> x, x) {
    cout << dp[x] << " " << dp2[x] << endl;
  }

  return 0;
}



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

using namespace std;
#define pb push_back
#define loop(ii,nn) for(int ii=0;ii<nn;ii++)
typedef vector<int> vi;


int main(){
		int n;cin>>n;
		vi l(n);
		
		loop(i,n)cin>>l[i];
		int count=0;
		for(int i=0;i<n;i+=2){
			if(l[i]%2==1)
			count++;
			
		}
		
	cout<<count;
	return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	string s;
	cin >> s;
	int co = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') {
			s[i] = 'D';
		}
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3716
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		boolean flg = false;

		for(int i=1;i<=9;i++) {
			for(int j=1;j<=9;j++) {
			if(n == i*j) {

				flg = true;
			}
			}
		}
		System.out.println(flg?"Yes":"No");
		scan.close();
	}

}


Measured memory_bytes: 23636
import Data.Array.ST
import Data.Array
import Data.STRef
import Control.Monad.ST
import Control.Monad

--lは含まない、rは含む。
bin_ser_STA2::Int->STArray s Int Int ->(Int,Int)-> ST s Int
bin_ser_STA2 v ar (l,r) = if (l+1) == r then return r else do
  let mid = div (l+r) 2
  v_m<-readArray ar mid
  let (l', r') = if  v > v_m then (mid,r) else (l,mid)
  ans<-bin_ser_STA2 v ar (l',r')
  return ans

test_bin_STA2::[Int]->Int->Int
test_bin_STA2 ls v = runST $ do
  sta<-thaw (listArray (1,length ls) ls)
  a<-bin_ser_STA2 v sta (1,length ls)
  return a

ins_write_STA::Int->Int->STArray s Int Int ->ST s ()
ins_write_STA v len ar = do
  idx<-bin_ser_STA2 v ar (0,len)
  writeArray ar idx v
  return ()

test_ins_STA2::[Int]->Int->Array Int Int
test_ins_STA2 ls v = runSTArray $ do
  sta<-thaw (listArray (1,length ls) ls)
  ins_write_STA v (length ls) sta
  return sta

add_STA::Int->Int->STArray s Int Int -> ST s ()
add_STA v len ar = do
  writeArray ar (len+1) v
  return ()

--更新関数：Aの新規値、今のLIS長（STAの有効最大idx）、STA、アクション
update::Int->STArray s Int Int -> STRef s Int -> ST s ()
update v ar len_pt = do
  len <- readSTRef len_pt
  if len == 0 then do
                writeArray ar 1 v
                writeSTRef len_pt 1
                return ()
              else do
                top<-readArray ar len
                if top < v then do
                            writeSTRef len_pt (len+1)
                            add_STA v len ar
                            return ()
                           else do
                            ins_write_STA v len ar
                            return ()

test_update::[Int]->Int->Int->Array Int Int
test_update ls len v = runSTArray $ do
  sta<-thaw (listArray (1,length ls) ls)
  len_pt<-newSTRef len
  update v sta len_pt
  return sta

solver::[Int] -> Int -> Int
solver ls size = runST $ do
  ar<-newArray (1,size) 0
  len_pt<-newSTRef 0
  forM_ ls (\v -> update v ar len_pt)
  len'<-readSTRef len_pt
  return len'


n_get::Int->IO [Int]
n_get 0 = return []
n_get n = do
  c<-getLine
  let dat = read c
  rest<-n_get (n-1)
  return (dat:rest)

main::IO()
main=do
  nc<-getLine
  let n = read nc
  dat<-n_get n
  print (solver dat n)




Measured memory_bytes: 63504
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int N, K; cin >> N >> K;
  int h[100001];
  for(int i=0; i<N; i++) cin >> h[i+1];
  
  int dp[100001];
  dp[1] = 0;
  
  for(int i=2; i<=N; i++){
    int cost[K+1];
    for(int j=1; j<=K && i-j>0; j++){
      cost[j] = dp[i-j] + max(h[i] - h[i-j], h[i-j] - h[i]);
    }
    int m = cost[1];
    for(int j=1; j<=K && i-j>0; j++){
      if(m > cost[j]) m = cost[j];
    }
    dp[i] = m;
  }
  
  cout << dp[N] << endl;
  
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int n , m ;
int a[55] , b[55] , count[55] ;
int main(void){
     cin >> n >> m ;
     for(int i=0;i<n;i++){
          count[i] = 0 ;
     }
     for(int i=0;i<m;i++){
          cin >> a[i] >> b[i] ;
          count[a[i]]++ ; count[b[i]]++ ;
     }
     
     for(int i=1;i<=n;i++){
          cout << count[i] << endl ;
     }
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007ll
#define endl "\n"

int main()
{
    ll n,w;
    cin>>n>>w;
    vector<pair<ll,ll>> ar(n);
    vector<ll> dp(w+1,0);     //Max. value for a given weight
    for(ll x=0;x<n;x++)
    {
        cin>>ar[x].first>>ar[x].second;
    }
    for(ll x=0;x<n;x++)
    {
        for(ll y=w;y>=ar[x].first;y--)
        {
            dp[y]=max(dp[y],dp[y-ar[x].first]+ar[x].second);
        }
    }
    ll ans=0;
    for(ll x:dp)
    {
        ans=max(ans,x);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

int main()
{
    int a,b;
    cin>>a>>b;
    if(a*b%2==0){
        cout<<"Even"<<endl;
    }else{
        cout<<"Odd"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
typedef long long ll;
const int N=0;
int n,k,x,t,m;
string s;
vector<int>v;
int main(){

	cin >> n >> m;
	int eight = n/0.08;
	int ten = m/0.1;	
	

	for(int i =0;i<=1000;i++){
		if(i*8/100 == n && i*10/100 == m){
			cout << i ;
			return 0;;
		}
	}
	cout << -1;
	return 0;
}

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

using namespace std;

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

  int ans = 0;
  for (int i = 0; i <= 9; ++i) {
    char ic = i + '0';
    for (int j = 0; j <= 9; ++j) {
      char jc = j + '0';
      for (int k = 0; k <= 9; ++k) {
	char kc = k + '0';
	int y;
	for (y = 0; y < n; ++y) {
	  if (s[y] == ic) break;
	}
	if (y >= n) continue;
	for (y = y + 1; y < n; ++y) {
	  if (s[y] == jc) break;
	}
	if (y >= n) continue;	

	for (y = y + 1; y < n; ++y) {
	  if (s[y] == kc) break;
	}
	if (y >= n) continue;	

	if (y < n) {
	  ans++;
	}
      }
    }
  }
  cout << ans << endl;
  return 0;
}



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


Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
int arr[100009][3];
int main()
{
    int n;
    scanf("%d",&n);
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<3;j++)
        {
            scanf("%d",&arr[i][j]);
        }
    }
    for(i=1;i<n;i++)
    {
        arr[i][0]+=max(arr[i-1][1],arr[i-1][2]);
        arr[i][1]+=max(arr[i-1][0],arr[i-1][2]);
        arr[i][2]+=max(arr[i-1][1],arr[i-1][0]);
    }
    printf("%d\n",max(arr[n-1][0],max(arr[n-1][1],arr[n-1][2])));
    return 0;
}


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

int main(){
    int n, i, c = 0, m = 0;
    string s;
    cin >> s;
    for(i=0; i<s.size(); i++){
        if(s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C'){
            c++;
        }else{
            m = max(m, c);
            c = 0;
        }
    }
    m = max(m, c);
    cout << m;
    return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

struct S {
  ll p;
  int abi, ci;
  bool operator<(const S& s) const { return p < s.p; }
};

int main() {
  in(ll, x, y, z, k);
  vector<ll> a(x), b(y), c(z);
  rep(i, x) cin >> a[i];
  rep(i, y) cin >> b[i];
  rep(i, z) cin >> c[i];
  vector<ll> ab;
  rep(i, x) rep(j, y) ab.push_back(a[i] + b[j]);
  sort(all(ab));
  reverse(all(ab));
  sort(all(c));
  reverse(all(c));
  priority_queue<S> q;
  rep(i, z) q.push({ab[0] + c[i], 0, i});
  rep(i, k) {
    S s = q.top();
    q.pop();
    out(s.p);
    ++s.abi;
    if (s.abi == ab.size()) {
      continue;
    }
    s.p = ab[s.abi] + c[s.ci];
    q.push(s);
  }
}


Measured memory_bytes: 11684
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(nullptr); ios::sync_with_stdio(false)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    IOS;
    int N; cin >> N;
    vector<int> X,Y;
    rep(i,N){
        int a; cin >> a;
        X.push_back(a);
        Y.push_back(a);
    }
    sort(X.begin(),X.end());
    int A=X[N/2],B=X[N/2-1];
    rep(i,N){
        if(upper_bound(X.begin(),X.end(),Y[i])-X.begin()>N/2)
        cout << B << endl;
        else 
        cout << A << endl;
    }

    return 0;
}


Measured memory_bytes: 6372
def check(a,x):
    if x == 3 :
        print a,
    elif x % 10 == 3:
        print a,
    elif x :
        check(a,x/10)
        
        
n = input()
print"",

for i in range(3,n+1) :
    if i % 3 == 0 :
        print i ,
    elif i%10 == 3 :
        print i,
    else :
        check(i,i/10)
        

        

Measured memory_bytes: 6520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    string S = in<string>();
    int red = 0;
    REP(i,S.size()){
        if(S[i] == '0')red++;
    }
    int blue = S.size()-red;
    cout << min(red,blue)*2 << "\n";
}

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

namespace Volume0_0013
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack<int> trains = new Stack<int>();
            string input;
            while ((input = Console.ReadLine()) != null)
            {
                if (input == "0") Console.WriteLine( trains.Pop() );
                else trains.Push(Convert.ToInt32(input)); 
            }
        }
    }
}

Measured memory_bytes: 10064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string> 
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g;}
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

int main()
{
	int n, k; cin >> n >> k;
	string s; cin >> s;
	vi a;
	if (s.front() == '0')a.push_back(0);
	int j = 0;
	while (j < sz(s))
	{
		int cnt = 1;
		while (j + 1 < sz(s) && s[j] == s[j + 1])
		{
			cnt++;
			j++;
		}
		a.push_back(cnt);
		j++;
	}
	if (s.back() == '0')a.push_back(0);
	int m = sz(a);
	if (k >= m / 2)
	{
		co(n);
		return 0;
	}
	vi sum(m + 1);
	rep(i, m + 1) sum[i] = i == 0 ? 0 : sum[i - 1] + a[i - 1];
	int ans = 0;
	for (int i = 0; 2 * (i + k) < m + 1; i++)
	{
		int start = 2 * i;
		int end = 2 * (i + k) + 1;
		int tmp = sum[end] - sum[start];
		chmax(ans, tmp);
	}
	co(ans);
	return 0;
}


Measured memory_bytes: 1272
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;

#define N 10000
#define INF 100000000

struct Edge {
	int to, cost, dist;
	Edge(int t, int c, int d) : to(t), cost(c), dist(d) {};
	Edge() {};
};

typedef vector<Edge> Graph;
typedef pair<int, int> P;

Graph g[N];
int cost[N], ucost[N];
int n;

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > q;
	for(int i=0; i<n; ++i) {
		cost[i] = INF; ucost[i] = INF;
	}
	q.push(P(0,s)); cost[s] = 0; ucost[s] = 0;
	while(!q.empty()) {
		int v = q.top().second, c = q.top().first; q.pop();
		if(cost[v]<c) continue;
		for(int i=0; i<(signed)g[v].size(); ++i) {
			Edge e = g[v][i];
			if(cost[v]+e.cost<cost[e.to]) {
				cost[e.to] = cost[v] + e.cost;
				q.push(P(cost[e.to],e.to));
				ucost[e.to] = e.dist;
			}else if(cost[v]+e.cost==cost[e.to]) {
				if(e.dist<ucost[e.to]) {
					ucost[e.to] = e.dist;
				}
			}
		}
	}
}

int main() {
	int m, ans;
	int u, v, d, c;
	while(1) {
		cin >> n >> m;
		if(!n&&!m) break;
		for(int i=0; i<n; ++i) g[i].clear();
		for(int i=0; i<m; ++i) {
			cin >> u >> v >> d >> c;
			v--; u--;
			g[u].push_back(Edge(v,d,c));
			g[v].push_back(Edge(u,d,c));
		}
		dijkstra(0);
		ans = 0;
		for(int i=1; i<n; ++i) {
			ans += ucost[i];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
inline int read(){
	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
	int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
	while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(int x){if (x<0)putchar('-'),x=-x;if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(int x){write(x);puts("");}
int f[310][310][310],kk,ans,l;
char s[1000];
signed main(){
	scanf("%s",s);kk=read();l=strlen(s);//f[i][j][k]为i到i+j-1最多修改k个后变成回文最少插入的个数 
	memset(f,10,sizeof(f));for (int i=0;i<=l+5;i++){
		memset(f[i][0],0,sizeof(f[i][0]));memset(f[i][1],0,sizeof(f[i][1]));
	}for (int j=2;j<=l;j++)
		for (int i=1;i+j-1<=l;i++)
			for (int k=0;k<=kk;k++){
				if (k)f[i][j][k]=f[i+1][j-2][k-1];
				if (s[i-1]!=s[i+j-2]){
					if (k)f[i][j][k]=min(f[i][j][k],f[i+1][j-2][k-1]);//修改一发 
				}else f[i][j][k]=min(f[i][j][k],f[i+1][j-2][k]);
				f[i][j][k]=min(f[i][j][k],min(f[i][j-1][k],f[i+1][j-1][k])+1);//插入一发
			}
	writeln(l-f[1][l][kk]);
}



Measured memory_bytes: 116736
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,k;
	long long i;
	scanf("%lld %lld %lld",&a,&b,&k);
	for(i=min(a,b);i>=1;i--)
	{
		if(a%i==0&&b%i==0)
		{
			k--;
			if(k==0)
			{
				printf("%lld",i);
				return 0;
			}
		}
	}
	return 0;
}


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

dp = [[0] * 3 for i in range(n)]
dp[0] = list(map(int, input().split()))

for i in range(1, n):
    a, b, c = map(int, input().split())
    dp[i][0] = max(dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i - 1][2] + b, dp[i - 1][0] + b)
    dp[i][2] = max(dp[i - 1][0] + c, dp[i - 1][1] + c)

print(max(dp[-1]))

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

void solve(){
	int n;
	cin >> n;
	map<string, int> m;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		m[s]++;
	}
	cout << "AC x " << m["AC"] << '\n';
	cout << "WA x " << m["WA"] << '\n';
	cout << "TLE x " << m["TLE"] << '\n';
	cout << "RE x " << m["RE"] << '\n';
}

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

	int t = 1;
	while(t--) solve();
}

Measured memory_bytes: 3652
#include <iostream>
#include <string.h>
#include <bits/stdc++.h>
#include<algorithm> 
using namespace std;
// main() is where program execution begins.



int main() {
    int A,B,K,count = 0;
    cin>>A>>B>>K;  
   
   for (int i = min(A,B); i >=1; --i)
   {
     if (A%i == 0 && B%i==0)
     {
       count++;
       if (count == K)
       {
         cout << i << endl;
         break;
       }
     }
   }

   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define dl double
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
#define cases ll t; cin>>t; while(t--)
#define rep1(qq,pp) for(ll i=qq;i<pp;i++)
#define rep2(qqq,ppp) for(ll i=qqq;i>=ppp;i--)
#define nl "\n"
#define Y cout<<"Yes\n"
#define N cout<<"No\n"
//cout<<fixed<<setprecision(13);

int main(){
	faster;

	int n,x,v,a;
	dl ans;
	
	cin>>n>>x>>v;
	
	ans=(double)n/(double)x;
	a=ceil(ans)*v;
	
	cout<<a<<nl;
}

Measured memory_bytes: 3632
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,s[100000];
int main(void){
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    sort(s,s+n);
    cout<<s[n/2]-s[n/2-1]<<endl;
}


Measured memory_bytes: 640