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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int n;
  cin >> n;

  vector<double> p(n);
  rep(i,0,n) cin >> p[i];

  vector<vector<double>> dp(n+1, vector<double>(n+1));
  dp[0][0] = 1;

  rep(i,0,n) {
    rep(j,0,i+1) {
      dp[i+1][j] += dp[i][j]*(1-p[i]);
      dp[i+1][j+1] += dp[i][j]*p[i];
    }
  }

  double ans = 0;
  rep(j,n/2+1,n+1) ans += dp[n][j];
  cout << fixed  << setprecision(10) << ans << '\n';
}

Measured memory_bytes: 70784
#include<cstdio>
#include<algorithm>
#define MM	1000000001 
using namespace std;
int dp[1001][1001],d[1000],c[1000];
int main(void)
{
	int n,m,i,j,k,mn;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&d[i]);
	}
	for(i=0;i<m;i++){
		scanf("%d",&c[i]);
	}
	for(i=0;i<=n;i++){
		for(j=0;j<=m;j++){
			dp[i][j]=MM;
		}
	}
	dp[0][0]=0;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(dp[i][j]!=MM){
				dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
				dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+d[i]*c[j]);
			}
		}
	}
	mn=MM;
	for(i=0;i<=m;i++){
		mn=min(mn,dp[n][i]);
	}
	printf("%d\n",mn);
	return 0;
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    string s, t;
    cin >> s >> t;
    int ans = INF;
    for (int i=0; i+sz(t)<=sz(s); ++i) {
        int cnt = 0;
        for (int j=0; j<sz(t); ++j) if (s[i+j] != t[j]) ++cnt;
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3596
n,K = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for k in range(K,n+2):
  #ans += (n+1)*n//2 -(n+1-k)*(n-k)//2-k*(k-1)//2 + 1
  #ans += (n**2+n)//2 - (n**2-n*k+n-k-n*k+k**2)//2 - (k**2-k)//2 + 1
  #ans += (n**2+n - (n**2-n*k+n-k-n*k+k**2) -k**2 + k)//2 + 1
  #ans += (n**2 + n - n**2 + n*k - n + k + n*k - k**2 - k**2 + k)//2 + 1
  #ans += (2*n*k + 2*k - 2*k**2)//2 + 1
  ans += n*k - k**2 + k  + 1
print(ans%mod)

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

int main()
{
  int a,b;
  cin>>a>>b;
  int mn=min(a,b);
  int mx=max(a,b);
  for(int i=0;i<mx;i++)
    cout<<mn;
  cout<<endl;
 
  return 0;
}

Measured memory_bytes: 256
#include <limits>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <bitset>
#include <map>
#include <unordered_map>
#include <cstdint>
using namespace std;


int main(){
    int a,b;
    cin >> a >> b;

    cout << (a <= 8 && b <= 8 ? "Yay!" : ":(") << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
using namespace std;

int main() {

	unsigned long long K;
	unsigned long long N;
	cin >> K >> N;

	unsigned long long Anew = 0;
	unsigned long long Aold;
	unsigned long long A1;
	unsigned long long diff = 0;
	unsigned long long diff_max = 0;
	cin >> A1;

	Aold = A1;
	for (unsigned long long i = 0; i < N - 1; i++) {
		cin >> Anew;
		diff = Anew - Aold;
		if (diff > diff_max) {
			diff_max = diff;
		}
		Aold = Anew;
	}

	diff = (K - Anew) + A1;
	if (diff > diff_max) {
		diff_max = diff;
	}

	cout << K - diff_max << endl;

	return 0;
}



Measured memory_bytes: 256
d = {}
n = int(raw_input())
for i in range(n):
	s = raw_input()
	if d.get(s) == None:
		d[s] = 1;
	else:
		d[s] += 1;
m = int(raw_input())
for i in range(m):
	s = raw_input()
	if d.get(s) == None:
		d[s] = -1;
	else:
		d[s] -= 1;
ans = -10000000000
for i in d:
	if d[i] > ans:
		ans = d[i];

print max(ans,0);

Measured memory_bytes: 2568
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,q = inpl()
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
c = [0] * n
for i in range(q):
    a,b = inpl()
    c[a-1] += b
q = deque()
q.append(0)
fin = [False] * n
fin[0] = True
while q:
    v = q.popleft()
    for nv in g[v]:
        if fin[nv]:continue
        c[nv] += c[v]
        fin[nv] = True
        q.append(nv)
print(*c)

Measured memory_bytes: 122000
fun main() = Thread(null, ::abc169b, "(^o^)", 128 * 1024 * 1024).apply { start() }.join()

@OptIn(ExperimentalStdlibApi::class)
fun abc169b() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(' ').map { it.toLong() }

    if (aList.contains(0)) return println(0)

    val max = 1000000000000000000L

    var answer = aList.first()

    for (a in aList.drop(1)) {
        if (answer > 0 && max / answer < a && max / a < answer)
            return println(-1)
        answer *= a
        if (answer > max)
            return println(-1)
    }

    println(answer)
}


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

using namespace std;
const long long INF = 1LL<<60;
//const long long INF = 100;


int main(){
    long long A, B, N;
    cin >> A >> B >> N;
    long long ok = 0;
    long long ng = B;

    long long ans = 0;

    while( abs(ok - ng) > 1){
        long long mid = (ok + ng) /2;

        long long left = floor((A*mid)/B);
        long long right = A*floor((mid/B));
        long long calc = left - right;
        if(mid <= N){
            if(calc >= ans){
                ok = mid;
                ans = calc;        
            }else{
                ng = mid;
            }
        } 
        else{
            ng = mid;
        } 
    }

    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <math.h>
#define rep(i,n) for(int i=0;i<=(n);i++)
using namespace std;


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

  if(d == 25){
    cout << "Christmas";
  }else if(d == 24){
    cout << "Christmas Eve";
  }else if(d == 23){
    cout << "Christmas Eve Eve";
  }else if(d == 22){
    cout << "Christmas Eve Eve Eve";
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  int N;
  string s;
  cin >> N >> s;
  int cnt = 0;
  for (int i = 0; i < N-2; i++) {
    if (s.at(i) == 'A' && s.at(i+1) == 'B' && s.at(i+2) == 'C') {
      cnt++;
    }
  }
  
  cout << cnt<< endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long double ld;
typedef long long ll;

int main(){
    ios;
    string s,t;
    cin >> s >> t;
    bool flag = true;
    rep(i,s.size()){
        if(t[i] != s[i]) flag = false;
    }
    cout << ((flag)? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 3652
import numpy
A, B, C, X, Y = map(int, raw_input().split())
min_idx = numpy.argmin([X, Y])
max_idx = numpy.argmax([X, Y])
cost = 0
if A + B > 2 * C:
    cost += 2 * C * min(X, Y)
else:
    cost += (A + B) * min(X, Y)
if [A, B][max_idx] > 2 * C:
    cost += 2 * C * (max(X, Y) - min(X, Y))
else:
    cost += [A, B][max_idx] * (max(X, Y) - min(X, Y))
print cost


Measured memory_bytes: 16392
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define abs(x) (x<0?(-x):x)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 1000000000000000005
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int main(){
	int n;
	while(~getI(n)) printf("%s\n",(n==3||n==5||n==7)?"YES":"NO");
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int a,b,c,x,y;
	int ans = 0;
	scanf("%d %d %d %d %d",&a,&b,&c,&x,&y);
	/*
	2*abピザの値段 < a+b だったら
	xとyの小さい方をまず abピザで埋めてその後 abピザのほうが安かったら残りもそちらで作る。
	*/
	if( 2*c < a+b){	//abピザ2枚の方がaピザbピザを個別に買うよりも安い場合
		if(x>y){	//aピザの方が買う枚数が多い場合
			ans += 2*c*y;	//bピザの値段を加算する
			if( 2*c < a){	//abピザを二枚買うほうがaピザよりも安い場合
				ans += (x-y)*2*c;
				printf("%d",ans);
				return 0;
			}else{
				ans += (x-y)*a;
				printf("%d",ans);
				return 0;
			}
		}else
		{	
			//bピザを買う枚数の方が多い場合
			ans += 2*c*x;	//aピザの値段を加算する
			if(2*c < b){	//abピザ二枚の方がbピザより安い場合
				ans += 2*c*(y-x);
				printf("%d",ans);
				return 0;
			}else{
				ans += b*(y-x);
				printf("%d",ans);
				return 0;
			}
		}
		
	}else{
		ans += a*x + b*y;
		printf("%d",ans);
		return 0;
	}
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int n;
	cin >> n;
	int b[n+1];
	b[0] = b[n] = 1000000;
	REP(i,n-1) cin >> b[i+1];
	ll sum = 0;
	REP(i,n){
		sum += min(b[i],b[i+1]);
	}
	printf("%lld",sum);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
#include<string>
#include<math.h>
#define ll long long
using namespace std;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
const ll N= 1e8;
inline void fastio()
{ 
     ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
ll a[1000005], number[1000005],repeat[1000005];
int main()
{
    ll n, ans = 0,maxn=0;
    cin >> n;
    for (ll i = 1; i <= n;i++) 
    {
        cin >> number[i];
        maxn = max(maxn, number[i]);
    }
    for (ll i = 1; i <= n;i++)
    {
        if(repeat[number[i]]==1)
            a[number[i]] = 1;
        repeat[number[i]] = 1;
        for (ll j = 2; (j * number[i]) <= maxn; j++)
                a[j * number[i]] = 1;
    }
    for (ll i = 1; i <= n;i++)
    {
        if(a[number[i]]==0)   ans++;
    }
    cout << ans;
    system("pause");
    return 0;
}

Measured memory_bytes: 20816
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 12; i++) {
            int n = sc.nextInt();
            if (m.containsKey(n)) {
                m.put(n, m.get(n) + 1);
            } else {
                m.put(n, 1);
            }
        }
        int c = 0;
        for (Map.Entry<Integer, Integer> e : m.entrySet()) {
            if (e.getValue() % 4 == 0) {
                c += e.getValue() / 4;
            }
        }
        System.out.println(c == 3 ? "yes" : "no");
    }
}


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

int main() {
  vector<ll> abc(3);
  for (int i=0; i<3; i++) cin >> abc.at(i);
  sort(abc.begin(), abc.end());
  if (abc.at(2)%2) cout << abc.at(0) * abc.at(1) << endl;
  else cout << 0 << endl;
}
  

Measured memory_bytes: 256
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as C
import Data.List

r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

mdl :: Num a => a
mdl = 10^9 + 7

t a b = a * b `mod` mdl

positivize x = if x < 0 then x + mdl else x

main :: IO ()
main = do
    [n,a,b] <- r' :: IO [Int]
    let al = powMod 2 n - 1
    let na = choose n a
    let nb = choose n b
    print $ positivize $ (al - na - nb) `mod` mdl

powMod :: Int -> Int -> Int
powMod cur 0 = 1
powMod cur n
    | even n = powMod (t cur cur) (div n 2)
    | odd n  = (t cur) $! powMod (t cur cur) (div n 2)

chooseOpt n i
    | n-i < i   = choose n (n-i)
    | otherwise = choose n i

choose :: Int -> Int -> Int
choose n i = t (prod' $ U.generate i (+ (n-i+1)) ) $ modInv (prod' $ U.generate i succ)

prod' :: U.Vector Int -> Int
prod' = U.foldr' t 1

modInv :: Int -> Int
modInv a =  let (x,_,1) = eEA a mdl
            in  positivize x

eEA :: Int -> Int -> (Int, Int, Int)
eEA a 0 = (1, 0, a)
eEA a b =   let (q, r) = a `quotRem` b
                (s, t, g) = eEA b r
            in  (t, s-q*t, g)

Measured memory_bytes: 7164
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h = onem()
co = 1
c = 0
while h:
    h //= 2
    c += co
    co *= 2

print(c)




Measured memory_bytes: 38384
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

template <class T, class U>
ll euclid_gcd(T a, U b){
    if(a < b)return euclid_gcd(b,a);
    ll r;
    while((r = a%b)){
        a = b;
        b = r;
    }
    return b;
}


int main(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<int> res(n), l(n), r(n);
    rep(i,n){
        if(!i){l[i] = a[i];continue;}
        l[i] = euclid_gcd(l[i-1],a[i]);
    }
    for(int i = n-1; 0 <= i; i--){
        if(i == n-1){r[i] = a[i];continue;}
        r[i] = euclid_gcd(r[i+1], a[i]);
    }
    rep(i,n){
        if(!i){
            res[i] = r[i+1];
            continue;
        }
        if(i == n-1){
            res[i] = l[i-1];
            continue;
        }
        res[i] = euclid_gcd(l[i-1], r[i+1]);
    }
    cout << *max_element(res.begin(), res.end()) << endl;
    return 0;
}

Measured memory_bytes: 2176
#include <vector>
#include <iostream>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
#include <deque>
#include <algorithm>
using namespace std;

const int maxn = 2e6, mod = 1e9 +7;

int n, m, cnt[maxn], used[maxn], a[maxn], dp[maxn][2];

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	long long cnt = 0;
	long long last = 0;

	for(int i= 1; i <= n; i++) {
		int x;
		cin >> x;
		if(x == 0) cnt += last / 2, last = 0;
		else last +=x;
	}
	cnt += last / 2;
	cout << cnt;
}


//22 84 84 22
//1  2  3 4  2
//1 2 1  2


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<char> table(26);
    for(int i = 0; i < s.size(); i++){
        char ans = s[i] + n > 'Z' ? s[i] + n - 26 : s[i] + n;
        cout << ans;
    }
    cout << endl;
}

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

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,lessl<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define double long double

#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()

#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define endl "\n"

#define f(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)

#define bp __builtin_popcountll
#define inf 1e18

const int N=1e5+5;
const int M=1e9+7;
void solve()
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(a[k]<a[i]+a[j] && a[i]!=a[j] && a[j]!=a[k])
				ans++;
				
			}
		}
	}
	cout<<ans<<endl;
}



