akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=2005;
int n,m,fa[N][N],pos[N][N],ans;
vector<int>E[N];
void dfs(int u,int f,int *ff){
	ff[u]=f;
	for(int v:E[u])
		if(v!=f)
			dfs(v,u,ff);
}
void add(int x,int y){
	if(x==y||pos[x][y]==y||pos[y][x]==x)return;
	if(pos[x][y]!=-1)add(pos[x][y],y);
	else if(pos[y][x]!=-1)add(pos[y][x],x);
	else{
		pos[x][y]=y;pos[y][x]=x;queue<int>Q;
		Q.push(y);
		while(!Q.empty()){
			int u=Q.front();Q.pop();
			for(int v:E[u])
				if(v!=fa[x][u])
					if(pos[x][v]!=-1)
						add(y,v);
					else pos[x][v]=y,Q.push(v);
		}
		Q.push(x);
		while(!Q.empty()){
			int u=Q.front();Q.pop();
			for(int v:E[u])
				if(v!=fa[y][u])
					if(pos[y][v]!=-1)
						add(x,v);
					else pos[y][v]=x,Q.push(v);
		}
	}
}
void dfs2(int u,int f,int las){
	if(pos[las][u]==u)++ans,las=u;
	for(int v:E[u])
		if(v!=f)
			dfs2(v,u,las);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		E[x].push_back(y);E[y].push_back(x);
	}
	for(int i=1;i<=n;++i)dfs(i,0,fa[i]);
	memset(pos,-1,sizeof(pos));
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;++i)dfs2(i,0,i);
	printf("%d\n",ans>>1);
	return 0;
}


Measured memory_bytes: 32128
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod (int)1e9+7
#define inf (int)1e16
#define rep(i,n) for (int i = 0; i < n; i++)
#define Rep(i,n) for (int i = n; i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout<<endl;
#define P pair<int, int>
#define prique priority_queue<P, vector<P>, greater<P>>
struct edge { int to, cost; };
using namespace std;
template<typename T> void unsort(vector<T>& vec) {
	sort(all(vec), greater<T>());
	return;
}

int n, m;
priority_queue<int, vector<int>, greater<int>> que;
P p[114514];
int ans = 0;
signed main() {
	cin >> n >> m;
	rep(i, n) {
		int a;
		cin >> a;
		que.push(a);
	}
	rep(i, m) {
		cin >> p[i].second >> p[i].first;
	}
	sort(p, p + m, greater<P>());
	rep(i, m) {
		if (que.top() >= p[i].first) break;
		rep(j, p[i].second) {
			int b = que.top(); que.pop();
			if (b >= p[i].first) {
				que.push(b);
				break;
			}
			que.push(p[i].first);
		}
	}
	rep(i, n) {
		ans += que.top();
		que.pop();
	}
	cout << ans << endl;
}

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

namespace AOZ
{
	class MainClass
	{
		static void Main(string[] args)
		{
			//n
			//b f r v
			//b 1-4
			//f 1-3
			//r 1-10
			//
			const int room_num_per_building = 30;
			int[] rooms = new int[4 * 3 * 10];

			int n = int.Parse(Console.ReadLine());
			for (int i = 0; i < n; i++)
			{
				var arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
				int b = arr[0]; int f = arr[1]; int r = arr[2]; int v = arr[3];
				int room_id = (b - 1) * room_num_per_building + ((f - 1) * 10) + (r - 1);
				rooms[room_id] += v;
			}
			var sb = new StringBuilder();
			var index = 0;
			foreach (var r in rooms)
			{
				if (index != 0)
				{
					if (index % 10 == 0) sb.AppendLine();
					if (index % 30 == 0) sb.AppendLine("####################");
				}
				sb.Append(" "+r);
				index++;
			}
			Console.WriteLine(sb.ToString());
		}
	}
}



