akhauriyash/Code-Regression huggingface dataset:
// ABC077_A
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <tuple>  // std::tuple std::get
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define REPN(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0LL)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
#define zero_pad(num) setfill('0') << std::right << setw(num)
#define space_pad(num) setfill(' ') << std::right << setw(num)

typedef long long ll;

const ll MOD7 = 1000000007;  // 1 000 000 007
const ll MOD9 = 1000000009;  // 1 000 000 009

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

    // input
    string N, M;
    cin >> N >> M;
    // vector<ll> vec(N);
    // REP(i, N) cin >> vec[i];
    
    // calculation
    reverse(M.begin(), M.end());
    if (N == M) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
    
    
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    string u;
    rep(i, n)
    {
        u += s[i];
        u += t[i];
    }
    cout << u << endl;
    return 0;
}

Measured memory_bytes: 3624
s = int(input())
i = "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"
i1 = list(map(int, i.split(", ")))
print(i1[s-1])

Measured memory_bytes: 38384
#include <iostream>
#include <cstring>

int main(void) {
	char str[201];
	std::cin >> str;

	int beg = strlen(str) - 1;
	if(beg % 2) beg --;

	int i;
	for(i=beg; i>=0; i-=2){
		bool f = true;
		for(int j=0; j<i/2; j++){
			if(str[j] != str[i/2+j]){
				f = false;
				break;
			}
		}
		if(f) break;
	}

	std::cout << i << '\n';

	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# 0かつ9が1回は登場する数列の種類
# 0−9からなる数列集合から 1を含まない集合 U 9を含まない集合 を引く
# つまり答えは
# 10^n - 2*(9^n) + 8^n
N = a_int()
print((pow(10, N, MOD) - 2 * pow(9, N, MOD) + pow(8, N, MOD)) % MOD)


Measured memory_bytes: 68788
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_N = 50;

int N, A;
int Y[MAX_N + 1];
long long dp[MAX_N + 1][MAX_N * 50];

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

    cin >> N >> A;

    int sum = 0;

    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        Y[i] = x - A;
        if (Y[i] > 0) {
            sum += Y[i];
        }
    }

    dp[0][N * (A - 1)] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= sum + N * (A - 1); j++) {
            if (j >= Y[i + 1] && j <= sum + N * (A - 1) + Y[i + 1]) {
                dp[i + 1][j] = dp[i][j - Y[i + 1]] + dp[i][j];
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }

    cout << dp[N][N * (A - 1)] - 1 << "\n";

    return 0;
}

Measured memory_bytes: 4576
#include <bits/stdc++.h>
using namespace std;
void dfs1(vector<vector<int>> &E, vector<int> &p, vector<set<int>> &c, vector<int> &d, int v = 0){
  for (int w : E[v]){
    if (d[w] == -1){
      p[w] = v;
      c[v].insert(w);
      d[w] = d[v] + 1;
      dfs1(E, p, c, d, w);
    }
  }
}
int dfs2(vector<set<int>> &c, vector<int> &imos, int v = 0){
  for (int w : c[v]){
    imos[v] += dfs2(c, imos, w);
  }
  return imos[v];
}
int dfs3(vector<vector<int>> &c2, vector<int> &total, vector<int> &mx, int v = 0){
  mx[v] = total[v];
  for (int w : c2[v]){
    mx[v] = max(mx[v], total[v] + dfs3(c2, total, mx, w));
  }
  return mx[v];
}
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    E[s].push_back(t);
    E[t].push_back(s);
  }
  vector<int> p(N, -1);
  vector<set<int>> c(N);
  vector<int> d(N, -1);
  d[0] = 0;
  dfs1(E, p, c, d);
  vector<int> imos(N, 0);
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (!c[i].count(j) && !c[j].count(i) && d[j] > d[i]){
        imos[j]++;
        imos[i]--;
      }
    }
  }
  dfs2(c, imos);
  int ccnt = -1;
  vector<int> tec(N, -1);
  deque<int> dq;
  dq.push_back(0);
  while (!dq.empty()){
    int v = dq.front();
    dq.pop_front();
    if (imos[v] == 0){
      ccnt++;
    }
    tec[v] = ccnt;
    for (int w : c[v]){
      if (imos[w] != 0){
        dq.push_front(w);
      } else {
        dq.push_back(w);
      }
    }
  }
  ccnt++;
  vector<int> total(ccnt, 0);
  for (int i = 0; i < N; i++){
    total[tec[i]] += a[i];
  }
  vector<set<int>> E2(ccnt);
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (tec[i] != tec[j]){
        E2[tec[i]].insert(tec[j]);
      }
    }
  }
  vector<int> p2(ccnt, -1);
  vector<bool> used(ccnt, false);
  used[0] = true;
  vector<vector<int>> c2(ccnt);
  queue<int> Q2;
  Q2.push(0);
  while (!Q2.empty()){
    int v = Q2.front();
    Q2.pop();
    for (int w : E2[v]){
      if (!used[w]){
        used[w] = true;
        p2[w] = v;
        c2[v].push_back(w);
        Q2.push(w);
      }
    }
  }
  vector<int> mx(ccnt, 0);
  dfs3(c2, total, mx);
  int ans = 0;
  for (int i = 0; i < ccnt; i++){
    ans = max(ans, mx[i]);
    vector<int> ch;
    for (int j : c2[i]){
      ch.push_back(mx[j]);
    }
    sort(ch.begin(), ch.end());
    reverse(ch.begin(), ch.end());
    if (ch.size() >= 2){
      ans = max(ans, ch[0] + ch[1] + total[i]);
    }
  }
  cout << ans << endl;
}


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

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;

