akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

constexpr int INF = 0x3f3f3f3f;

vector<pair<int, int>> edgesFrom[100001];
int size[100001], maxSubtree[100001];

int n;
long long ans = 0;

void dfs(int x, int parent) {
	size[x] = 1;
	maxSubtree[x] = 0;
	
	for (auto &&e: edgesFrom[x])
		if (e.first != parent) {
			dfs(e.first, x);
			size[x] += size[e.first];
			maxSubtree[x] = max(maxSubtree[x], size[e.first]);

			const int maxTravelTimes = 2 * min(size[e.first], n - size[e.first]);
			ans += static_cast<long long>(maxTravelTimes) * static_cast<long long>(e.second);
		}

	maxSubtree[x] = max(maxSubtree[x], n - size[x]);
}

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

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		edgesFrom[a].push_back(make_pair(b, c));
		edgesFrom[b].push_back(make_pair(a, c));
	}

	dfs(1, 1);

	int gravityCenter = 1;
	for (int i = 2; i <= n; ++i)
		if (maxSubtree[i] < maxSubtree[gravityCenter]) gravityCenter = i;
	
	if (n % 2 == 0 && maxSubtree[gravityCenter] == n / 2) {
		for (auto &&e: edgesFrom[gravityCenter])
			if (maxSubtree[e.first] == n / 2) {
				ans -= e.second;
				break;
			}
	} else {
		int minLength = INF;
		for (auto &&e: edgesFrom[gravityCenter])
			if (e.second < minLength) minLength = e.second;
		ans -= minLength;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 10496
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{

    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            int N;int K;
            Multi(out N, out K);
            var X = GetIntArray();
            var min = int.MaxValue;
            for(int i = 0; i < N-K+1; i++)
            {
                var left = X[i];
                var right = X[i + K - 1];
                min = Math.Min(min, Math.Min(Math.Abs(left), Math.Abs(right)) + Math.Abs(left - right));
            }
            Console.WriteLine(min);

        }



        static public string GetStr() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
    }
}

Measured memory_bytes: 21856
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 100000;

int n, m;
int fa[MAXN+5];
int val[MAXN+5];
vector <int> blk[MAXN+5];
vector <int> ansEdge;
long long int ans;

int SetFind(int x)
{
    if(fa[x] != x)
        return fa[x] = SetFind(fa[x]);
    return fa[x];
}

void SetInit(int n)
{
    for(int i = 1; i <= n; i++)
        fa[i] = i;
}

int main()
{
    int blkcnt;

    cin >> n >> m ;
    SetInit(n);
    blkcnt = n;

    for(int i = 1; i <= n; i++)
        cin >> val[i] ;
        //blk[i].push_back(val[i]);


    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        u++, v++;
        if(SetFind(u) != SetFind(v))
            fa[SetFind(u)] = SetFind(v), blkcnt--;
    }

    for(int i = 1; i <= n; i++)
        blk[SetFind(i)].push_back(val[i]);
/*
    for(int i = 1; i <= n; i++)
    {
        if(!blk[i].empty())
            cout << blk[i].size() << endl ;
    }
*/
    if(blkcnt <= 1)
    {
        cout << 0 << endl ;
        return 0;
    }

    blkcnt -= 2;

    for(int i = 1; i <= n; i++)
        if(!blk[i].empty())
        {
            sort(blk[i].begin(), blk[i].end());
            ans += blk[i][0];
            for(int k = 1; k < blk[i].size(); k++)
                ansEdge.push_back(blk[i][k]);
        }

    if(ansEdge.size() < blkcnt)
    {
        cout << "Impossible" << endl;
        return 0;
    }

    sort(ansEdge.begin(), ansEdge.end());

    for(int i = 0; i < blkcnt; i++)
        ans += ansEdge[i] ;

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


