akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;

int solve(int x) {
	int d = __builtin_popcount(x);
	if(d==0) return 0;
	return solve(x % d) + 1;
}


int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	string x;
	cin>>n>>x;
	vector<vi> pref(3, vi(n+2)), suf(3, vi(n+2)), p(3, vi(n+2));
	vi d(3);
	for(int i=0; i<n; ++i) {
		if(x[i] == '1') d[0]++;
	}
	d[1] = d[0] - 1;
	d[2] = d[0] + 1;
	for(int it=0; it<3; ++it) {
		if(d[it] <= 0) continue;
		p[it][0]=1;
		for(int i=1; i<=n; ++i) {
			pref[it][i] = pref[it][i-1];
			if(x[n-i] == '1') {
				pref[it][i] += p[it][i-1];
				pref[it][i] %= d[it];
				suf[it][i] += p[it][i-1];
				suf[it][i] %= d[it];
			}
			p[it][i] = p[it][i-1] * 2 % d[it];
		}

		for(int i=n; i>=1; --i) {
			suf[it][i] += suf[it][i+1];
			suf[it][i] %= d[it];
		}
	}
	
	reverse(x.begin(), x.end());

	for(int i=n; i>=1; --i) {
		if(x[i-1] == '0') {
			int rem = pref[2][i-1] + suf[2][i+1] + p[2][i-1];
			rem %= d[2];
			cout<<solve(rem) + 1<<'\n';
		}
		else {
			if(d[1] <= 0) cout<<0<<'\n';
			else {
				int rem = pref[1][i-1] + suf[1][i+1];
				rem %= d[1];
				cout<<solve(rem) + 1<<'\n';
			}
		}
	}

}


Measured memory_bytes: 11308
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
  seen[v] = true;
  for (auto next_v : G[v]) {
    if (seen[next_v]) continue;
    dfs(G, next_v);  // 再帰的に探索
  }
}

int main() {
  // 頂点数と辺数
  int N, M;
  cin >> N >> M;

  // グラフ入力受取
  Graph G(N);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  // 全頂点が訪問済みになるまで探索
  int count = 0;
  seen.assign(N, false);
  for (int v = 0; v < N; ++v) {
    if (seen[v]) continue;  // v が探索済みだったらスルー
    dfs(G, v);  // v が未探索なら v を始点とした DFS を行う
    ++count;
  }
  cout << count - 1 << endl;
}


Measured memory_bytes: 9540
N = int(input())
VC = []
V = list(map(int, input().split()))
C = list(map(int, input().split()))

for i in range(N):
    VC.append(V[i] - C[i])

ans = 0
for i in range(N):
    if VC[i] > 0:
        ans += VC[i]
print(ans)

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

int main(){
    int N,M,openflag=0,flag = 0;
    string baf_U,baf_T;
    string U[256];
    string T[256];
    cin >> N;
    for(int i= 0;i<N;i++){
        cin >> baf_U;
        U[i] = baf_U;
    }
    cin >> M;
    for(int i=0;i<M;i++){
        cin >> baf_T;
        T[i] = baf_T;
    }
    for(int i=0;i<M;i++){
        for(int k = 0;k<N;k++){
            if(U[k]==T[i]){
                flag = 1;
            }
        }
        if(flag ==1){
            if(openflag==0){
                cout <<"Opened by "<<T[i]<<endl;
                openflag = 1;
            }else{
                cout <<"Closed by "<<T[i]<<endl;
                openflag = 0;
            }
        }else{
            cout <<"Unknown "<<T[i]<<endl;
        }
        flag = 0;
    }
    return 0;
}


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

using pa = pair<string, int>;

int main() {
  int N;
  cin >> N;
  vector<pair<pa,int>> a(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i].first.first >> a[i].first.second;
    a[i].first.second *= -1;
    a[i].second = i;
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < N; ++i) {
    cout << a[i].second + 1 << endl;
  }
}
  

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

int main(){
  ull N,a,b,c,d,e;
  cin>>N>>a>>b>>c>>d>>e;
  ull m=a;
  if (m>b)
    m=b;
  if (m>c)
    m=c;
  if (m>d)
    m=d;
  if (m>e)
    m=e;
  
  ull fastmin=0;
  fastmin=N/m;
  if (N%m!=0)
    fastmin++;
  cout<<(fastmin+4)<<endl;
  return 0;
}

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

typedef long long ll;
#define int ll
#define pb push_back
const int INF = 1e18;

signed main(){

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

	int n; cin>>n;
	int cost[n+1][3];
	for(int i=1;i<=n;i++)
		cin>>cost[i][0]>>cost[i][1]>>cost[i][2];

	vector<vector<int>> dp(n+1,vector<int> (3,-INF));
	dp[1][0] = cost[1][0], dp[1][1] = cost[1][1], dp[1][2] = cost[1][2];

	for(int i=1;i<n;i++){
		dp[i+1][0] = max(dp[i][1],dp[i][2]) + cost[i+1][0];
		dp[i+1][1] = max(dp[i][0],dp[i][2]) + cost[i+1][1];
		dp[i+1][2] = max(dp[i][1],dp[i][0]) + cost[i+1][2];
	}

	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));

	return 0;
}

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

using namespace std;

