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

const int N = 200005;
const int mod = 1e9 + 7;

typedef pair<int, int> ii;

int n, res = 1;
int prd[N], inv[N];
int deg[N];
int f[N], sz[N];
int nxt[N];
bool visit[N];
bool in[N];
vector<int> G[N], nG[N];
vector<int> vec;
vector<ii> edges;

int pw(int x, int y) {
	if (!y) return 1; 
	int ret = pw(x, y >> 1); ret = 1LL * ret * ret % mod;
	if (y & 1) ret = 1LL * ret * x % mod; return ret; 
}

int C(int n, int k) {
	if (n < k) return 0;
	return 1LL * prd[n] * inv[n - k] % mod * inv[k] % mod;
}

void preDfs(int u) {
	visit[u] = 1, vec.push_back(u);
	for (auto v : G[u]) if (!visit[v]) preDfs(v);
}

void dfs(int u) {
	sz[u] = 0;
	for (auto v : nG[u]) {
		dfs(v), sz[u] += sz[v];
	}
	int cur = sz[u];
	f[u] = 1;
	for (auto v : nG[u]) {
		f[u] = 1LL * f[u] * f[v] % mod * C(cur, sz[v]) % mod, cur -= sz[v];
	}
	sz[u]++;
}

int cal() {
	// reset
	nG[0].clear();
	for (auto i : vec) nG[i].clear(), deg[i] = 0;
	for (auto i : edges) nxt[i.first] = i.second;
	// creates edges
	for (auto i : vec) {
		for (auto j : G[i]) {
			if (j == nxt[i]) continue;
			if (j < nxt[i]) nG[i].push_back(j), deg[j]++;
			// j comes first
		}
	}
	for (auto i : vec) {
		// connects components
		if (!deg[i]) nG[0].push_back(i);
	}
	// dfs + dp
	dfs(0); return f[0];
}

int solve(int r) {
	vec.clear(), preDfs(r);
	// bfs find circle
	queue<int> qu;
	for (auto i : vec) {
		if (deg[i] == 1) qu.push(i);
	}
	edges.clear();
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			if (deg[v] > 1) {
				deg[v]--, edges.push_back(ii(u, v));
				if (deg[v] == 1) qu.push(v);
			}
		}
	}
	int res = 0;
	for (auto i : vec) {
		if (deg[i] != 2) continue;
		// creates circle
		vector<int> circle;
		int cur = i;
		while (!in[cur]) {
			in[cur] = 1, circle.push_back(cur);
			for (auto v : G[cur]) {
				if (!in[v] && deg[v] == 2) cur = v;
			}
		}
		// each circle has 2 ways
		for (int j = 0; j < 2; ++j) {
			vector<ii> buffer = edges;
			int sz = circle.size();
			for (int k = 0; k < sz; ++k) {
				edges.push_back(ii(circle[k], circle[(k + 1) % sz]));
			}
			res = (res + cal()) % mod;
			edges = buffer, reverse(circle.begin(), circle.end());
		}
		return res;
	}
}


int main() {
	ios::sync_with_stdio(false);
	// for calculating nCk
	prd[0] = inv[0] = 1;
	for (int i = 1; i < N; ++i) {
		prd[i] = 1LL * i * prd[i - 1] % mod;
		inv[i] = pw(prd[i], mod - 2);
	}
	// input
	cin >> n; n <<= 1;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		y += n >> 1, deg[x]++, deg[y]++;
		G[x].push_back(y), G[y].push_back(x); 
	}
	// 0 case
	for (int i = 1; i <= n; ++i) {
		if (!G[i].size()) {
			cout << 0; return 0;
		}
	}
	// solve each component
	int cur = n;
	for (int i = 1; i <= n; ++i) {
		if (visit[i]) continue;
		res = 1LL * res * solve(i) % mod * C(cur, vec.size()) % mod;
		cur -= vec.size();
	}
	// output
	cout << res;
}

Measured memory_bytes: 30972
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cmath>

#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 FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(a, n) sort(a, a+n)
#define VSORT(v) sort(v.begin(), v.end())

using namespace std;


int main()
{
    long n;
    long sum = 0;

    cin >> n;

    REP(i, n) {
        if(((i+1)%5!=0) && ((i+1)%3!=0)) {
            sum += long(i+1);
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

int cnt[101010];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N,M; cin>>N>>M;
  int ac=0,wa=0;
  rep(i,M){
    int P; string S; cin>>P>>S; P--;
    if(S=="AC"){
      if(cnt[P]!=-1) wa+=cnt[P];
      cnt[P]=-1;
    }else{
      if(cnt[P]!=-1) cnt[P]++;
    }
  }
  rep(i,N) ac+=(cnt[i]==-1);
  cout<<ac<<" "<<wa<<endl;
  return 0;
}

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

constexpr ll INF = 1LL << 60;
constexpr int MAX_N = 105;
constexpr int MAX_V = 100005;
ll value[MAX_N];
ll weight[MAX_N];
ll dp[MAX_N][MAX_V];

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

  int n, W;
  cin >> n >> W; 
  rep(i, n) cin >> weight[i+1] >> value[i+1];

  fill(&dp[0][0], &dp[MAX_N][0], INF);
  dp[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
      dp[i][sum_v] = dp[i-1][sum_v];
      if (sum_v >= value[i]) {
        dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v - value[i]] + weight[i]);
      }
    }
  }
  int ans = 0;
  for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
    if (dp[n][sum_v] <= W) ans = sum_v;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 82304
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	int d, x; cin >> d >> x;
	int a, ans = x;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		ans += ((d - 1) / a + 1);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int arr[maxn];
