akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000];
char a[1000][1000];
int x,y;
int dfs(int p,int q)
{
    if(a[p][q]=='#')
    return 0;
    if(p>=x || q>=y)
    return 0;
    if(p==x-1 && q==y-1)
    return 1;
    if(dp[p][q]>-1)
    return dp[p][q];
    int n=dfs(p+1,q);
    int m=dfs(p,q+1);
    dp[p][q]=(m+n)%1000000007;
    return dp[p][q];
}
int main()
{
    int i;
    cin>>x>>y;
    memset(dp,-1,sizeof dp);
    for(i=0;i<x;i++)
    {
        cin>>a[i];
    }
    cout<<dfs(0,0)<<endl;
    return 0;
}

Measured memory_bytes: 8464
#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define fr first
#define sc second
#define sz(v) ((int)(v).size())
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,p) for(int i=a-1;i>=p;i--) 
#define M 1000000007
#define vi vector<int>
#define vp vector<pair<int,int> >
#define ml map<int,int>
#define MPI 3.1415926536
using namespace std;
int temp=0,r,l,w,k=0,m1,e,p,q,ans,k1=0,k2=0,d=0,a=0,b=0,s=0,x,y,min1=1000000010,max1=0,m,c=0,t=0,i,n,c1=0,tot=0,t1,k4=0,c2=0,j=0,k3=0;char ch,ch1,ch2;string s1,s2,s3;
signed main()
{
cin>>n;
vi v(n+1),v2(n+1,0);
rep(i,1,n+1)cin>>v[i];
v2[1]=0;
v2[2]=abs(v[2]-v[1]);
rep(i,3,n+1)
{
	v2[i]=min(abs(v2[i-1]+abs(v[i]-v[i-1])),abs(v2[i-2]+abs(v[i]-v[i-2])));
}
cout<<v2[n];
}

Measured memory_bytes: 1792
#include <stdio.h>
int main(void){
  long long int n,a[100000],b[100000],i,j,m=0;
  scanf("%lld",&n);
  for(i=0;i<n;i++)
    scanf("%lld %lld",&a[i],&b[i]);
  for(i=n-1;i>=0;i--){
    if(a[i]%b[i])
      m+=(b[i]*(a[i]/b[i]+1))-a[i];
    if(i>0)
      a[i-1]+=m;
  }
  printf("%lld\n",m);
  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(k,nu)    for(int i=k; i<nu;  i++)
#define rep2(k,n)   for(int j=k; j<n;  j++)
#define INF 1000000000000 //1e+12
#define MOD 10000007 //1e9+7
#define ll long long
#define pb pop_back
template<typename T> inline void chMin(T* a, T* b) {if(*a>*b) *a=*b;}
template<typename T> inline void chMax(T* a, T* b) {if(*a<*b) *a=*b;}
template<typename T> inline int  divUp(T a, T b)   {return ((a+b-1)/b);}
const double PI = acos(-1);

int main(){
    int n; cin >> n;
    int a;
    vector<int> ans(n+1);
    rep(2,n+1){
        cin >> a;
        ans[a-1]++;
    }
    rep(0,n) cout << ans[i] << endl;
    return 0;
}
/*

*/


Measured memory_bytes: 3984
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

const int N = 26, D = 365;

using namespace std;
int main() {
    int d;
    cin >> d;
    vector<int> c(N);
    vector<vector<int>> s(D, vector<int>(N));
    for (int i = 0; i < N; ++i)
        cin >> c[i];
    for (int i = 0; i < d; ++i)
        for (int j = 0; j < N; ++j)
            cin >> s[i][j];
    vector<int> ans;
    double best = LLONG_MIN;
    for (int start = 0; start < N; ++start) {
        for (int second = 0; second < N; ++second) {
            double tot = s[0][start] + s[1][second];
            vector<int> last(N, 0), cans = {start + 1, second + 1};
            for (int i = 0; i < N; ++i) {
                if (i != start)
                    tot -= c[i];
                if (i != second) {
                    if (i == start)
                        tot -= c[i];
                    else
                        tot -= c[i] * 2;
                }
            }
            last[start] = 1;
            last[second] = 2;
            for (int i = 3; i <= d; ++i) {
                int maxt = 0;
                double maxg = LLONG_MIN, maxpts = LLONG_MIN;
                for (int j = 0; j < N; ++j) {
                    double gain = s[i - 1][j];
                    double pts = gain;
                    for (int k = 0; k < N; ++k)
                        if (k != j) {
                            pts -= c[k] * (i - last[k]);
                            gain -= (double)s[i - 1][k] * c[k] * (i - last[k]);
                        }
                    if (gain > maxg) {
                        maxg = gain;
                        maxpts = pts;
                        maxt = j;
                    }
                }
                last[maxt] = i;
                cans.emplace_back(maxt + 1);
                tot += maxpts;
            }
            if (tot > best) {
                best = tot;
                ans = cans;
            }
        }
    }
    for (int i : ans)
        cout << i << endl;
}


Measured memory_bytes: 3684
H, W = map(int, input().split())
S = [input() for _ in range(H)]

def getBomb(x, y):
  if x < 0 or y < 0 or x >= W or y >= H:
    return 0
  if S[y][x] == "#":
    return  1
  return 0

def getBombNum(x, y):
  total = 0
  for i in range(-1, 2):
    for j in range(-1, 2):
      if i == 0 and j == 0:
        if getBomb(x, y) == 1:
          return -1
      else:
        total += getBomb(x + i, y + j)
  return total

table = [0] * (W * H)
for y in range(H):
  for x in range(W):
    num = getBombNum(x, y)
    if num < 0:
      print("#", end="")
    else:
      print(num, end="")
  print()


Measured memory_bytes: 74572
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, i, j, t=0, b=0, sum=1;
  cin >> N;
  vector<int> card(N, 0);
  
  for(i=0; i<N; i++){
    cin >> card[i];
  }
  while(1){
    b=0;
    for(i=0; i<N; i++){
      if(card[i] < card[i+1] && i != N-1){
        t= card[i+1];
        card[i+1] = card[i];
        card[i] = t;
        b++;
      }
    }
    if(b==0)
      break;
  }
  for(i=0; i<N; i++){
    if(card[i] != card[i+1] && i != N-1){
      sum++;
    }
  }
  cout << sum << endl;
}
  

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n;
  scanf("%d", &n);

  int a[n];
  for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
  }

  for(int i = n - 1; i >= 0; i--){
        printf("%d", a[i]);
        if(i != 0){printf(" ");}
  }

  printf("\n");

  return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k;
    long long ans = 0;
    cin >> n >> k;
    vector<int> h(n);
    for(int i=0; i<n; i++) cin >> h[i];
    
    sort(h.begin(), h.end());

    for(int i=0; i<n-k; i++) ans += h[i];

    cout << ans << endl;

    return 0;
}

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

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

	int n, k;
	string s;
	cin >> n >> s >> k;
	for (int i=0; i<n; i++){
		if (s[i]!=s[k-1]) s[i]='*';
	}
	cout << s << "\n";
}

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

