akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use itertools::Itertools;
use std::process::exit;
use std::cmp::*;
use num::*;
use num::integer::Roots;

fn main() {
    input! {
    a:usize,
    v:[isize;a],
    }
    let mut z=10000000000;
    let mut s=0;
    let mut g:isize=v.iter().sum();
    for i in 0..a{
        if z>(g-s*2).abs(){z=(g-s*2).abs()}
        s+=v[i];
    }
    println!("{}",z)
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<string> post(n);
    for(int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    vector<map<string, string>> dp(1 << n);
    function<string(int, string)> rec = [&](int S, string order) {
        if(S == (1 << n) - 1) return string();
        if(dp[S].count(order)) return dp[S][order];
        string& res = dp[S][order];
        res = "invalid";
        for(int i = 0; i < n; ++i) {
            if(S & (1 << i)) continue;
            int idx = 0;
            for(int j = 0; j < n; ++j) {
                if(post[i][idx] == order[j]) {
                    idx++;
                }
            }
            if(idx != k) continue;
            string nord = post[i];
            reverse(begin(nord), end(nord));
            for(auto c : order) {
                if(find(begin(nord), end(nord), c) == end(nord)) {
                    nord += c;
                }
            }
            string s = rec(S | (1 << i), nord);
            if(s != "invalid") {
                res = (char)('A' + i) + s;
                break;
            }
        }
        return res;
    };

    string ans = "Z";
    for(int fst = 0; fst < n && ans == "Z"; ++fst) {
        string s = post[fst];
        reverse(begin(s), end(s));
        string remain;
        for(char c = 'A'; c < 'A' + n; ++c) {
            if(find(begin(s), end(s), c) == end(s)) {
                remain += c;
            }
        }
        do {
            string ord = s + remain;
            auto t = rec(1 << fst, ord);
            if(t != "invalid") {
                ans = min(ans, (char)('A' + fst) + t);
            }
        } while(next_permutation(begin(remain), end(remain)));
    }

    cout << ans << endl;
}



Measured memory_bytes: 31036
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int oper(int a,int b,int c)
{
    if ((a==b)&&(a==c))
    {
        return 0;
    }
    if (a>b) swap(a,b);
    if (b>c) swap(b,c);
    if (a>b) swap(a,b);
    if (a==b)
    {
        return oper(a+1,b+1,c)+1;
    }
    else
    {
        return oper(a+2,b,c)+1;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int a,b,c;
    cin>>a>>b>>c;
    cout<<oper(a,b,c);
    return 0;
} 


Measured memory_bytes: 256
ID, LT, RT, PARENT, SIBLING, DEGREE, TYPE, DEPTH, HEIGHT = 1,2,3,4,5,6,7,8,9

def dfs(node, i):
  l,r = i,i
  if node[LT] != -1:
    l = dfs(nodes[node[LT]], i+1)
  if node[RT] != -1:
    r = dfs(nodes[node[RT]], i+1)
  return max(l, r)
  
def depth(node, i):
  if node[PARENT] == -1:
    return i
  return depth(nodes[node[PARENT]], i+1)

n = int(input())
nodes = [{} for _ in range(n)]

for node in nodes:
  id, lt, rt = list(map(int, input().split()))
  nodes[id][ID] = id
  nodes[id][LT] = lt
  nodes[id][RT] = rt
  nodes[id][SIBLING] = -1
  nodes[id][TYPE] = 'root'
  nodes[id][DEPTH] = 0
  nodes[id][PARENT] = -1
  nodes[id][HEIGHT] = 0
  nodes[id][DEGREE] = 0

for node in nodes:
  id = node[ID]
  deg = 0
  if node[LT] != -1:
    nodes[node[LT]][PARENT] = id
    if node[RT] == -1:
      nodes[node[LT]][SIBLING] = -1
    else:
      nodes[node[LT]][SIBLING] = nodes[node[RT]][ID]
    deg += 1
  if node[RT] != -1:
    nodes[node[RT]][PARENT] = id
    if node[LT] == -1:
      nodes[node[RT]][SIBLING] = -1
    else:
      nodes[node[RT]][SIBLING] = nodes[node[LT]][ID]
    deg += 1
  nodes[id][DEGREE] = deg


for node in nodes:
  nodes[node[ID]][HEIGHT] = dfs(node, 0)
  nodes[node[ID]][DEPTH] = depth(node, 0)
  if nodes[node[ID]][DEGREE] == 0 and nodes[node[ID]][PARENT] != -1:
    nodes[node[ID]][TYPE] = 'leaf'
  elif nodes[node[ID]][DEGREE] != 0 and nodes[node[ID]][PARENT] != -1:
    nodes[node[ID]][TYPE] = 'internal node'

for i in range(len(nodes)):
  node = nodes[i]
  print ('node {ID}: parent = {PARENT}, sibling = {SIBLING}, degree = {DEGREE}, depth = {DEPTH}, height = {HEIGHT}, {TYPE}'
    .format(ID=node[ID], PARENT=node[PARENT], SIBLING=node[SIBLING], DEGREE=node[DEGREE], DEPTH=node[DEPTH], HEIGHT=node[HEIGHT], TYPE=node[TYPE]))
    


Measured memory_bytes: 5636
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


template<class T>
class segment_tree_t {
public:
  segment_tree_t(int size) : size_(1), xp_(std::numeric_limits<T>::min()) {
    while (size_ < size)
      size_ *= 2;

    a_ = new T[size_ * 2];

    for (int i = 0, size = size_ * 2; i < size; i ++)
      a_[i] = xp_;
  };

  ~segment_tree_t() {
    delete[] a_;
  };

public:
  void update(int i, T x) {	// 0-index
    i += size_ - 1;

    a_[i] = x;

    while (i > 0) {
      i = (i - 1) / 2;

      a_[i] = std::max(a_[i * 2 + 1], a_[i * 2 + 2]);
    }
  };

  T query(int a, int b, int k = -1, int l = -1, int r = -1) const {	// [a, b)
    if (k < 0) {
      return query(a, b, 0, 0, size_);
    }
    else {
      if (r <= a || b <= l)
        return xp_;

      if (a <= l && r <= b) {
        return a_[k];
      }
      else {
        return std::max(query(a, b, k * 2 + 1, l, (l + r) / 2),
                        query(a, b, k * 2 + 2, (l + r) / 2, r));
      }
    }
  };

private:
  int size_;

  T* a_;

  T xp_;
};


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N, h[222222], a[222222];

  std::cin >> N;

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

    h[i] --;
  }

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

  segment_tree_t<long long> tree(N);

  for (int i = 0; i < N; i ++)
    tree.update(i, 0);

  for (int i = N - 1; i >= 0; i --) {
    long long x = tree.query(h[i], N);

    tree.update(h[i], a[i] + x);
  }

  std::cout << tree.query(0, N) << std::endl;

  return 0;
}


