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

using namespace std;

constexpr int MAXN = 1000;

int mat[MAXN + 2][MAXN + 2], idx[MAXN + 2], mmx[MAXN + 2];

int main() {
	int N; cin >> N;
	for(int i = 1; i <= N; i++)
		for(int j = 0; j < N - 1; j++)
			cin >> mat[i][j];
	queue<int> q;
	for(int i = 1; i <= N; i++)
		q.push(i);
	q.push(-1);
	int ans = 1, rem = N;
	while(q.size() > 1) {
		int x = q.front();
		q.pop();
		if(x == -1) {
			ans++;
			q.push(x);
			continue;
		}
		if(mmx[x] >= ans)
			continue;
		int y = mat[x][idx[x]];
		if(mat[y][idx[y]] == x && mmx[y] < ans) {
			if(++idx[x] != N - 1)
				q.push(x);
			else
				--rem;
			if(++idx[y] != N - 1)
				q.push(y);
			else
				--rem;
			mmx[x] = ans;
			mmx[y] = ans;
		}
	}
	if(rem)
		ans = -1;
	cout << ans << '\n';
}


Measured memory_bytes: 4224
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>
#include <unordered_map>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)(n);++i)
#define rep1(i, n) for (int i=1;i<=(int)(n);++i)
#define range(i, l, r) for (int i=l;i<(int)(r);++i)
#define rrange(i, l, r) for (int i=r-1;i>=(int)(l);--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

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

template<typename T>bool chmin(T&a,T b){return a>b?(a=b,true):false;}
template<typename T>bool chmax(T&a,T b){return a<b?(a=b,true):false;}
//int read(){int a;scanf("%lld",&a);return a;}

constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}

const int inf = TEN(18)*3 + 10;
const int mod = TEN(9) + 7;

int N, K;

signed main()
{
	cin >> N >> K;
	vector<double> a(N + 1), rui(N + 1);
	rep(i, N) {
		int p; cin >> p;
		a[i + 1] = (p + 1) / 2.0;
	}

	rep(i, N) {
		rui[i + 1] += rui[i] + a[i + 1];
	}

	double ans = 0;

	rep1(i, N) {
		if (i + K - 1 <= N) chmax(ans, rui[i + K - 1] - rui[i - 1]);
	}

	printf("%.10f\n", ans);
}


Measured memory_bytes: 3328
#pragma region noncode
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#pragma endregion

int main() {
    ll a, b, n;
    cin >> a >> b >> n;
    ll x;
    if(n < b - 1)
        x = n;
    else
        x = b - 1;
    cout << a * (x % b) / b << endl;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
const int MM = 305;

int n, m, k, b[MM][MM], t;
char a[MM][MM];

int main(){
    
    scanf("%d %d %d", &n, &m, &k);
    
    for(int i = 0; i < n; i++)
        scanf("%s", a[i]);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == '#'){
                b[i][j] = ++t;
                for(int k = j-1; k >= 0 && !b[i][k] && a[i][k] == '.'; k--)
                    b[i][j] = t;
                for(int k = j+1; k < m && !b[i][k] && a[i][k] == '.'; k++)
                    b[i][j] = t;
            }
        }
    }
    
    //if empty, nothing in row, do pre
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!b[i][j])
                b[i][j] = b[i-1][j];
        }
    }
    for(int i = n-2; i >= 0; i--){
        for(int j = 0; j < m; j++){
            if(!b[i][j])
                b[i][j] = b[i+1][j];
        }
    }
    //c
    for(int j = 1; j < m; j++){
        for(int i = 0; i < n; i++){
            if(!b[i][j])
                b[i][j] = b[i][j-1];
        }
    }
    for(int j = m-2; j >= 0; j--){
        for(int i = 0; i < n; i++){
            if(!b[i][j])
                b[i][j] = b[i][j+1];
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            printf("%d ", b[i][j]);
        }
        pc(10);
    }
    
    return 0;
}

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

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()

using LL   =  long long;
using pii  =  pair <int, int>;
using vii  =  vector <pii>;

const int INF = INT_MAX;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

int main()
{
    //ios::sync_with_stdio(false); cin.tie(nullptr);
    
    string s;
    cin>>s;
    s[3] = '8';
    cout<<s<<"\n";

    return 0;
}

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

int main(int argc, char const *argv[]) {
    using namespace std;
    string s;

    cin >> s;
    int size = s.length();
    int c = 0;

    for (int i = 0; i < size / 2; i++) {

        if (s[i] != s[size - i - 1]) {
            c++;
        }
    }
    cout << c << endl;

    return 0;
}


Measured memory_bytes: 256
def p_is_smaller(p):
    total = 0
    number_of_track = 1
    for w in W:
        total += w
        if total > p:
            number_of_track += 1
            if number_of_track > k:
                return 1
            total = w
    return 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    W = [int(input()) for _ in range(n)]
    left, right = max(W), sum(W)
    while right > left:
        mid = (left + right) // 2
        if p_is_smaller(mid):
            left = mid + 1
        else:
            right = mid
    print(right)


