akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define stop char nyaa;cin>>nyaa;


void solve() {
	int n;
	cin >> n;
	vector<int> cnt(1 << 22), a(1 << 22);
	rep(i, n) {
		int k;
		cin >> k;
		int bit = 0;
		rep(i, k) {
			int x;
			cin >> x;
			bit += (1 << (x - 1));
		}
		++cnt[bit];
		a[bit] = bit;
	}
	rep(j, 22) {
		rep(i, 1 << 22) {
			if (i&(1 << j)) {
				cnt[i ^ (1 << j)] += cnt[i];
				a[i ^ (1 << j)] |= a[i];
			}
		}
	}
	int ans = 0;
	vector<int> b(1 << 22);
	rep(i, 1 << 22)rep(j, 22) {
		if (i&(1 << j))b[i]++;
	}
	rep(i, 1 << 22) {
		if (cnt[i] < 3)continue;
		ans = max(ans,b[i]*b[a[i]]);
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(6);
	solve();
	//stop
		return 0;
}


Measured memory_bytes: 51924
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  rep(i, n) cin >> h[i];
  vector<int> dp(n + 1);
  dp[1] = abs(h[0] - h[1]);
  for(int i = 2; i < n; ++i) {
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
  }
  cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <functional>
#include <queue>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;

using ll          = long long;
using db          = double;
using ld          = long double;
using uint        = unsigned int;
using ull         = unsigned long long;

using pii         = pair<int, int>;
using pll         = pair<ll, ll>;
using tiii        = tuple<int, int, int>;

#define mod7        1000000007
#define mod9        1000000009

#define forall(v)   v.begin(), v.end()
#define prec(x)     setprecision(x) << fixed

/* [💭] [💡] [🎈] */

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1), val(n + 1);

    for (int i = 0; i < n - 1 + m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    int rt;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            rt = i;
            break;
        }
    }

    queue<int> q;
    q.emplace(rt);

    while (q.size()) {
        int c = q.front();
        q.pop();

        int minin = 999999;

        for (int x : g[c]) {
            if (minin > in[x]) {
                minin = in[x];
            }
        }

        for (int x : g[c]) {
            if (in[x] == minin && !val[x]) {
                val[x] = c;
                q.emplace(x);
            }
            in[x]--;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << val[i] << '\n';
    }

    return 0;
}

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

int N,A,B,C;
int l[10];

int dfs(int ind,int a,int b,int c){
  if (ind == N){
    if (min({a,b,c})>0) return abs(a-A)+abs(b-B)+abs(c-C)-30;
    else return 100000000;
  }
  int cond0 = dfs(ind+1,a,b,c);
  int cond1 = dfs(ind+1,a+l[ind],b,c)+10;
  int cond2 = dfs(ind+1,a,b+l[ind],c)+10;
  int cond3 = dfs(ind+1,a,b,c+l[ind])+10;

  return min({cond0,cond1,cond2,cond3});
}

int main(){
  cin >> N >> A >> B >> C;
  for (int i=0;i<N;i++) cin >> l[i];
  cout << dfs(0,0,0,0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a,b,c,d,e,f;
scanf("%d %d %d %d\n",&a,&b,&c,&d);
e=a+b+c+d;
scanf("%d %d %d %d",&a,&b,&c,&d);
f=a+b+c+d;
if(e>=f){
printf("%d\n",e);
}
else{
printf("%d\n",f);
}
return 0;
}


Measured memory_bytes: 2148
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int w;
	cin>>w;
	int r=1;
	vector<char>ans;
	while(r<w)r*=3;
	while(r>0){
		if(abs(w)>r/2){
			if(w<0){
				ans.push_back('-');
				w+=r;
			}else{
				ans.push_back('+');
				w-=r;
			}
		}else{
			ans.push_back('0');
		}
		r/=3;
	}
	for(int i=0;i<ans.size();i++){
		if(i==0&&ans[i]=='0')continue;
		cout<<ans[i];
	}
	cout<<endl;
}

Measured memory_bytes: 3144
//Dragon_warrior7(IITK)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define maxin(v) *max_element(v.begin(), v.end())
#define minin(v) *min_element(v.begin(), v.end())
#define sumall(vect) accumulate(vect.begin(), vect.end(), 0)
#define count(x, vect) count(vect.begin(), vect.end(), x)
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 100000000000000000
#define deb(x) cout << #x << " " << x << "\n"
#define pll pair<ll, ll> 
#define vll vector<ll> 
#define rub cout << "------------------------------------\n"
//#define min(a, b, c) min(a, min(b, c))
//#define max(a, b, c) max(a, max(b, c))
void read(vector<ll> &v)
{
	for (int i = 0; i < v.size(); i++)
		cin >> v[i];
}

