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

const int MAXN = 1e6 + 10;

int main(int argc, char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    if(argc > 1 && !strcmp(argv[1], debug.debug)) debug.on = true;

    int a, b;
    cin >> a >> b;
    cout << max(0, a - 2 * b) << endl;
    return 0;
 
}























Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }


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

    vector<int>d(N);
    rep(i,N)cin >> d[i];

    sort(d.begin(),d.end());

    cout << d[N/2] - d[(N/2)-1] << endl;

    

}



Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int main() {
#define int ll
    int N, W;
    cin >> N >> W;
    int w[N], v[N];
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];
    if(W < w[0]) {
        cout << 0 << "\n";
        return 0;
    }
    int tmp = w[0];
    for(int i = N - 1; i >= 0; i--) w[i] -= w[0];
    int dp[N + 1][N * 3 + 1];
    for(int i = 0; i <= N; i++)
        for(int j = 0; j <= N * 3; j++) dp[i][j] = -1;
    dp[0][0] = 0;
    for(int i = 0; i < N; i++) {
        for(int a = N * 3; a >= 0; a--) {
            for(int k = N; k >= 0; k--) {
                if(dp[k][a] == -1) continue;
                dp[k + 1][a + w[i]] = max(dp[k + 1][a + w[i]], dp[k][a] + v[i]);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= N * 3; j++) {
            if(W < tmp * i + j) continue;
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 512
using System;

class ITP1_4_D
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string[] Input_Str = Console.ReadLine().Split(' ');

        int[] Input_Num = new int[n];
        int min, max;
        long sum = 0;

        for (int i = 0; i < n; i++)
            Input_Num[i] = int.Parse(Input_Str[i]);

        min = Input_Num[0];
        max = Input_Num[0];

        for (int i = 0; i < n; i++)
        {
            if (Input_Num[i] < min)
                min = Input_Num[i];
            if (Input_Num[i] > max)
                max = Input_Num[i];
            sum += Input_Num[i];
        }

        Console.WriteLine(min + " " + max + " " + sum);
    }
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

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

    int res = (x / 500) * 1000;
    x %= 500;

    res += (x / 5) * 5;

    cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
  node* prev;
  int v;
  node(){}
  node(int v):v(v){}
};
struct mstack{
  node *cur;
  mstack(){
    cur=NULL;
  }
  void push(int k){
    node *tmp=new node(k);
    tmp->prev=cur;
    cur=tmp;
  }
  void pop(){
    node *tmp=cur->prev;
    delete(cur);
    cur=tmp;
  }
  int top(){
    return cur->v;
  }
};
signed main(){
  string s;
  vector<string> v;
  while(cin>>s) v.push_back(s);
  mstack st; 
  for(int i=0;i<(int)v.size();i++){
    if(v[i][0]=='+'){
      int r=st.top();st.pop();
      int l=st.top();st.pop();
      st.push(l+r);
      continue;
    }
    if(v[i][0]=='-'){
      int r=st.top();st.pop();
      int l=st.top();st.pop();
      st.push(l-r);
      continue;
    }
    if(v[i][0]=='*'){
      int r=st.top();st.pop();
      int l=st.top();st.pop();
      st.push(l*r);
      continue;
    }
    st.push(stoi(v[i]));
  }
  cout<<st.top()<<endl;
  return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define ROOP(i, N) for(int i=0; i<N; i++)
#define RVROOP(i, N) for(int i=N; i>=0; i--)
#define INF 1e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main() {
  string S; cin>>S;
  int ans=0;
  for(int i=0; i<S.size(); i++){
    if(S.at(i)=='R' && i%2==1){
      ans=1;
      break;
    }
    if(S.at(i)=='L' && i%2==0){
      ans=1;
      break;
    }
  }
  if(ans==0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repd(i,a,b) for (int i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;
int main(void)
{
	int S, W;
	cin >> S >> W;
	if(S>W) cout << "safe" << endl;
	else cout << "unsafe" << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep1(i, s, n) for (int i = (s); i >= (n); i--)

typedef struct {
	char suit;
	int value;
} deck;

deck BS[36];
deck SS[36];

void BubbleSort(deck* C, int N)
{
	int tmp1, tmp2;

	rep(i, N) {
		rrep1(j, N - 1, i + 1) {
			if (C[j].value < C[j - 1].value) {
				tmp1 = C[j].value;
				tmp2 = C[j].suit;
				C[j].value = C[j - 1].value;
				C[j].suit = C[j - 1].suit;
				C[j - 1].value = tmp1;
				C[j - 1].suit = tmp2;
			}
		}
	}

	rep(i, N - 1) cout << C[i].suit << C[i].value << " ";
	cout << C[N - 1].suit << C[N - 1].value << endl;
	cout << "Stable" << endl;
}

void SelectionSort(deck* C, int N, deck* Compare)
{
	int tmp1, tmp2, mini;
	bool isStable = true;

	rep(i, N) {
		mini = i;
		rep1(j, i, N - 1) {
			if (C[j].value < C[mini].value) mini = j;
		}
		tmp1 = C[mini].value;
		tmp2 = C[mini].suit;
		C[mini].value = C[i].value;
		C[mini].suit = C[i].suit;
		C[i].value = tmp1;
		C[i].suit = tmp2;
	}

	rep(i, N - 1) cout << C[i].suit << C[i].value << " ";
	cout << C[N - 1].suit << C[N - 1].value << endl;

	rep(i, N) {
		if ((C[i].value != Compare[i].value)
			|| (C[i].suit != Compare[i].suit)){
			isStable = false;
			break;
		}
	}

	if (isStable) cout << "Stable" << endl;
	else cout << "Not stable" << endl;
}

int main()
{
	int N;

	cin >> N;
	rep(i, N) cin >> BS[i].suit >> BS[i].value;
	rep(i, N) {
		SS[i].suit = BS[i].suit;
		SS[i].value = BS[i].value;
	}

	BubbleSort(BS, N);
	SelectionSort(SS, N, BS);

	return 0;
}



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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n;

LL d(LL x) {
	LL l = 0;
	while(x) { x /= 10; l++; }
	return l;
}

int main() {
	cin >> n;
	
	LL ans = 13;
	inc1(i, 100000) {
		if(i * i > n) { break; }
		if(n % i == 0) { setmin(ans, max(d(i), d(n / i))); }
	}
	
	cout << ans << endl;
	
	return 0;
}


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;


int n;
ll a[maxn];
ll prefix[maxn], suffix[maxn];

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

  cin>>n;
  for (int i=0; i<n*3; i++) {
    cin>>a[i];
  }

  priority_queue<ll,vector<ll>,greater<ll>> pq;
  ll tot = 0;
  for (int i=0; i<n; i++) {
    tot += a[i];
    pq.push(a[i]);
    prefix[i] = tot;
  }

  for (int i=n; i<2*n; i++) {
    tot += a[i];
    pq.push(a[i]);
    tot -= pq.top();
    pq.pop();
    prefix[i] = tot;
  }

  while (pq.size()) pq.pop();
  tot = 0;

  
  for (int i=3*n-1; i>=2*n; i--) {
    tot -= a[i];
    pq.push(-a[i]);
    suffix[i] = tot;
  }
  

  
  for (int i=2*n-1; i>=n; i--) {
    tot -= a[i];
    pq.push(-a[i]);
    tot -= pq.top();
    pq.pop();
    suffix[i] = tot;
  }

  ll ans = -2e18;

  for (int i=n-1; i<2*n; i++) {
    ans = max(ans, prefix[i] + suffix[i+1]);
  }


  cout<<ans<<endl;
  return 0;
}
// don't forget to read in the input :^)


Measured memory_bytes: 12660
#include <stdio.h>

int main(void){

  char s[100000+1];
  scanf("%s", s);
  int alp_count[26];
  for (int i = 0; i < 26; i++) {
    alp_count[i] = 0;
  }
  for (int i = 0; i < 100000+1; i++) {
    if (s[i] < 'a' || s[i] > 'z') {
      break;
    }
    alp_count[s[i]-'a']++;
  }
  int flag = 0;
  for (int i = 0; i < 26; i++) {
    if (alp_count[i] == 0) {
      printf("%c\n", 'a'+i);
      flag = 1;
      break;
    }
  }
  if (flag == 0) {
    printf("None\n");
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
//#define f(i,a,n) for(ll i=a;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll isPrime(int n) 
{ 
	// Corner cases 
	if (n <= 1) 
		return 1; 
	if (n <= 3) 
		return 2; 

	// This is checked so that we can skip 
	// middle five numbers in below loop 
	if (n % 2 == 0 || n % 3 == 0) 
		return 1; 

	for (int i = 5; i * i <= n; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return 1; 

	return 2; 
} 

 
int main() 
{
    fast;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n,k=0;
        cin>>n;
        ll A[n],B[9]={0};
        for(ll i=0;i<n;i++)
        {
            cin>>A[i];
            if(A[i]>=1 && A[i]<=399)
            {
                B[0]++;
            }
            if(A[i]>=400 && A[i]<=799)
            {
                B[1]++;
            }
            if(A[i]>=800 && A[i]<=1199)
            {
                B[2]++;
            }
            if(A[i]>=1200 && A[i]<=1599)
            {
                B[3]++;
            }
            if(A[i]>=1600 && A[i]<=1999)
            {
                B[4]++;
            }
            if(A[i]>=2000 && A[i]<=2399)
            {
                B[5]++;
            }
            if(A[i]>=2400 && A[i]<=2799)
            {
                B[6]++;
            }
            if(A[i]>=2800 && A[i]<=3199)
            {
                B[7]++;
            }
            if(A[i]>=3200)
            {
                B[8]++;
            }
        }
        for(ll i=0;i<8;i++)
        {
            if(B[i]>0)
            k++;
        }
        if(k==0)
        cout<<k+1<<" "<<k+B[8];
        else
        cout<<k<<" "<<k+B[8];
    }    
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

int main(){
    ll N;
    cin >> N;
    vector<ll> a(N), S(1e5+1);
    map<ll,ll> mp;
    rep(i,N){
        cin >> a[i];
        mp[a[i]]++;
    }
    rep(i,1e5){
        S[i+1] = mp[i] + S[i];
    }
    ll M = -1;
    ll tmp = -1;
    for(ll i=1; i<1e5-1;i++){
        if(M < S[i+2] - S[i-1]){
            M = S[i+2] - S[i-1];
            tmp = i;
        }
    }
    
    cout << M << endl;
}


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

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  ll d = c-a-b;
  if(d>0&&d*d>4*a*b) cout << "Yes";
  else cout << "No";
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

h, w = il()
s = ils(h, "list(input())")
for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == "#":
            continue
        for k, l in zip([-1, -1, -1, 0, 1, 1, 1, 0], [-1, 0, 1, 1, 1, 0, -1, -1]):
            if 0 <= i+k < h and 0 <= j+l < w:
                if s[i + k][j + l] == "#":
                    cnt += 1
        s[i][j] = cnt
for i in s:
    for j in i:
        print(j, end="")
    print("")

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    string s; cin >> s;

    int n = s.size();
    V<int> ans(n);

    for(int i = 0; i < 2; i++){
        {
            int cnt = 0;
            for(int j = 0; j < n; j++){
                if(s[j] == 'R') cnt++;
                else{
                    ans[j] += cnt / 2;
                    ans[j - 1] += (cnt + 1) / 2;
                    cnt = 0;
                }
            }
        }
        reverse(ALL(ans));
        reverse(ALL(s));
        for(int j = 0; j < n; j++){
            if(s[j] == 'L') s[j] = 'R';
            else s[j] = 'L';
        }
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3824
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const ll MOD=1e9 + 7 ;
const ll dx[4] = { -1,1,0,0 };
const ll dy[4] = { 0,0,-1,1 };
const ll MAX =  3e5 ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
long long gcd(long long  a, long long  b) { return (b == 0 ? a : gcd(b, a % b)); }
ll n , m  , k , Q , l , x , y, ans; string s;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
   // freopen("test.in","r",stdin);
    ll A,B;
    cin>>n>>A>>B;
    ll a = 0 , b = 0 , c = 0;
    for(int i = 0 ; i < n ; ++i){
        cin>>x;
        if(x <= A) a++;
        if(x > A && x <= B) b ++;
        if(x > B) c++;

    }

    cout<<min({a,b,c})<<'\n';


    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define gc c = getchar()
int read(){
	int x = 0, f = 1; char gc;
	for(; !isdigit(c); gc) if(c == '-') f = -1;
	for(; isdigit(c); gc) x = x * 10 + c - '0';
	return x * f;
}
#undef gc
const int MAXN = 1e5 + 5;
struct Data {
	int x, id;
	bool operator<(const Data &b) const {
		if(x != b.x) return x > b.x;
		return id < b.id;
	}
} a[MAXN];
long long ans[MAXN];
int main(){
	int n = read();
	for(int i = 1; i <= n; i++) a[i].x = read(), a[i].id = i;
	sort(a + 1, a + n + 1);
	int j = 1;
	for(int i = 2; i <= n; i++) {
		while(a[i].x == a[i - 1].x) i++;
		ans[a[j].id] += 1LL * (a[j].x - a[i].x) * (i - 1);
		if(a[j].id < a[i].id) a[j].x = a[i].x;
		else j = i;
	}
	ans[a[j].id] += 1LL * a[j].x * n;
	for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}


Measured memory_bytes: 2688
import bisect
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = list(range(0,M+1))
for x in C:
    A,B = x[0],x[1]
    ind = bisect.bisect_right(hist,M-A)
    if ind>0:
        hist.pop(ind-1)
        rev += B
print(rev)

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

int main() {
    int a, b, W;
    std::cin >> W >> a >> b;

    if (a <= b) {
        if (b <= (a + W)) {
            std::cout << 0 << std::endl;
        } else {
            std::cout << (b - (a + W)) << std::endl;
        }
    } else {
         if (a <= (b + W)) {
            std::cout << 0 << std::endl;
        } else {
            std::cout << (a - (b + W)) << std::endl;
        }
    }

    return 0;
}


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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

const int mod = 1000000007;
struct mint {
    long long x;
    mint(long long x = 0) : x((x % mod + mod) % mod) {}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

int main() {
    int N;
    cin >> N;
    string S1, S2;
    cin >> S1 >> S2;

    vector<int> patturns(0);

    for (int i = 0; i < N; i++) {
        if (S1[i] != S2[i]) {
            patturns.push_back(0);
            i++;
        } else {
            patturns.push_back(1);
        }
    }
    dump(patturns);

    mint ans(1);
    for (int i = 0; i < patturns.size(); i++) {
        if (i == 0) {
            if (patturns[i] == 0) {
                ans *= 6;
            } else {
                ans *= 3;
            }
        } else {
            if (patturns[i - 1] == 0 && patturns[i] == 0) { ans *= 3; }
            if (patturns[i - 1] == 0 && patturns[i] == 1) { ans *= 1; }
            if (patturns[i - 1] == 1 && patturns[i] == 0) { ans *= 2; }
            if (patturns[i - 1] == 1 && patturns[i] == 1) { ans *= 2; }
        }
    }

    cout << ans.x << endl;

    return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
#include<cstring>
char s[200005];

int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    for(int i = 1; i <= n; i++){ 
        if(s[i]=='?') printf("D");
        else printf("%c",s[i]);
    }
    printf("\n");    
    return 0;
}


Measured memory_bytes: 1832
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
 	public static void main (String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[][] comb = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
		    for (int j = 0; j <= i; j++) {
		        if (j == 0 || j == i) {
		            comb[i][j] = 1;
		        } else {
		            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
		        }
		    }
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= k; i++) {
		    long tmp = ((long)comb[k - 1][i - 1] * (long)comb[n - k + 1][i]) % MOD;
		    sb.append(tmp).append("\n");
		}
		System.out.print(sb);
	}
}


Measured memory_bytes: 52436
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class E
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = Scanner.Scan<int>();
            var A = Scanner.ScanEnumerable<int>().ToArray();
            // j - i == Ai + Aj
            // i + Ai == j - Aj
            var answer = 0L;
            var B = new int[N];
            for (var i = 0; i < N; i++)
            {
                var r = i + A[i];
                var l = i - A[i];
                if (l >= 0) answer += B[l];
                if (r < N) B[r]++;
            }
            Console.WriteLine(answer);

        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
            public static IEnumerable<T> ScanEnumerable<T>() => Console.ReadLine().Trim().Split(" ").Select(x => (T)Convert.ChangeType(x, typeof(T)));
        }
    }
}


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

using namespace std;

/*-------------------------------*/
#define FOR(i, a, b) for(int i = (a); i < (b); i++)  //a~(b - 1)?????§
#define print(i) cout << i << endl //?°??????????Python?????????

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
/*-------------------------------*/

int main(void)
{
  int a;
  int da[3];
  cin >> a;

  FOR(i, 0, a){
    cin >> da[0] >> da[1] >> da[2];
    sort(da, da + 3);
    if (da[0] * da[0] + da[1] * da[1] == da[2] * da[2]) print("YES");
    else print("NO");
  }

  return 0;
}

Measured memory_bytes: 1168
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String s = sc.next();
		String c = sc.next();
		System.out.println("A" +s.charAt(0) + "C");
		sc.close();
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 25044
program main
	implicit none
	character(1) :: b
	read(*, *) b
	if(b == 'A') then
		write(*, *) 'T'
	else if(b == 'T') then
		write(*, *) 'A'
	else if(b == 'C') then
		write(*, *) 'G'
	else
		write(*, *) 'C'
	end if
end program main

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define intMax 2147483647
#define longMax 9223372036854775807
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>
#define vii vector<pair<int,int>>
#define ii pair<int, int>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repp(i, a, b) for (int i = a; i >= b; i--)
#define be(x) x.begin(), x.end()
#define rbe(x) x.rbegin(), x.rend()
#define pb push_back
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string a,b;
    cin>>a>>b;
    int x=a.size();
    int z=0;
    rep(i,0,x){
        if (a[i]==b[i]){
            z++;
        }
    }   
    cout<<z;
}

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


int main(){
  int N;
  cin >> N;
  int M = N;
  int sum=0;
  while(M){
    sum += M%10;
    M /= 10;
  }
  cout << (N%sum==0 ? "Yes" : "No") << endl;
}

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

using namespace std;

int main(){

  string s1,s2;
  
  cin >> s1 >> s2;

  if( s1.size() == s2.size()){
    for( int i = 0; i < s1.size(); ++i){
      cout << s1[i] << s2[i];
    }
    cout << endl;
  }else if( s1.size() > s2.size()){
    for( int i = 0; i < s2.size(); ++i){
      cout << s1[i] << s2[i];
    }
    cout << s1[s1.size()-1] << endl;
  }else{
    for( int i = 0; i < s1.size(); ++i){
      cout << s1[i] << s2[i];
    }
    cout << s2[s2.size()];
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define fort(i,n) for (int i = 1; i <= n; ++i)
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define sz size()
#define er erase
#define fr first
#define sc second
#define rc(x) return cout << x, 0
using namespace std;

int n,k,h[100005],dp[100005];

int32_t main()
{
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> k;
    fort (i,n)
    {
        cin >> h[i];
        dp[i]=1000000001;
    }
    dp[1]=0, dp[2]=abs(h[1]-h[2]);
    for (int i = 3; i <= n; ++i)
        fort (j,k)
            if (j<i) dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i]);
    cout << dp[n];
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[] x = new int[m];
		for(int i=0;i<m;i++) {
			x[i] = in.nextInt();
		}
		if(n>=m) System.out.println(0);
		else {
			Arrays.sort(x);
			int[] dif = new int[m-1];
			for(int i=0;i<m-1;i++) {
				dif[i] = x[i+1] - x[i];
			}
			Arrays.sort(dif);
			int ans = 0;
			for(int i=0;i<m-n;i++) {
				ans += dif[i];
			}
			System.out.println(ans);
		}
		in.close();

	}

}


Measured memory_bytes: 48380
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,count=0;
  string s;
  cin>>n>>s;
  for(int i=0;i<n-2;i++){
    if(s[i]!='A')continue;
    if(s[i+1]!='B')continue;
    if(s[i+2]!='C')continue;
    count++;
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<string>
#include<iostream>
#include<set>
using namespace std;
 
set<string> data;
char *ans[1000000];
int cor = 0;
 
int main(){
    int n;
    string A,B;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> A >> B;
        if(A == "insert"){
            data.insert(B);
        }
        else if(A == "find"){
            if(data.find(B) == data.end())
                ans[cor] = "no";
            else
                ans[cor] = "yes";
            cor++;
        }
    }
    for(int i = 0;i < cor;i++)
        cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 35972
import java.util.*;
import java.lang.Math;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int K = in.nextInt();
		long num = 0;
		
		Deque<Long> lunlun = new ArrayDeque<Long>(9);
		
		for(long i = 1; i <=9; i++) {
			lunlun.add(i);
		}
			
		for(long i = 0; i < K; i++) {
			num = lunlun.pollFirst();
			
			if (num%10 != 0) {
				lunlun.add((num*10) + (num%10) - 1);
			}
			
			lunlun.add((num*10) + (num%10));
			
			if (num%10 != 9) {
				lunlun.add((num*10) + (num%10) + 1);
			}
		}
		System.out.println(num);
		
	}
}


Measured memory_bytes: 29908
import sys
sys.setrecursionlimit(10**6)
def solve(a,lvl,prev,dp):
    if (prev,lvl) in dp: return dp[(prev,lvl)]
    if lvl==len(a)-1:
        if prev==0: return max(a[-1][1],a[-1][2])
        if prev==1: return max(a[-1][0],a[-1][2])
        if prev==2: return max(a[-1][0],a[-1][1])
    if prev==-1:
        p=a[0][0]+solve(a,lvl+1,0,dp)
        q=a[0][1]+solve(a,lvl+1,1,dp)
        r=a[0][2]+solve(a,lvl+1,2,dp)
        return max(p,q,r)
    dp[(prev,lvl)]=max(a[lvl][(prev+1)%3]+solve(a,lvl+1,(prev+1)%3,dp),a[lvl][(prev-1)%3]+solve(a,lvl+1,(prev-1)%3,dp))
    return dp[(prev,lvl)]
if __name__=='__main__':
    n=int(input())
    a=[]
    for i in range(n):
        a.append([int(i) for i in input().split()])
    if n==1:
        print(max(a[0]))
    else:
        print(solve(a,0,-1,{}))

Measured memory_bytes: 138860
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector< PII >
#define VVI vector< VI >
#define MP make_pair
#define PB push_back
#define F first
#define S second
const int INF=1e9;
const int MOD=1e9+7;
// >.<
int n,a[100000],dist[100000];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        a[i]--;
    }
    queue<int> q;
    q.push(0);
    memset((dist),-1,sizeof(dist));
    dist[0]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        int v=a[u];
        if(dist[v]==-1){
            dist[v]=dist[u]+1;
            q.push(v);
        }
    }
    printf("%d\n",dist[1]);
    return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int64_t> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    int64_t ans = 0;
    for (int i = n - 1; 0 <= i; --i) {
        int64_t mod = (a[i] + ans) % b[i];
        if (mod) {
            ans += b[i] - mod;
        }

        /*if (a[i] + ans <= b[i]) {
            ans += b[i] - (a[i] + ans);
        }
        else {
            auto mod = (a[i] + ans) % b[i];
            if (mod) ans += b[i] - mod;
        }*/
    }

    cout << ans << endl;
}



