akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int64 gcd(int64 a, int64 b) {
  if (a < b) return gcd(b, a);
  int64 r = a % b;
  if (r == 0) return b;
  else return gcd(b, r);
}

int main() {
  int64 a, b, c, d;
  cin >> a >> b >> c >> d;
  int64 lcm = c * d / gcd(c, d);
  // cout << "lcm: " << lcm << endl;
  int64 ans = 0;
  auto f = [&](int64 x) {
    int64 val = 0;
    val += x;
    val -= x / c;
    val -= x / d;
    val += x / lcm;
    return val;
  };
  ans += f(b);
  ans -= f(a - 1);
  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline  #文字列入力では注意！

N = int(input())
a,b,c = map(int,input().split())
dp = [[a,b,c]]
for i in range(N-1):
    a,b,c = map(int,input().split())
    A = max(dp[i][1]+a,dp[i][2]+a)
    B = max(dp[i][2]+b,dp[i][0]+b)
    C = max(dp[i][0]+c,dp[i][1]+c)
    dp.append([A,B,C])
print(max(dp[-1]))


Measured memory_bytes: 22740
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdint>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;
	
ll M = 1000000007;

typedef pair<int, int> P;

bool ps1(const P &element1, const P &element2)
{ //first昇順
	return element1.first < element2.first;
}
bool ps2(const P &element1, const P &element2)
{ //first降順
	return element1.first > element2.first;
}
bool ps3(const P &element1, const P &element2)
{ //second昇順
	return element1.second < element2.second;
}
bool ps4(const P &element1, const P &element2)
{ //second降順
	return element1.second > element2.second;
}
int digits(int n)
{
	int count = 0;
	while (n > 0)
	{
		n /= 10;
		count++;
	}
	return count;
}
ll combination(ll n, ll r)
{
	if (r * 2 > n)
		r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i)
	{
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}
vector<int> divisor(int n)
{
	vector<int> value;
	FOR(i, 1, pow(n, 0.5) + 1)
	{
		if (i <= sqrt(n))
		{
			if (n % i == 0)
			{
				value.push_back(i);
				if (i * i != n)
				{
					value.push_back(n / i);
				}
			}
		}
	}
	return value;
}
int main()
{
	string s;
	cin>>s;
	deque<char>ans;
	int n=s.size();
	rep(i,n){
		if(s[i]=='C' or s[i]=='F'){
			ans.pb(s[i]);
		}
	}
	n=ans.size();
	int cnt=0;
	rep(i,n){
		if(ans[i]=='C'&&cnt==0){
			cnt++;
		}
		
		if(ans[i]=='F'&&cnt==1){
			cnt++;
			break;
		}
	}
	if(cnt==2){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

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

using namespace std;

vector<int> p(9592);
bool isp[100001];
int ans[50001];

int main(void)
{
    p[0] = 2;
    int count = 1;
    bool flag;
    for (int i = 3; i < 100000; i += 2)
    {
        flag = true;
        for(auto itr = p.begin(); *itr * *itr <= i; itr++)
        {
            if (!(i % *itr))
            {
                flag = false;
                break;
            }
        }
        if (flag) p[count++] = i;
    }
    int now = 0;
    for (auto i : p)
    {
        for(int j = now; j < i; j++) isp[j] = false;
        isp[i] = true;
        now = i + 1;
    }
    for (int j = now; j <= 100000; j++) isp[j] = false;
    int Q;
    int L ,R;
    cin >> Q;
    ans[0] = 0;
    count = 0;
    for (int i = 1; i <= 50000; i++)
    {
        if (isp[i] && isp[i * 2 - 1]) count++;
        ans[i] = count;
    }
    for (int i = 0; i < Q; i++)
    {
        cin >> L >> R;
        cout << (ans[((R + 1) / 2)] - ans[(L - 1) / 2]) << endl;
    }
    return 0;
}

Measured memory_bytes: 1532
# Fifty-Fifty
S = str(input())

count = 1
ans = 0
for i in range(4):
    for j in range(i+1, 4):
        if S[i] == S[j]:
            count = count + 1
            if count == 2:
                count = 1
                ans = ans + 1
            else:
                pass
        else:
            pass
if ans == 2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include<cstdio>
using namespace std;
int n,m,x,y,tot,v[1500],c[1500][2];
bool a[1500][1500],f[1500][1500];
int read() {
	int tmp=0, fh=1; char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}
	while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();
	return tmp*fh;
}
bool dfs(int x,int col) {
	//printf("%d %d\n",x,col);
	v[x]=col; c[tot][col-1]++;
	for (int i=1;i<=n;i++) if (x!=i&&(!a[x][i])) {
		if (!v[i]) {
			if (!dfs(i,3-col)) return 0;
		} else if (v[i]==v[x]) return 0;
	}
	return 1;
}
int main() {
	n=read(); m=read();
	for (int i=1;i<=m;i++) {
		x=read(); y=read();
		a[x][y]=a[y][x]=1;
	}
	for (int i=1;i<=n;i++) if (!v[i]) {
		tot++;
		if (!dfs(i,1)) {
			printf("-1\n"); return 0;
		}
	}
	f[0][0]=1;
	for (int i=1;i<=tot;i++)
	for (int j=n;j>=0;j--) if (f[i-1][j]) f[i][j+c[i][0]]=f[i][j+c[i][1]]=1;
	for (int i=n/2;i>=0;i--) if (f[tot][i]) {
		printf("%d\n",i*(i-1)/2+(n-i)*(n-i-1)/2);
		return 0;
	}
}

Measured memory_bytes: 3200
#include<cstdio>
#include<cstring>
int oo,N,sum,g[67108864],f[200010],x[27],n;
char s[200010];
int min(int a,int b)
{
	if (a<b) return(a);
	return(b);
}
int main()
{
	oo=1000000000;
	scanf("%s",s);
	n=strlen(s);
	N=1<<26;
	for (int i=0;i<N;i++) g[i]=oo;
	g[0]=0;
	for (int i=0;i<26;i++) x[i]=1<<i;
	x[26]=0;
	sum=0;
	for (int i=0;i<n;i++)
	{
		sum=sum^(1<<(s[i]-'a'));
		f[i]=oo;
		for (int j=0;j<=26;j++) f[i]=min(f[i],g[x[j]^sum]+1);
		g[sum]=min(g[sum],f[i]);
	}
	printf("%d\n",f[n-1]);
	return 0;
}

Measured memory_bytes: 263296
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = 1

#import collections
#lcm_pf = collections.defaultdict(int)
#for i, v in enumerate(a):
#    j = 2
#    pf = {}
#    while j ** 2 <= v:
#        ext = 0
#        while v % j == 0:
#            ext += 1
#            v //= j
#        if ext:
#            pf[j] = ext
#            lcm_pf[j] = max(lcm_pf[j], ext)
#        j += 1
#    if v != 1:
#        pf[v] = 1
#        lcm_pf[v] = max(lcm_pf[v], 1)
#for p in lcm_pf:
#    lcm = lcm * (p ** lcm_pf[p])
import math
for v in a:
    lcm = (lcm // math.gcd(lcm, v)) * v

ans = 0
for v in a:
    ans = ans + (lcm // v)
    #ans = (ans + (lcm // v)) % MOD
print(ans % MOD)


Measured memory_bytes: 75152
fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}

fn main() {
    let x = get_line().parse().unwrap();

    let mut res = 0;
    for i in 1..(x + 1) {
        if (i * (i + 1)) / 2 >= x {
            res = i;
            break;
        }
    }
    println!("{}", res);
}


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

int sum[10000001];
int main(){
	int n;scanf("%d",&n);
	rep(i,n){
		int h;scanf("%d",&h);
		sum[h]++;
	}
	for(int i=9999999;i>=0;i--)sum[i]+=sum[i+1];
	ll cnt=1;
	int a=4;
	for(int i=1;i<=10000000;i++){
		cnt+=min(a,sum[i]);
		a+=4;
	}
	printf("%lld\n",cnt);
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))
#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define nepit(x) for (__typeof((x).rbegin()) it = (x).rbegin(); it != (x).rend(); it++)
#define All(x) (x).begin(),(x).end()
#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))
#define Unique(v) v.resize(unique(All(v)) - v.begin())
#define End '\n'
#define Out(x) cout<<(x)<<End
#define OutP(p, sep, end) cout<<p.first<<sep<<p.second<<end
template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair
#define X first
#define Y second

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

struct Chunk {
	int left, right;
	int m;
	V<int> data;

	Chunk() : left(-1), right(-1), m(INT_MAX) {}

	int calc() {
		int ret = m;
	    V<Chunk> v;
		Chunk c;

		int i, len = data.size();

		rep(i, len) data[i] -= m;

		rep(i, len) {
			if (data[i] != 0) {
				if (c.left == -1) c.left = i;
				else c.right = i;
				
				c.data.pb(data[i]);
				c.m = min(c.m, data[i]);
			} else {
				if (c.left != -1) {
					if (c.right == -1) c.right = c.left;
					
					v.pb(c);
				}

				c.left = -1;
				c.right = -1;
				c.m = INT_MAX;
				c.data.clear();
			}
		}

		if (c.left != -1) {
			if (c.right == -1) c.right = c.left;

			v.pb(c);
		}
		
		len = v.size();
		rep(i, len) ret += v[i].calc();

		return ret;
	}
};

void solve(const V<Chunk> &v) {
	int ans = 0;

	for (auto c : v) ans += c.calc();

	Out(ans);
}

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

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

    int n;

	cin >> n;

	int h[n];
	Chunk c;
	V<Chunk> v;

	cin >> h[0];

	if (h[0] != 0) {
		c.left = 0;
		c.data.pb(h[0]);
		c.m = min(c.m, h[0]);
	}

	int i;

	repi(i, n, 1) {
		cin >> h[i];

		if (h[i] == 0 && c.left != -1) {
			v.pb(c);

			c.left = -1;
			c.right = -1;
			c.m = INT_MAX;
			c.data.clear();
		} else if (h[i] != 0) {
			if (c.left == -1) c.left = i;
			else c.right = i;
			
			c.data.pb(h[i]);
			c.m = min(c.m, h[i]);
		}
	}

	if (c.left != -1) {
		if (c.right == -1) c.right = c.left;

		v.pb(c);
	}

	if (v.size() != 0) solve(v);
	else Out(0);
	
	return 0;
}


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

typedef pair<int, int> P;
typedef long long ll;
const int mod = 1000000007;

bool square(ll a){ll n=(ll)sqrt(a);return a==n*n;}
int digitsum(ll N,int a);//a進数におけるNの各桁の和、計算量はloga(N)
ll mpow(ll x, ll n);
ll inv_mod(ll a){return mpow(a,mod-2);}
int gcd(int x,int y){return y ? gcd(y,x%y) : x;};//xとyの最大公約数
int lcm(int x,int y){return x*y/gcd(x,y);}//xとyの最小公倍数

class Fuctorical{//階乗とその逆元を求めて計算に利用するクラス
private:
    vector<ll> fac;
public:
    
    Fuctorical(ll N){
        fac.push_back(1);
        for(int i=0;i<N;i++) fac.push_back(fac[i]*(i+1)%mod);
    }

    ll fact(ll a){return fac[a];}
    ll ifact(ll a){return inv_mod(fac[a]);}

    ll cmb(ll a,ll b){
        if(b==0) return 1;
        if(a<b||a<=0) return 0;
        ll tmp =ifact(a-b)*ifact(b)%mod;
        return tmp*fac[a]%mod;
    }
};

int main(){
    string L;
    cin>>L;
    Fuctorical get(100001);
    ll N=L.length();
    ll ans=0;
    int num=0;
    int count=0;
    vector<int> V(N);
    REP(i,N){
        if(L[i]=='1') count++;
        V[i]=count;
    }
    ll X=0,Y=0;
    REP(i,N+1) (X+=get.cmb(N,i)*mpow(2,i)%mod)%=mod; 
    for(int i=1;i<N;i++){ 
        if(L[i]=='0') (Y+=mpow(3,N-i-1)*mpow(2,V[i]+1)%mod)%=mod;
    }
    //cout<<Y<<endl;
    ans=X-Y;
    if(ans<0) ans=mod+ans;
    cout<<ans<<endl;
}

int digitsum(ll N,int a){
    if(N==0) return 0;
    int ret=0;
    ret+=digitsum(N/a,a)+N%a;
    return ret;
}
ll mpow(ll x, ll n){ //x^n(mod division) ←普通にpow(x,n)では溢れてしまうため，随時mod計算 2分累乗法だから早い
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % mod;
        x = x*x % mod;
        n = n >> 1;
    }
    return ans;
}
/*
class Fuctorical{//階乗とその逆元を求めて計算に利用するクラス
private:
    vector<ll> fac;
public:
    
    Fuctorical(ll N){
        fac.push_back(1);
        for(int i=0;i<N;i++) fac.push_back(fac[i]*(i+1)%mod);
    }

    ll fact(ll a){return fac[a];}
    ll ifact(ll a){return inv_mod(fac[a]);}

    ll cmb(ll a,ll b){
        if(a==0&&b==0) return 1;
        if(a<b||a<0) return 0;
        ll tmp =ifact(a-b)*ifact(b)%mod;
        return tmp*fac[a]%mod;
    }
};
*/