Measured memory_bytes: 9560
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
template<typename T = int, T mod = 1'000'000'007, typename U = long long>
struct umod{
    T val;
    umod(): val(0){}
    umod(U x){ x %= mod; if(x < 0) x += mod; val = x;}
    umod& operator += (umod oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
    umod& operator -= (umod oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
    umod& operator *= (umod oth){ val = ((U)val) * oth.val % mod; return *this; }
    umod& operator /= (umod oth){ return *this *= oth.inverse(); }
    umod& operator ^= (U oth){ return *this = pwr(*this, oth); }
    umod operator + (umod oth) const { return umod(*this) += oth; }
    umod operator - (umod oth) const { return umod(*this) -= oth; }
    umod operator * (umod oth) const { return umod(*this) *= oth; }
    umod operator / (umod oth) const { return umod(*this) /= oth; }
    umod operator ^ (long long oth) const { return umod(*this) ^= oth; }
    bool operator < (umod oth) const { return val < oth.val; }
    bool operator > (umod oth) const { return val > oth.val; }
    bool operator <= (umod oth) const { return val <= oth.val; }
    bool operator >= (umod oth) const { return val >= oth.val; }
    bool operator == (umod oth) const { return val == oth.val; }
    bool operator != (umod oth) const { return val != oth.val; }
    umod pwr(umod a, U b) const { umod r = 1; for(; b; a *= a, b >>= 1) if(b&1) r *= a; return r; }
    umod inverse() const {
        U a = val, b = mod, u = 1, v = 0;
        while(b){
            U t = a/b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if(u < 0)
            u += mod;
        return u;
    }
};
using U = umod<>;
template<typename U>
struct NCR {
    vector<U> fact, ifact;
    NCR(int size){
        fact.resize(size + 1); ifact.resize(size + 1);
        fact[0] = 1;
        for(int i = 1; i <= size; i++) fact[i] = fact[i - 1] * i;
        ifact[size] = fact[size].inverse();
        for(int i = size - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
    }
    U ncr(int n, int r){
        if(n < r) return 0;
        return fact[n] * ifact[r] * ifact[n - r];
    }
};
using N = NCR<U>;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k; cin >> n >> k;
	N kit(2 * n);
	// k = min(k, n);
	U ans = 0;
	for(int i = 0; i <= n; i++){
		if(i <= k){
			int has = n - i;
			ans += kit.ncr(n, i) * kit.ncr(has + i - 1, i);
		}
	}
	cout << ans.val << '\n';
	return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  vector<int> C(N - 1);
  for(int i = 0;i < N;i++){
    cin >> A.at(i);
    A.at(i) -= 1;
  }
  for(int i = 0;i < N;i++){
    cin >> B.at(i);
  }for(int i = 0;i < N - 1;i++){
    cin >> C.at(i);
  }
  int ans = 0;
  int x = 100000;
  for(int i = 0;i < N;i++){
    int now = A.at(i);
    ans += B.at(now);
    if(x == now - 1){
      ans += C.at(x);
    }
    x = now;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3616
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, A, B, C;
int ans = INF;

void calc(vector<int> l, vector<int> v) {
		int a = 0, b = 0, c = 0, t = 0, cnt = 0;
		for (int i = 0; i < N; i++ ) {
				switch (v[i]) {
						case 0: 
									if (a) cnt++;
									a += l[i];
									break;
						case 1: 
									if (b) cnt++;
									b += l[i];
									break;
						case 2: 
									if (c) cnt++;
									c += l[i];
									break;
						case 3: 
									break;
						default: 
									break;
				}
		}

		if (min( {a, b, c} ) ) t = abs(A - a) + abs(B - b) + abs(C- c) + 10 * cnt;
		else t = INF;

		if ( ans > t ) ans = t;
}

void dfs(int depth, vector<int> l, vector<int> v) {
		if ( depth == N ) calc(l, v);
		else {
				for ( int i = 0; i < 4; i++ ) {
						v[depth] = i;
						dfs(depth + 1, l, v);
				}
		}
}

int main() {
		cin >> N >> A >> B >> C;
		vector<int> l(N, 0);
		for ( int i = 0; i < N; i++ ) {
				cin >> l[i];
		}

		vector<int> v(N, 0);
		dfs(0, l, v);
		cout << ans << endl;

		return 0;
}


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

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

	int n;
	cin>>n;
	vector<int> start;
	for(int i=1; i<=n; ++i){
		start.push_back(i);
	}
	vector<vector<int>> seq;
	do{
		seq.push_back(start);
	}while( next_permutation(start.begin(),start.end()) );

	vector<int> first;
	vector<int> second;
	for(int i=0; i<n; ++i){
		int x; cin>>x; first.push_back(x);
	}
	for(int i=0; i<n; ++i){
		int x; cin>>x; second.push_back(x);
	}
	int a =0, b=0;
	for(int i=0; i<seq.size(); ++i){
		bool ok = true;
		for(int j=0; j<n; ++j){
			if( seq[i][j] != first[j] ){
				ok = false;
				break;
			}
		}
		if(ok){ a = i; break; }
	}
	for(int i=0; i<seq.size(); ++i){
		bool ok = true;
		for(int j=0; j<n; ++j){
			if( seq[i][j] != second[j] ){
				ok = false;
				break;
			}
		}
		if(ok){ b = i; break; }
	}
	cout<<abs(a-b)<<'\n';

	return 0;
}


Measured memory_bytes: 3384
/*
ID: zhaowei10
TASK:
LANG: C++14
*/
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 0
#endif

#define eb emplace_back

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vc = vector<char>;
using vb = vector<bool>;
using vll = vector<ll>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(9);

#ifdef LOCAL
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#else
#endif

  ll a, b;
  int c;
  char d;
  cin >> a >> b >> d >> c;
  b = b * 100 + c;
  cout << (a * b) / 100;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;

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

string s;
cin >> s;
int n = SZ(s);

s = '0' + s;
bool ok = true;
for(int l = 0, r = n; l <= r; l++, r--) {
    if(s[l] != s[r]) {
        ok = false;
        break;
    }
}
if(!ok || s[1] != '1') {
    cout << -1 << endl;
    return 0;
}

vi vec = {0};
for(int l = 0, r = n; l <= r; l++, r--) {
    if(s[l] == '1') vec.push_back(l);
}
vec.push_back(n);
rep(i,SZ(vec)) {
    if(vec[i] == n) continue;
    for(int u = vec[i]+1; u <= vec[i+1]; u++) {
        if(u == n) continue;
        cout << vec[i]+1 << ' ' << u+1 << endl;
    }
}

return 0;
}

Measured memory_bytes: 1900
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	plus := make([]int, 0)
	minusTotal := 0
	count := 0
	aa := make([]int, n)
	bb := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&aa[i])
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&bb[i])
	}

	for i := 0; i < n; i++ {
		a, b := aa[i], bb[i]
		d := a - b
		if d > 0 {
			plus = append(plus, d)
		} else {
			minusTotal += d
			count++
		}
	}

	if minusTotal >= 0 {
		fmt.Println(0)
		return
	}

	sort.Ints(plus)

	for i := len(plus) - 1; i >= 0; i-- {
		count++
		minusTotal += plus[i]
		if minusTotal >= 0 {
			fmt.Println(count)
			return
		}
	}

	fmt.Println(-1)
}


