akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int n,A[50];
int solve(int i,int m){
  if(m==0){
    return 1;
  }
  if(i>=n){
    return 0;
  }
  int res=solve(i+1 , m) ||solve(i+1 , m-A[i]);
return res;
}

int main(){
  int q,M,i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&M);
    if(solve(0,M)){
      printf("yes\n");
    }
    else{
      printf("no\n");
    }
  }
  return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<string, pair<int, int>> P;

bool pairCompare(const P &p1, const P &p2)
{
    if (p1.first < p2.first)
    {
        return true;
    }
    else if (p1.first > p2.first)
    {
        return false;
    }
    else
    {
        return p1.second.first > p2.second.first;
    }
}

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;
    vector<P> v;

    for (int i = 0; i < N; i++)
    {
        string s;
        int p;
        cin >> s >> p;
        std::pair<int, int> tempp = std::make_pair(p, i + 1);
        v.push_back(P(s, tempp));
    }
    sort(v.begin(), v.end(), pairCompare);

    for (int i = 0; i < N; i++)
    {
        cout << v[i].second.second << endl;
    }
}

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

#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed fixed<<setprecision(14)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline lol abs(A &a) { return (a < 0 ? -a : a); }
const lol inf=(1LL<<60);
const lol Mod=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
lol n,m,k,r;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >>n>>m;
  map<int,int> ma;
  lol ans=1;
  lol o=m;
  while(o%2==0){
    ma[2]++;
    o/=2;
  }
  for(lol i=3;i<=sqrt(m);i+=2){
    while(o%i==0){
      o/=i;
      ma[i]++;
    }
  }
  for(auto l=ma.begin();l!=ma.end();l++){
      ans*=pow(l->fi,(l->se/n));
  }
  if(n==1) cout <<m<<'\n';
  else cout <<ans<<'\n';
  return (0);
}


Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int mod = (int) 1e9 + 7;

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int maxn = 5005;
int n, a, b;

bool read() {
  if (scanf("%d%d%d", &n, &a, &b) < 3) {
    return false;
  }
  return true;
}

int dp[maxn][maxn][2];
int dp0[maxn][2];

void solve() {
  if (a < b) {
    swap(a, b);
  }
  memset(dp, 0, sizeof(dp));
  memset(dp0, 0, sizeof(dp0));
  add(dp[0][0][1], 1);
  add(dp[1][0][1], mod - 1);
  add(dp0[0][0], 1);
  add(dp0[1][0], mod - 1);
  add(dp0[0][1], 1);
  add(dp0[1][1], mod - 1);
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int t = 0; t < 2; t++) {
        auto &cur = dp[i][j][t];
        if (i) {
          add(cur, dp[i - 1][j][t]);
        }
        //eprintf("%d %d %d: %d\n", i, j, t, cur);
        if (!cur || i >= n) {
          continue;
        }
        int l = i + 1, r = n;
        if (t) {
          l = min(r, i + b);
        }
        add(dp[l][j][!t], cur);
        add(dp[r][j][!t], mod - cur);
        if (t && i + b <= n) {
          if (j + a > n) {
            add(dp0[n][!t], cur);
            add(dp0[n + 1][!t], mod - cur);
          }
        }
        if (!t) {
          int l = i + 1, r = n + 1;
          int m = j + a;
          if (l < m) {
            add(dp0[l][!t], cur);
            add(dp0[min(r, m)][!t], mod - cur);
          }
        }
      }
    }
    for (int t = 0; t < 2; t++) {
      auto &cur = dp0[i][t];
      if (i) {
        add(cur, dp0[i - 1][t]);
      }
      //eprintf("%d %d: %d\n", i, t, cur);
      if (!cur || i >= n) {
        continue;
      }
      int l = i + 1, r = n + 1;
      if (t) {
        r = min(r, i + b);
      } else {
        r = min(r, i + a);
      }
      add(dp0[l][!t], cur);
      add(dp0[r][!t], mod - cur);
      if (!t) {
        int l = i + 1, r = n + 1;
        add(dp[l][i][!t], cur);
        add(dp[r][i][!t], mod - cur);
      }
    }
  }
  int res = 1;
  for (int i = 0; i < n; i++) {
    res = mul(res, 2);
  }
  add(res, mod - dp0[n][0]);
  add(res, mod - dp0[n][1]);
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 199564
#include <stdio.h>

int main(void)
{
	int m, n;
	int masu[2000], dice[2000];
	int now;
	int i;
	
	while (scanf("%d %d", &n, &m), n) {
		now = 1;
		
		for (i = 1; i <= n; i++) {
			scanf("%d", &masu[i]);
		}

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

		for (i = 1; now < n; i++) {
			now += dice[i];
			now += masu[now];
		}
		printf("%d\n", i - 1);
	}
	return (0);
}

