akhauriyash/Code-Regression huggingface dataset:
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
 
//
// # Examples
//
// # integers
// input! { n: usize, m: usize, ... }
//
// # array
// input! { n: usize, v: [u64; n], }
//
// # matrix
// input! { n: usize, m: usize, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: usize,
//     w: usize,
//     board: [chars; h],
// }
 
// https://practice.contest.atcoder.jp/tasks/practice_1

use std::collections::HashMap;

fn main() {
    input! { s: chars }
    let s: String = s.into_iter().collect();
    let mut map = HashMap::new();
    map.insert("A".to_string(),"T");
    map.insert("T".to_string(),"A");
    map.insert("C".to_string(),"G");
    map.insert("G".to_string(),"C");
    println!("{}", map.get(&s).unwrap());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;
#define inf 1e9

int main() {
    int a,b;
    string s;
    cin>>a>>b>>s;
    rep(i,a+b-1) {
        if (i!=a) {
            if (s[i]=='-') {
                cout<<"No"<<endl;
                return 0;
            } 
        }
        else {
            if (s[i]!='-') {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
} 


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define FOR(i,a,n) for(i=a;i<n;i++)
int comp(const void* a,const void* b){
	return *(int*)b-*(int*)a;
}
void fill(int a[],int b,int c){
	int i;
	FOR(i,0,b) a[i]=c;
	return;
}
int l[200];
int main(void)
{
	int ans=0,n,i;
	scanf("%d",&n);
	FOR(i,0,n*2) scanf("%d",&l[i]);
	qsort(l,2*n,sizeof(int),comp);
	for(i=1;i<2*n;i+=2) ans+=l[i];
	printf("%d\n",ans);
	return 0;
}
    
    


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
 
  int x; cin >> x;
  
  vector<int> vec(x);
  int t = 0;
  
  for(int i=0; i<x; i++){
    cin >> vec.at(i);
    
    if (i == 0){
      t += abs(vec.at(0));
    } else{
      t += abs(vec.at(i) - vec.at(i-1)); 
    }
    
    if (i == x-1){
      t += abs(vec.at(x-1));
    }
    
  }
  
  int ans;
  for(int i=0; i<x; i++){
    
    if (i == 0){
      ans = t - abs(vec.at(0)) - abs(vec.at(1) - vec.at(0)) + abs(vec.at(1)); 
    } else if (i == x-1){
      ans = t - abs(vec.at(i)) - abs(vec.at(i) - vec.at(i-1)) + abs(vec.at(i-1)); 
    } else {
      ans = t 
            - abs(vec.at(i) - vec.at(i-1)) 
            - abs(vec.at(i+1) - vec.at(i)) 
            + abs(vec.at(i+1) - vec.at(i-1));
    }
    cout << ans << endl;
  } 
 
}

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

int main(){
    int n,q;ll k;
    cin >> n >> k >> q;
    vector<int> a(n);
    rep(i,q){
        int b;cin >> b;
        b--;
        a[b]++;
    }
    rep(i,n){
        if(k - q + a[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
    
typedef long long ll;
typedef unsigned long long ull;
    
#define MOD 1000000007
#define mi 1000000000


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n],c[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    c[0]=0;
    for(int i=1;i<n;i++)
    {
        ull min=mi;
        for(int j=i-1;j>=0&&j>=i-k;j--)
        {
            if(abs(a[j]-a[i])+c[j]<min)
                min=abs(a[j]-a[i])+c[j];
        }
        c[i]=min;
    }
    cout<<c[n-1];
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {
	//i, j : カウント変数
	//len : 文字列の長さを格納
	//f : 真フラグを格納
	//c, d : 文字列sと文字列tのそれぞれのi番目の文字を格納
	//s[], t[] : 入力した文字列を格納
	int i, j, len;
	int f = 0;
	char c, d;
	char s[200001] = {}, t[200001] = {};
	
	//文字列をscanf
	scanf("%s%s", s, t);
	//lenに文字列の長さを格納
	if (strlen(s) == strlen(t)) f = 1;
	len = strlen(s);

	for (i = 0; i < len; i++) {
		//文字列sと文字列tのi番目の文字が一致するか
			//↓一致しなかった場合の処理（一致した場合は何もしない）
		if (s[i] != t[i]) {
			//c, d に文字列sと文字列tのi番目の文字を格納
			c = s[i];
			d = t[i];
			//文字列tを0からlenまで走査していき、cと一致していたらdと、dと一致していたらcと交換する
			for (j = 0; j < len; j++) {
				if (t[j] == c) {
					t[j] = d;
					//すでに交換した文字を再度交換した場合フラグを偽にする
					if (i > j) {
						f = 0;
						break;
					}
				} else if (t[j] == d) {
					t[j] = c;
					//すでに交換した文字を再度交換した場合フラグを偽にする
					if (i > j) {
						f = 0;
						break;
					}
				}
			}
		}
	}
	//結果の出力
	printf(f ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(ll i=0;i<(n);++i)
#define Fr(i,n) for(long long i=1;i<=(n);++i)
#define ifr(i,n) for(long long i=(n)-1;i>=0;--i)
#define iFr(i,n) for(long long i=(n);i>0;--i)

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long long  ans,b;
  int n;
  ll a;
  cin>>n;
  ll st[n]{};
  ll ed[n]{};
  fr(i,n){
    cin>>a>>b;
    st[i]=a;
    ed[i]=b;
  }
  if(n==1){
    cout<<b-a+1;
  }
  sort(st, st+n);
  sort(ed,ed+n);
  if(n%2==1){
    ans=ed[n-n/2-1]-st[(n-1)/2]+1;
  }
  else{
    ans=(ed[n-n/2-1]-st[n/2]+1)*2-1+(st[n/2]-st[n/2-1])+(ed[n-n/2]-ed[n-n/2-1]);
    
  }
  cout<<max(0ll,ans);
}

Measured memory_bytes: 6772
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lld;
 
#define forn(i,n) for(ll i = 0;i<n;i++)
#define forne(i,j,n) for(ll i = j;i<n;i++)
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ll INF = 3e18;
const ll N = 100001;
const lld PI = 3.141593;
#define F first
#define pb(a) push_back(a)
#define S second
#define pii pair<int,int>
typedef pair<ll,ll> pll;

int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

string s;
cin>>s;
if(s == "RSS") cout<<"1"<<endl;
else if(s == "RSR") cout<<"1"<<endl;
else if(s == "SRS") cout<<"1"<<endl;
else if(s == "SSR") cout<<"1"<<endl;
else if(s == "RRS") cout<<"2"<<endl;
else if(s == "SRR") cout<<"2"<<endl;
else if(s == "RRR") cout<<"3"<<endl;
else cout<<"0"<<endl;
}

Measured memory_bytes: 3652
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>  
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000000000000000000000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0) return 0;
		vector<double> input;
		double sum = 0;
		REP(i, n) {
			double a;
			cin >> a;
			input.push_back(a);
			sum += a;
		}
		sum /= (double)n;
		int ans = 0;
		REP(i, n) {
			if (input[i] <= sum) ans++;
		}
		cout << ans << endl;
	}
}



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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //N個
		int L = sc.nextInt(); //長さL
		
		String[] stvals = new String[N];
		for(int i=0;i<N;i++) {
			stvals[i] = sc.next();
		}
		Arrays.sort(stvals);
		for(String s:stvals) {
			System.out.print(s);
		}
		System.out.println();
		
		sc.close();
	}	

}

Measured memory_bytes: 21972
from collections import Counter
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

MOD = 998244353
N= int(input())
D = inpl()
C = Counter(D)

if (D[0] != 0) or (C[0] != 1):
    print(0)
else:
    M = max(C.keys())
    ans = 1
    for i in range(M):
        ans = ans * pow(C[i], C[i+1], MOD) % MOD
    print(ans)


Measured memory_bytes: 19864
#include <bits/stdc++.h>
using namespace std;
 
bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}
 
string s;
int me[26];
char da[30];
int co;


int main(){
    cin >> s;

    for(int i = 0; i < s.length(); i++){
        me[(int)(s[i]-'a')]++;
    }
    for(int i = 0; i < 26; i++){
        if(me[i] == 0){
            s += char(i+'a');
            cout << s << endl;
            return 0;
        }
    }

    char mem = s[s.length()-1];
    bool flag = false;
    for(int i = s.length()-1; i > 0; i--){
        if(s[i] > s[i-1]){
            if(flag){
                for(int j = 0; j < i-1; j++){
                    cout << s[j];
                }
                da[co] = s[i];
                co++;
                sort(da, da+co);
                for(int j = 0; j < co; j++){
                   // cout <<  j << ' ' << da[j] << endl;
                    if(s[i-1] < da[j]){
                        cout << da[j] << endl;
                        break;
                    }
                }
                return 0;
            }
            for(int j = 0; j < s.length()-2; j++)   cout << s[j];
            cout << s[s.length()-1] << endl;

            return 0;
        }
        if(s[i] < s[i-1]){
            da[co] = s[i];
            co++;
            flag = true;
        }
    }

    

    cout << "-1\n";
}

Measured memory_bytes: 256
package main

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

func main() {
	K := nextInt()
	S := nextString()

	if len(S) <= K {
		fmt.Println(S)
	} else {
		fmt.Printf("%s...\n", S[:K])
	}
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

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

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
const int Max=2e5+5;
int a[Max];
int main()
{
	int n;
	sc(n);
	map<int,int>fa;
	ll cou=0;
	rep(i,1,n){
		sc(a[i]);
		if(fa.count(i-a[i]))cou+=fa[i-a[i]];
		if(fa.count(i+a[i]))fa[i+a[i]]++;
		else fa[i+a[i]]=1;
	}
	pf("%lld\n",cou);
}


Measured memory_bytes: 13896
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){rep(i,vec.size())is>>vec[i];return is;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int N, K, C[2000], G[2000];

int dp[2001];

signed main()
{
    cin >> N >> K;

    vector<vi> T(10);

    rep(i, N) {
        cin >> C[i] >> G[i];
        -- G[i];
        T[G[i]].PB(C[i]);
    }

    rep(i, 10) {
        sort(all(T[i]), greater<int>());
        for (int j = 1; j < T[i].size(); ++j) {
            T[i][j] += T[i][j - 1] + 2 * j;
        }
    }

    rep(i, 10) {
        rrep(j, K + 1) {
            rep(k, T[i].size()) {
                if (j - k - 1 < 0) break;
                chmax(dp[j], dp[j - k - 1] + T[i][k]);
            }
        }
    }

    cout << dp[K] << endl;
}

Measured memory_bytes: 1296
n = int(input())
l = ['a','b','c','d','e','f','g','h','i','j']

def dfs(res,i):
    if len(res)==n:
        print(res)
        return
    for k in range(i):
        dfs(res+l[k],i)
    dfs(res+l[i],i+1)

dfs('',0)


Measured memory_bytes: 61656
c=[list(map(int,input().split())) for _ in range(3)]
a=[0]*3
b=[0]*3
for i in range(3):
    b[i]=c[0][i]-a[0]
for i in range(3):
    a[i]=c[i][0]-b[0]

for i in range(3):
    for j in range(3):
        if a[i]+b[j] != c[i][j]:
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 3064
// AtCoder ABC132: C - Divide the Problems
// 2019.9.3 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define MAX 100000
int d[MAX+3];

int cmp(const void *u, const void *v) { return *(int *)u - *(int *)v; }

int main()
{
	int i, k, N, ans;

	N = in(); for (i = 0; i < N; i++) d[in()]++;
	N >>= 1;
	k = 0; for (i = 0; k < N; i++) k += d[i];
	if (k > N) ans = 0;
	else {
		k = i-1; while (d[i] == 0) i++;
		ans = i-k;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 512
from itertools import combinations

N, K = map(int,input().split())
points = []
X = []
Y = []

for _ in range(N):
    x, y = map(int,input().split())
    points.append((x, y))
    X.append(x)
    Y.append(y)

X.sort()
Y.sort()

ans = float('inf')

for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = 0
        for point in points:
            if x1 <= point[0] <= x2 and y1 <= point[1] <= y2:
                cnt += 1
        if cnt >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Measured memory_bytes: 47488
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        StringBuilder nStr = new StringBuilder();
        int m = scn.nextInt();
        StringBuilder mStr = new StringBuilder();
        for(int i  = 0 ; i < n;i++){
            nStr.append(m) ;
        }
        for(int i = 0 ;i <m ; i ++) {
            mStr.append(n);
        }
        String[] arr = {nStr.toString(),mStr.toString()};
        Arrays.sort(arr);
        System.out.println(arr[0]);
    }
}


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


 
int main() {
//cin>>str;
//cout<<str<<endl;
  long long taka, nakaz, hiku, K;
  long long kaisuu;
  long long twa, nwa, hwa;
  
  cin>>taka>>nakaz>>hiku>>K;
  long long judge = 0;
  if(K%2 == 0){
    judge = taka - nakaz;
  }else{
    judge = nakaz - taka;
  }
  cout<<judge<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
void get_unique(vector<T>& x) {
    x.erase(unique(x.begin(), x.end()), x.end());
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uf.unite(a, b);
    }
    int ans = 0;
    rep(i, n) ans += i == uf.root(i);
    cout << ans - 1 << '\n';
}

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

bool b[ 11000 ];

int main( int argc, char *argv[] )
{
int i;
int j;
int N;
int s;
int iMax;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> N;

	iMax = 0;
	b[ 0 ] = true;
	for( i = 0; i < N; i++ )
	{
		cin >> s;
		for( j = iMax; j >= 0; j-- )
		{
			if( b[ j ] ) b[ j + s ] = true;
		}

		iMax += s;
	}

	for( j = iMax; j >= 0; j-- )
	{
		if( b[ j ] && ( j % 10 != 0 ) )
		{
			cout << j << endl;

			return 0;
		}
	}

	cout << 0 << endl;

	return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main() {
    int n, m; cin>> n >> m;
    ll a;
    priority_queue<ll> pq;
    rep(i, n){
        cin>> a;
        pq.push(a);
    }
    rep(i, m){
        int tmp = pq.top();
        pq.pop();
        tmp /= 2;
        pq.push(tmp);
    }

    ll ans = 0;
    rep(i, n){
        int tmp = pq.top();
        pq.pop();
        ans += tmp;
    }
    cout<< ans << endl;
}


Measured memory_bytes: 4228
package main

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

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

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var sum int
	m := make(map[int]int)
	as := make([]int, n)
	for i := range as {
		sc.Scan()
		as[i], _ = strconv.Atoi(sc.Text())
		m[as[i]]++
		sum += as[i]
	}

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())
	for i := 0; i < q; i++ {
		sc.Scan()
		b, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		c, _ := strconv.Atoi(sc.Text())
		if cnt, ok := m[b]; ok {
			m[b] = 0
			m[c] += cnt
			sum += (c - b) * cnt
		}
		fmt.Println(sum)
	}

}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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


Measured memory_bytes: 9364
import java.util.*;

public class Main {

    long INF = Long.MAX_VALUE;

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long M = sc.nextLong();
        String S = sc.next();
        String T = sc.next();
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        long g = gcd(N, M);
        long l = N / g * M;
        int n = (int) (N / g);
        int m = (int) (M / g);
        for (int i = 0; i < g; i++) {
            if (s[i * n] != t[i * m]) {
                System.out.println("-1");
                return;
            }
        }
        System.out.println(l);
    }

    long gcd(long m, long n) {
        if (m < n) {
            return gcd(n, m);
        }
        if (n == 0) {
            return m;
        }
        return gcd(n, m % n);
    }
}