int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n+1;i++)
		cin >> arr[i];
	int ans = 0;
	for(int i=2,val;i<=n+1;i++) {
		cin >> val;
		int add = min(arr[i-1],val);
		ans += add;
		val -= add;
		add = min(arr[i],val);
		ans += add;
		arr[i] -= add;
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 1024
a = int(input())
b = int(input())
c = int(input())
x = int(input())
l = [500, 100, 50]
ans = 0
for i in range(a+1):
    for j in range(b+1):
        s = 500*i + 100*j
        if (x-s)%50==0 and (x-s) >= 0 and (x-s)<= 50*c:
            ans  += 1
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	int n, s= 0;
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		int x;
		cin >> x;
		s += x - 1;
	}
	cout << s;





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;


public class Main {
    private static int gcd(int a, int b)
    {
        while (b > 0)
        {
            int temp = b;
            b = a % b; // % is remainder
            a = temp;
        }
        return a;
    }

    private static int lcm(int a, int b)
    {
        return a * (b / gcd(a, b));
    }


    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader in
                = new BufferedReader(new InputStreamReader(System.in));

        String line;
        int rows, cols;
        int two, three, a, b;
        double rate;
        boolean checker;
        double count;
        while ((line = in.readLine()) != null && !(line.equals(""))) {
                String [] temp = line.split(" ");
                a = Integer.parseInt(temp[0]);
                b = Integer.parseInt(temp[1]);

                System.out.println(gcd(a, b) + " " +lcm(a, b));

        }


    }
}

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

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> x, y;
    y.push_back(0);
    for (int i=0;i<n;++i) {
        ll a;
        cin >> a;
        if (a < 0) x.push_back(-a);
        else y.push_back(a);
    }

    x.push_back(0);//番兵(なんでこれが必要なのかは不明)
    sort(x.begin(), x.end());
    int ms = min(k, (ll)y.size()-1);//kと正の数の個数のmin
    ll ans = 1e16;
    for (int i = ms; i >= 0; i--) {
        if (k - i >= x.size()) break;//正の数と負の数の和の個数の和がkを上回ったらダメ
        ans = min(ans, 2 * y[i] + x[k - i]);
        ans = min(ans, 2 * x[k - i] + y[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1656
import math
def fact(a,b):
    ans = 1
    while a != b:
        ans *= a
        a -= 1
    return ans
def nCr(n,r):
    return (fact(n,r)) // (math.factorial(n-r))
def nHr(n,r):
    return nCr(n+r-1, r-1)
def prime(n): # nまでの素数を列挙
    import math
    num_list = [i + 1 for i in range(2,n,2)]
    list_prime = [2]
    limit = math.sqrt(n)
    if n == 2:
        return list_prime
    else:
        while True:
            p = num_list[0]
            if p >= limit:
                return list_prime + num_list
            list_prime.append(p)
            num_list = [num for num in num_list if num % p != 0]

def primeFactorization(n):
    import math
    list_prime = prime(int(math.sqrt(n)))
    i = 0
    dict_pF = {}
    dict_primeFactorization = {}
    for pri in list_prime:
        dict_pF[pri] = 0
    while True:
        if n == 1:
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        elif i >= len(list_prime):
            dict_pF[n] = 1
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        p = list_prime[i]
        if n % p == 0:
            n //= p
            dict_pF[p] += 1
            continue
        else:
            i += 1

ans = 1
n,m = map(int, input().split())
if m == 1:
    ans = 1
else:
    for factor,degree in primeFactorization(m).items():
        ans *= (nHr(degree,n)) % (10**9+7)
        
print(ans % (10**9+7))


Measured memory_bytes: 3912
/*
   Username : moondancer
   Name : Moon Dancer
*/


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

#define int long long

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    t^=1;
    cout<<t;
    return 0;
}

Measured memory_bytes: 3648
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
#define MAXN 200006
using namespace std;
int n,K,L,fa[3][MAXN],u,v,sum[MAXN];
vector<int> road[MAXN];
map<int,int> ma;
int root(int x,int op)
{
	if(fa[op][x]==x) return x;
	fa[op][x]=root(fa[op][x],op);
	return fa[op][x];
}
int main()
{
	scanf("%d%d%d",&n,&K,&L);
	for(int i=1;i<=n;i++)
	{
		fa[0][i]=i;
		fa[1][i]=i;
	}
	for(int i=1;i<=K;i++)
	{
		scanf("%d%d",&u,&v);
		fa[0][root(u,0)]=root(v,0);
	}
	for(int i=1;i<=L;i++)
	{
		scanf("%d%d",&u,&v);
		fa[1][root(u,1)]=root(v,1);
	}
	for(int i=1;i<=n;i++)
		road[root(i,0)].push_back(i);
	for(int i=1;i<=n;i++)
	{
		ma.clear();
		for(int j=0;j<(int)road[i].size();j++)
			ma[root(road[i][j],1)]++;
		for(int j=0;j<(int)road[i].size();j++)
			sum[road[i][j]]+=ma[root(road[i][j],1)];
	}
	for(int i=1;i<=n;i++)
		printf("%d ",sum[i]);
}

Measured memory_bytes: 14072
//#pragma warning disable
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System;
using System.Numerics;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int F() => int.Parse(ReadLine());
	long FL() => long.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	long[] GL() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();
	public const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var s = Console.ReadLine();
		var a = s.Select(c => c - '0').ToArray();
		for (var i = 0; i < 8; i++)
		{
			var x = a[0];
			for (var j = 0; j < 3; j++) x += ((i & (1 << j)) != 0 ? 1 : -1) * a[j + 1];
			if (x == 7)
			{
				Write(a[0]);
				for (var j = 0; j < 3; j++) Write("{0}{1}", (i & (1 << j)) != 0 ? "+" : "-", a[j + 1]);
				WriteLine("=7");
				break;
			}
		}
	}
}


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