Measured memory_bytes: 6528
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2000;
const int oo = 1000000000;
int n,k,head[maxn+1],link[maxn*2],adj[maxn*2],d[maxn+1];
int d1[maxn+1],d2[maxn+1];
void enter()
{
	cin >> n >> k;
	for (int i=1; i<=n-1; i++)
	{
		int a,b;
		cin >> a >> b;
		link[i*2-1]=head[a];
		adj[i*2-1]=b;
		head[a]=i*2-1;
		link[i*2]=head[b];
		adj[i*2]=a;
		head[b]=i*2;
	}
}
int bfs(int s,int diameter)
{
	for (int i=1; i<=n; i++)
		d[i]=oo;
	d[s]=0;
	queue<int> q;
	q.push(s);
	int res=1;
	do
	{
		int t=q.front();
		q.pop();
		if (d[t]==diameter) break;
		int i=head[t];
		while (i!=0)
		{
			if (d[adj[i]]>d[t]+1)
			{
				if (d[adj[i]]==oo) res++;
				d[adj[i]]=d[t]+1;
				q.push(adj[i]);
			}
			i=link[i];
		}
	}
	while (!q.empty());
	return res;
}
int bfs2(int x,int y,int diameter)
{
	for (int i=1; i<=n; i++)
		d1[i]=oo;
	d1[x]=0;
	for (int i=1; i<=n; i++)
		d2[i]=oo;
	d2[y]=0;
	queue<int> q;
	q.push(x);
	do
	{
		int t=q.front();
		q.pop();
		int i=head[t];
		while (i!=0)
		{
			if (d1[adj[i]]>d1[t]+1)
			{
				d1[adj[i]]=d1[t]+1;
				q.push(adj[i]);
			}
			i=link[i];
		}
	}
	while (!q.empty());
	while (!q.empty()) q.pop();
	q.push(y);
	do
	{
		int t=q.front();
		q.pop();
		int i=head[t];
		while (i!=0)
		{
			if (d2[adj[i]]>d2[t]+1)
			{
				d2[adj[i]]=d2[t]+1;
				q.push(adj[i]);
			}
			i=link[i];
		}
	}
	while (!q.empty());
	int res=0;
	for (int i=1; i<=n; i++)
		if (min(d1[i],d2[i])<=diameter) res++;
	return res;
}
void solve()
{
	int res=0;
	if (k%2==0)
	{
		for (int i=1; i<=n; i++)
			res=max(res,bfs(i,k/2));
	}
	else
	{
		for (int i=1; i<=n; i++)
		{
			int j=head[i];
			while (j!=0)
			{
				res=max(res,bfs2(i,adj[j],k/2));
				j=link[j];
			}
		}
	}
	cout << n-res;
}
int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("C.inp","r",stdin);
	//freopen("C.out","w",stdout);
	enter();
	solve();
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; cin >> N; 
	int A[200010] = {}; 
	long long cnt[200010] = {}; 
	for(int i = 0; i < N; i++){
		cin >> A[i]; 
		cnt[A[i]] ++; 
	}
	long long ans = 0LL; 
	for(int i = 1; i <= N; i++){
		ans += cnt[i] * (cnt[i] - 1) / 2; 
	}
	for(int i = 0; i < N; i++){
		long long decrease; 
		decrease = cnt[A[i]] - 1; 
		cout << ans - decrease << endl; 
	}
}

Measured memory_bytes: 4864
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

#define rep(i, n) for(int i = 0; i < n; i ++)

using namespace std;

int getNext(int, int);
int getNum(vector<int>);

int main(void){
	int a[21];
	for(int l; cin >> a[0] >> l, l;){
		for(int i = 1; i < 21; i ++){
			a[i] = getNext(a[i - 1], l);
			
			int* p = find(a, a + i, a[i]);
			if(p != a + i){
				cout << p - a << " " << *p << " " << i - (p - a) << endl;
				break;
			}
		}
	}
	return 0;
}

int getNext(int a, int l){
	vector<int> number;

	while(l --){
		number.push_back(a % 10);
		a /= 10;
	}

	sort(number.begin(), number.end());
	int minNumber = getNum(number);
	reverse(number.begin(), number.end());
	int maxNumber = getNum(number);
	
	return maxNumber - minNumber;
}

int getNum(vector<int> a){
	int result = 0;
	rep(i, a.size()) result += a[i] * (int)pow(10., int(a.size() - i - 1));

	return result;
} 

