akhauriyash/Code-Regression huggingface dataset:
/*
[arc098] C - Attention
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 300000;

int N;
string s;

int solve() {
    int sum[MAX_N + 1];
    sum[0] = 0;
    for (int i = 0; i < N; i++) {
        sum[i + 1] = sum[i] + (s[i] == 'W' ? 1 : 0);
    }

    int ans = N;
    for (int i = 1; i <= N; i++) {
        ans = min(ans, sum[i - 1] + N - i - (sum[N] - sum[i]));
    }
    return ans;
}

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

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 1924
#include <iostream>
using namespace std;
int main(void){
           int H,W;
   while(1){
           cin>>H>>W;
       if(H==0&&W==0)break;
       for(int a=1;a<=H;a++){
       for(int b=1;b<=W;b++){
           if((a+b)%2==0){cout<<"#";}
           else{cout<<".";}
       }cout<<endl;
       }
cout<<endl;
}
    
    return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, D, N, ans=0;
    char tmp;
    string S;
    cin >> S;
    S[5] = ' ';
    S[13] = ' ';
    
    cout <<S<<endl;
    
    // if(tmp == '-')
    // 	cout << A-B<<endl;
    // else
    // 	cout <<A+B<<endl;
    

    // string S;
    // cin >>S;
    // cout << S + "pp"<<endl;
    // if(A+B==C || B+C==A || C+A==B)
    // 	puts("Yes");
    // else
    // 	puts("No");
    	
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL n,k;
    cin >> n >> k;
    vector<LL> a(n),b(n);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }
    
    LL bitlen = 1;
    while((1 << bitlen) <= k){
        bitlen++;
    }
    vector<LL> nbit(bitlen+1,0);
    for(LL j = 1; j < bitlen+1; j++){
        nbit[j] = nbit[j-1] + (1 << (j-1));
    }
    vector<LL> s;
    s.push_back(k);
    LL formask = 1 << bitlen;
    for(LL j = bitlen; j > 0; j--){
        LL jbit = 1 << (j-1);
        if(k&jbit){
            LL mask = formask - 1 - nbit[j];
            LL x = k&mask;
            x |= nbit[j-1];
            s.push_back(x);
        }
    }

    vector<LL> sum(s.size(),0);
    for(int i = 0; i < n; i++){
        for(int l = 0; l < sum.size(); l++){
            if((s[l]&a[i]) == a[i]){
                sum[l] += b[i];
            }
        }
    }

    LL ans = -1;
    for(int i = 0; i < sum.size(); i++){
        ans = max(ans,sum[i]);
    }

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

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

int main() {
  int N, A, l, r;
  A = 0;
  l = 0;
  r = 0;
  cin >> N;
  for ( int i = 0; i < N; i++ ) {
    cin >> l >> r;
    A += ( r - l + 1 );
  }
  cout << A << endl;
}

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

using namespace std;

int main (){
    long long a, b, sum1, sum2, av;
    cin>>a>>b;
    av = (a+b)/2;
    sum1 = abs(a-av);
    sum2 = abs(b-av);
    if(sum1==sum2) cout<<av<<endl;
    else cout<<"IMPOSSIBLE"<<endl;

    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define REP(i,a) FOR(i,0,a)
const ll MAX_N=2e5,INF=1e18;
ll N,K,P[MAX_N+1],sec[MAX_N],negP[MAX_N];
struct segtree{
	vector<ll> ary;
	segtree(ll *a,ll n){
		ll n2=1;
		while(n2<n)n2<<=1;
		ary.resize(n2*2-1);
		REP(i,n2){
			if(i<n){
				ary[i+n2-1]=a[i];
			}else{
				ary[i+n2-1]=INF;
			}
		}
		for(ll k=n2-2;k>=0;k--){
			ary[k]=min(ary[k*2+1],ary[k*2+2]);
		}
	}
	ll query(ll l,ll r){
		ll inx=ary.size()/2,ret=INF;
		while(l<r){
			if(l&1){
				ret=min(ret,ary[inx+l]);
				l++;
			}
			if(r&1){
				ret=min(ret,ary[inx+r-1]);
				r--;
			}
			l>>=1;
			r>>=1;
			inx>>=1;
		}
		return ret;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>K;
	REP(i,N)cin>>P[i];
	P[N]=-INF;
	REP(i,N)negP[i]=-P[i];
	vector<ll> pcan;
	for(ll i=N-1;i>=0;i--){
		if(P[i]<P[i+1]){
			sec[i]=sec[i+1]+1;
		}else{
			sec[i]=1;
		}
	}
	segtree seg(P,N),nseg(negP,N);
	bool cmpflg=false;
	REP(i,N){
		if(sec[i]>=K){
			cmpflg=true;
		}else if(i+K<=N){
			pcan.push_back(i);
		}
	}
	ll ans=(cmpflg?1:0);
	REP(i,pcan.size()){
		ll pi=pcan[i];
		ans++;
		bool f=false;
		FOR(j,i+1,pcan.size()){
			ll pj=pcan[j];
			if((pj>=pi+K)||
				(sec[pi]<pj-pi)||
				(sec[pi+K]<pj-pi)||
				(seg.query(pj,pi+K)<P[pj-1])||
				(-nseg.query(pj,pi+K)>P[pi+K])
				){
				i=j-1;
				f=true;
				break;
			}
		}
		if(!f){
			break;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 15348
def main():
    from math import gcd
    n, *a = map(int, open(0).read().split())
    m = 10 ** 6 + 1

    c = [0] * (m + 1)
    g = a[0]
    for i in a:
        g = gcd(g, i)
        c[i] = 1

    if g > 1:
        pre = "not"
    else:
        for i in range(2, 10 ** 6 + 1):
            if sum(c[i::i]) > 1:
                pre = "setwise"
                break
        else:
            pre = "pairwise"

    print(pre + " coprime")


if __name__ == '__main__':
    main()


Measured memory_bytes: 121544
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define pb push_back
#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define LOOP_IT(s) for(auto it=(s).begin();it!=(s).end();++it)
#define loop for(int i=0;i<n;++i)


int main(int argc,char* argv[])
{
    ZOOM

    string s;
    cin>>s;bool f=0,f2=0;
    int n=s.size();
    loop
    {
        if(s[i]=='A')
            f=1;
        else
            f2=1;
    }
    if(f&f2)
        cout<<"Yes\n";
    else
        cout<<"No\n";

    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 repi(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 bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

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) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
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 power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

template<typename F>
class FixPoint : F
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : F(std::forward<F>(f))
  {}
 
  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};
 
template<typename F>
static inline constexpr decltype(auto)
makeFixPoint(F&& f) noexcept
{
  return FixPoint<F>{std::forward<F>(f)};
}

void solve() {
  i64 N, X; cin >> N >> X;
  auto rec = makeFixPoint([&](auto f, i64 a, i64 b) -> i64 {
    if (a < b) swap(a, b);
    if (a % b == 0) return a / b * 2 * b - b;
    else return a / b * 2 * b + f(b, a % b);
  });
  i64 ans = X + (N - X) + rec(X, N - X);
  cout << ans << '\n';
}


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

int main() {
  int X,ans=0;
  cin>>X;
  while(X>=500){
    X-=500;
    ans+=1000;
  }
  while(X>=5){
    X-=5;
    ans+=5;
  }
  cout<<ans;
}


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

using namespace std;

const int N = 15, inf = 1e9;

int w[N][N], n, m, prep[N][1<<N], dp[N][1<<N]; 

int cost(int s, int t){
	int res = 0, mask = 0;
	for(int i = 0; i < n; ++i) mask += (1 << i) * ((s >> i) & 1);
	for(int i = 0; i < n; ++i) res += prep[i][mask] * ((t >> i) & 1);
	return res;
}

signed main(){
	memset(dp, 0x3f, sizeof(dp));
	
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		int u, v, c;
		cin >> u >> v >> c, --u, --v;
		w[u][v] = w[v][u] = c;
	}
	
	for(int i = 0; i < n; ++i){
		for(int mask = 0; mask < (1<<n); ++mask){
			for(int j = 0; j < n; ++j){
				if(mask & (1<<j)) prep[i][mask] += w[i][j];
			}
		}
	}
	
	dp[0][1] = 0;
	for(int mask = 1; mask < (1<<n); ++mask){
		for(int i = 0; i < n; ++i){
			if(!(mask & (1 << i))){
				for(int j = 0; j < n; ++j){
					if(mask & (1 << j) && w[j][i]){
						dp[i][mask | (1 << i)] = min(dp[i][mask | (1 << i)], dp[j][mask] + cost(mask ^ (1 << j), (1 << i)));
					}
				}
			}
		}
		int comp = (1<<n) - mask;
		for(int sub = comp; sub > 0; sub = (sub - 1) & comp){
			for(int i = 0; i < n; ++i){
				if(mask & (1 << i)){
					dp[i][mask | sub] = min(dp[i][mask | sub], dp[i][mask] + cost(mask ^ (1 << i), sub));
				}
			}
		}
	}

	cout << dp[n-1][(1<<n) - 1];
}

Measured memory_bytes: 7480
#include<stdio.h>
#include<string.h>

int main(void){
  int k; scanf("%d",&k);
  char s[101]; scanf("%s",&s);
  int len = strlen(s);

  if(len<=k){
    printf("%s",s);
  }
  else{
    for(int i = 0;i < k;i++){
      printf("%c",s[i]);
    }
    printf("...");
  }
  return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





string S;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    if (S.front() == '0' or S.back() == '1') {
        printf("-1\n");
        return;
    }

    rep(i, 0, (N - 1) / 2) if (S[i] != S[N - 2 - i]) {
        printf("-1\n");
        return;
    }

    vector<pair<int, int>> ans;
    int top = 0;
    rep(i, 0, N - 1) {
        ans.push_back({ top, i + 1 });

        if (S[i] == '1') top = i + 1;
    }

    fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1);
}


Measured memory_bytes: 2372
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
const int maxn = 200100;
const int mod = 1000000007;
struct tree{
    vector<int> data;
    tree(){
        data.resize(4 * maxn);
        fill(data.begin(), data.end(), maxn);
    }
    void update(int id, int l, int r, int pos, int v){
        if(l == r) data[id] = v;
        else{
            int mid = (l + r)>>1;
            if(pos <= mid) update(id + id, l, mid, pos, v);
            else update(id + id + 1, mid + 1, r, pos, v);
            data[id] = min(data[id + id], data[id + id + 1]);
        }
    }
    void update(int pos, int v){
        update(1, 0, maxn-1, pos, v);
    }
    int query(int id, int l, int r, int x, int y){
        if(l > y || r < x) return maxn;
        if(x <= l && r <= y) return data[id];
        int mid = (l + r)>>1;
        return min(query(id + id, l, mid, x, y), query(id + id + 1, mid + 1, r, x, y));
    }
    int query(int x, int y){
        return query(1, 0, maxn-1, x, y);
    }
};
tree pares, impares;
int arr[maxn];
int pos[maxn];
vector<int> sol;
int M(){
    int n;
    if(!~scanf("%d", &n)) return 0;
    for(int e = 0; e < n; e++)
        scanf("%d", arr + e);
    for(int e = 0; e < n; e++)
        pos[arr[e]] = e;
    pares = tree();
    impares = tree();
    for(int e = 0; e < n; e++)
        if(e & 1) impares.update(e, arr[e]);
        else pares.update(e, arr[e]);
    sol.clear();
    priority_queue<tuple<int, int, int > > pq;
    pq.push(make_tuple(- pares.query(0, n-1), 0, n-1));
    while(!pq.empty()){
        int best, second, l, r;
        tie(best, l, r) = pq.top(); pq.pop();
        // if(l >= r) continue;
        if(l % 2 == 0){
            best = pares.query(l, r);
            second = impares.query(pos[best] + 1, r);
        } else {
            best = impares.query(l, r);
            second = pares.query(pos[best] + 1, r);
        }
        sol.push_back(best);
        sol.push_back(second);
        if(l % 2 == 1 && l < pos[best])
            pq.push(make_tuple(- impares.query(l, pos[best]-1), l, pos[best]-1));
        else if(l % 2 == 0 && l < pos[best])
            pq.push(make_tuple(- pares.query(l, pos[best]-1), l, pos[best]-1));

        if(l % 2 == 1 && pos[best] + 1 < pos[second])
            pq.push(make_tuple( - pares.query(pos[best] + 1, pos[second] - 1), pos[best] + 1,
            pos[second]-1));
        else if(l % 2 == 0 && pos[best] + 1 < pos[second])
            pq.push(make_tuple( - impares.query(pos[best] + 1, pos[second] - 1), pos[best] + 1,
            pos[second]-1));

        if(l % 2 == 1 && pos[second] < r)
            pq.push(make_tuple( - impares.query(pos[second] + 1, r), pos[second] + 1, r));
        else if(l % 2 == 0 && pos[second] < r)
            pq.push(make_tuple( - pares.query(pos[second] + 1, r), pos[second] + 1, r));
    }
    for(int e = 0; e < n; e++)
        printf("%d%c", sol[e], " \n"[e == n-1]);
    return 1;
}
int main(){
    while(M());
    return 0;
}


Measured memory_bytes: 11664
def main():
    N, A, B = map(int, input().split())
    X = list(map(int, input().split()))
    dp = [float('inf')] * (N + 5)
    dp[0] = 0
    for i in range(1,N):
        dp[i] = dp[i-1] + min((X[i] - X[i-1]) * A, B)

    print(dp[N-1])

if __name__ == "__main__":
    main()

Measured memory_bytes: 86760
N = int(input())
S = input()
 
arr = [0] if S[0] == "." else []
b, w = 0, 0
for i in range(len(S)):
  if S[i] == ".":
    w += 1
  else:
    b += 1
  if S[i:i+2] == "#.":
    arr.append(b)
  if S[i:i+2] == ".#":
    arr.append(w)
if S[-1] == ".":
  arr.append(w)
#print(arr)
 
result = w
for i in range(0, len(arr), 2):
  result = min([arr[i]+w-arr[i+1], result])

print(result)

Measured memory_bytes: 11200
program XYZTriplets
    implicit none
    
    integer(4) :: n
    integer(4), allocatable :: cnt(:)

    integer(4) :: m, l
    integer(4) :: i, j, k
    read(*, *) n

    m = nint(sqrt(float(n-4)))
    allocate(cnt(1:n))

    cnt(1:n) = 0

    do i = 1, m+1
        do j = 1, m+1
            do k = 1, m+1
                l = i**2 + j**2 + k**2 + i*j + j*k + k*i
                if (l > n) then
                    exit
                end if
                cnt(l) = cnt(l) + 1
            end do
        end do
    end do

    do i = 1, n
        write(*, *) cnt(i)
    end do

    stop

end program XYZTriplets


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

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  long long n, a, b, c, d; cin >> n >> a >> b >> c >> d;
  for (auto&& i : {&a, &b, &c, &d}) *i *= 2;
  n--;
  long long e = (c + d) / 2, r = (d - c) / 2;
  for (long long i = -n; i <= n; i += 2) {
    long long l = a + i * e - n * r, u = a + i * e + n * r;
    if (l <= b and b <= u) {
      cout << "YES" << "\n";
      return 0;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append((b, itr))
  e[b].append((a, itr))
  
cidx = max([len(i) for i in e])

ans = [-1] * (n - 1)

q = deque()
q.append((0, 0, -1))
# 色は１から順に塗っていく
while q:
  v, p, pcol = q.popleft()
  col = 1
  for u, i in e[v]:
    if u != p:
      # 親と色がかぶる時は＋１
      if col == pcol:
        col += 1
      if ans[i] == -1: 
        ans[i] = col
      q.append((u, v, col))
      col += 1 

print(cidx)
for i in ans:
  print(i)

Measured memory_bytes: 53472
#include <stdio.h>

int main(){
 int N;
  scanf("%d",&N);
  
  int ans;
  ans = (N/1)%10;
  
  if(ans == 2|| ans == 4 || ans == 5 || ans == 7 || ans == 9){
    printf("hon");
  }else if(ans == 0 || ans == 1 || ans == 6 || ans == 8){
    printf("pon");
  }else{
    printf("bon");
  }
  
}

Measured memory_bytes: 1732
import java.util.Scanner;

/**
 * A - Red or Not
 * 整数 aと、英小文字からなる文字列 sが入力されます。
 * a が 3200以上なら s と出力し、a が 3200未満なら red と出力するプログラムを書いてください。
 */
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner( System.in );
        int a = sc.nextInt();
        String s = sc.next();

        if( a >= 3200 ) {
            System.out.println( s );
        } else {
            System.out.println( "red" );
        }
    }
}

