akhauriyash/Code-Regression huggingface dataset:
import sys

dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
w = 0
h = 0


def main():
    global w, h

    while True:
        count = 0
        w, h = map(int, input().split())
        if w is 0 and h is 0:
            break
        field = []
        [field.append(list(map(int, input().split()))) for _ in range(h)]

        for y in range(h):
            for x in range(w):
                if field[y][x] == 1:
                    dfs(field, x, y)
                    count += 1

        print(count)


def dfs(field, x, y):
    field[y][x] = 0

    for dx_, dy_ in zip(dx, dy):
        next_x = x + dx_
        next_y = y + dy_
        if next_x < 0 or next_y < 0 or next_x >= w or next_y >= h or field[next_y][next_x] == 0:
            continue
        dfs(field, next_x, next_y)


if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    main()

Measured memory_bytes: 10208
n = int(input())
w = list(map(int, input().split()))

ref = sum(w)

for i in range(n - 1):
    s1 = sum(w[0: i + 1])
    s2 = sum(w[i + 1: n])
    diff = abs(s1 - s2)
    if diff <=  ref:
        ref = diff

print(ref)

Measured memory_bytes: 3060
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

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

vector<ll> g[3];
void solve() {
	int a, b, c, kk;
	cin >> a >> b >> c >> kk;
	g[0].resize(a);
	g[1].resize(b);
	g[2].resize(c);
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < g[i].size(); j++) {
			cin >> g[i][j];
		}
		sort(g[i].begin(), g[i].end());
		reverse(g[i].begin(), g[i].end());
	}
	priority_queue<ll> q;
	for(int i = 0; i < a; i++) {
		for(int j = 0; j < b; j++) {
			for(int k = 0; k < c; k++) {
				ll curr = g[0][i] + g[1][j] + g[2][k];
				if(q.size() == kk && curr <= -q.top()) break;
				q.push(-curr);
				if(q.size() > kk) q.pop();
			}
		}
	}
	vector<ll> ret;
	while(q.size()) {
		ret.push_back(-q.top());
		q.pop();
	}
	sort(ret.begin(), ret.end());
	reverse(ret.begin(), ret.end());
	for(ll out: ret) cout << out << "\n";
}

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


Measured memory_bytes: 384
#define REP(i, n) for (int i = 0; i < (n); ++i)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