Measured memory_bytes: 28372
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<unordered_set>

using namespace std;




vector<int> prime_sieve(int n)
{
    int* arr = new int[n+1];
    
    int i, p;
    for (i = 0; i <= n; ++i) {
        arr[i] = i;
    }
    for (i = 2; i <= n; ++i) {
        if (arr[i] != 0) {
            for (p = arr[i] * arr[i]; p <= n; p += arr[i]) {
                arr[p] = 0;
            }
        }
    }
    vector<int> primes;
    for (i = 2; i <= n; ++i) {
        if (arr[i] != 0) {
            primes.push_back(arr[i]);
        }
    }
    return primes;
}

int min(int a, int b)
{
    return a < b ? a : b;
}


int main()
{
    string str;
    cin >> str;
    int i, j;
    for (i = 0; i < str.length(); ++i) {
        if (str[i] == 'A') {
            break;
        }
    }

    for (j = str.length() - 1; j >= 0; --j) {
        if (str[j] == 'Z') {
            break;
        }
    }

    int length = (j - i) + 1;
    cout << length;
    
}


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

using namespace std;

typedef long long ll;

#define FOR(index, init, max) for (int index = (init); index < (max); index++)
#define REP(index, max) for (int index = 0; index < (max); index++)
#define FOREACH(x, array) for (auto&& (x) : array)
#define VECCIN(vec) for (auto&& vec_i : vec) cin >> vec_i
#define VECCOUT(vec) for (const auto& vec_i : vec) cout << vec_i << endl

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

    map<string, int> st;
    REP(n_i, n) {
        string tmp;
        cin >> tmp;
        st[tmp]++;
    }

    int m;
    cin >> m;
    REP(m_i, m) {
        string tmp;
        cin >> tmp;
        st[tmp]--;
    }

    int ans = 0;
    FOREACH(st_i, st) {
        ans = max(ans, st_i.second);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

    int a,b,c;
    int i,cnt = 0;

    scanf("%d %d %d",&a, &b, &c);
    for(i = a; i <= b; i++){
        if(c % i == 0){
            cnt++;
        }  
    }

    printf("%d\n",cnt);

    return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

double Q(double x){
  return x*x;
}

double dist(double x1,double y1,double x2,double y2){
  return sqrt(Q(x1-x2)+Q(y1-y2));
}

int main() {
  int n;
  cin>>n;
  vector<pair<int,int>> xy(n);
  for(int i=0;i<n;i++)cin>>xy[i].first>>xy[i].second;
  vector<int>p;
  for(int i=0;i<n;i++)p.push_back(i);
  double ans=0;
  int total=0;
  do{
    for(int j=0;j<n-1;j++){
      ans+=dist(xy[p[j]].first,xy[p[j]].second,
		xy[p[j+1]].first,xy[p[j+1]].second);
    }
    total++;
  }while(next_permutation(p.begin(),p.end()));
  cout<<fixed<<setprecision(20)<<ans/total;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI (acos(-1))
#define ct cout<<
#define cn cin>>
#define spc <<" "<<
#define nl puts("")
#define _fl(x) puts("FLAG " #x);
#define  _(x)  cout<< #x <<" is "<< x <<endl;
#define fs first
#define sc second
#define pb push_back
#define all(v)  (v).begin(), (v).end()
#define _109 (1000000000)
#define _0(arr) memset(arr,0,sizeof ( arr ) )
#define _1(arr) memset(arr,-1,sizeof ( arr ) )
#define _ninp(n,arr) for(int i=0; i<n;i++)cin>>arr[i];
#define _nout(n,arr) for(int i=0; i<n;i++)cout<<arr[i]<<" \n"[i==n-1];
double _eps=1e-6;
long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {

    int n,m;
    cn n>>m;

    if(n==m)ct "Yes";
    else ct "No";
    nl;







    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int n, m, d;

    scanf("%d %d", &n, &m);

    for(d=m/n; d>=1; d--)
    {
        if(m%d==0 && n<=m/d)
        {
            printf("%d\n",d);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 128
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro split-and-bind (arg-lst string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str (gensym "STR")))
    (labels ((expand (arg-lst &optional (init-pos1 t))
	       (if (null arg-lst)
		   body
		   `((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			    (,pos2 (position #\space ,str :start ,pos1 :test #'char=))
			    (,(car arg-lst) (parse-integer ,str :start ,pos1 :end ,pos2)))
		       ,@(expand (cdr arg-lst) nil))))))
      `(let ((,str ,string))
         (declare (string ,str))
	 ,@(expand arg-lst)))))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

;; Hauptteil

(defun main ()
  (let* ((n (read))
         (m (read))
         (p-table (make-array (list (1+ n)) :element-type 'list :initial-element nil))
         (city-table (make-array (list m) :element-type 'list :initial-element nil)))
    ;; node := (prefecture year version)
    (dotimes (city-idx m)
      (split-and-bind (prefecture year) (read-line)
        (let ((node (list prefecture year)))
          (push node (aref p-table prefecture))
          (setf (aref city-table city-idx) node))))
    (loop for p-idx from 1 to n
          do (setf (aref p-table p-idx)
                   (sort (aref p-table p-idx) #'< :key #'second))
             (loop for node in (aref p-table p-idx)
                   for version from 1
                   do (setf (cddr node) version)))
    (dotimes (city-idx m)
      (format t "~6,'0D~6,'0D~%"
              (car (aref city-table city-idx))
              (cddr (aref city-table city-idx))))))

#-swank(main)


Measured memory_bytes: 66664
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b) { return *(int *)a - *(int *)b; }                            /* 1,2,3,4.. */
int des(const void *a, const void *b) { return *(int *)b - *(int *)a; }                            /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { return *(char *)a - *(char *)b; }                     /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) { return strcmp(*(const char **)a, *(const char **)b); } /* aaa,aab.. */
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

int main(void)
{
  int n, m, lr[100001][2];
  scanf("%d %d", &n, &m);

  int i;
  for (i = 0; i < m; i++)
  {
    scanf("%d %d", &lr[i][0], &lr[i][1]);
  }

  int first = 1, last = n;
  for (i = 0; i < m; i++)
  {
    first = max(lr[i][0], first);
    last = min(lr[i][1], last);
    if (first > last)
      break;
  }

  printf("%d\n", max(last - first + 1, 0));
  return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mxn= 1e5+5;
// check for forloop
// intialize variable
// overflow
// go for easy solution
#define mod 1000000007
ll INF = 1000000000000000005LL;
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main(){
    rishabh();
    ll n;
    cin>>n;
    cout<<((n-1)*n)/2;
}

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

// ----- BIT -----
// referring to http://hos.ac/slides/20140319_bit.pdf

template <typename T>
class BIT
{
  int N;
  vector<T> data;

public:
  BIT() {}
  BIT(int N) : N{N}, data(N + 1) {}

  void add(int i, T w) // data[i] += w;
  {
    for (; i < N; i |= i + 1)
    {
      data[i] += w;
    }
  }

  void update(int i, T w) // data[i] = w;
  {
    add(i, w - (*this)[i]);
  }

  T sum(int l, int r) // data[l] + \dots + data[r - 1]
  {
    return sum(r) - sum(l);
  }

  T operator[](int i) // data[i]
  {
    return sum(i, i + 1);
  }

private:
  T sum(int i) // data[0] + \dots + data[i - 1]
  {
    T res{0};
    for (--i; i >= 0; i = (i & (i + 1)) - 1)
    {
      res += data[i];
    }
    return res;
  }
};

int main()
{
  int N;
  cin >> N;
  BIT<long long> tree{N};
  int Q;
  cin >> Q;
  for (auto q{0}; q < Q; ++q)
  {
    int t;
    cin >> t;
    if (t == 0)
    {
      int k, x;
      cin >> k >> x;
      --k;
      tree.add(k, x);
    }
    else
    {
      int s, t;
      cin >> s >> t;
      --s;
      --t;
      cout << tree.sum(s, t + 1) << endl;
    }
  }
}



Measured memory_bytes: 3500
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <list>
using namespace std;

int n = 0, x = 0, y = 0, ans[10000] = {}, loopPaths[10000] = {}, loopLength = 0, straightLength = 0;

int main() {
	cin >> n >> x >> y;

	loopLength = y - x + 1;
	straightLength = n - loopLength + 2;

	for (int i = 1; i <= loopLength / 2; i++) {
		if (loopLength % 2 == 0 && i == loopLength / 2) {
			loopPaths[i] = loopLength / 2;
		}
		else {
			loopPaths[i] = loopLength;
		}

		if (i == 1) {
			loopPaths[i]--;
		}

		ans[i] = loopPaths[i];
	}

	for (int i = 1; loopPaths[i] > 0; i++) {
		if (loopPaths[i] == loopLength) {
			for (int j = 1; j < x; j++) {
				ans[i + x - j] += 2;
			}

			for (int j = y + 1; j <= n; j++) {
				ans[i + j - y] += 2;
			}
		}
		else {
			for (int j = 1; j < x; j++) {
				ans[i + x - j] += 1;
			}

			for (int j = y + 1; j <= n; j++) {
				ans[i + j - y] += 1;
			}
		}
	}

	for (int i = 1; i < straightLength; i++) {
		ans[i] += straightLength - i;
	}

	for (int i = 1; i <= n - 1; i++) {
		cout << ans[i] << "\n";
	}

	return 0;
}


Measured memory_bytes: 256
INF=10000050

N,M,X=map(int,input().split())

A=[]
C=[]
for i in range(N):
    array=list(map(int,input().split()))
    C.append(array[0])
    A.append(array[1:])

combination=[i for i in range(2**N)]

min_price=INF

for i in range(2**N):
    price=0
    knowledge=[0 for i in range(M)]
    for j in range(N):
        if combination[i]%(2**(j+1)):
            price+=C[j]
            for k in range(M):
                knowledge[k]+=A[j][k]
            combination[i]-=2**j
    if min(knowledge)>=X:
        min_price=min(min_price,price)

if min_price==INF:
    print("-1")
else:
    print(min_price)


Measured memory_bytes: 9308
#include<stdio.h>
int m[]={5,1,2,4,1,3,1,0,0,2,3,2,2,4,5,1,4,0,4,3,3,5,0,5};
char s[99];
int main(){s[87]=1;s[78]=4;s[69]=3;s[83]=2;for(int a,b,c,n,r,d;b=r=scanf("%d",&n),n;printf("%d\n",r)){for(a=c=0;n--;r+=a%3?b%3?(b+6-a)%6<3?2:5:b?3:4:a?6:1){scanf("%s",s);d=s[*s];d?d=d+c&3,a=m[4*a+d],b=m[4*b+d]:c+=*s-76?1:3;}}}

Measured memory_bytes: 0
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int P=139;
const int mod=149;
const int maxn=1e6+5;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int minn=0xc0c0c0c0;
int a[maxn],b[maxn];
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
	{
        int x,y;
        cin>>x>>y;
        a[i]=x+y;
        b[i]=x-y;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    cout<<max(a[n]-a[1],b[n]-b[1])<<endl;
    return 0;
}

Measured memory_bytes: 5188
def solve():
    
    x, k, d = map(int, input().split())

    if x > 0:

        if x >= d:
            steps = min(k, x // d)
            k -= steps
            x -= steps * d

        if x > 0 and x < d:
            if k % 2 == 0:
                print(x)
            else:
                print(abs(x - d))

            return
    
    if x < 0:
        if  x <= -d:
            steps = min(k, -x // d)
            k -= steps
            x += steps * d

        if x > -d and x < 0:
            if k % 2 == 0:
                print(abs(x))
            else:
                print(x + d)

            return

    if x == 0:
        if k % 2 == 0:
            print(0)
        else:
            print(d)
        
        return


    print(abs(x))

solve()

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

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

using namespace std;

int n, m;

int main(){
    cin >> n >> m;
    int x = n * 100 + m * 1800;
    rep(i, m){
        x <<= 1;
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
//basic c++ code is given here

#include<bits/stdc++.h>

using namespace std;


    int main (  )
    {
      long long  n;
        vector < char > v;
      cin >> n;
      
    while(n--){
        char k = 'a' + n%26;
        n = n/26 ;
    v.push_back(k);

    }
    for(int i = v.size()-1 ; i >= 0 ;i--){
        cout << v[i] ;
    }
    }


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
#define maxn 100020
#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define pb push_back
#define prev prev_
#define stack stack_
#define inf 0x3f3f3f3f

int a[maxn],mx[2],mx2[2],cnt[2],cnt2[2],num[2][maxn];
int n;

int main(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&a[i]);
		int t = i & 1;
		num[t][a[i]]++;
	}
	int lim = 1e5;
	rep(t,0,1){
		rep(i,1,lim){
			if ( cnt[t] < num[t][i] ) cnt2[t] = cnt[t] , mx2[t] = mx[t] , mx[t] = i , cnt[t] = num[t][i];
			else if ( cnt2[t] < num[t][i] ) cnt2[t] = num[t][i] , mx2[t] = i;
		}
	}
	if ( mx[0] == mx[1] ){
		cout<<n - max(cnt[0] + cnt2[1],cnt2[0] + cnt[1])<<endl;
	}
	else cout<<n - cnt[0] - cnt[1]<<endl;
}


Measured memory_bytes: 1408
from functools import reduce
import math
import collections
def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    s = collections.defaultdict(int)
    for i in range(N):
        s[input()] += 1
    M = int(input())
    for i in range(M):
        s[input()] -= 1
    print(max(max(s.values()),0))
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#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 REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
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 gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main() {
  INIT;
	VAR(int,h,w);
  VEC(string,s,h);

  bool ok = true;
  REP(hi,h){
    REP(wi,w){
      if (s[hi][wi] != '#') continue;
      if(hi+1<h && wi-1>=0)ok &= s[hi+1][wi-1] == '.';
      if(wi+1<w && hi-1>=0)ok &= s[hi-1][wi+1] == '.';
    }
  }
  cout<<(ok?"Possible":"Impossible")<<endl;
  
  return 0;
}


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	int n, k;
	cin >> s >> k;
	n = s.size();
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(4, vector<int>(2, 0)));
	dp[0][k-1][0] = s[0]-'0'-1;
	dp[0][k-1][1] = 1;
	for(int i=1; i<n; ++i){
		dp[i][k-1][0] = 9;
		for(int j=0; j<k; ++j){
			if(s[i] == '0'){
				dp[i][j][1] += dp[i-1][j][1];
				dp[i][j][0] += dp[i-1][j][0];
			}else{
				dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1];
			}
		}
		for(int j=1; j<=9; ++j){
			if(j == s[i]-'0'){
				for(int l=0; l<k; ++l){
					dp[i][l][1] += dp[i-1][l+1][1];
					dp[i][l][0] += dp[i-1][l+1][0];
				}
			}else if(j < s[i]-'0'){
				for(int l=0; l<k; ++l)
					dp[i][l][0] += dp[i-1][l+1][0] + dp[i-1][l+1][1];
			}else{
				for(int l=0; l<k; ++l)
					dp[i][l][0] += dp[i-1][l+1][0];
			}
		}
	}
	cout << dp[n-1][0][0] + dp[n-1][0][1] << "\n";
//	for(int i=0; i<n; ++i)
//		for(int j=0; j<k; ++j)
//			cout << i << " " << j << " : " << dp[i][j][0] << " " << dp[i][j][1] << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main(){

	int left,right,l_count,r_count;
	char buf[100001],pre;

	while(true){
		scanf("%s",buf);
		if(buf[0] == '#')break;

		l_count = 0;
		left = buf[0] - '0';
		if(left % 3 != 0){
			right = 3;
		}else{
			if(left == 3){
				right = 6;
			}else{
				right = 3;
			}
		}
		pre = 'l';

		for(int i = 1; buf[i] != '\0'; i++){
			if((left%3 == 0 && (buf[i] - '0')%3 > 0) || (left%3 == 2 && (buf[i] - '0')%3 == 1)){
				if(pre == 'l')l_count++;
				left = buf[i] - '0';
				pre = 'l';
			}else if((right % 3 == 1 && (buf[i] - '0')%3 != 1) || (right % 3 == 2 && (buf[i] - '0')%3 == 0)){
				if(pre == 'r')l_count++;
				right = buf[i] - '0';
				pre = 'r';
			}else{
				if(pre == 'l'){
					right = buf[i] - '0';
					pre = 'r';
				}else{
					left = buf[i] - '0';
					pre = 'l';
				}
			}
		}

		r_count = 0;
		right = buf[0] - '0';
		if(right % 3 != 1){
			left = 1;
		}else{
			if(right == 1){
				left = 4;
			}else{
				left = 1;
			}
		}
		pre = 'r';
		for(int i = 1; buf[i] != '\0'; i++){
			if((left%3 == 0 && (buf[i] - '0')%3 > 0) || (left%3 == 2 && (buf[i] - '0')%3 == 1)){
				if(pre == 'l')r_count++;
				left = buf[i] - '0';
				pre = 'l';
			}else if((right % 3 == 1 && (buf[i] - '0')%3 != 1) || (right % 3 == 2 && (buf[i] - '0')%3 == 0)){
				if(pre == 'r')r_count++;
				right = buf[i] - '0';
				pre = 'r';
			}else{
				if(pre == 'l'){
					right = buf[i] - '0';
					pre = 'r';
				}else{
					left = buf[i] - '0';
					pre = 'l';
				}
			}
		}

		printf("%d\n",min(l_count,r_count));

	}

    return 0;
}

Measured memory_bytes: 2792
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        if (x >= 0 && x <= 100) {
            int answer = x*x*x;
            System.out.println(answer);
        }
    }
}


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

ll count = 1;

int pekojun(ll q) {
  if(q == 1) {
    ++count;
    return 0;
  }
  ll a;
  a = q / 2;
  pekojun(a);
  count = count * 2;
}

  
int main(){
  ll H;
  cin >> H;
  pekojun(H);
  cout <<  count - 1;
}


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

using namespace std;

long long eulerPhi(long long n) {
    if (n == 0) return 0;
    long long res = n;
    for (long x = 2; x * x <= n; ++x) {
        if (n % x == 0) {
            res -= res / x;
            while (n % x == 0) n /= x;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}


int main() {
    long long n;
    cin >> n;

    cout << eulerPhi(n) << endl;
    return 0;
}


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

typedef long long LL;
const int mN = 3113;
const LL oo = 1e18;
LL a[mN], f[mN][mN][2];

void update(LL &var, LL val, int opt) {
    if (opt) var = max(var, val);
    else var = min(var, val);
}

LL dp(int l, int r, const LL t) {
    if (f[l][r][t] != -oo) return f[l][r][t];
    if (l == r) return f[l][r][t] = t * a[l];
    LL ans = oo;
    if (t) ans *= -1LL;
    update(ans, dp(l+1, r, 1-t) + t*a[l], t);
    update(ans, dp(l, r-1, 1-t) + t*a[r], t);
    //cerr << "f[" << l << "][" << r << "][" << t << "] = " << ans << "\n";
    return f[l][r][t] = ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
    cin >> n;
    LL sum = 0;
    for (int i=1; i<=n; i++) cin >> a[i], sum += a[i];
    for (int i=0; i<=n; i++)
        for (int j=0; j<=n; j++)
            f[i][j][0] = f[i][j][1] = -oo;
    LL taro_point = dp(1,n, 1LL);
    LL jiro_point = sum - taro_point;
    cout << taro_point - jiro_point;
    return 0;
}


Measured memory_bytes: 147968
#include <stdio.h>
#define max 100000

int z[100010];

int main(){

    int a,b,c,n,q,i;

    scanf("%d",&n);

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

    for(i=1;i<=max;i++){
        ans += i*z[i];
    }

    scanf("%d",&q);

    for(i=0;i<q;i++){
        scanf("%d %d", &b, &c);

        ans += z[b]*c - z[b]*b;
        
        z[c] += z[b];
        z[b] = 0;    
        
        printf("%ld\n",ans);
    }
    

    return 0;

}

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

int main()
{
	int N;
	cin >> N;
	vector<pair<int, int>> a( N );
	for( int i = 0; i < N; i++ ) {
		int A;
		cin >> A;
		a[i] = make_pair( A, i + 1 );
	}

	sort( a.begin(), a.end() );
	for( int i = 0; i < N; i++ ) {
		if( i ) cout << " ";
		cout << a[i].second;
	}
	cout << endl;
}


Measured memory_bytes: 1536
# 要は全員自由色のパターンを見落としていた
# もし自由色がいて、かつ、固定色が0人の場合、最小のパターンは1
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))


col = []  # boolean
for rate in range(0, 3200, 400):
    if len(A[(rate <= A) & (A < (rate + 400))]) is not 0:
        col.append(True)
    else:
        col.append(False)

jiyu = len(A[(3200 <= A)])  # 自由枠

assert len(col) == 8

# min
mi = sum(col)
# max
ma = mi + jiyu

# 以下を見落としていた
if (mi is 0) and (jiyu is not 0):
    mi = 1

print("{} {}".format(mi, ma))


Measured memory_bytes: 13220
#include<cstdio>
using namespace std;
long long n,m,x,y,dp[100010];
long long maxn(long long a,long long b){
	return a>b?a:b;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x,&y);
		for(int j=m;j>=x;j--)dp[j]=maxn(dp[j],dp[j-x]+y);
	}
	long long ans=0;
	for(int i=0;i<=m;i++)ans=maxn(ans,dp[i]);
	printf("%lld",ans);
}

Measured memory_bytes: 896