int main()
{
    int h,w;
    scanf("%d%d",&h,&w);
    int d[h][w];
    for(int o=0;o<h;o++)
    {
        for(int i=0;i<w;i++)
        {
            int a;
            scanf("%d",&a);
            d[o][i]=a;
        }
    }
    for(int o=0;o<h;o++)
    {
        for(int i=0;i<w;i++)
        {
            int b;
            scanf("%d",&b);
            d[o][i]-=b;
        }
    }
    const int off=12800;
    vector<bool> v[h][w];
    for(int o=0;o<h;o++) for(int i=0;i<w;i++) v[o][i].resize(2*off+1,0);
    v[0][0][d[0][0]+off]=1;
    v[0][0][-d[0][0]+off]=1;
    for(int o=0;o<h;o++)
    {
        for(int i=0;i<w;i++)
        {
            for(int j=0;j<=2*off;j++)
            {
                if(v[o][i][j]==0) continue;
                if(o<h-1)
                {
                    v[o+1][i][j+d[o+1][i]]=1;
                    v[o+1][i][j-d[o+1][i]]=1;
                }
                if(i<w-1)
                {
                    v[o][i+1][j+d[o][i+1]]=1;
                    v[o][i+1][j-d[o][i+1]]=1;
                }
            }
        }
    }
    int res=off;
    for(int i=off;i<=2*off;i++) if(v[h-1][w-1][i]) res=min(res,i-off);
    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 22656
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
#define inf 0x3f3f3f3f
char S[N];
int n, ans, f[N][5];
int main()
{
	scanf("%s", S + 1);
	n = strlen(S + 1);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 4 && j <= i; j++)
		{
			int mx = 0;
			for (int k = 0; k <= 4 && k <= i - j; k++)
				if (k != j)
					mx = max(mx, f[i - j][k]);
				else
				{
					int flg = 0;
					for (int l = 0; l < j; l++)
					{
						if (S[i - l] != S[i - l - j])
						{
							flg = 1;
							break;
						}
					}
					if (flg)
						mx = max(mx, f[i - j][k]);
				}
			f[i][j] = mx + 1;
		}
	}
	for (int i = 1; i <= 4 && i <= n; i++)
		ans = max(ans, f[n][i]);
	printf("%d\n", ans);
}


Measured memory_bytes: 4352
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Integer []a = new Integer[10];
		for(int i = 0; i < 10; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();
		Arrays.sort(a, Collections.reverseOrder());
		for(int i = 0; i < 3; i++) {
			System.out.println(a[i]);
		}
	}
}



Measured memory_bytes: 26252
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
aa=[]
for i in range(n):
    aa.append(int(input()))
ma = max(aa)
if aa.count(ma) > 1:
    for _ in range(n):
        print(ma)
else:
    for i in range(n):
        if aa[i] != ma:
            print(ma)
        else:
            print(max(aa[:i]+aa[i+1:]))

Measured memory_bytes: 15604
#include<cstdio>
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		if(i>=1&&i<=9)ans++;
		if(i>=100&&i<=999)ans++;
		if(i>=10000&&i<=99999)ans++;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
using System;

class Program
{
    static void Main()
    {
        string[] s = Console.ReadLine().Split(' ');
        int a = int.Parse(s[0]);
        int b = int.Parse(s[1]);
        int c = int.Parse(s[2]);

        Range r = new Range();
        Console.WriteLine(r.range(a,b,c) ? "Yes" : "No");
    }
}

class Range
{
    public bool range(int a, int b,int c)
    {
        if (a < b && b < c)
        {
            return true;
        }
        else
            return false;
    }
}

Measured memory_bytes: 8800
n=int(input())
h=list(map(int,input().split()))


h[0]-=1
ans="Yes"
for i in range(n-1):

  if h[i+1]==h[i]:
    continue
  elif h[i+1]>h[i]:
    h[i+1]-=1
  else:
    ans="No"
    break
print(ans)

Measured memory_bytes: 14224
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
nums = []

for i in range(n):
    nums.append(getN())

cur_max = 1
ans = nums[0] - 1

for num in nums[1:]:
    if num <= cur_max:
        pass
    elif num == cur_max + 1:
        cur_max += 1
    else:
         ans += (num - cur_max - 2) // (cur_max + 1) + 1

    # print(num, cur_max, ans)

print(ans)
"""
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1 4 1 5 9 2 6 5 3 5 8 9 7 9 (2)
1 1 1 1 5 9 2 6 5 3 5 8 9 7 9 (3)
1 1 1 1 1 9 2 6 5 3 5 8 9 7 9 (5)
1 1 1 1 1 1 2 6 5 3 5 8 9 7 9 (9)
1 1 1 1 1 1 2 2 5 3 5 8 9 7 9 (10)
1 1 1 1 1 1 2 2 2 3 5 8 9 7 9 (11)
1 1 1 1 1 1 2 2 2 3 1 1 1 1 1 (18)
"""

Measured memory_bytes: 45148
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
#define mp make_pair 
#define pii pair <int , int > 
#define pll pair < ll , ll >
int main(){
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
    int n , k ;
    cin >> n >> k ;
    ll c[n + 1][n + 1] , mod = 1000000007;
    memset(c , 0 , sizeof(c)) ;
    c[0][0] = 1 ;
    for(int i = 1; i <= n ; i++) {
        c[i][0] = 1; 
        for(int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%mod;
            // cout << i << " " << j << " " << c[i][j] << '\n';
        }
    }
    for(int i = 1 ; i <= k ; i++){
        cout << (c[n - k + 1][i]*c[k-1][i - 1])%mod << '\n';
    }
}

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

