akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

pair<int, int> cost[100001];
vector<int> g[100001];
set<int> st;

int qclr;
int clr[100001];
int vis[100001];

void dfs(int me){
    vis[me] = 1;
    for(auto &nxt: g[me]){
        if(vis[nxt]) continue;
        clr[nxt] = clr[me];
        dfs(nxt);
    }
}

int main(){
    int n,m;
    setbuf(stdout, NULL);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        cost[i].second = i;
        scanf("%d",&(cost[i].first));
        clr[i] = i;
    }
    for(int i=0;i<m;i++){
        int aa, bb;
        scanf("%d%d",&aa,&bb);
        g[aa].push_back(bb);
        g[bb].push_back(aa);
    }
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        dfs(i);
    }
    sort(cost, cost + n);
    long long ans = 0;
    int lft = (n - m - 2);
    if(lft >= 0){    
        for(int i=0;i<n;i++){
            if(st.find(clr[cost[i].second]) == st.end()){
                ans += cost[i].first;
                st.insert(clr[cost[i].second]);
            }else if(lft > 0){
                lft--;
                ans += cost[i].first;
            }
        }
    }
    if(lft <= 0) printf("%lld\n", ans);
    else printf("Impossible\n");
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}


int f(ll a, ll b){
	if(a>b) swap(a,b);
	int rt =0;
	for(;b>0; b/=10) rt++;
	return rt;
 }

int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	ll n; int ans=1<<29;
	cin >>n;
	
	for(ll i=1; i*i <=n; i++){
		if(n%i ==0){
			ans = min(ans, f(i, n/i));
		}
	}
	cout << ans <<"\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
using namespace std;
int d;
set<int> st;
int main(void)
{
    int n;
    cin >> n;
    st.insert(n);
    int i;
    for(i=2;;i++)
    {
        n=(n%2 ? n*3+1 : n/2);
        if(st.count(n)==1) break;
        st.insert(n);
    }
    cout << i;
    return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n, m, k[11], s[11][11];
bool a[11]; 
void solve(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> k[i];
		for(int j = 0; j < k[i]; j++){
			cin >> s[i][j];
			s[i][j]--;
		}
	}
	for(int i = 0; i < m; i++){
		cin >> a[i];
	}
	
	int cnt = 0;
	for(int i = 0; i < (1<<n); i++){
		bool c[11] = {0};
		for(int j = 0; j < n; j++){
			c[j] = (i>>j&1);
		}
		for(int j = 0; j < m; j++){
			bool ok = a[j];
			for(int jj = 0; jj < k[j]; jj++){
				ok ^= c[s[j][jj]];
			}
			if(ok) break;
			if(j == m-1) cnt++;
		}
	}
	cout << cnt << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define rep_down(i, n) for(int i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(int i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()

string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";
/*
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;

}
*/
/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}

ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}

bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}

