akhauriyash/Code-Regression huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline

    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    a = 1
    for i in range(1, n):
        a = 10 * a % 13
        if s[-(i+1)] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(a*j+k)%13] += dp[i-1][k] % mod
        else:
            j = int(s[-(i+1)])
            for k in range(13):
                dp[i][(a*j+k)%13] += dp[i-1][k] % mod
    print(dp[-1][5]%mod)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61788
package main

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

const MP_SYNTHESIS = 10

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nBamboos := scanInt(sc)

	desiredLens := []int{
		scanInt(sc),
		scanInt(sc),
		scanInt(sc),
	}

	bamboos := make([]int, nBamboos)
	for i := 0; i < nBamboos; i++ {
		bamboos[i] = scanInt(sc)
	}

	sums := make([]int, len(desiredLens))
	mps := make([]int, len(desiredLens))
	minMp := math.MaxInt32

	// 竹の合成パターンを全探索し、MPが最小となるパターンを探す。
	// パターン数は最大でも 4^8 = 65536 なので可能。
	// (各竹の用途は A,B,C,使わない の 4種類)
	patterns(len(bamboos), len(desiredLens)+1, func(ps []int) {
		for i := 0; i < len(desiredLens); i++ {
			sums[i] = 0
			mps[i] = -MP_SYNTHESIS
		}

		for i, p := range ps {
			if p < len(desiredLens) {
				sums[p] += bamboos[i]
				mps[p] += MP_SYNTHESIS
			}
		}

		for i, sum := range sums {
			if sum == 0 {
				// 竹が1本も使われてないケースは無効なのでスキップ。
				return
			}
			mps[i] += abs(desiredLens[i] - sum)
		}

		totalMp := 0
		for _, mp := range mps {
			totalMp += mp
		}
		if totalMp < minMp {
			minMp = totalMp
		}
	})

	fmt.Println(minMp)
}

func patterns(depth int, variation int, run func([]int)) {
	ps := make([]int, depth)

	var dfs func(int)
	dfs = func(d int) {
		if d == depth {
			run(ps)
			return
		}

		for i := 1; i < variation; i++ {
			dfs(d + 1)
			ps[d] = i
		}
		dfs(d + 1)
		ps[d] = 0
	}

	dfs(0)
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
  int n, R[MAX];

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

    int maxv = -2000000000;
    int minv = R[0];

  for(int i = 1; i < n; i++){
      maxv = max(maxv, R[i] - minv);
      minv = min(minv, R[i]);
  }
  cout << maxv << endl;
}

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

int dp[100010], v[100010], n;

int recur(int pos) {
	if(pos == n-1)
		return 0;
	if(pos >= n)
		return 0x3f3f3f3f;

	if(dp[pos] != -1)
		return dp[pos];

	int ret = recur(pos+1) + abs(v[pos] - v[pos+1]);
	ret = min(ret, recur(pos+2) + abs(v[pos] - v[pos+2]));
	dp[pos] = ret;

	return ret;
}

int main() {
	cin >> n;

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

	memset(dp, -1, sizeof dp);
	cout << recur(0) << endl;
	return 0;
}

Measured memory_bytes: 4096
# floor(Ax/B) - A floor(x/B) の最大値Mを求める
# xはN以下の非負整数
# floor(Ax / B) = M + A floor(x / B)
# x / B = k + r
# Ax / B = Ak + Ar

# floor(Ak + Ar) = M + A floor(k + r)
# Ak + floor(Ar) = M + Ak + A floor(r)
# floor(Ar) = M

# r = x / B - k
# M = floor(A * (x / B - k))
#   = floor(A * x /B) - Ak
#   = floor(A/B * x) - Ak
#   = floor(A/B * x) - A * (x // B) 

# A B N
# 5 7 4

# M = floor(5/7 * x) - 5 * (x // 7)


# A B N 
# 11 10 9
# M = floor(11 / 10 * x) - 11 * (x // 10)

import math

def calcM(A, B, x):
        return math.floor(x / B * A) - int(math.floor(x / B)) * A    

def resolve_v1(A, B, N):
    maxM = 0
    for x in range(N+1): # O(N)
        M = calcM(A, B, x)
        maxM = max(maxM, M)

    return maxM

def resolve_v2(A, B, N):
    # x == kB - 1
    maxM = calcM(A, B, N)

    for x in filter(lambda x: (x + 1) % B == 0, range(N+1)): # O(N/B)
        maxM = max(maxM, calcM(A, B, x))
    return maxM


def resolve_v3(A, B, N):
    return calcM(A, B, min(N, B - 1))

if __name__ == '__main__':
    A, B, N = map(int, input().split())
    M = resolve_v3(A, B, N)
    print(M)




Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long int N,M,S=0,i;cin>>N>>M;
  vector<pair<long long int,long long int>>X(N);
  for(i=0;i<N;i++)
    cin>>X.at(i).first>>X.at(i).second;
  sort(X.begin(),X.end());
  i=0;
  while(M>0){
    S+=X.at(i).first*min(M,X.at(i).second);
    M-=X.at(i).second;
    i++;
  }
  cout<<S<<endl;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
