akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
class segtree:
    """
    segment tree
    value store as object type and get update function(merge_func) from outside

    Attributes
    ----------
    n : int
        Number of elements
    initialize_func : func
        function for initialization
    merge_func : func
        function for merge x and y to x(this merge is distruction update)

    Methods
    -------
    update(i, x)
        update tree[i] value to x
    get(a, b)
        get value from [a, b)
        include a but not include b, return a merged value
    """
    def __init__(self, n, initialize_func, merge_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        initialize_func : func
            function for initialization
        merge_func : func
            function for merge x and y to x(this merge is distruction update)
        """
        self.n = n
        self.initialize = initialize_func
        self.merge = merge_func
        n2 = 1  # n2はnより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [initialize_func() for _ in range(n2 << 1)]

    def update(self, index, x):
        index += self.n2
        self.tree[index] = self.merge(self.tree[index], x)
        while index > 1:
            # (index ^ 1) はiと1の排他的論理和(XOR)
            x = self.merge(x, self.tree[index ^ 1])
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            self.tree[index] = self.merge(self.tree[index], x)

    def get(self, a, b):
        result = self.initialize()
        q = [(1, 0, self.n2)]
        while q:
            k, left, right = q.pop()
            if a <= left and right <= b:
                result = self.merge(result, self.tree[k])
                continue
            m = (left + right) // 2
            k <<= 1
            if a < m and left < b:
                q.append((k, left, m))
            if a < right and left < m:
                q.append((k + 1, m, right))
        return result


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    max_A = 3 * 10 ** 5 + 1

    seg = segtree(max_A, lambda: 0, max)
    for a in A:
        next = seg.get(max(0, a - K), min(a + K + 1, max_A))
        seg.update(a, next + 1)
    print(seg.get(0, max_A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 166424
import bisect


a,b,q = [int(_) for _ in input().split()]
s_l = [-float('inf')]
t_l = [-float('inf')]
x_l = []
for i in range(a):
    s_l.append(int(input()))
s_l.append(float('inf'))
for i in range(b):
    t_l.append(int(input()))
t_l.append(float('inf'))
for i in range(q):
    x_l.append(int(input()))
for i in range(q):
    x = x_l[i]
    s1_id = bisect.bisect_left(s_l, x) - 1 
    s2_id = s1_id + 1
    s1 = s_l[s1_id]
    s2 = s_l[s2_id]
    t1_id = bisect.bisect_left(t_l, x) - 1 
    t2_id = t1_id + 1
    t1 = t_l[t1_id]
    t2 = t_l[t2_id]
    res = float('inf')
    for s in [s1,s2]:
        for t in [t1,t2]:
            d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
            res = min(res, d1, d2)
    print(res)


Measured memory_bytes: 16152
#import<iostream>
#import<vector>
#import<cstdlib>
using namespace std;main(){int n,m,k,x,d,h,i,j,D[158][151][10];for(;cin>>n>>m,n;cout<<x<<endl){vector<pair<int,int> >S[151];for(i=0;i++<n;)for(cin>>k;k--;S[i].push_back(make_pair(x,d)))cin>>x>>d;fill(**D,*D[158],x=1e9);for(i=S[1].size();i--;)D[m][1][i]=0;for(i=S[2].size();i--;)D[m-1][2][i]=0;for(h=1;h++<n;)for(i=m;1+i;i--)for(j=S[h].size();j--;){for(k=S[h-1].size();k--;)D[i][h][j]=min(D[i][h][j],D[i][h-1][k]+(S[h][j].second+S[h-1][k].second)*abs(S[h][j].first-S[h-1][k].first));for(k=S[h-2].size();k--;)D[i][h][j]=min(D[i][h][j],D[i+1][h-2][k]+(S[h][j].second+S[h-2][k].second)*abs(S[h][j].first-S[h-2][k].first));}for(i=m;1+i;i--)for(j=S[n].size();j--;)x=min(x,D[i][n][j]);for(i=m;i;i--)for(j=S[n-1].size();j--;)x=min(x,D[i][n-1][j]);}}

Measured memory_bytes: 1864
use std::io::stdin;

fn main(){
    let x = geti64s()[0];
    let (d, m) = (x/11, x%11);
    println!("{}", match m {
        0         => d*2,
        x if x<=6 => d*2 + 1,
        _         => d*2 + 2
    });
}

#[allow(dead_code)]
fn getline() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn getvec() -> Vec<usize>{
    let line = getline();
    line.split_whitespace().map(|x| x.parse().unwrap()).collect()
}

#[allow(dead_code)]
fn geti64s() -> Vec<i64>{
    let line = getline();
    line.split_whitespace().map(|x| x.parse().unwrap()).collect()
}

#[allow(dead_code)]
fn getpair() -> (usize, usize){
    let nm = getvec();
    (nm[0], nm[1])
}

Measured memory_bytes: 4352
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
k=int(input())
count=0
for i in range(1,k+1):
    for j in range(i,k+1):
        for h in range(j,k+1):
            if i==j==h:
                x=gcd(i,j,h)
            elif i==j:
                x=3*gcd(i,j,h)
            elif j==h:
                x=3*gcd(i,j,h)
            else:
                x=6*gcd(i,j,h)
            count+=x
print(count)

Measured memory_bytes: 9516
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long n; cin >> n;
  	long long ans = 1, mat = pow(10,18);
    long long arr[n+5];
  	for(long long i=0;i<n;++i){
      cin >> arr[i];
    }
    sort(arr,arr+n);
    if(arr[0] == 0){ cout << 0; return 0; }
    for(int i=0;i<n;++i){
      if((double)mat/ans - arr[i] < 0) { cout << -1; return 0;}
      ans *= arr[i];
      if(ans > mat) { cout << -1; return 0;}
    }
    if(ans > mat) cout << -1;
  	else cout << ans;
  	return 0;
}

Measured memory_bytes: 4376
#include<bits/stdc++.h>
const int N = 2005;
using namespace std;
#define pb          push_back
#define m_p			make_pair
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define sz(x)       (int)x.size()
#define f			first
#define debug		cout<<"##########3"<<endl
#define mod			1000000007
#define ll			long long int
#define lMax		LLONG_MAX
int n, m;
vector<int> g[N], gr[N],gv[N];
int used[N];
vector<int> order;
vector<int> comp;
int ans[N];
int dp[N][N];
int t = 0,f=0,v=0;
int vis[3005],rec[3005],par[3005];
void dfsi(int a){
//	cout<<a<<"ji"<<endl;
	vis[a]=++t;
	rec[a]=1;
	for(auto it:gv[a]){
		if(!vis[it]){
			par[it] = a;
			dfsi(it);
		}
		else if(rec[it] && f<vis[it])
		{
			f = vis[it];
			v=it;
			par[it] = a;
			//cycle
			
		}
	}
	rec[a]=0;
}
void dfs(int v)
{
	used[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[to])
			continue;
		dfs(to);
	}
	order.push_back(v);
}
void dfs2(int v)
{
	comp.push_back(v);
	used[v] = 1;
	for (int i = 0; i < gr[v].size(); i++)
	{
		int to = gr[v][i];
		if (used[to])
			continue;
		dfs2(to);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		dp[a][b]=1;
		g[a].push_back(b);
		gr[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		if (used[i])
			continue;
		dfs(i);
	}
	reverse(order.begin(), order.end());
	for (int i = 1; i <= n; i++)
	{
		used[i] = 0;
	}
	for (int i = 0; i < order.size(); i++)
	{
		int id = order[i];
		if (used[id])
			continue;
		comp.clear();
		dfs2(id);
		if (comp.size() == 1)
			continue;
		//cout<<comp.size()<<endl;
		for (int j = 0; j < comp.size(); j++)
		{
			for(int ii=1;ii<=n;ii++){
				if(dp[comp[j]][ii]==1 && used[ii]==1)
					gv[comp[j]].pb(ii);
			}
		}
		dfsi(comp[0]);
		int q=v;
		int	c=1;
			vector<int> an;
			an.pb(q);
			while(par[v]!=q){
				c++;
				v = par[v];
				an.pb(v);
			}
			cout<<an.size()<<endl;
			rep(i,0,an.size()){
				cout<<an[i]<<endl;
			}
			return 0;
	}
 
	cout << -1;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

#define mt make_tuple
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sqr(x) ((ll)(x) * (x))

int main()
{
    int n;
    cin >> n;
    vi v(n);
    for(auto &z : v)cin >> z;

    int brojac = 0;
    int resenje = 0;

    for(int i = 0; i < n; i++)
    {
        int j;

        for(j = i + 1; j < n; j++)
        {
            if(v[j] <= v[j - 1])
            {
                brojac++;
            }

            else
            {
                resenje = max(brojac, resenje);
                brojac = 0;
                break;
            }
        }

        i = j - 1;
    }

    cout << max(brojac, resenje) << '\n';

    return 0;
}


Measured memory_bytes: 640
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int min =1;
		int max =100000;
		for(int i=0;i<M;i++) {
			int L = sc.nextInt();
			int R = sc.nextInt();
			if(L>min) {
				min = L;
			}
			if(R<max) {
				max = R;
			}
		}
		if(max>=min) {
			System.out.println(max-min+1);
		} else {
			System.out.println("0");
		}
	}
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  ll a,b,n;
  cin>>a>>b>>n;
  ll ans = 1e18;
  FOR(y,1,n+1){
    if(b%y != 0)continue;
    ll d = b/y;
    FOR(x,1,n+1){
      ll c = d*x;
      CHMIN(ans,abs(a-c));
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1156
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
n*k
*/



ll n,k,a[110],grundy[100010];

ll f(ll x){
	if(grundy[x]!=-1)return grundy[x];
	ll ans;
	set<int> s;
	rep(i,n){
		if(x-a[i]>=0)s.insert(f(x-a[i]));
	}
	rep(i,n+1){
		if(s.count(i)==0){
			ans=i;
			break;
		}
	}
	return grundy[x]=ans;
}

int main(void){
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	//
	rep(i,k+1)grundy[i]=-1;
	grundy[0]=0;
	//
	cout<<(f(k)!=0?"First":"Second")<<endl;
	return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,flag=1;
    scanf("%d",&n);
    for(int i=0;i<=n&&flag;i++)
        for(int j=0;j<=n&&flag;j++)
            if(4*i+7*j==n)
            {
                printf("Yes");
                flag=0;
            }
    if(flag)
        printf("No");
}


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

void solve()
{
    // 入力の処理
    int N;
    string S;
    cin >> N;
    cin >> S;
    string curr = "";
    int c = 0;
    string sb;
    for (int i = 0; i < N; i++)
    {
        sb = S.substr(i, 1);
        if (curr != sb)
        {
            c++;
        }
        curr = sb;
    }

    cout << c << endl;

    return;
}

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

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

int main(){
  int x;
  int count=0;
  cin>>x;
  x--;
  while(count==0){
    count=1;
    x++;
    for(int i=2;i<x;i++){
      if(x%i==0){
        count=0;
      }
    }
  }
  cout<<x<<endl;
  return 0;
}

Measured memory_bytes: 256
import math
import collections

def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


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

a_dic = collections.Counter(A)


default = {}
for key, value in a_dic.most_common():
  if value >= 2:
    default[key] = combinations_count(value, 2)
  else:
    default[key] = 0
default_amount = sum(default.values())

for k in range(N):
  key = A[k]
  value = a_dic[key] - 1
  if value >= 2:
    diff = combinations_count(value, 2)
  else:
    diff = 0
  print(default_amount - default[key] + diff)


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

ll a,b,c,x,y ;

ll cost(ll x,ll y, ll z)
{
	return a*x+b*y+c*z ;
}

ll minimum(ll a, ll b, ll c)
{
	if(a<=b and a<=c)
		return a ;
	else if(b<=a and b<=c)
		return b ;
	else 
		return c ;
}

int main()
{
	cin >> a >> b >> c >> x >> y ;
	ll mini= minimum(cost(x,y,(ll)0),cost((ll)0,max((ll)0,y-x),2*x),cost(max((ll)0,x-y),(ll)0,2*y)); 
	cout << mini << endl ;
	return 0 ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//g++ -std=c++11 

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7

ll N, K;
string S;

int main(){
	cin >> N >> K >> S;
	if(N == 1) {
		cout << 0 << endl;
		return 0;
	}

	ll num = 0;
	char ch = 'x';
	rep(i, N) {
		if(ch != S[i]) {
			num++;
			ch = S[i];
		}
	}

	char left, right;
	left  = S[0];
	right = S[N-1];

	if(left == right) {
		ll mid = num/2;
		mid = max(0ll, mid - K);
		cout << N - 1 - 2 * mid << endl;
	} else {
		ll mid = num/2;
		mid = max(0ll, mid - K);
		if(mid == 0) {
			cout << N - 1 << endl;
			return 0;
		}
		ll ans = N - 1;
		ans--;
		mid--;
		cout << ans - 2 * mid << endl;
	}
}

Measured memory_bytes: 3720
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	int res = 0;
	int mx = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		res += A[i];
		mx = max(mx, A[i]);
	}
	cout << res - (mx/2) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double A;
    long double B;

    cin >> A >> B;
    ll ans = A*B;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3752
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    ll res = 1;
    for(int i = 0; i  <N;i++){
        ll T; cin >> T;
        res = lcm(res,T);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m; scanf("%d%d",&n,&m);
    int res=0;
    for(int i=0;i<m;i++){
    	int x; scanf("%d",&x);
        res+=x;
    }
    if(res<=n) printf("%d",n-res);
    else puts("-1");
}


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

void insertationSort(int A[],int N){
    int i,j,key;
    for(i=0;i<N;i++){
        key=A[i];
        j=i-1;
        while(j>=0&&A[j]>key){
            A[j+1]=A[j];
            j=j-1;
        }
        A[j+1]=key;
        for(j=0;j<N;j++){
            printf("%d",A[j]);
            if(j<N-1) printf(" ");
        }
        printf("\n");
    }
}

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


Measured memory_bytes: 1812
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong();
        if (x <= 9 && x >= 1 && y <= 9 && y>= 1) {
            long result = y * x;
            System.out.println(result);
        } else {
            long result = -1;
            System.out.println(result);
        }
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define _boost ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define fi first
#define se second
#define clz __builtin_clz
#define clzll __builtin_clzll
#define bp __builtin_popcount
#define _unique(x) sort((x).begin(),(x).end()),(x).erase(unique((x).begin(), (x).end()),(x.end()))
#define all(x) (x).begin(),(x).end()
#define _rand(i,j) uniform_int_distribution<int>(i, j)(rng___)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;
template < typename _T, typename _T2> string to_string(pair<_T,_T2> x) {return "<"+to_string(x.fi)+", "+to_string(x.se)+">";}
template < typename _T> string to_string(vector<_T> vec) {string s="[ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]=']';s[s.size()-2]=' '; return s;}
template < typename _T> string to_string(set<_T> vec) {string s="{ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T, typename _T2> string to_string(map<_T,_T2> vec) {string s="{ "; for(auto el:vec)s+="mp["+to_string(el.fi)+"]= "+to_string(el.se)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T > inline void _DBG(const char *s, _T x){cerr << s << " = " << to_string(x) << "\n";}
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a){while(*s != ',') cerr << *s++;cerr << " = " << to_string(x) << "\n";_DBG(s + 1, a...);}
#ifdef LOCAL
#define _print(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define _print(...) ;//cout<<2;//(__VA_ARGS__)
#endif
mt19937 rng___(chrono::steady_clock::now().time_since_epoch().count());


const LL MOD = 1e9+7;//998244353;
const LL LLINF = 1e18+7;
const int N=1e5+8;
LD dp[302][302][302];
int main()
{
    _boost;
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> res(4,0);
    for(int i=0;i<n;i++)cin>>a[i],res[1]+=a[i]==1,res[2]+=a[i]==2,res[3]+=a[i]==3;
    LD invn=1.0/n;
    for(int k=0;k<=n;k++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int i=0;i<=n;i++)
            {
                if(i+j+k>n||i+j+k==0)continue;
                LD val=0;
                if(i>0)
                {
                    val+=i*invn*dp[i-1][j][k];
                }
                if(j>0)
                {
                    val+=j*invn*dp[i+1][j-1][k];
                }
                if(k>0)
                {
                    val+=k*invn*dp[i][j+1][k-1];
                }
                val+=1;
                dp[i][j][k]=val/(i+j+k)*n;
                //_print(i,j,k,dp[i][j][k]);
            }

        }
    }
    //_print(res);
    cout<<setprecision(20)<<dp[res[1]][res[2]][res[3]];
}




Measured memory_bytes: 428288
def main():
    import sys
    readline = sys.stdin.buffer.readline

    n, x, y = map(int, readline().split())

    l = [0] * (n-1)
    for i in range(1, n):
        for j in range(i+1, n+1):
            s = min(j-i, abs(x-i)+abs(j-y)+1)
            l[s-1] += 1
    for i in l:
        print(i)

main()

Measured memory_bytes: 9336
a,b = map(int,input().split())
s = input()
check = 1
if s[a] != '-':
	print('No')
else:
	for i in range(a):
		if s[i] == '-':
			check = -1
			break
	for k in range(a+1,a+b+1):
		if s[k] == '-':
			check = -1
			break
	if check == 1:
		print('Yes')
	else:
		print('No')

Measured memory_bytes: 3060
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}
struct uf{
  static const int MAXN=200005;
  int par[MAXN];
  int size[MAXN];
  void init(){
    memset(par,-1,sizeof(par));
    REP(i,MAXN) size[i]=1;
  }
  int root(int a){
    if(par[a]==-1) return a;
    return par[a]=root(par[a]);
  }
  void unite(int a,int b){
    a=root(a);b=root(b);
    if(a==b) return;
    if(size[a]<size[b]) swap(a,b);

    par[b]=a;
    size[a]+=size[b];
  }
  bool same(int a,int b){
    return root(a)==root(b);
  }
};

uf u;

int n,m,K;
int col[100005];
pair<int,pi> es[100005];
int main(){
  cin>>n>>m>>K;

  int K2=K;
  REP(i,n){
    scanf("%d",&col[i]);
    --col[i];
    if(col[i]==-1) col[i]=K2++;
  }
  REP(i,m){
    int a,b,w;scanf("%d%d%d",&a,&b,&w);
    --a;--b;
    int ca=col[a],cb=col[b];
    es[i]={w,{ca,cb}};
  }
  sort(es,es+m);
  u.init();
  int comp=K2;
  int uni=0;

  lint tot=0;
  lint res=-1;
  REP(i,m) {
    if(!u.same(es[i].sc.fr,es[i].sc.sc)){
      u.unite(es[i].sc.fr,es[i].sc.sc);
      --comp;
      ++uni;
      tot+=es[i].fr;
      if(uni==K-1){
        res=tot;
        break;
      }
    }
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 3328
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt(); //枚数
    int k = scanner.nextInt(); //人数
    
    int result = 1;
    
    if(n%k==0){
      result = 0;
    }
    
    System.out.println(result);
    
	}
}

Measured memory_bytes: 20948
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};

int main() {
    int n; cin >> n;
    int h[n]; rep(i, n) cin >> h[i];
    int ans = 0;
    rep(i, n) {
        int flg = 0;
        rep(j, i) {
            if (h[j] > h[i]) {
                flg = 1;
                break;
            }
        }
        if (flg == 0) ans++;
    }
    cout << ans << endl;
}
    


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

int main() {
	int n, k;
	string s;
	cin >> n >> k >> s;

	k--;
	if (s[k] == 'A') s[k] = 'a';
	else if (s[k] == 'B') s[k] = 'b';
	else s[k] = 'c';

	cout << s << endl;

	return 0;
}

Measured memory_bytes: 256
import math
from bisect import bisect_left,bisect_right
N,L,T=map(int,input().split())
table=[[0,0] for i in range(N)]
for i in range(N):
    x,y=map(int,input().split())
    table[i][0]=x
    table[i][1]=y
count=0
l=table[0][0]
w=table[0][1]
P=[0]*N
for i in range(N):
    if table[i][1]==1:
        P[i]=(table[i][0]+T)%L
    else:
        P[i]=(table[i][0]-T)%L
if w==1:
    for i in range(1,N):
        if table[i][1]==2:
            if (2*T-table[i][0]+l)>=0:
                count+=math.floor((2*T-table[i][0]+l)/L)+1
    count=count%N
if w==2:
    for i in range(1,N):
        if table[i][1]==1:
            if (2*T-(L-table[i][0]+l))>=0:
                count+=math.floor((2*T-(L-table[i][0]+l))/L)+1
            #print(count)
    count=(N-count)%N
a=P[0]
P.sort()
s=P.index(a)
ans=[0]*N
if w==1 and s<N-1 and P[s]==P[s+1]:
    s+=1
for i in range(N):
    ans[(count+i)%N]=P[(s+i)%N]

for i in ans:
    print(i)




Measured memory_bytes: 60852
#include <cstdio>
#include <algorithm>
using namespace std;
int n,x,y;
long long a=1,b=1,z;
int main() {
  scanf("%d",&n);
  while (n--) {
    scanf("%d%d",&x,&y);
    z=max((a+x-1)/x,(b+y-1)/y);
    a=x*z;
    b=y*z;
  }
  printf("%lld\n",a+b);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

ll xpowy(ll x, ll y) {
    ll res = 1LL;
    while (y > 0) {
        if ((y & 1)) 
            res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

ll n, a[100005], ans;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n;
    rep(i, 0, n) cin >> a[i];
    sort(a, a+n);
    for (int i = n%2; i < n; i+=2) {
        if (a[i] != a[i+1]) {
            cout << 0 << endl;
            return 0;
        }
    }
    if (n%2) ans = xpowy(2, (n-1)/2);
    else ans = xpowy(2, n/2);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string.h>
#include <vector>

int main () {
  int a,b;
  std::cin >>  a >> b;
  std::vector<int> me[1000];

  int answer = b - a;

  // answerメートルの間隔があることになる.
  
  int sub = 0;
  for (int i = 1; i <= answer; i++) {
    sub +=  i;
  }

  std::cout << sub - b <<std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n=  s.size();
    string t1,t2;
    for(int i = 0; i < n/2; i++){
        t1 += s[i];
    }
    for(int i = n/2+1; i < n; i++){
        t2 += s[i];
    }
    string sp = s;
    reverse(sp.begin(),sp.end());
    string t1p = t1,t2p = t2;
    reverse(t1p.begin(),t1p.end());
    reverse(t2p.begin(),t2p.end());
    if(sp != s || t1p != t1 || t2p != t2){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;

#define INF 999999
char stage[1010][1010];
int dp[1010][1010];
int main(){
	int n;
	while(scanf("%d",&n),n){
		memset(stage,0,sizeof(stage));
		memset(dp,0,sizeof(stage));
		int ans = 0;
		for(int i = 0; i < n; i++){
			scanf("%s",stage[i]);
			for(int j = 0; j < n; j++){
                dp[i][j] = (stage[i][j]=='*') ? 0 : ans = 1;
			}
		}
		for(int i = 1; i < n; i++){
			for(int j = 1; j < n ;j++){
				if(stage[i][j] == '*')continue;
				dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
				ans = max(dp[i][j],ans);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 6180
#include <stdio.h>

typedef struct{
  char c;
  int value;
}card;

int main(){
  char space;
  int i, j;
	int n, min, flag;
  card x, a[36], b[36];
	
  scanf("%d\n", &n);
	
  for(i = 0; i < n; i++){
    scanf("%c%d%c", &a[i].c, &a[i].value, &space);
    b[i] = a[i];
}
  for(j = 0; j < n; j++){
    flag = 0;
    for(i = n - 1; i > j; i--){
      if(a[i].value < a[i-1].value){
        x = a[i];
        a[i] = a[i - 1];
        a[i - 1] = x;
        flag = 1; 
}
}
    if(flag == 0) break;
  }
  for(j = 0; j < n; j++){
    min = j;
    for(i = j; i < n; i++){
      if(b[i].value < b[min].value)
        min = i;
    }
    if(min != j){
      x = b[j];
      b[j] = b[min];
      b[min] = x;
} 

}

  for(i = 0; i < n-1; i++){
    printf("%c%d ", a[i].c, a[i].value);
  }
	
  printf("%c%d\n", a[n-1].c, a[n-1].value);
  printf("Stable\n");
	
  for(i = 0; i < n-1; i++){
    printf("%c%d ", b[i].c, b[i].value);
    if(a[i].c != b[i].c){
flag = 2; 
}

}
  printf("%c%d\n", b[n-1].c, b[n-1].value);
  if(flag == 2){
    printf("Not stable\n");
  }
  else printf("Stable\n");
	
return 0; 
}

Measured memory_bytes: 608
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() =listOfString().map { it.toInt() }
fun listOfLong() =listOfString().map { it.toLong() }
fun listOfDouble() =listOfString().map { it.toDouble() }
fun main(args:Array<String>){
  var s = next()
  var n = s.length
  var ans = 100000000
  for(i in 0..n-3){
    var str = s.substring(i,i+3)
    var tmp = str.toInt() - 753
    if(tmp<0) tmp *= -1
    ans = if(ans<tmp) ans else tmp
  }
  println(ans)
}


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

if D == 0:
    if N == 100:
        print(101)
    else:
        print(N)
if D == 1:
    if N == 100:
        print(10100)
    else:
        print(N * 100)
if D == 2:
    if N == 100:
        print(101 * 100 * 100)
    else:
        print(N * 100 * 100)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <map>
using namespace std;
const int maxn = 100007;
int a[maxn],b[maxn];
int main()
{
	int sum,n,max1=0,l;
	cin>>n>>sum;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		if(max1<a[i])
			{
				max1=a[i];
				l=i;
			}
	}
	int sum1 = 0;
	int ans = 0;
	sort(b+1,b+1+n);
	int now = n;
	while(sum1<sum)
	{
		if(b[now]>max1)
		{
			sum1+=b[now];
			ans++;
			b[now]=0;
			now--;
		}
		else
		{
			sum1+=max1;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int k = sc.nextInt();
			if(n==0 && k==0) break;
			int[] a = new int[n];
			int sum = 0,maxsum = 0;
			for(int i=0;i<n;i++) a[i] = sc.nextInt();
			for(int i=0;i<n-k;i++){
				sum = 0;
				for(int j=0;j<k;j++){
					sum += a[i+j];
				}
				if(sum > maxsum) maxsum = sum;
			}
			System.out.println(maxsum);
		}
	}
}

Measured memory_bytes: 64080
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]

def wrap(S):
    return [row + ["."] for row in S] + [["."]*(W+1)]

S2 = wrap(S)
ans = [""]*(H)
for i in range(H):
    for j in range(W):
        if S2[i][j] == "#":
            ans[i] += "#"
        else:
            cnt = 0
            for di in (-1,0,1):
                for dj in (-1,0,1):
                    cnt += int(S2[i+di][j+dj] == "#")
            ans[i] += str(cnt)

for out in ans:
    print(out)

Measured memory_bytes: 3192
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Queue, PriorityQueue}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N = in.next().toInt


  //
  val ans = Array.ofDim[Int](N+1, N+1)

  def calc(lst: List[Int], level: Int): Unit = {
    val l = lst.length
    if (l == 1)
      ()
    else {
      val al = lst.take(l/2)
      val bl = lst.slice(l/2, l)

      for (a <- al; b <- bl) {
        ans(a)(b) = level
      }
      calc(al, level + 1)
      calc(bl, level + 1)
    }
  }

  calc((1 to N).toList, 1)
  for (i <- 1 until N) {
    pw.println(ans(i).slice(i+1, N+1).mkString(" "))
  }
  pw.flush()
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 37152
S = list(input())

count = 0
max_count = 0

if len(S) == 1:
    if S[0] == 'A' or \
        S[0] == 'C' or \
        S[0] == 'G' or \
        S[0] == 'T':
        print("1")
        exit()
    else:
        print("0")
        exit()


for i in range(len(S)):
    if  S[i] == 'A' or \
        S[i] == 'C' or \
        S[i] == 'G' or \
        S[i] == 'T':
        count += 1
    else:
        if count > max_count:
            max_count = count
        count = 0

if count > max_count:
    max_count = count

print(max_count)






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

using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(vr) vr.begin(),vr.end()
#define pi pair<int,int>

typedef long long ll;
namespace myrand
{
    mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
    ll Int(ll l,ll r) { return uniform_int_distribution<ll> (l,r)(mt); }
}
using namespace myrand;
auto ss=chrono::system_clock::now();
double remain_time()
{
    auto en=chrono::system_clock::now();
    return (chrono::duration_cast<chrono::nanoseconds>(en-ss).count()*1e-9);
}
string s;
bool check(int x,int y)
{
    string a,b;
    a="";
    b="";
    for(int i=x;i<=y;i++) a=a+s[i];
    for(int i=y;i>=x;i--) b=b+s[i];
    if (a==b) return 1; else return 0;
}

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin >> s;
   s='@'+s;
   int n=s.size()-1;
   if (check(1,n)==1 && check(1,(n-1)/2)==1 && check((n+3)/2,n)==1) cout << "Yes"; else cout <<"No";
   return 0;
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

ll N;

int digit_count(ll x)
{
	int res = 0;
	do{
		res++;
	}while(x /= 10);
	return res;
}

int main()
{
	scanf("%lld",&N);
	int ans = 1e9;
	for(ll i = 1;i * i <= N;i++){
		if(N % i == 0){
			chmin(ans,max(digit_count(i),digit_count(N / i)));
		}
	}

	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 256
// abc162_b
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
  int n;
  ll ans=0;
  cin>>n;
  for (int i=1;i<=n;++i) {
    if (!(i%3==0||i%5==0)) ans+=i;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3668
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var A = ab[0]; var B = ab[1];
            var count = 1;
            while (A + (count - 1) * (A - 1) < B) count++;
            Console.WriteLine(B == 1 ? 0 : count);
        }
    }
}


Measured memory_bytes: 11092
n=int(input())
xyh=[list(map(int,input().split())) for _ in range(n)]
for x,y,h in xyh:
    if h>0:
        sx=x
        sy=y
        sh=h
for i in range(101):
    for j in range(101):
        th=abs(i-sx)+abs(j-sy)+sh
        for x,y,h in xyh:
            if h!=max(th-abs(i-x)-abs(j-y),0):
                break
        else:
            break
    else:
        continue
    break
print(i,j,th)

Measured memory_bytes: 3064
import java.util.*;

public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        boolean ans=false;
        int n=sc.nextInt();
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                if(n==i*j){
                    ans=true;
                }
            }
        }
        if(ans)System.out.println("Yes");
        else System.out.println("No");




        sc.close();
    }
}


Measured memory_bytes: 23252
cin = open(0).read().strip().split('\n')
n,q=map(int, cin[0].split(' '))
ab = [tuple(map(int, a.split(' '))) for a in cin[1:n]]
px = [tuple(map(int, a.split(' '))) for a in cin[n:n+q]]

import sys
sys.setrecursionlimit(10**9)

def dfs(g, idx, seen):
    global score

    seen[idx] = True
    for i in g[idx]:
        if seen[i]: continue
        score[i] += score[idx]
        dfs(g, i, seen)

g = [[] for _ in range(n)]
for abi in ab:
    # 無向グラフはお互いが参照し合う
    g[abi[0]-1].append(abi[1]-1)
    g[abi[1]-1].append(abi[0]-1)

score = [0]*n
for pxi in px:
    score[pxi[0]-1] += pxi[1]

seen = [False]*n
dfs(g, 0, seen)

print(' '.join(map(str, score)))

Measured memory_bytes: 309612
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
#define MN 100005
#define mid (l+r>>1)
struct edge{int to,nex;}e[MN*2];int cnt,hr[MN],d[MN];
inline void INS(int f,int t){e[++cnt]=(edge){t,hr[f]};hr[f]=cnt;d[t]++;}
inline void ins(int f,int t){INS(f,t);INS(t,f);}
int n,rt,ans,flag,l,r;
multiset<int> s[MN+5];multiset<int>::iterator it;
int f[MN];
void dfs(int x,int fa){
	s[x].clear();f[x]=0;register int i;
	for(i=hr[x];i;i=e[i].nex) if(e[i].to!=fa) dfs(e[i].to,x),s[x].insert(f[e[i].to]+1);
	int has=0,has2=0,siz=s[x].size();if(!siz) ans++;ans-=(siz-1)/2;
	if(s[x].size()&&(*(--(it=s[x].end())))>mid) return (void)(flag=0);
	while(!s[x].empty()){
		it=s[x].end();--it;int v=*it;s[x].erase(it);
		it=s[x].upper_bound(mid-v);
		if(it==s[x].begin()){
			if(!has) has=v,f[x]=has;
			else if(~siz&1){
				if(!has2) has2=v,f[x]=has2;
				else return(void)(flag=0);
			}
			else return (void)(flag=0);
		}
		else s[x].erase(--it);
	}
}
int main(){
	n=read();register int i;
	for(i=1;i<n;i++) ins(read(),read());
	l=1,r=n;int res,anss;
	for(rt=1;~d[rt]&1;rt++);
	while(l<=r){
		ans=0;flag=1;dfs(rt,0);
		if(flag) res=mid,r=mid-1,anss=ans;
		else l=mid+1;
	}
	printf("%d %d",anss,res);
	return 0;
}


Measured memory_bytes: 17024
S=list(input())

s_1=[]
s_2=[]

for i in range(0,int(len(S)/2)):
    s_1.append(S[i])

for i in range(int(len(S)/2)+1,len(S)):
    s_2.append(S[i])


def kaibun(s):
    s=list(s)
    n=len(s)
    if n%2==0:
        for i in range(int(n/2)):
            if s[i]!=s[n-1-i]:
                return None
    else:
        for i in range(int(n/2)):
            if s[i] != s[n -1- i]:
                return None
    return True

if kaibun(S) and kaibun(s_1) and kaibun(s_2):
    print("Yes")
else:
    print("No")

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n;
vector<lint> a;
lint memo[2001][2];

template<typename T>
bool chmax(T &_a, T _b){
    if(_a < _b){
        _a = _b;
        return true;
    }else{
        return false;
    }
}

template<typename T>
bool chmin(T &_a, T _b){
    if(_a > _b){
        _a = _b;
        return true;
    }else{
        return false;
    }
}

lint solve(int k, int t, lint x, lint y){
    if(k == n){
        return abs(x - y);
    }else if(memo[k][t] >= 0LL){
        return memo[k][t];
    }

    lint res;

    if(t == 0){
        res = -LLINF;
        REP(i, k, n){
            chmax(res, solve(i + 1, 1, a[i], y));
        }
    }else{
        res = LLINF;
        REP(i, k, n){
            chmin(res, solve(i + 1, 0, x, a[i]));
        }
    }

    return memo[k][t] = res;
}

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

    lint z, w;
    cin >> n >> z >> w;

    a.resize(n);
    rep(i, n){
        cin >> a[i];
    }

    memset(memo, -1, sizeof(memo));

    lint ans = solve(0, 0, z, w);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
 
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
 
int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
 
    // 累積 GCD (左と右両方)
    vector<int> left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) left[i+1] = GCD(left[i], a[i]);
    for (int i = N-1; i >= 0; --i) right[i] = GCD(right[i+1], a[i]);
    
    // 集計
    int res = 0;
    for (int i = 0; i < N; ++i) {
        // 左側
        int l = left[i];
 
        // 右側
        int r = right[i+1];
 
        // 更新
        chmax(res, GCD(l, r));
    }
    cout << res << endl;
}

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

const double eps = 1e-9;
inline bool equals(double a, double b) { return fabs(a - b) < eps ;}

class Point {
public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {};

    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }

    double abs() { return sqrt(norm()); }
    double norm() { return x * x + y * y; }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point &p) const {
        return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
    }
};
typedef Point Vector;

struct Segment {Point p1, p2;};

double dot(const Vector& a, const Vector& b) {
    return a.x * b.x + a.y * b.y;
}

// return abs of closs product
double cross(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

int ccw(Point p0, Point p1, Point p2) {
    const int COUNTER_CLOCKWISE = 1, CLOCKWISE = -1;
    const int ONLINE_BACK = 2, ONLINE_FRONT = -2, ON_SEGMENT = 0;
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) >  eps) return COUNTER_CLOCKWISE;
    if (cross(a, b) < -eps) return CLOCKWISE;
    if (dot(a, b)   < -eps) return ONLINE_BACK;
    if (a.norm() < b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool intersect(Point p1, Point p2, Point p3, Point p4) {
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}

bool intersect(Segment s1, Segment s2) {
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

int main(void) {
    int q;
    cin >> q;
    while (q--) {
        double x0, y0, x1, y1, x2, y2, x3, y3;
        cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        Segment s1 = {Point(x0, y0), Point(x1, y1)};
        Segment s2 = {Point(x2, y2), Point(x3, y3)};
        cout << (intersect(s1, s2) ? 1 : 0) << endl;
    }
    return 0;
}

Measured memory_bytes: 1236