akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include<iomanip>
#include <algorithm>
#include <map>
#include <vector>
#include<queue>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include <map>
#include<string.h>
#include<sstream>
#include<stack>
#include<unordered_map>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <cstdio>
#include <cstdlib>
#include <complex>
#define ll long long
#define  point complex<double>
#define  pi acos(-1)
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define arr2dof vector  vector<vector<int>>dp(N,vector<int>(2, inf));
using namespace std;
const ll N = 2e5 + 5, mod = 1e9 + 7, inff = -1e12, inf = 1e9 + 7;
const double ep = 0.0000000001;
//const double pi = 3.14159265359;

double dot(point a, point b) {
	return  (conj(a)*b).real();
}
double cross(point a, point b) {
	return  (conj(a)*b).imag();
}
double angle(point a, point b)
{
	double dt = dot(a, b);
	dt /= abs(a);
	dt /= abs(b);
	return acos(dt) * 180.0 / pi;
}

bool isrightangel(int ind) {//90 degree
	vector<point>v;
	return(angle(v[ind] - v[(ind + 1) % 3], v[ind] - v[(ind + 2) % 3]) == 90);//bshof hal eldot producty3ny fe
	//dl3en 3moden 3ashn yb2a right trinagle
}

ll fact[1000006], inv[1000006];

ll fp(ll base, ll exp)
{
	if (exp == 0)
		return 1;
	ll ans = fp(base, exp / 2);
	ans = (ans * ans) % mod;
	if (exp % 2 != 0)
		ans = (ans * (base % mod)) % mod;
	return ans;
}

void calcFacAndInv(ll n)
{
	fact[0] = inv[0] = 1;
	for (ll i = 1; i <= n; i++)
	{
		fact[i] = (i * fact[i - 1]) % mod;
		inv[i] = fp(fact[i], mod - 2);
	}
}

ll ncr(ll n, ll r)
{
	return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

ll npr(ll n, ll r)
{
	return (fact[n] * inv[n - r]) % mod;
}

int GCD(int a, int b) {
	if (b == 0)
		return a;
	else
		return GCD(b, a%b);
}
int LCM(int a, int b) {
	return (a*b) / GCD(a, b);
}

void intersectline(pair<int,int>a, pair<int, int>b, pair<int, int>c, pair<int, int>d) {

	double a1, b1, c1, a2, b2, c2;
	 a1 = b.second - a.second;
	 b1 = a.first - b.first;
	 c1 = (a1 * a.first) + (b1 * a.second);


      a2 = d.second - c.second;
	  b2 = c.first - d.first;
	  c2 = (a2 * c.first) + (b2 * c.second);

	 double dt= a1 * b2 - a2 * b1;
	 double  dy, dx;
	 dx = c1 * b2 - c2 * b1;
	 dy = a1 * c2 - a2 * c1;
	 if (dt==0&&(dx!=0||dy!=0))
         cout << "NONE" << endl;
	 	 else if (dt == 0 && dx == 0&& dy == 0) {
		 cout << "LINE" << endl;
	 }
	 else {
		 double x = (b2*c1 - b1 * c2) / dt;
		 double y = (a1*c2 - a2 * c1) / dt;
		 if (x==0.0)
				cout <<fixed<<setprecision(2)<< "POINT" << " " << x << " " << y<< endl;
		
	 }

}
	
		

	double arr[3005];
	double dp[3005][3005];
int main()
{
	int n;
	memset(dp, 0.0, sizeof dp);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
	}
	dp[0][0] = 1.0;
	for (int i = 1; i <= n; ++i) {
		for (int l = 0; l <= i; l++) {
			if (l==0)
				dp[i][l] = dp[i - 1][l] * (1 - arr[i]);
			else
				dp[i][l] = dp[i - 1][l] * (1 - arr[i]) + dp[i - 1][l - 1] * arr[i];
		}
	}
	double ans = 0.0;
	for (int i = (n+1) / 2; i <= n; ++i) {
		ans += dp[n][i];
	}
	cout <<fixed<<setprecision(10)<< ans;
	return 0;
}

