akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int mod = 2019;

int main(void){
    ll L, R;
    cin >> L >> R;
    
    if(R - L + 1 >= 2019){
        cout << 0 << endl;
        return 0;
    }
    for(ll i = L; i <= R; ++i){
        if(i % mod == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    
    int ans = 2020;
    for(ll i = L; i < R; ++i){
        for(ll j = i + 1; j <= R; ++j){
            ll temp = (i * j) % mod;
            ans = min(ans, (int)temp);
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <string>
#include<map>
using namespace std;
typedef long long ll;
typedef long long ld;

int main() {
	string s;
	cin >> s;
	ll ans = 0;
	int v = 0;
	for (int i = s.size() - 1; i >= 0; --i) {
		if (s[i] == 'B'){
			ans += s.size() - i - 1 - v;
			v++;
		}
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 640
import sys
import io


def run(input: io.TextIOBase, output: io.TextIOBase):
    n = int(input.readline())
    k = int(input.readline())
    x = int(input.readline())
    y = int(input.readline())

    if n < k:
        r = n*x
    else:
        r = k*x+(n-k)*y

    output.write(str(r) + '\n')


if __name__ == '__main__':
    run(sys.stdin, sys.stdout)


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

vector<vector<int>> G(10);
int ans = 0;
int n, m;

void dfs(int now, vector<bool> &visited) {

  visited[now] = true;

  bool stop = true;
  for (int i = 0; i < G[now].size(); i++) {
    if (!visited[G[now][i]]) stop = false;
  }
  if (stop) {
    bool ok = true;
    rep (i, n) {
      if (!visited[i]) {
        ok = false;
      }
    }
    if (ok) ans++;
    return ;
  }
  
  for (int i = 0; i < G[now].size(); i++) {
    if (!visited[G[now][i]]) {
      dfs(G[now][i], visited);
      visited[G[now][i]] = false;
    }
  }
}

int main(void) {
  
  cin >> n >> m;

  

  rep (i, m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<bool> visited(n, false);
  dfs(0, visited);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

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

    vector<int> G[N];
    int a[M], b[M];
    for(int i=0; i<M; i++){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }

    priority_queue<P, vector<P>, greater<P>> q;
    q.push(P(0, 0));
    int dp[N];
    fill(dp, dp+N, 1000000005);
    dp[0] = 0;
    while(!q.empty()){
        int now = q.top().second;
        int d = q.top().first;
        q.pop();
        if(dp[now] != d) continue;

        for(auto next: G[now]){
            if(dp[next] > dp[now] + 1){
                dp[next] = dp[now] + 1;
                q.push(P(dp[now]+1, next));
            }
        }
    }

    bool fl = true;
    for(int i=0; i<N; i++){
        if(dp[i] == 1000000005) fl = false;
    }

    if(!fl){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    int ans[N];
    for(int i=0; i<M; i++){
        if(dp[b[i]] == dp[a[i]] - 1) ans[a[i]] = b[i];
        if(dp[a[i]] == dp[b[i]] - 1) ans[b[i]] = a[i];
    }

    for(int i=1; i<N; i++){
        cout << ans[i] + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 12532
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define ll long long
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0)
#define sz(a) (a).size()
#define triple pair<pill, ll>
using namespace __gnu_pbds;
using namespace std;
typedef gp_hash_table<int, short, hash<int>, equal_to<int>, direct_mod_range_hashing<int>, linear_probe_fn<>, hash_standard_resize_policy<hash_prime_size_policy, hash_load_check_resize_trigger<true>, true>> gp;

const ll N = 1e3 + 10;
const ll big = 1e18;
const ll block = 800;
const ll mod = 1e6;

ll n, m;
ll x, y;
ll e1, e2;
char c[N][N];
ll rst[N][N];

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

/*
xxxxx
xx.xx
x...x
xx.xx
xxxxx
-2 +2
if(i != 0 && j != 0)

*/

void bfs() {
	deque<pill> f;
	rst[x + 1][y + 1] = 1;
	f.push_front({x + 1, y + 1});
	while(f.size()) {
		pill z = f.front();
		f.pop_front();
		for(int i = -2; i < 3; i++) {
			for(int j = -2; j < 3; j++) {
				ll k = z.f - i, l = z.s - j;
				if(c[k][l] != '.' || (!i && !j))
					continue;
				if((!i && abs(j) == 1) || (!j && abs(i) == 1)) {
					if(!rst[k][l] || rst[k][l] > rst[z.f][z.s]) {
						rst[k][l] = rst[z.f][z.s];
						f.push_front({k, l});
					}
				}
				else {
					if(!rst[k][l] || rst[k][l] > rst[z.f][z.s] + 1)
						rst[k][l] = rst[z.f][z.s] + 1,
						f.push_back({k, l});
				}
			}
		}
	}
	cout << rst[e1 + 1][e2 + 1] - 1;
}

int main() {
	cin >> n >> m;
	cin >> x >> y;
	cin >> e1 >> e2;
	for(int i = 2; i <= n + 1; i++) {
		for(int j = 2; j <= m + 1; j++) {
			cin >> c[i][j];
		}
	}
	bfs();
}

/*

*/


Measured memory_bytes: 12492
#include<bits/stdc++.h>;
using namespace std;
//#define LOCAL
typedef long long ll;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
int a[5];
int main(){
#ifdef LOCAL
     freopen("in.txt", "r", stdin);
     //freopen("out.txt", "w", stdout);
#else
 fastIO;
#endif
//***************************//**************************//******************************

for(int i=0;i<5;i++){
    cin>>a[i];
}
for(int i=0;i<5;i++){
    if(a[i]==0){
        cout<<i+1<<endl;
        break;
    }
}
}


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

void input(int& rnAchieve, vector<int>& rvnPrice, vector<vector<int>>& rvvnSkill)
{
  int nPriceSiz, nSkillSiz;
  cin >> nPriceSiz >> nSkillSiz >> rnAchieve;
  rvnPrice.resize(nPriceSiz);
  rvvnSkill.resize(nPriceSiz, vector<int>(nSkillSiz));

  for (int ny = 0; ny < rvvnSkill.size(); ny++)
  {
    cin >> rvnPrice[ny];

    for (int nx = 0; nx < rvvnSkill[ny].size(); nx++)
      cin >> rvvnSkill[ny][nx];
  }
}

int calcMinPriceSkillup(int nAchieve, const vector<int> cnrvnPrice, 
                      const vector<vector<int>>& cnrvvnSkill)
{
  int nMinPrice = INT_MAX;

  for (int nCtl = 0; nCtl < ( 1 << cnrvnPrice.size() ); nCtl++)
  {
    int nPrice = 0;
    vector<int> vnSumSkill(cnrvvnSkill[0].size());

    for (int ny = 0; ny < cnrvnPrice.size(); ny++)
      if (nCtl & ( 1 << ny ))
      {
        for (int nx = 0; nx < cnrvvnSkill[ny].size(); nx++)
          vnSumSkill[nx] += cnrvvnSkill[ny][nx];

        nPrice += cnrvnPrice[ny];
      }

    bool bRslt = true;

    for (int nSumSkill : vnSumSkill)
      if (nSumSkill < nAchieve)
      {
        bRslt = false;
        break;
      }

    if (bRslt)
      nMinPrice = min(nMinPrice, nPrice);
  }
  if (nMinPrice == INT_MAX)
    return -1;
  else
    return nMinPrice;
}
  
int main()
{
  int nAchieve;
  vector<int> vnPrice;
  vector<vector<int>> vvnSkill;

  input(nAchieve, vnPrice, vvnSkill);
  cout << calcMinPriceSkillup(nAchieve, vnPrice, vvnSkill) << endl;

  return 0;
}

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

using namespace std;

#define DEBUG
#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1)
	{
		cerr << name << " = " << arg1 << endl;
	}
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args)
	{
		const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " = " << arg1 << " || ";
		__f(comma+1, args...);
	}
#else
#define debug(...)
#endif

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"

// priority_queue<ll, vector<ll>, less<ll>>pq;     // Max Heap
// priority_queue<ll, vector<ll>, greater<ll>>pq;  // Min Heap

//K-th smallest
//cout << k << "kth (1 based indexing) smallest: " << *A.find_by_order(k - 1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

int main()
{
	FAST_IO;

 	ll k;
 	cin >> k;
 	string a, b = "";
 	cin >> a;
 	ll n = a.length();
 	if(n <= k) cout << a << endl;
 	else
 	{
 		for(int i=0;i<k;i++) b += a[i];
 		b += "...";
 		cout << b << endl;
 	}   
    return 0;
}

Measured memory_bytes: 3652
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void){
   int a[10];
   int b[10];
   for(int i = 0;i < 10;i++){
      scanf("%d",&a[i]);
   }
   sort(a,a+10);
   for(int i = 0;i < 10;i++){
      scanf("%d",&b[i]);
   }
   sort(b,b+10);
   printf("%d %d\n",a[9]+a[8]+a[7],b[9]+b[8]+b[7]);
   return 0;
}

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

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

const ll INF = 1LL << 60;
const int MOD = 1000000007;

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

int h, w, n;
vector<string> s;
vector< vector<int> >steps;
int power;

void bfs(int sx, int sy, int gx, int gy){
    queue<P> q;
    q.push(make_pair(sx, sy));

    while(!q.empty()){
        int x, y;
        tie(x, y) = q.front(); q.pop();
        if(x == gx && y == gy) return;
        for(int k = 0; k < 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
            if(s[ny][nx]=='#') continue;
            if(steps[ny][nx] != 0) continue;
            steps[ny][nx] = steps[y][x] + 1;
            q.emplace(nx, ny);
        }
    }
    return;
}

int main() {
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif

    cin >> h >> w;
    s.resize(h);
    for(int i = 0;i < h; i++){
        cin>>s[i];
    }
    int num = 1;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(s[i][j] == '#'){
                ++num;
            }
        }
    }

    steps.resize(h);
    for(int j = 0; j < h; j++){
        steps[j].resize(w);
    }

    int sx = 0;
    int sy = 0;
    int gx = w - 1;
    int gy = h - 1;
    bfs(sx, sy, gx, gy);

    int ans = -1;
    if(steps[gy][gx] != 0){
        ans = h * w - num - steps[gy][gx];
    }

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



Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
        int r,c;
        scanf("%d %d",&r,&c);
        int sheet[r+1][c+1];
        for(int i=0;i<r+1;i++){
            for(int j=0;j<c+1;j++){
                    sheet[i][j]=0;
                }
        }
        for(int i=0;i<r;i++){
                for(int j=0;j<c;j++){
                        scanf("%d",&sheet[i][j]);
                        sheet[i][c]+=sheet[i][j];
                        sheet[r][j]+=sheet[i][j];
                        sheet[r][c]+=sheet[i][j];
                }
        }
        for(int i=0;i<r+1;i++){
                for(int j=0;j<c+1;j++){
                        if(j<c)printf("%d ",sheet[i][j]);
                        if(j==c)printf("%d\n",sheet[i][j]);
                }
        }
        return 0;
}

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

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a>b){
    if(c<a&&c>b){
      cout<<"Yes"<<endl;
    }
    else{
      cout<<"No"<<endl;
    }
  }
  else{
    if(a<c&&b>c){
      cout<<"Yes"<<endl;
    }
    else{
      cout<<"No"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

const int maxn = 300 * 1000;
const int inf = 1000 * 1000 * 1000 + 1;

int n;
vector<int> g[maxn];
int a[maxn];
int d[maxn];
int ans[maxn];
bool used[maxn];

void DFS(int v, int len) {
  if (used[v]) return;
  used[v] = true;


  int l = 0;
  int r = n + 1;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (a[v] > d[m]) l = m; else r = m;
  }

  int prevD = d[l + 1];
  d[l + 1] = a[v];

  if (d[len + 1] < inf) len++;
  ans[v] = len;

  for (int to : g[v]) DFS(to, len);
  d[l + 1] = prevD;
}

int main()
{
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  for (int i = 1; i < n + 10; ++i) d[i] = inf;
  DFS(0, 0);
  for (int i = 0; i < n; ++i) cout << ans[i] << endl;
  cout << endl;

  return 0;
}


Measured memory_bytes: 30920
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def g(n):
    return (1 + n) * n // 2

def solve():
    N = II()
    ans = 0
    for j in range(1, N+1):
        ans += g(N // j) * j
    print(ans)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 9184
# after pdf explanation
n = gets.strip.to_i
zx = 0
wn = zn = 1000000001
wx = -1000000001
n.times do
  x,y = gets.strip.split.map(&:to_i)
  z = x + y
  w = x - y
  zx = z if z > zx
  zn = z if z < zn
  wx = w if w > wx
  wn = w if w < wn
end
p [zx-zn,wx-wn].max

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

int main() {
  int n,m,ans=0;
  cin >> n >> m;

  vector<string>table_a(n);
  vector<string>table_b(n);

  for (int i = 0; i < n; i++) {
    cin >> table_a.at(i);
  }

  for (int i = 0; i < n; i++) {
    cin >> table_b.at(i);
  }  

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (table_a.at(i).at(j) != table_b.at(i).at(j)) {
        ans++;
      }
    } 
  }
  cout << ans << endl;
}





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

#define    int               long long int
 #define    bp(x)         __builtin_popcount(x)
#define  ld         long double
 #define  f(i,j,n)            for(int i = j; i <= n; i++)
#define  r(i,n,j)       for(int i = n; i >= j; i--)
 #define  all(container)       container.begin() , container.end()
#define  sz(container)   (int)container.size()
 #define  ff             first
#define  ss             second
 #define  pii      pair <int , int>
#define  sp(x)       setprecision(x)
#define  mod  1000000007
#define  endl  "\n"
 #define  pb    push_back
#define  mp    make_pair
 #define  T     int ttt; cin >> ttt; while(ttt--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int power(int x, int y, int p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)  
    {     
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res; 
}
vector<int>v[100005];
int b[100005],w[100005];

void dfs(int r,int p){
    int x=1,y=1;
    for(auto i : v[r])
        if(i!=p){
            dfs(i,r);
            x=(x*(w[i]+b[i]))%mod;
            y=(y*w[i])%mod;
        }
    b[r]=y,w[r]=x;
}

int32_t main()
{
    fast
    int x,y,n;  cin>>n;
    f(i,1,n-1){
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,1);
    cout<<(b[1]+w[1])%mod;
}

Measured memory_bytes: 18828
#include <stdio.h>
int main(){
	int n,m,d,i,j,k,au=0,space=0;
	char kyu[101][101];
	scanf("%d%d%d",&n,&m,&d);
	for(i=0;i<n;i++){
		scanf("%s",kyu[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			for(k=0;k<d;k++){
				if(kyu[i][j+k]=='.'){
					au++;
					if(au==d){
						space++;
						au=0;
					}
				}
				else if(kyu[i][j+k]!='.'){
					au=0;
					break;
				}
			}
		}
	}
	for(j=0;j<m;j++){
		for(i=0;i<n;i++){
			for(k=0;k<d;k++){
				if(kyu[i+k][j]=='.'){
					au++;
					if(au==d){
						space++;
						au=0;
					}
				}
				else if(kyu[i+k][j]!='.'){
					au=0;
					break;
				}
			}
		}
	}
	printf("%d\n",space);
	return 0;
}



Measured memory_bytes: 2104
# gets stdin
n = gets.rstrip.to_i
happies = n.times.map{gets.rstrip.split.map(&:to_i)}

dp = Array.new(n+1){Array.new(3, 0)}

0.upto(n-1) do | i |
  dp[i+1][0] = [dp[i][1] + happies[i][0], dp[i][2] + happies[i][0]].max
  dp[i+1][1] = [dp[i][0] + happies[i][1], dp[i][2] + happies[i][1]].max
  dp[i+1][2] = [dp[i][0] + happies[i][2], dp[i][1] + happies[i][2]].max
end
p dp[-1].max

Measured memory_bytes: 16124
#include<iostream>
#include<string.h>
using namespace std;

int main()
{
    int n;
    string s;
    cin>>n>>s;
    for(int i=0; i<s.length(); i++)
    {
        char ch=s[i]+n;
        if(ch<'A' || ch>'Z')
        {
            ch=s[i];
            for(int i=1; i<=n; i++)
            {
                if(ch=='Z') ch='A';
                else ch++;

            }

        }
        s[i]=ch;
    }
    cout<<s<<endl;
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  int n,k,t,i;
int main()
{
	
	cin>>n>>k;
	
	t=n;n=1;
	for (i=1;i<=t;i++)
	  if (n<k)
	    n+=n;
	  else
	    n+=k;
	    
	cout<<n;
	
}

Measured memory_bytes: 256
#include<algorithm>
#include<cstdio>
using namespace std;

int n, ans;
int pr[100];

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int x = i;
        for (int j = 2; j <= i; j++) { 
            while (x % j == 0) {
                pr[j - 1]++;
                x /= j;
            }
            if (x == 1) break;
        }
    }

    sort(pr, pr + n);
    int a = pr + n - lower_bound(pr, pr + n, 24);
    int b = pr + n - lower_bound(pr, pr + n, 14);
    int c = pr + n - lower_bound(pr, pr + n, 4);
    int d = pr + n - lower_bound(pr, pr + n, 2);
    ans += pr + n - lower_bound(pr, pr + n, 74);
    ans += a * (d - 1);
    ans += b * (c - 1);
    ans += c * (c - 1) / 2 * (d - 2);
    printf("%d\n", ans);
    return 0;
} 


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <array>
#include <deque>
#include <bitset>
typedef long long ll;
using namespace std;
#define trace(x) cerr << #x << " is " << x << endl;
 
int main() {
    string s;
    cin >> s;
    int n = s.length();
    string res = "";
    for (int i = 0; i < n; i++) {
        res += 'x';
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();
        int N = S.length;

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < S.length; i++) {
            char ch = S[i];
            if (stack.empty()) {
                stack.push(ch);
            } else {
                if (ch == stack.peek()) stack.push(ch);
                else stack.pop();
            }
        }

        int cnt = N;
        while (!stack.empty()) {
            stack.pop();
            cnt--;
        }

        System.out.println(cnt);

        return;
    }

}


Measured memory_bytes: 28188
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
 

//result = Math.pow(num1, num3)
//StringBuffer str = new StringBuffer(hoge1);
//String hoge2 = str.reverse().toString();
public class Main {
	private static Scanner sc = new Scanner(System.in);
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p(long ans) {System.out.println(ans);};
	//static String eikomoji[]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
	
	
	public static void main(String[] args) {
	int n=sc.nextInt();
	Map<Integer, Integer> map = new HashMap<Integer, Integer>(n);
	boolean a=true;
	for(int i=0;i<n&&a;i++) {
		int A = sc.nextInt();
		
		if(!map.containsKey(A)) {
			map.put(A,1);
		}else {
			a=false;
			
		}
	}
	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	//ArrayList<String> cc = new ArrayList<>(n);
	if(a) {
		p("YES");
	}else {
		p("NO");
	}


	
	
	
	
 }
}

Measured memory_bytes: 96836
#include "bits/stdc++.h"
using namespace std;
 
const int N=200;
 
int n,m,q,arr[N],a[N],b[N],c[N],d[N],ans;
 
void f(int i,int pv)
{
	if(i==n+1)
	{
		int cost=0;
		for(int i=0;i<q;i++)
		{
			if(arr[b[i]]-arr[a[i]]==c[i]) cost+=d[i];
		}
		ans=max(ans,cost);
		return;
	}
	for(int j=pv;j<=m;j++)
	{
		arr[i]=j;
		f(i+1,j);
	}
}
 
int main()
{
	cin>>n>>m>>q;
	for(int i=0;i<q;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
	f(1,1);
	cout<<ans;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int ans = 0;
  int B;
  vector<int> A(N);
  vector<int> C(N-1);
  for(int i=0;i<N;i++) cin >> A[i];
  for(int i=0;i < N;i++){
    cin >> B;
    ans += B;
  }
  for(int i=0;i<N-1;i++) cin >> C[i]; 
  for(int i=0;i < N-1;i++) if(A[i] + 1 == A[i+1]) ans += C[A[i] - 1];
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#define int long long
#define loop(i, a, b) for(int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
const int MOD = 1e9 + 7, INF = 1e9;
using vi = vector <int>;
using vvi = vector <vi>;
//g++ -std==c++14
 
signed main(){
    string s;
    cin >> s;
    int ans = 0;
    rep(i, s.size()){
        if(i % 2 == 0){
            if(s[i] == 'p')
                ans--;
        }
        else{
            if(s[i] == 'g')
                ans++;
        }
    }
    cout << ans << endl;
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

#define N 100010
int n;
//iとM[i].secondをM[i].firstでつなぐ
vector< vector<pii> > M(N, vector<pii>());
vector<bool> used(N, false);
vi mincost(N, inf);

bool cmp1(pair<pii, int> a, pair<pii, int> b) {
	if (a.first.second < b.first.second) {
		return true;
	}
	else if (a.first.second > b.first.second) {
		return false;
	}
	else {
		if (a.first.first < b.first.first) {
			return true;
		}
		else if (a.first.first > b.first.first) {
			return false;
		}
		else {
			if (a.second < b.second) {
				return true;
			}
			else {
				return false;
			}
		}
	}
}

void prim(int s) {
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	int used_cnt = 0;
	mincost[s] = 0;
	pq.push(make_pair(0, s));
	int i;
	while (used_cnt < n) {
		int u;
		pii f;
		while (true) {
			f = pq.top();
			pq.pop();
			u = f.second;
			if (!used[u]) {
				break;
			}
		}
		mincost[u] = f.first;
		for (i = 0; i < M[u].size(); i++) {
			int v = M[u][i].second;
			int c = M[u][i].first;
			pq.push(make_pair(c, v));
		}
		used[u] = true;
		used_cnt++;
	}
}

int main() {
	int i, j;
	cin >> n;
	vector< pair<pii, int> > r(n);
	for (i = 0; i < n; i++) {
		cin >> r[i].first.first >> r[i].first.second;
		r[i].first.first--;
		r[i].first.second--;
		r[i].second = i;
	}
	sort(r.begin(), r.end());
	for (i = 0; i < n - 1; i++) {
		int x1 = r[i].first.first, y1 = r[i].first.second;
		int x2 = r[i + 1].first.first, y2 = r[i + 1].first.second;
		int r1 = r[i].second, r2 = r[i + 1].second;
		M[r1].push_back(make_pair(min(abs(x2 - x1), abs(y2 - y1)), r2));
		M[r2].push_back(make_pair(min(abs(x2 - x1), abs(y2 - y1)), r1));
	}
	sort(r.begin(), r.end(), cmp1);
	for (i = 0; i < n - 1; i++) {
		int x1 = r[i].first.first, y1 = r[i].first.second;
		int x2 = r[i + 1].first.first, y2 = r[i + 1].first.second;
		int r1 = r[i].second, r2 = r[i + 1].second;
		M[r1].push_back(make_pair(min(abs(x2 - x1), abs(y2 - y1)), r2));
		M[r2].push_back(make_pair(min(abs(x2 - x1), abs(y2 - y1)), r1));
	}
	prim(0);
	ll sum = 0;
	for (i = 0; i < n; i++) {
		sum += mincost[i];
	}
	cout << sum << endl;

}

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

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;

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

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

int main(){
  ll N, K;
  cin >> N >> K;
  ll A[N];
  rep(i, N) cin >> A[i];

  repi(i, K, N){ 
    cout << (A[i] > A[i-K] ? "Yes" : "No") << endl;
  }
  return 0;
}



Measured memory_bytes: 5192
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
//const lld MAXN = 1e9;

int main()
{
	string s[3];
	cin >> s[0] >> s[1] >> s[2];
	cout << s[0][0] << s[1][0] << s[2][0] << endl;

	return 0;
}

Measured memory_bytes: 256
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
#define fi   first
#define se   second
using namespace std;
struct P{int x,y;};
P mns(P x,P y){x.x-=y.x,x.y-=y.y;return x;}
ll det(P x,P y){return x.x*1ll*y.y-x.y*1ll*y.x;}
int n;
pair<pair<int,int>,int> p[105];
int U,D,iu[105],id[105],Q,iq[105];
P pu[105],pd[105],pq[105];
double ans[105],PI=6.2831853071795864769;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&p[i].fi.fi,&p[i].fi.se),p[i].se=i;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;++i){
		P a;
		a.x=p[i].fi.fi,a.y=p[i].fi.se;
        while(U>1&&det(mns(pu[U],pu[U-1]),mns(a,pu[U]))>=0)--U;
        pu[++U]=a;
        iu[U]=p[i].se;
    }
    for(int i=1;i<=n;++i){
		P a;
		a.x=p[i].fi.fi,a.y=p[i].fi.se;
        while(D>1&&det(mns(pd[D],pd[D-1]),mns(a,pd[D]))<=0)--D;
        pd[++D]=a;
        id[D]=p[i].se;
    }
    for(int i=1;i<=U;++i)++Q,iq[Q]=iu[i],pq[Q]=pu[i];
    for(int i=D-1;i>1;--i)++Q,iq[Q]=id[i],pq[Q]=pd[i];
    if(Q==2){
    	ans[iq[1]]=ans[iq[2]]=0.5;
    }
    else{
    	pq[Q+1]=pq[1];
    	pq[0]=pq[Q];
    	for(int i=1;i<=Q;++i){
    		P p1=mns(pq[i],pq[i-1]),p2=mns(pq[i+1],pq[i]);
    		double d=acos((p1.x*1.0*p2.x+p1.y*1.0*p2.y)/sqrt(p1.x*1.0*p1.x+p1.y*1.0*p1.y)/sqrt(p2.x*1.0*p2.x+p2.y*1.0*p2.y));
    		ans[iq[i]]=d/PI;
    	}
    }
    for(int i=1;i<=n;++i)printf("%.10lf\n",ans[i]);
    return 0;
}


Measured memory_bytes: 4180
/*ॐॐ*/
/* I have already deleted My old account because somebody stole my code
and i have no idea how. If you are copying this code atleast make it look different.
Change variable names or change some Data structres or anything just make sure MOSS do not
Detect Anything.
Yours Faithfully
Shobhit Yadav */

/* I do not fear this new challenge. Rather like a true warrior I will rise to meet it. 
                                       -Prince Vegeta  */

 /* “Strength is the only thing that matters in this world. Everything else is just a delusion for the weak.” – Vegeta */

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



ll N;
/*ll freq[200005];*/
void solve(){
   /*memset(freq,0,sizeof(freq));*/
   cin>>N;

   cout<<N*N<<'\n';
   

}



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

  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define vi vector<int>
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m-1);i>=(int)(n);i--)
#define rev(i, n) revi(i, n, 0)
#define each(i, n) for(auto&& i: n)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size()) 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin() , (v).rend()
#define dump(x) cerr << #x << "=" << x <<endl
#define gcd __gcd
int lcm(int a, int b){return a / gcd(a, b) * b;}
const int INF = 1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-15;
const double PI = acos(-1);

void solve()
{
	/*--------------------------*/

	int N; cin >> N;
	bool f = true;
	rep(i, N) {
		int a; cin >> a;
		if (a % 2 == 0) {
			if (a % 3 != 0 && a % 5 != 0) {
				f = false;
			}
		}
	}
	if (f) cout << "APPROVED" << endl;
	else cout << "DENIED" << endl;

	/*--------------------------*/
}

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	solve();
}

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

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    S += '.';
    int ans = 0;
    int i = 0;
    while (i<N){
        if (S[i] != S[i+1]) ans += 1;
        i += 1;
    }
    cout << ans << endl;
}

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