const int N = int(1e5 + 10);
int a[N];

int main() {
    int n, m;
    
    scanf("%d %d", &n, &m);
    
    int tot = 0;
    
    for(int i = 0 ; i < n ; i++){ 
        scanf("%d", &a[i]);
        
        tot += a[i];
    }
    
    int add = 0;
    
    for(int i = 0 ; i < n ; i++){
        if(tot <= a[i] * 4 * m){
            add++;  
        }
    }
    
    printf("%s\n", add >= m ? "Yes" : "No");
    
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

ll p = 1e9+7;
ll x = rand()%p, y = rand() % p;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> board(2*n, vector<int> (2*n));

	rep(i,0,n) rep(j,0,n){
		char c;
		cin >> c;
		board[i][j] = board[i+n][j] = board[i][n+j] = board[i+n][j+n] = c - 'a';
	}

	vector<vector<ll>> pre(2*n+1, vector<ll>(2*n+1));
	rep(i,0,2*n) rep(j,0,2*n){
		pre[i+1][j+1] = (-x*y%p*pre[i][j] + x*pre[i+1][j] + y*pre[i][j+1] + board[i][j]) % p;
	}

	vector<vector<ll>> erp(2*n+1, vector<ll>(2*n+1));
	rep(i,0,2*n) rep(j,0,2*n){
		erp[i+1][j+1] = (-x*y%p*erp[i][j] + y*erp[i+1][j] + x*erp[i][j+1] + board[i][j]) % p;
	}

	vector<ll> px(2*n+1, 1), py(2*n+1, 1);
	rep(i,0,2*n) px[i+1] = px[i] * x % p;
	rep(i,0,2*n) py[i+1] = py[i] * y % p;

	int ans = 0;

	rep(a,0,n) rep(b,0,n){
		ll res = pre[n+a][n+b] - pre[a][n+b]*py[n] - pre[n+a][b]*px[n] + pre[a][b] * px[n] % p * py[n];
		res -= erp[n+a][n+b] - erp[a][n+b]*px[n] - erp[n+a][b]*py[n] + erp[a][b] * py[n] % p * px[n];
		res %= p;
		if(res == 0){
			ans++;
			cerr << a << ' ' << b << endl;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 7424
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define ll long long int
#define ld double
#define pi pair<ll,ll>
#define pb push_back
#define pf push_front
#define pu push
#define po pop
#define fi first
#define se second
#define mk make_pair
#define ve vector
#define lr(n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define be begin
#define sz(a) (ll)a.size()
#define INF 1e18
 
typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
 
ll mod=1e9+7;
// ll gcd(ll a, ll b){
//     if(a<b) swap(a,b);
//     if(b==0) return a;
//     return gcd(b,a%b);
// }
 
// ll fun(ll x, ll y){
//     ll rem=1;
//     while(y!=0){
//         if(y%2==1){
//             rem=(rem*x)%mod;
//         }
//         x=(x*x)%mod;
//         y/=2;
//     }
//     return rem;
// }

ll dp[10010][110];
char s[10010];
ll d,n;
ll ans=0;


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>&s[1];
	cin>>d;
	n=strlen(&s[1]);
	for(ll i=0;i<=n;i++) for(ll j=0;j<d;j++) dp[i][j]=0;
	dp[0][0]=1;
	for(ll i=1;i<=n;i++){
		for(ll k=0;k<d;k++){
			for(ll j=0;j<10;j++){
				dp[i][(k+j)%d]=(dp[i][(k+j)%d]+dp[i-1][k])%mod;
			}
		}
	}
	ll x=0;
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<(s[i]-'0');j++){
			ans=(ans+dp[n-i][(d-(x+j)%d)%d])%mod;
		}
		x=(x+s[i]-'0')%d;
	}
	if(x==0) ans++;
	cout << (ans-1+mod)%mod << "\n";
	return 0;
}

Measured memory_bytes: 8832
N=list(input())
ans=0
for i in range(2**(len(N)-1)):
   s=N[0]
   for j in range(len(N)-1):
      if (i >> j) & 1:
         s=s+"+"+N[j+1]
      else:
         s=s+N[j+1]
   ans+=eval(s)