Measured memory_bytes: 1220
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define m_p make_pair
#define re return
#define pb push_back
#define si set<int>
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll quickpower(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string int_to_string(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int string_to_int(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
int main()
{
	ios::sync_with_stdio(0);
	//think twice,code once
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int ans=0;
	ans+=min(a,k);
	k-=a;
	if(k>0)
	{
		k-=b;
	}
	if(k>0)
		ans-=k;
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3628
def zero_or_swap(p)
  sorted = p.sort
  count = 0
  0.upto(p.size - 1) do |i|
    if sorted[i] != p[i]
      count += 1
      return 'NO' if count > 2
    end
  end
  'YES'
end

n = gets.chomp.to_i
p = gets.split.map(&:to_i)
puts zero_or_swap(p)


Measured memory_bytes: 1916
#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    a, b = map(int, readline().split())

    if a <= b:
        print(str(a) * b)
    else:
        print(str(b) * a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
// 1:T 2:H
long long ans;
int w,h,n,m,i,j,fa[200005],typ[200005];
struct ii
{
	int x,y,val;
}a[200005];
bool cmp(ii x,ii y)
{
	return x.val>y.val;
}
int fnd(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=fnd(fa[x]); 
}
bool mrg(int x,int y)
{
	x=fnd(x);y=fnd(y);
	if(x==y){
		if(typ[x]==2) return 0;
		typ[x]=2;return 1;
	}
	if(typ[x]==2&&typ[y]==2) return 0;
	if(typ[x]==1&&typ[y]==2) {fa[x]=y;return 1;}
	if(typ[x]==2&&typ[y]==1) {fa[y]=x;return 1;}
	if(typ[x]==1&&typ[y]==1) {fa[x]=y;return 1;}
	exit(-1);
}
int main()
{
	scanf("%d%d%d",&n,&h,&w);
	fz1(i,w+h){
		fa[i]=i;
		typ[i]=1;
	}
	fz1(i,n){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
		a[i].y+=h;
	}
	sort(a+1,a+n+1,cmp);
	fz1(i,n){
		if(mrg(a[i].x,a[i].y)) ans+=a[i].val;
	}
	cout<<ans<<endl;
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N;
    cin >> N;

    ll k = 111;
    for(ll i=1; i<=9; i++){
        if(N <= k*i){
            cout << k*i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<ll>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
using namespace std;
typedef long long ll;


int main(void) {
	int n, r; cin >> n >> r;
	if (n >= 10) {
		cout << r << endl;
	}
	else {
		cout << r+(100 * (10 - n)) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////

ll N;

ll X[2000], Y[2000];

bool ch() {
	ll a = abs(X[1] + Y[1]) % 2;
	repn(i, N) {
		if (abs(X[i] + Y[i]) % 2 != a) { return false; }
	}
	return true;
}

ll cnt;

void robot(ll x, ll y) {

	if (cnt == 39) {
		if (x == 1) { cout << 'R' << endl; }
		if (x == -1) { cout << 'L' << endl; }
		if (y == 1) { cout << "U" << endl; }
		if (y == -1) { cout << "D" << endl; }
		return;
	}

	ll a = x % 2;
	if (a < 0) { a += 2; }
	ll b = (x + y) % 4;
	if (b < 0) { b += 4; }

	if (a == 1 && b == 1) {
		cout << 'L';
		x = (x + 1) / 2;
		y = y / 2;
	}

	if (a == 1 && b == 3) {
		cout << 'R';
		x = (x - 1) / 2;
		y = y / 2;
	}

	if (a == 0 && b == 1) {
		cout << 'D';
		x = x / 2;
		y = (y + 1) / 2;
	}

	if (a == 0 && b % 4 == 3) {
		cout << 'U';
		x = x / 2;
		y = (y - 1) / 2;
	}

	cnt++;

	robot(x, y);

}


void solve() {

	if (!ch()) {
		cout << -1;
		return;
	}

	ll a = abs(X[1] + Y[1]) % 2;

	if (a % 2 == 1) {

		cout << 39 << endl;
		ll d = 1;
		repn(i, 39) {
			cout << d << " ";
			d *= 2;
		}
		cout << endl;

		repn(i, N) {

			cnt = 1;

			robot(X[i], Y[i]);
		}
		return;
	}

	cout << 40 << endl;
	cout << 1 << " ";
	ll d = 1;
	repn(i, 39) {
		cout << d << " ";
		d *= 2;
	}
	cout << endl;

	repn(i, N) {
		cout << 'L';

		cnt = 1;

		robot(X[i] + 1, Y[i]);
	}

	return;


}




int main() {

	cin >> N;
	repn(i, N) cin >> X[i] >> Y[i];

	
	solve();
	
	


	system("PAUSE");
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int main(){
	int n;
	string s;
	cin >> n >> s;
	string an = s;
	int k = 0;
	f(i, 0, n)if (s[i] == '(')++k;
	else if (k)--k;
	else an = "(" + an;
	while (k--)an += ')';
	printf("%s\n", an.c_str());
}

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

double dp[3000][3000];

int main(){
    int n;
    cin>>n;
    vector<double> arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    dp[0][0]=1;                           // probability of 0 heads when 0 coins
    for(int i=1;i<=n;i++){
        dp[0][i]=0;
        dp[i][0]= 1;                //probability of i heads with 0 coins
    }

    double ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]= arr[i]*dp[i-1][j-1] + (1-arr[i])*dp[i-1][j];
            //ans+=dp[i][j];
        }
    }
    //double ans=0;
    /*for(int i=n/2+1;i<=n;i++){
        ans+= dp[n][i];
    }*/
    cout<<fixed<<setprecision(10)<<dp[n][(n+1)/2]<<endl;

    return 0;
}


Measured memory_bytes: 70528
# coding: utf-8
# Your code here!
k = int(input())
l = list(range(1,10))
x = 0

while True:
    a = l.pop(0)
    x += 1
    
    if x >= k:
        print(a)
        exit()
    if k > 10000 and x > k/2:
        continue
    
    if a%10 == 0:
        b = int(str(a) + "0")
        l.append(b)
        
        b = int(str(a) + "1")
        l.append(b)
        
            
    elif a%10 == 9:
        b = int(str(a) + "8")
        l.append(b)
        
        b = int(str(a) + "9")
        l.append(b)
        
        
    else:
        b = int(str(a) + str((a%10)-1))
        l.append(b)
        
        b = int(str(a) + str(a%10))
        l.append(b)
        
        b = int(str(a) + str((a%10)+1))
        l.append(b)
        
        
        if x >= k:
            print(a)
            exit()

Measured memory_bytes: 6944
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		int h = fs.nextInt(), w = fs.nextInt();
		int a = fs.nextInt(), b = fs.nextInt();
		
		if(h==a||w==b) {
			System.out.println(0);
			return;
		}
		
		pre_factrials(200010);
		long all = fastFermatComb(h+w-2, h-1);
		for(int i=0;i<b;i++) {
			long s = fastFermatComb(h-a-1+i, i);
			long t = fastFermatComb(a-1+w-i-1, a-1);
			long st = mul(s,t);
			all = sub(all,st);
		}
		System.out.println(all);
		
	}
	
	//Fast Fermat Combination
	static long factorials[];

	static void pre_factrials(int n) {
		factorials = new long[n + 1];
		factorials[0] = 1;
		for (int i = 0; i < n; i++) {
			factorials[i + 1] = mul(i + 1, factorials[i]);
		}
	}

	static long fastFermatComb(long a, long b) {
		if (factorials.length == 0)
			System.err.println("error : factorials has not been culculated!! do [pre_factorial] method");
		long af = factorials[(int) a];
		long bf = factorials[(int) b];
		long abf = factorials[(int) (a - b)];
		long res = af * modpow(bf, mod - 2) % mod * modpow(abf, mod - 2) % mod;
		return res;
	}
	
	//MOD culculations
	static long plus(long x, long y) {
		x %= mod;
		y %= mod;
		long res = (x + y) % mod;
		return res;
	}

	static long sub(long x, long y) {
		x %= mod;
		y %= mod;
		long res = (x - y + mod) % mod;
		return res;
	}

	static long mul(long x, long y) {
		x %= mod;
		y %= mod;
		long res = x * y % mod;
		return res;
	}

	static long div(long x, long y) {
		x %= mod;
		y %= mod;
		long res = x * modpow(y, mod - 2) % mod;
		return res;
	}

	//modの元での高速pow()
	static long modpow(long a, long p) {
		if (p == 0)
			return 1;
		if (p % 2 == 0) {
			long halfP = p / 2;
			long root = modpow(a, halfP);
			return root * root % mod;
		} else
			return a * modpow(a, p - 1) % mod;
	}

}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 25300
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int H = scan.nextInt();
		int W = scan.nextInt();
		int[][]a = new int[H][W];
		int cnt = 0;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				int t = scan.nextInt();
				a[i][j] = t;
				if(t % 2 == 1) {
					cnt++;
				}
			}
		}
		scan.close();
		StringBuilder sb = new StringBuilder();
		int[][] list = new int[H * W][2];
		int[] list2 = new int[cnt];
		int index = 0;
		int cnt2 = 0;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				int k = 0;
				if(i % 2 == 1) {
					k = W - j - 1;
				}else {
					k = j;
				}
				if(a[i][k] % 2 == 1) {
					list2[cnt2] = index;
					cnt2 ++;
				}
				list[index][0] = i;
				list[index][1] = k;
				index++;
			}
		}
		int l = cnt;
		if(cnt % 2 == 1) {
			l --;
		}
		int n = 0;
		for(int i = 0; i < l; i+=2) {
			for(int j = list2[i]; j < list2[i+1]; j++) {
				int a1 = list[j][0] + 1;
				int a2 = list[j][1] + 1;
				int a3 = list[j+1][0] + 1;
				int a4 = list[j+1][1] + 1;
				sb.append(a1 + " " + a2 + " " + a3 + " " + a4);
				sb.append("\n");
				n++;
			}
		}
		System.out.println(n);
		System.out.println(sb.toString());

	}

}

