akhauriyash/Code-Regression huggingface dataset:
MOD = 1000000007
M = 2*10**5 + 10
fact = [1] * M
ifact = [1] * M
for i in range(2, M):
    fact[i] = fact[i - 1] * i % MOD
ifact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(2, M - 1)[::-1]:
    ifact[i] = ifact[i + 1] * (i + 1) % MOD


def comb(n, k):
    if n < 0 or k > n:
        return 0
    return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD


class DP:
    def __init__(self, dp = 1, size = 0):    
        self.dp = dp
        self.size = size

    def __add__(self, other):
        dp = self.dp
        dp *= other.dp
        dp %= MOD
        size = self.size + other.size
        dp *= comb(size, self.size)
        dp %= MOD
        return DP(dp, size)

    def __sub__(self, other):
        size = self.size - other.size
        dp = self.dp
        dp *= pow(comb(self.size, size), MOD - 2, MOD)
        dp %= MOD
        dp *= pow(other.dp, MOD - 2, MOD)
        dp %= MOD
        return DP(dp, size)

    def addRoot(self):
        return DP(self.dp, self.size + 1)


N = int(input())
e = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [v - 1 for v in map(int, input().split())]
    e[a].append(b)
    e[b].append(a)

order = []
parent = [-1] * N
stack = [0]
while stack:
    v = stack.pop()
    order.append(v)
    for c in e[v]:
        if c == parent[v]:
             continue
        stack.append(c)
        parent[c] = v

dp = [DP() for _ in range(N)]
for v in order[1:][::-1]:
    dp[parent[v]] += dp[v].addRoot()
for v in order[1:]:
    d = dp[parent[v]] - dp[v].addRoot()
    dp[v] += d.addRoot()
for d in dp:
    print(d.dp)

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

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

    vector<pair<int, int>> a(N-1);
    for(int i = 0; i < N-1; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());

    vector<long long> p(N+1,0);
    for(int i = 0; i < Q; i++){
        int j, k;
        cin >> j >> k;
        p[j]+=k;
    }

    for(int i = 0; i < N-1; i++){
        p[a[i].second] += p[a[i].first];
    }

    for(int i = 1; i <= N; i++){
        cout << p[i] << endl;
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
      cin >> vec.at(i);
    }
    int m = *min_element(vec.begin(), vec.end());
    int M = *max_element(vec.begin(), vec.end());
    cout << M - m << endl; 
}

Measured memory_bytes: 3632
n, m = map(int, input().split())
num_list = ['X'] * n

def ans():
    if n == 1 and m == 0:
        return 0
    for i in range(m):
        set = list(map(str, input().split()))
        if set[0] == '1' and set[1] == '0' and n != 1:
            return -1
        else:
            if num_list[int(set[0]) - 1] == 'X':
                num_list[int(set[0]) - 1] = set[1]
            elif num_list[int(set[0]) - 1] == set[1]:
                continue
            else:
                return -1

    for i in range(n):
        if num_list[i] == 'X':
            num_list[i] = '1' if i == 0 else '0'

    return ''.join(num_list)

print(ans())


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

