akhauriyash/Code-Regression huggingface dataset:
function memoization(f) {
  const cache = {};
  return (...param) => {
    const c = cache[param];
    return typeof c === 'undefined' ? cache[param] = f(...param) : c;
  };
}

class _Node {
  constructor(id, parentId, leftId, rightId) {
    this.id = id;
    this.parentId = parentId;
    this.leftId = leftId;
    this.rightId = rightId;
  }
  get type() {return this.parentId === -1 ? 'root' : this.leftId === -1 && this.rightId === -1 ? 'leaf' : 'internal node'}
}

class BinaryTree {
  constructor() {
    this.nodes = [];
    this._nodeInfo = [];
    this.getDepth = memoization(this.getDepth.bind(this));
    this.getHeight = memoization(this.getHeight.bind(this));
  }
  static get Node() {return _Node;}

  add(id, leftId, rightId) {this.nodes[id] = new BinaryTree.Node(id, -1, leftId, rightId);}
  find(id) {return this.nodes[id]}
  connect() {
    for (let i = 0; i < this.nodes.length; i++ ) this._nodeInfo[i] = {node:null, sibling:-1, degree:0};
    this.nodes.forEach(n => {
      if (n.leftId !== -1) {
        this.nodes[n.leftId].parentId = n.id;
        this._nodeInfo[n.leftId].sibling = n.rightId;
      }
      if (n.rightId !== -1) {
        this.nodes[n.rightId].parentId = n.id;
        this._nodeInfo[n.rightId].sibling = n.leftId;
      }
    });
    this.nodes.forEach(n => {
      this._nodeInfo[n.id] = {sibling: this._nodeInfo[n.id].sibling, node: n, degree: (n.leftId !== -1) + (n.rightId !== -1)}
    });
  }
  getDepth(id, i = 0) {
    let pid = this.find(id).parentId;
    return pid === -1 ? i : this.getDepth(pid, i + 1);
  }
  getHeight(id, i = 0) {
    if (id === -1) return i - 1;
    let n = this.find(id);
    return Math.max(this.getHeight(n.leftId, i + 1), this.getHeight(n.rightId, i + 1))
  }
  print() {
    console.log(this._nodeInfo.map(o =>
      `node ${o.node.id}: parent = ${o.node.parentId}, sibling = ${o.sibling}, degree = ${o.degree}, depth = ${this.getDepth(o.node.id)}, height = ${this.getHeight(o.node.id)}, ${o.node.type}`
    ).join('\n'));
  }
}

(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  let tree = new BinaryTree();
  lines.map(l => l.split(' ').map(Number)).forEach(line => tree.add(...line));
  tree.connect();
  tree.print();
})();



Measured memory_bytes: 16452
import java.util.*;
class Main{
	public static long mod(long num,long a,long mod) {
		long p = 1;
		for(int i = 0; i < num; i++) {
			p = p*a%mod;
		}
		return p;
	}
	public static void main(String[] args) {
		long mod = 1000000000 + 7;
		Scanner scanner = new Scanner(System.in);
		long num = scanner.nextInt();
		long result = 0;
		result = (mod(num,10,mod) - 2*mod(num,9,mod) + mod(num,8,mod))%mod;
		result = (result + mod)%mod;
		System.out.println(result);
		scanner.close();
	}
}

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

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

  int cnt = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') {
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 764
S = input()
MOD = 10 ** 9 + 7

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Measured memory_bytes: 43740
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int N, x;
	int a[100];
	long long num = 0LL;
	
	cin >> N >> x;
	for (int i = 0;i < N;i++) cin >> a[i];
	sort(a, a + N);
	int count=0;
	
		for (int k = 0;k < N-1;k++) {
				num += a[k];
				if(num<=x)
				count++;
			
		}
		if (num <= x) {
			if (x - num == a[N - 1]) count++;
		}
		cout << count;
	
	
	
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a.at(i);
	vector<ll> dp(n + 1);
	vector<int> cnt(3);
	dp[0] = 1;
	rep(i,n){
		int k = 0;
		rep(j,3){
			if(cnt.at(j) == a.at(i)) k++;
		}
		dp[i + 1] = dp[i] * k % mod;
		rep(j,3){
			if(cnt.at(j) == a.at(i)){
				cnt.at(j)++;
				break;
			}
		}
	}
	cout << dp[n] << endl;
}


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

const ll MOD = 1e9 + 7;

bool cmp(char x,char y){return x<=y;}

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

	map<ll,int> mp;

	for(int i=0;i<n;i++){
		ll x; cin>>x; mp[x]++;
	}
	int ans=0;
	for(auto t:mp){
		ll x = t.first; ll f = t.second;
		if(x > f) ans += f;
		else ans += f-x;
	}

	cout<<ans;
}

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

