akhauriyash/Code-Regression huggingface dataset:
import fractions
#A=int(input())
#A=list(map(int,(input().split())))
A,B=list(map(int,(input().split())))
C=fractions.gcd(A,B)
lis=[]
waru=2
while (C!=1 and waru<=C**0.5+10):
	
	if C%waru==0:
		lis.append(waru)
		while(C%waru==0):
			C/=waru
	waru+=1
if C!=1:lis.append(waru)
print(len(lis)+1)

Measured memory_bytes: 5048
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
  int n,i,a[100010];
  vector<int> l;
  vector<int>::iterator ite;
  cin >> n;
  for (i=0;i<n;i++) cin >> a[i];
  for (i=n-1;i>=0;i--){
    ite=lower_bound(l.begin(),l.end(),a[i]+1);
    if (ite==l.end()) l.push_back(a[i]);
    else *ite=a[i];
  }
  cout << l.size() << endl;
  return 0;
}

Measured memory_bytes: 1276
#include <stdio.h>

#define MAX 10000
#define NIL -1

typedef struct {
	int parent, left, right;
} Node;

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u,int d) {
  if(u == NIL) return;
  D[u] = d;
  setDepth(T[u].left, d+1);
  setDepth(T[u].right,d+1);
}

int setHeight(int u) {
  int h1 = 0, h2 = 0;
  if(T[u].left != NIL)
    h1 = setHeight(T[u].left)  + 1;
  if(T[u].right != NIL)
    h2 = setHeight(T[u].right) + 1;
  return H[u] = (h1 > h2 ? h1 : h2);
}

// 接点 u の兄弟を返す
int getSibling(int u) {
  if(T[u].parent == NIL) return NIL;
  if(T[T[u].parent].left != u && T[T[u].parent].left != NIL )
    return T[T[u].parent].left;
  if(T[T[u].parent].right != u && T[T[u].parent].right != NIL )
    return T[T[u].parent].right;
  return NIL;
}

void print(int u) {
  int deg = 0;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",getSibling(u));
  if(T[u].left  != NIL) deg++;
  if(T[u].right != NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);
  
  if(T[u].parent == NIL) {
    printf("root\n");
  } else if(T[u].left == NIL && T[u].right == NIL) {
    printf("leaf\n");
  } else {
    printf("internal node\n");
  }
}

int main(void) {
  int i, v, l, r, root = 0;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].parent = NIL;
  for(i=0;i<n;i++) {
    scanf("%d %d %d",&v,&l,&r);
    T[v].left  = l;
    T[v].right = r;
    if(l != NIL) T[l].parent = v;
    if(r != NIL) T[r].parent = v;
  }
  
  for(i=0; i<n; i++)
  if(T[i].parent == NIL) root = i;
  
  setDepth(root,0);
  setHeight(root);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}


Measured memory_bytes: 2104
c=list(list(map(int,input().split())) for _ in range(3))

if all(c[i][0]-c[0][0]==c[i][1]-c[0][1] and c[i][1]-c[0][1]==c[i][2]-c[0][2] for i in [1,2]):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


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


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().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, read().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, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().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
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, K = read_ints()
A = read_ints()
# N = K = 2 * 100000
# A = [0] * N

# 愚直に実装するとO(N**3)ぐらいO(N√N)以下じゃないと間に合わない
# 一回あたりの操作はO(N)(imos法)
# 操作回数はmin(K,logN)に気づくと通る

for _ in range(min(50, K)):
    imos = [0] * (N + 1)
    for i, d in enu(A):
        imos[max(i - d, 0)] += 1
        imos[min(i + d + 1, N)] -= 1
    A = list(accumulate(imos))[:-1]
print(*A)


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

# define fr first
# define sc second
# define pb push_back
//# define int long long
# define mk make_pair
# define sz(s) (int)s.size()
# define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5+10;
const int inf = 1e9+7;

int n, cnt = 0;
int a[2*N];
pair <int, int> t[4*N][2];
pair <int, int> b[N];
vector <int> g[2*N];
vector <pair <int, int> > ans;

void build(int v, int tl, int tr, int o) {
    if(tl == tr) {
        if(o == 0)
            t[v][o] = mk(a[tl*2-1], tl*2-1);
        else
            t[v][o] = mk(a[tl*2], tl*2);
        return;
    }
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm, o);
    build(v + v + 1, tm + 1, tr, o);
    t[v][o] = t[v + v][o];
    if(t[v][o].fr > t[v + v + 1][o].fr)
        t[v][o] = t[v + v + 1][o];
}