const int N = 5e5 + 9;

int n, L, T, w[N], x[N], t;

int main () {
	scanf("%d%d%d", &n, &L, &T);
	for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &w[i]);
	for (int i = 0, j; i < n; ++i) {
		if (w[i] == 1) {
			j = x[i] + T;
			t = (j / L + t) % n;
			j %= L;
		} else {
			j = x[i] - T;
			if (j < 0) t = ((j + 1) / L - 1 + t) % n;
			j %= L;
			if (j < 0) j += L;
		}
		x[i] = j;
	}
	sort(x, x + n);
	if (t < 0) t += n;
	for (int i = 0; i < n; ++i) {
		printf("%d\n", x[(i + t) % n]);
	}
	return 0;
}

Measured memory_bytes: 1920
// Contest: Panasonic Programming Contest 2020 (https://atcoder.jp/contests/panasonic2020)
// Problem: C: Sqrt Inequality (https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c)


// region {{{ boilerplate
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <chrono>
#include <cstdint>
#include <deque>
#include <exception>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#if __cplusplus >= 201703L
#   include <optional>
#   include <string_view>
#   include <variant>
#endif

using namespace std;

#if __cplusplus >= 201703L
#   define all(a)      begin(a),end(a)
#   define sz(x)       ((int)size(x))
#else
#   define all(a)      (a).begin(),(a).end()
#   define sz(x)       ((int)(x).size())
#endif

#define rep(a, b)      for(int a = 0; a < (b); ++a)
#define reps(a, b, c)  for(int a = (b); a < (c); ++a)
#define trav(a, b)     for(auto& a : b)

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;

#if __cplusplus >= 201703L
#   define MAYBE_UNUSED [[maybe_unused]]
#else
#   define MAYBE_UNUSED
#endif

MAYBE_UNUSED static constexpr int INF = (int)1e9 + 5;
MAYBE_UNUSED static constexpr ll INFL = (ll)1e18 + 5;
MAYBE_UNUSED static mt19937 rng((u32)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion }}}

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

    ll a, b, c; cin >> a >> b >> c;
    if (c - a - b < 0)
        cout << "No\n", exit(0);
    cout << (4 * a * b <  (c - a - b) * (c - a - b) ? "Yes\n" : "No\n");

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int p[500][500];
int d[30][30];

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

    int n, c;
    cin >> n >> c;

    for (int i = 0; i < c; i++) {
        for (int j = 0; j < c; j++) {
            cin >> d[j][i];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
            p[i][j]--;
        }
    }

    int s[30][3] = {};
    for (int h = 0; h < c; h++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int m = (i + j) % 3;
                s[h][m] += d[h][p[i][j]];
            }
        }
    }

    int x = 1 << 30;
    for (int i = 0; i < c; i++) {
        for (int j = 0; j < c; j++) {
            if (j == i) continue;
            for (int k = 0; k < c; k++) {
                if (k == i || k == j) continue;
                x = min(x, s[i][0] + s[j][1] + s[k][2]);
            }
        }
    }

    cout << x << endl;

    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, k, ans = INFLL; cin >> n >> k;
    vi x(n);

    // 入力処理と始点の探索
    ll sp = INFLL;
    rep(i, n){
        cin >> x[i];
        if(sp == INFLL && x[i]>=0) sp = i;
        if(x[i] < 0) x[i] *= -1;
    }
    // 始点に0を挿入
    if(sp != INFLL) x.insert(x.begin()+sp, 0);
    else { x.push_back(0); sp = n; }
    n++;

    // 右方向にi本ロウソクを点ける
    for(ll i=1; i<=k; i++){
        // 左方向でk-i本ロウソクを点ける
        ll j = k-i;
        // もし範囲からはみ出る本数が指定されるなら飛ばす
        if(sp+i >= n || sp-j < 0) continue;
        // 右方向にi本ロウソクを点ける
        ll calc = x[sp+i];
        // 左方向に進む必要があるなら戻る分も考慮して移動量を算出
        if(j >= 1) calc += x[sp+i]+x[sp-j];
        // 最小値の更新
        chmin(ans, calc);
    }

    // 左方向にi本ロウソクを点ける
    for(ll i=1; i<=k; i++){
        // 右方向でk-i本ロウソクを点ける
        ll j = k-i;
        // もし範囲からはみ出る本数が指定されるなら飛ばす
        if(sp+j >= n || sp-i < 0) continue;
        // 左方向にi本ロウソクを点ける
        ll calc = x[sp-i];
        // 右方向に進む必要があるなら戻る分も考慮して移動量を算出
        if(j >= 1) calc += x[sp-i]+x[sp+j];
        // 最小値の更新
        chmin(ans, calc);
    }

    // 最小値の出力
    cout << ans << endl;
}