Measured memory_bytes: 612
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 1000000000;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};


int main(){
  ll N; cin >> N;
  vector<ll> A(3 * N);
  rep(i, 3 * N) cin >> A[i];

  vector<ll> l(N+1);
  ll leftsum = 0;
  priority_queue<ll, vector<ll>, greater<ll>> left;
  for(int i = 0; i < N; i++){
    left.push(A[i]);
    leftsum += A[i];
  }
  l[0] = leftsum;
  for(int i = N; i < 2 * N; i++){
    ll a = left.top();
    left.pop();
    if(a > A[i]){
      left.push(a);
    }else{
      left.push(A[i]);
      leftsum += A[i] - a;
    }
    l[i-N+1] = leftsum;
  }

  reverse(A.begin(), A.end());
  vector<ll> r(N+1);
  ll rightsum = 0;
  priority_queue<ll> right;
  for(int i = 0; i < N; i++){
    right.push(A[i]);
    rightsum += A[i];
  }
  r[0] = rightsum;
  for(int i = N; i < 2 * N; i++){
    ll a = right.top();
    right.pop();
    if(a < A[i]){
      right.push(a);
    }else{
      right.push(A[i]);
      rightsum -= a - A[i];
    }
    r[i-N+1] = rightsum;
  }
  ll ans = - INFL;
  for(int i = 0; i < N+1; i++){
    ans = max(ans, l[i] - r[N-i]);
  }
  cout << ans << endl;

}


Measured memory_bytes: 6516
n,m=map(int,input().split())
a=[]
l=[]
r=[]
for i in range(m):
    a.append(list(map(int,input().split())))
    l.append(a[i][0])
    r.append(a[i][1])

ans=min(r)-max(l)
if ans<0:
    ans=0
else:
    ans+=1
print(ans)



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

typedef ostringstream OSS;
typedef istringstream ISS;

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<PII> VPII;

#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x) (x).begin(),(x).end()
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define rep(i, N) for (int i = 0; i < (N); i++)
#define rep2(i, j, N, M) rep(i, N) rep(j, M)
#define rep3(i, j, k, N, M, L) rep(i, N) rep(j, M) rep(k, L)
#define REP(i, init, N) for (int i = (init); i < (N); i++)

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int N, W;
VI vs;

double solve() {
    VI ts(15);
    for (auto v : vs) {
        ts[v / W]++;
    }

    int WW = 0;
    {
        rep(i, 15) {
            if (ts[i]) {
                WW = i;
            }
        }
    }

    int H = *max_element(ALL(ts));

    double ans = 0.01;
//    cerr << "  " << WW << " " << H << endl;
    rep(i, WW + 1) {
        double c = 1. * (WW - i) / WW;
        double v = 1. * ts[i] / H;
//        cerr << "    " << c << " " << v << endl;
        ans += c * v;
    }

    return ans;
}