Measured memory_bytes: 5760
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

V = sum(v)

dp = [ [INF for _ in range(V+1)] for _ in range(N+1) ]

dp[0][0] = 0

for i in range(N):
    for j in range(V+1):
        if j < v[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])

#print(dp[N])

ans = 0
for v in range(V+1):
    if dp[N][v] <= W:
        ans = v

print(ans)

Measured memory_bytes: 314804
A1,A2,A3=map(int,input().split())
A4,A5,A6=map(int,input().split())
A7,A8,A9=map(int,input().split())

N=int(input())
B=[]
for i in range(N):
    B.append(int(input()))
flag=0

if A1 in B and A2 in B and A3 in B:
    flag=1
if A4 in B and A5 in B and A6 in B:
    flag=1
if A7 in B and A8 in B and A9 in B:
    flag=1

if A1 in B and A4 in B and A7 in B:
    flag=1
if A2 in B and A5 in B and A8 in B:
    flag=1
if A3 in B and A6 in B and A9 in B:
    flag=1

if A1 in B and A5 in B and A9 in B:
    flag=1
if A3 in B and A5 in B and A7 in B:
    flag=1

print('Yes' if flag==1 else 'No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
ll r,D,x;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>r>>D>>x;
    rep(i,1,11){
        x=r*x-D;
        cout <<x<<"\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007
 

 string mcxi="mcxi";
 int dig[4]={1000,100,10,1};

string toMCXI(int n){
	string ret="";
	rep(i,4){
		if(n%10!=0) ret+=mcxi[mcxi.size()-1-i];
		if(n%10>1) ret+=(char)('0'+(n % 10));
		n/=10;
	}
	reverse(all(ret));
	return ret;
}

int fromMCXI(string s){
	int ret=0;
	rep(i,s.size()){
		int t=1;
		if(s[i]>='2'&&s[i]<='9') t+=s[i]-'1',i++;
		rep(j,4) {
			if(s[i]==mcxi[j]) {
				t*=dig[j];
				break;
			}
		}
		ret+=t;	
	}
	return ret;
}

int main(){
	int n;
	cin>>n;
	string s,t;
	rep(i,n){
		cin>>s>>t;
		cout<<toMCXI(fromMCXI(s)+fromMCXI(t))<<endl;
	}
	
}

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

int main(){
    int n;
    ll res = 1;
    cin >> n;
    ll a;
    bool f = false;
    ll j;
    
    for(int i = 0;i<n;i++){
        cin >> a;
        
        if(a > j){
            f = true;
        } else{
            res *= a;
        }
        if(a == 0){
            f = false;
            res = 0;
            break;
        }
        j = 1000000000000000000/res;
    }

    if(f){
        cout << -1 << endl;
    }else{
        cout << res << endl;
    }
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
  int n;
  cin>>n;
  map<string,int>m;
  rep(i,n){
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    m[s]++;
  }
  ll ans=0;
  for(auto& p:m){
    int q=p.second;
    ans+=(ll)q*(q-1)/2;
  }
  cout<<ans<<endl;
}

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

inline void gc(long* x){
    *x = 0;
    for(;;){
        int c=getchar_unlocked();
        if('0'<= c && c <='9'){
            *x = *x*10 + c-'0';
        }else{
            break;
        }
    }
}

int cmp(const long *a, const long *b){
    if(*a==*b){
        return 0;
    }else if(*a<*b){
        return 1;
    }else{
        return -1;
    }
}

int main(void){
    static long b[100000];
    long a, n, h, am=0;
    gc(&n);
    gc(&h);
    for(long i=0; i<n; i++){
        gc(&a);
        gc(b+i);
        am = a>am ? a : am;
    }
    qsort(b, n, sizeof(long), (int (*)(const void *, const void *))cmp);
    long m=0;
    while(b[m]>am && h>0){
        h-=b[m];
        m++;
    }
    if(h>0){
        m+=(h+am-1)/am;
    }
    printf("%ld", m);
    return 0;
}


Measured memory_bytes: 1788
#include <stdio.h>
int gcd(int p,int q){while(q){int t=p%q;p=q;q=t;}return p;}

int main(){
	int n;
	scanf("%d",&n);
	int ans=n;
	for(int i=2;i*i<=n;i++)if(n%i==0){
		ans-=ans/i;
		while(n%i==0)n/=i;
	}
	printf("%d\n",n==1?ans:ans-ans/n);
}


Measured memory_bytes: 2112
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
#endif

#ifdef _DEBUG
void init_global_C() {}
#else

#endif

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

    int N;  cin >> N;
    vi A(N); REP(i, N) cin >> A[i];
    vi B(N); REP(i, N) cin >> B[i];
    vi C(N); REP(i, N) cin >> C[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    ll ans = 0;
    REP(i, N) {
        ans += (lower_bound(A.begin(), A.end(), B[i]) - A.begin()) 
                * (C.end() - upper_bound(C.begin(), C.end(), B[i]));
    }    

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1408
#20
import sys
s = int(input())
a = []
i = 2

while i >0:
    if s %2 == 0:
        a.append(s)
        s = int(s/2)
    else:
        a.append(s)
        s = 3*s+1
    for j in a:
        if s == j:
            print(i)
            sys.exit()
    i+=1
        

Measured memory_bytes: 9060
#include<bits/stdc++.h>
using namespace std ;
int main(){
    string s ;
    int a , b , c ;
    a = b = c = 0 ;
    cin >> s ;
    int len = s.length() ;
    for( int i = 0 ; i < len ; i++ ){
        if ( s[i] == 'a' ) a++ ;
        if ( s[i] == 'b' ) b++ ;
        if ( s[i] == 'c' ) c++ ;
    }
    int maxx = max( max( a , b ) , c ) ;
    int minx = min( min( a , b ) , c ) ;
    if ( maxx - minx > 1 ) cout << "NO" << endl ;
    else cout << "YES" << endl ;
    return 0 ;
}

Measured memory_bytes: 512
N = int(input())
S = input()
 
eastNumber = S.count('E')
westNumber = 0
minimum = N
 
for i in range(N):
    if S[i] == 'E':
        eastNumber -= 1
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
    else:
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
        westNumber += 1
 
print(minimum)

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

const int inf = 1e9;
const ll linf = 1e18;

int top(int n)
{
    while (n >= 10) n /= 10;
    return n;
}

int last(int n)
{
    return n % 10;
}

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

    int n; cin >> n;

    ll a[10][10] = {0};
    for (int i = 1; i <= n; i++) a[top(i)][last(i)]++;

    ll ans = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            ans += a[i][j] * a[j][i];
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    ll H, W;
    cin >> H >> W;
    //Hが2で割り切れるかどうか　余りをたす
    if( H % 2 == 0){
        cout << W * H / 2 << endl;
    }else{
        if(H == 1 || W == 1){
            cout << 1 << endl;
        }else   cout << (W * (H - 1) / 2) + W / 2 + W % 2 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
#define LOCAL
using namespace std;
// using namespace atcoder;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
//#define int long long
using P = pair<int,int>;
//#########################################
int dp[13][5500];
const int INF = 1001001001;
void chmin(int &a,int b){
    if(a > b)a = b;
}
int main(){
    rep(i,13)rep(j,5500)dp[i][j] = INF;
    dp[0][0] = 0;
    int n,m;cin >> n >> m;
    vector<P> res(m);
    rep(i,m){
        cin >> res[i].second;
        int x;cin >> x;
        int tmp = 0;
        while(x--){
            int p;cin >> p;
            p--;
            tmp |= 1<<p;
        }
        res[i].first = tmp;
    }
    rep(i,n)rep(j,1<<n){
        chmin(dp[i+1][j],dp[i][j]);
        rep(k,m){
            chmin(dp[i+1][j|res[k].first],dp[i][j]+res[k].second);
        }
    }
    int ans = dp[n][(1<<n)-1];
    if(ans == INF)ans = -1;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3904
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
ans = 0
stack = []
stack.append([0,set()])
while stack:
  v,visited = stack.pop()
  if v in visited:
    continue
  visited2 = visited.copy()
  visited2.add(v)
  if len(visited2) == N:
    ans += 1
    continue
  for child in G[v]:
    stack.append([child,visited2])

print(ans)

Measured memory_bytes: 3064
#include <functional>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
typedef pair<int,int> P;

int a[401][401];
int d[401][401];
int h,w;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
#define inf 10000000

long long ans,c,nw,sx,sy;

void bfs(int sx,int sy){
    queue<pair<int, int>> q;
    d[sx][sy]=1;
    q.push({sx,sy});
    if(a[sx][sy]==0)nw++;
    while(!q.empty()){
        pair<int, int> p = q.front();
        int tx = p.first;
        int ty = p.second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int x=tx+dx[i];
            int y=ty+dy[i];
            if(x<0 || x>=h)continue;
            if(y<0 || y>=w)continue;
            if((a[tx][ty]!=a[x][y])&&d[x][y]==0){
                c++;
                if(a[x][y]==0)nw++;
                d[x][y]=1;
                q.push({x,y});
                
            }
        }
    }
}

int main(void){
    cin>>h>>w;
    string str;
    for(int i=0; i<h; i++){
        cin>>str;
        for(int j=0; j<w; j++){
            if(str[j]=='.')a[i][j]=0;
            else{a[i][j]=1;}
        }
    }
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            c=1; nw=0;
            if(d[i][j]==0){
                bfs(i,j);
                ans+=nw*(c-nw);
                //cout<<nw<<c<<endl;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const long long N = 1e6 + 1;
ll a[N], q[N], n, m, k, x, y, z, l, r, cnt, ans;
int main()
{
    ios_base::sync_with_stdio(0);
    string s;
    string t;
    cin >> s >> t;
    for ( int i=0; i<3; i++ ){
        if ( s[i] == t[i] )
            cnt ++;
    }
    cout << cnt;

}



Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static final int NA = Integer.MAX_VALUE;

    public static void main(String[] args) {
        try (CustomReader in = new CustomReader()) {
            new Main().execute(in);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void execute(CustomReader in) throws IOException {
        final String A = in.readLine();
        final String B = in.readLine();
        System.out.println(editDistance(A, B));
    }

    private int editDistance(String A, String B) {
        int[][] dp = new int[A.length() + 1][B.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], NA);
        }

        for (int i = 0; i <= A.length(); i++) {
            for (int j = 0; j <= B.length(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    if (A.charAt(i - 1) == B.charAt(j - 1)) {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j] + 1), dp[i][j - 1] + 1);
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1), dp[i][j - 1] + 1);
                    }
                }
            }
        }

        return dp[A.length()][B.length()];
    }


    static class CustomReader extends BufferedReader {

        //private static final int DEFAULT_BUF_SIZE = 2048;
        private static final int DEFAULT_BUF_SIZE = 4096;
        //private static final int DEFAULT_BUF_SIZE = 8192;
        //private static final int DEFAULT_BUF_SIZE = 16384;
        // private static final int DEFAULT_BUF_SIZE = 1048576;

        public CustomReader() throws IOException {
            super(new InputStreamReader(System.in), DEFAULT_BUF_SIZE);
        }


        public int readLineAsInt() throws IOException {
            return Integer.parseInt(this.readLine());
        }


        public int[] readLineAsIntArray() throws IOException {
            String[] strArray = this.readLine().split(" ");
            int[] intArray = new int[strArray.length];
            for (int i = 0, n = strArray.length; i < n; i++) {
                intArray[i] = Integer.parseInt(strArray[i]);
            }
            return intArray;
        }

        public int[][] readAsIntMatrix(int rows, int columns) throws IOException {
            int[][] matrix = new int[rows][columns];
            for (int i = 0; i < rows; i++) {
                String[] r = this.readLine().split(" ");
                for (int j = 0; j < columns; j++) {
                    matrix[i][j] = Integer.parseInt(r[j]);
                }
            }
            return matrix;
        }
    }
}


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