#define SORT(v) sort(v.begin(),v.end())
#define si(n) scanf("%d",&n)
#define sii(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define ss(cad) scanf("%s",cad)
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl; 
#define M 1000000007
#define N_MAX 100010

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vp;

ll costo[100100][3];
ll dp[100100][3];

int main(){
	int n;
	si(n);
	for(int i = 1; i <= n; i++){
		sl(costo[i][0]);
		sl(costo[i][1]);
		sl(costo[i][2]);
	}	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			dp[i][j] = 0;
			for(int k = 0; k < 3; k++){
				if(j == k)
					continue;
				dp[i][j] = max(dp[i][j], dp[i-1][k] + costo[i][j]);
			}
		}
	}
	ll ans = max(dp[n][0], dp[n][1]);
	ans = max(ans, dp[n][2]);
	printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 8404
import java.util.*;
import java.io.*;

public class Main {

	static char[][] grid;
	static int[][] dp;
	static int h, w;
	static int mod = (int) 1e9+7;

	public static int dp(int r, int c) {
		if (r == h - 1 && c == w - 1) {
			return 1;
		}
		if (r == h || c == w) {
			return 0;
		}
		if (grid[r][c] == '#')
			return 0;
		if (dp[r][c] != -1) {
			return dp[r][c];
		}
		return dp[r][c] = (dp(r + 1, c) + dp(r, c + 1)) % mod;

	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		h = sc.nextInt();
		w = sc.nextInt();
		grid = new char[h][];
		for (int i = 0; i < h; i++) {
			grid[i] = sc.next().toCharArray();
		}
		dp = new int[h][w];
		for (int[] x : dp)
			Arrays.fill(x, -1);
		pw.println(dp(0, 0));
		pw.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}

	}

}


Measured memory_bytes: 36668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;


int main(){
    ll N, X;
    cin>>N>>X;
    vector<ll> A(N);
    rep(i, N){
        cin>>A[i];
    }
    ll Ans=0;
    if(A[0]>X){
        Ans+=A[0]-X;
        A[0]=X;
    }
    rep(i, N-1){
        ll Num=A[i]+A[i+1];
        if(Num>X){
            ll K=Num-X;
            Ans+=K;
            A[i+1]-=K;
        }
    }
    cout<<Ans<<endl;
}

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

using namespace std;




int main(){
  
  #ifndef ONLINE_JUDGE
  freopen ("input.txt", "r", stdin);
  freopen ("outt.txt", "w", stdout);
#endif
 
 long long a,b,c;
 cin>>a>>b>>c;
 long long k;
 cin>>k;
 int cnt =0 ;
 while(a>=b){
  b*=2;
  cnt++;
 }
 while(b>=c){
  c*=2;
  cnt++;
 }
 if(cnt>k){
  cout<<"No\n";

 }
 else
  cout<<"Yes\n";




}






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

using namespace std;

template <class T> inline T updmax(T& a, T b) { return a = max(a, b); }
template <class T> inline T updmin(T& a, T b) { return a = min(a, b); }

void dfs(vector<vector<int>>& g, vector<int>& ans, vector<int>& f, vector<bool>& visit, int u, int val) {
	ans[u] = val + f[u];
	visit[u] = true;
	for (auto v : g[u])
		if (!visit[v]) dfs(g, ans, f, visit, v, ans[u]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, Q;
	cin >> n >> Q;
	vector<vector<int>> g(n);
	vector<int> f(n);
	vector<int> ans(n, 0);
	vector<bool> visit(n);
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	for (int i = 0; i < Q; i++) {
		int p, x;
		cin >> p >> x;
		f[p - 1] += x;
	}

	dfs(g, ans, f, visit, 0, 0);
	for (int i = 0; i < n; i++) cout << ans[i] << " ";
	cout << "\n";

	return 0;
}

Measured memory_bytes: 30592
package main

import (
	"bufio"
	"fmt"
	_ "math"
	"os"
	_ "sort"
)

func Min64(x, y int64) int64 {
	if x < y {
		return x
	}
	return y
}

func Max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{})  { fmt.Fscanf(reader, f, a...) }

func main() {
	defer writer.Flush()

	var n, m int64
	scanf("%d %d\n", &n, &m)
	if n*2 < m {
		p := (m - n*2) / 4
		n += p
		m -= 2 * p
	}
	ans := Min64(n, m/2)
	printf("%d\n", ans)
}


Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

const int MAX_STONES = 100001;
const int MAX_VALUE = 2e9;