print(ans)

Measured memory_bytes: 3060
/**
 * Motto:   To Become Better Than Me
 * Author: cherry0697
 **/

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

#define rep(i,n) for(i=0;i<n;i++)
#define repc(i,a,n) for(i=a;i<n;i++)
#define repa(i,a,n) for(i=a;i<=n;i++)
#define repb(i,a,n) for(i=a;i>=n;i--)
#define trav(a,x) for(auto a=x.begin();a!=x.end();a++)
#define all(x) x.begin(),x.end()
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef vector <long long int> vi;

void solve()
{
  ll n;
  cin>>n;

  ll a[n];
  ll b[n],i,temp1,temp2;

  rep(i,n)
  {
    cin>>a[i];
    b[i]=a[i];
  }

  sort(a,a+n);

  temp1=a[n-1];
  temp2=a[n-2];

  rep(i,n)
  {
    if(b[i]==temp1)
      cout<<temp2<<endl;
    else
      cout<<temp1<<endl;
  }
}

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

  int t;
  t=1;

  while(t--)
    solve();

return 0;
}


Measured memory_bytes: 4736
#include <iostream>

using namespace std;

int main() {
  int a, b, c, k, max, ans = 0;

  cin >> a >> b >> c >> k;

  max = a;

  if (max < b) {
    max = b;
  }
  if (max < c) {
    max = c;
  }

  ans = max;

  for (int i = 1; i <= k; i++) {
    ans *= 2;
  }

  ans += a + b + c - max;

  cout << ans << endl;

  return 0;
}


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

int main() {
    int n; cin >> n;
    set<string> used;
    vector<string> words(n);
    for (int i=0; i<n; ++i) {
        cin >> words[i];
        used.insert(words[i]);
    }
    int ans = true;
    if (used.size() != words.size()) ans = false;
    for (int i=1; i<n; ++i) {
        if (words[i-1].back() != words[i][0]) ans = false;
    }
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
	int N, M;
	cin >> N >> M;
	vector<int> A(M);
	for(int i=0;i<M;i++)cin >> A[i];

	vector<int> odd, even;
	for(int x : A){
		if(x % 2 == 0){
			even.push_back(x);
		} else {
			odd.push_back(x);
		}
	}
	if(odd.size() >= 3){
		cout << "Impossible" << endl;
		return 0;
	}

	vector<int> a, b;
	if(M == 1){
		a = A;
		b.push_back(a[0] - 1);
		b.push_back(1);
	} else {
		if(odd.size() == 0){
			a = even;
		} else {
			a = odd;
			a.insert(a.begin() + 1, even.begin(), even.end());
		}
		for(int i=0;i<a.size();i++){
			if(i == 0)b.push_back(a[i] - 1);
			else if(i == a.size() - 1)b.push_back(a[i] + 1);
			else b.push_back(a[i]);
		}
	}

	if(b.front() == 0)b.erase(b.begin());
	
	for(int x : a)cout << x << " ";
	cout << endl;
	cout << b.size() << endl;
	for(int x : b)cout << x << " ";
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    long long N, A, B;
    cin >> N >> A >> B;
    long long ans = 0;
    if (A > B)
    {
        ans = 0;
    }else if (A == B)
    {
        ans = 1;
    }else if(A < B)
    {
        if (1 == N)
        {
            ans = 0;
        }else if (2 == N)
        {
            ans = 1;
        }
        else
        {
            ans = (B - A) * (N - 2) + 1;
        }
        
    }
    
    cout << ans << endl;
    
    return 0;
}

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

