akhauriyash/Code-Regression huggingface dataset:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None

    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)

    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id],
                                        self.nodes[right_id])


class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right

        self.update_height()

        for child in self.children():
            child.parent = self
            child.update_depth()

    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()

    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()

    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'

    def degree(self):
        return len(self.children())

    def children(self):
        return [child for child in [self.left, self.right] if child]

    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())


tree = Tree()

n = int(input())
for i in range(n):
    id, left, right = map(int, input().split())
    tree.add_child(id, left, right)

for id in sorted(tree.nodes):
    if id != -1:
        print(tree.nodes[id])


Measured memory_bytes: 5612
#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 K,N;
cin>>N>>K;
map<int,int> S;
vec(A)
fx(N){
	int a;
	cin>>a;
	if(S[a]==0){
		pb(A,a)
	}
	S[a]++;
}
int ans=0;
if(A.size()>K){
vec(B)
fx(A.size()){
	pb(B,S[A.at(x)])
}
sorts(B)
int k=0;
while(k++<A.size()-K){
	ans+=B.at(k-1);
}

}
	ce(ans)
}

Measured memory_bytes: 11892
// Created by code_sm
//
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp> 
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> pseudo_set;
#define ll long long
#define vi vector<int>
#define si set<int> 
#define mii map<int,int>
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define extract_word(s)  stringstream str(s); while(str>>word)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SET(s) cout<<fixed<<setprecision(s)
#define chotu 1000000007
#define set0(a) memset(a,0,sizeof(a))
#define endl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define lower_string(s) transform(all(s),s.begin(),::tolower())
#define upper_string(s) transform(all(s),s.begin(),::toupper())
#define size(s) s.size()
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<typename T,typename U>
bool compare(T x,U y){return(abs(x-y)<=1e-9);}
void solve()
{
fastio
	int a,b;
	cin>>a>>b;
if((a<=9)&&(b<=9))
  cout<<a*b;
  else
    cout<<-1;
}
int main()
{
//code
	int t=1;
while(t--)
{
	solve();
	cout<<endl;
}
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n;i++)
using namespace std;
int main(){
    int n; cin>>n;
    vector<int>v;
    long long sum=0;
    vector<long long>dp(n);
    rep(i,n){
        int hoge; cin>>hoge;
        v.push_back(hoge);
        sum+=hoge;
    }
    for(int i=n-1; i>=0;i--)if(i==n-1)dp[i]=v[i]; else dp[i]=v[i]+dp[i+1];
    long long ans=LLONG_MAX;
    rep(i,n)if(i)ans=min(ans,abs(sum-dp[i]-dp[i]));
    cout<<ans<<endl;
    
}

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

int main(){
	int n;
	cin >> n;
	int a[4]{};
	while(n--){
		int x;
		cin >> x;
		a[x % 4]++;
	}
	cout << (a[1] + a[2] % 2 + a[3] <= a[0] + 1 ? "Yes" : "No") << endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  ll a, b, n;
  cin >> a >> b >> n;

  ll x = min(b-1, n);

  cout << a * x / b - a * (x / b) << endl;

  return 0;
}


Measured memory_bytes: 3588
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define REP(i,n) for(int i = 0; i < n; i++)

