akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお
 
int height[2001][2001];
int width[2001][2001];
 
int main() {
    int h, w; cin >> h >> w;
    vector<string> field(h);
    rep(i,h){
        cin >> field[i];
    }
    rep(i,h){
        int count = 1;
        rep(j,w){
            if(field[i][j]=='#'){
                count = 1;
            }else{
                width[i][j] = count;
                count++;
            }
        }
    }
    rep(i,w){
        int count = 1;
        rep(j,h){
            if(field[j][i]=='#'){
                count = 1;
            }else{
                height[j][i] = count;
                count++;
            }
        }
    }
    for(int i = h-1; i >= 0; i--){
        for(int j = w-2; j >= 0; j--){
            if(width[i][j+1]!=0 && width[i][j]!=0){
                width[i][j] = width[i][j+1];
            }
        }
    }
    for(int i = w-1; i >= 0; i--){
        for(int j = h-2; j >= 0; j--){
            if(height[j+1][i]!=0 && height[j][i]!=0){
                height[j][i] = height[j+1][i];
            }
        }
    }
    int ans = 0;
    rep(i,h){
        rep(j,w){
            ans = max(ans,width[i][j]+height[i][j]);
        }
    }
    cout << ans-1 << endl;
    
 
    return 0;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) int ab;cin>>ab;(p).push_back(ab);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
 		
int main() {
	
	int N;
	string S;
	cin>>N>>S;
	int maxi=0;
	fx(N-1){
		string a=S.substr(0,x+1);
		string b=S.substr(x+1);
      sorts(a)
		int i=0;
		int ans=0;
		while(i<=x){
          if(i>0&&a.at(i-1)==a.at(i)){i++;continue;}
			fy(b.size()){
				if(a.at(i)==b.at(y)){
					ans++;
					break;
				}
			}
          i++;
		}
		maxi=max(maxi,ans);
	}
	ce(maxi)
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    string s;
    cin >> s;
    bool ok=false;
    rep(i,s.size()) if(s.substr(i,2)=="AC") ok=true;
    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
// define
#define INF 1<<24
#define endl "\n"
#ifdef LOCAL
#define lout cerr
#else
ostream devnull(0);
#define lout devnull
#endif
#define AMULET \
  cin.tie(0);  \
  ios::sync_with_stdio(false);
// Inspired by: https://github.com/kurokoji/.cpp-Template/blob/master/template/template2.cpp
#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...)                                 \
  GET_MACRO(__VA_ARGS__, rep4, rep3, rep2, rep1) \
  (__VA_ARGS__)
#define rep1(n) rep2(_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, n) rep4(i, a, n, 1)
#define rep4(i, a, n, d) rep5(i, a, n, d, <)
#define rep5(i, a, n, d, o) for (auto i = decltype(n)(a), _n = (n); i o _n; i += (d))

#define rrep(...)                                    \
  GET_MACRO(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1) \
  (__VA_ARGS__)
#define rrep1(a) rrep2(_, a)
#define rrep2(i, a) rrep3(i, a, 0)
#define rrep3(i, a, n) rrep4(i, a, n, -1)
#define rrep4(i, a, n, d) rep5(i, (a)-1, n, d, >=)

#define repc(...)                                    \
  GET_MACRO(__VA_ARGS__, repc4, repc3, repc2, repc1) \
  (__VA_ARGS__)
#define repc1(n) repc2(_, n)
#define repc2(i, n) repc3(i, 0, n)
#define repc3(i, a, n) repc4(i, a, n, 1)
#define repc4(i, a, n, d) rep5(i, a, n, d, <=)

#define dump(x) lout << #x << " = " << x << endl;
// alias
typedef long long ll;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
// func
template <class C>
inline void vcin(C &c);
template <class C, class D>
inline void vcin(C &c, D &d);
template <class C>
inline void vcout(const C &c, const string separate = "\n");
template <class T = int>
inline T in();
//http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }

void solve()
{
  const int n = in();
  vector<int> a(n);
  vcin(a);

  lint s = 0;
  int cnt_neg = 0;
  int min_abs_a = INF;
  rep(i, n)
  {
    if (a[i] < 0)
    {
      cnt_neg++;
    }
    int abs_a = abs(a[i]);
    min_abs_a = min(abs_a, min_abs_a);
    s += abs_a;
  }
  if (cnt_neg % 2 == 0)
  {
    cout << s << endl;
  }
  else
  {
    cout << s - 2 * min_abs_a << endl;
  }
}

signed main()
{
  AMULET
  solve();
  return 0;
}

template <class C>
inline void vcin(C &c)
{
  for (auto &a : c)
  {
    cin >> a;
  }
}
template <class C, class D>
inline void vcin(C &c, D &d)
{
  for (auto it1 = c.begin(), it2 = d.begin(); it1 != c.end() && it2 != d.end(); it1++, it2++)
  {
    cin >> *it1 >> *it2;
  }
}
template <class C>
inline void vcout(const C &c, const string separate)
{
  for (auto it = c.begin(); it != c.end(); it++)
  {
    if (it != c.begin())
      cout << separate;
    cout << *it;
  }
}
template <class T = int>
inline T in()
{
  T x;
  cin >> x;
  return (x);
}


Measured memory_bytes: 640
N,M=map(int,input().split())
man,pt=[],[]
def getter(freq,obj):
    for _ in range(freq):
        a,b=map(int,input().split())
        obj.append([a,b])
def solve():
    for tm in man:
        judg=[]
        for tp in pt:
            judg.append(abs(tm[0]-tp[0])+abs(tm[1]-tp[1]))
        print(judg.index(min(judg))+1)
def main():
    getter(N,man)
    getter(M,pt)
    solve()
if __name__ =='__main__':
    main()

Measured memory_bytes: 3064
#include<stdio.h>

int main(){

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

    int count=0;
    for(int i=n-1;i>=0;i--){
        count=0;
        for(int j=i;j<n;j+=(i+1)){
            count+=b[j];
        }
        if(count%2!=a[i]){
            b[i]=1;
        }
    }
    
    count=0;
    for(int i=0;i<n;i++){
        if(b[i]==1){
            count++;
        }
    }
    printf("%d\n",count);

    for(int i=0;i<n;i++){
        if(b[i]==1){
            printf("%d ",i+1);
        }
    }

    return 0;
}

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

using namespace std;

const int N = 200010;

char s[N];
int ne[N][26];
int f[N];

int main() {
  scanf("%s", s);
  int n = (int)strlen(s);
  for (int i = 0; i < 26; ++i) {
    ne[n][i] = n;
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < 26; ++j) {
      ne[i][j] = ne[i + 1][j];
    }
    ne[i][s[i] - 'a'] = i;
  }
  f[n] = 0;
  for (int i = n - 1; i >= 0; --i) {
    int k = 0;
    for (int j = 0; j < 26; ++j) {
      k = max(k, ne[i + 1][j]);
    }
    f[i] = f[k] + 1;
  }
  int len = 1e9;
  for (int i = 0; i < 26; ++i) {
    len = min(len, f[ne[0][i]]);
  }
  string ans = "";
  int j = -1;
  while (j < n) {
    int k = -1;
    for (int i = 26; i >= 0; --i) {
      if (f[ne[j + 1][i]] == len) {
        k = i;
      }
    }
    assert(k != -1);
    ans += (char)('a' + k);
    j = ne[j + 1][k];
    --len;
  }
  printf("%s\n", ans.c_str());
}

