akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()


using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

//bit全探索
vector<ll>bitSearch(int bit,int n){
    vector<ll>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    S.push_back(1e9);
    return S;
}

int main(){
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d), total(d);
    rep(i, d){
        cin >> p[i] >> c[i];
        total[i] = 100 * (i + 1) * p[i] + c[i];
    }
    
    ll res = INF;
    for(int bit = 0; bit < (1 << d); bit++){
        vector<ll> S = bitSearch(bit, d);
        ll sum = 0, cnt = 0;
        for(ll s : S){
            if(s == INF)break;
            sum += total[s];
            cnt += p[s];
        }
        ll rem = g - sum;
        if(g <= sum){
            res = min(res, cnt);
        }
        else {
            for(int i = d - 1; i >= 0; i--){
                if(i == *lower_bound(ALL(S), i))continue;
                
                REP(j, 1, p[i] - 1){
                    if(sum >= g)break;
                    sum += 100 * (i + 1);
                    cnt++;
                }
                if(sum >= g)break;
            }
            if(g <= sum)res = min(res, cnt);
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var S = ReadText().ToArray();
            S[3] = '8';
            return string.Join("", S);
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 26284
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int main() {
	ll n,h,w;
	scanf("%lld %lld %lld",&n,&h,&w);
	int ans=0;
	for(int i=0;i<n;i++){
		ll a,b;
		scanf("%lld %lld",&a,&b);
		if(a>=h && b>=w)
		    ans++;
	}
	printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

int main()
{
  lint n;
  cin >> n;
  int result=0;
  if(n<9){
    result = n;
  }else if(n<100){
    result = 9;
  }else if(n<999){
    result = 9+(n-99);
  }else if(n<10000){
    result = 909;
  }else if(n<99999){
    result = 909+(n-9999);
  }else{
    result = 90909;
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    Lcm(a,b)  ((a*b)/(__gcd(a,b)))
#define    clr(v,d)      memset( v, d ,sizeof(v))
typedef  long long     ll ;
typedef  unsigned long long     ull ;
const long double eps= (1e-9);
using namespace std;
using namespace __gnu_pbds;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
void GO(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int N=0;

int main(){
    GO();
    int k;
    string st;
    cin>>k>>st;

    if(sz(st)<=k) cout<<st<<"\n";
    else{
        for(int i=0;i<k;i++) cout<<st[i];
        cout<<"...\n";
    }
}

























Measured memory_bytes: 3592
#include<bits/stdc++.h>
//F:LCS	

using namespace::std;

const int SIZE = 3e3 + 1;
int DP[SIZE][SIZE];
int wayf[SIZE][SIZE];//0 diagonal, 1 cad_abajo, 2 cad_arriba

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

	string A,B;
	cin >> A >> B;

	int N = A.size();
	int M = B.size();

	A = " " + A; B = " " + B;

	for(int i = 1;i <= N;i++){
		for(int j = 1;j <= M;j++){
			if(A[i] == B[j]){
				DP[i][j] = DP[i - 1][j - 1] + 1;
				wayf[i][j] = 0;
			}
			else{
				if(DP[i][j - 1] > DP[i - 1][j]){
					DP[i][j] = DP[i][j - 1];
					wayf[i][j] = 1;
				}
				else{
					DP[i][j] = DP[i - 1][j];
					wayf[i][j] = 2;
				}
			}
		}
	}

	string cad;
	int sol = DP[N][M];
	while(N && M){
		int aux = wayf[N][M];
		if(aux == 0){
			cad += A[N];
			N--;
			M--;
		}
		else if(aux == 1)
			M--;
		else
			N--;
	}

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

	cout << cad << '\n';

	return 0;
}


Measured memory_bytes: 70656
#include<iostream>
#include<vector>
using Int = long long;

int main() {

	Int N;
	std::cin >> N;

	std::vector<Int> a(N);
	for (int i = 0; i < N; i++) std::cin >> a[i];

	Int res = 0;
	for (int i = 0; i < N; i++) {
		if (a[i] % 2)res++;
	}
	
	std::cout << (res % 2 ? "NO" : "YES") << std::endl;

}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;

int n,k,mi = 0x3f3f3f3f;
int a[105];
int dp[100005];

int main(){
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a[i]);
		mi = min(mi,a[i]);
	}
	for(int i = 0;i < mi;i ++) dp[i] = -1;
	for(int i = mi;i <= k;i ++){
		int mi = 1;
		for(int j = 1;j <= n;j ++){
			if(i - a[j] >= 0) mi = min(mi,dp[i - a[j]]);
		}
		if(mi == -1) dp[i] = 1;
		else dp[i] = -1;
	}
	if(dp[k] == 1) printf("First\n");
	else printf("Second\n");
	return 0;
}
//

Measured memory_bytes: 640
#include <stdio.h>

int main() {
    int x, y, syoukin = 0;
    scanf("%d %d", &x, &y);
    switch (x) {
        case 1:
            syoukin = syoukin + 300000;
            break;
        case 2:
            syoukin = syoukin + 200000;
            break;
        case 3:
            syoukin = syoukin + 100000;
            break;
    }
    switch (y) {
        case 1:
            syoukin = syoukin + 300000;
            break;
        case 2:
            syoukin = syoukin + 200000;
            break;
        case 3:
            syoukin = syoukin + 100000;
            break;
    }
    if (x == 1 && y == 1) {
        syoukin = syoukin + 400000;
    }
    printf("%d\n", syoukin);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define p(a,b) printf(a,b);
#define o(s) cout<< s << endl;
typedef long long LL;
template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int main()
{
    string s="";
    cin >> s;
    rep(i,s.size()-8)cout<<s[i];
    cout<<endl;
}


Measured memory_bytes: 256
n,x,m = map(int, input().split())

#xに何番目にきたかを記録していく。-1じゃなければ一回以上きている
table = [-1] * m
extra = []
l = 0
total = 0
#table[x]は周期が始まる点
while table[x] == -1:
    
    extra.append(x)
    table[x] = l
    l += 1
    total += x
    x = (x*x) % m 

#周期の長さ
c = l - table[x]

#周期の和
s = 0
for i in range(table[x], l):
    s += extra[i]

ans = 0

#周期がnより長い場合
if n <= l:
    for i in range(n):
        ans += extra[i]
else:
    #最初の一週目を足す
    ans += total
    n -= l
    #残りの周期の周の和を足す
    ans += s*(n//c)
    n %= c

    for i in range(n):
        ans += extra[table[x]+i]

print(ans)


Measured memory_bytes: 69696
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1e18;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};

ll BF(ll s,vector<vector<PL>>& v ,ll V){
  vector<ll> d(V,INF);
  d[s]=0;
  ll cnt=0;
  bool update=false;

  while(1){
    update=false;
    for(int i=0;i < V;i++)
    {
      for(int j=0;j < siz(v[i]);j++)
      {
        if(d[i] != INF && d[v[i][j].fi]> d[i]+v[i][j].se){
          update=true;
          d[v[i][j].fi]=d[i]+v[i][j].se;
          if(cnt==V-1){
              d[v[i][j].fi]=-INF;
          }
        }
      }
    }
    
    if(!update)break;
    cnt++;

    if(d[V-1]<-1e12){
        return INF;
    }else if(cnt>2*V){
        break;
    }
  }
  return d[V-1];
}

ll n,m,p,ans;
vector<vector<PL>> v(2510,vector<PL>(0));

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

    cin>>n>>m>>p;
    
    ll a,b,c;
    rep(i,m){//here?kasukasukasu
        cin>>a>>b>>c;
        a--;b--;
        v.at(a).pb({b,-(c-p)});
    }

    ans=BF(0,v,n);

    if(ans==INF){
        cout<<-1<<endl;
    }else{
        cout<<max(-ans,0ll)<<endl;
    }
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> freq((int) 1e6 + 1, 0);
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    freq[val]++;
  }
  vector<int> ans;
  for (int i = 0; i <= 1000000; i++) {
    while (freq[i]) {
      freq[i]--;
      ans.push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      cout << ' ';
    }
    cout << ans[i];
  }
  cout << '\n';
  return 0;
}



Measured memory_bytes: 15080
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <limits>
using std::endl;
using std::cin;
using std::cout;
using std::vector;
using std::pair;
using std::string;
using std::map;
using std::multimap;
using std::make_pair;
using std::sort;
using std::reverse;

//std::numeric_limits<uint32_t>::max()
//for (uint32_t i = 0; i < N; i++){
//vector<uint32_t> A(N);

int main(void)
{
    string w;
    cin >> w;

    if (w == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (w == "Cloudy") {
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }
    return 0;
}


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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

Int dp[100];

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < (Int)n; i++) {
        cin >> a[i];
    }
    dp[0] = 1000;
    for (Int i = 1; i < n; i++) {
        for (Int j = 0; j < i; j++) {
            dp[i] = max(dp[i], dp[j]);
        }
        for (Int j = 0; j < i; j++) {
            if (a[i] <= a[j]) continue;
            dp[i] = max(dp[i], (dp[j] % a[j]) + a[i] * (dp[j] / a[j]));
        }
    }
    print(dp[n - 1]);
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main(){
	char ch;
	int numAlpha[26] = {0};

	while(cin >> ch){
		if('a' <= ch && ch <= 'z'){
			numAlpha[ch - 'a']++;
		}else if('A' <= ch && ch <= 'Z'){
			numAlpha[ch - 'A']++;
		}
	}

	for(int i = 0; i < 26; i++){
		cout << static_cast<char>('a'+i) <<  " : " << numAlpha[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3000
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#include<bits/stdc++.h>
using namespace std;

#if defined(DAIJOBU)
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif

#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int n, m;
char grid[30][30];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int dist[30][30], used[30][30];

bool isValid(int x, int y){
	if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#')return true;
	return false;
}

int bfs(int x, int y){
	used[x][y] = 1;
	queue<pii> q;
	q.push({x, y});
	while(!q.empty()){
		auto u = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int tx = u.fi + dx[i];
			int ty = u.se + dy[i];
			if(isValid(tx, ty) && !used[tx][ty]){
				used[tx][ty] = 1;
				dist[tx][ty] = dist[u.fi][u.se] + 1;
				q.push({tx, ty});
			}
		}
	}
	int res = 0;
	forn(i, 30){
		forn(j, 30)res = max(res, dist[i][j]);
	}
	return res;
}

int main(){
	FIO
	
	cin >> n >> m;
	forn(i, n)forn(j, m)cin >> grid[i][j];
	int ans = 0;
	forn(i, n){
		forn(j, m){
			if(grid[i][j] == '.'){
				memset(used, 0, sizeof used);
				memset(dist, 0, sizeof dist);
				ans = max(ans, bfs(i, j));
			}
		}
	}
	cout << ans;
	return 0;
}


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

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

    rep2(i,3){
        if(i == a || i == b) continue;
        ans = i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
int main(){
    int a,b,n;
    while(scanf("%d",&n),n){
        int asum=0,bsum=0;
        for(int i=0;i<n;i++){
            scanf("%d %d",&a,&b);
            if(a>b){
                asum+=a+b;
            }
            else if(a<b){
                bsum+=a+b;
            }
            else{
                asum+=a;
                bsum+=b;
            }
        }
        printf("%d %d\n",asum,bsum);
    }
    return 0;
}

Measured memory_bytes: 1028
// AUTHOR : Kishan Srivastav
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}

int main() {
	ios
#ifndef ONLINE_JUDGE
	in;
	out;
#endif

	int x;
	cin>>x;
	if(x == 0) cout<<"1"<<endl;
	else cout<<"0"<<endl;
}

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

int main(){
	int i;
	string S;
	cin >> S;
	vector<int> ans(S.size(), 0);
	for(i = 0; i < S.size(); ){
		int j, k;
		for(j = i; j < S.size() && S[j] == 'R'; j++);
		for(k = j; k < S.size() && S[k] == 'L'; k++);
//		printf("(i, j, k) = (%d, %d, %d)\n", i, j, k);
		ans[j - 1] = k / 2 - i / 2;
		ans[j] = k - i - ans[j - 1];
		if(j % 2 == 1){
			swap(ans[j - 1], ans[j]);
		}
		i = k;
	}
	for(i = 0; i < S.size(); i++){
		printf("%d ", ans[i]);
	}
	printf("\n");
	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> a(M);
  vector<int> b(M);
  
  for(int i=0; i<M; i++){
    cin >> a.at(i);
    cin >> b.at(i);
  }
  
  int count = 0;
  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      if(a.at(j) == i+1 || b.at(j) == i+1){
        count++;
      }
    }
    cout << count << endl;
    count = 0;
  }
}


Measured memory_bytes: 256
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let s: String = read!();
    let t: String = read!();
    let s = s.chars().collect_vec();

    let mut b = false;
    for i in 0..s.len() {
        b = b
            || t == (format!(
                "{}{}",
                s[i..].iter().collect::<String>(),
                s[..i].iter().collect::<String>()
            ))
    }

    let ans = if b { "Yes" } else { "No" };
    println!("{}", ans);
}


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

using namespace std;

int main(){
  string S,T;
  cin>>S>>T;
  unsigned long long h=0;
  unsigned long long B=99999999947ULL;
  for(int i=0;i<T.size();i++){
    h=h*B+T[i];
  }
  vector<unsigned long long> hashes;
  unsigned long long b=1;
  for(int i=T.size()-1;i>=0;i--){
    for(char c='a';c<='z';c++){
      if(T[i]!=c){
	hashes.push_back(h-T[i]*b+c*b);
      }
    }
    for(char c='A';c<='Z';c++){
      if(T[i]!=c){
	hashes.push_back(h-T[i]*b+c*b);
      }
    }
    b*=B;
  }
  sort(begin(hashes),end(hashes));
  unsigned long long sh=0;
  for(int i=0;i<T.size();i++){
    sh=sh*B+S[i];
  }
  int ans=0;
  for(int i=0;;i++){
    ans+=binary_search(begin(hashes),end(hashes),sh);
    if(i+T.size()>=S.size())break;
    sh=sh*B-b*S[i]+S[i+T.size()];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 69472
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Collections;
import java.awt.Point;
import java.util.Map;
import java.util.HashMap;


public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int ka = Integer.parseInt(nk[1]);
        
        int[] fixed = new int[n+1];
        for (int i = 0; i < ka; i++) {
            String[] line = br.readLine().split(" ");
            fixed[Integer.parseInt(line[0])] = Integer.parseInt(line[1]);
        }
        
        //i日目まで、今日、昨日
        long[][][] dp = new long[n+1][4][4];
        dp[0][0][0] = 1;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    for (int l = 0; l < 4; l++) {
                        if (j==k && k==l) continue;
                        if (fixed[i] > 0 && fixed[i] != j) continue;
                        
                        dp[i][j][k] += dp[i-1][k][l];
                        if (dp[i][j][k] >= 10000) dp[i][j][k] -= 10000;
                        //System.out.println(dp[i][j][k]);
                    }
                }
            }
        }
        
        long ans = 0;
        for (int k = 1; k < 4; k++) {
            for (int l = 1; l < 4; l++) {
                ans += dp[n][k][l];
                if (ans >= 10000) ans -= 10000;
            }
        }
        
        //System.out.println(dp[1][1][1]);
        System.out.println(ans);
    }
}






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