int main(void)
{
    int N;
    cin >> N;
    int L[N];
    for(int  i = 0 ; i < N ; i++) cin >> L[i];

    sort(L, L+N);
    int maxL = L[N-1];

    int sum = 0;
    for(int i = 0; i < N-1; i++){
        sum += L[i];
    }

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

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>

int main (){
  int a, b;
  char op;
  std::cin >> a >> op >> b;

  while (op != '?')
    {
      switch (op)
        {
        case '+':
          std::cout << a + b << std::endl;
          break;
        case '-':
          std::cout << a-b<< std::endl;
          break;
        case '*':
          std::cout << a*b<< std::endl;
          break;
        case '/':
          std::cout << a/b<< std::endl;
          break;
        }
      std::cin >> a >> op >> b;
    }

}


Measured memory_bytes: 3104
#include <iostream>
using namespace std;
#include<string>
int main(){
	int sunadakun=0;
	char sunadatyan='1';
	string S;
      cin>>S;
      for(int i=0;i<3;i++){
      	if(S[i]==sunadatyan){
      		sunadakun=sunadakun+1;
      	}
      }
      cout<<sunadakun<<endl;
}


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

int main() {
    ll A;
    string Bs;
    cin >> A >> Bs;
    int B1 = stoi(Bs.substr(0, Bs.find(".")));
    int B2 = stoi(Bs.substr(Bs.find(".") + 1));
    
    ll ans = A * (B1 * 100 + B2) / 100;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <string>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
string s;
bool dp[30001][4][1000];

int main() {
	int i, j, k;
	
	cin >> n >> s;
	
	dp[0][0][0] = true;
	rep(i, n) {
		rep(j, 4) {
			rep(k, 1000) {
				if (!dp[i][j][k]) continue;
				dp[i + 1][j][k] = true;
				
				if (j == 3) continue;
				int nxt = 10 * k + (s[i] - '0');
				if (nxt >= 1000) continue;
				dp[i + 1][j + 1][nxt] = true;
			}
		}
	}
	
	int ans = 0;
	rep(k, 1000) if (dp[n][3][k]) { ans++; }
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 117504
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
#include<algorithm>
#define m(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int inf = 1 << 30;
const int maxn = 1e5;
struct point{
	int x,cont;
	float mon;
}ans[maxn+5];
bool cmp(point a,point b){
	if(a.mon != b.mon) return a.mon > b.mon;
	if(a.cont == b.cont)
		return a.x < b.x;
	return a.cont > b.cont;
}
int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	int ans = min(a,b)+min(c,d);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int N;
  int i,j,k,max=0,maxk=0;
  
  scanf("%d",&N);
  
  for(i=1;i<=N;i++){
    k=0;
    j=i;
    while(1){
      if(j%2 ==1)
        break;
      j/=2;
      k++;
    }
    if(maxk <= k){
      max = i;
      maxk=k;
    }
  }
  
  printf("%d\n",max);
  return 0;
}

Measured memory_bytes: 128
import numpy as np

W, H, N = map(int, input().split())
F = np.ones((H, W), dtype = int)

for _ in range(N):
    x, y, a = map(int, input().split())
    if a == 1:
        for i in range(H):
            for j in range(x):
                if F[i][j] == 1:
                    F[i][j] = 0
    if a == 2:
        for i in range(H):
            for j in range(x, W):
                if F[i][j] == 1:
                    F[i][j] = 0
    if a == 3:
        for i in range(y):
            for j in range(W):
                if F[i][j] == 1:
                    F[i][j] = 0
    if a == 4:
        for i in range(y, H):
            for j in range(W):
                if F[i][j] == 1:
                    F[i][j] = 0

print(sum(sum(F)))


Measured memory_bytes: 27308
#最低でも1つはピラミッド内の座標がないと解けない？

N = int(input())
#これが唯一の事実データ
src = [tuple(map(int,input().split())) for i in range(N)]
 
INF = float('inf')
#ここ以降でかかれてあるcx,cyはあくまで頂上であると仮定しているだけで条件と合わない場合に不適切な座標となる。
for cx in range(0,101):
    for cy in range(0,101):
        tmph = None
        maxh = INF
        for x,y,h in src:
            if h > 0:
                tmp = h + abs(x-cx) + abs(y-cy)
                if tmph is None:
                    tmph = tmp
                else:
                    #ここが等しくないとピラミッドの高さの公式に矛盾する
                    if tmp != tmph:
                        break
                if tmph > maxh:
                    break
            else:
                #ここでmaxhがtmphよりも小さくなってしまった場合、hは0だから頂点からのxとyの差の和が最低でもtmphはなければならないのに、それを下回っているため
                #データx,yは絶対的な値なのでcx,cyが間違っていることになる。それを判定するのが上のtmph > maxh の時
                maxh = min(maxh, abs(x-cx) + abs(y-cy))
        else:
            for x,y,h in src:
                if max(tmph - abs(x-cx) - abs(y-cy), 0) != h:
                    break
            else:
                print(cx,cy,tmph)
                exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define In_The_Name_Of_Allah_The_Merciful ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define Alhamdulillah return 0;
#define loop(i,k,n) for (ll i = k ; i < n ; ++i)
#define all(v) v.begin(),v.end()
#define debug(n) cerr << "[" << #n << " = " << n << "]" << endl

void Suhaib_Sawalha (){

    int H , H2 , M , M2 , k;
    cin >> H >> M >> H2 >> M2 >> k;
    int cool = (M2 - M) + (H2 - H) * 60;
    cout << max (0,cool-k);
}

int main(){
                                In_The_Name_Of_Allah_The_Merciful   /* بسم الله الرحمن الرحيم  */
#ifndef ONLINE_JUDGE
    freopen("SuhaibSawalha1.txt","r",stdin);
#endif
//int _;for(cin>>_;_;--_,cout<<endl)
        Suhaib_Sawalha();
                                         Alhamdulillah                    /* الحمد لله */
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	a, z := len(s), 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'A' && i < a {
			a = i
		} else if s[i] == 'Z' && i > z {
			z = i
		}
	}
	fmt.Println(z - a + 1)
}


Measured memory_bytes: 1920
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#include <iostream>  
#include <algorithm>  
#include <time.h>  
#include<cstdio>
#include<vector>
#include<functional>


using namespace std;


int main() {
	long long N, A, B,n;
	scanf("%lld %lld %lld", &N, &A, &B);
	n = (N - 2)*(B-A)+1;
	if (N == 0)printf("0");
	else if ((N == 1) && (A != B))printf("0");
	else if (A > B)printf("0");
	else printf("%lld", n);
	return 0;
	
}

Measured memory_bytes: 256
N=int(input())
dic={"B":[0]*N,"W":[0]*N}
for i in range(2*N):
    c,a=input().split()
    a=int(a)
    dic[c][a-1]=i

Btable=[[0 for i in range(N+1)] for i in range(N)]
BBtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["B"][i]<dic["B"][j])
    BBtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["W"][j-1]>dic["B"][i]:
            S+=1
        Btable[i][j]=S+BBtable[i]
    Btable[i][0]=BBtable[i]

Wtable=[[0 for i in range(N+1)] for i in range(N)]
WWtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["W"][i]<dic["W"][j])
    WWtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["B"][j-1]>dic["W"][i]:
            S+=1
        Wtable[i][j]=S+WWtable[i]
    Wtable[i][0]=WWtable[i]

dp=[[0 for j in range(N+1)] for i in range(N+1)]

for j in range(N-1,-1,-1):
    dp[N][j]=dp[N][j+1]+Wtable[j][N]

for i in range(N-1,-1,-1):
    for j in range(N,-1,-1):
        if j!=N:
            dp[i][j]=min(dp[i+1][j]+Btable[i][j],dp[i][j+1]+Wtable[j][i])
        else:
            dp[i][j]=dp[i+1][j]+Btable[i][j]