Measured memory_bytes: 107340
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] s = new int[n];
		int[] t = new int[n];
		
		String ss = sc.next();
		for(int i = 0; i < n; i++) {
			s[i] = ss.charAt(i) - 'a';
		}
		
		String st = sc.next();
		for(int i = 0; i < n; i++) {
			t[i] = st.charAt(i) - 'a';
		}
		
		int[] table = new int[26];
		for(int i = 0;i < 26; i++) {
			table[i] = 0;
		}
		table[s[0]] = 1;
		
		for(int i = 1; i < n - 1; i++) {
			table[s[i]] += table[t[i]];
			table[s[i]] %= 1000000007;
		}
		
		System.out.println(table[t[n-1]]);
	}
}


Measured memory_bytes: 34192
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  3005

ll dp[N][N];
ll pre(ll ind,ll l,ll r)
{
    if(l>r)
        return 0;
    return (dp[ind][r]-dp[ind][l-1]+hell)%hell;
}
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    rep(i,1,n+1)
    {
        dp[1][i]=1;
    }
    rep(i,2,n+1)
    {
        rep(j,1,i+1)
        {
            if(s[i-2]=='>')
            {
                dp[i][j]=(dp[i][j-1]+pre(i-1,j,i-1))%hell;
            }
            else
            {
                dp[i][j]=(dp[i][j-1]+pre(i-1,1,j-1))%hell;
            }
        }
    }
    ll ans=0;
    // rep(i,1,n+1)
    cout<<dp[n][n]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 49828
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    n = len(s)

    prev = ""
    ans = 0
    i = 0
    while i < n:
        if s[i] == prev:
            if i + 1 < n:
                ans += 1
                prev = s[i] + s[i+1]
                i += 2
            else:
                i = n
        else:
            ans += 1
            prev = s[i]
            i += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 73260
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#") for x in range(h)]+[["#"]*(w+2)]
sx,sy=1,1
gx,gy=w,h
loc=[[sy,sx]]
ans=sum(i.count(".")for i in grid)
for c in range(h*w):
    next_loc=[]
    for y,x in loc:
        for i,j in([0,1],[1,0],[0,-1],[-1,0]):
            if grid[y+i][x+j]=='.':
                grid[y][x]=c+1
                grid[y+i][x+j]=c+2
                next_loc.append([y+i,x+j])
    loc=next_loc
    if [gy,gx] in loc:
        ans-=grid[gy][gx]