int main() {
	string N;
	cin >> N;
	
	int dp[2][10][8];
	for (int i = 0;i < 2;++ i) for (int j = 0;j < 10;++ j) for (int k = 0;k < 8;++ k) dp[i][j][k] = 0;

	int tmp = N[0] - '0', ans = 0;
	if (tmp > 3) {
		dp[0][0][1] = 1;
		if (tmp > 5) {
			dp[0][0][2] = 1;
			if (tmp > 7) dp[0][0][4] = 1;
			else if (tmp == 7) dp[1][0][4] = 1;
		} else if (tmp == 5) dp[1][0][2] = 1;
	} else if (tmp == 3) dp[1][0][1] = 1;
	
	for (int i = 1;i < N.size();++ i) { // 桁数を求めたいのに固定したとき
		tmp = N[i] - '0';
		for (int j = 0;j < 8;++ j) {
			for (int k = 1;k < 8;k <<= 1) dp[0][i][j | k] += dp[0][i - 1][j];
			if (tmp > 3) {
				dp[0][i][j | 1] += dp[1][i - 1][j];
				if (tmp > 5) {
					dp[0][i][j | 2] += dp[1][i - 1][j];
					if (tmp > 7) dp[0][i][j | 4] += dp[1][i - 1][j];
					else if (tmp == 7) dp[1][i][j | 4] += dp[1][i - 1][j];
				} else if (tmp == 5) dp[1][i][j | 2] += dp[1][i - 1][j];
			} else if (tmp == 3) dp[1][i][j | 1] += dp[1][i - 1][j];
		}
	}
	ans = dp[0][N.size() - 1][7] + dp[1][N.size() - 1][7];
	
	for (int i = 0;i < 2;++ i) for (int j = 0;j < 10;++ j) for (int k = 0;k < 8;++ k) dp[i][j][k] = 0;
	dp[0][1][1] = dp[0][1][2] = dp[0][1][4] = 1;
	for (int i = 2;i < N.size();++ i) { // Nより小さい桁数の場合全て
		for (int j = 0;j < 8;++ j) for (int k = 1;k < 8;k <<= 1) dp[0][i][j | k] += dp[0][i - 1][j];
		ans += dp[0][i][7];
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

dpすると解ける
*/

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

int n;
double v[51];

void solve(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
    sort(v,v+n);
    double tmp=v[0];
    for(int i=1; i<n; i++){
        tmp=(tmp+v[i])/2;

    }
    printf("%.8f\n", tmp);
}

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
// C++ program to toggle cases of a given
// string.
#include <iostream>
#include <cstring>
using namespace std;

// function to toggle cases of a string
void toggle(string str)
{
	int length = str.length();
	for (int i = 0; i < length; i++) {
		int c = str[i];
		if (islower(c))
			cout <<  "a";
		else if (isupper(c))
			cout << "A";
	}
}

// Driver Code
int main()
{
	string str ;cin>>str;
	toggle(str);
	return 0;
}


Measured memory_bytes: 3580
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Control.Monad
import Control.Arrow
import Data.Ord


r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine



main :: IO ()
main = do
    [h,w] <- r'
    print $ if h == 1 || w == 1 then 1 else ceiling (fromIntegral w/2) * h - (if odd w then floor (fromIntegral h/2) else 0)



Measured memory_bytes: 380
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n,m;
    cin>>n>>m;
    map<pair<ll,ll>,vector<pair<pair<ll,ll>,ll> > > v;  // adjList
    map<ii, int> visited;
    map<ii, ll>  distance;

    for(ll i=0;i<m;i++){
        ll p,q,c;
        cin>>p>>q>>c;
        v[mp(p,c)].pb(mp(mp(q,c),0));
        v[mp(q,c)].pb(mp(mp(p,c),0));
        v[mp(p,c)].pb(mp(mp(p,0),0));
        v[mp(p,0)].pb(mp(mp(p,c),1));
        v[mp(q,c)].pb(mp(mp(q,0),0));
        v[mp(q,0)].pb(mp(mp(q,c),1));

        visited[mp(p,c)]=0;
        visited[mp(q,c)]=0;
        visited[mp(p,0)]=0;
        visited[mp(p,0)]=0;

        distance[mp(p,0)]=1e17;
        distance[mp(p,c)]=1e17;
        distance[mp(q,c)]=1e17;
        distance[mp(q,0)]=1e17;
    }

    priority_queue< pair<ll,ii> , vector<pair<ll,ii> >, greater<pair<ll,ii> > > pq;

    distance[mp(1,0)]=0;
    pq.push(mp(0,mp(1,0)));

    while(!pq.empty()){
        ll u=pq.top().se.fi;  //station
        ll t=pq.top().se.se;  //platform
        pq.pop();
        if(visited[mp(u,t)]!=0)
            continue;
        visited[mp(u,t)]=1;
        for(ll i=0;i<v[mp(u,t)].size();i++){
            ll station   = v[mp(u,t)][i].fi.fi;
            ll platform  = v[mp(u,t)][i].fi.se;
            ll dis =  v[mp(u,t)][i].se;

            if(distance[mp(station,platform)]>distance[mp(u,t)]+dis){
                distance[mp(station,platform)]=distance[mp(u,t)]+dis;
                pq.push(mp(distance[mp(station,platform)],mp(station,platform)));
            }
        }
    }
    if(visited[{n,0}]!=0)
        cout<<distance[{n,0}];
    else
        cout<<-1;
    return 0;
}


Measured memory_bytes: 145072
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt

readIntList = map readInt . BS.words

getIntList = readIntList <$> BS.getLine

main = do
  [n, k, s] <- getIntList
  let t = if s == 10 ^ 9 then 1 else s + 1
  putStrLn $ concat (intersperse " " (map (\x -> show x) (replicate k s ++ replicate (n - k) t)))


Measured memory_bytes: 5520
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for (int i = 0; i < N; i++)
    cin >> S[i];
  sort(S.begin(), S.end());
  string Ans;
  for (int i = 0; i < N; i++)
    Ans += S[i];
  cout << Ans << endl;
  return 0;
}

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

