akhauriyash/Code-Regression huggingface dataset:
from collections import deque
n = input()
a = map(int, raw_input().split())

res = deque()

for i in range(n):
  if i % 2 == 0:
    res.appendleft(a[i])
  else:
    res.append(a[i])
if n % 2 == 0:
  print ' '.join(map(str, reversed(res)))
else:
  print ' '.join(map(str, res))

Measured memory_bytes: 28672
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15 + 5;
#define ll long long
struct Node
{
    ll x , y;
    ll p;
}node[maxn];
ll minn[maxn];
int n ;
ll ans = 1e18;
void dfs (int step , int rest , ll sum)
{
    if (step == n + 1){
        ll gg = 0;
        for (int i = 1 ; i <= n ; i++) gg += minn[i];
        ans = min (ans , gg);
        return ;
    }
    // 不放
    dfs (step + 1 , rest , sum);
    if (rest == 0) return ;
    // 横着放 - 更新minn数组
    ll all = 0 , o[16];
    for (int i = 1 ; i <= n ; i++){
        o[i] = minn[i];
        minn[i] = min (minn[i] , abs(node[step].y - node[i].y) * node[i].p);
        all += minn[i];
    }
    dfs (step + 1 , rest - 1 , all);
    // 竖着放
    all = 0;
    for (int i = 1 ; i <= n ; i++){
        minn[i] = o[i];
        minn[i] = min (minn[i] , abs(node[step].x - node[i].x) * node[i].p);
        all += minn[i];
    }
    dfs(step + 1 , rest - 1 , all);
    for (int i = 1 ; i <= n ; i++) minn[i] = o[i];
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    memset( minn , 0x3f , sizeof minn);
    ll sum = 0;
    for (int i = 1 ; i <= n ; i++){
        cin >> node[i].x >> node[i].y >> node[i].p;
        minn[i] = min(abs(node[i].x) , abs(node[i].y)) * node[i].p;
        sum += minn[i];
    }
    for (int i = 0 ; i <= n ; i++){
        ans = 1e18;
        dfs(1 , i , sum);
        cout << ans << endl;
    }
    return 0;
}


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

int n;
int ax[5000],ay[5000];
int bx[5000],by[5000];

vector< ll > X,Y;

vector< int > Ga[5000];
vector< int > Gb[5000];
int f[5000];

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>ax[i]>>ay[i]>>bx[i]>>by[i];
    X.push_back(ax[i]);
    Y.push_back(ay[i]);
    X.push_back(bx[i]);
    Y.push_back(by[i]);
  }
  sort(X.begin(),X.end());
  sort(Y.begin(),Y.end());
  X.erase( unique( X.begin(), X.end()) , X.end() );
  Y.erase( unique( Y.begin(), Y.end()) , Y.end() );
  
  for(int i=0;i<n;i++){
    ax[i]=lower_bound(X.begin(),X.end(),ax[i])-X.begin();
    ay[i]=lower_bound(Y.begin(),Y.end(),ay[i])-Y.begin();
    bx[i]=lower_bound(X.begin(),X.end(),bx[i])-X.begin();
    by[i]=lower_bound(Y.begin(),Y.end(),by[i])-Y.begin();

    Ga[ ay[i] ].push_back( ax[i] );
    Ga[ ay[i] ].push_back( bx[i] );
    Gb[ by[i] ].push_back( ax[i] );
    Gb[ by[i] ].push_back( bx[i] );
  }
  ll ans=0;

  for(int y=0;y+1<(int)Y.size();y++){
    for(int i=0;i<(int)Ga[y].size();i+=2){
      int si=Ga[y][i];
      int ti=Ga[y][i+1];
      for(int x=si;x<ti;x++)f[x]++;
    }
    for(int i=0;i<(int)Gb[y].size();i+=2){
      int si=Gb[y][i];
      int ti=Gb[y][i+1];
      for(int x=si;x<ti;x++)f[x]--;
    }
    for(int x=0;x+1<(int)X.size();x++){
      if(f[x]==0)continue;
      ans+=(Y[y+1]-Y[y])*(X[x+1]-X[x]);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


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

  if (n % 2 == 1) {
    rep(i, m) {
      cout << (i+1) << " " << (n-i) << "\n";
    }
    return 0;
  }

  int cnt = 0;
  rep(i, n/4) {
    cout << (n/4 - i) << " " << (n/4+i+1) << "\n";
    ++cnt;
    if (cnt >= m) return 0;
  }

  int k = ((n/2)+1)/2 - 1;
  rep2(i, 1, m+1) {
    cout << (n-k-i) << " " << (n-k+i) << "\n";
    ++cnt;
    if (cnt >= m) return 0;
  }
  return 0;
}


Measured memory_bytes: 3644
n = int(input())
a = list(map(int,input().split()))
t = [0] * 8
p = 0

for i in range(n):
    if a[i] < 3200:
        t[a[i] // 400] = 1
    else:
        p += 1

x = t.count(1)
amax = p+x
if x == 0:
    amin = 1
else:
    amin = x
print(amin,amax)

Measured memory_bytes: 9108
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <map>
#include <string.h>
#define ll long long
#define mp(a, b) make_pair(a, b)

using namespace std;

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n, m, x, y, min1 = 1e9, maks = -1 * 1e9;
	cin >> n >> m >> x >> y;
	min1 = min(min1, y);
	maks = max(maks, x);
	for(int i = 1; i <= n; i ++){
		int a; cin >> a;
		maks = max(maks, a);
	}
	for(int i = 1; i <= m; i ++){
		int a; cin >> a;
		min1 = min(min1, a);
	}
	if(min1 <= maks)cout << "War" << endl;
	else cout << "No War" << endl;

	return 0;
}

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

char buf[4096];
int pnt;
int main() {
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);
    int e = (int)fmin(b + 1, a + k);
    for (int i = a; i < e; i++) {
        int len = sprintf(&buf[pnt], "%d\n", i);
        pnt += len;
    }
    for (int i = fmax(e, b - k + 1); i <= b; i++) {
        int len = sprintf(&buf[pnt], "%d\n", i);
        pnt += len;
    }
    puts(buf);
    return 0;
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] info = sc.nextLine().split(" ");
		int N=Integer.parseInt(info[0]);
		int K=Integer.parseInt(info[1]);
		Integer result=Arrays.asList(sc.nextLine().split(" "))
				.stream()
				.map(Integer::valueOf)
				.sorted(Comparator.reverseOrder())
				.collect(Collectors.toList())
				.subList(0, K)
				.stream()
				.mapToInt(Integer::valueOf)
				.sum();
		System.out.println(result);
	}
}