Measured memory_bytes: 1792
module.exports=function(e){var r={};function t(n){if(r[n])return r[n].exports;var o=r[n]={i:n,l:!1,exports:{}};return e[n].call(o.exports,o,o.exports,t),o.l=!0,o.exports}return t.m=e,t.c=r,t.d=function(e,r,n){t.o(e,r)||Object.defineProperty(e,r,{enumerable:!0,get:n})},t.r=function(e){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(e,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(e,"__esModule",{value:!0})},t.t=function(e,r){if(1&r&&(e=t(e)),8&r)return e;if(4&r&&"object"==typeof e&&e&&e.__esModule)return e;var n=Object.create(null);if(t.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:e}),2&r&&"string"!=typeof e)for(var o in e)t.d(n,o,function(r){return e[r]}.bind(null,o));return n},t.n=function(e){var r=e&&e.__esModule?function(){return e.default}:function(){return e};return t.d(r,"a",r),r},t.o=function(e,r){return Object.prototype.hasOwnProperty.call(e,r)},t.p="",t(t.s=0)}([function(e,r,t){t(1)(t(2).readFileSync("/dev/stdin","UTF-8"))},function(e,r){e.exports=function(e){for(var r=e.split("\n"),t=Number(r[0]),n=[],o=0;o<t;o++)n.push(Number(r[o+1]));for(var u=1,i=0;i<t;i++)if(2==(u=n[u-1]))return void console.log(i+1);console.log(-1)}},function(e,r){e.exports=require("fs")}]);