Measured memory_bytes: 21504
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  string s;
  cin >> n>>s;

  int ans = 0;
  int l = 0, r = n - 1;
  while(r-l>0){
    if(s[r]=='R'){
      // changeするlを探す
      rep(i,l,r){
        if(s[l]=='W'){
          // change suru
          ans++;
          r--;
          l++;
          break;
        }
        l++;
      }

    } else {
      // not change
      r--;
    }
  }

  cout<<ans<<endl;
}


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

using namespace std;
typedef long long ll;
ll a[100000];


int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> a[i];
    }
    ll temp = a[0];
    ll ans=0;
    ll ans2=0;
    if(a[0]!=0){
        for(int i=1;i<n;++i){
        //cout << "i:" << i << "temp:" << temp << endl;
            if(temp*(temp+a[i])>=0){
                ans += abs(temp+a[i])+1;
                if(temp>0)temp = -1;
                else temp = 1;
            }else{
                temp += a[i];
            }
        }
        temp = a[0];
        if(a[0]>0){
            ans2 += abs(a[0])+1;
            temp = -1;
        }else if(a[0]<0){
            ans2 += abs(a[0])+1;
            temp = 1;
        }
        for(int i=1;i<n;++i){
            if(temp*(temp+a[i])>=0){
                ans2 += abs(temp+a[i])+1;
                if(temp>0)temp = -1;
                else temp = 1;
            }else{
                temp += a[i];
            }
        }
    }else{
        temp=1;
        ans=1;
        for(int i=1;i<n;++i){
        //cout << "i:" << i << "temp:" << temp << endl;
            if(temp*(temp+a[i])>=0){
                ans += abs(temp+a[i])+1;
                if(temp>0)temp = -1;
                else temp = 1;
            }else{
                temp += a[i];
            }
        }
        temp=-1;
        ans2=1;
        for(int i=1;i<n;++i){
            if(temp*(temp+a[i])>=0){
                ans2 += abs(temp+a[i])+1;
                if(temp>0)temp = -1;
                else temp = 1;
            }else{
                temp += a[i];
            }
        }
    }
    
    cout << min(ans,ans2) << endl;
    return 0;
}

Measured memory_bytes: 1024
n=int(input())
dic={}
for i in range(n):
    s=input()
    l=[]
    for a in s:
        l.append(a)
    l.sort()
    s="".join(l)
    if s in dic:
        dic[s]+=1
    else:
        dic[s]=1
total=0
for f in dic:
    total+=int((dic[f]*(dic[f]-1))/2)
print(total)


Measured memory_bytes: 17804
n,d=gets.split.map(&:to_i)
xs=n.times.map{gets.split.map(&:to_i)}
ans=0
xs.combination(2) do |arr1,arr2|
  dis=0
  d.times do |i|
    dis+=((arr1[i]-arr2[i]).abs)**2
  end
  check=false
  (dis+1).times do |i|
    if i**2==dis
      check=true
      break
    end
  end
  ans+=1  if check