Measured memory_bytes: 26836
#include<iostream>
#include<algorithm>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

int main() {
  int A, B, M;
  cin >> A >> B >> M;
  int a[A], b[B], x[M], y[M],c[M];
  rep(i,0,A-1) cin >> a[i];
  rep(i,0,B-1) cin >> b[i];
  rep(i,0,M-1) cin >> x[i] >> y[i] >> c[i];
  int ans = 1<<20;
  rep(i,0,M-1) ans = min(ans, a[x[i]-1] + b[y[i]-1] - c[i]);
  int mina = *min_element(a, a+A);
  int minb = *min_element(b, b+B);
  ans = min(ans, mina + minb);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2176
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(){
    int A,B,C,K;

    cin >> A >> B >> C >> K;

    if(K <= A)cout << K << endl;
    else if(K > A + B)cout << A - (K - (A + B)) << endl;
    else cout << A << endl;
    
    return 0;
}

Measured memory_bytes: 3220
n, d, a = map(int, input().split())
d *= 2
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
x = [0] * n
h = [0] * n
for i in range(n):
    x[i], h[i] = l[i]
    h[i] = (h[i] - 1) // a + 1
t = 0
r = 0
ans = 0
for l in range(n):
    tmp = 0
    while r < n and x[r] - x[l] <= d:
        h[r] -= t
        t += max(h[r], 0)
        tmp += max(h[r], 0)
        r += 1
    t -= max(h[l], 0)
    ans += tmp
print(ans)


Measured memory_bytes: 61368
package main

import "fmt"

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var N int
	fmt.Scan(&N)
	h := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&h[i])
	}
	dp := make([]int, N)
	dp[1] = abs(h[0] - h[1])
	for i := 2; i < N; i++ {
		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
	}
	fmt.Println(dp[N-1])
}


Measured memory_bytes: 5504
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = Integer.parseInt(scanner.nextLine());

		int result = 0;
		for(int dIdx = 0; dIdx < 32; dIdx++) {
			int digit = 1;
			if(num % 2 != 0) {
				digit <<= dIdx;
				result += digit;
				num--;
			}
			num /= -2;
		}

		System.out.println(Integer.toBinaryString(result));
	}
}


Measured memory_bytes: 21972
n, k = map(int, input().split())
s = input()

state = '1'
cnt = 0
start = 0
ret = 0

for i in range(len(s)):
    if state == '1' and s[i] == '0':
        cnt += 1
        if cnt <= k:
            length = i - start + 1
            ret = max(ret, length)
        else:
            has_zero = False
            while True:
                if has_zero and s[start] == '1':
                    break
                else:
                    if s[start] == '0':
                        has_zero = True
                    start += 1
            length = i - start + 1
            ret = max(ret, length)
        state = '0'
    elif state == '1' and s[i] == '1':
        length = i - start + 1
        ret = max(ret, length)
    elif state == '0' and s[i] == '0':
        length = i - start + 1
        ret = max(ret, length)
    else:
        state = '1'
        length = i - start + 1
        ret = max(ret, length)

print(ret)



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

int main() {
	long A,B,C,K;
	cin >>A>>B>>C>>K;
	if(K<=A){
		cout <<K;
	}
	else if(K<=A+B){
		cout <<A;
	}
	else{
		cout <<A-(K-A-B);
	}

	

}

Measured memory_bytes: 3636
D = int(input())
c = list(map(int,input().split()))
s = []
for i in range(D):
    s.append(list(map(int,input().split())))

def last(d,la):
    s = 0

    for i in range(26):
        if la[i] == 0 and  i == d:
            s += c[i] * (d - la[i]-1)
        else:
            s += c[i] * (d - la[i])
    return s

lastday = [0]*26
a = 0

for d in range(D):

    eff = s[d][0] - last(d+1,lastday)
    ret = 0
    for t in range(26):
        bef = lastday[t]
        #lastday[t] = d+1
        
        now = s[d][t] - last(d+1,lastday)
        if eff < now:
            eff = now 
            ret = t

        lastday[t] = bef
        
    lastday[ret] = d+1
    a += eff
    print(ret+1)

Measured memory_bytes: 9288
#include<map>
#include<cmath>
#include<stack>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll x,y,sum,ans;
int main(){
    scanf("%lld%lld",&x,&y);
    ans=y/x;
    while(ans)ans/=2,sum++;
    printf("%lld\n",sum);
    return 0;
}

Measured memory_bytes: 256
<?php
list($n) = ints();
$p = ints();
$ans = $cnt = 0;
for ($i = 0; $i < $n; ++$i) {
    if ($p[$i] === $i + 1) {
        $cnt++;
    } else {
        if ($cnt > 0) $ans += (int) ceil($cnt / 2);
        $cnt = 0;
    }
    if ($i === $n - 1 && $cnt > 0) $ans += (int) ceil($cnt / 2);
}
echo $ans;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


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