Measured memory_bytes: 16316
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
LL a[50];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	LL ans = 0;
	while (1) {
		LL sum = 0;
		for (int i = 0; i < N; i++) sum += a[i] / N;
		if (sum == 0) break;
		ans += sum;
		for (int i = 0; i < N; i++) {
			LL q = a[i] / N;
			a[i] += sum - q;
			a[i] -= q*N;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
while True:

 sent = input()

 if sent == "-":
  break

 else:

  sn = len(sent)

  m = int(input())

  l = [0 for i in range(sn)]

  for i in range(m):
   h = int(input())

   for j in range(sn-h):
    l[j] = sent[j+h]

   for k in range(h):
    l[sn-h+k] = sent[k]

   sent = "".join(map(str, l))

  print(sent)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define read cin >>
#define echo cout <<
#define fin << endl
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)

// for debug macro
bool global_debug_flag = true;
#define DEBUG(val) \
  if (global_debug_flag) cout << #val << " = " << val << endl

int dp[105][2][105];

int rec(string &s, int D, int keta = 0, bool tight = true, int sum = 0) {
  if (keta == s.size()) {
    // sum??????????(sum == D)?1???
    // ????????0???
    return sum == D;
  }

  int x = s[keta] - '0';
  int r = tight ? x : 9;
  int res = 0;
  // -1??????????????????????????????
  if (dp[keta][tight][sum] != -1) {
    return dp[keta][tight][sum];
  } else {
    for (int i = 0; i <= r; i++) {
      if (i == 0) {
        res += rec(s, D, keta + 1, tight && i == r, sum);
      } else {
        res += rec(s, D, keta + 1, tight && i == r, sum + 1);
      }
    }
  }
  dp[keta][tight][sum] = res;
  return res;
}

int main() {
  memset(dp, -1, sizeof(dp));
  string s;
  read s;
  int k;
  read k;
  // cout << dp[s.size()][0][k] + dp[s.size()][1][k] << endl;
  cout << rec(s, k) << endl;
}


Measured memory_bytes: 384
//わからなかった

#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  string s;
  cin >> s;

  sort(all(s));
  if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define fin ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define w(t) while(t--)
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
#define what_is(x) cerr << #x << " is " << x << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e6 + 3;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
const double E = 1e-9;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
ll a, b;
ll f(int x){
    return  floor((a * x) / b) - (a * floor(x / b));
}
int main(){
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    fin;
    ll n;
    cin >> a >> b >> n;
    ll x = min(b - 1, n);
    cout << floor((a * x) / b) << '\n';
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;
}   

Measured memory_bytes: 3756
#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;
const int INF = 1 << 30;
const long long MOD = 1000000000 + 7;
const double PI = acos(-1);

int main() {
	int N; cin >> N;
	vector<int> W(N);
	rep(i, N)cin >> W[i];
	int s1 = W[0];
	int s2 = accumulate(W.begin() + 1, W.end(), 0);
	int ans = abs(s1 - s2);
	rep(i, N - 1) {
		s1 += W[i + 1];
		s2 -= W[i + 1];
		int dif = abs(s1 - s2);
		if (ans > dif)ans = dif;
	}
	cout << ans;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Pair{
	int x;
	int y;
	public Pair(int x,int y) {this.x=x;this.y=y;}
}
class UnionFind{
	int[] par;
	public UnionFind(int N) {
		par=new int[N];
		for(int i=0;i<N;i++)par[i]=i;
	}
	int root(int x) {
		if(par[x]==x)return x;
		return par[x]=root(par[x]);
	}
	void unite(int x,int y) {
		int rx=root(x);
		int ry=root(y);
		if(rx==ry)return;
		par[rx]=ry;
	}
	boolean same(int x,int y) {
		int rx=root(x);
		int ry=root(y);
		return rx==ry;
	}
}

public class Main {
	static int N;
	static int M;
	static int[]p;
	static Pair[]sw;
	static UnionFind uf;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		M= sc.nextInt();
		p=new int[N+1];
		sw=new Pair[M+1];
		for(int i=1;i<=N;i++) {
			p[i]=sc.nextInt();
		}
		for(int i=1;i<=M;i++) {
			sw[i]=new Pair(sc.nextInt(),sc.nextInt());
		}
		uf=new UnionFind(N+1);

		for(int i=1;i<=M;i++) {
			Pair s=sw[i];
			uf.unite(s.x, s.y);
		}
		int sum=0;
		for(int i=1;i<=N;i++) {
			if(uf.same(i, p[i]))sum++;
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 97048
#!/usr/bin/env python3
#ABC42 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

h,w,a,b = map(int,input().split())

fact = [1]*(200000+1)
for i in range(1,200000+1):
    fact[i] = fact[i-1]*(i) % mod

def comb(n,r):
    return fact[n] * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod) % mod
ans = 0
for i in range(b,w):
    x = comb(h-a-1+i,i)*comb(a-1+w-i-1,a-1) % mod
    ans += x
    ans %= mod
print(ans)


Measured memory_bytes: 42860
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End

/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template

signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Cinii(a, b);
    int sub = b - a - 1;
    cout << sub * (sub + 1)/2 - a << nn;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;

signed main()
{
    int n;
    cin >> n;
    
    vi a(n);
    rep(i, n){
        cin >> a[i];
        --a[i];
    }
    
    int ans = 0;
    int i = 0;
    while(1){
        while(i < n && a[i] != i) ++i;
        if(i == n) break;
        
        int j = i;
        while(j < n && a[j] == j) ++j;
        ans += (j-i+1) / 2;
        if(j == n) break;
        i = j;
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 640
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		ArrayList<String> input = new ArrayList<String>();
		Scanner insert = new Scanner(System.in);
		String line = insert.nextLine();
		int nn = Integer.parseInt(line);
		for(int i = 0; i < nn; i++) {
			String line2 = insert.nextLine();
			if (line2.equals("")) {
				break;
			}
			input.add(line2);
		}
		for(String a:input) {
			int sum = 0;
			String array1[] = a.split(" ");
			int y = Integer.parseInt(array1[0]);
			int m = Integer.parseInt(array1[1]);
			int day = Integer.parseInt(array1[2]);
			int n = 1000-y;
			for(int i = 0;i < n; i++) {
				if(i % 3 == 0) {
					sum+=200;
				}
				else {
					sum+=195;
				}
			}
			if(y % 3 == 0) {
				for(int i = 1; i <= m; i++) {
					sum-=20;
				}
			}
			else {
				for(int i = 1; i <= m; i++) {
					if(i % 2 == 0) {
						sum-=19;
					}
					else {
						sum-=20;
					}
				}
			}
			if((y % 3 != 0) && (m % 2 ==0)) {
				sum+=(20-day);
			}
			else {
				sum+=(21-day);
			}
			System.out.println(sum);
		}
	}


}




Measured memory_bytes: 26356
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int main() {
  int h, w;
  cin >> h >> w;
  char s[h][w];
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> s[i][j];
    }
  }
  int ans = -1;
  for (int sy = 0; sy < h; ++sy) {
    for (int sx = 0; sx < w; ++sx) {
      if (s[sy][sx] == '#') continue;
      queue<pair<int, int> > que;
      vector<vector<int> > dist(h, vector<int>(w, -1));
      que.push(make_pair(sy, sx));
      dist[sy][sx] = 0;
      while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        for (int d = 0; d < 4; ++d) {
          int ny = y + dy[d];
          int nx = x + dx[d];
          if (0 <= ny && ny < h && 0 <= nx && nx < w) {
            if (s[ny][nx] == '.' && dist[ny][nx] == -1) {
              que.push(make_pair(ny, nx));
              dist[ny][nx] = dist[y][x] + 1;
            }
          }
        }
      }
      int res = -1;
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
          if (s[i][j] == '#') continue;
          res = max(res, dist[i][j]);
        }
      }
      ans = max(ans, res);
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

using ll = long long;

constexpr ll MOD = 1000000007;

#ifndef ONLINE_JUDGE
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
#else
#define print(...)
#endif

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H1, H2, M1, M2, K;
    
    cin >> H1 >> M1  >> H2 >> M2 >> K;

    ll T1 = H1 * 60 + M1; 
    ll T2 = H2 * 60 + M2;

    if(T1 > T2){
        T2 += 24 * 60;
    }

    ll diff = T2-T1;

    ll ans = max(diff-K,0ll);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
int D;
int c[27], s[400][27];
int L[27];
int last[27];
long long ANS = 0;
long long ans = 0;
int main(){
    scanf("%d",&D);
    for (int i = 1; i <= 26; i++) scanf("%d",&c[i]);
    for (int i = 1; i <= D; i++){
        for (int j = 1; j <= 26; j++)
            scanf("%d",&s[i][j]);
    }
    for (int i = 1; i <= D; i++){
        int b1 = -1;
        long long ok = 0;
        for (int t = 1; t <= 26; t++){
            for (int x = 1; x <= 26; x++){
                for (int y = 1; y <= 26; y++){
                    ans = ANS;
                    for (int j = 1; j <= 26; j++){
                        last[j] = L[j];
                    }

                        ans += (s[i][t]+c[t]*(D-i)/2);
                        last[t] = i;

                        for (int j = 1; j <= 26; j++){
                            ans -= c[j]*(i-last[j]);
                        }

                    if (i != D){
                        ans += (s[i+1][x]+c[x]*(D-i-1)/2);
                        last[x] = i+1;
                        for (int j = 1; j <= 26; j++){
                            ans -= c[j]*(i+1-last[j]);
                        }
                    }

                    if (i < D-1){
                        ans += (s[i+2][y]+c[y]*(D-i-2)/50);
                        last[y] = i+2;
                        for (int j = 1; j <= 26; j++){
                            ans -= c[j]*(i+2-last[j]);
                        }
                    }

                    if (b1 == -1 || ans > ok){
                        b1 = t;
                        ok = ans;
                    }
                }
            }
            //printf("for %d: %lld\n",t,ans);
        }
        ANS += s[i][b1];
        L[b1] = i;
        for (int j = 1; j <= 26; j++){
            ANS -= c[j]*(i-L[j]);
        }
        printf("%d\n",b1);
        //printf("score %lld\n",ANS);
    }
}


Measured memory_bytes: 3900
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
int dp[4010][4010];
int ka[214514],inv[214514];
void setkaijo(int n){
	ka[0]=1;
	for(int i=1;i<=n;i++){
		ka[i] = ka[i-1] * i;
		ka[i] %= inf;
	}
}
int modpow(int x,int k){
	// x ^ k mod inf
	int p2[55],res=1;
	p2[0]=1;p2[1]=x%inf;
	for(int i=2;i<=50;i++){
		p2[i]=p2[i-1]*p2[i-1];
		p2[i] %= inf;
	}
	for(int i=1;i<=50;i++){
		if(k%2==1){
			res *= p2[i];
			res %= inf;
		}
		k /= 2;
	}
	return res;
}
void setinv(int n){
	for(int i=0;i<=n;i++){
		inv[i] = modpow(ka[i],(ll)inf-2);
	}
}
int comb(int n,int k){
	if( k<0 || n<0 || k>n)return 0;
	if(k==0 || k==n)return 1;
	int res = (ka[n] * inv[k]) % inf;
	res = (res*inv[n-k]) % inf;
	return res;
}
signed main(){
	string st;
	cin>>st;
	int n = st.size();
	setkaijo(10000);
	setinv(10000);
	dp[0][0] = 1;
	int rc = 0, bc = 0;
	for(int i=1;i<=n;i++){
		char cur = st[i-1];
		if( cur == '2'){
			rc += 2;
		}
		else if( cur == '1' ){
			rc++;
			bc++;
		}
		else{
			bc += 2;
		}
		for(int j=0;j<=2000;j++){
			if( j <= n && j < rc ){
				dp[i][j+1] += dp[i-1][j];
				dp[i][j+1] %= inf;
			}
			if( (i-1-j) >= 0 && (i-1-j) < bc){
				dp[i][j] += dp[i-1][j];
				dp[i][j] %= inf;
			}
		}
	}
	//for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){cout<<"dp"<<i<<j<<" "<<dp[i][j]<<endl;}}
	int ans = 0;
	for(int i=0;i<=n;i++){
		ans += dp[n][i] * comb(n,rc-i);
		ans %= inf;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 65920
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))

const ll mod = 1e9 + 7;
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll a , ll b){ a = a%mod; if(b == 0) return 1LL;if(b&1)  return (a*1LL*expo(a , b - 1))%mod;ll t = expo(a , b/2);return (t*1LL*t)%mod;}
ll inv(ll x){return expo(x,mod-2);}
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};