using namespace std;
#define ll long long
#define db long double
#define all(a) a.begin(),a.end()
#define pb push_back
#define f(i,l,u) for(ll i=l;i<u;i++)
#define lb lower_bound
#define ub upper_bound
#define pii pair<ll,ll> 

unsigned long long fac[200001]; 
void powe(ll p)
{

    fac[0] = 1; 
    for (int i = 1; i <= 200001; i++) 
        fac[i] = (fac[i - 1] * i) % p; 

}

unsigned long long power(unsigned long long x, 
                         ll y, ll p) 
{ 
    unsigned long long res = 1; // Initialize result 
  
    x = x % p; // Update x if it is more than or 
    // equal to p 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
unsigned long long modInverse(unsigned long long n, ll p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
unsigned long long nCrModPFermat(unsigned long long n, 
                                 ll r, ll p) 
{ 
    // Base case 
    if (r == 0) 
        return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
}


int main() {
 ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll t=1;
//cin>>t;
while(t--)
{
ll n,d;
cin>>n>>d;
ll sum=0;
f(i,0,n)
{
    ll a,b;
    cin>>a>>b;
    db e=(db)a;
    db f=(db)b;
    db val=e*e;
    db vel=f*f;
    val+=vel;
    val=sqrt(val);
    if(val<=d)
    sum++;
    
}
    cout<<sum<<endl;
    
    
}




return 0;
}

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

int main() {
  int n, check;
  long long a[3], min;
  set<int> b;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> a[i];
  }
  sort(a, a+n, greater<long long>());
  min = a[0]-a[1];
  check=0;
  if(n==3) {
    if(min > a[1]-a[2]) {
      min=a[1]-a[2];
      check=1;
    }
  }

  if(check==1) {
    while(a[1]!=a[2]) {
      if(a[1]>a[2]) a[1]=a[1]-a[2];
      else a[2]=a[2]-a[1];
    }
  }
  while(a[0]!=a[1]) {
    if(a[0]>a[1]) a[0]=a[0]-a[1];
    else a[1]=a[1]-a[0];
  }

  for(int i=1; i*i<=a[0]; i++) {
    if(a[0]%i==0) {
      b.insert(i);
      b.insert(a[0]/i);
    }
  }
  for(set<int>::iterator it=b.begin(); it!=b.end(); it++) {
    cout << *it << endl;
  }
  return 0;
}


Measured memory_bytes: 1220
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <set>
#include <vector>

long solve(int n, const std::string& s)
{
  std::vector<int> rr;
  std::vector<int> gg;
  std::vector<int> bb;
  for (int i = 0; i < n; ++i) {
    switch (s[i]) {
    case 'R':
      rr.push_back(i);
      break;
    case 'G':
      gg.push_back(i);
      break;
    case 'B':
      bb.push_back(i);
      break;
    default:
      throw s[i];
    }
  }

  long result = rr.size() * gg.size() * bb.size();
  std::set<std::tuple<int, int, int>> dame;
  for (auto r : rr) {
    for (auto g : gg) {
      int a = std::min(r, g);
      int b = std::max(r, g);

      int d = b - a;
      if (b + d < static_cast<int>(s.size()) && s[b + d] == 'B') {
        dame.emplace(a, b, b + d);
      }

      if (a - d >= 0 && s[a - d] == 'B') {
        dame.emplace(a - d, a, b);
      }

      if (d % 2 == 0 && s[a + d / 2] == 'B') {
        dame.emplace(a, a + d / 2, b);
      }

    }
  }
  return result - dame.size();
}

int main()
{
  int n;
  std::string s;
  std::cin >> n >> s;

  std::cout << std::setprecision(20);
  std::cout << solve(n, s) << std::endl;
}


Measured memory_bytes: 59188
#include <iostream>

using namespace std;

int main(void){
    int inp,a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cin >> inp;
    cout << a[inp-1];
    return 0;
}

Measured memory_bytes: 256
N=int(input())
S=input()

E=[0]*N
W=[0]*N

for i in range(N):
    if S[i]=="E":
        E[i]+=1
    else:
        W[i]+=1

for i in range(1,N):
    E[i]=E[i-1]+E[i]
for i in range(N-2,-1,-1):
    W[i]=W[i+1]+W[i]

SUM=[E[i]+W[i] for i in range(N)]
print(N-max(SUM))

Measured memory_bytes: 39200
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
#define ran 6200
int n,m;string s;
vector<int> A, B;
tuple<int, int, bool> a[ran];
pair<string, int> c[ran];
vector<string> dp[ran];
bool g[ran];
void upd(vector<string>&A,const vector<string>&B) {
	string a = "", b = "";
	for (auto c : A)a += c;
	for (auto c : B)b += c;
	if (a < b)A = B;
}
int main() {
	cin >> n >> s;
	m = s.length();
	for (int i = 0; i < m; i++) {
		if (s[i] == 'a')A.push_back(i);else
			B.push_back(i);
		c[i].second = -1;
	}
	for (int i = 0; i < n; i++) {
		if (A[i] < B[i])
			a[i] = make_tuple(A[i], B[i], false);
		else
			a[i] = make_tuple(B[i], A[i], true);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (!get<2>(a[i])) {
			c[get<0>(a[i])] = make_pair("ab", get<1>(a[i]) + 1);
		}
		else {
			memset(g, 0, sizeof(g));
			int L = get<0>(a[i]), R = get<1>(a[i]);
			for (int j = 0; j < n; j++){
				int x = get<0>(a[j]), y = get<1>(a[j]);
				if (x >= L && x <= R && get<2>(a[j])) {
					R = max(R, y);
					g[x] = g[y] = true;
				}
			}
			string cur = "";L = R = -1;
			for (int j = 0; j < m; j++)if (g[j]) {
				if (L == -1)L = j;
				R = j;
				cur += s[j];
			}
			c[L] = make_pair(cur, R + 1);
		}
	}
	dp[0].clear();
	for (int i = 0; i < m; i++){
		auto vs = dp[i];
		upd(dp[i + 1], dp[i]);
		if (c[i].second != -1) {
			while (vs.size() > 0 && vs.back() < c[i].first)
				vs.pop_back();
			vs.push_back(c[i].first);
			upd(dp[c[i].second], vs);
		}
	}
	string out = "";
	for (auto it : dp[m])
		out += it;
	puts(out.c_str());
	return 0;
}

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


Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<vector<vector<int>>> d(2, vector<vector<int>>(m, vector<int>(m, INF)));
        for(int i=0; i<m; ++i) {
            d[0][i][i] = d[1][i][i] = 0;
        }
        for(int i=0; i<n; ++i) {
            int a, b, cost, time;
            cin >> a >> b >> cost >> time;
            a--; b--;
            d[0][a][b] = d[0][b][a] = cost;
            d[1][a][b] = d[1][b][a] = time;
        }
 
        for(int k=0; k<m; ++k) {
            for(int i=0; i<m; ++i) {
                for(int j=0; j<m; ++j) {
                    d[0][i][j] = min(d[0][i][j], d[0][i][k] + d[0][k][j]);
                    d[1][i][j] = min(d[1][i][j], d[1][i][k] + d[1][k][j]);
                }
            }
        }
 
        int k;
        cin >> k;
        for(int i=0; i<k; ++i) {
            int p, q, r;
            cin >> p >> q >> r;
            p--; q--;
            cout << d[r][p][q] << endl;
        }
    }
}

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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	int n;
	cin >> n;
	vector<int> s;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		s.push_back(a);
	}
	sort(s.begin(), s.end(), greater<int>());
	int a = 0;
	int b = 0;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			a =a + s[i];
		}
		else {
			b = b + s[i];
		}
	}
	cout << a - b;
}