ll gcd(ll a, ll b){
  ll tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

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

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

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

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

int main(void){
  ll N, M, A, B, C, D, E, F, K,L, W, H, P, Q, R, X, Y;
  ll ans;
  string S, T;
  cin >> N >> K;
  ll x[N];
  rep(i, N) cin>>x[i];
  ans = 0;
  rep(i, N){
    ans += min(2*x[i], 2*(K-x[i]));
  }
  cout << ans << endl;

}


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

int main(){
  string s;
  getline(cin, s);
  rep(i,s.size()){
    if(islower(s.at(i))){
      s.at(i) = toupper(s.at(i));
    }
    else if(isupper(s.at(i))){
      s.at(i) = tolower(s.at(i));
    }
  } 
    cout << s << endl;
  return 0;
}



Measured memory_bytes: 3180
<?php
class main {
    function run () {
        fscanf(STDIN, "%d", $n);
        $line = trim(fgets(STDIN));
        $lines = explode(" ", $line);
        $arr = array();
        foreach ($lines as $k => $v) {
            if (!isset($arr[$v])) {
                $arr[$v]['count'] = 1;
                $arr[$v]['min'] = $k + 1;
                $arr[$v]['value'] = $v;
            } else {
                $arr[$v]['count']++;
            }
        }
        krsort($arr);
        $arr = array_values($arr);
        $ans = array();
        for ($i = 1; $i <= $n; $i++) {
            $ans[$i] = 0;
        }
        for ($i = 0; $i < count($arr) - 1; $i++) {
                $ans[$arr[$i]['min']] += ($arr[$i]['value'] - $arr[$i + 1]['value']) * $arr[$i]['count'];
                $arr[$i + 1]['count'] += $arr[$i]['count'];
                if ($arr[$i]['min'] < $arr[$i + 1]['min']) {
                    $arr[$i + 1]['min'] = $arr[$i]['min'];
                }
        }
        $ans[$arr[$i]['min']] += $arr[$i]['value'] * $arr[$i]['count'];

        for ($i = 1;$i <= $n;$i++ ) {
            echo $ans[$i] . "\n";
        }
    }
}

$object = new main();
$object->run();

Measured memory_bytes: 105108
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define INF 1e9
#define LINF 1e18
#define ld double
#define ll long long
#define ull unsigned long long

const int SZ = 1 << 13;
char buff[SZ], *pos = buff + SZ - 1;
#define getchar() ++ pos == buff + SZ ? fread(pos = buff, 1, SZ, stdin), *pos : *pos

inline ll read() {
	ll x = 0; int f = 1, c = getchar();
	for (;!isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x<<3) + (x<<1) + (c^48);
	return x * f;
}

inline void read(char *s) {
	int c = getchar();
	for (; isspace(c); c = getchar());
	for (;!isspace(c); c = getchar()) *s = c, s ++;
	*s = 0;
}

#define sqr(x) (1LL * (x) * (x))

const int N = 2e5 + 5;
int n;
ll C;
int h[N];

int que[N];
int lb, rb;
ll dp[N]; 

void ins(int x) {
	while (rb - lb + 1 >= 2) {
		ll a = ((-2LL * h[que[rb]]) - (-2LL * h[que[rb - 1]])) * ((dp[x] + sqr(h[x])) - (dp[que[rb]] + sqr(h[que[rb]])));
		ll b = ((-2LL * h[x]) - (-2LL * h[que[rb]])) * ((dp[que[rb]] + sqr(h[que[rb]])) - (dp[que[rb - 1]] + sqr(h[que[rb - 1]])));
		if (a <= b) break;
		-- rb;
	}
	que[++ rb] = x;
}

int qry(int x) {
	while (rb - lb + 1 >= 2) {
		ll a = dp[que[lb]] + C + sqr(h[x] - h[que[lb]]);
		ll b = dp[que[lb + 1]] + C + sqr(h[x] - h[que[lb + 1]]);
		if (a <= b) break;
		++ lb;
	}
	return que[lb];
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif
	
	n = read(), C = read();
	for (int i = 0; i < n; ++ i) h[i] = read();
	lb = 1;
	que[++ rb] = 0;
	
	for (int i = 1; i < n; ++ i) {
		int x = qry(i);
		dp[i] = dp[x] + C + sqr(h[i] - h[x]);
		ins(i);
	}
	printf("%lld\n", dp[n - 1]);
	
	return 0;
}


Measured memory_bytes: 3328
s=input()
t=list(map(int,input().split()))
u=list(map(int,input().split()))
list=[]
a=int(s)
c=t[0]
d=0
e=0
for i in range(a):
  if t[i]<=u[i]:
    if t[i+1]<=u[i]-t[i]:
      d+=t[i]+t[i+1]
      t[i+1]=0
    else:
      d+=u[i]
      t[i+1]=t[i+1]+t[i]-u[i]
  else:
    d+=u[i]
print(d)

Measured memory_bytes: 19004
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll MOD = 1000000007;

#define vec                vector<int>
#define vecll              vector<ll>
#define vecd               vector<double>
#define vecst              vector<string>
#define vecb               vector<bool>
#define vec2(var, n, m)    vector<vector<int>> var(n, vector<int>(m, 0))
#define vecll2(var, n, m)  vector<vector<ll>> var(n, vector<ll>(m, 0))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
void prtok(bool ok){prt(ok ? "Yes" : "No");}
//----------------------------------------------------------------

int main(void) {
  char c;
  cin >> c;
  if(c>'Z'){
    prt('a');
  } else {
    prt('A');
  }
}


Measured memory_bytes: 3616
L,R=map(int,input().split())

R=min(R,L+2019)
#print(L,R)  
 
COUNT=2019
NUMBER=0
 
for i in range(L,R+1):
  for j in range(i+1,R+1):
    
    NUMBER=i*j%2019
    #print(i,j,NUMBER)
    if COUNT>NUMBER:
      COUNT=NUMBER
      #print(i,j,NUMBER)
 
    
print(COUNT)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
//debug
#define vecprint(v) cout << "  vector: ";rep(i,v.size())cout << v[i] << " ";cout << endl;
#define setprint(s) cout << "  set: ";for(auto i=s.begin();i!=s.end();i++)cout << *i << " ";cout << endl;
#define mappairprint(s) cout << "  map: ";for(auto i=s.begin();i!=s.end();i++)cout << i->first << " " << i->second << endl;cout << endl;
//reader
#define r1(a) cin>>(a)
#define r2(a,b) cin>>(a)>>(b)
#define r3(a,b,c) cin>>(a)>>(b)>>(c)
//writer
#define w1(a) cout<<(a)<<" "
#define w2(a,b) cout<<(a)<<" "<<(b)<<" "
#define w3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "
#define wl1(a) cout<<(a)<<endl
#define wl2(a,b) cout<<(a)<<" "<<(b)<<endl
#define wl3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
//variable definition
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
//roop
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define all(c) c.begin(),c.end()
//term
#define elif else if
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
using namespace std;
using ll = long long;
//const


int main() {
  //input
  int a,b;
  cin >> a >> b;
 

  cout << a * b << endl;  
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  map<char,string> mp;
  cin >> mp['a'] >> mp['b'] >> mp['c'];
  char turn = 'a';
  while(true){
    if(mp[turn].size()==0){
      cout << char(turn - 0x20) << endl;
      break;
    }
    char next_turn = mp[turn].at(0);
    mp[turn] = mp[turn].substr(1);
    turn = next_turn;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct Bipartite_matching{
	int V;
	vector< vector<int> > G;
	vector<int> match;
	vector<bool> used;
	void init(int N){
		V=N;
		G.assign(V,vector<int>());
		match.assign(V,0);
		used.assign(V,false);
	}
	void add_edge(int v,int u){
		G[v].pb(u);
		G[u].pb(v);
	}
	bool dfs(int v){
		used[v]=true;
		rep(i,G[v].size()){
			int u=G[v][i],w=match[u];
			if(w<0 || (!used[w] && dfs(w))){
				match[v]=u;
				match[u]=v;
				return true;
			}
		}
		return false;
	}
	int max_matching(){
		int res=0;
		fill(all(match),-1);
		rep(v,V){
			if(match[v]<0){
				fill(all(used),false);
				if(dfs(v)) res++;
			}
		}
		return res;
	}
};

int N,A,B;
int main(){
	cin>>N>>A>>B;
	vector<int> cs;
	int res = 0;
	rep(i,N){
		int x,y;
		cin>>x>>y;
		int c = x-y;
		if(abs(c)<=A || (B<=abs(c) && abs(c)<=2*A)) res++;
		else cs.pb(c);
	}
	N = cs.size();

	Bipartite_matching BM;
	BM.init(N);
	rep(i,N) rep(j,i){
		int x = abs(cs[i]+cs[j]);
		if(x<=A || (B<=x&&x<=2*A)) BM.add_edge(i,j);
	}
	cout<<res+BM.max_matching()<<endl;
}



Measured memory_bytes: 3296
from bisect import bisect as bisect
l = [0]*100000
for i in range(len(l)):
    l[i] = (i*(i+1))//2

N = int(input())
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

d = prime_decomposition(N)
ans = 0
for i in d:
    ans += bisect(l,d[i])-1
print(ans)


Measured memory_bytes: 64816
#include<bits/stdc++.h>
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 RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int a[26];
int b[26];

int bit[100001];
int n;

int su(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i -= (i& -i);
	}
	return s;
}

void add(int i,int x){
	while(i <=n){
		bit[i]+=x;
		i+=(i&-i);
	}
}

int main(){
	REP(i,26){
		a[i]=0;
		b[i]=0;
	}
	string S;
	cin>>S;
	n=S.size()/2;
	REP(i,S.size()){
		a[S[i]-'a']++;
	}
	int num=-1;
	int sum=0;
	REP(i,26){
		if(a[i]%2==0){
		}else{
			if(num==-1){
				num=i;
			}else{
				cout<<-1<<endl;
				return 0;
			}
		}
		a[i]/=2;
		sum+=a[i];
	}
	LL ans=0;
	vector<int>v;
	vector<int>v2;
	int center=0;
	REP(i,S.size()){
		int aa=S[i]-'a';
		if(a[aa]!=0){
			ans+=i-v.size();
			//cout<<i<<" "<<v.size()<<" "<<i-v.size()<<endl;
			v.push_back(aa);
			a[aa]--;
		}else if(aa==num){
			ans+=v2.size();
			num=-1;
		}else{
			v2.push_back(aa);
		}
	}
	reverse(v2.begin(),v2.end());
	//v1とv2の値を変更
	map<int,int>m;
	REP(i,v.size()){
		m[v[i]+26*a[v[i]]]=i;
		a[v[i]]++;
		v[i]=i;
	}
	REP(i,v2.size()){
		int me=v2[i]+26*b[v2[i]];
		b[v2[i]]++;
		v2[i]=m[me];
	}
	
	/*
	cout<<endl;
	REP(i,v.size()){
		cout<<v[i]<<endl;
	}
	cout<<endl;
	REP(i,v2.size()){
		cout<<v2[i]<<endl;
	}
	*/
	//v2の転倒数を求める
	//cout<<ans<<endl;
	REP(j,v2.size()){
		ans += j- su(v2[j]+1);
		//cout<<su(v2[j]+1)<<" aa ";
		//cout<<j-su(v2[j]+1)<<endl;;
		add(v2[j]+1,1);
	}
	cout<<ans<<endl;
	return(0);
}

Measured memory_bytes: 6268
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
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; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int h, n;
    cin >> h >> n;

    vector<int> dp(h + 1, INF);
    dp[0] = 0;

    rep(i, n) {
        int a, b;
        cin >> a >> b;
        rep(j, h) {
            int nj = min(j + a, h);
            dp[nj] = min(dp[nj], dp[j] + b);
        }
    }

    cout << dp[h] << endl;

    return 0;
}

Measured memory_bytes: 256
import math


def main():

    mod = 1000000007
    N = int(input())

    A = [0]
    B = [0]

    for n in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    calc = dict()
    non_count = 0

    for i in range(1, N + 1):

        if A[i] == 0 and B[i] == 0:
            non_count += 1
        elif A[i] == 0:
            k = (0, 1)
            if calc.get(k):
                calc[k][0] += 1
            else:
                calc[k] = [1, 0]
        elif B[i] == 0:
            k = (0, 1)
            if calc.get(k):
                calc[k][1] += 1
            else:
                calc[k] = [0, 1]
        else:
            r = math.gcd(A[i], B[i])
            m = 1
            if A[i] * B[i] < 0:
                m = -1
            k1 = (m * abs(A[i] // r), abs(B[i] // r))
            k2 = (-m * abs(B[i] // r), abs(A[i] // r))
            if calc.get(k1):
                calc[k1][0] += 1
            elif not calc.get(k2):
                calc[k1] = [1, 0]
            else:
                calc[k2][1] += 1

    N = N - non_count

    count = 0
    for k, v in calc.items():
        if not v[0] * v[1] == 0:
            count += v[0] + v[1]

    ans = pow(2, N - count, mod)
    for k, v in calc.items():
        if not v[0] * v[1] == 0:
            comb = (pow(2, v[0]) + pow(2, v[1]) - 1)
            ans = (ans * comb) % mod

    print((ans - 1 + non_count) % mod)


if __name__ == '__main__':
    main()


Measured memory_bytes: 138904
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<bitset>
using namespace std;
int main()
{
    long long int q;
    cin>>q;
    bitset<32> bs(q);
    cout<<bs<<endl;
    cout<<(~bs)<<endl;
    cout<<(bs<<1)<<endl;
    cout<<(bs>>1)<<endl;
}


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

int main(){
    int A, B, C, X, sum{};
    cin >> A >> B >> C >> X;
    for(int i{}; i <= A; i++){
        for(int j{}; j <= B; j++){
            if(500*i+100*j+50*C>=X && 500*i+100*j<=X){
                sum++;
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
A, B = list(map(int, input().split()))
c = []
c.append(A % 4 // 2 ^ (B + 1) % 4 // 2)

keta = 2
while(B // keta != 0):
    if A // keta % 2 == 0:
        a = 0
    else:
        a = A % keta
    if B // keta % 2 == 0:
        b = 0
    else:
        b = B % keta
        b += 1
    c.append((b - a) % 2)
    keta = keta<<1
ans = 0

for i in range(len(c) - 1, -1, -1):
    ans = ans<<1
    ans ^= c[i]
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<cstdio>
#pragma warning(disable:4996)
using namespace std;
int dat[262145], n, q, _size;
void update(int x, int y) {
	x += _size; dat[x] = y;
	while (x > 1) {
		x /= 2;
		dat[x] = min(dat[x * 2], dat[x * 2 + 1]);
	}
}
int query(int l, int r, int a, int b, int pos) {
	if (l <= a && b <= r) { return dat[pos]; }
	if (l > b)return 2147483647; if (r < a)return 2147483647;
	int D1 = query(l, r, a, (a + b + 1) / 2 - 1, pos * 2);
	int D2 = query(l, r, (a + b + 1) / 2, b, pos * 2 + 1);
	return min(D1, D2);
}
int main() {
	scanf("%d%d", &n, &q); _size = 1; while (_size < n)_size *= 2;
	for (int i = 0; i < 262145; i++)dat[i] = 2147483647;
	for (int i = 0; i < q; i++) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		if (a == 0)update(b, c);
		if (a == 1)cout << query(b, c, 0, _size - 1, 1) << endl;
	}
	return 0;
}


Measured memory_bytes: 4180
def f(x,r,p):
  ans=1
  for i in range(r):
    ans=(ans*(x-i))%p
  return ans
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,a,b=map(int,input().split())
mod=10**9+7
a=min(a,n-a)
b=min(b,n-b)
ca=f(n,a,mod)*power_func(f(a,a,mod),mod-2,mod)
cb=f(n,b,mod)*power_func(f(b,b,mod),mod-2,mod)
ans=(-1+power_func(2,n,mod)-ca-cb)%mod
print(ans)

Measured memory_bytes: 38512
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

int main(){
    vector<string> s;
    string temps;
    while (cin>>temps){
        s.push_back(temps);
    }
    int cnt[26]={};
    for (vector<string>::iterator i=s.begin();i!=s.end();i++){
        for (int j=0;j<i->length();j++){
            if ((*i)[j]>='a' && (*i)[j]<='z'){
                (*i)[j]+='A'-'a';
            }
            if ((*i)[j]>='A' && (*i)[j]<='Z'){
                cnt[(int)((*i)[j]-'A')]++;
            }
        }
    }
    for (int i=0;i<26;i++){
        printf("%c : %d\n",i+'a',cnt[i]);
    }
    return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<ll,ll> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int main()
{   
    set<string> al;
    int n;cin>>n;
    string s;
    REP(i,n)
    {
        cin>>s;
        string temp;
        REP(j,s.size()-1)
        {
            for(int k=0;k<=j;k++)temp+=s[k];for(int k=j+1;k<=s.size()-1;k++)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=j+1;k<s.size();k++)temp+=s[k];for(int k=0;k<=j;k++)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=j;k>=0;k--)temp+=s[k];for(int k=j+1;k<=s.size()-1;k++)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=j+1;k<s.size();k++)temp+=s[k];for(int k=j;k>=0;k--)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=0;k<=j;k++)temp+=s[k];for(int k=s.size()-1;k>=j+1;k--)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=s.size()-1;k>=j+1;k--)temp+=s[k];for(int k=0;k<=j;k++)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=j;k>=0;k--)temp+=s[k];for(int k=s.size()-1;k>=j+1;k--)temp+=s[k];
            al.insert(temp);temp.clear();
            for(int k=s.size()-1;k>=j+1;k--)temp+=s[k];for(int k=j;k>=0;k--)temp+=s[k];
            al.insert(temp);temp.clear();
        }
        //for_each(al.begin(),al.end(),[](string x){cout<<" "<<x;});
        cout<<al.size()<<endl;
        al.clear();
    }
}


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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

int main(){
  int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
  cout << string(tx-sx,'R') << string(ty-sy,'U');
  cout << string(tx-sx,'L') << string(ty-sy,'D');
  cout << 'D' << string(tx-sx+1, 'R') << string(ty-sy+1, 'U') << 'L';
  cout << 'U' << string(tx-sx+1, 'L') << string(ty-sy+1, 'D') << 'R';
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

B = [-1 for _ in range(N)]
ans = []

for i in range(N, 0, -1):
    tmp_sum = 0
    tmp_i = 2 * i
    while N >= tmp_i:
        tmp_sum += B[tmp_i - 1]
        tmp_i += i

    if A[i-1] == tmp_sum % 2:
        B[i-1] = 0
    else:
        ans.append(i)
        B[i-1] = 1

print(len(ans))
if len(ans):
    print(" ".join(map(str, ans[::-1])))


Measured memory_bytes: 26936
#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=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
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; }

ll n, m;

// a^b
ll pow(ll a, ll b) {
    if (b == 0) return 1;
    ll res = pow(a*a % MOD, b/2);
    if (b % 2 == 1) {
        res *= a;
        res %= MOD;
    }
    return res;
}

int main() {
    cin >> m >> n;
    cout << pow(m, n) << endl;
}



Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
#define lowbit(x) ((x)&(-x))
#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())
using namespace std;
string s;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	for(int i=0;i<s.size();i++)
		s[i]='x';
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;

inline double sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
// }}}


signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	unsigned bit = 0;
	bit--;
	rep(i,n){
		int k;
		cin >> k;
		unsigned bit2 = 0;
		rep(j,k){
			int a;
			cin >> a;
			bit2 |= (1 << (a-1));
		}
		bit &= bit2;
	}
	cout << __builtin_popcount(bit) << '\n';
	return 0;	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const int MOD = 1000000007;

ll N, K;
ll A[200010], acc[200010];
map<ll, ll> mp;

signed main(){
    cin >> N >> K;
    REP(i, N) cin >> A[i];
    ll ans = 0;
    acc[0] = (A[0] - 1) % K;
    REP(i, N - 1){
        acc[i + 1] = (acc[i] + A[i + 1] - 1) % K;
    }
    REP(i, min(N, K - 1)) mp[acc[i]]++;
    ans += mp[0];
    mp[acc[0]]--;
    int j = K - 2;
    FOR(i, 1, N){
        if(j < N - 1){
            j++;
            mp[acc[j]]++;
        }
        if(i <= j) ans += mp[acc[i - 1]];
        mp[acc[i]]--;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 19220
/**   Created by: Humberto Yusta
          Codeforces User: humbertoyusta
          Country: Cuba
          Copyright��                    */
#include<bits/stdc++.h>
using namespace std;
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 200010;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = (((1ll<<59ll)-1ll)*2ll)+1ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return pwur * pwur % mod;
}
/// My Code -------------------------------------------------

int arr[maxn], ans[maxn], sum;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));

    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);

    int a, b, c;
    cin >> a >> b >> c;
    swap(a,b);
    swap(a,c);
    cout << a << ' ' << b << ' ' << c << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {a = b; return true;}
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {a = b; return true;}
  return false;
}

int main() {
  int N, M; cin >> N >> M;
  V A(M), C(M);
  rep(i, M) {
    cin >> A[i];
    int b; cin >> b;
    rep(j, b) {
      int c; cin >> c;
      c--;
      C[i] |= 1<<c;
    }
  }

  int bit_max = 1<<N;
  VV dp(M+1, V(bit_max, INF));
  rep(m, M+1) dp[m][0] = 0;

  rep(m, M) rep(bi, bit_max) {
    dp[m+1][bi] = dp[m][bi];
    chmin(dp[m+1][bi], dp[m][bi&~C[m]] + A[m]);
  }

  if (dp[M][bit_max-1] == INF) cout << -1;
  else cout << dp[M][bit_max-1];
  cout << endl;
  return 0;
}


Measured memory_bytes: 16384
#include<stdio.h>
#include<string.h>
int main(void)
{
	int n,a=0,i;
	char s[101];
	scanf("%s", s);
	if(strlen(s)%2==0)
	n=strlen(s)/2-1;
	else
	n=strlen(s)/2;
	for(i=0; i<=n; i++)
	{
		if(s[i]!=s[strlen(s)-(i+1)])
		a++;
	}
	printf("%d\n", a);
	
	return 0;
}

Measured memory_bytes: 128
import collections
import sys
sys.setrecursionlimit(2000000)
# import math
# import itertools
# import statistics
# import numpy as np
n = int(input())
#n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a_count = collections.Counter(a)
a_list = list(a_count.items())
a_sorted = sorted(a_list, key=lambda x: x[1])
# print(a_sorted)
count = 0
for i in range(len(a_sorted)):
    if a_sorted[i][0] != a_sorted[i][1]:
        if a_sorted[i][0] < a_sorted[i][1]:
            count += a_sorted[i][1]-a_sorted[i][0]
        else:
            count += a_sorted[i][1]

print(count)


Measured memory_bytes: 21740
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i * i <= n; ++i) {
		if (i * i <= n) {
			ans = max(ans, i * i);
		}
	}

	dunk(ans);

	return 0;
}