Measured memory_bytes: 4780
#define George_Plover
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 111000
#define LL long long
#define INF (-1)
using namespace std;
int n,m;
char s[MAXN];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    int sum=1;
    for(int i=0;s[i];i++)
    {
        if(i&&s[i]!=s[i-1])
        {
            sum++;
        }
    }
    sum=max(1,sum-2*m);
    cout<<n-sum<<endl;
    
    return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 200005

enum Type{
	X,
	Y,
};

struct Info{
	int loc,command;
	ll diff;
};

int N = 1;
ll uniformity[8*NUM][2],partial[8*NUM][2];
Info info[NUM];


void init(int first_N){
	while(N < first_N)N *= 2;
}

void add_and_updateNodes(int left,int right,ll value,int node_id,int node_left,int node_right,Type type){

	if(right < node_left || left > node_right)return;
	else if(left <= node_left && right >= node_right){
		uniformity[node_id][type] += value;
	}else{
		partial[node_id][type] += (min(right,node_right)-max(left,node_left)+1)*value;
		add_and_updateNodes(left,right,value,2*node_id+1,node_left,(node_left+node_right)/2,type);
		add_and_updateNodes(left,right,value,2*node_id+2,(node_left+node_right)/2+1,node_right,type);
	}
}

ll getSum(int left,int right,int node_id,int node_left,int node_right,Type type){
	if(right < node_left || left > node_right)return 0;
	else if(left <= node_left && right >= node_right){
		return (node_right-node_left+1)*uniformity[node_id][type]+partial[node_id][type];

	}else{
		ll sum = (min(right,node_right)-max(left,node_left)+1)*uniformity[node_id][type];
		sum += getSum(left,right,2*node_id+1,node_left,(node_left+node_right)/2,type);
		sum += getSum(left,right,2*node_id+2,(node_left+node_right)/2+1,node_right,type);
		return sum;
	}
}