using namespace std;

#define SIZE 3005

int dp[SIZE][SIZE];
string ch, bh, ss = "";
	
int LCS(int len_a, int len_b)
{
	for(int i = 0; i <= len_a; i++)
	{
		for(int j = 0; j <= len_b; j++)
	    {
			if(i == 0 || j == 0) dp[i][j] = 0;
			else if(ch[i-1] == bh[j-1])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
			} 
			else 
			{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	
	/*for(int i = 0; i < len_a; i++) // LCS Table
	{
		for(int j = 0; j < len_b; j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	return dp[len_a][len_b];
}

void print_LCS(int m, int p, int q)
{
	while(1)
	{
		if(p == 0 || q == 0) break;
		int ans = max(dp[p-1][q], dp[p][q-1]);
		if(ans== m)
		{
			if(ans == dp[p-1][q])
			{
				p -= 1;
			}
			else
			{
				q -= 1;
			}
		}
		else
		{
			m = ans;
			ss.push_back(ch[p-1]);
			p -= 1;
			q -= 1;
		}
	}
	reverse(ss.begin(), ss.end());
	cout << ss << endl;
}

int main()
{	
	cin >> ch >> bh;
	
	int len_a = ch.size(), len_b = bh.size();
	
	int ans = LCS(len_a, len_b);
	
	print_LCS(ans, len_a, len_b);
	
	
	return 0;
}


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

int main() {
	VB b = { true,false,false };

	char c1, c2, c;
	while (cin >> c1 >> c >> c2) {
		swap(b[c1 - 'A'], b[c2 - 'A']);
	}

	int ans;
	rep(i, 3)if (b[i])ans = i;
	Cout((char)(ans + 'A'));
}


Measured memory_bytes: 3080
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define SENTINEL INT_MAX

int A[500000],c=0;

void Merge(int left, int mid, int right){
	int i, j, k;
	int n1 = mid - left;
	int n2 = right - mid;
	int L[500000], R[500000];
	//L = (int *)malloc(sizeof(int)*n1);
	//R = (int *)malloc(sizeof(int)*n2);

	for (i = 0; i < n1;i++){
		L[i] = A[left + i];
	}
	for (i = 0; i < n2;i++){
		R[i] = A[mid + i];
	}
	L[n1] = SENTINEL;
	R[n2] = SENTINEL;
	i = 0;
	j = 0;
	for (k = left; k < right;k++){
		c++;
		if (L[i] <= R[j]){
			A[k] = L[i];
			i = i + 1;
		}else{
			A[k] = R[j];
			j = j + 1;
		}
	}
	//free(L);
	//free(R);
}

void Merge_Sort(int left, int right){
	int mid;
	if (left + 1 < right){
		mid = (left + right) / 2;
		Merge_Sort(left, mid);
		Merge_Sort(mid, right);
		Merge(left, mid, right);
	}
}

int main(){
	int i, j, k;
	scanf("%d",&i);
	for (j = 0; j < i;j++){
		scanf("%d",&A[j]);
	}

	Merge_Sort(0,j);

	
	for (i = 0; i < j; i++){
		printf("%d", A[i]);
		if (i < j - 1){
			printf(" ");
		}
	}
printf("\n%d\n",c);
return 0;
}

Measured memory_bytes: 5492
n,m=map(int,input().split())
l=[0]*m
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(a[0]):
    l[a[j+1]-1]+=1
z=0
for i in range(m):
  if n==l[i]:
    z+=1
print(z)



Measured memory_bytes: 62500
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  int n,k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i=0;i<n;i++) cin >> a[i];

  ll l,r;
  l=0;
  r=1000001000;
  while(l+1<r){
    ll t=(l+r)/2;
    int tn=0;
    for(int i=0;i<n;i++){
      tn+=a[i]/t;
      if(a[i]%t!=0) tn++;
      tn--;
    }
    if(tn<=k){
      r=t;
    }else{
      l=t;
    }
    //cout << l << "," << r << " " << t << " " << tn << endl;
  }

  cout << r << endl;

  return 0;
}


Measured memory_bytes: 4668
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef pair<int,int> P;

int n;
struct expo{
	int x,y;
};

bool comp(const expo &a,const expo &b){
	return a.x>b.x;
}

int abs(int a){
	if(a<0)return -a;
	return a;
}

expo in[100001];
expo add[100001];
expo minu[100001];
int team[2][100001];

bool C(int div){
	for(int i=0;i<n;i++)team[0][i]=team[1][i]=-1;
	team[0][add[0].y]=0;
	for(int i=0;i<n;i++){
		if(abs(add[i].x-add[0].x) >div && abs(add[i].x-add[n-1].x) >div)return false;
		if(abs(add[i].x-add[0].x) >div)team[0][add[i].y]=1;
		if(abs(add[i].x-add[n-1].x) >div)team[0][add[i].y]=0;
	}
	
	team[1][minu[0].y]=0;
	for(int i=0;i<n;i++){
		if(abs(minu[i].x-minu[0].x)>div && abs(minu[i].x-minu[n-1].x)>div)return false;
		if(abs(minu[i].x-minu[0].x)>div)team[1][minu[i].y]=1;
		if(abs(minu[i].x-minu[n-1].x)>div)team[1][minu[i].y]=0;
	}
	int a=0,b=0;
	for(int i=0;i<n;i++){
		if(team[0][i]==-1 || team[1][i]==-1){
			b++;
		}else{
			if(team[0][i]!=team[1][i])a++;
		}
	}
	return (a==0 || a+b==n);
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d",&in[i].x,&in[i].y);
		add[i].x=in[i].x+in[i].y;
		minu[i].x=in[i].x-in[i].y;
		add[i].y=minu[i].y=i;
	}
	sort(add,add+n,comp);
	sort(minu,minu+n,comp);
	int lb=-1,ub=400001;
	while(ub-lb>1){
		int mid=(lb+ub)/2;
		if(C(mid))ub=mid;
		else lb=mid;
	}
	
	printf("%d\n",ub);
	return 0;
}

Measured memory_bytes: 4332
def main():
    import sys
    input=sys.stdin.readline
    k,n=map(int,input().split())
    A=list(map(int,input().split()))
    m=0
    for i in range(n-1):
        m=max(m,A[i+1]-A[i])
    m=max(m,A[0]+k-A[-1])
    print(k-m)
if __name__ == '__main__':
    main()

Measured memory_bytes: 71884
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue> 
#include <tuple>
#include <map>
 
using namespace std;

typedef long long ll;

int main() {
	cin.tie(0);

    int N;

    cin >> N;

    vector<int> H(N);

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

    for(int i = N - 2; i >= 0; i--) {
        if(H[i] > H[i + 1]) {
            if(H[i] - 1 > H[i + 1]) {
                cout << "No" << endl;
                return 0;
            }
            H[i]--;
        }
    }

    cout << "Yes" << endl;
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::scanf;
using std::printf;
using std::memset;
struct node
{
  long long data;
  int id;
  bool operator< (const node& o) const
  { return this->data < o.data;}
};

typedef long long llong;
const int maxn = 200010;

llong treeset[maxn];
llong end[maxn];
node rec[maxn];
llong n;
llong k;

inline int lowbit(int x)
{ return x&(-x);}

void add(int x, llong d)
{
  while(x <= n)
  {
    treeset[x] += d;
    x += lowbit(x);
  }
}

llong sum(int x)
{
  llong ans = 0;
  while(x)
  {
    ans += treeset[x];
    x -= lowbit(x);
  }
  return ans;
}

int main()
{
  llong tmp;
  llong ans = 0;
  scanf("%lld%lld", &n, &k);
  memset(rec, 0, sizeof(rec));
  for(int i = 1; i <= n; ++i)
  {
    scanf("%lld", &tmp);
    rec[i].data = rec[i-1].data +tmp-k;
    rec[i].id = i;
  }
  std::sort(rec+1, rec+1+n);
  end[rec[1].id] = 1;
  for(int i = 2; i <= n; ++i)
  {
    if(rec[i].data != rec[i-1].data)
    { end[rec[i].id] = i;}
    else
    { end[rec[i].id] = end[rec[i-1].id];}
  }
  for(int i = 1; i <= n; ++i)
  {
    add(end[i], 1);
    ans += sum(n) - sum(end[i]);
  }
  for(int i = 1; i <= n; ++i)
  {
    if(rec[i].data < 0)
    { ++ans;}
  }
  ans = n*(n+1)/2 - ans;
  printf("%lld\n", ans);
}


Measured memory_bytes: 6400
import java.util.*;
public class Main {
static int mod=(int)1e9+7;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n+1];
Arrays.fill(arr,-1);
arr[0]=0;
arr[1]=0;
for(int i=2;i<=n;i++) {
	 
		if(arr[i]==-1) {
			for(int j=i*i;j<=n;j+=i) {
				arr[j]=0;
		}
	}
}
//for(int i:arr) {
//	System.out.println(i+" ");
//}

long ans=1;
for(int i=0;i<=n;i++) {
	if(arr[i]==-1) {
		int res=0;
		int temp=i;
		while(n>=temp) {
			res+=(n/temp);
			
			temp=temp*i;
		}
		
		ans=(ans*(res+1))%mod;
	}
	
	
	
}
System.out.println(ans);



}
}

Measured memory_bytes: 35508
import java.util.*;
import java.lang.*;
import java.io.*;

public final class Main
{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
      for(int i =0; i< n; i++)
        arr[i]= in.nextInt();
        
        int[] dp = new int[n];
        dp[0] =0;
         dp[1]= Math.abs(arr[1]-arr[0]);
      for(int i =2; i< n ; i++) {
         dp[i] = Math.min(Math.abs(arr[i]-arr[i-1])+ dp[i-1], 
                         Math.abs(arr[i]- arr[i-2])+ dp[i-2]);
      }
      System.out.println(dp[n-1]);
    }
}


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

const int N=100005;
long long MOD=1e9+7;
const long long INF=0x3f3f3f3f3f3f3f3f;
int n,k;
long long a[3005],dp[105][N];

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=0;i<=k;i++) dp[0][i]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=1;
		for(int j=1;j<=a[i];j++)
		{
			dp[i][j]=dp[i-1][j];
			dp[i][j]=(dp[i][j]+MOD+dp[i][j-1])%MOD;
		}
		for(int j=a[i]+1;j<=k;j++)
		{
			dp[i][j]=dp[i-1][j]-dp[i-1][j-a[i]-1];
			dp[i][j]=(dp[i][j]+MOD+dp[i][j-1])%MOD;
		}
	}
	printf("%lld\n",(dp[n][k]-dp[n][k-1]+MOD)%MOD);
}

Measured memory_bytes: 80128
#include<stdio.h>
int main(){
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);
    if(a<b){
        printf("a < b\n");
    }else if(a>b){
        printf("a > b\n");
    }else{
        printf("a == b\n");
    }
return 0;
}

Measured memory_bytes: 580
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

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

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 3 && i % 5) {
            sum += i;
        }
    }

    std::cout << sum << std::endl;
}


Measured memory_bytes: 3636
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))

temp = []
temp.append(a.pop())
temp[-1] -= 1

while sum(a) != 0:
    a = sorted(a)
    temp.append(a.pop())
    temp[-1] -= 1
    a.append(temp.pop(0))

print(temp[0])

Measured memory_bytes: 41068
n,wmax=gets.split.map(&:to_i)
dp=Array.new(110){[0]*10010}
for i in 0..n-1
    vi,wi=gets.split.map(&:to_i)
    for w  in 1..wmax
    if (w-wi)>=0
    dp[i+1][w]=[dp[i][w-wi]+vi,dp[i][w]].max
    else
    dp[i+1][w]=dp[i][w]
    end
    end
end
#p dp[0..10]
p dp[n][wmax]


Measured memory_bytes: 15468
N,K = map(int,input().split())
Dices = list(map(int,input().split()))

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

print(total)

Measured memory_bytes: 25060
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const long double eps = 1e-8;
const long double pi = acos(-1);

class Point {
    public:
    long double x;
    long double y;
    
    Point(long double x = 0, long double y = 0) : x(x), y(y) {}
    bool operator<(const Point& p) const {
        return abs(x - p.x) > eps ? x < p.x : y < p.y;
    }
    bool operator==(const Point& p) const {
        return abs(x - p.x) < eps && abs(y - p.y) < eps;
    }
    Point operator+(const Point& p) const {
        return Point(x + p.x, y + p.y);
    }
    Point operator-(const Point& p) const {
        return Point(x - p.x, y - p.y);
    }
    Point operator*(long double r) const {
        return Point(x * r, y * r);
    }
    Point operator/(long double r) const {
        return Point(x / r, y / r);
    }
};

inline long double angle(const Point& p1, const Point& p2) {
    return (p1.x * p2.x + p1.y * p2.y) / sqrt(p1.x * p1.x + p1.y * p1.y) / sqrt(p2.x * p2.x + p2.y * p2.y);
}

enum CCW {
    LEFT = 1,
    RIGHT = -1,
    FRONT = 2,
    BACK = -2,
    ON = 0
};

inline CCW ccw(const Point& p1, const Point& p2, const Point& p3) {
    Point v = p2 - p1;
    Point w = p3 - p1;
    long double r = v.x * w.y - v.y * w.x;
    if (r > eps) return LEFT;
    if (r < -eps) return RIGHT;
    long double t = (v.x * w.x + v.y * w.y) / (v.x * v.x + v.y * v.y);
    if (t > 1) return FRONT;
    if (t < 0) return BACK;
    return ON;
}

vector <Point> convex_hull(vector <Point>& v) {
    int m = 0, r;
    vector <Point> w(v.size() * 2);
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); w[m++] = v[i++]) {
        while (m > 1 && ccw(w[m - 1], w[m - 2], v[i]) <= 0) m--;
    }
    for (int i = v.size() - 2, r = m; i >= 0; w[m++] = v[i--]) {
        while (m > r && ccw(w[m - 1], w[m - 2], v[i]) <= 0) m--;
    }
    w.resize(m - 1);
    return w;
}

Point p[100];

int main() {
    int n, i, j;
    vector <Point> v;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        p[i] = Point(x, y);
        v.push_back(p[i]);
    }
    
    v = convex_hull(v);
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < v.size(); j++) {
            if (v[j] == p[i]) break;
        }
        
        if (j == v.size()) {
            puts("0");
        } else {
            Point p1 = v[(j - 1 + v.size()) % v.size()] - v[j];
            Point p2 = v[(j + 1) % v.size()] - v[j];
            long double t = pi - acos(max(-1.0L, min(angle(p1, p2), 1.0L)));
            
            printf("%.12Lf\n", t / pi / 2);
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
prices = []

prices = input().split()

sum1 = int(prices[0]) + int(prices[1])
sum2 = int(prices[0]) + int(prices[2])
sum3 = int(prices[1]) + int(prices[2])

if sum1 <= sum2 and sum1 <= sum3:
    print(sum1)
elif sum2 <= sum1 and sum2 <= sum3:
    print(sum2)
elif sum3 <= sum1 and sum3 <= sum2:
    print(sum3)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;

int N;
long long D, A;
vector<long long> X, H;

long long solve() {
    // モンスターを X が小さい順に
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return X[i] < X[j]; });
    vector<long long> nX(N), nH(N);
    for (int i = 0; i < N; ++i) nX[i] = X[ids[i]], nH[i] = H[ids[i]];
    X = nX, H = nH;

    // imos 法で処理していく
    vector<long long> S(N+1, 0);
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] < H[i]) {
            // モンスター i を倒すのに必要な回数
            long long need = (H[i] - S[i] + A - 1) / A;
        
            // X[i] を左端とした爆発が届く範囲を求める
            long long right = X[i] + D * 2;
            int id = upper_bound(X.begin(), X.end(), right) - X.begin();
            
            // imos しながら爆発させる
            S[i] += need * A;
            S[id] -= need * A;
            res += need;
        }

        // imos の累積和をとる操作
        S[i+1] += S[i];
    }
    return res;
}

int main() {
    cin >> N >> D >> A;
    X.resize(N); H.resize(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> H[i];
    cout << solve() << endl;
}


Measured memory_bytes: 8832
S = list(input())
S = [ord(x) for x in S]
S_exist = sorted(S)
if len(S_exist) != 26:
    for i in range(len(S_exist)):
        if S_exist[i] != i+97:
            S.append(i+97)
            break
    if len(S_exist) == len(S):
        S.append(max(S_exist)+1)
    print("".join(map(str, [chr(x) for x in S])))
else:
    S.reverse()
    if S == S_exist:
        print(-1)
    else:
        flag = 0
        for i in range(25):
            if S[i] > S[i+1]:
                a = S[i+1]
                for j in sorted(S[:i+2]):
                    if j > a:
                        S = [j] + S[i+2:]
                        flag = 1
                        break
            if flag == 1:
                break
        S.reverse()
        print("".join(map(str, [chr(x) for x in S])))


Measured memory_bytes: 3064
N, K = map(int, input().split())
X = list(map(int, input().split()))

ans = float('inf')
for i in range(N-K+1):
    ans = min(ans, abs(X[i] - X[i+K-1]) + abs(X[i]))
    ans = min(ans, abs(X[i] - X[i+K-1]) + abs(X[i+K-1]))

print(ans)


Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define pb push_back 
#define mp make_pair
typedef long long ll;

const int maxb=62;

ll mul(ll a,ll b, ll c){
	ll ans=0;
	while(b>0){
		if(b&1) ans=(ans+a)%c;
		a=(a+a)%c;
		b>>=1;
	}
	return ans;
}

const ll mod=1000000007; 

int main(){
	int n; cin>>n;
	ll a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	
	ll sum[n+5][100];
	ll total[100];
	
	for(int i=0;i<70;i++){
		sum[n][i]=0;
		total[i]=0;
	}
	
	for(int i=n-1; i>=0; i--){
		ll temp=a[i];
		for(int j=0; j<=62; j++){
			int cif=temp%2;
			temp/=2;
			sum[i][j]=sum[i+1][j]+cif;
			
			if(i==n-1) continue;
			
			if(cif) total[j] += n-i-1-sum[i+1][j];
			else total[j] += sum[i+1][j];
		}
	}
		
	ll ans=0ll;
	ll ind=1ll;
	
	for(int i=0; i<=62; i++){
		ans+=mul(total[i],ind,mod);
		ans%=mod;
		if(i!=62) ind*=2;
	}
	
	cout<<ans;
	
	return 0;
}


Measured memory_bytes: 236928
#include <bits/stdc++.h>
using namespace std;
#define p5(x) 1LL * (x) * (x) * (x) * (x) * (x)
bool is_power5(long long n) {
	if(n < 0) n = -n;
	else if(n == 0) return true;
	for(int k = 2; 1LL * k * k <= n; ++k) {
		if(n % k == 0) {
			int i = 0;
			while(n % k == 0) {
				++i;
				n /= k;
			}
			if(i % 5) 
				return false;
		}
	}
	return n == 1;
}
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int X, A = 1e9, B = 1e9;
	cin >> X;
	for(int k = 0; k <= 140; ++k) {
		long long b = X - p5(k);
		if(is_power5(b)) {
			A = k, B = pow(abs(b), 0.2);
			if(b > 0) B = -B;
			break;
		}
	}
	cout << A << ' ' << B << '\n';
	return 0;
}


Measured memory_bytes: 4024
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    s = [""] * N
    t = [0] * N
    for i in range(N):
        st = input().split()
        s[i] = st[0]
        t[i] = int(st[1])
    X = input().rstrip()

    idx = s.index(X)
    ans = sum(t[idx + 1:])

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
using System;

namespace AtCoder2
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            if (N == 1)
            {
                Console.WriteLine("Hello World");
            }
            else
            {
                int A = int.Parse(Console.ReadLine());
                int B = int.Parse(Console.ReadLine());
                Console.WriteLine(A + B);
            }
       }
    }
}

Measured memory_bytes: 11092
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = std::vector<int>;
using VI2D = std::vector<vector<int>>;
using VLL = std::vector<long long>;
using VLL2D = std::vector<vector<long long>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};

template <typename T, std::size_t N>
struct make_vector_type {
	using type =
		typename std::vector<typename make_vector_type<T, (N - 1)>::type>;
};

template <typename T>
struct make_vector_type<T, 0> {
	using type = typename std::vector<T>;
};

template <typename T, size_t N>
auto make_vector_impl(const std::vector<std::size_t>& ls, T init_value) {
	if constexpr(N == 0) {
		return std::vector<T>(ls[N], init_value);
	} else {
		return typename make_vector_type<T, N>::type(
			ls[N], make_vector_impl<T, (N - 1)>(ls, init_value));
	}
}

template <typename T, std::size_t N>
auto make_vector(const std::size_t (&ls)[N], T init_value) {
	std::vector<std::size_t> dimensions(N);
	for(int i = 0; i < N; i++) {
		dimensions[N - i - 1] = ls[i];
	}
	return make_vector_impl<T, N - 1>(dimensions, init_value);
}

template <typename T>
std::vector<T> make_vector(std::size_t size, T init_value) {
	return std::vector<T>(size, init_value);
}

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max<T>(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min<T>(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	string s;
	cin >> s;

	int n = s.size();
	cout << s + (s[n - 1] == 's' ? "es" : "s") << endl;
	return 0;
}


Measured memory_bytes: 3624
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if(a%500 == 0) {
			System.out.println("Yes");
		}
		else if(a%500-b <= 0) {
			System.out.println("Yes");
		}
		else if(a%500-b > 0) {
			System.out.println("No");
		}
	}
}

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

int dp[50][1 << 16], mem[1 << 16][11];
int n, x, y, z;
int ok(int v) {
	bool a = false, b = false;
	int c = 0, d = 0;
	for (int i = 0; i < 17; i++) {
		c++;
		if (v >> i & 1) {
			if (!a&&c == z)a = true, c = 0;
			if (a && !b&&c == y)b = true, c = 0;
			if (a&&b&&c == x)return -1;
		}
		if (i != 16)d |= (v >> i & 1) << i;
	}
	return d;
}
int main() {
	scanf("%d%d%d%d", &n, &x, &y, &z);
	rep(i, 1 << 16) {
		for (int j = 1; j <= 10; j++) {
			int t = i << j; t |= 1 << (j - 1);
			mem[i][j] = ok(t);
		}
	}
	dp[0][0] = 1;
	rep(i, n)rep(j, 1 << 16) {
		if (dp[i][j] == 0)continue;
		for (int k = 1; k <= 10; k++) {
			if (mem[j][k] != -1)(dp[i + 1][mem[j][k]] += dp[i][j]) %= MOD;
		}
	}
	ll ans = 0, b = 1;
	rep(i, n)(b *= 10) %= MOD;
	rep(j, 1 << 16)(ans += dp[n][j]) %= MOD;
	printf("%lld\n", (b - ans + MOD) % MOD);
}

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

using namespace std;
#define ll long long
#define ld long double
const int N=2e5 + 5;
const ll mod = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    if(n % 2 == 0) n--;
    int l = 1, r = n / 2;
    while(m && l < r) {
        cout << l << " " << r << endl;
        m--;
        l++;
        r--;
    }
    l = n / 2 + 1;
    r = n;
    while(m && l < r) {
        cout << l << " " << r << endl;
        m--;
        l++;
        r--;
    }
    return 0;
}


Measured memory_bytes: 3660
def combs_mod(n,k,mod):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,-1,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans
def solve():
  mod = 998244353
  N, K = map(int, input().split())
  ans = 0
  if K<N:
    return ans
  com = combs_mod(K,K,mod)
  com2 = combs_mod(K-1,K-1,mod)
  for r in range(K+1):
    b = K-r
    dif = r-b
    if dif<0 or r<N:
      continue
    elif dif==0:
      ans += com2[r]
      if N>=2:
        ans -= com2[N-2]
    elif dif<N:
      ans += com[r] - com[N-1-dif]
    else:
      ans += com[r]
    ans %= mod
  return ans
print(solve())

Measured memory_bytes: 68272
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int>xx[2];
vector<vector<int> >adj;
int ans[200005];
void dfs(int ver,int x,int pr)
{
   xx[x%2].push_back(ver);
   for(auto i:adj[ver])
   {
      if(i!=pr)
      {
         dfs(i,x+1,ver);
      }
   }
}

signed main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
   
 #ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
 #endif

// -------------------------------------Code starts here---------------------------------------------------------------------     

   int n;
   cin>>n;
      adj.resize(n+1);
   int x,y;
   for(int i=0;i<n-1;i++)
   {
      cin>>x>>y;
      adj[x].push_back(y);
      adj[y].push_back(x);
   }
   dfs(1,0,0);
   vector<int>pp[3];
   for(int i=1;i<=n;i++)
   {
      pp[i%3].push_back(i);
   }
   if(xx[0].size()>xx[1].size())
      swap(xx[0],xx[1]);
   if(xx[0].size()<=pp[0].size())
   {
      for(auto i:xx[0])
      {
         ans[i]=pp[0].back();
         pp[0].pop_back();
      }
      for(auto i:xx[1])
      {
         if(!pp[0].empty())
         {
            ans[i]=pp[0].back();
            pp[0].pop_back();
         }
         else if(!pp[1].empty())
         {
            ans[i]=pp[1].back();
            pp[1].pop_back();
         }
         else
         {
            ans[i]=pp[2].back();
            pp[2].pop_back();
         }         
      }
   }
   else
   {
      for(auto i:xx[0])
      {
         if(!pp[1].empty())
         {
            ans[i]=pp[1].back();
            pp[1].pop_back();
         }
         else
         {
            ans[i]=pp[0].back();
            pp[0].pop_back();  
         }         
      }
      for(auto i:xx[1])
      {
         if(!pp[0].empty())
         {
            ans[i]=pp[0].back();
            pp[0].pop_back();
         }
         else if(!pp[1].empty())
         {
            ans[i]=pp[1].back();
            pp[1].pop_back();
         }
         else
         {
            ans[i]=pp[2].back();
            pp[2].pop_back();
         }         
      }
   }
   for(int i=1;i<=n;i++)
      cout<<ans[i]<<" ";

// -------------------------------------Code ends here------------------------------------------------------------------
     clock_t clk;
 	clk = clock();
 
    clk = clock() - clk;
 	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
 	return 0;
 }


Measured memory_bytes: 23404
#include <bits/stdc++.h> 
using namespace std; 
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main(void) {
    io;
    int N; cin >> N;
    vector<int> input(N);
    long long ans = INT_MAX;

    for (int i = 0; i < N; i++) cin >> input[i];
    for (int i = -100; i <= 100; i++) {
        long long sum(0);
        for (int k = 0; k < N; k++) {
            sum += (input[k]-i) * (input[k]-i);
        }
        ans = min(sum, ans);
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3604
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

import bisect

for x in X:
    ans = 10**12
    tmpans1 = 0
    pos1 = bisect.bisect_left(S,x)
    if pos1==0:
        tmpans1 += abs(S[pos1]-x)
        p = bisect.bisect_left(T,S[pos1])
        tmpans1 += min(abs(S[pos1]-T[min(p,B-1)]),abs(S[pos1]-T[max(0,p-1)]))
        ans = min(ans,tmpans1)
    elif pos1==A:
        pos1 -= 1
        tmpans1 += abs(x-S[pos1])
        p = bisect.bisect_left(T,S[pos1])
        tmpans1 += min(abs(S[pos1]-T[min(p,B-1)]),abs(S[pos1]-T[max(0,p-1)]))
        ans = min(ans,tmpans1)
    else:
        tmpans1 += abs(S[pos1]-x)
        p = bisect.bisect_left(T,S[pos1])
        tmpans1 += min(abs(S[pos1]-T[min(p,B-1)]),abs(S[pos1]-T[max(0,p-1)]))
        ans = min(ans,tmpans1)
        tmpans1 = 0
        pos1 -= 1
        tmpans1 += abs(x-S[pos1])
        p = bisect.bisect_left(T,S[pos1])
        tmpans1 += min(abs(S[pos1]-T[min(p,B-1)]),abs(S[pos1]-T[max(0,p-1)]))
        ans = min(ans,tmpans1)
    
    tmpans1 = 0
    pos1 = bisect.bisect_left(T,x)
    if pos1==0:
        tmpans1 += abs(T[pos1]-x)
        p = bisect.bisect_left(S,T[pos1])
        tmpans1 += min(abs(T[pos1]-S[min(p,A-1)]),abs(T[pos1]-S[max(0,p-1)]))
        ans = min(ans,tmpans1)
    elif pos1==B:
        pos1 -= 1
        tmpans1 += abs(T[pos1]-x)
        p = bisect.bisect_left(S,T[pos1])
        tmpans1 += min(abs(T[pos1]-S[min(p,A-1)]),abs(T[pos1]-S[max(0,p-1)]))
        ans = min(ans,tmpans1)
    else:
        tmpans1 += abs(T[pos1]-x)
        p = bisect.bisect_left(S,T[pos1])
        tmpans1 += min(abs(T[pos1]-S[min(p,A-1)]),abs(T[pos1]-S[max(0,p-1)]))
        ans = min(ans,tmpans1)
        tmpans1 = 0
        pos1 -= 1
        tmpans1 += abs(T[pos1]-x)
        p = bisect.bisect_left(S,T[pos1])
        tmpans1 += min(abs(T[pos1]-S[min(p,A-1)]),abs(T[pos1]-S[max(0,p-1)]))
        ans = min(ans,tmpans1)
    
    print(ans)

        
        
        

Measured memory_bytes: 16172
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<int>b(n);
    for(int i = 0; i < n; i++){
        if(a[i] % 2 == 0) b.push_back(a[i]);
    }
   // if(b.size() == 0)
   int count = 0;
    for(int i = 0; i < b.size(); i++){
        if(b[i]%3 == 0 || b[i]%5 == 0 ) count += 1;
    }
    if(count == b.size()) cout << "APPROVED";
    else cout << "DENIED";
}


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

int n;
std::string t[256];
std::string str;

int dfs(char op, int& i) {
  int res = op == '+' ? 0 : 1;
  i += 1; // '('
  for(;;) {
    char c = str[i];
    if( c == ')' ) {
      return res;
    }
    int t;
    if( c == '+' or c == '*' ) {
      i += 1;
      t = dfs(c, i);      
    }
    else {
      t = c - '0';
    }
    res = ((op == '+') ? res + t : res * t);
    i += 1;
  }
  assert(0);
  return 0;
}

int main() {
  for(;;) {
    for(int i = 0; i < 256; ++i) {
      t[i].clear();
    }
    str.clear();
    scanf("%d", &n);
    if( n == 0 ) break;
    for(int i = 0; i < n; ++i) {
      std::cin >> t[i];
    }
    str += '(';
    for(int i = 0; i < n; ++i) {
      str += t[i][t[i].size()-1];
      if( t[i].size() < t[i+1].size() ) {
        str += '(';
      }
      if( t[i].size() > t[i+1].size() ) {
        for(int j = 0; j < t[i].size() - t[i+1].size(); ++j) {
          str += ')';
        }
      }
    }
    int i = 0;
    int res = dfs('+', i);
    printf("%d\n", res);
  }

  return 0;
}

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int W,a,b;
    cin >> W >> a >> b;

    if(a+W > b && b+W > a){
        cout << 0 << endl;
    }else{
        cout << min(abs(b-a-W),abs(a-b-W)) << endl;
    }

    return 0;
}


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

class Program
{

    public static void Main( )
    {
        string S = Console.ReadLine( );
        int Q = int.Parse( Console.ReadLine( ) );
        bool isReversed = false;
        var ans = new List<char>( S.ToArray() );

        for ( int i = 0; i < Q; i++ )
        {
            var query = Console.ReadLine( );

            if ( query[ 0 ] == '1' )
            {
                isReversed = !isReversed;
                continue;
            }

            if ( query[ 0 ] == '2' )
            {
                var row = query.Split( ).ToArray();
                int F = int.Parse( row[ 1 ] );
                char C = row[ 2 ][0];

                if ( F == 1 & !isReversed || ( F == 2 & isReversed ) )
                {
                    ans.Insert(0, C);
                }
                else
                {
                    ans.Add( C );
                }
            }
        }

        if ( isReversed )
        {
            ans.Reverse( );
        }
        Console.WriteLine( String.Concat(ans) );
    }
}

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

int main()
{
    ll n,k;
    while(~scanf("%lld%lld",&n,&k))
    {
        ll res=0LL;
        for(ll b=k+1;b<=n;b++)
        {
            res+=n/b*(b-k);
            res+=max(0LL,(n%b)-k+1);
        }
        if(k==0) res=n*n;
        printf("%lld\n",res);
    }
}


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

#define ll long long
#define pb push_back

int main(){

	string S;
	cin >> S;
	int ans = 0;
	for(int i = 0; i < S.size(); i ++){
		if(S[i] == '2')ans ++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256