const int M = 610;
const int N = M * M;

int n, d1, d2;
vector<int> g[N];
bool used[N];
int c1[N], c2[N];

void read() {
  cin >> n >> d1 >> d2;
}

int enc(int i, int j) {
  return i + 2 * n * j;
}

void dfs(int x, int * c, int color) {
  if (used[x]) {
    assert(c[x] == color);
    return;
  }
  c[x] = color;
  used[x] = true;
  for (int y : g[x])
    dfs(y, c, color ^ 1);
}

void color(int d, int *c) {
  vector<int> dx, dy;
  for (int i = 0; i * i <= d; ++i) {
    for (int j = 0; j * j <= d; ++j) {
      if (i * i + j * j == d) {
        dx.push_back(i);
        dx.push_back(i);
        dx.push_back(-i);
        dx.push_back(-i);

        dy.push_back(j);
        dy.push_back(-j);
        dy.push_back(j);
        dy.push_back(-j);
      }
    }
  }

  for (int i = 0; i < 2 * n; ++i)
    for (int j = 0; j < 2 * n; ++j) {
      int cur = enc(i, j);
      g[cur].clear();
      for (int k = 0; k < (int) dx.size(); ++k) {
        int ti = i + dx[k];
        int tj = j + dy[k];
        if (0 <= min(ti, tj) && max(ti, tj) < 2 * n) {
          g[cur].push_back(enc(ti, tj));
        }
      }
    }

  fill(used, used + 4 * n * n, false);
  for (int i = 0; i < 4 * n * n; ++i)
    if (!used[i])
      dfs(i, c, 0);
}

int cnt[2][2];

void kill() {
  color(d1, c1);
  color(d2, c2);

  int m = 4 * n * n;
  for (int i = 0; i < m; ++i)
    cnt[c1[i]][c2[i]]++;
  for (int x = 0; x < 2; ++x)
    for (int y = 0; y < 2; ++y)
      if (cnt[x][y] >= m / 4) {
        int cur = 0;
        for (int i = 0; i < m && cur < n * n; ++i)
          if (c1[i] == x && c2[i] == y) {
            cout << (i % (2 * n)) << " " << (i / (2 * n)) << "\n";
            ++cur;
          }
        assert(cur == n * n);
        return;
      }
}

