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

#define rep(i,N) for(int i=0; i<(N); i++)
#define pb push_back

typedef long long ll;
typedef pair<int,int> P;
const ll mod=1e9+7;

ll A,B;

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>A>>B;

//A-K=B-K
//A-K=K-B
//K-A=B-K
if((A+B)%2){
	cout<<"IMPOSSIBLE"<<endl;
}else{
	cout<<(A+B)/2<<endl;
}



}
	


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
void merge(int*,int,int,int);
void mergeSort(int*,int,int);
int cnt=0;

int main(void) {
	int n,l,m,r,i;
	int *M;
	
	scanf("%d",&n);
	M=(int *)malloc(n * sizeof(int));
	for(i = 0; i <n; i++) scanf("%d",&M[i]);
		l = 0;
		r = n;
		mergeSort(M,l,r);
		for(i=0;i<n;i++) {
			if(i==n-1)printf("%d",M[i]);
			else printf("%d ",M[i]);
		}
		printf("\n");
		printf("%d\n",cnt);
		free(M);
		return 0;
}

	
	void merge(int M[],int l ,int m, int r) {
		int  p = m-l;
		int  q = r-m;
		int L[p],R[q];
		int i;
		
		for(i = 0; i<p;i++) L[i] = M[l+i];
		for(i=0;i<q;i++) R[i] = M[m+i];
		L[p] = 2000000000;
		R[q] = 2000000000;
		i=0;
		int j=0;
		for(int k = l; k < r; k++) {
			if(L[i]<=R[j]) {
				M[k]=L[i];
				i+=1;
				cnt++;
			}
			else {
				M[k]=R[j];
				j+=1;
				cnt++;
			}
		}
	}
	
	void mergeSort(int M[],int l,int r) {
		if(l+1 < r) {
			int m=(l+r)/2;
			mergeSort(M,l,m);
			mergeSort(M,m,r);
			merge(M,l,m,r);
		}
	}


Measured memory_bytes: 5488
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007