#        for i in grid:
#            print(*i)
        print(ans)
        exit()
print(-1)

Measured memory_bytes: 41328
import sys

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

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

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


def main():
    H, W = mi()
    S = ['w'*(W+2)]+['w'+input()+'w' for i in range(H)]+['w'*(W+2)]
    ans = [[0]*W for i in range(H)]

    for j in range(1, W+1):
        for i in range(1, H+1):
            if S[i][j] == '#':
                ans[i-1][j-1] = '#'
            else:
                t = S[i-1][j-1]+S[i-1][j]+S[i-1][j+1] \
                +S[i][j-1]+S[i][j+1] \
                +S[i+1][j-1]+S[i+1][j]+S[i+1][j+1]
                ans[i-1][j-1] = str(t.count('#'))
    print(*(''.join(ans[i]) for i in range(H)), sep='\n')



if __name__ == '__main__':
    main()


Measured memory_bytes: 68048
import sys
 
_ = input()
minv = int(input())
maxv = -1000000000
 
for r in map(int,sys.stdin.readlines()):
  m = r-minv
  if maxv < m: 
    maxv = m
    if m < 0: minv = r
  elif m < 0: minv = r
 
print(maxv)

Measured memory_bytes: 21820
#include<stdio.h>
int main(void) {
	int A,B;
	scanf("%d", &A);
	scanf("%d", &B);
	if ((1 <= A && A <= 9) && (1 <= B && B <= 9))
		printf("%d\n", A*B);
	else
		printf("%d\n", -1);

	return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> d1(n),d2(n);
  for(int i=0;i<n;i++){
    cin >> d1.at(i) >> d2.at(i);
  }
  
  int k = -1;
  for(int i=0;i<n-2;i++){
    if(d1.at(i) == d2.at(i)){
      if(d1.at(i+1) == d2.at(i+1)){
        if(d1.at(i+2) == d2.at(i+2)) k = 0;
      }
    }
  }
 
  if(k == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 3592
#最小コストソート

n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = 0
for i in range(n-1):
    t = cnt = 0
    #本来i番目にいるべき値はaではどこにいるのか（ループの最小値）
    x = a.index(b[i])
    #もしあるべき場所にあったり、あるべき場所に帰ってきたら終了
    while x != i:
        #ループで最も小さい値を使いまわしながら整えていく
        #ループの最小値が入っている場所にいるべき値がaでは何処にいるか
        y = a.index(b[x])
        #a[x]とa[y]を入れ替えればよい
        a[x],a[y] = a[y],a[x];cnt += 1
        t += a[x] + a[y]
        x = y
    if cnt: c += min(t, (b[i]+b[0])*2 + t -(b[i]-b[0])*cnt)
print(c)
# print(a)


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

ans = [0]*(N+1)

for x in range(1,100,1):
    for y in range(1,100,1):
        for z in range(1,100,1):
            tmp = x*x+y*y+z*z+x*y+y*z+z*x
            if 0 < tmp and tmp <=N:
                ans[tmp]+=1


for i in ans[1:len(ans)]:
    print(i)

Measured memory_bytes: 9132
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	string s;
	int n,m;
	cin >>m>> s >> n;

	if (s[0] == '-')
		cout << m - n << endl;
	else
		cout << m + n << endl;
	
	return 0;
}



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


int main(int argc, const char * argv[]) {
    
  // input from txt （提出時にこの箇所は削除すること）
  std::ifstream in("input.txt");
  std::cin.rdbuf(in.rdbuf());
  
  cin.tie(0);
  ios::sync_with_stdio(false);
  

  vector<int> a(5);
  int m = 10;
  for(int i = 0; i < 5; i++){
    cin >> a.at(i);
    if(a.at(i) % 10 != 0){
      m = min(m, a.at(i)%10);
    }
  }
  int total = 0;
  for(int i = 0; i < 5; i++){
    total += (a.at(i)%10 == 0 ? a.at(i):(a.at(i)/10) * 10 + 10);
  }
  if(m != 10){
    total += m - 10;
  }
  cout << total << endl;
  return 0;
}


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

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef LOCAL
    #define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define debug(...) 42
    #define eprintf(...) 42
#endif

#define PI 3.1415926535897932384626433832795
#define INF 2e9
#define SINV(t) greater<t>()
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define FOREACH(i, v) for(auto i=(v).begin(); i!=(v).end(); ++i)
#define ALL(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;
#define vv(t) vector<t>

#define CHC(mp, x) if(mp.end() != mp.find(x))

template<typename T>
inline T lcm(T a, T b) {return a / __gcd(a, b) * b;}

#pragma endregion

template<typename T>
void SV(vector<T> v){
    REP(i,v.size()){
        #ifdef LOCAL
            cout << i << " : " << v[i] << endl;
        #endif
    }
}
int bitCount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16);
}