int main(){
    unsigned Num;
    unsigned num;

    cin>>Num>>num;

    int var[Num];

    double sum = 0;//総得票数

    for(unsigned i = 0;i < Num;i++){
        cin>>var[i];
        sum+=var[i];
    }

    double a = sum/(4*num);//条件

    int counter = 0;

    for(unsigned i = 0;i < Num;i++){
        if(var[i]>=a){
            counter++;
        }
    }

    if(counter>=num){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vi32 d(n);
  cin >> d;
  sort(all(d));
  if (d[0] == 0) {
    cout << 0 << endl;
    return;
  }
  vi32 l(25);
  l[24] = 1;
  bool right = false;
  rep(i, n) {
    int t = d[i];
    if (l[t] && l[24-t]) {
      cout << 0 << endl;
      return;
    }
    if (right) l[24-t] = 1;
    else l[t] = 1;
    right = !right;
  }
  int ans = 1e9;
  int cnt = 1;
  reps(i, 24) {
    if (l[i]) {
      amin(ans, cnt);
      cnt = 1;
    } else {
      cnt++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
N, A, B = map(int, input().split())
S = input()

total = 0
tot_b = 0

ans = []

for s in S:
    if s == "a" and total < A + B:
        ans.append("Yes")
        total += 1
    elif s == "b" and total < A + B and tot_b < B:
        ans.append("Yes")
        tot_b += 1
        total += 1
    else:
        ans.append("No")

print(*ans, sep="\n")


Measured memory_bytes: 6344
N = int(input())

link = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    link[u - 1].append((v - 1, w))
    link[v - 1].append((u - 1, w))

d = [-1] * N
d[0] = 0
q = [0]
while q:
    p = q.pop()
    for n, w in link[p]:
        if d[n] == -1:
            d[n] = d[p] + w
            q.append(n)

for i in d:
    print(i % 2)


Measured memory_bytes: 42796
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b;
inline ll read()
{
	ll x=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*ff;
}
int main()
{
	//freopen("1.in","r",stdin);
	n=read();a=read();b=read();
	ll zhou=n/(a+b);
	ll yu=n%(a+b);
	ll c=zhou*a+(yu>a?a:yu);
	printf("%lld",c);
	return 0;
}


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

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int INF = int (1e9) + int (1e5);
const ll INFL = ll(2e18) + ll(1e10);
const ui MOD = 1E9 + 7;
const double EPS = 1e-9;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define ROF(i,x) for(int i = (x) ; i >= 0 ; --i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ODD(x) (((x)&1)==0?(0):(1))
#define sign(x) ((x > 0) - (x < 0))
std::mt19937_64  generator(std::chrono::system_clock::now().time_since_epoch().count());

inline ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b) { return a ? gcd(b%a, a): b; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }


void READ(bool _local){
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
    if (_local)
        freopen ("in.txt", "r", stdin);
#endif
}

/// tree con LCA procesamiento O(N log N) consultas O(log N)
struct tree {
    int N, timer, l,root;
    vector<vii> G;
//   vii children[NMAX];
    vvi up;
    vi tin,tout,level;
    tree(int n,int _root) : N(n),root(_root) {
        tin.resize(n),tout.resize(n),level.resize(n);
        up.resize(n),G.resize(n);
    };

    void add_edge(int a, int b, int w = 0) {
        G[a].push_back(MP(b, w));
        G[b].push_back(MP(a, w));
    }

    void build() {
        l = log2(N)+1;
        for(int i = 0; i < N; ++i) up[i].resize(l + 1);
        dfs(root,root);
    }

    void dfs(int node, int p,int lev=0) {
        tin[node] = ++timer;
        level[node]=lev++;
        up[node][0] = p;
        for(int i = 1; i <= l; ++i)
            up[node][i] = up[up[node][i - 1]][i - 1];
        for(auto c : G[node])
            if(c.first != p) dfs(c.first, node,lev);
        tout[node] = ++timer;
    }

    bool upper(int a, int b) {return tin[a] <= tin[b] && tout[a] >= tout[b];}

    int lca(int a, int b) {
        if(upper(a, b)) return a;
        if(upper(b, a)) return b;
        for(int i = l; i >= 0; --i)
            if(!upper(up[a][i], b))
                a = up[a][i];
        return up[a][0];
    }

    int dist(int u,int v){
        return abs(level[u]-level[v]);
    }
};


int main() {
    READ(1);
    int n,u,v;cin>>n>>u>>v;
    --u,--v;
    tree t(n,v);
    FOR(i,n-1){
        int x,y;cin>>x>>y;
        t.add_edge(x-1,y-1);
    }
    t.build();
    int ret=1;
    for(int i=0;i<n;++i) {
        if (t.tin[i]+1==t.tout[i] && t.level[i]>ret){
            int l=t.lca(i,u);
            int d1=t.dist(u,l);
            if (d1<t.level[l]){
                ret=t.level[i];
            }
        }
    }
    cout << ret -1;
}



Measured memory_bytes: 20224
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}
#define SZ 666666
int n,a[SZ],d[SZ],fe[SZ]; Edg
void dfs(int x,int f=0)
{
	if(d[x]==1)
	{
		fe[x]=a[x];
		return;
	}
	int g=a[x]+a[x];
	for esb(x,e,b) if(b!=f)
	{
		dfs(b,x),g-=fe[b];
		if(fe[b]>a[x])
		{
			puts("NO");
			exit(0);
		}
	}
	if(g<0||g>a[x])
	{
		puts("NO");
		exit(0);
	}
	fe[x]=g;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	for(int i=1;i<n;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		adde(a,b); ++d[a],++d[b];
	}
	if(n==2)
	{
		if(a[1]==a[2]) puts("YES");
		else puts("NO");
		return 0;
	}
	int x=0;
	for(int i=1;i<=n;++i) if(d[i]>1) x=i;
	dfs(x);
	if(fe[x]!=0)
	{
		puts("NO");
		return 0;
	}
	puts("YES");
}


Measured memory_bytes: 19072
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int BingoCard[3][3], N , Number[10];
    bool CheckCard[3][3] = {0}, Bingo = 0;
    long ans = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
        cin >> BingoCard[i][j];
        }
    }
    cin >> N;
    for(int k = 0; k < N; k++){
        cin >> Number[k];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                 if(BingoCard[i][j] == Number[k]){
                     CheckCard[i][j] = 1;
    		    }
    		}
    	}
    }
    
    for(int i = 0; i < 3; i++){
        if(CheckCard[i][0] && CheckCard[i][1] && CheckCard[i][2]){
            Bingo = 1;
        }
        else if(CheckCard[0][i] && CheckCard[1][i] && CheckCard[2][i]){
            Bingo = 1;
        }
    }
    if(CheckCard[0][0] && CheckCard[1][1] && CheckCard[2][2]){
        Bingo = 1;
    }
    else if(CheckCard[0][2] && CheckCard[1][1] && CheckCard[2][0]){
        Bingo = 1;
    }
    if(Bingo){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
/*
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cout << CheckCard[i][j] << " ";
        }
        cout << endl;
    }
    cout << N <<endl;
    for(int i = 0; i < N; i++){
        cout << Number[i] << endl;;
    }
*/
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	vector<int> x(4), y(4);
	cin >> x[0] >> y[0] >> x[1] >> y[1];
	x[2] = x[1] - (y[1] - y[0]);
	y[2] = y[1] + (x[1] - x[0]);
	x[3] = x[2] - (x[1] - x[0]);
	y[3] = y[2] - (y[1] - y[0]);

	cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3] << "\n";

	return 0;
}


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