void print(vector<ll> v)
{
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
}
ll n,m,a,b,temp;
string str;
set<ll> s;
vll v;
ll t[4*100000];
void build(ll a[],int v,int tl,int tr)
{
    if(tl==tr)
    t[v]=a[tl];
    else
    {
        int tm=(tl+tr)/2;
        build(a,2*v,tl,tm);
        build(a,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[v*2+1]);
    }
}
ll query(int v,int tl,int tr,int l,int r)
{
    if(l>r)
    return -llmax;
    if(tl==l && r==tr)
    return t[v];
    int tm=(tl+tr)/2;
    return max(query(v*2, tl, tm, l, min(r, tm)),query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	ll c;
	cin>>c;
	vector<pll> vp(n);
	for(int i=0;i<n;i++)
	{
	  cin>>vp[i].se>>vp[i].fi;
	}
	ll ans=0;
	ll pr[n];
	pr[0]=vp[0].fi-vp[0].se;
	for(int i=1;i<n;i++)
	{
	    pr[i]=pr[i-1]+vp[i].fi-(vp[i].se-vp[i-1].se);
	}
	ll suffix[n];
	suffix[n-1]=vp[n-1].fi-(c-vp[n-1].se);
	for(int i=n-2;i>=0;i--)
	{
	    suffix[i]=vp[i].fi-(vp[i+1].se-vp[i].se)+suffix[i+1];
	}
	build(suffix,1,0,n-1);
	for(int i=0;i<n;i++)
	{
	    ans=max(ans,pr[i]);
	    ans=max(ans,suffix[i]);
	    ans=max(ans,pr[i]-vp[i].se+query(1,0,n-1,i+1,n-1));
	}
	build(pr,1,0,n-1);
	for(int i=n-1;i>0;i--)
	{
	  ans=max(ans,suffix[i]-(c-vp[i].se)+query(1,0,n-1,0,i-1));  
	}
	cout<<ans;
}

Measured memory_bytes: 5504
from collections import deque
lista=deque([3,5,7])
count=0
lim=int(input())
while True:
    t=lista.popleft()
    if t>lim:
        break
    c=list(str(t))
    if c.count("3") and c.count("5") and c.count("7"):
        count+=1
    lista.append(10*t+3)
    lista.append(10*t+5)
    lista.append(10*t+7)
print(count)

Measured memory_bytes: 6132
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N],cnt[N],p[N],vis[N],las;
int main(){
	//freopen("special_01","r",stdin);
	//freopen("qwq","w",stdout);
	n=read();
	for(int i=1;i<=n;++i){
		p[i]=i;
		a[i]=read();
		//cerr<<" "<<i<<" "<<a[i]<<endl;
		++cnt[a[i]];
	}
	if(n==2)return !printf("-1\n");
	//cerr<<" "<<a[91]<<endl;
	for(int i=1;i<=n;++i){
		if(a[las]==p[i]){
			swap(p[i],p[i+1]);
		}
		int u=p[i];
		/*if(u==91){
			cerr<<" !! "<<p[i+1]<<" "<<a[u]<<" !! "<<endl;
		}*/
		if(vis[a[u]]){
			if(i==n-2&&a[p[i+1]]==p[i+2]&&a[p[i+2]]==p[i+1]){
				if(p[i+1]==a[las]){
					swap(p[i],p[i+2]);
					swap(p[i+1],p[i+2]);
				}
				else{
					swap(p[i],p[i+1]);
				}
			}
		}
		else if(cnt[a[u]]==n-i){
		//	cerr<<" !!!! "<<u<<" "<<a[u]<<" ???? "<<endl;
			for(int j=i+1;j<=n;++j){
				if(p[j]==a[u]){
					for(int k=j;k>i;--k){
						swap(p[k],p[k-1]);
					}
					break;
				}
			}
		}
		printf("%d ",p[i]);
		vis[p[i]]=1;
		--cnt[a[p[i]]];
		las=p[i];
		if(i>=n-20)sort(p+i+1,p+n+1);
	}
	return 0;
}



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

using namespace std;

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

  int N, K;
  cin >> N >> K;

  double prob = 0.;
  double rate = 1.;
  int i = N;
  for (int thre = K; thre >= 1; thre = (thre + 1) / 2) {
    int acc = 0;
    for (; thre <= i && i <= N; --i) {
      ++acc;
    }
    prob += acc * rate;
    rate /= 2;
    if (thre == 1) break;
  }
  cout << setprecision(15) << fixed << (prob / N) << endl;
}


Measured memory_bytes: 256
def d_wall(H, W, C, A):
    # cost[i][j]には最終的に数字iからjに移行するための最小コストが格納される
    cost = [x[:] for x in C]

    # ワーシャルフロイド法で最小コストを計算
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    ans = 0
    # 壁の各数字ごとにコストの値を参照、和を取る
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += cost[A[i][j]][1]  # 壁の数字から1へ移行するための最小コスト
    return ans

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

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

