akhauriyash/Code-Regression huggingface dataset:
# 2019-11-15 00:35:39(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def nCr(n, r):
    r = min(r, n - r)
    upper = reduce(op.mul, range(n, n-r, -1), 1)
    lower = reduce(op.mul, range(r, 0, -1), 1)
    return upper // lower

mod = 10 ** 9 + 7

def main():
    n, k = [int(x) for x in sys.stdin.readline().split()]

    for i in range(1, k+1):
        if i <= n - k + 1:
            print(nCr(n-k+1, i) * nCr(k-1, i-1) % mod)
        else:
            print(0) # i > n - k + 1 となる並べ方は存在しない

if __name__ == "__main__":
    main() 


Measured memory_bytes: 3940
a, b, c, d = map(int, input().split())
if abs(a-b) <abs(a-c):
  if abs(a-b)<=d and abs(b-c)<=d:
    print('Yes')
  else:
    print('No')
else:
  if abs(a-c)<= d:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

N,M = map(int,input().split())
S = input()
T = input()
g = gcd(N,M)
N1 = N//g
M1 = M//g

bl = True
for i,s in enumerate(S[::N1]):
    if s != T[M1*i]:
        bl = False
        break

answer = N * M1 if bl else -1
print(answer)

Measured memory_bytes: 3316
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  int N; cin >> N;
  vector <int> Graph[N];
  for (int i = 0; i < N - 1; i++){
    int A, B; cin >> A >> B;
    A--; B--;
    Graph[A].push_back(B);
    Graph[B].push_back(A);
  }
  
  vector <int> Dist(N);
  fill(Dist.begin(), Dist.end(), -1);
  queue <int> que; que.push(0);
  Dist[0] = 0;

  while (!que.empty()){
    int Q = que.front(); que.pop();
    for (int i = 0; i < Graph[Q].size(); i++){
      int next = Graph[Q][i];
      if (Dist[next] == -1){
        Dist[next] = Dist[Q] + 1;
        que.push(next);
      }
    }
  }

  int cnt0 = 0, cnt1 = 0;
  for (int i = 0; i < N; i++){
    if (Dist[i] % 2 == 0) cnt0++;
    else cnt1++;
  }
  
  vector <int> ans(N);
  int now1 = 1, now2 = 2, now3 = 3;
  vector <bool> Checked(N);
  if (cnt0 <= N / 3){
    for (int i = 0; i < N; i++){
      if (Dist[i] % 2 == 0){
        ans[i] = now3;
        Checked[now3 - 1] = true;
        now3 += 3;
      }
    }
  }else if (cnt1 <= N / 3){
    for (int i = 0; i < N; i++){
      if (Dist[i] % 2 == 1){
        ans[i] = now3;
        Checked[now3 - 1] = true;
        now3 += 3;
      }
    }
  }else{
    for (int i = 0; i < N; i++){
      if (Dist[i] % 2 == 0 && now1 <= N){
        ans[i] = now1;
        Checked[now1 - 1] = true;
        now1 += 3;
      }
      if (Dist[i] % 2 != 0 && now2 <= N){
        ans[i] = now2;
        Checked[now2 - 1] = true;
        now2 += 3;
      }
    }
  }
  
  int now = 0;
  for (int i = 0; i < N; i++){
    if (ans[i] == 0){
      for (int j = now; j < N; j++){
        if (Checked[j] == false){
          ans[i] = j + 1;
          Checked[j] = true;
          now = j;
          break;
        }
      }
    }
  }
  
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i < N - 1) cout << " ";
    else cout << endl;
  }
  
  return 0;
}


Measured memory_bytes: 15220
#include<iostream>
#include<vector>
#define INF 1e9+11