typedef vector< long long > vi;
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define ll long long

ll cost(ll n, ll h[]);

ll dp[100005];
ll k;

int main(void)
{
    fill_n(dp, 100005, -1);
    ll n;
    dp[1] = 0;
    cin >> n >> k;
    ll h[n];
    for (int i = 0; i < n; i++)
        cin >> h[i];
    
    cout << cost(n, h) << "\n";
}

ll cost(ll n, ll h[])
{
    if (n < 1)
        dp[n] = 1000000000000;
    
    if (dp[n] == -1)
    {
        ll mincost = 1000000000000;
        for (int i = 1; i <= min(n - 1 ,k); i++)
            mincost = min(mincost, cost(n - i, h) + abs((h[n - 1] - h[n - i - 1])));
        dp[n] = mincost;
    }
    
    return dp[n];
}

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

public class Main {

    Scanner sc = new Scanner(System.in);

    void show(final int[] xs) {
        if (xs != null) {
            String out =
                    Arrays.stream(xs)
                            .mapToObj(Integer::toString)
                            .collect(Collectors.joining(" "));
            System.out.println(out);
        }
    }

    void solve() {
        // Input
        int n = sc.nextInt();
        int[] R = new int[n];
        for (int i = 0; i < n; i++) {
            R[i] = sc.nextInt();
        }

        // Solve
        int swapCount = 0;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = n - 1; i >= 1; i--) {
                if (R[i] < R[i - 1]) {
                    int tmp = R[i];
                    R[i] = R[i - 1];
                    R[i - 1] = tmp;
                    swapCount++;
                    flag = true;
                }
            }
        }
        // Output
        show(R);
        System.out.println(swapCount);
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}



Measured memory_bytes: 32676
N,a,b,c,d = map(int,input().split())
n = N - 1
ans = "NO"
for i in range(n+1):
    m1 = i*d - (n-i)*c
    m2 = -1*(n-i)*d + i*c
    if m1 <= m2:
        if a + m1 <= b and b <= a+ m2:
            ans = "YES"
            #print(m1,m2)
            break
    else:
        if a + m2 <= b and b <= a + m1:
            ans = "YES"
            #print(m1,m2)
            break
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  int h, w;
  string s, t;
  while(1) {
    h = w = 0;
    s = t = "";
    cin >> h >> w;
    if (h == 0 && w == 0) break;
    for (int i = 0; i < w; i++) {
      if (i % 2 == 0) s += "#";
      if (i % 2 == 1) s += ".";
     }
    for (int j = 0; j < w; j++) {
      if (j % 2 == 1) t += "#";
      if (j % 2 == 0) t += ".";
    }
    for (int k = 0; k < h; k++) {
      if (k % 2 == 0) cout << s << endl;
      if (k % 2 == 1) cout << t << endl;
    }
    cout << endl;
  }
}


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

int main() {
  int N,M,C;
  cin >>N>>M>>C;
  vector<int>B(M);
  for(int i=0;i<M;i++){
    cin>>B.at(i);
  }
  vector<vector<int>>A(N,vector<int>(M));
  for(int i=0;i<N;i++){  
    for(int j=0;j<M;j++){
      cin>>A.at(i).at(j);
    }
  }  
  int sum=0;
  int count=0;
  for(int i=0;i<N;i++){ 
    sum=0;
    for(int j=0;j<M;j++){
      //cout<<B.at(j)<<" "<<A.at(i).at(j)<<" "<<B.at(j)*A.at(i).at(j)<<endl;
      sum+=B.at(j)*A.at(i).at(j);
    }
    if(sum+C>0)count++;
  }
  cout <<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 60);
constexpr ll MOD = 1000000007ll;

// struct ---------------------------------------------

// function -------------------------------------------


// main -----------------------------------------------

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

    vector<bool> is_prime(1000001, true);
    is_prime[0] = is_prime[1] = false;

    vector<ll> prime_table;
    REP(i, 1000001){
        if(is_prime[i] == true){
            prime_table.push_back(i);
            for(ll k = i * i; k < 1000001; k += i){
                is_prime[k] = false;
            }
        }
    }

    ll cnt = 0;
    for(ll i = 0; i < (ll)(prime_table.size()); i ++){
        ll ppp = prime_table[i];
        while(n % ppp == 0){
            n /= ppp;
            cnt ++;
            ppp *= prime_table[i];
        }
        while(n % prime_table[i] == 0){
            n /= prime_table[i];
        }
    }
    if(n != 1){
        cnt ++;
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 4440
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}



signed main(){

    int N; cin >> N;
    vec p(N); readv(p);
    SORT(p);
    int ans = 0;
    REP(i, N) ans += p[i];
    ans -= p[N - 1] / 2;
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n;
    scanf("%d", &n);
    int h[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &h[i]);
    }
    int ans = 0;
    int max = 0;
    for(int i = 0; i < n; i++){
        if(h[i] >= max){
            ans += 1;
            max = h[i];
        }
    }
    printf("%d\n", ans);
    return 0; 
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define debugP int debug_point; cin>>debug_point;
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
ll pown(ll fi,ll se){
  ll ans=1;
  rep(i,se){
    ans*=fi;
  }
  return ans;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}