const int M = 2e5 + 5;


int main(){
    //freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);

int n;
cin >> n;

cout<<48 - n;



















}














Measured memory_bytes: 256
N=int(input())
m=0
a=0
r=0
c=0
h=0
for i in range(N):
  s=input()
  if s[0]=="M":
    m+=1
  if s[0]=="A":
    a+=1
  if s[0]=="R":
    r+=1
  if s[0]=="C":
    c+=1
  if s[0]=="H":
    h+=1
ans=0
L=[m,a,r,c,h]
for i in range(3):
  for j in range(i+1,4):
    for k in range(j+1,5):
      ans+=L[i]*L[j]*L[k]
print(ans)

Measured memory_bytes: 3188
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int[] a = new int[10];
            for(int i=1; i<=4; i++) a[sc.nextInt()] = i;
            int hit = 0;
            int blow = 0;
            for(int i=1; i<=4; i++) {
                int b = sc.nextInt();
                if(i == a[b]) hit++;
                else if(a[b] > 0) blow++;
            }
            System.out.println(hit + " " + blow);
        }
    }
}



Measured memory_bytes: 26140
def prime_factors(n):
    i = 2
    factors = []
    while i**2 <= n:
        if n % i != 0:
            i += 1
        else:
            factors.append(i)
            n = n // i
    if n > 1:
        factors.append(n)
    return factors

