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

#define ll long long
#define endl "\n"
#define int ll

signed main ()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector <int> prices(n);
	for (auto &i : prices) cin >> i;

	int ans = 1000;
	int current = 0;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			if (prices[i + 1] >= prices[i]) {
				current += (ans / prices[i]);
				ans %= prices[i];
			}
		}

		else if (i == n - 1) {
			ans += prices[i] * current;
			current = 0;
		}

		else {
			if (prices[i] >= prices[i + 1] and prices[i] >= prices[i - 1]) {
				ans += current * prices[i];
				current = 0;
			}

			else if (prices[i] <= prices[i - 1] and prices[i] <= prices[i + 1]) {
				current += (ans / prices[i]);
				ans %= prices[i];
			}
		}
	}

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 3664
#include <stdio.h>

#define MAX_N 100

int main() {

    int i, x, y, z, e, n, ans = 0;
    int A[MAX_N], B[MAX_N], C[MAX_N];

    scanf("%d", &n);
    for ( i=0; i<n; ++i ) A[i] = B[i] = C[i] = 0;

    scanf("%d", &x);
    for ( i=0; i<x; ++i ) {
	scanf("%d", &e);
	A[e-1] = 1;
    }

    scanf("%d", &y);
    for ( i=0; i<y; ++i ) {
	scanf("%d", &e);
	B[e-1] = 1;
    }

    scanf("%d", &z);
    for ( i=0; i<z; ++i ) {
	scanf("%d", &e);
	C[e-1] = 1;
    }

    for ( i=0; i<n; ++i ) {
	if ( (!A[i] && C[i]) || (B[i] && C[i]) ) ++ans;
    }
    printf("%d\n", ans);

    return 0;
}



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

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'

int main(){
	int n, k;
	cin >> n >> k;
	int g = 0, mx = 0;
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		g = __gcd(g, x);
		mx = max(mx, x);
	}
	if(mx >= k && k % g == 0)
		cout << "POSSIBLE" << endl;
	else
		cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,j,n,k,x,y,ans=0;
	cin>>n>>k;
	int a[n+1];
	memset(a,0,sizeof(a));
	for(i=1;i<=k;i++)
	{
		cin>>x;
		for(j=1;j<=x;j++)
		{
			cin>>y;
			a[y]++;
		}
	}
	for(i=1;i<=n;i++)
		if(a[i]==0)
			ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};


int main(){
    string S; cin >> S;
    int n=-1,cnt=0;
    for(int i=0;i<S.length();i++){
        //cerr << "\n";
        if(S[i]=='A' || S[i]=='C' || S[i]=='G' || S[i]=='T'){
            int tmp=1;
            //cerr << S[i] << " ";
            for(int j=i+1;j<S.length();j++){
                //cerr << S[j] << " ";
                if(S[j]=='A' || S[j]=='C' || S[j]=='G' || S[j]=='T'){
                    tmp++;
                }else{
                    break;
                }

            }
            if(tmp>cnt){
                cnt=tmp;
                n=i;
            }
        }
    }
    cout << cnt << endl;    
    return 0;
}


Measured memory_bytes: 256
#include <string.h>
#include <algorithm>

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>

static void C_ColoringColorfully();

int main()
{

	C_ColoringColorfully();

	fflush(stdout);
	return 0;
}