/*
class UnionFind{//UnionFind木
 private:
    vector<int> Parent;
 public:
    UnionFind(int N){
        for(int i=0;i<N;i++) Parent.push_back(-1);
    }

    int root(int A){
        if(Parent[A]<0) return A;
        return Parent[A]=root(Parent[A]);
    }

    int size(int A){
        return -Parent[root(A)];
    }

    bool connect(int A,int B){
        A=root(A);
        B=root(B);
        if(A==B) return false;
        if(size(A)<size(B)) swap(A,B);
        Parent[A]-=Parent[B];
        Parent[B]=A;
    }
};
*/


Measured memory_bytes: 1780
#include<iostream>
using namespace std;
int main() {
	bool sosu[110000] = { false };
	for (int i = 2; i <= sizeof(sosu) / sizeof(bool); ++i) {
		if (sosu[i] == false) {
			for (int k = i * 2; k <= sizeof(sosu) / sizeof(bool); k+=i) {
				sosu[k] = true;
			}
		}
	}
	int answer;
	int time;
	while (1) {
		cin >> time;
		answer = 0;
		int cnt = 0;
		if (time == 0)break;
		for (int i = 2; cnt != time; ++i) {
			if (sosu[i] == false) {
				answer += i;
				++cnt;
			}
		}
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 1272
import copy
def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]
    B = copy.copy(A)
    B.sort()
    A_max = B[-1]
    A_sec = B[-2]
    for i in range(N):
        if (A[i] == A_max):
            print(A_sec)
        else:
            print(A_max)
resolve()

Measured memory_bytes: 14560
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using LL = long long;
using P = pair<int,int>;


int main(){
	int N;
	cin >> N;
	vector<int> a(N);
	rep(i,N) cin >> a[i];
	bool ok = false;
	int tmp = 1;
	rep(i,N){
		if(a[i] == tmp) {
			tmp++;
			ok = true;
		}
	}
	if(ok)	cout << N - tmp + 1 << endl;
	else cout << -1 << endl;
}













Measured memory_bytes: 4068
if __name__ == "__main__":
    N,x = list(map(int, input().split()))
    a=list(map(int, input().split()))

    result = 0


    for i in range(1,N):
        tot = a[i] + a[i-1]
        if tot>x:
            result += (tot - x)
            tmp = a[i]
            a[i] =  max(0, a[i]- tot +x)
            if a[i] == 0:
                a[i-1] = min(x,a[i-1])

    print(result)



Measured memory_bytes: 14152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second

int main(){
    ll n;
    cin >> n;
    queue<pair<ll,ll>> q;//BFS
    q.push({n,0});//残金、操作回数

    while(1){
        ll a = q.front().fi;
        ll i = q.front().se;
        
        if(a==0){
            cout << i << endl;
            return 0;
        }//終了条件
        
        q.pop();
        ll b=a,c=a;

        ll j=1,k=1;
        i++;//操作回数加算
        
        while(c>=0){//9^x引き出す
            c -= pow(9,k);
            if(c>0){
                k++;
                c += pow(9,k-1);
            }
            else if(c==0){
                cout << i << endl;
                return 0;
            }else if(k!=1){//k==1のときは６のwhileで処理させる
                q.push({a-pow(9,k-1),i});
            }
        }

        while(b>=0){//6^x引き出す
            b -= pow(6,j);
            if(b>0){
                j++;
                b += pow(6,j-1);
                continue;
            }
            else if(b==0){
                cout << i << endl;
                return 0;
            }else{
                q.push({a-pow(6,j-1),i});
            }
        }
    }
}

Measured memory_bytes: 768
N=int(input())
F={}
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        F[i]=1
        N//=i
    while N%i==0:
        N//=i
        F[i]+=1
if N>1:
    F[N]=1

ans=0
for f in F:
    j=1
    while True:
        F[f]-=j
        j+=1
        if F[f]>=0:
            ans+=1
        else:
            break
print(ans)

Measured memory_bytes: 9384
import sys
readline = sys.stdin.readline
from operator import add
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            pre = self.intv
            for idx in (SR + SL[::-1]):
                if check(self.segf(self.data[idx], pre)):
                    break
                else:
                    pre = self.segf(self.data[idx], pre)
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(self.data[2*idx+1], pre)):
                    idx = 2*idx + 1
                else:
                    pre = self.segf(self.data[2*idx+1], pre)
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.intv
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0