int main(){

	int first_N,Q;
	scanf("%d %d",&first_N,&Q);

	init(first_N);

	for(int i = 0; i <= 2*N-2; i++){

		uniformity[i][X] = 0;
		uniformity[i][Y] = 0;

		partial[i][X] = 0;
		partial[i][Y] = 0;
	}

	for(int i = 0; i < Q; i++){

		scanf("%d %d %lld",&info[i].loc,&info[i].command,&info[i].diff);
	}

	ll L,R,mid,limit;

	for(int i = Q-1; i >= 0; i--){

		if(info[i].command == 1){

			L = 0, R = first_N-1, mid = (L+R)/2;
			limit = N;

			while(L <=R){

				if(mid+getSum(mid,mid,0,0,N-1,X) >= info[i].loc){

					limit = mid;
					R = mid-1;

				}else{

					L = mid+1;
				}
				mid = (L+R)/2;
			}

			add_and_updateNodes(0,limit-1,-2*info[i].diff,0,0,N-1,Y);

		}else{

			L = 0, R = first_N-1, mid = (L+R)/2;
			limit = -1;

			while(L <=R){

				if(mid+getSum(mid,mid,0,0,N-1,Y) < info[i].loc){

					limit = mid;
					L = mid+1;

				}else{

					R = mid-1;
				}
				mid = (L+R)/2;
			}

			add_and_updateNodes(limit+1,N-1,2*info[i].diff,0,0,N-1,X);

		}
	}

	for(int i = 0; i < first_N; i++){

		printf("%lld\n",(getSum(i,i,0,0,N-1,X)-getSum(i,i,0,0,N-1,Y))/2);
	}

	return 0;
}