Measured memory_bytes: 74248
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
ll n;
ll xx[100005] , yy[100005];
ll p[200005];
ll fs(ll x)
{
        return p[x] == x ? x : p[x] = fs(p[x]);
}
void us(ll a , ll b)
{
        a = fs(a);
        b = fs(b);
        p[b] = a;
}
class pt1
{
public:
        ll x , y , id;
        pt1()
        {

        }
        pt1(ll a , ll b, ll yo)
        {
                x = a;
                y = b;
                id = yo;
        }
        bool operator< (pt1 &ot)
        {
                return x < ot.x;
        }
};
class pt2
{
public:
        ll x , y , id;
        pt2()
        {

        }
        pt2(ll a , ll b, ll yo)
        {
                x = a;
                y = b;
                id = yo;
        }
        bool operator< (pt2 &ot)
        {
                return y < ot.y;
        }
};
class edge
{
public:
        ll w , from , to;
        edge(ll a , ll b , ll c)
        {
                from = a;
                to = b;
                w = c;
        }
        bool operator< (edge &ot)
        {
                return w < ot.w;
        }
};
vector<pt1> A;
vector<pt2> B;
vector< pair<ll,ll> > g[500005];
vector< edge > e;
int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cin >> n;
        for(ll i=1;i<=n;i++)
        {
                ll p , q;
                cin >> p >> q;
                xx[i] = p;
                yy[i] = q;
                pt1 aa(p , q ,i);
                pt2 bb(p , q ,i);
                A.pb(aa);
                B.pb(bb);
        }
        sort(A.begin() , A.end());
        sort(B.begin() , B.end());
        for(ll i = 1 ;i < A.size() ; i++)
        {
                ll X = A[i].id;
                ll Y = A[i-1].id;
                ll ww = min(abs(xx[X] - xx[Y]) , abs(yy[X] - yy[Y]));
                edge E(X , Y , ww);
                e.pb(E);
        }
        for(ll i=1;i<B.size();i++)
        {
                ll X = B[i].id;
                ll Y = B[i-1].id;
                ll ww = min(abs(xx[X] - xx[Y]) , abs(yy[X] - yy[Y]));
                edge E(X , Y , ww);
                e.pb(E);
        }
        sort(e.begin() , e.end());
        for(ll i = 1 ; i <= n ; i++) p[i] = i;
        ll ans = 0;
        for(auto i : e)
        {
                //cout << i.from << " " << i.to << " " << i.w << endl;
                if(fs(i.from) == fs(i.to)) continue;
                us(i.from , i.to);
                ans += i.w;
        }
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 28580
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define bp __builtin_popcountll
const int N = 105;
string s;
ll k;
ll dp[N][N][2];

ll solve(ll id,ll tot,ll chk)
{
    if(id==s.size())
    {
        if(tot==k)  return 1;
        else        return 0;
    }
    ll ans = dp[id][tot][chk];
    if(ans!=-1)   return ans;
    ans = 0;
    if(chk==1)
    {
        for(ll i=0;i<s[id]-'0';i++)
        {
            if(i==0)
            {
                ans = ans + solve(id+1,tot,0);
            }
            else       ans += solve(id+1,tot+1,0);
        }
        if(s[id]=='0')    ans = ans + solve(id+1,tot,1);
        else             ans += solve(id+1,tot+1,1);
    }
    else
    {
        for(ll i=0;i<=9;i++)
        {
            if(i==0)   ans += solve(id+1,tot,0);
            else       ans += solve(id+1,tot+1,0);
        }
    }
    dp[id][tot][chk] = ans;
    return ans;
}
int main()
{
    cin >> s >> k;
    memset(dp,-1,sizeof(dp));
    ll ans = solve(0,0,1);
    cout<<ans;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>

//#define int long long
#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second

using namespace std;
using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

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; }
template<class T>void put_double(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
template<class T>void print(T a){cout << a << endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void) {
    int n; cin >> n; 
    if(n % 10 == 7 || n % 100 / 10 == 7 || n / 100 == 7) {
        print("Yes");
    } else {
        print("No");
    }

    return 0;
}


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

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

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

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans =0;
	string s;
	cin >>n;
	
	cout << 180 * (n-2) <<"\n";
	return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a=0,b=0;
    for(int i=0;i<3;i++)
    {
        scanf("%d",&n);
        if(n==5)
            a++;
        if(n==7)
            b++;
    }
    if(a==2&&b==1)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}


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

int n;
vector<vector<int>> g;
vector<int> par;

void make_par() {
    // now,from
    queue<pair<int, int>> bfs;
    bfs.push({0, -1});
    while (!bfs.empty()) {
        auto now = bfs.front();
        bfs.pop();
        par[now.first] = now.second;
        for (auto e : g[now.first]) {
            if (e == now.second) {
                continue;
            }
            bfs.push({e, now.first});
        }
    }
}

vector<int> path() {
    vector<int> res;
    int now = n - 1;
    res.push_back(now);
    while (now != 0) {
        now = par[now];
        res.push_back(now);
    }
    reverse(res.begin(), res.end());
    return res;
}

int area(int border, int enemy) {
    int res = 0;
    queue<pair<int, int>> bfs;
    bfs.push({border, enemy});
    while (!bfs.empty()) {
        auto now = bfs.front();
        bfs.pop();
        res++;
        for (auto e : g[now.first]) {
            if (e == now.second) {
                continue;
            }
            bfs.push({e, now.first});
        }
    }
    return res;
}