def resolve():
    N = int(input())
    import collections
    factors = collections.Counter(prime_factors(N))
    numbers = [0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9]
    cnt = 0
    for k, v in factors.items():
        cnt += numbers[v]
    print(cnt)


if '__main__' == __name__:
    resolve()


Measured memory_bytes: 9384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
const int INF = 1 << 30;
 
class Solver {
  public:
    bool solve() {
        int N, M; cin >> N >> M;
        vector<int> A(N), B(N); rep(i, N) cin >> A[i] >> B[i];
        vector<int> C(M), D(M); rep(i, M) cin >> C[i] >> D[i];
 
        rep(i, N) {
            int a = A[i], b = B[i];
            int index = -1, dist = INF;
            rep(j, M) {
                int dd = abs(a - C[j]) + abs(b - D[j]);
                if(set_min(dist, dd)) {
                    index = j + 1;
                }
            }
            cout << index << endl;
        }
        return 0;
    }
};
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}

Measured memory_bytes: 256
while True:
    n = int(input())
    if n == 0:
        break
    
    a = []
    for i in range(n):
        p = list(input())
        a.append(len(p))
    
    def solve(a):
        N = len(a)
        for i in range(N):
            judge = 0
            rest = 5
            for j in range(i,N):
                if judge == 0:
                    rest -= a[j]
                    if rest == 0:
                        judge = 1
                        rest = 7
                    elif rest < 0:
                        break
                elif judge == 1:
                    rest -= a[j]
                    if rest == 0:
                        judge = 2
                        rest = 5
                    if rest < 0:
                        break
                elif judge == 2:
                    rest -= a[j]
                    if rest == 0:
                        judge = 3
                        rest = 7
                    elif rest < 0:
                        break
                elif judge == 3:
                    rest -= a[j]
                    if rest == 0:
                        judge = 4
                        rest = 7
                    elif rest < 0:
                        break
                elif judge == 4:
                    rest -= a[j]
                    if rest == 0:
                        judge = 5
                        break
                    elif rest < 0:
                        break
            if judge == 5:
                return i+1
    print(solve(a))