Measured memory_bytes: 5888
(* Vicfred
 * https://atcoder.jp/contests/abc133/tasks/abc133_b
 * math, implementation
 * *)
let ans, n, xss = Scanf.(scanf "%d %d" @@ fun n d -> ref 0, n, Array.(init n @@ fun _ -> init d @@ fun _ -> scanf " %d" ( + ) 0))
let rec f i n = if i * i >= n then i * i  = n else f (i + 1) n
let g n = n * n
let main = Array.(iteri (fun i xs -> for j = i +  1 to n - 1 do if f 1 @@ fold_left ( + ) 0 @@ mapi (fun k x -> g (x - xss.(j).(k))) xs then incr ans done) xss); Printf.printf "%d\n" !ans



Measured memory_bytes: 3828
t = []
 
N = input()
 
for i in range(int(N)):
    t.append(list(map(int, input().split())))
    
t.sort()
 
co, co_ = [0, 0, 0], [0, 0, 0]
flag = 1
 
for i in range(len(t)):
    co_[0] = t[i][0] - co[0]
    co_[1] = t[i][1] - co[1]
    co_[2] = t[i][2] - co[2]
    dis = abs(co_[1]) + abs(co_[2])
    if dis % 2 != (t[i][0]-co[0]) % 2:
        flag = 0
        break
    elif dis > co_[0]:
        flag = 0
        break
        
    co = t[i]
    
if flag == 0:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 27312
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <iostream>
#include <algorithm>
using namespace std;

int N, X, T;

int main()
{
	cin >> N >> X >> T;
	int a = (N / X) + (N % X > 0);
	cout << a * T << endl;

	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    vector<double> p(n);
    for(int i = 0; i < n; i++) cin >> p[i];
    double sum = 0, ave = 0;
    for(int i = 0; i < k; i++) sum += p[i];
    ave = max(ave, (sum + k) / 2);
    for(int i = k; i < n; i++){
        sum -= p[i - k];
        sum += p[i];
        ave = max(ave, (sum + k) / 2);
    }
    cout << fixed << setprecision(8) << ave;
    return 0;
}

Measured memory_bytes: 1792
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

typedef pair<int, int> P;

int dp[4005][4005];
int mod = 998244353;

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

    string s;
    cin >> s;

    int N = s.size();

    vector<int> sum(N + 1, 0);
    REP(i, N) {
        char c = s[i];
        int r = 0;
        switch (c) {
            case '0':
                r += 2;
                break;
            case '1':
                r += 1;
                break;
        }
        sum[i + 1] = sum[i] + r;
    }

    dp[0][0] = 1;
    REP(i, 2 * N) {
        REP(r, sum[N] + 1) {
            if (r > i) break;

            int t = i + 1 > N ? N : i + 1;

            // 赤を足す
            if (sum[t] >= r + 1) {
                dp[i + 1][r + 1] += dp[i][r];
                dp[i + 1][r + 1] %= mod;
            }
            // 青を足す
            if ((i + 1) * 2 - sum[t] >= i + 1 - r) {
                dp[i + 1][r] += dp[i][r];
                dp[i + 1][r] %= mod;
            }

        }
    }

    cout << dp[2 * N][sum[N]] << endl;
    return 0;
}


Measured memory_bytes: 123648
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void foreach_permutation(int n, std::function<void(int *)> f) {
    int indexes[n];
    for (int i = 0; i < n; i++) indexes[i] = i+1;
    do {
        f(indexes);
    } while (std::next_permutation(indexes, indexes + n));
}

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

  bool flag = true;
    for(int i=0;i<N;i++){
        if(A[i]%2==0){
            if(A[i]%3!=0&&A[i]%5!=0){
                flag = false;
            }
        }
    }

    if(flag){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }



}