pair <int, int> get(int v, int tl, int tr, int l, int r, int o) {
    if(l > r) return mk(inf, 0);

    if(tl == l && r == tr)
        return t[v][o];

    int tm = (tl + tr) / 2;

    pair <int, int> nw = get(v + v, tl, tm, l, min(tm, r), o);
    pair <int, int> nw2 = get(v + v + 1, tm + 1, tr, max(tm + 1, l), r, o);

    if(nw.fr < nw2.fr) return nw;
    return nw2;
}

void A(int l, int r, int p) {
    if(l > r) return;
    int num = ++cnt;
    g[p].pb(num);
    if(l & 1) {
        int pos = get(1, 1, n, (l + 1) / 2, r / 2, 0).sc;
        int ps = get(1, 1, n, (pos + 1) / 2, r / 2, 1).sc;
        b[num] = mk(pos, ps);
        A(l, pos - 1, num);
        A(pos + 1, ps - 1, num);
        A(ps + 1, r, num);
    }
    else {
        int pos = get(1, 1, n, l / 2, r / 2, 1).sc;
        int ps = get(1, 1, n, pos / 2 + 1, r / 2 + 1, 0).sc;
        b[num] = mk(pos, ps);
        A(l, pos - 1, num);
        A(pos + 1, ps - 1, num);
        A(ps + 1, r, num);
    }
}

inline void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    n /= 2;
    build(1, 1, n, 0);
    build(1, 1, n, 1);

    A(1, 2*n, 0);

    set <pair <int, int> > st;
    st.insert(mk(-1, 0));

    while(!st.empty()) {
        int ok = st.begin()->sc;
        st.erase(st.begin());
        if(ok != 0)
            ans.pb(b[ok]);
        for(int j = 0; j < g[ok].size(); j++)
            st.insert(mk(a[b[g[ok][j]].fr], g[ok][j]));
    }

    for(int i = 0; i < sz(ans); i++)
        cout << a[ans[i].fr] << " " << a[ans[i].sc] << " ";
}


int test = 1;

int main() {
    while(test--) {
        solve();
    }
}


Measured memory_bytes: 30196
N = int(input())
a = list(map(int, input().split()))

ans = []

s = 0
for i in range(N):
    if i == 0:
        s += abs(a[0])
    else:
        s += abs(a[i]-a[i-1])
s += abs(a[-1])

for i in range(N):
    if i == 0:
        temp = s  - abs(a[i]) - abs(a[i+1]-a[i]) + abs(a[i+1])
    elif i < N-1:
        temp = s - abs(a[i]-a[i-1]) - abs(a[i+1]-a[i]) + abs(a[i+1]-a[i-1])
    else:
        temp = s - abs(a[i]) - abs(a[i]-a[i-1]) + abs(a[i-1])
    ans.append(temp)
for x in range(N):
    print(ans[x])

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

// うし木(一点更新区間取得) : 0-indexed
// min 更新 RMQ
// auto f = [](int a, int b) { return min(a, b); };
// SegmentTree<int, decltype(f)> seg(f, UNIT);
// seg.build(vi(n, UNIT));
template <typename T, typename F>
struct SegmentTree {
    // using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f, T ti) : f(f), ti(ti) {}

    void init(int n_) {
        n = 1;
        while (n < n_)
            n <<= 1;
        dat.assign(n << 1, ti);
    }

    void build(const vector<T> &v) {
        int n_ = v.size();
        init(n_);
        for (int i = 0; i < n_; i++)
            dat[n + i] = v[i];
        for (int i = n - 1; i; i--)
            dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
    }
    // k: index, x: value
    void set_val(int k, T x) {
        dat[k += n] = x;
        while (k >>= 1)
            dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
    // 探索範囲は半開区間 [a,b)
    T query(int a, int b) {
        T vl = ti, vr = ti;
        for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = f(vl, dat[l++]);
            if (r & 1) vr = f(dat[--r], vr);
        }
        T x = f(vl, vr);
        int cnt = 0;
        while (x > 0) {
            if (1 & x) cnt++;
            x >>= 1;
        }
        return cnt;
    }
};

int main() {
    int n, q;
    string s;
    cin >> n >> s >> q;
    auto f = [](int a, int b) { return a | b; };
    SegmentTree<int, decltype(f)> seg(f, 0);
    vector<int> v(n);
    rep(i, n) {
        v[i] = 1 << (s[i] - 'a');
    }
    seg.build(v);
    rep(i, q) {
        int cond;
        cin >> cond;
        if (cond == 1) {
            int idx;
            char c;
            cin >> idx >> c;
            idx--;
            seg.set_val(idx, 1 << (c - 'a'));
        } else {
            int l, r;
            cin >> l >> r;
            l--, r--;
            out(seg.query(l, r + 1));
        }
    }
}


