akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <boost/algorithm/string/join.hpp>
#include <boost/range/irange.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::irange;
using boost::algorithm::join;

typedef long long ll;
typedef unsigned long long ull;
//typedef long double ld;

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

constexpr ll MOD = 1e9+7;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/4;
constexpr int INF=inf<int>;
constexpr ll LINF=inf<ll>;

#define Sort(x) sort(begin(x),end(x))
#define Reverse(x) reverse(begin(x),end(x))
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ull<<(n))
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,(v).size())

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
    #define endl "\n"
  }
} before_main_function;

// ========== end of template ==========

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

  if (N%2) {
    cout << 0 << endl;
    return 0;
  }

  N /= 2;
  ll f = 5;
  ll ret = 0;
  while (f<=N) {
    ret += N/f;
    f *= 5;
  }

  cout << ret << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 1e6 + 34;

int main()
{
    int x;
    cin >> x;
    x = 1999 - x;
    cout << x / 200 + 1;
}


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

template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
long gcd(long a, long b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }}
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcount(n)

int main(){
    int d, c;
    cin >> d >> c;
    cout << d * c << endl;
}




Measured memory_bytes: 3104
#include <stdio.h>
int main(void){
    int a, b;
    scanf("%d %d", &a, &b);
    if(a==b){
        printf("a == b\n");
    }
    if(a>b){
        printf("a > b\n");
    }
    if(a<b){
        printf("a < b\n");
    }
    return 0;
}


Measured memory_bytes: 2132
import sys

N = int(sys.stdin.readline())
ABC = [[None]*3 for i in range(N)]

for i in range(N):
    ABC[i][0], ABC[i][1], ABC[i][2] = map(int, sys.stdin.readline().split())

happiness = [[0] *3 for i in range(N+1)]

for i in range(N):
    for j in range(3):
        happiness[i+1][j] = max(happiness[i][j-1] + ABC[i][j], happiness[i][j-2] + ABC[i][j])