Measured memory_bytes: 256
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
for i in range(min(x,k)):
  for j in range(min(y,k)):
    if i*j>k:
      break
    for l in range(min(z,k)):
      if i*j*l>k:
        break
      else:
        ans.append(a[i]+b[j]+c[l])
ans.sort(reverse=True)
for i in range(k):
  print(ans[i])

Measured memory_bytes: 112348
import sys
n = int(input())
p = list(map(int,input().split()))

#昇順かどうか
def check(ls):
        for i in range(len(ls)-1):
                if ls[i] > ls[i+1]:
                        return False
        return True

for i in range(n):
        for j in range(i,n):
                p[i],p[j] = p[j],p[i]
                if check(p):
                        print('YES')
                        sys.exit()
                p[j],p[i] = p[i],p[j]
print('NO')


Measured memory_bytes: 39792
S = input(str())
N = len(S)
X=[[i-1 if S[i]=='L' else i+1 for i in range(N)] if j==0 else [0]*N for j in range(20)]
#print(X)

for k in range(1, 20):
    for i in range(N):
        X[k][i] = X[k-1][X[k-1][i]]
#print(X)

A = [0]*N
for i in range(N):
    A[X[-1][i]] += 1
print(*A)

Measured memory_bytes: 29620
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{
    string s;
    cin >> s;
    
    int sum = 0;
    rep(i, s.size()/2) {
        if (s[i] != s[s.size() - 1 - i]) sum ++;
    }
    println(sum)
    return 0;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int maxn=0x7fffff;
int main(){
	int n,ma=-1,num;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x=0;
		int nn=i;
		while(nn%2==0){
			nn/=2;
			x++;;
		}
		if(x>ma){
			ma=x;
			num=i;
		}
	}
	cout<<num;
	return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <map>
#include <utility>
#include <set>
  
#define rep(i, n) for(int i = 0; i < n; i++)
#define repx(i, a, n) for(int i = a; i < n; i++)
#define loop while(1)
#define lli long long int
 
using namespace std;
 
int main() {

  double x0, y0, x1, y1;
  cin >> x0 >> y0 >> x1 >> y1;

  printf("%.6lf", sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1)));
  
  return 0;
}



Measured memory_bytes: 3204
#include<bits/stdc++.h>
const int maxn = 1e2 + 5;
using namespace std;

int a,b,c;
int ans = 1;