print(dp[0][0])

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

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

#define REPR(i, n) for (int i = n; i >= 0; --i)

#define _REP(i, m, n) for (int i = m; i < n; ++i)

#define INF 2e9

using namespace std;
long long  e_gcd(long long  a, long long  b)
{
    if (a%b== 0)
        return b;
    else 
        return e_gcd(b, a%b);
}

int main()
{
    long long a, b;
    cin >> a >> b;

    long long num = e_gcd(a, b);

    long long ans = 1;
    for (long long i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            while (num % i == 0)
            {
                num /= i;
            }
            ans++;
        }
    }

    if (num != 1)
        ans++;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
def trucks_needed(pack, p):
    count = 1
    sum = 0
    for i in pack:
        if i > p:
            return -1
        elif sum + i > p:
            count += 1
            sum = i
        else:
            sum += i
    return count

values = input().split(" ")
n = int(values[0])
k = int(values[1])
pack = []
for i in range(n):
    pack.append(int(input()))

sum = 0
max = 0
for i in pack:
    if i > max:
        max = i 
    sum += i
ave = int(sum / k)
if ave > max:
    start = ave
else:
    start = max

left = start
right = sum + 1

while left < right:
    mid = int((left + right) / 2)
    #print("mid: " + str(mid))
    num = trucks_needed(pack, mid)
    #print("num: " + str(num))
    if num <= k:
        right = mid
    else:
        left = mid + 1
print(right)


Measured memory_bytes: 9556
//yymm or mmyy
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;
int main(int argc, char const *argv[])
{
	string s;
	cin>>s;
	int ab,cd;
	ab = stoi(s.substr(0,2));
	cd = stoi(s.substr(2,2));
	if(0<ab&&ab<13){
		if(0<cd&&cd<13){
			cout<<"AMBIGUOUS"<<endl;
		}else{
			cout<<"MMYY"<<endl;
		}
	}else{
		if(0<cd&&cd<13){
			cout<<"YYMM"<<endl;
		}else{
			cout<<"NA"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
/*
        Choo Lo jo mujhe tum kabhi, kho na jaoon main raat din
    Nazaron mein tum ho basey
        Keh do jo tum ek baar, Mere ho bas tum mere
    Nazaron mein tum ho basey
*/
 
#include<bits/stdc++.h>
#include<cstdio>
 
#define deb(x) cout << #x << " -> " << x << el
#define db double
#define ll long long int
#define ull unsigned long long int
#define umap unordered_map
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define sclu(x) scanf("%llu", &x)
#define scd(x) scanf("%lf", &x)
#define pass cout<<"pass\n"
#define vi vector<int>
#define pb push_back
#define vec vector
#define el "\n"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define umap unordered_map
#define f(i,x,y) for(int i=x;i<y;++i)
#define ff(i,x,y) for(int i=x;i<=y;++i)
#define mem(x) memset(x, 0, sizeof(x))
#define mems(x,y) memset(x, y, sizeof(x))
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ppi pair<int, pii>
#define mat vector<vector<ll> > 
#define mod 1000000007
#define MAX 100005
 
using namespace std;

int H, W;

void solve() {
	cin >> H >> W;

	string s;
	vec<int> cur(W + 1, 0), prev(W + 1, 0);
	prev[1] = 1;

	for(int row = 1; row <= H; ++row) {
		cin >> s;
		for(int col = 1; col <= W; ++col) {
			if(s[col - 1] == '#') cur[col] = 0;
			else cur[col] = (cur[col - 1] + prev[col]) % mod;
		}
		prev = cur;
	}
	cout << cur[W] << el;
}

int main() {
    // freopen("inp.txt", "r", stdin);
    int ccc = 1;
    // sc(ccc);
    while(ccc--) {
        solve();
    }
 
    return 0;
}


Measured memory_bytes: 256
/**
 *    Author: "Robin Singh" !!
 *    rob_in_1
**/

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

#define dbg( args...) { vector<string> _v = split( #args, ','); err( _v.begin(), args); cerr << '\n'; }
vector<string> split( const string& s, char c) { vector<string> v; stringstream ss( s); string x; 
while ( getline( ss, x, c)) v.emplace_back(x); return move(v); }
void err( vector<string>::iterator it) { } 
template<typename T, typename... Args>
void err( vector<string>::iterator it, T a, Args... args) {
cerr << it -> substr( ( *it)[0] == ' ', it -> length()) << " = " << a << '\t'; err( ++it, args...); }

#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define MP make_pair
#define szz(v) ((int)(v).size())  
#define fr(i, j, k) for(int i = j; i < k; i++)     
#define bk(i, j, k) for(int i = j-1; i >= k; i--)
#define mem(ptr, val)  memset(ptr, val, sizeof ptr)
#define sbit(n)  __builtin_popcount(n)
#define nl "\n"

typedef long double ld;
typedef pair<int, int> pii;
typedef vector <int> vi;
typedef vector < pair<int,int> > vpii;
const long double eps = 1e-9;
const int mod = 1e9+7;

pii dir[8] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1} , {-1, 1}, {1, -1} };

//*********************************!Template Ends Here!**********************************//

const int nn = 1e5+5;
int n;
int h[nn], dp[nn];

void robin(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> h[i];
	}
	dp[1] = 0;
	dp[2] = abs(h[1]-h[2]);
	for(int i = 3; i <= n; i++){
		dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
	}
	cout << dp[n];
}