int main() {
    cin.sync_with_stdio(false);
    cin.tie();

    int stones[MAX_STONES];
    int cost[MAX_STONES];

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> stones[i];
    cost[0] = 0;
    cost[1] = abs(stones[1] - stones[0]);
    for (int i = 2; i < n; ++i) {
        int from = max(0, i - k);
        int min = MAX_VALUE;
        for (int j = from; j < i; ++j) {
            int cur_cost = abs(stones[i] - stones[j]) + cost[j];
            if (min > cur_cost) {
                min = cur_cost;
            }
        }
        cost[i] = min;
    }
    cout << cost[n - 1] << endl;

    return 0;
}


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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

using uint=unsigned;
using ull=unsigned long long;

//initfact();
//const uint mod=998244353;
const uint mod=1000000007;
//uint mod=1;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint& operator+=(const mint&rhs){return s(v+rhs.v);}
	mint&operator-=(const mint&rhs){return s(v+mod-rhs.v);}
	mint&operator*=(const mint&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	mint&operator/=(const mint&rhs){return *this*=rhs.inv();}
	mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
	mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
	mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
	mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
	mint pow(int n)const{
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	/*mint inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return mint(x);
	}*/
	friend ostream& operator<<(ostream&os,const mint&m){
		return os<<m.v;
	}
	bool operator<(const mint&r)const{return v<r.v;}
	bool operator==(const mint&r)const{return v==r.v;}
};

const int vmax=10000010;
mint fact[vmax],finv[vmax],invs[vmax];
void initfact(){
	fact[0]=1;
	rng(i,1,vmax){
		fact[i]=fact[i-1]*i;
	}
	finv[vmax-1]=fact[vmax-1].inv();
	for(int i=vmax-2;i>=0;i--){
		finv[i]=finv[i+1]*(i+1);
	}
	for(int i=vmax-1;i>=1;i--){
		invs[i]=finv[i]*fact[i-1];
	}
}
mint choose(int n,int k){
	return fact[n]*finv[n-k]*finv[k];
}
mint binom(int a,int b){
	return fact[a+b]*finv[a]*finv[b];
}
mint catalan(int n){
	return binom(n,n)-(n-1>=0?binom(n-1,n+1):0);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	initfact();
	
	int n,k;cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		mint ans=1;
		if(n-k+1>=i&&k-1>=i-1)
		ans=choose(n-k+1,i)*choose(k-1,i-1);
		else ans=0;
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 117504
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }
    sort(all(A));
    vector<ll> B(N);
    B[0] = A[0];
    rep(i,N - 1){
        B[i + 1] = A[i + 1] + B[i];
    }
    ll minum = 0;
    rep(i,N - 1){
        if (B[i] * 2 < A[i + 1]) minum = i + 1;
    }
    cout << N - minum << endl;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	size_t f1,f2;
	f1=s.find("AB");
	f2=s.find("BA");
	if(f1==string::npos and f2==string::npos)
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
	return 0;
}

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

using namespace std;

typedef long long LL;

struct Edge {
    int to, t, m;
    LL v;
};

void dfs(int v, int parent, const vector<vector<Edge>> &graph, vector<pair<int,Edge>> &ord) {
    for(const auto &e : graph[v]) {
        if(e.to == parent) continue;
        ord.push_back(make_pair(e.to, e));
        dfs(e.to, v, graph, ord);
        ord.push_back(make_pair(v, e));
    }
}

