akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pii             pair<int , int >
#define in(a)           scanf("%d", &a)
#define in2(a, b)       scanf("%d%d", &a, &b)
#define in3(a, b, c)    scanf("%d%d%d", &a, &b, &c)
#define piil            pair<ll , ll >
#define inl(a)          scanf("%lld", &a)
#define inl2(a, b)      scanf("%lld%lld", &a, &b)
#define inl3(a, b, c)   scanf("%lld%lld%lld", &a, &b, &c)
#define ins(s)          scanf("%s",s)
#define prst(s)         printf("%s\n",s)
#define pn              printf("\n")
#define pr(a)           printf("%d\n", a)
#define prl(a)          printf("%lld\n", a)
#define prs(a)          printf("%d ", a)
#define pr2(a, b)       printf("%d %d\n", a, b)
#define pr3(a, b, c)    printf("%d %d %d\n", a, b, c)
#define prsl(a)         printf("%lld ", a)
#define prl2(a, b)      printf("%lld %lld\n", a, b)
#define prl3(a, b, c)   printf("%lld %lld %lld\n", a, b, c)
#define pcs(a)          printf("Case %d: ", a)
#define pf              printf
#define sc              scanf
#define m_p             make_pair
#define vi              vector<int >
#define vil             vector<ll >
#define pb              push_back
#define fi              first
#define sc              second
#define mem(a, b)       memset((a), (b), sizeof(a))
#define lg2(n)         (31-__builtin_clz(n))
#define PI		        acos(-1.0)
#define N 100005
#define unq(v)       v.erase(unique(all(v)),v.end())
#define inf 2e18
#define ll long long
#define ull unsigned long long
#define fbo find_by_order
#define ook order_of_key
#define fi first
#define sc second
#define __  std::ios_base::sync_with_stdio (false); cin.tie(0); cout.tie(0);
#define Check(n, pos) (n & (1<<pos))
#define Set(n, pos) (n | (1<<pos))
ll gcd(ll a, ll b){if(b==0) {return a;}return gcd(b, a % b);}
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename F, typename S>
using ordered_map = tree<F, S, less<F>, rb_tree_tag, tree_order_statistics_node_update>;
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); deb(_it, args); }
void deb(istream_iterator<string> it) {}
template<typename T, typename... Args>
void deb(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    deb(++it, args...);
}
ll BigMod(ll B,ll P,ll M){     ll R=1; while(P>0)      {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;}
//______________________________________________________________________________________________________________________________________________________
ll dp[N],arr[N],kp[N];
char str[N];
#define mod 1000000007
ll n,m,k,a,b,t;

int main()
{
    __;

   ll sum=0;
   string s;
   cin>>n;
   cin>>s;
   sort(s.begin(),s.end());
   for(int i=0;i<s.size();i++)
   {
       dp[s[i]-'a'+1]++;
   }
   ll ans=1;
  for(int i=1;i<=26;i++)
  {

     ans=(ans*dp[i])+ans;
     ans%=mod;

  }
  cout<<(ans-1)<<endl;


    return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int N=1e5+5;
int n,a[3*N];
LL dp1[N],dp2[N],ans;
priority_queue<int> q;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<3*n;++i) 
		cin>>a[i];
	for(int i=0;i<n;++i) {
		dp1[0]+=a[i];
		q.push(-a[i]);
	}
	for(int i=1;i<=n;++i) {
		dp1[i]=dp1[i-1];
		if(a[i+n-1]>-q.top()) {
			dp1[i]+=q.top();
			q.pop();
			dp1[i]+=a[i+n-1];
			q.push(-a[i+n-1]);
		}
	}
	while(!q.empty()) q.pop();
	for(int i=3*n-1;i>=2*n;--i) {
		dp2[0]+=a[i];
		q.push(a[i]);
	}
	for(int i=1;i<=n;++i) {
		dp2[i]=dp2[i-1];
		if(a[2*n-i]<q.top()) {
			dp2[i]-=q.top();
			q.pop();
			dp2[i]+=a[2*n-i];
			q.push(a[2*n-i]);
		}
	}
	ans=-1e17;
	for(int i=0;i<=n;++i) {
		ans=max(ans,dp1[i]-dp2[n-i]);
		//cout<<i<<" "<<dp1[i]<<" "<<dp2[n-i]<<endl;
	}
	cout<<ans<< endl;	
}

Measured memory_bytes: 3576
#include<stdio.h>
int ssearch(int S[], int n, int k)
{
  int i=0;
  S[n]=k;
  
  while(S[i]!=k)i++;
  return i!=n;
}

int main(){
  int i,n,S[10001],q,key,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&S[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if( ssearch(S, n, key) )sum++;
  }
  printf("%d\n",sum);
  
  return 0;
}
    



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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll from;
	ll to;
	ll cost;
};
using Graph = vector<vector<Edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define RES(a, n) (a).resize(n)
#define VLCIN(a, n) REP(i,n){cin >> a[i];}
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 2.0 * asin(1.0);
const ll INF = 1L<<60;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MAX = (ll)pow(10,7);
/****** define constant end ********/
/****** define variable start ******/
ll n;
vll a;
Graph G;
/******* define variable end *******/
vector<vector<ll>> d;