#define N 100005

int n, m;

vector<int> to[N];

int dfn[N], low[N], bel[N], tim, cnt;

stack<int> stk;
bitset< N > vis;

void tarjan(int u)
{
	dfn[u] = low[u] = ++tim; stk.push(u); vis.set(u);
	
	for (auto v : to[u])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	
	if (low[u] == dfn[u])
	{
		int t; ++cnt;
		do
		{
			t = stk.top(); stk.pop();
			bel[t] = cnt; vis.reset(t);
		}
		while (t != u);
	}
}

signed main(void)
{
	cin >> n >> m;
	
	for (int u, v; m--; )
	{
		cin >> u >> v;
		to[u].push_back(v);
	}
	
	for (int i = 0; i < n; ++i)
		if (!dfn[i])tarjan(i);
	
	int q; cin >> q;
	
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		cout << (bel[x] == bel[y]) << endl;
	}
}

Measured memory_bytes: 6568
def solve(a,b):
	start,end= int(a/0.08),int((a+1)/0.08)
	for i in range(start,end):
		if int(i*0.10)==b:
			if int(i*0.08)==a:
				return i
	return -1
a,b= map(int,input().split(' '))
print(solve(a,b))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void){
	int n;
	vector<int> v(101, 0);
	while(cin >> n){
		v[n]++;
	}
	int mx = 0;
	rep(i,v.size()){
		if(v[i] > mx)mx = v[i];
	}
	rep(i,v.size()){
		if(v[i] == mx)cout << i << endl;
	}

	return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


// Union-Find Disjoint Sets Library written in OOP manner, using both path compression and union by rank heuristics
// initialize: UnionFind UF(N)

class UnionFind {                                              // OOP style
private:
	vector<int> p, rank, setSize;
	// p = path toward the root of disjoint set; p[i] = i means it is root
	// rank = upper bound of the actual height of the tree; not reliable as accurate measure
	// setSize = size of each disjoint set

	int numSets;
public:
	UnionFind(int N) {
		setSize.assign(N, 1);
		numSets = N;
		rank.assign(N, 0);
		p.assign(N, 0);
		for (int i = 0; i < N; i++) p[i] = i;	// each belongs to its own set
	}

	int findSet(int i) {
		return (p[i] == i) ? i : (p[i] = findSet(p[i]));		// path compression: cut short of the path if possible
	}

	bool isSameSet(int i, int j) {
		return findSet(i) == findSet(j);
	}

	void unionSet(int i, int j) {
		if (!isSameSet(i, j)) {
			numSets--;
			int x = findSet(i), y = findSet(j);
			// rank is used to keep the tree short
			if (rank[x] > rank[y]) { p[y] = x; setSize[x] += setSize[y]; }
			else {
				p[x] = y; setSize[y] += setSize[x];
				if (rank[x] == rank[y]) rank[y]++;
			}
		}
	}

	int numDisjointSets() {		// # of disjoint sets
		return numSets;
	}

	int sizeOfSet(int i) {		// size of set
		return setSize[findSet(i)];
	}
};

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

	int n, m, i, j, k, ans;
	cin >> n >> m;
	vector<pair<int, int>> edge(m);
	for (i = 0; i < m; i++) cin >> edge[i].first >> edge[i].second;

	ans = 0;
	for (i = 0; i < m; i++) {
		UnionFind uf(n + 1);
		for (j = 0; j < m; j++) {
			if (i != j) uf.unionSet(edge[j].first, edge[j].second);
		}
		if (uf.numDisjointSets() > 2) ans++;
	}
	cout << ans << "\n";

	return 0;
}


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

ll f(ll x){
    if(x == 1) return 1;
    else return f(x/2)*2 + 1;
}

int main(){
    ll h;
    cin >> h;
    cout << f(h) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

const static int N_MAX = 100;

void Swap(int &a, int &b)
{
	int t = b;
	b = a;
	a = t;
}

int BubbleSort(int *A, int N)
{
	int count = 0;
	bool flag = true;
	while (flag)
	{
		flag = false;
		for (int i = N - 1; i > 0; i--)
		{
			if (A[i - 1] > A[i])
			{
				swap(A[i - 1], A[i]);
				flag = true;
				count++;
			}
		}
	}

       return count;
}

int main()
{
	int N, A[N_MAX],sum;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	sum = BubbleSort(A, N);

	for (int i = 0; i < N; i++)
	{
		if (i <N-1)
			cout << A[i] << ' ';
	}
	cout << A[N-1] << endl << sum << endl;

	return 0;
}


Measured memory_bytes: 3100
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        try{

            int a = scanner.nextInt();
            int b = scanner.nextInt();

            if(a<b){
                System.out.println("a < b");
            }else if(a>b){
                System.out.println("a > b");
            }else{
                System.out.println("a == b");
            }

        }catch(NumberFormatException e){
                System.out.println(e);
        }finally{
            scanner.close();
        }
    }
    
}