signed main()
{
	FAST
    int t=1;
    // cin>>t;
    for(int tc=1;tc<=t;tc++)
    {
    	// cout<<"Case #"<<tc<<": ";
    	solve();
    }
}


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

int main()
{
    int N, Z, W;
    cin >> N >> Z >> W;
    int A[N+3];
    for(int i = 0; i < N; ++i) cin >> A[i];

    if(N == 1) cout << abs(A[0] - W) << endl;
    else cout << max(abs(A[N-1] - W), abs(A[N-2] - A[N-1]));
    return 0;
}

Measured memory_bytes: 256
from math import gcd

def main():
    N = int(input())
    A = list(map(int, input().split()))
    R = [0] * (N+1)
    L = [0] * (N+1)
    for i in range(N):
        L[i+1] = gcd(L[i], A[i])

    for i in range(N-1,-1,-1):
        R[i] = gcd(R[i+1], A[i])
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i],R[i+1]))
    print(ans)

if __name__ == "__main__":
    main()

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

int main() {
  int L,R,d,ans=0;
  cin >> L >> R >> d;
  for(int i=L;i<R+1;i++){
    if(i%d==0)ans++;
  }
  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3588
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma once
#include<bits/stdc++.h>
#define q register

typedef long long ll;

using namespace std;

ll n,ans,sum;

inline ll qread()
{
	q char ch=getchar();
	q ll v=0;
	while(ch<'0'||ch>'9')   ch=getchar();
	while(ch>='0'&&ch<='9'){
		v=v*10+ch-'0';
		   ch=getchar();
	}
	return v;
}

inline void qwrite(ll v)
{
	if(v>9)   qwrite(v/10);
	   putchar(v%10+'0');
}

int main()
{
	n=qread();
	sum=1;
	for(q ll i=1;;i++){
		sum*=2;
		if(sum>n){
			ans=sum/2; 
			   break;
		}
	}
	qwrite(ans);
	   putchar('\n');
	return 0;
}

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

const long int MAX_Q = 100001;

int main(int argc, char const *argv[]) {
  long int Q;
  long int l[MAX_Q], r[MAX_Q];
  bool f[100001];
  int c[100002];

  cin >> Q;
  for (int i = 0; i < Q; i++) cin >> l[i] >> r[i];

  for(int i=2;i<=100000;i++) if(!f[i]) for(int j=i+i;j<=100000;j+=i) f[j]=true;
  for(int i=3;i<=100000;i+=2) if(!f[i]&&!f[(i+1)/2]) c[i]++;
  for(int i=3;i<=100000;i++) c[i]+=c[i-1];

  for (int i = 0; i < Q; i++) {
    cout << c[r[i]] - c[l[i]-1] << endl;
  }
  
  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 131082;

int N;
vector<ii> al[MX_N];

vector<ii> dfs(int u, int lim) {
    vector<ii> res;
    if (al[u].empty()) {
        res.emplace_back(0,0);
    } else {
        assert(SZ(al[u]) == 2);
        ii v = al[u][0], w = al[u][1];
        vector<ii> l = dfs(v.fi,lim), r = dfs(w.fi,lim), a, b;
        if (SZ(l) > SZ(r)) { swap(v,w); swap(l,r); }

        for (int i = 0, j = 0; i < SZ(l) && j < SZ(r); ++i) {
            while (j < SZ(r) && l[i].sc + v.sc + r[j].fi + w.sc <= lim) ++j;
            if (j > 0) {
                a.emplace_back(l[i].fi + v.sc, r[j-1].sc + w.sc);
                b.emplace_back(r[j-1].sc + w.sc, l[i].fi + v.sc);
            }
        }

        for (int i = 0, j = SZ(b)-1; i < SZ(a) || j >= 0;) {
            ii x;
            if (j < 0 || (i < SZ(a) && a[i] < b[j])) 
                x = a[i++];
            else
                x = b[j--];
            if (res.empty() || res.back().sc > x.sc) {
                while (!res.empty() && res.back().fi == x.fi) res.pop_back();
                res.push_back(x);
            }
        }

        //cout << "dfs " << u << " " << v.fi << ":" << v.sc << " " << w.fi << ":" << w.sc << " :: ";
        //for (auto& x : res) cout << x.fi << "," << x.sc << ' ';
        //cout << endl;
    }

    return res;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int A, V; cin >> A >> V;
        al[A].emplace_back(i+1,V);
    }

    int lo = -1, hi = 1e9; 
    //ll lo = -1, hi = 10;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        //cout << "TRY " << mid << endl;
        if (dfs(1,mid).empty()) lo = mid;
        else hi = mid;
    }
    cout << hi;
}