Measured memory_bytes: 27364
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i,n)       for(int i=0; i<n; i++)
#define clr(arr)       memset(arr, 0, sizeof arr)
#define all(x)         x.begin(), x.end()
const int MOD = 1e9 + 7;
template<class F, class S> ostream& operator<<(ostream &out, const pair<F, S> &p)
{
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out)
{
	out << '{';
	for (auto i = x.begin(); i != x.end(); i++)
		out << *i << (i == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dmp() {}
template<class T, class... Args> void dmp(T &&x, Args... args)
{
	cerr << x << ";  "; dmp(args...);
}
#ifdef SMIT
struct Nl {~Nl() {cerr << '\n';}};
#define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dmp(x), Nl(), cerr << ""
#else
#define debug(...) {}
#endif
// Yes you CAN
const int V = 1e5 + 1, N = 101;

int n, W, dp[N][V], w[N], v[N], no;

int knapsack2(int n, int val)
{
	if (n == no)
	{
		if (val) return INT_MAX;
		else return 0;
	}
	if (dp[n][val] != -1)
		return dp[n][val];
	int include = INT_MAX, exclude = INT_MAX;
	if (v[n] <= val)
	{
		include = w[n] + knapsack2(n + 1, val - v[n]);
	}
	exclude = knapsack2(n + 1, val);
	return dp[n][val] = min(include, exclude);

}
void solve()
{
// #define TEST
	memset(dp, -1, sizeof dp);
	cin >> n >> W;
	rep(i, n) cin >> w[i] >> v[i];
	int ans = 0;
	no = n;
	rep(i, V)
	{
		int wt = knapsack2(0, i);
		if (wt <= W)
			ans = i;
	}
	cout << ans << endl;

}

int32_t main()
{
#ifdef SMIT
	freopen("/home/smit/Desktop/in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while (t--)
		solve();
}

Measured memory_bytes: 82516
N_K = [int(i) for i in input().split()] 
A = [int(i) for i in input().split()]

A = len(A)
a = 0
l_s = N_K[1]
l = 0
for i in range(N_K[0]):
    
    if l>=N_K[0]:
        print(a)
        
        break
    a = a+1
    l = l + l_s
    if l > l_s:
        l -= 1

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

   typedef long long ll;
   typedef pair<ll, ll> Pii;
   typedef vector<ll> Vi;
   typedef vector<Vi> VVi;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define RSORT(x) sort((x).rbegin(), (x).rend()
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
   template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}
   ll pow(ll a, ll b, ll m){if (b == 0) return 1; else if (b % 2 == 0) return (pow(a * a, b / 2, m) % m); else return (pow(a * a, b / 2) * a) % m;}
   ll residue(ll a, ll m){return ((a % m) + m) % m;};

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

int main(){
   string S; cin >> S;
   ll ans = 0, temp = 0;
   REP(i, S.size()){
      if(S[i] == 'B') temp++;
      else ans += temp;
   }
   cout << ans << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<vector<pair<int, int>>> V(N);
  for (int i = 0, a; cin >> a; i++)
    for (int j = 0, x, y; j < a && cin >> x >> y; j++)
      V.at(i).push_back({x, y});

  int ans = 0;
  for (int bit = 0; bit < 1 << N; bit++) {
    for (int i = 0; i < N; i++) {
      if (bit >> i & 1) {
        for (auto v : V.at(i)) {
          int x = v.first - 1;
          int y = v.second;
          if (bit >> x & 1 ^ y) goto NG;
        }
      }
    }
    ans = max(ans, __builtin_popcount(bit));
    NG:;
  }

  cout << ans << "\n";
}

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

using namespace std;

int n,m;
int c[21];
int ans;
int dp[21][50001];
int null = -1;
int inf = 1<<21;

int dfs(int i,int price){
    int res;
    
    if(dp[i][price] != null){
        res = dp[i][price];
        return res;
    }
    else if(price == 0){
        res =  0;
    }
    else if(price < 0  || i == m){
        res = inf;
    }
    else if(price < c[i]){
        res = dfs(i+1,price);
    }
    else if(price > 0){
        res = min(dfs(i+1,price),dfs(i,price-c[i])+1);
    }
    dp[i][price] = res;
    return res;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> c[i];
    }
    //sort(c,c+m,greater<>());
    //なぜか上のように降順にソートすると以下のテストケースでacされる、ソートしないと43000回目くらいの再帰(i=0,price=6000くらい(c[i]=1)で唐突に止まる。
    //50000 20
    //1 92 1377 3168 7095 1170 1809 5046 3225 1054 4016 142 108 6430 3970 48 8416 4909 114 6968
    //調べたところメモリのスタック領域が何とか、、ソートするとaｃとなる理由はわからず。
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            dp[i][j] = null;
        }
    }
    ans = dfs(0,n);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9540
from fractions import gcd
import collections

a, b= map(int, input().split())

def factorization(n):
    arr = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.add(i)

    if temp!=1:
        arr.add(temp)
    if arr==[]:
        arr.add(n)
    return arr

l = gcd(a,b)
print(len(factorization(l)) + 1)


Measured memory_bytes: 5088
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int w,h,x,y,r;
    scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
    
    if(x-r >=0 &&
       x+r <=w &&
       y-r >= 0 &&
       y+r <= h){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    
    
    return 0;
}

Measured memory_bytes: 584
// Write your code here
#include <bits/stdc++.h>
using namespace std;
#include <iostream>

int main(){
	long long int n,ans=0,m,tmp=1,x;
	m=1e9+7;
	cin>>n;
	long long int arr[n],prefix[n+1];
	for(int j=0;j<n;j++){
		cin>>x;
		arr[j]=x%m;
	}
	prefix[0]=0;
	for(int j=0;j<n;j++){
		tmp=(prefix[j]+arr[j]);
		prefix[j+1]=(tmp)%m;
	}
	for(int j=0;j<n;j++){
		tmp=prefix[n]-prefix[j+1];
		tmp=tmp%m;
		tmp=arr[j]*tmp;
		tmp=tmp%m;
		ans=ans+tmp;
		ans=ans%m;
        if(ans<0){
            ans=ans+m;
            ans=ans%m;
        }
	}
	
	cout<<ans;
}

Measured memory_bytes: 6724
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 5;

int n, m, q;
int a[N], b[N];

int main()
{
  cin >> n >> m >> q;
  int xx = 1e9, yy = 1e9;
  for(int i = 0 ; i < n ; i++){
    cin >> a[i];
    xx = min(xx, a[i]);
  }
  for(int i = 0 ; i < m ; i++) {
    cin >> b[i];
    yy = min(yy, b[i]);
  }
  int best = xx + yy;
  while(q--) {
    int x, y, c;
    cin >> x >> y >> c;
    --x, --y;
    best = min(best, a[x] + b[y] - c);
  }
  cout << best << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int x;
    cin >> x;
    int n = x / 100;
    int mod = x % 100;
    if (mod <= n * 5) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

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


int main(){
  int sum=0;
  int sasum=0;
  int max=0;
  for(int i=0;i<5;i++){
   int time;
    cin>>time;
       sum+=time;
    
    int sa=0;
   if(time%10!=0) sa=10-time%10;
 
    sasum+=sa;
    if(sa>max)max=sa;
    
  }
  cout<<sum+sasum-max<<endl;
  
}

Measured memory_bytes: 384
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = iil()

cnt = 1
state = 'first'
for i in A:
#    print(i)
    if state == 'first':
        state = 'even'
    else:
        if state == 'even':
            if i > num:
                state = 'more'
            elif i < num:
                state = 'less'
        elif state == 'more':
            if i < num:
                cnt += 1
                state = 'even'
        elif state == 'less':
            if i > num:
                cnt += 1
                state = 'even'
    num = i
#print((cnt,state))
print(cnt)

Measured memory_bytes: 14480
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N;
  cin >> N;
  vector<int64_t> A(N + 1, 0);
  for (int64_t i = 1; i <= N; ++i) {
    cin >> A[i];
  }
  vector<int64_t> counts(N + 1, 0);
  vector<int64_t> result;
  for (int64_t i = N; i >= 1; --i) {
    int64_t s = 0;
    for (int64_t j = 2 * i; j <= N; j += i) {
      s += counts[j];
    }
    s %= 2;
    counts[i] = (A[i] == s) ? 0 : 1;
    if (A[i] == s) {
      counts[i] = 0;
    } else {
      counts[i] = 1;
      result.push_back(i);
    }
  }
  cout << result.size() << endl;
  if (result.size() > 0) {
    for (int64_t i = 0; i < static_cast<int64_t>(result.size()); ++i) {
      if (i != 0) {
        cout << " ";
      }
      cout << result[i];
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 5108
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1e5+100;
int a[maxn],n;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int maxx=a[0];
    for(int i=1;i<n;i++)
        maxx=max(maxx,a[i]);
    int ans=0;
    if(maxx&1)
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]==maxx) continue;
            if(min(abs(a[i]-maxx/2),abs(a[i]-maxx/2-1))<min(abs(ans-maxx/2),abs(ans-maxx/2-1)))
                ans=a[i];
        }
        printf("%d %d\n",maxx,ans);
    }
    else
    {

        for(int i=0;i<n;i++)
        {
            if(a[i]==maxx) continue;
            if(abs(a[i]-maxx/2)<abs(ans-maxx/2))
                ans=a[i];
        }
        printf("%d %d\n",maxx,ans);
    }
    return 0;
}