print(max(happiness[N]))

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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)

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

	LL cnt = 0;
	int i = 0;
	int ac = 0;
	while (i + 2 < S.size()) {
		if (S[i] == 'A') {
			++ac;
		}
		else {
			ac = 0;
		}

		if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
			S[i] = 'B';
			S[i + 1] = 'C';
			S[i + 2] = 'A';

			cnt += ac;
			ac -= 1;

			i += 2;
		}
		else {
			++i;
		}
	}

	cout << cnt << endl;

	return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int64_t> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int64_t res = 0, m = A[0];
  for (int i = 0; i < N; i++) {
    if (m > A[i]) {
      res += m - A[i];
    }
    m = max(m, A[i]);
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 4776
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    x = min(a[i], b[i])
    ans += x
    a[i] -= x
    b[i] -= x
    if b[i] > 0:
        x = min(a[i + 1], b[i])
        ans += x
        a[i + 1] -= x
print(ans)


Measured memory_bytes: 82020
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long

int d[5000],e[5000];
int k, q;

void solve(){
    int n, x, m; cin >> n >> x >> m; x %= m;
    int sum = 0; 
    REP(i,k){
        e[i] = d[i] % m + ( d[i] % m == 0 ? m : 0 );
        sum += e[i];
    }
    sum *= (n-1) / k;
    sum += x;
    REP(i, (n-1)%k) sum += e[i];
    cout << n - 1 - (sum / m) + (x / m) <<endl;
}

signed main(){
    cin >> k >> q;
    REP(i,k) cin >> d[i];
    REP(i,q) solve();
}

Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <tuple>
#define pb push_back
#define mod 1000000007
using namespace std;
typedef long long int ll;


int hako1[111111];
int hako2[111111];
int main(void){
  int N,C;
  int s,t,c;
  cin>>N>>C;

  vector<tuple<int,int,int> >tp3;
  for(int i=0;i<N;i++){
    cin>>s>>t>>c;
    tp3.pb(tuple<int,int,int>(c,s,t));
  }

  sort(tp3.begin(),tp3.end());

  hako1[get<1>(tp3[0])-1]++;
  hako1[get<2>(tp3[0])]--;
  for(int i=1;i<tp3.size();i++){
    if(get<0>(tp3[i])==get<0>(tp3[i-1])&&get<1>(tp3[i])==get<2>(tp3[i-1])) hako1[get<1>(tp3[i])]++;
    else hako1[get<1>(tp3[i])-1]++;
    hako1[get<2>(tp3[i])]--;
  }
  
  int res=0;
  int tmp=0;
  for(int i=0;i<111111;i++){
    tmp+=hako1[i];
    res=max(res,tmp);
  }
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 1912
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	std::string s;
	std::cin >> s;
	int xx=0;
	int yy=0;
	rep(i,n) {
		if(s[i]=='2' && i==(i&(n-1)) ) xx^=1;
		if(s[i]=='2')yy=1;
	}
	if(xx==1) {
		print(1);
		return 0;
	}
	if(yy) {
		print(0);
		return 0;
	}
	int xxx=0;
	rep(i,n) {
		if(s[i]=='3' && i==(i&(n-1)) ) xxx^=1;
	}
	if(xxx) print(2);
	else print(0);
	return 0;
}


Measured memory_bytes: 1412
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    # 証言を有向グラフで管理，-1：証言なし
    graph = [[-1 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        ai = int(input())

        for _ in range(ai):
            xi, yi = map(int, input().split())
            # 0-indexだと実装が楽に
            xi -= 1
            graph[i][xi] = yi

    ans = 0

    # See:
    # https://www.youtube.com/watch?v=tNyPYIhy9Ms&feature=youtu.be
    # KeyInsight：
    # あるパターンを決め打って，条件を満たすかどうかを判定する
    # 0/1で何を表現するか=>正直な人を1，不親切な人を0と割り当てる
    # 不親切な人=嘘つきではない

    # できた部分：正直な人と不親切な人をbitで割り当てて，全探索
    # できなかった部分: 正直な人と不親切な人の判定

    # bit全探索
    # ある人について，0/1を全て試す2^n通り
    for bit in range(1 << n):
        d = [0 for _ in range(n)]

        for j in range(n):
            # 0 1 0 0 1 ・・・のように，正直な人と不親切な人の集合を作成している
            # あるパターンのときにjビット目が1かどうかを判定
            if (bit >> j) & 1:
                d[j] = 1

        is_ok = True

        # 正直な人の証言が全て矛盾していないかを判断
        # 不親切な人の証言は判定しなくてもよいのがポイント
        for j in range(n):
            if d[j] == 1:
                for k in range(n):
                    # 該当する証言がない
                    if graph[j][k] == -1:
                        continue

                    # 証言とパターンの比較
                    if graph[j][k] != d[k]:
                        is_ok = False

        # 正直な人の最大値を更新
        if is_ok:
            ans = max(ans, sum(d))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 45676
#include <iostream>

using namespace std;
typedef long long ll;

int main(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        ll xi;
        cin >> xi;
        ans += 2 * min(xi, k - xi);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 504
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX(x,y) ((x)<(y)?(y):(x))


typedef struct{
  int num;
  long long int Happy;
}Human;
  
int koujun(const void*a,const void*b){
  return ((Human*)b)->Happy-((Human*)a)->Happy;
};

int main(){
  long long int chi_n,sum=0;
  scanf("%lld",&chi_n);
  Human child[2000];
  for(int i=0;i<chi_n;i++){
    child[i].num=i;
    scanf("%lld",&child[i].Happy);
  };
  qsort(child,chi_n,sizeof(Human),koujun);   
  long long int dp[2001][2001];
  dp[0][0] = 0;
	  for (int i = 0; i < chi_n; i++)
  {
      for (int j = 0; i + j + 1 <= chi_n; j++)      {
	        dp[i+1][j] = MAX(dp[i+1][j], dp[i][j] + child[i+j].Happy * (child[i+j].num - i));
	        dp[i][j+1] = MAX(dp[i][j+1], dp[i][j] + child[i+j].Happy* (chi_n - 1 - j - child[i+j].num) );
	      }
	  }
  for (int i = 0; i <= chi_n; i++)
	  {
	     sum = MAX(sum, dp[i][chi_n-i]);
	  }
	  printf("%lld", sum);
	  
  return 0;
	}

Measured memory_bytes: 24484
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
struct N{
	int t,b,n,s,e,w;
	int y,x;
	
	int c;
	bool operator<(const N &r)const
	{
		return c>r.c;
	}
	void roll(int d)
	{
		int tmp;
		y+=dy[d],x+=dx[d];
		
		if(d==0)
		{
			tmp=t; t=s; s=b; b=n; n=tmp;
		}else if(d==1)
		{
			tmp=t; t=e; e=b; b=w; w=tmp;
		}else if(d==2)
		{
			tmp=t; t=n; n=b; b=s; s=tmp;
		}else
		{
			tmp=t; t=w; w=b; b=e; e=tmp;
		}
	}
};

int dp[10][10][50];

int main()
{
	int h,w;
	while(cin>>h>>w,h)
	{
		int g[h][w],sy,sx,gy,gx;
		rep(i,h)rep(j,w)cin>>g[i][j];
		
		cin>>sy>>sx>>gy>>gx;
		rep(i,10)rep(j,10)fill_n(dp[i][j],50,inf);
		dp[sy][sx][1*7+2]=0;
		
		N cur; cur.y=sy,cur.x=sx,cur.c=0;
		cur.t=1,cur.b=6,cur.e=3,cur.w=4,cur.s=2,cur.n=5;
		
		priority_queue<N> Q; Q.push(cur);
		while(!Q.empty())
		{
			cur=Q.top(); Q.pop();
			
			if(cur.y==gy&&cur.x==gx)
			{
				cout<<cur.c<<endl; break;
			}
			
			rep(d,4)
			{
				int ny=cur.y+dy[d],nx=cur.x+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w)continue;
				
				N nxt=cur; nxt.roll(d);
				nxt.c+=g[ny][nx]*nxt.b;
				if(dp[ny][nx][nxt.t*7+nxt.s]<=nxt.c)continue;
				dp[ny][nx][nxt.t*7+nxt.s]=nxt.c;
				Q.push(nxt);
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 960
A,B,C = map(int,input().split())

if A%2 != 0 and B%2 != 0 and C%2 != 0:
    print(0)
    exit()
if A == B == C:
    print(-1)
    exit()

ans = 0
while A%2 == 0 and B%2 == 0 and C%2 == 0:
    A, B, C = (B+C)//2, (A+C)//2, (A+B)//2
    ans += 1
print(ans)


Measured memory_bytes: 3060
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

int main() {
    ll N;
    cin >> N;
    auto is_black = make_vec_nd(false, N, N);
    bool has_black = false;
    rep(i,0,N) {
        rep(j,0,N) {
            char c;
            cin >> c;
            is_black[i][j] = (c == '#');
            if (is_black[i][j]) {
                has_black = true;
            }
        }
    }
    if (!has_black) {
        cout << -1 << endl;
        return 0;
    }
    ll black_row_cnt = 0;
    vector<bool> is_black_row(N);
    rep(i,0,N) {
        is_black_row[i] = true;
        rep(j,0,N) {
            if (!is_black[i][j]) {
                is_black_row[i] = false;
            }
        }
        if (is_black_row[i]) {
            black_row_cnt++;
        }
    }
    ll black_col_cnt = 0;
    vector<bool> is_black_column(N);
    rep(j,0,N) {
        is_black_column[j] = true;
        rep(i,0,N) {
            if (!is_black[i][j]) {
                is_black_column[j] = false;
            }
        }
        if (is_black_column[j]) {
            black_col_cnt++;
        }
    }
    if (black_row_cnt > 0) {
        cout << N - black_col_cnt << endl;
        return 0;
    }
    ll ans = numeric_limits<ll>::max();
    rep(i,0,N) {
        ll ans_loc = 0;
        ll black_cnt_hori = 0;
        ll black_cnt_vert = 0;
        rep(j,0,N) {
            if (is_black[i][j]) {
                black_cnt_hori++;
            }
            if (is_black[j][i]) {
                black_cnt_vert++;
            }
        }
        if (black_cnt_vert == 0) {
            ans_loc++;
            black_cnt_vert++;
        }
        ans_loc += (N - black_cnt_hori);
        ans_loc += (N - black_col_cnt);
        ans = min(ans, ans_loc);
    }
    cout << ans << endl;
}


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

int main(){
    using namespace std;
    constexpr unsigned long MOD = 998244353;

    string S;
    cin >> S;
    reverse(begin(S), end(S));
    unsigned long K;
    cin >> K;
    K = min<unsigned long>(count(begin(S), end(S), '1'), K);

    vector dp(K + 1, vector(K + 1, 0UL)), tmp(K + 1, vector(K + 1, 0UL));
    dp[0][0] = 1;
    unsigned long cnt{0};
    for(const auto& c : S){
        if(c == '1')++cnt;
        else{
            for(auto&& i : tmp)fill(begin(i), end(i), 0UL);
            for(unsigned long i{0}; i < K; ++i){
                for(unsigned long j{0}; j + i < K; ++j){
                    tmp[j + i + 1][i] = tmp[j + i][i] + dp[j + i][i];
                    if(j >= cnt)tmp[j + i + 1][i] -= dp[j - cnt + i][i];
                }
            }
            for(auto&& i : dp)partial_sum(begin(i), end(i), begin(i));
            for(unsigned long i{0}; i <= K; ++i){
                for(unsigned long j{0}; j <= i; ++j){
                    (dp[i][j] += tmp[i][j]) %= MOD;
                }
            }
            cnt = 0;
        }
    }
    unsigned long ans{0};
    for(auto&& i : dp)partial_sum(begin(i), end(i), begin(i));
    for(unsigned long i{0}; i <= K; ++i)ans += dp[i][i];
    cout << ans % MOD << endl;
    return 0;
}

Measured memory_bytes: 5020
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
        new Main().run();
    }
	int n;
	int[] a;
	boolean[] b;
	public void run(){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			n = scan.nextInt();
			a = new int[n];
			int max = 0;
			for(int i = 0;i < n;i++){
				a[i] = scan.nextInt();
				max += a[i];
			}
			b = new boolean[max+1];
			bruteForce(0,a[0]);
			bruteForce(0,0);
			int q = scan.nextInt();
			int t = 0;
			for(int i = 0;i < q;i++){
				t = scan.nextInt();
				System.out.println((max >= t && b[t])?"yes":"no");
			}
		}
	}
	public void bruteForce(int i,int sum){
		b[sum] = true;
		if(i == n-1){
			return;
		}
		bruteForce(i+1,sum+a[i+1]);
		bruteForce(i+1,sum);
		return;
	}
}

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

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

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

    // start
    int n, m;
    cin >> n >> m;
    cout << (n-1)*(m-1) << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second

struct RLQ{
  int n=(1<<17);
  P data[(1<<18)];
  RLQ(){
  	r(i,(1<<18)){
  		data[i]=P(INT_MAX,INT_MAX);
  	}
  }
  void update(int k,int x){
  	int y=k;
    k+=n-1;
    data[k]=P(x,y);
    while(k>0){
      k=(k-1)/2;
      data[k]=min(data[k*2+1],data[k*2+2]);
    }
  }
  P find(int a,int b,int k=0,int l=0,int r=(1<<17)){
    if(r<=a || b<=l)return P(INT_MAX,INT_MAX);
    if(a<=l && r<=b)return data[k];
    P v1=find(a,b,k*2+1,l,(l+r)/2);
    P v2=find(a,b,k*2+2,(l+r)/2,r);
    return min(v1,v2);
  }
};

int pre[100009];

signed main(){
	memset(pre,-1,sizeof(pre));
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	RLQ R;
	R.update(0,0);
	for(int i=1;i<=n;i++){
		if(s[i]=='1')continue;
		int l=max(i-m,0);
		P p=R.find(l,i);
		R.update(i,p.first+1);
		pre[i] = p.second;
		//cout<<i<<' '<<p.second<<endl;
	}

	vector<int>v;
	int idx=n;

	while(pre[idx]!=-1){
		if(pre[idx]==INT_MAX){
			cout<<-1<<endl;
			return 0;
		}
		v.push_back(abs(idx-pre[idx]));
		idx=pre[idx];
	}
	if(idx!=0){
		cout<<-1<<endl;
		return 0;
	}
	reverse(v.begin(),v.end());
	r(i,(int)v.size()){
		if(i)cout<<' ';
		cout<<v[i];
	}
	cout<<endl;

}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

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

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define MOD (1000000007l)
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)

using namespace std;

void rec(ll pos, ll length, char limit, vector<char> &vec) {
  if (pos == length) {
    for (auto it: vec) cout << it;
    cout << endl;
    return;
  }
  for (char x = 'a'; x <= limit; x++) {
    vec[pos] = x;
    char aaa = x + 1;
    rec(pos + 1, length, max(limit, aaa), vec);
  }
}

void solve() {
  ll N;
  cin >> N;
  vector<char> vec(N);
  rec(0, N, 'a', vec);
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}


Measured memory_bytes: 1536
#include <iostream>
using namespace std;
int main(){
    long long int a,b,k,tmpk;
    cin >>a>>b>>k;
    tmpk=k;k-=a;
    if(k>0){a=0;}
    if(k<1){a-=tmpk;}
    if(k>0){
        tmpk=k;k-=b;
        if(k>0){b=0;}
        if(k<1){b-=tmpk;}
    }
    cout<<a<<" "<<b<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (long long int i = f; i < t; i++)
#define pr(i, f, t) for (long long int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
#define ce(a) cout << (a) << endl
int main()
{
    ll n;
    cin >> n;
    ll a[n];
    rp(i, 0, n)
            cin >>
        a[i];
    ll ma = 0, mi = inf;
    rp(i, 0, n)
    {
        ma = max(ma, a[i]);
        mi = min(mi, a[i]);
    }
    ce(ma - mi);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);
void Min(ll * pos,ll val){*pos=min(*pos,val);}
void Add(ll * pos,ll val){*pos=mod(*pos+val);}
const long double EPS=1E-8;
////////////////////////////////////////




int main(){
    ll n,k;cin>>n>>k;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    bool dp[k+1];memset(dp,0,sizeof(dp));
    rep(i,a[0],k){
        rep(j,0,n-1){
            if(i-a[j]>=0&&!dp[i-a[j]])dp[i]=true;
        }
    }
    //rep(i,0,k)cout<<dp[i]<<" ";cout<<endl;
    if(dp[k])cout<<"First"<<endl;
    else cout<<"Second"<<endl;
    
    return 0;
}


Measured memory_bytes: 384
n, l = map(int, input().split())
m = []
for i in range(1, n+1):
    m.append(l+i-1)
ab = 10**10
apple = 0
for i in range(n):
    if ab > abs(m[i]):
        apple = i
        ab = abs(m[i])
ans = 0
for i in range(n):
    if i == apple: continue
    ans += m[i]
print(ans)


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc061_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string d = Console.ReadLine();

            String[] x = d.Split(' ');

            int[] y = new int[3];

            for(int i=0;i<y.Length;i++)
            {
                y[i] = Convert.ToInt32(x[i]);
            }

            if(y[2]>=y[0]&&y[1]>=y[2])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
            Console.Read();
        }
    }
}


Measured memory_bytes: 13268
fun main(arr: Array<String>) {
    val (n,x) = readLine()!!.split(" ").map { it.toInt() }
    val m = (1..n).map { readLine()!!.toInt() }
    val remain = x - m.sum()
    val ans = n + (remain / m.min()!!)
    println(ans)
}


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

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

using namespace std;

int main(void) {
    int S = 0, W = 0;

    cin >> S >> W;

    if (W >= S) {
        cout << "unsafe" << endl;
    }
    else {
        cout << "safe" << endl;
    }

    return 0;
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;

static long long N, K, ANS = 0, B[200010] = {}, BIT[200010] = {};
vector<long long> V;

void Add(int X, long long Y) {
	for (int i = X; i <= N + 1; i += i & -i) BIT[i] += Y;
}

long long Sum(int X) {
	long long Ret = 0;
	for (int i = X; i > 0; i -= i & -i) Ret += BIT[i];
	return Ret;
}

int main() {
	cin >> N >> K;
	V.push_back(0);
	for (int i = 0; i < N; i++) {
		long long A;
		cin >> A;
		A -= K;
		B[i + 1] = B[i] + A;
		V.push_back(B[i + 1]);
	}
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for (int i = 0; i <= N; i++) {
		int X = lower_bound(V.begin(), V.end(), B[i]) - V.begin() + 1;
		ANS += Sum(X);
		Add(X, 1);
	}
	cout << ANS;
}

Measured memory_bytes: 5104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int main() {
  int n, T;
  cin >> n >> T;
  vector<int> t(n);
  rep(i,n) cin >> t[i];
  int ans = 0;
  int start;
  int cnt = 0;
  for(int i=0; i<n; i++){
    if(cnt==0){
      start = t[i];
    }
    //cout << start << endl;
    if(t[i]+T>=t[i+1] && i<n-1){
      cnt++;
    }
    else{
      cnt = 0;
      ans += t[i]+T-start;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(e) e.begin(), e.end()
#define RALL(e) e.rbegin(), e.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define dbg(x) (cerr << #x << ":" << x << endl)
#define mid (l + r) / 2
#define pii pair <int, int>
#define fi first
#define sc second
#define N 1000000009

using namespace std;
#define int long long
typedef long long lli;
#define n 401
int dist[n][n];
char mp[n][n];

signed main(){
	ios::sync_with_stdio(0);

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i == j) continue;
			dist[i][j] = INT_MAX;
		}
	}

	int h, w;
	cin >> h >> w;

	for(int i=1; i<=h; i++){
		string s;
		cin >> s;
		for(int j=1; j<=w; j++){
			mp[i][j] = s[j-1];
			if(mp[i][j] != '.') continue;
			int id1 = (i-1)*w + j;
			if(i > 1 and mp[i-1][j] == '.'){
				int id2 = (i-2)*w + j;
				dist[id1][id2] = 1;
				dist[id2][id1] = 1;
			}
			if(i < h and mp[i+1][j] == '.'){
				int id2 = (i+1)*w + j; 
				dist[id1][id2] = 1;
				dist[id2][id1] = 1;
			}
			if(j > 1 and mp[i][j-1] == '.'){
				int id2 = (i-1)*w + j-1;
				dist[id1][id2] = 1;
				dist[id2][id1] = 1;
			}
			if(j < w and mp[i][j+1] == '.'){
				int id2 = (i-1)*w + j+1;
				dist[id1][id2] = 1;
				dist[id2][id1] = 1;
			}
		}
	}

	for(int k=0; k<n; k++){
		for(int j=0; j<n; j++){
			for(int i=0; i<n; i++){
				if(dist[i][k] + dist[k][j] < dist[i][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}

	int res = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(dist[i][j] == INT_MAX) continue;
			res = max(res, dist[i][j]);
		}
	}

	cout << res;

	return 0;
}

Measured memory_bytes: 1536
import javax.print.DocFlavor;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.function.BiConsumer;

public class Main {

    //グローバル変数を定義

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        String last = sc.next();
        boolean isInRule = true;
        ArrayList<String> already = new ArrayList<>();
        already.add(last);

        for(int i=1; i<n; i++){
            String input = sc.next();
            if(last.charAt(last.length()-1) != input.charAt(0)){
                isInRule = false;
                break;
            }
            if(already.contains(input)){
                isInRule = false;
            }
            already.add(input);
            last = input;
        }

        if(isInRule){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
long long N,A[100010]={};
long long cnt=0;

long long pow1(long long a,long long b){
  long long ans=1;
  if(b==0){
    return 1;
  }
  else{
    for(long long i=0;i<b;i++){
      ans = a*ans;
      ans %= 1000000007; ////
    }
    return ans;
  }
}

//char op;
int main(){
  cin >> N;
  for(long long i=0;i<N;i++){
    cin >> A[i];

  }
  sort(A,A+N);
  if(N%2==0){
    for(long long i=0;i<N;i+=2){
      if(A[i]==i+1 && A[i+1]==i+1) cnt++;
      else break;
    }
    if(cnt==N/2){
      cout << pow1(2,N/2)%(pow1(10,9)+7) << endl;
      return 0;
    }
  }
  else{
    if(A[0]==0){
      for(long long i=1;i<N;i+=2){
        if(A[i]==i+1 && A[i+1]==i+1) cnt++;
        else break;
      }
      if(cnt==(N-1)/2){cout << pow1(2,(N-1)/2)%(pow1(10,9)+7) << endl;
        return 0;
      }
    }
  }
  cout << 0 << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int table[200005];
bool ans[200005];

void pre_kmp(vector<ll> b, int n) {
  table[0] = -1;
  for(int i = 1; i <= n; i++) {
    int k = table[i-1];

    while(k >= 0) {
      if(b[k] == b[i-1]) break;
      else k = table[k];
    }
    table[i] = 1 + k;
  }
}

void kmp(vector<ll> a, vector<ll> b, int n) {
  int m = b.size();

  for(int i = 0, k = 0; i < 2 * n; i++) {
    while(k >= 0 && a[i] != b[k]) {
      k = table[k];
    }
    if(++k == m) {
      ans[i-m+1] = true;
      k = table[k];
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];

  vector<ll> A(2*n);
  vector<ll> B(n);

  for(int i = 0; i < n; i++) {
    if(i == n-1) {
      A[i] = a[0] ^ a[i];
      A[i+n] = A[i];
    }
    else {
      A[i] = a[i] ^ a[i+1];
      A[i+n] = A[i];
    }
  }
  for(int i = 0; i < n; i++) {
    if(i == n-1) {
      B[i] = b[0] ^ b[i];
    }
    else B[i] = b[i] ^ b[i+1];
  }
  //  for(int i = 0; i < 2*n; i++) cout << A[i] << endl;

  pre_kmp(B,n);
  kmp(A,B,n);
  // for(int i = 0; i < n; i++) cout << ans[i] << endl;

  for(int i = 0; i < n; i++) {
    if(ans[i]) {
      cout << i <<' '<< (a[i] ^ b[0]) << endl;
    }
  }
}
  
  
    


Measured memory_bytes: 13868
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) begin(s),end(s)
#define ITE(c) typeof((c).begin())
#define VIEW(dat) for(auto v : dat){cout<<v<<endl;}
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))


const int INF=1<<24;

using namespace std;

string valOf(int n){ stringstream ss;ss<<n;return ss.str();}
int    valOf(string s){return atoi(s.c_str());}
int    valOf(char s){return (unsigned int)(s - '0');}

int main(){
	int n, m, s;
	vector<int> a, b;
	
//	ifstream cin("in.txt");
	
	while(cin>>n>>m,n||m){
		int  A=0, B=0;
		a.clear();b.clear();
		rep(i,n){
			cin>>s;
			A+=s;
			a.pb(s);
		}
		rep(i,m){
			cin>>s;
			B+=s;
			b.pb(s);
		}
		sort(ALL(a));
		sort(ALL(b));
		
		int p,q;
		p=q=INF;
		rep(i,n){
			rep(j,m){
				if(A-a[i]+b[j]==B-b[j]+a[i]&&b[j]+a[i]<p+q){
					p=a[i];
					q=b[j];
				}
			}
		}
		if(p==INF){
			cout<<"-1"<<endl;
		}else{
			cout<<p<<" "<<q<<endl;
		}
	}
}

Measured memory_bytes: 1224
import java.util.*;class Main{public static void main(String[]z){Scanner s=new Scanner(System.in);String r;for(int m,t;(m=s.nextInt())>0;System.out.println(r))for(r="NA",t=0;t++<12;)if((m-=s.nextInt()-s.nextInt())<=0&&r=="NA")r=""+t;}}

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

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

using ll = long long;
using pii = pair<int, int>;
using Vi = vector<int>;

int main() {
  string s;
  cin >> s;
  int c = 0;
  rep(i, 3){
    if(s[i]-'0' == 1){
      c++;
    }
  }
  cout << c << endl;
  
}

Measured memory_bytes: 3564
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <ctime>
#include <random>

#define ll long long
#define ld long double
#define mod 1000000007
using namespace std;
//ifstream cin("input.txt"); ofstream cout("output.txt");
//ifstream cin("umbrella.in"); ofstream cout("umbrella.out");

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	
	ll d, n;
	cin >> d >> n;
	for (int i = 1; i <= 1e7; i++) {
		int x = i;
		int k = 0;
		while (x % 100 == 0) {
			x /= 100;
			k++;
		}
		if (k == d) {
			n--;
			if (n == 0) {
				cout << i;
				return 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define INF 999999999
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using llong = long long;
using namespace std;

int main(){
    llong n,w[102],s[3]={};
    cin >> n;
    rep(i,n){
        cin >> w[i];
        s[0] += w[i];
    }
    
    llong ans=s[0];
    rep(i,n){
        s[0] -= w[i];
        s[1] += w[i];
        ans = min(ans,abs(s[0]-s[1]));
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                          
using namespace std;    
long long n,m,x[100005],a,ans=1e16+7,b; 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n-m+1;i++)
	{
		b=x[i+m-1]-x[i];
		if(x[i]>=0) b=abs(x[i+m-1]);
		else if(x[i+m-1]<=0) b=abs(x[i]);
		else a=min(abs(x[i]),abs(x[i+m-1])),b+=a;
		ans=min(ans,b);
	}
	cout<<ans;
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll n, m = 1000; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    rep(i, n-1) {
        if(a[i]<a[i+1]) {
            ll kabu = m/a[i];
            m = m+(a[i+1]-a[i])*kabu;
        }
    }
    cout << m << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 3628
use proconio::input;

fn main() {
	input!(s1: String);
	input!(s2: String);
	input!(s3: String);

	println!("{}{}{}",
		s1.to_uppercase().chars().nth(0).unwrap(),
		s2.to_uppercase().chars().nth(0).unwrap(),
		s3.to_uppercase().chars().nth(0).unwrap()
	);
}


Measured memory_bytes: 2204
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>

#define int long long

using namespace std;

signed main() {
	int n;
	cin >> n;
	int m = 0;
	for (int i = 0; i < n; i++) {
		int n, k;
		cin >> n >> k;
		while (n % k != 0) {
			int c = n / k + 1;
			if (n % k > c) {
				n -= ((n % k) / c) * c;
			}
			else {
				n -= n / k + 1;
			}
		}
		n /= k;
		m ^= n;
	}
	if (m == 0) {
		cout << "Aoki";
	}
	else {
		cout << "Takahashi";
	}
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 100005;


int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif
   int n;
   cin>>n;
   unordered_map<int,int>a;
   for(int i=0;i<n;i++){
     int x;
     cin>>x;
     a[x]++;
   }
   int m;
   cin>>m;
   unordered_map<int,int>b;
   for(int i=0;i<m;i++){
     int x;
     cin>>x;
     b[x]++;
   }
   bool fail=false;
   for(auto pr:b){
     if(a.find(pr.first)==a.end()||a[pr.first]<pr.second){fail=true;break;}
   }
   if(fail)cout<<"NO"<<endl;
   else cout<<"YES"<<endl;
   return 0;
}


Measured memory_bytes: 16712
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key){
    return u;
  }
  else if (k < u->key){
    return treeSearch(u->left,k);
  }
  else return treeSearch(u->right,k);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = 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(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}

void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    if(u->left != NIL)preorder(u->left);
    if(u->right != NIL)preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root,x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(com[0] == 'i'){
      scanf("%d", &x);
      insert(x);
    } 
else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
   }
  }

  return 0;
}

Measured memory_bytes: 19364
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


void work(){
	ll n,d,a,b,res=0;
	cin>>n>>d;
	for(ll i=0;i<n;i++){
		scanf("%lld%lld",&a,&b);
		if(a*a+b*b<=d*d) res++;
	}
	cout<<res<<endl;
	return ;
}

int main(){
	//work();
//freopen("C:\\Users\\lenovo\\Desktop\\in.txt","r",stdin);
	work();
	return 0;
}


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

int main(){
	//入力
	ll N,M; cin>>N>>M;
	vector<vector<ll>> s(M);
	rep(i,M){
		ll k; cin>>k;
		rep(j,k){
			ll a; cin>>a;a--;
			s[i].push_back(a);
		}
	}
	vll p(M); rep(i,M) cin>>p[i];
	
	ll ans=0;
	for(ll bit=0;bit<(1<<N);bit++){
		bool ok = true;
		rep(i,M){
			ll con=0;
			for (auto v : s[i]) {
                if (bit & (1<<v)) ++con;
            }
			if(con%2!=p[i]) ok=false;
		}
		if(ok)ans++;
	}
	
	//出力
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[100005];
int main() {
  cin >> n;
  for (int i = 0; i < n + 1; i++)
    cin >> a[i];
  ll cnt = 0;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    ll temp = min(a[i], x);
    cnt += temp;
    x -= temp;
    a[i] -= temp;
    cnt += min(x, a[i + 1]);
    a[i + 1] -= min(a[i + 1], x);
  }
  cout << cnt << endl;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = []
for i in range(m):
    b_list.append(list(map(int,input().split())))
    
    
b_list.sort(key=lambda x: x[1],reverse=True)
cnt = 0
for i in range(m):
    for j in range(b_list[i][0]):
        if cnt > n:
            break
        a_list.append(b_list[i][1])
        cnt += 1
    
a_list.sort()
print(sum(a_list[::-1][0:n]))

Measured memory_bytes: 34512
#include <stdio.h> 

int main(void)
{	
	int n, m, l, i, j, k;
	int a[100][100], b[100][100];
	long c[100][100] = {0};

	scanf("%d %d %d",&n, &m, &l);

	for(i=0; i<n; i++)
	{
		for(j=0; j<m; j++)
		{
			scanf("%d",&a[i][j]);
		}
	}

	for(i=0; i<m; i++)
	{
		for(j=0; j<l; j++)
		{
			scanf("%d",&b[i][j]);
		}
	}

	for(i=0; i<n; i++)
	{
		for(j=0; j<m; j++)
		{
			for(k=0; k<l; k++)
			{
				c[i][k] = c[i][k] + a[i][j] * b[j][k];
			}
		}
	}

	for(i=0; i<n; i++)
	{
		for(j=0; j<l; j++)
		{
			printf("%ld", c[i][j]);

			if(l-1 == j)
			{
				printf("\n");
			}
			else
			{
				printf(" ");
			}

		}
	}

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define C 10007
typedef unsigned long long int ull;

vector<ull> power_cache;

ull power(int p) {
    return power_cache[p];
}

int n, m;
string s;
int li, ri;

void init() {
    cin >> n >> m >> s;
    li = ri = 0;
    power_cache.resize(n);
    power_cache[0] = 1;
    for (int i = 1; i < n; i++) {
        power_cache[i] = power_cache[i-1] * C;
    }
}


map<int, map<int, ull> > cache;

ull calc_hash() {
    ull hash = s[li];
    for (int i = li+1; i <= ri; i++) 
        hash = hash * C + s[i];
    return hash;
}

void solve() {
    string q;
    set<ull> hashes;
    ull hash;
    cache[li][ri] = s[0];
    for (int i = 0; i < m; i++) {
        cin >> q;
        if (q == "R++") {
            ri++;
            if (cache[li][ri] != 0) {
                hash = cache[li][ri];
            } else if (cache[li][ri-1] != 0) {
                hash = cache[li][ri-1] * C + s[ri];
            } else {
                hash = calc_hash();
            }
        } else if (q == "R--") {
            ri--;
            if (cache[li][ri] != 0) {
                hash = cache[li][ri];
            } else {
                hash = calc_hash();
            }
        } else if (q == "L++") {
            li++;
            if (cache[li][ri] != 0) {
                hash = cache[li][ri];
            } else if (cache[li-1][ri] != 0) {
                hash = cache[li-1][ri] - s[li-1] * power(ri-li+1);
            } else {
                hash = calc_hash();
            }
        } else {
            li--;
            if (cache[li][ri] != 0) {
                hash = cache[li][ri];
            } else if (cache[li+1][ri] != 0) {
                hash = cache[li+1][ri] + s[li] * power(ri-li);
            } else {
                hash = calc_hash();
            }
        }
        cache[li][ri] = hash;
        hashes.insert(hash);
    }

    cout << hashes.size() << endl;
}

int main() {
    init();
    solve();
    return 0;
}

Measured memory_bytes: 49256
#include<iostream>

int main(void){
	int N;
	int *buf;
	std::cin >> N;
	buf = new int[N];

	for(int i = 0; i < N; i++){
		std::cin >>buf[i];
	}

	int min = buf[0];
	int max = buf[0];

	for(int i = 1; i < N; i++){
		if(min > buf[i]){
			min = buf[i];
		}
		else if(max < buf[i]){
			max = buf[i];
		}
	}
	std::cout << max - min;

	delete[] buf;

	return 0;
}

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

using namespace std;


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

int tb[7][5] = {
	{},
	{ 3, 5, 4, 2, 6},
	{ 3, 1, 4, 6, 5},
	{ 6, 5, 1, 2, 4},
	{ 1, 5, 6, 2, 3},
	{ 3, 6, 4, 1, 2},
	{ 4, 5, 3, 2, 1},
};

int main()
{

	int n;
	while (cin >> n && n){

		const int M = 110;
		int d[M * 3][M * 3];
		int a[M * 3][M * 3];
		memset(d, 0, sizeof d);
		memset(a, 0, sizeof a);
		for (int i = 0; i < n; i++){
			int t, f;
			cin >> t >> f;
			int x = M, y = M;


			while (1){
				int dir;
				for (int j = 0; j < 4; j++){
					if (tb[t][j] == f)dir = j;
				}

				int tj = -1, Max = 0;
				for (int j = 0; j < 4; j++){
					if (tb[t][(j + dir) % 4] >= 4 && tb[t][(j + dir) % 4] >= Max){
						if (d[x + dx[j]][y + dy[j]] < d[x][y]){
							tj = j;
							Max = tb[t][(j + dir) % 4];
						}
					}
				}

				if (tj == -1){
					d[x][y]++;
					a[x][y] = t;
					break;
				}

				x += dx[tj], y += dy[tj];
				if (tj == 0){
					f = t; t = tb[t][(tj + 2 + dir)%4];
				}
				if (tj == 1){
					t = tb[t][(tj + 2 + dir) % 4];
				}
				if (tj == 2){
					f = tb[t][4]; t = tb[t][(tj + 2 + dir) % 4];
				}
				if (tj == 3){
					t = tb[t][(tj + 2 + dir) % 4];
				}

			}

		}

		int ans[7]; memset(ans, 0, sizeof ans);
		for (int i = 0; i < M * 3; i++)
			for (int j = 0; j < M * 3; j++){
				ans[a[i][j]]++;
			}
		for (int i = 1; i <= 6; i++){
			if (i == 6)
				cout << ans[i] << endl;
			else
				cout << ans[i] << " ";
		}
		
	}


	return 0;
}

Measured memory_bytes: 2016
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int main (void) {
int N;
scanf("%d",&N);
char S[N];
scanf("%s",S);
char txt[]="ABC";
int count=0;
int res =0;

 for (int i=0;i<=N-strlen(txt);i++){

    for (int j=0;j<strlen(txt);j++){
        if (S[i+j]==txt[j])count++;
        if (count==3 || S[i+j]!=txt[j]) break;
    }
    if (count == strlen(txt)) res++;
    count=0;
 }
 printf("%d",res);


return EXIT_SUCCESS;
}


Measured memory_bytes: 128