int main() {
    cin >> n;
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    par.resize(n, -1);
    make_par();
    auto route = path();
    int s = route.size();
    int black = route[(s - 1) / 2];
    int white = route[(s + 1) / 2];
    int black_area = area(black, white);
    int white_area = area(white, black);
    string winner;
    if (black_area > white_area) {
        winner = "Fennec";

    } else {
        winner = "Snuke";
    }
    cout << winner << endl;
}

Measured memory_bytes: 9784
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

    
def main():
    n,m,d=inpm()
    if d==0:
        print((m-1)/n)
    else:
        print(2*(n-d)*(m-1)/(n**2))

if __name__ == "__main__":
    main()

Measured memory_bytes: 39020
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)();
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return exp(x,big-2);
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/
    
    double a,b,x;cin >> a >> b >> x;
    if(a*a*b<=2*x){
        double h=2*(a*a*b-x)/(a*a);
        cout << atan(h/a)*180/acos(-1) << endl;
    }
   else{
       double h=2*x/(a*b);
       cout << atan(b/h)*180/acos(-1) << endl;
   }
}

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

signed main() {
  int n;
  cin >> n;
  vector<string> s;
  for(int i = 0; i < n; i++){
    string str;
    cin >> str;
    s.push_back(str);
  }

  sort(s.begin(), s.end());
  string last = s[0];
  int kinds = 1;
  for(int i = 1; i < n; i++){
    if(last != s[i]){
      kinds++;
      last = s[i];
    }
  }

  cout << kinds << endl;
}

Measured memory_bytes: 11660
#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define LL long long
const int inf = 1e9 + 9;
using namespace std;
inline int read() {
	int s = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			w = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}
const int N = 2e7 + 5;
const int base = 131;
const LL mod=192608179;
string a,b;
int t[N];
LL ha[N],hb[N],fac[N];
LL hsh(int x){
    if(x + b.size() > a.size()) return -1;
    return (ha[x + b.size() - 1] - ha[x - 1] * fac[b.size()] % mod + mod) % mod;
}
int main(){
    cin>>a>>b;
    while(a.size() < b.size() * 2) a = a + a;
    a = a + a,a = a + a,a = a + a;
    fac[0] = 1,ha[0] = a[0] - 'a',hb[0] = b[0] - 'a';
    for(int i = 1;i < a.size();++i) fac[i] = fac[i - 1] * base % mod;
    for(int i = 1;i < a.size();++i) ha[i] = (ha[i - 1] * base % mod + a[i] -'a') % mod;
    for(int i = 1;i < b.size();++i) hb[i] = (hb[i - 1] * base % mod + b[i] - 'a') % mod;
    for(int i = 0;i < a.size();++i) t[i] = hb[b.size() - 1] == hsh(i);
    int ans = 0;
    for(int i = a.size() - b.size();i >= 0;--i) if(t[i]) t[i] += t[i + b.size()],ans = max(ans,t[i]);
    if(ans + 1 >= a.size() / b.size()) puts("-1");
    else printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 342756
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int N = 2e3 + 5;

int cnt[N];

int n,x,y;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> x >> y;
	rep(i,1,n+1){
		rep(j,i+1,n+1){
			int res = min(j-i,abs(i-x) + 1 + abs(y-j));
			++cnt[res];
		}
	}
	rep(i,1,n)cout << cnt[i] << '\n';
}


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

int main() {
    int n, k;
    cin>>n>>k;
    vector<int> stones(n);
    for(int i=0; i<n; i++) cin>>stones[i];

    // dp[i] - whether player starting with i stones wins or loses
    vector<bool> dp(k+1, false);
    for(int i=0; i<=k; i++) {
        if(dp[i]) continue;
        for(int j=0; j<n && i + stones[j] <= k; j++)
            dp[i + stones[j]] = true;
    }
    if(dp[k]) cout<<"First"<<endl;
    else cout<<"Second"<<endl;

    return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = getLine >>= print . f

f "SUN" = 7
f "MON" = 6
f "TUE" = 5
f "WED" = 4
f "THU" = 3
f "FRI" = 2
f "SAT" = 1

Measured memory_bytes: 380
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	int a,b,c;
	cin >> a >> b >> c;
	for (int i = 1; i <= b; i++) {
		if (a*i%b == c) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		
		long h=0,w=0;
		
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long[] array = new long[n];
		
		for(int i=0; i < n; i++){
			array[i] = sc.nextLong();
		}
		
		Arrays.sort(array);
		
		//System.out.println(array[0]);
		
		for(int i=array.length-1; i>0; i--){
			if(array[i] == array[i-1]){
				if(h == 0){
					h = array[i];
					i--;
				}
				else{
					w = array[i];
					System.out.println(h*w);
					return;
				}
			}
		}
		
		System.out.println("0");
		
	}

}