bool solve() {
    int N, T;
    if(!(cin >> N >> T)) return false;
    if(!N && !T) return false;

    vector<vector<Edge>> graph(N);
    for(int i = 0; i < N-1; ++i) {
        int a, b, t, m;
        LL v;
        cin >> a >> b >> t >> m >> v;
        --a; --b;
        graph[a].push_back((Edge){b, t, m, v});
        graph[b].push_back((Edge){a, t, m, v});
    }
    
    vector<pair<int,Edge>> ord;
    ord.push_back(make_pair(0, Edge()));
    dfs(0, -1, graph, ord);
    const int M = ord.size();
    vector<vector<LL>> dp(M, vector<LL>(T+1, -1));
    dp[0][0] = 0;
    for(int i = 1; i < M; ++i) {
        const int v = ord[i].first;
        const Edge &e = ord[i].second;
        if(v != e.to) { //back
            int rem = e.m;
            // should pay 2
            for(int t = T; t >= 0; --t) {
                if(t-e.t*2 >= 0 && dp[i-1][t-e.t*2] >= 0) dp[i][t] = dp[i-1][t-e.t*2] + min(2, e.m)*e.v;
            }
            rem -= min(2, e.m);
            // optionally pay 1 if e.m is odd
            if(rem % 2 == 1) {
                for(int t = T; t >= 0; --t) {
                    if(t-e.t*2 >= 0 && dp[i][t-e.t*2] >= 0) dp[i][t] = max(dp[i][t], dp[i][t-e.t*2] + e.v);
                }
                --rem;
            }
            // binary dp
            for(int k = 2; rem > 0; k *= 2) {
                const int s = min(k, rem);
                const int dt = e.t * s;
                const int dv = e.v * s;
                for(int t = T; t >= 0; --t) {
                    if(t-dt >= 0 && dp[i][t-dt] >= 0) dp[i][t] = max(dp[i][t], dp[i][t-dt] + dv);
                }
                rem -= s;
            }
        } else {
            dp[i] = dp[i-1];
        }
        // Ignore current subtree
        for(int j = i-1; j >= 0; --j) {
            if(ord[j].first == v) {
                for(int t = 0; t <= T; ++t) {
                    dp[i][t] = max(dp[i][t], dp[j][t]);
                }
                break;
            }
        }
        /*
        cout << i << ' ' << v << ": ";
        for(auto val : dp[i]) {
            cout << val << ' ';
        }
        cout << endl;
        */
    }
    cout << *max_element(dp[M-1].begin(), dp[M-1].end()) << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

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

int main(void){
    int n, m;
    std::vector<int> sw(n);
    std::cin >> n >> m;
    std::vector<std::vector<int>> ls;
    ls.resize(m);
    int k;
    for(int i = 0; i < m; i++){
	std::cin >> k;
	ls[i].resize(k);
	for(int j = 0; j < k; j++){
	    int s;
	    std::cin >> s;
	    s--;
	    ls[i][j] = s;
	}
    }
    std::vector<int> p(m);
    for(int i = 0; i < m; i++){
	std::cin >> p[i];
    }

    int ans = 0;
    bool flag;
    for(int i = 0; i < 1<<n; i++){
	flag = 0;
        for(int j = 0; j < n; j++){
            if(i>>j & 1) sw[j] = 1;
            else sw[j] = 0;
        }
        for(int j = 0; j < m; j++){
            int cnt = 0;
            int x = ls[j].size();
            for(int l = 0; l < x; l++){
		 int swn = ls[j][l];
                 cnt += sw[swn];	
            }
            if(cnt % 2 != p[j]){
                flag = 1;
                break;
            }
        }
        if(!flag) ans++;
    }
    std::cout << ans << std::endl;
    return 0;
}



Measured memory_bytes: 3768
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int main(){
  int n; cin >> n;
  int i;
  for(i = 0; i < n; i++){
    int a; cin >> a;
    if(a % 2 == 0){
      if(a % 3 == 0 || a % 5 == 0) continue;
      else break;
    }
  }
  if(i == n) cout << "APPROVED\n";
  else cout << "DENIED\n";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

int f_dir[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}}; //↑→↓←
int e_dir[2][8] = {{-1, -1, -1, 0, 0, 1, 1, 1}, {-1, 0, 1, -1, 1, -1, 0, 1}};
bool is_in_field(int y, int x, int h, int w){
  return (y >= 0 && y < h && x >= 0 && x < w);
}

struct UnionFind {
  vector<int> par;//parent
  vector<int>nodes;

  UnionFind(int N): par(N), nodes(N)
  {
    for(int i = 0; i < N; i++){
      par[i] = i;
      nodes[i] = 1;
    }
  }

  int root(int x) {//find the root and path compression
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    nodes[ry] += nodes[rx];
    par[rx] = ry;
  }

  bool same(int x, int y){
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }

};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  ll n, m;
  cin >> n >> m;
  UnionFind U(n);
  ll ans = 0;
  for(int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;
    a--, b--;
    U.unite(a, b);
  }
  for(int i = 1; i < n; i++){
    if(!U.same(0, i)){
      ans++;
      U.unite(0, i);
    }
  }
  cout << ans << endl;

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> vec(n);

	for (int i=0; i<n; i++)
		cin >> vec[i];

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

	//int diff = vec[vec.size()-1] - vec[0];
	if (vec[0] == vec[vec.size()-1]) {
		cout << "0";
	}
	else {
		int res = INT_MAX;
		int counter = 0;
		int temp = vec[0];
		while (temp <= vec[vec.size()-1]) {
			int sum = 0;
			for (int i=0; i<vec.size(); i++) {
				sum += (temp - vec[i])*(temp-vec[i]);
			}
			res = min (res, sum);
			temp++;
		}
		cout << res;
	}
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			String s = in.nextString();
			int n = s.length();

			out.println(s.substring(0, n-8));

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}


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