static void C_ColoringColorfully()
{
	static char szS[100000] = { 0 };

	scanf(" %s", szS);
	int N = strlen(szS); 
	
	int wStart = 0;
	int bStart = 0;
	for (int i = 0; i < N; i++) {
		// 白はじまり
		if (i % 2) {
			if (szS[i] != '1') {
				wStart++;
			}
			else {
				bStart++;
			}
		}
		else {
			if (szS[i] != '0') {
				wStart++;
			}
			else {
				bStart++;
			}
		}
	}

	printf("%d\n", (wStart < bStart) ? wStart : bStart);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
#define all(a) a.begin(), a.end()

const int MOD = 1e9+7;
const int INF = 1e9;

int main(){
    int D, G;
    cin >> D >> G;
    vector<pii> points;
    rep(i, 0, D){
        int p, c;
        cin >> p >> c;
        points.push_back(make_pair(p, c));
    }
    int ans = INF;
    rep(i, 0, 1<<D){
        ll score = 0;
        int cnt = 0;
        int last, prob;
        rep(j, 0, D){
            if ((i>>j)&1){
                score += points[j].first * (j+1) * 100 + points[j].second;
                cnt += points[j].first;
            }
            else{
                last = j;
                prob = points[j].first;
            }
        }
        while (score < G && prob > 1){
            score += (last+1) * 100;
            cnt++;
            prob--;
        }
        if (score >= G){
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
}

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


int main() {
	int n;
	int room[5][4][11] = { 0 };
	cin >> n;
	for (int i = 0; i < n; i++) {
		int b, f, r, v;
		cin >> b >> f >> r >> v;
		room[b][f][r] += v;
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 3; j++) {
			for (int k = 1; k <= 10; k++) {
				cout << ' ' << room[i][j][k];
			}
			cout << endl;
		}if (i != 4) {
			cout << "####################" << endl;
		}
	}
	return 0;
}

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

int main(){
	int n, q, query, x, t;
	
	cin>>n>>q;
	
	priority_queue<int> hoge[n];
	
	for(int i = 0; i < q; i++){
		cin>>query>>t;
		
		if(query == 0){
			cin>>x;
			hoge[t].push(x);
		} else if(query == 1){
			if(!hoge[t].empty())cout<<hoge[t].top()<<endl;
		} else {
			if(!hoge[t].empty())hoge[t].pop();
		}
	}
	
	return 0;
}


Measured memory_bytes: 4100
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

signed main(){
  lint N, X, Y; cin >> N >> X >> Y;
  vector<vector<lint> > G(N);
  G[0].push_back(1);
  for(lint i = 1; i < N - 1; i++){
    G[i].push_back(i - 1); G[i].push_back(i + 1);
  }
  G[N - 1].push_back(N - 2);
  G[X - 1].push_back(Y - 1); G[Y - 1].push_back(X - 1);
  vector<lint> num(N, 0);
  for(lint i = 0; i < N; i++){
    vector<lint> visit(N, -1);
    queue<lint> que;
    visit[i] = 0;
    que.push(i);
    while(!que.empty()){
      lint v = que.front(); que.pop();
      for(lint nv : G[v]){
        if(visit[nv] != -1) continue;
        visit[nv] = visit[v] + 1;
        que.push(nv);
      }
    }
    for(lint j = i + 1; j < N; j++){
      num[abs(visit[i] - visit[j])]++;
    }
  }
  for(lint i = 1; i < N; i++) cout << num[i] << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <string.h>
typedef long long ll;
using namespace std;
int main(void){
    ll x;
    cin>>x;
    if(x%11==0)cout<<x/11*2;
    else if(x%11<=6)cout<<x/11*2+1;
    else cout<<x/11*2+2;
}

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

#define debug(x) cout << x << "\n";
#define debug2(x,y) cout << x << " " << y << "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long 
const ll mod = 1e9+7;
const int MAX = 2e5+5;

int main() {
    int n; cin >> n;
    if(n % 2 == 1){
        cout << 0 << "\n";
        return 0;
    }
    vector<int> arr(n,0);
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr.begin(), arr.end());
    int mid = n / 2;
    int ans =  abs(arr[mid-1] - arr[mid]);
    cout << ans << "\n";
}






Measured memory_bytes: 3704
n,a,b = map(int,input().split())
s = 0
H = []
for _ in range(n):
    h = int(input())
    H.append(h)
from copy import deepcopy

from math import ceil
def count(x):
    Hc = deepcopy(H)
    cnt = 0
    for i in range(n):
        Hc[i] -= b*x
        if Hc[i]>0:
            cnt += ceil(Hc[i]/(a-b))
    return cnt <= x

l,r = 0, max(H)//b + 1
while l < r:
    mid = (l+r)//2
    if count(mid):
        r = mid
    else:
        l = mid+1
print(r)

Measured memory_bytes: 122940
# coding: utf-8
N=int(input())
XL=[]

for i in range(N):
    XL.append(list(map(int,input().split())))
    
XL.sort()
ans=N
r=XL[0][0]+XL[0][1]

for i in range(1,N):
    l=XL[i][0]-XL[i][1]
    if r > l:
        ans-=1
        if r > XL[i][0]+XL[i][1]:
            r=XL[i][0]+XL[i][1]
    else:
        r=XL[i][0]+XL[i][1]

print(ans)


Measured memory_bytes: 27872
#include<stdio.h>
int main(void)
{
  int k=2,i,N,a[100];

  scanf("%d",&N);

  while(k <= N){
    k=k*2;
  }


  if(k == 1){
    k=0;
  } else {
    k=k/2;
  }
  printf("%d\n",k);

    
  return 0;
}


Measured memory_bytes: 128
import math
N = int(input())
rootN  = math.floor(math.sqrt(N))
priFacInd = {}
count = 0
for i in range(2, rootN+1):
  if N % i ==0:
    priFacInd[i] = 0
  while N % i ==0:
    N /= i
    priFacInd[i] += 1
if not N == 1:
  priFacInd[N] = 1
for priFac in priFacInd:
  for i in range(1, rootN+1):
    priFacInd[priFac] -= i
    count += 1
    if priFacInd[priFac] < i+1:
      break
print(count)

Measured memory_bytes: 9212
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
template<class T> inline void chmax(T &a,T b){if(a<b)a=b;}
template<class T> inline void chmin(T &a,T b){if(a>b)a=b;}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,A;cin>>N>>A;
    N %= 500;
    cout << (N<=A ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
import statistics
N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
ma=statistics.median(A)
mb=statistics.median(B)
if N%2==0:
    print(int((mb-ma)*2+1))
else:
    print(int((mb-ma)+1))

Measured memory_bytes: 28852
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 1000000007;
signed main(){
    int m,d;
    cin>>m>>d;
    int cnt=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<d;j++){
            int m=i+1;
            int d=j+1;
            if(d%10>=2&&d/10>=2&&(d%10)*(d/10)==m)cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}



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

int main(){
for(;;){
int k,al,a[10000];
al=0;
cin>>k;
if(k==0){break;}
for(int i=0;2*i<k*(k-1);i++){
cin>>a[i];
al+=a[i];
}
cout<<al/(k-1)<<endl;
}


return 0;
}


Measured memory_bytes: 3020
N = int(input())
c = input()

left = 0
right = len(c)-1

count=0
if (right+1)%2==0:
    while (left-1)!=right:
        if c[left]=='R':
            left+=1 
        elif c[right]=='W':
            right-=1
        elif c[left]=='W' and c[right]=='R':
            left+=1
            right-=1
            count+=1
else :
    while left!=right:
        if c[left]=='R':
            left+=1 
        elif c[right]=='W':
            right-=1
        elif c[left]=='W' and c[right]=='R':
            left+=1
            right-=1
            count+=1


print(count)


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


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if (r > n) or (n < 0) or (r < 0):
        return 0

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    large_x, large_y = map(int, input().split())
    x = -large_x + 2 * large_y
    y = 2 * large_x - large_y

    if x % 3 != 0 or y % 3 != 0:
        print(0)
        exit()

    xy = (x + y) // 3
    y = y // 3
    print(count_combination(xy, y))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
def A():
    temp = [int(i) for i in input().split()]
    print(max(0, temp[0]-2*temp[1]))

def B():
    N = int(input())
    T = [int(i) for i in input().split()]
    s = 0
    for i in range(N):
        for j in range(i):
            s += T[i]*T[j]
    print(s)

def C():
    N = int(input())
    S = input()
    if N == 1:
        print(1)
    else:
        ans = 1
        cur_c = S[0]
        for c in S:
            if c != cur_c:
                ans += 1
                cur_c = c
        
        print(ans)

C()

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 1;

ll ans = 1;
int N;
string str;

int main(){
	cin>>N>>str;
	ll now = 0;
	for(int i=0; i<N*2; i++){
		if(str[i]=='B'){
			if(now%2){
				ans = (ans * now) % MOD;
				now--;
			}else{
				now++;
			}
		}else{
			if(now%2){
				now++;
			}else{
				ans = (ans * now) % MOD;
				now--;
			}
		}
	}
	if(now!=0){
		printf("0");
		return 0;
	}
	for(int i=1; i<=N; i++){
		ans = ((ll)i * ans) % MOD;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
using namespace std;
int a[100];
int main()
{
	int i,j,k,n,m=1;
	ll x,y;
	scanf("%d%lld",&n,&x);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&y);
		j=0;
		while(y>0)
		{
			a[j]+=y&1;
			y=y>>1;
			j++;
		}
		m=max(m,j);
	}
	j=0;
	ll x1=x;
	while(x>0)
	{
		x=x>>1;
		j++;
	}
	m=max(m,j);
	x=x1;
	bool bo=0;
	for(i=m-1;i>=0;i--)
	{
		if(bo)
		{
			if(a[i]<n-a[i])
			{
				a[i]=n-a[i];
			}
		}
		else
		{
			if(a[i]<n-a[i])
			{
				if((x>>i)&1)
				{
					a[i]=n-a[i];
				}
			}
			else
			{
				if((x>>i)&1)
				{
					bo=1;
				}
			}
		}
	}
	ll ans=0;
	for(i=m-1;i>=0;i--)
	{
		ans+=1ll*a[i]*(1ll<<i);
	}
	printf("%lld",ans);
	return 0;
}


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

using namespace std;

#define ll long long
#define ld long double
#define int ll
#define ff first
#define ss second
#define rsz resize
#define ins insert 
#define mp make_pair
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define ft front() 
#define bk back()
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define deb(x) cout<<#x<<" "<<x<<'\n';
#define rep(i,a,b) for (int i = (a); i < (b); ++i)

const ll mod = 1e9+7; // 998244353;
const ll inf = 1e18; 
const ld pie = acos((ld)-1);

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

vector<int> g[200001];
int vis[200001];
int n,m;
int cnt=1;

void dfs(int u){
	vis[u]=1;
	for(auto x:g[u]){
		if(!vis[x]){
			dfs(x);
			cnt++;
		}
	}
}

int32_t main(){
    
	scanf("%lld%lld",&n,&m);
	while(m--){
		int x,y;
		scanf("%lld%lld",&x,&y);
		x--;
		y--;
		g[x].pb(y);
		g[y].pb(x);
	}

	int ans=INT_MIN;

	for(int i=0;i<n;++i){
		if(!vis[i]){
			dfs(i);
			ans=max(ans,cnt);
			cnt=1;
			
		}
	}
	
	printf("%lld\n",ans);

	return 0;

	/*STUFF TO LOOK:	
		1. Check the constraints
		2. Corner cases(n==0||n==1)
		3. Variables in loops
		4. Make sure two ints aren’t multiplied to get a long long
		5. Don't use scanf or printf while using ios_base
		6. using the local variable of the same name when global variable was required to be used
	*/
}


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

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int main()
{
    int n, a;
    vector<pair<int, int>> a_vec;
    pair<int, int> tmp;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a;
        tmp.first = i+1; tmp.second = a;
        a_vec.push_back(tmp);
    }
    sort(a_vec.begin(), a_vec.end(), compare_by_b);
    
    for(int i=0; i<a_vec.size(); i++){
        cout << a_vec[i].first << ' ';
    }
    return 0;
}


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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define rep1(i,n) rep(i,1,n+1)
#define repR(i,s,n) for(ll i = (n-1); i >= (s); i--)
#define repR0(i,n) repR(i,0,n)
#define repR1(i,n) repR(i,1,n+1)

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;
#define fcout cout << fixed << setprecision(18)

class Vec {
public:
  int node; int dist;
  void init(int n, int d) {
    node = n; dist = d;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  ll INF = 1e9 + 7;
  vector<ll> x(N, -INF);
  vector<Vec> v[N];

  rep0(i, M) {
    int l, r, d;
    cin >> l >> r >> d;
    l--; r--;

    Vec V1, V2;
    V1.init(r, d);
    v[l].push_back(V1);
    V2.init(l, -d);
    v[r].push_back(V2);
  }

  bool ok = true;
  rep0(i, N) {
    if (x[i] != -INF) continue;
    x[i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int temp = q.front(); q.pop();
      for (auto V: v[temp]) {
        int n = V.node;
        int d = V.dist;
        if (x[n] == -INF) {
          x[n] = x[temp] + d;
          q.push(n);
        } else if (x[temp] + d == x[n]) {
        } else {
          ok = false;
          break;
        }
      }
    }
    if (!ok) break;
  }
  cout << (ok? "Yes": "No") << BR;

  return 0;
}

Measured memory_bytes: 9728
#include <stdio.h>

int getfinalscore (int,int scores[]);

int main (void)
{
	int i=0,j=0,k=0;
	int n[20];
	int s[20][100];
	int finalscore[20];

	for(i=0;;i++){
		scanf("%d",&n[i]);
		if(n[i]==0) break;

		for(j=0;j<n[i];j++){
			scanf("%d", &s[i][j]);
		}
	}
		
	/*i?????????????????§???performance?????°?????????*/
	/*j??????????????????*/

	for(k=0;k<i;k++){
		finalscore[k]=getfinalscore(n[k],s[k]);
		printf("%d\n", finalscore[k]);
	}

	return 0;
}

int getfinalscore (int judges,int scores[])
{
	int max=0,min=1000,sum=0,average,m;
	
	for(m=0;m<judges;m++){ /*m??????????????????*/
		sum+=scores[m];
		if(scores[m]>max){
			max=scores[m];
		}
		if(scores[m]<min){
			min=scores[m];
		}
	}

	average=(sum-max-min)/(judges-2);

	return average;
}

Measured memory_bytes: 608
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

int main() {

    string N;
    cin >> N;

    int ans = 0;
    for (int i = 0; i < N.size(); i++) ans += (N[i] - '0');

    N[0]--;
    int sum = N[0] - '0';
    for (int i = 1; i < N.size(); i++) sum += 9;

    cout << max(ans, sum) << endl;

}


























































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

int main() {
  int n, m;
  cin >> n >> m;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int h;
    cin >> h;
    if (h >= m) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
const int MAXN = 1e5 + 10;

struct vec {
    double x, y;
    double p;
    vec() {}
    vec(double a, double b)
    {
        x = a, y = b;
    }
    bool operator>(const vec a) const
    {
        return x == a.x ? y > a.y : x > a.x;
    }
    vec operator-(const vec a) const
    {
        return vec(x - a.x, y - a.y);
    }
    vec operator+(const vec a) const
    {
        return vec(x + a.x, y + a.y);
    }
    bool operator<(const vec a) const
    {
        return y == a.y ? x < a.x : y < a.y;
    }
    friend ostream& operator<<(ostream& out, vec& a)
    {
        cout << a.x << ' ' << a.y;
        return out;
    }
    friend istream& operator>>(istream& in, vec& a)
    {
        in >> a.x >> a.y;
        return in;
    }
} p[MAXN];
int n;
double chaji(vec A, vec B)
{
    return A.x * B.y - A.y * B.x;
}
double xuanzhuan(vec a, vec b, vec c)
{
    return chaji(b - a, c - a);
}
vec q[MAXN];
void Andrew(int& tail)
{
    sort(p + 1, p + 1 + n);
    tail = 1;
    q[1] = p[1];
    for (int i = 2; i <= n; i++) {
        while (tail > 1 && xuanzhuan(q[tail - 1], q[tail], p[i]) < 0)
            tail--;
        q[++tail] = p[i];
    }
    int basic = tail;
    for (int i = n - 1; i >= 1; i--) {
        while (tail > basic && xuanzhuan(q[tail - 1], q[tail], p[i]) < 0)
            tail--;
        q[++tail] = p[i];
    }
}

int main()
{
    //freopen("txt.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    int tail;
    Andrew(tail);

    cout << tail-1 << endl;
    for (int i = 1; i < tail; i++)
        cout << q[i] << endl;

    return 0;
}


Measured memory_bytes: 6896
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
6
"""

import sys


# from collections import namedtuple


class Rectangle(object):
    __slots__ = ('pos', 'height')

    def __init__(self, pos=float('inf'), height=-1):
        """
        init a Rectangle
        """
        self.pos = pos
        self.height = height


def gen_rec_info(_carpet_info):
    dp = [[float('inf')] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if int(_carpet_info[i][j]):
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + 1 if i > 0 else 1

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info.append(0)

    for i, v in enumerate(_hi_info):
        rect = Rectangle(pos=i, height=int(v))
        if not rec_stack:
            rec_stack.append(rect)
        else:
            last_height = rec_stack[-1].height
            if last_height < rect.height:
                rec_stack.append(rect)
            elif last_height > rect.height:
                target = i
                while rec_stack and rec_stack[-1].height >= rect.height:
                    pre = rec_stack.pop()
                    area = pre.height * (i - pre.pos)
                    hi_max_area = max(hi_max_area, area)
                    target = pre.pos
                rect.pos = target
                rec_stack.append(rect)

    return hi_max_area


def solve(_rec_info):
    overall_max_area = 0
    for hi_info in _rec_info:
        overall_max_area = max(overall_max_area, get_largest_area(hi_info))

    return overall_max_area


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    # Rectangle = namedtuple('Rectangle', ('pos', 'height'))

    rec_info = gen_rec_info(carpet_info)
    # print(rec_info)
    ans = solve(rec_info)
    print(ans)

Measured memory_bytes: 69880
import java.util.Scanner

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()

    var ans = 1
    while (n / powInt(k, ans) >= 1) {
        ans++
    }
    print(ans)
}

fun powInt(x: Int, y: Int): Int {
    return if (y == 1) x else x * powInt(x, y - 1)
}


Measured memory_bytes: 31392
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
	int n,m, flag = 0, a, b, count = 0, h, w, p = 0;

	cin >> n >> m ;

	vector<int> vec(n+1);

	for (int i = 0; i < m; i++) {
		cin >> h >> w;
		vec[h]++;
		vec[w]++;
	}

	for (int i = 1; i <= n; i++) {
		cout << vec[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
import os
import sys

import numpy as np

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)
if np.all(A == B):
    print(0)
else:
    ans = A.sum() - B[A > B].min()
    print(ans)


Measured memory_bytes: 25288
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const double pi = acos(-1);
const int mod = 100007;
const double eps = 1e-8;
const ll inf = 1e18+9;

int main(){
	string s,t;
	cin >> s >> t;
	int fl = 1;
	if(s.size() != t.size() - 1) fl = 0;
	for(int i = 0;i < s.size();i++){
		if(s[i] != t[i]){
			fl = 0;
			break;
		}
	} 
	if(fl) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size()
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pop pop_back
#define V vector
#define P pair
#define V2(a,b,c) V<V<int>> a(b,V<int>(c))
#define V2a(a,b,c,d) V<V<int>> a(b,V<int>(c,d))
#define incin(a) int a; cin>>a
//#define min min<int>
//#define max max<int>
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
/*template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}*/
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
struct Union{
  vector<int> par;
  Union(int n){
	par= vector<int>(n, -1);
  }
  int find(int x){
    if(par[x]<0)
      return x;
    else
      return par[x]=find(par[x]);
  }
  bool same(int a,int b){
    return find(a)==find(b);
  }
  int Size(int a){
    return -par[find(a)];
  }
  void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)
      return;
    if(Size(b)>Size(a))
      swap<int>(a,b);
    par[a]+=par[b];
    par[b]=a;
  }
};
int ketas(int a){
  string b=to_string(a);
  int c=0;
  fo(i,keta(a)){
    c+=b[i]-'0';
  }
  return c;
}
/*struct aa{
	vector<int> gt;
  aa(int n){
	gt= vector<int>(n, 1);
  }
	void c(V<int> d,int b){
	if(d[b]==0){
		gt[d[b]-1]++;
		gt[gt.sz-1]++;
	}
	else{
		gt[d[b]-1]++;
		c(d,d[d[b]]-1);
	}
}
void cok(int a){
	cout<<gt[a-1]<<endl;
	fo(i,a-1)
	cout<<gt[i]<<endl;
}
};
*/
signed main(){
	int a,b;
	cin>>a>>b;
	cout<<(a-1)*(b-1)<<endl;
}

Measured memory_bytes: 256
import collections
N,K = map(int,input().split())
dic = {}
A = []
for _ in range(N):
    t,d = map(int,input().split())
    A.append([t,d])
A.sort(key = lambda x:x[1], reverse = True)
val = 0
set_ = set()
duplicated = collections.deque([])
for t,d in A[:K]:
    val += d
    if t in set_:
        duplicated.append(d)
    else:
        set_.add(t)
now = val + len(set_)**2

nx = collections.deque(A[K:])
ans = now
c = len(set_)
while len(set_) < K and nx:
    i,j = nx.popleft()
    if i in set_:
        continue
    d = duplicated.pop()
    diff = j-d + 2*c+1
    set_.add(i)
    now += diff
    ans =max(ans,now)
    c += 1
print(ans)


Measured memory_bytes: 23328
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Int32;

class Program
{
    static void Main(string[] args)
    {
        label:
        ReadLine();
        string txt = ReadLine();
        var dic = new Dictionary<char, KeyValuePair<int, int>>();
        for (int i = 0; i < txt.Length; ++i)
        {
            char c = txt[i];
            int key = dic.ContainsKey(c) ? dic[c].Key : i;
            dic[c] = new KeyValuePair<int, int>(key, i);
        }
        var list = dic.Values.Where(p => p.Key < p.Value).ToList();
        int result = 0;
        foreach (var pair in list)
        {
            int left = pair.Key;
            var count = list.Count(p => p.Key <= left && left < p.Value);
            result = Math.Max(result, count);
        }
        WriteLine(result);
    }
}


Measured memory_bytes: 13408
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<long long int>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vvl vector<vector<ll> >
#define vvi vector<vector<int> >
#define pl pair<ll,ll>
#define pb push_back
#define PI 3.14159265
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fri(s,n) for(int i=s;i<n;i++)
#define frj(s,n) for(int j=s;j<n;j++)
#define T(i) int i=1;cin>>i;while(i--)
#define vsi vector<set<int> >
#define pii pair<int,int>
#define inf 1e9
#define vpii vector<pair<int,int> >


ll power(ll a,ll b){
    if(b==0)
        return 1;
    if(b&1)
        return a*power(a,b-1);
    ll temp=power(a,b/2);
    return temp*temp;
    }
bool mycompare(ll a,ll b){
    return a>b;
    }
ll dp[101][100005];
int solve(vi& a,int i,int n,int k){
    if(i==n-1){
        if(k<=a[i])
            return 1;
        return 0;}
    if(dp[i][k]!=-1)
        return dp[i][k];
    int ans=0;
    for(int put=0;put<=a[i];put++){
        ans=(ans+solve(a,i+1,n,k-put))%mod;
    }
    //cout<<i<<" "<<ans<<"\n";
    return dp[i][k]=ans%mod;
    }
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
	int n,k;
  	cin>>n>>k;
  	vector<int> a(n+1);
  	for(int i=1;i<=n;i++)
      	cin>>a[i];
  	int dp[n+1][k+1];
  	memset(dp,0,sizeof dp);
  	for(int c=0;c<=k;c++)
      dp[1][c]=(c<=a[1]?1:0);
  	for(int i=2;i<=n;i++){
      	dp[i][0]=1;
    	for(int c=1;c<=k;c++){
        	dp[i][c]=((dp[i][c-1] +dp[i-1][c])%mod-((c-1-a[i])>=0?dp[i-1][c-1-a[i]]:0)%mod+mod)%mod;
        }
    }
  	cout<<dp[n][k];

}


Measured memory_bytes: 43052
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n = int(input())
	a = list(map(int,input().split()))
	b = list(map(int,input().split()))
	c = list(map(int,input().split()))

	prev = -1
	ans = 0
	for i in a:
		ans += b[i-1]
		if(prev + 1 == i):
			ans+= c[prev-1]
		prev = i
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()


Measured memory_bytes: 5588
from collections import deque

a, b, k = map(int, input().split())
q = deque()

if a < b:
    for i in range(1, a+1):
        if a % i == 0 and b % i == 0:
            q.append(i)
else:
    for i in range(1, b+1):
        if a % i == 0 and b % i == 0:
            q.append(i)

print(q[len(q)-k])


Measured memory_bytes: 3316
N = int(input())
total = 0
number = input().split(" ")
point = input().split(" ")
C = input().split(" ")
for i in point:
    total += int(i)
for j in range(N-1):
    if int(number[j]) == int(number[int(j)+1])-1:
        x = int(number[j])-1
        total += int(C[x])
    else:
        pass
    
print(total)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
#define int unsigned long long
const int base=20040409;
const int N=1e6+5;
int n,ans,m,h[N],p[N],gs[N];
char a[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
	int ret=0,f=0;char c=gc();
	while(!isdigit(c)){if(c=='-')f=1;c=gc();}
	while(isdigit(c)){ret=ret*10+c-48;c=gc();}
	if(f)return -ret;return ret;
}
int find(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}
signed main()
{
	n=read();
	scanf("%s",a+1);
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=p[i-1]*base;
	for(int i=1;i<=n;i++)h[i]=h[i-1]*base+a[i];
	for(int i=1;i<=n;i++)
		gs[a[i]-'a']++;
	bool p=0;
	for(int i=1;i<=n;i++)
		if(gs[a[i]-'a']>=2)p=1;
	if(!p){puts("0");return 0;}
	int l=1,r=n/2;
	while(l<r)
	{
		int mid=(l+r+1)/2;
		for(int i=1;i<=n;i++)
			for(int j=i+mid;j<=n-mid+1;j++)
				if(find(i,i+mid-1)==find(j,j+mid-1))goto xjh;
		r=mid-1;
		continue;
		xjh:l=mid;
	}
	cout<<r;
}

Measured memory_bytes: 4352
import heapq
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

li=[]
push=heapq.heappush
pop=heapq.heappop

push(li,(-a[0]-b[0]-c[0],0,0,0))
ans=[]
used=set()

for _ in range(k):
    value,i,j,l=pop(li)
    ans.append(-value)
    if i<x-1 and (i+1,j,l) not in used:
        push(li,(-a[i+1]-b[j]-c[l],i+1,j,l))
        used.add((i+1,j,l))
    if j<y-1 and (i,j+1,l) not in used:
        push(li,(-a[i]-b[j+1]-c[l],i,j+1,l))
        used.add((i,j+1,l))
    if l<z-1 and (i,j,l+1) not in used:
        push(li,(-a[i]-b[j]-c[l+1],i,j,l+1))
        used.add((i,j,l+1))
for i in ans:
    print(i)

Measured memory_bytes: 5104
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second
#define MP make_pair
#define PB push_back

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;


int main()
{
  int n ;
  cin >> n ;
  vector<int> hei(n+1) ;
  hei.at(0) = 0 ;
  REP(i,n){
    cin >> hei.at(i+1) ;
  }
  
  FOR(i,1,n+1){
    if(hei.at(i)>hei.at(i-1)){
      hei.at(i)-- ;
    }
    if(hei.at(i-1)>hei.at(i)){
      cout <<"No"<<endl ;
      return 0 ;
    }
  }
  
  cout <<"Yes"<<endl ;


  return 0 ;
}

Measured memory_bytes: 640
#include <vector>
#include <iostream>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int ok[N];

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  int n;
  cin >> n;
  int x, m;
  cin >> x >> m;
  vector<int> v;
  int ans = 0;
  for (int i = x;; i = (i * i) % m) {
    if (++ok[i] == 2) {
      break;
    }
    ans += i;
    v.push_back(i);
  }
  int i = 0;
  while (ok[v[i]] != 2) {
    ++i;
  }
  for (int j = i; j < v.size(); ++j) {
    ans += v[j] * ((n - i) / (v.size() - i));
    ans -= v[j];
  }
  for (int j = i; j < i + ((n - i) % (v.size() - i)); ++j) {
    ans += v[j];
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 4620
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int N;
        cin >> N;
        vector<Int> X(N), L(N);
        vector<pair<Int, Int>> lr(N);
        for (int i = 0; i < N; ++i) {
            cin >> X[i] >> L[i];
            lr[i].first = X[i] - L[i];
            lr[i].second = X[i] + L[i];
        }

        sort(all(lr), [](auto a, auto b) {
            return a.second < b.second;
        });

        Int ans = 0;
        Int las = -INFl;

        for (int i = 0; i < N; ++i) {
            if (las <= lr[i].first) {
                las = lr[i].second;
                ans++;
            }
        }
        cout << ans << endl;
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 3960
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n = int(readline())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,set()))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            que.append((i,L|{mi*100+ma}))
                     
import itertools
#print(c)
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = set()
    for k in j:
      K |= k
    l = len(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Measured memory_bytes: 74648
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
  string S;
  cin>>S;
  bool easy=true;
  rep(i,3){
      if(S[i]==S[i+1]){
          easy=false;
          break;
      }
  }
  if(easy==true){
      cout<<"Good"<<endl;
  }
  else{
      cout<<"Bad"<<endl;
  }
  
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <numeric>
std::vector<int> read();
std::vector<std::vector<std::string>> make_rectangle(int, int);
std::vector<std::vector<std::string>> make_frame(int, int);
std::vector<std::vector<std::string>> make_chess(int, int);
void draw(std::vector<std::vector<std::string>>);

int main()
{
	std::vector<int> height;
	std::vector<int> width;
	std::vector<int> input;
	int count = 0;

	while (true)
	{
		input = read();

		if (input[0] == 0 && input[1] == 0)	break;

		height.emplace_back(input[0]);
		width.emplace_back(input[1]);

		++count;
	}

	for (int i = 0; i < count; i++)
	{
		std::vector<std::vector<std::string>> rectangle = make_chess(height[i], width[i]);
		draw(rectangle);
	}

	return 0;
}

std::vector<int> read()
{
	std::vector<int> input(2);
	std::cin >> input[0] >> input[1];

	return input;
}

std::vector<std::vector<std::string>> make_rectangle(int height, int width)
{
	std::vector<std::vector<std::string>> rectangle(height, std::vector<std::string>(width));

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			rectangle[i][j] = "#";
		}
	}

	return rectangle;
}

std::vector<std::vector<std::string>> make_frame(int height, int width)
{
	std::vector<std::vector<std::string>> rectangle(height, std::vector<std::string>(width));

	for (int i = 0; i < width; ++i)
	{
		rectangle[0][i] = "#";
		rectangle[height - 1][i] = "#";
	}

	for (int i = 1; i < height-1; ++i)
	{
		rectangle[i][0] = "#";
		rectangle[i][width - 1] = "#";

		for (int j = 1; j < width-1; ++j)
		{
			rectangle[i][j] = ".";
		}
	}

	return rectangle;
}

std::vector<std::vector<std::string>> make_chess(int height, int width)
{
	std::vector<std::vector<std::string>> rectangle(height, std::vector<std::string>(width));

	for (int i = 0; i < height; ++i)
	{
		for (int j = 0; j < width; ++j)
		{
			rectangle[i][j] = (i + j) % 2 ? "." : "#";
		}
	}

	return rectangle;
}

void draw(std::vector<std::vector<std::string>> rectangle)
{
	for (auto line : rectangle)
	{
		for (auto point : line)
		{
			std::cout << point;
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}



Measured memory_bytes: 4488
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0007
{
    class Program
    {
        static void Main(string[] args)
        {
            // 10万円の借金に対し1週間ごとに5%の利子が発生し1000円未満を切り上げるとき、n週間後の残高を出力するプログラム

            int n = int.Parse(Console.ReadLine());
            double balance=100000;
            for (int i = 0; i < n; i++)
            {
                double insert = (Math.Ceiling((balance * 0.05)/1000))*1000;
                balance += insert;
            }
            Console.WriteLine(balance);
        }
    }
}



Measured memory_bytes: 15876
#include <bits/stdc++.h>
#include <ctime>
#include <unordered_map>
#include <stdlib.h>
using namespace std;
#define ll  long long int
#define mod 1000000007
#define modd 998244353
#define com(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define pri(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<endl;
#define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*__builtin_clz();
__builtin_ctz();
__builtin_popcount();*/
int main()
{
    speed;
    ll h ,a;
    cin>>h>>a;
    ll x = h/a;
    if(h%a!=0)
    x++;
    cout<<x<<"\n";
    cerr << "\nTime elapsed: " << 1000 * clock()/CLOCKS_PER_SEC << "ms\n";
}
 
 
 
 
 
// bool prime[100000];
 
// // int gcdExtended(int a, int b, int *x, int *y) ;
// ll modInverse(int a, int m) 
// { 
//     int x, y; 
//     int g = gcdExtended(a, m, &x, &y); 
//     // if (g != 1) 
//     //     cout << "Inverse doesn't exist"; 
//     // else
//     // { 
//         // m is added to handle negative x 
//         int res = (x%m + m) % m; 
//         return res; 
//     // } 
// } 
  
// // // C function for extended Euclidean Algorithm 
// int gcdExtended(int a, int b, int *x, int *y) 
// { 
//     // Base Case 
//     if (a == 0) 
//     { 
//         *x = 0, *y = 1; 
//         return b; 
//     } 
  
//     int x1, y1; // To store results of recursive call 
//     int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
//     // Update x and y using results of recursive 
//     // call 
//     *x = y1 - (b/a) * x1; 
//     *y = x1; 
  
//     return gcd; 
// } 
// ll modu(ll x)
// {
//     if(x<0)
//     {
//         x+=mod;
//     }
//     else 
//     {
//         x=x%mod;
//     }
//     return x;
// }
 
// void SieveOfEratosthenes(int n) 
// { 
//     // Create a boolean aay "prime[0..n]" and initialize 
//     // all entries it as true. A value in prime[i] will 
//     // finally be false if i is Not a prime, else true. 
     
//     memset(prime, true, sizeof(prime)); 
  
//     for (int p=2; p*p<=n; p++) 
//     { 
//         // If prime[p] is not changed, then it is a prime 
//         if (prime[p] == true) 
//         { 
//             // Update all multiples of p greater than or  
//             // equal to the square of it 
//             // numbers which are multiple of p and are 
//             // less than p^2 are already been marked.  
//             for (int i=p*p; i<=n; i += p) 
//                 prime[i] = false; 
//         } 
//     } 
//     prime[1]=false;
  
//     // Print all prime numbers 
//     // for (int p=2; p<=n; p++) 
//     //    if (prime[p]) 
//     //       cout << p << " "; 
// } 
// ll power(ll x, unsigned ll y, ll p) 
// { 
//     ll res = 1;      // Initialize result 
  
//     x = x % p;  // Update x if it is more than or  
//                 // equal to p 
  
//     while (y > 0) 
//     { 
//         // If y is odd, multiply x with result 
//         if (y & 1) 
//             res = (res*x) % p; 
  
//         // y must be even now 
//         y = y>>1; // y = y/2 
//         x = (x*x) % p;   
//     } 
//     return res; 
// } 


Measured memory_bytes: 256