/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/


int main(){
ll a,b,q;
cin>>a>>b>>q;
vec(s,a+2);
vec(t,b+2);
vec(x,q);
repf(i,1,a+1){
  cin>>s[i];
}
repf(i,1,b+1){
  cin>>t[i];
}
s[0]=-10000000000;
s[a+1]=30000000000;
t[0]=-100000000000;
t[b+1]=300000000000;
rep(i,q)cin>>x[i];
rep(i,q){
  ll y[2];
  ll z[2];
  ll ans=LLONG_MAX;
  
  y[0]=*lower_bound(&s[0],&s[a+2],x[i]);
  y[1]=*(lower_bound(&s[0],&s[a+2],x[i])-1);
  z[0]=*lower_bound(&t[0],&t[b+2],x[i]);
  z[1]=*(lower_bound(&t[0],&t[b+2],x[i])-1);
  rep(j,2){
    rep(k,2){
      ans=min(ans,abs(y[j]-x[i])+abs(z[k]-y[j]));
      ans=min(ans,abs(z[j]-x[i])+abs(y[k]-z[j]));
    }
  }
  op(ans);
}
return 0;
}

Measured memory_bytes: 3712
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

bool chk(string s) {
  ll n = (ll)s.size();
  ll n2 = n / 2;
  bool ret = true;
  rep(i, n2) {
    if(s[i] != s[n-1-i]){
      ret = false;
      break;
    }
  }
  return ret;
}

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

  bool c1 = chk(s);
  if(!c1) {
    puts("No");
    return 0;
  }
  string s2 = s.substr(0, s.size()/2);
  bool c2 = chk(s2);
  if(!c2) {
    puts("No");
    return 0;
  }

  string s3 = s.substr(s.size()/2+1, s.size()/2);
  bool c3 = chk(s3);
  if(!c3) {
    puts("No");
    return 0;
  }

  puts("Yes");
  return 0;

}


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

vector<int> binary(int i, int n, int N){
    int x = 1;
    rep(j,N){
        x *= n;
    }
    vector<int> vec(N);
    rep(j,N){
        x /= n;
        vec[j] = i / x;
        i -= x * vec[j];
    }
    return vec;
}

int vector_finder(vector<int> vec, int number){
    int len = vec.size();
    int cnt = 0;
    rep(i,len){
        if (vec[i] == number) cnt++;
    }
    if (cnt >= 1) return 1;
    else return 0;
}

int main(){
    int N,M;
    cin >> N >> M;
    vector<pair<int,int> > route(M);
    rep(i,M){
        cin >> route[i].first >> route[i].second;
        route[i].first--;
        route[i].second--;
    }
    vector<vector<int> > connection(N, vector<int>(0));
    rep(i,M){
        connection[route[i].first].push_back(route[i].second);
        connection[route[i].second].push_back(route[i].first);
    }
    int num = 1;
    rep(i, N - 1){
        num *= (N - 1);
    }
    int ans = 0;
    rep(i,num){
        vector<int> road = binary(i, N - 1, N - 1);
        vector<int> count(N - 1, 0);
        bool double_count = false;
        bool possible = true;
        rep(j,N - 1){
            count[road[j]]++;
        }
        rep(j,N - 1){
            if (count[j] >= 2) double_count = true;
        }
        rep(j,N - 1){
            road[j]++;
        }
        if (double_count) continue;
        else{
            if (vector_finder(connection[0], road[0]) == 0){
                possible = false;
            }
            rep(j,N - 2){
                if (vector_finder(connection[road[j]], road[j + 1]) == 0){
                    possible = false;
                }
            }
            if (possible) ans++;
        }
    }
    cout << ans << endl;
}


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

signed main(){
	int n;
	cin>>n;
	int v[n];
	r(i,n)cin>>v[i];
	int q;
	cin>>q;
	while(q--){
		int w,e,re;
		cin>>w>>e>>re;
		rotate(v+w,v+e,v+re);
	}
	r(i,n){
		if(i)cout<<' ';
		cout<<v[i];
	}
	cout<<endl;
}


Measured memory_bytes: 3144
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		
		if(S.charAt(2)==S.charAt(3) && S.charAt(4)==S.charAt(5)) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

		sc.close();
	}
}

Measured memory_bytes: 21844
from collections import deque
INF = 10 ** 5
def bfs():
    que = deque([(1, 1)])
    cnt = [[0] * (N + 2) for _ in range(4)]
    cnt[1][1] = A[1][1]
    steps = [(1, 0), (0, 1)]
    while que:
        i, j = que.popleft()
        for di, dj in steps:
            ni, nj = i + di, j + dj
            if cnt[ni][nj] < cnt[i][j] + A[ni][nj]:
                cnt[ni][nj] = cnt[i][j] + A[ni][nj]
                que.append((ni, nj))
    return cnt[2][N]

N = int(input())
A = [[-INF] * (N + 2)]
for _ in range(2):
    a = list(map(int, input().split()))
    A.append([-INF] + a + [-INF])