int main (){
    int N;
    int d[200010];
    cin >> N;

    int m1 = 0, m2 = 0;
    for(int i = 0; i < N; ++i) {
        scanf("%d", d + i);
        if(m1 < d[i]) {
            m2 = m1;
            m1 = d[i];
        }else if (m2 < d[i]) {
            m2 = d[i];
        }
    }

    for(int i = 0; i < N; ++i) {
        cout << (m1 == d[i] ? m2 : m1) << "\n";
    }
}


Measured memory_bytes: 2432
fun main(args: Array<String>) {
    Main.init()

    Main.execute()

    Main.display()
}

data class Timestamp(var findedAt: Int? = null, var endedAt: Int? = null, var distance: Int? = null)

class Main {

    companion object {
        private val graphMatrix = arrayListOf<ArrayList<Boolean>>()

        private val timestampList = arrayListOf<Timestamp>()

        val queue = Queue(arrayListOf())

        private var currentTime = 0

        fun init() {
            val num = readLine()!!.toInt()

            initgraph(num)

            for (index in 1..num) {
                val inputs = readLine()!!.split(" ")
                val nodeIndex = inputs[0].toInt()
                for (inputIndex in 2 until inputs.size) {

                    val touchedNode = inputs[inputIndex].toInt()
                    graphMatrix[nodeIndex - 1][touchedNode - 1] = true
                }
            }
        }

        fun display() {
            timestampList.forEachIndexed { index, it ->
                println("${index + 1} ${it.distance ?: -1}")
            }
        }

        /**
         * 幅優先
         */
        fun execute() {
            timestampList[0].distance = 0
            gather(1)
        }

        /**
         * 集める
         */
        fun gather(index: Int) {

            val currentDistance = timestampList[index - 1].distance!!

            graphMatrix[index - 1].forEachIndexed { i, canGo ->

                if (!canGo) return@forEachIndexed

                // 未探索かつキューにまだなかったら
                if (timestampList[i].distance == null && !queue.contains(i)) {
                    queue.enqueue(i)

                    // 距離を記録
                    timestampList[i].distance = currentDistance + 1
                }
            }

            val topIndex = queue.dequeue() ?: return

            // 一つ移動
            gather(topIndex + 1)
        }

        fun initgraph(num: Int) {
            for (i in 0 until num) {
                graphMatrix.add(arrayListOf())
                for (j in 0 until num) {
                    graphMatrix[i].add(false)
                }
                timestampList.add(Timestamp())
            }
        }
    }
}


class Queue(list: MutableList<Int>) {

    var items: MutableList<Int> = list

    fun isEmpty(): Boolean = items.isEmpty()


    fun contains(i: Int): Boolean = items.contains(i)

    fun size(): Int = items.count()

    override fun toString() = items.toString()

    fun enqueue(element: Int) {
        items.add(element)
    }

    fun dequeue(): Int? {
        if (this.isEmpty()) {
            return null
        } else {
            return items.removeAt(0)
        }
    }

    fun peek(): Int? {
        return items[0]
    }
}


Measured memory_bytes: 34096
#include <iostream>
#include <string>
using namespace std;
int n;
long long  pprev;
long long  ans;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        long long val; cin >> val;
        if(pprev > val) ans+= pprev - val, val = pprev;
        pprev = val;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3156
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    # 最大　10 * 10 * 10 = 1000
    N = int(input())
    S = [int(s) for s in input()]

    ans = 0
    for i in range(0, 10):
        for j in range(0, 10):
            for k in range(0, 10):
                find_i = False
                find_j = False
                find_k = False
                for s in S:
                    if not find_i:
                        if i == s:
                            find_i = True
                    elif not find_j:
                        if j == s:
                            find_j = True
                    elif not find_k:
                        if k == s:
                            find_k = True
                            ans += 1
                            break
    print(ans)


Measured memory_bytes: 43608
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Stack<Integer> stack = new Stack<Integer>();
		while(in.hasNext()) {
			int tmp = in.nextInt();
			if(tmp == 0) System.out.println(stack.pop());
			else stack.push(tmp);
		}
		
	}

}

Measured memory_bytes: 17208
#include <bits/stdc++.h>
#include <numeric>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    long long x,y,ans=0;
    cin >> x >> y;
    while(x<=y){
        x*=2;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define PRINT(x) cout<<(x)<<endl
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair

const int MAX_N = 200000;

int N;
int a[MAX_N];

int main() {
    cin >> N;
    REP(i, N) cin >> a[i];
    int sum = 0;
    REP(i, N) sum ^= a[i];
    int b[MAX_N];
    REP(i, N) b[i] = sum ^ a[i];
    printf("%d", b[0]);
    REP2(i, 1, N) printf(" %d", b[i]); 
    printf("\n");
    return 0;
}

Measured memory_bytes: 5196
import java.util.Scanner;

public class Main{
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();
        int area = a * b;
        int length = (a + b) * 2;

        System.out.println(area + " " + length);
        sc.close();
    }
}


