akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
readline = stdin.readline


class vector:
    def cross(a, b):
        return a.real * b.imag - a.imag * b.real

    def dot(a, b):
        return a.real * b.real + a.imag * b.imag

    def ccw(a, b, c):
        b -= a
        c -= a
        if vector.cross(b, c) > 0:
            return 1 
        if vector.cross(b, c) < 0:
            return 2
        if vector.dot(b, c) < 0:
            return 3
        if abs(b) < abs(c):
            return 4
        return 5

    def polygon(p):
        if len(p) < 3:
            return 0
        return 0.5 * sum(vector.cross(p[i - 1], p[i]) for i in range(len(p)))

    def intersection(p1, p2, p3, p4):
        a1 = p4 - p2
        b1 = p2 - p3
        b2 = p1 - p2
        s1 = vector.cross(a1, b2) / 2
        s2 = vector.cross(a1, b1) / 2
        if s1 + s2 == 0:
            return 0
        c1 = p1 + (p3 - p1) * s1 / (s1 + s2)
        return c1


def main():
    n = int(readline())
    p = [map(float, readline().split()) for _ in range(n)]
    p = [x + y * 1j for x, y in p]
    q = int(readline())

    for _ in range(q):
        p1x, p1y, p2x, p2y = map(float, readline().split())
        p1, p2 = p1x + p1y * 1j, p2x + p2y * 1j

        pre_tmp = vector.ccw(p[-1], p1, p2)
        left = []
        for i in range(len(p)):
            tmp = vector.ccw(p[i], p1, p2)
            if pre_tmp != tmp and all(i in (1, 2) for i in (pre_tmp, tmp)):
                c1 = vector.intersection(p1, p[i - 1], p2, p[i])
                left.append(c1)
            if tmp != 2:
                left.append(p[i])

            pre_tmp = tmp
        print('{:.6f}'.format(vector.polygon(left)))
main()