int main()
{
	int n, k;
	std::cin >> n >> k;

	std::vector<int>h;
	for(int i = 0; i < n; i++)
	{
		int value;
		std:: cin >> value;
		h.push_back(value);
	}

	std::vector<int>dp(n+1, INF);
	dp[0] = 0;
	for(int i = 1; i < n; i++)
	{
		for(int j = 1; j <= k; j++)
		{
			if(i - j < 0) continue;
			dp[i] = std::min(dp[i], dp[i-j] + abs(h[i]-h[i-j]));
		}

	}

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

Measured memory_bytes: 1144
import numpy as np

num = [] #５個の料理の必要時間
total = 0
mini = 10
b = 1
for i in range(5): #入力
    a = input()
    a = int(a)
    b = a % 10 #bにはaの１の桁が０になったものが入る
    total += a - b
    if b != 0:
        total+=10
        if b < mini:
            mini=b


if mini== 10:
    print(total)
else:
    print(total -(10-mini))

Measured memory_bytes: 18720
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
X = LI()
mod = 10**9+7
Y = [X[i+1]-X[i] for i in range(N-1)]

r = 1  # (N-1)!
for i in range(1,N):
    r *= i
    r %= mod

C = [r]  # Ci = (N-1)!*(1/1+1/2+…+1/i)
for i in range(2,N):
    C.append((C[-1]+r*pow(i,mod-2,mod)) % mod)

ans = 0
for y,c in zip(Y,C):
    ans += y*c
    ans %= mod

print(ans)


Measured memory_bytes: 89216
/******************************************************************************

                            Online C Compiler.
                Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <vector>
#include <stdio.h>

using namespace std;

int main()
{
    
    
    
    long int a, b, c,d, res[6], max;
    
    scanf("%ld%ld%ld%ld", &a, &b, &c, &d);
    
    res[0] = a*c;
    res[1] = b*c;
    res[2] = a*d;
    res[3] = b*d;
    
    max = res[0];
    
    for(int i=0; i<4; i++)
    
    {
        if(res[i] > max){
            max = res[i];
        }
        
    }
    printf("%ld", max);
    
    
    
    return 0;
}


Measured memory_bytes: 1732
N = int(input())
A = list(map(int,input().split()))

from itertools import combinations
ans = 0
for c in combinations(range(N),3):
    c1,c2,c3 =c
    if A[c1] != A[c2] and A[c1] != A[c3] and A[c2] != A[c3]:
        if A[c1]+A[c2] > A[c3] and A[c3]+A[c2] > A[c1] and A[c1]+A[c3] > A[c2]:
#             print(c1+1,c2+1,c3+1)
            ans+=1
            
print(ans)

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

int main(){
    int N;
    int a[3003];
    int sum=0;
  cin >> N;
    for(int i=0; i<N; i++){
        cin >> a[i];
        sum += a[i];
    }

cout << sum-N << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(kbrni,n)cout<<" "<<a[kbrni];cout<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define svecp(v) cout<<#v<<":";each(kbrni,v)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

vector<int> G[MAX_N];
vi a;

int dfs(int u,int p)
{
    vi vec;
    int nx = 0;
    each(v,G[u]){
        if(v != p){
            nx++;
            int res = dfs(v,u);
            if(res < 0){
                return -1;
            }else{
                vec.pb(res);
            }
        }
    }
    if(nx == 0){
        return a[u];
    }
    int sm = accumulate(all(vec),0);
    int mx = *max_element(all(vec));
    if(nx == 1){
        if(sm != a[u]){
            return -1;
        }else{
            if(u == 0){
                return 0;
            }else{
                return sm;
            }
        }
    }else{
        if(sm < a[u] || 2*a[u] < sm){
            return -1;
        }else{
            if(a[u] < mx){
                return -1;
            }else{
                return 2*a[u] - sm;
            }
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    a.resize(n);
    rep(i,n){
        cin >> a[i];
    }
    rep(i,n-1){
        int x,y;
        cin >> x >> y;
        --x,--y;
        G[x].pb(y),G[y].pb(x);
    }
    if(dfs(0,-1) == 0){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
    return 0;
}


Measured memory_bytes: 15488
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h,w; cin >> h >> w;
    char hw[h][w];
    rep(i,h) rep(j,w) cin >> hw[i][j];
    rep(i,h){
        rep(j,w){
            if(hw[i][j] == '#'){
                if(i > 0) if(hw[i-1][j] == '#') continue;
                if(i < h-1) if(hw[i+1][j] == '#') continue;
                if(j > 0) if(hw[i][j-1] == '#') continue;
                if(j < w-1) if(hw[i][j+1] == '#') continue;
                No;
                return 0;
            }
        }
    }
    Yes;

    return 0;
}

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

int n, t1, t2, q, u, v, par[100005], d[100005], f[100005][21];
vector <int> path[100005];

void dfs(int u, int p) {
	par[u] = p, d[u] = d[p] + 1;
	for (int i : path[u]) {
		dfs(i, u);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t1;
		for (int j = 0; j < t1; j++) {
			cin >> t2;
			path[i].push_back(t2);
		}
	}
	dfs(0, -1);
	for (int i = 0; i < n; i++) f[i][0] = par[i];
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			if (f[j][i - 1] != -1) f[j][i] = f[f[j][i - 1]][i - 1];
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> u >> v;
		if (d[u] < d[v]) swap(u, v);
		for (int j = 19; j >= 0; j--) {
			if (d[f[u][j]] >= d[v]) u = f[u][j];
		}
//		cout << u << ' ' << v << endl;
		if (u == v) {
			cout << u << endl;
			continue;
		}
		for (int j = 19; j >= 0; j--) {
			if (f[u][j] != f[v][j]) u = f[u][j], v = f[v][j];
		}
		cout << par[u] << endl;
	}
}



Measured memory_bytes: 20668
#include<stdio.h>
 
#define MAXLEN 20000
 
int garea,gareas[(MAXLEN/2)+1],gcnt;
 
 
void getArea( char *inputs, int start, int end )
{
    int i;
    int ravine,water;
    
    gareas[gcnt]=water=ravine=0;
    for( i=start; i<=end && '\0'!=*(inputs+i) ; i++ ) {
        if( '\\'== *(inputs+i) ) {
            water+=(ravine*2);
            ravine++;
            water++;
        } else if( 0 < ravine && '/' == *(inputs+i) ) {   
            ravine--;
            if( 0 == ravine ) {
                gareas[gcnt]+=water;
                garea+=gareas[gcnt];
                gcnt++;
                break;
            }           
        } else {
	     	gareas[gcnt]+=ravine;
        }       
    }
 
    return;
}
  
int checkRavine( char *inputs, int start )
{
    int i,j;
    int ravine;
    
    gareas[gcnt]=ravine=0;
    for( i=start, j=0; '\0'!=*(inputs+i) && j<MAXLEN; i++, j++ ) {
        if( '\\'== *(inputs+i) ) {
            ravine++;
        } else if( 0 < ravine && '/' == *(inputs+i) ) {   
            ravine--;
            if( 0 == ravine ) {
            	getArea( inputs, start, i );
                return j;
            }           
        }
    }
    return 0;
}
 
 
void getAreas( char *inputs )
{
    int i,next;
     
    next=0;
    for( i=0; '\0'!=inputs[i]; i++ ) {
        next=checkRavine( inputs, i );
        i+=next;
    }
 
    return;
}
 
int main( void ) 
{
    char inputs[MAXLEN+1];
    int i;
 
    scanf( "%s", inputs );
    garea=gcnt=0;
    getAreas( inputs );
     
    printf( "%d\n", garea );
    
    if( gcnt ) {
        printf( "%d ", gcnt );
        gcnt--;
        for( i=0; i<=gcnt; i++ ) {
            printf( "%d", gareas[i] );
            if( i < gcnt ) {
                printf( " " );  
            } else {
            	printf( "\n" ); 
            }
        }
    } else {
        printf( "0\n" );
    }
     
    return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <vector>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    if(a >= 13) cout << b << endl;
    else if(a <= 5) cout << 0 << endl;
    else cout << b/2 << endl;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define REREP(i,n) for(int i=int(n-1); i>=0; i--)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define REFOR(i,m,n) for(int i=int(n-1); i>=int(m); i--)
#define ALL(obj) (obj).begin(),(obj).end()
 
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VD vector<double>
#define VVD vector<vector<double>>
#define VVVD vector<vector<vector<double>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VVVL vector<vector<vector<ll>>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VVVB vector<vector<vector<bool>>>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVVS vector<vector<vector<string>>>
 
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define VPII vector<pair<int,int>>
#define VVPII vector<vector<pair<int,int>>>
#define VVVPII vector<vector<vector<pair<int,int>>>>
#define VPLL vector<pair<ll,ll>>
#define VVPLL vector<vector<pair<ll,ll>>>
#define VVVPLL vector<vector<vector<pair<ll,ll>>>>
 
#define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.)
#define SUML(obj) accumulate((obj).begin(), (obj).end(), 0LL)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

#define PB push_back
#define Cout(str) cout << str << endl

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const ll EPS = (ll)1e-8;

int main(){
	int n,m;
	int a,b,c,d;
	int sum;
	string str;
	string s,t;
	char ch;
	VI vi;
	vector<char> vc;
	VS vs;
	int reserve_vi = 100;
	map<int, int> table; 
	string str2, str3;
	map<char, string> vowel;
	vector<char> vowel_vec = {'a', 'e', 'i', 'o', 'u'};
	set<int> set_i;

	//cin >> n >> m;
	cin >> a >> b;
	//cin >> a >> b >> c;
	//cin >> a >> b >> c >> d;
	//cin >> str;
	//cin >> str >> str2 >> str3;
	//cin >> n;
	
	//cin >> s >> t;
	//cin >> ch;
	//cin >> a >> ch >> b;
	
	if(a == 2 || b == 2){
		Cout("No");
		return 0;
	}
	set_i.insert(4);
	set_i.insert(6);
	set_i.insert(9);
	set_i.insert(11);
	if(set_i.count(a) == set_i.count(b)) Cout("Yes");
	else Cout("No");

	//transform(ALL(str_toupper), str_toupper.begin(), ::toupper);

	//cout << accumulate(vi.begin(), vi.begin()+n, 0) << endl;
	//replace(ALL(str), ',', ' ');

	//swap(a, b);
	//vi.resize(N);
	//fill(vi.begin(), vi.end(), 1);
	//vi.reserve(reserve_vi);
	//vi.PB(n);

	//vc.resize(5);
	//vc[i] = (str[i]);

	//sort(vc.begin(), vc.end(), greater<char>());
	//sort(vc.begin(), vc.end());

	//for(auto itr = table.begin(); itr != table.end(); ++itr) {
	return 0;
}



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

#define MOD (1000 * 1000 * 1000 + 7)
#define INF (1LL << 60)
#define pb push_back
#define po pop_back
#define fi first
#define se second

typedef long long ll;
typedef long double ld;

int main() {
    vector<string> str(3);
    for(auto &i : str){
        cin >> i;
        cout << *i.begin();
    }
    cout << endl;
    
    return 0;
}

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

long long Move(int *A,int N,int remain){
    long long i,sum = 0,moveCount = 0;
    for (i=0;i<N;i++){
        if (i%2==remain){
            if (sum + A[i] > 0){
                sum += A[i];
            }else{
                moveCount+=  - sum - A[i] + 1;
                sum = 1;
            }
        }else{
            if (sum + A[i] < 0){
                sum += A[i];
            }else{
                moveCount += sum + A[i] + 1;
                sum = - 1;
            }
        }
    }
    return moveCount;
}

int main()
{
    // 整数の入力
    int N,i=0;
    cin >> N;
    int* A = new int[N];
    // スペース区切りの整数の入力
    for (i=0;i<N;i++){
        cin >> A[i];
    }

    cout << min(Move(A,N,0),Move(A,N,1)) << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n - 1; i++){
    if(a[i] == a[i+1]){
      cout << "NO\n";
      return 0;
    }else{
      continue;
    }
  }
  cout << "YES\n";
  return 0;
}

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

int main(){
    int64_t X;
    cin >> X;
    
    int64_t Y = 100;
    int64_t res = -1;
    for ( int64_t i = 1; i < 5000; ++i){
        int64_t Z = Y / 100;
        Y = Y + Z;
        if ( Y >= X ){
            res = i;
            break;
        }
    }
    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int next(int a, int L){
  string S = to_string(a);
  while (S.size() < L){
    S = '0' + S;
  }
  string S1 = S;
  sort(S1.begin(), S1.end());
  string S2 = S;
  sort(S2.rbegin(), S2.rend());
  return stoi(S2) - stoi(S1);
}
int main(){
  while (1){
    int a0, L;
    cin >> a0 >> L;
    if (a0 == 0 && L == 0){
      break;
    }
    set<pair<int, int>> st;
    st.insert(make_pair(a0, 0));
    int a = a0;
    int n = 0;
    while (1){
      n++;
      int b = next(a, L);
      auto itr = st.lower_bound(make_pair(b, -1));
      if (itr != st.end()){
        if ((*itr).first == b){
          int i = n;
          int j = (*itr).second;
          cout << j << ' ' << b << ' ' << i - j << endl;
          break;
        }
      }
      st.insert(make_pair(b, n));
      swap(a, b);
    }
  }
}


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

const int nil = -1;

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

void print(int u) {
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";

    if (T[u].p == nil) cout << "root, ";
    else if (T[u].l == nil) cout << "leaf, ";
    else cout << "internal node, ";

    cout << "[";

    for (int i = 0, c = T[u].l; c != nil; i++, c = T[c].r) {
        if (i) cout << ", ";
        cout << c;
    }
    cout << "]" << endl;
}

void rec(int u, int p) {
    D[u] = p;
    if (T[u].r != nil) rec(T[u].r, p);
    if (T[u].l != nil) rec(T[u].l, p + 1);
}

int main(void) {
    int v, d, c, l, r;
    cin >> n;
    for (int i = 0; i < n; i++) T[i].p = T[i].l = T[i].r = nil;

    for (int i = 0; i < n; i++) {
        cin >> v >> d;
        for (int j = 0; j < d; j++) {
            cin >> c;
            if (j == 0) T[v].l = c;
            else T[l].r = c;
            l = c;
            T[c].p = v;
        }
    }

    for (int i = 0; i < n; i++) {
        if (T[i].p == nil) r = i;
    }

    rec(r, 0);

    for (int i = 0; i < n; i++) print(i);

    return 0;
}

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

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

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

  int q;
  cin >> q;
  VI a(q), b(q);
  REP(i, q) {
    cin >> a[i] >> b[i];
    if(a[i] > b[i]) swap(a[i], b[i]);
  }

  REP(i, q) {
    // [lb, ub)
    int lb = 0, ub = b[i]-a[i]+1;
    auto check = [&](int mid) -> bool {
      for(int j=mid/2-2; j<=mid/2+2; ++j) {
        if(j<0 || b[i]-a[i]<j) continue;
        if((a[i]+j)*(a[i]+mid-j) >= a[i]*b[i]) return false;
      }
      return true;
    };
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    cout << a[i]*2-2 + lb << endl;
  }

  return 0;
}


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

struct flower{
    ll h; //height
    ll b; //beauty
};
// any element is inserted and deleted atmost once so time complexity is O(NlogN)
ll solve(vector<flower>& v,ll n){
	vector<ll> dp(n+1);
	dp[1]=v[1].b;
	map<ll,ll> meaningful; //to store meaningful indices which can extend further
	meaningful[v[1].h]=v[1].b;
	ll ans=dp[1];
	for(int i=2;i<=n;++i){
	    dp[i]=v[i].b; // first option
	    // 2nd option 
	    auto it=meaningful.upper_bound(v[i].h);
	    if(it!=meaningful.begin()){
	        it--;
	        dp[i]+=it->second;
	    }
	    meaningful[v[i].h]=dp[i]; //insert into map
	    //delete all unnecessary heights which cant be extended in the future
	    it=meaningful.upper_bound(v[i].h);
	    while(it!=meaningful.end() and it->second<=dp[i]){
	        auto temp=it;
	        temp++;
	        meaningful.erase(it);
	        it=temp;
	    }
	    ans=max(ans,dp[i]);
	}
	return ans;
}

int main()
{
	ll n=0;cin>>n;
    vector<flower> v(n+1);
    for(int i=1;i<=n;++i)
        cin>>v[i].h;
    for(int i=1;i<=n;++i)
        cin>>v[i].b;
    cout<<solve(v,n)<<'\n';
	return 0;
}

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ a>b?:a=b; }
template<class T> void chmin(T& a, T b){ a<b?:a=b; }

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), b(n), c(n), d(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    ll sum = 0, ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        sum += c.end() - upper_bound(all(c), b[i]);
        d[i] = sum;
    }
    for (int i = 0; i < n; ++i) {
        ans += d[upper_bound(all(b), a[i]) - b.begin()];
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		while (true) {
			boolean judge = true;
			for (int i = 2; i <= Math.sqrt(N); i++) {
				if (N % i == 0) {
					judge = false;
					break;
				}
			}
			if (judge) {
				break;
			}
			N++;
		}
		System.out.print(N);
	}
}

Measured memory_bytes: 21972
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
	int n,k,q;
	string s;
	cin>>n>>k>>q;
	vector <int> ac(q),pt(n);
    rep(i,q) cin>>ac[i];
    rep(i,q) pt[ac[i]-1]++;
    rep(j,n){
        if(pt[j]>q-k)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    int N;
    cin >> N;

    vector<char> ans;
    if (N == 0) {
        ans.push_back('0');
    } else {
        while (N != 0) {
            if (N % 2 != 0) {
                ans.push_back('1');
                --N;
            } else {
                ans.push_back('0');
            }
            N /= -2;
        }
    }

    for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
        cout << *it;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _USE_MATH_DEFINES
#include <math.h>
 
using namespace std;
 
using LL = long long;
using VLL = std::vector<LL>;
using VVLL = std::vector<VLL>;
using VVVLL = std::vector<VVLL>;
using LD = long double;
using VLD = std::vector<LD>;
using VVLD = std::vector<VLD>;
using VVVLD = std::vector<VVLD>;
 
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }

#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) {LL i=0; for(auto (a): v ){   cerr <<i << " : "<<  a << endl; i++;}}
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl
#define cmax(a,b) {if(a<b){a=b;}}
#define cmin(a,b) {if(a>b){a=b;}}
//#define cmax(a,b) a = (a>b ? a:b)
//#define cmin(a,b) a = (a<b ? a:b) 

struct To{
  LL to;
  LL id;
};

vector<vector<To>> to;
vector<LL> edge_color;
void dfs(LL v , LL p=-1, LL pColor = -1){
  //cerr <<setw(3)<<p  << "  -> " << setw(3)<< v <<setw(3)<< pColor << endl;
  LL color = 0;
  REP(i,to[v].size()){
    LL u = to[v][i].to;
    LL id = to[v][i].id;
    if(u==p){
      continue;
    }
    if(color==pColor){
      color++;  
    }
    edge_color[id]=color;
    //!  エッジに対する処理 A
    dfs(u,v,color);
    //!  エッジに対する処理 B
    color++;
  }
}


void func() {
  LL N;
  cin >> N;
  to.resize(N);
  edge_color.resize(N-1);
  REP(i,N-1){
    LL a,b;
    cin >>a;
    cin >>b;
    a--;
    b--;
    To t;
    t.to = b;
    t.id = i;
    
    to[a].push_back(t);
    t.to = a;
    to[b].push_back(t);
  }
  LL K=0;
  for(auto t: to){
    //PRINTSP(t);
    chmax(K,(LL)t.size());
  }
  
  dfs(0,-1,-1);
  cout << K << endl;
  for(auto ec : edge_color){
    cout << ec+1 << endl;
  }

  return;
}

 
int main()
{
  func();
  return 0;
}
 

Measured memory_bytes: 9728
n = int(input())
a = [int(i) for i in input().split()]
#n = (10**5)*2
#n = 10
#a = [int(10**9)]*n
mod = (10**9)+7
ans = 0
c = [0]*n
c[n-1] = a[n-1]
for i in range(n-1,1,-1) :
    c[i-1] = c[i]+a[i-1]
c.pop(0)
for i in range(0,n-1) :
    ans += (a[i]*c[i])

print(ans%mod)

Measured memory_bytes: 31488
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int x=0;
    for(int i=0;;i++){
        scanf("%d",&x);
        if(x==0){
            break;
        }
        printf("Case %d: %d\n",i+1,x);
    }
    return 0;
}



Measured memory_bytes: 2032
N, K = input().split()
N = int(N)
K = int(K)

probability = []

for i in range(1, N+1):
    count = 0
    while i < K:
       i = i * 2
       count += 1
    probability.append((1/N)*(1/2)**count)   

result = 0
for i in probability:
    result = result + i

print(result)

Measured memory_bytes: 6296
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <bitset>
#include <functional>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main(void)
{
	long long X, Y, Z, K;
	long long A[1009], B[1009], C[1009];
	vector<long long> vec;

	cin >> X >> Y >> Z >> K;
	FOR(i, 0, X) {
		cin >> A[i];
	}
	sort(A, A + X, greater<long long>());
	FOR(i, 0, Y) {
		cin >> B[i];
	}
	sort(B, B + Y, greater<long long>());
	FOR(i, 0, Z) {
		cin >> C[i];
	}
	sort(C, C + Z, greater<long long>());

	FOR(i, 0, X) {
		FOR(j, 0, Y) {
			FOR(k, 0, Z) {
				if ((i + 1) * (j + 1) * (k + 1) > K) continue;
				vec.push_back(A[i] + B[j] + C[k]);
			}
		}
	}

	std::sort(vec.begin(), vec.end(), std::greater<long long>());

	FOR(i, 0, K) {
		cout << vec[i] << endl;
 	}

	return 0;
}

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


int N;

int main(){
    cin >> N;

    int ans = N;
    for(int i = 0; i <= N; i++){
        int tmp = 0;
        int six = i;
        while(six > 0){
            tmp += six % 6;
            six /= 6;
        }
        int nine = N - i;
        while(nine > 0){
            tmp += nine % 9;
            nine /= 9;
        }
        ans = min(ans, tmp);
    }

    cout << ans << endl;

}



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

int main(){
	int n;
	while(cin >> n){
		int ans = 0;
		for(int i = 0 ; i <= 9 ; i++){
			for(int j = 0 ; j <= 9 ; j++){
				for(int k = 0 ; k <= 9 ; k++){
					int l = n - i - j - k;
					if( 0 <= l and l <= 9 ) ans++;
				}
			}
		}
		cout << ans << endl;
	}
}

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

int main(){
	int a,b;
	cin>>a>>b;
	
	if(a%2==0 && b%2==0 || a%2!=0 && b%2!=0){
		int ans = b-a;
		ans/=2;
		ans+=a;
		printf("%d\n",ans);
	}
	else 
		puts("IMPOSSIBLE");
	
}

Measured memory_bytes: 256
/*
      author : Nishikawa
      created: 06.08.2020 17:46:44
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;


int main(){
    int N;
    cin >> N;//偶数
    vector<ll> a(N,0);
    for(int i=0; i<N; i++) cin >> a[i];
    ll X=a[0];
    for(int i=1; i<N; i++)
        X=X^a[i];
    for(int i=0; i<N; i++){
        ll tmp = X^a[i];
        cout << tmp << endl;
    }
    return 0;
}

Measured memory_bytes: 4816
N, M = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(N)]

_d = {i:[] for i in range(M+1)}
for a,b in AB:
  _d.setdefault(a, []).append(b)
  
import heapq

ans = 0
hp = []

for i in range(1, M+1):
  for b in _d[i]:
    heapq.heappush(hp, -b)
  if hp:
    ans += -heapq.heappop(hp)

print(ans)

Measured memory_bytes: 37248
N=int(input())
List=[input().split(" ") for _ in range(N)]
#識別用indexの添付
List2=[]
List_sub=[]
for i in range(N):
    List_sub=[i+1,List[i][0],int(List[i][1])]
    List2.append(List_sub)
#独立する地名をピックアップ
set_List=[]
for i in range(len(List)):
    set_List.append(List2[i][1])
#地名を名前の順に変える
set_List=list(set(set_List))
set_List.sort()
#名前順の地名ごとに数字の大きい順にピックアップ
Ans_List=[]
const_const_List=[]
const_List=[]
for i in range(len(set_List)):
    const_List=[]
    for j in range(N):
        if set_List[i]==List2[j][1]:
            const_const_List=[List2[j][2],List2[j][0]]
            const_List.append(const_const_List)
    const_List.sort(reverse=True)
    Ans_List.extend(const_List)
#最後に並んだ順にindexを出力

for i in range(N):
    print(Ans_List[i][1])

Measured memory_bytes: 3064
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**

PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 2e5+7;
const LL LINF = 1e17;

template <class T>
string to_str(T x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}

int ara[nmax][5];
int dp[nmax][5];
int n;

int solve(int pos,int prev)
{
    if(pos>n)
        return 0;

    int &ret = dp[pos][prev];
    if(ret!=-1) return ret;

    ret = 0;

    for(int j=1;j<=3;j++)
        if(j!=prev)
            ret = max(ret,solve(pos+1,j)+ara[pos][j]);

    return ret;

}

int main()
{
    //freopen("out.txt","w",stdout);

    optimizeIO();

    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            cin>>ara[i][j];

    memset(dp,-1,sizeof dp);

    cout<<solve(1,0)<<endl;


    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




Measured memory_bytes: 14208
// D - Wizard in Maze
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(int)(s);i<(int)(e);++i)

pair<int, int> dhw[] = { // <h, w>
        { 1, 0},
{ 0,-1},        { 0, 1},
        {-1, 0},
{ 2,-2},{ 2,-1},{ 2, 0},{ 2, 1},{ 2, 2},
{ 1,-2},{ 1,-1},        { 1, 1},{ 1, 2},
{ 0,-2},                        { 0, 2},
{-1,-2},{-1,-1},        {-1, 1},{-1, 2},
{-2,-2},{-2,-1},{-2, 0},{-2, 1},{-2, 2}
};

int main(){
	int H, W; cin>>H>>W;
	int sh, sw, eh, ew; cin>>sh>>sw>>eh>>ew; sh--, sw--, eh--; ew--;
	string S[H]; rp(i, 0, H) cin>>S[i];

  int INF = 1e9;
	vector<vi> dst(H, vi(W, INF));
	dst[sh][sw] = 0;
	deque<pair<int, int>> dq; // <h, w>
	dq.emplace_front(sh, sw);

	while(dq.size()){
		int h, w; tie(h, w) = dq.front(); dq.pop_front();
		int d = dst[h][w];

		rp(i, 0, 4){
			int nx_h = h + dhw[i].first, nx_w = w + dhw[i].second;
			if(nx_h < 0 || H <= nx_h || nx_w < 0 || W <= nx_w) continue;
			if(dst[nx_h][nx_w] <= d || S[nx_h][nx_w] == '#') continue;
			dst[nx_h][nx_w] = d;
			dq.emplace_front(nx_h, nx_w);
		}
		rp(i, 4, 24){
			int nx_h = h + dhw[i].first, nx_w = w + dhw[i].second;
			if(nx_h < 0 || H <= nx_h || nx_w < 0 || W <= nx_w) continue;
			if(dst[nx_h][nx_w] <= d+1 || S[nx_h][nx_w] == '#') continue;
			dst[nx_h][nx_w] = d + 1;
			dq.emplace_back(nx_h, nx_w);
		}
	}

	cout<< (dst[eh][ew]==INF? -1:dst[eh][ew]) <<endl;
}


Measured memory_bytes: 9428
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

class State {
public:
  int pos;
  int cost;
  int prev_hand;
  int prev_pos;
  State(int _p,int _c) : pos(_p),cost(_c),prev_hand(-1000),prev_pos(-1000) {}
  State(int _p,int _c,int _ph,int _pp) : pos(_p),cost(_c),prev_hand(_ph),prev_pos(_pp) {}
  bool operator<(const State& s) const{
    return cost < s.cost;
  }
  bool operator>(const State& s) const{
    return cost > s.cost;
  }
};

struct DP{
  int cost;
  int prev_hand;
  int prev_pos;
  DP(int _c,int _ph,int _pp) : cost(_c),prev_hand(_ph),prev_pos(_pp){}
  DP() : cost(INF),prev_hand(-1000),prev_pos(-1000){}
};

int main(){
  int total_cells;
  while(~scanf("%d",&total_cells)){
    int dice[7];
    for(int i=1;i<=6;i++){
      scanf("%d",dice + i);
    }
    int start,goal;
    scanf("%d %d",&start,&goal);
    int stage[303];
    for(int i=1;i<=total_cells;i++){
      scanf("%d",stage + i);
    }
    
    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(start,0,-1000,-1000));

    DP dp[303];

    while(!que.empty()){
      State s = que.top();
      que.pop();

      if(dp[s.pos].cost <= s.cost) continue;

      dp[s.pos].cost = s.cost;
      dp[s.pos].prev_hand = s.prev_hand;
      dp[s.pos].prev_pos = s.prev_pos;

      for(int i=1;i<=6;i++){
	int dx1 = s.pos + dice[i];
	int dx2 = s.pos - dice[i];

	if(1 <= dx1 && dx1 <= total_cells){
	  dx1 += stage[dx1];
	  que.push(State(dx1,s.cost + 1,i,s.pos));
	}
	if(1 <= dx2 && dx2 <= total_cells){
	  dx2 += stage[dx2];
	  que.push(State(dx2,s.cost + 1,-i,s.pos));
	}
      }
    }

    vector<int> hands;
    int prev_x = goal;
    for(int round = 0;round <= 3000;round++){
      hands.push_back(dp[prev_x].prev_hand);
      prev_x = dp[prev_x].prev_pos;
      if(prev_x == start) break;
    }

    reverse(hands.begin(),hands.end());

    int hand_idx = 0;
    for(int round = 0;round <= 3000;round++){
      int num;
      scanf("%d", &num);
      
      if(num != abs(hands[hand_idx])){
	printf("0\n"); fflush(stdout);
      }

      else if(num == abs(hands[hand_idx])){
	if(hands[hand_idx] > 0){
	  printf("1\n"); fflush(stdout);
	}
	else{
	  printf("-1\n"); fflush(stdout);
	}
	hand_idx++;
      }

      if(hand_idx >= hands.size()) break;
    }
  }
}

Measured memory_bytes: 1308
//----------------------------おまじない
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
//----------------------------
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#define eb(i,j) emplace_back((i),(j))
#include <bits/stdc++.h>
using namespace std;
//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<vvi> vvvi;
typedef long long ll;
const int mod = 1000000009;

int n;
string s;
int q;
int k[100];

int main(){
    cin >> n;
    cin >> s;
    cin >> q;
    REP(i,q) {
        cin >> k[i];
        vector<ll> imos( n*2 );
        vector<ll> jmos(n*2);
        vector<ll> mmos( n*2 );
        REP(j,n) {
            if (s[j] == 'D'){
                imos[j] ++;
                imos[j + k[i]] --;
            }
            if (s[j] == 'M'){
                mmos[max(0,j-k[i]+1)] ++;
                mmos[j] --;
            }
        
        }
        ll ret = 0;
        //vector<ll> jmos(n*2);
        REP(j,n){
            mmos[j+1] += mmos[j];

            // if(imos[j+1] < 0){
            if(j+1 >= k[i] && s[j-k[i]+1] == 'D'){
                jmos[j+1] -= mmos[j - k[i] + 1];
            }
            imos[j+1] += imos[j];

            if (s[j] == 'M'){
                jmos[j] += imos[j];
            }
            jmos[j+1] += jmos[j];

            if (s[j] == 'C'){
                ret += jmos[j];
            }
        }

        //REP(j,n) cerr << jmos[j];


        cout << ret << endl;
    }
}

Measured memory_bytes: 50192
#include<iostream>

//関数の宣言
void Mul();

int main()
{
	Mul();

	return 0;

}

//関数の定義
void Mul(){
	for (int i = 1; i <= 9; i++){
		for (int j = 1; j <= 9; j++){
			std::cout << i << 'x' << j << '=' << i*j << '\n';
		}
	}
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10; //1e-9?
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n, m; cin >> n >> m;
    map<int, int> ma;
    FOR(i, 0, m) {
        int a, b; cin >> a >> b;
        ++ma[a], ++ma[b];
    }
    bool ok = true;
    each(i, ma)ok &= i.second % 2 == 0;
    cout << (ok ? "YES" : "NO") << "\n";
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  long long L=0;
  long long F=0;
  long long M=0;
  cin>>N;
  vector<long long>vec(N);
  for(int X=0;X<N;X++){
    cin>>vec.at(X);
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(), vec.end());
  for(;;){
    if(L==0){
      M+=vec.at(F);
      L++;
      F++;
    }
    else if(L==N-2){
      M+=vec.at(F);
      L++;
      F++;
    }
    else if(L<N-2 && L>0){
      M+=vec.at(F)*2;
      L+=2;
      F++;
    }
    if(L>=N-1){
      break;
    }
  }
  cout<<M<<endl;
}

Measured memory_bytes: 4828
# -*- coding: utf-8 -*-


class Node():
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right


class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None

    def insert(self, z):
        z = Node(z)
        y = None
        x = self.root

        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

    def print(self):
        self.inorder()
        self.preorder()

    def find(self, k):
        x = self.root
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, z):
        # y is delete node.
        if z.left is None or z.right is None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.left is not None:
            x = y.left
        else:
            x = y.right
        
        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        if y != z:
            z.key = y.key

        

    def getSuccessor(self, x):
        if x.right is not None:
            return self.getMinimum(x.right)

        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

    def getMinimum(self, x):
        while x.left is not None:
            x = x.left
        return x


if __name__ == '__main__':

    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            z = T.find(int(c[1]))
            if z is None:
                print("no")
            else:
                print("yes")
        elif c[0] == "delete":
            z = T.find(int(c[1]))
            T.delete(z)
        else:
            T.print()


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

int dp[3001][3001];

using namespace std;
void   LCS(string s1,string s2,int dp[][3001]){
	
    //memset(dp,0,sizeof dp);
	int a=s1.length();
	int b=s2.length();
	for(int i=0;i<=a;i++){
			dp[i][0]=0;
	}

for(int i=0;i<=b;i++){
			dp[0][i]=0;
	}
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
        
			if(s1[i-1]==s2[j-1]){
				dp[i][j]=1+dp[i-1][j-1];
				
			}
		
		else{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
    }
 //return dp[a][b];  
}
int main() {
     string s1,s2;
     cin>>s1>>s2;
   
    int a=s1.length();
	int b=s2.length();
   
    
    LCS(s1,s2,dp);
    char ans [dp[a][b]];
    int x=a;
    int y=b;
    int i=dp[a][b]-1;
    while(i>=0){
        if(s1[x-1]==s2[y-1]){
            ans [i]=s1[x-1];
            x--;
            y--;
            i--;
        }
        else{
            if(dp[x-1][y]>dp[x][y-1]){
                    x--;
            }
            else{
                y--;
            }
        }
    }
    for(int j=0;j<dp[a][b];j++){
        cout<<ans[j];
    }
   // cout<<LCS(s1,s2,dp);
	return 0;
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i= 0;i<(int)c;i++)
int main() {
   int A;
   cin >> A;
   string S;
   cin >> S;
   if(A>=3200){
      cout << S<<endl;
   }else{
      cout << "red" << endl;
   }
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var A, B, C, D int
	fmt.Scan(&A, &B, &C, &D)
	t := (C + B - 1) / B // 高橋くんが青木くんを倒すために必要な攻撃の回数
	a := (A + D - 1) / D // 青木くんが高橋くんを倒すために必要な攻撃の回数
	if a >= t {          // aがt以上なら高橋くんのかち(高橋くんが先攻のため)
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1764