Measured memory_bytes: 6916
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] A = new int[h][w];
		int[][] B = new int[h][w];
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				B[i][j] = sc.nextInt();
			}
		}
		boolean[][][] dp = new boolean[h+1][w+1][2*6400];
		dp[0][1][0+6400] = true;
		dp[1][0][0+6400] = true;
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				for(int k = -6400; k < 6400; k++) {
					if(dp[i][j+1][k+6400] || dp[i+1][j][k+6400]) {
						if(6400 + k + A[i][j] - B[i][j] >= 0 && 
								6400 + k + A[i][j] - B[i][j] < 2*6400) {
							dp[i+1][j+1][6400 + k + A[i][j] - B[i][j]] = true;
						}
						if(6400 + k - A[i][j] + B[i][j] >= 0 && 
								6400 + k - A[i][j] + B[i][j] < 2*6400) {
							dp[i+1][j+1][6400 + k - A[i][j] + B[i][j]] = true;
						}
					}
				}
			}
		}
		int min = 6400;
		for(int k = -6400; k < 6400; k++) {
			if(dp[h][w][k+6400])
				min = Integer.min(Math.abs(k), min);
		}
		System.out.println(min);
	}
	static class FastScanner {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public FastScanner() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch(IOException e) {
				throw new RuntimeException(e);
			}
		}
	}

}


Measured memory_bytes: 130304
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
const ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;
ll rui[10000000 + 10];
V ans;

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

  cin >> n;
  rui[1] = 1;
  rrep(i, 2, n + 1) { rui[i] += rui[i - 1] + i; }
  ll now = n;
  rrep(i, 1, n + 1) {
    tmp = n - i;
    if (rui[i - 1] >= tmp) {
      ans.p_b(i);
      tmp = i;
      now -= i;
      break;
    }
  }
  rrrep(i, tmp - 1, 1) {
    if (now == 0) break;
    if (now >= i) {
      now -= i;
      ans.p_b(i);
    }
  }
  rep(i, Size(ans)) Cout(ans[i]);
  return 0;
}

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