Measured memory_bytes: 49132
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

#余りのモンスター
amari = 0
total = sum(A)

for i in range(N):
    if A[i] - B[i] >= 0:
        amari += A[i] - B[i]
    else:
        if A[i+1] - (B[i] - A[i]) >= 0:
            A[i+1] = A[i+1] - (B[i] - A[i])
        else:
            A[i+1] = 0

amari += A[N]

print(total - amari)

Measured memory_bytes: 18624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<bool>> t;
vector<bool> already;
int n,m;
int ans=0;
void rec(int next){
    already[next]=true;
    bool b=true;
    for(int i=0;i<n;i++){
        if(!already[i])b=false;
    }
    if(b){
        ans++;
        already[next]=false;
        return;
    }
    for(int i=0;i<n;i++){
        if(next==i)continue;
        if(!already[i]&&t[next][i]){
            rec(i);
        }
    }
    already[next]=false;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    already=vector<bool>(n,false);
    for(int i=0;i<n;i++){
        t.push_back(vector<bool>(n,false));
    }
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        t[a-1][b-1]=true;
        t[b-1][a-1]=true;
    }
    rec(0);
    cout<<ans<<endl;
    return 0;
}

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

#define MAXN 666

struct Edge {
	int to;
	bool can;
	Edge(int _to = -1, bool _can = false) : to(_to), can(_can) {}
};

vector<Edge> g[MAXN];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].emplace_back(v, true);
	}
	
	vector<double> dp(n);
	for(int i = n-2; i >= 0; i--) {
		dp[i] = 1;
		double tot = 0;
		for(Edge e : g[i]) {
			tot += dp[e.to];
		}
		
		dp[i] += tot / g[i].size();
	}
	
	double ans = dp[0];
	
	for(int i = 0; i < n-1; i++) {
		if((int) g[i].size() == 1) continue;
		int best = -1;
		double mx = -1;
		for(Edge e : g[i]) {
			if(dp[e.to] > mx) {
				best = e.to, mx = dp[e.to];
			}
		}
		
		for(Edge& e : g[i]) {
			if(e.to == best) {
				e.can = false;
			}
		}
		
		vector<double> new_dp(n);
		for(int u = n-2; u >= 0; u--) {
			new_dp[u] = 1;
			double tot = 0;
			int sz = 0;
			for(Edge e : g[u]) {
				if(!e.can) continue;
				sz++;
				tot += new_dp[e.to];
			}
			
			new_dp[u] += tot / sz;
		}
		
		ans = min(ans, new_dp[0]);
		
		for(Edge& e : g[i]) {
			if(e.to == best) {
				e.can = true;
			}
		}
	}
	
	cout << fixed << setprecision(10) << ans << endl;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include <stdlib.h>
#define M 10001