end
puts ans


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

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

    // 重さでグループ分け
    vector<vector<ll>> a(4, vector<ll>());
    rep(i, N) a[w[i] - w[0]].push_back(v[i]);
    rep(i, 4) sort(a[i].rbegin(), a[i].rend());

    // 累積和
    vector<vector<ll>> s(4, vector<ll>());
    rep(i, 4) {
        s[i].resize(a[i].size() + 1);
        rep(j, a[i].size()) s[i][j + 1] = s[i][j] + a[i][j];
    }

    ll ans = 0;
    rep(i, s[0].size()) {
        rep(j, s[1].size()) {
            rep(k, s[2].size()) {
                rep(l, s[3].size()) {
                    ll weight = w[0] * i + (w[0] + 1) * j + (w[0] + 2) * k + (w[0] + 3) * l;
                    if (weight <= W) chmax(ans, s[0][i] + s[1][j] + s[2][k] + s[3][l]);
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
chk_word = input().lower()

words = [] #入力情報の単語リスト
while True:
    sentence = input()
    if sentence == "END_OF_TEXT": #END_OF_TEXTまで読み込む
        break
    else:
        word = sentence.lower().split() #読み込んだ文章を単語に分割
        words.append(word) #単語を単語リストに加える（リスト内リストになっている）

count = 0
for i in range(len(words)):
    for j in range(len(words[i])):
        if chk_word == words[i][j]:
            count += 1
print(count)



Measured memory_bytes: 5564
#include <stdio.h>
int main(void){
    int n,s[110],ans=0,min=110;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
        ans+=s[i];
        if(min>s[i]&&s[i]%10!=0)min=s[i];
    }
    if(ans%10!=0)printf("%d\n",ans);
    if(min==110)printf("0\n");
    else if(ans%10==0)printf("%d\n",ans-min);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
	std::unordered_map<char, std::string> map;
	{
		std::string A, B, C;
		std::cin >> A >> B >> C;
		map['a'] = A;
		map['b'] = B;
		map['c'] = C;
	}

	char next = 'a';
	char ans;
	char temp;
	while (true) {
		if (map[next] == "") {
			ans = next;
			break;
		}
		temp = next;
		next = map[next][0];
		map[temp].erase(map[temp].begin());
	}

	if (ans == 'a')
		std::cout << "A\n";
	else if (ans == 'b')
		std::cout << "B\n";
	else
		std::cout << "C\n";

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string A="ABC";
    string B;
    cin>>B;
    int c=0;
int j=0;
for(int i=0;i<n;i++){
	char ch=B[i];
	if(ch==A[j]){
	//	cout<<i<<"  ";
		j++;
	}
  else{
    if(ch=='A')
    j=1;
    else
    j=0;
  }
 
if(j==3){
	c++;
	j=0;
	//	cout<<i<<" ";
	}
}
cout<<c;
}


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

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                        \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

void solve()
{	
	string s; cin >> s;
	int n = s.length();
	vector<ll> a(n + 1, 0);
	ll cnt = 0, c = 0;
	for (int i = 1; i < n + 1; ++i)
	{
		if (s[i - 1] == '<') 
		{
			cnt++;
		}
		else 
		{
			cnt = 0;
		}
		a[i] = max(a[i], cnt);
	}
	cnt = 0;
	debug() << imie(a);
	for (int i = n; i > 0; --i)
	{
		if (s[i - 1] == '>')
		{
			cnt++;
		}
		else
		{
			cnt = 0;
		}
		a[i - 1] = max(a[i - 1], cnt);
	}
	debug() << imie(a);
	cout << accumulate(all(a), 0LL);
}

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


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

typedef int64_t Int;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

Int n, m, q;
Int a[51], b[51], c[51], d[51];
Int res = 0;

void dfs(vector<Int> &v) {
    if ((Int)v.size() == n + 1) {
        Int sum = 0;
        for (Int i = 0; i < (Int)q; i++) {
            if (v[b[i]] - v[a[i]] == c[i]) {
                sum += d[i];
            }
        }
        res = max(res, sum);
        return;
    }
    for (Int i = v.back(); i <= (Int)m; i++) {
        v.push_back(i);
        dfs(v);
        v.pop_back();
    }
}

int main() {
    cin >> n >> m >> q;
    for (Int i = 0; i < (Int)q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<Int> v;
    v.push_back(1);
    dfs(v);
    print(res);
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  int H;
  int W;

  cin >> H >> W;

  vector<string> vec(H + 1); 
  for (int i = 0; i < H; i ++) {
    string str;
    cin >> str;

  


    string str2 = "#" + str + "#";
    vec.at(i + 1) = str2;
  }
  
  string insert;
  int size = vec.at(1).size();
  for (int i = 0; i < size; i++) {
      insert += "#";
    }
  vec.at(0) = insert;
  vec.push_back(insert);

  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
  }

}


Measured memory_bytes: 256
<?php
while (($line = trim(fgets(STDIN))) != 0) {
    $n = intval($line);
    $mul5  = 0;
    $mul2  = 0;
 
    for ($i = 1; $i <= $n; $i++) {
        $target = $i;
        while ($target % 2 == 0) {
            $mul2++;
            $target /= 2;
        }
        while ($target % 5 == 0) {
            $mul5++;
            $target /=5;
        }
    }
 
    echo min($mul5, $mul2) . "\n";
}

Measured memory_bytes: 15108
import sys
sys.setrecursionlimit(10 ** 7)

X, Y = map(int, input().split())

cnt_d1 = 0
cnt_d2 = 0

diff = Y - X
if diff == 0:
    if X % 3 != 0:
        print(0)
        exit()
    cnt_d1 = X // 3
    cnt_d2 = cnt_d1
elif diff > 0:
    Y -= 2 * diff
    X -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = X // 3
    cnt_d2 = diff + X // 3
else:
    diff = - diff
    X -= 2 * diff
    Y -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = diff + X // 3
    cnt_d2 = X // 3

MOD = 10**9 + 7
fact = [1]
fact_inv = [1]
for i in range(cnt_d1+cnt_d2 + 10):
    new_fact = fact[-1]*(i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD-2, MOD))


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod


print(mod_comb_k(cnt_d1+cnt_d2, cnt_d1, MOD))

'''
dp = np.array([[0] * (Y + 1) for _ in range(X + 1)], dtype=np.int64)
#dp = [np.zeros(Y+1, np.int64) for _ in range(X+1)]
print(dp)

for i in range(X):
    if i > 0:
        dp[i] = dp[i]
'''


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

int main(){
  long int n,k,r,s,p ;
  cin >> n >> k >> r >> s >> p ;
  vector<vector<char>> t((n/k)+1,vector<char>(k)) ;
  for(int i=0;i<(n/k)+1;i++){
    for(int j=0;j<k;j++){
      char x ; cin >> x ;
      t.at(i).at(j) = x ;
    }
  }
  for(int i=n%k;i<k;i++){
    t.at(n/k).at(i) = 'x' ;
  }
  long int ans = 0 ;
  for(int i=0;i<k;i++){
    for(int j=0;j<(n/k)+1;j++){
      if(j==0){
        if(t.at(j).at(i)=='r'){
          ans += p ;
          continue ;
        }else if(t.at(j).at(i)=='s'){
          ans += r ;
          continue ;
        }else if(t.at(j).at(i)=='p'){
          ans += s ;
          continue ;
        }
      }
      if(t.at(j).at(i)==t.at(j-1).at(i)){
        t.at(j).at(i) = 'x' ;
      }else if(t.at(j).at(i)=='r'){
          ans += p ;
          continue ;
      }else if(t.at(j).at(i)=='s'){
          ans += r ;
          continue ;
      }else if(t.at(j).at(i)=='p'){
          ans += s ;
          continue ;
      }
    }
  }
  cout << ans << endl ;
}

Measured memory_bytes: 5632
unittest
{
	assert( [ "33" ].parse.expand.solve == "2 -1" );
//	assert( [ "1" ].parse.expand.solve == "0 -1" );
	assert( [ "1" ].parse.expand.solve == "1 0" );
}



import std.bigint;
import std.conv;
import std.format;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto x = input.front.to!( long );
	return tuple( x );
}

auto solve( long x )
{
	auto xx = BigInt( x );
	
	BigInt[] fs;
	for( auto a = 0L;; a++ )
	{
		auto a5 = BigInt( a ) ^^ 5;
		fs ~= a5;
		foreach( long b; 0L .. a + 1 )
		{
			auto b5 = BigInt( b ) ^^ 5;
			if(  a5 -  b5 == xx ) return format( "%s %s",  a,  b );
			if(  a5 - -b5 == xx ) return format( "%s %s",  a, -b );
			if( -a5 -  b5 == xx ) return format( "%s %s", -a,  b );
			if( -a5 - -b5 == xx ) return format( "%s %s", -a, -b );
		}
	}
}


Measured memory_bytes: 4032
a, b = map(int, input().split())

ans_1 = ""
for i in range(b):
    ans_1 += str(a)
ans_2 = ""
for i in range(a):
    ans_2 += str(b)

if ans_1 < ans_2:
    print(ans_1)
else:
    print(ans_2)

Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

H, N = map(int, input().split())
A = sum(map(int, input().split()))

print("Yes" if H <= A else "No")

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

int main() {
  //input
  string S, T;
  cin >> S >> T;
  //calc
  int ls, lt;
  ls = S.length();
  lt = T.length();
  int max = ls - lt + 1;
  int cand = lt;
  string teststr;
  int change = 0;
  rep(i,max) {
    teststr = S.substr(i,lt);
    change = 0;
    rep(j,lt) {
      if ( T.at(j) != teststr.at(j) ) {
        change++;
      }
    }
    if ( cand > change ) {
      cand = change;
    }
  }
  //output
  cout << cand << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<algorithm>

using namespace std;

int main(){
	int n,a,b,c;
	int m=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a[3];
		for(int j=0;j<3;j++)scanf("%d",&a[j]);
		std::sort(a,a+3);
		
		int d = 35;
		if(a[0]>d || a[1]>d || a[2]>d)puts("hogehogehoge");
		
		if(a[0]*a[0]+a[1]*a[1] == a[2]*a[2]){
			puts("YES");
		}else{
			puts("NO");
		}
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define betheflash ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vs vector<string>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define msi map<string,int>
#define mis map<int,string>
#define pb push_back
#define mod 1000000007
#define PI 3.141592653589793238
using namespace std;
int main()
{
    betheflash
    int l=0,m;
    string s;
    cin>>s;
    for(int i=0;s[i]!='\0';i++)
		l++;
	m=(l-1)/2;
	for(int i=0;i<m;i++)
	{
		if(s[i]!=s[m-1-i])
		{
			cout<<"No";
			return 0;
		}
	}
	m=l;
	for(int i=(l+3)/2;i<m;i++)
	{
		if(s[i]!=s[m-1-i])
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	    return 0;
}

Measured memory_bytes: 256
n,k,s=gets.split.map(&:to_i)
l=[]
if s==1000000000
  n.times do |i|
    if i<k
      l[i] = s
    else
      l[i]=7
    end
  end
  puts l.join(" ")
  exit
end
n.times do |i|
  if i<k
    l[i] = s
  else
    l[i]=1000000000
  end
end
puts l.join(" ")


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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  ll vmax = 0;
  map<string, ll> mp;
  for (ll i = 0; i < N; i++) {
    string s; cin >> s;
    ll cnt = ++mp[s];
    if (vmax < cnt) vmax = cnt;
  }
  vector<string> ss;
  for (auto p : mp) {
    if (p.second == vmax) ss.push_back(p.first);
  }
  sort(ss.begin(), ss.end());
  for (string s : ss) {
    cout << s << "\n";
  }

  return 0;
}



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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    int sum = 0;
    rep (i, m) {
        int a;
        cin >> a;
        sum += a;
    }
    if (n >= sum) cout << n - sum << endl;
    else cout << -1 << endl;
    
    return 0;
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define MOD 1000000007
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN


void init(){
}

ll po(ll x, ll y) { 
    ll res = 1;
    while (y > 0) { 
        if (y & 1) 
            res = (res*x)%MOD; 
        y = y>>1;  
        x = (x*x)%MOD;
    } 
    return res; 
}



void solve(){
    string s;
    cin>>s;
    ll n = s.length();
    ll ans = 0;
    map<ll,ll> mp1;
    ll cur = 0;
    mp1[cur] = 1;
    ll inv = 202;
    for( ll i=0;i<n;i++ ){
        cur = (cur + ((s[i]-'0')*inv)%2019)%2019;
        ans += mp1[cur];
        mp1[cur]++;
        inv = (inv*202)%2019;
        //cout<<cur<<endl;
    }
    cout<<ans<<endl;
    return;
}

int main(){
    FAST;
    init();
    ll t = 1;
    //cin>>t;
    while( t-- ) solve();
    return 0;
} 

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define rep(begin, end) for (i=begin;i<end;i++)
#define repj(begin, end) for (j=begin;j<end;j++)
#define init(arr, end, val) for (i=0;i<end;i++) arr[i] = val;
#define printint(i0, i1) printf("%d %d\n", i0, i1)

using namespace std;
typedef long long int ll;
const int inf = 1000000000;
const int mod = 1000000007;
const int nil = -1;
ll i, n, m, k, ans, q, b, c;
ll a[100001];

int main() {
    rep(0, 100001) a[i] = 0;
    scanf(" %lld", &n);
    rep(0,n) {
        scanf(" %lld", &k);
        a[k]++;
    }
    ll sum = 0;
    rep(0, 100001) sum+=i*a[i];
    scanf(" %lld", &q);
    rep(0, q) {
        scanf(" %lld %lld", &b, &c);
        sum += (c - b) * a[b];
        printf("%lld\n", sum);
        a[c] += a[b];
        a[b] = 0;
    }
}

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

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

    int N, D, X;
    cin >> N >> D >> X;
    int A;
    int ans = X;
    rep(i, N){
        cin >> A;
        ans += 1 + (D - 1) / A;
    }
    cout << ans << endl;;

    return 0;
}

Measured memory_bytes: 256
END { load __FILE__ unless $stdin.eof? }

n, x, m = gets.split.map!(&:to_i)

def f(x, m)
  x * x % m
end

x1 = x2 = x
i = 0
begin
  i += 1
  x1 = f(x1, m)
  x2 = f(f(x2, m), m)
end while x1 != x2

x1 = x
j = 0
begin
  j += 1
  x1 = f(x1, m)
  x2 = f(x2, m)
end while x1 != x2

k = 0
begin
  k += 1
  x1 = f(x1, m)
  x2 = f(f(x2, m), m)
end while x1 != x2

if n <= j
  s = n.pred.times.sum(x) { x = f(x, m) }
  puts s
else
  s0 = j.pred.times.sum(x) { x = f(x, m) }

  n -= j
  s1 = k.times.sum { x = f(x, m) }
  s2 = (n % k).times.sum { x = f(x, m) }

  puts s0 + s1 * (n / k) + s2
end


Measured memory_bytes: 14372
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using ll = long long;
using namespace std;

int main() {
  int n, m;
  cin >> n;
  int t[n];
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> t[i];
    sum += t[i];
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    int p, x;
    cin >> p >> x;
    p--;
    cout << sum - t[p] + x << endl;
  }
}


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


#define long long long int

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef pair<int, int> pi;


int main() {
    std::ios_base::sync_with_stdio(false);

    int n;
    string s;
    cin >> n >> s;
    if (n % 2){
        cout << "No";
        return 0;
    }
    string str = s.substr(0, n / 2);
    if (str + str == s){
        cout <<"Yes";
    } else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC
{
    using System.Collections.Generic;
    using System.Runtime.InteropServices;
#if USE_STUB
    using static Stub.Console;
#else
    using static System.Console;
#endif
    using static System.Math;
    public class Program
    {
        static void Main(string[] args)
        {
            WriteLine(Solve());
        }

        static object Solve()
        {
            var N = int.Parse(ReadLine());
            var Pn = ReadLine().Split().Select(int.Parse).ToArray();
            var s = Pn.OrderBy(x => x).ToArray();
            if (Pn.Zip(s, (n, i) => new { n, i }).Count(x => x.n != x.i) > 2)
                return "NO";
            return "YES";
        }
    }
}


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

using namespace std;

int main()
{
    int mod=1000000007;
    int n,m;
    int c=0;
    cin>>n>>m;
    vector<string> str(n);
    for(int i=0;i<n;i++)
    {
        cin>>str[i];
    }
    vector<vector<int>>dp(n,vector<int>(m,0));


    for(int i=n-1;i>=0;i--)
    {
        if(str[i][m-1]=='.' && c==0)
        {
            dp[i][m-1]=1;

        }
        else
        {
            c=1;
        }
    }
    c=0;
    for(int j=m-1;j>=0;j--)
    {
        if(str[n-1][j]=='.' && c==0)
        {
            dp[n-1][j]=1;
        }
        else
        {
            c=1;
        }
    }
    for(int i=n-2;i>=0;i--)
    {
        for(int j=m-2;j>=0;j--)
        {
            if(str[i][j+1]!='#')
                dp[i][j]+=dp[i][j+1];
            dp[i][j]=dp[i][j]%mod;
            if(str[i+1][j]!='#')
                dp[i][j]+=dp[i+1][j];
            dp[i][j]=dp[i][j]%mod;
        }
    }
    cout<<dp[0][0]<<endl;
    return 0;
}



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

const int INF = 1001001001;

ll pow(ll base, ll order) {
	ll ans = 1;
	rep(i,order - 1) ans *= base;
	return ans;
}

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

	ll sum = 0;
	for (ll i = 1; i <= n; i++) {
		if (i % 3 == 0 || i % 5 == 0) continue;
		sum += i;
	}
	cout << sum << endl;
}


Measured memory_bytes: 3620
import sys
 
L, R = map(int, input().split())
 
if R-L >= 2019:
  print('0')
  sys.exit()
 
L = L % 2019
R = R % 2019
if L > R:
  print('0')
 
mmin = 2019
for i in range(L, R):
  for j in range(i+1, R+1):
    mmin = min(mmin, (i*j)%2019)
print(mmin)

Measured memory_bytes: 3064
X = int(input())

dp = [False]*(X+1)
dp[0] = True

for i in range(100, X+1):
  if i < 106:
    dp[i] = True
    continue
  if dp[i-100] or dp[i-101] or dp[i-102] or dp[i-103] or dp[i-104] or dp[i-105]:
    dp[i] = True

print(1) if dp[len(dp)-1] else print(0)

Measured memory_bytes: 9420
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		
		int n=Integer.parseInt(in.next()),q=Integer.parseInt(in.next());
		mystack A[]=new mystack[n];
		for(int i=0;i<n;i++)A[i]=new mystack();
		
		for(int i=0;i<q;i++){
			int query=Integer.parseInt(in.next());
			
			switch(query){
			case 0:
				int t1=Integer.parseInt(in.next()),x=Integer.parseInt(in.next());
				A[t1].stk.push(x);
				break;
				
			case 1:
				int t2=Integer.parseInt(in.next());
				if(!A[t2].stk.isEmpty())out.println(A[t2].stk.peek());
				break;
				
			case 2:
				int t3=Integer.parseInt(in.next());
				if(!A[t3].stk.isEmpty())A[t3].stk.pop();
				break;
			}
		}
		out.flush();
	}

}