Measured memory_bytes: 6852
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int main() {
    cin >> n;
    ll ans = n - 1;
    for (int i = 2; i < n; ++i) {
        ans += n % i? n / i : n / i - 1;
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 3772
#include <stdio.h>

int main(void){
    int k;
    int a;
    int b;

    int As,Bs,Aa,Ba;

    scanf("%d",&k);
    scanf("%d %d",&a,&b);

    As=a/k;
    Bs=b/k;

    Aa=a%k;
    Ba=b%k;



    if(a==b&&a>=k){
        printf("OK");
    }
    else if(Aa==0 || Ba==0){
        printf("OK");
    }
    else if(As==Bs){
        printf("NG");
    }
    else{
        printf("OK");
    }

    return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main() {
	int n; cin >> n;
	set<char> se;
	rep(i, n) {
		char c; cin >> c;
		se.insert(c);
	}
	if(se.size() == 3) printf("Three\n");
	else if(se.size() == 4) printf("Four\n");
	return 0;
}

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

struct State{
    int at;
    long long cost;
    State(int a, long long c) : at(a), cost(c){}
    bool operator>(const State& s) const{
        return cost > s.cost;
    }
};

struct Edge{
    int to;
    long long cost;
    Edge(int t, long long c) : to(t), cost(c){}
};

using Graph = vector<vector<Edge> >;
const long long INF = 1e15;

void dijkstra(int s, const Graph& G, vector<long long>& minc){
    minc.assign(G.size(), INF);
    priority_queue<State, vector<State>, greater<State> > pq;
    pq.emplace(s, 0);
    minc[s] = 0;

    while(!pq.empty()){
        State cur = pq.top();
        pq.pop();
        if(minc[cur.at] < cur.cost) continue;
        for(const Edge& e : G[cur.at]){
            long long cost = cur.cost + e.cost;
            if(minc[e.to] <= cost) continue;
            minc[e.to] = cost;
            pq.emplace(e.to, cost);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    Graph g1(n), g2(n);
    for(int i = 0; i < m; i++){
        int u, v;
        long long a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        g1[u].emplace_back(v, a);
        g1[v].emplace_back(u, a);
        g2[u].emplace_back(v, b);
        g2[v].emplace_back(u, b);
    }
    vector<long long> minc1(n, INF), minc2(n, INF);
    dijkstra(s, g1, minc1);
    dijkstra(t, g2, minc2);
    vector<long long> ans(n, INF);
    for(int i = n-1; i >= 0; i--){
        ans[i] = min(ans[i], minc1[i] + minc2[i]);
        if(i < n-1) ans[i] = min(ans[i], ans[i+1]);
    }
    for(int i = 0; i < n; i++){
        cout << INF - ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 19016
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<complex>
#include<numeric>
#include<bitset>
#define INF 1001001001
#define EPS 1e-8
#define x first
#define y second

using namespace std;
typedef vector<int> vint;
typedef vector<vint>  vvint;
typedef pair<int,int> pint;
typedef long long Int;

struct node{
	Int x;
	Int n;
	string s;
	vector<node*> childs;
	node* parent;
};

int kind(char c){
	if(c>='0' && c<='9') return 0;
	if(c>='A' && c<='Z') return 1;
	if(c=='(') return 2;
	if(c==')') return 3;
}
int readint(string &s,int &n){
	int ans=0;
	for(;n<s.length() && s[n]>='0' && s[n]<='9';ans*=10,n++){
		ans+=s[n]-'0';
	}
	return ans/10;
}
string readstr(string &s,int &n){
	string ans;
	for(;n<s.length() && s[n]>='A' && s[n]<='Z';ans+=s[n],n++);
	return ans;
}
		
int main(){
	string in;
	int n;
	while(cin >> in >> n){
//		cout << in << "	" << n << endl;
		if(in[0]=='0' && n==0) break;
		node *cur=new(node);
		cur->x=1;
		node *root=cur;
		in="1(" + in;
		in+=")";
		int p=0;
		for(;p<in.length();){
//			cout << cur->x << "	" << cur->n << "	" << cur->s << endl;
//			cout << in[p] << endl;
			if(kind(in[p])==0){
				int t=readint(in,p);
				node *c = new(node);
				c->x=t;
				(cur->childs).push_back(c);
				c->parent=cur;
				if(kind(in[p])==1){
					string s=readstr(in,p);
//					cout << s << endl;
					c->s=s;
					c->n=s.length();
					continue;
				}
				else{
					cur=c;
					p++;
					continue;
				}
			}else if(kind(in[p])==1){
				string s=readstr(in,p);
				node *c = new(node);
				(cur->childs).push_back(c);
				c->x=1;
				c->s=s;
				c->n=s.length();
				c->parent=cur;
				continue;
			}else if(kind(in[p])==3){
				cur->n=0;
				for(int i=0;i<(cur->childs).size();i++){
					cur->n += (cur->childs[i]->n)*(cur->childs[i]->x);
					if(cur->n > 1000010) cur->n=1000010;
//					cout << cur->n << endl;
				}
				cur=cur->parent;
				p++;
			}
		}
		cur=(root->childs[0]);
		for(;;){
//			cout << n << "	" << (cur->n) << "	" << (cur->x) <<endl;
			if(n>=(cur->n)*(cur->x)){
				cout << 0 << endl;
				break;
			}else if(cur->s != ""){
				cout << (cur->s)[n] << endl;
				break;
			}
			int i;
			for(i=0;(i<(cur->childs).size()) && (n>=(cur->childs[i]->n)*(cur->childs[i]->x));n-=(cur->childs[i]->n)*(cur->childs[i]->x),i++);
			cur=(cur->childs)[i];
			n%=(cur->n);
		}
	}
	return 0;
}

				
				
				
				
		

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T>inline bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>inline bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int K, S;
    scanf("%d%d", &K, &S);
    int cnt = 0;
    REP(i, K + 1) FOR(j, i, K + 1) FOR(k, j, K + 1) {
        if (i + j + k == S) {
            //cout << i<<" "<<j<<" "<<k<<endl;
            set<int> se{i, j, k};
            if (se.size() == 3) cnt += 6;
            else if (se.size() == 2) cnt += 3;
            else cnt++;
        }
    }
    printf("%d\n", cnt);
}


Measured memory_bytes: 384
package main

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

var sc *bufio.Scanner

func init() {
	// 100MB
	bufsize := 100 * 1024 * 1024
	sc = bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, bufio.MaxScanTokenSize), bufsize)
	sc.Split(bufio.ScanWords)
}
func readInt() int              { return readIntArray(1)[0] }
func readInt2() (int, int)      { a := readIntArray(2); return a[0], a[1] }
func readInt3() (int, int, int) { a := readIntArray(3); return a[0], a[1], a[2] }
func readIntArray(n int) []int {
	s := readStringArray(n)
	a := make([]int, n)
	for i := range a {
		a[i], _ = strconv.Atoi(s[i])
	}
	return a
}
func readString() string            { return readStringArray(1)[0] }
func readString2() (string, string) { a := readStringArray(2); return a[0], a[1] }
func readStringArray(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		a[i] = sc.Text()
	}
	return a
}
func max(ns ...int) int {
	max := ns[0]
	for _, n := range ns {
		if n > max {
			max = n
		}
	}
	return max
}
func min(ns ...int) int {
	min := ns[0]
	for _, n := range ns {
		if n < min {
			min = n
		}
	}
	return min
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	A, B := readInt2()
	al, bl := []int{}, []int{}

	for i := 1; i < 2000; i++ {
		if t := int(float64(i) * 0.08); t == A {
			al = append(al, i)
		}
		if t := int(float64(i) * 0.10); t == B {
			bl = append(bl, i)
		}
	}
	for _, av := range al {
		for _, bv := range bl {
			if av == bv {
				fmt.Println(av)
				return
			}
		}
	}
	fmt.Println(-1)
}


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

struct UnionFind {
    vector<ll> par;  // par[i]: parent of i
    vector<ll> siz;

    UnionFind(ll N) : par(N + 1), siz(N + 1, 1ll) {  // initialize by making every node a root node
        for (int i = 0; i <= N; i++) par[i] = i;
    }

    ll root(ll x) {  // find the root of a given node
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return;
        if (siz[rx] < siz[ry]) swap(rx, ry);
        siz[rx] += siz[ry];
        par[ry] = rx;
        return;
    }

    bool issame(ll x, ll y) {  // return true if x and y belong to the same tree
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    UnionFind uft(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uft.unite(a, b);
    }

    set<int> ss;
    for (int i = 0; i < n; ++i) {
        ss.insert(uft.root(i));
    }
    cout << ss.size() - 1 << endl;
}


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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    vector<int> alp(26);
    string s, ans;
    cin >> s;
    rep (i, s.size()) alp[s[i] - 'a']++;

    if (s.size() == 26) {
        int index = 25;
        for (int i = 24; i >= 0; --i) {
            if (s[i] > s[i + 1]) index = i;
            else break;
        }
        if (index == 0) {
            cout << -1 << endl;
            return 0;
        }
        char tmp = s[index - 1], t = s[index];
        ans = s.substr(0, index - 1);
        for (int i = index; i < s.size(); ++i) {
            if (s[i] > tmp && s[i] < t) t = s[i];
        }
        ans += t;
    } else {
        ans = s;
        rep (i, 26) {
            if (alp[i] == 0) {
                ans += (i + 'a');
                break;
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}



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



int main() {

    map<int,int> mp;
    int n;
    cin >> n;
    int tmp;
    rep(i,n){
        cin >> tmp;
        mp[tmp] = i+1;
    }

    auto begin = mp.begin(), end = mp.end();
    for(auto itr = begin; itr != end; itr++){
        cout << itr->second << ' ';
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 5504
N = int(input())
A = [int(a) for a in input().split()]

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b

g = [None] * N
grev = [None] * N
g[0] = A[0]
grev[-1] = A[-1]
for i in range(1, N):
    g[i] = gcd(g[i-1], A[i])
    grev[-1-i] = gcd(grev[-i], A[-1-i])
maxgcd = max(grev[1], g[N-2])
for i in range(1, N-1):
    maxgcd = max(maxgcd, gcd(g[i-1], grev[i+1]))
print(maxgcd)

Measured memory_bytes: 14052
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007; //998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template <class _T> static _T tp_abs(_T a) {
	if (a < (_T)0) {
		a *= (_T)-1;
	}
	return a;
}

static void A();

int main()
{
	A();
	fflush(stdout);
	return 0;
}


static void A()
{
	int N, X, T;

	get(N, X, T);

	printf("%d\n", (N / X) * T + ((N % X) ? T : 0));
}


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

public class Main {

	private static void solve(){
		//Implement solution here.
		System.out.println(ni() * 500 >= ni() ? "Yes":"No");
	}

	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 21204
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

A_ = list(map(int, input().split()))

A = [A_[i] - i - 1 for i in range(N)]
A.sort()

tmp = A[N // 2]

ans = 0
for a in A:
    ans += abs(tmp - a)

print (ans)

Measured memory_bytes: 25744
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, k = get_li()
    d = dict()
    t = n
    v = k
    m = 0
    while v > 1:
        if v < t:
            d[m] = t - int(ceil(v)) + 1
        m += 1
        t = min(t, int(ceil(v)) - 1)
        v = k / (2 ** m)
    d[m] = t - int(ceil(v)) + 1
    ans = 0
    for k, v in d.items():
        ans += v / (n * (2 ** k))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


Measured memory_bytes: 64620
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    print(-4+input().count('+')*2)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include <iostream>

using namespace std;

int main() {
	int H, W;
	while (true) {
		cin >> H >> W;
		if (H == 0 && W == 0) break;

		for (int k = 0; k < W; k++) {
			cout << '#';
		}
		cout << endl;



		for (int j = 1; j < H-1; j++) {

			cout << '#';

			for (int i = 1; i < W-1; i++) {
				cout << '.';

			}
			cout << '#';

			cout << endl;
		}
		for (int l = 0; l < W; l++) {
			cout << '#';
		}
		cout << endl <<endl;



	}


	return 0;
}




Measured memory_bytes: 3072
using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int count = 0;
        for (int i = 5; i <= n; i += 2) {
            int d = 2;
            for (int j = 3; j < i; j += 2) {
                if (i%j == 0) d ++;
                if (j == i-2 && d == 8) count ++;
            }
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 11092
#include <stdio.h>

int main(void)
{
	int count[4][3][10] = { 0 };
	int i, j ,k , s;
	int n;
	int b, f, r, v;

	scanf("%d", &n);

	for (i = 1; i <= n; i++) {
		scanf("%d %d %d %d", &b, &f, &r, &v);
		count[b - 1][f - 1][r - 1] += v;
	}


	for (i = 0; i < 4;i++) {
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 10; k++) {
				printf(" %d", count[i][j][k]);
			}
			printf("\n");
		}
		if (i < 3) {
			for (s = 0; s < 20; s++) {
				printf("#");
			}
			printf("\n");
		}
	}
	
	
	return 0;
}


Measured memory_bytes: 2056
#include<iostream>
#include<queue>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<stack>
#include<sstream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<list>
#include<numeric>
typedef long long ll;

#define pi 3.14159265358979323846264338327950L
#define VI vector<int>
#define VLL vector<long long>
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
using namespace std;
template<typename T>
T gcd(T a, T b) {
	if (b == 0) return a;
	return gcd(b, a % b);
	//return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	ll g = gcd(a, b);
	return a / g * b; // Be careful not to overflow
	//return a * b / gcd(a, b);
}

template<typename T>
T binarysearch(vector<T> A, T key) {
	ll left = 0;ll right = 4;ll mid;
	while (left < right) {
		mid = (left + right) / 2;
		if (key == A[mid]) return 1;
		if (key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}
	return 0;
}

template<typename T>
T finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll frac(ll n)//階乗
{
	if (n == 0) {
		return 1;
	}
	return (n * frac(n - 1)) % MOD;
}

template<typename T>
T keta(T a) {
	ll kazu = 1;
	while (1) {
		if (a / 10 != 0) { a /= 10;kazu++; }
		else break;
	}
	return kazu;
}//桁数

//素数判定
template<typename T>
bool IsPrime(T num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

template<typename T>
T nCr(ll n, T r) {
	ll ans = 1;
	for (int i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (int i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
/*char r[4];
int yaju[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*/
//vector<vector<int>> data(3, vector<int>(4));
//vector<vector<Type>> vv(n);
//cout << fixed << setprecision(20) << endl;

int main() {
	ll N, M;cin>>N>>M;
	ll ooo, oooo;
	bool ok = false;
	map<ll, ll>a;
	for (ll i = 0;i < M;i++) {
		cin >> ooo >> oooo;
		if (ooo == 1) {
			if (a[oooo] == 0||a[oooo]==1)a[oooo] = 1;
			else if(a[oooo]==N){
				ok = true;
				break;
			}
		}
		if (oooo == 1) {
			if (a[ooo] == 0 || a[ooo] == 1)a[oooo] = 1;
			else if (a[ooo] == N) {
				ok = true;
				break;
			}
		}
		if (ooo == N) {
			if (a[oooo] == 0 || a[oooo] == N)a[oooo] = N;
			else if (a[oooo] == 1) {
				ok = true;
				break;
			}
		}
		if (oooo == N) {
			if (a[ooo] == 0 || a[ooo] == N)a[ooo] = N;
			else if (a[ooo] == 1) {
				ok = true;
				break;
			}
		}
	}
	if (ok)cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int (x); SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long (x); SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x,y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1000000007;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
int dx[2] = {0,1};
int dy[2] = {1,0};

int main(){
    int N;
    string s,t;
    cin >> N >> s >> t;
    int ans = 2 * N;

    REP(i,N){
        REP(j,N){
            bool nowl = true;
            FORq(k,i,N-1){
                if (s[k] != t[k-i]) nowl = false;
            }
            if (nowl) chmin(ans,2*N - (N-i));
        }
    }

    cout << ans << endl;
    
}


Measured memory_bytes: 256
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static Main instance = new Main();

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		//入力値
		int numN = scan.nextInt();
		int numM = scan.nextInt();

		PriorityQueue<Integer> numA = new PriorityQueue<>(Collections.reverseOrder());

		for (int i = 0;  i < numN; i++) {
			numA.add(scan.nextInt());
		}

		for (int i = 0;  i < numM; i++) {
			numA.add(numA.poll() / 2);
		}

		long sum = 0L;
		for (int i : numA) {
			sum += i;
		}

		System.out.println(sum);
	}
}

Measured memory_bytes: 58876
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    tmp = tmp/(len(tree[ss])-1) + 1
    if tmp > dp[ss]:
        return dp[0]
    else:
        dp[ss] = tmp
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)


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

using namespace std;

typedef long long ll;

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

        int a, b, n;
        cin >> a >> b >> n;
        if (a < b)
                swap(a, b);
        swap(a, n);
        cout << (a / n) + ((a % n) != 0) << "\n";

}


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

#define ll long long int

int main()
{
    ll n,ans=0;
    cin>>n;
    if(n%2!=0)
    {
        cout<<0<<endl;
        return 0;
    }
    n/=2;
    while(n>0)
    {
        ans+=(n/5);
        n/=5;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3636
#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--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
const int mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n){
        if(a[i] % 2 != 0) continue;
        else{
            if(a[i] % 3 != 0 && a[i] % 5 != 0){
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
}


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

int main(){
	int m,f,r;

	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if(m==-1 && f==-1 && r==-1){
			break;
		}
		if(m==-1 || f==-1){
			printf("F\n");
		}else if((m+f)>=80){
			printf("A\n");
		}else if((m+f)>=65){
			printf("B\n");
		}else if((m+f)>=50){
			printf("C\n");
		}else if((m+f)>=30){
			if(r>=50){
				printf("C\n");
			}else{
				printf("D\n");
			}
		}else{
			printf("F\n");
		}
	}

	return 0;
}


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

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    int maxa=-1;
    rep(i,n) {
        cin>>a[i];
        maxa=max(maxa,a[i]);
    }
    int l=0,r=maxa;
    while(l+1<r){
        int x=(l+r)/2;
        auto f=[&](int x){
            long long now=0;
            rep(i,n){
                now+=(a[i]-1)/x;
            }
            return now<=k;
        };
        if(f(x))r=x;
        else l=x;
    }
    cout<<r<<endl;
}

Measured memory_bytes: 3932
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    ll n;
    cin>>n;
    vector<ll> v(n);
    rep(i,n){
        cin>>v[i];
    }
    vector<ll> v2(n+1);

    v2[0]=0;
    for(int i=1;i<n;i++){
        v2[i]=v[i-1]^v2[i-1];
    }
    bool f=true;
    for(int i=0;i<n;i++){
        ll check=0;
        if(i==0){
            check=v2[n]^v2[1];
        }else if(i==n-1){
            check=v2[n-1];
        }else{
            check=v2[i]^(v2[n]^v2[i+1]);
        }
        if(check!=v[i]){f=false;break;}
    }
    if(f){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }



    return 0;
}


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

#define REP(i,n) for(int i = 0;i < n;i++)
#define REPR(i,n) for(int i = n-1;i >= 0;i--)
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define PRINT(s) cout<<s
#define PRINTS(s) cout<<s<<' '
#define PRINTL(s) cout<<s<<endl
#define INF 2e9
#define ALL(v) v.begin(),v.end()
#define ll long long

using namespace std;

string pop_back(string s){
    string t = s.substr(0,s.size()-1);
    return t;
}

int gcd(int max,int min){
    
    if(max<min){
        int tmp=max;
        max=min;
        min=tmp;
    }

    if(max%min==0)return min;
    else return gcd(min,max%min);

}

int main(void){

    int n;
    cin>>n;

    int ans=0;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        ans+=r-l+1;
    }

    cout<<ans<<endl;

    return 0;
}




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

using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n<10)cout<<n<<"\n";
    if(n>=10&&n<100)cout<<"9"<<"\n";
    if(n>=100&&n<1000)cout<<n-99+9<<"\n";
    if(n>=1000&&n<10000)cout<<999-99+9<<"\n";
    if(n>=10000&&n<100000)cout<<999-99+9+n-9999<<"\n";
    if(n==100000)cout<<"90909\n";
    return 0;
}


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

int main()
{
    int N;
    cin >> N;
    vector<long double> A(N);
    for (int i = 0; i < N;i++)
        cin >> A[i];

    long double sig = 0;

    for (int i = 0; i < N;i++)
        sig += 1 / A[i];

    long double ans = 1 / sig;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n = (int(input()))
a = list(map(int,input().split()))
b = sorted(a)
j=0
u = [x-y for (x,y) in zip(a,b)]
for a in u:
    if(a!=0):
        j = j+1
if(j>2):
    print("NO")
else:
    print("YES")

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void inp_str(int*);


int main(void) {

int N,K;
char S[100];
char out[100];

scanf("%d",&N);

scanf("%s",S);
scanf("%d",&K);


/*printf("%d\n",N);
printf("%s\n",S);
printf("%d\n",K);*/


int i;
for(i=0;i<N;i=i+1){
if(S[i]==S[K-1]){
	out[i]=S[i];
}else{
	out[i]='*';
}
}
out[N]=S[N];

printf("%s\n",out);


//printf("%d\n",M);

//printf("%d\n",C);




/*

if(flag==1) {
	printf(":(\n");
}else{
printf("Yay!\n");
} 

*/                       
    return 0;
}


void inp_str(int instr[]){
char *ptr;
int z,i,count;
char str[100]={'\0'};
char *ln;

fgets(str, 100, stdin); // 入力："123456\n"
ln = strchr(str, '\n'); /* 改行文字を検索 */
if (ln != NULL) { /* 改行が読み取られていたかどうか */
   *ln = '\0';    /* 改行文字を終端文字に置き換える */
}
else {            /* 入力ストリーム上に文字が残ってる場合 */
   while (1) {    /* 改行文字が読み取られるまで空読みする */
       z = getchar();
      if (z == '\n' || z == EOF) break;
   }
}
	count=0;
    ptr = strtok(str, " ");
    i = atoi(ptr);
    instr[count]=i;
    count=count+1;
    // 2回目以降
    while(ptr != NULL) {
        // strtok関数により変更されたNULLのポインタが先頭
        ptr = strtok(NULL, " ");
        // ptrがNULLの場合エラーが発生するので対処
        if(ptr != NULL) {
		    i = atoi(ptr);
    instr[count]=i;
    		count=count+1;
        }
    }
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define cases long long test;cin>>test;while(test--)
#define f_io ios::sync_with_stdio(false); cin.tie(0)
#define foi(a,n) for(long long i=a;i<n;i++)
#define foj(a,n) for(long long j=a;j<n;j++)
#define fok(a,n) for(long long k=a;k<n;k++)
#define ll long long
#define MOD 1000000007
#define INF 1000000000
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

void topsort(vector<vector<ll> > &adj,vector<bool> &visited,stack<ll> &order,ll src)
{
    visited[src]=1;
    for(auto x:adj[src])
        if(!visited[x])
            topsort(adj,visited,order,x);
    order.push(src);
}

void dfs(vector< vector<ll> > &adj,vector< vector<ll> > &radj,vector<ll> &visited,ll src)
{
    visited[src] = 0;
    foi(0,adj[src].size())
    {
        if (visited[adj[src][i]]==-1)
            dfs(adj,radj,visited,adj[src][i]);
    }
    foi(0,radj[src].size())
    {
        if(visited[radj[src][i]]!=-1)
            visited[src] = max(visited[src],visited[radj[src][i]]+1);
    }
}

int main()
{
    f_io;
    ll n,m;
    cin >> n >> m;
    vector<vector<ll> > adj(n),radj(n);
    foi(0,m)
    {
        ll a,b;
        cin >> a >> b;
        adj[a-1].push_back(b-1);
        radj[b-1].push_back(a-1);
    }
    vector<bool> visited(n);
    stack<ll> order;
    foi(0,n)
        if(!visited[i])
            topsort(adj,visited,order,i);
    vector<ll> dist(n,-1);
    while(!order.empty())
    {
        dfs(adj,radj,dist,order.top());
        order.pop();
    }
    cout << *max_element(dist.begin(),dist.end());
    return 0;
}


Measured memory_bytes: 21876
a,b,c=map(int,input().split())
count=0
for i in range(a,b+1):
    #a,b,c=map(int,input().split())
    #count=0
    if c%i==0:
        count += 1
print(count)
"""
def divisible(x, y):
    return x % y == 0

count = 0
a, b, c = map(int, input().split())

for x in range(a, b + 1):
    if divisible(c, x):
        count += 1

print(count)
"""


Measured memory_bytes: 5608
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n, a; cin >> n >> a;
	if (n == 0) {
		if (a <= 1911) {
			cout << 'M' << a - 1867 << endl;
		}
		else if (a <= 1925) {
			cout << 'T' << a - 1911 << endl;
		}
		else if (a <= 1988) {
			cout << 'S' << a - 1925 << endl;
		}
		else {
			cout << 'H' << a - 1988 << endl;
		}
	}
	else if (n == 1) {
		cout << a + 1867 << endl;
	}
	else if (n == 2) {
		cout << a + 1911 << endl;
	}
	else if (n == 3) {
		cout << a + 1925 << endl;
	}
	else {
		cout << a + 1988 << endl;
	}
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100;
string Max(string a,string b){
    if(a.size()>b.size()) return a;
    if(a.size()<b.size()) return b;
    return a>b?a:b;
}
int Mp[11]={0,2,5,5,4,5,6,3,7,6},a[11];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    vector<string> dp(N+10,"-");
    dp[0]="";
    for(int i=0;i<=n;i++){
        if(dp[i]=="-") continue;
        for(int j=1;j<=m;j++){
            if( i+Mp[a[j]]<=n ){
                dp[i+Mp[a[j]]]=Max(dp[i+Mp[a[j]]],dp[i]+char(a[j]+'0'));
            }
        }
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 43648
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const S = input[0][0];

  return S[1] === "B" ? "ARC" : "ABC";
};

console.log(main(read()));


Measured memory_bytes: 29632
#include <cstdio>
#include <array>
using namespace std;

bool graph[8][8];

void dfs(int n, int &result, int root, array<bool, 8> visited)
{
    visited[root] = true;
    bool allVisited = true;
    for (int i = 0; i < n; ++i)
    {
        if (!visited[i])
        {
            allVisited = false;
            break;
        }
    }
    if (allVisited)
    {
        ++result;
        return;
    }
    for (int i = 0; i < n; ++i)
    {
        if (!visited[i] && graph[root][i])
        {
            dfs(n, result, i, visited);
        }
    }
}

int main()
{
    for (int i = 0; i < 8; ++i)
    {
        for (int j = 0; j < 8; ++j)
        {
            graph[i][j] = false;
        }
    }
    int n, m;
    scanf("%d %d", &n, &m);
    array<bool, 8> visited;
    visited.fill(false);
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a - 1][b - 1] = true;
        graph[b - 1][a - 1] = true;
    }
    int result = 0;
    dfs(n, result, 0, visited);
    printf("%d", result);
    return 0;
}


Measured memory_bytes: 1704
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>

using namespace std;

void print(int x){
	printf("%02d:%02d:%02d\n",x/3600,(x/60)%60,x%60);
}

int main(){
	int a,b,c;
	while(cin>>a>>b>>c,(~a||~b||~c)){
		int sum =2*60*60 - a*3600 - b * 60 - c;
		print(sum);
		print(3 * sum);
	}
	
    return 0;
}

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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  string s;
  void solve() {
    cin >> s;
    string t;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'A')
        t.push_back('A');
      else if (s[i] == 'B') {
        if (i < s.size() - 1 && s[i + 1] == 'C') {
          t.push_back('X');
          i++;
        } else {
          t.push_back('Y');
        }
      } else {
        t.push_back('Y');
      }
    }
    LL ans = 0;
    LL sum = 0;
    for (int i = 0; i < t.size(); ++i) {
      if (t[i] == 'A') {
        sum++;
      } else if (t[i] == 'X') {
        ans += sum;
      } else {
        sum = 0;
      }
    }
    cout << ans << endl;
  }
};

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);

  Problem::Solver sol;
  sol.solve();
  return 0;
}


Measured memory_bytes: 916
n=int(input())
song=[]
time=[]
song_t=""
time_t=0
ans=0
for i in range(n):
    song_t,time_t=input().split()
    time_t=int(time_t)
    song.append(song_t)
    time.append(time_t)
ref=str(input())
judge=False
for i in range(n):
    if(judge):
        ans+=time[i]
    else:
        if(song[i]==ref):
            judge=True
print(ans)

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

int main() {
    ll n;
    cin >> n;
    vector<string> ss(n, "");
    ll ans = 0;
    ll a = 0;
    ll b = 0;
    ll ba = 0;
    rep(i, n) {
        cin >> ss[i];
        size_t it = 0;
        if (ss[i].front() == 'B' && ss[i].back() != 'A') b++;
        if (ss[i].front() != 'B' && ss[i].back() == 'A') a++;
        if (ss[i].front() == 'B' && ss[i].back() == 'A') ba++;

        while (it != string::npos) {
            it = ss[i].find("AB", it);
            if (it != string::npos) {
                it++;
                ans++;
            }
        }
    }
    ans += min(a, b);                       //XB AX
    ans += min(ba, max(a, b) - min(a, b));  // BA BX or XA BA
    ba -= min(ba, max(a, b) - min(a, b));   // not use BA
    ans += (!max(a, b) && ba > 0) ? ba - 1 : ba;
    cout << ans << endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
clock_t startTime;
long double getTime(){
	return (long double)(clock()-startTime)/CLOCKS_PER_SEC;
}

int main(){
	startTime=clock();
	ll n;
	cin >> n;
	ll a[n],sum=0;
	FOR(i,n){
		cin >> a[i];
		a[i]-=(i+1);
		
	}

	sort(a,a+n);
	ll ans1=0,ans2=0;
	int median=n/2;
	FOR(i,n){

		ans1+=abs(a[i]-a[median]);
		if(median<n-1) ans2+=abs(a[i]-a[median+1]);	
	}
	//error(sum,ans,ans1);
	if(median==n-1) cout << ans1;
	else cout << min(ans2,ans1);


	return 0;
}

Measured memory_bytes: 5192
#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define pii pair<int,int>
deque<int> q1,q2;
char t[N];
int n,ans=1e9;
int tol[N],tor[N];
int mx[N];
int calc(int step){
    int ret=step;
    deque<int> a=q1;
    for(int i=0;i<n;i++){
        a[i]=a[i]!=q2[(i-step+n)%n]? 1:0;
        ret+=a[i];
        if(a[i]==1&&tol[i]<=step)
            a[i]=0;
    }
    for(int i=1;i<=step;i++) a.push_back(a.front()),a.pop_front();
    if(ret>=ans) return 1e9;
    memset(mx,0,sizeof(mx));
    for(int i=0;i<n;i++)
        if(a[i]==1) mx[tol[i]]=max(mx[tol[i]],tor[i]-step);
    for(int i=n-1;i>=0;i--) mx[i]=max(mx[i],mx[i+1]);
    int t=1e9;
    for(int i=0;i<n;i++) t=min(t,i+mx[i+1]);
    return ret+t*2;
}
int main(){
    scanf("%s",t+1);
    n=strlen(t+1);
    bool is0=true;
    for(int i=1;i<=n;i++) q1.push_back(t[i]-'0'),is0&=(t[i]=='0');
    scanf("%s",t+1);
    int dl=-1,dr=-1;
    for(int i=1;i<=n;i++){
        q2.push_back(t[i]-'0');
        if(t[i]=='1') dr=n-i;
        if(t[i]=='1'&&dl==-1) dl=i-1;
    } 
    if(!is0&&dr==-1) return puts("-1"),0;
    else if(is0&&dr==-1) return puts("0"),0;
    for(int i=0;i<n;i++){
        if(q2[i]==1) dr=0;
        else dr++;
        tol[i]=dr;
    }
    for(int i=n-1;i>=0;i--){
        if(q2[i]==1) dl=0;
        else dl++;
        tor[i]=dl;
    }
    for(int i=0;i<n;i++) ans=min(ans,calc(i));
    reverse(q1.begin(),q1.end());
    reverse(q2.begin(),q2.end());
    for(int i=0;i<n/2;i++)
        swap(tol[i],tor[n-i-1]),swap(tor[i],tol[n-i-1]);
    if(n%2==1) swap(tol[n/2],tor[n/2]);
    for(int i=0;i<n;i++) ans=min(ans,calc(i));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF ((ll)(1e15))

using namespace std;

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

const int MAX_N = 1000;
const int MAX_M = 2000;
int a[MAX_M], b[MAX_M];

ll c[MAX_M];
ll dist[MAX_N];

int main()
{
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0LL, sizeof(c));

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M; cin >> N >> M;


	rep (i, M){
		cin >> a[i] >> b[i] >> c[i];
		--a[i], --b[i];
		c[i] = -c[i];
	} // end rep

	rep (i, N){
		dist[i] = INF;
	} // end rep

	dist[0] = 0LL;
	rep (update, N - 1){
		rep (i, M){
			if (dist[a[i]] == INF) continue;
			if (dist[b[i]] > dist[a[i]] + c[i]){
				dist[b[i]] = dist[a[i]] + c[i];
			} // end if
		} // end rep
	} // end rep

	ll ans = dist[N - 1];

	bool negative[MAX_N];
	rep (i, N){
		negative[i] = false;
	} // end rep

	rep (update, N){
		rep (i, M){
			if (dist[a[i]] == INF) continue;
			if (dist[b[i]] > dist[a[i]] + c[i]){
				dist[b[i]] = dist[a[i]] + c[i];
				negative[b[i]] = true;
			} // end if

			if (negative[a[i]] == true){
				negative[b[i]] = true;
			} // end if
		} // end rep
	} // end rep

	if (negative[N - 1]){
		cout << "inf" << endl;
	}else{
		cout << -ans << endl;
	} // end if

	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
abs = []
n.times do
  abs << gets.split.map(&:to_i)
end
abs.sort_by! { |a, b| b }

ans = 'Yes'
cur = 0
abs.each do |a, b|
  if b >= cur + a
    cur = cur + a
  else
    ans = 'No'
    break
  end
end
puts ans

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

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

	int move = 0;

	for( int i = 0; i < N; ++i ) {
		int x;
		cin >> x;

		int a = x * 2;
		int b = (K - x) * 2;

		if( a < b ) {
			move += a;
		}
		else {
			move += b;
		}
	}

	cout << move << endl;
}


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

int main( void )
{
	int n;
	while ( cin >> n && n )
	{
		vector <int> list( 7, 0 );

		int age;
		for ( int i = 0; i < n; i++ )
		{
			cin >> age;
			for ( int i = 1; i < 7; i++ )
			{
				if ( age < 10*i )
				{
					list[i-1]++;
					break;
				}
			}
			if ( age >= 60 )
				list[6]++;
		}

		for ( int i = 0; i < 7; i++ )
			cout << list[i] << endl;

	}
	return 0;
}

Measured memory_bytes: 908
#include <stdio.h>

int main(void)
{
	double sum;
	double num;
	double tmp;
	int i;
	
	while (scanf("%lf", &num) != EOF){
		sum = 0;
		tmp = num;
		sum += num;
		for (i = 2; i <= 10; i++){
			if (i % 2 == 0){
				tmp *= 2;
			}
			else {
				tmp /= 3;
			}
			sum += tmp;
		}
		printf("%.8lf\n", sum);
	}
	return 0;
}

Measured memory_bytes: 652