//id: UG02-47-18-014
int main()
{
    int n,m,o,sum=0;
    scanf("%d%d%d",&n,&m,&o);
    sum=n+m+o;
    if(sum>=22)
    {
       printf("bust");
    }
    else{
       printf("win");
    }

    return 0;
}


Measured memory_bytes: 128
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

def is_move(i,j):
    if j < 0 or j > w - 1 or i < 0 or i > h - 1:
        return False
    return True

di=[0,1,0,-1]
dj=[1,0,-1,0]
flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            flag_4 = False
            for k in range(4):
                I = i + di[k]
                J = j + dj[k]
                if is_move(I, J):
                    if s[I][J] == "#":
                        flag_4 = True
            if not flag_4:
                flag = True

if flag:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
	int D;
	cin>>D;
	switch(D){
		case 25:
			cout<<"Christmas"<<endl;
			break;
		case 24:
			cout<<"Christmas Eve"<<endl;
			break;
		case 23:
			cout<<"Christmas Eve Eve"<<endl;
			break;
		case 22:
			cout<<"Christmas Eve Eve Eve"<<endl;
			break;
	} 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main() {
 
  while(1) {
 
    int n,k;
 
    cin >> n >> k;
 
    if(n == 0 && k == 0) break;
 
    int a,flag = 0;
    int K[101];
 
    for(int i=0;i<k;i++) 
      cin >> K[i];
 
    for(int i=0;i<n;i++) {
 
      for(int j=0;j<k;j++) {
    cin >> a;
    K[j] -= a;
    if(K[j] < 0) flag =1;
 
      }
    }
 
    if(flag == 1) cout << "No" << endl;
    else cout << "Yes" << endl;
 
  }
 
  return 0;
 
}

Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <stack>
#include <queue>
#include <cmath>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)

const int INF = 100000000;

using namespace std;


int main() {
	int a, b;
	cin >> a >> b;
	if (a + b > 9)cout << "error" << endl;
	else cout << a + b << endl;
	return 0;
}

Measured memory_bytes: 256
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j][0] <= x[0]:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def order(A):
    return sorted(A, key = lambda e: e[0])

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = (int(b), 'SHDC'.index(a))

x1 = x + []
quicksort(x1, 0, n-1)

if x1 == order(x):
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e[1]], e[0]

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

int main() {
  int N;
  int64_t count = 0;
  cin >> N;
  for (int i = 1; i < N + 1; i++) {
    if (i % 3 > 0 && i % 5 > 0)
      count += i;
  }
  cout << count << endl;  
}


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

int main() {
	
	int min0[1000000];
	int min1[1000000];
	fill(min0,min0+1000000,100);
	fill(min1,min1+1000000,100);

	for(int j=1;j<300;j++){
		int n = j*(j+1)*(j+2)/6;
		if( n>=1000000) break;
		min0[n] = 1;
		if((n%2)==1){
			min1[n] = 1;
		}
	}


	for(int i=1;i<1000000;i++)
	{
		for(int j=1;j<300;j++){
			int n = j*(j+1)*(j+2)/6;
			if( n+i>=1000000) break;
			min0[n+i] = min( min0[n+i], min0[i]+1);
			if( (n%2)==1){
				min1[n+i] = min( min1[n+i], min1[i]+1);
			}
		}
	}


	while(true){
		int n;
		cin >> n;
		if(n==0)break;
		cout << min0[n] << " " << min1[n] << endl;
	}

	return 0;
}

Measured memory_bytes: 8972
#include <iostream>
#include <vector>
#include <string>
#include <bits/stdc++.h>
#include <ctime>

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
#define TT int test_cases; cin >> test_cases; while(test_cases--)
#define TT1 int test_cases=1; while(test_cases--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
using namespace std;
typedef long long int ll;


int main() {
    
    FAST;
    TT1{
        
        int a;cin>>a;
        int d=a+a*a+a*a*a;
        cout<<d<<"\n";
    }
}

Measured memory_bytes: 3656
import itertools
#入力
N,M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

#橋はMAX50本なので、1本ずつ取り除いて全てが繋がるかどうかを試行する。

#UnionFind木


def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

#橋の組み合わせ
loop_list = list(itertools.combinations(ABs, M-1))
#print(loop_list)

ans = 0
for loop in loop_list:
    #ループ毎にリセットするので。良くない気がする。
    par = [i for i in range(N+1)]
    size = [1 for _ in range(N+1)]

    for bridge in loop:
        unite(bridge[0], bridge[1])
    
#    print(par)
#    print(size)
    if(max(size) != N):
        ans += 1

print(ans)

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
    string s;
    cin>>s;
    int flag=0;
    rep(i,s.length()){
        if(s[i]=='h'){
            if(i+1<=s.length()-1){
                if(s[i+1]=='i'){
                    flag=1;
                }
                else{
                    flag=0;
                    break;
                }
            }
        }
        else if(s[i]=='i'){
            if(i+1<=s.length()-1){
                if(s[i+1]=='h'){
                    flag=1;
                }
                else{
                    flag=0;
                    break;
                }
            }
        }
        else{
            flag=0;
            break;
        }
    }
    if(s.length()%2!=0){
        flag=0;
    }
    if(flag==1){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    
}