Measured memory_bytes: 256
n = int(input()) 
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
utility = 0
for i in a:
  utility += b[i-1]
for j in range(n-1):
  if a[j+1]-a[j] == 1:
    utility += c[a[j]-1]
print(utility)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                return;
            }
            int w = sc.nextInt();
            int h = sc.nextInt();
            int[][] map = new int[h][w];
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;
                map[y][x] = 1;
            }
            int s = sc.nextInt();
            int t = sc.nextInt();
            int max = 0;
            for (int i = 0; i <= h - t; i++) {
                for (int j = 0; j <= w - s; j++) {
                    int c = 0;
                    for (int k = 0; k < t; k++) {
                        for (int l = 0; l < s; l++) {
                            c += map[i + k][j + l];
                        }
                    }
                    // System.out.println(c);
                    max = Math.max(c, max);
                }
            }
            // arrayDump(map);
            // System.out.println();
            System.out.println(max);
            // System.out.println();
        }
    }

    public static void arrayDump(int[][] a) {
        for (int i = 0, l = a.length; i < l; i++) {
            for (int j = 0, l2 = a[0].length; j < l2; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

Measured memory_bytes: 55872
#include<iostream>
#define f(A,B,C)Y<A||Y==A&&M<B||Y==A&&M==B&&D<C
using namespace std;
int Y,M,D;
main()
{
	while(cin>>Y>>M>>D)
	{
		if(f(1868,9,8))cout<<"pre-meiji"<<endl;
		else if(f(1912,7,30))cout<<"meiji "<<Y-1867<<" "<<M<<" "<<D<<endl;
		else if(f(1926,12,25))cout<<"taisho "<<Y-1911<<" "<<M<<" "<<D<<endl;
		else if(f(1989,1,8))cout<<"showa "<<Y-1925<<" "<<M<<" "<<D<<endl;
		else cout<<"heisei "<<Y-1988<<" "<<M<<" "<<D<<endl;
	}
}



Measured memory_bytes: 2980
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c; cin >> a >> b >> c;
    if(a == b and b == c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 50;
ll monster[MAX],hero[MAX]={0};
int main(){
	memset(hero,0,sizeof(hero));
	int n;
	cin>>n;
	ll ans=0;
	for(int i=0;i<=n;i++){
		cin>>monster[i];
	}
	ll pre=0;
	for(int i=0;i<n;i++){
		cin>>hero[i];
		if(hero[i]+pre>=monster[i]){
			ans+=monster[i];
			if(pre<monster[i])
				pre=hero[i]-(monster[i]-pre);
			else pre=hero[i];
		}
		else{
			ans+=hero[i]+pre;
			pre=0;
		}
	}
	ans+=min(pre+hero[n],monster[n]);
	cout<<ans<<"\n";
	return 0;
}                                


Measured memory_bytes: 1792
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)
from collections import *

def dfs(v, pv, de):
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v, de+1)
        left[v] = max(left[v], left[nv]-1)
        right[v] = min(right[v], right[nv]+1)
    
    if v in d:
        if d[v]<left[v] or right[v]<d[v] or (d[v]-d[root])%2!=de%2:
            print('No')
            exit()
        else:
            left[v] = d[v]
            right[v] = d[v]
    
def dfs2(v, pv, now):
    ans[v] = now
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if left[nv]<=now-1<=right[nv]:
            dfs2(nv, v, now-1)
        elif left[nv]<=now+1<=right[nv]:
            dfs2(nv, v, now+1)
        else:
            print('No')
            exit()
    
N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)

d = defaultdict(int)
K = int(input())

for _ in range(K):
    V, P = map(int, input().split())
    d[V-1] = P
    root = V-1

left = [-10**18]*N
right = [10**18]*N
dfs(root, -1, 0)
ans = [-1]*N
dfs2(root, -1, d[root])
print('Yes')

for ans_i in ans:
    print(ans_i)


Measured memory_bytes: 193620
#include<bits/stdc++.h>
using namespace std;
#define int        long long
#define nn         3000
#define fsp(x)        cout<<fixed<<setprecision(10)<<x;
#define FAST       ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) 

int n;
double prob[nn+1];

double dp[nn+1][nn+1];
double solve(int i,int x){
    if(x == 0)
        return 1;
    if(i == 0)
        return 0;
    if(dp[i][x] > -0.9)
        return dp[i][x];
    
    return dp[i][x] = prob[i]*solve(i-1,x-1) + (1-prob[i])*solve(i-1,x);
}

int32_t main() {
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>prob[i];
    }

    fsp(solve(n,(n+1)/2));   
}