signed main() {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  pair<long long, long long> shops[N];
  REP(i, N) {
    cin >> shops[i].first >> shops[i].second;
  }
  sort(shops, shops + N);
  long long ans = 0;
  REP(i, N) {
    long long price = shops[i].first;
    long long num = shops[i].second;
    if (M > num) {
      M -= num;
      ans += price * num;
      continue;
    }
    ans += M * price;
    break;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
S = input()
T = input()

ans = 1000
for i in range(len(S)-len(T)+1):
    s = S[i:i+len(T)]
    n = 0
    for j in range(len(s)):
        ss = s[j]
        if T[j] != ss:
            n += 1
    ans = min(ans,n)
print(ans)

Measured memory_bytes: 67568
#include <iostream>
#include <iomanip> //setprecision()
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using ll = long long;
using namespace std;

double Mcos(double k){return cos(k*atan(1.0)*4/180);}

void monmo(){
    
}

int main() {
    int n;
    map<int,int> m;
    cin>>n;
    for(int i=1;i<=100;i++){
        for(int j=i;j<=100;j++){
            for(int l=j;l<=100;l++){
                if((pow(i,2)+pow(j,2)+pow(l,2)+i*j+j*l+l*i)<=n){
                    m[pow(i,2)+pow(j,2)+pow(l,2)+i*j+j*l+l*i]+=6;
                    if(i==j && j==l && l==i)m[pow(i,2)+pow(j,2)+pow(l,2)+i*j+j*l+l*i]-=5;
                    else if(i==j || j==l || l==i)m[pow(i,2)+pow(j,2)+pow(l,2)+i*j+j*l+l*i]-=3;
                }
                else break;
            }
            if((pow(i,2)+pow(j,2))>n)break;
        }
        if(pow(i,2)>n)break;
    }
    for(int i=1;i<=n;i++){
        cout<<m[i]<<endl;
    }
}


Measured memory_bytes: 3896
import sys, math
from functools import lru_cache
import numpy as np
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime


def main():
    Q = ii()
    l, r = i2(Q)
    m = max(r)

    dp = [0]*(m+1)
    check = makePrimeChecker(m)

    for i in range(1, m+1):
        if check[i] and check[(i+1)//2]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]

    for ll, rr in zip(l, r):
        print(dp[rr]-dp[ll-1])




if __name__ == '__main__':
    main()


Measured memory_bytes: 53540
#include <iostream>
#include <vector>
#include <deque>
#define MAXN 200005
#define mod 1000000007
using namespace std;

int n, dad[MAXN], crtDp, idxDp[MAXN], lvlCount[MAXN];
int pw2[MAXN];
vector<int> G[MAXN];
deque<int> dp[MAXN][3];

void precalc() {
    pw2[0] = 1;
    for (int i = 1; i < MAXN; ++i)
        pw2[i] = (pw2[i - 1] << 1) % mod;
}

void DFS(int u, int lvl) {
    ++lvlCount[lvl];
    if (G[u].empty()) {
        idxDp[u] = (++crtDp);
        dp[idxDp[u]][0].push_back(1);
        dp[idxDp[u]][1].push_back(1);
        dp[idxDp[u]][2].push_back(0);
        return;
    }

    int bestSon = G[u][0];
    for (auto x: G[u]) {
        DFS(x, lvl + 1);
        if (dp[idxDp[x]][0].size() > dp[idxDp[bestSon]][0].size())
            bestSon = x;
    }

    idxDp[u] = idxDp[bestSon];
    int idxu = idxDp[u];
    int lvlMax = 0;
    for (auto x: G[u]) {
        if (x == bestSon)
            continue;

        int idx = idxDp[x];
        int lvl = (int) dp[idx][0].size();
        lvlMax = max(lvlMax, lvl);
        for (int i = 0; i < lvl; ++i) {
            int x0 = dp[idxu][0][i];
            int x1 = dp[idxu][1][i];
            int x2 = dp[idxu][2][i];

            dp[idxu][0][i] = (1LL * x0 * dp[idx][0][i]) % mod;
            dp[idxu][1][i] = (1LL * x1 * dp[idx][0][i] + 1LL * x0 * dp[idx][1][i]) % mod;
            dp[idxu][2][i] = (1LL * x1 * dp[idx][1][i] % mod + 1LL * x2 * (dp[idx][0][i] + dp[idx][1][i])) % mod;
        }
    }

    for (int i = 0; i < lvlMax; ++i) {
        dp[idxu][0][i] = (dp[idxu][0][i] + dp[idxu][2][i]) % mod;
        dp[idxu][2][i] = 0;
    }

    dp[idxu][0].push_front(1);
    dp[idxu][1].push_front(1);
    dp[idxu][2].push_front(0);
}

int main() {
    ios::sync_with_stdio(0);
    precalc();

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> dad[i];
        G[dad[i]].push_back(i);
    }

    DFS(0, 0);

    int sol = 0;
    int idx = idxDp[0];
    int lvl = (int) dp[idx][1].size();

    for (int i = 0; i < lvl; ++i)
        sol = (sol + 1LL * dp[idx][1][i] * pw2[n + 1 - lvlCount[i]]) % mod;
    
    cout << sol << "\n";

    return 0;
}

Measured memory_bytes: 482048
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        System.out.println(solve(N));

        sc.close();
    }

    static int solve(int N) {
        int result = N;
        while (String.valueOf(result).chars().distinct().count() != 1) {
            ++result;
        }

        return result;
    }
}

Measured memory_bytes: 36080
N = int(input())
num = list(map(int,input().split()))
cnt = 0
flag = False
num_min = 10**8
for i in range(N):
	if(i == 0):
		cnt+=1
		continue
	num_min = min(num_min,num[i-1])
	if (num[i] <= num_min):
		cnt+=1
print(cnt)

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

using namespace std;

#define INF 999999999

inline int read(){
   int w=1,s=0;
   char ch=getchar();
   while(ch<'0'||ch>'9') {if (ch=='-') w=-1;ch=getchar();} 
   while(ch>='0'&&ch<='9')  s=s*10+ch-'0',ch=getchar();
   return s*w;
}

int main(){
    int n=read();
    if (n==1) cout<<" Hello World";
    else cout<<read()+read();
return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}

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

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}
	int size(int a) {
		return par[root(a)];
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};