Measured memory_bytes: 26272
n=int(input())
a=list(map(lambda x:int(x),list(input().split())))
for i in range(1,n):
    for k in range(n-1):
        print(a[k],end=" ")
    print(a[n-1])
    v=a[i]
    j=i-1
    while j>=0 and a[j]>v:
        a[j+1]=a[j]
        j=j-1
    a[j+1]=v

for k in range(n-1):
        print(a[k],end=" ")
print(a[n-1])




Measured memory_bytes: 5980
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <limits.h>
#include <utility>
#include <stack>

using namespace std;

#define fs first
#define sc second

typedef long long ll;
typedef pair<ll, ll> P;

ll N, X, D;

ll maxV(ll a){
    return (2 * N - a - 1) * D * a / 2;
}

ll minV(ll a){
    return (a - 1) * D  * a / 2;
}

ll absInt(ll a){
    return a > 0 ? a : -a;
}

ll myRem(ll x, ll d){
    if(x > 0){
        return x % d;
    }
    else{
        return (x % d + d) % d;
    }
}


int main(){
    map<ll, vector<P>> mpV;
    cin >> N >> X >> D;
//    cout << (-6) % 5 << endl;
    if(D == 0){
        if(X == 0){
            cout << 1 << endl;
        }
        else{
            cout << N + 1 << endl;
        }
        return 0;
    }

    ll res = 0;
    if(D < 0){
        D = -D;
        X = -X;
    }

    for (ll a = N; a >= 0; a--) {
        ll xDif = X * (2 * a - N);
        ll rem = myRem(xDif, 2 * absInt(D));

        ll difMax = maxV(a) - minV(N - a) + xDif;
        ll difMin = minV(a) - maxV(N - a) + xDif;
        if(mpV.find(rem) == mpV.end()){
            vector<P> v;
            v.emplace_back(P(difMin, difMax));
            mpV[rem] = v;
        }
        else{
            mpV[rem].emplace_back(P(difMin, difMax));
        }
    }

    for(auto v: mpV){
        vector<P> vv;
        for(auto vx: v.sc){
            vv.emplace_back(vx);
        }
        sort(vv.begin(), vv.end());

        P x = vv[0];
        for(int i = 1; i < vv.size(); i++){
            if(x.sc < vv[i].fs){
                res += (x.sc - x.fs) / (2 * D) + 1;
                x = vv[i];
            }
            else{
                x.sc = max(x.sc, vv[i].sc);
            }
        }
        res += (x.sc - x.fs) / (2 * D) + 1;
    }
    cout << res << endl;

}

Measured memory_bytes: 22144
/*  The round-robin scheduling (ラウンドロビンスケジューリング) */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define LEN 100005
#define MAX 100000

typedef struct pp
{
    char name[100];
    int t;
} P;

/* Global Variable */
P Q[LEN + 1];


void initialize(int *head, int *tail)
{
    *head = 0;
    *tail = 0;
}

int isEmpty(int *head, int *tail)
{
    return *head == *tail;
}

int isFull(int *head, int *tail)
{
    return *head == (*tail + 1) % MAX;
}

void enqueue(P x, int *head, int *tail)
{
    if (isFull(head, tail))
    {
        printf("error(overflow)\n");
        exit(0);
    }
    Q[*tail] = x;
    if (*tail + 1 == MAX)
    {
        *tail = 0;
    }
    else
    {
        *tail += 1;
    }
}

int dequeue(int *head, int *tail)
{
    int x;

    if (isEmpty(head, tail))
    {
        printf("error(underflow)\n");
        exit(0);
    }

    x = *head;
    if (*head + 1 == MAX)
    {
        *head = 0;
    }
    else
    {
        *head += 1;
    }
    return Q[x].t;
}

int main(void)
{
    int head, tail, n;
    int elaps = 0, c;
    int i, q;
    P u;

    initialize(&head, &tail);

    scanf("%d %d", &n, &q);
    for (i = 0; i < n; i++)
    {
        scanf("%s", u.name);
        scanf("%d", &u.t);
        enqueue(u, &head, &tail);
    }

    while (!isEmpty(&head, &tail))
    {
        c = Q[head].t - q;
        if (c > 0)
        {
            elaps += q;
            u.t = c;
            strcpy(u.name, Q[head].name);
            dequeue(&head, &tail);
            enqueue(u, &head, &tail);
        }
        else
        {
            elaps += Q[head].t;
            printf("%s% d\n", Q[head].name, elaps);
            dequeue(&head, &tail);
        }
    }

    return 0;
}