int main() {
#ifdef LOCAL
  assert(freopen("d.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();
}



Measured memory_bytes: 77568
#include <iostream>
#include <vector>
#include <numeric>
#include <map>

#define INFL (1LL << 62)

using namespace std;

typedef long long ll;

vector<ll> parent, urank;

ll root(ll x) { return (parent.at(x) == x ? x : parent.at(x) = root(parent.at(x))); }

bool in_same(ll x, ll y) { return root(x) == root(y); }
void unite(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x != y) {
        if (urank.at(x) < urank.at(y)) parent.at(x) = y;
        else {
            parent.at(y) = x;
            if (urank.at(x) == urank.at(y)) ++(urank.at(x));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    ll n, k, ans = -INFL;
    cin >> n >> k;
    vector<ll> p(n + 1), c(n + 1), sum(n + 1);
    parent.resize(n + 1);
    urank.resize(n + 1);
    iota(parent.begin(), parent.end(), 0);
    for (ll i = 1; i <= n; ++i) cin >> p.at(i), unite(i, p.at(i));
    for (ll i = 1; i <= n; ++i) cin >> c.at(i);
    map<ll, ll> m, loop;
    for (ll i = 1; i <= n; ++i) ++m[root(i)];
    for (auto i = m.begin(); i != m.end(); ++i) {
        ll pos = i -> first, init = pos, csum = 0;
        // cout << i -> first << " " << i -> second;
        while (true) {
            pos = p.at(pos);
            sum.at(pos) = (csum += c.at(pos));
            // cout << " " << pos;
            if (pos == init) {
                loop[init] = sum.at(pos);
                break;
            }
        }
        // cout << " " << loop[i -> first] << endl;
    }
    // for (ll start = 1; start <= n; ++start) cout << sum.at(start) << endl;
    for (ll start = 1; start <= n; ++start) {
        ll cmax = -INFL, lsum = loop.at(root(start)), llen = m.at(root(start)), pos = start, moves = 0, csum = 0;
        // cout << start << " " << lsum << " " << llen << endl;
        while (true) {
            pos = p.at(pos);
            ++moves;
            csum += c.at(pos);
            if (moves > k) break;
            ll cnt = csum;
            // cout << "\t" << pos << " " << cnt << endl;
            if (lsum > 0) cnt += lsum * ((k - moves) / llen);
            else if (pos == start) cnt += lsum;
            if (cmax < cnt) cmax = cnt;
            if (pos == start) break;
        }
        if (ans < cmax) ans = cmax;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p){os<<"("<<p.first<<","<< p.second<<")";return os;}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v){os<<"{";REP(i,(int)v.size()){if(i)os<<",";os<<v[i];}os<<"}";return os;}
template <typename T, size_t S> void printArray(const T (&array)[S]){for(auto val : array)std::cout << val << ", ";std::cout << "\n";}
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
const double PI=acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;
//const int dx[4] = {1, 0, -1, 0};
//const int dy[4] = {0, 1, 0, -1};
//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve(){
    ll n, h; cin >> n >> h;
    vector<ll> a, b;
    REP(i, n){
        ll ia, ib;
        cin >> ia >> ib;
        a.pb(ia); b.pb(ib);
    }
    sort(RALL(a));
    sort(RALL(b));
    ll mxa = a[0];
    ll res = 0;
    REP(i, n){
        if(h > 0){
            if(mxa < b[i]){
                h -= b[i];
                res++;
            }
        }
    }
    if(h > 0){
        res += h/mxa;
        if(h%mxa > 0) res++;
    }
    cout << res << endl;
}

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

Measured memory_bytes: 2036
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    int current;
    vector<int> v;
    int num;
    int K;
    cin >> K  >> num;
    for(int i=0;i<num;i++){
        cin >> current;
        v.push_back(current);
    }
    sort(v.begin(),v.end());
    int ans = K - v[num-1] + v[0];
    for(int i=1;i<num;i++){
        ans = max(ans,v[i]-v[i-1]);
    }
    cout << K-ans << endl;
    return 0;

}

Measured memory_bytes: 2032
X = int(input())
x = X
X *= 2
work = [True for i in range(X)]
for i in range(2, int(X**0.5)+1):
    if not work[i]:
        continue
    for j in range(i*2, len(work), i):
        work[j] = False
prime = []
for i in range(2, len(work)):
    if work[i] and i>=x:
        result = i
        break
print(result)

Measured memory_bytes: 4632
#include<iostream>
#include<string>
using namespace std;
int s[1000][4];
int main(){
	int n,m;
	while(true){
	cin>>n>>m;
	if(n==0&&m==0)
		break;
	int r;
	cin>>r;
	for(int i=0;i<r;i++)
		for(int j=0;j<4;j++)
		    cin>>s[i][j];
	int q;
	cin>>q;
	int bef,aft,m;
	for(int u=0;u<q;u++){
		cin>>bef>>aft>>m;
		int ans=0;
		int in=0;
		for(int i=0;i<r;i++){
			if(s[i][0]<bef&&s[i][2]==m){
				if(s[i][3]==1)
					in++;
				if(s[i][3]==0)
					in--;
			}
		}
		for(int time=bef;time<aft;time++){
			for(int i=0;i<r;i++){
				if(s[i][0]==time&&s[i][2]==m){
					if(s[i][3]==1)
						in++;
					if(s[i][3]==0)
						in--;
				}
			}
			if(in>0)
				ans++;
		}
		cout<<ans<<endl;
	}
	}
	return 0;
}

Measured memory_bytes: 1172
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
    }

    let mut l: Vec<usize> = vec![0;2];
    l[0] = 2;
    l[1] = 1;
    for i in 2..n+1 {
        l.push(l[i-1]+l[i-2]);
    }
    debug!(l);
    println!("{}", l[n]);
}