int main(){
	scanf("%d %d %d", &a,&b,&c);
	if(a != b) ans++;
	if(a != c && b != c) ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
n=int(input())
ans=[0]*n
three=n//3
two=(n-three)//2
one=n-three-two
t=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  t[a].append(b)
  t[b].append(a)
th=[]
Q=[0]
visited={0}
ma=0
thi=-1
while Q:
  th.append(Q)
  if len(Q)>ma:
    ma=len(Q)
    thi=len(th)-1
  P=[]
  for j in Q:
    for i in t[j]:
      if i not in visited:
        P.append(i)
        visited.add(i)
  Q=P
odd=even=0
for i in range(len(th)):
  if i%2==1:odd+=len(th[i])
  else:even+=len(th[i])
if odd>one+three:
  flag="error"
  d=0
elif even>one+three:
  flag="error"
  d=1
else:
  flag="normal"

if flag=="error":
  sudenideta=set()
  num=3
  for i in range(d,len(th),2):
    for j in th[i]:
      ans[j]=num
      sudenideta.add(num)
      num+=3
  num=1
  for i in range(d^1,len(th),2):
    for j in th[i]:
      while num in sudenideta:num+=1
      ans[j]=num
      sudenideta.add(num)
      num+=1
else:
  odd_num=2
  even_num=1
  three_num=3
  for i in range(len(th)):
    for j in th[i]:
      if i%2==1:
        if odd_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=odd_num
          odd_num+=3
      else:
        if even_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=even_num
          even_num+=3
print(*ans)

Measured memory_bytes: 108232
#include<stdio.h>
int main(void)
{
	int  l,a,b,c,d,x,y,z;
	scanf("%d %d %d %d %d",&l,&a,&b,&c,&d);
	x=a/c;
	if(a%c!=0)	x++;
	y=b/d;
	if(b%d!=0)	y++;
	if(x>y)	z=l-x;
	else	z=l-y;
	printf("%d\n",z);
	return 0;
}


Measured memory_bytes: 2076
N=int(input())
vec=list(map(int,input().split()))
vec.sort()
#print(vec)

if(0 in vec):
    print(0)
else:
    res = 1
    for v in vec:
        res *= v
        if(res > 10**18):
            res = -1
            break

    print(res)

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

int main()
{
    int N;
    string S;
    cin >> N >> S;

    int sum = 1;
    char col = S[0];
    for (int i = 1; i < N; i++) {
        if (col != S[i]) {
            col = S[i];
            sum++;
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#include <numeric>

using namespace std;

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

using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int gcd(int p, int q)
{
    while (q != 0)
    {
        int r = p % q;
        p = q;
        q = r;
    }
    return p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int K;
    cin >> K;

    int sum = 0;

    REP(i, 1, K + 1)
    REP(j, 1, K + 1)
    REP(k, 1, K + 1)
    {
        sum += gcd(gcd(i, j), k);
    }
    cout << sum << endl;
}

Measured memory_bytes: 3652
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans = ans * cand % MOD
            cand -= 1
            Qappend(i)
    print(ans % MOD)


if __name__ == "__main__":
    main()


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

using namespace std;

typedef long long ll;

char ch[400010];

int n;

int main() {
	scanf("%s", ch + 1), n = strlen(ch + 1);
	ll ans = 0;
	for(int i = 1, nxt; i <= n; i = nxt + 1) {
		int nw = 0;
		for(nxt = i; nxt <= n; ) {
			if(ch[nxt] == 'A') nw++, nxt++;
			else if(ch[nxt] == 'C') {break;}
			else if(ch[nxt] == 'B' && (nxt + 1 > n || ch[nxt + 1] != 'C')) {break;}
			else ans += nw, nxt += 2;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 384
import std.stdio, std.string, std.conv;
import std.algorithm, std.array, std.range;
auto solve(string s_){
    immutable K = s_.chomp.to!int();
    if(K<13) return K.to!string();
    string a;
    void add(int i){ a~=(i+'0').to!char(); }
    immutable M=18;
    auto dp = new int[10][M];
    dp[1][]=1;
    auto t=9;
    foreach(i;2..M) foreach(j;0..10){
        auto n=dp[i-1][j];
        if(j>0) n+=dp[i-1][j-1];
        if(j<9) n+=dp[i-1][j+1];
        dp[i][j]=n;
        if(j==0) continue;
        if(t+n<K){
            t+=n;
            continue;
        }
        a.reserve(i);
        add(j);
        auto p=j;
        foreach_reverse(m;1..i){
            foreach(k;max(0,p-1)..min(10,p+2)){
                if(t+dp[m][k]>=K){
                    add(k);
                    p=k;
                    break;
                }
                t+=dp[m][k];
            }
        }
        return a;
    }
    return a;
}
void main(){ for(string s; (s=readln.chomp()).length;) writeln(solve(s)); }

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

#define boost ios::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second

ll a,b,c,d,e,f;

int main()
{
    boost;
    if(fopen("inp.txt", "r")) {
      freopen("inp.txt", "r", stdin);
      freopen("outp.txt", "w", stdout);
    }

    cin>>a>>b>>c>>d>>e>>f;

    ll i,j,k,l;

    ll num=-1,den=-1;

    for (i=50;i>=0;i--)
        for (j=50;j>=0;j--)
            for (k=50;k>=0;k--)
                for (l=50;l>=0;l--) {
                    ll t=100LL*i*a+100LL*j*b+k*c+l*d;

                    if (t>f || (e*(i*a+j*b)<(k*c+l*d))) {
                        continue;
                    }

                    ll n=k*c+l*d;

                    if (num==-1 && den==-1)
                        num=n,den=t;

                    else if (num*t<den*n) {
                        num=n,den=t;
                    }
                }

    cout<<den<<" "<<num<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int maxn=410;
const int maxm=100010;
int n, m;
int x[maxm], y[maxm];
int a[maxn][maxn];

int main(){

	scanf("%d%d", &n, &m);
	for(int i=1;i<=m;i++) scanf("%d%d", &x[i], &y[i]);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++) if(a[ x[i] ][j]) a[ y[i] ][j]=a[j][ y[i] ]=1;
		for(int j=1;j<=n;j++) if(a[ y[i] ][j]) a[ x[i] ][j]=a[j][ x[i] ]=1;
		if(a[ x[i] ][ y[i] ]){
			for(int j=1;j<=n;j++) a[ x[i] ][j]=a[j][ x[i] ]=1, a[ y[i] ][j]=a[j][ y[i] ]=1;
		}
		a[ x[i] ][ y[i] ]=a[ y[i] ][ x[i] ]=1;
	}
	int ans=n*(n-1)>>1;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans-=a[i][j];
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

int main(){
    long N;
    cin>>N;
    long l = sqrt(N);
    long m = N-1;
    for(int i=1; i<=l; ++i){
        long a = N%i;
        if(a==0){
            m = min(m, N/i + i - 2);
        }
    }
    cout<<m<<endl;

    return 0;
}

Measured memory_bytes: 256
require 'matrix'

$stdin = DATA if $stdin.eof?

r, c = gets.split.map(&:to_i)

a = []
ARGF.each do |line|
  a << line.split.map(&:to_i)
end

table = Matrix[a]

r.times do |i|
  column = table.column(i).to_a[0]
  print column.join("\s")
  print "\s"
  puts  column.inject(:+)
end

c.times do |i|
  print table.row(0).inject(0){|m, row| m + row[i]}
  print "\s"
end

puts table.inject(:+).inject(:+)

Measured memory_bytes: 11120
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    vector<int> cnt(n+1,0);
    for(int x=1;x<=100;x++){
        for(int y=1;y<=100;y++){
            int ch=x*x+y*y+x*y;
            if(ch>=n) break;
            for(int z=1;z<=100;z++){
                int sum=x*x+y*y+z*z+x*y+y*z+z*x;
                if(sum>n) break;
                cnt[sum] ++;
            }
        }
    }
    rep(i,n){
        cout<<cnt[i+1]<<endl;
    }
}/*
./problem.exe
*/

Measured memory_bytes: 3680
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int main(){
    long long int n;
    long long int count[100001]={};
    long long int el = 0;
    int as=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin>>as;
        if(count[as]==0)el++;
        count[as]++;
    }
    long long int two = 0;
    for(int i=1;i<100001;i++){
        if(count[i]>1&&count[i]%2==0)two++;
    }
    cout<<el-(two%2)<<endl;
    return 0;
}


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


int MOD=1000000007;


int main() {
	int N,T;
	cin >> N >> T;
	int b=0,m=MOD,p=0,a;
	for(int i=0; i<N; i++){
		cin >> a;
		if(i){
			if(a-m==p)b+=1;
			else if(a-m>p){
				p=a-m;
				b=1;
			}
		}
		m=min(a,m);
	}
	cout << b << endl;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =99999999999;

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}

//素数判定
ll isprime(ll n){
  bool prime=true;
  for(int i=2;i<n;i++){
    if(n%i==0){
      prime=false; break;
    }
  }
if(prime){cout<<n<<" is prime"<<endl;
         }else{cout<<n<<" is not prime"<<endl;}

}
//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




//10億7。　　　100000007
//2*2行列 H*W
//vector<vector<int>> vec(H,vector<int>(W));
//for(int i=0;i<H;i++){
//for(int j=0;j<W;j++){
//cin>>vec[i][j];
//  }
//}

//文字列→数列
//string S;int A=atoi(S.c_str());
//数列→文字列
//int A;string S=to_string(A);
//数字判定　isdigit(a)
//pair宣言　pair<int,int> p(5,7);
//ソート　sort(vec.begin(),vec.end());



int main(){
cout<<fixed<<setprecision(10);

  
int A,B;cin>>A>>B;
  if((A+B)%2==0){
cout<<(A+B)/2<<endl;
  }else{
    cout<<(A+B)/2+1<<endl;
}}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); 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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

bool solve(){
	int n;cin>>n;
	ll ma=pow(10,6)+10;
	vector<ll>cnt(ma,0);
	vector<ll>p(n);
	rep(i,n){
		cin>>p[i];
		cnt[p[i]]++;
	}
	
	sort(all(p));
	int ans=0;
	rep(i,n){
		if(cnt[p[i]]==1)ans++;
		if(cnt[p[i]]==0)continue;
		cnt[p[i]]=0;
		for(ll j=p[i]+p[i];j<ma;j+=p[i]){
			cnt[j]=0;
		}
	}
	cout<<ans<<endl;
	/*multiset<ll>a;
	rep(i,n){
		int x;a.insert(x);
	}
	int ans=0;
	while(!a.empty()){
		ll p=*a.begin();
		//cout<<1<<endl;
		a.erase(a.begin());
		int is=1;
		while(a.size()!=0 and *a.begin()==p){
			is=0;
			//cout<<2<<endl;
			a.erase(a.begin());
		}
		ans+=is;
		ll x=p+p;
		while(x<pow(10,6)){
			//cout<<3<<endl;
			if(a.find(x)!=a.end())a.erase(x);
			x+=p;
		}
	}
	cout<<ans<<endl;*/
  	return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(15);
  solve();
}



Measured memory_bytes: 12644
#include <bits/stdc++.h>
using namespace std;
#define itn int
#define nibu(K,x) binary_search(K.begin(),K.end(),x)
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define out(x) cout<<x<<endl
#define put(x) out(x)
#define in(x) cin>>x
#define maxx(a,b,c) max(a,max(b,c))
#define minn(a,b,c) min(a,min(b,c))
using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
const double pi = 3.14159265358979;
const ll mod = 1000000007;


int main() {
 vl a(3),b(3),c(3);
  rep(i,3) in(a[i]>>b[i]>>c[i]);
  if(a[0]-a[1]==b[0]-b[1] &&a[0]-a[2] == b[0]-b[2] &&a[0]-a[1] ==c[0]-c[1] &&a[0]-a[2] == c[0] -c[2]){
  out("Yes");
  }
  else out("No");
}


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

#include <iostream>
using namespace std;

int main() {
    int n;
    int a[201];
    int b[201];
    int c[201];
    int t[201]={};
    int tokuten;

    cin>>n;

    for(int i=1; i<n+1; i++){
    	cin>>a[i]>>b[i]>>c[i];
	}




	for(int j=1; j<n+1; j++){
	  int tokuten=a[j];
	  for(int i=1; i<n+1; i++){
		  if(a[i]==a[j]&&(i!=j))tokuten=0;
	  }
	  t[j]+=tokuten;
	}
	  for(int j=1; j<n+1; j++){
	  	  int tokuten=b[j];
	  	  for(int i=1; i<n+1; i++){
	  		  if(b[i]==b[j]&&(i!=j))tokuten=0;
	  	  }
	  	  t[j]+=tokuten;
	  }
	  	  for(int j=1; j<n+1; j++){
	  		  int tokuten=c[j];
	  		  for(int i=1; i<n+1; i++){
	  			  if(c[i]==c[j]&&(i!=j))tokuten=0;
	  		  }
	  		  t[j]+=tokuten;


     cout<<t[j]<<endl;

	  	  }

	}

Measured memory_bytes: 3112
#include <iostream>
#include <iomanip>
using namespace std;
#define eps 1e-10
int a, tar, cnt[4];
double dp[301][301][301];
double ev (int ones, int twos, int threes){
    if (dp[ones][twos][threes]!=0) return dp[ones][twos][threes];
    if (ones==0 && twos==0 && threes==0) return dp[0][0][0];
    double cur=double(a)/double(ones+twos+threes);
    if (ones!=0) cur+=double(ones)/double(ones+twos+threes)*ev(ones-1, twos, threes);
    if (twos!=0) cur+=double(twos)/double(ones+twos+threes)*ev(ones+1, twos-1, threes);
    if (threes!=0) cur+=double(threes)/double(ones+twos+threes)*ev(ones, twos+1, threes-1);
    dp[ones][twos][threes]=cur;
    return dp[ones][twos][threes];
}
int main(){
    cin>>a;
    for (int i=0; i<a; i++){
        cin>>tar;
        cnt[tar]++;
    }
    dp[0][0][0]=0; //base case
    cout<<fixed;
    cout<<setprecision(11)<<ev(cnt[1], cnt[2], cnt[3])+eps<<endl;
}

Measured memory_bytes: 213248
#include<cstdio>

int main(){
	int N;
	scanf("%d", &N);
	double answer = 0;
	for (int i = 0; i < N; ++i)
	{
		double otoshidama;
		char tmp1, tmp2, tmp3;
		scanf("%lf %c%c%c", &otoshidama, &tmp1, &tmp2, &tmp3);
		answer += tmp1 == 'J' ? otoshidama : (otoshidama*380000);
	}
	printf("%lf\n", answer);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


bool is_pal(string s){
    REP(i, s.length() / 2){
        if(s[i] != s[s.length() - i - 1]) return false;
    }
    return true;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, s_without_x;
    VI not_x;
    cin >> s;
    not_x.push_back(-1);
    REP(i, s.length()){
        if(s[i] != 'x'){
            s_without_x += s[i];
            not_x.push_back(i);
        }
    }
    not_x.push_back(s.length());
    int ans = 0;
    if(!is_pal(s_without_x)){
        ans = -1;
    }else{
        REP(i, not_x.size() / 2){
            ans += abs((not_x[i + 1] - not_x[i])
                - (not_x[not_x.size() - i - 1] - not_x[not_x.size() - i - 2]));
        }
    }

    cout << ans << "\n";
    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
int A[222222];

signed main(){
    cin>>N>>M;
    rep(i,N)cin>>A[i];

    map<int,int>cnt;
    cnt[0]++;
    int s=0;
    int ans=0;
    rep(i,N){
        s=(s+A[i])%M;
        ans+=cnt[s];
        cnt[s]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int H,W,K;

void wSpread(vector<vector<int>> &C,pair<int,int> pos,int n){
    int x=pos.first,y=pos.second;
    if(C.at(x).at(y)==0) C.at(x).at(y)=n;
    if(y-1>=0 && C.at(x).at(y-1)==0) wSpread(C,make_pair(x,y-1),n);
    if(y+1<W && C.at(x).at(y+1)==0) wSpread(C,make_pair(x,y+1),n);
}

void hSpread(vector<vector<int>> &C,pair<int,int> pos,int wFrom,int wTo,int n){
    rep(i,wFrom,wTo+1) C.at(pos.first).at(i)=n;

    int sumB=0,sumF=0;
    rep(i,wFrom,wTo+1){
        if(pos.first-1>=0) sumB+=C.at(pos.first-1).at(i);
        if(pos.first+1<H) sumF+=C.at(pos.first+1).at(i);
    }

    if(pos.first-1>=0 && sumB==0) hSpread(C,make_pair(pos.first-1,pos.second),wFrom,wTo,n);
    if(pos.first+1<H && sumF==0) hSpread(C,make_pair(pos.first+1,pos.second),wFrom,wTo,n);
}

int main(){
    cin>>H>>W>>K;
    vector<vector<int>> Cake(H,vector<int>(W,0));
    set<pair<int,int>> setC;
    int n=1;
    rep(h,0,H)rep(w,0,W){
        char c; cin>>c;
        if(c=='#'){
            Cake.at(h).at(w)=n;
            setC.insert(make_pair(h,w));
            n++;
        }
    }

    for(auto s:setC){
        wSpread(Cake,s,Cake.at(s.first).at(s.second));
        int wFrom=W,wTo=0;
        rep(i,0,W){
            if(Cake.at(s.first).at(i)==Cake.at(s.first).at(s.second)){
                wFrom=min(wFrom,i);
                wTo=max(wTo,i);
            }
        }
        hSpread(Cake,s,wFrom,wTo,Cake.at(s.first).at(s.second));
    }

    rep(h,0,H){
        rep(w,0,W) cout<<Cake.at(h).at(w)<<" ";
        cout<<endl;
    }
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K,X;
  cin >> K >> X;
  for (int i=0;i<2*K-1;i++){
    cout << X-K+1+i;
    if (i<2*K-2){
      cout << ' ';
    }
    else {
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
N,M=map(int,input().split())
p=True
l=[-1 for _ in range(N)]
for i in range(M):
  s,c=map(int,input().split())
  if l[s-1] == -1:
    l[s-1] = c
  elif not l[s-1]==c:
    p=False
if p:
  ans=""
  if len(l) == 1:
    if l[0] == -1:
      ans = "0"
    else:
      ans = str(l[0])
  elif l[0]==0:
    p=False
  elif l[0]==-1:
    ans="1"
  else:
    ans=str(l[0])
  for i in l[1:]:
    if i == -1:
      ans+="0"
    else:
      ans+=str(i)
print(int(ans) if p else -1)

Measured memory_bytes: 9240
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (s);(i) --> (e);)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

int main() {
  i64 N;
  cin >> N;
  vector<i64> A(N), B(N);
  rep(i,0,N) cin >> A[i];
  rep(i,0,N) cin >> B[i];

  i64 ans = 1e18;

  for(i64 s = 0;s < (1 << N);s++) {
    if(__builtin_popcountll(s) % 2 == 1) continue;
    vector<i64> vec(N);
    vector<i64> idx(N);
    vector<i64> flip(N);
    rep(i,0,N) {
      if(s & (1 << i)) vec[i] = B[i], flip[i] = 1;
      else vec[i] = A[i];
      idx[i] = i;
    }
    auto X = vec;
    sort(all(vec));
    i64 res = 0;


    rep(i,0,N) {
      if(vec[i] != X[idx[i]]) {
        rep(j,i + 1,N) {
          flip[idx[j - 1]] ^= 1;
          res++;
          if(vec[i] == X[idx[j]]) {
            flip[idx[j]] ^= ((j - i) & 1);
            i64 idxj = idx[j];
            idx.erase(idx.begin() + j);
            idx.insert(idx.begin() + i, idxj);
            break;
          }
        }
      }
    }
    i64 F = 1;
    i64 b = -1;
    rep(ii,0,N) {
      i64 i = idx[ii];
      if(flip[i]) {
        if(b == -1) b = ii;
        else if(X[idx[b]] == X[idx[ii]] && (ii - b) % 2 == 1){
          res += (ii - b);
          b = -1;
        }
        else {
          F = 0;
          break;
        }
      }
    }
    if(F == 0) continue;
    ans = std::min(ans, res);
    i64 t = 0;
    for(i64 i = N;i --> 0;) {
      t |= ((s >> i) & 1) << (N - 1 - i);
    }
    //cout << bitset<5>(t) << " " << res << endl;
  }
  if(ans == 1e18) ans = -1;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int a,h,m,s;
    scanf("%d",&a);
    h=a/3600;
    m=(a-h*3600)/60;
    s=a-h*3600-m*60;
    
    printf("%d:%d:%d\n",h,m,s);
    
    return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
const ll mod = 1000000007;
#define PI 3.1415926535
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> pair;
bool seen[505][505];

//dpTable
//bool dp[100050];

int main(){
    int N,ans = 0;
    cin >> N;
    vector<int> p(N);
    rep(i,N) cin >> p.at(i);
    for (int i = 1; i < N - 1; i++) {
        if ((p.at(i) > p.at(i - 1) && p.at(i) < p.at(i + 1)) || (p.at(i) < p.at(i - 1) && p.at(i) > p.at(i + 1))) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>


#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define pf push_front
#define eb emplace_back 
#define all(v) (v).begin(), (v).end()
#define mod 100000
#define mi multiset<int>
#define mii multiset<pii>
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000

// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>


// using namespace __gnu_pbds;
using namespace std;

int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}

int modp(int a,int m,int n)
{
    n=n%(m-1);
    a=a%m;
    int res=1;
    while(n>0)
    {
        if(n&1) res=(res*a)%m;
        a=(a*a)%m;
        n>>=1;
    }
    return res;
}



void solve()
{
    int t,n,m,i,k,l,r,u,v,w,j,s,pos,sum=0,flag=0,count=0;
    string S,T,U;
    // int h1,m1,h2,m2;
    cin>>n>>m;
    if(n==1||m==1)
    {
        cout<<"1";
        return;
    }
    // if(n%2&&m%2)
    {
        cout<<(n*m+1)/2;
    }
}



signed main()
{
 //   #ifndef ONLINE_JUDGE 
   //    freopen("input.txt","r",stdin);
     //  freopen("output.txt","w",stdout);
   // #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
#define ALL(a) a.begin(), a.end()
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    string s;
    cin >> s;
    int n=s.size();
    bool d=0;
    vector<char> l;
    rep(i,n){
        if(s[i]=='C'&&d==1){
            d=0;
            l.push_back('D');
        }else if(d==1){
            l.push_back('B');
            if(s[i]=='B'){
                d=1;
            }else{
                l.push_back(s[i]);
                d=0;
            }
        }else if(s[i]=='B'){
            d=1;
        }else{
            l.push_back(s[i]);
            d=0;
        }
    }
    int m=l.size();
    ll ans=0;
    ll temp=0;
    for(int i=0;i<m;i++){
        if(l[i]=='A'){
            temp++;
        }else if(l[i]=='D'){
            ans+=temp;
        }else{
            temp=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3924
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
int main() {
    int A, B, C, K; cin >> A >> B >> C >> K;
    int ans = 0;
    int t = 0;
    t = min(A, K);
    ans += t; K -= t;
    t = min(B, K);
    K -= t;
    t = min(C, K);
    ans -= t; K -= t;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <stdio.h>

#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;


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

    string answer = "No";
    //亀がint i
    for (int i = 0; i <= x;i++) {
        int total = 4 * i + 2 * (x - i);
        if (total == y) {
            answer = "Yes";
            break;
        }
    }

    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}

priority_queue<P> q1;
map<int,int> m1;

int main(){
	int n,m;
	int i,j,k;
	LL a,b,c,d;
	LL p[4];
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a;
		q1.push(make_pair(a,i));
	}
	m1[0]=1,m1[n+1]=1;
	a=q1.top().second,q1.pop();
	m1[a]=1;
	b=0;
	while(!q1.empty()){
		d=q1.top().first,a=q1.top().second,q1.pop();
		m1[a]=1;
		auto itr=m1.find(a);
		p[1]=(--itr)->first;
		if(itr!=m1.begin())p[0]=(--itr)->first;
		else p[0]=0;
		itr=m1.find(a);
		p[2]=(++itr)->first;
		if((++itr)!=m1.end())p[3]=itr->first;
		else p[3]=n+1;
		c=(a-p[1])*(p[3]-p[2])+(p[1]-p[0])*(p[2]-a);
		b+=c*d;
	}
	cout<<b<<endl;
}

Measured memory_bytes: 5748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    ll a[n];for(ll i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<a[n-1]-a[0];
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<utility>
using namespace std;
#define INF 1000000005
int main()
{
int n,x;
std::cin >> n >> x;
std::vector<long int> a;
for(int i = 0; i < n; i++){
    long int temp;
    std::cin >> temp;
    a.push_back(temp);
}

std::sort(a.begin(),a.end());
int sum = 0;
int index = 0;
while(x - a[index]>=0){
    if(index == n - 1){
        if(x == a[index]){
            sum++;
        }
        break;
    }
    x -= a[index];
    index++;
    sum++;
}
std::cout << sum << std::endl;

return 0;
}

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

int main(void){
    
    int  K;
    string s;
 
    cin >> K >> s;
    
    if(s.length()<=K){
        cout << s << endl;
    }else{
        for(int i=0;i<K;i++){
            cout << s[i];
        }
        cout << "..."<<endl;
    }
    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define maxn 200100
using namespace std;
vector<int>R[maxn],B[maxn];
int ans,fa[maxn],dep[maxn],n,x,y,s[maxn];
void dfs(int u,int f){
	dep[u]=dep[fa[u]=f]+1;
	for(int i=0;i<B[u].size();++i)if(B[u][i]!=f)
		dfs(B[u][i],u);
}
int gd(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	int d=dep[u]-dep[v];
	while(dep[u]>dep[v]&&d<=2)u=fa[u];
	while(u!=v&&d<=2)u=fa[u],v=fa[v],d+=2;
	return min(d,3);
}
void dfs2(int u,int f){
	if(f&&gd(u,f)>=3)s[u]=s[f]=1;
	for(int i=0;i<R[u].size();++i)if(R[u][i]!=f)
		dfs2(R[u][i],u);
}
void sol(int u,int f,int len){
	if(dep[u]<=len)return ;
	ans=max(ans,dep[u]);
	if(s[u])printf("-1"),exit(0);
	for(int i=0;i<R[u].size();++i)if(R[u][i]!=f)
		sol(R[u][i],u,len+1);
}
int main(){
	scanf("%d%d%d",&n,&x,&y);
	for(int i=2,u,v;i<=n;++i)
		scanf("%d%d",&u,&v),
		R[u].push_back(v),
		R[v].push_back(u);
	for(int i=2,u,v;i<=n;++i)
		scanf("%d%d",&u,&v),
		B[u].push_back(v),
		B[v].push_back(u);
	dep[0]=-1;
	dfs(y,0),dfs2(x,0),sol(x,0,0);
	printf("%d",ans<<1);

}

Measured memory_bytes: 33020
#include <iostream>
#include <iomanip> 
#include <cstdlib>
#include <cmath>
#include<map>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h> 
#include<vector>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define replb(i,a,b) for(ll i=a;i>=b;i--)
#define repl(i,a,b) for(ll i=a;i<b;i++)
#define repit(arr)  for(auto it=arr.begin();it!=arr.end();it++)  
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vl vector<long long int>
#define Vi vector<vector<int>>
#define seti set <int>
#define setl set <ll>
#define dseti set <int, greater <int> >
#define dsetl set <ll, greater <ll> >
#define mseti multiset <int>
#define msetl multiset <ll>
#define dmseti multiset <int, greater <int> >
#define dmsetl multiset <ll, greater <ll> >
#define sortA(arr)   sort(arr.begin(),arr.end())
#define ssort(arr) stable_sort(arr.begin(),arr.end())
#define search(arr,c)  binary_search(arr.begin(),arr.end(),c)
#define pb   push_back
#define ll long long
#define cl_bf cin.ignore(numeric_limits<streamsize>::max(), '\n');
#define castl static_cast<ll>
int gcd(int a,int b){
    if (a < b) swap(a, b);
    if (b == 0) return a;
    else return gcd(b, a % b);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=0,n;
    string s1,s2;cin>>s1>>s2;
    int l=s1.size();
    rep(i,0,l){
        if(s1[i]!=s2[i])t++;
    }
    cout<<t;
    return 0;
}

Measured memory_bytes: 3824
#include <iostream>

using namespace std;

int main (){
  int n;
  string a , b , c;
  char ac,bc,cc;
  cin >> n >> a >> b >> c;
  int cnt = 0;
  for(int i=0; i < n; i++){
    ac=a[i];bc=b[i];cc=c[i];
    if(ac==bc && bc==cc){
      continue;
    }
    if(ac==bc || bc==cc || cc==ac){
      cnt++;
      continue;
    }
    cnt += 2;
  }
  cout << cnt <<endl;
  return 0;
}


Measured memory_bytes: 256