Measured memory_bytes: 256
use std::cmp;

#[allow(unused_macros)]
macro_rules! invec {
    ( $t:ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(), Ok(n) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }}
}

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($(
            {
                 splits.next().unwrap().parse::<$t>().unwrap()
            },
        )*)
    }}
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (s,) = input!(String);

    let mut len = 0;
    let mut max_len = 0;
    for c in s.chars() {
        match c {
            'A' | 'C' | 'G' | 'T' => {
                len += 1;
                max_len = cmp::max(len, max_len);
            },
            _ => len = 0,
        }
    }

    println!("{}", max_len);
}

fn main() {
    solve();
}


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

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


Measured memory_bytes: 256
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy


def main():
    N = int(input())
    ans = [0 for i in range(60001)]
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                ans[x * x + y * y + z * z + x * y + y * z + z * x] += 1

    for i in range(N):
        print(ans[i + 1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 9864
#include <bits/stdc++.h>
using namespace std;
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define vecin1(n) vector<int> vec1(n); rep(i,n) cin >> vec1.at(i)
#define vecin2(n) vector<int> vec2(n); rep(i,n) cin >> vec2.at(i)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;


int main() {

int ans,n,H,y;
ans = y = 0; //y=左側にある山の最大値
cin >> n;
rep(i,n)
{
cin >> H; 
if (y<=H) //Hの山が海をみえるならば
ans++;
y=max(y,H); //今までの山の高さの最大値
}

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

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

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

    int n;
    cin >> n;

    vector<int> h(n);
    REP(i, n) cin >> h[i];

    vector<int> dp(n + 2, INT_MAX);
    dp[0] = 0;

    REP(i, n) REP(j, 3)
        chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));

    cout << dp[n - 1] << '\n';
    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
const LL mod=1e9+7;
const int N=1006;
using namespace std;
LL f[N];

LL fun(int n)
{
	LL ans=1;
	memset(f,0,sizeof(f));
	for(int i=2;i<=n;i++)
	{
		int k=i;
		for(int j=2;j<=k;j++)
		{
			while(k%j==0)
			{
				f[j]++;
				k/=j;
			}
		}
		if(k)
			f[k]++;
	}
	for(int i=2;i<=n;i++)
	{
		if(f[i])
			ans=ans*(f[i]+1)%mod;
	}
	return ans%mod;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		printf("%lld\n",fun(n));
	}
	return 0;
} 

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

using namespace std;

int solve(int a, int b, int c, int d){
	int l, r;

	l = max(a, c);
	r = min(b, d);

	return max(0, r - l);
}

int main(){
	int a, b, c, d;

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

	printf("%d\n", max(solve(a, b, c, d), solve(c, d, a, b)));

	return 0;
}

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

using namespace std;

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

    int start = max(X - K + 1, -1000000);
    int end = min(X + K - 1, 1000000);

    for (int i = start; i <= end; i++)
    {
        cout << i;
        if (i < end)
        {
            cout << ' ';
        }
        else
        {
            cout << endl;
        }
    }
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace C
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var n = int.Parse(Console.ReadLine());
            var pi = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var count = 1;
            var minIndex = 0;
            for (var i = 1; i < n; i++)
            {
                if (pi[i] <= pi[minIndex])
                {
                    count++;
                    minIndex = i;
                }
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 33628
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int X[305][305], N, M, L;
long long dist[305][305];

int f(int s, int t) {
	if (dist[s][t] <= L) return 0;
	int &ret = X[s][t];
	if (ret != -1) return ret;
	ret = 1e9;
	for (int i = 1; i <= N; ++i) {
		if (i != s && i != t) ret = min(ret, f(s, i) + f(i, t));
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M >> L;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) if (i != j) dist[i][j] = 1e15, X[i][j] = 1e9;
	for (int i = 0; i < M; ++i) {
		int a, b, c; cin >> a >> b >> c;
		if (c > L) continue;
		dist[a][b] = dist[b][a] = c;
	}
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			for (int k = 1; k <= N; ++k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (dist[i][j] <= L) X[i][j] = 1;
		}
	}
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			for (int k = 1; k <= N; ++k) X[j][k] = min(X[j][k], X[j][i] + X[i][k]);
	int Q; cin >> Q;
	for (int i = 0; i < Q; ++i) {
		int s, t; cin >> s >> t;
		int a = X[s][t] > N ? 0 : X[s][t];
		printf("%d\n",a - 1);
	}
	return 0;
}

