akhauriyash/Code-Regression huggingface dataset:
fun main(arg: Array<String>) {
    val N = nextInt()
    val TA = Array(N) { listOfLong() }
    var T = 1L
    var A = 1L
    for ((t, a) in TA) {
        val d = Math.max((T - 1) / t + 1, (A - 1) / a+ 1)
        T = t * d
        A = a * d
//System.err.println("T:$T A:$A")
    }
    val ans = T + A
    println(ans)
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }


Measured memory_bytes: 37880
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	log.SetFlags(log.Lshortfile)
	N := nextInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = nextInt()
	}
	a := make([]int, N)
	a[0] = A[0]
	for i := 1; i < N; i++ {
		a[i] = A[i] + a[i-1]
	}
	asum := sum(A)
	long := asum / 2
	var border int
	for i := 0; i < N; i++ {
		log.Println(i, a[i])
		if a[i] == long {
			fmt.Println("0")
			return
		}
		if a[i] > long {
			border = i
			break
		}
	}
	// log.Println(long, border)
	// log.Println(a)
	// log.Println(A[border], a[border], a[border])
	// log.Println(A[border], a[border-1], a[len(a)-1]-a[border+1])
	// log.Println(a[border-1], sum(A[border+1:]))
	// log.Println(A[border-1], sum(A[border+1:]))
	fmt.Println(abs(A[border] - abs(a[border-1]-sum(A[border+1:]))))
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type pair struct {
	a, b int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 8856
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
#include <iomanip>
#define M_PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
int now = 0;

const int MAX = 200000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
struct edge {
	int t;
	ll cost;
	edge(int _t, ll _cost) : t(_t)
		, cost(_cost) {
	}
};
bool isPrime(int n) {

	if (n == 1) return false;
	for (ll i = 2; i * i <= n; i++)
	{
		if (n % i == 0) return false;
	}
	return true;
}
int anyDigitSum(int n) {
	int res = 0;
	while (n > 0)
	{
		res += n % 10;
		n /= 10;
	}
	return res;
}
ll f(double n) {

	n *= n;
	n += 4.0;
	return n / 8.0;
}
void Solve() {
	string s;
	cin >> s;
	int c[] = { 0,0,0,0 };
	for (size_t i = 0; i < s.size(); i++)
	{
		if (s[i] == 'N') c[0] = 1;
		if (s[i] == 'S') c[1] = 1;
		if (s[i] == 'E') c[2] = 1;
		if (s[i] == 'W') c[3] = 1;
	}

	if ((c[0] ^ c[1]) || (c[2] ^ c[3])) {
		cout << "No" << endl;
	}
	else cout << "Yes" << endl;
}
int main() {
	Solve();
	return 0;
}



Measured memory_bytes: 256
#!ruby -n
n, s, w, e = false
$_.each_char do |c|
  if c == "N"
    n = true
  elsif c == "S"
    s = true
  elsif c == "W"
    w = true
  elsif c == "E"
    e = true
  end
end

xt = (w && e) || (!w && !e)
yt = (n && s) || (!n && !s)

if xt && yt
  puts "Yes"
else
  puts "No"
end


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

void insertionSort(vector<int> A, int N) {
    for (int i = 0; i < N; i++) {
        int v = A[i];
        int j = i - 1;
        while (0 <= j && v < A[j]) {
            A[j + 1] = A[j];
            j--;
            A[j + 1] = v;
        }
        for (int j = 0; j < N; j++) {
            cout << A[j];
            if (j != N - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
}

int main() {

    int n;
    cin >> n;

    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    insertionSort(A, n);

    return 0;

}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=300010;
char str[maxn];
int _right[maxn],_left[maxn];
int main(){
	int n;
	scanf("%d%s",&n,str+1);
	for(int i=1;i<=n;i++){
		_left[i]=_left[i-1];
		_right[i]=_right[i-1];
		if(str[i]=='E') _right[i]++;
		else _left[i]++;
	}
	int ans=n+1;
	for(int i=1;i<=n;i++)
		ans=min(ans,_left[i-1]+_right[n]-_right[i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2944
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *


N = INT()
A = LIST()
Q = INT()

ans = sum(A)
dic = defaultdict(int)

for x in A:
	dic[x] += 1

for _ in range(Q):
	B, C = MAP()
	ans += (C-B)*dic[B]
	print(ans)
	dic[C] += dic[B]
	dic[B] = 0

Measured memory_bytes: 24144
n = int(input())
v = list(map(float, input().split()))

v.sort()
while(True):
    if len(v) == 1:
        break
    else:
        x = v.pop(0)
        y = v.pop(0)
        v.append((x+y)/2)
        v.sort()

print(v[0])


Measured memory_bytes: 2940
#[allow(dead_code)]
fn main() {
    let (n, m) = i::u2();
    let a = i::uv(m);

    let a_set: HashSet<usize> = a.iter().cloned().collect();

    let mut dp = vec![1usize];
    if !a_set.contains(&1) {
        dp.push(1);
    } else {
        dp.push(0);
    }
    for i in 2..(n + 1) {
        if a_set.contains(&i) {
            dp.push(0);
            continue;
        }
        let t = (dp[i - 1] + dp[i - 2]) % 1_000_000_007;
        dp.push(t);
    }
    println!("{}", dp[n]);
    // dbg!(dp);
}

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::num::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(dead_code)]
mod i {
    use super::*;

    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn u2() -> (usize, usize) {
        (read(), read())
    }

    pub fn u3() -> (usize, usize, usize) {
        (read(), read(), read())
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }

    pub fn iv2(n: usize) -> Vec<(i64, i64)> {
        (0..n).map(|_| iv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn uv2(n: usize) -> Vec<(usize, usize)> {
        (0..n).map(|_| uv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv3(n: usize) -> Vec<(usize, usize, usize)> {
        (0..n).map(|_| uv(3)).map(|a| (a[0], a[1], a[2])).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}


Measured memory_bytes: 8444
//============================================================================
// Name        : AOL.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>
using namespace std;



int main(){


	int n;
	int d=0;
	cin>>n;
	int flag1,flag2;

	string  s1,s2;
	cin>>s1;
	int m1=s1.size();

	for(int i=0; i<n; i++){
		cin>>s2;
		int m2=s2.size();
		flag2=0;
		for(int j=0; j<m2-m1+1; j++){
			if(s2[j]==s1[0]){
				for(int k=0; k<50; k++){
					if(m2-j>(k+1)*(m1-1)){
						flag1=1;
						for(int l=1; l<m1; l++){
							if(s2[j+l*(k+1)]!=s1[l])flag1=0;
						}
						if(flag1==1)flag2=1;
					}
				}
			}
		}
		if(flag2==1)d+=1;
	}
	cout<<d<<endl;
	return 0;

}

Measured memory_bytes: 3136
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
if n%2==0:
    k = k0 = n//2
    for i in range(k0):
        x = s[k0]
        if not (s[k0+i]==s[k0-1-i]==x):
            break
        k += 1
else:
    k0 = n//2
    k = k0+1
    x = s[k0]
    for i in range(1,k0+1):
        if not (s[k0+i]==s[k0-i]==x):
            break
        k += 1
print(k)


Measured memory_bytes: 39408
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <tuple>
#include <functional>
#include <cstring>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i <= n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i <= n; i++)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<std::vector<bool> > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

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

using namespace std;

int main(void)
{
    ll n, k, r, s, p;
    cin >> n >> k >> r >> s >> p;
    vector<char> takahashi = {'r', 's', 'p'};
    map<char, ll> point;

    point['r'] = p;
    point['s'] = r;
    point['p'] = s;

    string t;
    cin >> t;

    ll sum = 0;

    irep(i, k) { 

        v_char game;
        for(ll j = i; j < n; j+=k) {
            game.push_back(t[j]);
        }
        //for(auto g : game) { cout << g ; } cout << endl;

        v2_ll dp(game.size(), v_ll(2, -1));

        dp[0][0] = point[game[0]];
        dp[0][1] = 0;

        for(ll j = 0; j < game.size()-1; j++) {

            if(game[j+1] != game[j]) {
                dp[j+1][0] = max(dp[j+1][0], dp[j][0] + point[game[j+1]]);
                dp[j+1][0] = max(dp[j+1][0], dp[j][1] + point[game[j+1]]);
                dp[j+1][1] = max(dp[j+1][1], dp[j][0]);
                dp[j+1][1] = max(dp[j+1][1], dp[j][1]);
            } else {
                dp[j+1][0] = max(dp[j+1][0], dp[j][1] + point[game[j+1]]);
                dp[j+1][1] = max(dp[j+1][1], dp[j][0]);
            }
        }
        sum += max(dp[game.size()-1][0], dp[game.size()-1][1]);
        //cout << sum << endl;
    }
    cout << sum;
    return 0;
}
/** atcodr **/


Measured memory_bytes: 5888
#include<stdio.h>
int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a==b&&a!=c) printf("Yes");
    else if(a==c&&a!=b) printf("Yes");
    else if(b==c&&a!=b) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
<?php

class Inputs
{
    public static function dd()
    {
        fscanf(STDIN, '%d %d', $a, $b);
        return [$a, $b];
    }
}

//最大公約数
function gcd($m, $n)
{
    if ($n > $m) {
        list($m, $n) = array($n, $m);
    }

    while ($n !== 0) {
        $tmp_n = $n;
        $n = $m % $n;
        $m = $tmp_n;
    }
    return $m;
}

//最小公倍数
function lcm($m, $n)
{
    return $m * $n / gcd($m, $n);
}

list($a, $b) = Inputs::dd();

echo lcm($a, $b) . PHP_EOL;


Measured memory_bytes: 4604
def main():
    n = int(input())
    a=list(map(int,input().split()))
    r = []
    r.append(sum([a[i] for i in range(n) if i % 2 == 0])-sum([a[i] for i in range(n) if i % 2 ==1]))

    for i in range(1,n):
        r.append(a[i-1]*2-r[i-1])

    print(" ".join(list(map(str,r))))

main()

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

string s[100];
int p[100];
int n,m;
int c(string b){
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<8;j++){
			if(s[i][j]!='*'&&b[j]!=s[i][j])break;
		}
		if(j==8)return p[i];
	}
	return 0;
}
int main(void){
	int sum;
	string b;
	while(cin>>n>>m,n){
		sum=0;
		for(int i=0;i<n;i++)cin>>s[i]>>p[i];
		for(int i=0;i<m;i++){
			cin>>b;
			sum+=c(b);
		}
		cout<<sum<<endl;
	}
	return 0;
}

Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int A[50001];
bool OK = 1;
ll ans = 1;
const ll mod = 1e9 + 7;
const int ma = 31;

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


	int N = getint();
	if (N & 1) {
		rep(i, N) {
			int a = getint();
			if (a & 1) {
				printf("0");
				return 0;
			}
			A[a / 2]++;
		}
		if (A[0] != 1) OK = 0;
		rep1(i, N / 2) {
			if (A[i] != 2) OK = 0;
			ans = ans << 1;
			if (!(i & ma)) ans %= mod;
		}
		if (OK) printf("%lld", ans % mod);
		else printf("0");
	}
	else {
		rep(i, N) {
			int a = getint();
			if (!(a & 1)) {
				printf("0");
				return 0;
			}
			A[a / 2]++;
		}
		rep(i, N / 2) {
			if (A[i] != 2) OK = 0;
			ans = ans << 1;
			if (!(i & ma)) ans %= mod;
		}
		if (OK) printf("%lld", ans % mod);
		else printf("0");
	}

	Would you please return 0;
}

Measured memory_bytes: 512
def main1(A, B):
    res = 0
    if A == B:
        res = A * 2
    else:
        res = (max(A,B) * 2) - 1
    print(res)

A, B = map(int, input().split())
main1(A, B)

#main1(5,3)#9
#main1(3,4)#7
#main1(6,6)#12


Measured memory_bytes: 2940
def examC():
    import bisect
    N, K = LI()
    D = list(map(str,input().split()))
    ansC = []
    for i in range(100001):
        cur = str(i)
        k = 1
        for s in cur:
            if s in D:
                k = 0
                break
        if k==1:
            ansC.append(i)
#    print(ansC)
    k = bisect.bisect_left(ansC, N)
    ans = ansC[k]
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

examC()

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

int main() {
  int N;
  cin >> N;
  vector<long long> data(N + 1);
  data.at(0) = 2;
  data.at(1) = 1;
  for(int i = 2; i <= N; i++) {
    data[i] = data[i - 1] + data[i - 2];
  }
  printf("%ld\n", data.at(N) );
}

Measured memory_bytes: 3692
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;
int score(vector<int> a, vector<int> b) {
    int n = a.size();
    vector<bool> used(n);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        vector<int> c;
        int cnt = 0;
        bool ok = false;
        for(int j = 0; j < n; j++) if(!used[j]) {
            if(b[j] == a[i]) {
                used[j] = true;
                ans += cnt;
                ok = true;
                break;
            }
            cnt ++;
        }
        if(!ok) return INT_MAX;
    }
    return ans;
}

int main(){
    int n, m;
    while(cin >> n >> m) {
        vector<int> a(n);
        REP(i, n) cin >> a[i];
        vector<int> b0, b1;
        REP(i, m) {
            int t;
            cin >> t;
            REP(j, t) {
                b0.push_back((i&1));
                b1.push_back((i&1)^1);
            }
        }
        cout << min(score(a, b0), score(a, b1)) << endl;
    }
    return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
int main()
{
  
  int r,c;
  cin>>r>>c;
  int arr[r+1][c+1],dp[r+1][c+1];
  for(int i=1;i<=r;i++)
  for(int j=1;j<=c;j++)
  {
    char k;
    cin>>k;
    if(k=='#')
      arr[i][j]=0;
    else
      arr[i][j]=1;
    
    dp[i][j]=0;
  }
  for(int i=0;i<=r;i++)
    dp[i][0]=0;
  for(int j=0;j<=c;j++)
    dp[0][j]=0;
  dp[1][1]=1;
  
  int mod=pow(10,9)+7;
  for(int x=1;x<=r;x++)
  {
    
    for(int y=1;y<=c;y++)
    {
      if(arr[x][y]==1)
      {
        dp[x][y]=(dp[x][y]+dp[x-1][y]+dp[x][y-1])%mod;         
      }
    }
  }
  cout<<dp[r][c]<<endl;
 
  return 0;
}

Measured memory_bytes: 8064
/**

Base Case:
For length 1 , answer is the value of that element

solve(l,r) = max(move1,move2)

where , move1 = a[l] - solve(l-1,r) // take l . solve(l-1,r) is opponent's score
        move2 = a[r] - solve(l,r-1) // take r . solve(l,r-1) is opponent's score

**/

/** Which of the favors of your Lord will you deny ? **/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**

PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 3e3+7;
const LL LINF = 1e17;

template <class T>
string to_str(T x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}

LL dp[nmax][nmax];

LL solve(int l,int r,const vector<LL>&v)
{
    LL &ret = dp[l][r];

    if(ret!=-1) return ret;

    if(l==r) return ret = v[l];

    ret = max(v[l]-solve(l+1,r,v),v[r]-solve(l,r-1,v));
    return ret;
}

int main()
{
    optimizeIO();

    int n;
    cin>>n;

    vector<LL>v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];

    memset(dp,-1,sizeof dp);
    cout<<solve(0,n-1,v)<<endl;

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




Measured memory_bytes: 74572
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        String a = sc.next();
        String b = sc.next();
		String ans ="";
		
		if(a.length()>b.length()){
		    System.out.println("GREATER");
		    return;
		}else if(a.length()<b.length()){
		    System.out.println("LESS");
		    return;
		}else{
		    for(int i=0; i<a.length(); i++){
		        int an = Character.getNumericValue(a.charAt(i));
		        int bn = Character.getNumericValue(b.charAt(i));
		        if(an>bn){
		            System.out.println("GREATER");
		            return;
		        }else if(an<bn){
		            System.out.println("LESS");
		            return;
		        }
		    }
		}

		
		System.out.println("EQUAL");
    }
}


Measured memory_bytes: 35400
/*input

*/
#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 

using namespace std;
long long mod=1e9+7;
long long INF=1e7;
typedef long long int lld;
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define scd(a) scanf("%d",&a)
#define scd2(a,b) scanf("%d%d",&a,&b)
#define scd3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scf(a) scanf("%lf",&a)
#define scf2(a,b) scanf("%lf%lf",&a,&b)
#define scf3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define all(c) c.begin(), c.end()
#define sz(a) ((int)a.size())
#define Error(x) cout<< #x << " = " << (x) <<endl;
#define Error2(a,b) cout<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define Error3(a,b,c) cout<<"("<<#a<<" , "<<#b<<" , "<<#c<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<")\n";
#define Error4(a,b,c,d) cout<<"("<<#a<<" , "<<#b<<" , "<<#c<<" , "<<#d<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<" , "<<(d)<<")\n";
#define errop(a) cout<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define popcount __builtin_popcountll
typedef pair<lld,lld> PA;
#define lim 200010
#define lim2 4023
#define qqqqqq 210
// inline lld sqr(lld x) { return x * x; }
// unordered_map<lld,lld>::iterator it;
// std::ios::sync_with_stdio(false);
// priority_queue<PA> Q;
// lld dp[1<<18];

lld B[lim],A[lim],C[lim];
// PA P[lim],Q[lim];
lld n,m,p,q;
// string S[lim],R[lim];
map<PA,lld> M;
vector<lld> V[lim];
// unordered_map<lld,lld> Ind;


lld powP(lld a,lld b){
    if(b==0) return 1%mod;
    lld k;
    k=powP(a,b/2);
    k=k*k%mod;
    if(b%2==0) return k;
    else return a*k%mod;
}

bool bitSet(lld n,lld i){
    if((n&(1LL<<i))!=0) return true;
    else return false;
}

lld solve(lld n, lld x){
    lld sum=0,t=x;
    while(n/t>0){
        sum+=n/t;
        t*=x;
    }
    return sum+1;
}

int main(){
    lld T,i,p,j,l,r,b,k,c,a,d,w,x,y,v,z,t,curr,prev,sum,ans,pos,val,countA,secondMin,indicator;
    sc(n);
    rep(i,2,n) A[i]=1;
    ans=1;
    rep(i,2,n){
        if(A[i]==1){
            for(lld j=i+i;j<=n;j+=i) A[j]=0;
            // Error2(i,solve(n,i));
            ans=ans*solve(n,i)%mod;
        }
    }
    prL(ans);
    return 0;
}

Measured memory_bytes: 5500
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int T, card[16];

bool is_same_number(int a, int b, int c) {
	if(a == b && b == c) return true;
	else return false;
}

bool is_sequence(int a, int b, int c) {
	if(a+2 == c && b+1 == c) return true;
	else return false;
}

bool is_good_set(int a, int b, int c) {
	return is_same_number(a, b, c) || is_sequence(a, b, c);
}

bool is_all_good_set() {
	if(is_good_set(card[0], card[1], card[2])) {
		if(is_good_set(card[3], card[4], card[5])) {
			if(is_good_set(card[6], card[7], card[8])) {
				return true;
			}
			return false;
		}
		return false;
	}
	return false;
}

int win() {
	sort(card,card+9);
	do{
		if(is_all_good_set()) return 1; 
	}while(next_permutation(card, card+9));
	return 0;
}

int main() {
	cin >> T;
	for(int t = 0; t < T; t++) {
		for(int i = 0; i < 9; i++) {
			cin >> card[i];
		}
		string color;
		for(int i = 0; i < 9; i++) {
			cin >> color;
			if(color == "G") card[i] += 10;
			else if(color == "B") card[i] += 20;
		}
		cout << win() << endl;
	}
	return 0;
}

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


/// File input & output /////
#define fRead(x)        freopen("x.txt","r",stdin)
#define fWrite(x)       freopen ("x.txt","w",stdout)

#define mt              make_tuple
#define ld              long double
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define INF             2e16
#define PI              acos(-1.0)
#define mp              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())


#define FASTIO        ios_base::sync_with_stdio(0);cin.tie(nullptr);




///..................Sort by second element in a pair in decending order............. ///
bool SortbySecDesc(const pair<long long,long long > &a, const pair<long long,long long > &b)
{
    return a.second>b.second;
}

///.........................first element of pair in descending order..........................//////
bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}



///.............................................................TEMPLATE................................................./////

int main()
{
    FASTIO;

    ll n;

    cin >> n;

    ll cnt[n+1]={0};


    for(int i=0; i<n-1; i++)
    {
        ll a;

        cin >> a;

        cnt[a]++;
    }

    for(int i=1; i<=n; i++)
       cout << cnt[i] <<endl;





    return 0;
}



Measured memory_bytes: 5148
// ABC178C - 

#include <bits/stdc++.h>
using namespace std;

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

#define MOD 1000000007 // MOD must be prime number.

ll powerMOD(ll n, ll p) {
	if (p == 0) {
		return 1;
	}
	if (p % 2 == 0) {
		ll t = powerMOD(n, p / 2);
		return t * t % MOD;
	}
	return n * powerMOD(n, p - 1)% MOD;
}

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

	if (N == 1) {
		cout << 0 << endl;
		return 0;
	}

	ll tmp1, tmp2, tmp3, tmp4, ans;

	tmp1 = powerMOD(10, N);
	tmp2 = powerMOD(9, N);
	tmp3 = powerMOD(8, N);
	tmp4 = (MOD + 2*tmp2 - tmp3)% MOD;

	ans = (MOD + tmp1 - tmp4)% MOD;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1000000007;
const ll INF = 9223372036854775807;
#define Sort(a) sort(a.begin(), a.end())
#define Bsort(a) sort(a.begin(), a.end(), greater<ll>())
#define Pi acos(-1)

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll a, b, c;
  cin >> a >> b >> c;
  if (a+b-c < 0 && (a+b-c)*(a+b-c) > 4*a*b) {
    cout << "Yes" << '\n';
  }
  else {
    cout << "No" << '\n';
  }
}

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

int cnt[101010],cnt2[101010];
map<int,int> mp;

int main(){
  int N,M; cin>>N>>M;
  rep(i,N){
    int X; cin>>X;
    int Y=X%M;
    if(mp[X]>=1&&Y!=0){
      cnt[Y]--;
      cnt2[Y]+=2;
      mp[X]--;
    }else{
      cnt[Y]++;
      mp[X]++;
    }
  }

  int ans=cnt[0]/2+(M%2==0?(cnt[M/2]+cnt2[M/2])/2:0);
  for(int i=1;i<=(M-1)/2;i++){
    int sum=cnt[i]+cnt2[i], sum2=cnt[M-i]+cnt2[M-i];
    if(sum<sum2){
      swap(sum,sum2);
      swap(cnt[i],cnt[M-i]);
      swap(cnt2[i],cnt2[M-i]);
    }
    cnt2[i]-=max(sum2-cnt[i],0);
    ans+=sum2+max(0,cnt2[i]/2);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main()
{
    long long n, m;
    std::cin >> n >> m;

    std::vector<std::pair<long long, long long>> cost_and_num(n);

    for (int i = 0; i < n; i++) {
        long long a, b;
        std::cin >> a >> b;

        cost_and_num[i] = std::make_pair(a, b);
    }

    std::sort(cost_and_num.begin(), cost_and_num.end());

    long long cost = 0;
    int num = 0;
    for (int i = 0; i < m; i++) {
        if (num + cost_and_num[i].second <= m) {
            cost += cost_and_num[i].first * cost_and_num[i].second;
            num += cost_and_num[i].second;
        } else {
            cost += cost_and_num[i].first * (m - num);
            break;
        }
    }

    std::cout << cost << std::endl;
}


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

#define iota(i,n,b,s) for(int i=int(b);i!=int((b)+(s)*(n));i+=(s))
#define range(i,n,m) iota(i,(((n)>(m))?((n)-(m)):((m)-(n))),(n),((n)>(m)?-1:1))
#define rep(i,n) iota(i,(n),0,1)
#define loop for(;;)

#define INF (1e9)
#define EPS (1e-9)
#define cons(a,b) (make_pair(a,b))
#define car(a) (a.first)
#define cdr(a) (a.second)
#define cadr(a) (car(cdr(a)))
#define cddr(a) (cdr(cdr(a)))
#define all(a) a.begin(), a.end()
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;

typedef long long Integer;
typedef double Real;
typedef vector<int> vi;
typedef vector<string> vs;
typedef map<string,int> Dictionary;

template<class S, class T>
ostream& operator<<(ostream& os, pair<S,T> p) {
  os << '(' << car(p) << ", " << cdr(p) << ')';
  return os;
}

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

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

inline void debug(int*hand) {
  rep (i, 9) {
    cout << "[" << (i+1) << "] * " << hand[i] << ", ";
  } cout << endl;
}

bool body(int*hand) {
  {
    bool ac = true;
    rep (i, 9) if (hand[i]) ac = false;
    if (ac) return true;
  }
  rep (i, 9 - 2) {
    if (hand[i] && hand[i+1] && hand[i+2]) {
      hand[i]--;
      hand[i+1]--;
      hand[i+2]--;
      bool b = body(hand);
      hand[i]++;
      hand[i+1]++;
      hand[i+2]++;
      if (b) return true;
    }
  }
  rep (i, 9) {
    if (hand[i] >= 3) {
      hand[i] -= 3;
      bool b = body(hand);
      hand[i] += 3;
      if (b) return true;
    }
  }
  return false;
}

bool solve(int*hand) {
  rep (i, 9) {
    if (hand[i] >= 5) return false;
  }

  rep (head, 9) {
    if (hand[head] < 2) continue;
    hand[head] -= 2;
    bool b = body(hand);
    hand[head] += 2;
    if (b) return true;
  }
  return false;
}

int main() {

  string s;
  loop {
    cin >> s; if (!cin) break;
    int hand[9] = {0};
    rep (i, s.size()) {
      hand[s[i] - '1']++;
    }

    vi ans;
    rep (i, 9) {
      hand[i]++;
      if (solve(hand)) ans.push_back(i + 1);
      hand[i]--;
    }

    if (ans.size() == 0) {
      cout << 0 << endl;
    } else {
      cout << ans << endl;
    }
  }

  return 0;
}

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

using namespace std;

using int64 = long long;
const int64 LINF = 1LL << 60;
const int INF = 1 << 26;

int V, E, K;
int64 g[26][150][150];

int main() {
  fill_n(**g, 26 * 150 * 150, -LINF);

  cin >> V >> E >> K;
  for(int i = 0; i < V; i++) {
    g[0][i][i] = 0;
  }
  for(int i = 0; i < E; i++) {
    int a, b;
    int64 c;
    cin >> a >> b >> c;
    g[0][a][b] = max(g[0][a][b], c);
  }

  for(int i = 0; i < 25; i++) {
    for(int j = 0; j < V; j++) {
      for(int k = 0; k < V; k++) {
        for(int l = 0; l < V; l++) {
          g[i + 1][k][l] = max(g[i + 1][k][l], g[i][k][j] + g[i][j][l]);
        }
      }
    }
  }


  auto check = [&](int bit) {
    vector< int64 > dp(V);
    for(int k = 30; k >= 0; k--) {
      if((bit >> k) & 1) {
        vector< int64 > dp2(V);
        for(int i = 0; i < V; i++) {
          for(int j = 0; j < V; j++) {
            dp2[j] = max(dp2[j], dp[i] + g[k][i][j]);
          }
        }
        dp.swap(dp2);
      }
    }
    return *max_element(begin(dp), end(dp)) >= K;
  };

  int ok = INF, ng = 0;
  while(ok - ng > 1) {
    int mid = (ok + ng) / 2;
    if(check(mid)) ok = mid;
    else ng = mid;
  }

  if(ok == INF) {
    cout << -1 << endl;
  } else {
    cout << ok << endl;

    if(ok <= 100) {
      int64 dp[101][150] = {{}}, pv[101][150];
      for(int i = 0; i < ok; i++) {
        for(int j = 0; j < V; j++) {
          for(int k = 0; k < V; k++) {
            if(dp[i][j] + g[0][j][k] > dp[i + 1][k]) {
              dp[i + 1][k] = dp[i][j] + g[0][j][k];
              pv[i + 1][k] = j;
            }
          }
        }
      }
      int high = 0;
      for(int i = 0; i < V; i++) {
        if(dp[ok][i] >= dp[ok][high]) high = i;
      }
      vector< int > route;
      for(int i = ok; i >= 0; i--) {
        route.push_back(high);
        high = pv[i][high];
      }
      reverse(begin(route), end(route));
      for(int i = 0; i < route.size(); i++) {
        if(i) cout << " ";
        cout << route[i];
      }
      cout << endl;
    }
  }
}




Measured memory_bytes: 7980
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

int main() {
    vector<int> v(3);
    cin >> v[0] >> v[1] >> v[2];
    sort(v.begin(), v.end());
    cout << v[0] << " " << v[1] << " " << v[2] << endl;
}


Measured memory_bytes: 3168
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

#define LIMIT 1000000000000
char ss[10];
int main(){
	ll s=10;
	while(s<LIMIT){
		printf("? %lld\n",s);
		fflush(0);
		scanf("%s",ss);
		if(*ss=='N')break;
		s*=10;
	}
	if(s==1000000000000){
		//答えは10べき
		s=2;
		while(s<LIMIT){
			printf("? %lld\n",s);
			fflush(0);
			scanf("%s",ss);
			if(*ss=='Y')break;
			s*=10;
		}
		printf("! %lld\n",s/2);
		fflush(0);
	}else{
		ll l=s/10,r=s-1;//(l,r]
		while(r-l>1){
			ll m=(l+r)/2;
			printf("? %lld0\n",m);
			fflush(0);
			scanf("%s",ss);
			if(*ss=='N')l=m;
			else r=m;
		}
		printf("! %lld\n",r);
		fflush(0);
	}
}

Measured memory_bytes: 504
public class Main {


  private static void solve() {
    int n = ni();
    double ret = 0;
    for (int i = 0; i < n; i ++) {
      double x = nd();
      ret += next().equals("JPY") ? x : (x * 380000);
    }
    System.out.printf("%.12f\n", ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


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

                            typedef long long ll;
                            typedef  double ld;
                            #define rep(i,a,n) for(ll i=(a); i<(n); i++)
                            #define per(i,a,n) for(ll i=(n-1); i>=(a); i--)
                            #define F first
                            #define S second
                            #define maxx(a,b) a=max(a,b)
                            #define minn(a,b) a=min(a,b)
                            #define db(x) cerr<<#x<<" = "<<x<<endl
                            #define N 1111111
                            #define mod 1000000007
                            #define rt return
                            #define inf 12345678908761

                            using namespace std;

                            ll a[3111][3111];

                            int main(){

                                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

                                //freopen("Ulug'bek","r",stdin);
                                //freopen("Abdimanabov","w",stdout);

                                int n,m; cin>>n>>m;

                                a[1][1]=1;

                                rep(i,1,n+1)
                                rep(j,1,m+1)
                                {
                                    char c; cin>>c;
                                    if(c=='#')continue;
                                    if(i+j>2)a[i][j]=(a[i-1][j]+a[i][j-1])%mod;
                                }

                                cout<<a[n][m];

                            rt 0;
                            }



















Measured memory_bytes: 23808
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 1e5;
const int MOD = 1e9 + 7;

int n;
char s1[60], s2[60];
LL dp[60];

int main()
{
	while(scanf("%d", &n) != EOF)
	{
		scanf("%s", s1 + 1);
		scanf("%s", s2 + 1);
		dp[0] = 1;
		if(s1[1] == s1[2]) dp[1] = 6;
		else dp[1] = 3;
		for(int i = 2; i <= n; i++) {
			if(s1[i] == s1[i + 1]) {
				if(s1[i - 1] == s2[i - 1]) {
					dp[i] = dp[i - 1] * 2 % MOD;
				}
				else {
					dp[i] = dp[i - 1] * 3 % MOD;
				}
				dp[i + 1] = dp[i];
				i++;
			}
			else if(s1[i] == s2[i]) {
				if(s1[i - 1] == s2[i -1]) {
					dp[i] = dp[i - 1] * 2 % MOD;
				}
				else if(s1[i - 1] != s2[i - 1]) {
					dp[i] = dp[i - 1] % MOD;
				}
			}
			else dp[i] = dp[i - 1];
		}
		printf("%lld\n", dp[n]);
	}
	return 0;
}

Measured memory_bytes: 128
i = input()
j = i.split(" ")

a = int(j[0])
b = int(j[1])
c = int(j[2])
k = int(j[3])

s = 0

if a < k :
    s += a
    
    if b < k-a :
        s -= k-a-b
        print(s)
        
    elif b == k-a :
        print(s)
    else :
        print(s)
    
elif a == k :
    s += a
    print(s)
    
else :    
    s += k
    print(s)
    
    
    
    
    
    

Measured memory_bytes: 9200
#include <iostream>
using namespace std;
int main(){
  int n,a,b;cin>>n>>a>>b;
  string s;cin>>s;
  int honsen = 0;
  int honsenkaigai = 0;
  for(int i = 0; n > i;i++){
    if(s[i] == 'c')cout << "No" << endl;
    else if(s[i] == 'b'){
      if(honsen < a+b && honsenkaigai < b){
        cout << "Yes" << endl;
        honsen++;honsenkaigai++;
      }else cout << "No" << endl;
    } else {
      if(honsen < a+b){
        cout << "Yes" << endl;
        honsen++;
      }else{
        cout << "No" << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

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

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;
}

#define rep(i, e) for(int i = 0; i < e; i++)
#define repp(i, s, e) for(int i = s; i < e; i++)
#define MAX_N 100
#define Card_Max 36
#define p(a) printf("%d\n", a);
#define ll long long
#define ull unsigned long long
#define MAX 1e9
#define NIL -1
typedef pair<ll, ll> P;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    ll N,K,sum = 0;

    cin>>N>>K;
    vector<ll> H(N, 0);
    rep(i, N) cin >> H[i];
    sort(H.begin(), H.end());
    for(int i=0; i<N-K; i++){
        sum += H[i];
    }
    cout << sum << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
const int INF = 1e6;
using namespace std;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
int main(){
    while(true){
        int n,x;
        cin >> n >> x;
        if(n == 0 && x == 0) break;
        int ans = 0;
        rep1(i,n){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;k++){
                    if(i+j+k == x){
                        ans++;
                    }
                }
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
  int R, G, B, N;
  cin >> R >> G >> B >> N;
  int cnt = 0;
  for(int i = 0; i < N + 1; i++){
    for(int j = 0; j < N + 1; j++){
      if(((N - (R*i + G*j)) % B) == 0 && (N - (R*i + G*j) >= 0))
        cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  int a1,b1,c1,a2,b2,c2,p,q,r;
  cin>>n;
  cin>>a1>>b1>>c1;
  for(int i=1; i<n; i++){
    cin>>a2>>b2>>c2;
    p=a1;
    q=b1;
    r=c1;
    a1=a2+max(q,r);
    b1=b2+max(p,r);
    c1=c2+max(p,q);
  }
  cout<<max(a1,max(b1,c1))<<"\n";
  return 0;
} 


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int B[MAX], C[MAX];

void countingSort(int A[], int B[], int k, int n)
{
    int i, j;

    for (i = 0; i <= k; i++)
        C[i] = 0;
    for (j = 1; j <= n; j++)
        C[A[j]]++;
    for (i = 1; i <= k; i++)
        C[i] = C[i] + C[i - 1];
    for (j = n; j >= 1; 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");
}

int main()
{
    int A[MAX];
    int n, i, j, k = 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &A[i + 1]);
        if (k < A[i])
            k = A[i];
    }
    countingSort(A, B, k, n);
    return 0;
}



Measured memory_bytes: 17380
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

a = [1]
p = [1]
for _ in range(51):
    a.append(3 + 2*a[-1])
    p.append(1 + 2*p[-1])

def burger(level: int, x: int):
    if level == 0:
        if x <= 0:
            return 0
        else:
            return 1
    
    if x == 1:
        return 0
    
    elif 1 < x <= 1+a[level-1]:
        return burger(level-1, x-1)
    
    elif x == 2+a[level-1]:
        return p[level-1] + 1
    
    elif 2+a[level-1] < x <= 2+2*a[level-1]:
        return p[level-1] + 1 + burger(level-1, x-1-a[level-1]-1)
    
    elif x == 3+2*a[level-1]:
        return 2*p[level-1] + 1
    
n,x = li()    
print(burger(n,x))
    

Measured memory_bytes: 3064
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    L = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            L[j] += 1
    res = 0
    for i in range(1, n + 1):
        res += i * L[i]
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 151740
from math import cos, sqrt
import math

A, B, H, M = map(int, input().split())
Md = M * 6
Hd = (H * 30) + ((M/60) * 30)
Cd = (Hd - Md) * (math.pi/180)
X = sqrt(A**2 + B**2 - (2*B*A * cos(Cd)))
print(X)

Measured memory_bytes: 9440