akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>

using namespace std;

int main (){
	int a, b, i=1;
	double n;
	cin >> a >> b;
	for(i=1; i<=b; i*=10);
	
	n = sqrt((double)(a*i)+b);
	
	if(fmod(n, 1) == 0) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i > 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  int N, K;
  cin >> N >> K;
  
  int h, count = 0;
  REP(i, N){
    cin >> h;
    if(h >= K) count++;
  };
  
  cout << count << endl;
  return 0;
};


Measured memory_bytes: 256
#![allow(unused)]
use std::io::{self, Read};
use std::f64::consts::PI;

fn get_stdin() -> String {
    let mut buf = String::new();
    let mut stdin = io::stdin();
    stdin.read_to_string(&mut buf);
    return buf
}

fn to_nums(ss: &str) -> Vec<i32> {
    ss.split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect()
}

fn main() {
    let input = get_stdin();
    let circ = Circle {
        radius: input.trim().parse::<f64>().unwrap(),
    };
    println!("{:.6} {:.6} ", circ.area(), circ.round());
}

struct Circle {
    radius: f64,
}

impl Circle {
    fn round(&self) -> f64 {
        self.radius * 2.0 * PI
    }
    fn area(&self) -> f64 {
        self.radius.powf(2.0) * PI
    }
}



Measured memory_bytes: 5060
using System;
using System.Collections.Generic;
using System.Linq;

namespace ITP1_7_B
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var nx = ReadInt();
                int n = nx[0];
                int x = nx[1];

                if (n == 0 && x == 0) break;

                int ans = 0;
                for (int i = 1; i <= n - 2; i++)
                {
                    for (int j = i + 1; j <= n - 1; j++)
                    {
                        for (int k = j + 1; k <= n; k++)
                        {
                            int sum = i + j + k;
                            if (sum == x) ans++;
                        }
                    }
                }

                Console.WriteLine(ans);
            }

            Console.ReadKey();
        }

        static int[] ReadInt()
        {
            int[] ret = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return ret;
        }
        static long[] ReadLong()
        {
            long[] ret = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return ret;
        }
    }
}



Measured memory_bytes: 18376
n=int(input())
a=list(map(int,input().split()))
lo=0
cnt=0
maxi=0
while lo<n-1:
    if a[lo]>=a[lo+1]:
        cnt+=1
        lo+=1
    else:
        maxi=max(maxi,cnt)
        cnt=0
        lo+=1
    if lo==n-1:
        maxi=max(maxi,cnt)
print(maxi)

Measured memory_bytes: 15020
def main():
    restaurant_map = {}
    n = int(input())
    for i in range(n):
        line = input()
        s, p = line.split(" ")
        p = int(p)
        if s not in restaurant_map:
            restaurant_map[s] = []
        restaurant_map[s].append({
            'no': i+1,
            'point': p,
        })
    for key in sorted(restaurant_map.keys()):
        restaurant_list = sorted(restaurant_map[key], key=lambda x: x['point'], reverse=True)
        for r in restaurant_list:
            print(r['no'])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import bisect

N = int(input())
A = tuple(sorted(map(int, input().split())))
B = tuple(map(int, input().split()))
C = tuple(sorted(map(int, input().split())))
res = 0
for i in range(N):
	res += bisect.bisect_left(A, B[i])*(N - bisect.bisect_right(C, B[i]))
print(res)

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

using namespace std;
const int N=2e5+10;
const int MOD=1e9+7;
typedef long long ll;
ll a[N];
ll pre[N];
ll dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    pre[1]=a[1];
    for(int i=3;i<=n;i+=2) pre[i]=pre[i-2]+a[i];
    //dp[1]=a[1];
    for(int i=2;i<=n;i++){


        if(i%2){
            dp[i]=max(dp[i-2]+a[i],dp[i-1]);
        }
        else{
            dp[i]=max(dp[i-2]+a[i],pre[i-1]);
        }
        }

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


Measured memory_bytes: 8324
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var l = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&l[i])
	}

	var max, sum int
	for _, v := range l {
		sum += v
		if v > max {
			max = v
		}
	}

	if max < (sum - max) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    // Your code here!

    int n;
    int a[100000] = {0};
    
    scanf("%d",&n);
    for(int i=0; i<n; i++){
      scanf("%d",&a[i]);
    }
    
    long long sum = 0;
    int min = a[0];
    int max = a[0];
    
    for(int i=0; i<n; i++){
      sum += a[i];
      if(min > a[i]) min = a[i];
      if(max < a[i]) max = a[i];
    }
    printf("%d %d %ld\n",min,max,sum);
    
}
    



Measured memory_bytes: 2236
#include <stdio.h>