int main() {
	ll a, b;
	cin >> a >> b;
	map<ll, int> A, B;
	for (ll i = 2; i * i <= a; i++) {
		if(a%i==0){
			while (a % i == 0) {
				a /= i;
				A[i] = 1;
			}
		}
	}
	if (a > 1)A[a] = 1;
	for (ll i = 2; i * i <= b; i++) {
		if (b % i == 0) {
			while (b % i == 0) {
				b/= i;
				B[i] = 1;
			}
		}
	}
	ll ans = 1;
	if (b > 1)B[b] = 1;
	for (auto x : A) {
		if (B[x.first] == A[x.first]) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int N, M, R, r[10], dist[201][201] = {}, bit[10] = {0, 1, 2, 4, 8, 16, 32, 64, 128}, dp[10][256];

int recursion(int n, int rest)
{
	if (dp[n][rest] >= 0) return dp[n][rest];
	else if (rest == 0) {
		dp[n][rest] = 0;
		return dp[n][rest];
	} else dp[n][rest] = 1 << 29;
	
	int i;
	for (i = 1; i <= R; i++) {
		if ((rest | bit[i]) == rest && recursion(i, rest ^ bit[i]) + dist[r[n]][r[i]] < dp[n][rest]) dp[n][rest] = recursion(i, rest ^ bit[i]) + dist[r[n]][r[i]];
	}
	return dp[n][rest];
}

int main()
{
	int i, j, u, v, w, c;
	scanf("%d %d %d", &N, &M, &R);
	for (i = 1; i <= R; i++) scanf("%d", &(r[i]));
	for (i = 1; i <= M; i++) {
		scanf("%d %d %d", &u, &w, &c);
		dist[u][w] = c;
		dist[w][u] = c;
	}
	for (u = 1; u < N; u++) {
		for (w = u + 1; w <= N; w++) {
			if (dist[u][w] == 0) {
				dist[u][w] = 1 << 29;
				dist[w][u] = 1 << 29;
			}
		}
	}
	for (v = 1; v <= N; v++) {
		for (u = 1; u < N; u++) {
			for (w = u + 1; w <= N; w++) {
				if (dist[u][v] + dist[v][w] < dist[u][w]) {
					dist[u][w] = dist[u][v] + dist[v][w];
					dist[w][u] = dist[u][v] + dist[v][w];
				}
			}
		}
	}
	
	int ans = 1 << 29, b = (1 << R) - 1;
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 256; j++) dp[i][j] = -1;
	}
	for (i = 1; i <= R; i++) if (recursion(i, b ^ bit[i]) < ans) ans = recursion(i, b ^ bit[i]);
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,a[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1,a+n+1,greater<int>());
	for(int i=1;i<=n;++i)
		if(i+1>a[i+1]){
			int tD=(upper_bound(a+1,a+n+1,i,greater<int>())-a-i-1)&1,tW=(a[i]-i)&1;
			if(tD||tW)cout<<"First\n";
			else cout<<"Second\n";
			return 0;
		}
	return 0;
}


Measured memory_bytes: 640
import numpy as np


N,K,Q=input().split()

N=int(N)
K=int(K)
Q=int(Q)
arr=np.full(N, K)
arr-=Q
for i in range(Q):
	A=int(input())
	arr[A-1]+=1
for j in arr:
	if j>0:
		print("Yes")
	else:
		print("No")