A.append([-INF] * (N + 2))
res = bfs()
print(res)


Measured memory_bytes: 9356
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i,j,a,b,arr[200009];
    scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  m=arr[0];
  a=1;
  for(i=1;i<n;i++)
  {
      if(arr[i]<=m)
      {
          m=arr[i];
          a++;
      }
  }
  printf("%d\n",a);
}


Measured memory_bytes: 1024
import java.util.Scanner;
 
class Main
{
	public static void main (String[] args){
		Scanner cin = new Scanner(System.in);
		int [] a = new int[110];
		int i;
		int max = 0;
 
		while (cin.hasNext()){
			i = cin.nextInt();
			a[i]++;
		}
 
		for (i = 0; i < 100; i++){
			if (max < a[i]){
				max = a[i];
			}
		}
 
		for (i = 0; i < 100; i++){
			if (max == a[i]){
				System.out.println(i);
			}
		}
	}
}

Measured memory_bytes: 26268
#include <iostream>
using namespace std;
int main(void){
  long N,M;
  cin >> N >> M;
  
  if(N == 1 && M == 1)
    cout << 1 << endl;
  else if(N == 1)
    cout << M - 2 << endl;
  else if(M == 1)
    cout << N - 2 << endl;
  else
    cout << (N - 2) * (M - 2) << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define H 250

int main()
{
  int n,i;
  int A[H];
  scanf("%d",&n);
  for(i=1;i<=n;i++)
     scanf("%d",&A[i]);
    
  for(i=1;i<=n;i++)
    {
      printf("node %d: key = %d, ",i,A[i]);
      if(i!=1)
        {
          printf("parent key = %d, ",A[i/2]);
        }
      if(2*i<=n)
        {
          printf("left key = %d, ",A[2*i]);
        }
      if(2*i+1<=n)
        {
          printf("right key = %d, ",A[2*i+1]);
        }
      printf("\n");
    }
  return 0;
}



Measured memory_bytes: 2104
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion

vector<vector<pair<int, int>>> g(100100);
vector<int> res(100100);

void dfs(int now, int p, int col)
{
	res[now] = col;
	for (auto q : g[now])
	{
		if (q.first == p)continue;
		if (q.second)dfs(q.first, now, 1 - col);
		else dfs(q.first, now, col);
	}
}

int main()
{
	int n; cin >> n;
	rep(i, n - 1)
	{
		int u, v, w; cin >> u >> v >> w;
		--u, --v, w %= 2;
		g[u].push_back(make_pair(v, w));
		g[v].push_back(make_pair(u, w));
	}
	dfs(0, -1, 0);
	rep(i, n)cout << res[i] << endl;
}

Measured memory_bytes: 11836
/* be name Khoda */
#include <bits/stdc++.h>
using namespace std;

const int MAX_BIT = 30, N = 200 * 1001;
int a[N], b[N], n, num_bit[MAX_BIT], a_bit[N], b_bit[N], ans;

void solve(int biti) {
	int t = (1 << (biti + 1));
	for (int i = 0; i < n; i++) {
		a_bit[i] = a[i] % t;
//		cout << a_bit[i] << " * * ";
	}
//	cout << endl;
	for (int i = 0; i < n; i++) {
		b_bit[i] = b[i] % t;
//		cout << b_bit[i] << "  &  ";
	}
//	cout << endl << endl;
//	sort(a_bit, a_bit + n);
	sort(b_bit, b_bit + n);
	int t2 = t / 2;
//	cout << t2 << " *** \n";
//	for (int i = 0; i < n; i++)
//		cout << a_bit[i] << "   ";
//	cout << endl;
//	for (int i = 0; i < n; i++)
//		cout << b_bit[i] << "  /  ";
//	cout << endl;
	for (int i = 0; i < n; i++) {
		int dif = t2 - a_bit[i],
			dif2 = t - a_bit[i];
		auto k = lower_bound(b_bit, b_bit + n, dif) - b_bit,
			 k2 = lower_bound(b_bit, b_bit + n, dif2) - b_bit;
//		cout << dif << "  **  " << dif2 << "  ^& ";
//		cout << k2 - k << " --- \n";
		num_bit[biti] += (k2 - k > 0 ? k2 - k : 0);
	}
	for (int i = 0; i < n; i++) {
		int dif = t2 - a_bit[i] + t,
			dif2 = t - a_bit[i] + t;
		auto k = lower_bound(b_bit, b_bit + n, dif) - b_bit,
			 k2 = lower_bound(b_bit, b_bit + n, dif2) - b_bit;
		num_bit[biti] += (k2 - k > 0 ? k2 - k : 0);
	}
//	cout << " ====>  "  << num_bit[biti] << endl;
}
	
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cin >> b[i];
	for (int i = 0; i < MAX_BIT; i++) 
		solve(i);
	for (int i = 0; i < MAX_BIT; i++)
		ans += (num_bit[i] % 2 == 0 ? 0 : (1 << i));
	cout << ans << endl;
}

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

int dp[100000]={0};
std::vector<int> v;

int rec(int i){
  if(i<=0)
    return 0;
  if (i==1) 
    return abs(v[1] - v[0]);
  if(dp[i]!=-1){
    return dp[i];
  }
  else {
    dp[i]=min(abs(v[i]-v[i-1])+rec(i-1),abs(v[i]-v[i-2])+rec(i-2));
    return dp[i];
  }
}