Measured memory_bytes: 11860
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;

class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
      if (n < 1000) {
        Console.WriteLine("ABC");
      } else {
        Console.WriteLine("ABD");
      }
    }
}


Measured memory_bytes: 13140
#include<iostream>
using namespace std;
bool huiwen(string s){
	for(int i=0;i<s.size()/2;++i)
		if(s[i]!=s[s.size()-1-i])
			return false;
	return true;
}
int main(){
	string s;
	cin>>s;
	if(huiwen(s)&&huiwen(s.substr(0,(s.size()-1)/2))&&huiwen(s.substr((s.size()+3)/2-1)))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

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

int main(){
    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    vector<string> output(H);
    for (int i = 0; i < H; i++)
    {
        cin >> S[i];
        output[i] = S[i];

    }

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

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            int cnt = 0;
            //8点移動
            if(S[i][j] == '.'){
                for (int k = 0; k < 8; k++)
                {
//                    if(i==5 && j == 1) cout <<i + dy[k]<<j + dx[k] << endl;
                    if(i+dy[k]>=0 && (i+dy[k]<H) && (j+dx[k]>=0) && (j+dx[k]<W)){

                        if(S[i + dy[k]][j + dx[k]] == '#'){
                            cnt++;
                        }
                    }
                }
                output[i][j] = char(cnt + '0');
            }
        }
    }
     for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << output[i][j];
        }
        cout  << endl ;
    }   
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int *x, int *y){ int t = *x; *x = *y; *y = t;}

int partition(int *a, int p, int r){
  int x , i, j;
  x = a[r];
  i = p - 1;
  for(j = p; j < r; ++j)
    if(a[j] <= x)
      swap(&a[++i], &a[j]);
  swap(&a[++i], &a[r]);
  return i;
}

int main(){
  int  n, a[100001], i, r, q;

  scanf("%d", &n);
  for(i = 0;i < n; ++i) scanf("%d", a + i);
  q = partition(a, 0, n - 1);

  for(i = 0; i < n; i++){
    if(i != 0) putchar(' ');
    printf(i != q ? "%d" : "[%d]", a[i]);
  }
  puts("");
  return 0;
}



Measured memory_bytes: 2160
#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 n,k;
    cin >> n >> k;
    vector<ll> h(n,0);
    rep(i,n)cin >> h[i];
    sort(h.begin(),h.end(),greater<ll>());
    rep(i,k){
        if(i < n){
            h[i] = 0;
        } 
    }
    ll sum = 0;
    rep(i,n)sum += h[i];
    cout << sum << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define INF 999999999999999

using namespace std;

typedef long long ll;