class mystack{
	Stack<Integer> stk;
	
	mystack(){
		stk=new Stack<>();
	}
}



Measured memory_bytes: 109852
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


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;}

//INSERT ABOVE HERE
signed main(){
  Int w,h,k,n;
  cin>>w>>h>>k>>n;
  k-=(w+1)/2;
  if(k<0){
    cout<<-1<<endl;
    return 0;
  }
  Int ans=((w+1)/2)*(h/2);
  Int cnt=0;
  vector<vector<Int> > vp(h+1);
  for(Int i=0;i<n;i++){
    Int x,y;
    cin>>x>>y;
    if(x&1) ans++;
    if(y&1) continue;
    vp[y].emplace_back(x);
  }
  const Int INF = 1e9;
  for(Int i=0;i<h+1;i++){
    if(vp[i].empty()) continue;
    vector<Int> dg(w+1,0);
    for(Int x:vp[i]) dg[x]=1;
    auto dp=make_v<Int>(2,w+1);
    fill_v(dp,-INF);
    dp[0][1]=0;
    for(Int j=1;j<w;j+=2){
      chmax(dp[0][j+2],dp[0][j]);
      chmax(dp[0][j+2],dp[1][j]);
      if(dg[j+1]) continue;
      chmax(dp[1][j+2],dp[0][j]+dg[j]+dg[j+2]);
    }
    ans-=max(dp[0][w],dp[1][w]);
    Int sum=0;
    for(Int x:vp[i]) if(x&1) sum++;
    cnt+=sum-max(dp[0][w],dp[1][w]);
  }
  chmin(cnt,k);
  ans-=min(ans,cnt*2);
  k-=cnt;
  ans-=min(ans,k);
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4228
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>
typedef long long int llint;

int main(void){
  int n;
  std::string s;
  std::cin >> n >> s;

  std::vector< std::set<int> > rgb(3);
  for(int i=0; i<s.size(); i++){
    if(s[i] == 'R') rgb[0].insert(i);
    if(s[i] == 'G') rgb[1].insert(i);
    if(s[i] == 'B') rgb[2].insert(i);
  }

  std::vector<std::vector<int> > patterns = {{0,1,2}, {0,2,1}, {1,0,2},{1,2,0}, {2,0,1}, {2,1,0}};
  llint count = 0;
  for(auto elem: patterns){
    //std::cout << elem[0] << elem[1] << elem[2] << std::endl;
    std::set<int>& a = rgb[elem[0]];
    std::set<int>& b = rgb[elem[1]];
    std::set<int>& c = rgb[elem[2]];

    std::vector<int> c_v(10000, c.size());
    for(auto val: c){
      for(int i=val+1; i<c_v.size(); i++){
	c_v[i]--;
      }
    }

    int a_idx=0;
    int b_idx;
    for(const auto& a_idx: a){
      for(const auto& b_idx: b){
	int diff = b_idx-a_idx;
	if(diff<0) continue;
	//std::cout << a_idx << " " << b_idx << " " << b_idx+diff << std::endl;
	count += c_v[b_idx];
	if(c.find(b_idx+diff) != c.end()) count--;
      }
    }
  }

  std::cout << count << std::endl;
  return 0;
}


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

int main(){
  ll n;
  cin >> n;
  
  ll a[n], b[n];
  
  cin >> a[0];
  b[0] = a[0];
  for(ll i=1; i<n; i++){
    cin >> a[i];
    b[i] = b[i-1] + a[i];
  }
  
  if(count(a,a+n, 0)==n){
    cout << 2*n-1 << endl;
    return 0;
  }
  
  ll sgn = 1;
  ll ans = 0;
  ll shift = 0;
  
  for(ll i=0; i<n; i++){
    if((b[i]+shift) * sgn <= 0){
      ans += abs(b[i]+shift) + 1;
      shift += -(b[i]+shift) + (b[i]+shift == 0 ? sgn : -(b[i]+shift)/abs(b[i]+shift));
    }
    sgn *= -1;
  }
  
  sgn = -1;
  shift = 0;
  ll ans2 = 0;
  
  for(ll i=0; i<n; i++){
    if((b[i]+shift) * sgn <= 0){
      ans2 += abs(b[i]+shift) + 1;
      shift += -(b[i]+shift) + (b[i]+shift == 0 ? sgn : -(b[i]+shift)/abs(b[i]+shift));
    }
    sgn *= -1;
  }
  cout << min(ans,ans2) << endl;
  
}

Measured memory_bytes: 1792
# coding: utf-8


def solve(*args: str) -> str:
    x = int(args[0])

    ret = None
    for a in range(120):
        for b in range(120):
            a5, b5 = pow(a, 5), pow(b, 5)
            if a5-b5 == x:
                ret = (a, b)
            elif a5+b5 == x:
                ret = (a, -b)

    return ' '.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 9144
H,W = map(int,input().split())
grid = [input() for i in range(H)]
INF = 10**18
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            continue
        q = [(i,j)]
        dis = [[INF]*W for i in range(H)]
        dis[i][j] = 0
        d = 1
        while q:
            qq = []
            for y,x in q:
                for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                    yy,xx = dy+y,dx+x
                    if not(0<= yy < H and 0 <= xx < W):
                        continue
                    if dis[yy][xx] != INF:
                        continue
                    if grid[yy][xx] == '#':
                        continue
                    dis[yy][xx] = d
                    qq.append((yy,xx))
            q = qq
            d += 1
        for k in range(H):
            for l in range(W):
                if dis[k][l] != INF:
                    ans = max(ans,dis[k][l])
print(ans)

Measured memory_bytes: 3064
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception{

        FastReader fs = new FastReader();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        long n = fs.nextLong();
        long k = fs.nextLong();

        if(n%k==0){
            out.println("0");
        }else if(n>k){
            long neg = n/k ;
            long val1 = Math.abs(n - neg*k);
            long val2 = Math.abs(n - (neg+1)*k);
            long val3 = Math.abs(n - (neg-1)*k);
            out.println(Math.min(Math.min(val1,val2),val3));
        }else{
            out.println(Math.min(n,Math.abs(n-k)));
        }









        out.close();
    }
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;

    //-----------MyScanner class for faster input----------
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------
}


