akhauriyash/Code-Regression huggingface dataset:
from fractions import gcd
from functools import reduce

def lcm(a,b): # lcmは標準ライブラリには存在しない
    return a * b // gcd(a,b)
def ls_lcm(A): # リストを引数に取れる
    return reduce(lcm ,A)
def ls_gcd(A): # リストを引数に取れる
    return reduce (gcd, A)

def count_two(n): # 2で割れる回数を取得
    cnt = 0
    while(n & 1 == 0): # 最下位ビットが0かどうか
        cnt += 1
        n = n >> 1 # 右ビットシフト
    return cnt

N, M = map(int, input().split())
A = list(map(int, input().split()))

if len(set([count_two(a) for a in A])) != 1:
    print (0)
    exit()
A = [a//2 for a in A] # a_k/2 を考える
lc = ls_lcm(A)
print ((M + lc) // (2*lc)) # 最小公倍数を奇数倍したものが条件を満たす


Measured memory_bytes: 94160
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  ll n, h;
  cin >> n >> h;

  vector<ll> a(n), b(n);
  rep(i, n) {
    cin >> a[i] >> b[i];
  }

  sortd(b);
  sorti(a);

  ll mmax = a.back();
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    ll bt = b[i];
    if (bt >= mmax and h > 0) {
      ans += 1;
      h -= bt;
    } else {
      break;
    }
  }
  
  if (h <= 0) {
    cout << ans << endl;
  } else {
    ans += h / mmax;
    if (h % mmax > 0) {
      ans += 1;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define all(obj) obj.begin(), obj.end()
#define db(x) cerr << #x << ":" << x << " "
#define dbl(x) cerr << #x << ":" << x << "\n"
#define dbv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbgvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << endl; }
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main () {
	int N; cin >> N;
	int time = 0;
	map<string, int> m;
	rep(i, N) {
		string s; int t; cin >> s >> t;
		time += t;
		m[s] = time;		
	}
	string X; cin >> X;
	cout << time - m.at(X) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
template<class T> int gmax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
template<class T> int gmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

const int N = 1005;
char seq[N][N];
int step[N][N];
int dir[10][2] = { {0, - 1}, {0, 1}, {1, 0}, {-1, 0} };

int main() {
    int H, W;
    while(~scanf("%d %d", &H, &W)) {
        memset(step, 0, sizeof(step));

        for(int i = 1; i <= H; ++i) {
            scanf("%s", seq[i] + 1);
        }

        queue<pair<int, int> > Q;
        for(int i = 1; i <= H; ++i) {
            for(int j = 1; j <= W; ++j) {
                if(seq[i][j] == '#') {
                    step[i][j] = 1;
                    Q.push(make_pair(i, j));
                }
            }
        }

        int result = -1;
        while(!Q.empty()) {
            int x = Q.front().first; int y = Q.front().second; Q.pop();
            result = max(result, step[x][y]);

            for(int i = 0; i < 4; ++i) {
                int xx = x + dir[i][0]; int yy = y + dir[i][1];
                if(xx >= 1 && xx <= H && yy >= 1 && yy <= W && step[xx][yy] == 0) {
                    step[xx][yy] = step[x][y] + 1;
                    Q.push(make_pair(xx, yy));
                }
            }
        }

        printf("%d\n", result - 1);



        

        

    }
    return 0;
}

Measured memory_bytes: 13328
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
long long gcd(long long p,long long q){
  while(q){
    p%=q;
    swap(p,q);
  }
  return p;
}
long long f(long long a[],long long b[],long long c[],long long d[],int p){
  long long tm,tp;
  if(p==0)
    return 1;
  tm=f(a,b,c,d,c[p]);
  tp=f(a,b,c,d,d[p]);
  return (a[p]+b[p])*tm*tp/gcd(tm*a[p],tp*b[p]);
}
int main(){
  int i;
  int e[101],n;
  long long a[101],b[101],c[101],d[101];
  while(cin>>n&&n){
    memset(e,0,sizeof(e));
    for(i=1;i<n+1;i++){
      cin>>a[i]>>b[i]>>c[i]>>d[i];
      e[c[i]]=1;
      e[d[i]]=1;
    }
    for(i=0;e[i];i++);
    cout<<f(a,b,c,d,i)<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

using flt = double;
const flt eps = 1e-12, inf = 1e18, PI = acos(-1.0);
template<typename T>
inline T sqr(T x) {return x * x;}
inline flt cmp(flt a, flt b, flt e = eps) {
  return fabs(a - b) >= e + fabs(a) * e ? a - b : 0;
}
inline int sgn(flt x, flt e = eps) {return x < -e ? -1 : (x > e);}
inline flt fix(flt x, flt e = eps) {return cmp(x, 0, e);}

struct point {
  flt x, y;
  point(flt x = 0, flt y = 0): x(x), y(y) {}
  bool operator < (const point &rhs) const {
    return cmp(x, rhs.x) < 0 || (cmp(x, rhs.x) == 0 && cmp(y, rhs.y) < 0);
  }
  bool operator == (const point &rhs) const {
    return cmp(x, rhs.x) == 0 && cmp(y, rhs.y) == 0;
  }
  point operator + (const point &rhs) const {
    return point(x + rhs.x, y + rhs.y);
  }
  point operator - (const point &rhs) const {
    return point(x - rhs.x, y - rhs.y);
  }
  point operator * (const flt k) const {
    return point(x * k, y * k);
  }
  point operator / (const flt k) const {
    return point(x / k, y / k);
  }
  point operator ~ () const {// counter clockwise rotate 90 degree
    return point(-y, x);
  }
  flt dot(const point &rhs) const {
    return x * rhs.x + y * rhs.y;
  }
  flt det(const point &rhs) const {
    return x * rhs.y - y * rhs.x;
  }
  flt norm2() const {
    return x * x + y * y;
  }
  flt norm() const {
    return hypot(x, y);
  }
  point rot(flt a) const {// counter clockwise rotate A rad
    return point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
  point rot(flt cosa, flt sina) const {// counter clockwise rotate using cos/sin
    return point(x * cosa - y * sina, x * sina + y * cosa);
  }
  point trunc(flt a = 1.0) const {
    return (*this) * (a / this->norm());
  }
};

using poly_t = std::vector<point>;

// check if point $O$ is on segment $AB$
bool OnSeg(const point &A, const point &B, const point &O) {
  return sgn((A - O).det(B - O)) == 0 && sgn((A - O).dot(B - O)) <= 0;
}

// check point O in polygon P; 0:outside, 2:border, 1:inside
int InPolygon(const poly_t &P, const point &O) {
  int cnt = 0, n = P.size();
  for (int i = 0; i < n; ++i) {
    const point &A = P[i], &B = P[(i + 1) % n];
    if (OnSeg(A, B, O)) return 2;
    int k = sgn((B - A).det(O - A));
    int d1 = sgn(A.y - O.y), d2 = sgn(B.y - O.y);
    cnt += (k > 0 && d1 <= 0 && d2 > 0);
    cnt -= (k < 0 && d2 <= 0 && d1 > 0);
  }
  return cnt != 0;
}

int main() {
  int n;
  scanf("%d", &n);
  std::vector<point> p(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lf%lf", &p[i].x, &p[i].y);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    point O;
    scanf("%lf%lf", &O.x, &O.y);
    int v = InPolygon(p, O);
    if (v == 2) v = 1;
    else if (v == 1) v = 2;
    printf("%d\n", v);
  }
  return 0;
}

Measured memory_bytes: 2760
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

ll a,b,n,x[100],y[100];
bool is_c[100][100];

ll search(ll x,ll y){
    if(x == a - 1 && y == b - 1)
    return 1;

    if(x >= a || y >= b || is_c[x][y])
        return 0;
    return search(x + 1,y) + search(x,y + 1);
}

bool input(){
    scanf("%lld%lld",&a,&b);
    if(a == 0 && b == 0)
        return false;
    scanf("%lld",&n);
    REP(i,n){
        scanf("%lld%lld",x + i,y + i);
        x[i]--;y[i]--;
    }
    return true;
}

void solve(){
    REP(i,a)
        REP(j,b)
            is_c[i][j] = false;
    REP(i,n)
        is_c[x[i]][y[i]] = true;
    printf("%lld\n",search(0,0));
}

int main(){
    while(input())
        solve();
    return 0;
}

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

#define F                   first
#define S                   second
#define int                 long long int
#define pb                  push_back
#define mp                  make_pair
#define pii                 pair<int,int>
#define vi                  vector<int>
#define mii                 map<int,int>
#define pqb                 priority_queue<int>
#define pqs                 priority_queue<int,vi,greater<int> >
#define mod                 1000000007
#define endl                '\n'
#define rep(i,a,b)            for(int i=a;i<b;i++)
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
    c_p_c();
    int n, maxw;
    cin >> n >> maxw;
    int w[n];
    int v[n];
    rep(i, 0, n) {
        cin >> w[i] >> v[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(maxw + 1, 0));
    for (int i = n - 1  ; i >= 0; i--) {
        rep(j, 1, maxw + 1) {
            dp[i][j] = dp[i + 1][j];
            if (w[i] <= j) {
                dp[i][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[0][maxw] << endl;


    return 0;
}

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


int main() {

	int N;
	cin >> N;
	int sum = 0;

	vector<int> p(N);
	for (int i = 0; i < N; i++) {
		cin >> p.at(i);
		sum += p.at(i);
	}

	sort(p.begin(), p.end());
	sum -= p.at(N - 1)/2;

	cout << sum << endl;

}

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

int main(){

    int n, t, a;
    cin >> n >> t >> a;

    double diff = 1e5;
    int ans = -1;
    for (int i=0; i<n; i++){
        int h;
        cin >> h;
        double buf = abs((double)a - ((double)t - h*0.006));
        diff = min(diff, buf);
        if (diff == buf){
            ans = i + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

void search_dfs(char map[3][50][50], int xpos, int ypos, int w, int h, int color){

	if( xpos < 0 || xpos >= w ) return;
	if( ypos < 0 || ypos >= h ) return;
	if( color == 0 && map[color][xpos][ypos] == 'W' ) return;
	if( color == 1 && map[color][xpos][ypos] == 'B' ) return;
	if( map[color][xpos][ypos] == '#' ) return;
	map[color][xpos][ypos] = '#';
	search_dfs( map, xpos + 1, ypos, w, h, color);
	search_dfs( map, xpos - 1, ypos, w, h, color);
	search_dfs( map, xpos, ypos - 1, w, h, color);
	search_dfs( map, xpos, ypos + 1, w, h, color);

}


int main(void){
	//FILE* fp_in = freopen("data.txt", "r", stdin);

	while(1){
		int w, h;

		cin >> w >> h;

		if( w == 0 && h == 0 )
			break;

		char map[4][50][50];

		for(int i = 0; i < h; i++) {
			string s;
			cin >> s;
			for(int j = 0; j < w; j++) {
				map[0][j][i] = s[j];
				map[1][j][i] = s[j];
				map[2][j][i] = s[j];
			}
		}

		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				if( map[2][j][i] == 'B' )
					search_dfs(map, j,i,w,h,0);
				if( map[2][j][i] == 'W' )
					search_dfs(map, j,i,w,h,1);
			}
		}

		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				map[3][j][i] = ' ';
				if( map[0][j][i] == '#' && map[1][j][i] == '.' ) {
					map[3][j][i] = 'B';
				} else if( map[1][j][i] == '#' && map[0][j][i] == '.' ) {
					map[3][j][i] = 'W';
				}
			}
		}

		int ans[] = {0,0};

		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				if( map[3][j][i] == 'B' ) ans[0] ++;
				if( map[3][j][i] == 'W' ) ans[1] ++;
			}
		}

		cout << ans[0] << " " << ans[1] << endl;
	}

	//while(1){}
    return 0;
}

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

using namespace std;

int64_t s(int64_t N) {
    int n = N;
    int ans = 0;
    do {
        ans += n % 10;
    }
    while((n /= 10) > 0);
    return ans;
}

int main(int argc, char *argv[])
{
    int64_t N;
    cin >> N;

    int sn = s(N);
    if(N % sn == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

vector<int> Solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  vector<int> xs(n);
  for (int i = 0; i < n; i++) {
    xs[i] = s[i] == 'x';
  }

  vector<int> ys(n + 2);
  for (int y0 = 0; y0 < 2; y0++) {
    for (int y1 = 0; y1 < 2; y1++) {
      ys[0] = y0;
      ys[1] = y1;
      for (int i = 2; i < n + 2; i++) {
        ys[i] = xs[(i - 1) % n] ^ ys[i - 2] ^ ys[i - 1];
      }

      if (ys[0] == ys[n] && ys[1] == ys[n + 1]) {
        ys.pop_back();
        ys.pop_back();
        return ys;
      }
    }
  }
  return vector<int>();
}

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

  vector<int> ans = Solve();
  if (ans.empty()) {
    cout << -1 << endl;
  } else {
    for (int v : ans) {
      cout << "SW"[v];
    }
    cout << endl;
  }
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define inf 100000000000000000
#define mod 1000000007
#define MAX 100005
#define pb push_back
#define vit vector<int>::iterator
typedef pair<lint,lint> pii;
lint A[MAX],B[MAX];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    lint n;
    cin>>n;
    for(lint i=1;i<=n;i++) cin>>A[i]>>B[i];
    for(lint i=2;i<n;i++){
        if(A[i-1]==B[i-1] && A[i]==B[i] && A[i+1]==B[i+1]){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    vector<int> h(n+1);
    for(int i=1;i<=n;i++)cin>>h[i];
    vector<bool> bit(n+1,1);
    for(int i=1;i<=m;i++){
        int a,b,min_h=0;
        cin>>a>>b;
        if(h[a]==h[b]) {
            bit[a]=0;
            bit[b]=0;
            continue;
        }
        min_h=min(h[a],h[b]);
        if(min_h==h[a])bit[a]=0;
        else bit[b]=0;
    }
    for(int i=1;i<=n;i++)if(bit[i]) ans++;
    cout<<ans<<endl;
}

Measured memory_bytes: 3788
#if 0
2019.12.11

设 x[u] 表示 u 子树内和 u 颜色相同的点权和，对应的 y[u] 表示颜色不同的点权和。
那么 x[u] 是确定的，简单的贪心策略可知要在此基础上最小化 y[u] 的值。
对于点 u ，假设已经计算出所有儿子 v 的最小 y[u] 。
那么每个儿子 v 有两种可能，分别是 v 与 u 颜色相同与否。
设所有与 u 颜色相同/不同的儿子集合为 S/T ，
记 X = sum_x(S) + sum_y(T), Y = sum_y(S) + sum_x(T) ，
那么只要 X <= x[u] 就可以将 u 附一个非负权值使得 u 子树颜色相同的点权和恰为 x[u] ，
自然有 y[u] = Y ，由于 X + Y 是常量，最小化 Y 等价于最大化 X ，
最大化 X 可以用 01 背包处理出所有可能的 X 值，取个最大的即可，
如果没有合法的 X ，全局无解。
#endif
#include <cstdio>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 1010, maxv = 5050;
int head[maxn], nxt[maxn];
int fa[maxn];
int a[maxn];
bool f[maxn][maxv];

bool dfs(int u, int &x, int &y) {
	int sum = 0;
	f[u][0] = 1;

	for(int v = head[u]; v; v = nxt[v]) {
		int vx, vy;
		if(!dfs(v, vx, vy)) return 0;
		sum += vx + vy;

		for(int k = a[u]; k >= 0; k --)
			f[u][k] = (k >= vx ? f[u][k - vx] : 0) | (k >= vy ? f[u][k - vy] : 0);
	}

/* 	for(int k = 0; k <= a[u]; k ++) */
/* 		debug("%d", f[u][k]); */
/* 	debug("\n"); */

	int use = a[u];
	while(use >= 0 and !f[u][use]) -- use;
	if(use < 0) return 0;

	x = a[u];
	y = sum - use;

	/* debug("%d: use=%d x=%d y=%d\n", u, use, x, y); */
	return 1;
}

int main() {
	int n = read;
	for(int i = 2; i <= n; i ++) {
		read(fa[i]);
		nxt[i] = head[fa[i]];
		head[fa[i]] = i;
	}

	for(int i = 1; i <= n; i ++)
		read(a[i]);

	int x, y;
	if(dfs(1, x, y)) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}


Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const ll mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

ll n;
vector<int> a;

template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }
};

// 中央値が x 以上か否か
bool C(int x){
    // (a[i] < x) → -1, (a[i] >= x) → 1 とした場合の累積和
    // second には位置情報が入っている
    vector<P> sum(n+1, P(0, 0));

    for(int i = 0; i < n; ++i){
        if(a[i] < x)    sum[i+1].first = sum[i].first - 1;
        else    sum[i+1].first = sum[i].first + 1;
        sum[i+1].second = i+1;
    }
    sort(sum.begin(), sum.end());
    
    // 転倒数を求めるためのセグ木
    SegmentTree<int> seg(n+1, [](int a, int b){return a + b;}, 0);
    ll res = 0;
    for(int i = 0; i < n+1; ++i){
        int pos = sum[i].second;
        res += seg.query(0, pos);
        seg.update(pos, 1);    
    }

    // x が中央値になるための条件
    ll comparision = (n * (n + 1) / 2 + 1) / 2;
    return res >= comparision;
}

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

    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; ++i)  cin >> a[i];

    int lb = 0, ub = *max_element(a.begin(), a.end()) + 1;
    while(ub - lb > 1){
        int mid = (lb + ub) / 2;
        if(C(mid))  lb = mid;
        else    ub = mid;
    }
    cout << lb << endl;
}

Measured memory_bytes: 2440
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
A, B, C, D = map(int,input().split())
Cres = B//C - (A-1)//C
Dres = B//D - (A-1)//D
CDres = B//lcm(C,D) - (A-1)//lcm(C,D)
print(B-A+1-(Cres + Dres - CDres))

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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 <= i; i--)
#define FOR(i, from, to) for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to) for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;

ll gcd(ll a, ll b)
{
    return (a < b) ? gcd(b, a) : ((a % b) ? gcd(b, a % b) : b);
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

ll powmod(ll x, ll p, ll m)
{
    if (p == 0)
        return 1;
    if (p & 1)
        return powmod(x, p - 1, m) * x % m;
    ll r = powmod(x, p / 2, m);
    return r * r % m;
}

constexpr ll MOD = 1000000007;

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include<iomanip>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>

i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;



//メモリ置き場


//inputします
void input() {
	
}

//ライブラリ置き場
i64 cup(i64 xxx38, i64 yyy38) {//切り上げ
	return (xxx38 + yyy38 - 1) / yyy38;
}
//main
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
	input();
	i64 n;
	cin >> n;
	vector<i64> dat(5);
	i64 min = giant;
	ff(i, 0, 5) {
		cin >> dat[i];
		if (min > dat[i])min = dat[i];
	}
	cout << cup(n, min) + 4 << endl;
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

// vectorの重複削除
// std::sort(test.begin(), test.end());
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //
// const int MOD = 1000000007;
// string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// printf("%.20f\n", ans); あれ
// const double PI = 3.141592653589793238462643383;
int n;
int ii;
int jj;
int mm;


int check(int num) {
  mm = sqrt(num);
  int cnt = 0;
  for (int i=1; i<=mm; i++) {
    //ii = i*i;
    //if (6*ii > num) break;

    for (int j=1; j<=mm; j++) {
      //jj = j*j;
      //if (ii + 3*jj + 2*i*j > num) break;

      for (int k=1; k<=mm; k++) {
        //if (ii + jj + k*k + i*j + j*k + i*k > num) break;
        if (i*i + j*j + k*k + i*j + j*k + i*k == num) {
          //if (i != j && i != k && j != k) return 6;
          //if (i == j && i == k) return 1;
          cnt++;
          //return 3;
        }
      }
    }
  }
  //return 0;
  return cnt;
}

int main() {
  cin>>n;
  //int a;
  for (int l=1; l<=n; l++) {
    //cout << check(l) << endl;
    //int a = check(l);
    printf("%d\n", check(l));
  }
  // int mm = sqrt(2);
  // cout << mm << endl;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define  INF 1000000007

using Edge = pair<int,int>;
using Graph = vector<vector<int> >;

Graph G;

vector<int> res;
vector<int> tmp;

//ツリー探索pはvの親。vをcに塗る
void dfs(int v, int p, int c){
    res[v] = tmp[v] + c;
    for(auto e : G[v]){
        if(e == p) continue;//子から親へ逆流を防ぐ
        else dfs(e,v,res[v]);
    }
}

int main(){
    int N,Q;cin >> N >> Q;
    G.resize(N+1);
    for(int i = 0; i < N-1 ; i++){
        int u,v,w;cin >> u >> v;
        u--;v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    res.assign(N,0);
    tmp.assign(N,0);
    for(int i = 0; i < Q ; i++){
        int p,x;cin >> p >> x;
        p--;
        tmp[p] += x;
    }
    dfs(0,-1,0);

    for(auto v : res)cout << v << " ";
    cout << "\n";

    return 0;
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5+23;
pair<int, int> a[N];

void solve() {
  int n; scanf("%d", &n);
  for (int x, i = 0; i < n; ++i) {
    scanf("%d", &x);
    a[i] = {x, i};
  }
  sort(a, a+n);
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i].second%2 != i%2) ++ans;
  }
  printf("%d", ans/2);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4640
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    return 'Yes' if len(set(S)) > 1 else 'No'


def main():
    S = read_str()
    print(slv(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6724
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int& x : v) {
        cin >> x;
    }
    int ans = 0;
    for (int i = 1; i <= min(n, k); i++) {
        for (int j = 1; j <= i; j++) {
            vector<int> t(i);
            auto p = [](int x) {return x < 0; };
            auto it = copy_if(begin(v), begin(v) + j, begin(t), p);
            it = copy_if(end(v) - i + j, end(v), it, p);
            sort(begin(t), it);
            int s = accumulate(begin(v), begin(v) + j, 0);
            s += accumulate(end(v) - i + j, end(v), 0);
            if (it - begin(t) > k - i)
                it = begin(t) + k - i;
            ans = max(ans, s - accumulate(begin(t), it, 0));
        }
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,a,b,c,d[100],y,i,p,j,tmp,max,k;
    int price,calorie,cur;
	scanf("%d %d %d %d",&n,&a,&b,&c);

    for(i = 0; i < n; i++){
		scanf("%d",&d[i]);
    }

	for(i = 0; i < n; i++){
		for(j = 0; j < i; j++){
			if(d[j] < d[i]){
				tmp = d[j];
				d[j] = d[i];
				d[i] = tmp;
			}
		}
	}
	
    price = a;
    calorie = c;
    max = calorie/price;
    for (i = 0; i < n; i++) {
		price += b;
		calorie += d[i];
		cur = calorie / price;
		if (max > cur) {
			break;
		}
		max = cur;
	}
	printf("%d\n",max);
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8


#define MAXI 2000000
#define INFI (1<<30)

int H,A[MAXI+7];

void maxHeapify(int i){
    int l,r,largest;
    l=2*i;
    r=2*i+1;
    if(l<=H && A[l]>A[i]){
        largest = l;
    }
    else{
        largest = i;
    }
    if(r<=H && A[r]>A[largest]){
        largest = r;
    }
    if(largest !=i){
        swap(A[i],A[largest]);
        maxHeapify(largest);
    }
}

int extract(){
    int maxv;
    if(H<1){
        return -INFI;
    }
    maxv=A[1];
    A[1]=A[H--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i,int key){
    if(key<A[i]){
        return;
    }
    A[i]=key;
    while(i>1&&A[i/2]<A[i]){
        swap(A[i],A[i/2]);
        i/=2;
    }
}

void insert(int key){
    H++;
    A[H] = -INFI;
    increaseKey(H,key);
}

int main(){
    int key;
    string S;

    while(1){
        cin >> S;
        if(S=="end"){
            break;
        }
        if(S=="insert"){
            cin >> key;
            insert(key);
        }
        else{
            cout << extract() << endl;
        }
    }
}


Measured memory_bytes: 7072
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if( A+B > C+D){
    cout << "Left" << endl;
  }
  if( A+B == C+D){
    cout << "Balanced" << endl;
  }
    if( A+B < C+D){
      cout << "Right" << endl;
    }
  }


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

ll cost(vector<ll> &X, ll p){
    ll res =0;
    int N = X.size();
    for(int i=0; i<N; i++){
        res += pow(X.at(i) - p, 2);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<ll> X(N);
    int x;
    int x_min = 101;
    int x_max = 0;
    for(int i=0; i<N; i++){
        cin >> x;
        X.at(i) = x;
        x_min = min(x_min, x);
        x_max = max(x_max, x);
    }

    ll ans = pow(N * 100, 2);
    for(int i=x_min; i<=x_max; i++){
        ans = min(ans, cost(X, i));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
// Author : Rifayat Samee (Sanzee)
// Problem :
// Algorithm:

/*

*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll memo[100005][2];
const int mod = 1e9+7;
ll dp(int i,int col,int p,const vector<vector<int>>&graph){
    if(memo[i][col] != -1)
        return memo[i][col];
    ll res = 1;

    for(int j=0;j<graph[i].size();j++){
        int v = graph[i][j];
        if(v != p){
            if(col)
                res = (res * dp(v,!col,i,graph))%mod;
            else{
                res = (res *((dp(v,col,i,graph) + dp(v,!col,i,graph))%mod ) )%mod;
            }

        }
    }

    memo[i][col] = res;
    return res;
}

int main(){

	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        graph[u].push_back(v);
        graph[v].push_back(u);

    }
    memset(memo,-1,sizeof(memo));
    ll res = (dp(1,0,0,graph) + dp(1,1,0,graph))%mod;
    printf("%lld\n",res);
	return 0;
}


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


// prime factorization
vector<pair<long long, int>> pf(long long N) {
	assert(N > 0);
	vector<pair<long long, int>> res;
	long long p = 2;
	for (long long p = 2; p * p <= N; p++) {
		if (N % p == 0) {
			int d = 0;
			while (N % p == 0) {
				N /= p;
				d++;
			}
			res.push_back(pair<long long, int>(p, d));
		}
	}
	if (N > 1) res.push_back(pair<long long, int>(N, 1));
	return res;
}

map<long long, int> pf_map(long long N) {
	map<long long, int> res;
	for (pair<long long, int> pd : pf(N)) {
		auto [p, d] = pd;
		res[p] = d;
	}
	return res;
}

vector<long long> pf_multi(long long N) {
	vector<long long> res;
	for (pair<long long, int> pd: pf(N)) {
		auto [p, d] = pd;
		for (int i = 0; i < d; i++) {
			res.push_back(p);
		}
	}
	return res;
}

// primarity test
bool is_prime(long long N) {
	assert(N > 0);
	if (N == 1) return false;
	for (long long p = 2; p * p <= N; p++) {
		if (N % p == 0) {
			return false;
		}
	}
	return true;
}

vector<bool> sieve(int N) {
	assert(N >= 0);
	vector<bool> res(N + 1, true);
	res[0] = false;
	if (N >= 1) res[1] = false;
	for (int p = 2; p <= N; p++) {
		if (res[p]) {
			for (int i = 2 * p; i <= N; i += p) {
				res[i] = false;
			}
		}
	}
	return res;
}

vector<int> prime(int N) {
	vector<int> res;
	vector<bool> se = sieve(N);
	for (int p = 2; p <= N; p++) {
		if (se[p]) res.push_back(p);
	}
	return res;
}

int main() {
	const int N_max = 1e5 + 7;
	vector<bool> is_p = sieve(N_max);
	vector<bool> a(N_max); // a[i]:iが条件を満たすか
	vector<int> b(N_max); // b[i]:[0,i)の条件を満たす数の個数
	for (int i = 1; i <= 1e5; i++) {
		if (i % 2 and is_p[i] and is_p[(i + 1) / 2]) {
			a[i] = true;
		}
		b[i + 1] = b[i] + a[i];
	}

	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int l, r; cin >> l >> r;
		cout << b[r + 1] - b[l] << endl;
	}
}

Measured memory_bytes: 3584
//Author: A_S_M_M@sud_P@rvez
#include<bits/stdc++.h>
using namespace std;
#define    MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define    For(i,n) for(int i=0;i<n;i++)
#define    rFor(i,n) for(int i=n-1;i>=0;i--)
#define    forn(i,n) for(int i=1;i<=n;i++)
#define    fors(i,s) for(int i=0;i<s.size();i++)
#define    all(v) v.begin(),v.end()
#define    gcd(a, b) __gcd(a , b)
#define    lcm(a,b) (a*(b/__gcd(a,b)))
#define    test   int t;cin>>t;for(int l=0;l<t;l++)
#define    min3(a,b,c)     min(a,min(b,c))
#define    max3(a,b,c)     max(a,max(b,c))
#define    min4(a,b,c,d)   min(min(a,b),min(c,d))
#define    max4(a,b,c,d)   max(max(a,b),max(c,d))
#define    Max(a)  *max_element(a,a+sizeof(a)/sizeof(a[0]))
#define    Min(a)  *min_element(a,a+sizeof(a)/sizeof(a[0]))
#define    nl     "\n"
#define    End    return 0 
#define    gt     greater<int>()
#define    ll     long long 
#define    mp     make_pair
#define    pb     push_back
#define    vi     vector<int>
#define    vl     vector<ll>
#define    mod    1000000007
#define    sp(n)  fixed<<setprecision(n)
#define    pi     acos(-1)

int main()
{
MP;
    //test
    {
        int n,c=0;
        cin>>n;
        int a[n];
        For(i,n)cin>>a[i];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    if(a[i]!=a[j]&&a[j]!=a[k]&&a[i]!=a[k] and 
                    a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[j]+a[k]>a[i])c++;
                }
            }
        }
        cout<<c;
    }
    
End;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define elif(a) else if(a)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,a[3];
  FOR(i,3) cin>>a[i];
  sort(a,a+3);
  cout<<a[0]+a[1]<<endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set> 
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
#define db double
#define inf 301
#define INF (int)1e8 
#define mod (int)(1e9+7)
#define pi acos(-1)
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
 
const int lim=18;
ll P10[20],cnt[20];
 
void pre_work(void){
    P10[0]=1LL;
    for (int i=1;i<=lim;i++){
        P10[i]=P10[i-1]*10LL;
    }
    for (int i=0;i<=9;i++){
        for (int j=0;j<=9;j++){
            cnt[i-j+10]++;
        }
    }
    return;
}
 
ll D,ans=0;
 
void dfs(int step,ll x,ll sum,int len){
    if (step>len/2-1){
        if (len&1){
            sum*=10LL;
        }
        if (x==D){
            ans+=sum;
        }
        return;
    }
    ll now=-9;
    while (now<=9 && x+now*(P10[len-step-1]-P10[step])<=D){
        now++;
    }
    now--;
    dfs(step+1,x+now*(P10[len-step-1]-P10[step]),sum*(cnt[now+10]-(step==0 && now>=0)),len);
    now++;
    if (now>9){
        return;
    }
    dfs(step+1,x+now*(P10[len-step-1]-P10[step]),sum*(cnt[now+10]-(step==0 && now>=0)),len);
    return;
}
 
int main(){
    rd(D)
    pre_work();
    for (int i=1;i<=18;i++){
        dfs(0,0LL,1LL,i);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	long long int A, B;

	cin >> A >> B;

	long long int big = max(A, B);
	long long int small = min(A, B);

	if (A % 2 != B % 2)
	{
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}

	long long int K;

	for (long long int i = small; ; i++)
	{
		if ((i - small) == (big - i))
		{
			K = i;
			break;
		}
	}

	cout << K << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/math/common_factor.hpp>
using namespace std;
using u64 = uint64_t;

int main() {
	u64 K;
	cin >> K;
	
	vector<vector<u64>> gcds(K+1, vector<u64>(K+1));
	
	for(u64 a=1; a<=K; a++) {
		for(u64 b=a; b<=K; b++) {
			gcds[a][b] = boost::math::gcd(a, b);
			gcds[b][a] = gcds[a][b];
		}
	}
	
	u64 ans = 0;
	
	for(u64 a=1; a<=K; a++) {
		for(u64 b=1; b<=K; b++) {
			u64 gcd_ab = gcds[a][b];
			
			for(u64 c=1; c<=K; c++) {
				ans += gcds[c][gcd_ab];
			}
		}
	}
	
	cout << ans;
	return 0;
}


Measured memory_bytes: 3936
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <list>



int main(int,char**){
	int t;
	std::cin >> t;
	while(t--){
		int n;
		std::cin >> n;
		int n2(n);
		std::vector<int> vec;
		vec.reserve(n);
		while(n2--){
			int hight;
			std::cin >> hight;
			vec.push_back(hight);
		}
		int up(0),down(0);
		for(int i(0);i<n-1;++i){ // 最後の一つ前まで
			int tempMove(vec[i+1]-vec[i]);
			if(!tempMove) continue;
			if(tempMove>0){
				if(tempMove>up) up=tempMove;
			}else{
				if(std::abs(tempMove)>down) down=std::abs(tempMove);
			}
		}
		std::cout << up << ' ' << down<<std::endl; 
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5+5, M = 105;
string s;
ll dp[N][M][2];
int n, D, MOD = 1e9+7;

ll f(int i, int mod, bool flag){
  if(i == n)return mod == 0;
  ll &ans = dp[i][mod][flag];
  if(ans != -1)return ans;
  ans = 0;
  int lim = flag ? 9: s[i]-'0';
  forn(j, 0, lim+1){
    int nxt_mod = (mod+j)%D;
    int nxt_flag = flag | (j < s[i]-'0');
    ans = (ans + f(i+1, nxt_mod, nxt_flag))%MOD;
  }
  return ans;
}


int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> s >> D;
  n = s.size();
  memset(dp, -1, sizeof dp);
  cout << (f(0, 0, 0)-1+MOD)%MOD << endl;

}





Measured memory_bytes: 168508
#include<stdio.h>
#include<string.h>

int main(void){
    char now[5];
    char day[7][5] = {"SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN"};
    scanf("%s", now);
    for(int i = 0; i < 7; i++){
        if(strcmp(day[i], now) == 0){
            printf("%d\n", i + 1);
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(a, b, c) for(ll c=a;c<b;c++)
#define re(b, c) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll a, n;std::cin >> n;
  multiset<ll> s;
  ll ans = 0;
  for(int i=0;i<n;i++) {
    std::cin >> a;
    ans ^= a;
    s.insert(a);
  }
  ll c = 0;
  for(int i=30;i>=0;i--){
    if(ans>=(1<<i)){
      c++;
      if(s.find((1<<i))==s.end()){
        std::cout << -1 << '\n';
        return 0;
      }
      auto itr = s.find((1<<i));
      s.erase(itr);
      while(s.size()!=0){
        auto itr = --s.end();
        if(*itr>(1<<i)){
          ll tmp = *itr;
          s.erase(itr);
          s.insert(tmp%(1<<i));
        }else{
          break;
        }
      }
      for(int j=i;j>=0;j--) ans ^= (1<<j);
    }
  }
  std::cout << c << '\n';
  return 0;
}


Measured memory_bytes: 4992
N = int(input())
S = input()
if N <= 3:
    print('0')
else:
    minuscount = 0
    Rcount = 0
    Gcount = 0
    Bcount = 0 
    for i in range(N):
        if S[i] == 'R':
            Rcount += 1
        elif S[i] == 'G':
            Gcount += 1
        else:
            Bcount += 1
        for j in range(1,N):
            if i+2*j>=N:
                break
            if S[i] != S[i+j] and S[i+j] != S[i+2*j] and S[i+2*j] != S[i]:
                minuscount += 1

    print(Rcount*Gcount*Bcount-minuscount)

Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	int i=0,count=0,flag=0;
	while(i<3)
	{
		while(s[i]=='R'&&i<3)
		{
			count++;
			i++;
			flag=1;
		}
		if(flag==1)
		{
			break;
		}
		else
		{
			i++;
		}
	}
	cout<<count;	
	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long A=100;
    long long count=0;
    long long X;
    cin >> X;
    while(1){
        A*=1.01;
        count++;
        if(A>=X){
            break;
        }
    }
    cout << count << endl;
}

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

int mod = 10007;
int dp[1010][8];

map<char,int> id = { {'J',0}, {'O',1}, {'I',2} };

int main(){
  int n;
  string s;

  cin >> n >> s;
  dp[0][1] = 1;
  
  rep(i,n)rep(j,8)rep(k,8){
    if( (j&k) && ((k>>id[s[i]])&1) ){
      (dp[i+1][k] += dp[i][j]) %= mod;
    }
  }

  rep(i,7)(dp[n][7] += dp[n][i]) %= mod;
  cout << dp[n][7] << endl;
}

Measured memory_bytes: 1244
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
   	int n,m;cin>>n;
	debug("debug test\n");
	vint a(n);
	rep(i, n){
		cin>>a[i];
	}
	sort(all(a));
	reverse(all(a));
	int ans = 0;
	rep(i, n){
		if(i%2==0){
			ans += a[i];
		}else{
			ans -= a[i];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

template <typename T>
vector<T> Dijkstra(int s, vector<vector<pair<int, T>>> & G, const T INF = 1e9){
    using P = pair<T, int>;
    int V = G.size();
    vector<T> dist(V, INF);
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s] = 0;
    que.emplace(0, s);
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v] < p.first) continue;
        for(int i = 0; i < G[v].size(); i++){
            int to = G[v][i].first;
            T cost = G[v][i].second;
            if(dist[to] > dist[v] + cost){
                dist[to] = dist[v] + cost;
                que.emplace(dist[to], to);
            }
        }
    }
    return dist;
}

signed main(){
    int n,u,v;
    cin >> n >> u >> v;
    u--;
    v--;
    vector<vector<P>> G(n);
    REP(i,n - 1){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace_back(b, 1);
        G[b].emplace_back(a, 1);
    }
    vector<int> distt = Dijkstra<int>(u, G);
    vector<int> dista = Dijkstra<int>(v, G);
    int ans = 0;
    REP(i,n){
        if(distt[i] <= dista[i]){
            ans = max(ans, dista[i] - 1);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7436
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>


using namespace std;



int max_profit(vector<int>& profit){
  int min_val = profit[0];
  int max_val = INT_MIN;

  int i  = 1;
  while(i < profit.size()){
    max_val = max(max_val, profit[i] - min_val); // update the max val
    min_val = min(min_val, profit[i]); // update the min val in [1 ... i]
    i++;
  }


  return  max_val;
}



int main(){
  int n;
  scanf("%d", &n);

  vector<int> data;
  int r;
  while(n > 0){
    scanf("%d", &r);
    data.push_back(r);
    n--;
  }


  cout << max_profit(data) << endl;

  
  return 0;
}

Measured memory_bytes: 3916