int main(){
	int n;
	scanf("%d" ,&n);
	if(n >= 100 && n <= 999){
		if(n % 10 == 7){
			printf("Yes\n");
		}
		else if(n / 10 % 10 == 7){
			printf("Yes\n");
		}
		else if(n / 100 == 7){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1624
n,m=map(int,input().split())
info=[]
for i in range(m):
    info.append(list(map(int,input().split())))
start,goal=info[0][0],info[0][1]
c=0

for i in range(1,m):
    start=max(start,info[i][0])
    goal=min(goal,info[i][1])
    if start>goal:
        c=1
        break
    
if c==0:
    print(goal-start+1)
else:
    print(0)

Measured memory_bytes: 27344
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>



int main(int argc, char* argv[])
{
  using std::cin;
  using std::cout;
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N;
  cin >> N;
  std::string si;

  int res = 0;
  int A = 0, B = 0, BA = 0;
  for (int i = 0; i < N; ++i)
  {
    cin >> si;

    if (si.front() == 'B' && si.back() == 'A') ++BA;
    else if (si.front() == 'B') ++B;
    else if (si.back() == 'A') ++A;

    char prev = 'Z';
    for (char c : si)
    {
      if (c == 'B' && prev == 'A') ++res;
      prev = c;
    }
  }

  if (BA)
  {
    res += BA-1;
    BA = 1;
  }

  const int c1 = std::min(A, std::min(B, BA));
  res += 2*c1;
  A -= c1; B -= c1; BA -= c1;

  if (A < B) A += BA;
  else B += BA;

  res += std::min(A, B);

  cout << res << "\n";

  return 0;
}


Measured memory_bytes: 256
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int MAXN = 5*1e5+10;

LL a[MAXN];

int f(int sum,int p)
{
	return (sum ? f(sum/p,p)+sum%p : 0);
}

int main()
{
	int n;
	scanf("%d",&n);
	int cnt=INF;
	for (int i=0;i<=n;i++) cnt=min(cnt,f(i,6)+f(n-i,9));
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)
#include <utility>

using namespace std;
#define ll long long

bool comp(pair<ll, int> p1, pair<ll, int> p2) {
  return p1.first < p2.first;
}

int main(){
  vector<pair<ll, int> > p;
  int N, M;
  cin >> N >> M;
  for(int i=0; i<N; i++) {
    ll a;
    int b;
    cin >> a >> b;
    p.push_back(make_pair(a, b));
  }
  sort(p.begin(), p.end(), comp);
  ll ans = 0LL;
  int i = 0;
  while(M > 0) {
    ans += p[i].first * min(M, p[i].second);
    M -= min(M, p[i].second);
    i++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() 
{
	int h;
	cin >> h;
	int w;
	cin >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++) 
    {
		cin >> a[i];
	}
 
	vector<bool> row(h, false);
	vector<bool> col(w, false);
	for (int i = 0; i < h; i++) 
    {
		for (int j = 0; j < w; j++) 
        {
			if (a[i][j] == '#') 
            {
				row[i] = true;
				col[j] = true;
			}
		}
	}
 
	for (int i = 0; i < h; i++) 
    {
		if (row[i]) {
			for (int j = 0; j < w; j++) 
            {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}


Measured memory_bytes: 504
package main

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

var (
	scanner = bufio.NewScanner(os.Stdin)
	w       = bufio.NewWriter(os.Stdout)
)

func readInt() (read int) {
	scanner.Scan()
	read, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return
}

func main() {
	scanner.Split(bufio.ScanWords)
	defer w.Flush()

	n := readInt()

	a := map[int]int{}
	for i := 0; i < n; i++ {
		j := readInt()
		a[j]++
	}

	var total = 0
	for k, v := range a {
		total += k * v
	}

	q := readInt()
	for i := 0; i < q; i++ {
		b := readInt()
		c := readInt()
		cnt := a[b]
		delete(a, b)
		a[c] += cnt

		dif := (c - b) * cnt
		total += dif
		fmt.Fprintln(w, total)
	}
}


Measured memory_bytes: 8276
n,k = map(int, input().split())
a = list(map(int, input().split()))
from collections import Counter
a1 = Counter(a).most_common()
num = 0
if k < len(a1):
    for i in range(1,len(a1)-k+1):
        num += a1[-i][1]
    print(num)
else:
    print(0)

Measured memory_bytes: 42704
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;
void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main() {
	int N, D; cin >> N >> D;
	int a, b;
	a = D * 2 + 1;
	b = N % a;
	if (b != 0) {
		cout << N / a + 1 << endl;
	}
	else {
		cout << N / a << endl;
	}

	//cout << b;



	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=1e5+7;
int read(){
	int ans=0,f=1,c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
	return ans*f;
}
int ans[M],T[M];
struct pos{int T,s;}e[M];
int x,k=1,n,m,sgn=-1;
void calc(LL &k){if(k<0) k=0; if(k>x) k=x;}
int main(){
	x=read();
	n=read(); for(int i=1;i<=n;i++) T[i]=read();
	m=read(); for(int i=1;i<=m;i++) e[i].T=read(),e[i].s=read();
	LL h=0,mx=x,mn=0;
	for(int i=1;i<=m;i++){
		while(k<=n&&T[k]<=e[i].T){
			LL v=(T[k]-T[k-1])*sgn;
			mx+=v; mn+=v; h+=v;
			calc(mx); calc(mn);
			k++;sgn*=-1; 
		}//printf("[%lld %lld %lld]\n",mx,mn,h);
		LL now=e[i].s+h,nowh=(e[i].T-T[k-1])*sgn; //printf("[%lld %lld]\n",now,nowh);
		if(now<mn) now=mn;
		if(now>mx) now=mx;
		now+=nowh; calc(now);
		printf("%lld\n",now);
	}
	return 0;
}

Measured memory_bytes: 2304
S = input()
a = len(S)
b = -1
for i in range(len(S)):
    if S[i] == "C":
        a = i
        break
for i in range(len(S)):
    if S[len(S)-i-1] == "F":
        b = len(S)-i-1
        break
if a < b:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 8964
# 下、右、上、左
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

H, W = map(int, input().split())
s = [input() for i in range(H)]


def main():
    for y in range(H):
        for x in range(W):

            if s[y][x] == '.':
                continue

            cnt = 0

            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]

                if ny < 0 or H <= ny\
                        or nx < 0 or W <= nx\
                        or s[ny][nx] == '.':
                    continue

                cnt += 1

            if cnt == 0:
                print("No")
                return

    print("Yes")
    return


main()


Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define MAX_V 200005
//lower_bound使え

struct edge{int to; ll cost;};
typedef pair<ll, int> P;//最短距離、頂点番号

int V;
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d,d+V,LINF);
  d[s] = 0;
  que.push(P(0,s));

  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    rep(i, G[v].size()){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

/*
 * 頂点数をVに代入すること
 */
int main(void){

  ll n,m;cin>>n>>m;
  V = n;
  rep(i,m){
    ll l,r,c;
    cin>>l>>r>>c;
    l--;r--;
    G[l].push_back({(int)r, c});
  }
  rep(i,n-1){
    G[i+1].push_back({(int)i, (ll)0});
  }

  dijkstra(0);
  if(d[n-1] == LINF){
    cout<<-1<<endl;
    return 0;
  }
  cout<<d[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 11772
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 500000000
using namespace std;

typedef pair<int,int> P;

int dis[6100];
vector<P> g[6100];
int g2[310][310];
map<string,int> id;
vector<int> gas;
int n,m,cap,d;
string a,b;

int main(){
  ios_base::sync_with_stdio(false);
  while(cin >> n >> m >> cap,n||m||cap){
    id.clear(); gas.clear();
    for(int i=0;i<6100;i++)g[i].clear();
    
    cin >> a >> b;
    id[a] = id.size(); id[b] = id.size();
    gas.push_back(1); gas.push_back(2);

    for(int i=0;i<n;i++){
      cin >> a >> b >> d;
      if(id.find(a) == id.end())id[a] = id.size();
      if(id.find(b) == id.end())id[b] = id.size();
      g[id[a]].push_back(P(d,id[b]));
      g[id[b]].push_back(P(d,id[a]));
    }
    for(int i=0;i<m;i++){
      cin >> a;
      gas.push_back(id[a]);
    }

    for(int i=0;i<gas.size();i++){
      for(int j=0;j<gas.size();j++)g2[i][j] = INF;
      g2[i][i] = 0;
    }

    for(int i=0;i<gas.size();i++){
      for(int j=0;j<=id.size();j++)dis[j] = INF;
      dis[gas[i]] = 0;
      priority_queue<P,vector<P>,greater<P> > q;
      q.push(P(0,gas[i]));
      
      while(q.size()){
	P p = q.top();q.pop();
	int dist = p.first;
	int pos = p.second;
	
	for(int x=0;x<g[pos].size();x++){
	  int tdis = dist + g[pos][x].first;
	  int nxt = g[pos][x].second;
	  if(dis[nxt] > tdis){
	    dis[nxt] = tdis;
	    q.push(P(tdis,nxt));
	  }
	}
      }
      for(int j=0;j<gas.size();j++){
	if(cap*10<dis[gas[j]])continue;
	g2[i][j] = dis[gas[j]];	
      }
    }

    for(int k=0;k<gas.size();k++)
      for(int i=0;i<gas.size();i++)
	for(int j=0;j<gas.size();j++)
	  g2[i][j] = min(g2[i][j],g2[i][k] + g2[k][j]);

    if(g2[0][1] == INF)cout << -1 << endl;
    else cout << g2[0][1] << endl;
  }
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    int2(m, k);
    vi state(n, -1);
    vi room(m);
    rep(i, m) {
        cin >> room[i];
        room[i]--;
        state[room[i]] = i;
    }

    vvi graph(n, vi(k, 0));
    rep(i, n) {
        rep(j, k) {
            cin >> graph[i][j];
            graph[i][j]--;
        }
    }

    vi dp((1 << m), INF);
    dp[(1 << m)-1] = 0;
    queue<int> que;
    que.push((1<<m)-1);
    while (dp[0] == INF) {
        int tmp = que.front();
        que.pop();
        //cout << tmp << ":" << endl;
        rep(i, k) {
            int nxt = 0;
            rep(j, m) {
                if (tmp & (1 << j)) {
                    int ikisaki = graph[room[j]][i];
                    if (state[ikisaki] != -1) {
                        //cout << state[ikisaki] << " ";
                        nxt |= (1 << state[ikisaki]);
                    }
                }
            }
            //cout << nxt << " ";
            if (dp[nxt] > dp[tmp]+1) {
                dp[nxt] = dp[tmp] + 1;
                que.push(nxt);
            }
        }
        //cout << endl;
    }
    cout << dp[0] << endl;

    return 0;
}

Measured memory_bytes: 3804
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
using P = pair<int,int>;
using ll = long long;
using namespace std;
int main(void){
    int n, k;
    cin >> n >> k;
    int d[k];
    int a[k][n];
    rep(i, k){
        cin >> d[i];
        rep(j, d[i]){
            cin >> a[i][j];
        }
    }
    
    int c[n];
    rep(i, n){c[i] =0;}
    rep(i, k){
        rep(j, d[i]){
            ++c[a[i][j]-1];
        }
    }
    
    int ans = 0;
    rep(i, n){
        if(c[i] == 0){++ans;}
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3568
#include<iostream>
using namespace std;
int main (){
    int a, b, c;
    cin >> a >> b >> c;
   int x, y, z;
    x = max(max(a, b), max(b, c));
    y = min(min(a, b), min(b, c));
    z = a + b + c - (x + y);
    cout << y << " " << z << " "<< x << endl;
    return 0;
}


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


int main(){
   int n,k;
  cin>>n>>k;
  int h[n];
  for (int i=0;i<n;i++)
     cin>>h[i];
  int b[n],mi;
  b[0]=0;
  int a[n][k];
  for (int i=0;i<k;i++)
      a[0][i]=0;
  for (int i=1;i<n;i++){
    mi=INT_MAX;
     for (int j=0;j<k;j++){
         if (j<i){
           a[i][j]=b[i-j-1]+abs(h[i]-h[i-j-1]);
           mi=min(mi,a[i][j]);}
         else
            a[i][j]=0;
     }
    b[i]=mi;
}
           
  
 cout<<b[n-1]<<endl; 
  
  return 0;
}

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

#define INF (INT32_MAX/2)

int main() {
	int N;

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

	vector<int> sum( N + 1 );
	vector<int> sumr( N + 1 );
	for( int i = 0; i < N; i++ ) {
		sum[i + 1] = sum[i] + W[i];
		sumr[N - 1 - i] = sumr[N - i] + W[N - 1 -i];
	}
	int ans = INF;
	for( int i = 0; i < N + 1; i++ ) {
		ans = min( ans, abs( sum[i] - sumr[i] ) );
	}

	cout << ans << endl;

	return 0;
}


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

int64_t f(int64_t x){//f(0,x)
    int64_t ret=((x&3)==1||(x&3)==2)?1:0;
    for(int b=1;b<45;b++){
        if((1LL<<b)&x){
            if((x&1)==0)ret|=(1LL<<b);
        }
    }
    return ret;
} 

int main(){
    int64_t A,B;
    cin>>A>>B;
    cout<<((A?f(A-1):0)^f(B))<<endl;

    return 0;
}

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

int main() {
  long long N,M,X;
  cin >> N >> M >> X;
  vector<long long> C(12);
  vector<vector<long long>> A(12,vector<long long> (M));
  for (int i=0; i<N; i++) {
    cin >> C[i];
    for (int j=0; j<M; j++) {
      cin >> A[i][j];
    }
  }
  for (int i=N; i<12; i++) {
    C[i] = 0;
    for (int j=0; j<M; j++) {
      A[i][j] = 0;
    }
  }
  
  long long ans = 1000000000;
  long long term;
  vector<long long> terma(M);
  bool ccc = false;
  for (int i_1 = 0; i_1<2; i_1++) {
  for (int i_2 = 0; i_2<2; i_2++) {
  for (int i_3 = 0; i_3<2; i_3++) {
  for (int i_4 = 0; i_4<2; i_4++) {
  for (int i_5 = 0; i_5<2; i_5++) {
  for (int i_6 = 0; i_6<2; i_6++) {
  for (int i_7 = 0; i_7<2; i_7++) {
  for (int i_8 = 0; i_8<2; i_8++) {
  for (int i_9 = 0; i_9<2; i_9++) {
  for (int i_10 = 0; i_10<2; i_10++) {
  for (int i_11 = 0; i_11<2; i_11++) {
  for (int i_12 = 0; i_12<2; i_12++) {
    ccc = true;
    term = 0;
    for (int j=0; j<M; j++) {
      terma[j] = 0;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[0][j] * i_1;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[1][j] * i_2;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[2][j] * i_3;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[3][j] * i_4;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[4][j] * i_5;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[5][j] * i_6;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[6][j] * i_7;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[7][j] * i_8;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[8][j] * i_9;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[9][j] * i_10;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[10][j] * i_11;
    }
    for (int j=0; j<M; j++) {
      terma[j] += A[11][j] * i_12;
    }
    for (int j=0; j<M; j++) {
      if (terma[j] < X) {
        ccc = false;
      }
    }
    if (!ccc) {
      continue;
    }
    term = C[0] * i_1 + C[1] * i_2 + C[2] * i_3 + C[3] * i_4 + C[4] * i_5 + C[5] * i_6 + C[6] * i_7 + C[7] * i_8 + C[8] * i_9 + C[9] * i_10 + C[10] * i_11 + C[11] * i_12;
    ans = min(ans,term);
  }
  }
  }
  }
  }
  }
  }
  }
  }
  }
  }
  }
  if (ans == 1000000000) {
    ans = -1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  string s;
  cin >> n >> s;
  string t = "ABC";
  vector<int> result; 
  int size = t.size();
  int f = s.find(t);
  while (f != ::string::npos) {
    result.push_back(f);
    f = s.find(t,f+size);
  }
  cout << result.size() << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
typedef vector<int> vi;
typedef long long ll;
int N;
string X;
int chara[26];
vector<int> same[10];
int sameset=0;
set<char> st;
int main(void)
{
  memset(chara,0,sizeof(chara));
  cin >> N >> X;
  for(int i=0;i<int(X.size());i++)
    {
      if(X[i]!='+')
	{
	  chara[int(X[i]-'a')]++;
	  st.insert(X[i]);
	}
    }
  for(int i=1;i<=9;i++)
    {
      for(int j=0;j<26;j++)
	{
	  if(chara[j]==i)
	    {
	      same[i].push_back(j);
	    }
	}
    }
  for(int i=2;i<=9;i++)
    {
      if(int(same[i].size())>=1)
	{
	  sameset++;
	}
    }
  int direct=0;
  direct=int(st.size()-1)+(int(st.size())-int(same[1].size()))*3+int(same[1].size());
  int kakko=int(same[1].size())*2;
  if(sameset>=1) kakko+=(sameset-1);
  for(int i=2;i<=9;i++)
    {
      if(int(same[i].size())>=2)
	{
	  kakko+=int(same[i].size())+int(same[i].size()-1)+4;
	}
	else if(int(same[i].size()==1)) kakko+=3;
    }
  cout << min(direct,kakko) << endl;
  return 0;
}



Measured memory_bytes: 3220
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0233
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int n = RInt();
                if (n == 0) break;

                Stack<string> res = new Stack<string>();
                while (n != 0)
                {
                    int q = n / -10;
                    int r = n - (q * -10);

                    if (r < 0)
                    {
                        r += 10;
                        q += 1;
                    }

                    res.Push(r.ToString());
                    n = q;
                }
                Console.WriteLine(WAr(res, string.Empty));
            }
        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}



Measured memory_bytes: 14596
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

struct UnionFind {
    vector<int> par;
    UnionFind(int n) : par(n, -1) {};
    
    void init(int n) {
        par.assign(n, -1);
    }

    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return -par[root(x)];
    }
};

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    rep(i, m) {
        cin >> a[i] >> b[i];
        --a[i], --b[i];
    }

    UnionFind uf(n);

    vector<ll> res(m);
    ll sum = n * (n - 1) / 2;
    for (int i = m - 1; i >= 0; --i) {
        res[i] = sum;

        if (uf.issame(a[i], b[i])) continue;
        sum -= uf.size(a[i]) * uf.size(b[i]);
        uf.unite(a[i], b[i]);
    }

    rep(i, m) {
        cout << res[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3328
n, m = map(int, input().split())
l = [0] * m
for i in range(n):
  a = list(map(int, input().split()))
  k = a[0]
  for j in range(k):
    l[a[j + 1] - 1] += 1
ans = 0
for i in l:
  if i == n:
    ans += 1
print(ans)


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

int main() { 
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 3608
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
ab  = [tuple(map(int, input().split())) for _ in range(n)]
ba = [(b, a) for (a, b) in ab]
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ba = sorted(ba)
#print(ba)

qa = 0
for (b, a) in ba:
    qa += a

    if qa > b:
        print('No')
        break
else:
    print('Yes')


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

int main()
{
    int yen = 0;
    int happiness = 0;
    scanf("%d",&yen);

    int yen500 = yen/500;
    happiness += 1000*yen500;
    yen = yen % 500;
    int yen5 = yen/5;
    happiness += 5*yen5;

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

    return 0;
}

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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf("%.12lf\n",mid);
// __builtin_popcount(int) count 1's in binary
// get decimal pert of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
int mod = 998244353;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
/*string sentence = "And I feel fine...";
    istringstream iss(sentence);
*/  

double eps = .000000001;


int main ()
{
  prep();
  int r;
  cin >> r;
  cout << r*r*3;
  return 0; 
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int l = sc.nextInt();
		int r = sc.nextInt();
		int d = sc.nextInt();

		int count = 0;

		for (int i = l; i <= r; i++) {
			if (i % d == 0) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 35592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int num[1000001];
int main() {
  int N;
  cin >> N;
  int A[N];
  int ans = 0;
  for (int i = 0; i < 1000001; i++) num[i] = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    num[A[i]]++;
  }
  for (int i = 0; i < N; i++) {
    bool OK = true;
    num[A[i]]--;
    for (int j = 1; j * j <= A[i]; j++) {
      if (A[i] % j != 0) {
        continue;
      }
      if (num[j] != 0) {
        OK = false;
      }
      if (num[A[i]/j] != 0) {
        OK = false;
      }
    }
    num[A[i]]++;
    if (OK) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

ll t[200001];

int main() {
    #ifdef DEBUG
        freopen("in.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    ll N, T; cin >> N >> T;
    for (int i = 0; i < N; i++) {
        cin >> t[i];
    }

    ll total = T;
    for (int i = 1; i < N; i++) {
        if (t[i - 1] + T <= t[i]) {
            total += T;
        } else {
            total -= (t[i - 1] + T) - t[i];
            total += T;
        }
    }
    cout << total << '\n';




    return 0;
}


Measured memory_bytes: 1792
#include<algorithm>
#include<chrono>
#include<ctime>  
#include<climits>
#include<functional>
#include<numeric>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<random>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<cassert>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
// #include<bits/stdc++.h>
using namespace std;
 
struct Debug{
    int cnt = 0;
    bool on = false;
    char debug[10] = "debug";
    template<class T>
    Debug & operator<<(const T & v) {
        if(on && cnt++ == 0) cerr << "debug: ";
        if(on) cerr << v << ' ';
        return *this;
    }
    Debug & operator<<(ostream&(*pManip)(ostream&)) {
        if(on) cerr << (*pManip);
        cnt = 0;
        return *this;
    }
} debug;
#define rep(i, a, b) for(auto i = (a); i < (b); i++)
#define rrep(i, a, b) for(auto i = (a); i > (b); i--)
#define all(v) (v).begin(), (v).end()
#define print(v) {if(debug.on){for(auto x : v) debug << x; debug << endl;}}
#define printn(v, n) {if(debug.on){for(int _i = 0; _i < n; _i++) debug << *(v + _i); debug << endl;}}
 
typedef unsigned long long ull;
typedef long long ll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
 
const int MAXN = 1e6 + 10;

int n, k;
int dp[110][2];

pair<ll, ll> cal(string s, int flag) {
	dp[0][0] = 1;
	if(flag && s[0] == s[n - 1])
		dp[0][1] = 1e9;
	else
		dp[0][1] = 0;

	for(int i = 1; i < n; i++) {
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
		if(s[i] == s[i - 1])
			dp[i][1] = dp[i - 1][0];
		else
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
	}
	return {dp[n - 1][0], dp[n - 1][1]};
}
 
int main(int argc, char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    if(argc > 1 && !strcmp(argv[1], debug.debug)) debug.on = true;

    string s;
    cin >> s;
    n = s.size();
    cin >> k;

    if(n == 1) {
    	cout << k / 2 << endl;
    	return 0;
    }

    auto p0 = cal(s, 0);
    auto p1 = cal(s, 1);

    // if(s[0] != s[n - 1]) {
    // 	ll res = min(p0.first, p0.second) * k;
    // 	cout << res << endl;
    // 	return 0;
    // }

    ll r1 = p0.first * k;
    ll r2 = p0.second * ((k + 1) / 2) + p1.first * (k / 2);
    ll r3 = p0.second + p1.second * (k - 1);

    ll res = min({r1, r2, r3});
    cout << res << endl;


    return 0;
 
}























Measured memory_bytes: 256
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    while(cin>>n)
    {
        vi a;
        rep(i,n)
        {
            vp(a,x);
        }
        s=0,n--;
        s=gcd(a[0],a[1]);
        rep(i,n)
        {
            s=gcd(s,a[i+1]);
        }
        cout<<s<<en;
    }
}



Measured memory_bytes: 1400
#include <cstdio>
#include<cstring>
using namespace std;

int main()
{
    int a,b,k,i;
    scanf("%d%d%d",&a,&b,&k);
    if(b-a+1>=2*k)
    {
        for(i=a; i<a+k; i++)
            printf("%d\n",i);
        for(i=b-k+1; i<=b; i++)
            printf("%d\n",i);
    }
    else
    {
        for(i=a; i<=b; i++)
            printf("%d\n",i);
    }
    return 0;
}


Measured memory_bytes: 128
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

unordered_map<ll, ll> mp;


int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = unordered_map<ll, ll>();
#pragma clang diagnostic pop
#endif
        string s, t;
        cin >> s >> t;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end(), greater<>());
        if (s < t) cout << "Yes" << endl;
        else cout << "No" << endl;

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

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

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

    std::sort(h.begin(), h.end());
    int diff = INT_MAX;
    for (int i = 0; i < n-k+1; i++) {
        diff = std::min(h[i+k-1] - h[i], diff);
    }

    std::cout << diff << std::endl;

    return 0;
}


Measured memory_bytes: 640
import math
from collections import Counter

mod = 10**9+7
n = int(input())
c = Counter()
cc = Counter()

for _ in range(n):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        c[-1] += 1
        continue
    elif a != 0 and b == 0:
        a, b = 1, 0
    elif a == 0 and b != 0:
        a, b = 0, 1
    else:
        a, b = a//math.gcd(a, b), b//math.gcd(a, b)

    c[(a, b)] += 1
    cc[(a, b)] += 1

l = []

for r in cc.keys():
    if r == -1:
        continue
    ra = c[r]

    a, b = r
    if a == 0:
        r_inv = (1, 0)
    elif b == 0:
        r_inv = (0, 1)
    elif a > 0:
        r_inv = (-b, a)
    else:
        r_inv = (b, -a)
    rb = c[r_inv]

    if ra >= 0 and rb >= 0:
        l.append([ra, rb])
        c[r] -= 10**9
        c[r_inv] -= 10**9

ans = 1
for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1
    ans %= mod

ans = (ans-1) + c[-1]
ans %= mod

print(ans)


Measured memory_bytes: 178184
#include <bits/stdc++.h>
using namespace std;
  
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 1e5 + 5, INF = 1e9;
vector<int> g[N];
int dp[N], dp_ret[N], sum[N], wh_ct[N], adj_wr[N];

string s;
int ans = INF;

void dfs(int node, int anc) {
    int ch = 1;
    for (int to : g[node]) {
        if (to != anc) {
            dfs(to, node);
            sum[node] += dp_ret[to] + 2;
            ch ^= 1;
        }
    }

    dp_ret[node] += (s[node] ^ ch) + sum[node];
    dp[node] = dp_ret[node];

    for (int to : g[node]) {
        if (to != anc) {
            dp[node] = min(dp[node], sum[node] - dp_ret[to] - 2 + 1 +
                dp[to] + (s[node] ^ ch ^ 1));
        }
    }
}

void walk(int node, int anc, int up, int up_ret) {
    ans = min(ans, up_ret + 2 + sum[node] + (s[node] ^ ((int)g[node].size() & 1)));

    multiset<int> st;
    for (int to : g[node]) {
        st.insert(to == anc ? up + 1 - up_ret - 2 : dp[to] + 1 - dp_ret[to] - 2);
    }

    if (!st.empty()) {
        ans = min(ans, sum[node] + up_ret + 2 + *st.begin() 
            + (s[node] ^ 1 ^ ((int)g[node].size() & 1)));
    }

    for (int to : g[node]) {
        if (to != anc) {
            int n_up_ret = up_ret + 2 + sum[node] - dp_ret[to] - 2 + (s[node] ^ ((int)g[node].size() & 1)),
                n_up = n_up_ret;

            st.erase(st.find(to == anc ? up + 1 - up_ret - 2 : dp[to] + 1 - dp_ret[to] - 2));

            if (!st.empty()) {
                n_up = min(n_up, sum[node] - dp_ret[to] - 2 + up_ret + 2 + *st.begin() + (s[node] ^ 1 ^ ((int)g[node].size() & 1)));
            }
            
            walk(to, node, n_up, n_up_ret);

            st.insert(to == anc ? up + 1 - up_ret - 2 : dp[to] + 1 - dp_ret[to] - 2);
        }
    }
}

void roam(int node, int anc) {
    wh_ct[node] = s[node];
    for (int to : g[node]) {
        if (to != anc) {
            roam(to, node);
            wh_ct[node] += wh_ct[to];
        }
    }

    vector<int> tmp;
    for (int to : g[node]) {
        if (to == anc || wh_ct[to]) {
            tmp.push_back(to);
        }
    }

    g[node] = tmp;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    cin >> s;

    int rt = 0;
    while (rt < n && s[rt] == 'B')
        rt++;

    if (rt == n) {
        cout << "0\n";
        return 0;
    }

    for (char &c : s) {
        c = (c == 'W');
    }

    roam(rt, -1);
    dfs(rt, -1);
    walk(rt, -1, -1, -2);

    // cout << dp[1] << "\n";

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 27728
#include<bits/stdc++.h>
using namespace std;
int n;
vector<double> p;
vector<vector<double>> dp;


void solve()
{
    dp.resize(n+1, vector<double>(n+1,0.0));
    dp[0][0] = 1;
    for(int i=1; i<=n; i++){
        dp[0][i] = (1-p[i])*dp[0][i-1];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            dp[j][i] = p[i]*dp[j-1][i-1] + (1-p[i])*dp[j][i-1];
        }
    }
    double res = 0.0;
    int m = n/2+1;
    for(int i=m; i<=n; i++){
        res += dp[i][n];
    }
    cout << setprecision(9) << res << '\n';
}

int main()
{
    cin >> n;
    p.resize(n+1);
    for(int i=1; i<=n; i++) cin >> p[i];
    solve();
    return 0;   
}

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

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

    string S, T;
    cin >> S >> T;

    string ans = "";
    for (int i = 0; i < N; i++) {
        ans += S[i];
        ans += T[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
A, B, C, D, E, F = map(int, input().split())

x, y, maxe = 0, 0, 0.0

for a in range(F//(A*100)+1):
    for b in range((F-100*A*a)//(B*100)+1):
        for c in range((F-100*(A*a+B*b))//C+1):
            for d in range((F-100*(A*a+B*b)-C*c)//D+1):
                if A*a+B*b == 0:
                    continue
                e = (C*c+D*d) / (A*a+B*b)
                if e <= E and maxe <= e:
                    maxe = e
                    y = C*c+D*d
                    x = 100*(A*a+B*b) + y

print(x, y)


Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<string.h>
#define ll long long

using namespace std;
const int inf=0x3f3f3f3f;

struct node
{
    string na;
    int order,p;
}s[105];

bool cmp(node a,node b)
{
    if(a.na==b.na) return a.p>b.p;
    else return a.na<b.na;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i].na;
        cin>>s[i].p;
        s[i].order=i+1;
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++)
        cout<<s[i].order<<endl;
}


Measured memory_bytes: 256
N = gets.to_i
arr = gets.split.map(&:to_i).sort.reverse

alice = 0
bob = 0

while arr.count >= 2
  alice += arr[0]
  bob += arr[1]
  arr.shift
  arr.shift
end

if arr.count == 1
  alice += arr[0]
end

a = alice - bob

puts a


Measured memory_bytes: 1788
N, M = map(int, input().split())
connect = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  connect[a].append(b)
  connect[b].append(a)  
  
#print(connect)  
ans = 0
used = [0] * N
for i in range(N):
  if used[i] == 0:
    used[i] = 1
    ans2 = 1
    queue = [i]
    while queue:
      now = queue.pop()
      for j in connect[now]:
        if used[j] == 0:
          used[j] = 1
          queue.append(j)
          ans2 += 1
      #print(queue, used)    
  ans = max(ans, ans2)        
        
print(ans)


Measured memory_bytes: 44720
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;

/*---------------------------------------------------*/

bool binary_search(int data[],int size,int target){
  int l=0,r=size;
  while(r-l>0){
    int mid=(l+r)/2;
    if(data[mid]==target)return true;
    else if(target<data[mid])r=mid;
    else l=mid+1;		 
  }
  return false;
}

int main(){
  int n,q,s[100005],t;
  scanf("%d",&n);
  rep(i,n)scanf("%d",&s[i]);
  scanf("%d",&q);

  int ans=0;
  rep(i,q){
    scanf("%d",&t);
    
    int l=0,r=n;
    while(r-l>0){
      int mid=(l+r)/2;
      if(s[mid]==t){ans++;break;}
      else if(t<s[mid])r=mid;
      else l=mid+1;
    }
  }
  
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 3528
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
# def combmod(n, k, mod=MOD):
#     if k == 0:
#         return 1
#     if k == 1:
#         return n
#     ret = 1
#     for i in range(n - k + 1, n + 1):
#         ret *= i
#         ret %= mod
#
#     for i in range(1, k + 1):
#         ret *= pow(i, mod - 2, mod)
#         ret %= mod
#
#     return ret
#
#
# class Segtree_op():
#     def __init__(self, n):
#         self.size = 1
#         while (n >= 1):
#             self.size = self.size << 1
#             n = n // 2
#
#         self.arr = [self.unit() for i in range(self.size * 2)]
#
#     def op(self, lch, rch):
#         # update min with holding index
#         return lch + rch
#
#     def unit(self):
#         return 0
#
#     def update(self, k, val):
#         k += self.size - 1
#         self.arr[k] = val
#         while (k):
#             k = (k - 1) // 2
#             self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])
#
#     def query(self, l, r):
#         L = l + self.size
#         R = r + self.size
#         s = self.unit()
#         while L < R:
#             if R & 1:
#                 R -= 1
#                 s = self.op(s, self.arr[R - 1])
#
#             if L & 1:
#                 s = self.op(s, self.arr[L - 1])
#                 L += 1
#             L >>= 1
#             R >>= 1
#         return s
#
# def update_daikou(st, k):
#     st.update(k, (st.query(0,k+1)) % MOD)
    # print(st.arr)
 
def main():
    k = getList()
    nums = getList()
    mn, mx = 2,2
    for num in nums[::-1]:
        mn = num * math.ceil(mn / num)
        mx = num * (mx// num) + num - 1
        tm = (mx // num) * num
        if tm < mn or tm > mx:
          print(-1)
          return
 
    print(mn, mx)
 
if __name__ == "__main__":
    main()
 

Measured memory_bytes: 59632
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define mp make_pair
#define ll long long
#define pb push_back


void solve()
{

   string s;
   cin>>s;
   int i;
   long long sum = 0;
   for(i=0;i<s.length();i++)
   {
        long long val =  (s[i]-'0');
        sum = sum + val;
   }

   long long x = 9;
   if(sum%x==0)
   {
       cout<<"Yes";
       return;
   }
   else
   {
       cout<<"No";
       return;
   }

    return;
}


int main()
{

  int t = 1;
  //cin>>t;

  while(t--)
    solve();

  return 0;
}


Measured memory_bytes: 3720
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define FFOR(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define rep(i,n) FOR(i,0,n-1)
#define int long long
#define MOD 998244353
#define MAXN  100005
#define P pair<int,int>
 
int s(int n)
{
	int ans = 0;
	while(n) ans +=n%10,n/=10;
	return ans;	
}
 
 
signed main(){
	
	int k;cin>>k;
	
	int num = 1;
	int keta = 1;
	
	rep(i,k)
	{
		cout << num << endl; 
		while((num + keta)*s(num+2*keta) > (num + 2*keta)*s(num+keta)) keta *=10;
		num += keta;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace  std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector <int> v;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    vector <int> dp;
    dp.resize(n);
    dp[n-1] = 0;
    for(int i = n-2; i >= 0; i--){
        dp[i] = abs(v[i] - v[i+1]) + dp[i+1];
        for(int j = 1; i+j < n and j <= k; j++){
            dp[i] = min(dp[i], abs(v[i] - v[i+j]) + dp[i+j]);
        }
    }
    cout << dp[0] << "\n";
}

Measured memory_bytes: 1024