int main(void){
    ll X;
    cin >> X;
    ll A = 1;
    map<ll, ll> bb;
    bb[0] = 0;
    while(1){
        ll A5 = A*A*A*A*A;
        bb[A5] = A;
        ll B5 = A5 - X;
        CHC(bb, abs(B5)){
            ll B = bb[abs(B5)];
            if(B5 < 0){
                B *= -1;
            }
            cout << A << ' ' << B << endl;
            return 0;
        }
        A++;
    }
    return 0;
}


Measured memory_bytes: 3604
import java.util.Scanner;

public class Main {
    public static void main(String[] args ) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();
        while(n != 0 || s != 0) {
            System.out.println(dfs(0, 0, s, 0, n));
            n = scanner.nextInt();
            s = scanner.nextInt();
        }
    }

    public static int dfs(int index, int sum, int s, int selected, int n){
        if(index > 10)
            return 0;
        else{
            if(sum == s && selected == n)
                return 1;
            else if(sum > s)
                return 0;
            else{
                if(selected > n)
                    return 0;
                else
                    return dfs(index + 1,sum + index, s, selected + 1, n) + dfs(index + 1,sum, s, selected, n);
            }
        }
    }
}



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

int main(){
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  double maxP = -100.0;
  int maxSum;
  int maxSugar;
  for (int i = 0; 100 * A * i <= F; ++i){
    for (int j = 0; 100 * A * i + 100 * B * j <= F; ++j) {
      if (i == 0 && j == 0) continue;
      for (int k = 0; 100 * A * i + 100 * B * j + C * k <= F; ++k) {
	for (int l = 0; 100 * A * i + 100 * B * j + C * k + D * l <= F; ++l){
	  if (i == 0 && j == 0 && k == 0 && l == 0) continue;
	  int sugar = C * k + D * l;
	  int water = 100 * A * i + 100 * B * j;
	  int sum = water + sugar;
	  double p = (sugar * 100.0) / sum;
	  if ((p <= ((100.0 * E) / (100.0 + E))) && (p > maxP)){
	      maxP = p;
	      maxSum = sum;
	      maxSugar = sugar;
	  }
	}
      }
    }
  }
  cout << maxSum << " " << maxSugar << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void){
	int n;
	cin >> n;
	int mn = INF;
	int mx = -INF;
	ll sum = 0;
	int c;
	rep(i,n){
		cin >> c;
		if(mx < c)mx = c;
		if(mn > c)mn = c;
		sum += c;
	}
	cout << mn << " " << mx << " " << sum << endl;

	return 0;
}



int StrToInt(string s){
	stringstream ss;
	ss << s;
	int val;
	ss >> val;
	return val;
}
string IntToStr(int i){
	stringstream ss;
	ss << i;
	return ss.str();
}

Measured memory_bytes: 1172
#Union-Find木の実装
from collections import Counter
N,M=map(int,input().split())

#初期化
par=[i for i in range(N)]#親の要素(par[x]=xのときxは木の根)
rank=[0]*N#木の深さ

#木の根を求める
def find(x):
  #xが根だった場合xをそのまま返す
  if par[x] == x:
    return x
  else:
    #根が出るまで再帰する
    par[x] = find(par[x])
    return par[x]