int main() {
	ll n,k;
	vector<ll>a;
	cin>>n>>k;
	k--;
	for(int i=0;i<n;i++){
		ll x;
		cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	ll ans=INF;
	for(int i=0;i<n-k;i++){
		ll now = a[i+k]-a[i];
		ans=min(ans,now);
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1400
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
toBit(x,r)=Bool[(x>>(r-i))%2==1 for i in 1:r]
function fromBit(a::Array{Bool,1},r)
	x = 0
	for i in 1:r
		x += a[i]*(2^(r-i))
	end
	x
end
bsnand(a::Array{Bool,1},b::Array{Bool,1},r)=Bool[!a[i]&&b[i] for i in 1:r]
bsxor(a::Array{Bool,1},b::Array{Bool,1},r)=Bool[a[i]$b[i] for i in 1:r]

function GaussJordan(a::Array{Array{Bool,1},1},n,m)
	o = min(n,m)
	for i in 1:o
		for j in i:m
			f = 0
			for k in i:n
				if a[k][j]
					tmp = a[i]
					a[i] = a[k]
					a[k] = tmp
					for l in k+1:n
						if a[l][j]
							a[l] = bsxor(a[l],a[i],m)
						end
					end
					f = 1
					break
				end
			end
			if f == 1
				break
			end
		end
	end
	for i in 1:o
		j = 0
		for q in 1:m
			if a[o-i+1][q]
				j = q
				break
			end
		end
		if j>0
			for k in i+1:o
				if a[o-k+1][j]
					a[o-k+1] = bsxor(a[o-k+1],a[o-i+1],m)
				end
			end
		end
	end
	a
end


function main()
	n = readline() |> parseInt
	ar = readline() |> split |> parseMap
	o = 0
	for i in 1:n
		o = o$ar[i]
	end
	x = toBit(o,60)
	g = [toBit(ar[i],60) for i in 1:n]
	for i in 1:n
		g[i] = bsnand(x,g[i],60)
	end
	g=GaussJordan(g,n,60)
	yg = g[1]
	for i in 2:min(n,60)
		yg = bsxor(yg,g[i],60)
	end
	y = fromBit(yg,60)
	println(2*y+fromBit(x,60))
end

main()

Measured memory_bytes: 162880
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

namespace tk {
template<typename T>
T gcd(T a, T b) {
	assert(a >= 0);
	assert(b >= 0);
	while (b != 0) {
		T t = a % b;
		a = b; b = t;
	}
	return a;
}

template<typename T>
T lcm(T a, T b) {
	assert(a >= 0);
	assert(b >= 0);
	if (a == 0 || b == 0) return 0;
	return a / gcd(a, b) * b;
}

template<typename T>
T ext_gcd(const T & a, T & x, const T & b, T & y) {
	assert(a > 0);
	assert(b > 0);
	T a0 = a, a1 = 1, a2 = 0, b0 = b, b1 = 0, b2 = 1;
	while (b0 > 0) {
		T q = a0 / b0, r = a0 % b0;
		T nb1 = a1 - q * b1, nb2 = a2 - q * b2;
		a0 = b0; b0 = r;
		a1 = b1; b1 = nb1;
		a2 = b2; b2 = nb2;
	}
	x = a1;
	y = a2;
	return a0;
}

template<typename T>
T mod_pow(T x, T n, const T & mod) {
	assert(mod > 0);
	assert(n >= 0);
	x = (x % mod + mod) % mod;
	T res = 1 % mod;
	while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

template<typename T>
T mod_inv(T x, const T & mod) {
	assert(mod > 0);
	T a, b;
	T g = ext_gcd(x, a, mod, b);
	assert(g == 1);
	return (a % mod + mod) % mod;
}

template<typename T>
std::pair<bool, T> chinese_remainder(T b1, const T & m1, T b2, const T & m2) {
	assert(m1 > 0);
	assert(m2 > 0);
	b1 = (b1 % m1 + m1) % m1;
	b2 = (b2 % m2 + m2) % m2;
	T p, q;
	T g = ext_gcd(m1, p, m2, q);
	if ((b2 - b1) % g != 0) return {false, 0};
	const T mod = m1 * m2;
	T res = b1 + (b2 - b1) / g * m1 * p;
	return {true, (res % mod + mod) % mod};
}
}

vector<ll> find_divisor(ll n) {
	vector<ll> divisor;
	
	ll i = 1;
	for (; i * i <= n; i++) if (n % i == 0) divisor.push_back(i);
	i--;
	if (i * i == n) i--;
	for (; i >= 1; i--) if (n % i == 0) divisor.push_back(n / i);
	
	return divisor;
}

int main() {
	ll N;
	cin >> N;
	N *= 2;
	
	ll ans = longINF;
	auto div = find_divisor(N);
	
	for (auto x : div) {
		ll y = N / x;
		// k(k + 1) \equiv 0 (mod. N)
		// x | k, y | k + 1
		// k \equiv 1 (mod. x)
		// k \equiv -1 (mod. y)
		auto res = tk::chinese_remainder<__int128_t>(0, x, y - 1, y);
		if (!res.first) continue;
		
		ll p = res.second;
		if (p == 0) p += x * y;
		chmin(ans, p);
	}
	
	cout << ans << endl;
	return 0;
}


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

#define lli long long int
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define INF 1000000007
#define endl "\n"
#define max(aa, bb) (aa > bb ? aa : bb)
#define min(aa, bb) (aa < bb ? aa : bb)

lli dp[100005][105], n;
vector<lli> val, w;

lli knapsack(lli x, lli i){
    lli &tmp=dp[x][i];
    if(tmp!=-1) return tmp;
    if(x<=0 || i>=n) return 0;

    if(w[i]<=x) return tmp=max(knapsack(x-w[i], i+1)+val[i], knapsack(x, i+1));
    else return tmp=knapsack(x,i+1);
}

int main(){
    lli x;
    cin>>n>>x;
    lli a,b;
    for(lli i=0;i<n;i++){
        cin>>a>>b;
        w.pb(a);
        val.pb(b);
    }
    memset(dp, -1, sizeof(dp));
    cout<<knapsack(x, 0);
}

Measured memory_bytes: 85628
N , M = input().split()

N = int(N)
M = int(M)


PYin = []
for i in range(M):
    p,y = input().split()
    p = int(p)
    y = int(y)
    PYin.append([p,y,i])

PYin.sort()
now = 0
num = 0

for lis in PYin:
    
    if (lis[0] == now) :
        num += 1
        lis.append(num)

    else:
        now = lis[0]
        num = 1
        lis.append(num)


iPn = []

for lis in  PYin:

    iPn.append([ lis[2],lis[0],lis[3] ])

iPn.sort()

for nlis in iPn:

    print (str(nlis[1]).zfill(6) + str(nlis[2]).zfill(6))
        


Measured memory_bytes: 41016
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k, a = 0;
    string s;
    cin >> n >> k >> s;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1])
            a++;
    }
    cout << min(k * 2 + a, n - 1) << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

// #define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vll vector<ll>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
   
const ll Mod = 1e9 + 7;
int n , m;
string Arr[1005];
int dx[] = {1 , 0 , 0 , -1};
int dy[] = {0 ,-1 , 1 ,  0};
bool visited[1005][1005];
bool check(int x , int y){
    if(x >= 0 && x < n && y >= 0 && y < m && !visited[x][y] && Arr[x][y] == '.')
        return true;
    return false;
}

int main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n >> m;
    for(int i =0 ;i < n; i++)
        cin >> Arr[i];

    queue<pair<int, int> > q;
    for(int i = 0 ;i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            if(Arr[i][j] == '#'){
                q.push(mp(i , j));
                visited[i][j] = true;
            }
        }
    }
    int Count = 0;
    while(q.size()){
        int size = q.size();
        bool f = false;
        for(int k = 0 ; k < size ; k++){
            pair<int, int> p = q.front();
            q.pop();
            for(int z = 0 ;z < 4 ; z++){
                if(check(p.F+dx[z] , p.S+dy[z])){
                    f = true;
                    q.push(mp(p.F+dx[z] , p.S + dy[z]));
                    visited[p.F+dx[z]][p.S+dy[z]] = true;
                }
            }
        }
        if(f)
            Count++;
    }

    cout << Count << endl;

   return 0;
}