int main() {
  string s;
  cin >> s;
  int cnt = 0;
  for (int i = 0; i < s.size() / 2; i++)
    if (s.at(i) != s.at(s.size() - 1 - i)) cnt++;
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<cstdio>
int main(){
	int l,m,n;
	long long int a[100][100],b[100][100],c[100][100];
	int i,j,k;
	scanf("%d %d %d",&l,&m,&n);
	for(i=0;i<l;i++){
		for(j=0;j<m;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			scanf("%lld",&b[i][j]);
		}
	}
	for(i=0;i<l;i++){
		for(j=0;j<n;j++){
			c[i][j] = 0;
			for(k=0;k<m;k++){
				c[i][j] += a[i][k] * b[k][j];
			}
		printf("%lld",c[i][j]);
		if(j==n-1) printf("\n");
		else printf(" ");
		}
	}
	return 0;
}

Measured memory_bytes: 2868
#include<stdio.h>
#include<stdlib.h>
int main()
{
    char str[10];
    int z, x, y;

    scanf("%[^\n]", str);
    z = strcmp(str, "Sunny");
    x = strcmp(str, "Cloudy");
    y = strcmp(str, "Rainy");


    if(z == 0)
    {
        printf("Cloudy");
    }

    else if(x == 0)
    {
        printf("Rainy");
    }

    else if(y == 0)
    {
        printf("Sunny");
    }

    return 0;

}


Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	char s[110];
	scanf("%s",s+1);
	int len=strlen(s+1),ans=len;
	for(char c='a';c<='z';c++)
	{
		int last=0,d=0;
		for(int i=1;i<=len;i++)
			if(s[i]==c)
			{
				d=max(d,i-last-1);
				last=i;
			}
		d=max(d,len-last);
		ans=min(ans,d);	
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iomanip>

const long long MOD = 1000000007;

long long FAC[3000], INV_FAC[3000], INV[3000];

void make_factorial() {
	FAC[0] = FAC[1] = 1;
	INV_FAC[0] = INV_FAC[1] = 1;
	INV[0] = 0;
	INV[1] = 1;
	for(int i = 2; i < 3000; ++i) {
		FAC[i] = FAC[i-1] * i % MOD;
		INV[i] = MOD - INV[MOD % i] * (MOD / i) % MOD;
		INV_FAC[i] = INV_FAC[i-1] * INV[i] % MOD;
	}
}

long long factorial(int n) {
	long long fac = 1;
	for(int i = 0; i < n; ++i) {
		fac *= (i + 1);
	}
	if(n < 0) fac = 0;
	return fac;
}

long long factorial2(int n, int m) {
	long long fac = 1;
	for(int i = m; i < n; ++i) {
		fac *= (i + 1);
	}
	if(n < 0) fac = 0;
	return fac;
}

long long factorial3(int n, int m, int l) {
	long long fac = 1;
	if(n < 0 || m < 0 || l < 0) fac = 0;
	else fac = FAC[n] * (INV_FAC[m] * INV_FAC[l] % MOD) % MOD;
	return fac;
}

int main(void) {
	// in
	int n, k;
	std::cin >> n >> k;
	
	make_factorial();

	std::vector<long long> n_op(k+1);
	n_op[1] = n - k + 1;
	for(int i = 2; i <= k; ++i) {
		long long buf = 0;
		buf = factorial3(n - k + 1, n - k - i + 1, i);
		buf *= factorial3(k - 1, k - i, i - 1);
		buf %= MOD;
		n_op[i] = buf;
	}

	for(int i = 1; i <= k; ++i) {
		std::cout << n_op[i] << std::endl;
	}

	return 0;
}


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

namespace AtCoder {
    class Program {
        static void Main(string[] args) {

            var s = Console.ReadLine().ToList();
            var n = Console.ReadLine().ToList();

            var ans = "No";
            for (int i = 0; i < s.Count; i++) {
                if (s.SequenceEqual(n)) {
                    ans = "Yes";
                }
                char temp;
                temp = s[0];
                s.RemoveAt(0);
                s.Add(temp);
            }

            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13152
#include <functional>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <sstream>
#include <numeric>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
 
using namespace std;
 
#define pii pair<int, int>
#define rank asdf
#define ll long long
 
const int mod = (int)1e9 + 7;

int n;
int a[2020];

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j < i; ++j){
            // a[i] - a[j] < x
            int l = 1, r = j - 1;
            int res = -1;
            while(r >= l){
                int mid = (l + r) >> 1;
                if(a[mid] > a[i] - a[j]){
                    r = mid - 1;
                    res = mid;
                }else{
                    l = mid + 1;
                }
            }
            if(res != -1){
                ans += j - res;
            }
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define fi first
#define se second
const int MOD=1e9+7;
void read(int &x){
	char ch=getchar();x=0;
	for (;ch==' '||ch=='\n';ch=getchar());
	for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
void write(ll x){
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
int H,W,n;
ll dp[3004],ans,cnt,inv[200004];
pii x[3004];
ll dat1[200004],dat2[200004];
void init(){
	cnt=1;
	inv[1]=1,dat1[0]=dat1[1]=1,dat2[H+W-1]=1;
	for (int i=2;i<H+W-1;i++)inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD,cnt=cnt*i%MOD,dat1[i]=dat1[i-1]*inv[i]%MOD;
	for (int i=H+W-2;i>0;i--) dat2[i]=dat2[i+1]*inv[i]%MOD;
}
ll posway(int h,int w){
	return cnt*dat2[h+w+1]%MOD*dat1[w]%MOD*dat1[h]%MOD;
}
int main(){
	read(H),read(W),read(n);
	init();
	for (int i=1;i<=n;i++) read(x[i].fi),read(x[i].se);
	sort (x+1,x+1+n);
	for (int i=1;i<=n;i++){
		dp[i]=posway(x[i].fi-1,x[i].se-1);
		for (int j=1;j<i;j++) if (x[i].fi>=x[j].fi && x[i].se>=x[j].se) dp[i]=(dp[i]-dp[j]*posway(x[i].fi-x[j].fi,x[i].se-x[j].se)%MOD+MOD)%MOD;
	}
	ans=posway(H-1,W-1);
	for (int i=1;i<=n;i++) ans=(ans-dp[i]*posway(H-x[i].fi,W-x[i].se)%MOD+MOD)%MOD;
	write(ans);
}

Measured memory_bytes: 4992
from functools import reduce
from itertools import accumulate,chain
def rerooting(N, adj, merge, identity, finalize):
    """
    merge: (T,T) -> T, (T, merge)はモノイド
    identity: 単位元
    finalize: T -> T

    以下の形で書けるdpは対応可能
    dp[u,v] = finalize(merge(dp[v,k] for k in adj[v] if k != u))
    ただし(u,v)は辺
    """

    order = [None]*N
    parent = [None]*N
    parent[0] = -1
    stack = [0]
    for i in range(N):
        v = stack.pop()
        order[i] = v
        for u in adj[v]:
            if parent[u] is None:
                parent[u] = v
                stack.append(u)

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        p = parent[v]
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in adj[v] if c != p),
            identity))

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        p = parent[v]
        if len(adj[v]) == 1 and adj[v][0] == p:
            continue
        temp = (dp_up[v],)+tuple(dp_down[u] for u in adj[v] if u != p)+(identity,)
        left = tuple(accumulate(temp,merge))
        right = tuple(accumulate(reversed(temp),merge))
        i = 0
        for u in adj[v]:
            if u != p:
                dp_up[u] = finalize(merge(left[i],right[-i-3]))
                i += 1

    for v,l in enumerate(adj):
        order[v] = reduce(merge,
                    (dp_down[u] for u in adj[v] if u != parent[v]),
                    identity)
        order[v] = finalize(merge(order[v], dp_up[v]))

    return order

def solve(N,M,E):

    adj = [[] for _ in range(N)]
    for a,b in E:
        adj[a].append(b)
        adj[b].append(a)

    def merge(x,y):
        return (x*y)%M
    def finalize(x):
        return x+1

    res = rerooting(N,adj,merge,1,finalize)
    return [v-1 for v in res]


if __name__ == '__main__':
    N,M = map(int,input().split())
    E = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    print(*solve(N,M,E),sep='\n')

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

int main() {
	;
	int N;
	string S;
	cin >> N >> S;
	int i = 0;
	
	for (int i = N - 1; i > 0; i--) {

		while (S[i] == S[i - 1]) {
			S.erase(i - 1, 1);
		}
	}
	

	int M = S.size();
	cout << M << endl;

	return 0;
}



Measured memory_bytes: 512
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,i;
    cin >> n >> i;
    cout << n - i + 1;

    return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main() {
	int x;
	int b;
	int p = 1;
	int y = 1;
	scanf("%d", &x);
	for (int i = 2; i < 33; i++) {
		b = i;
		for (int j = 0; j > -1; j++) {
			if (b >x) {
				b = b / i;
				if (b > y) {
					if (i != b) {
						y = b;
					}
				}
				break;
			}
			b = b * i;
		}
	}
	printf("%d\n", y);
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

fun main (args : Array<String>) {
  val input = Scanner(System.`in`)
  
  while (input.hasNext()) {
    val N = input.nextInt()
    val A = IntArray(N)
    
    for (i in A.indices) {
      A[i] = input.nextInt()
    }
    
    var stoolHeightSum = 0L
    for (i in 1..A.lastIndex) {
      if (A[i] < A[i - 1]) {
        stoolHeightSum += A[i - 1] - A[i]
        A[i] = A[i - 1]
      }
    }
    
    println(stoolHeightSum)
  } 
}

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

int main(){
  int n;
  cin >> n;
  int ans[n+1] = {};
  for(int x = 1; x*x <= n; x++) {
    for(int y = 1; y*y <= n; y++) {
      for(int z = 1; z*z <= n; z++) {
        int v = x*x + y*y + z*z + x*y + x*z + y*z;
        if(v <= n) ans[v]++;
      }
    }
  }
  for(int i = 1; i <= n; i++) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 3632
from sys import stdin
a = stdin.readline().strip()
ans = 0
n = len(a)
plus = n-1
b = [a[0]]
for i in xrange(1,n):
    b.append('')
    b.append(a[i])
    
total = 1<<plus
#print b,total
for i in xrange(total):
    x = ''
    c = list(b)
    #print "mask",i,c
    for j in xrange(n-1):
        if i & (1<<j):
            c[2*j+1] = '+'
    #print c            
    #print ''.join(c)
    ans += eval(''.join(c))
print ans            
    

Measured memory_bytes: 2568
#include <iostream>
#include <cmath>

using namespace std;

int main(){
  int N;
  cin >> N;
  int A[N+2];
  //実装上，初めと終わりに原点を入れる
  A[0] = 0; A[N+1] = 0;
  for(int i=1; i<N+1; i++)
    cin >> A[i];
  //ここまで入力

  //合計でいくらかかるか
  int sum = 0;
  for(int i=0; i<N+1; i++)
    sum += abs(A[i+1]-A[i] );

  //地点iを飛ばしたときに減る金額と，新しい金額
  int cancel, new_;
  for(int i=1; i<N+1; i++){
    //地点iが中継地点にあればsumから変化なし
    if(A[i-1] <= A[i] && A[i] <= A[i+1])
      cout << sum << endl;
    //そうでなければ，地点iを飛ばした金額を計算する
    else{
      cancel = abs(A[i+1] - A[i]) + abs(A[i] - A[i-1] );
      new_ = abs(A[i+1] - A[i-1] );
      cout << sum - cancel + new_ << endl;;
    }
  }

  
  
  return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>
void bubble(int *a,int *b){
  int c;
  c=*a;
  *a=*b;
  *b=c;
}
int main(){
  int N,i,j,v,k;
  int A[1000];
  int flag;
  int count=0;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  flag=1;
  while(flag){
    flag=0;
    for(j=N-1;j>=1;j--){
      if(A[j]<A[j-1]){
      bubble(&A[j],&A[j-1]);
      flag=1;
      count++;
    }
  }
}
  for(i=0;i<N-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[N-1]);
  printf("%d\n",count);
  return 0;
}


Measured memory_bytes: 2128
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll n, k;
  cin >> n >> k;
  vll p(n);
  rep(i, n){
    cin >> p[i];
  }
  sort(ALL(p));
  ll ans = 0;
  rep(i, k){
    ans += p[i];
  }
  print(ans);
}


Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <utility>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;

int main() {
	int a, b;
	while(1) {
		cin >> a >> b;
		if(a == 0 && b == 0) break;
		if(a > b) swap(a, b);
		cout << a << " " << b << endl;
	}
	return 0;
}

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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

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

  int n;cin>>n;
  string s;cin>>s;
  int r=count(s.begin(), s.end(), 'R');
  int b=count(s.begin(), s.end(), 'B');
  if(r>b)cout<<"Yes";
  else cout<<"No";
  cout<<endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

W = []

def dfs(checked, L):
    if len(L) == N:
        W.append(L)
        return
    for i in range(1, N+1):
        if not checked[i]:
            checked[i] = True
            dfs(checked, L+[i])
            checked[i] = False
    return

dfs([False]*(N+1), [])


for i, L in enumerate(W):
    if L == P:
        ip = i
    if L == Q:
        iq = i

print(abs(ip-iq))

Measured memory_bytes: 53724
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod1,mod2;
int n,tot=0,pos1=1,pos2=1,tot1=0,tot2=0;
int a[200005];
inline int Popcount(int x){
	if (x==0)  return 0;
	
	int step=0;
	while (x!=0){
		int cnt=0,k=x;
		while (k!=0){
			if (k%2==1)  cnt++;
			k/=2;
		}
		if (cnt!=0)  x%=cnt;
		else x=0;
		
		step++;
	}
	return step;
}
int ksm1(int x,int y){
	int res=1;
	for (;y;y=y>>1,x=(x*x)%mod1){
		if (y&1)  res=(res*x)%mod1;
	}
	return res;
}
int ksm2(int x,int y){
	int res=1;
	for (;y;y=y>>1,x=(x*x)%mod2){
		if (y&1)  res=(res*x)%mod2;
	}
	return res;
}
signed main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		char x;
		cin>>x;
		a[i]=x-'0';
	}
	for (int i=1;i<=n;i++){
		if (a[i]==1)  tot++;
	}
	int flag=1;
	for (int i=1;i<=n;i++){
		if (a[i]!=0){
			flag=0;
			break;
		}
	}
	if (flag==1){
		for (int i=1;i<=n;i++)  cout<<1<<endl;
		return 0;
	}
	mod1=tot-1;
	mod2=tot+1;	
	for (int i=n;i>=1;i--){
		if (mod1!=0)  tot1=(tot1+a[i]*pos1)%mod1,pos1=(pos1*2)%mod1;
		if (mod2!=0)  tot2=(tot2+a[i]*pos2)%mod2,pos2=(pos2*2)%mod2;
	}
	for (int i=1;i<=n;i++){
		if (a[i]==0){
			int now;
			if (mod2>0){
				now=(tot2+ksm2(2,n-i))%mod2;
				cout<<Popcount(now)+1<<endl;
			}
			else cout<<0<<endl;
		}
		else{
			int now;
			if (mod1>0)
			{
				now=((tot1-ksm1(2,n-i))%mod1+mod1)%mod1;
				cout<<Popcount(now)+1<<endl;
			}
			else cout<<0<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 5164
using System;

namespace abc142A
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string D = Console.ReadLine();
            int B = int.Parse(D);
            double A = double.Parse(D);
            double C;
            if (B % 2 == 1)
            {
                C = ((A+1)/2) / A;
            }
            else
                C = (A / 2) / A;
            Console.WriteLine(C);
        }
    }
}


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

using namespace std;
using ll = long long;


int main() {
    ll x;
    scanf("%lld", &x);
    ll res = 2 * (x / 11);
    x %= 11;
    if (x) res++;
    if (x > 6) res++;
    printf("%lld\n", res);
}


Measured memory_bytes: 256
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

S = str(input())
T=str(input())
ans = 0
temp = 0


for i in range(len(S)):
    temp = 0
    for j in range(len(T)):
        if(len(S)<i+len(T)):
            break
        if(S[i+j]==T[j]):
            temp += 1
    ans = max(ans,temp)

print(len(T)-ans)


Measured memory_bytes: 70188
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define iter(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define riter(i, c) for (auto i = (c).rbegin(); i != (c).rend(); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;

const ll INF = 1LL << 50;

ll dp[3030][3030][2];

ll dfs(const vector<ll>& a, int l, int r, bool is_first) {
    // [l,r)
    if (l == r) return 0;
    if (dp[l][r][is_first] > -INF) {
        return dp[l][r][is_first];
    }
    if (is_first) {
        ll left_score = a[l] + dfs(a, l + 1, r, false);
        ll right_score = a[r - 1] + dfs(a, l, r - 1, false);
        return dp[l][r][is_first] = max(left_score, right_score);
    }
    else {
        ll left_score = dfs(a, l + 1, r, true) - a[l];
        ll right_score = dfs(a, l, r - 1, true) - a[r - 1];
        return dp[l][r][is_first] = min(left_score, right_score);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N + 1) rep(j, 0, N + 1) {
        dp[i][j][0] = dp[i][j][1] = -INF;
    }
    cout << dfs(A, 0, N, true) << endl;
    return 0;
}

Measured memory_bytes: 143872
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int ap[1000000+20],n,a[200000+20];
int main(){
	fastio;
	cin>>n;
	rb(i,1,n) {
		cin>>a[i];
		
	}
	sort(a+1,a+1+n);
	rb(i,1,n){
		if(a[i]==a[i-1]){
			ap[a[i]]=1;
		}
	}
	int res=0;
	rb(i,1,n){
		if(!ap[a[i]])
			res++;
		if(a[i]!=a[i-1]){
			for(int j=2*a[i];j<=1000000;j+=a[i]){
				ap[j]=1;
			}
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 8348
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    int M;
    cin >> N >> M;

    vector<int> x(N, -1);

    vector<int> s(M), c(M);
    for(int i = 0; i < M; ++i){
        int s, c;
        cin >> s >> c;
        if(x[s - 1] != -1 && x[s - 1] != c) {cout << -1; return 0;}
        x[s - 1] = c;
    }
    
    if(N == 1) {
        if(x[0] == -1) cout << 0;
        else cout << x[0];
        return 0;
    }

    if(x[0] == 0) {cout << -1; return 0;}
    else if(x[0] == -1) cout << 1;
    else cout << x[0];

    for(int i = 1; i < N; ++i){
        if(x[i] == -1) cout << 0;
        else cout << x[i];
    }


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstring>
#include <bitset>
using namespace std;
const int MAX = 1e6;
struct koor{
    int r , c , val;
};
int main(){
    int R , C , k , ans;
    cin >> R >> C >> k;
    int *row , *column;
    row = new int [R] , column = new int [C];
    memset(row , 0 , sizeof(row)) , memset(column , 0 , sizeof(column));
    bool visited[R][C];memset(visited , 0 , sizeof(visited));
    string area[R];
    koor mula , akhir;mula.val = 0;

    cin >> mula.r >> mula.c >> akhir.r >> akhir.c;
    --mula.r , --mula.c , --akhir.r , --akhir.c;

    for (int i = 0 ; i < R ; i++)
        cin >> area[i];

    bool ketemu = 0;
    queue<koor> q;
    q.push(mula);
    while(!q.empty()){
        koor now = q.front();
        q.pop();
        if (now.r == akhir.r && now.c == akhir.c){
            ketemu = 1 , ans = now.val;
            break;
        }

        if (column[now.c] < R)
        for (int i = now.r - 1 , x = k ; x && i >= 0 && area[i][now.c] == '.' ; i-- , x--){//ke atas
            if (!visited[i][now.c])
                visited[i][now.c] = 1,
                column[now.c]++ , row[i]++,
                q.push({i , now.c , now.val + 1});
        }

        if (column[now.c] < R)
        for (int i = now.r + 1 , x = k ; x && i < R && area[i][now.c] == '.' ; i++ , x--){
            if (!visited[i][now.c])
                visited[i][now.c] = 1,
                column[now.c]++ , row[i]++,
                q.push({i , now.c , now.val + 1});
        }

        if (row[now.r] < C)
        for (int i = now.c - 1 , x = k ; x && i >= 0 && area[now.r][i] == '.' ; i-- , x--){
            if (!visited[now.r][i])
                visited[now.r][i] = 1,
                column[i]++ , row[now.r]++,
                q.push({now.r , i , now.val + 1});
        }

        if (row[now.r] < C)
        for (int i = now.c + 1 , x = k ; x && i < C  && area[now.r][i] == '.' ; i++ , x--){
            if (!visited[now.r][i])
                visited[now.r][i] = 1,
                column[i]++ ,  row[now.r]++,
                q.push({now.r , i , now.val + 1});
        }
    }
    if (!ketemu)
        cout << "-1\n";
    else
        cout << ans << endl;
}


Measured memory_bytes: 7468
#include <iostream>
#include <sstream>

using namespace std;

int main() {

    int H, W; 
    stringstream input;
    string out;

    // 1????????? stream ?????????.
    while(1) {
        int A, B;
        cin >> A >> B;
        // 0 0 ??§??????.
        if ( A == 0 && B == 0)
            break;
        input << A << " " << B << endl;
    }

    // stream ?????????????????????
    while (!input.eof()) {
        input >> H >> W;
        if (H == 0 && W == 0)
            break;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                out += "#";
            }
            out += "\n";
        }
        cout << out << "\n";
        out = "";
        // ?????????.
        H = 0;
        W = 0;
    }
    return 0;
}

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

int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    int n;
    cin>>n;
    int a[n];
    for(int i = 0;i < n;i++) cin>>a[i];
    int ans = 1;
    for(int i = 1;i < n;i++) {
        bool possible = true;
        for(int j = 0;j < i;j++) {
            if(a[j] > a[i]) {
                possible = false;
                break;
            }
        }
        ans += possible;
    }

    cout<<ans;
}

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

bool is_native(int x){
    bool flg = true;
    for(int i = 2; i < x; i++){
        if(x % i == 0) flg = false;
    }
    return flg;
}

int main(){
    int N;
    cin >> N;
    for(int i = N; ; i++){
        if(is_native(i)){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;

int main(){
  string s,t;
  cin>>s>>t;
  ll st=-1;
  bool p=true;
  ll k=s.length()-t.length();
  irep(i,k,0){
    p=true;
    rep(j,0,t.length()){
      if(s[i+j]=='?' || s[i+j]==t[j])continue;
      else {p=false;break;}
    }
    if(p){st=i;break;}
  }
  if(st==-1)cout<<"UNRESTORABLE";
  else{
    rep(i,0,st){if(s[i]=='?')cout<<'a';else cout<<s[i];}
    cout<<t;
    rep(i,st+t.length(),s.length()){if(s[i]=='?')cout<<'a';else cout<<s[i];}
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int main() {
	int n;
	string S;
	cin >> n >> S;
	int maxN = 0;
	for (int i = 1; i < (int)S.size(); i++)
	{
		int A[26] = { 0 };
		int B[26] = { 0 };
		for (int j = 0; j < i ; j++)
		{
			A[S[j] - 'a']++;
			//cout << S[j] - 'a' << endl;
		}
		//cout << endl;
		for (int j = i ;j < (int)S.size(); j++)
		{
			B[S[j] - 'a']++;
			//cout << S[j] - 'a' << endl;
		}
		//cout << endl;
		int cnt = 0;
		for (int i = 0; i < 26; i++)
		{
			if (A[i] != 0 && B[i] != 0) {
				cnt++;
			}
		}

		maxN = max(maxN, cnt);

	}
	cout << maxN << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a,b;
  cin >> a >> b;
  int ans=0;
  ans += a - 1;
  if (a <= b) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 3584
import bisect

a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
for i in range(q):
    ans = float("inf")
    x = int(input())
    index_s = bisect.bisect_left(s, x)
    index_t = bisect.bisect_left(t, x)
    if index_s > 0:
        s_m = s[index_s - 1]
        if index_t > 0:
            t_m = t[index_t - 1]
            ans = min(ans, x - min(s_m, t_m))
        if index_t < b:
            t_p = t[index_t]
            ans = min(ans, t_p * 2 - x - s_m)
            ans = min(ans, x + t_p - s_m * 2)
    if index_s < a:
        s_p = s[index_s]
        if index_t > 0:
            t_m = t[index_t - 1]
            ans = min(ans, s_p * 2 - x - t_m)
            ans = min(ans, x + s_p - t_m * 2)
        if index_t < b:
            t_p = t[index_t]
            ans = min(ans, max(s_p, t_p) - x)
    print(ans)

Measured memory_bytes: 12160
#include <iostream>
#include <list>
#include <algorithm>

int main(int argc, char const *argv[]) {
  std::string s;
  std::list<char> l;
  int q;
  std::cin >> s >> q;
  for(char c : s){
    l.push_back(c);
  }
  bool flagT = true;
  for (int i = 0; i < q; i++) {
    int t;
    std::cin >> t;
    if(t==1){
      flagT = !flagT;
    }else{
      int f;
      char c;
      std::cin >> f >> c;
      bool flagF = (f == 2);
      if(flagT ^ flagF){
        l.push_front(c);
      }else{
        l.push_back(c);
      }
    }
  }
  if(!flagT){
    std::reverse(l.begin(), l.end());
  }
  for(char c : l){
    std::cout << c;
  }
  std::cout << std::endl;
  return 0;
}


Measured memory_bytes: 10112
n = int(input())
arr = list(map(int, input().split()))

#arr：最小公倍数の対象とする配列
MOD = 10**9 + 7
def lcm(arr):
    primes = {}
    for val in arr:
        p = 2
        while p * p <= val:
            if val % p == 0:
                cnt = 0
                while val % p == 0:
                    cnt += 1
                    val //= p
                if p not in primes:
                    primes[p] = cnt
                else:
                    primes[p] = max(cnt, primes[p])
            p += 1
     
        if val != 1:
            if val not in primes:
                primes[val] = 1
    lcma = 1
    for p in primes:
        lcma = lcma * pow(p, primes[p], MOD) 
    return lcma

b = lcm(arr)

ans=0
for i in range(n):
    ans+= b*pow(arr[i],MOD-2,MOD)

print(ans%MOD)

Measured memory_bytes: 44764
#include <stdio.h>

int main(void)
{
   int i, j, s, n, d, x;
   scanf("%d%d%d", &n, &d, &x);
   int a[n];

   for(i = 0; i < n; i++){
      scanf("%d", &a[i]);
      s = 0;
      for(j = 0; 1; j++){
         if(d / (j*a[i] + 1) > 0){
            s++;
         }
         else{
            break;
         }
      }
      a[i] = s;
   }

   s = 0;
   for(i = 0; i < n; i++){
      s += a[i];
   }
   s += x;

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

   return 0;
}


Measured memory_bytes: 128
n = int(input())
a = [int(input()) for _ in range(n)]
pushed = [0 for _ in range(n)]
pushed[0] = 1
counter = 1
start = 1
end = a[start-1]
while True:
    if pushed[end-1] == 1:
        print(-1)
        exit()
    else:
        if end == 2:
            print(counter)
            exit()
        else:
            counter += 1
            pushed[end-1] = 1
            start = end
            end =  a[start-1]


Measured memory_bytes: 7884
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int A[n];
  for(int i=0;i<n;i++)
  	cin>>A[i];
  int dp[n];
  dp[0]=0;
  for(int i=1;i<n;i++){
    	dp[i]=INT_MAX;
    for(int j=1;j<=k;j++)
      	if(i>=j)
    		dp[i]= min( abs(A[i-j]-A[i])+dp[i-j], dp[i]);
  }
   cout<<dp[n-1]<<endl;
  return 0;
  }

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

int main(){
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> v(h);
    for (int i=0; i<h; i++){
        cin >> v.at(i);
    }
    int ans=0;
    for(int i=0; i<1<<h; i++){
        for(int j=0; j<1<<w; j++){
            int count = 0;
            for (int ih=0; ih<h; ih++){
                for (int jw=0; jw<w; jw++){
                    if(i>>ih&1){
                        continue;
                    }
                    if(j>>jw&1){
                        continue;
                    }
                    if(v.at(ih).at(jw)=='#')
                    {
                        count++;
                    }

                }
            }
            if (count == k){
                ans++;
            }
        }
    }
    cout << ans << endl;
 
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; (i) < (n); ++ (i))
#define loop(i,a,n) for (int i = (a); (i) < (n); ++ (i))
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 0
#define int long long
//#define int ll
using namespace std;
typedef vector<int> vi;
 
signed main(){
    int N,X;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> X;
    vector<int> niku(N+1),dpketa(N+1);
    rep(i,N+1) {
        if(i==0) dpketa[i] = 1;
        else {
            dpketa[i] = 3 + 2*dpketa[i-1];
        }
    }
    rep(i,N+1)
    {
        if(i==0) {
            niku[i] = 1;
        } else {
            niku[i] = 1 + 2*niku[i-1];
        }
    }
    int count = 0;
    int pp,sa = X;
    for(pp=N;pp>=0;pp--) {
    if(pp > 1) {
        if(sa == dpketa[pp]) {
            count += niku[pp];
            break;
        } else if(sa > (dpketa[pp-1]+2)) {
            count += niku[pp-1] + 1;
            sa -= dpketa[pp-1] + 2;
        } else if(sa ==(dpketa[pp-1]+2)) {
            count += niku[pp-1] + 1;
            break;
        } else if(sa > 1) {
            sa -= 1;
        } else if(sa == 1) {
            break;
        }
    } else if(pp == 1){
        switch(sa) {
            case 1: break;
            case 5:
            case 4: count++;
            case 3: count++;
            case 2: count++;
        }
        break;
    } else if(pp == 0 && sa == 1) {
        count++;
        break;
    } else break;
    }
    cout << count << endl;
    return 0; 
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;

int M;

long double L,N;

int main()
{
  cin>>L;
  
  N=L/3.;
  
  N=N*N*N;
  
  printf("%Lf",N);
  
  
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
const double eps = 1e-8;

class P {
public:
	double x, y, z;
	P(){};
	P(double x, double y, double z) : x(x), y(y), z(z) {};
	P operator+(const P &p) {
		return P(x + p.x, y + p.y, z + p.z);
	}
	P operator-(const P &p) {
		return P(x - p.x, y - p.y, z - p.z);
	}
	P operator*(const double &n) {
		return P(x * n, y * n, z * n);
	}
	P operator/(const double &n) {
		return P(x / n, y / n, z / n);
	}
};

double dot(const P &a, const P &b) {
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

P cross(const P &a, const P &b) {
	return P(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
}

int main() {
	P p[5];
	for (int i=0; i<5; ++i) cin >> p[i].x >> p[i].y >> p[i].z;

	P z = cross(p[3] - p[2], p[4] - p[2]);
	double a = dot(p[2] - p[0], z);
	double b = dot(p[1] - p[0], z);
	double c = abs(a);
	double d = abs(b) - c;

	if (abs(a) < eps || (b < -eps && eps < a) || (a < -eps && eps < b) || d < -eps) {
		cout << "HIT\n";
		return 0;
	}

	P i = (p[0] * d + p[1] * c) / (c + d);
	bool plus = false, minus = false;
	for (int k=0; k<3; ++k) {
		double t = dot(z, cross(p[(k + 1) % 3 + 2] - p[k + 2], i - p[k + 2]));
		if (-eps < t) plus = true;
		else if (eps > t) minus = true;
	}

	cout << ( ! plus || ! minus ? "MISS\n" : "HIT\n");
	return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;

  cin >> A >> B >> C >> D;
 
  if (A + B > C + D) {
    cout << "Left" << endl;
  } else if (A + B == C + D) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
S = input()
n = len(S)
ans = 0
for i in range(2 ** (n - 1)):
    ope = S
    cur = 0
    for j in range(n - 1):
        if (i >> j) & 1:
            ope = ope[:-j - cur - 1] + '+' + ope[-j - cur - 1:]
            cur += 1
    ans += eval(ope)
print(ans)


Measured memory_bytes: 9124
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    string S;
    int x,y;
    cin >> S >> x >> y;
    
    bool b = true;
    vector< vector<int> > T(2);
    int sum[2] = {0};
    int count = 0;
    
    for ( int i = 0; i < S.length(); i++ ) {
        if ( S[i] == 'T' ) {
            T[ b ? 0 : 1 ].push_back( count );
            sum[ b ? 0 : 1 ] += count;
            count = 0;
            b = !b;
        }
        else { count++; }
    }
    T[ b ? 0 : 1 ].push_back( count );
    sum[ b ? 0 : 1 ] += count;
    
    x -= T[0][0];
    sum[0] -= T[0][0];
    
    
    if ( sum[0] < abs(x) || sum[1] < abs(y) || sum[0]%2 != abs(x)%2 || sum[1]%2 != abs(y)%2 ) {
        cout << "No" << endl;
        return 0;
    }
    
    int x0 = (sum[0] - abs(x)) / 2;
    int y0 = (sum[1] - abs(y)) / 2;
    
    vector< vector<int> > dp( 2, vector<int>(8001,0) );
    
    dp[0][0] = dp[1][0] = 1;
    
    for ( int k = 0; k < 2; k++ ) {
    for ( int i = 0; i < T[k].size(); i++ ) {
        if ( !k && !i ) { continue; }
        
        for ( int j = 8000; j >= 0; j-- ) {
            if ( dp[k][j] ) {
                dp[k][ j+T[k][i] ] = 1;
            }
        }
    }
    }
    
    bool ans = dp[0][x0] && dp[1][y0];
    
    cout << ( ans ? "Yes" : "No" ) << endl;
    
    return 0;
}

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

int main(){
    string S;
    cin >> S;
    int n = S.size() - 1; //間の個数    
    vector<int> nums(S.size());
    
    for (int i = 0; i < S.size(); i++){
      nums.at(i) = S.at(i) - '0';
    }
    long long sum = 0;
    long long temp = nums.at(0);
    for (int bit = 0; bit < (1 << n); ++bit){
        for (int i = 0; i < n; ++i){
            if (bit & (1 << i)){
                //右からi-1番目の隙間に+が入っていた時
                sum += temp;
                temp = nums.at(i + 1);
            }else
            {
                temp = 10*temp + nums.at(i + 1);
            }
        }
        sum += temp;
        temp = nums.at(0);
    }
    cout << sum << endl;
}

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

int main() {

int N;
int a;
int A=0;
int B=0;

    cin>>N;
    vector<int> vec(N);
    for (int i = 0; i <N; i++) {
    cin>>vec.at(i);
   }

  sort(vec.begin(), vec.end());
 /*
  for(int i=0; i<N; i++){
  cout<<vec.at(i);
  }
cout<<endl;
*/

  reverse(vec.begin(), vec.end());
 /*
  for(int i=0; i<N; i++){
  cout<<vec.at(i);
  }
cout<<endl;
*/
for(int i=0; i<N; i++){
if(i%2==0){
A+=vec.at(i);
}
else
B+=vec.at(i);
}
/*
cout<<A<<endl;
cout<<B<<endl;
*/
cout<<A-B<<endl;

}//main;

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 500009 /// Still trying to be one thing
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define EPS 1e-12
using namespace std;
const ll INF = 1e17 + 9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long double a,b,c;
    cin>>a>>b>>c;
    if(c-(a+2*sqrt(a*b)+b)>EPS)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;   
}           



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

int main() {
    int n; cin >> n;
    int cnt = 0;
    vector<int> d{3, 5, 7};
    for (int keta = 0, pow3 = 1; keta <= 9; keta++, pow3 *= 3) {
        for (int i = 0; i < pow3; i++) {
            int num = 0;
            bitset<3> mask;
            for (int _ = 0, cur = i; _ < keta; _++) {
                num = num * 10 + d[cur % 3], mask.set(cur % 3);
                cur /= 3;
            }
            cnt += mask.all() && num <= n;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
using vi = vector<int>;

string str;
string stra;
int id = 0;

void pt(vector<int> v){
  for(int r=0;r<v.size();r++){
    cout << v[r];
  }
  cout << endl;
}

vi number(){
  vi res;
  for (;'0'<=stra[id]&&stra[id]<='9'; id++) {
    res.push_back(stra[id] - '0');
  }
  reverse(res.begin(),res.end());
  return res;
}
int solve(){
  stra = str;
  for (int i = 9; i >= 0; i--) {
    id = 0;
    for (int j = 0; j <(int)str.size(); j++) {
      if (str[j] == 'X') {
        stra[j] = i + '0';
      }
    }
    vi a = number();
    if (stra[id] == '+' ) {
      id++;
    }
    vi b = number();
    // a.resize(max(b.size() + 1,a.size()+1),0);
    // for (int j = 0; j < (int)b.size(); j++) {
    //   a[j] += b[j];
    //   if (a[j]>=10) {
    //     a[j] -= 10;
    //     a[j+1]++;
    //   }
    // }
    // for (int j = b.size(); j < (int)(a.size()-1); j++) {
    //   if (a[j] >= 10) {
    //     a[j] -= 10;
    //     a[j+1]++;
    //   }
    // }

    int j;
    int k=0;
    int l=0;
    vi ab;
    for(j=0;j<int(a.size())&&j<int(b.size());j++){
      k=0;
      if(a[j]+b[j]+l>=10){
        k++;
        ab.push_back(a[j]+b[j]+l-10);
      }
      else{
        ab.push_back(a[j]+b[j]+l);
      }
      l=k;
    }
    for(;j<int(a.size());j++){
      k=0;
      if(a[j]+l>=10){
        k++;
        ab.push_back(a[j]+l-10);
      }
      else{
        ab.push_back(a[j]+l);
      }
      l=k;
    }
    for(;j<int(b.size());j++){
      k=0;
      if(b[j]+l>=10){
        k++;
        ab.push_back(b[j]+l-10);
      }
      else{
        ab.push_back(b[j]+l);
      }
      l=k;
    }
    if(l>0){
      ab.push_back(l);
    }
    a=ab;
    /////////
    if (stra[id] == '=') {
      id++;
    }

    vi c = number();
    if (a.size() != c.size()) {
      continue;
    }
    int flag = 0;
    for (int j = 0; j < (int)a.size(); j++) {
      if (a[j] == c[j]) {
        flag++;
      }
    }
    if (flag ==(int)a.size()) {
      return i;
    }

  }
  return -1;
}
int main(){
  cin >> str;
  while(str.size()){
  int ans = solve();
  if (ans >= 0) {
    cout << ans << endl;
  } else {
    cout << "NA" << endl;
  }
  str="";
  cin >> str;
}
  return 0;
}



Measured memory_bytes: 3064
#include <bits/stdc++.h>
int main(void)
{
  int n;
  double m, sum = 0;
  std::string t;
  std::cin >> n;
  for(int i = 0; i != n; i++){
    std::cin >> m >> t;
    if(t == "JPY")
      sum += m;
    else
      sum += 380000 * m;
  }
  std::cout << sum << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n, k, sum = 0, ans = 0;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        sum += b[i];
    }
    bool f[114514] = {};
    for(int i = 30; i >= 0; i--){
        if(k & (1LL << i)){
            int tmp = 0;
            for(int j = 0; j < n; j++){
                if(!f[j] && a[j] & (1LL << i)) tmp += b[j];
            }
            ans = max(ans, sum - tmp);
        }else{
            for(int j = 0; j < n; j++){
                if(!f[j] && a[j] & (1LL << i)){sum -= b[j];f[j] = true;}
            }
        }
    }
    ans = max(ans, sum);
    cout << ans << endl;
}

Measured memory_bytes: 1920
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define mset(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define E 1e-6
#define INF 0x3f3f3f3f
void open(){freopen("data.txt","r",stdin);}
void out(){freopen("out.txt","w",stdout);}
const int maxn = 101010;
const int MOD = 1e9 + 7;

int u[255] , v[255];
int fa[55];
int Find(int x)
{
    if(x==fa[x]) return x;
    return fa[x] = Find(fa[x]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,0,m){
        scanf("%d%d",&u[i],&v[i]);
    }
    int ans = 0;
    rep(i,0,m){
        for(int j=1;j<=n;j++) fa[j] = j;
        rep(j,0,m){
            if(i==j) continue;
            int root1 = Find(u[j]);
            int root2 = Find(v[j]);
            if(root1==root2) continue;
            fa[root2] = root1;
        }
        bool ok = true;
        for(int j = 1;j<=n&&ok;j++){
            for(int k=1;k<=n&&ok;k++){
                if(Find(j)!=Find(k)){
                    ok = false;
                }
            }
        }
        if(!ok) ans++;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 256