Measured memory_bytes: 20820
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v(n+1), x(n+1);
    REP(i, n){
        cin >> v[i+1];
        x[i+1] = x[i] ^ v[i+1];
    }

    ll ans = 0;
    int l = 1, r = 1;

    while(l <= n){
        if((((x[r-1] ^ x[l-1]) & v[r]) == 0) && r <= n){
            r++;
        }else{
            ans += r - l;
            l++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Senky_Bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
ll an[500005];
ll id[500005];
ll vis[500005];
ll root(int a)
{
     if(a==id[a])
     return a;
     return id[a]=root(id[a]);
}
void union1(int a,int b)
{
    ll a1=root(a);
    ll b1=root(b);
    id[a1]=id[b1];
}
signed main()
{   
    Senky_Bansal
    IIIT_ALLAHABAD
     
    for(int i=1;i<500005;i++)
    id[i]=i;
    ll n,m;
    cin>>n>>m;
    map<ll,ll>mp;
    ll ans=0;
    while(m--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        mp[a]++;
        mp[b]++;
        union1(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[root(i)]==0){
        ans++;
        vis[root(i)]=1;}
    }
    cout<<ans<<endl;
}
    
    
    







Measured memory_bytes: 13184
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,w,h;
struct pt{
	int sx,sy;
	int ex,ey;
};
pt cun[1001];
int ans;
char mp[4999][4999];
void lshx()
{
	int gsw=0;
	int lsc[4005];
	for(int i=1;i<=n;i++)
	{
		for(int j=-1;j<1;j++)
		{
			int xi1=cun[i].sx+j;
			int xi2=cun[i].ex-j;
			if(xi1>=0&&xi1<=w)
			{
				gsw++;
				lsc[gsw]=xi1;
			}
			if(xi2>=0&&xi2<=w)
			{
				gsw++;
				lsc[gsw]=xi2;
			}
		}
	}
	sort(lsc+1,lsc+1+gsw);
	w=unique(lsc+1,lsc+1+gsw)-lsc-1;
	for(int i=1;i<=n;i++)
	{
		cun[i].sx=lower_bound(lsc+1,lsc+1+w,cun[i].sx)-lsc;
		cun[i].ex=lower_bound(lsc+1,lsc+1+w,cun[i].ex)-lsc;
	}
}
void lshy()
{
	int gsw=0;
	int lsc[4005];
	for(int i=1;i<=n;i++)
	{
		for(int j=-1;j<1;j++)
		{
			int xi1=cun[i].sy+j;
			int xi2=cun[i].ey-j;
			if(xi1>=0&&xi1<=h)
			{
				gsw++;
				lsc[gsw]=xi1;
			}
			if(xi2>=0&&xi2<=h)
			{
				gsw++;
				lsc[gsw]=xi2;
			}
		}
	}
	sort(lsc+1,lsc+1+gsw);
	h=unique(lsc+1,lsc+1+gsw)-lsc-1;
	for(int i=1;i<=n;i++)
	{
		cun[i].sy=lower_bound(lsc+1,lsc+1+h,cun[i].sy)-lsc;
		cun[i].ey=lower_bound(lsc+1,lsc+1+h,cun[i].ey)-lsc;
	}
}
struct pt2{
	int x,y;
};
char dx[5]={0,1,-1,0,0};
char dy[5]={0,0,0,1,-1};
void bfs(int si,int sj)
{
	pt2 dl[17001];
	int mod=(1<<14)-1;
	int front=1;
	int back=1;
	dl[back&mod]=(pt2){si,sj};
	back++;
	mp[si][sj]=1;
	while(front<back)
	{
		pt2 ls=dl[front&mod];
		front++;
		for(int i=1;i<5;i++)
		{
			int lsx=dx[i]+ls.x;
			int lsy=dy[i]+ls.y;
			if(lsx>0&&lsx<=w&&lsy>0&&lsy<=h)
			{
				if(mp[lsx][lsy]==0)
				{
					mp[lsx][lsy]=1;
					dl[back&mod]=(pt2){lsx,lsy};
					back++;
				}
			}
		}
	}
}
int main()
{
	while(1)
	{
		scanf("%d%d",&w,&h);
		if(w==0&&h==0)
		{
			break;
		}
		scanf("%d",&n);
		memset(cun,0,sizeof(cun));
		memset(mp,0,sizeof(mp));
		ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&cun[i].sx,&cun[i].sy,&cun[i].ex,&cun[i].ey);
		}
		for(int i=1;i<=n;i++)
		{
			cun[i].sx<<=1;
			cun[i].ex<<=1;
			cun[i].sy<<=1;
			cun[i].ey<<=1;
		}
		w<<=1;
		h<<=1;
		lshx();
		lshy();
		for(int i=1;i<=n;i++)
		{
			pt ls=cun[i];
			for(int ii=ls.sx;ii<=ls.ex;ii++)
			{
				for(int j=ls.sy;j<=ls.ey;j++)
				{
					mp[ii][j]=1;
				}
			}
		}
		for(int i=1;i<=w;i++)
		{
			for(int j=1;j<=h;j++)
			{
				if(mp[i][j]==0)
				{
					ans++;
					bfs(i,j);
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}










Measured memory_bytes: 27240
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.OptionalInt;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[][] a = in.nextIntArrayArray(n, 3);

            int[][] dp = new int[n][3];
            dp[0] = Arrays.copyOf(a[0], a[0].length);
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {
                        if (j == k) continue;

                        dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][j] + a[i + 1][k]);
                    }
                }
            }

            out.println(IntStream.of(dp[n - 1]).max().getAsInt());
        }

    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
            st = new StringTokenizer("");
        }

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

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

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

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

    }
}