Measured memory_bytes: 22732
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
    int N;cin>>N;
    vector<ll> p(N),pos(N+1);
    rep(i,N) {
        cin>>p[i];
        pos[p[i]] = i+1;
    }

    ll ans = 0;
    multiset<ll> ms;
    ms.insert(0);
    ms.insert(0);
    ms.insert(N+1);
    ms.insert(N+1);

    for(int i = N;i>=1;i--) {
        auto it = ms.lower_bound(pos[i]);
        ll r1 = *it;
        it++;
        ll r2 = *it;
        it--;
        it--;
        ll l1 = *it;
        it--;
        ll l2 = *it;
        ans += (l1-l2)*(r1-pos[i])*i;
        ans += (pos[i]-l1)*(r2-r1)*i;
        ms.insert(pos[i]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 9420
#include <cstdio>
#include <iostream>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node {int p,l,r;};
struct Node T[MAX];
int n;

void preParse(int u){
    if (u==NIL)return;
    cout << " "<< u;
    preParse(T[u].l);
    preParse(T[u].r);
}

void inParse(int u){
    if (u==NIL)return;
    inParse(T[u].l);
    cout <<" "<< u;
    inParse(T[u].r);
}

void postParse(int u){
     if (u==NIL)return;
    postParse(T[u].l);
    postParse(T[u].r);
    cout <<" "<<u;
}

int main(){
   int i,v,l,r,root;
   
   cin >> n;
   for(i=0; i<n; i++){
       T[i].p=NIL;
   }
   
   for(i=0; i<n; i++){
       cin >> v >> l >> r;
       T[v].l=l;
       T[v].r=r;
       if(l != NIL) T[l].p=v;
       if(r != NIL) T[r].p=v;
   }
   
   for (i=0; i<n; i++) if (T[i].p == NIL) root = i;
   
   cout <<"Preorder"<< endl;
   preParse(root);
   cout << endl;
   cout <<"Inorder"<< endl;
   inParse(root);
   cout << endl;
   cout <<"Postorder"<< endl;
   postParse(root);
   cout << endl;
   
   return 0;
}


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

const int N = 220000;

int a[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] -= i;
	}
	sort(a + 1, a + n + 1);
	int cnt = (n + 1) / 2;
	long long tot = 0;
	for (int i = 1; i <= n; i++) {
		tot += abs(a[i] - a[cnt]);
	}
	cout << tot << endl;
	return 0;
}