int main(void) {
    while (cin >> N >> W, N) {
        vs = VI(N);
        for (auto &v : vs) cin >> v;
        printf("%.9f\n", solve());
    }

	return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
// 型シノニム
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
// 定数
constexpr ll INF   = 1e16;
constexpr ll INM   = 114514;
constexpr ll MOD   = 1e9 + 7;
constexpr ld EPS   = 1e-12;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
// 便利関数
void IOS() { ios::sync_with_stdio(false), cin.tie(0); }
template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
vector<string> split(const string &s, char delim) {
	vector<string> elems;
	string item;
	for (char ch : s) {
		if (ch == delim) {
			if (!item.empty())
				elems.push_back(item);
			item.clear();
		} else {
			item += ch;
		}
	}
	if (!item.empty())
		elems.push_back(item);
	return elems;
}

// 本体

constexpr ll AMAX = 1e6;
bool ok[AMAX + 2];
int exists[AMAX + 2] = {};
int main() {
	IOS();
	ll n;
	cin >> n;
	vector<ll> a(n);
	Fill(ok, true);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		exists[a[i]]++;
		if (exists[a[i]] <= 1) {
			for (int j = 2; j * a[i] <= AMAX; j++) {
				ll baisuu  = j * a[i];
				ok[baisuu] = false;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (ok[a[i]] && exists[a[i]] <= 1) ans++;
	}
	dump(ans);
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int a, b, x;
    cin >> a >> b >> x;

    cout << ((a <= x and x <= a + b) ? "YES" : "NO");
    return 0;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int root;
int t[2][100000],hight[100000];
void dfs1(int p){
  if(p==-1)return;
  cout<<" "<<p;
  dfs1(t[0][p]);
  dfs1(t[1][p]);
}
void dfs2(int p){
  if(p==-1)return;
  dfs2(t[0][p]);
  cout<<" "<<p;
  dfs2(t[1][p]);
}
void dfs3(int p){
  if(p==-1)return;
  dfs3(t[0][p]);
  dfs3(t[1][p]);
  cout<<" "<<p;
}
int main(){
  int root;
  int n,par[100000];
  cin>>n;
  for(int i=0;i<n;i++)par[i]=-1;
  for(int i=0;i<n;i++){
    int a,b,c;
    cin>>a>>b>>c;
    t[0][a]=b;
    t[1][a]=c;
    if(b!=-1)par[b]=a;
    if(c!=-1)par[c]=a;
    }
  for(int i=0;i<n;i++)if(par[i]==-1)root=i;
  cout<<"Preorder"<<endl;
  dfs1(root);
  cout<<endl<<"Inorder"<<endl;
  dfs2(root);
  cout<<endl<<"Postorder"<<endl;
  dfs3(root);
  cout<<endl;
  return 0;
}

Measured memory_bytes: 1180
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define INF         1e9
#define EPS         1e-9
#define REP(i,n)    for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(lint i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(lint i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define R_UP(a,b)   (((a)+(b)-1)/(b))
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP        cout << fixed << setprecision(8)
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }

signed main()
{
	int h = in(), w = in();
	bool *is_white_row = new bool[h], *is_white_col = new bool[w];
	REP(i, h)is_white_row[i] = true;
	REP(i, w)is_white_col[i] = true;
	vector<vector<char>>bw(h, vector<char>(w));
	REP(i, h)
	{
		string s = in<string>();
		REP(j, w)
		{
			bw[i][j] = s[j];
			is_white_row[i] &= (bw[i][j] == '.');
			is_white_col[j] &= (bw[i][j] == '.');
		}
	}
	REP(i, h)
	{
		REP(j, w)if (!is_white_row[i] && !is_white_col[j])cout << bw[i][j];
		if (!is_white_row[i])cout << endl;
	}
}

Measured memory_bytes: 256
import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
A.sort()
B.sort()
C.sort()
# print(A, B, C)
for b in B:
    a_i = bisect.bisect_left(A, b)
    c_i = bisect.bisect_right(C, b)
    cnt = (a_i) * (N - c_i)
    # print(b, a_i, c_i, cnt)
    ans += cnt

print(ans)

Measured memory_bytes: 105572
#include <iostream>
#include <cmath>
#include <vector>

double CalcDist(int d, const std::vector<int>& lhs, const std::vector<int>& rhs) {
  double sum = 0;
  for (auto i = 0u; i < d; ++i) {
    double diff = static_cast<double>(lhs[i] - rhs[i]);
    sum += (diff * diff);
  }
  return std::sqrt(sum);
}

bool IsInteger(double value) {
  return static_cast<int>(value) == std::ceil(value);
}

int main() {
  int n;
  int d;
  std::cin >> n >> d;
  std::vector<std::vector<int>> coords(n);
  for (auto& coord : coords) {
    coord.resize(d);
    for (auto& value : coord) {
      std::cin >> value;
    }
  }
  int count = 0;
  for (auto i = 0u; i < n; ++i) {
    for (auto j = i + 1; j < n; ++j) {
      //std::cout << "dist(" << i << ", " << j << ") : " << CalcDist(d, coords[i], coords[j]) << std::endl;
      count += IsInteger(CalcDist(d, coords[i], coords[j]));
    }
  }
  std::cout << count << std::endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

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

	sort.Sort(sort.Reverse(sort.IntSlice(a)))

	alice, bob := 0, 0
	for i := 0; i < n; i++ {
		if i%2 == 0 {
			alice += a[i]
		} else {
			bob += a[i]
		}
	}
	fmt.Println(alice - bob)
}


Measured memory_bytes: 512
def func_n(x,y,z):
    return ((x+y+z)**2+x**2+y**2+z**2)//2
N=int(input())
box=[0]*N
for x in range(1,100):
    for y in range(1,99):
        for z in range(1,99):
            a=func_n(x,y,z)
            if a>N:
                break
            box[a-1]+=1
for i in range(N):
    print(box[i])


Measured memory_bytes: 9136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,x,y;cin>>n>>x>>y;x--;y--;
    vector<ll> d(n,0);//d[i]:距離iになるペアの数
    rep(i,n)rep2(j,i+1,n){
        ll dist = j - i;
        ll d1;//i,x,y,j
        ll d2;//i,y,x,j
        d1 = abs(i-x)+1+abs(y-j);
        d2 = abs(i-y)+1+abs(x-j);
        d1 = min(d1,d2);
        dist=min(dist,d1);
        d[dist]++;
    }
    rep2(i,1,n)cout<<d[i]<<endl;
    return 0;
}

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

using LL = long long;

#define ALL(a) begin((a)), end((a))
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define RFOR(i, a, b) for (int(i) = (a); (i) > (b); (i)--)
#define debug(x) cout << #x << " : " << x << '\n'

const int INF = 1e9;

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

  int ans;
  int a, b;
  cin >> a >> b;

  if ((a + b) % 2) {
    ans = (a + b + 1) / 2;
  } else {
    ans = (a + b) / 2;
  }

  cout << ans << '\n';

  return 0;
}

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