Measured memory_bytes: 22784
#include <bits/stdc++.h>
#define MAXN 10010
using namespace std;
typedef long long int lli;
lli N , M;
string S , T;
lli gcd(lli a , lli b){
    if(a > b) swap(a,b);
    
    if(a == 0) return b;
    
    return gcd(b%a , a);
}

int main()
{
    cin >> N >> M >> S >> T;
    
    
    lli L = (long long)(N*M) / gcd(N,M);
    lli a = L / N , b = L / M;
    
    lli ekp = a*b/gcd(a,b);
    
    lli i1 = ekp / a , i2 = ekp / b , p = 0 , q = 0;
    
    //cout << i1 <<  " " << i2 << endl;
    
    bool flag = true;
    while(p < N && q < M){
        if(S[p] != T[q]) flag = false;
        p += i1 , q += i2;
    }
    
    
    if(!flag) cout << -1 << '\n';
    else cout << L << endl;
    
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;

int main(){

	string s;
	cin >> s;
	if(s.length()!=26){
		for(char c='a'; c<='z'; c++){
			if(s.find(c)==-1){
				cout << s << (char)c << endl;
				return 0;
			}
		}
	} else {
		for(int i=s.size(); 0<i; i--){
			if(s[i]>s[i-1]){
				auto p=s.substr(i);
				sort(p.begin(), p.end());
				for(auto c:p){
					if(s[i-1]<c){
						cout << s.substr(0, i-1) << c << endl;
						return 0;
					}
				}
			}
		}
	}
	cout << -1 << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
ll gcd(ll a,ll b){
  ll r = a%b;
  while(r>  0){
    a = b;b=r;r=a%b;
  }
  return b;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b;cin>>a>>b;
  ll c = gcd(a,b);
  ll ans = 1;
  if(c%2 == 0){
    ans++;
    while(c%2 == 0){
      c/=2;
    }
  }
  for(ll i=3;i<=sqrt(c);i+=2){
    if(c%i == 0){
      ans++;
      while(c%i == 0){
	c/=i;
      }
    }
  }
  if(c > 1)ans++;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
string shafushafu;
int main(){
	#ifdef FILIN
		#ifndef LOCAL
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>shafushafu;
	for(int i=0;i<3;i++)
		if(shafushafu[i]=='7'){
			cout<<"Yes"<<endl;
			return 0;
		}
	cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3652
import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

dp = np.zeros((N+1, N+1), dtype='float')
dp[0, 0] = 1

for i in range(N):
    dp[i+1][:-1] += dp[i][:-1] * p1_list[i]
    dp[i+1][1:]  += dp[i][:-1] * p0_list[i]

print(np.sum(dp[N, (N+1)//2:]))


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

#ifndef ONLINE_JUDGE
	#define W(x, y) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << y;
#else
	#define W(x, y)
#endif


#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define vl vector<ll>
#define vll vector<pll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pi acos(-1)
#define ld long double
#define prime 1000000007

using namespace std;

#define INF 1000000000

ll pot(ll b, ll e){
	ll res = 1;
	while(e){
		if(e&1){
			res *= b;
			res %= prime;
		}
		b *= b;
		b %= prime;
		e >>= 1;
	}
	return res;
}

ll fat(ll n){
	ll res = 1;
	for(int i = 2; i <= n; ++i){
		res *= i;
		res %= prime;
	}
	return res;
}

ll comb(ll n, ll k){
	// if(n == 0 || n == 1){
	// 	return 1;
	// }
	// if(k == 0 || k == n){
	// 	return 1;
	// }
	// if(k == 1 || k == n-1){
	// 	return n;
	// }
	// return (comb(n-1, k-1) + comb(n-1, k))%prime;
	ll a = fat(n);
	ll b = pot((fat(n-k) * fat(k))%prime, prime-2);
	return (a * b) % prime;
}

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

	ll x, y;
	cin >> x >> y;
	
	if((x + y)%3 == 0){
		ll n = (x + y)/3;
		ll x0 = n, y0 = 2*n;
		for(ll x0 = n, y0 = 2*n, i = 0; y0 >= n && x0 <= 2*n; ++x0, --y0, ++i){
			if(x0 == x && y0 == y){
				cout << comb(n, i)%prime << endl;
				return 0;
			}
		}
		cout << 0 << endl;
	} else{
		cout << 0 << endl;
	}

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  int H, W; cin >> H >> W;
  vstr S(H); cin >> S;
  vector<vi64> xsums(H + 1, vi64(W + 1));
  vector<vi64> ysums(H + 1, vi64(W + 1));
  rep(i, W) rep(j, H) {
    if (S[j][i] == '.') xsums[j + 1][i + 1] = xsums[j][i + 1] + 1;
  }
  rep(i, H) rep(j, W) {
    if (S[i][j] == '.') ysums[i + 1][j + 1] = ysums[i + 1][j] + 1;
  }
  rep(i, W) rrep(j, H) {
    if (xsums[j][i + 1] == 0) continue;
    amax(xsums[j][i + 1], xsums[j + 1][i + 1]);
  }
  rep(i, H) rrep(j, W) {
    if (ysums[i + 1][j] == 0) continue;
    amax(ysums[i + 1][j], ysums[i + 1][j + 1]);
  }
  i64 ans = 1;
  reps(i, H) reps(j, W) {
    if (ans < xsums[i][j] + ysums[i][j] - 1) {
      ans = xsums[i][j] + ysums[i][j] - 1;
      // cerr << i << " " << j << '\n';
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 69120
#include<stdio.h>

int main(void){
  int n;
  scanf("%d",&n);
  
  int a[n];
  for(int i = 0;i < n;i ++){
    scanf("%d",&a[i]);
  }

  int iro[8] = {0} , max = 0;
  
  for(int i = 0;i < n;i ++){
    if(a[i]/400 < 8){
     iro[a[i]/400] = 1;
    }
    else{
      max ++;
    }
  }
  
  int count = 0;
  for(int i = 0;i <= 7;i ++){
    if(iro[i] == 1){
      count ++;
    }
  }
  
  if(count == 0){
   printf("1 %d",max);
  }
  
  else{
  printf("%d %d",count,count + max);
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define mp make_pair
#define f first
#define s second
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
 
void fio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const long double pi = 3.14159265358979323846;



void solve() {
  ll n, m, k; cin >> n >> m >> k;
  ll a[n], b[m];
  f0r(i, n) cin >> a[i];
  f0r(i, m) cin >> b[i];

  ll s = 0;
  f0r(i, n) s += a[i];

  ll pt = n - 1;
  ll ans = 0;
  while (s > k) {
    s -= a[pt];
    --pt;
  }
  ans = pt + 1;
  f0r(i, m) {
    s += b[i];
    while (s > k && pt >= 0) {
      s -= a[pt];
      --pt;
    }
    if (s <= k) ans = max(ans, pt + i + 2);
  }
  cout << ans << '\n';
}
 
int main() {
  fio();
  
  int T = 1;
  // cin >> T;
  while (T--) solve();
} 

Measured memory_bytes: 6724
#include <iostream>
using namespace std;
int main(){
	int n,m,ans;
	int f=1;
	int i,o;
	cin>>n>>m;
	for(ans=m;n>0;n--){
		cin>>i>>o;
		m+=(i-o);
		if(ans<m)ans=m;
		if(m<0)f=0;
	}
	cout<<ans*f<<endl;
	
	return 0;
}


Measured memory_bytes: 1160
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	ll N;
	cin >> N;
	ll A[100010];
	ll B[100010];
	vector<ll>C(N);
	vector<pair<ll,ll>>P(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
		C[i] = A[i] + B[i];
		P[i].first = C[i];
		P[i].second = i;
	}
	sort(P.begin(), P.end(),greater<pair<ll,ll>>());
	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		if (i % 2 == 0) {
			ans += A[P[i].second];
		}
		else {
			ans -= B[P[i].second];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 2e5 + 33, mod = 1e9 + 7;
#define left dsajfil
int n, to[maxn], deg[maxn];
set<pi, greater<pi>> bydeg;
set<int> left;
void erase(int x) {
	left.erase(x);
	bydeg.erase({deg[x], x});
	x = to[x];
	bydeg.erase({deg[x], x});
	bydeg.insert({--deg[x], x});
}
vi ans;
void brute() {
	vi t;
	for(auto i : left) t.pb(i);
	do {
		if((ans.empty()||to[ans.back()]!=t[0])&&to[t[0]]!=t[1]&&to[t[1]]!=t[2]) {
			for(auto i : t) ans.pb(i);
			return;
		}
	} while(next_permutation(all(t)));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(deg, 0, sizeof deg);
	cin >> n;
	if(n==2) return cout << -1, 0;
	for(int i = 1; i <= n; i++) cin >> to[i], deg[to[i]]++;
	for(int i = 1; i <= n; i++) {
		left.insert(i);
		bydeg.insert({deg[i], i});
	}
	while(true) {
		if(left.size()==3) {
			brute();
			break;
		}
		if(bydeg.begin()->first == left.size()-1) {
			ans.pb(bydeg.begin()->second);
			erase(bydeg.begin()->second);
		} else {
			auto it = left.begin();
			if(!ans.empty()&&to[ans.back()]==*it) it++;
			ans.pb(*it);
			erase(*it);
		}
	}
	for(auto i : ans) cout << i << " ";
}



Measured memory_bytes: 14716
#define cross(a1, b1, a2, b2) ((a1)*(b2)-(a2)*(b1))
int main(){
  double a[20],b[20],s,t,x;
  int n,c=1,i;

    for(i=0;~scanf("%lf,%lf",a+i,b+i);i++);
    n=i;
    for(i=s=t=0;i<n-1;i++){
      if((x=cross(a[i],b[i],a[i+1],b[i+1]))>0)
        s+=fabs(x)/2.0;
      else
        t+=fabs(x)/2;
    }
    if((x=cross(a[i],b[i],a[0],b[0]))>0)
      s+=fabs(x)/2;
    else
      t+=fabs(x)/2;
    printf("%.6f\n",fabs(s-t));

  return 0;
}

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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ll  = long long;
using ii  = pair<int, int>;
using vi  = vector<int>;
using vd  = vector<double>;
using vb  = vector<bool>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

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; }
template<class T>
T GCD(T a, T b) { if (b == 0) return a; else return GCD(b, a % b); }
template<class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;

	double con = 0.0;
	int w = 0, s = 0;

	for (int i = 0; i <= 30; ++i) {
		for (int j = 0; j <= 30; ++j) {
			for (int k = 0; k <= ceil((double)f / c); ++k) {
				for (int l = 0; l <= ceil((double)f / d); ++l) {
					int water = a * i + b * j;
					int suger = c * k + d * l;
					int total = 100 * water + suger;

					if (total <= f && suger <= water * e) {
						if (con < (double)suger / total) {
							con = (double)suger / total;
							w = 100 * water;
							s = suger;
						}
					}
				}
			}
		}
	}
	if (con == 0) w = 100 * a;

	cout << w + s << " " << s << endl;

}

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

using namespace std;

const int MAX = 26;
int G[MAX][MAX],n,visit[MAX];
string str;
bool flg;
 
void dfs(int pos){
    visit[pos] = 0;
    for(int i = 0 ; i < 26 ; i++){
	if(G[pos][i]&&visit[i]){
	    G[pos][i]--;
	    dfs(i);
	}
    }
}
 
int main(){
    while(cin >> n,n){
	map<char,int> in,out;
	fill(G[0],G[MAX],0);
	fill(visit,visit+MAX,0);
	for(int i = 0 ; i < n ; i++){
	    cin >> str;
	    in[str[0]]++; out[str[str.size()-1]]++;
	    visit[str[0]-'a'] = visit[str[str.size()-1]-'a'] = 1;
	    G[str[0]-'a'][str[str.size()-1]-'a']++;
	}
	flg = false;
	for(char j = 'a' ; j <= 'z'; j++){
	    if(in[j] != out[j]) flg = true;
	}
	if(!flg){
	    dfs(str[str.size()-1]-'a');
	    for(int i = 0 ; i < 26 ; i++){
		if(visit[i]) flg = true;
	    }
	    if(flg) cout << "NG" << endl;
	    else cout << "OK" << endl;
	}
	else cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3068
/*
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College
    Date:13/06/2020
*/
#include<bits/stdc++.h>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
#define int long long
#define ld long double
#define ff first
#define ss string 
#define se second
#define alt(v) v.begin(),v.end()
#define pb emplace_back
#define mp make_pair
#define fab(i,a,b) for(ll i=(a);i<(b);i++)
#define fba(i,a,b) for(ll i=(b);i>=(a);i--)
#define arr(i,n) fab(i,0,n)
ll mod=1000000007;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
bool test = 0;


void solve()
{
   
    int x,n;
    cin>>x>>n;
    map<int,int>m;
    for(int i=0;i<n;i++)
    {
        int y;
        cin>>y;
        m[y]++;
    }
    int x1=-1,x2=-1;
    for(int i=x;i>=0;i--)
    {
        if(m[i]==0)
        {
            x1=i;
            break;
        }
    }
    for(int i=x+1;i<=101;i++)
    {
        if(m[i]==0)
        {
            x2=i;
            break;
        }
    }
    if(x1==-1 or x2==-1)
    {
        cout<<max(x1,x2);
        return;
    }
    if(abs(x1-x)==abs(x2-x))
    {
        cout<<min(x1,x2);
        return;
    }
    if(abs(x1-x)<abs(x2-x))
    cout<<x1;
    else
    cout<<x2;
    
    
}










signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t=1;
    if(test)
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;

int main()
{
    int  n;
    cin >> n;
    if (n%2 == 0) {
        cout << n << endl;
    }else{
        cout << n * 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<set>
 
using namespace std;
 
int par[100000];
int ran[100000];
 
/* union find */
void init(int n) {
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		ran[i] = 0;
	}
}
 
int find(int x) {
	if (par[x] == x) return x;
	return par[x] = find(par[x]);
}
 
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (ran[x] < ran[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (ran[x] == ran[y]) ran[x]++;
	}
}
 
bool same(int x, int y) {
	return find(x) == find(y);
}
 
 
int main() {
	int n, m, x, y;
	cin >> n >> m;
	vector<size_t> p(n);
	for (auto& e : p) cin >> e;
 
	init(n);
 
 
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		unite(x-1, y-1);
	}
 
	int ret{ 0 };
	for (int i = 0; i < n; ++i) {
		if (same(i , p[i]-1)) ++ret;
	}
	cout << ret << endl;
 
	return 0;
}

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

int main() {
    int box[100002] = {};
    int num[100002];
    box[1] = 1;
  int n, m;

  cin >> n >> m;


  for(int i = 1; i <= n; i++){
      num[i] = 1;
  }

  int x, y;
  for(int i = 1; i <= m; i++){
      cin >> x >> y;
      if(num[x] == 0)continue;
      else if(num[x] == 1){
          box[y] |= box[x];
          box[x] = 0;
          num[y]++;
          num[x] = 0;
      }else if(num[x] > 1){
          box[y] |= box[x];
          num[y]++;
          num[x]--;
      }
  }

  int ans = 0;

  for(int i = 1; i <= n; i++){
      if(box[i] == 1)ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))

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

#define MAX_NUM (int)1e5 + 10
#define INF (int)1e9

using namespace std;

int dp[MAX_NUM] = { INF };
int h[MAX_NUM];

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

  cin >> h[0];
  //dp[0] = 0;

  for (auto id = 1; id < N; id++)
  {
    cin >> h[id];
    int dp1 = dp[id - 1] + abs(h[id] - h[id - 1]);
    int dp2 = dp1;

    if (id >= 2)
      dp2 = dp[id - 2] + abs(h[id] - h[id - 2]);
    
    dp[id] = min(dp1, dp2);
  }


  cout << dp[N -1] - dp[0] << endl;
}


Measured memory_bytes: 1024
/*
 * A.cpp
 *
 *  Created on: 2018/07/04
 *      Author: saca
 */

#include <iostream>

using namespace std;

int main() {
	int n;

	scanf("%d", &n);

	if(n%2 == 0)
	{
		printf("%d\n", n);
	}else
	{
		printf("%d\n", n*2);
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define all(a) a.begin(),a.end()
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define dbg_v(v) cout<<#v<<":";for(auto c:v) cout<<" "<<c; cout<<endl;
int power(ll x,ll y){ll res = 1;while(y>0){if(y&1)res = (res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
void solve(){
	ll h;
	cin>>h;
	int res=(double)log2(h);
	//cout<<res<<endl;
	ll p=1,ans=0;
	ans=(ll)pow(2,res+1)-1;
	cout<<ans<<endl;
}
int main(){ 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	
	int T=1;
//	cin>>T;
	while(T--){
		solve();
	}
}


Measured memory_bytes: 4060
/* dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define    endl        '\n'
#define pii         pair<ll ,ll>
#define vll          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005

int main()
{
    ios
    string a,b;
    ll i,j;
    cin>>a>>b;
    map<char,char>m,mm;
    for(i=0;i<a.size();i++){
        if(a[i]!=b[i]){
            m[a[i]]=b[i];
            mm[b[i]]=a[i];
        }
    }
    for(i=0;i<a.size();i++){
        if(m[a[i]]!=0&&b[i]!=m[a[i]]){
           cout<<"No";return 0;
        }
        if(mm[b[i]]!=0&&a[i]!=mm[b[i]]){
           cout<<"No";return 0;
        }
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 916
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j]+A[i][k])
print(max(dp[N]))

Measured memory_bytes: 47328
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int):
    if str(N) == str(N)[::-1]:
        print(YES)
    else:
        print(NO)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
int count[199];
int number=0;

void push(int x);
int pop();
  int main(){
  char s[199];
  int y;
  while(scanf("%s",s)!=EOF){
      switch(s[0]){
      case '+':
        push(pop()+pop());
        break;
      case '*':
        push(pop()*pop());
        break;
      case '-':
          y=pop();
        push(pop()-y);
        break;
      default:
        push(atoi(s));
        break;
      }
    }
    printf("%d\n",pop());
    return 0;
}
void push(int x){
  number++;
  count[number]=x;
}
int pop(){
  number--;
  return count[number+1];
}



Measured memory_bytes: 2104
s=input()
l=[]
i=0
while i < len(s):
    if i<len(s)-1:
        if s[i]=='B' and s[i+1]=='C':
            l.append('D')
            i+=2
        else:
            l.append(s[i])
            i+=1
    else:
        l.append(s[i])
        i+=1
n=len(l)
ca=0
count=0
for i in range(n):
    if l[i]=='A':
        ca+=1
    elif l[i]=='D':
        count+=ca
    else:
        ca=0
print(count)

Measured memory_bytes: 5096
#include<iostream>
using namespace std;
typedef long long ll;

int main() {
    ll N, M;
    cin >> N >> M;
    if (2 * N >= M) {
        cout << M / 2 << endl;
    }
    else {
        cout << N + (M - 2 * N) / 4 << endl;
    }
    return 0;
}

Measured memory_bytes: 256