Measured memory_bytes: 47292
package main

import (
	"fmt"
	"strings"
)

func main(){
	var n, b, f, r, v int
	fmt.Scan(&n)
	board := make([][][]int, 4)
	for i:=0; i<4; i++{
		board[i] = make([][]int, 3)
		for j:=0; j<3; j++{
			board[i][j] = make([]int, 10)
		}
	}

	for i:=0; i<n; i++{
		fmt.Scan(&b, &f, &r, &v)
		board[b-1][f-1][r-1] += v
	}

	for i:=0; i<4; i++{
		for _, j := range board[i]{
			for _, k:= range j{
				fmt.Printf(" %d", k)
			}
			fmt.Printf("\n")
		}
		if i != 3{
			fmt.Println(strings.Repeat("#", 20))
		}
	}
}


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

int main() {
    int h, w, n;
    while (cin >> h >> w >> n, h) {
        vector<vector<int>> a(h, vector<int>(w));
        for (auto &ai: a) for (int &aij: ai) cin >> aij;
        vector<vector<int>> dp(h + 1, vector<int>(w + 1));
        dp[0][0] = n - 1;
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
            dp[i + 1][j] += (dp[i][j] + !a[i][j]) / 2;
            dp[i][j + 1] += (dp[i][j] +  a[i][j]) / 2;
            a[i][j] ^= dp[i][j] & 1;
        }
        int i = 0, j = 0;
        while (i < h && j < w) {
            (a[i][j] ? j : i)++;
        }
        cout << i + 1 << " " << j + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 10760
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define repitr(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	map<int, int> a, b;
	pair<int, int> mxa1, mxa2, mxb1, mxb2;
	mxa1.second = mxa2.second = mxb1.second = mxb2.second = 0;
	rep(i, n/2){
		int ai, bi;
		cin >> ai >> bi;
		a[ai]++;
		b[bi]++;
	}
	for(auto p : a){
		if(p.second > mxa1.second){
			mxa2 = mxa1;
			mxa1 = p;
		}else if(p.second > mxa2.second){
			mxa2 = p;
		}
	}
	for(auto p : b){
		if(p.second > mxb1.second){
			mxb2 = mxb1;
			mxb1 = p;
		}else if(p.second > mxb2.second){
			mxb2 = p;
		}
	}
	int ans = 0;
	int cha1, cha2, chb1, chb2;
	cha1 = n/2 - mxa1.second;
	cha2 = n/2 - mxa2.second;
	chb1 = n/2 - mxb1.second;
	chb2 = n/2 - mxb2.second;
	if(mxa1.first != mxb1.first){
		ans += cha1;
		ans += chb1;
	}else{
		int t1, t2;
		t1 = cha1 + chb2;
		t2 = cha2 + chb1;
		ans = min(t1, t2);
		/*
		if(mxa1.second > mxb1.second){
			ans += cha1;
			ans += chb2;
		}else{
			ans += cha2;
			ans += chb1;
		}
		*/
	}
	cout << ans << endl;
	

	return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
  ll K;
  ll a = 7;
  cin >> K;
  ll i;
  for(i=1;i<=K;i++){
    if(a % K == 0){cout << i << endl; break;}
    if(i==K) {cout << -1 << endl; break;}
    a = (a * 10 + 7) % K;
    }
}

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

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

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

  for ( int i = n-1; i >= 0; i--){
    cout << a[i];
    if ( i != 0 )  cout << " ";
  }

  cout << endl;

  return 0;
}