Measured memory_bytes: 22868
#include<iostream>
#include<cstdio>
#include<cstring>
inline void check_min(int a,int &b){if(a<b)b=a;}
const int N=20100;
int s[N],A[N],B[N];
int n;
int main()
{
//	freopen("in","r",stdin);
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
		scanf("%d",&x),s[x]=i;
	A[1]=1;B[1]=s[1]-1;
	for(int i=2;i<=n;i++)
	{
		int x=A[i-1]+1,y=B[i-1]-1,k=s[i];
		A[i]=std::max(x,k-y);
		B[i]=std::min(y,k-x);
	}

	int tmp=1;
	for(int i=1;i<=n;i++)check_min(A[i],tmp);
	for(int i=1;i<=n;i++)A[i]-=tmp-1;
	tmp=1;
	for(int i=1;i<=n;i++)check_min(B[i],tmp);
	for(int i=1;i<=n;i++)B[i]-=tmp-1;

	for(int i=1;i<=n;i++)printf("%d ",A[i]);printf("\n");
	for(int i=1;i<=n;i++)printf("%d ",B[i]);printf("\n");
	return 0;
}


Measured memory_bytes: 768
#include<stdio.h>
int main(void){
  int n,m,i,j; 
  int a,x;
  while(1){
  scanf("%d",&n); scanf("%d",&m);
  if(n==0&&m==0){
    break;
  }else{
    int val[n],p[2];
    for(i=0;i<n;i++){
      scanf("%d",&val[i]);
    }
    x=0;
    for(i=0;i<n;i++){
      for(j=i+1;j<n;j++){
	a=val[i]+val[j];
	if(x<a&&a<=m){
	  x=a;
	}
      }
    }
    if(x==0){
      printf("NONE\n");
    }else{
      printf("%d\n",x);
    }
  }
  }
  return 0;
}