int main() {
  long a, b, c, k;
  cin >> a >> b >> c >>k;
  int ans;
  if(k % 2 == 0) {
    ans = a - b;
  } else {
    ans = b - a;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define F          first 
#define S          second
#define mod        1000000007
#define all(x)     x.begin(),x.end()  
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
void comp() {
  ll i,j,k,l,m,n,r;
  cin>>n;
  while(n>0) {
  	if(n%10==7) {
  		cout<<"Yes\n";
  		return;
  	}
  	n/=10;
  }
  cout<<"No\n";
}

int main() {
    speedup;
    ll i=0,t;
    //cin>>t;
    t=1;
    while(t--) {
        comp();
    }
    return 0;
}


Measured memory_bytes: 3648
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

mc = ModComb(2 * N)

ans = mc.nCk(2 * N - 1, N - 1)
if K + 1 < N:
    ans += sum((mod - mc.nCk(N, i)) * mc.nCk(N - 1, i) % mod for i in range(K + 1, N)) % mod

print(ans % mod)

Measured memory_bytes: 50776
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>




int main()
{
	int i,j,k;
	int n;
	int a,b,c;
	int x,z;
	int y[100];
	int frame,slot;

	while(1)
	{
		scanf("%d %d %d %d %d",&n,&a,&b,&c,&x);
		if((n==0)&&(a==0)&&(b==0)&&(c==0)&&(x==0)){break;}
		else
		{
			for(i=0;i<n;i++){scanf("%d",&y[i]);}
			frame=0;
			slot=0;

			if(x==y[0]){slot++;}
			if(slot!=n)
			{

			for(i=0;i<10000;i++)
			{
				if((a*x+b)%c==y[slot])
				{
					slot++;
				}
				x=((a*x+b)%c);
				frame++;
				if(slot==n){break;}
			}
			}
		}
		if(slot==n){printf("%d\n",frame);}
		else{printf("-1\n");}
	}
	return 0;
}
	

Measured memory_bytes: 1040
import sys
def main():
    #s = sys.stdin.readlines()
    N = input() # number of card
    A = sorted(list(map(int,input().split())), reverse = True) # card
    Alice = sum([ a for i,a in enumerate(A) if i%2 == 0 ])
    Bob = sum([ a for i,a in enumerate(A) if i%2 == 1 ])
    print(Alice-Bob)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
N = int(input())
A = list(map(int, input().split()))

def main(A):
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
    
main(A)


Measured memory_bytes: 21768
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
 
#define ll long long int
#define fast ios_base::sync_with_stdio(false)
#define fast_input cin.tie(NULL)
#define fast_output cout.tie(NULL)
#define vi vector<long long int> 
#define pb push_back
#define pa pair<long long int ,long long int> 
#define f(a,x,b) for(int a=x;a<b;a++)
// #define sort(x) sort(x.begin(),x.end());
#define siz(a) (int)a.size()
#define mod 1000000007
#define F first
#define S second
#define um unordered_map<ll,ll>
#define ordered_set tree<pa, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
void solve()
{ 
	ll n;
	cin>>n;
	vector<vector<ll>>has(n,vector<ll>(n));
	f(i,0,n)
	{
		f(j,0,n)
		{
			cin>>has[i][j];
		}
	}
	vector<ll>dp(1<<n +1);
	dp[0]=1;
	for(int i=1;i<=(1<<n);i++)
	{
	    ll ge=__builtin_popcount(i);
       for(int j=0;j<n;j++)
	   {
		   if((i&(1<<j))&&has[ge-1][j])
		   {
              dp[i]+=(dp[i&~(1<<j)]%mod);
		   }
	   }
	//    cout<<dp[i]<<" ";
	   dp[i]%=mod;
	}

	cout<<dp[(1<<n)-1]<<endl;
}
int main() {
	fast;
	fast_input;
	fast_output;
	// ll t;
	// cin>>t;
	// f(i,0,t)
	// {
    //   cout<<"Case #"<<i+1<<":"<<" ";
	     solve();
	// }
	return 0;
}

/*
*/

Measured memory_bytes: 35952
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[100005],a[100005],n,k;
main () {
	cin>>n>>k;
	for (ll i=1; i<=n; i++) {
		cin>>a[i];
		if (i==1) continue;
		dp[i]=1e9;
		for (int j=1; j<=min(k,i-1); j++) 
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
	}
	cout<<dp[n]<<endl;
}

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

int main()
{
	string str;
	int check[8][3] =
	{
		{0,1,2},
		{3,4,5},
		{6,7,8},
		{0,3,6},
		{1,4,7},
		{2,5,8},
		{0,4,8},
		{2,4,6}
	};

	while (cin >> str)
	{
		for (int i = 0; i < 8; i++)
		{
			if (str[check[i][0]] == 'o' && str[check[i][1]] == 'o' && str[check[i][2]] == 'o')
			{
				cout << 'o' << endl;
				break;
			}
			if (str[check[i][0]] == 'x' && str[check[i][1]] == 'x' && str[check[i][2]] == 'x')
			{
				cout << 'x' << endl;
				break;
			}
			if (i == 7) cout << 'd' << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1172
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
LQ = len(Q)
while LQ != 0:
    stan = Q[0][1]
    k = 1
    while LQ != 0:
        if Q[0][0] < stan:
            stan = min(stan,Q.pop(0)[1])
            LQ -= 1
        else:
            ans += 1
            break
print(ans)

Measured memory_bytes: 21700
import statistics
f = statistics.median
N = int(input())

a = [0]*N
b = [0]*N

for i in range(N):
    m, n = map(int, input().split())
    a[i] = m
    b[i] = n

if N % 2 == 1:
    print(int(f(b)-f(a)+1))
else:
    print(int(f(b)*2-f(a)*2+1))

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

using namespace std;

int main(int argc, char *argv[]) {
	string A, B, C;
	cin >> A >> B >> C;
	if (A.back() == B.front() && B.back() == C.front()) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 256
// Crt. 2019-12-28  21:12:49
#include <bits/stdc++.h>
#define N 200005
using namespace std;
#define int long long
typedef long long ll;

int n, m, v, p, a[N];

inline bool check(int x) {
    ll tmp = 1ll * (v - p + 1 - x) * m, mx = a[x] + m;
    for (int i = x + 1; i <= n - p + 1; ++i) {
        if (a[i] > mx) return false;
        tmp -= mx - a[i];
    }
    if (tmp <= 0) return true;
    else return false;
}

signed main() {
#ifdef LOCAL_JUDGE
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n >> m >> v >> p;
    
    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i);

    sort(a + 1, a + n + 1);

    int l = 1, r = n - p + 1, res;

//    cout << check(1) << endl;
//    return 0;

    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }

    cout << n - res + 1 << endl;

    return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 998244353; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;

void solve() {
	int N, M; cin >> N >> M;
	string S; cin >> S;
	int pos = N;
	vector<int>ans;
	while (pos > 0) {
		bool ok = false;
		FORR(d, M + 1, 1) {
			if (pos - d >= 0 && S[pos - d] == '0') {
				pos = pos - d;
				ans.push_back(d);
				ok = true;
				break;
			}
		}
		if (!ok) {
			print(-1); return;
		}
	}
	VREVERSE(ans);
	print_space(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 1480
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	[N, X, T] = input.split(" ");
  	result=Math.ceil(N/X)*T
	console.log(result)
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 30552
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,K;
const int MN = 5000;
const int MK = 5000;
int a[MN];
bool dpl[MN+1][MK];
bool dpr[MN+1][MK];
int main(){
	cin>>N>>K;
	rep(i,N) cin>>a[i];
	dpl[0][0]=1;
	rep(i,N) rep(k,K) if(dpl[i][k]){
		dpl[i+1][k]=1;
		int nk = k+a[i];
		if(nk>=K) continue;
		dpl[i+1][nk]=1;
	}
	dpr[N][0]=1;
	for(int i=N;i>0;i--) rep(k,K) if(dpr[i][k]){
		dpr[i-1][k]=1;
		int nk = k+a[i-1];
		if(nk>=K) continue;
		dpr[i-1][nk]=1;
	}
	int ans=0;
	rep(i,N){
		bool *l = dpl[i];
		bool *r = dpr[i+1];
		int imo[MK+1]={};
		rep(k,K) imo[k+1]=imo[k]+r[k];
		bool need=0;
		rep(k,K) if(l[k]){
			int le = K-a[i]-k, ri = K-k;
			if(le<0) le=0;
			if(imo[ri]-imo[le]>0) need=1;
		}
		if(!need) ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 49152
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	vector<vector <int> > v(a, vector<int>(b));
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			cin >> v[i][j];
		}
	}
	vector<int>x(b);
	for (int i = 0; i < b; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < a; i++) {
		long sum = 0;
		for (int j = 0; j < b; j++) {
			sum += v[i][j] * x[j];
		}
		cout << sum << endl;
	}
	return 0;
}


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

using namespace std;
int main(){
    int  n;
    cin >> n;
    char m;
    int num;
    int a[4][13]={};
    for(int i=0; i< n; i++){
        cin >> m  >> num;
        if(m == 'S')    a[0][num-1] = 1;
        if(m == 'H')    a[1][num-1] = 1;
        if(m == 'C')    a[2][num-1] = 1;
        if(m == 'D')    a[3][num-1] = 1;
    }
    for(int i = 0; i < 4; i++){
        for(int j=0; j < 13; j++){
            if(!a[i][j])    {
                if(i == 0)  cout << "S "  << j+1 << endl; 
                if(i == 1)  cout << "H "  << j+1 << endl; 
                if(i == 2)  cout << "C "  << j+1 << endl; 
                if(i == 3)  cout << "D "  << j+1 << endl; 
            }
            
        }
    }
    
}


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

using namespace std;

class seg_min_index{
public:
	int n,size;
	vector<long long> arr;
	vector<int> hai;
	long long inf;
	seg_min_index(int size) : n(size/2),inf(1LL << 60){
		arr.resize(n);
		hai.resize(n*2);
		fill(arr.begin(),arr.end(),inf);
		this->size=size;
		for(int i=n;i<size;i++) hai[i]=i-n;
	}
	
	void update(int i,long long v){
		arr[i]=v;
		i+=n;
		while(i>1){
			i/=2;
			hai[i]=arr[hai[2*i]] < arr[hai[2*i+1]] ? hai[2*i] : hai[2*i+1];
		}
	}
	int range_min_index(int left,int right){
		if(left>right) return -1;
		int res=left;
		left+=n,right+=n;
		for(;left<=right;left=(left+1)>>1,right=(right-1)>>1){
			if(left&1){
				if(arr[res] > arr[hai[left]]) res=hai[left];
			}
			if((right&1)==0){
				if(arr[res] > arr[hai[right]]) res=hai[right];
			}
		}
		return res;
	}
};
int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	
	int n,m;
	cin >> n >> m;
	string str;
	cin >> str;
	
	seg_min_index seg(1<<19);
	seg.update(n,0);
	vector<long long> dp(1<<19,1LL<<50);
	dp[n]=0;
	
	vector<vector<int>> ta(n+1);
	ta[0].push_back(n);
	for(int i=n-1;i>=0;i--){
		if(str[i]=='1') continue;
		int mn=seg.range_min_index(i+1,i+m);
		//cout << mn << " ";
		if(dp[mn]==(1LL<<50)) continue;
		dp[i]=dp[mn]+1;
		seg.update(i,dp[i]);
		
		ta[dp[i]].push_back(i);
		//cout << i << " " << dp[i] << "\n";
	}
	if(dp[0]>=(1LL<<40)){
		cout << -1 << "\n";
		return 0;
	}
	for(int i=0;i<=n;i++){
		reverse(ta[i].begin(),ta[i].end());
	}
	
	int cur=0;
	while(cur!=n){
		int v=dp[cur];
		v--;
		int ind=lower_bound(ta[v].begin(),ta[v].end(),cur)-ta[v].begin();
		int tugi=ta[v][ind];
		cout << (tugi-cur) << " ";
		cur=tugi;
	}
	cout << "\n";
	return 0;
}

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

using namespace std;

#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()

const int MX = (int)1e5 + 10;
const int mod = (int)1e9 + 7;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}


int main(){

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);

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

    int x[m], y[m], c[m];

    vector<int> st[n], nd[n];

    for(int i = 0; i < m; ++i){
        cin >> x[i] >> y[i] >> c[i];
        --x[i], --y[i];
        st[x[i]].push_back(i);
        nd[y[i]].push_back(i);
    }

    ll best[n];
    memset(best, 0x7f, sizeof best);
    best[0] = 0;

    multiset<ll> ms;

    for(int i = 0; i < n; ++i){

        if (not ms.empty())
            best[i] = *ms.begin();

        for(auto &idx : st[i]){
            ms.insert(best[i] + c[idx]);
        }
        
        for(auto &idx : nd[i]){
            auto it = ms.find(best[x[idx]] + c[idx]);
            assert(it != ms.end());
            ms.erase(it);
        }
    }

    ll res = best[n - 1];
    if(res >= n * 1LL * 1e9) res = -1; 

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 12928