int32_t main(){
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    for(int tc = 1; tc <= T; tc++){
    	// cout << "Case #" << tc << ": ";
    	robin();
    }
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define t int t; cin>>t; while(t--)
#define show(a) for(int bm=0;bm<a.size();bm++)cout<<a[bm]<<endl;
#define s(n) scanf("%d",&n);
#define u(i,a,b) for(i=a;i<b;i++)
#define d(i,a,b) for(i=a;i>b;i--)
#define all(x) x.begin(),x.end() 
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y) 
#define F first
#define S second
#define mod 1000000007
ll power(ll a,ll b,ll m)
{
    ll ret=1;
    while(b)
    {
        if(b%2)
            ret=((ret%m)*(a%m))%m;
        a=((a%m)*(a%m))%m;
        b/=2;
    }
    return ret;
}
vector<int> z_function(string s)
{
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
ll fact[100004];
void build()
{
	fact[0]=1;
	for(ll i=1;i<100004;i++)
	{
		fact[i]=((fact[i-1]%mod)*(i%mod))%mod;
	}
	return;
}
int main()
{
	build();
	ll n,m;
	cin>>n>>m;
	if(n>m+1 || m>n+1)
	{
		cout<<0;
		return 0;
	}
	ll x=max(n,m);
	ll y=min(n,m);
	n=x;
	m=y;
	ll p=fact[n]%mod;
	ll q=1;
//	q=power(q,mod-2,mod);
	q=((q%mod)*(fact[m]%mod))%mod;
	q=((q%mod)*(p%mod))%mod;
	if(n==m)
	{
		p=2;
		q=((q%mod)*(p%mod))%mod;
	}
	cout<<q;
}

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

int main(){
  int a,b;
  cin >> a >> b;
  if(b<0&&(b-a+1)%2==1)cout << "Negative"<<endl;
  else if(a>0||b<0)cout << "Positive"<<endl;
  else cout << "Zero"<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;

int main (void) {
  ios::sync_with_stdio(false);cin.tie(0);
  string s; cin >> s;
  deque<char> str;
  for (char c : s) str.push_back(c);
  int q; cin >> q;
  bool rev = false;
  while (q--) {
    int op; cin >> op;
    if (op == 1) rev = 1-rev;
    else {
      int f;
      char c;
      cin >> f >> c;
      if (rev) {
        if (f == 1) str.push_back(c);
        else str.push_front(c);
      } else {
        if (f == 1) str.push_front(c);
        else str.push_back(c);
      }
    }
  }
  if (rev) reverse(str.begin(), str.end());
  for (char c : str) cout << c;
  cout << '\n';
  return 0;
}



Measured memory_bytes: 976
while x = gets.chomp.split(" ")
   s = x[0]
   t = x[1]
   break if s=="0" && t=="0"
   a = Array.new(10,-1)
   hit = 0
   blow = 0
   for i in 0..3
     a[s[i].to_i] = i
   end
   for i in 0..3
     if a[t[i].to_i] == i
       hit = hit + 1
     elsif a[t[i].to_i] != -1 
       blow = blow + 1
     end
   end
   print(hit," ",blow,"\n")
end


Measured memory_bytes: 6116
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]

if m == 1:
  print("IMPOSSIBLE")

else:
  root = [[] for i in range(n)]
  for a, b in ab:
    root[a-1].append(b-1)
  
  flag = False
  for j in root[0]:
    if n-1 in root[j]:
      flag = True
      break

  print("POSSIBLE" if flag else "IMPOSSIBLE")
        
    
    

Measured memory_bytes: 72508
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;


int main() {
	int n;
	cin >> n ;
	
	string s = to_string(n);
	int sums = 0;
	for (char c: s){
		sums += (int)(c - '0');
	}
	if (n % sums == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
}


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

using namespace std;
#define ll long long
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define PRINT(item) cout << (item) << endl;
#define PRINT_VEC(V)                                                           \
    for (auto v : (V))                                                         \
        cout << v << ' ';
const int MOD = 1000000007;
/* cout << fixed << setprecision(10) << decimal << endl; */

int main() {
    /* code */
    string S;
    cin >> S;
    if (S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <utility>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long int ll;

int main() {
  int N,M;
  cin>>N>>M;
  
  vector<int> H(N);
  for(int i=0;i<N;++i){
    cin>>H[i];
  }
  
  vector<bool> flag(N+1);
  rep(i,N+1){
    flag[i]=true;
  }
  
  rep(i,M){
    int A,B;
    cin>>A>>B;
    
    if(H[A-1]<=H[B-1])
      flag[A]=false;
    if(H[B-1]<=H[A-1])
      flag[B]=false;
  }
  
  int ans=0;
  for(int i=1;i<=N;++i){
    if(flag[i])
      ++ans;
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 3784
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <iomanip>
#include <set>
#include <sstream>
#include <cmath>
#include <deque>
#include <list>
#include <bitset>
using namespace  std;
typedef pair<long long , long long> P;
typedef long long ll;
typedef long long lint;
#define REP(i, n) for(long long (i)=0; (i)<(n); ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define FST first
#define SND second
const lint MOD = (lint) 1e9 + 7;
lint pow(lint n, lint x) {
    lint res = 1LL;
    while(x){
        if(x%2==1) res = (res*n) % MOD;
        x = x>>1;
        n= (n*n) % MOD;
    }
    return res%MOD;
}
lint factorial(lint n) {
    if(n<=1) return 1;
    else return (n * factorial(n-1))%MOD;
}
 
lint cmb(lint n, lint r){
    lint res = 1LL;
    r = min(r, n-r);
    for(lint i=n-r+1; i<=n; i++) res = (res*i)%MOD;
    res *= pow(factorial(r), MOD-2);
    return res % MOD;
}
signed main(){
    lint N, M, K; cin >> N>>M>>K;
    lint res = 0;
    lint a = cmb(N*M-2, K-2);
    for(int dx=0; dx<M; dx++){
        for(int dy=0; dy<N; dy++){
            if(dx==0 and dy==0) continue;
            lint cnt;
            if(dx==0 or dy==0) cnt = (M-dx)*(N-dy);
            else cnt = (M-dx)*(N-dy)*2;
            cnt = (cnt*a) %MOD;
            res = (res + cnt*(dx+dy)%MOD) %MOD; 
        }
    }
    cout << res % MOD << endl;
    return 0; 
}

Measured memory_bytes: 1280
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2
 
 
int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll>a(N);
	vector<ll>sum(N + 1);
	rep(i, 0, N)cin >> a[i];
	rep(i, 0, N)sum[i + 1] = sum[i] + a[i];
	vector<ll>b;
	rep(i, 0, N)rep(j, i, N)b.pb(sum[j + 1] - sum[i]);
 
 
	ll fl = 0;
	set<ll>st;
	set<ll>st2;
	rrep(i, 60, 0) {
		ll msk = 1LL << i;
		if (fl == 0) {
			rep(j, 0, b.size()) {
				if (msk&b[j]) {
					st.insert(j);
				}
			}
			if (st.size() >= K) {
				fl = 1;
			}else {
				st.clear();
			}
		}
		else {
			rep(j, 0, b.size()) {
				if ((msk&b[j]) && (st.count(j))) {
					st2.insert(j);
				}
			}
			if (st2.size() < K) {
              	st2.clear();
				continue;
			}
			else {
				st.clear();
              	fore(x,st2)st.insert(x);
				st2.clear();
			}
		}
	}
	
	if (st.size() >= K) {
		ll ans = b[*st.begin()];
		st.erase(st.begin());
		fore(x, st)ans = ans & b[x];
		cout << ans << endl;
	}
	else {
		cout << 0 << endl;
	}
 
	return 0;
}

Measured memory_bytes: 10736
N = input()
K = int(input())

def K1(num):
	return int(num[0]) + (len(num)-1)*9

def K2(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K1(tmp)
	out1 = (int(num[0])-1)*(L-1)*9
	out2 = ((L-1)*(L-2)//2)*9*9
	return out + out1 + out2

def K3(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K2(tmp)
	out1 = (int(num[0])-1)*((L-1)*(L-2)//2)*9*9
	out2 = ((L-1)*(L-2)*(L-3)//6)*9*9*9
	return out + out1 + out2

if len(N) < K:
	ans = 0
else:
	if K == 1:
		ans = K1(N)
	elif K==2:
		ans = K2(N)
	else:
		ans = K3(N)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 3005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next;
}E[MAXN * 2];
int N,head[MAXN],sumE;
int64 A[MAXN],rem[MAXN];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
bool dfs(int u,int fa) {
    int64 s = 0;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    if(!dfs(v,u)) {
		if(A[u] > A[v]) return true;
	    }
	}
    }
    return false;
    
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(A[i]);
    int a,b;
    for(int i = 1 ; i < N ; ++i) {
	read(a);read(b);
	add(a,b);add(b,a);
    }
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
	if(dfs(i,0)) {out(i);space;}
    }
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 512
// プログラミングコンペティションサイト AtCode は、プログラミングコンテストを定期的に開催しています。
//
// AtCode で次に開催されるコンテストは ABC と呼ばれ、レーティングが 1200 未満の参加者のレーティングが変動します。
//
// その次に開催されるコンテストは ARC と呼ばれ、レーティングが 2800 未満の参加者のレーティングが変動します。
//
// そのさらに次に開催されるコンテストは AGC と呼ばれ、すべての参加者のレーティングが変動します。
//
// 高橋くんの AtCode でのレーティングは R です。彼のレーティングが変動する次のコンテストは何でしょうか？
//



#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(int argc, char const *argv[])
{
  int R;
  std::cin >> R;
  if(R < 1200){
    cout << "ABC"<< endl;
  }else if(R < 2800){
    cout << "ARC"<< endl;
  }
  if(R >= 2800){
    cout << "AGC"<< endl;
  }

  return 0;
}


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

int main(){
    ll n,m,targets;
    cin>>n>>m>>targets;
    unordered_map<int,int> row;
    unordered_map<int,int> col;
    set<pair<int,int>> s;
    ll t =targets;
    while(t--){
        ll x,y;
        cin>>x>>y;
        s.insert(make_pair(x,y));
        row[x]++;
        col[y]++;
    }
    /*for(auto g:row)cout<<g.first<<" "<<g.second<<" ";
    cout<<endl;
    for(auto g:col)cout<<g.first<<" "<<g.second<<" ";
    cout<<endl;*/
    int maxx = INT_MIN;
    unordered_set<int> index1,index2;
    for(auto cur:row){
        maxx = max(maxx,cur.second);
    }
    //cout<<maxx<<endl;
    for(auto cur:row){
        if(cur.second==maxx){
            index1.insert(cur.first);
        }
    }
    //for(auto g:index1)cout<<g<<endl;    
    int maxx2 = INT_MIN;
    for(auto cur:col){
        maxx2 = max(maxx2,cur.second);
    }
    //cout<<maxx2<<endl;
    for(auto cur:col){
        if(cur.second==maxx2){
            index2.insert(cur.first);
        }
    }
    //for(auto g:index2)cout<<g<<endl;    
    ll limit = (index1.size())*(index2.size());
    for(auto x:s){
        if(index1.find(x.first)!=index1.end() && index2.find(x.second)!=index2.end()){
            limit--;
        } 
    }
    if(limit>0)cout<<maxx+maxx2;
    else cout<<maxx+maxx2-1;
    //if(limit==targets)cout<<maxx+maxx2-1;
    //else cout<<maxx+maxx2;








    return 0;
}

Measured memory_bytes: 71712
#include<string>
#include<vector>
#include<iostream>

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

using namespace std;

void dfs(int i,int n,const string dic[100],const bool b[300][100],vector<string> &tmp,vector<string> &ans){
	if(i==-1){
		string res;
		for(int j=(int)tmp.size()-1;j>=0;j--){
			res+=tmp[j];
			if(j>0) res+=' '; else res+='.';
		}
		ans.push_back(res);
		return;
	}

	rep(j,n) if(b[i][j]) {
		int m=dic[j].length();
		tmp.push_back(dic[j]);
		dfs(i-m,n,dic,b,tmp,ans);
		tmp.pop_back();
	}
}

int main(){
	char f[128];
	f['a']='2'; f['b']='2'; f['c']='2';
	f['d']='3'; f['e']='3'; f['f']='3';
	f['g']='4'; f['h']='4'; f['i']='4';
	f['j']='5'; f['k']='5'; f['l']='5';
	f['m']='6'; f['n']='6'; f['o']='6';
	f['p']='7'; f['q']='7'; f['r']='7'; f['s']='7';
	f['t']='8'; f['u']='8'; f['v']='8';
	f['w']='9'; f['x']='9'; f['y']='9'; f['z']='9';

	for(int n;cin>>n,n;){
		string dic[100];
		rep(i,n) cin>>dic[i];
		string seq; cin>>seq;

		string num[100];
		rep(i,n) rep(j,dic[i].length()) num[i]+=f[dic[i][j]];

		bool b[300][100]={}; // b[i][j] := ( num[j] が seq[0..i] の suffix かどうか )
		int cnt[300]={};
		rep(i,seq.length()){
			rep(j,n){
				int m=num[j].length();
				if(m<=i+1 && num[j]==seq.substr(i-m+1,m) && (i-m==-1 || cnt[i-m]>0)){
					b[i][j]=true;
					cnt[i]++;
				}
			}
		}

		vector<string> ans,tmp;
		dfs(seq.length()-1,n,dic,b,tmp,ans); // 具体的な割り当てを復元
		rep(i,ans.size()) cout<<ans[i]<<endl;
		cout<<"--"<<endl;
	}

	return 0;
}

Measured memory_bytes: 1272
a, b, c, d = gets.chomp.split.map(&:to_i)

i = 0
while true
  if i.even?
    c -= b
    if c <= 0
      puts 'Yes'
      exit
    end
  else
    a -= d
    if a <= 0
      puts 'No'
      exit
    end
  end

  i += 1
end


Measured memory_bytes: 14308
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18

priority_queue<llint,vector<llint>,greater<llint>> que;
priority_queue<llint> q;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

llint n;


void solve(){
	cin >> n;
	llint a[n];
	llint mx=0;
	llint mn=inf;
	for(int i=0;i<n;i++){
		cin >> a[i];
		if(a[i]<mn)mn=a[i];
		if(a[i]>mx)mx=a[i];
	}
	cout << mx-mn << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
const int N = 110;
int _w;

int n, m;
vector<int> odd, even;

int main() {
	cin >> m >> n;
	for( int i = 1; i <= n; ++i ) {
		int a;
		cin >> a;
		if( a & 1 ) odd.push_back(a);
		else even.push_back(a);
	}
	if( odd.size() > 2 )
		return puts("Impossible"), 0;
	if( odd.size() == 0 ) {
		for( int i = 0; i < (int)even.size(); ++i )
			printf( "%d ", even[i] );
		puts("");
		if( even.size() == 1 ) {
			int a = even[0];
			puts("2");
			printf( "%d %d\n", a-1, 1 );
		} else {
			printf( "%d\n", (int)even.size() );
			printf( "%d ", even[0]+1 );
			for( int i = 1; i < (int)even.size()-1; ++i )
				printf( "%d ", even[i] );
			printf( "%d\n", *even.rbegin()-1 );
		}
	} else if( odd.size() == 1 ) {
		for( int i = 0; i < (int)even.size(); ++i )
			printf( "%d ", even[i] );
		printf( "%d\n", odd[0] );
		if( even.size() ) {
			printf( "%d\n", odd[0] == 1 ? n-1 : n );
			printf( "%d ", even[0]+1 );
			for( int i = 1; i < (int)even.size(); ++i )
				printf( "%d ", even[i] );
			if( odd[0] != 1 )
				printf( "%d\n", odd[0]-1 );
		} else {
			int a = odd[0];
			if( a != 1 ) {
				puts("2");
				printf( "%d %d\n", a-1, 1 );
			} else {
				puts("1"), puts("1");
			}
		}
	} else {
		printf( "%d ", odd[0] );
		for( int i = 0; i < (int)even.size(); ++i )
			printf( "%d ", even[i] );
		printf( "%d\n", odd[1] );
		printf( "%d\n", odd[1] == 1 ? n-1 : n );
		printf( "%d ", odd[0]+1 );
		for( int i = 0; i < (int)even.size(); ++i )
			printf( "%d ", even[i] );
		if( odd[1] != 1 )
			printf( "%d\n", odd[1]-1 );
	}
	return 0;
}


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

struct edge {int from;int to;ll cost;};

typedef pair<ll, ll> P;

vector<edge> es;

ll dist[2505];
ll inf=1ll<<50;
std::vector<int> rev_g[2505];
int ok[2505];
ll n,m,p;

void bfs(int v) {
  ok[v]=1;
  for(auto u : rev_g[v]) {
    if(ok[u])continue;
    bfs(u);
  }
}

bool solve_bf(){
  dist[0]=0;
  for(int i=0;i<n;i++){
    bool update = 0;
    for(auto e : es) {
      if(ok[e.from] &&ok[e.to] && dist[e.from] != inf && dist[e.to]>dist[e.from]+e.cost){
        dist[e.to]=dist[e.from]+e.cost;
        update=1;
      }
    }
    if(!update)break;
    if(i==n-1){
      cout<<-1<<endl;
      exit(0);
    }
  }
  return true;
}

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

  for(int i=0;i<2505;i++)dist[i]=inf;

  cin>>n>>m>>p;
  for(int i=0;i<m;i++){
    int a,b;ll c;cin>>a>>b>>c;a--;b--;
    es.push_back({a,b,-c+p});
    rev_g[b].push_back(a);
  }

  bfs(n-1);
  solve_bf();

  cout<<max(dist[n-1]*-1, 0ll)<<endl;

  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N;
ll A[MAX_N];
ll B[MAX_N];

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

  cin >> N;
  rep(i, N) cin >> A[i];
  rep(i, N) cin >> B[i];

  vector<Pll> vp;
  ll sum_neg = 0, sum_pos = 0;
  for (int i = 0; i < N; ++i) {
      vp.push_back(Pll(A[i]-B[i], i));
      if (A[i]-B[i] >= 0) {
          sum_pos += A[i]-B[i];
      } else {
          sum_neg += B[i]-A[i];
      }
  }

  if (sum_pos < sum_neg) {
      cout << -1 << endl;
      return 0;
  }
  if (sum_neg == 0) {
      cout << 0 << endl;
      return 0;
  }
  
  sort(all(vp));
  reverse(all(vp));

  int ans = 0;
  for (int i = 0; i < N; ++i) {
      ++ans;
      sum_neg -= vp[i].first;
      if (sum_neg <= 0) break;
  }

  for (int i = 0; i < N; ++i) {
      if (vp[i].first < 0) ++ans;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5108
#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i)
    std::cin >> a.at(i);

  int count = 0;
  for (int i = 0; i < n; ++i) {
    while (a.at(i) % 2 == 0) {
      a.at(i) /= 2;
      ++count;
    }
  }
  std::cout << count << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int main(){
	int N;
	int line[4][100001]={};
	char s[100001];
	cin>>N;
	cin>>s;
	line[0][0]=1;
	line[0][1]=1;
	line[1][0]=2;
	line[1][1]=2;
	line[2][0]=1;
	line[2][1]=2;
	line[3][0]=2;
	line[3][1]=1;
	bool flag[4]={};
	bool flag2[4]={};
	for(int i=0;i<4;i++){
		//printf("flag[%d]=%d\n",i,flag[i]);
	}
	for(int i=0;i<4;i++){
		for(int j=1;j<N-1;j++){
			if(line[i][j]==1 && line[i][j-1]==1){
				if(s[j]=='o')
					line[i][j+1]=1;
				else
					line[i][j+1]=2;
			}
			if(line[i][j]==1 && line[i][j-1]==2){
				if(s[j]=='o')
					line[i][j+1]=2;
				else
					line[i][j+1]=1;
			}
			if(line[i][j]==2 && line[i][j-1]==1){
				if(s[j]=='o')
					line[i][j+1]=2;
				else
					line[i][j+1]=1;
			}
			if(line[i][j]==2 && line[i][j-1]==2){
				if(s[j]=='o')
					line[i][j+1]=1;
				else
					line[i][j+1]=2;
			}
		}

		if(line[i][N-1]==1 && line[i][N-2]==1){
			if(s[N-1]=='o'){
				if(line[i][0]==1)
					flag[i]=1;
			}
			else{
				if(line[i][0]==2)
					flag[i]=1;
			}
		}
		if(line[i][N-1]==1 && line[i][N-2]==2){
			if(s[N-1]=='o'){
				if(line[i][0]==2)
					flag[i]=1;
			}
			else{
				if(line[i][0]==1)
					flag[i]=1;
			}
		}
		if(line[i][N-1]==2 && line[i][N-2]==1){
			if(s[N-1]=='o'){
				if(line[i][0]==2)
					flag[i]=1;
			}
			else{
				if(line[i][0]==1)
					flag[i]=1;
			}
		}
		if(line[i][N-1]==2 && line[i][N-2]==2){
			if(s[N-1]=='o'){
				if(line[i][0]==1)
					flag[i]=1;
			}
			else{
				if(line[i][0]==2)
					flag[i]=1;
			}
		}

//
		if(line[i][0]==1 && line[i][1]==1){
			if(s[0]=='o'){
				if(line[i][N-1]==1)
					flag2[i]=1;
			}
			else{
				if(line[i][N-1]==2)
					flag2[i]=1;
			}
		}
		if(line[i][0]==1 && line[i][1]==2){
			if(s[0]=='o'){
				if(line[i][N-1]==2)
					flag2[i]=1;
			}
			else{
				if(line[i][N-1]==1)
					flag2[i]=1;
			}
		}
		if(line[i][0]==2 && line[i][1]==1){
			if(s[0]=='o'){
				if(line[i][N-1]==2)
					flag2[i]=1;
			}
			else{
				if(line[i][N-1]==1)
					flag2[i]=1;
			}
		}
		if(line[i][0]==2 && line[i][1]==2){
			if(s[0]=='o'){
				if(line[i][N-1]==1)
					flag2[i]=1;
			}
			else{
				if(line[i][N-1]==2)
					flag2[i]=1;
			}
		}
	}
	for(int i=0;i<4;i++){
		//printf("flag[%d]=%d\n",i,flag[i]);
	}
	for(int i=0;i<4;i++){
		if(flag[i]==1 && flag2[i]==1){
			for(int j=0;j<N;j++){
				if(line[i][j]==1)
					printf("S");
				else if(line[i][j]==2)
					printf("W");
				else
					printf("err");
			}
			printf("\n");
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>
int main(void)
{
int n,a,b;
scanf("%d",&n);
for (a = 9;a > 0;a--)
{
    for (b = 9;b > 0;b--)
    {
        if (a*b == n)
        {
            break;
        }
    }
if (a*b == n)
{
    break;
}
}
if (a*b == n)
{
    printf("Yes");
}
else{
    printf("No");
}
return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<complex>
using namespace std;

int main(){
    int house[4][3][10] = {};
    int n, b, f, r, v;
    cin >> n;

    for (int i=0;i<n;i++){
        cin >> b >> f >> r >> v;
        house[b-1][f-1][r-1] += v;
    }

    for(int b=0;b<4;b++){
        for (int f=0;f<3;f++){
            for (int r=0;r<10;r++){
                cout <<" "<<house[b][f][r];
            }
            cout << endl;
        }
        if (b!=3){
            cout <<"####################" <<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3096
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int k,n,m = 0,sum = 0;

        k = sc.nextInt();
        
        for(int a = 1; a <= k; a++){
            for(int b = 1; b <= k; b++){
                for(int c = 1; c <= k; c++){
                    
                    int x,y,z,tmp;
                    x = a;
                    y = b;
                    z = c;
                    
                    if(a < b){
                        x = b;
                        y = a;
                    }
                    
                    
                    while ((tmp = x % y) != 0) {
                        x = y;
                        y = tmp;
                    }
                    
                    while ((tmp = y % z) != 0) {
                        y = z;
                        z = tmp;
                    }
                    
                    sum += z;

                }
            }
            
        }
        
        System.out.println(sum);
    }
}


Measured memory_bytes: 35764
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] arg) {
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			int K = sc.nextInt();
			int M = sc.nextInt();
			int[] next = new int[N];
			int[] prev = new int[N];
			for (int i = 0; i < N; ++i) {
				next[i] = (i + 1) % N;
				prev[i] = (i + N - 1) % N;
			}
			int pos = M - 1;
			next[prev[pos]] = next[pos];
			prev[next[pos]] = prev[pos];
			for (int i = 0; i < N - 2; ++i) {
				pos = prev[pos];
				int k = K % (N - 1 - i);
				for (int j = 0; j < k; ++j) {
					pos = next[pos];
				}
				next[prev[pos]] = next[pos];
				prev[next[pos]] = prev[pos];
			}
			System.out.println(next[pos] + 1);
		}
	}

}

Measured memory_bytes: 26284
import java.io.*;
 
class Main{
	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder str = new StringBuilder();
		
		while(true){
			String temp[] = br.readLine().split(" ");
			int x = Integer.parseInt(temp[0]);
			int y = Integer.parseInt(temp[1]);
			if(x == 0 && y == 0){
				break;
			}
			if(x>y){
				int tmp;
				tmp = x;
				x = y;
				y = tmp;
			}
			str.append(x + " " + y + "\n");
		}
		System.out.print(str);

	}
}

Measured memory_bytes: 25024
import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner scn = new Scanner(System.in);
        
        while(true){
            int n = scn.nextInt();
            int x = scn.nextInt();
            int count=0;
        if(n==0 && x==0)break;


            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    for(int k=j+1;k<=n;k++){
                        if(i+j+k==x){
                            count++;
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}

Measured memory_bytes: 19608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(int &x,int y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
int n,a[1000005],fac[1000005],ans,cnt[4],mup=1;char s[1000005];
int C(int x,int y){
    return fac[x] - fac[y] - fac[x - y];
}
int main()
{
    scanf("%d%s",&n,s+1);
    rep(i,1,n) a[i] = s[i] - 49, cnt[a[i]]++;
    rep(i,1,n){
        fac[i] = fac[i-1];
        int ii = i;
        while(ii % 2 == 0) {
            ii /= 2;
            fac[i]++;
        }
    }
    int pp = (cnt[0]>0) + (cnt[1]>0) + (cnt[2]>0);
    if(pp <= 1){puts("0");return 0;}
    if(cnt[0] && cnt[1] && cnt[2]){
        rep(i,1,n) if(a[i] == 2) a[i] = 0;
    }
    else if(cnt[0] && cnt[2]){
        mup = 2;
    }
    else if(cnt[1] && cnt[2]){
        rep(i,1,n) a[i]--;
    }
    rep(i,1,n) if(a[i]) {
        ans ^= (C(n - 1,i - 1) == 0);
    }
    printf("%d\n",ans * mup);
    return 0;
}

Measured memory_bytes: 9088