Measured memory_bytes: 256
N,M=map(int,input().split())

minG=1
maxG=N
for i in range(M):
    L,R=map(int,input().split())
    if L>minG:
        minG=L
    if R<maxG:
        maxG=R

if minG<=maxG:
    print(maxG-minG+1)
else:
    print(0)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define double ld
#define faster ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;
///------------------------------------------------------------------------
const int inf=1e18;
const int mod=1e9+7;
ifstream in("input.txt");
ofstream out("output.txt");
signed main()
{
    int n;
    cin>>n;
    vector<vector<int> >vec(n,vector<int>(3));
    for(int i=0; i<n; i++)
        cin>>vec[i][0]>>vec[i][1]>>vec[i][2];
    vector<vector<int> >dp(n,vector<int>(3));
    dp[0][0]=vec[0][0];
    dp[0][1]=vec[0][1];
    dp[0][2]=vec[0][2];
    for(int i=1; i<n; i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+vec[i][0];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+vec[i][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+vec[i][2];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
    return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    ll N,K; cin >> N >> K;
    vector<ll> A(N), B(N);
    REP(i,N){
        cin >> A[i];
        B[i] = A[i];
    }

    SORT(A);
    SORT(B); REVERSE(B);

    ll xl=-1000000000000000000,xr=-xl,X=(xl+xr)/2;
    while(xr-xl>1){
        ll tmp = 0;
        REP(i,N-1){
            if(A[i] < 0){
                ll l=-1, r=N-i-1, n=(l+r)/2;
                while(r-l>1){
                    if(A[i]*B[n] <= X) l = n;
                    else r = n;
                    n = (l+r)/2;
                }
                tmp += r;
            }
            else{
                ll l=i, r=N, n=(l+r)/2;
                while(r-l>1){
                    if(A[i]*A[n] <= X) l = n;
                    else r = n;
                    n = (l+r)/2;
                }
                tmp += max((ll)0,r-i-1);
            }
        }
        if(tmp < K) xl = X;
        else xr = X;
        X = (xl+xr)/2;
    }
    cout << xr << endl;
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long x,k,d;
	cin>>x>>k>>d;
	x=abs(x);
	if(x/d>k){
		cout<<x-k*d;
	}
	else{
		long long y=x%d;
		long long t=(x-y)/d;
		k-=t;
		if(k%2)
		y=abs(y-d);
		cout<<y;
	}
}

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

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

typedef pair<int,int> P;
struct graph{

    vector<P> ade;

    vector<int> ids;
    map<int,int> mp;
    vector<int> par;
    int ans=0;
    vector<bool> isc;


    void add_v(int x){
        if(mp.find(x)==mp.end()){
            par.push_back(par.size());
            isc.push_back(false);
            mp[x]=ids.size();
            ids.push_back(x);
        }
    }
    int find(int x){
        if(par[x]==x)return x;
        else return par[x]=find(par[x]);
    }
    void add_e(int x,int y){
        add_v(x);add_v(y);
        x=mp[x];x=find(x);
        y=mp[y];y=find(y);
        if(x==y){
            if(!isc[x]){
                ade.push_back({ids[x],ids[x]});
                ans++;isc[x]=true;
            }

        }
        else{
            if(isc[x]&&isc[y])return;
            par[x]=y;
            if(isc[x])isc[y]=true;
            ans++;
            ade.push_back({ids[x],ids[y]});
        }
    }
    int query(){
        return ans;
    }
};

void merge(graph &a,graph &b){
    if(a.ade.size()<b.ade.size())swap(a,b);
    rep(j,b.ade.size()){
        int l=b.ade[j].first;
        int r=b.ade[j].second;
        a.add_e(l,r);

    }

}
vector<P> es;


int ans[1<<17];

int n;
vector<int> G[1<<17];
int c[1<<17],d[1<<17];

int depth[1<<17];
void ddfs(int id,int fr){
    depth[id]=1;
    rep(j,G[id].size()){
        int to=G[id][j];
        if(to==fr)continue;
        ddfs(to,id);
        depth[id]+=depth[to];
    }
}

void sdfs(int id,int fr){
    es.push_back({c[id],d[id]});
    rep(j,G[id].size()){
        int to=G[id][j];
        if(to==fr)continue;
        sdfs(to,id);
    }
}

graph dfs(int id,int fr){
    graph g;
    g.add_e(c[id],d[id]);
    rep(j,G[id].size()){
        int to=G[id][j];
        if(to==fr)continue;
        graph nex=dfs(to,id);
        merge(g,nex);
    }
    ans[id]=g.query();
    return g;
}
void solve(){
    int n,k;cin>>n>>k;
    rep(i,n-1){
        int u,v;cin>>u>>v;u--;v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    rep(i,n){
        cin>>c[i]>>d[i];
        c[i]--;d[i]--;
    }
    ddfs(0,-1);
    dfs(0,-1);
    rep(i,n)cout<<ans[i]<<endl;

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


Measured memory_bytes: 59364
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
static const int INF (1<<30);

int N;
vector<int> prime;
int div_cnt[105], div_back[105];
int ans = 0;
int mul[5] = {3, 5, 15, 25, 75};

int isPrime(int x) {
  if (x < 2) return 0;
  else if (x == 2) return 1;

  if (x % 2 == 0) return 0;

  for (int i = 3; i*i <= x; i+=2) {
    if (x % i == 0) return 0;
  }

  return 1;
}


void dfs(int p, int cnt) {
  if (cnt == 75) {
    ans++;
    return;
  } else if (cnt > 75) {
    return;
  }

  if (p >= prime.size()) return;

  int idx = prime[p];

  for (int i = 0; i < 5; i++) {
    if (mul[i] > (div_cnt[idx]+1)) {
      dfs(p+1, cnt);
      break;
    } else {
      dfs(p+1, cnt * mul[i]);
      if (i == 4) dfs(p+1, cnt);
    }
  }
}

int main() {
  cin >> N;
  prime.push_back(1);
  for (int i = 2; i <= N; i++) {
    if (isPrime(i)) prime.push_back(i);
  }

  rep(i, 105) div_cnt[i] = 0, div_back[i] = 0;
  div_cnt[1] = 1;

  for (int i = 2; i <= N; i++) {
    int tmp = i;
    while (tmp > 1) {
      for (int j = 2; j <= i; j++) {
        if (tmp % j == 0) {
          div_cnt[j]++;
          tmp /= j;
          break;
        }
      }
    }
  }

  for (int i = N; i >= 1; i--) {
    div_back[i] = div_cnt[i] + div_back[i+1];
  }

  dfs(0, 1);

  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

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; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  ui N, M; cin >> N >> M;
  vector<ll> cost(M);
  vector<ui> can(M);
  for (size_t i = 0; i < M; i++){
    ui b; cin >> cost[i] >> b;
    for (ui cnt = 0; cnt < b; ++cnt){
      ui c; cin >> c;
      can[i] |= 1 << (c - 1);
    }
  }
  ui inf = 1 << N;
  vector<vector<ll>> dp(M + 1, vector<ll>(inf, -1));
  dp[0][0] = 0;
  for(ui row = 1; row < dp.size(); ++row)
  {
    ui itr = inf - 1;
    dp[row][0] = 0;
    while (itr != 0xFFFFFFFF)
    {
      auto jump_to = itr | can[row - 1];
      auto& jump_res = dp[row][jump_to];
      auto& cur_cost = dp[row - 1][itr];

      if(cur_cost != -1){
        if(dp[row - 1][jump_to] != -1){
          if(jump_res != -1){
            chmin(jump_res, cur_cost + cost[row - 1]);
          }else{
            jump_res = std::min(dp[row - 1][jump_to], cur_cost + cost[row - 1]);
          }
        }else{
          if(jump_res != -1){
            chmin(jump_res, cur_cost + cost[row - 1]);
          }else{
            jump_res = cur_cost + cost[row - 1];
          }
        }
      }
      --itr;
    }
    for(ui i = 0; i < dp[row].size(); ++i){
      if(dp[row][i] == -1
      && dp[row - 1][i] != -1){
        dp[row][i] = dp[row - 1][i];
      }
    }
  }
  
  auto ans = dp.back().back();  
  cout << ans << CRLF;
  return;
}

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

  solve();

  return 0;
}


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

int main() {
  string S;
  cin >> S;
  int c=0;
  for(int i=0; i<3; i++){
    if(S.at(i)=='o'){
      c++;
    }
  }
  cout << 700+c*100 << endl;
}


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

using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,k,h) for(int i = k; i < h; ++i)
#define rep3(i,k,h) for(int i = k; i <= h; ++i)
#define INF LLong_MAX // long long INF
#define inf INT_MAX // int inf

typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;


int main() {
    int n;
    cin >> n;
    ll ans = 1, mod = 1e9+7;
    for(int i = 1; i < n+1; i++) {
         ans *= i;
         ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll gcd(ll(a), ll(b)) {
	ll c = a;
	while (a % b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return b;
}




int main() {
	ll N, K;
	cin >> N >> K;
	double sum = 0,ma=0;
	vector<ll> p(N);
	rep(i, N) {
		cin >> p.at(i);
		if (i < K) {
			sum += (p.at(i)+1);
			ma = max(ma, sum);
		}
		else {
			sum += ((p.at(i) + 1));
			sum -= ((p.at(i - K) + 1));
			ma = max(ma, sum);
		}
		
	}
	double E = double(ma/2);
	cout << fixed << setprecision(10);
	cout << E << endl;
}



Measured memory_bytes: 4824
#include<stdio.h>
int main(void)
{
	int n,a=0,i;
	scanf("%d", &n);
	for(i=n; i>0; i--)
	{
		if(i<100000&&i>9999)
		a++;
		if(i<1000&&i>99)
		a++;
		if(i<10)
		a++;
	}
	printf("%d\n", a);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
using namespace std;
//cout << fixed << setprecision(0)
int main() { 
  int a,b,c;cin >> a >> b >> c;
  int ans;
  if(a%2==b%2){
    if(b%2!=c%2){
      a++;b++;ans++;
    }
  }else{
    if(b%2==c%2){
      b++;c++;ans++;
    }else{
      a++;c++;ans++;
    }
  }
  int r[3] = {a,b,c};
  sort(r,r+3);
  cout << ans+(r[2]-r[1])/2+(r[2]-r[0])/2 << endl;
}


Measured memory_bytes: 256