Measured memory_bytes: 15288
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();
		
		String intValue = String.valueOf(N);
		if (intValue.indexOf("9") > -1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

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

for i in range(1, N+1):
    for j in reversed(range(1, i)):
        if A[j] < A[j-1]:
            tmp = A[j]
            A[j] = A[j-1]
            A[j-1] = tmp
        else:
            break

    result = [str(k) for k in A]
    print(' '.join(result))



Measured memory_bytes: 5604
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main() {
	int N,x;
	cin >> N >> x;
	if(x==1||x==2*N-1){
		cout << "No";
		return 0;
	}
	cout << "Yes" << endl;
	for(int i=1;i<=2*N-1;i++){
		int v=(x+N+i-1)%(2*N-1);
		if(v==0){
			v=2*N-1;
		}
		cout << v << endl;
	}
}


Measured memory_bytes: 1536
#include <stdio.h>
 
int total[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30};
 
int Sum(int x) {
  int i, sum = 0;
 
  if(x < 0) {
    return 0;
  }
 
  for(i = 0; i < x; i ++) {
    sum += total[i];
  }
 
  return sum;
}
 
int main() {
  int month, day;
  while(scanf("%d %d", &month, &day)) {
    if(month == 0) {
      break;
    }
 
    switch((Sum(month - 1) + day)%7) {
      case 0:
        printf("Wednesday\n");
        break;
 
      case 1:
        printf("Thursday\n");
        break;
 
      case 2:
        printf("Friday\n");
        break;
 
      case 3:
        printf("Saturday\n");
        break;
 
      case 4:
        printf("Sunday\n");
        break;
 
      case 5:
        printf("Monday\n");
        break;
 
      case 6:
        printf("Tuesday\n");
        break;
    }
  }
 
  return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <cctype>

using namespace std;

#define Int int64_t

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}



int main() {
	int h, w; cin >> h >> w;
	vector<string> letter(h);
	

	for (int i = 0; i < h; i++) {
		cin >> letter[i];
	}
	for (int i = 0; i < w + 2; i++) cout << "#";
	cout << endl;
	for (int i = 0; i < h; i++) {
		//cin >> letter[i];
		cout << "#" << letter[i] << "#" << endl;
	}
	for (int i = 0; i < w + 2; i++) cout << "#";

	cout << endl;
	return 0;
}

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

if D == 0:
    if N  == 100:
        print(N+1)
    else:
        print(N)
elif D==1:
    if N == 100:
        print((100 * N )+ 100)
    else :
        print(100*N)
else:
    if N ==100:
        print((10000*N)+10000)
    else:
        
        print(10000*N)


Measured memory_bytes: 9168
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define re register
#define ll long long
#define N 2005
#define MAXN 4000000
using namespace std;
inline int read(){
    int x=0,f=1;
    char c;
    for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
    if(c=='-') f=-1,c=getchar();
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    return x*f;
}
inline void print(int number){
    const int SIZE=25; int un=1,extent=0; char letter[SIZE];
    if(number<0){ number=-number; un=-1;}
    while(number){ letter[++extent]=number%10+'0'; number/=10;}
    if(!~un) putchar('-'); if(!extent) putchar('0');
    else while(extent) putchar(letter[extent--]);
}
inline int getint(){
    char ch = getchar(); int x = 0;
    while (ch < '0'|| ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x;
}
inline void putint(long long x){
	if (x > 9) putint(x / 10);
	putchar(x % 10 + '0');
}
//
const int Mod=1e9+7;
int n, k;
ll f[N][N],f1[MAXN+5],f2[MAXN+5];
inline ll Equation(int n,int m){
	return (((f1[m] * f2[n]) % Mod) * f2[m - n]) % Mod;
}
inline ll Answer(ll x,int P){
    ll ans = 1, m = x;
    while(P){
        if(P&1)
			(ans *= m) %= Mod;
        P >>= 1;
		(m*=m) %= Mod;
    }
    return ans;
}
int main(){
//    scanf("%d%d",&n,&k);
	n = read(), k = read();
	
    if(k==1)//特判 
	{
		printf("%d\n",1);
		return 0;
	}
	
    f1[0] = 1;
	for(re int i = 1; i <= MAXN; ++i)
		f1[i] = (f1[i-1] * i) % Mod;
		
    f2[MAXN] = Answer(f1[MAXN], Mod-2);
    
	for(re int i = MAXN - 1; i>=0; --i)
		f2[i] = (f2[i + 1] * (i + 1)) % Mod;
		
    f[0][0]=1;
    
    for(re int i = 1;i <= n; ++i){
        for(re int j = 0;j <= i; ++j){
            f[i][j] = f[i - 1][j];
            if(!j)
				continue;
            (f[i][j] += f[i][j - 1] * (n - j + 1) % Mod * Equation(k - 2,n - i + (n - j + 1) * (k - 1) - 1) % Mod) %= Mod;
        }
    }
//    printf("%lld\n",f[n][n]);
	print(f[n][n]);
    return 0;
}

Measured memory_bytes: 94080
//
// うまく数字が合わない時は計算式をよく確認しましょう。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    ll N, sum = 0;
    cin >> N;
    vector<ll> A(N + 2);
    A[0] = 0;
    repi(i, N + 1, 1)
    {
        cin >> A[i];
        sum += abs(A.at(i - 1) - A.at(i));
    }
    A[N + 1] = 0;
    sum += abs(A.at(N));

    repi(i, N + 1, 1)
    {
        cout << sum + abs(A.at(i - 1) - A.at(i + 1)) - abs(A.at(i - 1) - A.at(i)) - abs(A.at(i) - A.at(i + 1)) << endl;
    }
    return 0;
}

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

# define debug(x) cerr << #x << " = " << x << endl

using namespace std;

const int N = 200000 + 77 , Mod = 1000000007;

inline int Pow(int x , long long y) {
   int r = 1;
   for(;y;y >>= 1 , x = x * 1ll * x % Mod)
      if(y & 1)
         r = r * 1ll * x % Mod;
   return r;
}

int n , A , sz[N] , P2[N];
vector < int > adj[N];
void dfs(int v , int prev = - 1) {
   sz[v] = 1;
   vector < int > S;
   for(int u : adj[v])
      if(u != prev)
         dfs(u , v) , sz[v] += sz[u] , S.push_back(sz[u]);
   if(v != 1)
      S.push_back(n - sz[v]);
   int ways = 1;
   for(int x : S)
      ways = (P2[x] - 1 + ways) % Mod;
   ways = (P2[n - 1] - ways + Mod)% Mod;
   A = (A + ways * 1ll * Pow(2 , Mod - 2)) % Mod;
}
int main() {
   P2[0] = 1;
   for(int i = 1;i < N;++ i)
      P2[i] = P2[i - 1] * 2 % Mod;
   scanf("%d" , & n);
   for(int v , u , i = 1;i < n;++ i)
      scanf("%d %d" , & v , & u) , adj[v].push_back(u) , adj[u].push_back(v);
   dfs(1);
   A = A * 1ll * Pow(P2[n - 1] , Mod - 2) % Mod;
   printf("%d\n" , A);
   return 0;
}


Measured memory_bytes: 28544
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

n, x = map(int, input().split())
X = list(map(int, input().split()))
L = [0] * n
for i in range(n):
    L[i] = abs(x - X[i])
ans = L[0]
for j in range(1, n):
    ans = gcd(ans, L[j])
print(ans)


Measured memory_bytes: 14252
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

				Scanner sc = new Scanner(System.in);
				int n = sc.nextInt();
				List<List<Integer>> A = new ArrayList<>();
				for (int i = 0; i <= n; i++) {
					List<Integer> a = new ArrayList<>();
					A.add(a);
				}
				int z = sc.nextInt();
				for (int i = 0; i < z; i++) {
					int q = sc.nextInt();
					if (q == 0) {
						int x = sc.nextInt();
						int t = sc.nextInt();
						List<Integer> a = A.get(x);
						a.add(t);
					}
					if (q == 1) {
						int x = sc.nextInt();
						if (A.get(x).size()!= 0) {
							System.out.println(A.get(x).get(A.get(x).size()-1));
						}
					}
					if (q == 2) {
						int x = sc.nextInt();
						if (A.get(x).size()!= 0) {
						A.get(x).remove(A.get(x).size()-1);
						}
					}
				}
				sc.close();
			}
}




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