#include<functional>
#include<memory>
template<typename T> class SegmentTree {
 public:
  explicit SegmentTree(int SIZE, const T& NIL = 0,  const std::function<T(T, T)>& MERGE = std::plus<T>()) : SIZE(SIZE), NIL(NIL), MERGE(MERGE), ROOT(std::make_unique<Node>()) {}
  void update(int a, int b, const T& v) {update(a, b + 1, v, ROOT, 0, SIZE);}
  T find(int a, int b) {return find(a, b + 1, ROOT, 0, SIZE);}
 private:
  struct Node {
    T lazy;
    T value;
    std::unique_ptr<Node> l_child, r_child;
  };
  inline void push(const std::unique_ptr<Node>& n) {
    if(not n->l_child) n->l_child = std::make_unique<Node>();
    if(not n->r_child) n->r_child = std::make_unique<Node>();
    if(n->lazy) {
      n->l_child->lazy += n->lazy;
      n->r_child->lazy += n->lazy;
      n->value += n->lazy;
      n->lazy = NIL;
    }
  }
  void update(int a, int b, const T& v, const std::unique_ptr<Node>& n, int l, int r) {
    push(n);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {n->lazy += v; push(n); return;}
    auto m = (l + r) / 2;
    update(a, b, v, n->l_child, l, m);
    update(a, b, v, n->r_child, m, r);
    n->value = MERGE(n->l_child->value, n->r_child->value);
  }
  T find(int a, int b, const std::unique_ptr<Node>& n, int l, int r) {
    push(n);
    if(b <= l || r <= a) return NIL;
    if(a <= l && r <= b) return n->value;
    auto m = (l + r) / 2;
    auto vl = find(a, b, n->l_child, l, m);
    auto vr = find(a, b, n->r_child, m, r);
    return MERGE(vl, vr);
  }
  const int SIZE;
  const T NIL;
  const std::function<T(T, T)> MERGE;
  const std::unique_ptr<Node> ROOT;
};

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

using LL = long long;

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

  struct Query {LL X, D, L;};
  vector<Query> query(Q);
  for(auto& q: query) cin >> q.X >> q.D >> q.L;
  reverse(begin(query), end(query));

  SegmentTree<LL> X(N + 1), Y(N + 1);

  auto get = [N](auto& S, auto X) {
    int l = 0, h = N + 1;
    while(l + 1 < h) {
      auto m = (l + h) / 2;
      if(m + S.find(m, m) <= X) l = m;
      else                      h = m;
    }
    return l;
  };

  for(auto q: query) {
    if(q.D == 1) Y.update(0, get(X,q.X), -2*q.L);
    else         X.update(1+get(Y,q.X), N, 2*q.L);
  }
  for(auto i = 1 ; i <= N; ++i) cout << (X.find(i,i) - Y.find(i, i)) / 2 << endl;
}

Measured memory_bytes: 82628
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
li1 = [0]*(n)
li2 = [0]*n
for i in range(n):
    if a[i]+i<n:
        li1[a[i]+i]+=1 
    if 0<=i-a[i]<n:
        li2[-a[i]+i]+=1
for i in range(n):
    ans+=li1[i]*li2[i]
print(ans)

Measured memory_bytes: 93252
#include <iostream>
#include <stdio.h>
#include <algorithm>
//#include <string>
#include <math.h>
//#include <vector>

using namespace std;