Measured memory_bytes: 5612
/**
*     => Md. Sajjat Hosen
*     => Department of Computer Science and Engineering
*     => Bangabandhu Sheikh Mujibur Rahman Science and Technology University
**/

/*..................! TRY ONCE MORE !..................*/

/*...Part - 01...*/

#include <bits/stdc++.h>
using namespace std ;

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

int Int(){int x ; scanf("%d",&x) ; return x ;}
ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
float Float(){float x ; scanf("%f",&x) ; return x ;}
double Double(){double x ; scanf("%lf",&x); return x;}

/*...Part - 03...*/
/*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)2e5 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     Int         Int()
#define     Long        Long()
#define        Float         Float()
#define     Double         Double()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/



int main(){
    //freopen("input.txt","r",stdin);
    int test = 1 , tc = 0 ;
    int i, ans = 0, x, y, j, l;
    while(test--){
        char a[150];
        scanf("%s", &a);
        l = strlen(a);
        j = l - 1;
        if(l % 2 == 0){
            x = l / 2;
            for(i = 0; i < x ; i++){
                if(a[i] != a[j--])
                    ans++;
            }
        }
        else{
            x = l / 2;
            for(i = 0; i < x ; i++){
                if(a[i] != a[j--])
                    ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll                    long long int
#define pb                    push_back
#define F                     first
#define S                     second
#define mp                    make_pair
#define MOD                   1000000007
#define vi                    vector<int>
#define vll                   vector<ll>
#define pll                   pair<ll,ll>
#define pii                   pair<int,int>
#define all(p)                p.begin(),p.end()
#define mid(s,e)              (s+(e-s)/2)
#define eb                    emplace_back
#define ull                   unsigned long long
#define KAMEHAMEHA            ios_base::sync_with_stdio(0);
#define RASENGAN              ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
    KAMEHAMEHA
//    #ifdef _soumik
//        freopen("input.txt", "r", stdin);
//    #endif
    int a,b;
    cin>>a>>b;
    if(a>b)
    {
        for(int i=1;i<=a;i++)
            cout<<b;
    }
    else
    {
        for(int i=1;i<=b;i++)
            cout<<a;
    }
    cout<<endl;
    return 0;
}




Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
h = LIST()
ans = 0
while sum(h) > 0:
	flag = False
	for i in range(N):
		if flag and h[i] == 0:
			flag = False
			ans += 1
		elif h[i] != 0:
			h[i] -= 1
			flag = True
	if flag:
		ans += 1
print(ans)


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

namespace Atcoder
{
    class Atcoderrrrrrr
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            List<string> set = new List<string>();
            string ans = "Yes";
            for(int i =0;i<N;i++){
                string obj = Console.ReadLine();
                if(set.Contains(obj)){
                    ans = "No";
                    break;
                }else{
                    set.Add(obj);
                }
                if(i>0){
                    if(set[i-1].EndsWith(obj.Substring(0,1))==false){
                        ans = "No";
                        break;
                    }
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(i=a;i<b;i++)
#define rloop(i,a,b) for(i=a;i>=b;i--)
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf=1000000001;
const ll INF=1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
#define T tuple<int,int,int>

int main(){
	int n;
	cin>>n;
	int i,j;
	vi s(n);
	int sum=0;
	loop(i,0,n){
		cin>>s[i];
		sum+=s[i];
	}
	sort(s.begin(),s.end());
	if(sum%10!=0){
		cout<<sum<<endl;
		return 0;
	}else{
		loop(i,0,n){
			if(s[i]%10!=0){
				cout<<sum-s[i]<<endl;
				return 0;
			}
		}
	}
	cout<<0<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//do {
//    print(v);
//  } while (std::next_permutation(v.begin(), v.end()));
int H,W;
int G[201][201];
int c[10][10];
void warshall(){
	REP(i,10){
		REP(j,10){
			REP(k,10){
				c[j][k]=min(c[j][k],c[j][i]+c[i][k]);
			}
		}
	}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	cin>>H>>W;
	REP(i,10){
		REP(j,10)cin>>c[i][j];
	}
	REP(i,W){
		REP(j,H){
			cin>>G[i][j];
		}
	}
	warshall();
	REP(i,10){
		//REP(j,10)cout<<c[i][j];
		//cout<<endl;
	}
	int ans=0;
	REP(i,W){
		REP(j,H){
			if(G[i][j]==-1 || G[i][j]==1)continue;
			ans+=c[G[i][j]][1];
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}




















Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <string>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
const int MOD = 1e9+7;

int main(){
    int H,W;
    cin >> H >> W;
    vector<string> str(1001);
    rep(i,H) cin >> str[i];
    ll dp[1001][1001];
    //int dp[101][101];
    
    dp[0][0] = 1;

    rep(i,H){
        rep(j,W){
            //右
            if(j+1 < W){
                if(str[i][j+1] == '.'){
                    dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
                }
            }
            //下
            if(i+1 < H){
                if(str[i+1][j] == '.'){
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
                }
            }
        }
    }

    // rep(i,H){
    //     rep(j,W){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    cout << dp[H-1][W-1] << endl;

    return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
namespace Flandle_Scarlet
{
    #define N 100100
    class Graph
    {
        public:
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            int head[N];
            int EdgeCount;

            void clear()
            {
                memset(Ed,-1,sizeof(Ed));
                memset(head,-1,sizeof(head));
                EdgeCount=0;
            }
            void AddEdge(int u,int v,int w)
            {
                ++EdgeCount;
                Ed[EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }

            int Start(int u){return head[u];}
            int To(int i){return Ed[i].To;}
            int Label(int i){return Ed[i].Label;}
            int Next(int i){return Ed[i].Next;}
    }G;
    void Add(int u,int v,int w,bool dir=0)
    {
        G.AddEdge(u,v,w);
        if (!dir){G.AddEdge(v,u,w);}
    }

    int color[N];
    int maxd[N];
    void DFS(int u,int dis,int c)
    {
        if (maxd[u]>=dis) return;
        maxd[u]=dis;
        if (color[u]==0) color[u]=c;

        for(int i=G.Start(u);~i;i=G.Next(i))
        {
            int v=G.To(i);
            if (~v)
            {
                DFS(v,dis-1,c);
            }
        }
    }

    int n,m,q;
    struct Question1
    {
        int v,d,c;
    }Q[N];
    void Input()
    {
        G.clear();
        memset(maxd,-1,sizeof(maxd));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            Add(u,v,1);
        }
        scanf("%d",&q);
        for(int i=1;i<=q;++i)
        {
            int v,d,c;
            scanf("%d%d%d",&v,&d,&c);
            Q[i]=(Question1){v,d,c};
        }
        reverse(Q+1,Q+q+1);
    }

    void Soviet()
    {
        for(int i=1;i<=q;++i)
        {
            DFS(Q[i].v,Q[i].d,Q[i].c);
        }
        for(int i=1;i<=n;++i)
        {
            printf("%d\n",color[i]);
        }
    }
    void IsMyWife()
    {
        if (0)
        {
            freopen("","r",stdin);
            freopen("","w",stdout);
        }
        Input();
        Soviet();
    }
};
int main()
{
    Flandle_Scarlet::IsMyWife();
    return 0;
}


Measured memory_bytes: 5376
#include<iostream>

using namespace std;

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

int main(){
    long int n;
    cin >> n;
    long int a;
    long int b;
    for (long int i = 1; i * i <= n; i++){
        if(n % i == 0){
            a = i;
            b = n / i;
        }
    }
    cout << (a - 1) + (b - 1) << endl;
    
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 5+1)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


N, M = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')


Measured memory_bytes: 128940
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
void ERR(T)(in T x) { stderr.writeln(x); }

long mod = pow(10, 9) + 7;
long moda(long x, long y) { return (x + y) % mod; }
long mods(long x, long y) { return ((x + mod) - (y % mod)) % mod; }
long modm(long x, long y) { return (x * y) % mod; }

void main()
{
	auto S = RD!string;
	auto T = RD!string;

	ulong pos = ulong.max;
	foreach (i; 0..S.length-T.length+1)
	{
		bool ng = false;
		foreach (j, c; T)
		{
			if (S[i+j] != c && S[i+j] != '?')
			{
				ng = true;
				break;
			}
		}
		if (!ng)
		{
			pos = i;
		}
	}
	if (pos == ulong.max) writeln("UNRESTORABLE");
	else
	{
		auto ans = S.dup;
		foreach (i; 0..T.length)
		{
			ans[pos+i] = T[i];
		}
		ans = ans.replace("?", "a");
		writeln(ans);
	}
	
	stdout.flush();
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#define llint long long
#define inf 1e18
#define mod 1000000007

using namespace std;

llint n, k;
llint a[200005], f[200005];

bool check(llint x)
{
  llint ret = 0;
  for(int i = 1; i <= n; i++){
    if(x >= a[i]*f[i]) continue;
    llint dif = a[i]*f[i] - x;
    ret += (dif+f[i]-1) / f[i];
  }
  return ret <= k;
}

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> f[i];
  sort(a+1, a+n+1);
  sort(f+1, f+n+1);
  reverse(f+1, f+n+1);

  llint ub = 1e18, lb = -1, mid;
  while(ub-lb>1){
    mid = (ub+lb)/2;
    if(check(mid)) ub = mid;
    else lb = mid;
  }
  cout << ub << endl;

  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;



int main() {
	int n, a, b, c;
	cin >> n >> a >> b >> c;
	string s[n];
	rep (i, n) cin >> s[i];

	vector<char> ans;
	if (a + b + c >= 2) {
		if (a == 0 && b == 0 && s[0] == "AB" || a == 0 && c == 0 && s[0] == "AC" || b == 0 && c == 0 && s[0] == "BC") {
			cout << "No" << endl;
			return 0;
		}
		rep (i, n) {
			if (i != n - 1) {
				if (s[i+1] == "AB") {
					if (s[i] == "AB") {
						if (a > b) {
							ans.pb('B');
							b++; a--;
						}
						else {
							ans.pb('A');
							b--; a++;
						}
					}
					if (s[i] == "AC") {
						if (c == 0) {
							ans.pb('C');
							c++; a--;
						}
						else {
							ans.pb('A');
							a++; c--;
						}
					}
					if (s[i] == "BC") {
						if (c == 0) {
							ans.pb('C');
							c++; b--;
						}
						else {
							ans.pb('B');
							b++; c--;
						}
					}
				}
				if (s[i+1] == "AC") {
					if (s[i] == "AB") {
						if (b == 0) {
							ans.pb('B');
							b++; a--;
						}
						else {
							ans.pb('A');
							a++; b--;
						}
					}
					if (s[i] == "AC") {
						if (a > c) {
							ans.pb('C');
							c++; a--;
						}
						else {
							ans.pb('A');
							a++; c--;
						}
					}
					if (s[i] == "BC") {
						if (b == 0) {
							ans.pb('B');
							b++; c--;
						}
						else {
							ans.pb('C');
							c++; b--;
						}
					}
				}
				if (s[i+1] == "BC") {
					if (s[i] == "AB") {
						if (a == 0) {
							ans.pb('A');
							a++; b--;
						}
						else {
							ans.pb('B');
							b++; a--;
						}
					}
					if (s[i] == "AC") {
						if (a == 0) {
							ans.pb('A');
							a++; c--;
						}
						else {
							ans.pb('C');
							c++; a--;
						}
					}
					if (s[i] == "BC") {
						if (b > c) {
							ans.pb('C');
							c++; b--;
						}
						else {
							ans.pb('B');
							b++; c--;
						}
					}
				}
			}
			else {
				if (s[i] == "AB") ans.pb(a > b ? 'B' : 'A');
				if (s[i] == "AC") ans.pb(a > c ? 'C' : 'A');
				if (s[i] == "BC") ans.pb(b > c ? 'C' : 'B');
			}
		}
	}
	else if (a + b + c == 1) {
		rep (i, n) {
			if (s[i] == "AB") {
				if (a || b) {
					ans.pb(a > b ? 'B' : 'A');
					swap(a, b);
				}
			}
			if (s[i] == "AC") {
				if (a || c) {
					ans.pb(a > c ? 'C' : 'A');
					swap(a, c);
				}
			}
			if (s[i] == "BC") {
				if (b || c) {
					ans.pb(b > c ? 'C' : 'B');
					swap(b, c);
				}
			}
		}
	}

	if (ans.size() < n) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
		rep (i, n) cout << ans[i] << endl;
	}
	return 0;
}

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

int D,x,y;
string a[30];
int p[30];


int calc(int bit){
  int sum = 0;
  for(int i=0;i<x;i++){
    if( (bit>>i&1) && a[i] == "D")sum += p[i];
  }
  for(int i=0;i<y;i++){
    if( (bit>>(x+2*i)&1) && (bit>>(x+2*i+1)&1) && a[x+i] == "DD")
      sum += p[x+i];
  }
  return sum;
}


int main(){
  cin >> D;

  cin >> x;
  for(int i=0;i<x;i++)cin >> a[i] >> p[i];

  cin >> y;
  for(int i=0;i<y;i++)cin >> a[x+i] >> p[x+i];

  D = min(D, x+2*y);

  int res = 0;
  int comb = (1<<D) -1;
  while( comb < (1<<(x+2*y)) ){
    
    res = max(res, calc(comb));

    int x = comb & -comb, y = comb + x;
    comb = ( ( (comb & ~y) /x ) >> 1) | y;
  }
  cout << res << endl;
}

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

using namespace std;

class UnionFind {
  int n;
  vector<int> par;
  vector<int> rk;
  vector<int> sz;
public:
  UnionFind(int n): n(n), par(n), rk(n), sz(n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
      sz[i] = 1;
    }
  }

  int f(int i) {
    if (par[i] == i) return i;
    return par[i] = f(par[i]);
  }

  bool same(int i, int j) {
    return f(i) == f(j);
  }

  int size(int i) {
    i = f(i);
    return sz[i];
  }

  void unite(int i, int j) {
    i = f(i);
    j = f(j);
    if (rk[i] > rk[j]) {
      par[j] = i;
      sz[i] += sz[j];
    } else if (rk[i] < rk[j]) {
      par[i] = j;
      sz[j] += sz[i];
    } else {
      par[i] = j;
      sz[j] += sz[i];
      rk[j] += 1;
    }
  }
};

class Solver {
  int N;
  int M;
  vector<int> A;
  vector<int> B;
  UnionFind uf;
public:
  Solver(int N, int M, vector<int> A, vector<int> B): N(N), M(M), A(A), B(B), uf(N) {}

  vector<int64_t> exec() {
    vector<int64_t> ans;
    ans.push_back((int64_t)N * (N - 1) / 2);

    for (int i = M - 1; i >= 1; i--) {
      int a = A[i], b = B[i];

      if (!uf.same(a, b)) {
        ans.push_back(ans.back() - (int64_t)uf.size(a) * uf.size(b));
        uf.unite(a, b);
      } else {
        ans.push_back(ans.back());
      }
    }

    reverse(ans.begin(), ans.end());
    return ans;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i] -= 1;
    B[i] -= 1;
  }
  auto ans = Solver(N, M, A, B).exec();
  for (auto i: ans) cout << i << endl;
}

Measured memory_bytes: 4984
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return min(x, y)


@njit
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8, i8[:]), cache=True)
def main(N, TX):
    dp1 = np.full(N, N - 2, np.int64)
    dp2 = np.full(N, N - 2, np.int64)
    seg1 = np.full(N + N, N - 2, np.int64)
    seg2 = np.full(N + N, N - 2, np.int64)
    filled1 = np.zeros(N, np.int64)
    filled2 = np.zeros(N, np.int64)

    ans = 0
    for i in range(0, len(TX), 2):
        t, x = TX[i:i + 2]
        x -= 2
        if t == 1 and filled1[x]:
            continue
        if t == 2 and filled2[x]:
            continue
        if t == 1:
            n = fold(seg2, x, N)
            ans += n
            if n:
                dp1[n - 1] = min(dp1[n - 1], x)
                set_val(seg1, n - 1, dp1[n - 1])
        elif t == 2:
            n = fold(seg1, x, N)
            ans += n
            if n:
                dp2[n - 1] = min(dp2[n - 1], x)
                set_val(seg2, n - 1, dp2[n - 1])
    return (N - 2) * (N - 2) - ans


N, Q = map(int, readline().split())
TX = np.array(read().split(), np.int64)

print(main(N, TX))


Measured memory_bytes: 123908
#!/usr/bin/env python
# coding: utf-8
#


def main(k):
    kinum = int(k/2) + k%2
    gunum = int(k/2)
    print(kinum * gunum)
    
if __name__ == '__main__':
    try:
        k = int(input().strip())
        main(k)
    except EOFError:
        pass


Measured memory_bytes: 3316