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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}


int n,m;

class dinic {
  typedef long long ll;
  vector<int> level;
  vector<int> iter;

  void bfs(int s) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();q.pop();
      for (int i = 0; i < (int)g[v].size(); i++) {
        edge &e = g[v][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          q.push(e.to);
        }
      }
    }
  }

  ll dfs(int v, int t, ll f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < (int)g[v].size(); i++) {
      edge &e = g[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        ll d = dfs(e.to, t, min(f,e.cap));
        if (d > 0) {
          e.cap -= d;
          g[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

public:
  struct edge { int to; ll cap; int rev; };
  vector<vector<edge>> g;
  const ll INF = 0x3f3f3f3f3f3f3f3f;

  dinic(int n) {
    g.resize(n); level.resize(n); iter.resize(n);
  }

  void add_edge(int u, int v, int cap) {
    g[u].push_back((edge){v,cap,(int)g[v].size()});
    g[v].push_back((edge){u,0,(int)g[u].size()-1});
  }

  ll max_flow(int s, int t) {
    ll flow = 0;
    while (true) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      ll f;
      while ((f = dfs(s,t,INF)) > 0) flow += f;
    }
  }
};


int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  cin >> n >> m;
  int a,b;
  dinic d(n);
  forn(i,m) {
    cin >> a >> b;
    a--,b--;
    d.add_edge(a, b, 1);
    d.add_edge(b, a, 1);
  }

  bool even = all_of(d.g.begin(),d.g.end(),[](vector<dinic::edge> v) { return v.size() % 4 == 0; });

  vi four;
  int six = 0;
  forn(i,n) {
    if (d.g[i].size() == 8) four.push_back(i);
    if (d.g[i].size() >= 12) six++;
  }

  bool ok;
  if (even && (four.size() >= 3 || six > 0)) ok = true;
  else if (!even || four.size() <= 1) ok = false;
  else {
    ll f = d.max_flow(four[0], four[1]);
    ok = f < 4;
  }

  if (ok)
    cout << "Yes\n";
  else
    cout << "No\n";

  return 0;
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)
  
  string N;
  IN(N);
  ll K;
  IN(K);
  vll dp1(4, 0);
  vll dp2(4, 0);
  vll dp1_copy, dp2_copy;

  dp1[0] = 0;
  dp2[0] = 1;

  REP(i,N.size()){
    dp1_copy = dp1;
    dp2_copy = dp2;
    REP(i,4) dp1[i] = 0;
    REP(i,4) dp2[i] = 0;
    char tmp = N[i];
    int num = (tmp-'0');
    if(num==0){
      REP(k,4){
        dp2[k] = dp2_copy[k];
      }
      REP(k,3){
        dp1[k+1] += dp1_copy[k]*9;
      }
      REP(k,4){
        dp1[k] += dp1_copy[k];
      }
    }else{
      REP(k,3){
        dp2[k+1] = dp2_copy[k];
      }
      REP(k,3){
        dp1[k+1] += dp1_copy[k]*9+dp2_copy[k]*(num-1);
      }
      REP(k,4){
        dp1[k] += dp1_copy[k]+dp2_copy[k];
      }
    }
    //vec_print(dp1);
    //vec_print(dp2);
  }

  OUT(dp1[K]+dp2[K]);


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = (((1<<30)-1)<<1)+1;
const int nINF = 1<<31;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

/////////////////////////////////////////////////////////////////////

const int N = 2e5;
ll n, a[N];

int main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    cin >> n;
    REP(i, n) cin >> a[i];
    ll l = 0, r = 0, s = 0, xs = 0, ans = 0;
    while(r < n) {
    	while(r < n && s+a[r] == (xs^a[r])) {
    		ans += (r-l+1);
    		s += a[r];
    		xs ^= a[r];
    		++r;
    	}
    	while(l < n && s+a[r] != (xs^a[r])) {
    		s -= a[l];
    		xs ^= a[l];
    		++l;
    	}
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;

bool cmp(long long x, long long y) {
  return(x < y);
}

int main(){
  long long n;
  vector<long long> a;
  vector<long long> c;
  cin >> n;
  for (int i=0;i<n;i++) {
    long long tmp_a;
    cin >> tmp_a;
    a.push_back(tmp_a);
  }
  sort(a.begin(), a.end(), cmp);
  long acc = 0;
  for (int i=0;i<n;i++) {
    acc += a[i];
    c.push_back(acc);
  }
  long long result = 1;
  for (int i=n-2;i>=0;i--) {
    if (a[i+1] <= 2*c[i]) {
      result++;
    } else {
      break;
    }
  }
  cout << result << endl;
  return(0);
}


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

int main(void) {
	string str;
	bool flag = true;
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		if (i % 2 == 0) {
			if (('R' == str.at(i) || 'U' == str.at(i)) || 'D' == str.at(i)) continue;
			else { flag = false; break; }
		}
		if (i % 2 == 1) {
			if (('L' == str.at(i) || 'U' == str.at(i)) || 'D' == str.at(i)) continue;
			else { flag = false; break; }
		}
	}
	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(unsigned i=0;i<(n);++i)
#define Fr(i,n) for(unsigned i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

vector<unsigned> solve(unsigned n,unsigned b){
    if(n==1) return vector<unsigned>({0,1});
    unsigned p=-1;
    fr(i,n) if((b>>i)&1) p=i;
    unsigned c=b^(1u<<p),m=(1u<<p)-1;
    auto P=solve(n-1,1u),Q=solve(n-1,c^1u);
    for(auto&i:P) i=(i&m)|((i&~m)<<1u);
    for(auto i:Q) i^=1u,P.push_back((i&m)|(1u<<p)|((i&~m)<<1u));
    return P;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    unsigned n,a,b;
    in>>n>>a>>b;
    b^=a;
    if(1u^__builtin_popcount(b)&1u) return puts("NO"),0;
    cout<<"YES"<<'\n';
    for(auto&i:solve(n,b)) cout<<(i^a)<<' ';
    cout<<'\n';
}


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

int main()
{
    string s, t;
    int i, j, k, n, m, ck, ans;

    cin >> s >> t;

    n = s.size();
    m = t.size();

    ans = 0;
    for(i=0; i<n-m+1; i++)
    {
        k = i, ck = 0;
        for(j=0; j<m; j++)
        {
            if(s[k] == t[j])
                ck++;

            k++;
        }

        ans = max(ans, ck);
    }

    cout << m-ans << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;

ll a[100005];

int main(){
    ll n,x,ans;
    

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

    ans = 0;
    for (int i=0; i<n; i++){
        int memo = a[i]+a[i+1]-x;
        if (memo>0){
            ans += memo;
            a[i+1] -= memo;
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 1024
#include<stdio.h>
int az(int a,int b,int c);
int main(void)
{
        int a,b,c,s;
        scanf("%d %d %d",&a,&b,&c);
        if((a>b)&&(a>c)) s=az(a,b,c);
        else if(b>c) s=az(b,a,c);
        else s=az(c,a,b);
        printf("%d\n",s);
        return 0;
}
int az(int a,int b,int c)
{
        int i,n1=0,n2=0,r=0;
        for(i=b;i<a;i=i+2) n1++;
        r=r+b+2*n1-a;
        for(i=c;i<a;i=i+2) n2++;
        r=r+c+2*n2-a;
        if(r==2) r=-1;
        return n1+n2+r;
}

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

#define ll long long

using namespace std;
const ll INF = 1e18;
const int SIZE_LIMIT = 1e3+5;
char maze[SIZE_LIMIT][SIZE_LIMIT];

ll dp[SIZE_LIMIT][SIZE_LIMIT];

int main() {
  //memset(maze, 0, sizeof(maze));
 // memset(dp, 0x3f, sizeof(dp));

  int h = 0, w = 0, ch, cw, dh, dw;
  scanf("%d%d%d%d%d%d", &h, &w, &ch, &cw, &dh, &dw);
  ch--;cw--;dh--;dw--;

   for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>maze[i][j];
          dp[i][j]=INF;
        }
    }

  deque<pair<int, int>> movable;
  movable.push_back({ch, cw});
  dp[ch][cw]=0;

   const int dx[]={+1,-1,+0,+0};
   const int dy[]={+0,+0,+1,-1};


  while (!movable.empty()) {
    auto p = movable.front();
    movable.pop_front();


    for (int i = 0; i < 4; ++i)
    {
      int nx = dx[i]+p.first, ny = dy[i]+p.second;
      if (nx>=0 and nx<h and ny>=0 and ny<w and maze[nx][ny] == '.' && dp[nx][ny] > dp[p.first][p.second]+0)
      {
        dp[nx][ny] = dp[p.first][p.second]+0;
        movable.push_front({nx, ny});
      }
    }
    // jump
    for (int i = -2; i <= 2; ++i) {
      for (int j = -2; j <= 2; ++j) {
        int nx = p.first+i, ny = p.second+j;
        if (nx>=0 && nx<h && ny>=0 && ny<w && maze[nx][ny] == '.' && dp[nx][ny] > dp[p.first][p.second]+1) {
          dp[nx][ny] = dp[p.first][p.second]+1;
          movable.push_back({nx, ny});
        }
      }
    }

  }

  if (dp[dh][dw] == INF) printf("-1\n");
  else printf("%d\n", dp[dh][dw]);



  return 0;
}


Measured memory_bytes: 12600
n = int(input())
a = list(map(int,input().split()))
 
ans = 0
e = [i for i in a if i % 2 == 0]
for i in e:
  sum = 0
  while True:
    i = i / 2
    sum += 1
    if i % 2 != 0:
      break
  ans += sum
print(ans)


Measured memory_bytes: 4148
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<string>s(n);
    vector<int>t(n);
    for(int i=0;i<n;i++)cin >> s[i] >> t[i];
    string x;
    cin >> x;
    int ans = 0;
    bool chk = false;
    for(int i=0;i<n;i++){
        if(chk){
            ans += t[i];
        }else if(x==s[i]){
            chk = true;
        }
    }
    cout << ans<<endl;
    
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cerr << v << " "; cerr << endl;
#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << v << " "; cerr << endl; } 
#define debugP(vec) for(auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl;
#define debug2DP(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl; } 

typedef long long ll;

constexpr ll INF = 1000000000; //10^10
//const ll MOD = 998244353;
constexpr ll MOD = 1000000007;

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


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

	ll n, k; cin >> n >> k;

	auto sumof = [](ll a) { return a*(a+1)/2 % MOD; };

	ll ans = 0;
	for (int i = k; i <= n; ++i) {
		ans += (sumof(n) - sumof(n - i) - sumof(i-1) + 1);
		if (ans < 0) ans += MOD; else ans %= MOD;
	}
	cout << (ans+1) % MOD << endl;
}

Measured memory_bytes: 3612
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

typedef pair<int,int> P;
bool use[15000000];

int main(){
  int n,m,now;

  for(;;){
    cin >> n >> m;
    if(!n && !m)break;

    now = 0;
    for(int i=0;i<3;i++){
      int num;
      cin >> num;
      for(int j=0;j<num;j++){
	int tmp;
	cin >> tmp;
	now += pow(3,tmp-1)*i;
      }
    }

    int lim = pow(3,n);
    for(int i=0;i<lim;i++)use[i] = false;
    use[now] = true;

    int ans = -1;

    queue<P> q;
    q.push(P(now,0));

    while(q.size()){
      P p = q.front();q.pop();
      stack<int> s[3];
      now = p.first;
      //cout << now << endl;
      for(int i=1;i<=n;i++){
	s[now%3].push(i);
	now/=3;
      }

      if((int)s[0].size()==n || (int)s[2].size()==n){
	ans = p.second;
	break;
      }
      if(p.second>m)break;

      int d1[] = {0,1,1,2},d2[] = {1,0,2,1};

      for(int i=0;i<4;i++){
	if(s[d1[i]].size() && (s[d2[i]].empty() || s[d1[i]].top()>s[d2[i]].top())){
	  int hoge = pow(3,s[d1[i]].top()-1);
	  now = p.first - hoge*d1[i] + hoge*d2[i];
	  if(!use[now]){
	    use[now] = true;
	    q.push(P(now,p.second+1));
	  }
	}
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 14000
// +build ignore
package main

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

func solve(sc *scanner, wr *bufio.Writer) int {
	T := sc.s()

	R := []byte{}

	var prev byte
	for i := 0; i < len(T); i++ {
		switch T[i] {
		case 'P':
			if prev == '?' {
				R[i-1] = 'D'
			}
		case 'D':
			if prev == '?' {
				R[i-1] = 'P'
			}
		case '?':
			if prev == 'P' {
				R = append(R, byte('D'))
				prev = 'D'
				continue
			}
			if prev == '?' {
				R[i-1] = 'P'
				R = append(R, byte('D'))
				prev = 'D'
				continue
			}

			// prev is D
			if i == len(T)-1 {
				R = append(R, byte('D'))
				prev = 'D'
				continue
			}
		}
		R = append(R, byte(T[i]))
		prev = T[i]
	}

	fmt.Println(string(R))
	return 0
}

func main() {
	sc := newScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	ret := solve(sc, wr)
	wr.Flush()
	os.Exit(ret)
}

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

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

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

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

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

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

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

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


Measured memory_bytes: 3992
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

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

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll A, B, M;
  cin >> A >> B >> M;
  vll a(A);
  vll b(B);
  vll x(M);
  vll y(M);
  vll c(M);
  ll c_a = kMod;
  ll c_b = kMod;
  REP(i, 0, A) {
    ll _a;
    cin >> _a;
    a[i] = _a;
    if (_a < c_a) {
      c_a = _a;
    }
  }
  REP(i, 0, B) {
    ll _b;
    cin >> _b;
    b[i] = _b;
    if (_b < c_b) {
      c_b = _b;
    }
  }
  ll ans = kMod * 100;
  REP(i, 0, M) {
    ll _x, _y, _c;
    cin >> _x >> _y >> _c;
    x[i] = _x;
    y[i] = _y;
    c[i] = _c;
    ll v = a[_x - 1] + b[_y - 1] - _c;
    if (v < ans) {
      ans = v;
    }
  }
  cout << min(ans, c_a + c_b) << endl;

  return 0;
}


Measured memory_bytes: 4224
// practice with Dukkha
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 50;

int aa[N], n;

void solvep(int ip) {
	int m = n - 1;
	for (int i = 0; i < n; i++)
		if (aa[i] < 0)
			m++;
	cout << m << '\n';
	for (int i = 0; i < n; i++)
		if (aa[i] < 0)
			cout << ip + 1 << ' ' << i + 1 << '\n';
	for (int i = 1; i < n; i++)
		cout << i << ' ' << i + 1 << '\n';
}

void solveq(int iq) {
	int m = n - 1;
	for (int i = 0; i < n; i++)
		if (aa[i] > 0)
			m++;
	cout << m << '\n';
	for (int i = 0; i < n; i++)
		if (aa[i] > 0)
			cout << iq + 1 << ' ' << i + 1 << '\n';
	for (int i = n - 1; i; i--)
		cout << i + 1 << ' ' << i << '\n';
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	int ip = -1, iq = -1;
	for (int i = 0; i < n; i++)
		if (aa[i] > 0 && (ip == -1 || aa[ip] < aa[i]))
			ip = i;
		else if (aa[i] < 0 && (iq == -1 || aa[iq] > aa[i]))
			iq = i;
	if (ip != -1 && iq == -1)
		solvep(ip);
	else if (ip == -1 && iq != -1)
		solveq(iq);
	else if (ip != -1 && iq != -1) {
		if (aa[ip] + aa[iq] >= 0)
			solvep(ip);
		else
			solveq(iq);
	} else
		cout << "0\n";
	return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>

int main()
{
	int n, a, b;

	scanf("%d", &n);

	if (n == 1)
		printf("Hello World\n");
	else
	{
		scanf("%d%d", &a, &b);
		printf("%d\n",a + b);
	}

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll c[10][10];
ll A[300][300];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H , W; cin >> H >> W;
  rep(i,10)rep(j,10)
    cin >> c[i][j];

  rep(i,H)rep(j,W)
    cin >> A[i][j];


  rep(k,10)rep(i,10)rep(j,10)
    c[i][j] = min(c[i][j], c[i][k]+c[k][j]);

  ll ans = 0;
  rep(i,H)rep(j,W){
    if(A[i][j]==-1) continue;
    ans += c[A[i][j]][1];
  }

  cout << ans << endl;
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 768
#include <iostream>
using namespace std;
int n, s, cnt;

void dfs(int depth, int num, int sum) {
  if (depth == 0 && sum == s) {
    cnt++;
    return;
  }
  if (num == 10 || depth == 0) return;
  dfs(depth, num + 1, sum);
  dfs(depth - 1, num + 1, sum + num);
}

int main() {
  while (cin >> n >> s, n | s) {
    cnt = 0;
    dfs(n, 0, 0);
    cout << cnt << endl;
  }
}


Measured memory_bytes: 3068
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//l={1,2,3,4}
//greater<int>()
//sort(l,l+n)

int main(void)
{
	int a, b;
	cin >> a >> b;
	cout << max({ a + b,a*b,a - b }) << endl;
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

struct Combination
{
    void init(ll n)
    {
        mNumTbl.resize(n + 1);
        mInverseNumTbl.resize(n + 1);
        mNumTbl[0] = 1;
        mInverseNumTbl[0] = 1;
        FOR(i, n + 1, 1)
        {
            mNumTbl[i] = (mNumTbl[i - 1] * i) % MOD;
        }
        FOR(i, n + 1, 1)
        {
            mInverseNumTbl[i] = modpow(mNumTbl[i]);
        }
    }

    ll get(ll n, ll r)
    {
        if (n < r || n < 0)
            return 0;
        return (((mNumTbl[n] * mInverseNumTbl[r]) % MOD) * mInverseNumTbl[n - r]) % MOD;
    }

    //! バイナリ方で累乗を計算
    ll modpow(ll n)
    {
        ll s = 1, p = n;
        for (ll i = 0; (1LL << i) <= MOD - 2; ++i, p = (p * p) % MOD)
        {
            if (((MOD - 2) & (1 << i)) == 0)
                continue;
            s *= p;
            s %= MOD;
        }
        return s;
    }

    vector<ll> mInverseNumTbl;
    vector<ll> mNumTbl;
};

int main()
{
    ll X, Y;
    cin >> X >> Y;
    ll ans = 0;

    Combination cmb;
    cmb.init(1000005);

    REP(i, X + 1)
    {
        //! x方向に1動かすのをi回行う
        ll x0 = i;
        if ((X - x0) % 2 == 1)
            continue;
        ll x1 = (X - x0) / 2;

        ll y = x0 * 2LL + x1 * 1;
        if (y != Y)
            continue;

        //! (x0+1)^x1;
        ans += cmb.get((x0 + 1) + x1 - 1, x1);
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  double A,B,N,K;
  cin >>N>>K;
  double ans;
  vector<double>b(N);
  vector<int>a(N);
    vector<double>c(1001);
  cin>>a[0];
  c[1]=1.0;
 for(int i=2;i<1001;i++){
   c[i]=((i-1)*c[i-1]+i)/i;
 }
  b[0]=c[a[0]];
  for(int i=1;i<N;i++){
    cin>>a[i];
    b[i]=b[i-1]+c[a[i]];
  }
  ans=b[K-1];
  for(int i=K;i<N;i++){
    ans=max(ans,b[i]-b[i-K]);

  }
  cout << std::setprecision(10)<<ans<< endl;
}


Measured memory_bytes: 2560
S = input()
SL = int(S[:2])
SR = int(S[2:])
if 1 <= SL <= 12:
    if 1 <= SR <= 12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if 1 <= SR <= 12:
        print('YYMM')
    else:
        print('NA')

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<int> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int N, M; cin >> N >> M;
  cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
}


Measured memory_bytes: 3592
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

inf = float('inf')

import queue

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] != '#':
            q = queue.Queue()
            d = [[inf for _ in range(W)] for _ in range(H)]
            # 距離を保存
            q.put([h, w])
            d[h][w] = 0
            # スタートをキューに、距離を0に
            while not q.empty():
                p = q.get()
                # if p == g:
                #     break
                for i in range(4):
                    nx = p[1] + dx[i]
                    ny = p[0] + dy[i]
                    if nx >= 0 and nx < W and ny >= 0 and ny < H and S[ny][nx] != '#' and d[ny][nx] == inf:
                        q.put([ny, nx])
                        d[ny][nx] = d[p[0]][p[1]] + 1
            for hh in range(H):
                for ww in range(W):
                    if d[hh][ww] != inf:
                        ans = max(ans, d[hh][ww])

print(ans)


Measured memory_bytes: 4080
o=input()
e=input()
x=['' for _ in range(len(o)+len(e))]
for i in range(0,len(o)+len(e),2):
    x[i]=o[i//2]
for i in range(1,len(o)+len(e),2):
    x[i]=e[(i-1)//2]
print(''.join(x))

Measured memory_bytes: 3060
N,M = map(int, raw_input().split())
V,W = [],[]
for i in range(N):
    v,w = map(int, raw_input().split())
    V.append(v)
    W.append(w)

dp = [[-1]*(M+1) for _ in range(N+1)]
def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]

    if i == N:
        res = 0
    elif j < W[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1,j), rec(i+1,j-W[i]) + V[i])

    dp[i][j] = res
    return res

print rec(0, M)


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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;
string s;

int main() {
    cin >> n;
    Vi a(n), b(n), c(n);
    REP(i, n) cin >> a[i];
    REP(i, n) cin >> b[i];
    REP(i, n) cin >> c[i];

    sort(ALL(a));
    sort(ALL(b));
    sort(ALL(c));

    Vl cnt(n);
    REP(i, n) {
        auto iter = upper_bound(ALL(c), b[i]);
        if (iter == c.end()) cnt[i] = 0;
        else cnt[i] = n - (iter - c.begin());
    }
    RREP(i, n-2, 0) {
        cnt[i] += cnt[i+1];
    }

    ll res = 0;
    FOR(i, a) {
        auto iter = upper_bound(ALL(b), *i);
        if (iter == b.end()) break;
        res += cnt[iter - b.begin()];
    }
    std::cout << res << '\n';

    return 0;
}


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

int main(){
  int n;  cin >> n;
  vector<int> p(n), cp(n);
  rep(i,n){
    cin >> p[i];
    cp[i] = p[i];
  }
  sort(cp.begin(), cp.end());
  int cnt = 0;
  rep(i,n){
    if(cp[i] == p[i]) continue;
    cnt++;
  }
  if(cnt < 3)
    puts("YES");
  else
    puts("NO");
  return 0;
}

Measured memory_bytes: 256
x, n = list(map(int, input().split()))
q = list(map(int, input().split()))
p = [i for i in range(0, 102) if i not in q]

for i in range(len(p)):
    if p[i] < x:
        continue
    # p[i] >= x
    break

if p[i] == x:
    print(p[i])
else:
    if p[i] - x < x - p[i - 1]:
        print(p[i])
    else:
        print(p[i - 1])

Measured memory_bytes: 9036
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>

int main(int argc, char const* argv[])
{
	while (true) {
		unsigned n;
		unsigned nshift{};
		std::string s;

		std::cin >> s;
		if (s == "-") break;
		std::cin >> n;

		for (int i = 0; i < n; i++) {
			int d;
			std::cin >> d;
			nshift += d;
		}
		nshift %= s.length();
		for (int i = 0; i < s.length(); i++) {
			std::cout << s[(nshift+i) % s.length()];
		}
		std::cout << std::endl;
	}

	return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <cstdio>
#include <algorithm>
#define F first
#define S second

using namespace std;

typedef long long ll;

ll n;
pair<ll, ll> a[100005];
ll b[100005];
ll ans;
ll mx = 0, mn = 4e18;

int main()
{
    scanf("%lld", &n);
    for(ll i = 0; i < n; i++)
    {
        scanf("%lld%lld", &a[i].F, &a[i].S);
        a[i].S++;
    }
    sort(a, a + n);
    for(ll i = n - 1; i >= 1; i--)
    {
        mx = max(mx, a[i].F);
        mn = min(mn, a[i].S);
        b[i] = max(mn - mx, 0LL);
    }
    mx = 0, mn = 4e18;
    for(ll i = 0; i < n - 1; i++)
    {
        mx = max(mx, a[i].F);
        mn = min(mn, a[i].S);
        ans = max(ans, b[i + 1] + max(mn - mx, 0LL));
    }
    ll mlen=0LL;
    for(ll i = 0; i < n; i++)
    {
        mx = max(mx, a[i].F);
        mn = min(mn, a[i].S);
        mlen = max(mlen, a[i].S - a[i].F);
    }
	ans = max(ans, mlen + max(0LL, mn - mx));
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 2560
///\/\/\/

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, ll>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    nvarep(n,v);
    map<int,int>fm,bm;
    rep(i,0,n){
        if(i%2==0)fm[v[i]]++;
        else bm[v[i]]++;
    }
    vector<p>f,b;
    irep(i,fm){
        f.pb(mp(i->second,i->first));
    }
    irep(i,bm){
        b.pb(mp(i->second,i->first));
    }
    f.pb(mp(0,0));
    b.pb(mp(0,0));
    sort(range(f));
    reverse(range(f));
    sort(range(b));
    reverse(range(b));
    if(f[0].second==b[0].second){
        cout<<n-max(f[0].first+b[1].first,f[1].first+b[0].first)<<nnn;
    }else{
        cout<<n-f[0].first-b[0].first<<nnn;
    }
    return 0;
}

Measured memory_bytes: 12592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define INF 1<<30
int main(){
  int N;
  cin>>N;
  vector<int> H(N);
  rep(i,N) cin>>H[i];
  vector<int> dp(N);
  dp[0]=0;
  rep(i,N-1) dp[i+1]=INF;
  rep(i,N){
    if(i>0) dp[i]=min(dp[i],dp[i-1]+abs(H[i]-H[i-1]));
    if(i>1) dp[i]=min(dp[i],dp[i-2]+abs(H[i]-H[i-2]));
  }
  cout<<dp[N-1]<<endl;
}

Measured memory_bytes: 1024
import math
a,b,c= map(int,input().split())
d = list(map(int,input().split()))
answer = 0
e = [list(map(int,input().split()))for i in range(a)]
for i in range(a):
    g = 0
    for j in range(b):
        g += e[i][j]*d[j]
    g += c
    if g>0:
        answer += 1
print(answer)

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

int main() {
  int A, B, c , d, e, k;
  cin >> A >> B >> c >> d >> e >> k;
  if(e - A > k){
    cout << ":(" << endl;
  }
  else{
    cout << "Yay!" << endl;
  }
}

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, vl> plv;
int main(){
    ll n[3];
    ll k;
    for(int i = 0;i < 3;i++)cin >> n[i];
    cin >> k;
    ll a[4][2000];
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < n[i];j++){
            cin >> a[i][j];
        }
        sort(a[i],a[i]+n[i],greater<ll>());
    }

    
    priority_queue<plv> pq;
    vl v_init = vector<ll>(3);
    plv p_init = make_pair(a[0][0] + a[1][0] + a[2][0],v_init);

    pq.push(p_init);
    set<vl> vis;
    while(k--){
        auto item = pq.top();pq.pop();
        if(vis.find(item.second) != vis.end()){k++;continue;}
        vis.insert(item.second);
        cout << item.first << endl;
        if(k < 0)break;
        for(int i = 0;i < 3;i++){
            auto item2 = item;
            ll index = item2.second[i];
            if(index == n[i]-1)continue;
            item2.second[i]++;
            //cout << "push: " <<  item.first - a[i][index] + a[i][index+1] << ", (" << item2.second[0] << ", " << item2.second[1] << ", " << item2.second[2] << ")" <<endl;
            pq.push(make_pair(item.first - a[i][index] + a[i][index+1],item2.second));
        }
    }

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
 
const int N=1e5+5;
int n,cnt[N];
 
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=0;i<n;++i){
		int x;
		cin>>x;
		cnt[x]++;
	}
	int res=0;
	for(int i=0;i<100000;++i){
		int sum=cnt[i]+cnt[i+1];
		if(i) sum+=cnt[i-1];
		res=max(res,sum);
	}
	cout<<res<<'\n';
}
 

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

int main(){
	string s;
	while(getline(cin, s), s != "."){
			stack<char> st;
			bool flag = true;
			for(int i = 0; i < (int)s.size(); i++){
				if(s[i] == '(' ) st.push('(');
				else if(s[i] == '[' ) st.push('[');

				if(s[i] == ')' ){
					if(st.empty() or st.top() != '('){
						flag = false;
						break;
					}
					if(!st.empty()) st.pop();
				}
				else if(s[i] == ']' ){
					if(st.empty() or st.top() != '['){
						flag = false;
						break;
					}
					if(!st.empty()) st.pop();
			}
		}
		if(!st.empty()) flag = false;
		if(flag) cout << "yes" << endl;
		else cout << "no" << endl;
		while(!st.empty()) st.pop();
	}
	return 0;
}



Measured memory_bytes: 3116
import java.util.Scanner

object Main{
  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    sc.nextLine

    val sortedSides: Array[Int] = sc.nextLine.split(" ").map(_.toInt).sorted
    val maxSide: Int = sortedSides(sortedSides.length - 1)
    if (maxSide < sortedSides.slice(0, sortedSides.length - 1).sum) println("Yes")
    else println("No")
  }
}

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


int main() {
    int N; //items
    int M; //discountTickets 
    cin >> N >> M;

    int A[N];
    for( int i = 0 ; i < N ; i++) cin >> A[i];

    priority_queue<int> prices;

    for( int i = 0 ; i < N ; i++) prices.push(A[i]);

    for( int i = 0 ; i < M ; i++) {
        int topPrice = prices.top();
        prices.pop();
        //discount
        prices.push(topPrice/2);
    }
 
    long answer = 0;
    while (!prices.empty()) {
        answer += prices.top();
        prices.pop();
    }

    cout << answer << endl;
    return 0;
}
    


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

#define all(v) (v).begin(), (v).end()

vector<pair<int, int>> cons, stars;
vector<int> luz[1010101];
  int m, n;

int main()
{
  while (cin >> m, m){

    cons.clear();
    stars.clear();
    for (int i = 0; i < 1000001; i++){
      luz[i].clear();
    }

    int x, y;
    cin >> x >> y;
    
    for (int i = 1; i < m; i++){
      int nx, ny;
      cin >> nx >> ny;
      cons.push_back(make_pair(nx - x, ny - y));
    }
    
    cin >> n;
    for (int i = 0; i < n; i++){
      int nx, ny;
      cin >> nx >> ny;
      luz[nx].push_back(ny);
      stars.push_back(make_pair(nx, ny));
    }

    for (auto &i : stars) {
      int cnt = 0;
      for (auto &j : cons) {
        int nx = i.first + j.first, ny = i.second + j.second;
        if (nx < 0 || ny < 0 || nx > 1000001 || ny > 1000001) continue;
        for (auto &k : luz[nx]){
          if (k == ny) cnt++;
        }
      }

      if (cnt == cons.size()) {
        cout << i.first - x << " " << i.second - y << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 26856
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct TEMP_OMAZINAI_ { TEMP_OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } TEMP__omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void TEMP_INPUT_IMPL_() {};
template <class T, class... Args> void TEMP_INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; TEMP_INPUT_IMPL_(args...); }
void TEMP_OUTPUT_IMPL_() {};
template <class T, class... Args> void TEMP_OUTPUT_IMPL_(T dest, Args... args) { cout << dest << (sizeof...(Args) ? " " : ""); TEMP_OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; TEMP_INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define rsort_v(v) std::sort(v.rbegin(), v.rend())
#define unique_v(v) v.erase(std::unique(v.begin(), v.end()), v.end()) //必ずソート後に実行
#define out(...) (TEMP_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

// ^^^ Template ^^^ //

int main() {
	in(ll, N);
	in_v(ll, A, N);
	in_v(ll, B, N);
	if (std::accumulate(A.begin(), A.end(), 0ll) - std::accumulate(B.begin(), B.end(), 0ll) < 0) {
		out(-1);
		return 0;
	}
	vector<pair<ll, ll>> d;
	ll ans = 0, rem = 0;
	//std::cerr << " > " << ans << " - " << rem << endl;
	loop(i, N) {
		ll t = A[i] - B[i];
		if (t < 0) {
			++ans;
			rem += t;
		} else if (t > 0) {
			d.push_back(make_pair(A[i] - B[i], i));
		}
	}
	//std::cerr << " > " << ans << " - " << rem << endl;
	sort_v(d);
	while (rem < 0) {
		if (d.empty()) {
			out(-1); return 0;
		}
		auto p = d.back();
		d.pop_back();
		rem += p.first;
		++ans;
	}
	out(ans);
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    int n = 0;
    
    for (int x = a; x <= b; x++)
    {
        if (c % x == 0)
        {
            n++;
        }
    }
    
    cout << n << "\n";
    
    return 0;
}


Measured memory_bytes: 3120
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int h = sc.NextInt();
        int w = sc.NextInt();

        string s = "";
        for (int i = 0; i < w + 2; i++)
        {
            s += "#";
        }
        Console.WriteLine(s);

        for (int i = 0; i < h; i++)
        {
            string s2 = "#";
            s2 += sc.Next();
            s2 += "#";
            Console.WriteLine(s2);
        }

        Console.WriteLine(s);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

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

int main() {
  int N;
  cin >> N;
  int d[N];
  rep(i, N) cin >> d[i];
  
  int ans = 0;
  rep(i, N)rep(j,N) {
    if (i <= j) continue;
    ans += d[i]*d[j];
  }
  
  cout << ans;
  
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const int inf = (int)1.05e9;

const i64 mod = 1e9 + 7;

int main()
{
	char s[105000];
	int len;

	scanf("%d%s", &len, s);

	i64 ans = 1;

	for(char c = 'a'; c <= 'z'; ++c) {

		i64 count = 0;
		for(int i = 0; i < len; ++i) {
			if(s[i] == c) {
				count += 1;
			}
		}

		ans = ans * (count + 1) % mod;
	}

	printf("%lld\n", ans - 1);

	return 0;
}

/* waffle */


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll  long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define e endl
#define MAXN 200005
#define debug cout<<"we are debuuging"<<endl;
#define MOD 1000000007
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
vector<int> g[MAXN];
vector<int> arr(MAXN);
vector<int> ans(MAXN);
void dfs(int u,int par,int val)
{
     ans[u]+=val;
     for(auto v : g[u])
     {
          if(v==par)
               continue;
          dfs(v,u,arr[v]+val);
     }
}
int main()
{
     int n,q;
     cin>>n>>q;
     int u,v;
     for(int i=0;i<n-1;i++)
     {
          cin>>u>>v;
          g[u].pb(v);
          g[v].pb(u);
     }
     int p,val;
     while(q--)
     {
          cin>>p>>val;
          arr[p]+=val;
     }
     dfs(1,-1,arr[1]);
     for(int i=1;i<=n;i++)
          cout<<ans[i]<<" ";
}


Measured memory_bytes: 24320
//
// Created by 江口慎悟 on 2019-04-13.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void a(){
    int A,B; cin >> A >> B;

    int ans = 0;
    if (A > B){
        ans +=A;A--;
    } else {
        ans += B;
        B--;
    }

    if (A > B){
        ans +=A;A--;
    } else {
        ans += B;B--;
    }

 cout << ans;

}

void b(){

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

    int c = 0;
    int max_h = 0;
    for(int i = 0; i < N ;i++){

        if(max_h <= H[i]){
            c++;
            max_h = H[i];
        }
    }

    cout << c;

}

void c(){

    string S; cin >> S;
    int N = S.size();
    int stBlack = 0;
    for(int i = 0; i < N; i++){
        if (i % 2 == 0 && S[i] == '1') stBlack++;
        if (i % 2 == 1 && S[i] == '0') stBlack++;
    }

    int stWhite = 0;
    for(int i = 0; i < N; i++){
        if (i % 2 == 0 && S[i] == '0') stWhite++;
        if (i % 2 == 1 && S[i] == '1') stWhite++;
    }

    cout << min(stBlack, stWhite);

}

void d(){

    int N,K; cin >> N >> K;
    string S; cin >> S;

    vector<int> st,ed;
    if (S[0] == '1') {
        st.push_back(0);
    }

    for(int i = 1; i < N ;i++){
        if( S[i-1] == '0' && S[i] == '1' ){ st.push_back(i); }
    }

    for(int i = 0; i < N -1 ;i++){
        if (S[i] == '1' && S[i+1] == '0'){
            ed.push_back(i);
        }
    }
    ed.push_back(N-1);//必ず

    int edMaxIdx = ed.size() - 1;
    int maxOne = 0;
    if(S[0] == '0'){
        maxOne = ed[ min(edMaxIdx, K-1)] + 1;
    }

    for(int stIdx = 0; stIdx < st.size(); stIdx++){
         int len = ed[ min(edMaxIdx, stIdx + K)] - st[stIdx] + 1;
         maxOne = max(maxOne, len);
    }

    cout << maxOne;


}

int main(){
    d();
    return 0;
}


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


int main() {
  int x, t;
  cin >> x >> t;
  int ans = 0;
  if(x > t) ans = x - t;
  cout << ans << endl;
  return 0;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,a[N],pre[N],bk[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    pre[1]=a[1];
    bk[n]=a[n];
    for(int i=2;i<=n;i++) pre[i]=max(pre[i-1],a[i]);
    for(int i=n-1;i>=1;i--) bk[i]=min(bk[i+1],a[i]);
    bool flag=true;
    for(int i=1;i<=n;i++)
        if((a[i]&1)^(i&1)) flag=false;
    for(int i=2;i<n;i++)
        if(a[i]!=i&&a[i-1]!=i-1&&a[i+1]!=i+1) flag=false;
    for(int i=1;i<n;i++)
        if(a[i]==i&&a[i+1]==i+1&&pre[i]!=i) flag=false;
    for(int i=2;i<n;i++)
        if(a[i]!=i&&pre[i-1]>a[i]&&bk[i+1]<a[i]) flag=false;
    for(int i=1;i<=n;i++)
        if(i<a[i]&&bk[i+1]>a[i]) flag=false;
    for(int i=n-1;i>=1;i--)
        if(i>a[i]&&pre[i-1]<a[i]) flag=false;
    for(int i=2;i<=n;i++) pre[i]=min(pre[i-1],a[i]);
    for(int i=n-1;i>=1;i--) bk[i]=max(bk[i+1],a[i]);
    for(int i=1;i<=n;i++)
        if(i<a[i]&&pre[i-1]>a[i]) flag=false;
    for(int i=n-1;i>=1;i--)
        if(i>a[i]&&bk[i+1]<a[i]) flag=false;
    printf(flag?"Yes\n":"No\n");
}


Measured memory_bytes: 3840