Measured memory_bytes: 1024
n, m, d = map(int, input().split())
if d == 0: print('{:.10f}'.format((m - 1) / n))
else:
    t = n * (n - 1) // 2
    print('{:.10f}'.format((m - 1) * (n - 1) * (n - d) / (t * n)))


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

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589
#define MOD 1000000007

using namespace std;

template<typename T> T gcd(T a, T b){return (a % b)? gcd(b, a % b) : b;}
template<typename T> T lcm(T a, T b){return a * b / gcd(a, b);}

int main(void){
    int n, k;
    cin >> n >> k;
    int h[n];
    REP(i,n) cin >> h[i];

    vector<int> dp(n+k+5, 1000000000);
    dp[0] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 1; j <= k; j++){
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]));
        }
    }

    cout << dp[n-1] << endl;
    
    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 5;
const int mod = 1000000007;

inline int add( int a, int b ) {
	return a + b >= mod ? a + b - mod : a + b;
}
inline int sub( int a, int b ) {
	return a - b < 0 ? a - b + mod : a - b;
}
inline int mul( int64_t a, int64_t b ) {
	return ( int )( a * b % mod );
}

int comb[ N ];
int dp[ N ][ N ], sz[ N ];
vector< int > G[ N ];
void dfs( int, int );

int main() {
	ios_base::sync_with_stdio( false );
	cin.tie( nullptr );
	int n; cin >> n;
	for ( int i = 1 ; i < n ; ++ i ) {
		int u, v; cin >> u >> v;
		G[ u ].push_back( v );
		G[ v ].push_back( u );
	}
	comb[ 2 ] = 1;
	for ( int i = 4 ; i <= n ; ++ i )
		comb[ i ] = mul( comb[ i - 2 ], i - 1 );
	dfs( 1, 1 );
	cout << sub( 0, dp[ 1 ][ 0 ] ) << '\n';
	return 0;
}

