akhauriyash/Code-Regression huggingface dataset:
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

calc :: Int -> Int -> Int
calc width height
    | height `mod` 3 == 0 = 0
    | width `mod` 3 == 0 = 0
    | otherwise = minimum $ diff width height (width `div` 2)
    where
        diff _ _ 0 = [width]
        diff w h n =
            let r1 = n * h
                r2 = (w - n) * (h `div` 2)
                r3 = (w - n) * (h - h `div` 2)
                rr = [r1, r2, r3]
            in (maximum rr - minimum rr) : diff w h (n - 1)
main :: IO ()
main = do
    [h, w] <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    print $ min (calc h w) (calc w h)


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

#define MAXN 500005
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f

using namespace std;

typedef greater<int> gr;
typedef vector<int> ve;

int n, k; 
int a[MAXN], deg[MAXN], ans[MAXN], total;
vector<int> g[MAXN];

struct segment {
	int l, r, v;
}t[MAXN << 2];

int read() {
	char c = getchar();
	int x = 0;
	while (!isdigit(c))
		c = getchar();
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x;
}

void build(int l = 1, int r = n, int x = 1) {
	t[x].l = l;
	t[x].r = r;
	t[x].v = INF;
	if (l == r)
		return ;
	int mid = (l + r) >> 1;
	build(l, mid, ls);
	build(mid + 1, r, rs);
}

void pushup(int x) {
	t[x].v = min(t[ls].v, t[rs].v);
}

void modify(int p, int v, int x = 1) {
	if (t[x].l == t[x].r) {
		t[x].v = v;
		return ;
	}
	int mid = (t[x].l + t[x].r) >> 1;
	if (p <= mid)
		modify(p, v, ls);
	else 
		modify(p, v, rs);
	pushup(x);
}

int query(int l, int r, int x = 1) {
	if (l <= t[x].l && t[x].r <= r)
		return t[x].v;
	int mid = (t[x].l + t[x].r) >> 1, res = INF;
	if (l <= mid)
		res = min(res, query(l, r, ls));
	if (r > mid)
		res = min(res, query(l, r, rs));
	return res;
}

void construct(int u, int l, int r) {
	int v = query(l, r);
	if (v != INF) {
		// cout << u << " -> " << v << endl;
		g[u].push_back(a[v]);
		++deg[a[v]];
	}
}

void topsort() {
	priority_queue<int, ve, gr> q;
	for (int i = 1; i <= n; ++i)
		if (!deg[i])
			q.push(i);
	while (!q.empty()) {
		int u = q.top();
		ans[u] = ++total;
		q.pop();
		for (int i = 0; i < (int)g[u].size(); ++i) {
			int v = g[u][i];
			if (--deg[v] == 0)
				q.push(v);
		}
	}
}

int main() {
	n = read();
	k = read();
	build();
	for (int i = 1; i <= n; ++i) 
		a[read()] = i;
	// for (int i = 1; i <= n; ++i)
		// cout << a[i] << " ";
	// cout << endl;
	for (int i = n; i >= 1; --i) {
		construct(a[i], max(1, a[i] - k + 1), a[i]);
		construct(a[i], a[i], min(a[i] + k - 1, n));
		modify(a[i], i);
	}	
	topsort();
	for (int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
}

Measured memory_bytes: 51968
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
constexpr int MOD = 100000000 + 7;
// constexpr int MOD = 998244353;
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;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int modpow(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

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

    int r;
    cin>>r;
    cout << r * r << endl;
}


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

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, x;
cin >> k >> x;
int high = 1000000;
int low = 0 - high;
int left = max(low, x - k + 1);
int right = min(high, x + k - 1);
for (int i = left; i <=right; i++){
cout << i << " ";
}
cout << "\n";
return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
using ll = long long;
using namespace std;

int main(){
    int k, n, tmp, kind = 0;
    int a[200100];
    REP(i, 200100){
        a[i] = -1;
    }
    cin >> n >> k;
    REP(i, n){
        cin >> tmp;
        if(a[tmp] == -1){
            kind++;
            a[tmp]++;
        }
        a[tmp]++;
    }
    int need = kind - k;
    sort(a, a + 200099);
    int ans = 0;
    int j = 0;
    for(int i = 0; i < need; i++){
        if(a[j] == -1){
            i--;
        }else{
            ans += a[j];
        }
        j++;
    }
    cout << ans << endl;
}

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

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

int main() {

    long long N, H;
    cin >> N >> H;

    vector<long long> a(N), b(N);
    for (int i = 0; i < N; i++) cin >> a[i] >> b[i];

    long long maxA = *max_element(a.begin(), a.end());

    priority_queue<long long> Q;
    for (int i = 0; i < N; i++) if (b[i] > maxA) Q.push(b[i]);

    int ans = 0;
    while (!Q.empty()) {
        long long d = Q.top();
        Q.pop();
        if (H <= 0) break;
        H -= d;
        ans++;
    }

    ans += max(0LL, H) / maxA;
    H -= (max(0LL, H) / maxA) * maxA;
    if (H > 0) ans++;

    cout << ans << endl;

    return 0;
}




























Measured memory_bytes: 2936
/*for better*/
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define f(i,a,b) for(i=a;i<b;i++)
#define fr(i,a,b) for(i=a;i>=b;i--)
#define endl '\n'
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define M 998244353
#define inf 1e9+10
using namespace std;

ll dp[100005];

int main()
{
    fast; 
    ll n,mx,i,j,m=100005,ans=0,x;
    cin>>n>>mx;
    ll w[n+1],v[n+1];
    f(i,1,n+1)
    	cin>>w[i]>>v[i];
    
    dp[0]=0;
    f(j,1,m)
    	dp[j]=inf;

    f(i,1,n+1)
    {
    	fr(j,m-1,1)
    	{
    		if(j>=v[i])
    		{
    			x=w[i]+dp[j-v[i]];
    			if(dp[j]>x)
    			{
    				dp[j]=x;
    				if(x<=mx)
    					ans=max(ans,j);
    			}
    		}
    	}
    }
    cout<<ans;
}


Measured memory_bytes: 1024
arr = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", ")
K = int(input())
print(arr[K-1])



