akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int x,t;
  cin >> x >> t;
  pr(max(0,x-t));
}

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


Measured memory_bytes: 256
import numpy as np

h, w = map(int, input().split())
N = int(input())
a = np.array(list(map(int, input().split())))

x = np.argsort(a)
x = x[::-1]
a = a[x]

tmp = np.zeros(h*w)

k = 0
for i in range(N):
    for j in range(a[i]):
        tmp[k] = x[i]+1
        k += 1

tmp = tmp.reshape((h,w))

for y in range(h):
    if y&1 == 0:
        for x in range(w):
            print(int(tmp[y][x]), end=" ")
        print()
    else:
        for x in range(w-1, -1, -1):
            print(int(tmp[y][x]), end=" ")
        print()


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

void doRoutine() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(322179);
#ifdef LOCAL
    freopen("/home/max/alg/clion_main/input.txt", "rt", stdin);
    freopen("/home/max/alg/clion_main/output.txt", "wt", stdout);
#endif
}

#define DBG(VAR) cerr << #VAR << ": " << VAR << endl

#define all(x) x.begin(), x.end()
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vc vector
#define $ make_pair

#ifndef LOCAL
#define cerr if(0) cerr
#define DBG(...) (true)
#endif

#define D double
#define CD complex<D>
#define ll long long

// ----------------------------- CODE NOW ------------------------



signed main() {
    doRoutine();

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

    vb good(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        if (a[i] >= a[i + 1]) {
            good[i] = true;
        }
    }

    int ans = 0;
    for (int i = 0; i < n;) {
        if (!good[i]) {
            ++i;
        }
        else {
            int cur = 0;
            while (good[i]) {
                ++i;
                ++cur;
            }
            ans = max(ans, cur);
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){ 
  int n,k;
  cin >> n>>k;
  if(abs(n-k)>=2){
    cout << 0;
    return 0;
  }
  long long ans=1,ans_1=1,answer=0;
  for(int i=1;i<=n;i++){
    ans*=i;
    ans%=1000000007;
  }
  
  for(int j=1;j<=k;j++){
    ans*=j;
    ans%=1000000007;
  }
  if(n==k){
    ans*=2;
  }
  ans%=1000000007;
  cout << ans;
}
  

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

int main()
{
  int h,w; cin>>h>>w;
  vector<string> a(h);
  vector<int> c(26, 0);
  rep(i, h) cin>>a[i];
  rep(i, h) rep(j, w) c[a[i][j]-'a']++;

  int g1 = (h%2 && w%2);
  int g2 = 0;
  if (h%2) g2 += w/2;
  if (w%2) g2 += h/2;
  int g4 = (h/2) * (w/2);

  int cnt1 = 0;
  int cnt2 = 0;
  int cnt4 = 0;
  rep(i, 26) {
    int x = c[i]%4;
    if (x == 1) {
      cnt1++;
    } else if (x == 2) {
      cnt2++;
    } else if (x == 3) {
      cnt1++;
      cnt2++;
    }
    cnt4 += c[i]/4;
  }
  if (cnt4-g4 > 0) {
    cnt2 += (cnt4-g4)*2;
    cnt4 = g4;
  }
  if (cnt1==g1 && cnt2==g2 && cnt4==g4) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
x=range(100000)
a=0;ans=0;
n=int(raw_input())
l=raw_input().split(" ")
for i in range(100000):
    x[i]=0;
for i in range(n):
    y=int(l[i])
    if x[y]==1:
        a+=1
    else:
        x[y]=1

for i in range(100000):
    if x[i]==1 :
        ans+=1

print str(ans-a%2)

Measured memory_bytes: 14520
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int h, w;
char c[55][55];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int dfs(){
    using ppi = pair<pii, int>;
    queue<ppi> que;
    que.push({{0, 0}, 0});
    bool used[h][w];
    rep(i, h)rep(j, w) used[i][j] = false;
    while(!que.empty()){
        int x, y, d;
        tie(x, y) = que.front().fi; d = que.front().se;
        if(x == h-1 && y == w-1) return d;
        used[x][y] = true;
        que.pop();
        rep(i, 4){
            int nx = x+dx[i], ny = y+dy[i];
            if(0<=nx && nx<h && 0<=ny && ny<w && c[nx][ny] != '#' && !used[nx][ny]){
                used[nx][ny] = true;
                que.push({{nx, ny}, d+1});
            }
        }
    }
    return mod;
}

int main(){
    scanf("%d%d", &h, &w);
    int cnt = 0;
    rep(i, h)rep(j, w) scanf(" %c", &c[i][j]), cnt += (c[i][j] == '.');
    int d = dfs();
    printf("%d\n", d == mod ? -1 : cnt-1 - d);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int N, M, p[100000];
char S[100000][2];

int cmp(const void* a, const void* b){
    if(p[*(int*)a]-p[*(int*)b] != 0){
        return p[*(int*)a]-p[*(int*)b];
    }else if(p[*(int*)a]-p[*(int*)b] == 0){
        if(*(int*)a-*(int*)b>0){
            return 1;
        }else{
            return -1;
        }
    }
}

int main(void){
    scanf("%d %d", &N, &M);
    int i;
    int a[100000];
    for(i=0;i<M;i++){
        scanf("%d %s", &p[i], S[i]);
        a[i] = i;
    }

    qsort(a, M, sizeof(int), cmp);

    int wa=0, ac=0;
    int notAC=0;

    int flg=0;

    for(i=0; i<M; i++){
        if(i != 0 && p[a[i]]!=p[a[i-1]]){
            if(flg==0){
                wa-=notAC;
            }
            flg=0;
            notAC=0;
        }
        if(flg==0 && S[a[i]][0]=='W'){
            notAC++;
            wa++;
        }else if(flg==0 && S[a[i]][0]=='A'){
            ac++;
            flg=1;
        }
    }

    if(flg==0){
        wa-=notAC;
    }
    
    printf("%d %d", ac, wa);
    return 0;
}

Measured memory_bytes: 1532
use std::io::BufRead;

pub struct StdinReader<R: BufRead> {
    pub buf_reader: R,
    pub buf: String,
}
impl<R: BufRead> StdinReader<R> {
    pub fn new(r: R) -> Self {
        StdinReader {
            buf_reader: r,
            buf: String::with_capacity(10000),
        }
    }
}

#[macro_export]
macro_rules! input {
    ($reader : expr, $t : ty) => { // one variable
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().parse().unwrap(); 
                reader.buf.clear();
                tmp_var
            },
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty) => { // 2 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0], tmp_var[1])
            }
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty, $t2 : ty) => { // 3 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0], tmp_var[1], tmp_var[2])
            }
        }
    };
    ($reader : expr, $t : ty; $size : expr) => { // Vector
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                tmp_var
            }
        }
    };
}