Measured memory_bytes: 3080
#include <stdio.h>
#define MAX 200000

using namespace std;
int temp[MAX];

long long merge(int A[], int lo, int mid, int hi) {
    for(int i = lo; i <= hi; i++) temp[i] = A[i];
    long long cnt = 0;
    int i = lo, j = mid + 1;
    for(int k = lo; k <= hi; k++) {
        if(i > mid) A[k] = temp[j++];
        else if(j > hi) A[k] = temp[i++];
        else if(temp[i] <= temp[j]) A[k] = temp[i++];
        else {
            A[k] = temp[j++];
            cnt = cnt + mid+1 - i;
        }
    }
    return cnt;
}

long long mergeSort(int A[], int lo, int hi) {
    if(lo >= hi) return 0;
    long long v1, v2, v3;
    int mid = (lo + hi) / 2;
    v1 = mergeSort(A, lo, mid);
    v2 = mergeSort(A, mid+1, hi);
    v3 = merge(A, lo, mid, hi);
    return v1 + v2 + v3;
}


int main()
{
    int n, A[MAX];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    long long res = mergeSort(A, 0, n-1);
    printf("%lld\n", res);

    return 0;
}

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

int main() {
	vector<char>data(3);
  for(int i=0;i<3;i++){
      cin >> data.at(i);
  }
  int aflag=0,bflag=0,cflag=0;
  for(int i=0;i<3;i++){
      if(data.at(i)=='a')aflag++;
      else if(data.at(i)=='b')bflag++;
      else if(data.at(i)=='c')cflag++;
  }
  if(aflag == 1 && bflag == 1 &&cflag == 1)cout << "Yes"<<endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
# 初期入力
N,M = (int(x) for x in input().split(" "))
S = []

#　問題種類をキー、ac,waを値の辞書
mondai_acwa ={i:list() for i in range(1,N+1) }
q_id =0
result =""
for i in range(M):
    q_id_str,result = (x for x in input().split())
    mondai_acwa[int(q_id_str)].append(result)

# ACが初めてでた時のindex＝その問題のWAの数（各問題）
ac_sum=0
wa_sum=0

for i,v_wa in mondai_acwa.items():
    if 0 < len(v_wa):
        if "AC" in v_wa: #ACがないときはWAも数えない
            ac_i =v_wa.index("AC") 
            ac_sum +=1
            wa_sum += ac_i
print(ac_sum,wa_sum)

Measured memory_bytes: 28820
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define FOR(i, first, last) for (int i = (first); i < (last); ++i)
#define REP(i, n) FOR(i, 0, n)
#define CLR(a) memset((a), 0, sizeof(a))
#define DUMP(x) std::cerr << #x << " = " << (x) << std::endl;

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

typedef unsigned long long ull;
typedef unsigned long ul;

int main() { 
  int N, K;
  cin>>N>>K;

  // DUMP(N);
  // DUMP(K);

  vector<int> xs;
  while (N--) {
    int x;
    cin>>x;
    xs.push_back(x);
  }

  int ans=0;
  for(const auto& x : xs){
    int dist = 2*min(abs(x), abs(K - x));
    ans += dist;
    // DUMP(x);
    // DUMP(dist);
  }
  cout << ans <<endl;
  
  return 0; 
}


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

int main() {
  int N,M;
  int ac=0,wa=0;
  int p;
  string S;
  cin >> N >> M;
  bool Nflag[N+1];
  int Nwa[N+1];
  for(int i=0;i<=N;i++){
    Nflag[i] = false;
    Nwa[i] = 0;
  }

  for(int i=0;i<M;i++){
    cin >> p >> S;
    if(!Nflag[p]){
      if(S=="WA") Nwa[p]++;
      else {
	ac++;
	Nflag[p]=true;
      }
    }
  }
  for(int i=1;i<=N;i++){
    if(Nflag[i]) wa += Nwa[i];
  }
  cout << ac << " " << wa << endl;
  return 0;
}


Measured memory_bytes: 768
var
	a:array[0..100010] of int64;
	i,j,n,v,w,c,max:longint;
begin
	readln(n,v);
	fillchar(a,sizeof(a),0);
	for i:=1 to n do
	begin
		read(c,w);
		for j:=v downto c do
			if w+a[j-c]>a[j] then a[j]:=w+a[j-c];
	end;
	writeln(a[v]);
end.


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL INF=1e12;

int main(){
	int N, D, A;
	cin >> N >> D >> A;
	vector<P> xh(N);
	rep(i,N){
		LL x, h;
		cin >> x >> h;
		xh[i]=P(x,(h+A-1)/A);
	}
	sort(xh.begin(),xh.end());
	vector<int> reach(N+1), damage(N+1);
	rep(i,N){
		P p=make_pair(xh[i].first+2*D,INF);
		int r=upper_bound(xh.begin(),xh.end(),p)-xh.begin();
		reach[i]=r;
	}
	LL ans=0;
	rep(i,N){
		if(i!=0) damage[i]+=damage[i-1];
		if(xh[i].second<=damage[i]) continue;
		LL num=xh[i].second-damage[i];
		ans+=num;
		damage[i]+=num, damage[reach[i]]-=num;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>

int main() {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	
	int total = 0;
	for(int i = 0; i <= a; i++) {
		int syarat = 0, counter = i;
		while(counter > 0) {
			syarat += counter % 10;
			counter /= 10;
		}
		if(syarat >= b && syarat <= c){
			total += i;
		}
	}
	printf("%d\n", total);
	
	return 0;
}

Measured memory_bytes: 1732
//written by newbiechd
#include <cstdio>
#include <cctype>
#include <algorithm>
#define R register
#define I inline
#define B 1000000
using namespace std;
const int N = 200003, M = 400003, inf = 1050000000;
char buf[B], *p1, *p2;
I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }
I int rd() {
    R int f = 0;
    R char c = gc();
    while (c < 48 || c > 57)
        c = gc();
    while (c > 47 && c < 58)
        f = f * 10 + (c ^ 48), c = gc();
    return f;
}
int d[N], f[N];
struct edge {
    int x, y, w;
    edge() {}
    edge(int x, int y, int w) : x(x), y(y), w(w) {}
    I int operator < (edge e) { return w < e.w; }
}e[M];
I int min(int x, int y) { return x < y ? x : y; }
I int find(int x) {
    R int r = x, y;
    while (f[r] ^ r)
        r = f[r];
    while (x ^ r)
        y = f[x], f[x] = r, x = y;
    return r;
}
int main() {
    R int n = rd(), Q = rd(), E = 0, a, b, c, i;
    long long ans = 0;
    for (i = 0; i < n; ++i)
        d[i] = inf, f[i] = i;
    for (i = 1; i <= Q; ++i)
        a = rd(), b = rd(), c = rd(), e[++E] = edge(a, b, c),
            d[a] = min(d[a], c + 1), d[b] = min(d[b], c + 2);
    d[0] = min(d[0], d[n - 1] + 2);
    for (i = 1; i < n; ++i)
        d[i] = min(d[i], d[i - 1] + 2);
    d[0] = min(d[0], d[n - 1] + 2);
    for (i = 1; i < n; ++i)
        d[i] = min(d[i], d[i - 1] + 2);
    e[++E] = edge(n - 1, 0, d[n - 1]);
    for (i = 1; i < n; ++i)
        e[++E] = edge(i - 1, i, d[i - 1]);
    sort(e + 1, e + E + 1);
    for (i = 1; i <= E; ++i) {
        a = find(e[i].x), b = find(e[i].y);
        if (a ^ b)
            f[a] = b, ans += e[i].w;
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 7424
#include <stdio.h>
#include <math.h>

int main(void){
  double a, b;
  double h, m;
  double th_a, th_b;
  double deg;
  
  scanf("%lf %lf %lf %lf",&a, &b, &h, &m);
  
  th_a = 2.0 * M_PI * (h / 12.0);
  th_a = th_a + ((M_PI * m) / 360.0);
  th_b = 2.0 * M_PI * (m / 60.0);
  
  if(th_a > th_b){
 	 deg = a * a + b * b - 2.0 * a * b * cos(th_a - th_b);
  }else{
    deg =  a * a + b * b - 2.0 * a * b * cos(th_b - th_a);
  }
  
  printf("%.20f\n",sqrt(deg));
  return 0;
}

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

using namespace std;

const int MOD = 1e9 + 7;


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

    long long csum = 0, x;
    cin >> x;

    for(int i = 1; i <= x; ++i) {
        if (i * (i + 1) / 2 >= x) {
            cout << i;
            return 0;
        }
    }
    return 0;
}


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

#define int long long
#define P pair<int, int>

signed main() {
    int N, K;

    cin >> N >> K;

    vector<P> lis;

    for(int i = 0; i < N; ++i){
        int a, b;
        cin >> a >> b;
        lis.push_back(make_pair(a, b));
    }

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

    int pos = 0;
    while(K > 0){
        if(lis[pos].second < K){
            K -= lis[pos].second;
            pos++;
        } else {
            cout << lis[pos].first << endl;
            return 0;
        }
    }
}


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

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PI;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a < b && b < c)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>
int main(void){
  long long int a[5];
  long long int n;
  long long int k = 0;
  long long int i,tmp,j;
  scanf("%lld",&n);
  scanf("%lld",&a[0]);
  scanf("%lld",&a[1]);
  scanf("%lld",&a[2]);
  scanf("%lld",&a[3]);
  scanf("%lld",&a[4]);
    
  for (i = 1; i < 5; i++) {
    tmp = a[i];
    if (a[i - 1] > tmp) {
        j = i;
        do {
            a[j] = a[j - 1];
            j--;
        } while (j > 0 && a[j - 1] > tmp);
        a[j] = tmp;
    }
  }
  n--;
  k=n/a[0];
  k=k+5;
  printf("%lld",k);
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

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

		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int numbers[] =new int[n];
		for (int i=0 ; i < n; i++) {
			numbers[i] =sc.nextInt();
		}
		sc.close();

		int ans = 0;
		boolean flag=true;

		while (flag){
			for(int i=0 ; i<n ;i++){
				if(numbers[i]%2==1){
					flag = false;
					break;
				} else {
					numbers[i] = numbers[i]/2;
				}
			}
			if (flag) {
				ans++;
			}
		}
		System.out.println(ans);


	}
}


Measured memory_bytes: 21972
object Main extends App {
	val temp = scala.io.StdIn.readLine.split(" ").map(_.toLong)

	val N = temp(0)
	val A = temp(1)
	val B = temp(2)
	val C = temp(3)
	val D = temp(4)

	val sum = B - A

	var resalt = "NO"

	for(i<- 0L until N){
		val under = i * C - (N - 1 - i) * D
		val top = i * D - (N - 1 - i) * C

//		println(s" ${under} < ${sum} < ${top}")

		if(under <= sum && sum <= top){
			resalt = "YES"
		}
	}

	println(resalt)

}

Measured memory_bytes: 34840
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll a,k,o=0;
vec<vec<ll>> l;
vec<ll> dp;

ll dfs(int v){
    if(dp[v]!=-1) return dp[v];
    dp[v] = 0;
    for(int h : l[v]){
        dp[v] = max(dp[v], dfs(h)+1);
    }
    o = max(o, dp[v]);
    return dp[v];
}

int main() {
    fast;
    cin>>a>>k;
    dp = vec<ll>(a, -1);
    l = vec<vec<ll>>(a, vec<ll>());
    for(int q=0; q<k; q++){
        ll x,y; cin>>x>>y; x--, y--;
        l[x].pb(y);
    }
    for(int q=0; q<a; q++){
        if(dp[q]==-1) dfs(q);
    }
    cout<<o;
}

Measured memory_bytes: 8064
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n=I()
def niwari(x):
    count=0
    while x%2==0:
        x//=2
        count+=1
    return count
mx=0
ans=1
for i in range(1,n+1):
    if niwari(i)>mx:
        mx=niwari(i)
        ans=i
print(ans)

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

typedef long long ll;

ll div2 ( ll x ){
    ll count = 0;
    while ( x % 2 == 0 ){
        x = x / 2;
        ++ count;
    }
    return count;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    for ( ll i = 0; i < N; ++i){
        cin >> a[i];
    }
    
    ll all = 0;
    for ( ll i = 0; i < N; ++i){
        all += div2(a[i]);
    }
    
    cout << all << endl;
    
    return 0;
}


Measured memory_bytes: 3740
A, B, K = map(int, input().split())

ans1 = [i for i in range(A, A + K) if A <= i and i <= B]
ans2 = [i for i in range(B, B - K, -1) if A <= i and i <= B]

ans = ans1 + ans2
ans = list(set(ans))
ans.sort()
for ans in ans:
    print(ans)

Measured memory_bytes: 9180
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

int K, N, A[200000];
signed main(){
	cin >> K >> N;
	rep(i, N) cin >> A[i];

	int ans = 0;
	rep(i, N){
		ans = max(ans, (A[i]-A[(i-1+N)%N]+K)%K);
		ans = max(ans, (A[(i+1+N)%N]-A[i]+K)%K);
	}
	cout << K-ans << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

ll mod = 1e9+7;

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

  int n;
  cin >> n;
  vvi tree(n,vi());
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    a--;b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }

  vi color(n);
  color[0] = 1;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int cur = que.front();
    que.pop();
    rep(i,tree[cur].size()){
      if(color[tree[cur][i]] != 0)continue;
      color[tree[cur][i]] = -color[cur];
      que.push(tree[cur][i]);
    }
  }
  int c1 = 0,c2 = 0;
  rep(i,n){
    if(color[i] == 1)c1++;
    if(color[i] == -1)c2++;
  }
  int m0 = 3,m1 = 1,m2 = 2;
  vi ret(n);
  if(c1 <= n/3){
    rep(i,n){
      if(color[i] == 1){
        ret[i] = m0;
        m0 += 3;
      }
      if(color[i] == -1){
        if(m1 <= n){
          ret[i] = m1;m1 += 3;
        }else if(m2 <= n){
          ret[i] = m2;m2 += 3;
        }else{
          ret[i] = m0;m0 += 3;
        }
      }
    }
  }else if(c2 <= n/3){
    rep(i,n){
      if(color[i] == -1){
        ret[i] = m0;
        m0 += 3;
      }
      if(color[i] == 1){
        if(m1 <= n){
          ret[i] = m1;m1 += 3;
        }else if(m2 <= n){
          ret[i] = m2;m2 += 3;
        }else{
          ret[i] = m0;m0 += 3;
        }
      }
    }
  }else {
    rep(i,n){
      if(color[i] == 1){
        if(m1 <= n){
          ret[i] = m1;
          m1 += 3;
        }else{
          ret[i] = m0;
          m0 += 3;
        }
      }else{
        if(m2 <= n){
          ret[i] = m2;
          m2 += 3;
        }else{
          ret[i] = m0;
          m0 += 3;
        }
      }
    }
  }
  rep(i,n){
    cout << ret[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 15344
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, D, X;
    cin >> N >> D >> X;
    int ans = X;
    for(int i = 0; i < N; i++) {
        int A;
        cin >> A;
        ans += (D-1)/A + 1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n=int(input())
xy=[]

for i in range(n):
    xy.append(list(map(int,input().split())))

import itertools

l=list(itertools.permutations(range(0,n)))
cnt=0
sum=0

while True:
    if len(l)==0:
        break
    temp=l.pop(0)
    for i in range(n-1):
        sum+=((xy[temp[i]][0]-xy[temp[i+1]][0])**2+(xy[temp[i]][1]-xy[temp[i+1]][1])**2)**(1/2)
    cnt+=1

print(sum/cnt)

Measured memory_bytes: 13908
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  string a, b;
  cin >> a >> b;
  int n = a.size();
  int m = b.size();
  if(n > m){
    cout << "GREATER" << endl;
  }else if(n < m){
    cout << "LESS" << endl;
  }else{
    REP(i, n){
      if(a[i] == b[i]) continue;
      if(a[i] > b[i])cout << "GREATER" << endl;
      if(a[i] < b[i])cout << "LESS" << endl;
      return 0;
    }
    cout << "EQUAL" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[200005],n,ans,j,h;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
	{
		for(;j<n;j++)
			if((h|a[j])!=(h+a[j]))
				break;
			else
				h+=a[j],ans=ans+j-i+1;
		h-=a[i];
	}
	cout<<ans;
	return 0;
}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int a;
    string s;
    cin >> a >> s;
    if (a >= 3200) cout << s << endl;
    else cout << "red" << endl;
    return 0;
}


Measured memory_bytes: 256