Measured memory_bytes: 1664
#include<stdio.h>
struct Card{char suit;int value; };
int main()
{
  struct Card a[101],b[101];
  int n,i,j,k,mini,m,sum=0; 
  char ch;
  scanf("%d%c",&n,&ch);
  for(i=0;i<n;i++){ 
    scanf("%c%d%c",&a[i].suit,&a[i].value,&ch);
  }
  for(i=0;i<n+1;i++){
    b[i]=a[i];
  }
   
  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      if(a[j].value<a[j-1].value){
    m=a[j].value;
    a[j].value=a[j-1].value;
    a[j-1].value=m;
    ch=a[j].suit;
        a[j].suit=a[j-1].suit;
        a[j-1].suit=ch;
      }
    }
  }  
  for(i=0;i<n-1;i++){
    mini=i; 
    m=b[i].value;
    for(j=i;j<n;j++){
      if(b[j].value<m){
    m=b[j].value;
    mini=j;
      }
    }
    if(m!=b[i].value){
      k=b[i].value;
      b[i].value=b[mini].value;
      b[mini].value=k;
      ch=b[i].suit;
      b[i].suit=b[mini].suit;
      b[mini].suit=ch;
    }
  }
  for(i=0;i<n;i++){
    if(a[i].suit==b[i].suit && a[i].value==b[i].value){
    sum++;
    }
  }
  for(i=0;i<n-1;i++){
    printf("%c%d ",a[i].suit,a[i].value);
  }
  printf("%c%d",a[i].suit,a[i].value);
  printf("\nStable\n");
 
  for(i=0;i<n-1;i++){
    printf("%c%d ",b[i].suit,b[i].value);
  }
  printf("%c%d",b[i].suit,b[i].value);
  if(sum==n)printf("\nStable\n");
  else printf("\nNot stable\n");
 
  return 0;
}


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

#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, N) FOR(i, 0, N)

#define MOD 1000000007
#define INF 1000000000

using ll = long long int;
using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;



int main() {
    int M; cin >> M;
    vector<ll> d(M), c(M);
    rep(i,M) cin >> d[i] >> c[i];

    ll ans = 0;
    rep(i,M) ans += c[i];
    ans--;

    ll sum = 0;
    rep(i,M){
        sum += (d[i]*c[i]);
    } 
    ans += (sum-1)/9;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<stdio.h>
#include<string.h>

#define M 1000000

#define L 14

char H[M][L];
int getChar(char ch) {
	if (ch == 'A') return 1;
	else if (ch == 'C')return 2;
	else if (ch == 'G')return 3;
	else if(ch == 'T')return 4;
	else return 0;
}

long long getKey(char str[]) {
	long long sum = 0, p = 1, i;
	for (i = 0; i < strlen(str); i++) {
		sum += p*(getChar(str[i]));
		p *= 5;
	}
	return sum;
}

int h1(int key) { return key % M; }
int h2(int key) { return 1 + (key % (M - 1)); }

int find(char str[]) {
	long long i,x,k;
	k = getKey(str);
	for (i=0;;i++) {

		x=(h1(k)+i*h2(k))%M;

		if (strcmp(H[x], str) == 0) {
      return 1;
    }
		else if (strlen(H[x]) == 0){
      return 0;
    }
	}
	return 0;
}

int insert(char str[]) {
	long long i,x,k;
	k = getKey(str);
	for (i =0;;i++){
		x=(h1(k)+i*h2(k))%M;

		if (strcmp(H[x], str) == 0) {
    return 1;
    }
		else if (strlen(H[x]) == 0){
			strcpy(H[x], str);
			return 0;
		}
	}
	return 0;
}

int main() {
	int i, n;
	char str[L], com[9];
	for (i = 0; i < M; i++)H[i][0] = '\0';
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s %s", com, str);

		if (com[0] == 'i') {
			insert(str);
		}
		else {
			if (find(str)) {
				printf("yes\n");
			}
			else { printf("no\n"); }
		}
	} return 0;
}



Measured memory_bytes: 15404
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(int, N, K);
    vector<pair<int, int>> sushi(N);
    rep(i, 0, N) {
        var(int, t, d);
        --t;
        sushi[i] = {d, t};
    }

    sort(all(sushi), greater<>());

    i64 ans = 0;
    vector<int> cnt(N);
    i64 sum = 0;

    auto itr = sushi.begin();
    rep(i, 0, K) {
        ++cnt[itr->second];
        sum += itr->first;
        ++itr;
    }

    i64 t = count_if(all(cnt), [](auto n) { return n > 0; });
    chmax(ans, sum + t * t);

    dump(cnt);
    dump(sum, t, ans);

    for (; itr != sushi.end(); ++itr) {
        if (t >= K) break;
        if (cnt[itr->second]) continue;
        repr(i, K - 1, 0) {
            if (cnt[sushi[i].second] > 1) {
                --cnt[sushi[i].second];
                sum -= sushi[i].first;

                ++cnt[itr->second];
                sum += itr->first;
                ++t;

                sushi[i] = *itr;
                break;
            }
        }

        chmax(ans, sum + t * t);
    }

    print(ans);

    return 0;
}


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

#define LEN 15.707963267948966


long long xone, yone, xtwo, ytwo, N;
vector<pair<long long, long long> >xy;
vector<pair<long long, long long> >xy_tate;
vector<pair<long long, long long> >xy_yoko;
long long pat;