int main() {
  int N;
  cin >> N;
  int a = N / 1000;
  int b = (N - a * 1000) / 100;
  int c = (N - a * 1000 - b * 100) / 10;
  int d = N - a * 1000 - b * 100 - c * 10;

  if ((a == b && a == c) || (b == c && b == d)) {
      cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 384
<?php
list($h, $w) = ints();
for ($i = 0; $i < $h; ++$i) list($s[]) = strs();
for ($i = 0; $i < $h; ++$i) {
    for ($j = 0; $j < $w; ++$j) {
        if ($s[$i][$j] === '#') {
            $a[$i][$j] = '#';
            continue;
        }
        $a[$i][$j] = 0;
        for ($l = max(0, $i - 1); $l <= min($h - 1, $i + 1); ++$l) {
            for ($m = max(0, $j - 1); $m <= min($w - 1, $j + 1); ++$m) {
                if ($s[$l][$m] === '#') $a[$i][$j]++;
            }
        }
    }
    echo implode('', $a[$i]) . PHP_EOL;
}

function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}
function strs()
{
    return explode(' ', trim(fgets(STDIN)));
}


Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  int count = 0;
  for(int i = A; i <= B ; i++) {
    int a = i % 10;
    int b = (i /10) % 10;
    int d = (i /10 /10 /10) % 10;
    int e = (i /10 /10 /10 /10) % 10;
    if(a == e && b == d) {
      count++;
    }
  }
  cout << count << endl;
}
    

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int inf = 1012345678;
#define REP(i, a, b) for(ll i = ll(a); i <= ll(b); i++)
ll range_btw_nums(ll a,ll b)
{
	ll cnt=0;
	REP(i,a,b)
	{
		cnt++;
	}
	return cnt;
}
int main()
{
	ll a,b;
	cin>>a>>b;
	if(a<0 && b>0)
		cout<<"Zero";
	else if(a==0 || b==0)
		cout<<"Zero";
	else if(a>0 && b>0)
		cout<<"Positive";
	else if(a<0 && b<0)
	{
		if(range_btw_nums(a,b)%2==0)
			cout<<"Positive";
		else if(range_btw_nums(a,b)%2!=0)
			cout<<"Negative";
	}
	//cout<<endl;
	//cout<<"range "<<range_btw_nums(a,b);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
main(){
  stack<int> num;
  char now[15];
  long long ans=0;
  while(cin>>now){
    if(now[0]=='+'){
      int a,b;
      a=num.top();num.pop();
      b=num.top();num.pop();
      num.push(a+b);
    }
    else if(now[0]=='-'){
      int a,b;
      a=num.top();num.pop();
      b=num.top();num.pop();
      num.push(b-a);
    }
    else if(now[0]=='*'){
      int a,b;
      a=num.top();num.pop();
      b=num.top();num.pop();
      num.push(a*b);
    }
    else if(now[0]=='/'){
      int a,b;
      a=num.top();num.pop();
      b=num.top();num.pop();
      num.push(b/a);
    }
    else{
      num.push(atoi(now));
    }
  }
  cout<<num.top()<<endl;
  num.pop();
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 100010;
int A[MAX_N], B[MAX_N], C[MAX_N], D[MAX_N];
int parent[MAX_N];
int size[MAX_N];

int find_parent(int u) {
	if(parent[u] == -1) return u;
	return parent[u] = find_parent(parent[u]);
}

void merge(int u, int v) {
	u = find_parent(u);
	v = find_parent(v);
	if(u == v) return;
	parent[v] = u;
	size[u] += size[v];
}

void run() {
	int n, m, k, i;
	cin >> n >> m >> k;
	for(i=0; i<MAX_N; i++) {
		A[i] = B[i] = C[i] = D[i] = -1;
		parent[i] = -1;
		size[i] = 1;
	}
	for(i=0; i<m; i++) {
		cin >> A[i] >> B[i];
		--A[i]; --B[i];
		merge(A[i], B[i]);
	}
	for(i=0; i<k; i++) {
		cin >> C[i] >> D[i];
		--C[i]; --D[i];
	}
	vector<int> ret(n, 0);
	
	for(i=0; i<n; i++)
		ret[i] = size[find_parent(i)] - 1;

	for(i=0; i<m; i++) {
		--ret[A[i]];
		--ret[B[i]];
	}
	for(i=0; i<k; i++) {
		if(find_parent(C[i]) == find_parent(D[i])) {
			--ret[C[i]];
			--ret[D[i]];
		}
	}
	for(i=0; i<n; i++)
		cout << ret[i] << " ";
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);		
	int t = 1;
	// cin >> t;
	while(t--) {
		run();
	}
}


Measured memory_bytes: 4224
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    ll N, Z, W;
    cin >> N >> Z >> W;

    ll a[N];
    REP(i, N) cin >> a[i];

    if (N == 1) {
        cout << abs(W - a[0]) << endl;
    } else {
        cout << max(abs(W - a[N-1]), abs(a[N-1] - a[N-2])) << endl;
    }

}


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