int main(){
  int a,b,k;
  cin >> a >> b >> k;
  
  int count = 0;
  for(int i=100; i>0; i--){
    if(a%i==0 && b%i==0){
      count++;
      if(count==k){
        cout << i << endl;
        break;
      }
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    L = 0
    R = 10**5 + 1
    for _ in range(M):
        left, right = map(int, input().split())
        L = max(L, left)
        R = min(R, right)

    return max(R - L + 1, 0)


if __name__ == '__main__':
    print(main())


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

int main() {
  int h, w;
  cin >> h >> w;

  string s[h];

  for (int k = 0; k < h; k++) {
    cin >> s[k];
  }

  for (int k = 0; k < h; k++) {
    for (int l = 0; l < w; l++) {
      if (s[k][l] == '#') {
        bool flag = false;
        if (k - 1 >= 0 && s[k-1][l] == '#') flag = true;
        if (l - 1 >= 0 && s[k][l-1] == '#') flag = true;
        if (l + 1 <= w && s[k][l+1] == '#') flag = true;
        if (k + 1 <= h && s[k+1][l] == '#') flag = true;
        if (flag == false) {
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;

// const
// 円周率
const double pi = M_PI;
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)

int main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  cin >> n;
  vector<ll> a(n + 1);
  vector<ll> asum(n + 1, 0);
  rep(i, n + 1) { cin >> a[i]; }
  asum[n] = a[n];
  for (ll i = n - 1; i >= 0; i--) {
    asum[i] = asum[i + 1] + a[i];
  }
  ll res = 1;
  ll preview = 1 - a[0];
  rep(i, n) {
    if (preview <= 0 and i!=n-1) {
      cout << -1 << endl;
      return 0;
    }
    res += min(asum[i + 1], preview * 2);
    preview = min(asum[i + 1], preview * 2) - a[i + 1];
  }
  if (preview < 0) {
    cout << -1 << endl;
    return 0;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4760
#include <bits/stdc++.h>
#define rep(a,n) for (int a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<int,int> P;
typedef pair<ll,P> PP;
typedef vector<vector<int> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

// auto mod int
// depends on Template

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//input
ll h,w,k;

mint dp[110][10];


int main(){
    cin >> h >> w >> k;
    k--;
    dp[0][0]=1;
    int sps[8]={1,1,2,3,5,8,13,21};
    for(int i=1;i<=h;i++){
        for(int j=0;j<w;j++){
            if(j>0){
                mint now = dp[i-1][j-1]*sps[j-1]*sps[w-j-1];
                dp[i][j] += now;
            }
            if(j<w-1){
                mint now = dp[i-1][j+1]*sps[j]*sps[w-j-2];
                dp[i][j] += now;
            }
            mint now = dp[i-1][j]*sps[j]*sps[w-j-1];
            dp[i][j]+=now;
        }
    }
    cout << dp[h][k] << endl;

    /*
    //debug
    for(int i=1;i<=h;i++){
        rep(j,w){
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }
    */

    return 0;
}



Measured memory_bytes: 3584
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B; cin >> N >> A >> B;
	vector<int> h(N); rep(i, 0, N) {
		cin >> h[i];
	}
	auto f = [&](int k) {
		int x = 0;
		rep(i, 0, N) {
			x += max(0LL, (h[i] - k*B + (A - B - 1)) / (A - B));
			dump(x);
		}
		return x <= k;
	};
	auto binarySearch = [&](int ng, int ok) {
		if (f(ng))return ng;
		while (ng + 1 < ok) {
			int m = (ng + ok) / 2;
			if (f(m))
				ok = m;
			else
				ng = m;
		}
		return ok;
	};
	cout << binarySearch(0, 1000000001) << endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;
 class Main{

     public static void main(String []args){
         Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        if(b%a==0)
        System.out.println(a+b);
        else
        System.out.println(b-a);
     }
}

Measured memory_bytes: 23380
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,k,ans=0;
  cin>>a>>b>>c>>k;
  for(int i=0;i<k;i++){
    if(i<=a-1)
      ans+=1;
    else if(i<=a+b+c-1 && i>=a+b)
      ans-=1;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x;cin>>n>>x;
    ll a[n];for(ll i=0;i<n;i++)cin>>a[i],x-=a[i];
    ll ans=n;
    sort(a,a+n);
    ans+=x/a[0];
    cout<<ans;
}


Measured memory_bytes: 256
while 1:
    try:
        numbers = map(int, raw_input())
    except EOFError:
        break
    dp = [[0] * 10 for _ in xrange(10)]
    dp[0] = numbers
    for i in xrange(9):
        for j in xrange(len(dp[i]) - 1):
            dp[i + 1][j] = (dp[i][j] + dp[i][j + 1]) % 10
    print dp[-1][0]

Measured memory_bytes: 4220
#include<stdio.h>
int main(void)
{
    int a[3],b,n,i,x,y;
	scanf("%d",&b);
    for(n=0;n<b;n++){
		for(i=0;i<3;i++){
		scanf("%d",&a[i]);
		}
		for(i=0;i<2;i++){
		    for(x=i+1;x<3;x++){
			    if(a[i]<a[x]){
				    y=a[i];
					a[i]=a[x];
					a[x]=y;
				}
			}
		}
		for(i=0;i<3;i++){
			a[i]=a[i]*a[i];
        }
	//	printf("%d\n",x);
		if(a[0]==a[1]+a[2]){
		    printf("YES\n");
		}
		else{
		    printf("NO\n");
		}
	}
	return 0;
}

Measured memory_bytes: 2476
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unordered_map>
#include <vector>

int main(){
  std::string S;
  int K;
  scanf("%d", &K);
  std::cin >> S;
  if (S.length()<=K) {
    std::cout << S << std::endl;
  } else {
    std::cout << S.substr(0, K) << "..." << std::endl;
  }
  return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;

#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////


int main(){fastio
    
    ll a,b;cin>>a>>b;
    if(a>b)swap(a,b);
    if(a<b)a=b-1;
    cout<<a+b<<endl;
    
    return 0;
}





Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
	int n,ans=0,i;
	string a,b,c;
	cin>>n;
	cin>>a>>b>>c;
	char ca[n],cb[n],cc[n];
	for(i=0;i<n;i++)
	{
		ca[i]=a[i];
		cb[i]=b[i];
		cc[i]=c[i];
		if(ca[i]!=cb[i] && cb[i]!=cc[i] && ca[i]!=cc[i])
		{
			ans=ans+2;
		}
		else if(ca[i]==cb[i] && cb[i]!=cc[i] && ca[i]!=cc[i] || ca[i]!=cb[i] && cb[i]==cc[i] && ca[i]!=cc[i] || ca[i]!=cb[i] && cb[i]!=cc[i] && ca[i]==cc[i])
		{
			ans++;
		}
	}	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int max, min;
    long sum = 0;
    int i = 1;
    
    while(i <= n){
        int x;
        cin >> x;
        if (i == 1){
            max = x;
            min = x;
        }
        if (max < x){
            max = x;
        }
        if (min > x){
            min = x;
        }
        sum = sum + x;
        i += 1; 
        
    }
    cout<<min <<" " <<max <<" " <<sum <<endl;
    return 0;
}


Measured memory_bytes: 3108
#n=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

s=input()
t=input()

if t==s+t[-1]:
    print("Yes")
else:
    print("No")






Measured memory_bytes: 9044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    vector<int>V(3);
    cin>>V[0]>>V[1]>>V[2];
    sort(V.begin(),V.end());
    int x=V[1]-V[0];
    if(x%2==0)cout<<x/2+V[2]-V[1]<<endl;
    else cout<<(x+3)/2+V[2]-V[1]<<endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		while(stdIn.hasNext())
		{
			long num = stdIn.nextLong();
			long[][] a = new long[10][10];
			for(int i = 9; i >= 0; --i)
			{
				a[0][i] = num % 10;
				num /= 10;
			}
			for(int i = 0; i < 9; ++i)
			{
				for(int j = 0; j < 9; ++j)
				{
					a[i + 1][j] = (a[i][j] + a[i][j + 1]) % 10;
				}
			}
			System.out.println(a[9][0]);
		}
	}
}

Measured memory_bytes: 12000
include Math
n = gets.chomp.to_i
x = gets.chomp.split(' ').map(&:to_f)
y = gets.chomp.split(' ').map(&:to_f)
z = []
x.zip(y) do |ary| 
  z << ary.inject(:-).abs
end
# d1
puts z.inject(:+)
# d2
sum = z.inject(0.0) {|res, i| res + i**2}
puts sqrt(sum)
# d3
sum = z.inject(0.0) {|res, i| res + i**3}
puts sum ** (1.0/3)
# d inf
puts z.max

Measured memory_bytes: 6192
A[10];i;b=-1;main(a){for(;i<10;)scanf("%d",A+i++);for(;~scanf("%d",&a);b^=~i?1<<i:0)for(i=9;a&&~--i;)a*=A[i]!=a;puts(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84?"No":"Yes");}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;
ll a, b, c, k;
int main() {
    cin >> a >> b >> c >> k;
    vector<ll> v = {a, b, c};
    sort(v.rbegin(), v.rend());
    while (k) {
        v[0] *= 2;
        --k;
    }
    cout << accumulate(v.begin(), v.end(), 0) << endl;

    return 0;
}


Measured memory_bytes: 3660
#include <stdio.h>
#define MAX 1000000
int prime_count[MAX];
int main(void){
  int n = 0, i, j;
 
  for(i = 2; i < MAX; ++i){
    if(prime_count[i] != -1){
      for(j = i * 2; j < MAX; j += i){
        prime_count[j] = -1;
      }
      prime_count[i] = ++n;
    }else{
      prime_count[i] = n;
    }
  }
 
  while(scanf("%d", &n) != EOF){
    printf("%d\n", prime_count[n]);
  }
  return 0;
}

Measured memory_bytes: 4500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    if(a<=8 && b<=8) cout << "Yay!" << endl;
    else cout << ":(" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int A,B,M;
int a[100005],b[100005],c[100005];
int x[100005],y[100005],m[100005];

int main(void){
	scanf("%d%d%d",&A,&B,&M);
	for(int i=0;i<A;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<B;i++){
		scanf("%d",&b[i]);
	}
	int ans=a[0]+b[0];
	for(int i=0;i<M;i++){
		scanf("%d%d%d",&x[i],&y[i],&m[i]);
		x[i]--;
		y[i]--;
		ans=min(ans,a[x[i]]+b[y[i]]-m[i]);
	}
	sort(a,a+A);
	sort(b,b+B);
	ans=min(ans,a[0]+b[0]);
	printf("%d\n",ans);
	return 0;
}


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

int main()
{
	int n, l;
	cin >> n >> l;
	int ans = 0, minabs = abs(l) + abs(n);
	for (int i = 0; i < n; i++)
	{
		ans += l + i;
		if (abs(l + i) < abs(minabs))
			minabs = l + i;
	}
	ans -= minabs;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)



int main(){
	ll H,W,ans=0;
	cin >> H >> W;
	ll dp[H][W];
	FOR(i,0,H){
		FOR(j,0,W){
			cin >> dp[i][j];
			dp[i][j] = 1 - dp[i][j];
			ans = max(ans,dp[i][j]);
		}
	}
	FOR(i,1,H){
		FOR(j,1,W){
			if(dp[i][j]){
				dp[i][j] = min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
				ans = max(ans,dp[i][j]);
			}	
		}
	}
	cout << ans*ans << endl;

}


Measured memory_bytes: 18392
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

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

using ll = long long;

int main() {
  std::vector<std::string> s, t;

  int N, M;

  cin >> N;
  s.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> s[i];
  }

  cin >> M;
  t.resize(M);
  for (int i = 0; i < M; ++i) {
    cin >> t[i];
  }

  int ans = 0;

  for (int i = 0; i < N; ++i) {
    int tmp = 0;

    for (int j = 0; j < N; ++j) {
      if (s[i] == s[j]) {
        tmp++;
      }
    }

    for (int j = 0; j < M; ++j) {
      if (s[i] == t[j]) {
        tmp--;
      }
    }

    ans = std::max(ans, tmp);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

@SuppressWarnings("unused")
public class Main {

	public static void main(String[] args) throws Exception {
		Main main = new Main();

		try (Scanner scan = new Scanner(System.in)) {
			main.yymmOrMmyy(scan);
		}
	}

	private void yymmOrMmyy(Scanner scan) {
		String s = scan.next();

		int f = Integer.valueOf(s.substring(0, 2));
		int l = Integer.valueOf(s.substring(2, 4));
		boolean yOkF = true, yOkL = true;

		if (f > 12 || f < 1) {
			yOkF = false;
		}
		if (l > 12 || l < 1) {
			yOkL = false;
		}
		if (yOkF) {
			if (yOkL) {
				System.out.println("AMBIGUOUS");
			} else {
				System.out.println("MMYY");
			}
		} else {
			if (yOkL) {
				System.out.println("YYMM");
			} else {
				System.out.println("NA");
			}
		}

	}

	private void changingACharchter(Scanner scan) {
		scan.nextInt();
		int k = scan.nextInt();
		char[] s = scan.next().toCharArray();

		s[k - 1] = Character.toLowerCase(s[k - 1]);
		System.out.println(new String(s));

	}

}


Measured memory_bytes: 22612
import sys
from collections import defaultdict
n,m=map(int,sys.stdin.readline().split())
l=list(map(int,sys.stdin.readline().split()))
l.sort()
l.reverse()
limit=(sum(l)/(4*m))
i=0
#print(l,'l')
while i<n and l[i]>=limit:
    i+=1
if i>=m:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38384
#include<iostream>
#include<vector>
using namespace std;
long long int dp[100001];

/*long long  frogjump(vector<int>v,int n)
{ if(n<=1)
 return 0;
    if(dp[n]!=-1)
      return dp[n];
      
      long long  ans1=abs(v[n]-v[n-1])+frogjump(v,n-1);
      long long  int ans2=abs(v[n]-v[n-2])+frogjump(v,n-2);
      return dp[n]=min(ans1,ans2);
	
	
}*/
long long  frogjump2(vector<int>v,int n)
{ dp[1]=0;
dp[0]=0;
v[0]=10000000;
  for(int i=2;i<=n;i++)
    dp[i]=min(abs(v[i]-v[i-1])+dp[i-1],abs(v[i]-v[i-2])+dp[i-2]);
  return dp[n];
	
	
}
int main()
{ 
  int n;
  cin>>n;
  vector<int> v(n+1);
  for(int i=1;i<=n;i++)
    {
   	  cin>>v[i];
  }
  cout<<frogjump2(v,n);
  
}

Measured memory_bytes: 1792
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	VI a(4); rep(i, 4)cin >> a[i];
	sort(all(a));
	puts(a[0] == a[1] && a[2] == a[3] ? "yes" : "no");
}


Measured memory_bytes: 3116
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int d[10101],a[10101],b[10101];
ll c[10101],p[10101];
vector<int> g[10101];
priority_queue<P> pq;
queue<int> q;

int main(void){
	int n,i,v,u;
	ll m = 0ll;
	P tmp;
	cin >> n;
	for(i=1; i<n; ++i){
		cin >> a[i] >> b[i];
		--a[i]; --b[i];
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	for(i=0; i<n; ++i){
		cin >> c[i];
	}
	sort(c,c+n);
	fill(d,d+n,INF);
	d[0] = 0;
	q.push(0);
	while(!q.empty()){
		v = q.front();
		q.pop();
		for(i=(g[v].l_ength()-1); i>=0; --i){
			u = g[v][i];
			if(d[u] > d[v]+1){
				d[u] = d[v]+1;
				q.push(u);
			}
		}
	}
	for(i=0; i<n; ++i){
		pq.push(P(d[i],i));
	}
	for(i=0; i<n; ++i){
		tmp = pq.top();
		pq.pop();
		p[tmp.second] = c[i];
	}
	for(i=1; i<n; ++i){
		m += min(p[a[i]],p[b[i]]);
	}
	cout << m << endl;
	for(i=0; i<n; ++i){
		cout << ((i)?" ":"") << p[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 1408
using System;

class MyClass
{
    public static void Main()
    {
        string str = Console.ReadLine();
        int S = int.Parse(str);

        int h = S / 3600;
        int m = S % 3600 / 60;
        int s = S % 3600 % 60;

        Console.WriteLine("{0}:{1}:{2}",h,m,s);
    }
}

Measured memory_bytes: 9196
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val x = sc.nextLong()
    println(rec(n, x))
}

fun rec(n: Int, x: Long):Long {
    if (x <= 0L) return 0
    if (n == 0) return 1
    var sum: Long
    if (x < 1L.shl(n + 1) - 2) {
        sum = rec(n - 1, Math.min(x - 1, 1L.shl(n + 1) - 3))
    } else {
        sum = 1L.shl(n) - 1
    }
    if (x >= 1L.shl(n + 1) - 1) {
        sum++
        sum += rec(n - 1, Math.min(x - 1L.shl(n + 1) + 1, 1L.shl(n + 1) - 3))
    }
    return sum
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

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

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

    int N, K;
    cin >> N >> K;
    vector<int> X(N);
    for (auto &x : X) cin >> x;

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += (X.at(i) < K - X.at(i)) ? 2 * X.at(i) : 2 * (K - X.at(i));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= M; j++){
            if((N*M - i*j - (N - i)*(M - j)) == K){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

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

    ll n, k; cin >> n >> k;

    if(n > k){
        n = n % k;
    }

    cout << min(n, k - n) << endl;

    return 0;
}

Measured memory_bytes: 3644
// clang-format

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;

using lli = long long int;

void solve(long long N, std::vector<long long> X, std::vector<long long> L) {
  vector<pair<lli, lli>> v;
  rep(i, N) v.emplace_back(X[i] + L[i], X[i] - L[i]);
  sort(v.begin(), v.end());
  lli cur = -1e18;
  lli ans = 0;
  rep(i, N) {
    if (v[i].second >= cur) {
      cur = v[i].first;
      ans++;
    }
  }
  cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> X(N);
  std::vector<long long> L(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &X[i]);
    scanf("%lld", &L[i]);
  }
  solve(N, std::move(X), std::move(L));
  return 0;
}


Measured memory_bytes: 3956
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 210000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
// long long C(int a,int b){
// 	if(a<b||b<0)return 0;
// 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
// }
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ

int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	printf("%.12f\n",(double)(b-1)*(a-c)/a/a*(c?2:1));
}

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

int main(void){

  long n;
  scanf("%ld", &n);

  long answer;
  for (long i = sqrt(n); i >= 1; i--) {
    if (n%i == 0) {
      answer = i+(n/i)-2;
      break;
    }
  }
  printf("%ld\n", answer);

  return 0;
}

Measured memory_bytes: 128
function Main(input) {
	input = input.split("\n");
	const S = input[0]
	const T = input[1]
	var n = 0
	for(i=0; i < 3; i++){
		if(S[i] == T[i]) n++
	}
	console.log(n)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int64_t L (int N) {
    vector<int64_t> dl(N+1);
    dl.at(0) = 2ll;
    dl.at(1) = 1ll;
    for (int i = 2; i < N+1; i++) {
        dl.at(i) = dl.at(i-1) + dl.at(i-2);
    }
    return dl.at(N);
}
int main() {
    int N;
    cin >> N;
    printf("%lld\n", L(N));
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <math.h>
int minimum(int a, int b) { return a < b ? a : b; }
int maximum(int a, int b) { return a > b ? a : b; }
const long long mod = 1000000007;
//const long long mod = 998244353;
struct Data {
	int x;
	int h;
	int r;
	bool operator<(const Data&d)const {
		return x < d.x;
	}
};
int search(Data*d, int t, int n) {
	if (d[0].x >= t)return 0;
	int r = 0;
	for (int i = 30; i >= 0; i--) {
		int c = r | (1 << i);
		if (c >= n)continue;
		if (d[c].x < t)r = c;
	}
	return r + 1;
}
int main() {
	int N, D, A;
	scanf("%d %d %d", &N, &D, &A);
	auto X = new int[N];
	auto H = new int[N];
	for (int i = 0; i < N; i++)scanf("%d %d", X + i, H + i);
	auto d = new Data[N];
	for (int i = 0; i < N; i++) {
		H[i] = (H[i] - 1) / A + 1;
		d[i] = Data{ X[i],H[i],0 };
	}
	long long res = 0;
	std::sort(d, d + N);
	int ind = 0;
	for (int i = 0; i < N; i++) {
		ind -= d[i].r;
		if (d[i].h > ind) {
			res += d[i].h - ind;
			int r = search(d, d[i].x + 2 * D + 1, N);
			if (r < N)d[r].r += d[i].h - ind;
			ind = d[i].h;
		}
	}
	printf("%lld", res);
	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<typename T> using v2 = vector<vector<T>>;
template<typename T> using v3 = vector<vector<vector<T>>>;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
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; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 200;
const ll INFLL = 2e18 + 200;

class UnionFind {
private:
    vector<int> data;

public:
    explicit UnionFind(size_t data_size) : data(data_size, -1)  {}

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    int find(size_t index) {
        if (data[index] < 0) return index;
        else return (data[index] = find(data[index]));
    }

    int size(size_t index) {
        return (-data[find(index)]);
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        uf.unite(A, B);
    }
    set<int> check;
    for (int i = 0; i < N; i++) {
        check.insert(uf.find(i));
    }
    cout << check.size() - 1 << endl;
}

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

int main() {
  int n;
  cin>>n;
  vector<vector<int> > a(n,vector<int>(2));
  for(int i=0;i<n;i++){
    for(int j=0;j<2;j++){
      cin>>a.at(i).at(j);
    }
  }
  double p=0;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      p+=sqrt(pow((a.at(i).at(0)-a.at(j).at(0)),2)+pow((a.at(i).at(1)-a.at(j).at(1)),2));
    }
  }
  cout<<fixed<<setprecision(10);
  cout<<2*p/n<<endl;
}


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

int compare_int(const void *a,const void *b){
	return *(long long*)a-*(long long*)b;
}

int main(){
	long long n,ncp;
	long long sosu[10000]={1};
	long long i,c=2;
	scanf("%lld",&n);
	if(n==1){
		puts("0");
		return 0;
	}
	sosu[1]=n;
	ncp=n;
	for(i=2;i*i<=ncp;i++){
		if(ncp%i==0){
			sosu[c]=i;c++;
			sosu[c++]=ncp/i;
	//		ncp/=i;
	//		i=1;
		}
	}
	if(sosu[c-1]==sosu[c-2])sosu[c-1]=n+1;
//	qsort(sosu,c,sizeof(long long),compare_int);
	long long ans=0;
	for(i=1;i<c;i++){
		if(n%(sosu[i]-1)==n/(sosu[i]-1))ans+=(sosu[i]-1);
	}
	printf("%lld\n",ans);
	return 0;
}

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

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

    vector<int> a(n);
    rep(i,n){
        cin >> a.at(i);
    }

    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    int A,B;
    A = B = 0;
    rep(i,n){
        if(i % 2 == 0){
            A += a.at(i);
        }else {
            B += a.at(i);
        }
    }
    cout << A - B << endl;
}

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, a, b;
	cin >> n >> a >> b;
	string s;
	cin >> s;
	ll ct = 0;
	ll rank = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'a')
		{
			if (ct < a + b)
			{
				cout << "Yes\n";
				ct++;
			}
			else
				cout << "No\n";
		}
		else if (s[i] == 'b')
		{
			rank++;
			if (ct < a + b && rank <= b)
			{
				cout << "Yes\n";
				ct++;
			}
			else
				cout << "No\n";
		}
		else
			cout << "No\n";
	}
	return 0;
}


Measured memory_bytes: 3780
def d_lunlun_number():
    import sys
    sys.setrecursionlimit(10**6)
    K = int(input())

    ans = []

    def dfs(num, current, digit_max):
        if current == digit_max:
            ans.append(num)
            return None
        for n in range(10):
            if abs((num % 10) - n) >= 2:
                continue
            dfs(num * 10 + n, current + 1, digit_max)

    for leading in range(1, 10):
        for d in range(1, 11):
            dfs(leading, 1, d)
    return sorted(ans)[K - 1]

print(d_lunlun_number())

Measured memory_bytes: 13828
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
// using Graph = vector<vector<Edge>>;
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vector<ll> A(N + 1);
  for (auto &it : A)
    cin >> it;
  vector<ll> th(N + 1);
  if (N == 0)
  {
    if (A[0] != 1)
    {
      cout << -1 << endl;
      return 0;
    }
    else
    {
      cout << 1 << endl;
      return 0;
    }
  }
  else
  {
    if (A[0] != 0)
    {
      cout << -1 << endl;
      return 0;
    }
    else
    {
      th[0] = 1;
      for (int i = 1; i < N + 1; i++)
      {
        th[i] = min(INF / 2, (th[i - 1] - A[i - 1]) * 2);
        if (A[i] > th[i] || (A[i] == th[i] && i != N))
        {
          cout << -1 << endl;
          return 0;
        }
      }
      ll ans = 0;
      ans += A[N];
      th[N] = A[N];
      for (int i = N - 1; i >= 0; i--)
      {
        ans += min(th[i], th[i + 1] + A[i]);
        th[i] = min(th[i], th[i + 1] + A[i]);
      }
      cout << ans << endl;
    }
  }
  return 0;
}

// 下から見ていく


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)  

int main()
{
  int n,m,a[100];
  cin >> n >> m;
  int sum= 0;
  rep(i, n){
    cin >> a[i];
    sum += a[i];
  }
  
  int ans = 0;
  rep(i, n)
  {
    if(a[i] * 4 * m >= sum)
    {
      ans++;
      if(ans >= m)
      {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << fixed << "No" << endl;
  return 0;
}

Measured memory_bytes: 256