Measured memory_bytes: 70784
#include<iostream>
using namespace std;
int main(){
	int H, W;
	
	while(1){
		cin >> H >> W;
		if ( H == 0 && W == 0 ) break;
		
		for ( int i = 0; i < H; i++ ){
			for ( int j = 0; j < W; j++ ){
				if ( i == 0 || i == H-1 || j == 0 || j == W-1 ){
					cout << "#";
				}else{
					cout << ".";
				}
			}
			cout << "\n";
		}
		cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3080
import std.stdio;
import std.string;
import std.algorithm;
import std.conv;

void main() {
    auto arr = readln.chomp.split.map!(to!int);

    int result = 0;
    for (int i = arr[0]; i <= arr[1]; i++) {
        if (arr[2] % i == 0) result++;
    }

    result.writeln;
}

Measured memory_bytes: 1052
# your code goes here
#binary search function
def bi(B0,bA,BI):
    bm=bA[1]+bA[2]
    bm//=2
    if BI[bA[1]]<=B0<=BI[bm]:
        bA=[0,bA[1],bm]
    else:
        bA=[0,bm,bA[2]]
   # print(bA)
    return bA
def bs(B0,BI):
    if B0<BI[0]:
        bA=[0,0,0]
    elif B0>BI[-1]:
        bA=[0,-1,-1]
    else:
        bA=[0,0,len(BI)-1]
        while bA[2]-bA[1]>1:
            bA=bi(B0,bA,BI)
        if B0==BI[bA[1]]:
            bA=[1,bA[1]]
        elif B0==BI[bA[2]]:
            bA=[1,bA[2]]
        else:
            bA=[0,bA[1],bA[2]]
   # print(bA)
    return bA
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]
c=0
for i in range(q):
    bA=bs(T[i],S)
    if bA[0]==1:
        c+=1
print(c)

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

int main() {
  string s;
  string t;
  cin >> s >> t;
  string ss = s + s;
  if(ss.find(t) != string::npos) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import sys
def f(h,i,j,k):z=(j-h)*(y-k)-(k-i)*(x-j);return([-1,1][z>0],0)[z==0]
for e in sys.stdin:
 p,q,r,s,t,u,x,y=map(float,e.split())
 print(['NO','YES'][f(p,q,r,s)==f(r,s,t,u)==f(t,u,p,q)])


Measured memory_bytes: 5584
#include <cstdio>
#include <set>
using namespace std;
const int N=200005;
int n,pre[N],cnex[N];
int h[N],tot;
struct Edge{
	int v,next;
}e[N*2];
int a[N],len,mex[N][2];
inline void addEdge(int u,int v){
	e[++tot]=(Edge){v,h[u]}; h[u]=tot;
}
void readData(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&pre[i]);		
		addEdge(pre[i],i);
	}
}
void findCircle(int u){
	static int stk[N],top=0;
	static bool vis[N];
	stk[++top]=u;
	vis[u]=true;
	if(vis[pre[u]]){
		int v=pre[u];
		cnex[v]=u;
		for(;stk[top]!=v;top--){
			cnex[stk[top]]=stk[top-1];
			a[++len]=stk[top];
		}
		a[++len]=v;
		return;
	}
	findCircle(pre[u]);
}
void dfs(int u,int dep){
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			dfs(v,dep+1);
	multiset<int> s;
	s.clear();
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			s.insert(mex[v][0]);
	for(mex[u][0]=0;s.find(mex[u][0])!=s.end();mex[u][0]++);
	if(dep==0)
		for(mex[u][1]=mex[u][0]+1;s.find(mex[u][1])!=s.end();mex[u][1]++);
}
bool run(int x){
	int last=x;
	for(int i=len-1;i>=1;i--){
		int u=a[i];
		last=(mex[u][0]==last)?mex[u][1]:mex[u][0];
	}
	last=(mex[a[len]][0]==last)?mex[a[len]][1]:mex[a[len]][0];
	return x==last;
}
bool judge(){
	for(int i=1;i<=len;i++)
		dfs(a[i],0);
	return run(mex[a[len]][0])||run(mex[a[len]][1]);
}
int main(){
	readData();
	findCircle(1);
	puts(judge()?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 8832
#include  <bits/stdc++.h>
using namespace std;
int main(){
   string s;
   cin >> s;
   if(s == "Sunny") cout << "Cloudy" << endl;
   else if(s == "Cloudy") cout << "Rainy" << endl;
   else cout << "Sunny" << endl;
}
//ctrl + shift + b

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


int main(){
    int N,D,X[10][10];
    cin >> N >> D;
    for(int i=0;i<N;++i) 
        for(int j=0;j<D;++j) cin >> X[i][j];
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = i+1; j < N; j++)
        {
            ll c = 0;
            for (int k = 0; k < D; k++)
            {
                c += (X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
            }
            bool flag = false;
            // sqrt(c)が整数どうかの判定
            for(int k=1;k*k<=c;k++) {
                if(k*k == c) flag = true;
            }
            if(flag) ++ans;
        }
        
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
// 0-1 BFS with virtual vertices
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define Map unordered_map
using namespace std;

int n,m;
Map<ll,vector<pair<ll,int>>> adj;
Map<ll,int> d;
Map<ll,bool> vst;

ll id(int x,int y){
	return 100000000LL*x+y;
}

int main() {
	#ifdef kvutxdy
	freopen("C:/Users/khanh/OneDrive/RoadtoPurple/Code/Codeforces/input.in", "r", stdin);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=0;i<m;++i){
		int u,v,c;
		cin>>u>>v>>c;
		adj[id(u,c)].push_back({id(v,c),0});
		adj[id(v,c)].push_back({id(u,c),0});
		adj[id(u,c)].push_back({id(u,0),0});
		adj[id(u,0)].push_back({id(u,c),1});
		adj[id(v,c)].push_back({id(v,0),0});
		adj[id(v,0)].push_back({id(v,c),1});
	}
	deque<ll> dq;
	d[id(1,0)]=0;
	dq.push_front(id(1,0));
	while(!dq.empty()){
		ll u=dq.front();
		dq.pop_front();
		vst[u]=true;
		for(auto nxt:adj[u]){
			ll v=nxt.fi;
			int c=nxt.se;
			if(vst.count(v)) continue;
			if(!d.count(v)||d[u]+c<d[v]){
				d[v]=d[u]+c;
				if(c==0) dq.push_front(v);
				else dq.push_back(v);
			}
		}
	}
	if(!d.count(id(n,0))) cout<<-1;
	else cout<<d[id(n,0)];
}

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

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
3
10 40 70
20 50 80
30 60 90
ans 210
"""

"""
1
100 10 1
ans 100
"""

"""
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
ans 46
8, 8, 5, 8, 8, 4, 7 -> 48
8, 8, 5, 7, 8, 3, 7 -> 46
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
n = int(input2())
a = np.array([list(map(int, input2().split())) for i in range(n)])  
############ Numpy_solution ############


    
    
    
########## Non_Numpy_solution ##########
arr = a
dp = [[0, 0, 0] for _ in range(n)]
dp[0] = arr[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
print (max(dp[-1]))



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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;

int main(){
    int N, x; cin >> N >> x;
    vector<int> a(N); REP(i, N) cin >> a[i];

    sort(all(a));

    int cnt = 0;
    REP(i, N) {
        if(x <= 0 || a[i] > x) {
            break;
        } else {
            cnt++;
            x = x - a[i];
        }

        if(i == N - 1) {
            if(x > 0) {
               cnt--; 
            }
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
import fractions

N = int(input())
T = [int(input()) for n in range(N)]

def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

ans = T[0]

for index, t in enumerate(T):
  if index == 0:
    continue

  ans = lcm(ans, t)

print(ans)

Measured memory_bytes: 5308