#xとyの属する集合を併合
def unite(x,y):
  x=find(x)#xの根
  y=find(y)#yの根
  #根が同じなら何もしない
  if x == y:
    return
  #もし根の深さがyの方が深いなら
  if rank[x] < rank[y]:
    par[x] = y#yを根にする
  else:
    par[y] = x#xを根にする
    if rank[x] == rank[y]:
      rank[x]+=1

#xとyが同じ集合に属するか否か
#def same(x,y):
  #return find(x)==find(y)

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  unite(a,b)

for i in range(N):
  find(i)
c=Counter(par)
c=c.most_common()[0][1]
print(c)

Measured memory_bytes: 44648
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String args[])throws IOException{
      try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
        String str_input = br.readLine();
        double input = Double.parseDouble(str_input);

        if(input < 1 || input > 100){
          System.exit(0);
        }

        /*奇数・偶数の確認*/
        if(input == 1){
          System.out.println(input);
        }else{
          if((input % 2) == 0){
            System.out.println((input/2)/input);
          }else{
            System.out.println(((input+1)/2)/input);
          }
        }
      }
    }
}

Measured memory_bytes: 23124
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <deque>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
 
using namespace std;
 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

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

 
int main () {
	int N;
    cin >> N;
	int a[200001];
	rep(i,N) {
		cin >> a[i];
	}
	int cur = 0;
	rep(i,N) {
		if (a[i] == cur + 1) {
			cur++;
		}		
	}
	if (cur == 0) {
		cout << -1 << endl;
		return 0;
	}
	cout << N - cur << endl;
    return 0;
}

Measured memory_bytes: 1024
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;


int main() {
	char c;
	cin >> c;
	char ans = c + 1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
const int MAXN=100000;
int b[MAXN+10];
typedef pair<int,int> pii;
pii sum[MAXN+10];
int t[2*MAXN+10];
inline int lowbit(int x){return x&(-x);}
void add(int p,int n)
{
	for(int i=p; i<=n; i+=lowbit(i)) {
		t[i]++;
	}
}
LL query(int p)
{
	LL ans=0;
	for(int i=p; i>0; i-=lowbit(i)) {
		ans+=t[i];
	}
	return ans;
}
bool check(int mid, LL n,vector<LL> a)
{
	for(int i=0; i<n; ++i) {
		b[i+1]=(a[i]>=mid)?1:-1;
	}	
	sum[0]=pii(0,0);
	for(int i=1; i<=n; ++i) {
		sum[i].first=sum[i-1].first+b[i];
		sum[i].second=i;
	}
	sort(sum,sum+n+1);
	LL ans=0;
	memset(t,0,sizeof(t));
	for(int i=0; i<=n; ++i) {
		ans+=query(sum[i].second+1);
		add(sum[i].second+1,n+1);
	}
	LL m=n*(n+1)/2;
	if (m%2==0) m=m/2;
	else m=m/2+1;
	return ans>=m;
}
void solve(long long N, vector<long long> a){
	int l=1,r=1e9;
	while(l<r-1) {
		int mid=(l+r)/2;
		if (check(mid,N,a)) {
			l=mid;
		} else {
			r=mid;
		}
	}
	if (check(l+1,N,a)) ++l;
	cout<<l<<endl;
}

int main(){	
#ifdef WAAUTOMATON
	freopen("in_D_3.txt","r",stdin);
#endif
	long long N;
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, a);
	return 0;
}



Measured memory_bytes: 4596
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<utility>
#include <numeric>
#include<list>
using namespace std;
typedef long long ll;