int main(){
  //freopen("input.txt","r",stdin);
  long long n,k;
  cin>>n;
  for(long long i=0;i<n;i++){
    cin>>k;
    v.push_back(k);
  }
  memset(dp, -1, sizeof(dp)) ;
  cout<<rec(n-1);
  return 0;
}

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

int main()
{
	long n;
	cin>>n;
	long count = 0;
	long arr[n];
	cin>>arr[0];
	for(long i=1; i<n; i++)
	{
		cin>>arr[i];
		if(arr[i]<arr[i-1]) 
		{
			count += (arr[i-1]-arr[i]);
			arr[i] = arr[i-1];
		}
	}
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 5152
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);
//aryread!string();
//auto PS = new Tuple!(long,string)[](M);
//x[]=1;でlong[]全要素1に初期化
void main()
{
    auto n = sread();
    // writeln(n[$ - 1]);
    switch (n[$ - 1])
    {
    case '2':
        writeln("hon");
        break;
    case '4':
        writeln("hon");
        break;
    case '5':
        writeln("hon");
        break;
    case '7':
        writeln("hon");
        break;
    case '9':
        writeln("hon");
        break;
    case '0':
        writeln("pon");
        break;
    case '1':
        writeln("pon");
        break;
    case '6':
        writeln("pon");
        break;
    case '8':
        writeln("pon");
        break;
    case '3':
        writeln("bon");
        break;
    default:

    }

}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}

void arywrite(T)(T a)
{
    a.map!text.join(' ').writeln;
}


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