int main(){
  int n,k; cin >> n >> k;
  long h[n]; for(int i=0; i<n; i++){cin >> h[i];}
  
  sort(h, h+n); long min=-1;
  for(int i=0; i<n-k+1; i++){
    if(min==-1 || h[i+k-1]-h[i]<min){min = h[i+k-1]-h[i];}
  }
  
  cout << min;
  
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {

    int x;
    int y;
    int tmp;

    while(1) {
        scanf("%d %d", &x, &y);
        
        if(x == 0 && y == 0) {
            break;
        }

        if(x > y) {
            tmp = x;
            x = y;
            y = tmp;
        }
        
        printf("%d %d\n", x, y);
    }

    return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String [] Num =s.split("");
		int az = 0;
		int za = 0;
		int n = Num.length;
		if(Num.length % 2 == 0) {
			for(int i = 0; i < n; i += 2) {
				if(Num[i].equals("0")) {
					az ++;
				}
				if(Num[i+1].equals("1")) {
					az ++;
				}
				if(Num[i].equals("1")) {
					za ++;
				}
				if(Num[i+1].equals("0")) {
					za ++;
				}
			}
		}else {
			for(int i = 0; i < n-1; i += 2) {
					if(Num[i].equals("0")) {
						az ++;
					}
					if(Num[i+1].equals("1")) {
						az ++;
					}
					if(Num[i].equals("1")) {
						za ++;
					}
					if(Num[i+1].equals("0")) {
						za ++;
					}
				}
				if(Num[n-1].equals("0")) {
					az ++;
				}
				if(Num[n-1].equals("1")) {
					za ++;
				}
			}
		int ans = Math.min(az, za);
		System.out.println(ans);
		sc.close();
	}
	
}



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