void dfs( int u, int f ) {
	dp[ u ][ 1 ] = sz[ u ] = 1;
	for ( int v : G[ u ] ) if ( v != f ) {
		dfs( v, u );
		for ( int i = 1 ; i <= sz[ u ] + sz[ v ] ; ++ i )
			dp[ 0 ][ i ] = 0;
		for ( int i = 1 ; i <= sz[ u ] ; ++ i )
			for ( int j = 0 ; j <= sz[ v ] ; ++ j )
				dp[ 0 ][ i + j ] = add( dp[ 0 ][ i + j ], mul( dp[ u ][ i ], dp[ v ][ j ] ) );
		for ( int i = 1 ; i <= sz[ u ] + sz[ v ] ; ++ i )
			dp[ u ][ i ] = dp[ 0 ][ i ];
		sz[ u ] += sz[ v ];
	}
	for ( int i = 2 ; i <= sz[ u ] ; i += 2 )
		dp[ u ][ 0 ] = sub( dp[ u ][ 0 ], mul( dp[ u ][ i ], comb[ i ] ) );
}

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

int main(){
    long int N;
    cin>>N;
    vector<long int> A(N),B(1000001,0);
    rep(i,N) cin>>A[i];
    sort(A.begin(),A.end());
    rep(i,N){
        long int n=A[i]*2;
        if (B[A[i]]==0){
            while(n<=1000000){
                B[n]=1;
                n+=A[i];
            }
        }
        if (i!=N-1){
            if (A[i]==A[i+1]){
                B[A[i]]=1;
            }
        }
    }
    long int ans=0;
    rep(i,N){
        if (B[A[i]]==0) ans++;
    }

    cout<<ans<<endl;;

    return 0;
}