void yes(){
cout<<"Yes"<<endl;
}
void no(){
cout<<"No"<<endl;
}
int main(){
ll n;
cin>>n;
double a[n];
double sum=0;
for(ll i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
sum=sum/n;

double min=1000000;
ll ans=0;
for(ll i=0;i<n;i++){
double ax=sum-a[i];
if(ax<0)
ax=ax*-1;
if(ax<min){
ans=i;
min=ax;
}

}
cout<<ans;
 return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s;
    cin >> s;
    rep(i,s.size()) cout << "x";
    cout << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){ 
    string s; cin >> s;
    int res = 1, index = 1; bool d = false;
    while(index < s.size()){
        if(!d && s[index] == s[index-1]){
            if(index == s.size()-1) break;
            d = true;
            index += 2;
        }else{
            d = false;
            index++;
        }
        res++;

    }
    cout << res << ln;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>

using namespace std;

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

    string str = "";
    while(n != 0){
        //nを２で割ったあまりを求める
        int r = n%2;

        //nからあまりを取り除いて-2で割る
        if(r < 0) r += 2;
        n = (n-r) / (-2);

        //答えに追加
        str += (char)('0' + r);
    }

    reverse(str.begin(), str.end());
    if(str == "") str = "0"; //n = 0 の時はから文字列になってしまうので例外処理
    cout << str << endl;
}



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

int main() {
  string S;
  cin >> S;
  int c=0;
  for(int i=0; i<3; i++){
    if(S.at(i)=='o'){
      c++;
    }
  }
  cout << 700+c*100 << endl;
}


    
    
       
      
      


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

struct Dataset{
	double a, b, c, d, e, f;
	double x, y;
	struct Dataset* next;
};

int main(){
	double a, b, c, d, e, f;
	struct Dataset *datalist, *p;

	datalist = (struct Dataset*)malloc(sizeof(struct Dataset));
	datalist->next = NULL;

	p = datalist;

	while(scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF){
		p->next = (struct Dataset*)malloc(sizeof(struct Dataset));
		p->next->next = NULL;
		p = p->next;
		p->a = a; p->b = b; p->c = c; p->d = d; p->e = e; p->f = f;
		if(a != 0){
			p->y = (a*f-c*d)/(a*e-b*d);
			p->x = c/a - b*(p->y)/a;
		}
		else{
			p->y = c/b;
			p->x = f/d - e*(p->y)/d;
		}
	}

	p = datalist;

	while(p->next != NULL){
		printf("%.3f %.3f\n", p->next->x, p->next->y);
		p = p->next;
	}

	return 0;
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
#define int long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void print(int x)
{ 
	if(x<0)
	{ 
		putchar('-');
		x=-x;
	}
	if(x>=10)print(x/10);
	putchar(x%10+'0');
}
const int N=5e3+10,mod=1e9+7;
int a[N],n,cnt=0,head[N],G[N],f[N][N],siz[N];
struct node{ 
	int v,next;
}e[N<<1];
inline void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
inline void dp(int x,int fa)
{ 
	static int t[N];
	f[x][1]=1;
	siz[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{ 
		int v=e[i].v; 
		if(v==fa)continue;
		dp(v,x);	
		for(int j=0,kel=siz[v];j<=siz[x];++j)for(int k=0;k<=siz[v];++k)(t[j+k]+=f[x][j]*f[v][k]%mod)%=mod;
		siz[x]+=siz[v];
		for(int j=0;j<=siz[x];++j)
		{
			f[x][j]=t[j];
			t[j]=0;
		}
	}
	int sum=0;
	for(int i=0;i<=siz[x];i+=2)sum+=mod-f[x][i]*G[i]%mod;
	f[x][0]=sum%mod;
}
inline void Add(int u,int v)
{
	add(u,v);
	add(v,u);
}
signed main(void)
{ 
	n=read();
	for(int i=1;i<n;i++)Add(read(),read());
	G[0]=1;
	for(int i=2;i<=n;i+=2)(G[i]=G[i-2]*(i-1))%=mod; 
	dp(1,1); 
	print((mod-f[1][0])%mod);
	return 0;
}

Measured memory_bytes: 194816
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144 * 4LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()
void init() {

}
#define int ll

vector<int> primes;

int grid[1000001] = {};
int cnt[1000001] = {};

void solve() {
	for (int i = 2; i*i <= 1e9; ++i) {
		int ok = 1;
		for (int q = 2; q * q <= i; ++q) {
			if (i % q == 0) ok = 0;
		}
		if (ok == 1) {
			primes.push_back(i);
		}
	}

	int l, r;
	cin >> l >> r;
	REP(i, r - l+1) {
		grid[i] = l + i;
	}
	for (int q = 0; q < primes.size(); ++q) {
		int hoge = ((l+primes[q] - 1) / primes[q]) * primes[q];
		hoge -= l;
		for (int i = hoge; i < r - l + 1;i += primes[q]) {
			while (grid[i] % primes[q] == 0) {
				grid[i] /= primes[q];
				cnt[i]++;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < r - l + 1; i++) {
		if (grid[i] != 1) cnt[i]++;
		REP(j, 10) {
			if (cnt[i] == primes[j]) ans++;
		}
	}
	cout << ans << endl;
}

#undef int
int main() {
	init();
	solve();
}


Measured memory_bytes: 18860
def aaa(num, target):
    a = 0
    aaa = num
    while target > aaa:
        a += 1
        aaa = aaa * 2
    return a


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = 0
    for i in range(0, N):
        jyou = aaa(i+1, K)
        ans += (1 / N) * ((1/2) ** jyou)

    print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long INF = 1e9 + 7;
using namespace std;
typedef long long ll;
map<int, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	cout << 180 * (n - 2) << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
count = 0
for i in range(1, n - 1):
    if p[i - 1] < p[i] < p[i + 1] or p[i - 1] > p[i] > p[i + 1]:
        count += 1
print(count)


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

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

    string first;

    bool possible=false;

    for(int i=0; i<s.size(); i++){
        first=s.substr(s.size()-1,1);
        s.insert(0,first);
        s=s.substr(0,s.size()-1);
        if(s==t){
            possible=true;
            break;
        }
    }

    cout<<(possible ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256