Measured memory_bytes: 2104
#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 k,n;
	std::cin >> k >> n;
	std::vector<int> a(n);
	rep(i,n) std::cin >> a[i];
	std::sort(all(a));
	int max = a[0]+k-a[n-1];
	rep(i,n-1) max=std::max(max,a[i+1]-a[i]);
	print(k-max);
	return 0;
}


Measured memory_bytes: 1792
s = gets.chomp.chars

zero = 0
one = 0
s.size.times do |i|
  if i%2==0
    zero += 1 if s[i]%2=="1"
    one += 1 if s[i]%2=="0"
  else
    zero += 1 if s[i]%2=="0"
    one += 1 if s[i]%2=="1"
  end
end

puts [zero,one].min

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

int main() {
  int n;
  cin >> n;
  map<string,priority_queue<P>> p;
  rep(i,0,n) {
    string si; int pi;
    cin >> si >> pi;
    p[si].push(P(pi,i+1));
  }
  auto itr = p.begin();
  rep(i,0,p.size()) {
    while(!(itr->second.empty())) {
      P a = itr->second.top(); itr->second.pop();
      cout << a.second << endl;
    }
    itr++;
  }
  return 0;
}


Measured memory_bytes: 3556
N = int(input())
k = 0
i = 0
ans = []
while k != N:
    j = pow(-2, i)
    p = '1' if (N - k - j) % pow(2, i + 1) == 0 else '0'
    ans.append(p)
    k += int(p) * j
    i += 1