int main()
{
    int n;
    int i;
    long long int a = 2, b = 1, ans;
    
    cin >> n;
    
    if(n == 0) {
        ans = a;
    } else if (n == 1) {
        ans = b;
    } else {
        
        for(i = 2; i <= n; i++) {
            ans = a + b;
            a = b;
            b = ans;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

Measured memory_bytes: 256
#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 ALL(x) x.begin(),x.end()


void solve(){
    int N;cin>>N;
    if(N==0)exit(0);
    vector<int>A(N);
    REP(i,N)cin>>A[i];
    sort(ALL(A));
    int sum = 0;
    FOR(i,1,N-1)sum+=A[i];
    cout<<sum/(N-2)<<endl;
}
signed main(){
    while(true){
        solve();
    }
}


Measured memory_bytes: 3128
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,ans,l[101],d[101];
int main(){
	scanf("%d%d",&n,&x);
	for(register int i=1;i<=n;i++)scanf("%d",&l[i]);
	for(register int i=1;i<=n+1;i++){
		if(d[i-1]+l[i-1]<=x){
			++ans;
			d[i]=d[i-1]+l[i-1];
		}
		else break;
	}
	printf("%d",ans);
}

Measured memory_bytes: 128
H,W = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(H)]
N = 0
ans = ""
for i in range(H):
    if i%2 == 0:
        for j in range(0,W,1):
            if a[i][j] % 2 == 1:
                if j == W-1:
                    if i == H-1:
                        break
                    else:
                        N += 1
                        ans += "{} {} {} {}\n".format(i+1,j+1,i+2,j+1)
                        a[i+1][j] += 1
                else:
                    N += 1
                    ans += "{} {} {} {}\n".format(i+1,j+1,i+1,j+2)
                    a[i][j+1] += 1
    else:
        for j in range(W-1,-1,-1):
            if a[i][j] %2 == 1:
                if j == 0:
                    if i == H-1:
                        break
                    else:
                        N += 1
                        ans += "{} {} {} {}\n".format(i+1,j+1,i+2,j+1)
                        a[i+1][j] += 1
                else:
                    N += 1
                    ans += "{} {} {} {}\n".format(i+1,j+1,i+1,j)
                    a[i][j-1] += 1
if N == 0:
    print(N)
else:
    print(N)
    print(ans)

Measured memory_bytes: 11096
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,x,y = readInts()

d = defaultdict(int)

for i in range(1,n+1):
	for j in range(i+1,n+1):
		d[min(abs(i-j),abs(i-x)+1+abs(y-j),abs(i-y)+1+abs(j-x))]+=1

for i in range(1,n):
	print(d[i])

Measured memory_bytes: 9676
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    REP(i, 0, N) cin >> A[i];
    sort(ALL(A));

    vector<ll> S(N);
    S[0] = A[0];
    REP(i, 1, N) S[i] += S[i - 1] + A[i];

    int ans = 0;
    REP(i, 0, N) {
        if (i == N - 1) {
            ans++;
            break;
        }
        
        if (S[i] * 2 >= A[i + 1]) {
            ans++;
        } else {
            ans = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define LL long long

const int N = 1e2 + 5;

int n, flag = 1;
char str[N];

int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    for(int l = 1; l <= n; ++l) if(str[n - l + 1] != str[l]) flag = 0;
    int end = (n - 1) / 2;
    for(int l = 1; l <= end; ++l) if(str[end - l + 1] != str[l]) flag = 0;
    for(int l = (n + 3) / 2; l <= n; ++l) if(str[n - l + 1] != str[l]) flag = 0;
    if(flag) puts("Yes");
    else puts("No"); 
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n%10==2||n%10==4||n%10==5||n%10==7||n%10==9||n==2||n==4||n==5||n==7||n==9)
    {
        cout<<"hon"<<endl;
    }
    else if(n%10==3||n==3)
    {
        cout<<"bon"<<endl;
    }
    else
        cout<<"pon"<<endl;

}


Measured memory_bytes: 3584
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    A = list(sorted(list(map(int, input().split()))))
    ans = 0
    for i in range(N - 1):
        ans += A[i + 1] - A[i]
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
 int N;
 cin >> N;
 
 vector<int> vec(N);
   for(int a = 0;a < N;a++) {
     cin >> vec.at(a);
   }
  
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  
  int Ascore = 0;
  int Bscore = 0;
    
  for(int i = 0;i < N;i++)  {
    
    if(i%2 == 0) {
      Ascore += vec.at(i);
    }
    
    else if(i%2 == 1) {
      Bscore += vec.at(i);
    }
  }  
  
  cout << Ascore - Bscore << endl;
}


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

int main() {
  int a,b,c;
  int deck[10];
  while(cin>>a>>b>>c){
    for(int i=0; i<10; i++) deck[i]=i+1;
    deck[a-1]=1000;
    deck[b-1]=1000;
    deck[c-1]=1000;
    sort(deck,deck+10);
    for(int i=0; i<4; i++) {
      if(a+b+deck[i]>20) {goto aho;}
    }
    cout<<"YES"<<endl;
    continue;
  aho:
    cout<<"NO"<<endl;
  }

  return 0;
}

Measured memory_bytes: 1168
#include <stdio.h>


int main(void)
{
	int H, W;
	int h, w;

	while (1) {
		scanf("%d%d", &H, &W);
		if (H == 0 && W == 0) break;
		
		for (w = 0; w < W; w++) putchar('#');
		putchar('\n');

		for (h = 2; h < H; h++) {
			putchar('#');
			for (w = 2; w < W; w++) putchar('.');
			putchar('#');
			putchar('\n');
		}

		for (w = 0; w < W; w++) putchar('#');
		putchar('\n');

		putchar('\n');
	}
	return 0;
}



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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> 
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main(){
	int h,w,k;
	cin >>h >>w >>k;
	vector<ll> dp(w+3);
	dp[0] = 1;
	
	rep(i, h){
		vector<ll> np(w+3);
		rep(j, w) rep(s, 1<<(w-1)){
			bool consw = false;
			rep2(p, 1, w-1){
				if((s>>p &1 )&&(s>>(p-1)&1))  consw=true;
			}
			if(consw) continue;
			if(s>>j &1) (np[j+1] += dp[j])%=mod;
			else if(j>0 && s>>(j-1) &1) (np[j-1] += dp[j])%=mod;
			else (np[j] += dp[j])%=mod;
		}
		swap(dp, np);
	}
	cout << dp[k-1] <<"\n";
}



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

int main() {
  int n;
  cin >> n;
  int nums[n];
  int max_num = 0;
  for (int i = 0; i < n; i++) {
    nums[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (i == 0 && x != 0) {
      cout << 0 << endl;
      return 0;
    }
    nums[x]++;
    max_num = max(x, max_num);
  }
  if (nums[0] != 1) {
    cout << 0 << endl;
    return 0;
  }
  long long count_num = 1;
  for (int i = 0; i < max_num; i++) {
    if (i != 0 && nums[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
    for (int j = 0; j < nums[i + 1]; j++) {
      count_num *= (long long)nums[i];
      count_num = count_num % 998244353;
    }
  }
  cout << count_num << endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define mem(a,v) memset(a,v,sizeof a)
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define max3(x,y,z) max(x,max(y,z))
#define min3(x,y,z) min(x,min(y,z))
#define f first
#define s second
#define fr(i,n) for(int j=i;j<n;j++)
#define rev(a) reverse(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define lb(a,v) lower_bound(all(a),v)
#define ub(a,v) upper_bound(all(a),v)
#define ins(v) insert(v)
#define pb(v) push_back(v)
#define sz(x) (int)(x).size()
#define MOD 1000000007
#define sf1(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sf4(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
using namespace std;
const int N=1e6+5,M=1e7+5,oo=0x3f3f3f3f;
vector<int>adj[N];
ll cost[N],cost1[N];
bool vis[N];
int s;
map<int,int>mp;
void dfs(int u)
{
	vis[u]=1;
	s+=mp[u];
	cost[u]+=s;
	for(int x:adj[u])
		if(!vis[x])	dfs(x);
	s-=mp[u];
}
int main() {
	int u,v,n,q;
    sf2(n,q);
    for(int i=0;i<n-1;i++)
    {
        sf2(u,v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<q;i++)
    {
        sf2(u,v);
        mp[u]+=v;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
        printf("%lld ",cost[i]);
    puts("");
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    cout << N/3 << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# https://atcoder.jp/contests/abc154/tasks/abc154_a

s, t = input().split()
a, b = [int(x) for x in input().split()]
u = input()
if s == u:
    a -= 1
if t == u:
    b -= 1
print(a, b)


Measured memory_bytes: 2940
N=int(input())
h=list(map(int,input().split()))

dp = [0 for i in range(N)]

dp[0]=0
dp[1]=abs(h[1]-h[0])

for i in range(2,N):
    dp[i]=min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2])
    
print(dp[N-1])

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

int main() {
    ll X, K, D;
    cin >> X >> K >> D;

    X = abs(X);
    ll n = X / D;

    ll distance = 0;
    if (K <= n) {
        distance = X - K * D;
    }
    else {
        ll d1 = X - n * D;
        ll d2 = (n+1) * D - X;
        if (n % 2 == K % 2) {
            distance = d1;
        }
        else {
            distance = d2;
        }
    }
    cout << distance << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    vector<string> S(N);
    for (int i = 0; i < N; i++)
    {
        cin >> S[i];
    }

    ll ans = 0;

    int a = 0;
    for (int b = 0; b < N; b++)
    {
        bool can = true;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                int newX = (i + a) % N;
                int newY = (j + b) % N;

                int newA = (newY - a);
                int newB = (newX - b);

                if(newA < 0){
                    newA+=N;
                }
                if(newB < 0){
                    newB+=N;
                }
                if (S[i][j] != S[newA][newB])
                {
                    can = false;
                }
            }
            if(!can){
                break;
            }
        }

        if (can)
        {
            ans++;
        }
    }

    cout << ans * N << endl;

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

#include <cstdio>

using namespace std;


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

	int a, b;
	cin >> a >> b;

	if (a + b == 15) {
		cout << '+' << '\n';
	}
	else if (a * b == 15) {
		cout << '*' << '\n';
	}
	else {
		cout << 'x' << '\n';
	}



	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
char s[100010];
int r;
int f(){
  int c=0,d[100010],n=0,i,j;
  while(s[r]-']'){//printf("%c",s[r]);
    if(s[r]==0)return 0;
    if(s[r]=='['){
      r++;
      d[c++]=f();
    }
    else n=n*10+s[r++]-'0';
  }//printf("%c",s[r]);
  r++;//printf("%d\n",c);
  if(c==0)return n/2+1;
  for(i=0;i<c;i++){
    n=d[i];
    for(j=i;j&&d[j-1]>n;j--)d[j]=d[j-1];
    d[j]=n;
  }//printf("\n");
  for(i=n=0;i<c/2+1;i++)n+=d[i];//printf("%d\n",n);
  return n;
}
int main(){
  int n;
  scanf("%d",&n);
  while(n--){
    scanf("%s",s);
    r=1;
    printf("%d\n",f());
  }
  return 0;
}



Measured memory_bytes: 2104
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long _x = x;
        int res = 0;
        while(x >= 10){
            res += 9;
            x /= 10;
        }
        res += (x-1);
        StringBuffer t = new StringBuffer();
        t.append(x);
        for (int i = 0; i < res/9; i++) {
            t.append("9");
        }
        long s = Long.parseLong(t.toString());
        if(s == _x){
            res++;
        }
        System.out.println(res);

        sc.close();
    }
}

class io {
    public static void br() {
        System.out.println("");
    }

    public static void yesno(boolean f) {
        System.out.println(f ? "yes" : "no");
    }

    public static void YesNo(boolean f) {
        System.out.println(f ? "Yes" : "No");
    }

    public static void YESNO(boolean f) {
        System.out.println(f ? "YES" : "NO");
    }

}

class Algo {
    public static int nibutan(int target, int[] ar) {
        // ar[i] >= target なる最小のiを探す
        int res;
        int high = ar.length;
        int low = 0;
        while (high > low) {
            res = (high + low) / 2;
            if (ar[res] < target) {
                // ↑↓ここを変える
                low = res + 1;
            } else {
                // ↓ここを変える
                high = res;
            }
        }
        return low;
    }

    public static boolean isOdd(int n) {
        return n % 2 == 1;
    }

    public static boolean isEven(int n) {
        return n % 2 == 0;
    }


}



Measured memory_bytes: 22608
#include <stdio.h>

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

//flagを用いたバブルソート
int bubbleSort(int A[],int N){
    int i,j;
    int sw = 0;
    unsigned short flag = 1;
    for(i=0;flag;i++){
        flag = 0;
        for(j=N-1;j>=i+1;j--){
            if(A[j]<A[j-1]){
                swap(&A[j],&A[j-1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main(void){
    int i, A[100], N, sw;
    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);
    
    sw = bubbleSort(A,N);
    
    for(i=0;i<N;i++){
        if(i) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n%d\n",sw);
    
    return 0;
}
    


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

int main() {
  int n,w;
  cin >> n >> w;
  vector<int> weight(n);
  vector<int> value(n);
  vector<vector<int>> dp(n+1, vector<int>(w+1,0));
  //入力
  for(int i=0;i<n;i++) {
    cin >> value.at(i) >> weight.at(i);
    //dpの操作
    //今入力した商品入れる？？？？？？？
    for(int j=1;j<w+1;j++) {
      if(0<=j-weight[i]) dp[i+1][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i]);
      else dp[i+1][j]=dp[i][j];
    }
  }
  cout<<dp[n][w]<<endl;
}


Measured memory_bytes: 6812
import java.util.Scanner;
    public class Main{
      public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        if((a*b)%2==0){
          System.out.println("Even");
        }else{
          System.out.println("Odd");
        }
      }
    }

Measured memory_bytes: 21844