long long LIS(vector<long long> nums){
	long long dp[200005];
	fill(dp, dp + nums.size(), INT_MAX);
	for (int i=0; i<nums.size(); ++i) {
		*lower_bound(dp, dp+nums.size(), nums[i]) = nums[i];
	}
	return lower_bound(dp, dp + nums.size(), INT_MAX) - dp;
}


int main(){
	cin >> xone >> yone >> xtwo >> ytwo;
	cin >> N;

	if(xone <= xtwo){
		if(yone <= ytwo){
			pat = 1;
		}else{
			pat = 2;
			yone *= -1;
			ytwo *= -1;
		}
	}else{
		if(yone <= ytwo){
			pat = 3;
			xone *= -1;
			xtwo *= -1;
		}else{
			pat = 4;
			xone *= -1;
			xtwo *= -1;
			yone *= -1;
			ytwo *= -1;
		}
	}

	for(long long i = 0; i < N; i++){
		long long xtmp, ytmp;
		cin >> xtmp >> ytmp;
		if(pat == 1){

		}else if(pat == 2){
			ytmp *= -1;
		}else if(pat == 3){
			xtmp *= -1;
		}else{
			xtmp *= -1;
			ytmp *= -1;
		}
		if(xone <= xtmp && xtmp <= xtwo && yone <= ytmp  && ytmp <= ytwo){
			xy.push_back(make_pair(xtmp, ytmp));
		}
		if(xone < xtmp && xtmp < xtwo && yone <= ytmp  && ytmp <= ytwo){
			xy_yoko.push_back(make_pair(xtmp, ytmp));
		}
		if(xone <= xtmp && xtmp <= xtwo && yone < ytmp  && ytmp < ytwo){
			xy_tate.push_back(make_pair(xtmp, ytmp));
		}
	}

	sort(xy.begin(), xy.end());
	sort(xy_yoko.begin(), xy_yoko.end());
	sort(xy_tate.begin(), xy_tate.end());

	vector<long long> lis;
	for(auto tmp: xy){
		lis.push_back(tmp.second);
	}

	vector<long long> lis_yoko;
	for(auto tmp: xy_yoko){
		lis_yoko.push_back(tmp.second);
	}

	vector<long long> lis_tate;
	for(auto tmp: xy_tate){
		lis_tate.push_back(tmp.second);
	}

	if(xone == xtwo || yone == ytwo){
		double base = (xtwo - xone) + (ytwo - yone);
		base *= 100;
		long long num = LIS(lis);
		//cout << "base = " << base << " num = " << num << endl;
		if(num == 1){
			base -= 20;
			base += 2 * LEN;
		}else if(num == 0){
		}else{
			return 1;
		}
		printf("%.15f\n", base);
		return 0;
	}else{
		double base = (xtwo - xone) + (ytwo - yone);
		base *= 100;
		long long num = LIS(lis);
		long long numtate = LIS(lis_tate);
		long long numyoko = LIS(lis_yoko);
		if(num - 1 <= numtate && num - 1 <= numyoko){
			base -= 20 * num;
			base += num * LEN;
		}else{
			if(num == min(xtwo - xone + 1, ytwo - yone + 1)){
				//have to use all
				base -= 20 * num;
				base += (num + 1) * LEN;
			}else{
				base -= 20 * num;
				base += (num) * LEN;
				//can skip one
				//base -= 20 * (num - 1);
				//base += (num - 1) * LEN;
				//return 1;
			}
			//return 1;
		}
		printf("%.15f\n", base);
		return 0;
	}
}