using ll = long long;
using namespace std;

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    int cost[n + 1][n + 1];
    for (int i = 0; i <= n; i++)
        for (int k = 0; k <= n; k++)
            cost[i][k] = 0;
    for (int i = 1; i < x; i++) {
        for (int k = i + 1; k <= x; k++) {
            cost[i][k] = k - i;
            cost[k][i] = k - i;
        }
    }
    for (int i = y; i < n; i++) {
        for (int k = i + 1; k <= n; k++) {
            cost[i][k] = k - i;
            cost[k][i] = k - i;
        }
    }
    for (int i = x; i < y; i++) {
        for (int k = i + 1; k <= y; k++) {
            int c = min(k - i, 1 + y - k + i - x);
            cost[i][k] = c;
            cost[k][i] = c;
        }
    }
    for (int i = 1; i <= x; i++) {
        for (int k = x + 1; k <= y; k++) {
            cost[i][k] = cost[i][x] + cost[x][k];
            cost[k][i] = cost[i][x] + cost[x][k];
        }
    }
    for (int i = x; i < y; i++) {
        for (int k = y; k <= n; k++) {
            cost[i][k] = cost[i][y] + cost[y][k];
            cost[k][i] = cost[i][y] + cost[y][k];
        }
    }
    for (int i = 1; i <= x; i++) {
        for (int k = y; k <= n; k++) {
            cost[i][k] = cost[i][x] + cost[y][k] + 1;
            cost[k][i] = cost[i][x] + cost[y][k] + 1;
        }
    }
    map<int, int> ans;
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k <= n; k++) {
            int c = cost[i][k];
            ans[c]++;
        }
    }
    for (int i = 1; i <= n - 1; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int w, h; cin >> w >> h;
  int x, y; cin >> x >> y;
  cout << fixed << setprecision(15) << 0.5 * w * h << ' ';
  cout << (2 * x == w and 2 * y == h) << '\n';
}

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

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

	int N;
	scanf("%d", &N);

	vector<long long> A(N), B(N);

	scanf("%lld", &A[0]);
	B[0] = A[0];
	for (int i = 1; i < N; i++) {
		scanf("%lld", &A[i]);
		B[i] = B[i - 1] + A[i];
	}
	// printf("%lld\n", B[N - 1]);

	long long result = abs(B[N - 1] - B[0] * 2);
	for (int i = 1; i < N - 1; i++) {
		result = min(abs(B[N - 1] - B[i] * 2), result);
		// printf("%d %d\n", A[i], B[i]);
	}
	printf("%lld\n", result);

	return 0;
}

