akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include "atcoder/all"
using namespace std;
using namespace atcoder;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
const long long int sMod = 998244353;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll op(ll a,ll b){
    return max(a,b);
}

ll e(){
    return -1;
}

ll target;

bool f(ll x){
    return x < target;
}

void solve(){
    ll n,q;
    cin >> n >> q;
    Vi a(n);
    rp(i,n) cin >> a[i];
    segtree<ll,op,e> seg(a);
    Vi ans;
    while(q--){
        ll t;
        cin >> t;
        if(t==1){
            ll x,v;
            cin >> x >> v;
            x--;
            seg.set(x,v);
        }
        if(t==2){
            ll l,r;
            cin >> l >> r;
            l--;
            ans.pb(seg.prod(l,r));
        }
        if(t==3){
            ll x;
            cin >> x >> target;
            x--;
            ans.push_back(seg.max_right<f>(x)+1);
        }
    }
    for(auto an:ans){
        print(an);
    }
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 11008
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

typedef long long ll;

const ll mod=1e9+7;

#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define rc(x)  return cout<<x<<"\n",0
#define sz(s)  (int) s.size()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;

ll k,l,r;

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> k >> l >> r;
	ll largest = (r/k)*k;
	
	if (l<=largest) {
		cout << "OK\n";
	}
	else cout << "NG\n";

}


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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    long long B = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        B ^= A[i];
    }
    for (int i = 0; i < N; ++i) cout << (B^A[i]) << endl;
}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const ll mod=1000000007;
const ll INF=1e15;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//最大公約数
ll yaku(ll a, ll b){
    if(a>b) return yaku(b,a);
    else{
        if(b%a==0) return a;
        else return yaku(b%a,a);
    }
}
int main(){
  ll A,B; cin>>A>>B;
  cout<<A*B/yaku(A,B)<<endl;
}

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

int check_a(int a, int b, int c, int x);
int check_b(int a, int b, int c, int x);
int check_c(int a, int b, int c, int x);

int main() {
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	cout << check_c(a, b, c, x) << endl;
	return 0;
}

int check_a(int a, int b, int c, int x){
	//cout << a << " " << b << " " << c << endl;
	if(a < 0) return 0;
	if(a * 500 + b * 100 + c * 50 == x)
		return 1 + check_a(a - 1, b, c, x);
	return check_a(a - 1, b, c, x);
}

int check_b(int a, int b, int c, int x){
	if(b < 0) return 0;
	return check_a(a, b, c, x) + check_b(a, b - 1, c, x);
}

int check_c(int a, int b, int c, int x){
	if(c < 0) return 0;
	return check_c(a, b, c - 1, x) + check_b(a, b, c, x);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 10000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int dp[n];
    int h[n];
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    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];

}



Measured memory_bytes: 4372
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> Z(0,0);
  for(int i=0; i<S.size()-1; i++){
    if(S[i]=='A' && S[i+1]=='C'){
      Z.push_back(i);
    }
  }
  for(int i=0; i<Q; i++){
    int l, r;
    cin >> l >> r;
    auto it1=lower_bound(Z.begin(), Z.end(), r-1);
    auto it2=lower_bound(Z.begin(), Z.end(), l-1);
    int ans=it1-it2;
    cout << ans << endl;
  }
}

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

#define fi first
#define se second
#define show(x) cerr << #x << "=" << "\n"
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

class union_find{
public:
    explicit union_find(int _n):n(_n){
        par.resize(static_cast<unsigned long>(_n));
        rank.resize(static_cast<unsigned long>(_n));
        sizes.resize(static_cast<unsigned long>(_n));
        for(int i=0;i<_n;i++){
            par[i]=i;
            rank[i]=0;
            sizes[i]=1;
        }
    }
    
    //親ノードを見つけます
    int find(int a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }
    
    //aとbが同じグループかの判定
    bool same(int a,int b){
        return find(a)==find(b);
    }
    
    //aとbを同じグループにします
    void unite(int a,int b){
        link(find(a),find(b));
    }
    
    //aが属するグループの要素数を求めます
    int size(int a){
        return sizes[find(a)];
    }
    
    //全体がどのグループに属しているかがわかります
    void view(){
        for(int i=0;i<n;i++){
            cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
        }
        for(int i=0;i<n;i++){
            cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
        }
        cout<<endl;
    }

private:
    void link(int a,int b){
        if(same(a,b))return;
        if(rank[a]>rank[b]){
            par[b]=a;
            sizes[a]+=sizes[b];
            sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            sizes[a]=0;
        }
    }
    int n;
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
};

int n, m;
map<int, vector<int> > mp;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1 = freopen("in.txt", "r", stdin);
  //stream2 = freopen("out.txt", "w", stdout);
  if (stream1 == NULL) return 0;
  //if (stream2 == NULL) return 0;:w