int main(){
  int i,j,n,*A,*B,C[M];
  scanf("%d",&n);
  A = malloc(sizeof(int)*n-1);
  B = malloc(sizeof(int)*n-1);
  for (i=0;i<M;i++){
    C[i]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d",&A[i+1]);
    C[A[i+1]]++;
  }
  for(i=1;i<M;i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=1;j<=n;j++){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  for(i=1;i<=n;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 17412
#include <stdio.h>

int main(){
  int H, W;


  while(1){
    scanf("%d %d", &H, &W);
    if(W==0&&H==0) break;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++) {
      printf("#");
    }
    printf("\n");
  }
  printf("\n");
}

  return 0;
}



Measured memory_bytes: 2044
#include <iostream>

using namespace std;

int main() {
    int n;
    cin>>n;
    bool ans = false;
    
    while(n>0){
        int temp = n%10;
        n/=10;
        
        if(temp==7){
            ans = true;
            break;
        }
    }
    
    string ch = ans ? "Yes" : "No";
    cout<<ch<<endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
int n,m,d;
int main(){
    scanf("%d %d %d", &n, &m, &d);
    long double res = (long double)(n-d)*(long double)(m-1)*2/((long double)n*n);
    if(d==0)res /= 2;
    printf("%.10llf\n",res);
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(ll i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln = '\n';

const int mx=200010;
const ll mod=1e9+7;

vector<int> v[mx];
 
vector<int> low(mx,-1);
vector<int> ord(mx,-1);
vector<pair<int,int>> bridge;                            //bridge
vector<int> art;                                         //articulation list
 
void dfs(int &count, int from, int x){
  ord[x] = count++;
  low[x] = ord[x];
  bool isart=false;
  int cnt=0;
  
  for(auto to:v[x]){
    if(to==from){ continue; }                            //kitatokoro
    if(ord[to]==-1){                                     // unseen
      cnt++;
      dfs(count,x,to); 
      if(ord[x]<low[to]){ bridge.emplace_back(min(x,to),max(x,to)); } //bridge?       
      if(from!=-1 && ord[x]<=low[to]){ isart=true; }
      low[x] = min(low[x],low[to]);
    } else { low[x] = min(low[x],ord[to]); }
  }
  if(from==-1 && cnt>1){ isart=true; }
  if(isart){ art.emplace_back(x);}                       //articulation?
}


int main(){
  int n,m;
  cin >> n >> m;
  rep(i,m){
    int x,y; cin >> x >> y; x--; y--;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  int cnt = 0;
  dfs(cnt,-1,0);
  int ans = bridge.size();
  cout << ans << ln;
  return 0;
}

Measured memory_bytes: 9452
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define show(x) cout<< #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll>pil;
typedef pair<ll,ll> pll;

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

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

const ll mod=1e9+7;
const int INF=INT_MAX/2;
const int N_MAX=300010;

ll a,b,n;

ll calc(ll x){
	return floor(a*x/b)-a*floor(x/b);
}

int main(){
	cin>>a>>b>>n;
	if(n+1>=b){
		cout<<floor(a*(b-1)/b)-a*floor((b-1)/b)<<endl;
	}else{
		if(n<100000){
			ll mx=0;
			for(ll i=1;i<=n;i++){
				mx=max(mx, calc(i));
			}
			cout<<mx<<endl;
		}else{
			ll left=0, right=n;
			ll middle;
			if(right%2==0)middle=right/2;
			else middle=(right+1)/2;
			while(middle!=right && middle!=left){
				if(calc(middle)<=calc(right)){
					left = middle;
					middle = (middle+right)/2;
				}else{
					right = middle;
					middle = (left+middle)/2;
				}
			}
			cout<<calc(middle)<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3764
x, y = map(int, input().split())

a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]

if x in a and y in a or x in b and y in b or x in c and y in c:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef complex<double> xy_t;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
ll inf = llmax / 2;

int main() {
    int N, M;
    cin >> N >> M;
    ll x[N], y[N], z[N];
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    ll ans = 0;
    int mark[3];
    ll a[N];
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 3; j++) {
            if ((i >> j) % 2 == 1) {
                mark[j] = 1;
            } else {
                mark[j] = -1;
            }
        }
        for (int j = 0; j < N; j++) {
            a[j] = x[j] * mark[0] + y[j] * mark[1] + z[j] * mark[2];
        }
        sort(a, a + N);
        reverse(a, a + N);
        ll n = 0;
        for (int j = 0; j < M; j++) {
            n += a[j];
        }
        if (n > ans) {
            ans = n;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n)]
ans = [0] * n
for _ in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)


q = deque([0])
visited = [False] * n
visited[0] = True

while q:
    now = q.popleft()
    
    for i in graph[now]:
        if visited[i]: continue
        
        visited[i] = True
        ans[i] = now
        q.append(i)
        

print("Yes")
for a in ans[1:]:
    print(a+1)

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

#define ll long long
#define pb push_back
#define ep emplace_back
#define st first
#define sc second

using namespace std;

const ll mod = 1e9 + 7;
const int e = 1e6 + 69;
const int base = 311;

// dung inverse module de tinh kCn
// 3
// cach tao hoan vi tu n so : n*(n+1)/2;

ll gt[e];
int a, b, n;


int main()
{
   ll n, m;
   cin >> n >> m;
   if(abs(n - m) > 1)
   {
       cout << 0;
       return 0;
   }
   gt[0] = 1;
   for(int i=1; i<=max(n, m); i++) gt[i] = (gt[i-1]*i%mod)%mod;
   if(n != m)
   {
       cout << (gt[n]%mod*gt[m]%mod)%mod;
   }
   else
   {
       cout << 2*(gt[n]%mod*gt[m]%mod)%mod;
   }
}


Measured memory_bytes: 1024
/*----------------by syr----------------*/
/*
  -----  -----  -----
  |   |  |---|    _/
  |   |  | \_    /
  -----  |   \  -----

  |---\  \   /  |\  /|
  |   |   \_/   | \/ |
  |   |   / \   |    |
  |---/  /   \  |    |
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i,x,y) for(int i=(x);i<(y);++i)
#define REP(i,x,y) for(int i=(x);i<=(y);++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;

const int INF=1e9+7;
const int maxn=1e5+5;

int n,k;
int h[maxn],dp[maxn];

int main(){
	scanf("%d%d",&n,&k);
	FOR(i,0,n) scanf("%d",h+i);
	FOR(i,0,n) dp[i]=INF;
	dp[0]=0;
	FOR(i,0,n){
		REP(j,i+1,min(i+k,n-1)) dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
	}
	printf("%d ",dp[n-1]);
	return 0;
}


Measured memory_bytes: 1024
// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long int lo;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define FOR for(lo i = 0 ; i < n ; i++)
#define FORV for(lo i = 0 ; i < (lo)v.size() ; i++)
lo a,b,d,e,x,y,n,p,m,t,a1[500005],a2[500000],c;
lo k;
string s1,s2,s3;
queue <pair<lo,lo> > q;
priority_queue <lo> pq;
map <lo,lo> mp1;
vector <lo> v;
lo vis[100000];
lo top;
int main(){
	// atcoder contest
	// freopen("gir.gir","r",stdin);
	// freopen("cik.cik","w",stdout);
	cin >> a >> b >> c;
	if((a == b && b != c) || (b == c && c != a) || (a == c && a != b)){
		cout << "Yes\n";
	}
	else{
		cout << "No\n";
	}
	return 0;
}


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

int main(){
    int x;
    cin >> x;
    if (x >= 30)
    {
        cout << "Yes" << endl;
    } else
    {
        cout << "No" << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = (a+b)*c/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;
typedef unsigned long long int ull;


int main()
{
	FAST;
	string str;
	cin >> str;
	if(str[0] != 'A')
	{
		cout << "WA";
		return 0;
	}
	bool flag = false;
	for(int i=1 ; i<str.size() ; i++)
	{
		if(str[i] == 'C')
		{
			if(flag)
			{
				cout << "WA";
				return 0;
			}
			
			if(i >= 2 && i <= str.size()-2)
			{
				flag = true;
			}
			else
			{
				cout << "WA";
				return 0;
			}
		}
		else if(str[i] >= 'A' && str[i] <= 'Z')
		{
			cout << "WA";
			return 0;
		}
	}

	if(!flag)
	{
		cout << "WA";
		return 0;
	}
	cout << "AC";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    int N;
    cin >> N;

    float x[N];
    vector<string> u(N);

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

    double otoshidama = 0;
    for(int i=0;i<N;i++){
        if(u[i] == "BTC"){
            otoshidama += (x[i] * 380000.0);
        }
        else otoshidama += x[i];
    }

    cout << otoshidama << endl;

    return 0;
}

Measured memory_bytes: 256
# 写経
# https://atcoder.jp/contests/m-solutions2020/submissions/15454214
 
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def resolve(XYP):
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	#print(X_cost)
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[:B], np.abs((Y-Y[n]) * P))
	#print(Y_cost)
	popcount = np.zeros(1 << N, np.int64)
	for n in range(N):
		popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1
	#print(popcount)
 
	INF = 10**18
	ans = np.full(N + 1, INF, np.int64)
	for s in range(1 << N):
		size = popcount[s]
		t = s
		#print("s" + str(s))
		#print("size" + str(size))
		for _ in range(INF):
			u = s ^ t
			#print("u" + str(u))
			#print("t" + str(t))
			cost = (np.minimum(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	return ans 
 
if sys.argv[-1] == 'ONLINE_JUDGE':
	import numba
	from numba.pycc import CC
	i8 = numba.int64
	cc = CC('my_module')
 
	def cc_export(f, signature):
		cc.export(f.__name__, signature)(f)
		return numba.njit(f)
 
	resolve = cc_export(resolve, (i8[:], ))
	cc.compile()
 
from my_module import resolve
 
N = int(readline())
XYP = np.array(read().split(), np.int64)
 
ans = resolve(XYP)
print('\n'.join(map(str, ans.tolist())))

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vi a(n),b(n),c(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n) cin>>c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    ll ans=0;
    rep(i,n){
        ll A = lower_bound(all(a),b[i])-a.begin();
        ll B = c.end()-upper_bound(all(c),b[i]);
        ans+=A*B;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 1408
N = int(input())
activities = []
plans = ['A', 'B', 'C']
for _ in range(N):
    activities.append(tuple(map(int, input().split())))
dp = {i: {p: 0 for p in plans} for i in range(1, N+1)}
for i, p in enumerate(plans):
    dp[1][p] = activities[0][i]
for i in range(2, N+1):
    a, b, c = activities[i-1]
    dp[i]['A'] = max([dp[i-1][p] + a for p in plans if p != 'A'])
    dp[i]['B'] = max([dp[i-1][p] + b for p in plans if p != 'B'])
    dp[i]['C'] = max([dp[i-1][p] + c for p in plans if p != 'C'])
print(max([dp[N][p] for p in plans]))

Measured memory_bytes: 69064
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

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

	vector<int> x(n), y(n);
	vector<int> xary, yary;

	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		xary.push_back(x[i]);
		yary.push_back(y[i]);
	}

	sort(begin(xary), end(xary));
	sort(begin(yary), end(yary));

	ll ans = 1LL * (xary[n-1]-xary[0]) * (yary[n-1]-yary[0]);

	for (int xi = 0; xi < n; xi++) {
		for (int xj = xi + 1; xj < n; xj++) {
			for (int yi = 0; yi < n; yi++) {
				for (int yj = yi + 1; yj < n; yj++) {
					int num=0;
					ll lx = xary[xi], rx = xary[xj];
					ll by = yary[yi], uy = yary[yj];

					for (int i = 0; i < n; i++) {
						// x[i]が長方形に含まれているか
						if (lx <= x[i] && x[i] <= rx && by <= y[i] && y[i] <= uy) {
							num++;
						}
					}
					if(num >= k) ans = min(ans, 1LL*(rx-lx)*(uy-by));
				}
			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <list>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(s,i,n) for(int i=s;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define skip(i,n,p) for(int i=0;i<n;i+=p)
#define int64 long long
#define debug cout << __FILE__ << ":" << __LINE__ << endl;

struct Init {
    Init() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
        cout << fixed;
    }
} init;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {
    for(int i = 0; i < (int) v.size(); i++) {
        ostr << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return ostr;
}

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

int X, Y;

int main() {
    cin >> X >> Y;

    if (X < 0 && Y < 0) {
        cout << abs(Y - X) + (X <= Y ? 0 : 2) << endl;
    } else if (X < 0) {
        cout << min(abs(Y + X) + 1, abs(Y - X)) << endl;
    } else if (Y < 0) {
        cout << abs(Y + X) + 1 << endl;
    } else {
        cout << abs(Y - X) + (Y - X < 0 ? 1 : 0) + (X > Y ? 1 : 0)  - (Y == 0 ? 1 : 0) << endl;
    }
}


Measured memory_bytes: 256
r,g,b,n = map(int,input().split())
a = [0]*(n+1)
a[0] = 1
for j in range(n+1-r):
    a[j+r]=a[j]
for j in range(n+1-b):
    a[j+b]+=a[j]
for j in range(n+1-g):
    a[j+g]+=a[j]
    #print(a)
print(a[n])


Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>
  
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
  
typedef struct node * Node;
  
Node root;


Node Search(Node t,int k);

void Insert(int k);

void Inorder(Node t);

void Preorder(Node t);

  

  
main(){
  int i, a, n;
  char A[10];
    
  scanf("%d",&n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%s",A);
  
    if (A[0]=='i'){
      scanf("%d",&a);
      Insert(a);
    } 
    else if (A[0]=='p'){
      Inorder(root);
      printf("\n");
        
      Preorder(root);
      printf("\n");
    }
    else if(A[0]=='f'){
      
      scanf("%d",&a);
      Node s=Search(root,a);
      if (s!= NULL ) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}


Node Search(Node t,int k){
  if(t==NULL || k==t->key){
    return t;
  }
  if(k<t->key){
    return Search(t->left,k);
  }
  else return Search(t->right,k);
}



void Insert(int k){
  Node y=NULL;
  Node x=root;
  Node z;
  
  z=malloc(sizeof(struct node));
  z->key=k;
  z->left=NULL;
  z->right=NULL;
    
  while(x!=NULL){
    y=x;
  
    if(z->key<x->key){
      x=x->left;
    }
    else x=x->right;
  }
  z->parent=y;
    
  if(y==NULL){
    root=z;
  }
  else if(z->key<y->key){
    y->left=z;
  }
  else y->right=z;
}



void Inorder(Node t){
    
  if(t!=NULL){
    if(t->left!=NULL){
      Inorder(t->left);
    }
    printf(" %d",t->key);
      
    if(t->right!=NULL){
      Inorder(t->right);
    }
  }
}



void Preorder(Node t){
  printf(" %d",t->key);
  if(t!=NULL){
    if(t->left!=NULL){
      Preorder(t->left);
    }
    if(t->right!=NULL){
      Preorder(t->right);
    }
  }
}
  



Measured memory_bytes: 20432
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

template<typename A>
using vpix = vector<pair<int, A>>;

vpix<char> u;
vpix<string> m;

int f(string s) {
  int c = 0, l = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    for (auto p : u) {
      if (s[i] == p.second) {
        c += p.first * (l <= p.first ? 1 : -1);
        l = p.first;
      }
    }
  }
  return c;
}

void solve() {
  u.pb(mp(1000, 'M'));
  u.pb(mp(500, 'D'));
  u.pb(mp(100, 'C'));
  u.pb(mp(50, 'L'));
  u.pb(mp(10, 'X'));
  u.pb(mp(5, 'V'));
  u.pb(mp(1, 'I'));
  string s;
  while (cin >> s) cout << f(s) << endl;
}

Measured memory_bytes: 3152
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T1> bool chmax(T1 &a, const T1 &b) { if (a < b) { a = b; return true; } return false; }
template<class T1> bool chmin(T1 &a, const T1 &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int T1,T2;
	int A1,A2;
	int B1,B2;
	cin>>T1>>T2>>A1>>A2>>B1>>B2;
	int P=(A1-B1)*T1,Q=(A2-B2)*T2;
	if(P>0)P=-P,Q=-Q;
	A1*=T1,A2*=T2,B1*=T1,B2*=T2;

	if(P+Q==0)
	{
		cout<<"infinity"<<endl;
		return 0;
	}
	if(P>0)
	{
		swap(A1,B1);
		swap(A2,B2);
	}
	if(P+Q<0)cout<<"0"<<endl;
	else
	{
		/*int T=(-P)/(P+Q);
		T*=2;
		if((-P)%(P+Q)!=0)T++;
		cout<<T<<endl;*/
		int D=A1+A2-B1-B2;
		int T=(B1-A1)/D;
		T*=2;
		if((B1-A1)%D!=0)T++;
		cout<<T<<endl;
	}
	

	return 0;
}


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

using namespace std;

const int N = 1e5+5;
int q[N];

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int Max = 0,cnt = 0;
    for(int i=0;i<n;i++) cin >> q[i];
    for(int i=1;i<n;i++){
    	if(q[i]<=q[i-1]) cnt++;
    	else if(cnt>=Max){
    		Max = cnt;
    		cnt = 0;
		}else cnt = 0;
	}
	if(cnt>=Max) Max = cnt;
	cout << Max << endl;
    
	return 0;
}


Measured memory_bytes: 640
class Node():
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        
def insert(key):
    global root

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)


n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    else:
        ino(root);print();pre(root);print()
        
    


Measured memory_bytes: 105420
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n,mx=0,i;
    cin>>n;
    string s;   
    map<string ,ll> mp1;
    for(i=0;i<n;i++){
        cin>>s;
        mp1[s]++;
    }
    for(auto x:mp1){
        mx=max(mx,x.second);
        //cout<<x.first<<" "<<x.second<<endl;
    }
    for(auto x:mp1){
        if(x.second==mx){
            cout<<x.first<<endl;
        }
    }
}