Measured memory_bytes: 26252
#include<bits/stdc++.h>
#include<math.h>
#include<vector>
#include <iostream>
//#include <algorithm>
#include <limits>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define ll long long
/*void printdp(int N,ll Vmax){
	rep(i,N+1){
		for(ll j=0;j<Vmax+1;j++){
			if(dp[i][j]==llMAX)continue;
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	return;
}*/
int main(void){
	int N;
	vector<double> p;
	cin >> N;
	p=vector<double>(N+1,0);
	rep(i,N){
		cin >> p[i+1];
	}
	vector<vector<double>> dp;
	dp = vector<vector<double>>(N+1,vector<double>(N+1,0));
	dp[0][0]=1;
	/*rep(i,N+1){
		rep(j,N+1){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	rep(i,N){
		rep(j,N){
			if(i>=j){
				dp[i+1][j+1]+=dp[i][j]*p[i+1];
				dp[i+1][j] += dp[i][j]*(1-p[i+1]);
			}
		}
	}
	/*rep(i,N+1){
		rep(j,N+1){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	double ans = 0.0;
	for(int i=(N+1)/2;i<N+1;i++){
		ans +=dp[N][i];
	}
	cout <<fixed << setprecision(10)<< ans;
	return 0;
}

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

int main()
{
	int i,j,k,n,m;
	string s,t;
	while(cin>>s>>t)
	{
		if(s == t)
			cout<<"Yes"<<endl;
		else
		{
			int flag = 0;
			int k=0;
			while(1)
			{
				s = s[s.length()-1] + s;
				s.erase(s.end() - 1);
				if(s == t)
				{
					cout<<"Yes"<<endl;
					flag = 1;
					break;
				}
				k++;
				if(k>s.length())
					break;
			}
			if(flag == 0)
				cout<<"No"<<endl;
		}
	}
	return 0;
}

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


int main(){
int A,B;
cin >> A >> B;
for (double i = B*10;i < B*10+10;i++) {
  int ans = i*0.08; 
  if (ans == A) {
    cout << i << endl;
    return 0;
  }
}
cout << -1 << endl;

return 0;

}

Measured memory_bytes: 256
main(i,m,h,t,a){
    char s[201];
    for(;scanf("%s%d",s,&m),s[0]!='-';puts("")){
        a=strlen(s);
        for(i=t=0;i<m;scanf("%d",&h),t+=h,i++);
        for(i=0;i<a;printf("%c",s[(t+i++)%a]));
    }
}

Measured memory_bytes: 1860
#include <cstdio>

using namespace std;

int gcd(int a, int b) {
  while (b) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int main() {
  int n;
  scanf("%d", &n);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        ans += gcd(i, gcd(j, k));
      }
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 1732
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <limits.h>
#include <float.h>
#include <numeric>
#include <queue>
#include <deque>

using namespace std;

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

int myabs(int x){
    if(x < 0){
        x = -x;
    }
    return x;
}

vector<int> x_num, y_num;

int main(){
    string s;
    int x, y;
    cin >> s;
    cin >> x >> y;
    int len = s.length();

    int start = 0;
    while(s[start] == 'F' && start < len){
        x--;
        start++;
    }

    int dir = 0;
    int tmp = 0;
    for(int i = start; i < len; i++){
        if(s[i] == 'T'){
            if(tmp > 0){
                if(dir == 0){
                    x_num.push_back(tmp);
                }
                else{
                    y_num.push_back(tmp);
                }
                tmp = 0;
            }
            dir = 1 - dir;
        }
        else{
            tmp++;
        }
    }
    if(tmp > 0){
        if(dir == 0){
            x_num.push_back(tmp);
        }
        else{
            y_num.push_back(tmp);
        }
    }

    int x_value[2][8100], y_value[2][8100];
    fill(x_value[0], x_value[0]+8100, 0);
    fill(y_value[0], y_value[0]+8100, 0);
    fill(x_value[1], x_value[1]+8100, 0);
    fill(y_value[1], y_value[1]+8100, 0);

    x_value[0][0] = 1; y_value[0][0] = 1;
    int x_sum = 0, y_sum = 0;
    for(int i = 0; i < x_num.size(); i++){
        x_sum += x_num[i];
        for(int j = 0; j < x_num[j]; j++){
            x_value[1][j] = x_value[0][j];
        }
        for(int j = x_num[i]; j < 8100; j++){
            x_value[1][j] = max(x_value[0][j-x_num[i]], x_value[0][j]);
        }
        for(int j = 0; j < 8100; j++){
            x_value[0][j] = x_value[1][j];
        }

    }
    for(int i = 0; i < y_num.size(); i++){
        y_sum += y_num[i];
        for(int j = 0; j < y_num[j]; j++){
            y_value[1][j] = y_value[0][j];
        }
        for(int j = y_num[i]; j < 8100; j++){
            y_value[1][j] = max(y_value[0][j-y_num[i]], y_value[0][j]);
        }
        for(int j = 0; j < 8100; j++){
            y_value[0][j] = y_value[1][j];
        }
    }

    if(x_sum - myabs(x) < 0 || y_sum - myabs(y) < 0){
        cout << "No" << endl;
    }
    else if((x_sum - myabs(x)) % 2 == 1 || (y_sum - myabs(y)) % 2 == 1){
        cout << "No" << endl;
    }
    else if(x_value[0][(x_sum - myabs(x))/2] == 1 && y_value[0][(y_sum - myabs(y))/2] == 1){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }


    return 0;
}


Measured memory_bytes: 512
import sys
fin = sys.stdin.readline


MAX_INT = (1 << 63) - 1
N, K = [int(elem) for elem in fin().split()]
h_list = [int(elem) for elem in fin().split()]

dp = [MAX_INT] * N
dp[0] = 0
for i in range(1, N):
    min_cost = MAX_INT
    for j in range(max(0, i - K), i):
        min_cost = min(min_cost, dp[j] + abs(h_list[i] - h_list[j]))
    dp[i] = min_cost

print(dp[N - 1])


Measured memory_bytes: 53724
#include <bits/stdc++.h>
#include <unordered_map>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,c;
    cin >> a >> b >> c;
    if(a + c == 2 * b){
        print("YES");
    }else{
        print("NO");
    }
}


Measured memory_bytes: 256
shape = list(map(int, input().split()))
shape.sort()
N, M = shape
# print(N, M)

if N == 1:
    if M > 2:
        ans = M - 2
    else:
        ans = M
elif N == 2:
    ans = 0
else:
    ans = (N - 2) * (M - 2)
print(ans)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
char s[300005];
int sum[300000];
int main()
{
    int n;
    //int sum
    while(cin>>n)
    {
        memset(sum,0,sizeof(sum));
        scanf("%s",s);
        int sume=0,sumw=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='E')
                sume++;
            else
                sumw++;
        }
        int e=0,w=0;
        for(int i=0;i<n;i++)
        {
            sum[i]=w;
            if(s[i]=='W')
            {
                w++;
            }

            if(s[i]=='E')
            {
                e++;
            }
            sum[i]=sum[i]+sume-e;
        }
        int minn=999999;
        for(int i=0;i<n;i++)
        {
            if(sum[i]<minn)
                minn=sum[i];
        }
        //sort(sum,sum+n);
        cout<<minn<<endl;

    }
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> v(N + 1, 0);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		++v[a];
		++v[b];
	}

	bool ok = true;
	for (int i = 0; i <= N; ++i) {
		if (v[i] % 2 == 1) { ok = false; }
	}

	if (ok) { cout << "YES" << endl; }
	else { cout << "NO" << endl; }

	return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)


typedef long long ll;
#define INF 1LL<<60
int N;
vector<int> E[101010];
int K;
ll P[101010];
//-----------------------------------------------------------------
ll L[101010], R[101010];
bool ans = true;
void dfs1(int cur, int par) {
	if (P[cur] != INF)
		L[cur] = R[cur] = P[cur];
	else
		L[cur] = INF;

	for (int to : E[cur]) if (to != par) {
		dfs1(to, cur);

		if (L[to] == INF) {
			// 下が空
			continue;
		} else if (L[cur] == INF) {
			// こっちが空
			L[cur] = L[to] - 1;
			R[cur] = R[to] + 1;
		}
		else {
			// どっちもある
			ll LL = L[to] - 1;
			ll RR = R[to] + 1;
			
			// 偶奇判定
			if ((LL + L[cur]) % 2 != 0) {
				//printf("A[%d]\n", cur);
				ans = false;
				return;
			}

			// かぶってるか判定
			L[cur] = max(LL, L[cur]);
			R[cur] = min(RR, R[cur]);

			if (R[cur] < L[cur]) {
				//printf("B");
				ans = false;
				return;
			}
		}
	}
}
//-----------------------------------------------------------------
void dfs2(int cur, int par) {
	if (P[cur] == INF) {
		if (par == 0)
			P[cur] = L[cur];
		else if (L[cur] == INF)
			P[cur] = P[par] - 1;
		else {
			ll PP = P[par] + 1;
			if (L[cur] <= PP && PP <= R[cur])
				P[cur] = P[par] + 1;
			else
				P[cur] = P[par] - 1;
		}
	}
	for (int to : E[cur]) if (to != par) dfs2(to, cur);
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	cin >> K;
	rep(i, 1, N + 1) P[i] = INF;
	rep(i, 0, K) {
		int v, p;
		cin >> v >> p;
		P[v] = p;
	}

	dfs1(1, 0);

	/*rep(i, 0, N)
		printf("<%d : %d>\n", i + 1, P[i + 1]);

	rep(i, 0, N) {
		printf("%d : [%d, %d]\n", i + 1, L[i + 1], R[i + 1]);
	}*/

	if (!ans) {
		cout << "No" << endl;
		return 0;
	}

	dfs2(1, 0);
	
	printf("Yes\n");
	rep(i, 1, N + 1) printf("%lld\n", P[i]);
}