int main() {
	string S; cin >> S;
	bool p=false;
	for(int i=0; i+1<S.size(); ++i){
	    if(S[i]=='A' && S[i+1]=='C'){
	        p=true;
	        break;
	    }
	}
	if(p) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    k = int(input())
    a, b = list(map(int, input().split()))
    ans = 0
    for i in range(a, b + 1):
        if i % k == 0:
            ans = 1
    print("OK" if ans else "NG")
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 9848
#include<iostream>
using namespace ::std;
int main(){
int N,K,Q;
cin>>N>>K>>Q;
int point[N];
for(int i=0;i<N;i++){
    point[i]=K-Q;
}
int A=0;
for(int i=0;i<Q;i++){
cin>>A;
point[A-1]++;
}
for(int i=0;i<N;i++){
    // point[i]-=(K-Q);
    if(point[i]<=0)
cout<<"No"<<endl;
else 
cout<<"Yes"<<endl;    
    }

}

Measured memory_bytes: 1024
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;

class Node {
    Integer id;
    Integer parentId;
    Integer depth;
    Integer type;
    List<Integer> childrenIds;
}


class Main {
    static Map<Integer, Node> nodes = new HashMap<>();

    static final Map<Integer, String> types = new HashMap<Integer, String>() {
      {
          put(1, "root");
          put(2, "internal node");
          put(3, "leaf");
      }
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            Integer id = sc.nextInt();
            int m = sc.nextInt();

            Node node = nodes.get(id);
            if (node == null) {
                node = new Node();
                node.id = id;
                node.type = 1;
                node.depth = 0;
                node.parentId = -1;
                nodes.put(id, node);
            } else if (m != 0) {
                node.type = 2;
            } else {
                node.type = 3;
            }

            Node parentNode = nodes.get(node.parentId);
            if (parentNode != null) {
                node.depth = parentNode.depth + 1;
            }

            List<Integer> childrenIds = new ArrayList<>();

            for (int j = 0; j < m; j++) {
                Integer childrenId = sc.nextInt();
                Node childrenNode = nodes.get(childrenId);
                if (childrenNode == null) {
                    childrenNode = new Node();
                    childrenNode.id = childrenId;
                    nodes.put(childrenId, childrenNode);
                }
                childrenNode.parentId = node.id;
                childrenNode.depth = new Integer(node.depth.intValue() + 1);
                if (childrenNode.childrenIds == null || childrenNode.childrenIds.isEmpty()) {
                    childrenNode.type = 3;
                } else {
                    childrenNode.type = 2;
                }
                childrenIds.add(childrenId);
            }
            node.childrenIds = childrenIds;
        }

        for (Integer i = 0; i < n; i++) {
            Node node = nodes.get(i);
            System.out.printf("node %d: parent = %d, depth = %d, %s, [%s]\n",
                    node.id,
                    node.parentId,
                    node.depth,
                    types.get(node.type),
                    node.childrenIds.stream().map(elm -> elm.toString()).collect(Collectors.joining(", ")));
        }
    }
}



Measured memory_bytes: 194644
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<algorithm>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
int main(void){
    int a,b;
    string s;
    cin>>a>>b;
    cin>>s;
    if(s.size()==a+b+1 && s[a]=='-') {
        rep(j,s.size()){
            if(j!=a && s[j]=='-' ){
                cout<<"No"<<endl;
                return 0;
            }
        }
        cout<<"Yes"<<endl;
    }    
    else cout<<"No"<<endl;
    return 0;
}

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

using namespace std;
using i64 = long long;
using f64 = double;

#define FOR(i, s, n) for (size_t i = (s); i < (size_t)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()

#define BLACK '#'

template <typename T, typename U>
inline bool chmax(T &a, U b) {
  return a < b ? (a = b, true) : false;
}