int main() {
  int n;
  cin >> n;
  string ans = "Three";
  for (int i = 0; i < n; i++) {
    string c;
    cin >> c;
    if (c == "Y") {
      ans = "Four";
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;
const int N=2005;
int n, size[N];
char s[N];
long long f[N], g[N];
std::vector<int> e[N];
void dfs(int u, int fa) {
	size[u]=s[u]-'0';
	f[u]=g[u]=0;
	for(int v: e[u])
		if(v!=fa) {
			dfs(v, u);
			if(g[v]+size[v]<=f[u]) f[u]-=g[v]+size[v];
			else if(g[u]<=f[v]+size[v]) f[u]=f[v]+size[v]-g[u];
			else f[u]=(g[u]+g[v]+size[v])%2;
			g[u]+=g[v]+size[v];
			size[u]+=size[v];
		}
}
int main() {
	long long ans=-1;
	assert(scanf("%d%s", &n, s+1)==2);
	for(int i=1; i<n; ++i) {
		int a=rd(), b=rd();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1; i<=n; ++i) {
		dfs(i, 0);
		if(f[i]==0&&(g[i]/2<ans||ans==-1)) ans=g[i]/2;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>

using namespace std;

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

    vector<pair<int, int>> city(M), city2(M);
    for (int i = 0; i < M; i++) {
        cin >> city[i].first >> city[i].second;
        city2[i] = city[i];
    }
    
    sort(city2.begin(), city2.end());
    /*
    for (int i = 0; i < M; i++) {
        cout << city2[i].first << "  " << city2[i].second << endl;
    }
    */
    map<pair<int, int>, int> junban;
    int cnt = 1;
    for (int i = 0; i < M; i++) {
        //cout << "i=" << i << endl;
        //cout << "cnt=" << cnt << endl;
        junban[city2[i]] = cnt;
        if (i < M - 1 && city2[i].first == city2[i + 1].first)
            cnt++;
        else
            cnt = 1;
    }
    //cout << "papaya" << endl;
    for (int i = 0; i < M; i++) {
        printf("%06d%06d\n", city[i].first, junban[city[i]]);
    }
    //printf("%06d", 111);
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
#define N 10000005
#define M 205
using namespace std;
int n,cnt1=0,cnt2=0,cnt,p1[M],p2[M],a[M],b[N],pr[M*M*100],match[N];bool vis[N],used[M],mp[M][M];
bool dfs(int u){
	for (int i=1;i<=cnt2;i++){
		if (!mp[u][i]||used[i]) continue;
		used[i]=1;
		if (!match[i]||dfs(match[i])){
			match[i]=u;
			return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d",&n);int mx=0;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=1,mx=max(mx,a[i]);
	for (int i=1;i<=mx+1;i++)
		if (b[i]!=b[i-1]){
			if (i&1) p1[++cnt1]=i;
			else p2[++cnt2]=i;
		}
	for (int i=2;i<=1e7;i++){
		if (!vis[i]) pr[++cnt]=i;
		for (int j=1;j<=cnt;j++){
			if (i*pr[j]>=N) break;
			vis[i*pr[j]]=1;
			if (i%pr[j]==0) break;
		}
	}
	vis[2]=vis[1]=1;int ans=0;
	for (int i=1;i<=cnt1;i++)
		for (int j=1;j<=cnt2;j++)
			if (!vis[abs(p1[i]-p2[j])]) mp[i][j]=1;
	for (int i=1;i<=cnt1;i++){
		memset(used,0,sizeof(used));
		if (dfs(i)) ans++;
	}
	int now1=cnt1-ans;int now2=cnt2-ans;
	ans=ans+(now1/2)*2+(now2/2)*2;
	if (now1&1) ans+=3;
	printf("%d\n",ans);
	return 0;
}

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

template<typename Type>
Type input() {
	Type value;
	std::cin >> value;
	return value;
}

void debug(int x, std::string msg = "debug") {
	std::cout << msg<<" : "<< x << std::endl;
}

bool isPrime(int N) {
	if(N == 1) return false;
	if(N == 2) return true;
	if(N % 2 == 0) return false;
	for(int i = 3; i*i <= N; i += 2) {
		if(N % i == 0) return false;
	}

	return true;
}

int howmanyPrime( int *numbers, const int n) {
//std::cout << ": "<< numof(numbers) << std::endl;
	int count = 0;
	for(int i = 0; i < n; ++i) {
		if( isPrime( numbers[ i ] ) ) {
			++count;
		} else {
		}
	}
	return count;
}

int main() {
	// 1 <= n <= 10,000 ??\??????????????´??°?????°
	const int n = input<int>();
	// 2 <= numbers[i] <= 10^8 ( 0<=i<=n-1) ?????????????????´??°
	int numbers[ n ];
	for(int i = 0; i < n; ++i)
		numbers[ i ] = input<int>();

	std::cout << howmanyPrime( numbers, n) << std::endl;

	return 0;
}

Measured memory_bytes: 1196
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=1e5+100;
inline ll read()
{
	ll f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
char s[maxn];
signed main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	if (s[1]=='0'||s[n]=='1')return puts("-1"),0;
	for (int i=1;i<=n/2;i++)
		if (s[i]!=s[n-i])return puts("-1"),0;
	int last=1;
	for (int i=2;i*2<=n;i++)
	{
		if (s[i]=='1')
		{
			for (int j=last;j<i;j++)printf("%d %d\n",i,j);
			last=i;
		}
	}
	for (int i=last;i<n;i++)printf("%d %d\n",i,n);
}


Measured memory_bytes: 1536
S = input()

ans = 'AC'

if S[:1] != 'A':
    print('WA')
    exit()

if S[2:-1].count('C') != 1:
    print('WA')
    exit()

X = S[1:].split('C')
for x in X:
    if x.islower():
        pass
    else:
        print('WA')
        exit()

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

void  base_num(ll data,ll base){
    if(data == 0) return;
    ll next = abs(data) % abs(base);
    if(data < 0) next = (abs(base) - next) % abs(base);
    base_num((data - next)/base,base);
    cout << next;
}
int main(){
    ll n;
    cin >> n;
    if (n==0){
        cout << 0 << endl;
        return 0;
    }
    base_num(n,-2);
    cout << endl;
    return 0;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	long long a, b, c, e;
	cin >> a >> b >> c;
	if (b > c) {
		cout << '0' << endl;
	}
	else {
		cout << max(((a - 1) * c + b) - ((a - 1) * b + c) + 1, (long long)0) << "\n";
	}
	cin >> e;
}

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

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

    std::vector<int> C(N);
    std::vector<int> S(N);
    std::vector<int> F(N);
    for (int i = 0; i < N - 1; i ++) {
        std::cin >> C[i] >> S[i] >> F[i];
    }

    for (int i = 0; i < N; i ++) {
        int time = 0;
        for (int j = i; j < N - 1; j ++) {
            time = std::max(time, S[j]);
            if (time % F[j] != 0) {
                time = (time / F[j] + 1) * F[j];
            }
            time += C[j];
        }
        std::cout << time << std::endl;
    }
}


Measured memory_bytes: 256
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        N: i64,
        A: i64,
        B: i64,
        C: i64,
        L: [i64; N],
    }

    println!("{:?}", f(N-1, &L, (A, B, C), (0, 0, 0), 0));
}

fn f(n: i64, l: &Vec<i64>, a: (i64, i64, i64), e: (i64, i64, i64), cost: i64) -> i64 {
    if n == -1 {
        if e.0 > 0 && e.1 > 0 && e.2 > 0 {
            return cost + (e.0 - a.0).abs() + (e.1 - a.1).abs() + (e.2 - a.2).abs() - 30;
        } else {
            return std::i64::MAX;
        }
    }

    let ret1: i64 = f(n - 1, &l, a, e, cost);
    let ret2: i64 = f(n - 1, &l, a, (e.0 + l[n as usize], e.1, e.2), cost + 10);
    let ret3: i64 = f(n - 1, &l, a, (e.0, e.1 + l[n as usize], e.2), cost + 10);
    let ret4: i64 = f(n - 1, &l, a, (e.0, e.1, e.2 + l[n as usize]), cost + 10);

    return [ret1, ret2, ret3, ret4].iter().fold(std::i64::MAX, |acc, i| min(acc, *i))
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
  uint64_t n,m,i,ct=0,fee=0,neg;
  cin>>n>>m;

  vector<pair<uint64_t,uint64_t> > data(n);


  for(i=0;i<n;i++){
    cin>>data.at(i).first>>data.at(i).second;
  }
  sort(data.begin(),data.end());



  for(i=0;i<n;i++){
    fee+=data.at(i).first*data.at(i).second;
    ct+=data.at(i).second;
    if(ct==m){
      break;
    }else if(ct>m){
      neg=ct-m;
      fee-=neg*data.at(i).first;
      break;
    }
  }

  cout<<fee<<endl;

  return 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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



int main() {
    ll n, m, a = 0, b = 0;
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        a += (i - 1) * x - (n - i) * x;
        a %= MOD;
    }
    for (int i = 1; i <= m; i++) {
        ll y;
        cin >> y;
        b += (i - 1) * y - (m - i) * y;
        b %= MOD;
    }
    
    cout << a * b % MOD << endl;
}

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

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  if (a >= b) {
    cout << "delicious" << endl;
  } else if (a + x >= b) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string a, b;
  cin>>a >> b;
  int ans = 0;
  for (int i = 0; i < a.length(); ++i) {
    if (a[i] != b[i]) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3916
#include<cstdio>
#include<cmath>
int a,b,m,h;
double s,f,j;
int main()
{
	scanf("%d%d%d%d",&a,&b,&h,&m);
	s=(60*h+m)*0.5;
	f=6*m;
	j=fabs(s-f);
	if(j>180)
		j=360-j;
	printf("%.20f",sqrt(a*a+b*b-2*a*b*cos(j*M_PI/180)));
	return 0;
}

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

int A;
int B;
char S[ 100010 ];

int main()
{
int i;
char C;

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

	cin >> S;

	i = 0;
	while( C = S[ i ] )
	{
		if( C == '0' )
			A++;
		else
			B++;

		i++;
	}

	if( A < B )
		cout << A * 2 << endl;
	else
		cout << B * 2 << endl;

	return 0;
}


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

const int maxn = 11000;

string str[maxn];
string s;
char tmp[maxn];
bool vis[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	int ans = 0;
	for(int i = 0; i < n; ++ i) {
		cin >> s;
		int l = 0;
		for(int i = s.length() - 1; i >= 0; -- i) {
			if(i && s[i] == 'B' && s[i - 1] == 'A') {
				++ ans;
				-- i;
			}
			else tmp[l ++] = s[i];
		}
		tmp[l] = 0;
		reverse(tmp, tmp + l);
		str[i] = tmp;
	}
	int ac = 0, bc = 0, cnt = 0;
	for(int i = 0; i < n; ++ i) {
		if(str[i].length()) {
			bool flag = true;
			if(str[i][0] == 'B') ++ bc;
			else flag = false;
			if(str[i][str[i].length() - 1] == 'A') ++ ac;
			else flag = false;
			if(flag) ++ cnt;
		}
	}
	if(ac != bc) ans += min(ac, bc);
	else if(ac){
		if(cnt == ac) ans += ac - 1;
		else ans += ac;
	}
	cout << ans;
	return 0;
}
/*
4
A
BABA
B
AB
*/


Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int K, X;
	cin >> K >> X;
	if (K * 500 >= X) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


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

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> List(N);
	vector<pair<int, int>> Order(M);
	for (int i = 0; i < M; i++) {
		cin >> Order[i].first >> Order[i].second;
		List[Order[i].first - 1].push_back(Order[i].second);
	}
	for (int i = 0; i < N; i++) sort(List[i].begin(), List[i].end());
	for (int i = 0; i < M; i++) {
		int city = Order[i].first;
		const auto& l = List[city - 1];
		cout << setfill('0') << setw(6) << city
			<< setfill('0') << setw(6) << distance(l.begin(), lower_bound(l.begin(), l.end(), Order[i].second)) + 1 << endl;
	}
}

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

using namespace std;

#define REP(i,n)	for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,s,n)	for(int i=(s), i##_len=(n); i<i##_len; ++i)

#define ALL(obj)	(obj).begin(),(obj).end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

//typedef pair<int,int>			P;
typedef vector<int>				V;
typedef vector<V>				VV;

template<typename T>string join(const v(T)&v)
{stringstream s;REP(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define MAX 		40010

const ll LINF = (ll)1e18+7;		//
const int INF = 1e9+7;			//2,147,483,647 (Max int)
const ll MOD = 1e9+7;
// テンプレ終了
//====================================================================//




//
int main(){
	int N;cin>>N;
	V B(N-1);
	REP(i,N-1)cin>>B[i];

	int suml = B[0]+B[N-2];

	REPS(i,1,N-1){
		suml += min(B[i-1],B[i]);
	}

	cout << suml << endl;

	return 0;
}




Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int N;
  long int D;
  scanf("%d%ld", &N, &D);
  
  long int x[N], y[N], d;
  int i, count = 0;
  for (i = 0;i < N;i ++) {
    scanf("%ld%ld", &x[i], &y[i]);
    d = x[i] * x[i] + y[i] * y[i];
    if (d <= D*D) {
      count ++;
    }
  }
  
  printf("%d", count);
  return 0;
}
    


Measured memory_bytes: 4820
k=int(input())

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))
 
       
print(q[k-1])

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

const int MAX_N = 2 * 1e5 + 2;

bool is_visited[MAX_N];
int dist[MAX_N];
vector<int> graph[MAX_N];

void get_longest(int node, int d) {
    is_visited[node] = true;
    dist[node] = d;
    for (int i = 0; i < graph[node].size(); i++) {
        if (!is_visited[graph[node][i]]) {
            get_longest(graph[node][i], d + 1);
        }
    }
    return;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int a, b;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    get_longest(0, 0);
    int max_l = 0, node;
    for (int i = 0; i < N; i++) {
        if (max_l < dist[i]) {
            node = i;
            max_l = dist[i];
        }
    }
    for (int i = 0; i < N; i++) is_visited[i] = false;
    get_longest(node, 0);
    max_l = 0;
    for (int i = 0; i < N; i++) {
        max_l = max(max_l, dist[i]);
    }
    if (max_l % 3 == 1) cout << "Second" << endl;
    else cout << "First" << endl;
    return 0;
}

Measured memory_bytes: 21504
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int c = scan.nextInt();
		int m = scan.nextInt();
		int ans = 0;
		switch(c) {
		case 3:ans = 100000;
		break;
		case 2:ans = 200000;
		break;
		case 1:ans = 300000;
		}
		switch(m) {
		case 3:ans += 100000;
		break;
		case 2:ans += 200000;
		break;
		case 1:ans += 300000;
		}
		if(c == 1&&m == 1) {
			ans += 400000;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21972
# Can't Wait for Holiday

S = input()

if S == 'SUN':
    a = 0
elif S == 'MON':
    a = 1
elif S == 'TUE':
    a = 2
elif S == 'WED':
    a = 3
elif S == 'THU':
    a = 4
elif S == 'FRI':
    a = 5
elif S == 'SAT':
    a = 6

answer = 7 - a

print(answer)

Measured memory_bytes: 8900
using System;

class Program {
    private static int Main() {
        while( true ) {
            var input = Console.ReadLine();
            var values = input.Split( ' ' );

            int H = int.Parse( values[ 0 ] );
            int W = int.Parse( values[ 1 ] );

            if( H == 0 && W == 0 ) { break; }

            var output1 = new string( '#', W );
            var output2 = string.Format( "{0}{1}{2}", '#', new string( '.', W - 2 ), '#' );
            for( int i = 0; i < H; ++i ) {
                if( i == 0 || i == H - 1 ) {
                    Console.WriteLine( output1 );
                } else {
                    Console.WriteLine( output2 );
                }
            }
            Console.WriteLine();
        }

        return 0;
    }
}

Measured memory_bytes: 5368
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author TM
 */

#include <bits/stdc++.h>

using namespace std;

#include <bits/stdc++.h>

using namespace std;

//dp[i][j][k]:=x1,x2,…,xiまででj個使ってkを作れる総数
class CTakAndCards {
public:
    void solve(std::istream &cin, std::ostream &cout) {
        int n, a;
        cin >> n >> a;
        vector<int> x_vec(n, 0);
        for (int i = 0; i < n; ++i) {
            cin >> x_vec[i];
        }
        int max_sum = a * n;
        vector<vector<vector<long long int>>> dp(n + 1, vector<vector<long long int>>(n + 1,
                                                                                      vector<long long int>(max_sum + 1,
                                                                                                            0)));
//        vector<vector<int>> dp(n + 1, vector<int>(max_sum, 0));
//        dp[0][0] = 0;
        dp[0][0][0] = 0;
        for (long long int i = 1; i < n + 1; ++i) {
            int now = x_vec[i - 1];
            dp[i][1][now] = 1;
            for (long long int j = 1; j < i + 1; ++j) {
                for (long long int k = 1; k < max_sum + 1; ++k) {
//                    i枚目まで見て、j枚抜き取ったとき、和がkとなる組み合わせの数
                    if (k - now >= 0) dp[i][j][k] += dp[i - 1][j - 1][k - now];
                    dp[i][j][k] += dp[i - 1][j][k];
                }
            }
        }
//        for (int i = 1; i < n + 1; ++i) {
//            int now = x_vec[i - 1];
//            dp[i][now] = 1;
//            for (int j = 1; j < n + 1; ++j) {
//                if (dp[i - 1][j] == 0) continue;
//                dp[i][j] += dp[i - 1][j];
//                dp[i][j + now] += dp[i - 1][j];
//            }
//        }

        long long int ans = 0;
        for (int l = 1; l < n + 1; ++l) {
            ans += dp[n][l][a * l];
        }

        cout << ans << endl;

    }
};


int main() {
    CTakAndCards solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 52224
def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()

def killTime(H):
    if H ==0:
        return 0
    if H==1:
        return 1
    return 1+2*killTime(H//2)

def main():
    return killTime(iRaw())


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  vector<vll> a(3, vll(3));
  for (ll i = 0; i < 3; i++) {
    for (ll j = 0; j < 3; j++) {
      cin >> a[i][j];
    }
  }

  ll n;
  cin >> n;
  for (ll i = 0; i < n; i++) {
    ll b;
    cin >> b;
    for (ll j = 0; j < 3; j++) {
      for (ll k = 0; k < 3; k++) {
        if (b == a[j][k]) a[j][k] = 0;
      }
    }
  }

  for (ll i = 0; i < 3; i++) {
    for (ll j = 0; j < 3; j++) {
      if (a[i][j] > 0) break;
      if (j == 2) {
        Yes();
        return 0;
      }
    }
  }

  for (ll i = 0; i < 3; i++) {
    for (ll j = 0; j < 3; j++) {
      if (a[j][i] > 0) break;
      if (j == 2) {
        Yes();
        return 0;
      }
    }
  }

  for (ll i = 0; i < 3; i++) {
    if (a[i][i] > 0) break;
    if (i == 2) {
      Yes();
      return 0;
    }
  }

  for (ll i = 0; i < 3; i++) {
    if (a[i][2 - i] > 0) break;
    if (i == 2) {
      Yes();
      return 0;
    }
  }

  No();
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string>
#define ll long long
using namespace std;

#define MAX 100005

int main() {
  vector<int> l(MAX);
  int n;
  ll ans = 0;
  cin >>n;
  for(int i = 0; i < n ; i++){
    int a;
    cin >> a;
    l[a]++;
    ans += a;
  }
  ll q;
  cin >> q;
  for(ll i = 0; i < q; i++){
    int b,c;
    cin >> b >> c;
    ans += (ll)(c-b) * (ll)l[b];
    l[c] += l[b];
    l[b] = 0;
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3748
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include<cstdio>
using namespace std;

int main()
{
	string S;

	cin >> S;
	

	S.replace(3, 1, "8");
	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
S = input()
a = [0] * (len(S) + 1)
for i in range(len(S)):
    if S[i] == "<":
        a[i + 1] = a[i] + 1

for i in list(range(len(S)))[::-1]:
    if S[i] == ">" and a[i + 1] >= a[i]:
        a[i] = a[i + 1] + 1

print(sum(a))


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

using namespace std;

int main()
{
    int n  , x;
    cin >> n;
    int arr[n];
    vector< pair<int,int> >vp;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> x;
        vp.push_back({x,i+1});
    }
    sort(vp.begin(),vp.end());
    for(int i = 0 ; i < n ;i++)
    {
        cout << vp[i].second << " ";
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 1780
//
//  main.cpp
//  CP
//
//  Created by Shiv Pavan Raj on 22/02/20.
//  Copyright © 2020 Shiv Pavan Raj. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)(x).size())
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define M 1000000007
#define MM 998244353
#define SZ(a) int((a).size())

using ll = long long;
using VI = vector<int>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using VLL = vector<ll>;
using ld = long double;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}
const int MX = 2e5+10;
const int MX2 = 1e6+5;

ll INF= 4 * (ll)1e18;
int mx = 2 * (ll)1e9 + 10;


int main(int argc, const char * argv[]) {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); // insert code here...
    int l;
    cin >> l;
    cout << fixed << setprecision(6) << (double)l * l * l / 27 << endl;
    
    return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
int par[111111];
set<ii> R,B;
vi adjr[111111];
vi adjb[111111];

int rt(int u)
{
	if(par[u]<0) return u;
	else return (par[u]=rt(par[u]));
}

queue<ii> q;
int res;

void merge(int u, int v)
{
	u=rt(u); v=rt(v);
	if(u==v) return ;
	res++;
	if(par[u]>par[v]) swap(u,v);
	//v merges to u
	par[u]+=par[v]; par[v]=u;
	for(int i=0;i<adjr[v].size();i++)
	{
		int val=adjr[v][i]; val=rt(val);
		if(val==u) continue;
		adjr[u].pb(val);
		R.insert(mp(u,val));
		if(B.find(mp(u,val))!=B.end()||B.find(mp(val,u))!=B.end()) q.push(mp(u,val));
	}
	for(int i=0;i<adjb[v].size();i++)
	{
		int val=adjb[v][i]; val=rt(val);
		if(val==u) continue;
		adjb[u].pb(val);
		B.insert(mp(u,val));
		if(R.find(mp(u,val))!=R.end()||R.find(mp(val,u))!=R.end()) q.push(mp(u,val));
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	memset(par,-1,sizeof(par));
	int n; cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v;
		u--; v--;
		R.insert(mp(u,v));
		adjr[u].pb(v); adjr[v].pb(u);
	}
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v;
		u--; v--;
		B.insert(mp(u,v));
		adjb[u].pb(v); adjb[v].pb(u);
		if(R.find(mp(u,v))!=R.end()||R.find(mp(v,u))!=R.end())
		{
			q.push(mp(u,v));
		}
	}
	res=0;
	while(!q.empty())
	{
		int u=q.front().fi; int v=q.front().se; q.pop();
		merge(u,v);
	}
	cout<<(res==n-1?"YES":"NO")<<'\n';
}


Measured memory_bytes: 34816