if N == 0:
    print(0)
else:
    print(''.join(reversed(ans)))


Measured memory_bytes: 38384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Pavel Mavrin
 */
public class Main {

    private void solve() throws IOException {
        int n = nextInt();
        int k = nextInt();
        int g = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int x = nextInt();
            g = gcd(g, x);
            max = Math.max(max, x);
        }
        if (k % g == 0 && k <= max) {
            out.println("POSSIBLE");
        } else {
            out.println("IMPOSSIBLE");
        }
    }

    private int gcd(int a, int b) {
        while (b > 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    PrintWriter out = new PrintWriter(System.out);

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

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

    private void run() throws IOException {
        solve();
        out.close();
    }

}


Measured memory_bytes: 36428
n = int(input())
if n==0:
  print(0)
  exit()
if n==1:
  print(1)
  exit()
l = []
while n!=1:
  if n%2==0:
    n //= -2
    l.append(0)
  else:
    n = (n-1)//(-2)
    l.append(1)
l.append(1)
l = l[::-1]
print(*l,sep="")

Measured memory_bytes: 9060
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[4];
	cin>>a[0]>>a[1]>>a[2]>>a[3];
	sort(a,a+4);
	if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
  	return 0;
}


Measured memory_bytes: 256
import heapq


def main():
    N, M = [int(x) for x in input().split()]
    heap = [-int(x) for x in input().split()]
    heapq.heapify(heap)

    for _ in range(M):
        x = heapq.heappop(heap)
        x = -x
        x = x // 2
        x = -x
        heapq.heappush(heap, x)
    print(-sum(heap))


if __name__ == '__main__':
    main()

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

int main (void){
	int n,a,b,max,min;
	cin >> n >> a >> b;
	max=std::min(a,b);
	min=std::max(0,a+b-n);
	cout << max << " " << min << endl;
	return 0;
}

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

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector <pair <ll, ll>> v(m, pair <ll, ll> ());
  rep(i, m) cin >> v.at(i).second >> v.at(i).first;
  sort(v.begin(), v.end());
  ll max = v.at(0).first, res = 1;
  rep(i, m) {
    if (v.at(i).second >= max) {
      max = v.at(i).first;
      res++;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 1792