template <typename T, typename U>
inline bool chmin(T &a, U b) {
  return a > b ? (a = b, true) : false;
}

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  auto matrix = vector<vector<char>>(h, vector<char>(w));
  for (auto &row : matrix) {
    for (auto &c : row) {
      cin >> c;
    }
  }

  auto ans = 0;
  REP (mask_row, (1 << h)) {
    REP (mask_col, (1 << w)) {
      auto black_sum = 0;
      REP (i, h) {
        auto row_selected = ((mask_row >> i) & 0b000001) == 1;
        REP(j, w) {
          auto col_selected = ((mask_col >> j) & 0b000001) == 1;
          if (!row_selected && !col_selected && matrix[i][j] == BLACK) {
            black_sum++;
          }
        }
      }
      if (black_sum == k) {
        ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3224
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String o = input.readLine( );
		String e = input.readLine( );
		String[] oList = o.split("");
		String[] eList = e.split("");
		int max = Math.min(o.length(), e.length());
		for(int i=0; i<max; i++){
			System.out.print(oList[i]);
			System.out.print(eList[i]);
		}
		if(o.length()>e.length()){
			System.out.println(oList[max]);
		}else{
			System.out.println();
		}
	}
}


Measured memory_bytes: 21460
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<algorithm>

using namespace std;

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

    cout << (a + b) / 2 + (a + b) % 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<vector>
#include<string>
#include <iostream>
using namespace std;
int main()
{
	int n,a[100],count = 0;
	cin>>n;
	for (int i = 0; i < n; i++)
	{
		cin>>a[i];
		if (a[i] % 2 == 0)
		{
			count ++;
		}
	}
	cout<<count<<endl;
    return false; 
}


Measured memory_bytes: 3112
#include<iostream>
using namespace std;

int main(){
  int n,a[1100],cnt=0;
  double sum=0,m;
  cin>>n>>m;

  for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; }
  double j=sum/(4*m);
  for(int i=0;i<n;i++){
    if(j<=a[i]) cnt++;
  }
  if(cnt>=m) cout<<"Yes";
  else cout<<"No";
}


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

typedef long long ll;
const ll INF = 1LL << 30;

int n, k;
int h[100010];

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

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

    sort(h, h+n);

    ll res = INF;
    for (int i = 0; i < n-k+1; i++){
        res = min(res, (ll)(h[i+k-1] - h[i]));
    }

    cout << res << endl;
}

Measured memory_bytes: 640
a=list(map(int,input().split()))
ans=[10**8]*6
ans[0]=abs(a[1]-a[0])+abs(a[2]-a[1])
ans[1]=abs(a[2]-a[0])+abs(a[1]-a[2])
ans[2]=abs(a[0]-a[1])+abs(a[2]-a[0])
ans[3]=abs(a[2]-a[1])+abs(a[0]-a[2])
ans[4]=abs(a[0]-a[2])+abs(a[1]-a[0])
ans[5]=abs(a[1]-a[2])+abs(a[0]-a[1])
print(min(ans))

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

const int Maxn = 1e3 + 100;

int N;
LL Dp[20000 + 100];
struct info
{
	int w, s, v;
} A[Maxn];

inline int cmp (info a, info b) { return a.s + a.w < b.s + b.w; }

int Max;

inline void Solve ()
{
	sort(A + 1, A + N + 1, cmp);
	LL ans = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = A[i].s; j >= 0; --j)
		{
			Chkmax(Dp[j + A[i].w], Dp[j] + A[i].v);
			Chkmax(ans, Dp[j + A[i].w]);
		}
	cout<<ans<<endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i)
		A[i].w = read<int>(), A[i].s = read<int>(), A[i].v = read<int>(), Chkmax(Max, A[i].s);
}