Measured memory_bytes: 10512
# encoding: utf-8


class Solution:
    @staticmethod
    def linear_search():
        array_length_1 = int(input())
        array_1 = [int(x) for x in input().split()]
        array_length_2 = int(input())
        array_2 = [int(x) for x in input().split()]

        print(len(set(array_1).intersection(set(array_2))))


if __name__ == '__main__':
    solution = Solution()
    solution.linear_search()

Measured memory_bytes: 8432
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    string s;
    cin >> s;
    if (s.size() < 4) {
        cout << "No" << endl;
    } else if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I') {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}


int dfs(int x, int y){
    if( x % y == 0) return 2 * y * (int( x / y ) - 1) + y; 
    return 2 * y * int( x / y) + dfs(y, x% y); 
}

signed main(){
    int n,x;
    cin >> n >> x;
    if( n - x < x) x = n - x;
    cout << n + dfs(n - x , x) << endl;

}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;
const int max_n = 200005;

int m, n;

int dist[max_n];
int par[max_n];

map<PII, int> e;

int fufind(int v) {
	if (v == par[v]) return v;
	int x = fufind(par[v]);
	dist[v] += dist[par[v]];

	par[v] = x;
	return x;
}


int main() {
	read2(n, m);
	FOR(i,0,n) dist[i] = 0;
	FOR(i,0,n) par[i] = i;
	FOR(i,0,m) {
		make3(l, r, d);
		l--; r--;
		int a = fufind(l);
		int b = fufind(r);

		int x = dist[l];
		int y = dist[r];
		if (a == b) {
			if (d + y - x != 0) {
				printf("No\n");
				return 0;
			}
		} else {
			par[a] = b;
			e[mp(a,b)] = d + y - x;
			dist[a] = d + y - x;
		}
	}
	printf("Yes\n");
}


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

typedef long long ll;
ll mod=1000000007;

ll pow(ll u,ll a){
    if(a==1) return u;
    if(a==0) return 1;
    if(a%2==0) return pow(u,a/2)*pow(u,a/2)%mod;
    return pow(u,a-1)*u%mod;
}

ll com(ll a,ll b){
    ll ans=1;
    for(ll i=a;i>=a-b+1;i--){
        ans=ans*i%mod;
    }
    for(ll i=1;i<=b;i++){
        ans=ans*pow(i,mod-2)%mod;
    }
    return ans;
}

int main(){
    
    ll H,W,A,B;cin>>H>>W>>A>>B;
    ll ans=0;
    ll X=com(H-A-1+B,H-A-1)*com(A-2+W-B,A-1)%mod;
    for(int i=1;i<=W-B;i++){
        ans+=/*(com(H-A-1+B+i,H-A-1)*com(A-2+W-B-i,A-1)%mod)*/X;
        X=X*(H-A-1+B+i)%mod;
      X=X*pow(B+i,mod-2)%mod;
      X=X*(W-B-i)%mod;
        X=X*pow(A-1+W-B-i,mod-2)%mod;
        ans=ans%mod;
    }
    cout<<ans<<endl;
}



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