Measured memory_bytes: 2184
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    long long int Y;
    cin >> N >> Y;
    bool judge = false;
    for(int yen10000 = 0; yen10000 <= N; yen10000++) {
        for(int yen5000 = 0; yen5000 <= N - yen10000; yen5000++) {
            int yen1000 = N - yen10000 - yen5000;
            int sum = 10000*yen10000 + 5000*yen5000 + 1000*yen1000;
            if(sum == Y) {
                judge = true;
                cout << yen10000 << " " << yen5000 << " " << yen1000 << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int r, g;
    cin >> r >> g;
    cout << 2 * g - r << endl;
    return 0;
}

Measured memory_bytes: 256
/* Bismillahirrahmanirrahim
   Semoga Dapet AC ya Allah
   Amin.................. :)
*/
#include<bits/stdc++.h>
#define forA for(int i=0; i<a; i++)
#define ll long long
#define F first
#define S second
using namespace std;

int main(){
	string str;
	int max=0, temp=0;
	cin >> str;
	int a=str.size();
	forA{
		if((str[i]=='A')||(str[i]=='T')||(str[i]=='C')||(str[i]=='G')){
			temp++;
		}
		else temp=0;
		if(temp>max) max=temp;
	}
	cout << max;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int

using namespace std;
lli recursion(string s)
{
    //cout<<s<<endl;
    if(s.length()==0)
    {
        return 0;
    }
    lli len=s.length(),i,j,sum=atoll(s.c_str());
    for(i=1;i<len;i++)
    {
        string c;
        c=s.substr(0,i);
        //cout<<c<<endl;
        sum=sum+pow(2,len-i-1)*(atoll(c.c_str()))+(recursion(s.substr(i,len-i)));

    }

    return sum;
}
int main()
{

    string s;
    cin>>s;
    lli ans=recursion(s);
    cout<<ans<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()

a = [0] * (len(S)+1)
for i in range(len(S)):
    if S[i] == '<':
        a[i+1] = a[i] + 1
#print(a)

for j in range(len(S) - 1, -1, -1):
    if S[j] == '>':
        a[j] = max(a[j], a[j + 1] +1)
#print(a)
print(sum(a))


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

int main()
{
  ll n;
  ll ans = 0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    ll nums = n / i;
    ans = ans + nums * (i + nums * i) / 2;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define ll long long int
#define p pair<ll,ll>
#define pp pair<pair<ll,ll>,ll>
#define fi first
#define se second
#define opti ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll N = 1e6+6;
ll t,i,j,k,n,m,q;
int main()
{
    opti
    
        cin>>n;
        ll a[n+1];
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        ll maxi = 0;
        ll ans=0;
        for(ll i=0;i<n;i++){
            if(a[i] >= maxi){
                ans++;
                maxi = a[i];
            }
        }
        cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.immutable._
import scala.io.StdIn.readLine

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}

object Main {
  val m = (1 << 9) - 1

  def solve(sc: => Scanner): Unit = {
    val A, B, C, D = sc.nextInt
    println(if (math.abs(A - C) <= D || (math.abs(A - B) <= D && math.abs(B - C) <= D)) ("Yes") else ("No"))
  }

  def recursive(now: Int, A: Array[List[Int]]): Int = {
    if (A(now).size == 0) (now) else {
      val next = A(now).head
      A(now) = A(now).filter(_ != next)
      A(next) = A(next).filter(_ != now)
      recursive(next, A)
    }
  }

  def check(A: Array[List[Int]]): Boolean = {
    A.map(_.size == 0).fold(true)((a, b) => a & b)
  }

  def shift(n: Long): Long = {
    if (n == 0) (0) else if (n == 1) (1) else (shift(n - 1) << 1)
  }

  def unShift(n: Long): Long = {
    if (n == 0) (0) else (unShift(n >> 1) + 1)
  }

  def calc(v: Long): Long = (v + 1) * v / 2

  def gcd(i: Long, j: Long): Long = {
    if (i < j) (gcd(j, i)) else (if (j == 0) (i) else (gcd(j, i % j)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

object Util {
  def getPermutation(begin: Long = 0): Stream[Long] =
    Stream.cons(begin, getPermutation(begin + 1))

  def getPrimeList(): Stream[Long] =
    getPrimeListRecursive(getPermutation(begin = 2))

  private def getPrimeListRecursive(A: Stream[Long]): Stream[Long] =
    Stream.cons(A.head, getPrimeListRecursive(A.tail.filter(_ % A.head != 0)))

  def fib(a: Long = 0, b: Long = 1, mod: Long = Long.MaxValue): Stream[Long] = a #:: fib(b % mod, (a + b) % mod, mod)
}

Measured memory_bytes: 25540
#include <iostream>

int main()
{
	int a, b;
	std::cin >> a >> b;
		if (a*b % 2 == 0) {
			std::cout << "Even";
		}
		else if (a*b % 2 == 1) {
			std::cout << "Odd";
		}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace Test01
{
    class Program
    {
        static void Main(string[] args)
        {
            //入力1(N)
            int N = int.Parse(Console.ReadLine());
            //入力2(a)
            int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            int cnt = 0;  //負数の数          
            int min = Math.Abs(a[0]);  //絶対値の最小値
            long sum = 0;  //合計値

            for(int i = 0; i < N; i++)
            {
                if (a[i] < 0) cnt++;
                min = Math.Min(min, Math.Abs(a[i]));
                sum += Math.Abs(a[i]);
            }

            if (cnt % 2 == 1) sum -= 2 * min;

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 28252
from collections import defaultdict
from math import factorial

N = int(input())

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

d = defaultdict(int)
for _ in range(N):
    sin = list(input())
    sin.sort()
    d["".join(sin)] += 1

ans = 0
for i in d.values():
    if i >= 2:
          ans += combinations_count(i, 2)

print(ans)

Measured memory_bytes: 18188
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int MOD=1000000007;
const int nmax=3123;

int d,a,b,i2,kmax,pos;
ll dp[102],res,tmp[102],tmp2;
char k[10002];

int main()
{
    scanf("%s",&k);
    for(; k[kmax]!=0; ++kmax)
    {
        if(k[kmax]!='0')
            a+=k[kmax]-'0';
    }
    scanf("%d",&d);
    pos=kmax-1;
    dp[0]=1;
    a%=d;
    if(a==0)
        ++res;
    while(pos>=0)
    {
        if(k[pos]!='0')
        {
            b=k[pos]-'0';
            a-=b;
            while(a<0)
                a+=d;
            tmp2=0;
            i2=(d-a)%d;
            for(int i=0; i<b; ++i)
            {
                tmp2+=dp[i2];
                --i2;
                if(i2<0)
                    i2+=d;
            }
            res=(res+tmp2)%MOD;
        }
        tmp[0]=0;
        i2=d-1;
        for(int i=0; i<9; ++i)
        {
            tmp[0]+=dp[i2];
            --i2;
            if(i2<0)
                i2+=d;
        }
        for(int i=1; i<d; ++i)
        {
            ++i2;
            i2%=d;
            tmp[i]=tmp[i-1]+dp[i-1]-dp[i2];
        }
        for(int i=0; i<d; ++i)
        {
            dp[i]=(dp[i]+tmp[i])%MOD;
        }
        --pos;
    }
    --res;
    if(res<0)
        res+=MOD;
    printf("%lld",res);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000000000
using namespace std;
typedef long long ll;

int main(){
  int n, m; cin >> n >> m;
  cout << (1900*m+100*(n-m))*pow(2, m) << endl;
  return 0;
}

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

int a[30];
int n;

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	int cnt=0;
	for(int i=1;i<n-1;i++){
		vector <int> v;
		v.push_back(a[i-1]); v.push_back(a[i+1]); v.push_back(a[i]);
		sort(v.begin(),v.end());
		if(v[1]==a[i]) cnt++;
	}
	cout<<cnt;
	return 0;
}

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

B = False
if all(A):
    # print("not contain")
    M = 0
    for i in range(N):
        if A[i] < 0:
            A[i] *= -1
            M += 1
    # print(M)
    if M%2 == 0:
        B = True
    else:
        B = False

else:
    for i in range(N):
        if A[i] < 0:
            A[i] *= -1
    B = True

if B:
    print(sum(A))
else:
    print(str(sum(A)-2*min(A)))

Measured memory_bytes: 14412
#include <bits/stdc++.h>
using namespace std;
int n, cnt;
char s[500020];
int p[500020];
int f[500020];
int g[500020];
void gao(int *f) {
	int u = 0;
	for (int i = 2; i <= n; i++) {
		while (u > 0 && s[u + 1] != s[i]) {
			u = p[u];
		}
		if (s[u + 1] == s[i]) {
			u++;
		}
		p[i] = u;
	}
	for (int i = 1; i <= n; i++) {
		if (p[i] == 0 || i % (i - p[i]) > 0) {
			f[i] = 1;
		}
	}
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	gao(f);
	if (f[n]) {
		printf("1\n1\n");
		return 0;
	}
	reverse(s + 1, s + 1 + n);
	gao(g);
	for (int i = 1; i <= n; i++) {
		if (f[i] && g[n - i]) {
			cnt++;
		}
	}
	if (cnt == 0) {
		printf("%d\n1\n", n);
	} else {
		printf("2\n%d\n", cnt);
	}
	return 0;
}

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

using namespace std;


int main()
{

	int a, b, c, d, e;
	int k;
	cin >> a; cin >> b; cin >> c; cin >> d; cin >> e;
	cin >> k;

	if (e - a > k) cout << ":(" << endl;
	else cout << "Yay!" << endl;

    return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


int main(){
  
  string s,t;
  cin >> s >> t;
  vector<vector<ll>> dp(3030,vector<ll>(3030,1));
  rep(i,s.size()){
    rep(j,t.size()){
      if(s[i] == t[j])dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
      dp[i+1][j+1] = max({dp[i][j+1],dp[i+1][j+1],dp[i+1][j]});
    }
  }
  string res = "";
  ll size = dp[s.size()][t.size()],last = t.size();
  for(int i = s.size();i > 0;i--)for(int j = last;j > 0;j--){
    if(dp[i][j] == size){
      if(s[i-1] != t[j-1])continue;
      res += s[i-1];
      size--;
      last = j-1;
      break;
    }
  }
  reverse(ALL(res));
  cout << res << endl;





  

  return 0;
}

Measured memory_bytes: 72192
import sys

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

p1 = (b1 - a1) * t1
p2 = (b2 - a2) * t2

if p1 + p2 == 0:
    print('infinity')
    sys.exit()

if p1 + p2 < 0:
    p1 *= -1
    p2 *= -1

if p1 > 0:
    print(0)
    sys.exit()

ans = int((-1 * p1) / (p1+p2)) * 2 + 1

if (-1 * p1) % (p1+p2) == 0:
    ans -= 1

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

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


int main()
{
    vector<int> num(4,0);
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        if(s=="AC") num[0]++;
        else if(s=="WA") num[1]++;
        else if(s=="TLE") num[2]++;
        else num[3]++;
    }

    cout << "AC" << " " << "x" << " " << num[0] << endl;
    cout << "WA" << " " << "x" << " " << num[1] << endl;
    cout << "TLE" << " " << "x" << " " << num[2] << endl;
    cout << "RE" << " " << "x" << " " << num[3] << endl;




    return 0;
}

Measured memory_bytes: 3624
/*#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
*/

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define debug(x) cerr<<#x<<": "<<(x)<<'\n'
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const ll nax = 0;
string s;
unordered_map<char, int>cnt;

int main(){
	IOS
	cin >> s;
	for(int i=0;i<s.length();++i){
		if(s[i]=='A' && s[i+1]=='C'){
			cout << "Yes" << '\n';
			return 0;
		}
	}
	cout << "No" << '\n';
}


Measured memory_bytes: 3624
S = input()
T = input()
c = dict()
T2 = list(T)
f = False
start = 1
end = len(S) -1
for i in list(reversed(range(len(S)))):
    S = S[len(S)-1] + S[0:len(S)-1]
    if T == S:
        print("Yes")
        f = True
        break
if f == False:
    print("No")
    



Measured memory_bytes: 3060
// 2018, Sayutin Dmitry.

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int64_t n = input<int64_t>();
    int64_t p = input<int64_t>();

    int64_t r = 1;

    for (int64_t x = 2; x * x <= p; ++x) {
        int64_t cnt = 0;

        while (p % x == 0) {
            p /= x;
            ++cnt;
        }

        if (cnt >= n) {
            cnt = cnt / n;
            for (int64_t i = 0; i < cnt; ++i)
                r *= x;
        }
    }

    if (p > 1) {
        auto x = p;
        int64_t cnt = 1;

        if (cnt >= n) {
            cnt = cnt / n;
            for (int64_t i = 0; i < cnt; ++i)
                r *= x;
        }       
    }

    cout << r << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

vector<int> d;

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

    int N;
    cin >> N;

    d.resize(N, 0);
    rep (i, N) cin >> d[i];

    u64 ans = 0;
    rep (i, N)
    {
        for (int j = i + 1; j < N; ++j)
        {
            ans += d[i] * d[j];
        }
    }

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



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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> Pair;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N, M;
VL sum;
vector<bool> red;

int main() {
    cin >> N >> M;
    sum.assign(N, 1);
    red.assign(N, false);
    red[0] = true;
    REP(i, M) {
        CINT(x, y);
        x--;
        y--;
        if(red[x]) red[y] = true;
        if(sum[x] == 1) red[x] = false;
        sum[x]--;
        sum[y]++;
    }
    ll ans = 0;
    REP(i, N) if(red[i]) ans++;
    cout << ans << "\n";
}

Measured memory_bytes: 1024
import os
import heapq
import sys,threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]

def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

def main():
    n=int(input())
    arr=inar()
    count=1
    for i in range(n):
        if arr[i]==count:
            count+=1
    # print(count
    if count==1:
        print(-1)
    else:
        print(n-count+1)






BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()
    #threadin.Thread(target=main).start()


Measured memory_bytes: 109500
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

#define LL long long
#define MOD 1000000007

int n, a[100004], abit[100002][31] = {}, bcnt[31] = {};
bool flg = true;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = 0; j < 30; j++) {
			abit[i][j] = a[i] % 2;
			a[i] /= 2;
			if(abit[i][j])bcnt[j]++;
		}
	}
	for (int i = 0; i < 30; i++) {
		if (bcnt[i] % 2) {
			flg = false;
			break;
		}
	}
	cout << (flg ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _h cout<<"here"<<endl;
#define fill(a,v) memset(a,v,sizeof(a));
#define all(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(i,n) cout<<a[i]<<" \n"[i==n-1];// printf("%s\n"," " );
#define ff first
#define ss second
#define pu push_back
#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)
template<typename S, typename T> 
ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.ff<<", "<<p.ss<<')';return out;}
template<typename T>
ostream& operator<<(ostream& out,vector<T> const& v){
int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}
template<typename T>
void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}
template<typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}
const int inf = 1e9+10;
const ll INF = 1e18+10;
const int MOD = 1e9+7;
const int MAXN = 2e5+10;

void solve()
{
	int n;
	int a[MAXN];
	cin>>n;
	vector<int> v[MAXN];
	rep(i,n){
		cin>>a[i];
		v[a[i]-1].push_back(i);
	}
	int maxc = 0, maxi = 0,ans = 0;
	
	if(v[0].size()>0){
		maxc = 1;
		maxi = v[0][0];	
	}
	
	if(maxc == 0){
		maxi = n+1;
		ans = -1;
	}
	maxc = 0;
	rep(i,n){
		if(v[i].size()>0){
			// tr(lower_bound(all(v[i]), maxi)-v[i].begin(), v[i].size());
			if(lower_bound(all(v[i]), maxi)-v[i].begin() <v[i].size())
			{
				maxc++;
				maxi++;
				// tr(maxc,maxi);
			}
			else
				break;
		}
		else
			break;
	}
	if(ans==-1)
		cout<<ans<<endl;
	else
	{
		cout<<n-maxc<<endl;
	}
}
int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin>>t;
	while(t--){
		solve();
	}
	return 0;

}
    

Measured memory_bytes: 12032
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			char a[] = sc.next().toCharArray();
			char b[] = sc.next().toCharArray();
			if(a[0]==b[0]){
				System.out.println("H");
			}else{
				System.out.println("D");
			}
	}
}

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

int main(void)
{
    int N,K;
    cin >> N >> K;
    int l[N];
    for( int i = 0; i < N; i++){
        cin >> l[i];
    }
    sort(l, l+N);
    int sum = 0;
    for( int i = N-1; i > N-1-K; i--){
        sum += l[i];
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int search(int A[], int n, int key) {
	int i = 0;
	A[n] = key;
	while (A[i] != key)i++;
	return i != n;
}

int main() {
	int i, n, A[10000 + 1], q, key, sum = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)scanf("%d", &A[i]);
	scanf("%d", &q);
	for (i = 0; i < q; i++) {
		scanf("%d", &key);
		if (search(A, n, key))sum++;
	}
	printf("%d\n", sum);
	return 0;
}

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

int main()
{
  int N,M;
  vector<int> a(10001);
  cin >> N >> M;
  for(int i=0; i<M; i++)
  {
  cin >> a.at(i);
  }
  for(int i=0; i<M; i++)
  {
   	N-=a.at(i);
  }
  if(N>=0)
    cout << N << endl;
  else
    cout <<"-1"<< endl;
}


Measured memory_bytes: 3612
n = int(input())
a_list = list(map(int,input().split()))

def count(sign):
    
    count = 0
    a_sum = 0
    for a in a_list:
        a_sum +=a
        if a_sum*sign <= 0: 
            ope = sign - a_sum
            a_sum += ope
            count += abs(ope)
        sign *= -1
    return count
print(min(count(1),count(-1)))


Measured memory_bytes: 14332
//hitachi2020_b.cpp
//Sun Mar  8 20:53:14 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int rei[a];
	int cheapestrei = INTINF;
	for (int i=0;i<a;i++){
		cin >> rei[i];
		cheapestrei = min(cheapestrei,rei[i]);
	}
	int den[b];
	int cheapestden = INTINF;
	for (int i=0;i<b;i++){
		cin >> den[i];
		cheapestden = min(cheapestden,den[i]);
	}

	int ans = INTINF;
	for (int i=0;i<m;i++){
		int x,y,c;
		cin >> x >> y >> c;
		x--;y--;
		ans = min(ans,rei[x]+den[y]-c);
	}

	ans = min(ans,cheapestrei+cheapestden);


	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 1024
dg=10**7
import heapq
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append([1,b])
  edge[b].append([1,a])

s=0
d=[10**20]*n
used=[False]*n
used[s]=True
d[s]=0
edgelist=[]
fromv=[-1]*n

for e in edge[s]:
  e.append(s)
  heapq.heappush(edgelist,e)
while len(edgelist):
  minedge=heapq.heappop(edgelist)
  v=minedge[1]
  if used[v]:
    continue
  d[v]=minedge[0]
  used[v]=True
  fromv[v]=minedge[2]
  for e in edge[v]:
    if not used[e[1]]:
      heapq.heappush(edgelist,[e[0]+d[v],e[1],v])
      fromv[e[1]]=v
if any([x==-1 for x in fromv[1:]]):
  print('No')
else:
  print('Yes')
  for x in fromv[1:]:
    print(x+1)

Measured memory_bytes: 154132
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))


Measured memory_bytes: 87756
// I - Coins
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; cin>>N;

	double dp[N+1][N+1]; // i 枚までで、j 枚表の確率
	rp(j, 1, N+1) dp[0][j] = 0;
	dp[0][0] = 1;

	rp(i, 1, N+1){ // [1,N]
		double p; cin>>p;
		rp(j, 0, N+1){ // [0,N]
			dp[i][j] = dp[i-1][j] * (1-p); // i: back, ¬pi
			if(0 <= j-1) dp[i][j] += dp[i-1][j-1] * p; // i: front, pi
		}
	}

	double ans = 0;
	rp(j, (N+2-1)/2, N+1) ans += dp[N][j]; // dp[N][]: N 枚までで、j=ceil(N/2) 枚以上が表を集計
	cout<<setprecision(10)<< ans <<endl;
}


Measured memory_bytes: 70528
IDENTIFICATION DIVISION.
      PROGRAM-ID. 081A.
      DATA DIVISION.
      WORKING-STORAGE SECTION.
      01 INP.
      	03 S1 PIC 9(1).
      	03 S2 PIC 9(1).
      	03 S3 PIC 9(1).
      01 ANS PIC 9(1).
      
      PROCEDURE DIVISION.
      ACCEPT INP.
      COMPUTE ANS = S1 + S2 + S3
      DISPLAY ANS.
      STOP RUN.

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

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

  int k, x; cin >> k >> x;
  if(k * 500 >= x) cout << "Yes" << endl;
  else cout << "No" << endl;

}


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

ans = 10 ** 10
for i in range(N - K + 1):
    if x[i + K - 1] <= 0:
        tmp = -x[i]
    elif x[i] >= 0:
        tmp = x[i + K - 1]
    else:
        tmp = -x[i] * 2 + x[i + K - 1]
        tmp = min(tmp, -x[i] + 2 * x[i + K - 1])

    if tmp < ans:
        ans = tmp
print(ans)


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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  ll ans_0, ans_1, A, B, K;
  cin >> A >> B >> K;
  ans_0 = A;
  ans_1 = B;

  ans_0 = max(A - K, 0ll);
  if(A < K){
    K -= A;
    ans_1 = max(B - K, 0ll);
  }

  cout << ans_0 << " " << ans_1 << endl;

  return 0;
}


Measured memory_bytes: 256