#endif
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int k; cin >> k;
    for (int j = 0; j < k; j++) {
      int a; cin >> a; a--;
      mp[a].push_back(i);
    }
  }
  union_find uf(n);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < (int)mp[i].size() - 1; j++) {
      uf.unite(mp[i][j], mp[i][j + 1]);
    }
  }
  if (uf.size(0) == n) {
    cout << "YES" << endl;
  } else cout << "NO" << endl;
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

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

int x, y;

int main () {
	cin >> x >> y;
	if (x>y && y != 1){
		cout << "Alice" << endl;
	}else{ if (x<y && x != 1){
			cout << "Bob" << endl;
	}else{ if (x == y){
		cout << "Draw" << endl;
	}else { if (x>y && y == 1) {
		cout << "Bob" << endl;
	}else {if (x<y && x==1){
		cout << "Alice" << endl;
	}
}
}
}
}
}

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

vector<vector<int>> AdjList(100005);
vector<vector<int>> ta(2, vector<int>(100005));
bitset<100005> visited;

void dfs(int vertex, int dist, int selection) {
    if (visited[vertex] == false) {
        ta[selection][vertex] = dist;
        visited[vertex] = true;
        for (int i = 0; i < AdjList[vertex].size(); ++i) {
            dfs(AdjList[vertex][i], dist + 1, selection);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, u, v;
    cin >> n >> u >> v;
    u--; v--;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        AdjList[a - 1].push_back(b - 1);
        AdjList[b - 1].push_back(a - 1);
    }
    dfs(u, 0, 0);
    visited.reset();
    dfs(v, 0, 1);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (ta[1][i] > ta[0][i]) {
            ans = max(ans, ta[0][i] + (ta[1][i] - ta[0][i] - 1));
        }
    }
    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 10360
import Control.Monad
import Data.IntMap.Strict ((!)) 
import qualified Data.IntMap.Strict as M 
import qualified Data.Set as S 
import qualified Data.ByteString.Char8 as B 
import qualified Data.Array.IArray as A 
import Data.Maybe 

type Vertex = Int 
type Weight = Int 
type Edge = (Vertex, (Vertex, Weight)) 
type Graph = A.Array Vertex (S.Set (Vertex, Weight))
type Memo = M.IntMap Weight

buildG :: Int -> [Edge] -> Graph 
buildG n = A.accumArray (flip S.insert) S.empty (1, n) 

from :: Graph -> Vertex -> S.Set (Vertex, Weight) 
from g = (g A.!) 

readDirectedEdge :: B.ByteString -> [Edge] 
readDirectedEdge = map ((\[s,t,w] -> (s,(t,w))) . map readVertex . B.words) . B.lines 

readVertex :: B.ByteString -> Vertex 
readVertex = fst . fromJust . B.readInt

main :: IO ()
main = do
  [n,_] <- map read . words <$> getLine
  es <- readDirectedEdge <$> B.getContents
  let g = buildG n es
  putStrLn $ maybe "inf" show (score n g)

score :: Int -> Graph -> Maybe Weight
score n g = guard (im1!n == im2!n) >> return (im1!n)
  where
    im0 = M.singleton 1 0
    im1 = bellman_ford g n im0
    im2 = bellman_ford g (n + 1) im1

bellman_ford :: Graph -> Int -> Memo -> Memo
bellman_ford g n im
  | n == 1 = im
  | otherwise = bellman_ford g (n - 1) (M.foldrWithKey (move g) im im)

move :: Graph -> Vertex -> Weight -> Memo -> Memo
move g s aw im = S.foldr update im (from g s)
  where 
    update (t,w) acc
      | M.notMember t acc || (acc!t) < aw + w = M.insert t (aw + w) acc
      | otherwise = acc

Measured memory_bytes: 2428
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits.h>
#include <map>
#define MAXX 200000
#define Amari 1000000007
#define p pair <int,int>
using namespace std;
multimap <int, int> ship;
int n,m,cnt=0;
bool clear = false; 
vector <int> buckets(100004,0);
stack <char> ans;
int main(int argc,char const* argv[])
{
  string x;
  cin >> x;
  n=x.size();
  for(int i=0;i<n;i++)
    {
      if(x[i] =='S')
	{
	  ans.push('S');
	}
      else if(x[i]=='T' && ans.size()==0)
	{
	  ans.push('T');
	}
      else if(x[i] =='T' && ans.top()=='S')
	{
	  ans.pop();
	}
      else if(x[i]=='T' && ans.top()=='T')
	{
	  ans.push('T');
	}
	
    }
  int answer=ans.size();

  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 1028
#include <bits/stdc++.h>
 using namespace std;
 #define rep(i, n) for (int i = 0; i < (int)(n); i++)
 #define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
 
 int main(){
   int R;
   cin >> R;

   if (R >= 2800 ){
     cout << "AGC" <<endl;
   }
   else if (R >= 1200)
   {
     cout << "ARC" << endl;
   }
   else
   {
     cout << "ABC" << endl;
   }
   
   
 }

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

vector<int> poloc;
vector<int> poloc_odd;

void make_poloc()
{
	int n=1;
	while(1){
		int a = n*(n+1)*(n+2)/6;
		if(a > 1000000)
			break;
		
		poloc.push_back(a);
		if(a % 2 == 1)
			poloc_odd.push_back(a); 
		n++;
	}
}

int main()
{
	make_poloc();

	int n;
	int dp[1000001];
	for(int i=0;i<=1000000;i++){
		dp[i] = 1000000;
	}
	dp[0] = 0;
	for(int i=0;i<poloc.size();i++){
		for(int j=0;j<=1000000;j++){
				if(j+poloc[i] <= 1000000)
					dp[j+poloc[i]] = min(dp[j+poloc[i]],dp[j]+1);
			
		}
	}
	int dpp[1000001] = {0};
	for(int i=0;i<=1000000;i++){
		dpp[i] = 1000000;
	}
	dpp[0] = 0;
	for(int i=0;i<poloc_odd.size();i++){
		for(int j=0;j<=1000000;j++){
				if(j+poloc_odd[i] <= 1000000)
					dpp[j+poloc_odd[i]] = min(dpp[j+poloc_odd[i]],dpp[j]+1);
		}
	}
	
	while(cin >> n){
		if(n==0)
			break;
		cout << dp[n] << " " << dpp[n] << endl;
	}

	return 0;
	
}

Measured memory_bytes: 8604
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
//int dx[4] = { 1,0,0,-1 };
//int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 100005

const int INF = 1e9 + 7;




int main() {


	ios::sync_with_stdio(false);
	cin.tie(0);

	ll n;
	cin >> n;
	vector<ll> a(n);
	for (int i = n - 1; i >= 0; i--) {
		cin >> a[i];
	}

	ll mini = 2;
	ll maxi = 2;

	for (ll i = 0; i < n; i++)
	{
		bool exist = false;
	
		mini = a[i] * ((mini - 1) / a[i] + 1);
		maxi = a[i] * (maxi / a[i]) + (a[i] - 1);
		if ((maxi-mini+1)/a[i] <= 0)
		{
			cout << "-1" << endl;
			return 0;
		}
	}
	cout << mini << " " << maxi << endl;
	

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>


#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back 
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define mod2 998244353
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 1000000000000

// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>


// using namespace __gnu_pbds;
using namespace std;

using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;

int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,l,k,r,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U;
    // int x,y,a,b,c;
    cin>>n;
    vi a(n);
    rep(i,0,n) 
    {
        cin>>t;
        if(t%2==0)
        {
            if(t%3==0) continue;
            if(t%5==0) continue;
            cout<<"DENIED";
            return;
        }
    }
    cout<<"APPROVED";
}


signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    int T=0;
    while(t--)
    {
        T++;
        // if(T>1) cout<<"\n";
        // cout<<"Case #"<<T<<": ";
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3608
N = int(input())
S = input()

ans = 0
for n in range(1000):
    target = "{:03}".format(n)
    j = 0
    for i in range(N):
        if S[i] == target[j]:
            j += 1
        if j == 3:
            ans += 1
            break

print(ans)


Measured memory_bytes: 73948
#include<bits/stdc++.h>
#define ll long long int
#define mii map<int,int>
#define qi queue<int>
#define pqi priority_queue<int>
#define pqgi priority_queue<int,vector<int>,greater<int>>
#define si set<int>
#define vi vector<int>
#define vll vector<long long int>
#define vii vector<pair<int,int>>
#define mii map<int,int>
#define ii pair<int,int>
#define SYNC ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define f(i,a,b) for(int i=a;i<b;i++)
#define rf(j,c,d) for(int j=c;j>d;j--)
#define mod 1000000007
#define mo 998244353
#define inf 1e18
#define INF (int)INT_MAX
#define PI 3.1415926535898
using namespace std;
const int N=1e5+5;
/*ll po(ll A,ll B)
{
	ll RES=1;
	while(B)
	{
		if(B&1)
			RES*=A;
		B>>=1;
		A*=A;
	}
	return RES;
}*/
/*void sieve(int P)
{
	prime[0]=0;prime[1]=0;
	f(i,2,P+1)
		prime[i]=1;
	f(i,2,P+1)
	{
		if(prime[i]==1)
		{
			for(int j=i*i;j<P+1;j+=i)
			{
				prime[j]=i;
			}
		}
	}
}*/
void solve()
{
	int n;
	cin>>n;map<string,int> mp;string s;
	f(i,0,n)
	{
		cin>>s;
		mp[s]++;
	}
	cout<<"AC x "<<mp["AC"]<<'\n';
	cout<<"WA x "<<mp["WA"]<<'\n';
	cout<<"TLE x "<<mp["TLE"]<<'\n';
	cout<<"RE x "<<mp["RE"]<<'\n';
	return;
}
int main()
{
    SYNC
    //sieve();
    int t=1;
    //cin>>t;
    while(t--)
    	solve();
    return 0;
}

Measured memory_bytes: 3668
#include<stdio.h>
#define MAX 100000

int A[MAX],n;

int partition(int p,int r){
    int x,i,j,t;
    x=A[r];
    i=p-1;
    for(j=p;j<r;j++){
        if(A[j]<=x){
            i++;
            t=A[i]; A[i]=A[j]; A[j]=t;
        }
    }
    t=A[i+1]; A[i+1]=A[r]; A[r]=t;
    return i+1;
}

int main(){
    int i,q;
    
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    
    q=partition(0,n-1);
    
    for(i=0;i<n;i++){
        if(i) printf(" ");
        if(i==q) printf("[");
        printf("%d",A[i]);
        if(i==q) printf("]");
    }
    printf("\n");
    
    return 0;
}


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

#define vl vector<ll>
#define vi vector<int>

#define ff first
#define ss second

#define pb push_back
#define MOD 1e9+7 
//const int nax = 1e6+5;
#define display(v) for(int i =0;i<v.size();++i)cout << v[i] << " "

inline ll add(ll a, ll b){ ll c = a + b; if(c > MOD) c -= MOD; return c; }

const int nax = (int)1e4 + 5;
vector<pair<int,int> > v;
int dp[nax];

int fun(int h){
    if(h <= 0){
        return 0;
    }
    if(dp[h] != -1){
        return dp[h];
    }
    int way = INT_MAX;
    for(int i =0;i<v.size();++i){
        way = min(way,v[i].ss + fun(h-v[i].ff));
    }
    dp[h] = way;
    return dp[h];
}

int main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int h,n;
    cin>>h>>n;
    for(int i =0;i<n;++i){
        int a,b; cin>>a>>b;
        v.pb({a,b});
    }
    memset(dp,-1,sizeof(dp));
    int val = fun(h);
    cout << val;
    return 0;
 }

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,pair<ll,ll> >
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ii>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a);  a = (a * a);  b/=2;  }  return res; }
#define rs resize
long long readLI(){  register char c;  for(c = getchar(); !(c>='0' && c<='9'); c = getchar());  register long long a=c-'0';
    for(c = getchar(); c>='0' && c<='9'; c = getchar())
        a = (a<<3)+(a<<1)+c-'0';
    return a;
}
const ll N = 1000009;
ll n,a,t;
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n;
    a = n;
    while(a > 0) t += a%10,a/=10;
    cout<<(n%t == 0 ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define test() int t; cin>> t; while (t--)
#define scan(a, i) for (int j = 0; j < i; j++) cin>> a[j];
#define print(a, i) for (int j = 0; j < i; j++) cout<< a[j]<< endl;
#define lli long long int
int main() 
{
    fastio()
    lli x, y, i;
    cin>> x>> y;
    lli count = 1;
    for (i = 2 * x; i <= y; i *= 2)
        count++;
    cout<< count<< endl;
    return 0;
}


Measured memory_bytes: 256
package main

import (
  "bufio"
  "fmt"
  "os"
  "sort"
  "strconv"
  "strings"
)

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,10000)}
  n,m,k := input.NextInts()
  c := input.NextIntArray()
  num := k
  for i:=0;i<n;i++ {
    c[i]--
    if c[i] < 0 {
      c[i] = num
      num++
    }
  }
  es := NewEdges(m)
  for i:=0;i<m;i++ {
    a,b,w := input.NextInts()
    a,b = a-1,b-1
    es[i] = Edge{c[a],c[b],int64(w)}
  }
  sort.Sort(es)
  uf := NewUnionFind(num)
  ans := int64(0)
  cnt := 0
  for _,e := range es {
    if uf.Same(e.fm,e.to) { continue }
    uf.Unite(e.fm,e.to)
    ans += e.cost
    cnt++
    if cnt == k-1 { break }
  }
  if cnt != k-1 { ans = -1 }
  fmt.Println(ans)
}