Measured memory_bytes: 2940
#include <iostream>

using namespace std;
long long a[50],k;
int main(){
    cin >> k;
    long long i,x = k%50;
    cout << 50 << endl;
    for(i=0;i<50;i++){
        a[i] = 50 - i;
    }
    for(i=0;i<50;i++){
        if(i<x) a[i] += k/50;
        else a[i] += (k/50-1LL);
        cout << a[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define dl double long
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }

ll gcd(ll a, ll b){
  ll surp, ans=b;
  surp = a%b;
  if(surp != 0) ans = gcd(b, surp);
  return(ans);
}

int main()
{
  ll K, sum=0;
  cin >> K;

  REP(i, 1, K+1){
    REP(j, 1, K+1){
      REP(k, 1, K+1){
        sum += gcd(i, gcd(j, k));
      }
    }
  }
  cout << sum << "\n";
}


Measured memory_bytes: 3632
#include <iostream>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <random>
#include <string>
#include<algorithm>


using namespace std;


int main(){
	string s;
	cin >> s;
	if(s.find("AC") != string::npos){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

    return 0;
}

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

#define pb push_back
#define fi first
#define se second
typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int s, w;
	cin >> s >> w;
	if (s <= w)
		cout << "un";
	cout << "safe\n";
}


Measured memory_bytes: 3660
import sys
input = sys.stdin.readline
n = int(input())
rl = [list(map(int, input().split())) for i in range(n)]
bl = [list(map(int, input().split())) for i in range(n)]

rl.sort(key=lambda x: x[1], reverse=True)
bl.sort(key=lambda y: y[0])

ans=0

# 貪欲
# それぞれの青に対してペアになれる赤のうち、yが最大のものを選んでいく
for b in bl:
    for r in rl:
        if r[0] < b[0] and r[1] < b[1]:
            rl.remove(r)
            ans += 1
            break
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef long long LL;

int main() {
//    freopen("test.txt", "r", stdin);
    int n, tmp;
    scanf("%d", &n);
    map<int, int> m;
    set<int> s2;
    set<int> s4;
    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        m[tmp]++;
        if (m[tmp] == 2)  s2.insert(-tmp);
        if (m[tmp] == 4) s4.insert(tmp);
    }
    LL ret = 0;
    if (s2.size() >= 2) {
        ret = *s2.begin();
        ret *= *(++s2.begin());
    }
    if (!s4.empty()) {
        LL tmp = *s4.rbegin();
        tmp = tmp*tmp;
        ret = tmp > ret ? tmp : ret;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 4992
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = Console.ReadLine().Split(' ');
            int iN = int.Parse(sS[0]);
            sS = Console.ReadLine().Split(' ');
            List<int> lstM = new List<int>();
            for (int i = 0; i < sS.Length; i++) { lstM.Add(int.Parse(sS[i])); }
            List<int> lstB = new List<int>();
            lstB.AddRange(lstM);
            List<int> lst2 = new List<int>();
            //// debug入力
            //int iN = 200000;
            //List<int> lstM = new List<int>();
            //for (int i = 0; i < iN; i++) { lstM.Add(i + 1); }
            //List<int> lstB = new List<int>();
            //lstB.AddRange(lstM);
            //List<int> lst2 = new List<int>();

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析出力
            lstB.Sort();
            lst2.AddRange(lstB);
            iN = (iN / 2) - 1;
            if (iN > 100)
            {
                int iMd1 = lstB[iN + 0];
                int iMd2 = lstB[iN + 1];
                int iMda = 0;
                for (int i = 0; i < lstM.Count; i++)
                {
                    iMda = iMd1;
                    if (lstM[i] <= iMd1) { iMda = iMd2; }
                    Console.WriteLine("{0}", iMda.ToString().Trim());
#if DEBUG
                    if (i > 100) { break; }
#endif
                }
            }
            else
            {
                for (int i = 0; i < lstM.Count; i++)
                {
                    lstB.Remove(lstM[i]);
                    Console.WriteLine("{0}", lstB[iN].ToString().Trim());
                    lstB.Clear();
                    lstB.AddRange(lst2);
#if DEBUG
                    if (i > 100) { break; }
#endif
                }
            }

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }
}


Measured memory_bytes: 38648
#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int next;
	int to;
	int color;
}edge[200005];
int head[100005],cnt,m[100005],ans,n;