long int gcd(long int a, long int b){
  long int r;

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



int main() {
  int N, K;
  long int A[100000];
  long int tmp;
  long int max;
  long int gc;

  int i;
  
  cin >> N >> K;

  for(i=0;i<N;i++){
    cin >> A[i];
  }

  gc = A[0];
  max = A[0];
  for(i=1;i<N;i++){
    tmp = A[i];
    if(tmp > max) max = tmp;
    gc = gcd(gc,tmp);
  }

  if(K>max) cout << "IMPOSSIBLE";
  else if(K%gc==0){
    cout << "POSSIBLE";
  }else{
    cout << "IMPOSSIBLE";
  }
 
  return 0;
}


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

using namespace std;

int main(){
    int m,d;
    cin>>m>>d;
    int ans=0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 2; j <=9 ; ++j) {
            for (int k = 2; k <= 9; ++k) {
                if(j*10+k<=d){
                    if(i==j*k)++ans;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

ll evaluation(vector<ll>& C, vector<vector<ll>>& S, ll t, ll day, vector<ll>& last) {
  ll score = 0;
  score += S.at(day).at(t);
  for (ll j = 0; j < 26; ++j) {
    if (j == t) {
      continue;
    }
    score -= (day + 1 - last.at(j)) * C.at(j);
  }
  return score;
}

int main() {
  //-----------input-------------
  ll D;
  cin >> D;
  vector<ll> C(26), T(D);
  vector<vector<ll>> S(D, vector<ll>(26));
  for (ll i = 0; i < 26; ++i) {
    cin >> C.at(i);
  }
  for (ll i = 0; i < D; ++i) {
    for (ll j = 0; j < 26; ++j) {
      cin >> S.at(i).at(j);
    }
  }
  //--------------------------------------
  vector<ll> last(26, 0);
  for (ll day = 0; day < D; ++day) {
    ll max_contest = 0;
    ll max_score = -INF;
    for (ll contest = 0; contest < 26; ++contest) {
      ll temp_score = evaluation(C, S, contest, day, last);
      if (temp_score > max_score) {
        max_score = temp_score;
        max_contest = contest + 1;
      }
    }
    last.at(max_contest - 1) = day;
    T.at(day) = max_contest;
  }

  for (ll i = 0; i < D; ++i) {
    cout << T.at(i) << "\n";
  }

  // vector<ll> ans = evaluation(C, S, T);
  // for (ll i = 0; i < ans.size(); ++i) {
  //   cout << ans.at(i) << "\n";
  // }
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
#define unsort(vec); sort(vec);reverse(vec);
#define int long long
long long ans=1;

int gcd(int x,int y){
	if(y==0) return x;
	else return gcd(y,x%y);
}

int lcm(int x,int y){
	return x/gcd(x,y)*y;
}
signed main(){
	int n,cnt=0;
	cin>>n;
	int s[26];
	for(int i=0;i<26;i++){
		s[i]=0;
	}
	for(int i=0;i<n;i++){
		char a;
		cin>>a;
		int z=a-'a';
		s[z]++;
	}
	for(int i=0;i<26;i++){
		ans*=s[i]+1;
		ans%=1000000007;
	}
	cout<<(ans-1)<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int h, w;
char s[22][22];
int shortest(int st, int gl)
{
    int v[410] = {};
    int q[410] = {};
    int head = 0, tail = 0;

    q[tail++] = st;
    v[st] = 1;

    while (v[gl] == 0)
    {
        int now = q[head++];
        int next;
        for (int j = 0; j < 4; j++)
        {
            next = now;
            switch (j)
            {
            case 0:
                if (next >= w)
                {
                    next -= w;
                }
                break;
            case 1:
                if (next % w != w - 1)
                {
                    next += 1;
                }
                break;
            case 2:
                if (next < w * (h - 1))
                {
                    next += w;
                }
                break;
            case 3:
                if (next % w != 0)
                {
                    next -= 1;
                }
                break;
            default:
                break;
            }
            if (next == now || next < 0 || next >= h * w)
            {
                continue;
            }
            if (s[next / w][next % w] == '.' && v[next] == 0)
            {
                q[tail++] = next;
                v[next] = v[now] + 1;
            }
        }
    }
    //printf("%d,%d  %d\n", st, gl, v[gl] - 1);
    return v[gl] - 1;
}
int main()
{
    int ans = 0;
    int t;
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; i++)
    {
        scanf("%s", &s[i]);
    }
    for (int st = 0; st < h * w; st++)
    {
        //puts("a");
        if (s[st / w][st % w] == '#')
        {
            continue;
        }
        for (int gl = st + 1; gl < h * w; gl++)
        {
            if (s[gl / w][gl % w] == '#')
            {
                continue;
            }
            t = shortest(st, gl);
            ans = (t > ans) ? t : ans;
        }
        //printf("%d %d\n", st, ans);
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 128
package main

import "fmt"

func main ()  {
  a := [3]int{}
  b := true
  for i := range a {
    fmt.Scan(&a[i])
  }

  for i := range a {
    if len(a) <= i + 1 {break}
    b = b && (a[i] < a[i+1])
  }

  if b {
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}


Measured memory_bytes: 1120
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
yet = [a[i]!=b[i] for i in range(n)]

prev2 = b[0]
prev = b[1]
i = 2
count = n - sum(yet)
ans = 0
while count<n:
    current = b[i]
    if prev2==prev and (yet[i-1] or yet[i-2]):
        ans = -1
        break
    if  prev==current and (yet[i-1] or yet[i]):
        ans = -1
        break
        
    if yet[i-1] and prev2<prev>current:
        if a[i-1]>max(prev2, current):
            num = (prev-a[i-1])//(prev2+current)
            prev -= num*(prev2+current)
            b[i-1] = prev
            ans += num
            if prev!=a[i-1]:
                ans = -1
                break
            yet[i-1] = False
            count += 1
        else:
            if prev<=current+prev2:
                ans = -1
                break
            num = (prev-max(prev2, current))//(prev2+current) + int((prev-max(prev2, current))%(prev2+current)>0)
            prev -= num*(prev2+current)
            b[i-1] = prev
            if prev==a[i-1]:
                yet[i-1] = False
                count += 1
            elif prev<=0:
                ans = -1
                break
            ans += num
            
    prev2, prev = prev, current
    i += 1
    i %= n
print(ans)


Measured memory_bytes: 108868
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define rep(i, j, k) for(int i=(j);i<(k);++i)
#define repi(i, j, k) for(int i=(j);i<=(k);++i)
#define per(i, j, k) for(int i=(j);i>(k);--i)
#define peri(i, j, k) for(int i=(j);i>=(k);--i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).begin(),(x).end(), greater<int>()
#define sz(x) ((int)(x).size())
#define endl "\n"
#define INF 0x20202020
#define EPS 1e-9
#define PI 3.1415926535897932384626
#define MOD 1000000007
typedef long long ll;
typedef long double ld;

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> si;

class A {
public:
    void solve(std::istream &cin, std::ostream &cout) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (abs(a - c) <= d || (abs(a - b) <= d && (abs(b - c) <= d))) {
            cout << "Yes" << endl;
            return;
        }
        cout << "No" << endl;
    }
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    A solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
    int k;
    char s[101];
    scanf("%d",&k);
    scanf("%s",s);
    if(strlen(s)<=k)
    {
        printf("%s",s);
    }
    else
    {
        for(int i=0;i<k;i++)
        {
            printf("%c",s[i]);
        }
        printf("...");
    }
    
}

Measured memory_bytes: 1692
#include<iostream>
#include<cstdio>

using namespace std;

int n;
int a[100100];
int n4,n2,n1;
bool t=true;

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(a[i]%4==0) n4++;
		if(a[i]%4==2) n2++;
		if(a[i]==0) t=false;
	}
	
	n1=n-n4-n2;
	
	if(n1-1>n4) t=false;
	if(n4*2==n1&&n4!=0&&n4!=1) t=false;
	if(n1-1==n4&&n2>0) t=false;
	
	if(t)
		cout<<"Yes";
	else
		cout<<"No";
		
	return 0; 
} 

Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;

int main() {
	ll a,b;
  cin>>a>>b;
  cout<<a-b+1<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define ppll pair<ll, pll>
#define pii pair<int, int> 
#define mod 1000000007
ll power(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
ll ncr(ll n,ll k){
    if(k==0||k==n) return 1ll;
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro%mod);
}
vector<int> prime;
void seive(){
    vector<bool > isprime(1000001,true);
    for(int i=2;i*i<=1000000;i++){
        if(isprime[i]){
            for(int j=i*i;j<=1000000;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string str;
    int len;
    cin>>len;
    cin>>str;
    map<char,ll> m;
    for(int i=0;i<str.size();i++){
        m[str[i]]++;
    } 
    ll ans=1;
    for(auto itr:m){
        ans=(ans*(itr.se+1))%mod;
    }
    ans--;
    ans=(ans+mod)%mod;
    cout<<ans;
    return 0;
}


Measured memory_bytes: 512
a, b, c, d = gets.split.map(&:to_i)

tmp1c  = b / c
tmp1d  = b / d
tmp1cd = b / c.lcm(d)
tmp1   = b - (tmp1c + tmp1d - tmp1cd)

tmp2c  = (a - 1) / c
tmp2d  = (a - 1) / d
tmp2cd = (a - 1) / c.lcm(d)
tmp2   = a - 1 - (tmp2c + tmp2d - tmp2cd)

puts tmp1 - tmp2


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

signed main(void)
{
	string s;
	set<char> st;
	cin >> s;

	rep(i, s.size())
	{
		st.insert(s[i]);
	}
	if (st.size() == s.size())
		cout << "yes" << endl;
	else
		cout << "no" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.begin(), a.end(), greater<int>()
#define ROT(a) a.begin(), a.begin() + 1, a.end()
#define RROT(a) a.begin(), a.end() - 1, a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9 + 7;
const int MAX = 10000000;
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b)
{
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
//cout << 'H' << endl;
/*--------------------------------------------*/

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

    ll a;
    string s;
    int b;
    cin >> a >> s;

    b = (s[0] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');

    ll c = a * b;


    string ans = to_string(c);

    if (sz(ans) == 1 || sz(ans) == 2) {
        cout << 0 << endl;
        return 0;
    }

    rep(i, sz(ans) - 2)
    {
        cout << ans[i];
    }

    cout << endl;
}


Measured memory_bytes: 3720
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

struct edge{int to,cost;};

vector<ll> dijkstra(int n,vector<vector<edge> > G,int s){
  priority_queue<pii,vector<pii>,greater<pii> > que;
  vector<ll> dist(n,inf);
  dist[s]=0;
  que.push(pii(0,s));
  while(!que.empty()){
    int c,v;
    tie(c,v)=que.top();
    que.pop();
    if(dist[v]<c) continue;
    for(int i=0;i<G[v].size();i++){
      edge e=G[v][i];
      int nc=e.cost;
      int nv=e.to;
      if(dist[nv]>dist[v]+nc){
        dist[nv]=dist[v]+nc;
        que.push(pii(dist[nv],nv));
      }
    }
  }
  return dist;
}

int main(){
  int n,m,s; cin >> n >> m >> s;
  vector<vector<edge> > G(n,vector<edge>(0));
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    G[a].push_back({b,c});
  }
  vector<ll> dist=dijkstra(n,G,s);
  rep(i,n){
    if(dist[i]!=inf) cout << dist[i] << endl;
    else cout << "INF" << endl;
  }
  
}


Measured memory_bytes: 20672
/*C - Walk on Multiplication Table*/

#include <bits/stdc++.h>

using namespace std;
using Long = long long;

int main(){
	
	Long ans = LLONG_MAX;
	Long divisor;
	Long numero;
	Long raiz;
	Long aux;

	cin >> numero;

	raiz = sqrt(numero);

	for (Long i = 1ll; i <= raiz; ++i)
	{
		if(numero % i == 0){

			divisor = numero / i;
			aux = (divisor + i) - 2ll;
			ans = min(ans, aux);
		}

	}

	cout << ans;

	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    vector<ll> a;
    for (ll i = 0; i < n; i++)
    {
        ll temp;
        cin >> temp;
        a.push_back(temp);
    }

    sort(a.begin(), a.end(), greater<ll>());
    ll x = 0, y = 0;

    for (ll i = 0; i < a.size() - 1; i++)
    {
        if (a[i] == a[i + 1])
        {
            x = a[i];
            a.erase(a.begin() + i);
            a.erase(a.begin() + i);
            break;
        }
    }

    for (ll i = 0; i < a.size(); i++)
    {
        if (a[i] == a[i + 1])
        {
            y = a[i];
            break;
        }
    }

    if (x == 0 || y == 0)
        cout << 0 << endl;
    else
        cout << x * y << endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s << "[";
    for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
    s << "]";
    return s;
}

#define ALL(a) (a).begin(), (a).end()

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

    map<int, int> map;
    vector<int> a(N);
    int target = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (a[i] >= 3200) {
            target++;
            continue;
        }
        for (int j = 1; j <= 8; j++) {
            if (a[i] < 400 * j) {
                map[j]++;
                break;
            }
        }
    }
    if (map.size() <= 1) cout << 1;
    else cout << map.size();

    cout << " ";
    cout << map.size() + target << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int 
#define pb push_back
 
using namespace std;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b;
	cin>>a>>b;
	int c=b;
	int count=0;
	while(b){
		b/=10;
		count++;
	}
	a*=(pow(10,count));
	a+=c;
	int d=sqrt(a);
	if((d*d)==a){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}

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

int main() {

    int N;

    cin >> N;

    int cnt = 0;

    for (int i = 1; i <= N; i++) {
        string s = to_string(i);
        if(s.size() % 2 == 1){
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;

}

Measured memory_bytes: 3720
#include <iostream>
#include <cstdio>
#include <cfloat>
#include <cmath>
#include <random>
#include <algorithm>
#define norm(X) ((X) * (X))
using namespace std;
using ll = long long;
    
struct Point {
    ll x, y;
    ll z;
};

int main() {
    ll n;
    Point e[105];
    double ans = 0;
    ll sx[4] = {};
    ll sy[4] = {};

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> e[i].x >> e[i].y;

        e[i].z = 0;
        if (e[i].y > 0) {
            e[i].z |= 2;
        }
        if (e[i].x > 0) {
            e[i].z |= 1;
        }

        sx[e[i].z] += e[i].x;
        sy[e[i].z] += e[i].y;
    }

    mt19937 rnd(1719);
    ll x, y;

    for (int z = 0; z < 4; z++) {
        
        for (int k = 0; k < 30000; k++) {
            x = sx[z];
            y = sy[z];

            for (int i = 0; i < n; i++) {
                ll zz = 0;
                if (e[i].y > 0) zz |= 2;
                if (e[i].x > 0) zz |= 1;
                e[i].z = (zz == z ? -1 : 1);
            }

            for (int j = 0; j < 300; j++) {
                ll indx = rnd() % n;

                if (e[indx].z != -1) {
                    if (norm(x) + norm(y) < norm(x + e[indx].x) + norm(y + e[indx].y)) {
                        x += e[indx].x;
                        y += e[indx].y;
                        e[indx].z = -1;
                    }
                }
                else {
                    if (norm(x) + norm(y) < norm(x - e[indx].x) + norm(y - e[indx].y)) {
                        x -= e[indx].x;
                        y -= e[indx].y;
                        e[indx].z = 1;
                    }
                }
            }

            ans = max(ans, hypot(x, y));
        }
    }
    
    printf("%.*lf\n", DBL_DIG, ans);

    return 0;
}


Measured memory_bytes: 256
#define ALGORITHM   0
#define CLIMITS     0
#define CMATH       0
#define DEQUE       0
#define LIST        0
#define MAP         0
#define QUEUE       0
#define SET         0

#define DP          0
#define DIRECTIONS  0

#define _GLIBCXX_DEBUG
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#if ALGORITHM
#include <algorithm>
#endif
#if CLIMITS
#include <climits>
#endif
#if CMATH
#include <cmath>
#endif
#if DEQUE
#include <deque>
#endif
#if LIST
#include <list>
#endif
#if MAP
#include <map>
#endif
#if QUEUE
#include <queue>
#endif
#if SET
#include <set>
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;

#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.1415926535897932384626433832795028841971L;
constexpr ll INF9 = (1 << 30);
constexpr ll INF18 = (long long)1e18 + 1;
constexpr ll MOD = (int)1e9 + 7;

#if DP
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 (a>b) { a = b; return 1; } return 0; }
#endif

#if DIRECTIONS
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#endif
//
//
//
//
//
/*追加部分*/



/*main関数*/

int main() {
FASTIO;
    int n;
    ll a[200000];
    ll b[200001];
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i + 1] = b[i] + a[i];
        b[i + 1] %= MOD;
    }
    ll ans = 0;
    for (int i = n - 1; i >= 1; --i) {
        ans += (a[i] * b[i]) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;

return 0;
}

Measured memory_bytes: 6760
INF = 10 ** 20

n, m = map(int, input().split())
c_lst = list(map(int, input().split()))

dp = [INF for _ in range(n + 1)]
dp[0] = 0
for coin in c_lst:
  for price in range(coin, n + 1):
    dp[price] = min(dp[price], dp[price - coin] + 1)

print(dp[n])


Measured memory_bytes: 7640
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
  int n,k;
  cin>>n>>k;
  int a[n];
  int ans1=0,ans2=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(a[i]>0)ans1+=a[i];
  }
  int p=0,m=0;
  for(int i=0;i<k;i++){
    if(a[i]>0)p+=a[i];
    else m-=a[i];
  }
  ans2=min(p,m);
  for(int i=k;i<n;i++){
    if(a[i-k]>0)p-=a[i-k];
    else m+=a[i-k];
    if(a[i]>0)p+=a[i];
    else m-=a[i];
    ans2=min(ans2,min(p,m));
  }
  cout<<ans1-ans2;

  
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll inf=mod*100;
    ll n,num;
    set<ll> s;
    queue<ll> q;
    cin>>n;
    for(ll i=1;i<10;i++){
    	s.insert(i);
    	q.push(i);
    }
    while(!q.empty()){
    	ll m=q.front();
    	if(m%10!=0LL){
    		num=m*10+m%10-1;
    		s.insert(num);
    		if(num<inf)q.push(num);
    	}
    	num=m*10+m%10;
    	s.insert(num);
    	if(num<inf)q.push(num);
    	if(m%10!=9LL){
    		num=m*10+m%10+1;
    		s.insert(num);
    		if(num<inf)q.push(num);
    	}
    	q.pop();
    }
    auto itr=s.begin();
    while(--n)itr++;
    cout<<*itr<<endl;

    return 0;
}


Measured memory_bytes: 79616
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int a, b;
  cin >> a >> b;
  for (int i = 1; i <= 1009; ++i) {
    int res1 = i * 0.08;
    int res2 = i * 0.10;
    if (res1 == a && res2 == b) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    BC = [tuple(map(int, input().split())) for _ in range(M)]
    BC.sort(key=lambda x: x[1], reverse=True)
    D = []
    for b, c in BC:
        D.extend([c] * b)
        if len(D) >= N:
            break
    D = D[:N]
    r = sum(A)
    for a, d in zip(A, D):
        r = max(r, r - a + d)
    print(r)

main()


Measured memory_bytes: 23256
# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x



    def same(self, x, y):
        return self.find(x) == self.find(y)


n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()
# aの各点に通し番号を振る
for i in range(n):
    a[i].append(i)

# 繋ぐ点の候補は上下左右の４つ
# 左右に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

a.sort(key=lambda x:x[1])
# 上下に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

b.sort(key=lambda x:x[2])

uf=UnionFind(n)
ans=0
cnt=0
# クラスカル法
for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)

Measured memory_bytes: 131364
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define mod 1000000007
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f(i,n) for(ll i=0;i<n;i++)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ms(v,n) memset((v),n,sizeof(v));
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define sll set<ll>
#define vll vector<ll>
#define vpll vector<pll>
#define maxi(a,b,c) max(a,max(b,c))
#define maxii(a,b,c,d) max(max(a,b),max(c,d))
#define mini(a,b,c) min(a,min(b,c))
#define md(a,b)  ((a%mod)*(b%mod)+mod)%mod 
#define ad(a,b)  (a%mod+b%mod+mod)%mod
#define nl endl
#define inf 1e18
#define cases ll t;cin>>t;while(t--)
#define BLOCK 500
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
 
using namespace std;

const int N=1e5+5;
ll dp[N];
ll n,m,x,y;
vll g[N];

ll go(ll i)
{
    if(dp[i]!=-1)
        return dp[i];

    if(i>=n)
    return 0;

    dp[i]=0;

    for(auto j:g[i+1])
    {
        dp[i]=max(dp[i],1+go(j-1));
    }
    return dp[i];
}

int32_t main()
{
    fast
   
    cin>>n>>m;
   
    f(i,m)
    {
        cin>>x>>y;
        g[x].pb(y);
    }

    
    ms(dp,-1);
    f(i,n)
    go(i);

    cout<<*max_element(dp, dp+n);        
        

    

    

       
    return 0;
    
}


Measured memory_bytes: 7936
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
using namespace std;
#define MAXSIZE 200
#define MAXL 100
typedef long long int lli;

int main(){
    string s;
    cin >> s;
    cout << s[0] << (s.length() - 2) << s[s.length() - 1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#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>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  string s = std::to_string(n);
  ll l = 0;
  rep(i,s.size()) l += s[i]-'0';
  if(n%l==0) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int sz=1e5+7;
const int mod=1e9+7;
int n;
int T;
int ans;
int cnt;
bool flag;
int b[sz];
int a[sz],r[sz],rr[sz];
int t[sz],rt[sz];
int qp[sz],_qp[sz];
int inv[sz],fac[sz],_fac[sz];
int del[sz],dep[sz];
queue<int>q;
void upd(int &x,int y){
	x=x+y>=mod?x+y-mod:x+y;
}
int qpow(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*x*ret%mod;
	return ret;
}
void find(int x){
	if(dep[x]) flag=0;
	cnt++;
	del[x]=1;
	if(!del[a[x]]) find(a[x]);
	b[a[x]]=x;
}
void init(){
	qp[0]=_qp[0]=1;
	fac[0]=_fac[0]=1;
	inv[1]=fac[1]=_fac[1]=1;
	for(int i=2;i<sz;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[i]=1ll*i*fac[i-1]%mod;
		_fac[i]=1ll*inv[i]*_fac[i-1]%mod;
	}
	for(int i=1;i<sz;i++){
		qp[i]=2ll*qp[i-1]%mod;
		_qp[i]=1ll*inv[2]*_qp[i-1]%mod;
	}
}
void build(){
	for(int i=1;i<=n;i++) if(!r[i]) q.push(i);
	while(!q.empty()){
		int x=q.front();
		dep[a[x]]=dep[x]+1;
		r[a[x]]--;
		if(!r[a[x]]) q.push(a[x]);
		del[x]=1;
		q.pop();
	}
	for(int i=1;i<=n;i++){
		if(del[i]==1&&rr[i]>1) { printf("0\n"); exit(0); }
		if(del[i]==0&&rr[i]>2) { printf("0\n"); exit(0); }
	}
	for(int i=1;i<=n;i++)
	if(!del[i]){
		cnt=0;
		flag=1;
		find(i);
		if(flag) t[cnt]++;
		else{
			int x=i;
			while(!dep[x]) x=b[x];
			rt[++T]=x;
		}
	}
}
void dfs(int x,int res){
	if(dep[x]){
		if(res>0) ans=0;
		if(res<0) ans=2ll*ans%mod;
		res=dep[x];
	}
	if(!del[x]) return;
	del[x]=0;
	dfs(b[x],res-1);
}
int main(){
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),r[a[i]]++,rr[a[i]]++;
	build();
	ans=1;
	for(int i=1;i<=n;i++){
		if(!t[i]) continue;
		int sum=0;
		for(int j=0;j<=t[i];j+=2){
			int tot;
			tot=1ll*fac[t[i]]*_fac[t[i]-j]%mod*_fac[j/2]%mod*_qp[j/2]%mod*qpow(i,j/2)%mod;
			if(i%2==1&&i>1) tot=1ll*tot*qp[t[i]-j]%mod;
			upd(sum,tot);
		}
		ans=1ll*ans*sum%mod;
	}
	for(int i=1;i<=T;i++) dfs(rt[i],0);
	printf("%d\n",ans);
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    int Q;
    cin >> Q;

    vector<set<int>> alpha(26);
    rep(i, 26) alpha[i].insert(1000000);
    rep(i, N) {
        alpha[S[i] - 'a'].insert(i + 1);
    }

    rep(i, Q) {
        int ct;
        cin >> ct;
        if (ct == 1) {
            int l;
            char c;
            cin >> l >> c;
            l--;
            char be = S[l];
            S[l] = c;
            alpha[be - 'a'].erase(l + 1);
            alpha[c - 'a'].insert(l + 1);
        }
        else {
            int l, r;
            cin >> l >> r;
            int res = 0;
            rep(j, 26) {
                int il = *alpha[j].lower_bound(l);
                int ir = *alpha[j].upper_bound(r);
                // cout << il << " " << ir << endl;
                if (il != ir) res++;
            }
            cout << res << endl;
        }
    } 
    return 0;
}

Measured memory_bytes: 27256
#include<stdio.h>

int decreasable(long long K, long long* a, int N){
  long long count = 0;
  for(int i = 0; i < N; i++){
    count += (a[i] + K + 1) / (N + 1);
  }
  
  return count <= K;
}

int main(){
  int N; scanf("%d", &N);
  
  long long a[N];
  for(int i = 0; i < N; i++) scanf("%lld", a + i);
  
  long long ok = 10e17;
  long long ng = -1;
  while(ok - ng > 1){
    long long K = (ok + ng) / 2;
    if(decreasable(K, a, N)) ok = K;
    else ng = K;
  }
  
  for(int i = 1; i <= ok && i <= N * N; i++){
    if(decreasable(ok - i, a, N)) ng = ok - i - 1;
  }
  ok = ng + 1;
  
  printf("%lld\n", ok);
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int
#define ff first
#define ss second
#define eps 1e-9
#define mod 1000000007

using namespace std;

ll bigmod(ll b,ll e)
{
    ll res = 1;

    while(e)
    {
        if(e%2)
        {
            res*=b;
            res = res%mod;
            e--;
        }
        else
        {
            b*=b;
            b = b%mod;
            e/=2;
        }
    }

    return res;
}

int main()
{

    ll t,n,m,f,a,b,c,l,r,q,k,x,y,z,ans,mn,mx,sum=0;
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    cin>>n;


    x = bigmod(10,n);
    y = bigmod(9,n);
    z = bigmod(8,n);

    ans = x - y ;

    if(ans<0)
        ans+=mod;

    ans = ans - y;

    if(ans<0)
        ans+=mod;


    ans = (ans+z)%mod;

    cout<<ans<<endl;

}


Measured memory_bytes: 3596