int main() {
	int N, Q;

	cin >> N >> Q;
	vector<int> S( N );
	vector<int> T( N );
	vector<int> X( N );
	for( int i = 0; i < N; i++ ) {
		cin >> S[i] >> T[i] >> X[i];
	}
	vector<int> D( Q );
	for( int i = 0; i < Q; i++ ) {
		cin >> D[i];
	}

	vector<tuple<int, int, int>> v;
	for( int i = 0; i < N; i++ ) {
		v.push_back( make_tuple( S[i] - X[i], 1, X[i] ) );
		v.push_back( make_tuple( T[i] - X[i], -1, X[i] ) );
	}
	sort( v.begin(), v.end() );
	int j = 0;
	set<int> a;
	for( int i = 0; i < Q; i++ ) {
		while( j < v.size() && get<0>( v[j] ) <= D[i] ) {
			if( get<1>( v[j] ) > 0 ) {
				a.insert( get<2>( v[j] ) );
			}
			else {
				a.erase( get<2>( v[j] ) );
			}
			j++;
		}
		int ans = -1;
		if( !a.empty() ) {
			ans = *a.begin();
		}
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 18412
#include"bits/stdc++.h"
//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
//const int mod = 1e9 + 7;

int main() {
	int w, h, n;
	int x[102], y[102], a[102];
	int lx=0, rx=INT_MAX, ly=0, ry=INT_MAX;
	cin >> w >> h >> n;
	rep(i, 0, n) { cin >> x[i] >> y[i] >> a[i]; }
	rep(i, 0, n) {
		if (a[i] == 1 && lx < x[i]) { lx = x[i]; }
		else if (a[i] == 2 && rx > x[i]) { rx = x[i]; }
		else if (a[i] == 3 && ly < y[i]) { ly = y[i]; }
		else if (a[i] == 4 && ry > y[i]) { ry = y[i]; }
	}
	if (rx != INT_MAX) { rx = w - rx; w = w - (lx + rx);}
	else { w -= lx; }
	if (ry != INT_MAX) { ry = h - ry; h = h - (ly + ry);}
	else { h -= ly; }
	if (w <= 0 || h <= 0) { print(0); }
	else {print(w*h); }
	return 0;
}

Measured memory_bytes: 256
# 11th
n = int(input())
a = [[int(i) for i in input().split()] for j in range(n)]
t = [i[0] for i in a]
x = [i[1] for i in a]
y = [i[2] for i in a]
tmpt=0
tmpx=0
tmpy=0
for i in range(n):
    tmp = (t[i] - tmpt) - abs(x[i] - tmpx) - abs(y[i] - tmpy)
    tmpt = t[i]
    tmpx = x[i]
    tmpy = y[i]
    if tmp >= 0 and tmp%2 == 0:
        continue
    print("No")
    break
else:
    #最後までfor文がbreakしなかった場合
    print("Yes")

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

#define MAXDIFF (80*160)

int dp[80][80][MAXDIFF] = {0};
int grida[80][80], gridb[80][80];

int main(void) {
	int h, w;
	scanf("%d%d", &h, &w);

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			scanf("%d", &grida[i][j]);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			scanf("%d", &gridb[i][j]);

	dp[0][0][abs(grida[0][0] - gridb[0][0])] = 1;
	for (int i = 1; i < h; i++) {
		int cur = abs(grida[i][0] - gridb[i][0]);
		for (int k = 0; k < MAXDIFF; k++) {
			if (dp[i-1][0][k]) {
				dp[i][0][abs(k+cur)] = 1;
				dp[i][0][abs(k-cur)] = 1;
			}
		}
	}
	for (int j = 1; j < w; j++) {
		int cur = abs(grida[0][j]-gridb[0][j]);
		for (int k = 0; k < MAXDIFF; k++) {
			if (dp[0][j-1][k]) {
				dp[0][j][abs(k+cur)] = 1;
				dp[0][j][abs(k-cur)] = 1;
			}
		}
	}

	for (int i = 1; i < h; i++) {
		for (int j = 1; j < w; j++) {
			int cur = abs(grida[i][j]-gridb[i][j]);
			for (int k = 0; k < MAXDIFF; k++) {
				if (dp[i-1][j][k] || dp[i][j-1][k]) {
					dp[i][j][abs(k+cur)] = 1;
					dp[i][j][abs(k-cur)] = 1;
				}
			}
		}
	}

	for (int k = 0; k < MAXDIFF; k++) {
		if (!dp[h-1][w-1][k])
			continue;
		printf("%d\n", k);
		break;
	}
}


Measured memory_bytes: 318592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n;
    cin >> n;
    vector<PII> p(n);
    REP(i, n) {
        ll u, v;
        cin >> u >> v;
        p[i] = minmax(u, v);
    }
    
    sort(ALL(p));
    ll mi = INF, ma = -INF;
    ll idx1 = -1, idx2 = -1;
    vector<ll> x(n), y(n);
    REP(i, n) {
        x[i] = p[i].first, y[i] = p[i].second;
        if(mi > x[i]) mi = x[i], idx1 = i;
        if(ma < y[i]) ma = y[i], idx2 = i;
    }
    dump(x, y);

    ll rmin = INF, rmax = -INF, bmin = INF, bmax = -INF;
    REP(i, n) {
        chmin(rmin, x[i]);
        chmax(rmax, x[i]);
        chmin(bmin, y[i]);
        chmax(bmax, y[i]);
    }
    ll ret = (rmax - rmin) * (bmax - bmin);
    dump(ret);

    multiset<ll> st;
    st.insert(y[idx1]);
    st.insert(x[idx2]);
    REP(i, n) {
        if(i == idx1 || i == idx2) continue;
        st.insert(x[i]);   
    }
    dump(st);
    chmin(ret, (ma-mi) * (*st.rbegin() - *st.begin()));
    REP(i, n) {
        if(i == idx1 || i == idx2) continue;
        st.erase(st.find(x[i]));
        st.insert(y[i]);
        dump(st);
        chmin(ret, (ma-mi) * (*st.rbegin() - *st.begin()));
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long int lli;
#define tc int t;cin>>t;while(t--)
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>


int main() {
   lli per,n;
   cin>>per>>n;
   lli a[n];
   for(int i=0;i<n;i++)
    cin>>a[i];

   lli mx=a[0]+per-a[n-1];

   for(int i=0;i<n-1;i++)
   {
       mx=max(mx,a[i+1]-a[i]);
   }

   cout<<per-mx<<"\n";
   return 0;
}


Measured memory_bytes: 1792
input = gets.chomp
w,h,x,y = input.split.collect{ |item| item.to_i}

result = w.to_f*h.to_f/2.0

if ((x*2 == w) && (y*2 == h))
  puts "#{result} 1"
else
  puts "#{result} 0"
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i, e, n) for (int i = e; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const ll inf=1000000000007;

int main() {
  int H,W,h,w;
  cin >> H >> W >> h >> w;
  cout << H*W - h*W - H*w + h*w << endl;
  return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

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


Measured memory_bytes: 256
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    if a[0] >999:
        print("ABD")
    else:
        print("ABC")



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

int asc(const void *a, const void *b) {
	long *A = (long *)a;
	long *B = (long *)b;
	if (*A > *B) return 1;
	if (*A < *B) return -1;
	return 0;
}

int main()
{
	int n;
	cin >> n;
	long A[n];
	rep(i, n)
		cin >> A[i];
	qsort(A, sizeof(A) / sizeof(*A), sizeof(*A), asc);
	rep(i, n-1)
	{
		if (A[i] == A[i + 1])
		{
			cout << "NO\n"; return 0;
		}
	}
	cout << "YES\n";
	return (0);
}


Measured memory_bytes: 3324
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=3e5+5;
const int M=1e5+5;
int n,m,now;
pair<int,int> p[N];

struct Tree_Array
{
	int c[N];
	int lowbit(int x)
	{
		return x&(-x);
	}
	
	void update(int pos,int add)
	{
		while(pos<=m)
		{
			c[pos]+=add;
			pos+=lowbit(pos);
		}
	}
	
	int query(int pos)
	{
		int ret=0;
		while(pos)
		{
			ret+=c[pos];
			pos-=lowbit(pos);
		}
		return ret;
	}
};
Tree_Array SS;

int cmp(pair<int,int> x,pair<int,int> y)
{
	return x.second-x.first<y.second-y.first;
}
void init()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%d%d",&p[i].first,&p[i].second);
	sort(p+1,p+n+1,cmp);
}

void work()
{
	int i,j,ans;
	for(i=1;i<=m;++i)
	{
		ans=0;
		for(now;now<n&&p[now+1].second-p[now+1].first+1<=i;++now)
			SS.update(p[now+1].first,1),SS.update(p[now+1].second+1,-1);
		for(j=i;j<=m;j+=i) ans+=SS.query(j);
		printf("%d\n",ans+n-now);
	}
}

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

Measured memory_bytes: 3712
import java.util.*;

public class Main {
  public static void main(String[] args) {
    String S;
    try(Scanner sc = new Scanner(System.in)) {
      S = sc.next();
    }
    System.out.println(solve(S));
  }
  
  private static int solve(String s) {
    String pre = "";
    List<String> tokenList = new LinkedList<>();
    int n = s.length();
    StringBuilder rest = new StringBuilder();
    for(int i = 0; i < n; i++) {
      String cand = s.substring(i, i+1);
      rest.append(cand);
      String strRest = rest.toString();
      if ( strRest.equals(pre) == false ) {
        tokenList.add(strRest);
        rest.delete(0, rest.length());
        pre = strRest;
      }
    }
    return tokenList.size();
  }
}

Measured memory_bytes: 49908
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;

void mainmain(){
    vint v(4);
    rep(i, 3) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        v[a]++;
        v[b]++;
    }
    int odd = 0;
    rep(i, 4) {
        odd += v[i] % 2;
    }
    if (odd == 0 || odd == 2) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}



}

int main() try{
    mainmain();
}
catch(...){
}

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

int main() {
  int n, k;
  cin >> n >> k;
  
  bool okashi[n];
  rep(i, n) okashi[i] = false;
  
  rep(i, k){
    int d;
    cin >> d;
    rep(j, d){
      int a;
      cin >> a;
      okashi[a-1] = true;
    }
  }

  int res = 0;
  rep(i, n) if(!okashi[i]) ++res;
  
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3624
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll curT = 0;
    ll curX = 0;
    ll curY = 0;

    ll n;
    cin >> n;
    ll nextT,nextX,nextY;
    bool possible = true;
    rp(i,n){
      cin >> nextT >> nextX >> nextY;
      if(abs(curX - nextX) + abs(curY - nextY) > nextT - curT) possible = false;
      if(abs(curT + curX+curY + nextT + nextX + nextY)%2 == 1 ) possible = false;
      curX = nextX;
      curY = nextY;
      curT = nextT;
    }
    if(possible)
      cout << "Yes" <<endl;
    else
      cout << "No" << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define UMap        std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    llong power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    llong power ( llong x, llong n ) { return power( x, n, 1000000007 ); }
    llong gcd   ( llong x, llong y ) { return x % y ? gcd( y, x % y ) : y; }
    llong lcm   ( llong x, llong y ) { return ( x / gcd(x, y) * y ); }
    llong abs   ( llong n )          { return ( n < 0 ) ? -n : n; }
    template<class A, class B>inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B>inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    Vi vi;
    PQueue<Pii> sa;
    Vi placed;

    signed call_of_Cthulhu( signed datum ) {

        int n, m;
        read n >> m;
        if ( m <= n ) {
            echo 0 fin;
            return 0;
        }
        for ( int i = 0; i < m; i++ ) {
             int a;
             read a;
             vi.bash ( a );
        }
        bozo_sort(alles(vi));
        for ( int i = 0; i < m-1; i++ ) {
            sa.push( Pii ( std::abs(vi[i+1] - vi[i]), -i ) );
        }
        for ( int i = 0; i < n-1; i++ ) {
            sa.pop();
        }
        int ans = 0;
        while ( !sa.empty() ) {
            ans += sa.top().first;
            sa.pop();
        }

        echo ans fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 2228
mod=998244353
mask=2**32
ide_ele=0
lazy_ele=mask
def segfunc(a,b):
  a1,a2=divmod(a,mask)
  b1,b2=divmod(b,mask)
  c1=(a1+b1)%mod
  c2=(a2+b2)
  return (c1*mask)+c2
def op(a,x):
  a1,a2=divmod(a,mask)
  x1,x2=divmod(x,mask)
  c1=(a1*x1+a2*x2)%mod
  c2=a2
  return (c1*mask)+c2
def merge(x,y):
  x1,x2=divmod(x,mask)
  y1,y2=divmod(y,mask)
  z1=(x1*y1)%mod
  z2=(x2*y1+y2)%mod
  return (z1*mask)+z2
class lazysegmenttree():
  def __init__(self,init_val,func=segfunc,ie=ide_ele,le=lazy_ele,op=op,merge=merge):
    n=len(init_val)
    self.func=func
    self.op=op
    self.merge=merge
    self.ie=ie
    self.le=le
    self.h=(n-1).bit_length()
    self.num=1<<self.h
    self.tree=[ie]*self.num*2
    self.lazy=[le]*self.num*2
    for i in range(n):
      self.tree[i+self.num]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=func(self.tree[2*i],self.tree[2*i+1])
  def reflect(self,k):
    if self.lazy[k]==self.le:return self.tree[k]
    return self.op(self.tree[k],self.lazy[k])
  def propagate(self,k):
    if self.lazy[k]==self.le:return
    self.lazy[2*k]=self.merge(self.lazy[2*k],self.lazy[k])
    self.lazy[2*k+1]=self.merge(self.lazy[2*k+1],self.lazy[k])
    self.tree[k]=self.reflect(k)
    self.lazy[k]=self.le
  def thrust(self, k):
    for i in range(1,self.h+1)[::-1]:
      self.propagate(k>>i)
  def recalc(self,k):
    while k:
      k>>=1
      self.tree[k]=self.func(self.reflect(2*k),self.reflect(2*k+1))
  def update(self,left_0,right_0,value):
    l=left_0+self.num
    r=right_0+self.num+1
    vl=l
    vr=r
    x=value
    self.thrust(l)
    self.thrust(r-1)
    while r-l>0:
      if l&1:
        self.lazy[l]=self.merge(self.lazy[l],x)
        l+=1
      if r&1:
        r-=1
        self.lazy[r]=self.merge(self.lazy[r],x)
      l>>=1
      r>>=1
    self.recalc(vl)
    self.recalc(vr-1)
  def query(self,left_0,right_0):
    l=left_0+self.num
    r=right_0+self.num+1
    self.thrust(l)
    self.thrust(r-1)
    vl=vr=self.ie
    while r-l>0:
      if l&1:
        vl=self.func(vl,self.reflect(l))
        l+=1
      if r&1:
        r-=1
        vr=self.func(self.reflect(r),vr)
      l>>=1
      r>>=1
    return self.func(vl,vr)//mask
n,q=map(int,input().split())
a=[(i*mask)+1 for i in map(int,input().split())]
st=lazysegmenttree(a)
ans=[]
for _ in range(q):
  q,*p=map(int,input().split())
  if q:
    l,r=p
    ans+=[st.query(l,r-1)]
  else:
    l,r,b,c=p
    st.update(l,r-1,(b*mask)+c)
print(*ans,sep='\n')

Measured memory_bytes: 173132
#include <iostream>
using namespace std;
int main(){

  int h,n,i;
int A[100000];
cin >> h >> n;

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

for (i=0;i<n;i++){
h -= A[i];
}
if (h <= 0){
  cout <<"Yes";
  }
else{
  cout << "No";
}


return 0;
}

Measured memory_bytes: 640
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <complex>
typedef long long int LL;
using namespace std;

// 插入此處

int main() {
    int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    scanf("%d", &k);
    printf("%d\n", a[k-1]);
}


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

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        long[] a = new long[n];
        long total = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            total += a[i];
        }
        long res = 0;
        for (int i = 1; i < n; i += 2) {
            res += a[i];
        }
        long[] x = new long[n];
        x[0] = total - 2 * res;
        for (int i = 1; i < n; i++) {
            x[i] = 2 * a[i - 1] - x[i - 1];
        }
        for (int i = 0; i < n - 1; i++) {
            System.out.printf("%d ", x[i]);
        }
        System.out.println(x[n - 1]);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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


Measured memory_bytes: 67000
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int d = sc.nextInt();
		
		int count = 0;
		for (int i = 1; i <= m; i++) {
			for (int i1 = 20; i1 <= d; i1++) {
				int ten = i1 / 10;
				int one = i1 - ten * 10;
				
				if (ten <= 1 || one <= 1) {
					continue;
					
				} else if (i == ten * one) {
					count++;
//					System.out.println(i);
//					System.out.println(li);
				
				} else {
					continue;
				}
			}
		}
		System.out.println(count);
		
		sc.close();
	}
}