Measured memory_bytes: 3456
/// 25-01-2018
/// MD:NUR ALAM
/// Eastern University of Bangladesh

#include "bits/stdc++.h"

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = (a); i < (b); ++i)
#define fo(i, a, b) for (int i = (a); i <(b); ++i)
#define fors(i, s) for (int i = 0; s[i]; ++i)
#define rs(x) scanf("%s", (x))
#define mp make_pair
#define pb push_back
#define mso(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define len(X) strlen(x)

using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef long double lu;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpll;
typedef pair<int,int> Pll;
typedef map<string,int>msi;
typedef set<int>se;

template<class t> void _r(t &x) { cin >> x; }
void _r(int &x) { scanf("%d", &x); }
void _r(int64_t &x) { scanf("%lld", &x); }
void _r(double &x) { scanf("%lf", &x); }
void _r(char &x) { scanf(" %c", &x); }
void _r(char *x) { scanf("%s", x); }
void r() {}
template<class t, class... u> void r(t &head, u &... tail) { _r(head); r(tail...); }
template<class t> void _w(const t &x) { cout << x; }
void _w(const int &x) { printf("%d", x); }
void _w(const int64_t &x) { printf("%lld", x); }
void _w(const double &x) { printf("%.16f", x); }
void _w(const char &x) { putchar(x); }
void _w(const char *x) { printf("%s", x); }
template<class t,class u> void _w(const pair<t,u> &x) {_w(x.f); putchar(' '); _w(x.s);}
void w() {}
template<class t, class... u> void w(const t &head, const u &... tail) { _w(head); putchar(sizeof...(tail) ? ' ' : '\n'); w(tail...); }
template<class t, class... u> void debug(const t &head, const u &... tail) {
#ifdef HOME
#endif
}

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