void warshall_floyd(){
	for(ll k = 0; k < n; k++){
		for(ll i = 0; i < n; i++){
			for(ll j = 0; j < n; j++){
				if(i == j){
					d[i][j] = 0;
					d[j][i] = 0;
				}else{
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
	}
}
std::vector<ll> dij;

void dijkstra(const Graph &G, ll s){
	std::priority_queue<P, std::vector<P>, std::greater<P>> que;
	for(ll i = 0; i < n; i++) dij[i] = INF;
	dij[s] = 0;
	que.push(P(0, s));

	while(!que.empty()){
		P p = que.top(); que.pop();
		ll v = p.second;
		if(dij[v] < p.first) continue;
		for(ll i = 0; i < G[v].size(); i++){
			Edge e = G[v][i];
			if(dij[e.to] > dij[v] + e.cost){
				dij[e.to] = dij[v] + e.cost;
				que.push(P(dij[e.to], e.to));
			}
		}
	}
}
int solve() {
	cin >> n;
	G.resize(n);
	a.resize(n, vl(n));
	d.resize(n, vl(n, INF));
	dij.resize(n);
	REP(i, n){
		REP(j, n){
			cin >> a[i][j];
			if(i != j){
				Edge e = {i, j, a[i][j]};
				G[i].push_back(e);
				d[i][j] = a[i][j];
			}else{
				Edge e = {i, j, 0};
				G[i].push_back(e);
			}
		}
	}
	warshall_floyd();
	bool flag = true;
	ll mi = INF;
	REP(i, n){
		REP(j, n){
			if(a[i][j] != d[i][j]){
				flag = false;
				break;
			}
			mi = min(mi, d[i][j]);
		}
		if(!flag) break;
	}
	if(!flag) {
		cout << -1 << endl;
		return 0;
	}else{
		vll an(n, vl(n, -1));
		REP(i, n){
			REP(j, n){
				REP(k, n){
					if(an[i][k] == 0 || (d[i][j] + d[j][k] == d[i][k] && i != j && j != k && i != k)){
						an[i][k] = 0;
					}else{
						an[i][k] = d[i][k];
					}
				}
			}
		}
		ll ans = 0;
		REP(i, n){
			FOR(j, i+1, n){
				ans += an[i][j];
			}
		}
		cout << ans << endl;
	}
	return 0;
}
int main() {
	//clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 8784
char*p;s[5],t,d[999],D;main(g){for(memset(s,'~',17);!d[99];t++){for(g=D;g--;)if(t==d[g]+g%2*17+g%3*3+19)while(p=strchr(s,g+1))*p='~';for(;t>=D*5&&(g=D%5-1?2:5,p=strstr(s,"~~~~~"+5-g));memset(p,++D,g))d[D]=t;}for(;~scanf("%d",&g);)printf("%d\n",d[g]-g*5);}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
constexpr auto INF = 1000000000;
constexpr auto LLINF = 1LL << 62;
constexpr auto mod = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }

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

    string s;
    cin >> s;
    vector<char> c;
    for (char i : s)c.push_back(i);
    SORT(c);
    cout << (c[0] == c[1] && c[2] == c[3] && c[1] != c[2] ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 256
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    auto xs = readln.split.to!(int[]);
    if (xs[0] != xs[1]) writeln(xs.reduce!max * 2 - 1);
    else writeln(xs[0] * 2);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln =  '\n';

const int mx=200010;
const ll mod=1e9+7;


int main(){
  int n;
  cin >> n;
  vector<ll> a(n),b(n),c(n);
  rep(i,n){
    cin >> a[i] >> b[i] >> c[i];
  }

  vector<vector<ll>> dp(mx, vector<ll>(3,0));
  rep(i,n){
    dp[i+1][0] = max(dp[i+1][0], max(dp[i][1],dp[i][2])+a[i]);
    dp[i+1][1] = max(dp[i+1][1], max(dp[i][0],dp[i][2])+b[i]);
    dp[i+1][2] = max(dp[i+1][2], max(dp[i][0],dp[i][1])+c[i]);
  }
  ll ans = max(max(dp[n][0],dp[n][1]),dp[n][2]);
  cout << ans << ln;
  return 0;
}

Measured memory_bytes: 13568
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<stdbool.h>
#include<tgmath.h>
#include<time.h>
#define ll long long
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define miin(a,b,c) min((a), min((b), (c)))
#define maax(a,b,c) max((a), max((b), (c)))

char s[1111111] = {}, c;
int q, a, b, i = 500000, j, nyan = 0;

int main(){
    j = i;while((c=getchar()) != 10){s[j] = c;j++;}j--;
    scanf("%d", &q);
    while(q--){
        scanf("%d", &a);
        if(a == 1){
            nyan ^= 1;
        }else {
            scanf("%d %c",&b, &c);
            if(b == 1){
                if(nyan == 0){
                    i--;
                    s[i] = c;
                }else {
                    j++;
                    s[j] = c;
                }
            }else {
                if(nyan == 0){
                    j++;
                    s[j] = c;
                }else {
                    i--;
                    s[i] = c;
                }
            }
        }
    }
    if(nyan == 0){
        for(int k=i;k<=j;k++)putchar(s[k]);
    }else{
        for(int k=j;k>=i;k--)putchar(s[k]);
    }
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

int N, Q;
vector<vector<int>> G;
vector<int> A;

void dfs(int v, int p) {
    if (p != -1) A[v] += A[p];

    for (auto nv : G[v]) {
        if (nv == p) continue;
        dfs(nv, v);
    }
}

int main() {
    cin >> N >> Q;
    G.resize(N + 1);
    A.assign(N + 1, 0);
    for (int i = 0; i < N - 1; i++) {
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 0; i < Q; i++) {
        int p, x; cin >> p >> x;
        A[p] += x;
    }

    dfs(1, -1);

    for (int i = 1; i <= N; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 23552
#include "bits/stdc++.h"
#include <unordered_set>

#define _CRT_SECURE_NO_WARNINGS

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

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

using LL = long long int;
using LD = long double;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

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

	int w, h, n;
	cin >> w >> h >> n;

	vvi M(h, vi(w));

	for (int i = 0; i < n; i++) {
		int x, y, a;
		cin >> x >> y >> a;

		if (a == 1) {
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < x; j++) {
					M[i][j] = 1;
				}
			}
		} else if (a == 2) {
			for (int i = 0; i < h; i++) {
				for (int j = x; j < w; j++) {
					M[i][j] = 1;
				}
			}
		} else if (a == 3) {
			for (int i = 0; i < y; i++) {
				for (int j = 0; j < w; j++) {
					M[i][j] = 1;
				}
			}
		} else {
			for (int i = y; i < h; i++) {
				for (int j = 0; j < w; j++) {
					M[i][j] = 1;
				}
			}
		}

		//cout << "=========================" << endl;
		//for (int i = 0; i < h; i++) {
		//	for (int j = 0; j < w; j++) {
		//		cout << M[i][j];
		//	}
		//	cout << endl;
		//}
	}

	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (M[i][j] == 0) ans++;
		}
	}

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

Measured memory_bytes: 256
def main(argv)
  n = gets.chomp.to_i
  d = gets.chomp.split(' ').map(&:to_i).sort
  
  i = n / 2
  
  puts (d[i] - d[i - 1]).to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 12024
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define vi vector<int>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int MOD = 1e9+7;
int32_t main() {
    // freopen("in.txt", "r", stdin);
    IOS;
    int n; cin >> n;
    int x = 1, y = 1, z = 1;
    for(int i=1; i<=n; i++) {
        (x *= 10) %= MOD;
        (y *= 9) %= MOD;
        (z *= 8) %= MOD;
    }
    int ans = (x - 2*y + z) % MOD;
    cout << (ans + MOD) % MOD;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h,w,k;
  cin>>h>>w>>k;
  vector<vector<char>> c(h,vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>c[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<(1<<h);i++){
    for(int j=0;j<(1<<w);j++){
      int cnt=0;
      for(int k=0;k<h;k++){
        for(int s=0;s<w;s++){
          if((i>>k)&1)continue;
          if((j>>s)&1)continue;
          if(c[k][s]=='#')cnt++;
        }
      }
      if(cnt==k)ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[100001];
int a,b,c;

int main()
{
    a=0;
    b=0;
    c=0;
    scanf("%s",&s);
    int n = strlen(s);
    for(int i = 0 ;i < n ;i++)
        if(s[i]=='a')
            a++;
        else if(s[i]=='b')
            b++;
        else
            c++;
    if(n==1)
        printf("YES\n");
    else if(max(a,max(b,c))-min(a,min(b,c))>1)
            printf("NO\n");
    else if(min(a,min(b,c))==0&&max(a,max(b,c)) >= 2)
            printf("NO\n");
    else if(max(a,max(b,c)) > n / 2)
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}


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

typedef long long ll;
ll n;

ll dfs(ll x, ll three, ll five, ll seven){
	if(n<x) return 0;
	ll ret = 0;
	if(0<three && 0<five && 0<seven) ret++;
	ret += dfs(x*10+3, three+1, five, seven);
	ret += dfs(x*10+5, three, five+1, seven);
	ret += dfs(x*10+7, three, five, seven+1);

	return ret;
}


int main(){
	cin >> n;
	cout << dfs(0,0,0,0) << endl;

	return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *left;
  struct node *right;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
Node root;
 
Node treeMinimum(Node x){
  while(x->left!=NIL){
    x = x->left;
  }
  return x;
}
 
Node treeSearch(Node u, int k){
     if (u == NIL){return NIL;}
    if (u->key == k){ return u; }
    else if (u->key > k){
        return treeSearch(u->left, k);
    }
    else{
        return treeSearch(u->right, k);
    }
}
     
Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL){
    return treeMinimum(x->right);
  }
  y=x->parent;
  while(y != NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
 
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left == NIL || z->right == NIL)
    y=z;
  else y=(Node)treeSuccessor(z);
   
  if(y->left!=NIL)
    x=y->left;
  else x =y->right;
 
  if(x!=NIL)
    x->parent = y->parent;
  if(y->parent==NIL)
    root = x;
  else if(y==y->parent->left)
    y->parent->left = x;
  else y->parent->right = x;
 
  if(y!=z)
    z->key = y->key;
}
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x!=NIL){
    y = x;
    if(z->key<x->key){
      x = x->left;
    }
    else{
      x =x->right;
    }
  }
  z->parent= y;
  if(y==NIL){
    root = z;
  }
  else if(z->key<y->key){
    y->left =z;
  }
  else{
    y->right =z;
  }
   
  }
 
void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
 
void preorder(Node u){
  if(u!=NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
      
      
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  
  return 0;
}

Measured memory_bytes: 19364
#include<stdio.h>
int main(){
    int A[100];
    int N;
    int i,j,n,m;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    for(n=0;n<N;n++){
        printf("%d",A[n]);
        if(n<N-1){
            printf(" ");
        }
    }
    printf("\n");

    for(i=1;i<N;i++){
        m = A[i];
        j = i-1;
        while(j >= 0 && A[j] > m){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = m;
        for(n=0;n<N;n++){
            printf("%d",A[n]);
            if(n<N-1){
                printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

ll top10(ll n) {
  if (n < 10) return n;
  return top10(n/10);
}

ll len(ll n) {
  if (n == 0) return 0;
  return 1 + len(n/10);
}

ll sum(ll n) {
  if (n == 0) return 0;
  return (n%10) + sum(n/10);
}

int main()
{
  ll n;
  cin>>n;
  ll top = top10(n);
  ll num = len(n);
  cout << max(sum(n), top-1 + (num-1) * 9) << endl;
  return 0;
}


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

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

# print(rb)
rmSet = set()

# rb.sort(key=lambda x:x[0])
rb.sort()
r = rb[0][0] + rb[0][1]

# print(rb)
prevIdx = 0

for i in range(1, n):
    # print(i, r)
    l1 = rb[i][0] - rb[i][1]

    # Skip if not overlapped with previous one
    if l1 >= r:
        r = rb[i][0] + rb[i][1]
        continue

    r1 = rb[i][0] + rb[i][1]

    # Remove self if r is bigger than previous one
    if r1 > r:
        # print('(A) remove:', rb[i][0])
        rmSet.add(rb[i][0])
    else:
        # print('(B) remove:', rb[prevIdx][0])
        r = r1
        rmSet.add(rb[prevIdx][0])
        prevIdx = i
        # print('(B) remove:', rb[i - 1][0])
        # r = r1
        # rmSet.add(rb[i - 1][0])

# print('rmSet:', rmSet)
print(n - len(rmSet))

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

using ull = unsigned long long;
using ll = long long;
using ld = long double;

const int mod = 998244353;
const int inf = INT_MAX;
const int N = 2e5 + 5;

template <const int M> struct ModInt {
    int val;
    ModInt(ll x = 0): val((x % M + M) % M) {}
    ModInt pow(ll n) const { ModInt ans = 1, x = val; while (n) { if (n & 1) ans *= x; x *= x; n /= 2; } return ans; }
    ModInt inverse() const { return pow(M - 2); }
    ModInt operator+ (const ModInt& m) { int res = val + m.val; return res < M ? res : res - M; }
    ModInt operator- (const ModInt& m) { int res = val - m.val; return res < 0 ? res + M : res; }
    ModInt operator* (const ModInt& m) { return val * (ll)m.val % M; }
    ModInt operator/ (const ModInt& m) { return *this * m.inverse(); }
    ModInt operator+=(const ModInt& m) { return *this = *this + m; }
    ModInt operator-=(const ModInt& m) { return *this = *this - m; }
    ModInt operator*=(const ModInt& m) { return *this = *this * m; }
    ModInt operator/=(const ModInt& m) { return *this = *this / m; }
    friend ostream& operator<<(ostream& os, const ModInt& m) {
        os << m.val;
        return os;
    }
};

using mint = ModInt<mod>;

int n, k;
mint dp[2*N];
pair<int, int> a[N];

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

    cin >> n >> k;
    for (int i = 0; i < k; i++) cin >> a[i].first >> a[i].second;

    dp[1] = 1;
    dp[2] = -1;
    for (int i = 1; i <= n; i++) {
        dp[i] += dp[i - 1];
        for (int j = 0; j < k; j++) {
            dp[i + a[j].first] += dp[i];
            dp[i + a[j].second + 1] -= dp[i];
        }
    }
    cout << dp[n] << '\n';
    return 0;
}

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m, x;
  cin >> n >> m >> x;
  vi a(m + 1, 0);
  for (int i = 1; i < m + 1; i++) {
    cin >> a[i];
  }
  int ans1 = 0;
  for (int i = x; i < n; i++) {
    if (find(a.begin(), a.end(), i) != a.end()) {
      ans1++;
    }
  }
  int ans2 = 0;
  for (int i = x; i > 0; i--) {
    if (find(a.begin(), a.end(), i) != a.end()) {
      ans2++;
    }
  }
  cout << min(ans1, ans2) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

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

const double PI=(acos(-1));

int n=0,a=0,b=0,c=0;
int ans=10000;
vector<int> l(n,0);
vector<int> vc(n,0);

void calc(vector<int> v){
    int aa=0,bb=0,cc=0;
    int s=0,t=0,r=0;
    int mp=0;
    rep(i,n){
        if(v[i]==0){
            aa+=l[i];
            ++s;
        }else if(v[i]==1){
            bb+=l[i];
            ++t;
        }else if(v[i]==2){
            cc+=l[i];
            ++r;
        }else{
        }
    }
    mp+=(s==0)?10000:(s-1)*10;
    mp+=(t==0)?10000:(t-1)*10;
    mp+=(r==0)?10000:(r-1)*10;
    mp+=abs(a-aa)+abs(b-bb)+abs(c-cc);
    ans=min(ans,mp);
}

void dfs(int d,vector<int> v){
    if(d==n){
        calc(v);
        return;
    }
    for(int i=0;i<4;++i){
        v[d]=i;
        dfs(d+1,v);
    }
}

int main(){
    cin>>n>>a>>b>>c;
    l.assign(n,0);
    vc.assign(n,0);
    rep(i,n)cin>>l[i];
    dfs(0,vc);
    cout<<ans<<endl;
}


Measured memory_bytes: 3576
#include <stdio.h>

int main(){

  int i, j, k, p, n[100], x[100], ans, output;
  int m = 0;
  
  while(1){
    scanf("%d %d", &n[m], &x[m]);
    if( n[m] == 0 && x[m] == 0){
      m--;
      break;
    }
    m++;
  }
  
  for ( p = 0; p <= m; p++){
    output = 0;
    for( i = 1; i <= n[p] - 2 ; i++){
      for( j = i + 1; j <= n[p] - 1; j++){
        for ( k = j + 1; k <= n[p]  ; k++){
          ans = i + j + k;
          if ( x[p] == ans ){
            output = output + 1;
          }
        }
      }
    }
    printf("%d\n",output);
  }

  return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

string S;

int main() {
    cout << fixed << setprecision(15);
    cin >> S;
    cout << S.substr(0, 3) << endl;
}

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



int main(){
  int N,K;
  cin>>N>>K;
  string S;
  cin>>S;
  
  if(S.at(K-1)=='A')
    S.at(K-1)='a';
  
  if(S.at(K-1)=='B')
    S.at(K-1)='b';
  
  if(S.at(K-1)=='C')
    S.at(K-1)='c';
  
  cout<<S;
}

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

int N;

class bintree {
public:
  bintree(int n) : buf(new int[n]) {
    for (int i = 0; i < n; i++)
      buf[i] = 0;
  }
  int *buf;
};

int main(int argc, char **argv) {
  cin >> N;
  int H[N];
  int i, cnt = 0, maxhight = 0;

  for (i = 0; i < N; i++) {
    cin >> H[i];
    if (maxhight <= H[i]) {
      maxhight = H[i];
      cnt++;
    }
  }
  cout << cnt << endl;

  return 0;
}


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

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

using namespace std;

int main(void){
  int l, r, d;
  int i, cnt = 0;
  
  cin >> l >> r >> d;

  for(i = l; i <= r; i++){
    if(i % d == 0){
      cnt++;
    }
  }

  cout << cnt;

  return 0;
}


Measured memory_bytes: 3640
#len(s)//2-s.count("p")
def 解():
    iG = 0
    iR = 0
    for s in input().rstrip():
        if s == "g" :
            if 0 < iG:
                iR += 1
                iG -= 1
            else:
                iG += 1
        else:
            if 0 < iG:
                iG -= 1
            else:
                iR -= 1
                iG += 1
    print(iR)
解()


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;
#define all(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0; i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)

const int MOD = 1000000007;

int main(){
    int N, K; cin >> N >> K;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<vector<int>> dp(N+1,vector<int>(K+1,0));
    vector<vector<int>> dp_sum(N+1,vector<int>(K+1,0));
    dp[0][0] = 1;
    REP(j,K+1) dp_sum[0][j] = 1;
    REP(i,N+1) dp_sum[i][0] = 1;
    REP(i,N)REP(j,K+1){
        if (a[i]>=j){
            dp[i+1][j] = dp_sum[i][j];
            if(j) dp_sum[i+1][j] = (dp_sum[i+1][j-1] + dp[i+1][j]) % MOD;
        }else{
            dp[i+1][j] = (MOD + dp_sum[i][j] - dp_sum[i][j-a[i]-1]) % MOD;
            dp_sum[i+1][j] = (dp_sum[i+1][j-1] + dp[i+1][j]) % MOD;
        }
    }
    cout << dp[N][K] << endl;
    return 0;
}

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

template <uint32_t mod>
class modint{
    uint64_t value;
public:
    constexpr modint(const int64_t x=0) noexcept: value(x % mod + (x < 0 ? mod : 0)){ }
    constexpr explicit operator uint64_t() const noexcept{ return value; }
    constexpr modint inverse() const noexcept{ return pow(*this, mod-2); }
    constexpr bool operator==(const modint &rhs) const noexcept{ return value == rhs.value; }
    constexpr bool operator!=(const modint &rhs) const noexcept{ return value != rhs.value; }
    constexpr modint operator+() const noexcept{ return modint(*this); }
    constexpr modint operator-() const noexcept{ return modint(mod - value); }
    constexpr modint operator+(const modint &rhs) const noexcept{ return modint(*this) += rhs; }
    constexpr modint operator-(const modint &rhs) const noexcept{ return modint(*this) -= rhs; }
    constexpr modint operator*(const modint &rhs) const noexcept{ return modint(*this) *= rhs; }
    constexpr modint operator/(const modint &rhs) const noexcept{ return modint(*this) /= rhs; }
    constexpr modint &operator+=(const modint &rhs) noexcept{
        if((value += rhs.value) >= mod) value -= mod;
        return *this;
    }
    constexpr modint &operator-=(const modint &rhs) noexcept{ return *this += mod - rhs.value; }
    constexpr modint &operator*=(const modint &rhs) noexcept{
        if((value *= rhs.value) >= mod) value %= mod;
        return *this;
    }
    constexpr modint &operator/=(const modint &rhs) noexcept{ return *this *= rhs.inverse(); }
    constexpr modint operator++(int) noexcept{
        modint ret(*this);
        if((++value) >= mod) value -= mod;
        return ret;
    }
    constexpr modint operator--(int) noexcept{
        modint ret(*this);
        if((value += mod - 1) >= mod) value -= mod;
        return ret;
    }
    constexpr modint &operator++() noexcept{ return *this += 1; }
    constexpr modint &operator--() noexcept{ return *this -= 1; }
    friend std::ostream &operator<<(std::ostream &os, const modint<mod> &x){ return os << x.value; }
    friend std::istream &operator>>(std::istream &is, modint<mod> &x){
        int64_t i;
        is >> i;
        x = modint<mod>(i);
        return is;
    }
    friend constexpr modint<mod> pow(const modint<mod> &x, uint64_t y){
        modint<mod> ret{1}, m{x};
        while(y > 0){
            if(y & 1) ret *= m;
            m *= m;
            y >>= 1;
        }
        return ret;
    }
};
constexpr int64_t mod = 1'000'000'007;

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    modint<mod> ans = pow(modint<mod>{2}, n) - 1;
    modint<mod> nCa = n, nCb = n;
    for(int i=2;i<=a;++i){
        nCa *= n - i + 1;
        nCa /= i;
    }
    for(int i=2;i<=b;++i){
        nCb *= n - i + 1;
        nCb /= i;
    }
    ans -= nCa + nCb;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int i,j,k,m,n,x,t,y,vis[N],a[N];
char s[N];
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (i = 1; i <= n; ++i)vis[i] = (s[i] == '1');
    if (!vis[1] || !vis[n - 1] || vis[n])return puts("-1"), 0;
    for (i = 2; i < n - 1; ++i)if (vis[i] != vis[n - i])return puts("-1"), 0;
    for (x = 0, i = 1; i <= n; ++i) {
        if (vis[i])while (x > 0)printf("%d %d\n", a[x--], i);
        if (i != n)a[++x] = i;
    }
    while (x > 0)printf("%d %d\n", a[x--], n);
}


Measured memory_bytes: 2304
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;

#define MAXN 600

typedef array<short,4> tile;

int n;
tile a[MAXN];
long d[MAXN];

int input() {
	if (scanf("%d", &n) < 0) return 0;
	for (int i=0; i<n; i++)
		for (int j=0; j<4; j++)
			scanf("%hd", &a[i][j]);
	return 1;
}

void init() {
}

tile rotate(const tile &x, int k=1) {
	tile y;
	for (int i=0; i<4; i++) y[(i+k) % 4] = x[i];
	return y;
}

tile normalize(const tile &x) {
	tile z=x;
	for (int i=1; i<4; i++) {
		tile y=rotate(x, i);
		if (y<z) z=y;
	}
	return z;
}

int mirror(const tile &x) {
	int r = 1;
	for (int i=1; i<4; i++) {
		tile y=rotate(x, i);
		if (y==x) r++;
	}
	return r;
}

tile get_face(const tile &u, const tile &d, int x, int y) {
	return normalize({u[x], u[y], d[3-y], d[3-x]});
}

//use id to speed up
long id(const tile &x) {
	return x[0]*1000000000L + x[1]*1000000L + x[2]*1000L + x[3];
}

long get_face_id(const tile &u, const tile &d, int x, int y) {
	long z = id({u[x], u[y], d[3-y], d[3-x]});
	long r = z;
	for (int i=0; i<3; i++) {
		z = z/1000L + z%1000L * 1000000000L;
		if (z<r) r = z;
	}
	return r;
}

long solve() {
	map<long,long> ct;
	map<long,long> mi;
	for (int i=0; i<n; i++) {
		a[i] = normalize(a[i]);
		d[i] = id(a[i]);
		ct[d[i]]++;
		mi[d[i]] = mirror(a[i]);
	}
	long ans = 0;
	for (int i=0; i<n; i++) {
		ct[d[i]]--;
		for (int j=i+1; j<n; j++) {
			ct[d[j]]--;
			for (int k=0; k<4; k++) {
				tile d=a[i], u=rotate(a[j], k);
				//tile f[4];
				long g[4];
				long r = 1;
				for (int t=0; t<4; t++) {
					//f[t] = get_face(u, d, t, (t+3)%4);
					//g[t] = id(f[t]);
					g[t] = get_face_id(u, d, t, (t+3)%4);
					r *= mi[g[t]] * ct[g[t]]--;
				}
				//printf("* %d %d %d: %ld\n", i, j, k, r);
				ans += r;
				for (int t=0; t<4; t++) ct[g[t]]++;
			}
			ct[d[j]]++;
		}
		ct[d[i]]++;
	}
	return ans/3;
}

void output(long ans) {
	printf("%ld\n", ans);
}

void cleanup() {
}

int main() {
	//int ca; scanf("%d", &ca);
	while (input()) {
		init();
		output(solve());
		cleanup();
		//break;
	}
}





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

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef long double ld;

const ll mod = (ll)1e9 + 7;
const ll mxN = 200200;

string red(string s) {
	stack<char> st;
	for(auto i: s)
		if(i=='(')
			st.push('(');
		else if(i==')' && (st.size()==0 || st.top()==')'))
			st.push(')');
		else
			st.pop();
	string ans="";
	while(st.size())
		ans+=st.top(),st.pop();
	reverse(all(ans));
	return ans;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(20);
	cout << fixed;
	
	ll a,b,c;
	cin>>a>>b>>c;
	cout<<(c/a)*b;


}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long i64;

#define BIG_PRIME 1000000007
#define remainder(x) ((x) % BIG_PRIME)

int M1, D1, M2, D2;

void Solve()
{
	if (M1 == M2) puts("0");
	else puts("1");
}

void Init()
{
	cin >> M1 >> D1 >> M2 >> D2;
}

void Clean(){}
int main(){ Init(); Solve(); Clean(); return 0; }


Measured memory_bytes: 888
h,w = map(int,input().split())
ls = [list(input()) for _ in range(h)]
num = []
di = [0]*w
for i in range(h):
    if "#" not in ls[i]:
        num.append(i)
    for j in range(w):
        if ls[i][j] == "#":
            di[j] += 1
num = sorted(num,reverse=True)
for k in range(h-1,-1,-1):
    if k in num:
        ls.pop(k)
        continue
    for l in range(w-1,-1,-1):
        if di[l] == 0:
            if l != 0 and l != w-1:
                ls[k] = ls[k][:l] + ls[k][l+1:]
            elif l == 0:
                ls[k] = ls[k][1:]
            else:
                ls[k] = ls[k][:w-1]
for p in range(h-len(num)):
    print("".join(ls[p]))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  int N; cin >> N;
  vector<string> A(N);
  vector<int> B(N);
  map<string, int> m{};
  for (auto& a : A) {
    cin >> a;
    ++m[a];
  }
  for (int i = 0; i < N; ++i) {
    B[i] = m[A[i]];
  }
  auto cnt = *boost::max_element(B);
  set<string> res{};
  for (int i = 0; i < N; ++i) {
    if (B[i] == cnt) {
      res.emplace(A[i]);
    }
  }
  vector<string> ans(res.begin(), res.end());
  for (const auto& s : ans) {
    cout << s << CRLF;
  }
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 37120
#include <bits/stdc++.h>
#define lli long long int
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(lli i=0, i##_len=(lli)(n); i<i##_len; i++)
#define repf(i, n) for(lli i=1, i##_len=(lli)(n+1); i<i##_len; i++)
#define per(i, n) for(lli i=((lli)(n))-1; i>=0; i--)
#define perf(i, n) for(lli i=((lli)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
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; }
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    lli n, q;
    cin >> n >> q;
    vvi t(n, vi(0, 0));
    vi pc(n, INFLL); pc[0] = -1;
    vi cnt(n, 0);

    rep(i, n-1){
        lli a, b;
        cin >> a >> b;
        a--; b--;
        t[a].push_back(b);
        t[b].push_back(a);
    }

    queue<lli> que;
    vi order;
    que.push(0);
    while(!que.empty()){
        lli node = que.front();
        que.pop();
        order.push_back(node);
        for(auto p: t[node]){
            if(pc[p] == INFLL){
                pc[p] = node;
                que.push(p);
            }
        }
    }

    rep(i, q){
        lli p, x;
        cin >> p >> x;
        p--;
        cnt[p] += x;
    }

    repf(i, n-1) cnt[order[i]] += cnt[pc[order[i]]];
    rep(i, n){ cout << cnt[i] << ((i == n-1) ? endl : " "); }
    return 0;
}

Measured memory_bytes: 21232
package main

import (
	"fmt"
)

const n = 7

var (
	seq = []int{}
	flg bool
)

func dfs(left, i int, str string) {
	if i == len(seq) {
		if left == 0 && !flg {
			fmt.Printf("%s=%d\n", str, n)
			flg = true
		}
		return
	}
	for j := range make([]struct{}, 2) {
		if j == 1 || i != 0 {
			tmp := ""
			if i != 0 {
				tmp = [...]string{"-", "+"}[j]
			}
			tmp += string(seq[i] + '0')
			dfs(left-seq[i]*[...]int{-1, 1}[j], i+1, str+tmp)
		}
	}
}

func main() {
	var abcd string
	fmt.Scan(&abcd)

	for _, c := range abcd {
		seq = append(seq, int(c)-'0')
	}
	dfs(n, 0, "")
}


Measured memory_bytes: 512
import copy
from collections import deque

n , m = map(int,input().split())
route = [[] for i in range(n+1)]
nuku = []
for i in range(m):
    a , b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
    nuku.append([a,b])
ans = 0
for a , b in nuku:
    kari = copy.deepcopy(route)
    kari[a].remove(b)
    kari[b].remove(a)
    d = deque()
    d.append(1)
    tansaku = [True for i in range(n+1)]
    cou = 0
    tansaku[1] = False
    while d:
        cou += 1
        now = d.popleft()
        for k in kari[now]:
            if tansaku[k]:
                tansaku[k] = False
                d.append(k)
    if cou != n:
        ans += 1
print(ans)

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

using namespace std;

#define int long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fr(i,j,k) for(i = j; i < (k); i++)
#define all(x) x.begin(), x.end()
#define el '\n'
#define remax(a,b) a = max(a, b)
#define remin(a,b) a = min(a, b)
#define sz(x) int32_t(x.size())

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
// --------------------------------------------------------------------

const pii dxy[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
const int mod = 1e9 + 7;
const int inf = 2e18;
const ld eps = 1e-9;
const int NN = 1e5 + 2;


void solve() {
      int i = 0, j = 0, k = 0, n = 0, m = 0; 
      cin>>k>>n;
      fr(i, 0, n) {
            cin>>j;
            m += j;
      }
      if(m > k) cout << -1;
      else cout << (k - m);
}

int32_t main() {
      ios::sync_with_stdio(false); cin.tie(0); 
      int T = 1; 
      // cin >> T;
      for(int tc = 1; tc <= T; tc++) {
            solve();
       }

      return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>

int main()
{
	int p[19], i = 0, j = 1, n, a = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &p[i]);
	}
	for (j = 1; j < n - 1; j++)
	{
		if (((p[j - 1] < p[j]) && (p[j] < p[j + 1])) || ((p[j - 1] > p[j])&&(p[j] > p[j + 1])))
		{
			a = a + 1;
		}
	}
	printf("%d", a);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

ll mygcd(ll a, ll b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return mygcd(b, a % b);
    }
}
ll mylcm(ll a, ll b)
{
    return a * b / mygcd(a, b);
}

signed main()
{
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    ll l = n * m / mygcd(n, m);
    ll a = mylcm(l / n, l / m);
    rep(i, l / a)
    {
        //        cout << i * l / n << " " << i * l / m << endl;
        if (s[i * l / m] != t[i * l / n])
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << l << endl;
    return 0;
}

Measured memory_bytes: 3764
#include <iostream>

using namespace std;

int main(void)
{
    int n;
    int A[200002];
    bool B[1000002]={0,};
    bool check[1000002]={0,};
    
    cin >> n;
    for(int i=1 ; i<=n ; i++)
    {
        cin >> A[i];
        if(check[A[i]] == false) check[A[i]]=true;
        else B[A[i]] = true;
        if(B[A[i]] != true)
        for(int j=2 ; j<= 1000002/A[i] ; j++)
            B[j*A[i]] = true;
        
    }
    int cnt=0;
    for(int i=1 ; i<=n ; i++)
        if(B[A[i]] == false) cnt++;
        
    cout << cnt;
    
    return 0;
}

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

int main() {
	int a;
  cin >> a;
  if (a % 2 == 0){
    cout << a/2 * a/2 << endl;
  }else if(a%2 != 0){    
    cout <<  (a/2)*(a/2 + 1) << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> H(N);
    for(int i = 0; i < N; i++ ) {
	cin >> H[i];
    }
    int count = 0;
    for(int i = N; i > 0; i--) {
	int max = 0;
	for(int j = 0; j < i; j++) {
	    if(max < H[j]) max = H[j];
	}
	if(max <= H[i]) count++;
    }
    count++;
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
// AOJ 2175: Whist
// 2017.11.5 bal4u@uu

#include <stdio.h>

char trump;
int c[4][13][2];
char tr['Z'];

int main()
{
	int i, j, suit, rank, leader, max, winner;
	char buf[5], score[2];

	tr['A'] = 14, tr['T'] = 10, tr['J'] = 11, tr['Q'] = 12, tr['K'] = 13;
	for (i = 2; i <= 9; i++) tr['0'+i] = i;

	while (scanf("%s", buf) && *buf != '#') {
		trump = *buf;
		for (i = 0; i < 4; i++) for (j = 0; j < 13; j++) {
			scanf("%s", buf);
			c[i][j][0] = tr[*buf], c[i][j][1] = *(buf+1);
		}

		score[0] = score[1] = 0;
		leader = c[0][0][1];
		for (j = 0; j < 13; j++) {
			winner = max = 0;
			for (i = 0; i < 4; i++) {
				rank = c[i][j][0], suit = c[i][j][1];
				if (suit != trump && suit != leader) continue;
				if (suit == trump) rank += 100;
				if (max < rank) max = rank, winner = i;
			}
			score[winner & 1]++;
			leader = c[winner][j+1][1];
		}
		if (score[0] > score[1]) printf("NS %d\n", score[0]-6);
		else                     printf("EW %d\n", score[1]-6);
	}
	return 0;
}

Measured memory_bytes: 1752
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char ip1,ip2,ip3;
	int sum=700;
	cin>>ip1>>ip2>>ip3;
	if (ip1=='o')
	 sum=sum+100;
	if (ip2=='o')
	sum=sum+100;
	if (ip3=='o')
	sum=sum+100;
	cout <<sum;
} 

Measured memory_bytes: 256
from itertools import accumulate as ac
from collections import Counter as co
n=int(input())
a=list(map(int,input().split()))
b=[0]+a
b=list(ac(b))
c=co(b)
cc=c.most_common()
cnt=0
for i in cc:
    if i[1]>1:
        cnt+=(i[1]*(i[1]-1)//2)
print(cnt)

Measured memory_bytes: 48508
//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N,Q; cin>>N>>Q;
    set<pair<ll,ll>> top;
    set<pair<ll,ll>> left;
    
    top.insert({N - 1,N});
    left.insert({N,N});
    
    while(Q--)
    {
        ll t; cin>>t;
        if(t == 1) //top
        {
            ll y; cin>>y;
            auto it = left.lower_bound({y,-1});
            ll x = it->second;
            //cout<<"For y= "<<y<<", x is "<<x - 1<<endl;
            if(x - 1 > 0)
            {
                
                top.insert({x - 1,y});
            }
        }
        else
        {
            ll x; cin>>x;
            auto it = top.lower_bound({x,-1});
            ll y = it->second;
            //cout<<"For x= "<<x<<", y is "<<y - 1<<endl;
            if(y - 1 > 0)
            {
                left.insert({y - 1,x});
            }
        }
    }
    
    //
    ll tot = N*N;
    ll unfilled = (2*N - 1) - (left.size() + top.size());
    tot -= unfilled;
    
    //cout<<"For top"<<endl;
    for(auto it: top)
    {
        //cout<<it.second<<" "<<it.first<<endl;
        tot -= (it.first);
    }
    
    //cout<<"For left"<<endl;
    for(auto it: left)
    {
        //cout<<it.second<<" "<<it.first<<endl;
        tot -= (it.first);
    }
    
    cout<<tot<<endl;
}
    

Measured memory_bytes: 16140