akhauriyash/Code-Regression huggingface dataset:
// F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500500;

int n, m, dfn[MAX_N], level[MAX_N], low[MAX_N];
vector<int> G[MAX_N];

void dfs(int v, int l = 0)
{
    dfn[v] = 1, level[v] = l;
    low[l] = v;
    int pt = -1;
    for (int i = 0, siz = G[v].size(); i < siz; i++)
    {
        int to = G[v][i];
        if (dfn[to] == 1 && (pt == -1 || level[pt] < level[to]))
            pt = to;
    }

    if (pt != -1)
    {
        set<int> ret;
        ret.insert(pt);
        for (int i = l; low[i] != pt; i--)
            ret.insert(low[i]);
        int cnt = 0;
        for (int u : ret)
            for (int to : G[u])
                if (ret.count(to))
                    cnt++;

        if (cnt == ret.size())
        {
            cout << cnt << endl;
            for (int u : ret)
                cout << u << endl;
            exit(0);
        }
    }

    for (int i = 0, siz = G[v].size(); i < siz; i++)
    {
        int to = G[v][i];
        if (dfn[to] == 0)
            dfs(to, l + 1);
    }
    dfn[v] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), G[u].push_back(v);
    for (int i = 1; i <= n; i++)
        dfs(i, 0);
    puts("-1");
    return 0;
}

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

using namespace std;

#ifdef LOCAL
#define err cerr
#else
#define err if (false) cerr
#endif

typedef long long ll;

const int MAXN = 55;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n; cin >> n;
    if (n % 2 == 1)
    {
        cout << 0; return 0;
    }
    n /= 2;
    ll ans = 0;
    while (n > 0)
    {
        ans += n / 5;
        n /= 5;
    }
    cout << ans;
}


Measured memory_bytes: 256
S = input()
K = int(input())
a = []
for i in range(len(S)+1):
    for j in range(1,6):
        if i+j <= len(S):
            a.append(S[i:i+j])
        else:
            break
            
a = list(set(a))
a.sort()
print(a[K-1])

Measured memory_bytes: 5068
#include <iostream>