int main(){
	ll n;
	cin >> n;
	ll a[n+1];a[0]=0;ll aa;
	for(int i = 1; i <= n; i++){
		cin >> aa;
		a[i]=a[i-1]+aa;
	}
	ll ans = INF;
	ll num[4];
	ll fq=1;ll tq=3;
	for(ll i=2; i < n-1; i++){
		ll dif=INF;
		for(int j = fq; j < i; j++){
			if(dif > abs(a[j]*2-a[i]))fq=j,dif=abs(a[j]*2-a[i]);
			else break;
		}
		dif=INF;
		for(int k = max(tq,i+1); k < n; k++){
			if(dif > abs((a[k]-a[i])*2-a[n]+a[i]))tq=k,dif=abs((a[k]-a[i])*2-a[n]+a[i]);
			else break;
		}
		num[0]=a[fq];
		num[1]=a[i]-a[fq];
		num[2]=a[tq]-a[i];
		num[3]=a[n]-a[tq];
		sort(num,num+4);
		ans = min(ans, num[3]-num[0]);
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int A;
int B;
int X;
int AN;
int RN;

int main(void){
scanf("%d%d%d",&A,&B,&X);

AN = A + B;
RN = AN - X;
if(A<= X){
    if(RN >= 0){
    printf("YES\n");
    }else {
    printf("NO\n");
    }
}else{
    printf("NO\n");
}
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;


int main()
{
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;

    bool criterion_x = x-r >= 0 && x+r <= W,
         criterion_y = y-r >= 0 && y+r <= H;

    if (criterion_x && criterion_y)
        cout << "Yes";
    else 
        cout << "No";
    cout << endl;

}


Measured memory_bytes: 3100
<?php
fscanf(STDIN, '%d', $n);
$Aarray = explode(' ', trim(fgets(STDIN)));
rsort($Aarray);
$Alice = 0;
$Bob = 0;
for($i = 0; $i <= ($n-1); $i += 2){
    $Alice += $Aarray[$i];
}
for($j = 1; $j <= ($n-1); $j += 2){
    $Bob += $Aarray[$j];
}
print $Alice - $Bob;


Measured memory_bytes: 4604
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
void setcomb() {
	fac[0] = 1;
	ifac[0] = 1;
	for (ll i = 0; i < 1000000; i++) {
		fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M)
	}
	ifac[1000000] = mpow(fac[1000000], M - 2);
	for (ll i = 1000000; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i%M;
	}
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
ll perm(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	return fac[a] * ifac[a - b] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b, int n) {
	int i, j, k, t;
	vector<vector<ll>> c(n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			t = 0;
			for (k = 0; k < n; k++)
				t = (t + a[i][k] * b[k][j] % M) % M;
			c[i].push_back(t);
		}
	}
	return c;
}

template< typename Monoid >
struct SegmentTree {

	int sz;
	vector< Monoid > seg;

	const Monoid M1;

	SegmentTree(int n, const Monoid &M1) : M1(M1) {
		sz = 1;
		while (sz < n) sz <<= 1;
		seg.assign(2 * sz, M1);
	}

	void set(int k, const Monoid &x) {
		seg[k + sz] = x;
	}

	void build() {
		for (int k = sz - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	void update(int k, const Monoid &x) {
		k += sz;
		seg[k] = x;
		while (k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(int a, int b) {
		Monoid L = M1, R = M1;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = f(L, seg[a++]);
			if (b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid value(const int &k) const {
		return seg[k + sz];
	}

	Monoid f(Monoid a, Monoid b) {
		return a + b;
	}

};

int main() {
	int n;
	char s[1111];
	cin >> n >> s;
	if (n < 3200)
		cout << "red" << endl;
	else
		cout << s << endl;
}

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

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

    int all = 1, sub = 1;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(x%2 == 0)    sub *= 2;
        all *= 3;
    }

    cout << all-sub << endl;
    return 0;
}

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

using namespace std;

const int N = 200010;

int n, a, b, c, d;
char s[N];

bool go(int u, int v) {
    while (u < v) {
        if (s[u + 1] == '.' && u + 1 <= v) u++;
        else if (s[u + 2] == '.' && u + 2 <= v) u += 2;
        else break;
    }  
    return u == v;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a >> b >> c >> d;
    cin >> (s + 1);    
    int res = go(a, c) & go(b, d);
    if (c > d) {
        int found = 0;
        for (int i = b; i <= d; i++) {
            if (s[i - 1] == s[i] && s[i] == s[i + 1] && s[i] == '.') {
                found = 1;
                break;
            }
        }
        res &= found;
    }
    cout << (res ? "Yes" : "No") << endl;
    return 0;
}

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

int main() {
  int N;
  cin>>N;
  for (int i = 0; i < N; i++) {
  string x;
    cin>>x;
    if(x=="Y"){
      cout<<"Four"<<endl;
      break;
    }
      else if(i==N-1){
        cout<<"Three"<<endl;
    }
  }
  }

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文

int main() {
	int k;
	cin >> k;
	cout << (k / 2) * ((k + 1) / 2);
}


Measured memory_bytes: 256
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    k = int(readline())
    if k < 10:
        print(k)
    else:
        ls_r = [str(i) for i in range(1, 10)]
        ls_z = ["0"]
        t = 9
        while True:
            t_ls_r = []
            t_ls_z = []
            for v in ls_r + ls_z:
                top = int(v[0])
                for i in range(max(0, top - 1), min(10, top + 2)):
                    if i == 0:
                        t_ls_z.append("".join([str(i)] + list(str(v))))
                    else:
                        t_ls_r.append("".join([str(i)] + list(str(v))))
            if len(t_ls_r) + t >= k:
                t_ls_r.sort()
                print(t_ls_r[k - t - 1])
                exit()
            else:
                ls_r = t_ls_r
                ls_z = t_ls_z
                t += len(t_ls_r)


if __name__ == '__main__':
    solve()


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

using namespace std;

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

int main() {

  int H, W; cin >> H >> W;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  int ans = 1e9;
  
  REP(a, 1, H) REP(b, a+1, H) {
    int K = 0;
    rep(i, H) rep(j, W) {
      if(i < a) K += G[i][j] != 'W';
      if(a <= i && i < b) K += G[i][j] != 'B';
      if(b <= i) K += G[i][j] != 'R';
    }
    ans = min(ans, K);
  }

  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3236