Measured memory_bytes: 16512
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(i64, i64); n],
        cd: [(i64, i64); m],
    }
    let mut ans = vec![0; n];
    for i in 0..ab.len() {
        let mut min = std::i64::MAX;
        let mut cdi = 0;
        for j in 0..cd.len() {
            let tmp = i64::abs(ab[i].0 - cd[j].0) + i64::abs(ab[i].1 - cd[j].1);
            if min > tmp {
                min = tmp;
                cdi = j;
            }
        }
        ans[i] = cdi;
    }
    for i in 0..ans.len() {
        println!("{}", ans[i] + 1);
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define SIZE 402
using namespace std;

typedef pair<int, int> P;
const int di[] = {0, 0, -1, 1};
const int dj[] = {-1, 1, 0, 0};
char s[SIZE][SIZE];
int t[SIZE][SIZE];

int main(){
  int h, w;
  cin >> h >> w;
  long long result = 0;
  queue<P> q;
  
  int im = h+1, jm = w+1;
  for(int i=0; i<=im; i++) t[i][0] = t[i][jm] = 1;
  for(int j=0; j<=jm; j++) t[0][j] = t[im][j] = 1;
  
  for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++)
      scanf(" %c", &s[i][j]);
  
  for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++){
      int bl = 0, wh = 0;
      if (t[i][j]==0){
        t[i][j] = 1;
        q.push(P(i, j));
      }
      while( !q.empty() ){
        P p = q.front();
        q.pop();
        if(s[p.first][p.second] == '#')bl++; else wh++;
        for(int a=0; a<4; a++){
          int k = p.first + di[a];
          int l = p.second+ dj[a];
          if(
            t[k][l] == 0
            && s[p.first][p.second] != s[k][l]
          ){
            t[k][l] = 1;
            q.push(P(k,l));
          }
        }
      }
      result += (long long)bl * (long long)wh;
    }
  cout << result << endl;
}