Measured memory_bytes: 25216
#include <iostream>
#include <vector>
#include <algorithm>

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

int main()
{
  int N;
  cin >> N;
  int d[N];
  vector<int> a;
  rep(i,N) cin >> d[i];
  sort(d, d + N);
  rep(i, N) {
    if(i==0)
      a.push_back(d[i]);
    else {
      if(d[i] != d[i-1])
        a.push_back(d[i]);
    }
  }
  cout << a.size() << endl;
  return 0;
}


Measured memory_bytes: 256
# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-

import math


def main():
    N = int(input())
    P = list(map(int, input().split()))
    tmp = [f != s for f, s in zip(P, sorted(P))]
    if sum(tmp) <= 2:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()


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

int main() {
  string s;
  cin >> s;
  
  if ((s.at(5)=='0') 
    && (s.at(6)=='1' || s.at(6)=='2' 
        || s.at(6)=='3' || s.at(6)=='4')) {
      cout << "Heisei" << endl;
  }
  else {
    cout << "TBD" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<memory.h>
#include<stdlib.h>
int comp(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}
int main(void)
{
	char s[100005];
	scanf("%s", s);
	int l = strlen(s);
	int i, sc = 0;
	for (i = 0; i < l; i++)
	{
		if (i % 2 == 0)
		{
			if (s[i] == 'p')
				sc--;
		}
		else
		{
			if (s[i] == 'g')
				sc++;
		}
	}
	printf("%d", sc);
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

var (
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
)

func main() {
	defer writer.Flush()
	var S string
	fmt.Fscanf(reader, "%s\n", &S)
	SArray := strings.Split(S, "")
	for i, s := range SArray {
		if i % 2 == 0 {
			fmt.Fprintf(writer, "%s", s)
		}
	}
	fmt.Fprint(writer, "\n")
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






long long int gcd(long long int a,long long int b)
{
 
  long long int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int n,y;
  cin>>n>>y;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n-i;j++){
      if(i*10000+j*5000+(n-i-j)*1000==y){
        cout<<i<<' '<<j<<' '<<n-i-j<<endl;
        return 0;
      }
    }
  }
  cout<<-1<<' '<<-1<<' '<<-1<<endl; 
}
///////////////////////////

Measured memory_bytes: 256