int main()
{
#ifdef hk_cnyali
	freopen("X.in", "r", stdin);
	freopen("X.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

Measured memory_bytes: 384
//Kyu in AtCoder

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll,ll>;
using graph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int n;cin>>n;
    if(n<=599)cout<<"8"<<nnn;
    else if(n<=799)cout<<"7"<<nnn;
    else if(n<=999)cout<<"6"<<nnn;
    else if(n<=1199)cout<<"5"<<nnn;
    else if(n<=1399)cout<<"4"<<nnn;
    else if(n<=1599)cout<<"3"<<nnn;
    else if(n<=1799)cout<<"2"<<nnn;
    else if(n<=1999)cout<<"1"<<nnn;
    return 0;
}

Measured memory_bytes: 3644
def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7

ans = 0
for i, c in enumerate(C, 1):
  ans = (ans + (N-i+2) * c) % MOD

ans *= power(4, N-1)
ans %= MOD
print(ans)

Measured memory_bytes: 26176
#include <iostream> 
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<queue>
#include<deque>
#include<iomanip>
#include<sstream>
#include<cmath>
#include<bitset>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define req(i,n) for(int i = 1;i <=  n; i++)
#define rrep(i,n) for(ll i = n-1;i >= 0;i--)
#define ALL(obj) begin(obj), end(obj)
#define RALL(a) rbegin(a),rend(a)
typedef long long int ll;
typedef long double ld;
const ll INF = 1e15;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
    std::fill((T*)array, (T*)(array + N), val);
}
const int MAX = 510000;
const int MOD = 1000000007;
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; }
int n; vector<int> a;
template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
};
int main(void) {
    cin >> n;a.resize(n);
    rep(i, n) cin >> a[i];
    int right = 1<<30,left = 0;
    while (right - left > 1) {
        int mid = (right + left) / 2;
        ll cnt = 0;
        BIT<ll> bit(n * 2 + 10);
        int sum = 0;
        bit.add(n + 1, 1);
        rep(i, n) {
            sum += (a[i] <= mid) ? 1 : -1;
            cnt += bit.sum(1, sum + n + 1);
            bit.add(sum + n + 1, 1);
        }if (cnt >(ll)n * (n + 1) / 4)right = mid;
        else left = mid;
    }cout << right << endl;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N, W;
	cin >> N >> W;

	vector<int> v( N+1 ), w( N+1 );
	for( int i = 1; i <= N; ++i ) {
		cin >> v[i] >> w[i];
	}

	vector<vector<int>> dp( N+1, vector<int>( W+1 ) );
	for( int i = 1; i <= N; ++i ) {
		for( int j = 1; j <= W; ++j ) {
			if( j >= w[i] ) {
				dp[i][j] = max(
					dp[i-1][j-w[i]] + v[i],
					dp[i-1][j] );
			}
			else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}

	cout << dp[N][W] << endl;

	return 0;
}



Measured memory_bytes: 6828
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <bitset>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;


ll a[500000]={};

int main(){
    ll N,K;
    cin >> N >> K;
    ll A[2000];
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    ll tento[2000]={};
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            if(A[i]>A[j]){
                tento[i]++;
                tento[i]%=MOD;
            }
        }
    }
    
    ll all[2000]={};
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(A[i]>A[j]){
                all[i]++;
                all[i]%=MOD;
            }
        }
    }
    
    ll ans = 0;
    ll sigma = (K*(K-1)/2)%MOD;
    for(int i=0; i<N; i++){
        ans += (K*tento[i])%MOD + (all[i]*sigma)%MOD;
        ans%=MOD;
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

long long N;
long long X;
ll arr[100005];
ll divi[100005];
ll gcd;

int main() {
	scanf("%lld %lld", &N, &X);
	for(int i = 0; i < N; i++) {
		scanf("%lld", &arr[i]);
	}
	for(int i = 0; i < N; i++) {
		divi[i] = abs(X - arr[i]);
	}
	gcd = divi[0];
	for(int i = 1; i < N; i++) {
		gcd = __gcd(gcd, divi[i]);
	}
	printf("%lld\n", gcd);
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 1792
N=int(input())

if N<=50:
    A=[0 for i in range(50)]
    for i in range(N):
        A[i]=50
    print(50)
    print(*A)
else:
    A=[50-i for i in range(50)]
    N-=50
    for i in range(50):
        A[i]+=N//50
    for i in range(N%50):
        A[i]+=1
    print(50)
    print(*A)

Measured memory_bytes: 38324
#include<iostream>
using namespace std;

int abc(int num){
	int xx = num / 10000;
	int x = num / 1000 - xx * 10;
	int y = num / 100 - xx * 100 - x * 10;
	int z = num / 10 - xx * 1000 - x * 100 - y * 10;
	int w = num % 10;

	return xx + x + y + z + w;
}

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

	int sum = 0;
	for(int i = 1; i <= n; ++i){
		int tmp = abc(i);
		if(a <= tmp && tmp <= b) sum += i;
	}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

// typedef
typedef long long ll;

// container util
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

// repetition
#define FOR(i,m,n) for(ll i = ((ll) m); i < ((ll) n); ++i)
#define REP(i,n) FOR(i,0,n)

int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> interval;
    REP(i, m) {
        int s, e;
        cin >> s >> e;
        interval.emplace_back(s, e);
    }
    sort(interval.begin(), interval.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second < b.second;
        }
    );
    int ans = 0;
    int end = 0;
    for(const auto& p : interval) {
        if (end <= p.first) {
            end = p.second;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

/*
D - Islands War
https://atcoder.jp/contests/abc103/tasks/abc103_d

島から島への区間が被らないような要望を全て採用する必要がある.
採用された要望と区間が被っているものは自動的に採用されているのと一緒になるから.
島から島への区間が被らないような要望を最大限多く取る -> 区間スケジューリング

1次元の区間があって, 被る・被らないが問題になるときは
区間スケジューリングを疑ってみると良さそう.
*/

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

int main() {
  int n,count;
  cin >> n;
  vector <int> a(1000);
  vector <int> b(1000);
  for (int i=0;i<n-1;i++)
    cin >> b.at(i);
  count+=b.at(0);
  count+=b.at(n-2);
  for (int i=0;i<n-2;i++){
  a.at(i+1)=min(b.at(i),b.at(i+1));
    count+=a.at(i+1);
  }
  cout << count << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created: 土  9/ 8 21:16:36 2018

# Usage
#
"""
def input_get():
    INPUT = input()
    INPUTPARSED = INPUT.split(' ')
    return [int(i) for i in INPUTPARSED]

def judge(data):
    """
    >>> judge([3,1])
    Yes
    >>> judge([1,2])
    No
    >>> judge([2,2])
    No
    """
    if (data[0] * data[1]) % 2 == 0:
        print('No')
    else:
        print('Yes')
if __name__ == '__main__':
    judge(input_get())


Measured memory_bytes: 3060