void add(int u,int v)
{
	edge[++cnt].next=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}
void dfs(int x,int fa)
{
//	cout<<x<<endl;
	int us=1,ban=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		if(edge[i].to==fa)
		{
	//		cout<<i<<endl;
			ban=edge[i].color;
			break;
		}
	}
//	cout<<x<<' '<<ban<<endl;
	for(int i=head[x];i;i=edge[i].next)
	{

		if(edge[i].to==fa) continue;	//	cout<<x<<' '<<us<<endl;
		if(us==ban)
			us++;
		edge[i].color=edge[i+1].color=us;

		dfs(edge[i].to,x);		us++;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		if(u>v) swap(u,v);
		add(u,v);
		add(v,u);
		m[u]++;
		m[v]++;
	}
	for(int i=1;i<=n;i++)
	{
//		t[i]=m[i];
		ans=max(ans,m[i]);
	}
	cout<<ans<<endl;
	dfs(1,0);
	for(int i=1;i<=2*(n-1);i+=2)
		cout<<edge[i].color<<endl;
	return 0;
}

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

int n;

int main() {
	//freopen(".inp", "r", stdin); freopen(".out", "w", stdout);
	cin >> n;
	int ans = 0;
	while (n--) {
		int a; cin >> a;
		ans += a - 1;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int x, y;
  for (;;) {
    cin >> x >> y;
    if (x == 0 && y == 0)
      break;

    if (x < y) {
      cout << x << " " << y << endl;
    } else {
      cout << y << " " << x << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

const int INF = 1001001001;
 
int main(){
    int H, N;
    cin >> H >> N;
    int A[N], B[N];
    rep(i, N) cin >> A[i] >> B[i];

    ll dp[N+1][H+1];
    vec<ll> dpnew(H+1, INF);
    dpnew[0] = 0;
    rep(h, H+1) rep(n, N+1) dp[n][h] = INF;
    rep(n, N+1) dp[n][0] = 0;
    rep(n, N) rep(h, H) {
        int nh = min(h+A[n], H);
        dp[n+1][nh] = min(dp[n][nh] , dp[n+1][h] + B[n]);
        dpnew[nh] = min(dpnew[h]+B[n], dpnew[nh]);
        // if (h-A[n-1]>=0) {
        //     dp[n][h] = min(dp[n-1][h], dp[n][h-A[n-1]] + B[n-1]);
        // } else {
        //     dp[n][h] = dp[n-1][h];
        // }
    }

    // for(int n=0; n<=N; n++) {
    //     for(int h=0; h<=H; h++) {
    //         cout << dp[n][h] << " ";
    //     }
    //     cout << endl;
    // }

    //cout << dp[N][H] << endl;
    cout << dpnew[H] << endl;
}

Measured memory_bytes: 78592
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define INF 1000000000000000000
#define all(x) x.begin(), x.end()
#define PI 3.141592653589793

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
    dp[0][0] = 0;
    rep(i, N) {
        rep(j, M) {
            dp[i + 1][j] = (dp[i][j] - (ll)j) + (ll)(M - j);
            dp[i][j + 1] = (dp[i][j] - (ll)i) + (ll)(N - i);
        }
    }

    rep(i, N + 1) {
        rep(j, M + 1) {
            if (dp[i][j] == (ll)K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 8064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            while (true)
            {
                string input = Console.ReadLine();

                if (string.IsNullOrEmpty(input)) break;

                string[] arr = input.Split(' ');
                int x = int.Parse(arr[0]);
                int y = int.Parse(arr[1]);

                int gcd = GCD(x, y);
                int lcm = x / gcd * y;

                sb.AppendLine(gcd + " " + lcm);
            }
            Console.Write(sb);
        }

        static int GCD(int x, int y)
        {
            int a = Math.Max(x, y);
            int b = Math.Min(x, y);
            int r;

            while ((r = a % b) != 0)
            {
                a = b;
                b = r;
            }
            return b;
        }
    }
}

Measured memory_bytes: 9192
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif


int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n;
  cin >> n;
  unordered_map<ll,int> mp;
  vector<ll> a(n);
  rep(i,n) {
    cin >> a[i];
    mp[a[i]]++;
  }

  int cnt = 0;
  auto check = [&](ll x, ll y) {
    if (mp.count(y)) {
      if (x == y && mp[y] >= 2) {
        cnt++;
        return true;
      }
      else if (x != y) {
        cnt++;
        return true;
      }
    }
    return false;
  };

  rep(j,n) {
    for (ll i = 1; i*i <= a[j]; ++i) {
      if (a[j]%i != 0) continue;
      if (check(a[j], i)) break;
      if (i*i != a[j]) {
        if (check(a[j], a[j]/i)) break;
      }
    }
  }
  std::cout << n - cnt << endl;
  return 0;
}

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

using namespace std;
typedef long long int LL;
const int MAXN = 200010;
int a[MAXN], n;
bool play()
{
    int cnt = 0, x = 0;
    for(int i = 0; i < n; i++) if(a[i]&1) cnt++, x = i;
    if((n - cnt) & 1) return true;
    if(cnt > 1) return false;
    if(a[x] == 1) return false;
    a[x] -= 1;
    int g = a[0];
    for(int i = 1; i < n; i++) g = __gcd(g, a[i]);
    for(int i = 0; i < n; i++) a[i] /= g;
    return !play();
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    if(n == 1) puts(a[0]&1 ? "Second":"First");
    else puts(play() ? "First" : "Second");

    return 0;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

class Main {
    static int TABLE_SIZE = 50;

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

        int n = Integer.parseInt(r.readLine());
        String[] str = r.readLine().split(" ");

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }

        LinkedList<Integer>[] listTable = generateHashedTable(arr);

        int q = Integer.parseInt(r.readLine());
        String[] str2 = r.readLine().split(" ");

        Integer[] arr2 = new Integer[q];
        for(int i = 0; i < q; i++) {
            arr2[i] = Integer.parseInt(str2[i]);
        }

        int count = 0;
        for(Integer v: arr2) {
            if (search(listTable, v)) {
                count ++;
            }
        }

        System.out.println(count);
    }

    private static LinkedList<Integer>[] generateHashedTable(Integer[] arr) {
        @SuppressWarnings("unchecked")
        LinkedList<Integer>[] listTable = (LinkedList<Integer>[]) new LinkedList[TABLE_SIZE];

        for (Integer v : arr) {
            int h = generateHash(v);
            if (listTable[h] == null) {
                listTable[h] = new LinkedList<>();
            }

            LinkedList<Integer> list = listTable[h];
            list.add(v);
        }

        return listTable;
    }

    private static boolean search(LinkedList<Integer>[] listTable, Integer searchNum) {
        int h = generateHash(searchNum);

        LinkedList<Integer> list = listTable[h];
        if (list == null) { return false; }

        return list.contains(searchNum);
    }

    private static int generateHash(Integer v) {
        int h = v.hashCode();
        if (h < 0) {  h = 0 - h; }
        return h % TABLE_SIZE;
    }
}

Measured memory_bytes: 27804
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
#define REP(i,n) for(int i=0;i<(int)n;++i)
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
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 (a>b) { a=b; return 1; } return 0; }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

ll N, M, V, P;

bool judge(ll idx, vector<ll> &A){
    ll kosu = A.end() - upper_bound(A.begin(), A.end(), A[idx]);
    if(kosu <= P-1) return true;

    ll R = V*M - (P)*M;
    ll zibun = A[idx] + M;
    ll tot = 0;
    //dump(zibun)
    REP(i, N-(P-1)){
        //dump(A[i])
        if(i == idx) continue;
        if(A[i]>zibun) return false;
        tot += min(zibun-A[i], M);
    }
    //dump(tot)
    //dump(R)
    if(tot>=R) return true;
    else return false;
}

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

    cin >> N >> M >> V >> P;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    sort(A.begin(), A.end());
    //cout << A << endl;

    ll ng = -1, ok = N;
    while(ok-ng>1){
        ll md = (ok+ng)/2;
        //dump(md)
        bool ja = judge(md, A);
        //dump(ja)
        if(ja) ok = md;
        else ng = md;
    }
    cout << N - ok << endl;
    return 0;   
}