Measured memory_bytes: 25044
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long A = long.Parse(str[0]);
		long B = long.Parse(str[1]);
		long C = long.Parse(str[2]);
		string ans = "No"; 
		if(A==B && B==C){
			ans = "Yes";
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 11092
#include <stdio.h>

int main()
{
	int a1,a2,a3;
	scanf( "%u", &a1 );
	scanf( "%u", &a2 );
	scanf( "%u", &a3 );
	if ( (a1+a2+a3) >= 22 )
		printf("bust");
	else
		printf("win");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
//#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 200005, mod = 998244353;
int dp[MX], n, x[MX], d[MX];
vi c;
map<int, int> mp;
set<ii> st;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	forn (i, n) {
		cin >> x[i] >> d[i];
		mp[x[i]] = d[i];
		c.pb(x[i]);
	}

	sort(all(c));

	dp[n] = 1;

	for (int i = n - 1; i >= 0; i--) {
		int r = c[i] + mp[c[i]];

		auto it = st.lower_bound({r, -1});

		if (it == st.begin()) {
			dp[i] = 2 * dp[i + 1];
			st.emplace(c[i], i);
		} else {
			it--;
			dp[i] = dp[i + 1] + dp[it->se + 1];

			while (st.size() && st.begin()->se < it->se)
				st.erase(st.begin());

			st.emplace(c[i], it->se);
		}

		dp[i] %= mod;
	}

	cout << dp[0] << endl;

	return 0;
}


Measured memory_bytes: 25052
n = gets.chomp.to_i

points = []
while line = gets
  x,y = line.strip.split(" ").map(&:to_i)
  points << [x,y]
end

distanse_cathe = {}
distanses = []

points.permutation(n).each do |visittiong_order|
  total_distanse = 0
  visittiong_order.each_with_index do |point,n|
    if n == 0 
      next
    end
    x_div = point[0]-visittiong_order[n-1][0]
    y_div = point[1]-visittiong_order[n-1][1]
    total_distanse += Math.sqrt(x_div * x_div + y_div * y_div)
  end
  distanses << total_distanse
end

puts distanses.inject(&:+) / distanses.length

Measured memory_bytes: 2300
#include <iostream>

using namespace std;

int main(){

    int n;
    cin >> n;
    if(n < 4)
        cout << "No";
    else{
        if((n%4 == 0) || (n%7 == 0))
            cout << "Yes";
        else{
            int c = 0;
            for(int i=4;i<n;i+=4){
                if(((n-i)%7) == 0){
                    cout << "Yes";
                    c = 1;
                    break;
                }
            }
            if(c == 0)
                cout << "No";

        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long c = sc.nextLong();
		if( a==b && b==c){
			if( a%2 == 0 ){
				System.out.println(-1);
			}else{
				System.out.println(0);
			}
			return;
		}
		
		long ans = 0;
		while(a%2==0 && b%2==0 && c%2==0){
			long x = b/2 + c/2;
			long y = c/2 + a/2;
			long z = a/2 + b/2;
			a=x;
			b=y;
			c=z;
			ans++;
		}
		
		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 23764
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
// #include<C:\Users\J\Desktop\AC\athead.h>
#define showa(v) for(int iii = 0; iii < v.size(); iii++){ cout << v[iii] << " ";} cout << endl;
#define show(iiii) cout << iiii << endl; 
#define shows(iiiii) cout << iiiii << " ";
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include<tuple>
#include <utility>
#include <map>
#define waru 1000000000+7

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<int> b(n);
    rep(i,n+1){
        cin >> a[i];
    }
        rep(i,n){
        cin >> b[i];
    }
    unsigned long long int res = 0;

    rep(i,n){
        if(a[i] >= b[i]){
            // a[i] -= b[i];
            res += b[i];
            // b[i] = 0;

        }
        else{
            res += a[i];
            int nextb = b[i] - a[i];
            if( nextb > a[i+1]){
                res += a[i+1];
                a[i+1] = 0;
            }
            else{
                res += nextb;
                a[i+1] -= nextb;
            }
        }
    }
    cout << res;



}

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

int n;
int t[10001],s[10001];

int main(void){
	while(cin>>n,n){
		for(int i=0;i<n;i++) cin>>t[i];
		for(int i=0;i<n;i++) cin>>s[i];
		sort(s,s+n);
		reverse(s,s+n);

		bool flg = true;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(t[j] > 0){
					t[j]--;
					s[i]--;
				}
			}

			if(s[i] != 0){
				flg = false;
				break;
			}
		}

		cout<<(flg ? "Yes" : "No")<<endl;
	}

	return 0;
}

Measured memory_bytes: 932
from functools import reduce

def main():
    # 一文字のみを読み込み
    # s = input().rstrip().split(' ')
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 位置文字ずつ標準入力を配列として読み込み
    # s = list(input().rstrip())
    N, A = [int(_) for _ in input().split()]
    X = [int(_) for _ in input().split()]

    # dp[n][k][s] : n枚目までからk枚選んで合計をsにする場合の数
    dp = [[[0 for _ in range(2501)] for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    
    for n in range(N+1):
        for k in range(n+1):
            for s in range(50*k+1):
                if(n>=1 and s<X[n-1]):
                    dp[n][k][s] = dp[n-1][k][s]
                if(n>=1 and s>=X[n-1]):
                    dp[n][k][s] = dp[n-1][k][s] + dp[n-1][k-1][s-X[n-1]]

    Ans = 0
    for i in range(1,N+1):
        Ans += dp[N][i][i*A]
 
    print(Ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 66008
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twol pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define mk make_pair
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
inline int in(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
int n,x;
vi v,a;
int main(){FAST;xRand;
cin>>n;v.pb(69);
for(int i=1;i<=n;i++)
	cin>>x,v.pb(x);
for(int i=n;i>0;i--){
	bool ok=0;
	for(int j=i;j>=1;j--){
//		cout<<v[j]<<" "<<j<<endl;
		if(v[j]==j){
			v.erase(v.begin()+j);
//			cout<<"VSAX";
			ok=1;
			a.pb(j);
			break;
		}
	}
	if(ok==0){
		cout<<-1<<endl;
		return 0;
	}
}

reverse(ALL(a));
for(int i=0;i<sz(a);i++){
	cout<<a[i]<<endl;
}
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> prl;
typedef vector<ll> vcl;
typedef map<ll,ll> mapl;
typedef unordered_map<ll,ll> umap;
#define pb push_back
#define all(v) v.begin(), v.end()
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repi(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;

int main() {
    // your code goes here
    string s;
    cin >> s;
    if(s=="RRR") cout << 3 << endl;
    else if(s=="SSS") cout << 0 << endl;
    else if(s=="RRS") cout << 2 << endl;
    else if(s=="SRR") cout << 2 << endl;
    else cout << 1 << endl;
    return 0;
}

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

using namespace std;

int main() {
	
	string s, t;
	cin >> s >> t;

	for (int i = s.size() - t.size(); i >= 0; i--) {
		for (int j = 0; j < t.size(); j++) {
			if (s[i+j]!='?' && s[i + j] != t[j]) { break; }
			if (j == t.size() - 1) {
				for (int k = 0; k < s.size(); k++) {
					if (k >= i && k < i + t.size()) { cout << t[k - i]; }
					else if (s[k] == '?') { cout << 'a'; }
					else { cout << s[k]; }
				}
				return 0;
			}
		}
	}
	cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
	int s;
	double w, h;
	char a;
	while (cin >> s >> a >> w >> a >> h) {
		if (w / h / h >= 25.0) {
			cout << s << endl;
		}
	}
}

Measured memory_bytes: 3148
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

int main() {
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    
    cout << (H-h) * (W-w) << endl;

    return 0;
}


Measured memory_bytes: 256