Measured memory_bytes: 12752
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
typedef pair<int, int> P;

signed main(){
    int n;
    cin >> n;
    int ans = 0, m = 1;
    for(ans = 1;; ans++){
        m *= 3;
        if(m >= n) break;
    }
    cout << ans << endl;
}

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

#define ll long long 
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define in insert
#define pii pair<int, int>
#define pll pair<ll, ll>
#define N int(1e5) + 5
#define T int(1e4) + 55
#define H int(1e3) + 55
#define mp make_pair

using namespace std;

string  w;
ll n, sum, num, sam, nam, q[N];

int main() {
	cin >> n ;
	for(int i = 0;i < n; ++ i) {
	 	cin >> q[i];
	}
	for(int i = 0;i < n; ++ i) {
		if(q[i] == q[i + 1]) {
		 	sum ++;
     	}
     	else {
     	    num += (sum + 1) / 2;
     	    sum = 0;
     	}	
	}
	num += (sum + 1) / 2;
	cout << num ;
	return 0;
}

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

using lint = long long;

lint n, s;
lint dp[1001][101][11];

lint dfs(int sum = 0, int num = 0, int cnt = 0) {
  if (cnt == n) return sum == s;
  if (num > 100 || sum > s) return 0;

  lint &ret = dp[sum][num][cnt];
  if (~ret) return ret;

  ret = dfs(sum, num + 1, cnt) + dfs(sum + num, num + 1, cnt + 1);

  return ret;
}