fn main() {
    let handle = std::io::stdin();
    let mut r = StdinReader::new(handle.lock());

    let (mut x, mut y): (usize, usize) = input!(r, usize, usize);
    let mut count = 1;
    loop {
        if x * 2 > y { break; }
        else {
            x *= 2;
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    ll a[100002];
    for(int i = 0; i < n; i++) cin >> a[i];
    bool p[1000002];
    fill(p, p + 1000001, true);
    vector<int> prime;
    for(int i = 2; i <= 1000000; i++){
        if(p[i]) prime.push_back(i);
        for(int j = i * 2; j <= 1000000; j += i) p[j] = false;
    }
    int v[1000002]{0};
    for(int i = 0; i < n; i++){
        int r = a[i];
        for(int j : prime){
            if(j > 1000){
                v[r] = 1;
                break;
            }
            int k = 0;
            while(r % j == 0){
                r /= j;
                k++;
            }
            v[j] = max(v[j], k);
        }
    }
    ll m = 1;
    for(int j : prime){
        m = m * modpow(j, v[j]) % MOD;
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans = (ans + m * modpow(a[i], MOD - 2) % MOD) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6264
#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,Rcnt;
    Rcnt=0;
    cin>>n;
    vector<char> c(n);
    char tmp;
    rep(i,n){
        cin>>tmp;
        if (tmp=='R') Rcnt++;
        c[i]=tmp;
    }

    ll ans=0;
    rep(i,Rcnt){
        if(c[i]=='W'){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}



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

const int N = 50 + 1;
int n, m;
char g[N][N];
vector<pair<int, int> > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

bool isValid(int r, int c) {
  return (r >= 0 && c >= 0 && r < n && c < m && g[r][c] == '#');
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);    

    cin >> n >> m;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        cin >> g[i][j];

    for (int i = 0; i < n; i++){
      for (int j = 0; j < m; j++){
        if (g[i][j] == '#') cout << "#";
        else{
          int cnt_hash = 0;
          for (int k = 0; k < 8; k++){
            int x = i + dir[k].first;
            int y = j + dir[k].second;
            if (isValid(x, y))
              cnt_hash++;
          }
          cout << cnt_hash;
        }
      }
      cout << endl;
    }
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,count=0;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    for(int i=0; i<n; i=i+2)
    {
        if(a[i]%2!=0)
            count++;
    }
    cout<<count<<endl;

}


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

int n, A[20];

int solve(int i, int m){
	if (m == 0) return 1;
	if (i >= n) return 0;
	int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
	return res;
}

int main(){
	int q, m;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i];
	cin >> q;
	while (cin >> m){
		if (solve(0, m)) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
#define ALL(x) (x).begin(), (x).end()
#define LBi(x, n) lower_bound(ALL(x), n) - (x).begin()
#define ZIP(x) (x).erase(unique(ALL(x)), (x).end())
#define Pi pair<int, int>
#define Vi vector<int>

string s;

int main() {
	cin >> s;
	cout << 100 * (7 + (s[0] == 'o' ? 1 : 0) + (s[1] == 'o' ? 1 : 0) + (s[2] == 'o' ? 1 : 0)) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm> 
#include <cmath>
//#include <bitset>
//#include <deque>
#include <iterator>
#include <map> 
//#include <queue>
//#include <stack>
#include <string>
#include <vector>
#include <array>
//#include <tuple>
#include <unordered_map>
//#include <unordered_set>

using namespace std;

typedef long long ll;
struct __{__(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}__; 



int main() {
	ll n;
	cin >> n;
	int ans = 1e9 + 7;
	for (ll i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			int p1 = 0;
			int p2 = 0;
			int a = i, b = n / i;
			while (a) {
				p1++;
				a /= 10;
			}
			while (b) {
				p2++;
				b /= 10;
			}
			ans = min(ans,max(p1,p2));
		}
	}
	cout << ans;
} 
















Measured memory_bytes: 3592
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int n,a, b, c, d, e;
	cin >> n >> a >> b >> c >> d >> e;
	int m = min({ a,b,c,d,e });
	print((n+m-1)/m + 4);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  priority_queue<double> A;
  for (int i = 0; i < N; i++){
    double AA;
    cin >> AA;
    A.push(AA);
  }
  for (int i = 0; i < M; i++){
    double AA = A.top();
    AA /= 2.0;
    A.pop();
    A.push(AA);
  }
  long long int ans = 0;
  for (int i = 0; i < N; i++){
    ans += A.top();
    A.pop();
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

int main()
{
//	cut here before submit 
//	freopen("testcase.runlen", "r", stdin);
	string str = "";
	while (getline (cin, str ) ){
		int len = str.length();
		string res = "";
		int n;
		int i,j;

		i = 0;
		while (i < len){
			if (str[i] != '@'){
				res += str[i];
			}else{
				++i;
				int n = str[i] - '0';
				++i;
				char c = str[i];
				for (j = 0; j < n; ++j){
					res += c;
				} // end for
			} // end if
			++i;
		} // end while
	cout << res << endl;	

	} // end loop

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 20) + 10;
ll n,m,i,j,t,k;
ll a,b,c,d;
char A,C,X,Y,Z;
ll ans,MAX,MIN;
ll ax[2000500];
char cx[10000];
ll dx[12];
ll bx[2000500];
ll l[N],r[N];

int main()
{
    t=1;
    //scanf("%lld",&t);
    while(t--)
    {
    cin>>n>>k>>c;
    string s;
    cin>>s;
    ll cnt=k-1,mx=n;
    for(i=s.length()-1;i>=0;i--)
        if(s[i]=='o'&&i<mx&&cnt>=0) r[cnt]=i,mx=i-c,cnt--;
    cnt=0,mx=-1;
    for(i=0;i<s.length();i++)
        if(s[i]=='o'&&i>mx)
		   l[cnt]=i,mx=i+c,cnt++;
    for(i=0;i<k;i++)
        if(l[i]==r[i])
		    cout<<l[i]+1<<endl;
    }
	return 0;
}

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

int main(){
	ll h,w;
	cin >> h >> w;
	if(h == 1 || w == 1){
		cout << 1 << endl;
	}else{
		cout << (h*w+1)/2 << endl;
	}
    return 0;
}

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

int main(){
  string N;
  cin >> N;
  for(int i=1;i<=2;i++){
    if((N.at(i)==N.at(i-1))&&(N.at(i)==N.at(i+1))){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A = {'a': list(iss()), 'b': list(iss()), 'c': list(iss())}
    n = 'a'

    while True:
        if len(A[n]) > 0:
            n = A[n].pop(0)

        else:
            print(str.upper(n))
            exit()


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=105;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll inv(ll a,ll p){return qpow(a,p-2);}
int main()
{
    std::ios::sync_with_stdio(false);
    int h,w;
    while(cin>>h>>w)
    {
        char a[N][N];
        for(int i=1;i<=h;i++)
        {
            cin>>a[i];
            cout<<a[i]<<endl<<a[i]<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

struct Node{
	bool operator<(const struct Node &arg) const{
		return weight < arg.weight;
	};
	int from,to,weight;
};

int parent[101],height[101];

int getParent(int id){
	if(parent[id] == id)return id;
	else{
		return parent[id] = getParent(parent[id]);
	}
}

bool isSame(int a, int b){
	return getParent(a) == getParent(b);
}

void unite(int a,int b){
	int a_parent = getParent(a);
	int b_parent = getParent(b);

	if(a_parent == b_parent)return;

	if(height[a_parent] > height[b_parent]){
		parent[b_parent] = a_parent;
	}else{
		if(height[a_parent] == height[b_parent])height[b_parent]++;
		parent[a_parent] = b_parent;
	}
}


int main(){

	int V,E,ans,maximum,minimum;
	bool FLG;
	Node nodes[4950];

	while(true){
		scanf("%d %d",&V,&E);
		if(V == 0 && E == 0)break;

		for(int i = 1; i <= V; i++){
			parent[i] = i;
			height[i] = 0;
		}

		for(int i = 0; i < E; i++){
			scanf("%d %d %d",&nodes[i].from,&nodes[i].to,&nodes[i].weight);
		}

		sort(nodes,nodes+E);

		maximum = 0;
		minimum = BIG_NUM;

		for(int i = 0; i < E; i++){
			if(!isSame(nodes[i].from,nodes[i].to)){
				maximum = max(maximum,nodes[i].weight);
				minimum = min(minimum,nodes[i].weight);
				unite(nodes[i].from,nodes[i].to);
			}
		}

		FLG = true;
		for(int i = 2; i <= V; i++){
			if(!isSame(1,i)){
				FLG = false;
				break;
			}
		}

		if(!FLG){
			printf("-1\n");
			continue;
		}

		ans = maximum - minimum;

		for(int start = 0; start < E;start++){

			for(int i = 1; i <= V; i++){
				parent[i] = i;
				height[i] = 0;
			}

			maximum = 0;
			minimum = BIG_NUM;

			for(int i = start;i < E;i++){
				if(!isSame(nodes[i].from,nodes[i].to)){
					maximum = max(maximum,nodes[i].weight);
					minimum = min(minimum,nodes[i].weight);
					unite(nodes[i].from,nodes[i].to);
				}
			}

			FLG = true;
			for(int i = 2; i <= V; i++){
				if(!isSame(1,i)){
					FLG = false;
					break;
				}
			}

			if(FLG){
				ans = min(ans,maximum-minimum);
			}
		}

		printf("%d\n",ans);
	}

	return 0;
}

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

long long int a[5];
char name[5] = {'M', 'A', 'R', 'C', 'H'};

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < 5; j++) {
			if (s[0] == name[j]) {
				a[j]++;
				break;
			}
		}
	}
	long long int ans = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			for (int k = j + 1; k < 5; k++) {
				ans += a[i] * a[j] * a[k];
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
X = int(input())

for A in range(-118, 120):
    for B in range(-119, 119):
        A5 = pow(A,5)
        B5 = pow(B,5)
        if( (A5-B5) == X):
            ans = str(A) + ' ' + str(B)
            break

print(ans)

Measured memory_bytes: 9156
import java.util.*;
public class Main {
	public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
      
      String s = sc.next();
      int s1 = Integer.parseInt(s.substring(0,2));
      int s2 = Integer.parseInt(s.substring(2,4));
      boolean y1 = 0 <= s1;
      boolean m1 = 0<s1&& s1<13;
      boolean y2 = 0 <= s2;
      boolean m2 = 0<s2 && s2<13;
      String ans ="NA";
      if(y1 && y2 && m1 && m2){
        ans = "AMBIGUOUS";
      }else if(y1 && m2){
        ans = "YYMM";
      }else if(m1 && y2){
        ans = "MMYY";
      }

      // 出力
      System.out.println(ans);
	}
}

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

int main(){
    int N,tonari = 0;
    cin >> N;
    vector<char>S(N);
    for (int i = 0; i < N; i++){
        cin >> S.at(i);
    }
    for (int i = 0; i < N-1; i++){
        if (S.at(i)==S.at(i+1)){
            tonari += 1;
        }
    }
    cout << N - tonari << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

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

int GCD(int a, int b){
    if(b == 0) return a;
    else return GCD(b, a % b);
}

int main(){
    int N, M;
    cin >> N >> M;
    string S, T;
    cin >> S >> T;
    int gcd = GCD(N, M);
    int n = N / gcd;
    int m = M / gcd;
    rep(k, gcd){
        if(S[k * n] != T[k * m]){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << (ll)gcd * n * m << endl;
    return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.exe

ll gcd(ll c, ll d) { return d ? gcd(d, c%d) : c;}
ll lcm(ll c, ll d) { return c / gcd(c,   d) * d;}
    
int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    
ld w,h,x,y;
cin >> w >> h >> x >> y;
cout << w*h/2 <<" ";
if (w/2 == x && h/2 == y)
{
    cout << '1' << endl;
}else
{
    cout << '0' << endl;
}


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<iomanip>
#include<sstream>
#include<list>
#include<iterator>
#include<queue>
#include<stack>


#define ll long long
#define ull unsigned long long
#define pi acos(-1)
#define el cout<<"\n"
#define pb push_back
#define f1(i, n)        for (ll i = 1; i <= n; i++)
#define f0(i, n)        for (ll i = 0; i < n; i++)
#define fo(i, s, n)     for (ll i = s; i <= n; i++)


using namespace std;


//**************  MY CODE STARTS HERE  **************************//


int main()
{
    ull n,k;
    cin>>n>>k;
    
    if(k<=n)
    {
        ull x=n/k;
        n=n-(k*x);
    }
   
    ull min1=n;
    while(1)
    {
        if(n>=k)n=n-k;
        if(n<k) n=k-n;
        if(n>=min1 || min1==0)
        {
            cout<<min1;el;
            return 0;
        }
        min1=min(n,min1);
    }
    
}


Measured memory_bytes: 256
/*author : Yashvardhan
Sunday, August 18, 2019
6:46 PM
*/

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

typedef long long ll;

#define int ll
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define vpi vector<pi>
#define ff first
#define ss second
#define mp make_pair
#define endl '\n'
#define all(a) a.begin(), a.end()
#define initialise(a, x) memset(a, x, sizeof(a))
#define rev(Y) reverse(all(Y))
#define printArr(name,from,to) for(int x = from; x < to; x++) cout << name[x] << " ";


#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#ifdef __APPLE__
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << "  ";
	__f(comma + 1, args...);}
#else
#define debug(...)
#endif

template <typename T> ostream& operator << (ostream& os,const vector<T>& v){for(int i=0;i<v.size();++i) os<<v[i]<<" ";return os;} 
template <typename T> ostream& operator << (ostream& os,const set<T>& v){for(auto it:v) os<<it<<" ";return os;} 
template <typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {os<<v.ff<<" "<<v.ss;return os;}

const int mod = 1e9 + 7;
const int inf = 2e18;
const int ninf = -2e18;

const int N = 1e5 + 5;

int arr[26][N];
int focc[N];

int takemod(int a){return ((a%mod)+mod)%mod;}

int pow(int a, int b, int m)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int a){return takemod(pow(takemod(a), mod-2,mod));}


signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef __APPLE__
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("error.txt","w",stderr);
	#endif

	time_t t1, t2;
	t1 = clock();
	
	string s,t;
	cin>>s>>t;

	int n = s.size();
	
	bool possi = true;
	
	initialise(focc,-1);
	initialise(arr,0);

	vi occ[26];

	for(int i = 1; i <= n ; i++){
		for(int j = 0; j < 26; j++) arr[j][i] = arr[j][i-1];
		int curr = s[i-1] - 'a';		
		arr[curr][i]++;
		if(focc[curr] == -1) focc[curr] = i;
		occ[curr].pb(i);
	}


	for(auto i: t){
		int curr = i - 'a';
		if(arr[curr][n] == 0){
			possi = false;
			break;
		}
	}

	if(!possi){
		cout<<-1<<endl;
		return 0;
	}

	int cpos = 0;
	int ans = 0;
	for(int i = 0; i < t.size(); i++){
		int curr = t[i] - 'a';
		if(cpos == 0){
			ans++;
			cpos = focc[curr];
		}
		else{
			if(arr[curr][n] - arr[curr][cpos] == 0){
				cpos = focc[curr];
				ans++;
			}
			else{
				int ind = lower_bound(all(occ[curr]),cpos+1) - occ[curr].begin();
				cpos = occ[curr][ind];
			}
		}
	}

	ans = ans*n;

	ans -= (n-cpos);

	cout<<ans<<endl;
	

	t2 = clock();
	cerr<<endl<<t2-t1<<endl;
	
	return 0;
}



Measured memory_bytes: 22736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, x, y) for (ll i = x; i < y; i++)

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

  for (int i = 1;; i++)
  {
    c = 1 + (a - 1) * i;
    if ((b - 1) % (a - 1) == 0)
    {
      cout << (b - 1) / (a - 1) << endl;
      break;
    }
    else if (c > b)
    {
      cout << i << endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 3644
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
alias route = Tuple!(long, "From", long, "To");
long bignum = 1_000_000_007;
auto dp = new long[](100_100);

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    long n = lread();
    auto blackboard = aryread();
    if(blackboard.sum % 2)
        writeln("NO");
    else
        writeln("YES");
}

Measured memory_bytes: 4536
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

int main()
{
  int N;
  std::cin >> N;
  std::vector<int> X(N);
  std::vector<std::pair<int, int> > mapX;
  for (int i = 0; i < N; i++)
  {
    int tmp;
    std::cin >> tmp;
    mapX.push_back(std::make_pair(tmp, i));
  }
  sort(mapX.begin(), mapX.end());
  for (int i = 0; i < N; i++)
  {
    if (i < N/2)
      X.at(mapX.at(i).second) = mapX.at(N/2).first;
    else
      X.at(mapX.at(i).second) = mapX.at(N/2-1).first;
  }
  for (int i = 0; i < N; i++)
    std::cout << X.at(i) << std::endl;
}


Measured memory_bytes: 4720
import collections
n = int(input())

v  = list(map(int,input().split()))

even = collections.Counter(v[0::2])
odd  = collections.Counter(v[1::2])

a1 = odd.most_common()[0][1]
if len(odd) >=2:
    a2 = odd.most_common()[1][1]

b1 = even.most_common()[0][1]
if len(even) >= 2:
    b2 = even.most_common()[1][1]

if odd.most_common()[0][0] != even.most_common()[0][0]:
    print(n-a1-b1)
elif len(even) == 1 and len(odd) >= 2:
    print(n-b1-a2)
elif len(odd) == 1 and len(even)>= 2: 
    print(n-a1-b2)
elif len(odd) == 1 and len(even) == 1:
    print(n//2)
elif a1+b2 >= a2+b1:
    print(n-a1-b2)
else:
    print(n-a2-b1)


Measured memory_bytes: 18656
#include <stdio.h>

int main(){
    int N;
    int heho;
    scanf("%d",&N);
    
    for (int i=1; i<=1000000000; i++) {
        heho = i*i;
        if (N < heho) {
            printf("%d", (i - 1)*(i-1));
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

struct UnionFind{
    vector<ll> par;
    vector<ll> sizes;
    UnionFind(ll n) : par(n), sizes(n, 1) {
        rep(i,n) par[i] = i;
    }
    int find(ll x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
    }

    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    ll size(ll x) {
        return sizes[find(x)];
    }
};


int main(){
    int n, m;
    cin >> n >> m;
    int a[2500], b[2500];
    
    rep(i, m) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    int ans = 0;
    rep(i, m){
        UnionFind tree(n);
        rep(j, m){
            if (j == i) continue;
            tree.unite(a[j], b[j]);
        }
        if (tree.size(0) != n) ans++;
    }
    
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(){
    int n,re=0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin  >> a[i];
    }
    sort(a.begin(),a.end());
    int best = 0;
    for (int i = 0; i < n - 1; i++) {
		if (min(best, a.back() - best) < min(a[i], a.back() - a[i])) {
			best = a[i];
		}
	}
    cout << a.back() << ' ' << best << endl;
    return 0;
}

Measured memory_bytes: 640
/**
 * @author karayuu
 */
fun main(args: Array<String>) {
    val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
    val r = readLine()!!.toInt()
    if (a > b && a > c) {
        println(R(a, r) + b + c)
    } else if (b > a && b > c) {
        println(R(b, r) + a + c)
    } else if (c > a && c > b) {
        println(R(c, r) + b + a)
    } else {
        println(R(a, r) + b + c)
    }
}

fun R(a: Int, r: Int) : Int {
    var result = a
    for (i in 1..r) {
        result *= 2
    }
    return result
}

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

int main(){
  int n;
  cin >> n;
  vector<double> vec(n);
  for(int i = 0; i < n; i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  
  double ans = vec.at(0);
  
  for(int i = 1; i < n; i++) {
    ans = (ans + vec.at(i)) / 2;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
import           Control.Monad (replicateM)

main :: IO ()
main = do
  [n, m, k] <- map read . words <$> getLine
  [as, bs] <- replicateM 2 $ zip [0..] . scanl (+) 0 . takeWhile (<= k) . map read . words <$> getLine
  let f (a:as) (b:bs) | (sum . map snd) [a,b] <= k = [(sum . map fst) [a,b]] ++ f as (b:bs)
                      | otherwise = f (a:as) bs
      f [] _ = []
      f _ [] = []
      ans = maximum $ f as $ reverse bs
  print ans


Measured memory_bytes: 212632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int long long
#define mod 1000000007
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f(i,n) for(ll i=0;i<n;i++)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ms(v,n) memset((v),n,sizeof(v));
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define sll set<ll>
#define vll vector<ll>
#define vpll vector<pll>
#define maxi(a,b,c) max(a,max(b,c))
#define maxii(a,b,c,d) max(max(a,b),max(c,d))
#define mini(a,b,c) min(a,min(b,c))
#define md(a,b)  ((a%mod)*(b%mod)+mod)%mod 
#define ad(a,b)  (a%mod+b%mod+mod)%mod
#define nl endl
#define inf 1e18
#define cases ll t;cin>>t;while(t--)
#define BLOCK 500
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
 
using namespace std;

const int N=405;

ll dp[N][N];
//dp[i][j] min cost to combine from i to j
ll a[N];
ll n;

ll sum(ll i,ll  j)
{
    ll s=0;
    for(ll k=i;k<=j;k++)
    {
        s+=a[k];

    }
    return s;
}

int main()
{
    
    fast
    cin>>n;
    f(i,n)
    {
        cin>>a[i];

    }
    f(i,n)
    f(j,n)
    dp[i][j]=inf;
    // ms(dp,inf);
    

    for(ll i=n-1;i>=0;i--)
    {
        for(ll j=i;j<n;j++)
        {
            if(i==j)
            dp[i][j]=0;
            else
            {
            for(ll k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum(i,j));
            }
            }
        }
    }
    


    cout<<dp[0][n-1];


    

       
    return 0;
    
}



Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? 1e9:1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){int b=0;for(auto itr :a){if(b++!=0)cout << " "; cout << itr;} }
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
#define int ll
signed main(){
    string s;cin >> s;
    string ans = "AKIHABARA";
    if(ans == s)return puts("YES")*0;
    bool flag = false;
    function<void(string,int)> dfs = [&] (string t,int index){
        t.insert(t.begin()+index, 'A');
        if(t == ans){flag = true;return;}
        if(t.size() >= ans.size())return;
        for(int i = index+1;i<t.size()+1;i++){
            string temp = t;
            dfs(temp,i);
        }
        return;
    };
    rep(i,s.size())dfs(s,i);
    cout << (flag ? "YES":"NO") << endl;
}



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

typedef long long ll;

int main () {
	char c[200005];
	cin >> c;
	int i=0, sum=0;
	while ('0'<=c[i] && c[i]<='9') {
		sum += (int)(c[i]-'0');
		sum %= 9;
		i++;
	}
	if (sum%9 == 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3784
import java.util.Scanner;

public class Main {

    private static int f[] = new int[45];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] matrix = new int[n][n];

        for (int i = 0; i < n; i++) {
            int row = scanner.nextInt();
            int neighborCount = scanner.nextInt();
            for (int j = 0; j < neighborCount; j++) {
                matrix[row - 1][scanner.nextInt() - 1] = 1;
            }
        }

        StringBuilder sb = new StringBuilder(n * 4);
        for (int i = 0; i < n; i++) {
            sb.append(matrix[i][0]);
            for (int j = 1; j < n; j++) {
                sb.append(" ");
                sb.append(matrix[i][j]);
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }

}



Measured memory_bytes: 29068
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1e9+7;
const int N=2e5+5;
vector<int>adj[N];
bool visi[N];
ll dp[N][2];
void dfs(int s)
{
  visi[s]=1;
  dp[s][1]=dp[s][0]=1;
  ll w=1,b=1;
  for(int i=0;i<adj[s].size();i++)
  {
    if(visi[adj[s][i]]==0)
       {
         dfs(adj[s][i]);
         w=(w*(dp[adj[s][i]][0]+dp[adj[s][i]][1])%mod)%mod;
         b=(b*dp[adj[s][i]][0])%mod;
       }
    }
            dp[s][0]=w;
            dp[s][1]=b;
 }
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n-1;i++)
  {
    int x,y;
    cin>>x>>y;;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(1);
  cout<<(dp[1][0]+dp[1][1])%mod<<endl;
}


Measured memory_bytes: 16512
/*
 Educational Dp Contest Atcoder
 
 */

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}

const ll MOD =998244353;
const ll hell=1000000007;
const int INF=1e16;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=200005;
int bit[N];
int dp[N];
int getparent(int i)
{
    return i-(i& -i);
}
int getnext(int i)
{
    return i+ (i& -i);
}
int getmax(int r)
{
    if(r==0)
        return 0;
    int ans=0;
    while(r>0)
    {
        ans=max(ans,bit[r]);
        r=getparent(r);
    }
    return ans;
}
void update(int i,int v)
{
    while(i<N)
    {
        bit[i]=max(bit[i],v);
        i=getnext(i);
    }
    
}

void solve()
{
    int n;
    cin>>n;
    int h[n+1],a[n+1],ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int mx=getmax(h[i]-1);
        ans=max(ans,a[i]+mx);
        update(h[i],mx+a[i]);
    }
    cout<<ans<<endl;
}

int32_t main()
{
    
    IOS;
    //FILE *fin = freopen("in","r",stdin);
    //FILE *fout = freopen("out","w",stdout);
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define int long long int
#define N 100001
#define mp make_pair
#define pb push_back
#define mod 1000000007
using namespace std;
vector<pair<int,int>> adj[N];
int val[N];
int siz[N];
bool check[N];
int mini[N];
int maxi[N];
signed main()
{
    int n,k;
    cin>>n>>k;
    vector<int> V;
    for(int i=0;i<=n;i++)
    V.push_back(i);

    int ans=0;

    

    
    mini[0] = 0;
    for(int i=0;i<n;++i)
    {
        mini[i+1] = mini[i] + i+1;
        //maxi[i+1] = maxi[i] + n-i;
        //cout<<i+1<<" "<<maxi[i+1]<<endl;
    }

    for(int i=k;i<n+1;i++)
    {
        int mi,ma;
        mi = mini[i-1];
        ma = mini[n] - mini[n-i];

        ans =   (ans + (ma-mi+1))%mod;
    }
    cout<<(ans+1)%mod;

    return 0;
}


Measured memory_bytes: 8660
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        String[] bstr = sc.next().split("\\.");
        long b1 = Long.valueOf(bstr[0]) * 100;
        long b2 = Long.valueOf(bstr[1]);
        System.out.println(a * (b1 + b2) / 100);
    }

}


Measured memory_bytes: 35816
N = int(input())
name = [input() for i in range(N)]
nameList = [0 for i in range(5)]

P = [0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,2]
Q = [1 ,1 ,1 ,2 ,2 ,3 ,2 ,2 ,3 ,3]
R = [2 ,3 ,4 ,3 ,4 ,4 ,3 ,4 ,4 ,4]

for n in name:
  if n[0] == 'M':
    nameList[0] += 1
  elif n[0] == 'A':
    nameList[1] += 1
  elif n[0] == 'R':
    nameList[2] += 1
  elif n[0] == 'C':
    nameList[3] += 1
  elif n[0] == 'H':
    nameList[4] += 1

ans = 0
for i in range(10):
  ans += nameList[P[i]] * nameList[Q[i]] * nameList[R[i]]
    
print(ans)


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

using namespace std;
int main(){
    int n;
    cin >> n;
    int min = 200001,ans = 0;
    int p;
    for(int i = 0; i < n; i++){
        cin >> p;
        if(min > p){
            min = p;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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++)

int main() {
    /*変数定義，入力*/
    int N, M;
    ll sum = 0;

    cin >> N;
    cin >> M;

    std::vector<ll> A(N);

    rep(i, N) cin >> A[i];
    std::sort(A.begin(), A.end(), std::greater<int>());
    int k = 0;
    
    
    //rep(j,N) cout << A[j] << ",";
    //cout << endl;
    
    
    
    
    rep(i, M){
        if(A[k] >= A[0] && k < A.size()){
            A[k] = A[k] / 2;
            k ++;
        }else{
            std::sort(A.begin(), A.end(), std::greater<int>());
            A[0] = A[0] / 2;
            k = 1;
        }
        //rep(j,N) cout << A[j] << ",";
        //cout << endl;
    }


    rep(i,N) sum += A[i]; 
    cout << sum;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
static const int MAX = 1000000;

int main(){
  long long int N;
  long long int A[MAX];
  long long int B[MAX];

  cin >> N;
  for (int i = 1; i < N; i++){
    cin >> A[i];
  }

  for (int i = 1; i < N; i++){
    B[A[i]] += 1;
  }

  for (int i = 1; i < N + 1; i++){
    cout << B[i] << endl;
  }

  return 0;
}


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

#define FOR0(i,n) for (int i = 0; i < n; i++)
#define FOR(i,j, n) for (int i = j; i < n; i++)
// bool isEven(ll n) {return (n%2!=0)?false:true;};
#define INF 1000000000 // 1 billion, safer than 2B for Floyd Warshall’s

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
// #define int ll


using namespace std;
typedef pair<int, pair<int, int> > ppp;

//leetcode

int a[200010];

int main()
{
  int n;
  cin>>n;
  FOR0(i, n) cin>>a[i];

  int maxNum = a[0];

  int result = 1;

  for (int i = 1; i < n; ++i)
  {
  	if(a[i]<=maxNum)
  	{
  		result++;
  		maxNum = a[i];
  	}
  }

  cout<<result<<endl;
}

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

int main() {
  int cnt = 0;
  string s;

  cin >> s;

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

  if(15 - s.size() + cnt >= 8) {
    cout << "YES";
  } else {
    cout << "NO";
  }

  return 0;
}

Measured memory_bytes: 256