type Edge struct { fm,to int;cost int64 }
type Edges []Edge
func NewEdges(n int) Edges { return make([]Edge,n) }
func(e Edges) Len() int { return len(e) }
func(e Edges) Swap(i,j int) { e[i],e[j] = e[j],e[i] }
func(e Edges) Less(i,j int) bool { return e[i].cost < e[j].cost }

type UnionFind struct { par,rank []int }
func NewUnionFind(n int) UnionFind {
  par := make([]int,n)
  rank := make([]int,n)
  for i:=0;i<n;i++ { par[i] = i }
  return UnionFind{par,rank}
}
func(u UnionFind) Find(i int) int {
  if u.par[i] == i { return i }
  u.par[i] = u.Find(u.par[i])
  return u.par[i]
}
func(u UnionFind) Same(i,j int) bool { return u.Find(i) == u.Find(j) }
func(u UnionFind) Unite(i,j int) {
  i,j = u.Find(i),u.Find(j)
  if i == j { return }
  if u.rank[i] < u.rank[j] { u.par[i] = j;return }
  u.par[j] = i
  if u.rank[i] == u.rank[j] { u.rank[i]++ }
}

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int,int) {
  s := strings.Fields(i.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  z,_ := strconv.Atoi(s[2])
  return x,y,z
}
func(i *Input) NextIntArray() []int {
  s := strings.Fields(i.NextLine())
  a := make([]int,len(s))
  for i:=0;i<len(s);i++ { a[i],_ = strconv.Atoi(s[i]) }
  return a
}

Measured memory_bytes: 10752
// C - 白昼夢 / Daydream
#include <bits/stdc++.h>
using namespace std;

int main(){
	vector<string> T{"dreamer","eraser","erase","dream",};
	for(auto &p:T){ reverse(p.begin(), p.end()); }

	string s; cin>>s;
	reverse(s.begin(), s.end());

	string ans;
	int i = 0;
	while(i<s.size()){
		ans = "NO";
		int j;
		for(j=0; j<4; ++j){
			if(T[j]==s.substr(i,T[j].size())){
				ans="YES";
				break;
			}
		}
		if(ans=="NO") break;
		i += T[j].size();
	}
	cout<< ans <<endl;

}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  int n;
  cin >> n;
  vl a(n), b(n);
  ll suma = 0, sumb = 0;
  rep (i, n) {
    cin >> a[i];
    suma += a[i];
  }
  rep (i, n) {
    cin >> b[i];
    sumb += b[i];
  }
  if (sumb > suma) {
    cout << -1 << endl;
    return 0;
  }
  ll fusoku = 0;
  vl amari;
  int ans = 0;
  rep (i, n) {
    if (a[i] > b[i]) {
      amari.push_back(a[i] - b[i]);
    }
    else if (a[i] < b[i]) {
      fusoku += b[i] - a[i];
      ans++;
    }
  }
  sort(all(amari));
  while (fusoku > 0) {
    if (fusoku >= amari.back()) {
      fusoku -= amari.back();
      amari.pop_back();
      ans++;
    }
    else {
      fusoku = 0;
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 2428
import heapq

def main():
    N, K = map(int, input().split())
    H = [int(x) for x in input().split()]

    q = list(map(lambda x: x*-1, H))
    heapq.heapify(q)

    # 必殺技を使える回数が敵の数より多いケースを考慮する
    K = min(N, K)

    for _ in range(K):
        heapq.heappop(q)

    print(sum(q)*-1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 25896
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

int main() {
  int a, b;
  cin >> a >> b;
  cout << max(0, a - 2 * b) << endl;

  
  return 0;
}

Measured memory_bytes: 256
// # ======================================= #
// # Ilham Firdausi Putra, 23 Desember 2017  #
// # ======================================= #
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define nl printf("\n");

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull; 


int main()
{
  int A,B,N,sum=0;
  cin >> N >> A >> B;

  for (int i = 1; i <= N; ++i)
  {
    int x, nilai=0, tempX;
    // scanf("%d", &x);
    tempX = i;
    while(tempX!=0){
      nilai+=(tempX%10);
      tempX/=10;
    }

    if ( (nilai>=A) && (nilai<=B) )
    {
      sum+=i;
    }
  }

  printf("%d\n", sum);

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>

int main()
{
	char s[300];
	int i, f=0, j;
	scanf("%s", s);
	int l = strlen(s);
	if(s[0] == 'A')
	{
		for(i=2; i<l-1; i++)
		{
			if(s[i] == 'C')
			{
				for(j=1, f=1; j<l; j++)
				{
					if(s[j] < 'a' && j!=i)
					{
						f=0;
						break;
					}
				}
				break;
			}
		}
	}
	
	if(f)	printf("AC\n");
	else 	printf("WA\n");
	return 0;
}
// printf("1\n");



Measured memory_bytes: 128
#include <stdio.h>
#define N 100

int m[N][N];

int main ()
{
    int n, u, k, v;
    int i, j;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d %d", &u, &k);
        u--;
        for (j = 0; j < k; j++) {
            scanf("%d", &v);
            v--;
            m[u][v] = 1;
        }
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (j) {
                printf(" ");
            }
            printf("%d", m[i][j]);
        }
        printf("\n");
    }

    return 0;
}



Measured memory_bytes: 2052
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
  vector<int> X(3);
  cin >> X[0] >> X[1] >> X[2];
  sort(X.begin(), X.end());
  cout << X[0] + X[1] << endl;
}

Measured memory_bytes: 256
/**
 *      ABC 86 A
 *      author  : kyomukyomupurin
 *      created : 2018-09-01 04:43:27
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b; cin >> a >> b;
    a * b % 2 == 0 ? cout << "Even" : cout << "Odd";

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n = 0;
  long a[100000] = {};
  int i = 0;
  int divfour = 0;
  int divtwo = 0;
  int odd = 0;
  int success = 0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%ld",&a[i]);
    if(a[i] % 4 == 0){
      divfour++;
    }else if(a[i] % 2 == 0){
      divtwo++;
    }else{
      odd++;
    }
  }
  //printf("%d %d %d/",divfour,divtwo,odd);
  if(divtwo != 0){
    if((n-divtwo)%2==0){
      if(divfour >= odd){
        success = 1;
      }
    }else{
      if(divfour >= odd + 1){
        success = 1;
      }
    }
  }else{
    if(divfour+1 >= odd){
      success = 1;
    }
  }
  if(success){
    printf("Yes");
  }else{
    printf("No");
  }
  return 0;
}
        
  

Measured memory_bytes: 896
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

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

  return 0;
}


Measured memory_bytes: 256
main(){
  int l=1000010,n,q;
  long long m[l],c[l],x[l];
  char s[l];
  scanf("%d%s%d",&n,s,&q);
  for(int i=1;i<=n;i++){
    m[i]=m[i-1];
    c[i]=c[i-1];
    x[i]=x[i-1];
    if(s[i-1]=='M')m[i]++;
    else if(s[i-1]=='C'){
      c[i]++;
      x[i]+=m[i];
    }
  }
  while(q--){
    long long a=0;
    int k;
    scanf("%d",&k);
    for(int i=0;i<n;i++){
      int j=i+k;
      if(j>n)j=n;
      if(s[i]=='D')a+=x[j]-x[i]-(c[j]-c[i])*m[i];
    }
    printf("%lld\n",a);
  }
}

Measured memory_bytes: 24576
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
using namespace std;

bool notzero[10]; //i番目の文字は0になれない
int num[10]; //i番目の文字の値
bool used[10]; //iが使われているか
int co[10]; //i番目の係数
int m; //係数の数
int ans;

void dfs(int pos){
	if(pos==m){
		int sum = 0;
		for(int i=0;i<m;i++){
			sum += co[i] * num[i];
		}
		if(sum==0) ans++;
		return;
	}
	for(int i=0;i<10;i++){
		if(used[i] || (i==0&&notzero[pos])) continue;
		used[i] = true;
		num[pos] = i;
		dfs(pos+1);
		used[i] = false;
	}
}


int main(){

	int n;
	while(cin >> n,n){
		vector<string> inputs(n);
		string dict = "";
		for(int i=0;i<n;i++){
			cin >> inputs[i];
			for(int j=0;j<inputs[i].size();j++){
				if(dict.find(inputs[i][j])==-1) dict.push_back(inputs[i][j]);
			}
		}

		m = dict.size();
		fill(co,co+m,0);
		fill(notzero,notzero+m,false);
		int p;
		for(int i=0;i<n-1;i++){
			p = 1;
			for(int j=inputs[i].size()-1;j>=0;j--){
				co[dict.find(inputs[i][j])] += p;
				p *= 10;
			}
			if(inputs[i].size()!=1){
				notzero[dict.find(inputs[i][0])] = true;
			}
		}
		p = 1;
		for(int j=inputs[n-1].size()-1;j>=0;j--){
			co[dict.find(inputs[n-1][j])] -= p;
			p *= 10;
		}
		if(inputs[n-1].size()!=1){
			notzero[dict.find(inputs[n-1][0])] = true;
		}

		ans = 0;
		dfs(0);
		cout << ans << endl;
	}
	return 0;

}

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

int main() {
  ll X = 0, N = 0, ans = 200;
  cin >> X >> N;
  vector<ll>dame(N);
  vector<ll>A(200); //0~200
  vector<ll>S(200); //abs
  rep(i,N){
    cin >> dame[i];
  }
  rep(i,200){
    A[i] = i; 
    S[i] = abs(A[i] - X);
  }
  bool a = true;
  rep(i,200){
    rep(j,N){
      if(i == dame[j]){
        a = false;
      }
    }
    if(a){
      ans = min(S[i], ans);
    }
    else{
      a = true;
    }
  }
  rep(i,N){
    if(X-ans == dame[i]){
      cout << ans + X;
      return 0;
    }
  }
  cout << X - ans;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
  int x = 0, n, max = 0;
  std::string s;
  std::cin >> n >> s;
  for ( auto c : s ) { 
    if ( c == 'I' )
      x++;
    else
      x--;

    max = std::max( x, max );
  }

  std::cout << max << std::endl;

  return 0;
}


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

const int INF = 1e9;

int main() {
    int n, m;
    cin>>n>>m;

    int k[m];
    int s[10][10];
    for (int i=0; i<m; i++) {
        cin>>k[i];
        for (int j=0; j<k[i]; j++) {
            cin>>s[i][j];
            --s[i][j];
        }
    }
    int p[m];
    for (int i=0; i<m; i++) cin>>p[i];

    int ans = 0;
    for (int i=0; i<(1<<n);i++) {
        bool flag = true;
        for (int j=0; j<m; j++) {
            int tmp = 0;
            for (int ki=0; ki<k[j]; ki++) {
                if ((i>>s[j][ki]) & 1) {
                    ++tmp;
                }
            }
            if (tmp % 2 != p[j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ++ans;
        }
    }
    cout<<ans<<endl;


}

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

constexpr int INF = INT_MAX;

struct edge{
    int from, to, d;
    edge(){}
    edge(int from, int to, int d):from(from),to(to),d(d){}
};

struct Graph{
    int V;
    vector<vector<edge> > g;
    vector<vector<int> > dist;
    void init(int _V){
        V = _V;
        g.resize(V);
    }
    void add_edge(int u, int v, int d){
        g[u].push_back(edge(u,v,d));
        g[v].push_back(edge(v,u,d));
    }
    void wf(){
        dist.resize(V, vector<int>(V, INF/3));
        for(auto &v : g){
            for(auto &e : v){
                int u = e.from, v = e.to, d = e.d;
                dist[u][v] = d;
                dist[v][u] = d;
            }
        }
        for(int i=0;i<V;i++){
            dist[i][i] = 0;
        }
        for(int k=0;k<V;k++){
            for(int i=0;i<V;i++){
                for(int j=0;j<V;j++){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    vector<edge> operator [](int i) {
        return g[i];
    }
};

int main(void){
    int V, E, Tmax;
    cin >> V >> E;
    Graph graph;
    graph.init(V);
    for(int i=0;i<E;i++){
        int u, v, d;
        cin >> u >> v >> d;
        u--; v--;
        graph.add_edge(u,v,d);
    }
    graph.wf();
    cin >> Tmax;
    set<int> req;
    queue<int> reqque, que;
    vector<bool> remain(V);
    int now = 0, cnt = 0, nxt = 0;
    for(int t=0;t<Tmax;t++){
        // 情報の受け取り
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            int id, dst;
            cin >> id >> dst;
            if(req.count(dst-1)==0){
                req.insert(dst-1);
                reqque.push(dst-1);
            }
        }
        if(now == 0){
            if(!reqque.empty()){
                while(!reqque.empty()){
                    int dst = reqque.front();
                    que.push(dst);
                    remain[dst] = true;
                    reqque.pop();
                }
                que.push(0);
                remain[0] = true;
                req.clear();
            }
        }
        if(!que.empty()){
            if(cnt == 0){
                int dst;
                while(!que.empty()){
                    dst = que.front();
                    if(remain[dst]) break;
                    que.pop();
                }
                for(auto &e : graph[now]){
                    if(now == e.to) continue;
                    if(graph.dist[now][e.to] + graph.dist[e.to][dst] == graph.dist[now][dst] && graph.dist[now][e.to] == e.d){
                        nxt = e.to;
                        cnt = e.d;
                        break;
                    }
                }
            }
            cout << nxt+1 << endl;
            now = -1;
            cnt--;
            if(cnt == 0){
                now = nxt;
                remain[now] = false;
                if(now == que.front()) que.pop();
            }
        }
        else{
            cout << -1 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<int,P>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
char x[200000],y[200000];
signed main(){
	int a,b,c=-1,d;
	string s;
	cin>>a>>b>>s;
	d=a;
	f(i,b){
		cin>>x[i]>>y[i];
	}
	for(int i=b-1;i>=0;i--){
		if(x[i]==s[c+1]&&y[i]=='L')c++;
		if(x[i]==s[d-1]&&y[i]=='R')d--;
		if(x[i]==s[c]&&y[i]=='R')c--;
		if(x[i]==s[d]&&y[i]=='L')d++;
	}
	cout<<max((int)(0),d-c-1)<<endl;
    return 0;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = pow(10, 9) + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << endl; exit(0);}

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

  ll odd = 0, four = 0;
  for (ll i = 0; i < N; i++)
  {
    ll A;
    cin >> A;
    if (A % 2 == 1)
      odd++;
    else if (A % 4 == 0)
      four++;
  }

  cout << ((odd <= four || (odd - 1 == four && odd + four == N)) ? "Yes" : "No") << endl;
}

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

const double PI = 3.14159265358979323846;
//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
//typedef unsigned long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<int, int> P;
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 100;
//const ll INF = (1ll << 31) - 1;
const ll INF = 1e15;
//const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;

struct Cake {
    int count, type;

    bool operator<(const Cake &cake) const {
        return (count < cake.count);
    }
};


int main() {
    int k, t;
    cin >> k >> t;

    vector<int> cakes(t);
    rep(i, t) cin >> cakes[i];

    int ma = *max_element(cakes.begin(), cakes.end());
    int ans = max(ma - 1 - (k - ma), 0);
    cout << ans << endl;
}


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

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[100][4][4][4];

int main() {
  int n;
  cin >> n;
  dp[0][3][3][3] = 1;
  rep(i,n)rep(j,4)rep(k,4)rep(l,4) {
    rep(d, 4) {
      if(d == 1 && l == 2 && k == 0) continue;
      if(d == 1 && l == 0 && k == 2) continue;
      if(d == 2 && l == 1 && k == 0) continue;
      if(d == 1 && l == 2 && j == 0) continue;
      if(d == 1 && k == 2 && j == 0) continue;
      dp[i + 1][d][l][k] += dp[i][l][k][j];
    }
  }
  mint ans = 0;
  rep(j,4)rep(k,4)rep(l,4) {
    ans += dp[n][j][k][l];
  }
  cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define dbgmint(n,arr) rep(i,n){cerr<<arr[i].x<<" ";}cerr<<endl;
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

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

    string s;
    cin>>s;
    ll n = s.length();
    rep(i,n){
        s[i] = 'x';
    }
    cout<<s<<endl;
    return  0;
}


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

#define pb push_back
#define all(a) (a).begin(), (a).end()

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

// borrowed from neal's code
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const ll MOD = 1e9 + 7;

ll binpow(ll a, ll b, const ll m = MOD) {
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<ll> cnt(k + 1, 0);

    for (int g = k; g >= 1; --g) {
    	ll cur = binpow(k / g, n);
    	ll sub = 0;

    	for (int i = g * 2; i <= k; i += g) 
    		sub = (sub + cnt[i]) % MOD;

    	cnt[g] = (cur - sub + MOD) % MOD;
    }

    // dbg(cnt);

    ll ans = 0;
    for (int g = 1; g <= k; ++g) {
    	ans = (ans + (g * cnt[g])) % MOD;
    }

    cout << ans << "\n";
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
const ll mod = 1e9 + 7;
const int M = 2e6 + 5;
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll base,ll pow){ll ans = 1;
   if(pow < 0) return 0;
   while(pow!=0){if(pow&1==1){ans = ans*base;ans = ans%mod;}
   base *= base;base%=mod;pow/=2;}return ans;}
ll inv(ll x){return expo(x,mod-2);}
ll mult_mod(ll a , ll b){a = a%mod; b = b%mod;ll c = (a * b)%mod;return c;}
ll add_mod(ll a , ll b){a = (a + mod)%mod;b = (b + mod)%mod;ll c = (a + b)%mod;return c;}
ll fac[(int)(2e6 + 7)] , inv_fac[(int)(2e6 + 7)];
void precomp_factorial(){fac[0] = 1;for(ll i = 1 ; i <= M ; i++) fac[i] = mult_mod(i , fac[i - 1]);
    inv_fac[M] = inv(fac[M]);for(ll i = M - 1 ; i >= 0 ; i--) inv_fac[i] = mult_mod(i + 1 , inv_fac[i + 1]);}
ll nCk(ll n , ll k){ll ans = fac[n];ans = mult_mod(ans , inv_fac[n - k]);ans = mult_mod(ans , inv_fac[k]);return ans;}
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};


int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int cond = 0;
    for(int i = 0; i < s1.size(); i++){
        int cond1 = 1;
        for(int j = 0; j < s2.size(); j++){
            int ind = i+j;
            if(ind >= s1.size()) ind -= s1.size();
            if(s1[ind] != s2[j]){
                cond1 = 0;
                break;
            }
        }
        cond = cond1;
        if(cond) break;
    }
    if(cond) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256