int main()
{
    int N, H[100];
    std::cin >> N;

    for (int i = 0; i < N; ++i)
    {
        std::cin >> H[i];
    }

    int ans = 0;

    for (int i = 0; i < N; ++i)
    {
        bool visible = true;
        for (int j = 0; j < i; ++j)
        {
            if (H[i] < H[j])
            {
                visible = false;
                break;
            }
        }

        if (visible)
        {
            ans++;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
suuretsu = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
number = int(input(''))
print(suuretsu[number - 1])

Measured memory_bytes: 3060
#include <stdio.h>
int main() {
	int a, b, c, r;
	scanf("%d%d%d", &a, &b, &c);
	if (b >= c)r = b + c;
	else {
		r = 2 * b;
		if (c - b > a)r += a + 1;
		else r += c - b;
	}
	printf("%d", r);
	return 0;
}




Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 998244353
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, S = read_ints()
A = read_ints()

# 包除？
# もしピッタリSを作ることのできる部分集合をかぶりなく複数構成できるとすると、その組み合わせを計算すればよい
# 求めたいものは→Sの部分和問題。なるべく細かく。背反に構成。
# 部分和復元してまた部分和？
# 3000*3000だから複数回DPはTLE

# 一回部分和を解いて、復元するときに分岐の数のを掛ければいいのでは？ #むしろ掛け算をDPするときにしちゃえばいいのでは？


# 1回部分和DPする
'''
dp[i][j]...[,i)の数の中の部分集合で、和をjにすることのできる通りの総数

使う可能性のあるものを全列挙できたらいいなぁ
'''

dp = [[0] * (S + 1) for _ in ra(N + 1)]
dp[0][0] = 1
for i, j in product(ra(N), ra(S + 1)):
    dp[i + 1][j] = 2 * dp[i][j]
    if j - A[i] >= 0:
        dp[i + 1][j] += dp[i][j - A[i]]
    dp[i + 1][j] %= MOD

# print(*dp, sep='\n')
print(dp[-1][-1])


Measured memory_bytes: 139848
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int main(){
    int n; cin >> n;
	vector<int> A(n + 1);
    for(int i = 1; i < n; i++){
    	int x; cin >> x;
      	A[x]++;
    }
    for(int i = 1; i <= n; i++){
    	cout << A[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4048
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

#define DEBUG 0

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

using namespace std;

string calc(lli num){
	string str="";

	while(num!=0){
		if(DEBUG)cout<<"num="<<num<<endl;
		lli flag=0;
		if(num < 0){
			if(num%2==0){
				num /= (-2);
			}
			else{
				flag = 1;
				num /= (-2);
				num += 1;
			}
		}
		else{
			flag = num % 2;
			num /= (-2);
		}
		if(flag){
			str = "1"+str;
		}
		else{
			str = "0"+str;
		}
	}
	if(str==""){
		str = "0";
	}
	return str;
}


int main(){

	lli num;
	cin>>num;

	cout<<calc(num)<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    if(s[0] == s[1] && s[1] == s[2]) puts("Yes");
    else if(s[1] == s[2] && s[2] == s[3]) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 384
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(n):
    l = (bisect.bisect_left(a,b[i]))*(n-bisect.bisect_right(c,b[i]))
    ans += l
print(ans)

Measured memory_bytes: 23092
import numpy as np

sa = str(input())
lena = len(sa)
sb = str(input())
lenb = len(sb)
sc = str(input())
lenc = len(sc)

i = 0
ia = 0
ib = 0
ic = 0

while True:
  if i ==0:
    marker = sa[ia]
    i+=1
    ia+=1
  else:
    if marker == 'a':
      if ia == lena:
        ans ='A'
        break
      marker = sa[ia]
      ia +=1
    elif marker =='b':
      if ib == lenb:
        ans ='B'
        break
      marker = sb[ib]
      ib +=1
    elif marker =='c':
      if ic == lenc:
        ans ='C'
        break
      marker = sc[ic]
      ic +=1

    
    
print(ans)
    
    

Measured memory_bytes: 12504
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
using namespace std;
int MOD = 1e9 + 7;

int N;
typedef pair<int, int> pii;   //自分、親
vector<vector<int>> G;   //グラフ
vector<pii> order;

void setorder() {
	vector<bool> check;
	check.resize(N, false);   //来た->true
	queue<pii> st;
	st.push(pii(0,-1));
	while (!st.empty()) {
		pii cur = st.front();
		st.pop();
		check[cur.first] = true;
		order.push_back(cur);
		for (int next : G[cur.first]) {
			if (check[next])continue;
			st.push(pii(next, cur.first));
		}
	}
}

int main() {
	cin >> N;
	G.resize(N);
	for (int n = 0; n < N - 1; n++) {
		int u, v;
		cin >> u >> v;
		G[--u].push_back(--v);
		G[v].push_back(u);
	}
	setorder();
	vector<long long> DP[2];
	DP[0].resize(N, 1);
	DP[1].resize(N, 1);
	for (int ord = N - 1; ord >= 0; ord--) {
		pii cur = order[ord];
		//葉っぱの場合
		if (G[cur.first].size() == 1 && G[cur.first][0] == cur.second) {
			DP[0][cur.first] = 1;
			DP[1][cur.first] = 1;
		}
		if (cur.second == -1)continue;
		DP[0][cur.second] *= (DP[0][cur.first]+DP[1][cur.first]);
		DP[1][cur.second] *= (DP[0][cur.first]);
		DP[0][cur.second] %= MOD;
		DP[1][cur.second] %= MOD;
	}
	cout << (DP[0][0] + DP[1][0]) % MOD << endl;
	return 0;
}

Measured memory_bytes: 9076
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

ll dp[10001][2][100] = {};

int main() {
  string k;
  int d;
  cin >> k;
  cin >> d;
  int n = k.length();

  dp[0][0][0] = 1;
  REP(_i, n) {
    int i = _i + 1;
    int D = k[_i] - '0';
    REP(j, d) {
      REP(digit, D) {
        dp[i][1][(j + digit) % d] =
            (dp[i][1][(j + digit) % d] + dp[i - 1][0][j]) % MOD;
      }
      REP(digit, 10) {
        dp[i][1][(j + digit) % d] =
            (dp[i][1][(j + digit) % d] + dp[i - 1][1][j]) % MOD;
      }
      dp[i][0][(j + D) % d] = (dp[i][0][(j + D) % d] + dp[i - 1][0][j]) % MOD;
    }
  }

  cout << (dp[n][1][0] + dp[n][0][0] - 1 + MOD) % MOD << endl;
}


Measured memory_bytes: 15872
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include <queue>
#include <stack>
#include<set>
#include<algorithm>
#include<stdio.h>

using namespace std;
int main() {

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int i = 0;
	while (a > 0 && c > 0)
	{
		if (i % 2 == 0)
			c -= b, i++;
		else
			a -= d, i++;
	}
	if (min(a, c) == a)
		cout << "No";
	else cout << "Yes";
	

		return 0;
}
	




Measured memory_bytes: 3636
import sys
import itertools

def resolve(in_):
    A = tuple(map(int, itertools.chain.from_iterable(line.split() for line in itertools.islice(in_, 3))))
    assert len(A) == 9
    C = [False] * 9
    N = int(next(in_))
    # B = tuple(map(int, itertools.islice(in_, N)))
    B = frozenset(map(int, itertools.islice(in_, N)))

    for i, a in enumerate(A):
        if a in B:
            C[i] = True
    # print(f'{A=} {C=}')

    b = any(all(line) for line in itertools.chain(
        ((C[i * 3], C[i * 3 + 1], C[i * 3 + 2]) for i in range(3)),
        ((C[i], C[i + 3], C[i + 6]) for i in range(3)),
        ((C[0], C[4], C[8]), (C[2], C[4], C[6])),
    ))
    return 'Yes' if b else 'No'


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9228
#include<bits/stdc++.h>
#define int long long
#define rep(i,m,n) for(int i=m;i<n;i++)
#define repr(i,n,m) for(int i=n;i>=m ;i--)
#define mod 1000000007
#define float long double
#define pb push_back
#define mp make_pair
#define print(v1) rep(i,0,v1.size()){cout<<v1[i]<<" ";} cout<<"\n";
using namespace std;
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
int modulo(int n,int m=1000000007){
    if(n<0){
        return (m-abs(n)%m)%m;
    }
    else return n%m;
}
void solve()
{ 
    string s,t;
    cin>>s>>t;
    int mini=INT_MAX,total=0;
    int n1=s.size(),n2=t.size();
    rep(i,0,n1-n2+1){
      total=0;
      rep(j,0,n2){
        if(t[j]!=s[j+i]){
            total++;
        }
      }
      if(mini>total)
      {
        mini=total;
        // cout<<mini<<"\n";
      }
      // cout<<total<<"\n";
    }cout<<mini;
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   // #ifndef ONLINE_JUDGE
   // freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
   // #endif
   int t=1;
   //cin>>t;
   while(t--)
   {
      solve();
      cout<<"\n";
   }
   cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
  return 0;
 }

Measured memory_bytes: 3796
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value != 0>::type
fill_v(U& u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value == 0>::type
fill_v(U& u, const V... v) { for (auto& e : u) fill_v<T>(e, v...); }
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 (a > b) { a = b; return 1; } return 0; }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vi P(N);
	REP(i, N) {
		cin >> P[i];
	}
	int ind = -1;
	REP(i, N) {
		if (P[i] != i + 1) {
			if (ind == -1) {
				ind = i;
			}
			else if(ind == -2){
				cout << "NO" << endl;
				return 0;
			}
			else {
				swap(P[i], P[ind]);
				ind = -2;
			}
		}
	}
	REP(i, N) {
		if (P[i] != i + 1) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1000000000;

int main(){
    int h,w;cin >> h >> w;
    char s[h][w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> s[i][j];
        }
    }
    vector<vector<LL>> dp(h,vector<LL>(w,0));
    for (int i = 0; i < h; i++) {
        if(s[i][0]=='#') break;
        dp[i][0]=1;
    }
    for (int i = 0; i < w; i++) {
        if(s[0][i]=='#') break;
        dp[0][i]=1;
    }
    for (int i = 1; i < h; i++) {
        for (int j = 1; j < w; j++) {
            if(s[i][j]=='#') continue;
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}



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

int main(){
	int n,cnt,a;
	cin>>n;
	
	for(int i=0;pow(10,i)<=n;i+=2){
		a=pow(10,i);
		for(int j=a;j<pow(10,i+1)&&j<=n;j++){
			cnt++;
		}
	}
	cout<<cnt<<'\n';
	return 0;
}


Measured memory_bytes: 512
#define dbg(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define dpri(x) dbg(#x ": %d\n", x)
#define dprs(x) dbg(#x ": %s\n", x)
#include <stdio.h>
typedef long long ll;
const int MYINF = 1e9+7;

#define STKSZ 20480

typedef struct {
	int stk[STKSZ];
	int idx;
} stack_t;

void push(stack_t *s, int x) {
	s->stk[s->idx++] = x;
}

int pop(stack_t *s) {
	if (s->idx == 0) return -1;
	return s->stk[--s->idx];
}

int peek(stack_t *s) {
	if (s->idx == 0) return -1;
	return s->stk[s->idx - 1];
}

int empty(stack_t *s) {
	return s->idx == 0;
}

stack_t slope_stk;
stack_t lakes_left_stk;
stack_t lakes_capa_stk;
stack_t *slope = &slope_stk;
stack_t *lleft = &lakes_left_stk;
stack_t *lcapa = &lakes_capa_stk;

void merge(int newleft, int adding) {
	int l, c, sum;
	sum = adding;
	while (!empty(lleft)) {
		l = peek(lleft);
		c = peek(lcapa);
		if (newleft < l) {
			sum += c;
			pop(lleft);
			pop(lcapa);
		} else break;
	}
	push(lleft, newleft);
	push(lcapa, sum);
}

int main(int argc, char **argv)
{
	int c, xpos, left, potion, k, sum;

	xpos = 0;
	while ((c = getchar()) != EOF) {
		if (c == '\\') {
			push(slope, xpos);
		} else if (c == '/') {
			left = pop(slope);
			if (left == -1) continue;
			potion = xpos - left;
			merge(left, potion);
		}
		xpos++;
	}

	while (!empty(lleft)) pop(lleft); // for reuse
	sum = k = 0;
	while (!empty(lcapa)) {
		k++;
		c = pop(lcapa);
		sum += c;
		push(lleft, c);
	}
	printf("%d\n%d", sum, k);
	while (!empty(lleft)) {
		printf(" %d", pop(lleft));
	}
	putchar('\n');

	return 0;
}

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

int main() {
    string str, order, p;
    int q, a, b;
    cin >> str >> q;
    rep(i, q) {
        cin >> order >> a >> b;
        if(order == "print") {
            cout << str.substr(a, b - a + 1) << endl;
        } else if(order == "replace") {
            cin >> p;
            str.replace(a, b - a + 1, p);
        } else if(order == "reverse") {
            p = str.substr(a, b - a + 1);
            reverse(p.begin(), p.end());
            str.replace(a, b - a + 1, p);
        }
    }
}


Measured memory_bytes: 3232
#include <iostream>
using namespace std;
int main()
{
    // スペース区切りの整数の入力
    int p,q,r;
    cin >> p >> q >> r;
    
    int a = p + q;
    int b = p + r;
    int c = q + r;
    
    if (a < b && a < c) {
      cout << a << endl; 
    } else if (b < c) {
      cout << b << endl;
    } else {
      cout << c << endl;
    }
  
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
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; }
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
ll keta(ll a){
    ll res = 0;
    while(a > 0){
        res += a%10;
        a /= 10;
    }
    return res;
}
int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    ll ans = 0;
    rep(i,1,n+1){
        if (a <= keta(i) && keta(i) <= b) ans += i;
    }
    PRINT(ans);
}

Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

struct ZAlgorithm
{
	std::vector<int> z;
	ZAlgorithm(const std::vector<int>& s) : z(s.size(),0) {
		int n = s.size();
		int l=0,r=0;
		z[0] = n;
		for(int i=1;i<n;i++) {
			z[i] = std::max((int)0, std::min(z[i-l], r-i+1));
			while(i+z[i]<n && s[z[i]] == s[i+z[i]]) {
				l=i; r=i+z[i]; z[i]++;
			}
		}
	}
};

std::vector<int> KMP(std::vector<int> s, std::vector<int> w) {
	// first create table for w
	ZAlgorithm z(w);
	std::vector<int> t(w.size()+1,0);
	t[0]=-1;
	for(int i=1;i<w.size();i++) {
		if(z.z[i]>0) {
			t[i+z.z[i]]=std::max(t[i+z.z[i]],z.z[i]);
			t[i]=-1;
		}
	}
	// search over s (mod)
	std::vector<int> ans;
	int k=0;
	for(int i=0;i<w.size()&&k<s.size();) {
		debug(i,k);
		if(w[i]==s[(k+i)%s.size()]) i++;
		else {
			k=k+i-t[i];
			if(t[i]>=0) i=t[i];
			else i=0;
		}
		debug(i,k);
		if(i==w.size()) {
			ans.emplace_back(k);
			k=k+i-t[i];
			i=t[i];
		}
	}
	return ans;
}

signed main() {
	int n;
	std::cin >> n;
	std::vector<int> a(n),b(n);
	rep(i,n) std::cin >> a[i];
	rep(i,n) std::cin >> b[i];
	std::vector<int> w(n),s(n);
	rep(i,n) s[i] = a[i]^a[(i+1)%n];
	rep(i,n) w[i] = b[i]^b[(i+1)%n];
	debug(s,w);
	auto x = KMP(s,w);
	debug(x);
	for(int k:x) {
		std::cout << k << ' ' << (a[k]^b[0]) << ENDL;
	}
	return 0;
}


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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int ggcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  long long int n,max1=0,max2=0,max3=0,max4=0,ans1=0,ans2=0,ans3=0,ans4=0,x,y;
  bool flag1=false,flag2=false;
  cin>>n;
  vector<long long int> a(n/2),b(n/2);
  map<long long int,long long int> mp1,mp2;
  rep(i,n){
    int m;
    cin>>m;
    if(i%2==0){
      a[i/2]=m;
    }else{
      b[i/2]=m;
    }
  }
  rep(i,n/2){
    mp1[a[i]]++;
    mp2[b[i]]++;
    
  }
  
  rep(i,n/2){
    if(max1<mp1[a[i]]){
      ans1=a[i];
      max1=mp1[a[i]];
    }
  }
  rep(i,n/2){
    if(max2<mp2[b[i]]){
      ans2=b[i];
      max2=mp2[b[i]];
    }
  }
  x=mp1[ans1];
  y=mp2[ans2];
  mp1[ans1]=0;
  mp2[ans2]=0;
  max1=0;
  max2=0;
  rep(i,n/2){
    if(max1<mp1[a[i]]){
      ans3=a[i];
      max1=mp1[a[i]];
    }
  }
  rep(i,n/2){
    if(max2<mp2[b[i]]){
      ans4=b[i];
      max2=mp2[b[i]];
    }
  }
  if(ans1!=ans2){
    cout<<n-x-y<<endl;
  }else{  
    cout<<min(n-x-mp2[ans4],n-y-mp1[ans3])<<endl;
  }
  
  
  
}
///////////////////////////





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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> broken(n+1);
  rep(i,m) {
    int a;
    cin >> a;
    broken[a] = 1;
  }
  vector<int> dp(n+2);
  const int mod = 1000000007;
  dp[n] = 1;
  for (int i = n-1; 0 <= i; i--) {
    if (broken[i]) {
      dp[i] = 0;
      continue;
    }
    dp[i] = (dp[i+1] + dp[i+2])%mod;
  }
  cout << dp[0] << endl;
  return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Volume0009
{
    class Program
    {
        static void Main(string[] args)
        {
            string numstr = "";
            while ((numstr = Console.ReadLine()) != null)
            {
                int primeCount = 0;
                int num = int.Parse(numstr);
                if (num == 0 || num == 1)
                { }
                else if (num == 2)
                {
                    ++primeCount;
                }
                else
                {
                    primeCount = 1;
                    for (int i = 3; i <= num; i += 2)
                    {
                        if (Prime.IsPrime(i))
                        {
                            ++primeCount;
                        }
                    }
                }
                Console.WriteLine(primeCount);
            }
        }
    }
    class Prime
    {
        internal static bool IsPrime(int num)
        {
            double sqrtNum = Math.Sqrt(num);
            for (int i = 3; i <= sqrtNum; i += 2)
            {
                if (num % i == 0)
                {
                    return false;
                }
            }
            return true;
        }
    }
}



Measured memory_bytes: 15944
#-*-coding:utf-8-*-

class UnionFind:
    def __init__(self, n):
    # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.parent = [i for i in range(n + 1)]
    # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)
    #検索
    def find(self, x):
    #根ならその番号を返す
        if self.parent[x] == x:
            return x
        else:
    # 走査していく過程で親を書き換える
            self.parent[x] = self.find(self.parent[x])
            return self.find(self.parent[x])
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    #併合
    def unite(self, x, y):
    #根を探す
        x = self.find(x)
        y = self.find(y)
    # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
    # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def main():

    n, m = map(int, input().split())
    es = []

    for _ in range(m):
        a, b = map(int, input().split())
        es.append((a, b))
        
    ans = 0
    for i in range(m):
        u = UnionFind(n)
        for j, e in enumerate(es):
            if j != i:
                a, b = e
                u.unite(a, b)
        a, b = es[i]
        if not u.same_check(a, b):
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()

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

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

int main(){
    int K, T;
    cin >> K >> T;
    vector<int> a(T);
    rep(i, T) cin >> a[i];

    int mx = 0;
    int mi;
    rep(i, T) mx = max(mx, a[i]);
    rep(i, T) if(mx == a[i]) mi = i;

    int mi_elim_sum = 0;
    rep(i, T){
        if(i == mi) continue;
        mi_elim_sum += a[i];
    }
    int ans = 0;
    int sub = mx - mi_elim_sum;
    if(sub >= 1) ans = sub-1;
    else ans = 0;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M,C;
  cin >> N >> M >> C;
  vector<int> B(M);
  for (int i=0; i<M; i++){
  cin >> B.at(i);
  }
    vector<vector<int>> A(N,vector<int>(M));
  for (int i=0; i<N; i++){
    for (int j=0; j<M; j++){
      cin >> A.at(i).at(j);
    }
  }
  
  int ans=0,sumi;
  for (int i=0; i<N; i++){
    sumi=0;
    for (int j=0; j<M; j++){
      sumi+=B.at(j)*A.at(i).at(j);
    }
    if (sumi + C>0){
    ans++;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
a, b, c, d = map(int, input().split())

alice = []
bob = []
for i in range(a, b+1):
    alice.append(i)
#print(alice)
for j in range(c, d+1):
    bob.append(j)
#print(bob)

count=0
for i in range(len(alice)):
    if alice[i] in bob:
        count += 1

if count>0:
    print(count-1)
else:
    print(count)

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

#define rep(i,k,n) for(int (i)=(k);(i)<(n);(i)++)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a)>0 ?(a):-(a))
#define llong long long

int main(){
	int a; scanf("%d",&a);
	printf("%d",a+a*a+a*a*a);
	return 0;
}


Measured memory_bytes: 1732
/*
 * I won't be broken
 * I won't be tortured
 * I won't be beaten down
 * I have the answer
 * I can take the pressure
 * I will turn it all around
 * Lift me up above this
 * The flames and the ashes
 * Lift me up and help me to fly away
*/
#include <bits/stdc++.h>
using namespace std;
long long dp[100005];
int n, v[105];
long long w[105],W;
int main(){
	scanf("%d%lld",&n,&W);
	for(int i = 0; i<n; i++)
		scanf("%lld%d",w+i,v+i);
	for(int i = 0; i<100005; i++)
		dp[i]=2e9;
	dp[0]=0;
	for(int i = 0; i<n ; i++){
		for(int j = 100000; j>=0; j--)
			if(v[i]<=j)
				dp[j]=min(dp[j],dp[j-v[i]]+w[i]);	
	}
	int ans;
	for(int i = 0; i<100005; i++)
		if(dp[i]<=W)
			ans=i;
	printf("%d\n",ans);
        return 0;
}




Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x = scan.nextInt();
        int y = scan.nextInt();

        int[] t = new int[n];

        for (int i = 1; i < n+1; i++) {
            for (int j = i+1; j < n+1; j++) {
                t[Math.min(j-i,Math.abs(i-x) + Math.abs(j-y) + 1)]++;
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.println(t[i]);
        }
    }
}


Measured memory_bytes: 23636
n = int(input())
s = input()

def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
if check(hi):
	print(hi)
else:
  	print(lo)

Measured memory_bytes: 135644
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<ll, ll>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%MOD+MOD)%MOD) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

/* -- template -- */

int main() {
    int N; ll M; cin >> N >> M;
    ll A[N];rep(i, N) cin >> A[i];
    vector<ll>sum(N, 0);
    sum[0] = A[0];
    for(int i = 1;i < N;++i)
        sum[i] = sum[i - 1] + A[i];
    rep(i, N)
        sum[i] %= M;
    map<int, ll> m;
    rep(i, N)
        ++m[sum[i]];
    ll ans = 0;
    for(auto iter = begin(m); iter != end(m); ++iter) {
        if(iter->first % M == 0)
            ans += (iter->second) * (iter->second + 1) / 2;
        else
            ans += (iter->second) * (iter->second - 1) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

int main() {
  ll n;
  string x;
  cin >> n >> x;
  ll k = 0;  /// popcount
  rep(i, n) if(x[i] == '1') k++;
  mod = k + 1;
  vector<mint> m(2);
  rep(a, 2) {
    rep(i, n) {
      m[a] *= 2;
      if(x[i] == '1') m[a] += 1;
    }
    mod = k - 1;
    if(k - 1 == 0) break;
  }
  rep(i, n) {
    ll y;
    if(x[i] == '1') {
      if(k - 1 == 0) {
        cout << 0 << '\n';
        continue;
      }
      mod = k - 1;
      mint now = m[1];
      now -= mint(2).pow(n - 1 - i);
      y = now.x;
    } else {
      mod = k + 1;
      mint now = m[0];
      now += mint(2).pow(n - 1 - i);
      y = now.x;
    }
    ll ans = 1;
    while(y > 0) {
      ans++;
      ll cnt = 0;
      rep(j, 32) if(y >> j & 1) cnt++;
      y %= cnt;
    }
    cout << ans << '\n';
  }
}

Measured memory_bytes: 3724
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner scn = new Scanner(System.in);
    int N = scn.nextInt();
    int M = scn.nextInt();

    int Lmax = scn.nextInt();
    int Rmin = scn.nextInt();
    for (int i = 1; i < M; i++) {
      int L = scn.nextInt();
      if (L > Lmax) {
        Lmax = L;
      }
      int R = scn.nextInt();
      if (R < Rmin) {
        Rmin = R;
      }
    }

    if (Rmin - Lmax < 0) {
      System.out.println(0);
    } else {
      System.out.println(Rmin - Lmax + 1);
    }

  }
}

Measured memory_bytes: 62156
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		char c = in.next().charAt(0);
		switch (c) {
		case 'A': c = 'T'; break;
		case 'T': c = 'A'; break;
		case 'G': c = 'C'; break;
		case 'C': c = 'G'; break;
		}
		System.out.println(c);
	}

}


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

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;

using namespace std;


int main() {
	int h, w, n;
	cin >> h >> w >> n;
	VI a(n+1);
	REP(i, n)cin >> a[i+1];
	VVI c(h, VI(w));
	bool b = true;
	int k = 1;
	REP(i, h) {
		if (b) {
			REP(j, w) {
				if (a[k] > 0) {
					c[i][j] = k;
					a[k]--;
				}
				else {
					k++;
					c[i][j] = k;
					a[k]--;
				}
			}
		}
		else {
			for (int j = w - 1; j >= 0; j--) {
				if (a[k] > 0) {
					c[i][j] = k;
					a[k]--;
				}
				else {
					k++;
					c[i][j] = k;
					a[k]--;
				}
			}
		}
		if (b)b = false;
		else b = true;
	}
	REP(i, h) {
		REP(j, w)cout << c[i][j]<<' ';
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
//0 sheep
//1 wolf
using namespace  std;
const int maxn = 1e5+10;
int n;
string s;
int b[4][2]={{0,0},{0,1},{1,0},{1,1}};
int ans[maxn];
bool check() {
    char c;
    if(ans[0]){
        if(ans[n-1]==ans[1]){
            c = 'x';
        }else{
            c = 'o';
        }
        if(s[0]!=c)
            return false;
    }else{
        if(ans[n-1]==ans[1]){
            c = 'o';
        }else{
            c = 'x';
        }
        if(s[0]!=c)
            return false;
    }
    for(int i=1; i<n-1; i++){
        if(ans[i]){
            if(ans[i-1]==ans[i+1]){
                c = 'x';
            }else{
                c = 'o';
            }
            if(s[i]!=c)
                return false;
        }else{
            if(ans[i-1]==ans[i+1]){
                c = 'o';
            }else{
                c = 'x';
            }
            if(s[i]!=c)
                return false;
        }
    }
    if(ans[n-1]){
        if(ans[n-2]==ans[0]){
            c = 'x';
        }else{
            c = 'o';
        }
        if(s[n-1]!=c)
            return false;
    }else{
        if(ans[n-2]==ans[0]){
            c = 'o';
        }else{
            c = 'x';
        }
        if(s[n-1]!=c)
            return false;
    }
    return true;
}
int main() {
//    freopen("input.txt","r",stdin);
   cin >> n >> s;
   for(int i=0; i<4; i++){
       for(int j=0; j<2; j++){
           ans[j] = b[i][j];
       }
       for(int j=2; j<n; j++){
           if(ans[j-1]==1&&s[j-1]=='x'){
               ans[j]=ans[j-2];
           }else if(ans[j-1]==1&&s[j-1]=='o'){
               ans[j]=!ans[j-2];
           }else if(ans[j-1]==0&&s[j-1]=='o'){
               ans[j]=ans[j-2];
           }else{
               ans[j]=!ans[j-2];
           }
       }
//       for(int j=0; j<n; j++){
//           cout << ans[j];
//       }
//       cout<<endl;
       if(check()){
           for(int j=0; j<n; j++){
               if(ans[j]){
                   cout <<"W";
               }else{
                   cout <<"S";
               }
           }
           cout << endl;
           return 0;
       }
   }
   cout << -1 << endl;
   return 0;
}


Measured memory_bytes: 896
#include<iostream>
using namespace std;
int main(){
  int n;
  int i,j,k;
  int build[4][3][10]={{{}}};
  cin >> n;
  int b,f,r,v;
  for(i=0;i<n;i++){
    cin >> b >> f >> r >> v;
    build[b-1][f-1][r-1]+=v;
  }
  for(i=0;i<4;i++){
    for(j=0;j<3;j++){
      for(k=0;k<10;k++){
        cout << " ";
        cout << build[i][j][k];
      }
      cout << endl;
    }
    if(i<3)cout << "####################" << endl;
  }
  return 0;
}




Measured memory_bytes: 3116
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func main() {
	sc.Split(bufio.ScanWords)
	N := nextInt()
	H := make([]int, N)

	for i := 0; i < N; i++ {
		H[i] = nextInt()
	}

	log.Printf("%+v", H)
	max := 0
	total := 0
	for i := 0; i < N-1; i++ {
		if H[i+1] <= H[i] {
			total +=1
		} else {
			if total > max {
				max = total
			}
			total = 0
		}
	}

	if total > max {
		max = total
	}
	fmt.Printf("%d", max)
}


Measured memory_bytes: 7680
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;

typedef long long ll;

int MOD=1000000007;


int main(){
 ll N,M,ans=0;
 cin >> N >> M;
 vector<pair<ll,ll>> AB;
 for(ll i=0; i<N; i++){
   ll A,B;
   cin >> A >> B;
   AB.push_back({A,B});
 }
 sort(AB.begin(),AB.end());

  for(ll i=0; i<N; i++){
    ll cnt=min(AB[i].second, M);
    M-=cnt;
    ans+=(AB[i].first*cnt);
  }
  cout << ans << endl;
}

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

using namespace std;

int main(){
	int N;
	cin >> N;
	vector<double> x(N), y(N);
	rep(i,N) cin >> x[i] >> y[i];
	vector<int> p(N);
	rep(i,N) p[i]=i;
	double ans=0;
	do{
		rep(i,N-1){
			double dx=x[p[i+1]]-x[p[i]];
			double dy=y[p[i+1]]-y[p[i]];
			double dist=sqrt(dx*dx+dy*dy);
			ans+=dist;
		}
	}while(next_permutation(p.begin(),p.end()));
	rep(i,N) ans/=(i+1);
	cout << setprecision(15) << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main()
{
  ll N; cin >> N;
  ll K; cin >> K;
  vector<ll> a(N);
  for (int i=0; i<N; i++){
    cin >> a[i];
  }
  vector<vector<ll>> dp(N+1, vector<ll>(K+1, 0));
  for (int i=0; i<=N; i++) {
    dp[i][0] = 1;
  }
  for (int i=1; i<=N; i++) {
    for (int j=1; j<=K; j++) {
      dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
      if (j-a[i-1]-1 >= 0) {
        dp[i][j] = (dp[i][j]-dp[i-1][j-a[i-1]-1]+mod)%mod;
      }
    }
  }
  cout << dp[N][K] << endl;

  return 0;
}


Measured memory_bytes: 80256
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

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

func nextIntSlice(size int) []int {
	re := make([]int, size)
	for i := 0; i < size; i++ {
		re[i] = nextInt()
	}
	return re
}

func main() {
	//sc.Split(bufio.ScanWords)
	s := nextLine()
	n := len(s)

	for i := n - 2; i > 0; i -= 2 {
		t := s[0:i]
		if strings.Compare(t[:len(t)/2], t[len(t)/2:]) == 0 {
			fmt.Println(len(t))
			return
		}
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define all(v)          ((v).begin()), ((v).end())
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define clr(v,d)		memset(v, d, sizeof(v))
const double EPS = 1e-8;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>P;
const ll mod = 998244353;
int dx[] = { 0, 0, -1, 1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
const int N = 500001;
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
void stop(){
#ifndef ONLINE_JUDGE
	system("pause");
#endif
}
struct point{
	double x, y;
};
ll gcd(ll a, ll b){ return !b ? a : gcd(b, a % b); }
ll fixMod(ll a, ll b){ return ((a%b) + b) % b; }
double triangle_area(int x1, int y1, int x2, int y2, int x3, int y3) {
	return abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2.;
};
ll dis(point a, point b) {
	ll x = a.x - b.x, y = a.y - b.y;
	return x * x + y * y;
}
double traingleArea(double a, double b, double c) {
	double s = (a + b + c) / 2.0;
	return sqrt(s * (s - a) * (s - b) * (s - c));
}
double circleArea(double r) {
	return acos(-1) * r * r;
}
ll power(ll x, ll y,ll mod)
{
	if (y == 0)return 1;
	if (y == 1)return x;
	ll r = power(x, y / 2,mod) % mod;
	return r%mod*r%mod*power(x, y % 2,mod) % mod;
}
bool is(int n){
	if (n % 2 == 0 && n != 2 || n <= 1)return 0;
	for (int i = 3; i*i <= n; i += 2)if (n%i == 0)return 0;
	return 1;
}
int main(){
	ll a, b, c;
	cin >> a >> b >> c;
	ll ans = min(b, c) * 2;
	c -= ans / 2;
	b -= ans / 2;
	if(c)ans+=min(c , a) + (c - min(c , a) != 0);
	cout << ans+b;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define intt int64_t
#define all(vec) vec.begin(), vec.end()

int main() {
    vector<int> vec(10);
    rep(i,10) scanf("%d", &vec.at(i));
    sort(all(vec), greater<>());
    rep(i,3) printf("%d\n", vec.at(i));
}


Measured memory_bytes: 3176
#include <iostream>
#include <string>

using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
const int s = 12;
string map[12];
int isl;

void dfs(int x, int y) 
{
    map[y][x] = '0';
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= s || ny >= s)
            continue;
        else if (map[ny][nx] == '1')
            dfs(nx, ny);
    }
}

int main()
{
    string str;

    while (cin >> str) {
        map[0] = str;
        for (int i = 1; i < s; i++)
            cin >> map[i];
        
        isl = 0;
        for (int y = 0; y < s; y++) {
            for (int x = 0; x < s; x++) {
                if (map[y][x] == '1') {
                    isl++;
                    dfs(x, y);
                }
            }
        }
        cout << isl << endl;        
    }
    
    return 0;
}

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

int main()
{
    int n, a = 0, w = 0, t = 0, r = 0;
    string s[200000];
    cin >> n;
    rep(i, n) cin >> s[i];

    rep(i, n)
    {
        if (s[i].compare("AC")==0)
            a++;
        else if (s[i].compare("WA")==0)
            w++;
        else if (s[i].compare("TLE")==0)
            t++;
        else
            r++;
    }

    cout << "AC x " << a << endl;
    cout << "WA x " << w << endl;
    cout << "TLE x " << t << endl;
    cout << "RE x " << r << endl;
    return 0;
}

Measured memory_bytes: 9884
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define Rep(i, N) for(int i = 0; i < N; i++)

signed main()
{
  int N;
  int A[100005];
  int sum = 0;
  cin >> N;
  Rep(i, N) {
    cin >> A[i]; sum += A[i];
  }

  if(sum % (N * (N + 1) / 2)) cout << "NO" << endl;
  else {
    bool flag = false;
    int s = sum / (N * (N + 1) / 2);
    int cnt = 0;
    A[N] = A[0];
    for(int i = 1; i <= N; i++) {
      if((s - (A[i] - A[i - 1])) % N) flag = true;
      else cnt += (s - (A[i] - A[i - 1]) + N - 1) / N;
    }
    if(flag || cnt != s) cout << "NO" << endl;
    else cout << "YES" << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(){
	int n, i, m;
	m=100000;
	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
		m=m*1.05;
		if(m%1000!=0)
		{
			m=m-m%1000;
			m=m+1000;
		}
	}
	printf("%d\n", m);
	return 0;
}

Measured memory_bytes: 592
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	h := nextInt()
	_ = nextInt()
	orig := make([]string, h)
	for i := 0; i < h; i++ {
		orig[i] = nextStr()
	}
	for i := 0; i < 2*h; i++ {
		fmt.Println(orig[i/2])
	}

}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1816
#include<iostream>
using namespace std;
int main(){
	int i, j;
	string s;
	cin>>i>>s;
	for(j=0;s[j]!='\0';j++);
	if(i>=j)
	cout<<s;
	else{
		for(j=0;j<i;j++)
		cout<<s[j];
		cout<<"...";
	}
}  

Measured memory_bytes: 3580