N, Q = map(int, readline().split())
A = list(map(int, readline().split()))
INF = 10**9+7
T = Segtree(A, -INF, initialize = True, segf = max)
Ans = []
N0 = T.N0
for _ in range(Q):
    t, x, v = map(int, readline().split())
    if t == 1:
        T.update(x-1, v)
    elif t == 2:
        Ans.append(T.query(x-1, v))
    else:
        k = T.binsearch(x-1, N0, lambda x: x >= v)
        if k == -1:
            Ans.append(N+1)
        else:
            Ans.append(k+1)

print('\n'.join(map(str, Ans)))
    

Measured memory_bytes: 117624
#include <queue>
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

class Point{
    public:
        int x, y, d;
        Point(int a, int b, int c){
            x = a;
            y = b;
            d = c;
        }
};

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    in_arr(string, s, h);
    int whites = 0;
    repi(i, s){
        repi(j, *i){
            if(*j == '.') whites++;
        }
    }
    queue<Point> q;
    int d;
    q.push(Point(0, 0, 1));
    while(!q.empty()){
        Point p = q.front();
        d = p.d;
        if(p.x == w - 1 && p.y == h - 1)
            break;
        q.pop();
        if(s[p.y][p.x] == '#')
            continue;
        s[p.y][p.x] = '#';
        if(p.x > 0){
            q.push(Point(p.x - 1, p.y, p.d + 1));
        }
        if(p.x < w - 1){
            q.push(Point(p.x + 1, p.y, p.d + 1));
        }
        if(p.y > 0){
            q.push(Point(p.x, p.y - 1, p.d + 1));
        }
        if(p.y < h - 1){
            q.push(Point(p.x, p.y + 1, p.d + 1));
        }

    }
    if(q.empty()){
        cout << -1 << endl;
    }else{
        cout << whites - d << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX;
const ll MOD = 998244353;

ll dp[2*112345][2][3][3];
int main() {
  string S;cin >> S;
  int N = S.length();
  int Smod3=0;
  bool uni=true;
  bool cont=false;
  repeat(i,N){
    Smod3 = (Smod3+S[i]-'a')%3;
    uni &= S[0]==S[i];
    if(i<N-1) cont|=S[i]==S[i+1];
  }
  if(uni){
    cout << 1 << endl;
    return 0;
  }
  if(N==2){
    cout << (S[0]==S[1]? 1:2)<<endl;
    return 0;
  }
  if(N==3){
    if((S[0]+S[1]+S[2])%3==0){
      cout << 3 << endl;
    }else if(cont){
      cout << 6 << endl;
    }else{
      cout << 7 << endl;
    }
    return 0;
  }
  //cerr << "!!!!!" << endl;
  repeat(i,3){
    dp[0][0][i][i] = 1;
  }
  repeat(i,N-1){
    repeat(t,2){
      repeat(last,3){
        repeat(mod3,3){
          repeat(s,3){
            dp[i+1][t|(last==s)][s][(mod3+s)%3] =
                    (dp[i+1][t|(last==s)][s][(mod3+s)%3]+dp[i][t][last][mod3])%MOD;
            //debug(dp[i+1][t|(last==s)][s][(mod3+s)%3]);
          }
        }
      }
    }
  }
  //debug(cont);
  ll ans = ((dp[N-1][1][0][Smod3]+dp[N-1][1][1][Smod3])%MOD+dp[N-1][1][2][Smod3])%MOD;
  if(!cont) ans = (ans+1)%MOD;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 29188
//--------------------------------------------------
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,avx,avx2,popcnt,fma")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//--------------------------------------------------
#include <bits/stdc++.h>
#include <chrono>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <time.h>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <stack>
#include <cstring>
//--------------------------------------------------
#define forn(i, n) for(int i = 0; i < n; i++)
#define forw(i, n) for(int i = n-1; i >= 0; --i)
#define forns(i, n, s) for(int i = s; i < n; i++)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
//----------------------------------------------------
using namespace std;
//----------------------------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef vector<ll> lnum;
typedef complex<ld> comp;
//----------------------------------------------------
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;
const ll inf = 1e18;
const int base = 1e9;
const ld PI = 3.1415926;
//----------------------------------------------------
//#define endl '\n';
#ifdef MY_DEBUG
void deb(ld x) { cerr << x << endl; };
#else
void deb(ld x){};
#endif
//----------------------------------------------------
//----------------------------------------------------
string s;
//----------------------------------------------------
unsigned int bitcount(ull val) { return __builtin_popcount(val) + __builtin_popcount(val >> 32); }

void local() {
    freopen("test.in", "r", stdin);
}

void remote() {
}

void read() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> s;
}

bool isPalindrome(int l, int r){
    while(l < r){
        if(s[l] != s[r])
            return false;
        l++;r--;
    }
    return true;
}

int main() {
#ifdef MY_DEBUG
    local();
#else
    remote();
#endif
    read();

    if(isPalindrome(0, s.size()-1) && isPalindrome(0, (s.size()-1)/2 - 1) && isPalindrome((s.size()+1)/2, s.size()-1)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

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

using namespace std;


int main() {
	double l;
	cin >> l;
	double a, b, c;
	a = b = l / 3;
	c = l - (a + b);

	printf("%lf\n", a * b * c);
	return 0;
}

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

const int obstacle=1;
const int start=2;
const int goal=3;
unsigned res;

int dr[]={-1, 0, 1, 0}, dc[]={0, -1, 0, 1};
int h, w;

void dfs(vector<vector<int>>& b, int r, int c, unsigned t)
{
    if (t>=10) return;

    for(int i=0;i<4;++i) {
        int nr=r+dr[i], nc=c+dc[i];
        if (b[nr][nc]==obstacle) continue;
        while (nr>0 and nr<=h and nc>0 and nc<=w and b[nr][nc]==0) {
            nr+=dr[i];
            nc+=dc[i];
        }
        if (nr<1 or nr>h or nc<1 or nc>w) continue;
        if (b[nr][nc]==obstacle) {
            b[nr][nc]=0;
            dfs(b, nr-dr[i], nc-dc[i], t+1);
            b[nr][nc]=obstacle;
        }
        else if (b[nr][nc]==goal) {
            res=min(res, t+1);
            return;
        }
    }
}

int main()
{
    while (cin>>w>>h, h) {
        vector<vector<int>> board(h+2, vector<int>(w+2));
        int sr, sc;
        for(int i=1;i<=h;++i) {
            for(int j=1;j<=w;++j) {
                cin>>board[i][j];
                if (board[i][j]==start) {
                    sr=i; sc=j; board[i][j]=0;
                }
            }
        }
        res=-1u;
        dfs(board, sr, sc, 0);
        cout<<(int)res<<endl;
    }
}

Measured memory_bytes: 1220
#include <stdio.h>

int main(void)
{
	long long k, n, t, max = 0;
	scanf("%lld%lld", &k, &n);
	long long a[n];
	for(t = 0; t < n; t++)
		scanf("%lld", &a[t]);

	max = a[1] - a[0];

	for(t = 0; t < n - 1; t++)
		if(max <= a[t + 1] - a[t])
			max = a[t + 1] - a[t];

	if(max <= k + a[0] - a[n - 1])
		max = k + a[0] - a[n - 1];

	printf("%lld", k - max);

	return 0;
}

Measured memory_bytes: 1664
n = int(input())
array = [input().split() for i in range(n)]
b_1 = []
b_2 = []
b_3 = []
b_4 = []
zero = "0 0 0 0 0 0 0 0 0 0"
for i in range(3):
    b_1.append(zero.split())
    b_2.append(zero.split())
    b_3.append(zero.split())
    b_4.append(zero.split())
for i in range(n):
    b = int(array[i][0])
    f = int(array[i][1])
    r = int(array[i][2])
    v = int(array[i][3])
    if b == 1:
        b_1[f-1][r-1] = str(int(b_1[f-1][r-1])+v)
    elif b == 2:
        b_2[f-1][r-1] = str(int(b_2[f-1][r-1])+v)
    elif b == 3:
        b_3[f-1][r-1] = str(int(b_3[f-1][r-1])+v)
    else:
        b_4[f-1][r-1] = str(int(b_4[f-1][r-1])+v)
for i in range(4):
    for i2 in range(3):
        for i3 in range(10):
            if i == 0:
                if i3 == 9:
                    print(b_1[i2][i3])
                elif i3 == 0:
                    print(" "+b_1[i2][i3],end=" ")
                else:
                    print(b_1[i2][i3],end=" ")
            elif i == 1:
                if i3 == 9:
                    print(b_2[i2][i3])
                elif i3 == 0:
                    print(" "+b_2[i2][i3],end=" ")
                else:
                    print(b_2[i2][i3],end=" ")
            elif i == 2:
                if i3 == 9:
                    print(b_3[i2][i3])
                elif i3 == 0:
                    print(" "+b_3[i2][i3],end=" ")
                else:
                    print(b_3[i2][i3],end=" ")
            else:
                if i3 == 9:
                    print(b_4[i2][i3])
                elif i3 == 0:
                    print(" "+b_4[i2][i3],end=" ")
                else:
                    print(b_4[i2][i3],end=" ")
    if i == 3:
        break
    else:
        print("####################")

Measured memory_bytes: 7796
package main

import (
	"fmt"
	"strings"
)

func main() {
	var a, b, c, now string
	fmt.Scan(&a, &b, &c)
	all := map[string]string{
		"a": a,
		"b": b,
		"c": c,
	}
	key := "a"
	for all[key] != "" {
		now = string(all[key][0])
		all[key] = all[key][1:]
		key = now
	}
	fmt.Print(strings.ToUpper(key))
}

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


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

	int n = N;
	int digitSums = 0;
	while(n >= 10){
		digitSums += n % 10;
		n = n / 10;

	}
	digitSums += n;


	if(N % digitSums == 0){
		cout << "Yes\n";
	}else{
		cout << "No\n";
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ip pair<ll,ll>
#define vii vector<ll>
#define vpp vector<ip>
#define vdd vector<ld>
#define vb vector<bool>
#define pi  pair<ll,ip>
#define sc(x) scanf("%lli",&x)
#define c(x) cin >> x
#define fo(i,k,n) for( int i=k;i<n;i++)
#define hu 200010
#define pq priotity_queue<ll>
#define pqs priority_queue<ll,vii,greater<ll>>
#define ppq priority_queue<ip,vpp,greater<ip>>
#define INF INT_MAX
#define ff first
#define ss second
using namespace std;
const ll M = 1000000000+7;
//Grid Movement
ll dx[] = {-1, 0, 1, 0};
ll dy[] = {0, -1, 0, 1};

ld Pi= acos(-1);

ll lcm(ll a,ll b)
{
    return (a*b)/(__gcd(a,b));
}

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

bool comp(ll comp1,ll comp2)
{
    return comp1>comp2;
}

void yes()
{
    printf("YES\n");
}

void no()
{
    printf("NO\n");
}

ll inv(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
 
    if (m == 1)
      return 0;
 
    while (a > 1)
    {
        int q = a / m;
        int t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
 
    if (x < 0)
       x += m0;
 
    return x;
}

void sieve(ll n)
{
    vii primes(n+1);
    vb is_prime(n+1);
	is_prime.resize(n+1);
	primes.resize(n+1);
 
	is_prime[0] = is_prime[1] = false;
	for(int i = 2; i<=n; i++)
	{
	    if(is_prime[i])
	    {
	    	primes.pb(i);
	        for (int j = i*i; j<=n; j+=i)
	            is_prime[j] = false;
	    }
	}
}

void solve()
{
    ll a;
    sc(a);
    ll x= a*(1+a+a*a);
    printf("%lli",x);
}

int main()
{
    ll t=1;
 //   sc(t);
    while(t--) solve();
}

Measured memory_bytes: 3788
import java.util.Scanner;

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

        sc.close();

        if (str.contains("Y")) {
            System.out.println("Four");
        } else {
            System.out.println("Three");
        }
    }
}


Measured memory_bytes: 21844
#include<stdio.h>

long long count_one(long long x, long long div){
  long long ret;
  long long q = x / div;
  long long r = x % div;
  if(q % 2 == 0){
    ret = (q / 2) * div;
  }else{
    ret = ((q - 1) / 2) * div + r + 1;
  }
  return ret;
}

int main(){
  long long a, b;
  scanf("%lld %lld", &a, &b);
  long long f = 0;
  long long div = 1;
  long long d = 0;
  while(b / div != 0){
    if((count_one(b, div) - count_one(a - 1, div)) % 2 == 1){
      f |= (1ull << d);
    }
    d++;
    div *= 2;
  }
  printf("%lld\n", f);
  return 0;
}


Measured memory_bytes: 128
def gcd(m,n):
    x=max(m,n)
    y=min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        else:
            return z

nums=list(map(int,input().split(" ")))
g=gcd(nums[0],nums[1])
arr=[0 for i in range(100)]
a=0
for i in range(100):
    i+=1
    if nums[0]%i==0 and nums[1]%i==0:
        arr[a]=i
        a+=1
        if i==g:
            print(arr[a-nums[2]])
            break

Measured memory_bytes: 3064
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
d = {}
for i in list(set(s) | set(t)):
    d[i] = 0
for i in s:
    d[i] += 1
for i in t:
    d[i] -= 1
print(max(0, d[max(d, key=d.get)]))

Measured memory_bytes: 3064
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define ALL(x) x.begin(), x.end()
using namespace std;

typedef vector<vector<int> > G;
const int inf = 1e9;

int n, m;
G graph;
vector<int> ans;

int visited[100100];

void dfs(int u){

    ans.push_back(u);
    visited[u] = 1;

    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if( !( visited[v] ) ){
            return dfs(v);
        }
    }
    return;
}

int main(void){
    cin >> n >> m;
    graph = G(n+100);
    for(int i=0; i<m; i++){

        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);

    }
    
    dfs(1);
    reverse(ans.begin(), ans.end());
    ans.pop_back();
    dfs(1);

    cout << ans.size() << endl;

    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << " ";
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 10104
#include<iostream>
#include<sstream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cfloat>
#include<functional>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<bitset>
#include<list>
#include<numeric>
#include<complex>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<long long, long long> ll_ll;
typedef pair<double, double> d_d;
typedef vector<int> Vint;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define rep2d(i, j, n) for(i = 0;i < n;++i)for(j = i + 1;j < n;++j)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << x << "\n"
#define pri2(x, y) cout << x << " " << y << "\n"
#define pri3(x, y, z) cout << x << " " << y << " " << z << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << x << "\n"
#define debug2(x, y) cout << " --- " << x << " " << y << "\n"
#define debug3(x, y, z) cout << " --- " << x << " " << y << " " << z << "\n"
#define X first
#define Y second
#define eps 0.000000001
#define prid(x) printf("%.15lf\n", x)


signed main(void){
  int i, j, k;
  for(int testcase = 0;testcase < 1234567;testcase++){
    for(;;){
      double d; cin >> d; if(d == 0.0)break;
      double t, b;
      bool fl = false;
      for(b = 1.0;!fl;b+=1.0){
        for(t = b * 3.0;t < b * 4.0;t+=1.0){
          if(PI - d <= t / b && t / b <= PI + d){
            fl = true;
            printf("%d/%d\n", (int)t, (int)b);
            break;
          }
        }
      }

    }

/*/

//*/ break;
  }
  return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int N;
	int M;
	int maxCoinsTmp = 0;
	int maxCoins;
	string tmp;

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

	cin >> M;
	string t[M];
	for (int k = 0; k < M; k++) { cin >> t[k]; }
	

	// s[]を検索
	for (int i = 0; i < N; i++) {

		tmp = s[i];
		maxCoinsTmp = 1;

		// i以外を検索
		for (int j = 0; j < N; j++) {
			
			if (j != i) {
				if (s[j] == tmp) {
					maxCoinsTmp++;
				}
			}
		
		}
		
		// t[]を検索
		for (int k = 0; k < M; k++) {
			if (t[k] == tmp) {
				maxCoinsTmp--;
			}
		}

		maxCoins = max(maxCoins, maxCoinsTmp);	
	}

	cout << max(0,maxCoins) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int a,b,wa,answer;
	while(scanf("%d %d",&a,&b) != EOF){
		answer = 1;
		wa = a+b;
		while(wa/10 != 0){
			wa = wa/10;
			answer++;
		}
		printf("%d\n",answer);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
 
int main() {
  int a,b;
  cin >> a >> b;
  vector<int> vec(b);
  rep(i, b) {
    cin >> vec.at(i);
  }
  int p = -1;
  rep(i, b-1) {
    if (vec.at(i+1) -vec.at(i) > p) {
      p = vec.at(i+1) -vec.at(i);
    }
    else continue;
  }
  if (p > a+vec.at(0)-vec.at(b-1)) {
    cout << a-p << endl;
  }
  else {
    cout << vec.at(b-1)-vec.at(0) << endl;
  }
}

Measured memory_bytes: 1024
n,m,x = map(int,input().split())
l = []
for i in range(n):
    ca = list(map(int,input().split()))
    l.append(ca)
ans = 9999999999
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(l[j])
    skill = [0]*m
    enough = [0]*m
    money = 0
    for sub in bag:
        money += sub[0]
        for k in range(1,m+1):
            skill[k-1] += sub[k]
            if skill[k-1]>=x:
                enough[k-1] += 1
        if 0 not in enough:
            if ans>money:
                ans = money
if ans == 9999999999:
    
    print(-1)
else:
    print(ans)




Measured memory_bytes: 9236
from bisect import *
while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    P = [int(raw_input()) for i in range(N)] + [0]
    P = sorted(set(i+j for i in P for j in P))
    P = P[:bisect(P,M) - 1]
    print max(i + P[bisect(P,M-i) - 1] for i in P)

Measured memory_bytes: 47464
N=gets.to_i
a = 1
b = 0
l = []
while a < N && b < N do
  b = N - a
  m = 0
  n = (a.to_s + b.to_s).split""
  n.each do |k|
    m += k.to_i
  end
  l << m
  a += 1
end
puts l.min


Measured memory_bytes: 2812
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n;
  cin >> n;
  long long a[n],b[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
    b[i]=a[i];
  }
  sort(b,b+n);
  for(int i=0;i<n;i++){
    if(a[i]<=b[n/2-1]){
      cout << b[n/2] << endl;
    }else if(a[i]>=b[n/2]){
      cout << b[n/2-1] << endl;
    }
  }
  return 0;  
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>p(n); for(auto&&i:p)cin>>i;
	int ans=0;
	for(int i=1;i<n;++i){
		if(p.at(i-1)==i)swap(p.at(i-1),p.at(i)),++ans;
	}
	if(p.back()==n)++ans;
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 640
import java.util.*;
public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        card [] A  = new card[n];
        for(int i=0;i<n;i++){
            card c = new card();
            c.insert(sc.next(),sc.nextInt(),i);
            A[i] = c;
        }
        quicksort(A,0,n-1);
        boolean check = true;
        for(int i=0;i<n-1;i++) if(A[i].num==A[i+1].num&&A[i].index>A[i+1].index) check = false;
        if(check) System.out.println("Stable");
        else System.out.println("Not stable");
        for(int i=0;i<n;i++) System.out.println(A[i].mark+" "+A[i].num);
    }
    public static void quicksort(card [] A,int p,int r){
        if(p<r){
            int q = partition(A,p,r);
            quicksort(A,p,q-1);
            quicksort(A,q+1,r);
        }
    }
    public static int partition(card [] A ,int p,int r){
        int x = A[r].num;
        int i = p-1;
        for(int j=p;j<r;j++){
            if(A[j].num<=x){
                i++;
                swap(A,i,j);
            }
        }
        swap(A,i+1,r);
        return i+1;
    }
    public static void swap(card [] A,int i,int j){
        String mark = A[i].mark;
        int num = A[i].num;
        int index = A[i].index;
        A[i].mark = A[j].mark;
        A[i].num = A[j].num;
        A[i].index = A[j].index;
        A[j].mark = mark;
        A[j].num = num;
        A[j].index = index;
    }
    public static class card{
        String mark;
        int num;
        int index;
        public void insert(String mark,int num,int index){
            this.mark = mark;
            this.num = num;
            this.index = index;
        }
    }
}


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

int dp[1025][100001];//dp[i][j]:頂点iまでで重みj以下最大、ただし頂点番号は問題のまま
struct P{int w,v;};
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}

int main(){
  int n;cin>>n;
  vector<int> v(n),w(n);
  for(int i=0;i<n;i++)cin>>v[i]>>w[i];
  for(int i=0;i<min(n,1024);i++){
    for(int j=0;j<100001;j++){
      dp[i+1][j]=dp[(i+1)/2][j];
      if(j-w[i]>=0)chmax(dp[i+1][j],dp[(i+1)/2][j-w[i]]+v[i]);
      if(j>0)chmax(dp[i+1][j],dp[i+1][j-1]);
    }
  }
  int q;cin>>q;
  while(q--){
    int a,l;cin>>a>>l;
    int ans=0;
    if(a<=1024){cout<<dp[a][l]<<endl;continue;}
    vector<P> S;//
    S.push_back({0,0});
    while(a>1024){
      int t=S.size();
      for(int i=0;i<t;i++)if(S[i].w+w[a-1]<=l)S.push_back({S[i].w+w[a-1],S[i].v+v[a-1]});
      a>>=1;
    }
    for(P p:S)chmax(ans,dp[a][l-p.w]+p.v);
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 405464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<l_l> vpl;
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=1;i<=(n);i++)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=10100100100100100;
template<class T> inline bool chmin(T& a,T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a,T b){
if(a<b){
a=b;
return true;
}
return false;
}
int main(){
    cout<<fixed<<setprecision(10);
    ll n;cin>>n;
    vector<vector<ld>> dp(n+1,vector<ld>(n+1));
    dp[0][0]=1.0;
    vector<ld> p(n);rep(i,n)cin>>p[i];
    rep(i,n){
        rep(j,n){
            dp[i+1][j+1]+=dp[i][j]*p[i];
            dp[i+1][j]+=dp[i][j]*(1.0-p[i]);
        }
    }
    ld ans=0.0;
    for(int i=n/2+1;i<=n;i++)ans+=dp[n][i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 141056
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <tuple>
#include <stdlib.h>

using namespace std;

int main()
{
	string S;
	cin >> S;
	if (S == "Sunny")cout << "Cloudy";
	if (S == "Cloudy")cout << "Rainy";
	if (S == "Rainy")cout << "Sunny";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
#define INF 1<<21
using pii = std::pair<int, int>;
#define SORT(v) std::sort(v.begin(), v.end())
int main(void) {
    int N;
    std::string ans;
    std::string s, t;
    std::cin >> s >> t;
    bool make = false;
    std::vector<std::string> ans_s;
    if (s.size() < t.size()) {
        std::cout << "UNRESTORABLE" << std::endl;
        return 0;
    }
    for (int i = 0; i <= s.size() - t.size(); i++) {
        make = true;
        for (int j = 0; j < t.size(); j++) {
            if (s[i + j] != '?'&&s[i + j] != t[j]) {
                make = false;
                break;
            }
        }
        if (make) {
            ans = s;
            for (int j = 0; j < t.size(); j++) {
                ans[i + j] = t[j];
            }
            for (int j = 0; j < ans.size(); j++) {
                if (ans[j] == '?') {
                    ans[j] = 'a';
                }
            }
            ans_s.push_back(ans);
        }
        

    }
    SORT(ans_s);
    if (!ans_s.empty()) {
        std::cout << ans_s[0] << std::endl;
    }
    else {
        std::cout << "UNRESTORABLE" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////

int main(){
    string s;cin>>s;
    string t[3]={"Sunny","Cloudy","Rainy"};
    rep(i,0,2){
        if(s==t[i]){
            cout<<t[(i+1)%3]<<endl;
        }
    }
    
    
    return 0;
}


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

int main(){
  int N;
  cin >> N;
  int a;
  set<int>S;
  for(int i = 0; i<N; i++){
    cin >> a;
    if(S.count(a)){
      cout << "NO" << endl;
      return 0;
    }
    S.insert(a);
  }
  cout << "YES" << endl;
  return 0;
  
}

Measured memory_bytes: 12848
A=list(map(int,input().split()))
A.sort()
a=A[2]-A[1]
b=A[2]-A[0]
if a%2==0 and b%2==0:
  print(a//2+b//2)
elif a%2==1 and b%2==1:
  print(a//2+b//2+1)
else:
  print(a//2+1+b//2+1)

Measured memory_bytes: 9188
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(M)]


uni = UnionFind(N)
res = []
for a,b in edges[::-1]:
    if uni.find(a-1) != uni.find(b-1):
        siz_a = uni.size(a-1)
        siz_b = uni.size(b-1)
        tmp = siz_a * siz_b
        res.append(tmp)
    else:
        res.append(0)
    uni.union(a-1, b-1)

bef = 0
for v in res[::-1]:
    print(v+bef)
    bef += v 

Measured memory_bytes: 34128