Measured memory_bytes: 1024
N,K = map(int,input().split())
a_num = [0 for i in range(10**5+1)]
for i in range(N):
    a,b = map(int,input().split())
    a_num[a] += b #aの場所にbを加算することによってKが0または負の値になるときの答えの数がわかる

for i in range(len(a_num)):
    K -= a_num[i]
    if K <= 0: #もしKが0以下になったらiが答えになる
        print(i)
        exit()



Measured memory_bytes: 5928
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    s = S()
    print(s.count("1"))
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 39408
#include<iostream>

using namespace std;

int main()
{
	bool ketemu;
	string s;
	long long i,l,r;
	cin >> s;
	ketemu = false;
	if(s.length() == 2)
	{
		if(s[0] == s[1])
		{
			ketemu = true;
			l = 0;
			r = 1;
		}
	}
	else
	{
		for(i=0;i<s.length()-2;i++)
		{
			if(s[i] == s[i+1])
			{
				l = i;
				r = i+1;
				ketemu = true;
				break;
			}
			else if(s[i] == s[i+2])
			{
				l = i;
				r = i+2;
				ketemu = true;
				break;
			}
			else if(s[i+1] == s[i+2])
			{
				l = i+1;
				r = i+2;
				ketemu = true;
				break;
			}
		}
	}
	if(ketemu)
	{
		cout << l+1 << " " << r+1 << endl;
	}
	else
	{
		cout << "-1 -1" << endl;
	}
}

Measured memory_bytes: 512
#include <iostream>
#define rep(i, n) for(int i=0; i<n; i++)

using namespace std;

int main(void){
  int H, N;
  cin >> H >> N;
  int A[N];
  rep(i, N)
    cin >> A[i];

  int sum = 0;
  rep(i, N)
    sum += A[i];

  if(sum >= H)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <vector>
#include <algorithm>
#define rep(I,N) for(int I=0; I<N; I++)
#define chmin(x,y) x=min(x,y)
#define all(vec) vec.begin(), vec.end()
using namespace std;
typedef long long ll;

int n,m,l;
const int INF = 1001001001;

int main(){
	{auto dmy=scanf("%d %d %d", &n, &m, &l);}
	
	/*
	  read gragh
	  dist_ij = 0	if i=j
	          = c   if there is a route
	          = INF otherwize
	*/
	vector<vector<int>> dist(n, vector<int>(n,INF));
	rep(i,n) dist[i][i] = 0;
	rep(i,m){
		int a,b,c; auto dmy=scanf("%d %d %d", &a, &b, &c);
		a--; b--;
		dist[a][b] = dist[b][a] = c;
	}

	// Warshall-Floyd
	rep(k,n) rep(i,n) rep(j,n) chmin(dist[i][j], dist[i][k]+dist[k][j]);

	// make new gragh 0-1
	vector<vector<int>> dist2(n, vector<int>(n,INF));
	rep(i,n) rep(j,n) if(dist[i][j]<=l) dist2[i][j]=1;
	rep(k,n) rep(i,n) rep(j,n) chmin(dist2[i][j], dist2[i][k]+dist2[k][j]);

	// solve 
	int q;	auto dmy = scanf("%d", &q);
	rep(i,q){
		int s,t; auto dmy = scanf("%d %d", &s, &t);
		s--; t--;
		printf("%d\n", (dist2[s][t]==INF ? -1 : dist2[s][t]-1));
	}
}

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

int main(){

    int n, k; cin >> n >> k;
    vector<int> h(n), dp(n, 1e9+9);
    for(int &u:h) cin >> u;

    dp[0] = 0; for(int i=1; i<n; i++){
        for(int j=1; j<=k; j++)
        if(i>=j) dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
    }cout << dp[n-1] << "\n";

    return 0;
}


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

int main() {
    
    int n[3];
    cin >> n[0];
    cin >> n[1];
    cin >> n[2];

    sort(n, n + 3);

    int diff = 2 * n[2] - n[1] - n[0];
    if(diff % 2  == 0){
        cout << diff / 2 << endl;
    } else {
        cout << ((diff + 1) / 2 ) + 1 << endl;
    }

    return 0;
}
    

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

int main() {
  int N;
  cin >> N;
  vector<string> s(N);
  for (int i = 0; i < N; i++) {
    cin >> s.at(i);
  }
  int M;
  cin >> M;
  vector<string> t(M);
  for (int i = 0; i < M; i++) {
    cin >> t.at(i);
  }
  
  int count, max = 0;
  for(int i=0; i<N; i++){
    count = 0;
    for(int j=0; j<N; j++){
      if(s.at(i) == s.at(j)){
        count ++;
      }
    }
    for(int j=0; j<M; j++){
      if(s.at(i) == t.at(j)){
        count --;
      }
    }
    if(max < count){
      max = count;
    }
  }
  cout << max;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){

	int n,max=0,sum=0;

	scanf("%d",&n);

	int p[n];
	
	for(int i=0;i<n;i++){
		scanf("%d",&p[i]);
	}

	for(int i=0;i<n;i++){
		sum+=p[i];
		if(max<p[i]){
			max=p[i];
		}
	}

	sum-=max/2;

	printf("%d",sum);
}

Measured memory_bytes: 128