int main() {
  while (cin >> n >> s, n + s) {
    memset(dp, -1, sizeof(dp));
    cout << dfs() << endl;
  }
}

Measured memory_bytes: 11776
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int l = 0;
        int total = 0;
        int count = 1;
        for (int i = 0; i < n; i++) {
            l = sc.nextInt();
            total += l;
            if(total <= x) {
                count++;
            }
        }
        System.out.println(count);
    }
}

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

typedef pair<int, int> II;
typedef vector< II > VII;
typedef vector<int> VI;

#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ll long long
#define fr(i,n) for(i=0;i<n;i++)


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int a,b,i,len;
    string s;
    cin>>a>>b>>s;
    len=SZ(s);
    if(len!=a+b+1)
        cout<<"No\n";
    else
    {
        for(i=0;i<a;i++)
            if(s[i]<48 || s[i]>'9')
                break;
        if(i<a)
            cout<<"No\n";
        else
        {
            if(s[i]=='-')
            {
                for(i=i+1;i<len;i++)
                    if(s[i]<48 || s[i]>'9')
                        break;
                if(i<len)
                    cout<<"No\n";
                else
                    cout<<"Yes\n";
            }
            else
            {
                cout<<"No\n";
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
MOD=998244353
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def ma():
    return map(int,input().split())
def main():
    n,m,k=ma()
    
    ans=0
    for j in range(k+1):
        ans+=m*comb(n-1,j)%MOD *pow(m-1,(n-1-j),MOD)
        ans%=MOD
    print(ans)

main() 

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define trav(a, b) for(auto a : b)

int n, m;
const int maxn = 105;
int a[maxn][maxn];
int b[maxn][maxn], c[maxn][maxn];
bool vis[maxn][maxn];
int col[maxn][maxn];

bool find(int j, vector<vi>& g, vi& btoa, vi& vis) {
	if (btoa[j] == -1) return 1;
	vis[j] = 1; int di = btoa[j];
	trav(e, g[di])
		if (!vis[e] && find(e, g, btoa, vis)) {
			btoa[e] = di;
			return 1;
		}
	return 0;
}
int dfsMatching(vector<vi>& g, vi& btoa) {
	vi vis;
	rep(i,0,sz(g)) {
		vis.assign(sz(btoa), 0);
		trav(j,g[i])
			if (find(j, g, btoa, vis)) {
				btoa[j] = i;
				break;
			}
	}
	return sz(btoa) - (int)count(all(btoa), -1);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> a[i][j];
            a[i][j]--;
            col[i][j] = a[i][j] / m; 
        }
    }
    for(int iter = 0;iter < m;iter++){
        vector<vi> g(0);
        for(int i = 0;i < n;i++){
            vi tmp(0);
            for(int j = 0;j < m;j++){
                if(!vis[i][j]){
                    tmp.push_back(col[i][j]);
                } 
            }
            sort(all(tmp));
            auto it = unique(all(tmp));
            tmp.erase(it, tmp.end());
            g.push_back(tmp);
        }
        vi btoa(n, -1);
        dfsMatching(g, btoa);
        for(int i = 0;i < n;i++){
            int r = btoa[i];
            for(int j = 0;j < m;j++){
                if(!vis[r][j] and col[r][j] == i){
                    vis[r][j] = true;     
                    b[r][iter] = a[r][j];
                    break;
                }
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            col[i][j] = b[i][j] / m;
        }
    } 
    for(int j = 0;j < m;j++){
        for(int i = 0;i < n;i++){
            c[col[i][j]][j] = b[i][j];
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << b[i][j] + 1 << (j == m - 1 ? '\n' : ' ');
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << c[i][j] + 1 << (j == m - 1 ? '\n' : ' ');
        }
    }
    return 0;
}


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

using namespace std;

int main(void) {
	int N;
	int ans;
	int count0 = 0;
	int count1 = 0;
	string S;
	cin >> S;
	N = S.size();
	for (int i = 0; i < N; i++) {
		if (S[i] == '0') {
			count0++;
		}
		else {
			count1++;
		}
	}
	ans = 2 * min(count0, count1);
	cout << ans;
}

Measured memory_bytes: 512