Measured memory_bytes: 512
n = int(input())
ans, cnt = 1, 0
for i in range(1, n+1):
    k = i
    t = 0
    while k != 0:
        if k%2 == 0:
            k /=2
            t += 1
        else:
            break    
    if t > cnt:
        ans = i
        cnt = t
print(ans)

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

int main() {
  int i=0,a=0;
  int N,l,r;
  cin >> N;
  for(i=0; i<N; i++){
      cin >> l >> r;
      a += (r - l + 1);
  }
  cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define repf(i, n) for(int i=1; i<(int)(n+1); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    lli n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p >> t;
    vi w = {r, s, p};
    vi tt(n);   // Win pattern
    rep(i, n){
        if(t[i] == 'r') tt[i] = 2;      // Win is "p(2)"
        else if(t[i] == 's') tt[i] = 0; // Win is "r(0)"
        else if(t[i] == 'p') tt[i] = 1; // Win is "s(1)"
    }

    vvi dp(n, vi(3, 0));
    // Devide k-groups
    rep(i, k){
        dp[i][tt[i]] = w[tt[i]];
        for(lli j = i+k; j<n; j +=k){
            for(int rsp=0; rsp<3; rsp++){
                if(tt[j] == rsp){
                    dp[j][rsp] = max(dp[j-k][(rsp+1)%3], dp[j-k][(rsp+2)%3]) + w[rsp];
                }else{
                    dp[j][rsp] = max(dp[j-k][(rsp+1)%3], dp[j-k][(rsp+2)%3]);
                }
            }
        }
    }
    lli ans = 0;
    rep(i, k) ans += max(dp[n-i-1][0], max(dp[n-i-1][1], dp[n-i-1][2]));
    cout << ans << endl;
}

Measured memory_bytes: 6608
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int h,w; cin >> h >> w;
  vector<string> s(h); rep(i,h) cin >> s[i];
  vector<vi> dp(h,vi(w,INF));
  if(s[0][0] == '#') dp[0][0] = 1;
  else dp[0][0] = 0;
  rep(i,h){
    rep(j,w){
      if(0 <= j-1){
        if(s[i][j-1] != s[i][j]) chmin(dp[i][j],dp[i][j-1]+1);
        else chmin(dp[i][j],dp[i][j-1]);
      }
      if(0 <= i-1){
        if(s[i-1][j] != s[i][j]) chmin(dp[i][j],dp[i-1][j]+1);
        else chmin(dp[i][j],dp[i-1][j]);
      }
    }
  }
  if(s[h-1][w-1] == '#') dp[h-1][w-1]++;
  cout << dp[h-1][w-1]/2;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3672
#include <iostream>


using namespace std;


int main()
{
	int d, n;

	cin >> d >> n;

	int hd = 1;

	while (d > 0){
		hd *= 100;
		d--;
	}

	if (n < 100)	cout << n*hd << "\n";
	else		cout << 101*hd << "\n";
}


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

using namespace std;

typedef long long ll;

int divi(int x, int d){
  if(x %d == 0) return x/d;
  else return x/d + 1;
}

int main(){
  int N, K; cin >> N >> K;
  int a[N+1];
  for(int i=1;i<=N;i++) cin >> a[i];
  if(K == N){
    cout << 1 << endl;
    return 0;
  }
  int idx = -1;
  for(int i=1;i<=N;i++){
    if(a[i] == 1) idx = i;
  }
  if(idx == 1 || idx == N){
    cout << divi(N - K, K - 1) + 1 << endl;
    return 0;
  }
  int d = K - 1;
  int ans = 1000000;
  for(int s=max(1, idx-d);s<=min(N, idx+d);s++){
    int left = max(0, divi(s - 1, d));
    int right = max(0, divi(N - (s + d), d));
    ans = min(ans, left + right + 1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define in(n1) cin>>n1
#define lp(i,j,n) for(int i=j;i<=n;i++)
#define output(n1) cout<<n1<<endl
#define output2(n2) cout<<n2<<" "
#define ll long long 
#define ld long double
using namespace std;
int main()
{
 int a,b;
  cin>>a>>b;
  cout<<a*b;
}

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

int main(){
  int N;
  cin >> N;
  long long int ans = 1;
  int mod = pow(10,9) + 7;
  for(long long int i = 1; i <= N;i++){
    ans = (ans%mod) * (i%mod);
    ans %= mod;
  }
  cout << ans%mod;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		
		if((char)s.charAt(1)=='B') {
			System.out.println("ARC");
		}else {
			System.out.println("ABC");
		}
		
	}
}

Measured memory_bytes: 27000
#include <iostream>

int main()
{
  int res[3];

  for (int i = 0; i < 3; ++i)
    std::cin >> res[i];

  if (res[0] == res[1]) {
    std::cout << res[2] << std::endl;
    return 0;
  }
  if (res[0] == res[2]) {
    std::cout << res[1] << std::endl;
    return 0;
  }
  if (res[1] == res[2]) {
    std::cout << res[0] << std::endl;
    return 0;
  }
}


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

len_A = len(A)
isOdd = len_A % 2 == 1
m = {}

nums = []
if isOdd:
    nums = [i for i in range(len_A) if i % 2 == 0]
    nums.append(0)
else:
    nums = [i for i in range(len_A) if i % 2 != 0]

for n in nums:
    m[n] = 0

for a in A:
    m.setdefault(a, 0)
    m[a] += 1

# check
for k, v in m.items():
    if k == 0:
        if isOdd:
            if v != 1:
                print(0)
                exit()
            else:
                continue
        else:
            print(0)
            exit()
    elif v == 0 or v > 2:
        print(0)
        exit()

print(pow(2, len_A//2) % 1000000007)


Measured memory_bytes: 15200
N, L = map(int, input().split())

aji = [L + i + 1 - 1 for i in range(N)]
saishouzettai = 999999
for v in aji:
    if abs(v) < abs(saishouzettai):
        saishouzettai = v

print(sum(aji)-saishouzettai)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll n , k;
    cin >> n >> k;
    ll ans = 1;
    ll cnt = k;

    while(!(cnt > n)){
        ans ++;
        cnt *= k;
    }

    dunk(ans);
}

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

int main(void)
{
	int i = 0,j = 0,ans = 0;
	int N = 0,T = 0,*A;
	int *a,*b;
	
	scanf("%d%d",&N,&T);
	
	A = (int *)malloc(sizeof(int) * N);
	a = (int *)malloc(sizeof(int) * N);
	b = (int *)malloc(sizeof(int) * N);
	
	for(i = 0;i < N;i++)
		b[i] = 0;
	for(i = 0;i < N;i++){
		scanf("%d",&A[i]);
	}
	
	a[0] = A[0];
	b[N - 1] = A[N - 1];
	for(i = 1;i < N;i++){
		if(a[i - 1] > A[i])
			a[i] = A[i];
		else
			a[i] = a[i - 1];
		
		if(b[N - i - 1] < A[N - i])
			b[N - i] = A[N - i];
		else
			b[N - i] = b[N - i - 1];
	}
	
	for(i = 0;i < N;i++){
		if(j < b[i] - a[i]){
			ans = 1;
			j = b[i] - a[i];
		}else if(j == b[i] - a[i])
			ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1280
#include<stdio.h>
#include<math.h>
int main(){

  double n;
  double s[1000];
  int i;
  double sum,ave,ans;
  
  while(scanf("%lf",&n),n){
    sum=0;
    for(i=0;i<n;i++){
      scanf("%lf",&s[i]);
      sum+=s[i];
    }
    
    ave = sum / n;
    ans = 0;
    
    for(i=0;i<n;i++){
      ans+=(ave-s[i])*(ave-s[i]);
    }
    ans /= n;
    printf("%lf\n",sqrt(ans));
    
  }
  return 0;
}

	   
    
  



Measured memory_bytes: 2048
#include <iostream>

void printN (int N);
int main()
{
    int N;
    std::cin >> N;
    printN (N);
	return 0;
    }

void printN (int N)
{
    for (int i = 0; i < N; ++i) {
        int x, y, z;
        std::cin >> x >> y >> z;
        if (x * x + y * y == z * z) {
        std::cout << "YES" << std::endl;
        } else if (y * y + z * z == x * x) {
        std::cout << "YES" << std::endl;
        } else if (z * z + x * x == y * y) {
        std::cout << "YES" << std::endl;
        } else {
        std::cout << "NO" << std::endl;
        }
    }
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

struct Combination {
    vector<int64_t> fact, rfact;
    Combination(int sz) : fact(sz + 1), rfact(sz + 1) {
        fact[0] = 1;
        for(int i = 1; i < fact.size(); i++){
            fact[i] = fact[i - 1] * i % mod;
        }
        rfact[sz] = inv(fact[sz]);
        for(int i = sz - 1; i >= 0; i--){
            rfact[i] = rfact[i + 1] * (i + 1) % mod;
        }
    }
    int64_t inv(int x) const {
        return pow(x, mod - 2);
    }
    int64_t pow(int64_t x, int64_t n) const {
        int64_t ret = 1;
        while(n > 0){
            if(n & 1) (ret *= x) %= mod;
            (x *= x) %= mod;
            n >>= 1;
        }
        return (ret);
    }
    int64_t P(int n, int r) const {
        if(r < 0 || n < r) return (0);
        return (fact[n] * rfact[n - r] % mod);
    }

    int64_t C(int p, int q) const {
        if(q < 0 || p < q) return (0);
        return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
    }

    int64_t H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return (r == 0 ? 1 : C(n + r - 1, r));
    }
};

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n);
    Combination cb(n);
    rep(i, 0, n){
        cin >> x[i];
    }
    x[n - 1]++;
    int ans = 1;
    int target = 1;
    rep(i, 0, n){
        if(target <= x[i]){
            x[i] = target;
            target += 2;
        }else{
            x[i] = target - 2;
        }
    }
    map<int, int> mp;
    rep(i, 0, n) mp[x[i]]++;
    int cnt = 0;
    for(auto i : mp){
        if(i.second == 2){
            ans = (ans * (cnt + 2)) % mod;
            cnt++;
        }else{
            cnt++;
        }
    }
    ans = ans * cb.fact[mp.size()] % mod;
    cout << ans << endl;
}

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

const long long FACT_MAX = 1001;
const long long MOD = 1e9+7;
long long famod[FACT_MAX+1];
long long simod[FACT_MAX+1];
long long fimod[FACT_MAX+1];

void create_fact_mod(int num){
    famod[0] = 1;
    famod[1] = 1;
    long long i;
    for(i=2; i<=num; i++){
        famod[i] = famod[i-1] * i % MOD;
    }
}

void create_seq_inv_mod(int num){
    simod[0] = 1;
    simod[1] = 1;
    long long i;
    for(i=2; i<=num; i++){
        simod[i] = (MOD - MOD/i) * simod[MOD%i] % MOD;
    }
}

void create_fact_inv_mod(int num){
    fimod[0] = 1;
    fimod[1] = 1;
    long long i;
    for(i=2; i<=num; i++){
        fimod[i] = fimod[i-1] * simod[i] % MOD;
    }
}

void create_mod_tables(int num){
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

long long comb_mod(int n, int k){
    return famod[n] * fimod[n-k] % MOD * fimod[k] % MOD;
}

long long perm_mod(int n, int k){
    return famod[n] * fimod[n-k] % MOD;
}

long long power_mod(long long num, long long power){
    long long prod = 1;
    num %= MOD;
    while(power > 0){
        if((power&1) == 1){
            prod = prod * num % MOD;
        }
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

long long extgcd(long long a, long long b, long long& x, long long& y){
    long long d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) % x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

long long mod_inv(long long a){
    long long x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

const int MAX = 1001;
long long dp[MAX][MAX];

int main(){
    long long i, j, k;
    long long N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;

    create_mod_tables(N);

    dp[A-1][0] = 1;
    for(i=A; i<=B; i++){
        for(j=0; j<=N; j++){
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            for(k=C; (k<=D && j+i*k<=N); k++){
                long long add = perm_mod(N-j, i*k) * power_mod(fimod[i], k) % MOD * fimod[k] % MOD;
                dp[i][j+i*k] = (dp[i][j+i*k] + add * dp[i-1][j] % MOD) % MOD;
            }
        }
    }
    cout << dp[B][N] << endl;
    return 0;
}

Measured memory_bytes: 8064
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s[1]=='S'){
        int cnt = 0;
        REP(i,3){
            if(s[i]=='R')cnt++;
        }
        cout << min(1,cnt) << endl;
    }else{
        int cnt = 0;
        REP(i,3){
            if(s[i]=='R')cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}

Measured memory_bytes: 3636
#include	<cstdint>
#include	<iostream>
#include	<fstream>
#include	<string>

typedef		std::uint_least16_t		USI;
typedef		std::int_least16_t		SSI;
typedef		std::uint_least32_t		ULI;		//10^9
typedef		std::int_least32_t		SLI;
typedef		std::uint_least64_t		ULLI;
typedef		std::int_least64_t		SLLI;

using namespace std;

struct Card
{
	char	S;
	USI		N;
};

string		StableCheck[9];

void	Swap(Card pC[], int a, int b)
{
	Card temp = pC[a];
	pC[a] = pC[b];
	pC[b] = temp;
}

void	CheckStable(Card C[], int N, string str[])
{
	for (int i = 0; i < N; i++)
	{
		str[C[i].N - 1] += C[i].S;
	}
}

void	PrintOutStable(string str[])
{
	bool	IsStableSort = true;

	for (int i = 0; i < 9; i++)
	{
		if (str[i] != StableCheck[i])
		{
			IsStableSort = false;
			break;
		}
	}

	if (IsStableSort)
	{
		cout << "\nStable\n";
	}
	else
	{
		cout << "\nNot stable\n";
	}
}

void	PrintOut(Card pC[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (i != 0)		cout << " ";
		cout << pC[i].S << pC[i].N;
	}
}

void	BubbleSort(const Card pC[], int N)
{
	Card	C[36];
	bool	IsStable = true;

	for (int i = 0; i < N; i++)
	{
		C[i] = pC[i];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = N - 1; j > i; j--)
		{
			if (C[j].N < C[j - 1].N)
			{
				Swap(C, j, j - 1);
			}
		}
	}

	PrintOut(C, N);

	string		strSelectionSort[9];
	CheckStable(C, N, strSelectionSort);
	PrintOutStable(strSelectionSort);
}

void	SelectionSort(const Card pC[], int N)
{
	Card	C[36];

	for (int i = 0; i < N; i++)
	{
		C[i] = pC[i];
	}

	for (int i = 0; i < N; i++)
	{
		int	minj = i;
		for (int j = i; j < N; j++)
		{
			if (C[j].N < C[minj].N)
			{
				minj = j;
			}
		}
		if (i != minj)
		{
			Swap(C, i, minj);
		}
	}

	PrintOut(C, N);

	string		strSelectionSort[9];
	CheckStable(C, N, strSelectionSort);
	PrintOutStable(strSelectionSort);
}

int main()
{
	int		N;
	cin >> N;
	cin.clear();
	cin.ignore();

	Card	C[36];
	string	str;

	for (int i = 0; i < N; i++)
	{
		cin >> str;
		C[i].S = str[0];
		C[i].N = str[1] - '0';
	}

	CheckStable(C, N, StableCheck);

	BubbleSort(C, N);
	SelectionSort(C, N);

	return 0;
}

Measured memory_bytes: 3132
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    long n;
    cin >> n;
    long mini = 10000000000000;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            long b = n / i;
            mini = min( mini, i + b - 2);
        }
    }
    cout << mini << endl;
}

Measured memory_bytes: 256
a, b = map(int, input().split())
if (b - a + 1) % 2 == 0:
    if a % 2 == 0:
        print((b - a + 1) // 2 % 2)
    else:
        print(a ^ b ^ ((b - a - 1) // 2 % 2))
else:
    if a % 2 == 1:
        print(a ^ (b - a) // 2 % 2)
    else:
        print(b ^ (b - a) // 2 % 2)


Measured memory_bytes: 3060