Measured memory_bytes: 1024
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
C=input()
red=0
redls=[]
for i,ele in enumerate(C):
    if ele=="R":
        red+=1
        redls.append(i)
redth=0
for i in range(red):
    if C[i]=="R":
        redth+=1   
diff=red-redth
print(diff)

Measured memory_bytes: 17960
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<tuple>
#include <iomanip>

typedef long long ll;
typedef long double ld;

using namespace std;
using Graph = vector<vector<ll>>;

#define rep(i, N) for (ll i = 0; i < (ll)(N); ++i)
#define ALL(a) (a).begin(),(a).end()

const ll inf = 1e18+7;
const ll mod = 1e9+7;

ll GetDigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

int main(){
    char C;
    cin >> C;
    cout << ++C << endl;
	return 0;
}



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

int main() {
 string s;
 cin >> s;
 int n = s.size();
 bool k = true,g = true;
 for(int i = 0; i < n;i++){
 	if(i % 2 ==1){
 		if(s.at(i) == 'R'){
 			g = false;
 		}
 	}
 	else{
 		if(s.at(i) == 'L'){
 			k = false;
 		}
    }
 }

 	if(k&&g){
 		cout << "Yes" << endl;
 	}
 	else{
 		cout << "No" << endl; 
 	}
 } 



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<stack>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int main(){
	ll a,b,c;
	cin>>a>>b>>c;
	if(a+b>=c)
		cout<<"No"<<endl;
	else{
		ll d=c-a-b;
		d=d*d;
		if(4*a*b<d)
			cout<<"Yes";
		else
			cout<<"No";
	}
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <ios>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
using namespace std;
typedef long long ll;
#define mp make_pair;
#define pb push_back;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

ll gcd(ll a, ll b) {
  if(a < b) gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll A,B,C,D;
  cin >> A >> B>> C >>D;
  ll ans_A=0;
  ll ans_B=0;
  ll lcm = D*(C/gcd(C,D));
  ans_A = (A-1)/C + (A-1)/D - (A-1)/lcm;
  ans_B = (B)/C + (B)/D - (B)/lcm;
  //  cout << ans_A << " " << ans_B << endl;
  ll ans = B - A + 1 +(ans_A) - ans_B;

  cout << ans << endl;


  return 0;
    

}


Measured memory_bytes: 256
n = gets.to_i
m = gets.split(" ").map(&:to_i)
numbers = m[0,n-1]
answer = m[-1]
dp = Array.new(n-1) {Array.new(21, 0)}
dp[0][numbers[0]] = 1
numbers[1..-1].each_with_index do |number, i|
  #p i
  dp[i].each_with_index do |current, j|
    if ! ((j + number) > 20)
      dp[i+1][j + number] += current
    end
    if ! ((j - number) < 0)
      dp[i+1][j - number] += current
    end
  end
end
puts dp[-1][answer]

Measured memory_bytes: 8684
N, M, X = gets.chomp.split(" ").map(&:to_i)
A = gets.chomp.split(" ").map(&:to_i)

C = Array.new(N, 0)
A.each{|a| C[a-1] = 1}
wk = C[0, X-1].inject(:+)

puts [wk, M-wk].min


Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
#include <algorithm>
//#include <iomanip> : 表示桁数

#define pi 3.14159265358979323846
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
typedef unsigned char Byte;
using namespace std;

//string ans = "Yes";
string ans;
int K;
string S;
int main() {
	cin >> K >> S;
	if (S.length() > K) {
		S = S.substr(0, K);
		S += "...";
	}
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 3640
#include<stdio.h>

int main(void)
{
  int a, b, d, r;
  double f;

  scanf("%d %d", &a, &b);

  d = a / b;
  r = a % b;
  f = 1.0 * a / b;
  
  printf("%d %d %lf\n", d, r, f);

  return 0;
}



Measured memory_bytes: 2140
T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            a = min(a, a ^ b)
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')


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

using namespace std;

int main(void){
string s;
string t;
cin>>s;
cin>>t;
int c=0;

for(int i=0;i<s.length();i++){
  if(s[i]!=t[i]){
    c++;
  }
}
cout<<c;
return 0;
}


Measured memory_bytes: 3920
#include<stdio.h>

int main() {
  int a, b, n;

  scanf("%d%d", &a, &b);
  
  if (a < b) {
    n = a;
    a = b;
    b = n;
  }
  while (b > 0) {
    n = a % b;
    a = b;
    b = n;
  }
  
  printf("%d\n", a);
  
  return 0;
}

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

#define se second
#define fi first
#define mk(a,b) make_pair(a,b)

typedef long long ll;
typedef pair<ll,ll> pii;

ll N;
ll A[100010];

class BIT
{
public:
    vector<ll> bit;
    int M;

    BIT(int M):
        bit(vector<ll>(M + 1, 0)), M(M + 1) {}

    int sum(int i)
    {
        if(!i)return 0;
        return bit[i] + sum(i - (i & -i));
    }

    void add(int i, int x)
    {
        if(i > M)return;
        bit[i] += x;
        add(i + (i & -i), x);
    }
};

bool judge(int mid)
{
    ll mem[100010] = {0};
    for(int i = 0; i < N; i++)
    {
        if(A[i] <= mid)mem[i] = 1;
        else mem[i] = -1;
    }

    vector<pii> v;
    ll tmp = 0;
    for(int i = 0; i < N; i++)
    {
        tmp += mem[i];

        v.push_back(mk(tmp, -i - 1));
    }
    v.push_back(mk(0,0));

    sort(v.begin(), v.end());

    BIT bit(N + 10);
    ll sum = 0;
    for(int i = 0; i < v.size(); i++)
    {
        sum += bit.sum(-v[i].se + 1);
        bit.add(-v[i].se + 1, 1);
    }

    if(N * (N + 1) / 2 < sum * 2)return true;
    return false;
}

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

    int l = 0, r = 1000000001;
    for(int i = 0; i < 100; i++)
    {
        int mid = (l + r) / 2;
        if(judge(mid))r = mid;
        else l = mid;
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 7464
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
#include <numeric>
#include <tuple>



typedef long long ll;


using namespace std;

typedef pair<int, int> P;
#define FOR(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) FOR(i,0,n)



ll fast_pow(ll x,ll n,ll mod){
    if (n==0) return 1;
    ll res=fast_pow(x*x %mod,n/2,mod);
    if (n&1) res=res*x%mod;
    return res;
}

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;




int main(){
    int N;
    cin>>N;
    int a[N];
    rep(i,N){
        cin>>a[i];
    }
    ll memo[N+1];
    memo[0]=0;memo[1]=abs(a[1]-a[0]);
    FOR(i,2,N){
        memo[i]=min(memo[i-2]+abs(a[i]-a[i-2]),memo[i-1]+abs(a[i]-a[i-1]));
    }
    
    
    cout<<memo[N-1]<<endl;
    
    
}


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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

const long mod = 1000000007;

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   long modpow(long x, long n) {
      if( n == 0 ) return 1;
      long t = modpow(x, n / 2);
      long y = (t * t) % mod;
      return n % 2 == 1 ? (y * x) % mod : y;
   }
   long factMemo[112345];
   long factMemo2[112345];
   long nCr(long n, long r) {
      if( r < 0 ) return 0;
      if( n < 0 ) return 0;
      if( n < r ) return 0;
      if( n == 0 or r == 0 ) return 1;
      return ((factMemo[n] * factMemo2[r]) % mod * factMemo2[n-r]) % mod;
   }
   void initFactMemo() {
      factMemo[0] = factMemo2[0] = 1;
      for(long i = 1; i < 112345; ++i) {
         factMemo[i] = (factMemo[i-1] * i) % mod;
         factMemo2[i] = modpow(factMemo[i], mod - 2);
      }
   }
   void solve() {
      initFactMemo();
      long n; scan(n);
      n += 1;
      LI xs(n); for(long &x : xs) scan(x);
      LI ys(n, -1);
      long d = -1;
      for(long i = 0; i < n; ++i) {
         if( ys[xs[i]] != -1 ) {
            d = i - ys[xs[i]] - 1;
         }
         ys[xs[i]] = i;
      }
      // dumpl(d);
      for(long k = 1; k <= n; ++k) {
         long t0 = nCr(n-2, k);
         long t1 = (2 * nCr(n-2, k-1) + mod - nCr(n-2-d, k-1)) % mod;
         long t2 = nCr(n-2, k-2);
         long res = (t0 + t1 + t2) % mod;
         // dumplll(t0, t1, t2);
         printf("%ld\n", res);
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}



Measured memory_bytes: 4480
while 1:
    try:
        xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2=map(float, raw_input().split())
        print "NO" if xa2<xb1 or xb2<xa1 or ya2<yb1 or yb2<ya1 else "YES"
    except EOFError:
        break

Measured memory_bytes: 4204
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll a,ans=0;
    rep(i,1,n+1)
    {
        cin>>a;
        if(i%2 and a%2)
            ans++;
    }
    cout<<ans<<"\n";
}


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

using namespace std;

bool mark[200];

int main() {
	int n, k, cnt = 0;
	cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		int d, tr;
		cin >> d;
		for (int j = 0; j < d; ++j) {
			cin >> tr;
			mark[tr] = 1;
		}
	}
	for (int i = 1; i <= n; ++i)
		if (!mark[i])
			++cnt;
	cout << cnt << '\n';
}


Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	int n, k, i, j;
	scanf("%d%d", &n, &k);
	vl a(n);
	vl sum(n + 1);
	for (i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
		a[i] -= k;
		sum[i + 1] = sum[i] + a[i];
	}
	int b = sqrt(n);
	vll sum2;
	i = 0;
	while (i <= n) {
		sum2.push_back(vl());
		for (j = 0; j < b; j++) {
			sum2[sum2.size() - 1].push_back(sum[i]);
			i++;
			if (i > n)
				break;
		}
	}

	for (i = 0; i < sum2.size(); i++) {
		sort(sum2[i].begin(), sum2[i].end());
	}
	ll cnt = 0;
	for (i = 0; i < n; i++) {
		for (j = i + 1; (j <= n) && (j%b != 0); j++) {
			if (sum[j] - sum[i] >= 0) {
				cnt++;
			}
		}
		for (j = i / b + 1; j < sum2.size(); j++) {
			cnt += (sum2[j].end() - lower_bound(sum2[j].begin(), sum2[j].end(), sum[i]));
		}
	}
	printf("%lld\n", cnt);
}

Measured memory_bytes: 5248
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
#define p 998244353
using namespace std;
inline ll read(){
    ll x = 0; char zf = 1; char ch = getchar();
    while (ch != '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,sum;
char c[400010];
struct q{
	char x,y;
}q[400010];
int golef(int x){
	for(rt i=1;i<=m;i++){
		if(c[x]==q[i].x){
			if(q[i].y=='L')x--;else x++;
			if(x<=0)return 1;
		}
	}
	return 0;
}
int gorig(int x){
	for(rt i=1;i<=m;i++){
		if(c[x]==q[i].x){
			if(q[i].y=='L')x--;else x++;
			if(x>n)return 1;
		}
	}
	return 0;
}
int main(){
	n=r;m=r;
	scanf("%s",c+1);
	for(rt i=1;i<=m;i++){
		char x,y;
		cin>>x>>y;
		q[i]={x,y};
	}
	int lef,rig;
	if(!golef(1))lef=1;
	else {
		int L=1,R=n;
		while(L<=R){
			const int mid=L+R>>1;
			if(golef(mid))lef=mid+1,L=mid+1;
			else R=mid-1;
		}
	}
	if(!gorig(n))rig=n;
	else {
		int L=1,R=n;
		while(L<=R){
			const int mid=L+R>>1;
			if(gorig(mid))rig=mid-1,R=mid-1;
			else L=mid+1;
		} 
	}
	cout<<max(0,rig-lef+1);
    return 0;
}








Measured memory_bytes: 896
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long n = in.nextLong();
            long a = in.nextLong();
            long b = in.nextLong();

            if (a > b) {
                out.println(0);
            } else {
                if (n >= 2) {
                    out.println(a + (n - 1) * b - a * (n - 1) - b + 1);
                } else {
                    if (a == b) {
                        out.println(1);
                    } else {
                        out.println(0);
                    }
                }
            }
        }

    }

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar;
        private int snumChars;

        public InputReader(InputStream st) {
            this.stream = st;
        }

        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



Measured memory_bytes: 22868
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long double ld;
int main() {fio ;// remove during scanf
	ld n, m, k;
	int N, M, K;
	cin >> N >> M >> K;
	n = N; m = M; k = K;
	ld d = k;
	ld mul = m - 1;
	ld tot = 0;
	tot += N - K;
	tot += N - K;
	ld m2 = tot;
	if(K == 0) {
		m2 /= 2;
	}
	cout << fixed << setprecision(10) << (mul * m2)/(n * n);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, j, n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;
 
typedef long long i64;
typedef pair<int, int> pi;
 
template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);}

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

  int x;
  cin >> x;
  if(x == 7 || x == 5 || x == 3) cout << "YES\n";
  else cout << "NO\n";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main(){
	long long int n, k, i, j, p, q, ans=0;
	scanf("%lld%lld", &n, &k);
	// k=0
	if(k==0){
		printf("%lld\n", n*n);
	}
	else{
		// k>0
		// a<b
		for(i=n; i>k; i--){
			ans+=i-k;
		}
		// printf("%lld\n", ans);
		// a>b
		for(i=n-k; i>k; i--){
			p=n%i;
			q=n/i;
			if(p>=k && q==0){
				ans+=p-k+1;
			}
			else if(p>=k){
				ans+=(i-k)*(q-1)+p-k+1;
			}
			else{
				ans+=(i-k)*(q-1);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 128
n = int(input())
a = list(map(int,input().split()))
b = []
total = sum(a)
for i in range(1, n, 2):
    total -= a[i] * 2
b.append(total)
prev = total
for i in a:
    prev = 2 * i - prev
    b.append(prev)

result = ""
for i in range(n):
    if i != 0: result += " "
    result += str(b[i])
print(result)


Measured memory_bytes: 14152
#include <iostream>
using namespace std;
int main(void){
    long long N,a,b,c,A,B,C,D,E,F,i;
    cin>>N;
    for(i=0;i<N;i++){
        cin>>a>>b>>c;
        if(i==0){
            A=a;B=b;C=c;
        }else{
            D=max(B+a,C+a);
            E=max(A+b,C+b);
            F=max(A+c,B+c);
            A=D;B=E;C=F;
        }
    }
    A=max(A,max(B,C));
    cout<<A<<endl;
}


Measured memory_bytes: 384
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

using pll = pair < ll, ll > ;

int main() {
	int n, m;
	cin >> n >> m;
	vector<pll> v;

	rep(i, n) {
		int a; cin >> a;
		v.push_back({ a, 1 });
	}
	rep(i, m) {
		ll x, y;
		cin >> x >> y;
		v.push_back({ y, x });
	}

	sort(v.begin(), v.end(), greater<pll>());

	ll num = 0;
	ll res = 0;
	for (auto p : v) {
		if (num + p.second <= n) {
			res += p.first * p.second;
			num += p.second;
		}
		else {
			res += p.first * (n - num);
			num = n;
			break;
		}
	}
	cout << res << endl;
	return 0;
}


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

#define rep(X,N) for(int X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define MODN 1000000007
#define MODN2 998244353
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;

int main(){

    int n;
    cin >> n;

    ll ans = 1;
    long double k = 1.0;

    vector<ll> v(n);

    rep(i, n){
        cin >> v[i];
    }

    sort(ALL(v));

    rep(i, n){
        k *= v[i];

        if(k > 1000000000000000000){
            ans = -1;
            break;
        }

        if(v[i] == 0){
            ans = 0;
            break;
        }

        ans *= v[i];
    }

    cerr << k << endl;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3996
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/05/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = unsigned long long;

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

  int n; cin>>n;
  vector<ll> A(n); for(auto& a:A) cin>>a;
  vector<ll> aca(n);
  aca[0] = A[0];
  for (int i = 1; i < n; i++)
    aca[i] = aca[i-1]+A[i];
  auto sum = [&](int l, int r) {
    auto res = aca[r];
    if (l>0)
      res -= aca[l-1];
    return res;
  };

  vector<vector<ll>> dp(n, vector<ll>(n));
  for (int d = 2; d <= n; d++) {
    for (int l = 0; l <= n-d; l++) {
      auto r = l+d-1;
      dp[l][r] = numeric_limits<ll>::max();
      for (int k = l+1; k <= r; k++) {
        dp[l][r] = min(dp[l][r], dp[l][k-1]+dp[k][r]);
      }
      dp[l][r] += sum(l,r);
    }
  }
  cout << dp[0][n-1] << endl;

  return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n;
vector<P> es;

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

  cin>>n;

  vector<vector<ll> > vs;
  if(n%2==1){
    rep(i,((n+1)/2)-1){
      vector<ll> tmp;
      tmp.push_back(i);
      tmp.push_back(n-2-i);
      vs.push_back(tmp);
    }
    vector<ll> tmp;
    tmp.push_back(n-1);
    vs.push_back(tmp);
  }else{
    rep(i,(n+1)/2){
      vector<ll> tmp;
      tmp.push_back(i);
      tmp.push_back(n-1-i);
      vs.push_back(tmp);
    }
  }

  rep(i,vs.size()){
    rep(j,i){
      rep(k,vs[i].size())rep(l,vs[j].size()){
        es.push_back(P(vs[i][k],vs[j][l]));
      }
    }
  }

  cout<<es.size()<<endl;
  rep(i,es.size())cout<<es[i].fi+1<<" "<<es[i].se+1<<endl;

  return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string>
#include <iostream>

//using namespace std;


int main(){
    int n=0;

    while(scanf("%d",&n)!=EOF){
        int temp=0;
        
        for(int a=0; a<10; a++){
            for(int b=0; b<10; b++){
                for(int c=0; c<10; c++){
                    for(int d=0; d<10; d++){
                        if(a+b+c+d==n){
                            temp++;
                        }
                    }
                }
            }
        }
        printf("%d\n",temp);
    }
}

Measured memory_bytes: 1188