Measured memory_bytes: 20748
def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    c_num_list = num_list[:]

    num_list.sort()

    for i in range(n):
        tmp = num_list[n//2]
        if c_num_list[i] >= tmp:
            print(num_list[n//2-1])
        else:
            print(num_list[n//2])
        

if __name__ == '__main__':
    main()

Measured memory_bytes: 93780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> X(N);
    rep(i, N) cin >> X.at(i);
    
    int ans = INF;
    rep(i, N - K + 1){
        int time = 0;
        time += abs(X.at(i + K - 1) - X.at(i));
        time += min(abs(X.at(i)), abs(X.at(i + K - 1)));
        ans = min(ans, time);
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<map>
#define pb push_back
using namespace std;
map<char,long long int > ind;
long long int save[200005][3];
vector<char> res;
char s[200005][2];
int  main(){
  long long int  N;
  cin>>N>>ind['A']>>ind['B']>>ind['C'];
  for(long long int  i=0; i<N; i++) cin>>s[i];
  save[N][0]=save[N][1]=save[N][2]=N;
  for(int i=N-1; i>=0; i--){
    if(s[i][0]=='A' || s[i][1]=='A') save[i][0]=i;
    else save[i][0]=save[i+1][0];
    if(s[i][0]=='B' || s[i][1]=='B') save[i][1]=i;
    else save[i][1]=save[i+1][1];
    if(s[i][0]=='C' || s[i][1]=='C') save[i][2]=i;
    else save[i][2]=save[i+1][2];
  }
  for(long long int i=0; i<N; i++){
    if(ind[s[i][0]]==ind[s[i][1]] && ind[s[i][0]]==0){
      cout<<"No"<<endl;
      return 0;
    }
    else if(ind[s[i][0]]!=0 && ind[s[i][1]]==0){
      ind[s[i][0]]--;
      ind[s[i][1]]++;
      res.pb(s[i][1]);
    }
    else if(ind[s[i][1]]!=0 && ind[s[i][0]]==0){
      ind[s[i][1]]--;
      ind[s[i][0]]++;
      res.pb(s[i][0]);
    }
    else if(ind[s[i][0]]==1 && ind[s[i][1]]>1){
      ind[s[i][0]]++;
      ind[s[i][1]]--;
      res.pb(s[i][0]);
    }
    else if(ind[s[i][1]]==1 && ind[s[i][0]]>1){
      ind[s[i][1]]++;
      ind[s[i][0]]--;
      res.pb(s[i][1]);
    }
    else if(ind[s[i][1]]==1 && ind[s[i][0]]==1){
      if(save[i+1][s[i][0]-'A']<save[i+1][s[i][1]-'A']){
        ind[s[i][1]]--;
        ind[s[i][0]]++;
        res.pb(s[i][0]);
      }
      else{
        ind[s[i][0]]--;
        ind[s[i][1]]++;
        res.pb(s[i][1]);
      }
    }
    else{
      ind[s[i][0]]--;
      ind[s[i][1]]++;
      res.pb(s[i][1]);
    }
  }
  cout<<"Yes"<<endl;
  for(long long int  i=0; i<res.size(); i++) cout<<res[i]<<endl;
  return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
#define LINF 1e18
typedef long long ll;


int main() {
    int N,Q; cin >> N >> Q;
    vector<vector<int>> G(N);
    REP(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<int> count(N,0);
    vector<bool> checked(N,false);
    REP(i,Q){
        int p,x; cin >> p >> x;
        p--;
        count[p] += x;
    }

    queue<int> q;
    q.push(0);
    checked[0] = true;

    while(!q.empty()){
        auto p = q.front(); q.pop();
        for(auto next: G[p]){
            if(checked[next] == true) continue;

            checked[next] = true;
            count[next] += count[p];
            q.push(next);
        }
    }

    REP(i,N) cout << count[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 16612
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <cassert>
using namespace std;
 
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<int, ll> i_ll;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
typedef vector<int> vi;
struct edge { int v; ll w; };
 
const int MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
int INF = INT_MAX / 2;

int main() {
	int N, x; cin >> N >> x;
	vector<int> a(N);
	rep(i, N) scanf("%d", &a[i]);
	vector<ll> b(N + 1);
	for (int i = N - 1; i >= 0; i--) {
		b[i] = b[i + 1];
		if (a[i] <= b[i] * 2 + 1) b[i] += a[i];
	}
	vector<bool> ans(N);
	rep(i, N) {
		ans[i] = (x > b[i + 1]);
		x = min(x, abs(x - a[i]));
	}
	int Q; cin >> Q;
	while (Q--) {
		int i; scanf("%d", &i); i--;
		printf("%s\n", ans[i] ? "YES" : "NO");
	}
}


Measured memory_bytes: 7808
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0]*((N + 1)//2)
    if N % 2 == 1:
        for a in A:
            if a % 2 == 1:
                print(0)
                return
            B[a//2] += 1
    else:
        for a in A:
            if a % 2 == 0:
                print(0)
                return
            B[(a - 1)//2] += 1
    ans = 1
    # print(B)
    for i in range(len(B)):
        b = B[i]
        if N % 2 == 1 and i == 0:
            if b != 1:
                print(0)
                return
        elif b != 2:
            print(0)
            return
        ans = (ans * b) % (10**9 + 7)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14008
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

  ll ans = 0;
  for (int i = 1; i <= N; i++) {
    if (i % 3 != 0 && i % 5 != 0) {
      ans += i;
    }
  }

  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 < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    string s;
    cin >> s;
    int size = s.length();
    int sizeh = size/2;
    int j = size-1;
    int ans = 0;
    rep(i,sizeh){
        if(s[i] != s[j]) ans++;
        j--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3720
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut user = vec![vec![]; m];
    for i in 0..n {
        let v = read_vec::<usize>();
        for j in 1..v.len() {
            user[v[j] - 1].push(i);
        }
    }
    let mut uft = UnionFindTree::new(n);
    for mi in 0..m {
        for i in 1..user[mi].len() {
            uft.unite(user[mi][0], user[mi][i]);
        }
    }
    if uft.get_size(0) == n {
        println!("YES");
    } else {
        println!("NO");
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[derive(Debug, Clone)]
struct UnionFindTree {
    parent: Vec<isize>,
    size: Vec<usize>,
    height: Vec<u64>,
}

impl UnionFindTree {
    fn new(n: usize) -> UnionFindTree {
        UnionFindTree {
            parent: vec![-1; n],
            size: vec![1usize; n],
            height: vec![0u64; n],
        }
    }

    fn find(&mut self, index: usize) -> usize {
        if self.parent[index] == -1 {
            return index;
        }
        let idx = self.parent[index] as usize;
        let ret = self.find(idx);
        self.parent[index] = ret as isize;
        ret
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    fn get_size(&mut self, x: usize) -> usize {
        let idx = self.find(x);
        self.size[idx]
    }

    fn unite(&mut self, index0: usize, index1: usize) -> bool {
        let a = self.find(index0);
        let b = self.find(index1);
        if a == b {
            false
        } else {
            if self.height[a] > self.height[b] {
                self.parent[b] = a as isize;
                self.size[a] += self.size[b];
            } else if self.height[a] < self.height[b] {
                self.parent[a] = b as isize;
                self.size[b] += self.size[a];
            } else {
                self.parent[b] = a as isize;
                self.size[a] += self.size[b];
                self.height[a] += 1;
            }
            true
        }
    }
}


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

using vi = vector<int>;
using vl = vector<long long int>;
using vii = vector<vector<int>>;
using vll = vector<vector<long long int>>;
#define pb push_back;
#define mp make_pair;
/*ll powM(ll a,ll b,ll m)
{
    ll ans=1;
    a%=m;
    while(b)
        {
            if(b&1)ans=ans*a%m;
            a=a*a%m;
            b>>=1;
        }
        return ans;
}
*/


int main(){
      ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.precision(2);
cout<<fixed;
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll a1=c/b;
ll a2=a/d;
if(c%b)a1++;
if(a%d)a2++;
if(a1<=a2)cout<<"Yes"<<"\n";
else cout<<"No"<<"\n";
 return 0;


}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <iomanip>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti = tuple<int, int, int>;

const double eps=1e-14;
const int mod = 1e9 + 7;
const int inf = ((1<<28));
const ll linf = (1LL<<58);

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    if(n > m/2) cout << m/2 << endl;
    else
    {
      m -= 2*n;
      cout << n + m/4 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <deque>
using namespace std;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(e, elem) for(auto& (e) : (elem))
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define all(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e);
using ll = long long;
using ull = unsigned long long;

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

    ll ab = n / (a + b);
    ll aab = n % (a + b);

    ll ans = a * ab;
    ans += min(aab, a);

    println(ans);
}


Measured memory_bytes: 256
N,M=map(int, input().split()) 
P=list(map(int,input().split()))
par=[i for i in range(N+1)]
rank=[0]*(N+1)
#根
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
  
def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
  
#同じ集合か判定
def same(x,y):
  return find(x)==find(y)

def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 0
  if rank[x]<rank[y]:
    par[x]=y
  else:
    par[y]=x
    if rank[x]==rank[y]:
      rank[x]+=1

for i in range(M):
  a,b=map(int,input().split())
  union(a,b)

ans=0
for i in range(1,N+1):
  if same(P[i-1],i):
    ans+=1
print(ans)
 

Measured memory_bytes: 13812
#!/usr/bin/env python3
#ABC131 E
import sys
import math

N, K = map(int,input().split())

if K > (N - 1)*(N - 2) // 2:
    print(-1)
    exit()

print((N - 1)*(N - 2) // 2 + (N - 1) - K)
for i in range(N - 1):
    print(1,i+2)
s = 2
t = 3
for i in range((N - 1)*(N - 2) // 2 - K):
    print(s,t)
    t += 1
    if t > N:
        s += 1
        t = s + 1


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

using namespace std;

//#define DEBUG

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
#else
#define PRINT(A)
#endif

int main() {
    ll N; cin >> N;
    ll sum = 0;
    for(int i = 1; i <= N; i++){
        if(i%3 != 0 && i%5 !=0){
            sum += i;
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, ll> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 200010;
const int MAXM = 35;
const int MAXK = 510;
const int MAXQ = 200010;

int n, a[MAXN], b[MAXN];
vector<int> A, B;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> b[i];

    int res = 0;
    FOR(k,0,28) {
        A.clear();
        FOR(i,1,n) A.emplace_back(a[i] % (1 << (k+1)));
        B.clear();
        FOR(i,1,n) B.emplace_back(b[i] % (1 << (k+1)));
        sort(ALL(B));

        int q = 0;

        FOR(i,0,n-1) {
            if (A[i] & (1 << k)) {
                q += lower_bound(ALL(B), (2 << k) - A[i]) - B.begin();
                q += B.end() - lower_bound(ALL(B), (3 << k) - A[i]);
            }
            else {
                auto s = lower_bound(ALL(B), (1 << k) - A[i]);
                auto t = lower_bound(ALL(B), (2 << k) - A[i]);
                q += t - s;
            }

        }
        res += ((q & 1) << k);
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  ll n;
  cin >> n;
  vi p(n);
  ll count = 0;
  rep(i, n){
    cin >> p[i];
    count += p[i];
  }
  sort(all(p));
  p[n - 1] /= 2;
  count -= p[n - 1];
  print(count);
}

Measured memory_bytes: 256
#include <stdio.h>

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

int n, A[30];

int solve(int i, int m) {
  if(m == 0) return 1;
  if(i >= n) return 0;
  return solve(i + 1, m) || solve(i + 1, m - A[i]);
}

int main(void) {
  scanf("%d", &n);
  REP(i, n) {
    scanf("%d", &A[i]);
  }

  int q;
  scanf("%d", &q);
  int m;
  REP(i, q) {
    scanf("%d", &m);
    if(solve(0, m)) {
      printf("yes\n");
    } else {
      printf("no\n");
    }
  }

  return 0;
}

Measured memory_bytes: 2688
#include<stdio.h>
#define MAX 500001
int n;
void maxHeapify(int *,int);
void buildMaxHeap(int *);
int main(){
  int A[MAX],i;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d",&A[i]);
  buildMaxHeap(A);
  for(i=1;i<=n;i++)
    printf(" %d",A[i]);
  printf("\n");
  return 0;
}

void maxHeapify(int A[],int i) 
{
  int l,r,largest,tmp;
  l = i*2;
  r = i*2+1;
  if(l<=n && A[l]>A[i]) 
    largest = l;
  else 
    largest = i;
  if(r<=n && A[r]>A[largest])
    largest = r;
  
  if(largest != i) {
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(A,largest);
  }
}

void buildMaxHeap(int A[]) 
{
  int i;
  for(i=n/2; i>=1; i--)
    maxHeapify(A,i);
}

Measured memory_bytes: 2548
def In(): return int(raw_input())
while 1:
  m = In()
  if m==0: break

  card = [0]*m
  total = 0
  for i in range(m):
    a,b = map(int, raw_input().split())
    card[i] = [a,b]
    total += a*b
  card = sorted(card)[::-1]

  B = [0]*(total+1)
  for a,b in card:
    A = B[:]
    B = [0]*(total+1)
    B[a:a*b+1:a] = [1]*b
    for i in range(total+1)[::-1]:
      if A[i]:
        for e in range(i,i+a*b+1,a): B[e] += A[i]

  for _ in [0]*In():
    n = In()
    if 0<=n<=total: print B[n]
    else: print 0

Measured memory_bytes: 4408
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(void){
    int n,k; cin >> n >> k;
    int r,s,p; cin >> r >> s >> p;
    string t; cin >> t;
    string str;
    for(int i=0;i<t.length();i++){
        if(t[i]=='r') str+= 'p';
        else if(t[i]=='s') str += 'r';
        else str += 's';
    }
    for(int i=0;i<str.length()-k;i++){
        if(str[i] == str[i+k]) str[i+k] = ' ';
    }
    // cout << str << endl;
    int ans = 0;
    for(int i=0;i<str.length();i++){
        if(str[i]=='r') ans+=r;
        else if(str[i]=='s') ans+=s;
        else if(str[i]=='p') ans+=p;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
   int s;cin >> s;
   int left = s/100;
   int right = s%100;

   if(1 <= left && 12 >= left){
       if(1 <= right && 12 >= right)cout << "AMBIGUOUS" << endl;
       else cout << "MMYY" << endl;
   }else{
       if(1 <= right && 12 >= right)cout << "YYMM" << endl;
       else cout << "NA" << endl;
   }
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <map>
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c && c == a) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    A, B = MI()
    print(A*B)
    


if __name__ == "__main__":
	main()

Measured memory_bytes: 9188
function Main(input) {
  input = input.trim()
  input = input.split("\n");
  var N = input[1].split("");
  var A = input[0].split(" ").map(Number);
  N[A[1]-1] = hoge(N[A[1]-1]);
  
  console.log(N.join(""))

}Main(require("fs").readFileSync("/dev/stdin", "utf8"));
function hoge(N){
switch(N){
  case "A":
  return "a";
  break;
    case "B":
  return "b";
  break;
    case "C":
  return "c";
  break;
}
}

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

using namespace std;

#define FOR(i,s,e) for(int i=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp make_pair
#define mt make_tuple
#define t0(t) get<0>((t))
#define t1(t) get<1>((t))
#define t2(t) get<2>((t))

typedef long long ll;
const int N = 1e5;
int n;
int x[N+1], y[N+1], t[N+1];

int main() {
  fscanf(stdin, "%d ", &n);
  FOR(i,1,n+1) fscanf(stdin, "%d%d%d ", t+i, x+i, y+i);
  int ok = 1;
  REP(i,n) {
    int d = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);
    d -= t[i+1] - t[i];
    if (d > 0 || (-d)&1) ok = 0;
  }
  puts(ok ? "Yes" : "No");
  return 0;
}


Measured memory_bytes: 1408
N, W = map(int, input().split())
I = [list(map(int, input().split())) for i in range(N)]
V = sum(v for v, w in I)

dp = [W+1] * (V + 1)
dp[0] = 0
for v, w in I:
    for j in range(V, v-1, -1):
        dp[j] = min(dp[j-v] + w, dp[j])
print(max(i for i in range(V+1) if dp[i] <= W))


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

int main() {

    ll n, k;
    cin >> n >> k;

    if(k == 0){
        cout << n*n << endl;
        return 0;
    }
    ll ans = 0;
    for(ll i=k+1; i<=n; ++i){
        ans += (i-k) * (n/i);
        ll x = n % i;
        if(x - k >= 0 && k != 0){
            ans += x - k + 1;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256