int main(){

     string a;
     r(a);
     if(a[0]==a[1] && a[1]==a[2])w("Yes");
     else if(a[1]==a[2] && a[2]==a[3])w("Yes");
     else w("No");
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  char s[4];
  scanf("%s", s);
  
  int two;
  if(s[0] == s[1] && s[2] == s[3] && s[0] != s[2]){
    two = 1;
  }else if(s[0] == s[2] && s[1] == s[3] && s[0] != s[1]){
    two = 1;
  }else if(s[0] == s[3] && s[1] == s[2] && s[0] != s[1]){
    two = 1;
  }else{
    two = 0;
  }
  
  if(two){
    printf("Yes");
  }else{
    printf("No");
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

using namespace std;

int main() {
    using ll = long long;
    
    ll n, k;
    cin >> n >> k;
    
    ll ans = 0;
    
    for (int i = 1; i <= n; i++) {
        int d = k - i % k;
        
        if ((2 * d) % k == 0) {
            ll l = (1 + i + k - 1) / k;
            ll r = (n + i) / k;
            
            if (r - l >= 0) {
                ans += (r - l + 1) * (r - l + 1);   
            }
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> v(h);
  
  for (int i=0; i<h; i++){
      cin >> v[i];
  }
 
  set<int> sh, sw;
  for (int i=0; i<h; i++){
    for (int j=0; j<w; j++){
      if (v[i][j] == '#'){
        sh.insert(i);
      }
    }
  }
  
  
  for (int i=0; i<w; i++){
    for (int j=0; j<h; j++){
      if (v[j][i] == '#'){
        sw.insert(i);
      }
    }
  }
  
  
  for (int i=0; i<h; i++){
    if(sh.count(i) == 0){
      continue;
    }
    else {
    for (int j=0; j<w; j++){
      if (sw.count(j) != 0){
        cout << v[i][j];
      }  
    }
    cout << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
/*** akshaykumar99 ***/
 
#include<bits/stdc++.h> 
using namespace std;
 
const long long MOD = 998244353;
const long double PI = acos(-1);
const long long N = 4e5+1;
 
typedef long long ll;
typedef long double ld;

ll t[4*N], lazy[4*N];

void build(ll a[], ll v, ll tl, ll tr)
{
    if(tl == tr)
        t[v] = a[tl];
    else
    {
        ll tm = (tl + tr) >> 1;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
}
void push(ll v)
{
    t[v * 2] = (t[v*2] + lazy[v]) % MOD;
    lazy[v * 2] = (lazy[v * 2] +lazy[v])%MOD;
    t[v * 2 + 1] = (t[v * 2 + 1] + lazy[v])%MOD;
    lazy[v * 2 + 1] =( lazy[v * 2 + 1]+lazy[v]) % MOD;
    lazy[v] = 0;
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll val)
{
    if(l > r)
        return;
    if(l == tl && r == tr)
    {
        t[v] = (t[v] + val)% MOD;
        lazy[v] = (lazy[v] + val) % MOD;
    }
    else
    {
        push(v);
        ll tm=(tl+tr)>>1;
        update(v*2, tl, tm, l, min(r, tm), val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, val);
        t[v]=min(t[v*2], t[v*2+1]);
    }
}

ll query(ll v, ll tl, ll tr, ll l, ll r)
{
    if(l>r)
        return INT_MAX;
    if(l<=tl && tr<=r)
    {
        return t[v];
    }
    push(v);
    ll tm=(tl+tr)>>1;
    return min(query(v*2, tl, tm, l, min(r, tm)), 
            query(v*2+1, tm+1, tr, max(l, tm+1),r));
}
void test_case()
{
	ll n, k;
	cin >> n >> k;
	vector<pair<ll,ll>> v(k+1);
	for(int i = 1; i <= k; i++)
	{
		cin >> v[i].first >> v[i].second;
	}
	ll nn = 2 * n + 1;
	ll a[nn] = {0};
	build(a, 1, 0, nn-1);
	update(1, 0, nn-1, 1, 1, 1);
	for(int i = 1; i < n; i++)
	{
		ll z = query(1, 0, nn-1, i, i);
		// cout << z << " ";
		if(!z)
			continue;
		for(int j = 1; j <= k; j++)
		{
			// cout << v[j].first << ' ' << v[j].second << '\n';
			update(1, 0, nn-1, i + v[j].first, i+v[j].second, z);
		}
	}
	ll z = query(1, 0, nn-1, n, n);
	cout << z<< '\n';
	
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    ll tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}


Measured memory_bytes: 23060
#include<iostream>
using namespace std;
int main(){
  int n,d=100000;
  cin>>n;
  for(int i=0;i<n;i++){
    d*=1.05;
    if(d%1000!=0)d=(d/1000)*1000+1000;
  }
  cout <<d<<endl;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };


LL N;

LL ans = 0LL;


LL f(LL b, LL n) {
	if (n < b)return n;
	else return f(b, n / b) + n % b;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);


	cin >> N;
	LL s; cin >> s;

	ans = LINF;
	if (N == s)ans = N + 1;

	for (LL i = 2; i*i <= N; i++) {
		LL val = f(i, N);
		if (val == s)
			ans = min(ans, i);
	}

	for (LL i = 1; i*i < N; i++) {
		LL b = (N - s) / i + 1;
		if (b > 1) {
			if (f(b, N) == s) {
				ans = min(ans, b);
			}
		}
	}

	if (ans == LINF)ans = -1;
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fv               first
#define sv               second
#define ll               long long
#define pll              pair<ll,ll>
#define pii              pair<int,int>
#define READ(x)          freopen(x,"r",stdin)
#define WRITE(x)         freopen(x,"w",stdout)
#define isWorking()      cout<<"Wroking"<<endl
#define all(x)           (x).begin(),(x).end()
#define allr(x)          (x).rbegin(),(x).rend()
#define fill(x,y)        memset(x, y, sizeof(x))
#define PRINT(ok)        cout<<(ok? "YES":"NO")<<endl
#define DoublePrint(x,a) cout<<fixed<<setprecision(x)<<a<<endl
#define Fast_Input       ios_base :: sync_with_stdio(0),cin.tie(0);

const ll mod = 1e9+7, INF = 1e8, mx = 1e5+5, mn = 100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    while(testCase--){
        int n; cin >> n;
        vector <ll> v(n);
        for(int i=0; i<n; i++) cin >> v[i];
        sort(allr(v));
        ll ans = v[0];
        int lim = n/2;
        for(int i=1; i<lim; i++) ans+=(2*v[i]);
        if(n&1) ans+= v[n/2];
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4776
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;
const int mod = MOD7;

void ERROR(int num) { printf("ERROR%d!\n",num); }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};


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

    int A, B;
    cin >> A >> B;
    double maxn = 100 / 0.08 + 1;

    int ans = -1;
    for(int i = 1; i < maxn; i++){
      int a = i * 0.08;
      int b = i * 0.1;
      if(a>0 && b>0 && a==A && b==B){
        ans = i;
        break;
      }      
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import numpy as np
N, X, D = map(int, input().split())

if not D:
  if not X:
    print(1)
  else:
    print(N+1)

else:
  num_dict = dict()
  ans = 0
  for i in range(N+1):
    left_num = int(i*X/D) + int(i*(i-1)/2)
    right_num = int(i*X/D) + int(i*(2*N-1-i)/2)
    judge_num = i*X%D
    if not judge_num in num_dict:
      num_dict[judge_num] = [(left_num,right_num)]
    else:
      num_dict[judge_num].append((left_num,right_num))

  for j,k in num_dict.items():
    new_k = sorted(k)
    L = new_k[0][0]
    R = new_k[0][1]
    for l in new_k:
      if l[0] <= R <= l[1]:
        R = l[1]
      elif R < l[0] and R < l[1]:
        ans += R-L+1
        L, R = l[0], l[1]
    ans += R-L+1
    
  print(ans)

Measured memory_bytes: 89852
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <malloc.h>

int main(void)
{
	int N;
	int a = 0;
	int b = 0;
	int c = 0;
	int d = 0;
	char* S;


	scanf("%d", &N);

	S = (char *)calloc(N, sizeof(char));

	for (int i = 0; i < N; i++)
	{
		scanf("%s", &S[i]);
		if ((strcmp(S + i, "AC")) == 0)
		{
			a++;
		}
		else if ((strcmp(S + i, "WA")) == 0)
		{
			b++;
		}
		else if ((strcmp(S + i, "TLE")) == 0)
		{
			c++;
		}
		else if ((strcmp(S + i, "RE")) == 0)
		{
			d++;
		}
		else
		{
			;
		}
	}
	printf("AC x %d\n", a);
	printf("WA x %d\n", b);
	printf("TLE x %d\n", c);
	printf("RE x %d\n", d);

	return 0;
}


Measured memory_bytes: 2192
// みなさん私はカーティキー・シャルマです。LNMIITで勉強しています。私は2年目で、コロナパンデミックが発
// 生しています。世界は終わりそうだ。だから私はそれを最大限に生きたいと思っています。それはつまり、コー
// ドを最大限に意味しているのです。私の好きなアニメは「キメツノヤイバ」で、私の一番の男の子はゼニツで、
// 私の一番の女の子はネズコです。私の好きな呼吸スタイルは息吹です。私の最高の悪魔の血の芸術は、
// ククシボによって使用される月の息です。ムーザンは亡くなり、今ではタンジローがポップの新しい魔王です。
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define PI 3.14159265358979323
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
      FastIO
      string s;
      cin >> s;
      if (s == "ABC")
      	cout << "ARC";
      else{
      	cout << "ABC";
      }
      return 0;
}

Measured memory_bytes: 3612