akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 5;
const ll MOD = 1e9 + 7;
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pis pair<ll,string>
#define F first
#define S second
#define LCM(a,b) ((a*b)/__gcd(a,b))
#define inf 1e15
#define test ll cse;cin>>cse;for(ll _i=1;_i<=cse;_i++)
#define PI 3.14159265
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const double EPS = 1E-9;
typedef vector< vector<double> > matrix;
typedef vector< vector<int> > array_2D;
typedef pair<int, pair<int, int> > ppi;
typedef vector<int> vi;



int main() {


    string s;
    string t;

    cin >> s;
    cin >> t;


    if(s.size() + 1 == t.size() && t.substr(0, s.size()) == s) {
        cout << "Yes\n";
    }
    else
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int n, box=0, zero=0;
  cin >> n;
  int a[n], b[n];
  for(int i=0; i<n; i++){
    cin >> a[i];
    if(a[i]==0) zero++;
  }
  vector<int> c;
  for(int i=n-1; i>n/2-1; i--){
    if(a[i]==1) {b[i]=1; box++; c.push_back(i+1);}
    else b[i]=0;
  }
  for(int i=n/2-1; i>=0; i--){
    int m=n/(i+1), count=0;
    for(int j=2; j<=m; j++){
      count+=b[(i+1)*j-1];
    }
    if(count%2==0){
      if(a[i]==1) {b[i]=1; box++; c.push_back(i+1);}
      else b[i]=0;
    }
    else{
      if(a[i]==1) b[i]=0;
      else {b[i]=1; box++; c.push_back(i+1);}
    }
  }
  sort(c.begin(), c.end());
  if(zero==n) cout << "0";
  else if(box==0) cout << "-1";
  else{
    cout << box << endl;
    cout << c[0];
    for(int i=1; i<c.size(); i++){
      cout << " " << c[i];
    }
  }
  return 0;
}

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;

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

	
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin() x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin() x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b; cin>>a>>b;
	ll A=0, B=0;
	if (a==b){
		cout << a << "\n";
		return 0;
	}
	b++;
	rep(i, 40){
		ll mask = 1LL << i;
		ll k = b/(mask*2)*mask + max(0ll, b%(mask*2)-mask);
		B |= mask*(k%2);
	}
	rep(i, 40){
		ll mask = 1LL << i;
		ll k = a/(mask*2)*mask + max(0ll, a%(mask*2)-mask);
		A |= mask*(k%2);
	}
	cout << (B^A) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const ll mod=1e9+7;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
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;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int n=s.size();
    int res=0;
    for(int i=0;i<n;i++){
        if(i>=n/2)break;
        if(s[i]!=s[n-1-i])res++;
    }
    cout<<res<<endl;
    return 0;
    }


Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
signed main(){
    fastio
    int x , n ;
    cin >> x >> n ; 
    set<int> s ; 
    for(int i = 0; i < n; i++){
        int a ;
        cin >> a ;
        s.insert(a) ;
    }
    int a = 0 , b = 0 ; 
    for(int i = x; ; i++){
        if ( s.count(i) == 0 ) {
            a = i ; 
            break ;
        }
    }
    for(int j = x; ; j--){
        if ( s.count(j) == 0 ) {
            b = j ; 
            break ;
        }
    }
    if ( abs(x - b) <= abs(x - a) ){
        cout << b << endl;
    }
    else cout << a << endl;
    return 0; 
}

Measured memory_bytes: 3656
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>

typedef long long ll;

#define rep(i,n) for(int i = 0; i < n; i++)
#define debug(x) cerr << #x << ": " << x << "\n";

using namespace std;
 
const ll INF = ll(1e18)+1;
const double PI=3.14159265358979323846;

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

  if(s == "ABC") cout << "ARC" << endl;
  else cout << "ABC" << endl;
}


Measured memory_bytes: 3596
N = int(input())
A = list(map(int, input().split()))

ans = 0
mod = 1000000007

for i in range(60):
    one_count =0
    zero_count = 0
    for j in range(N):
        if A[j] >> i & 1 == 1:
            one_count+=1
        else:
            zero_count+=1
    ans += (one_count*zero_count)*(2**i)
    ans = ans%mod
print(ans)

Measured memory_bytes: 122808
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict(list)
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    S = input()
    T = input()
    dic_s = {}
    dic_t = {}
    for i in range(len(S)):
        s = S[i]
        t = T[i]
        if s in dic_t:
            if dic_t[s] != t:
                print('No')
                exit()
        if t in dic_s:
            if dic_s[t] != s:
                print('No')
                exit()
        dic_t[s] = t
        dic_s[t] = s
    print('Yes')
if __name__ == '__main__':
  main()


Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#include <stdlib.h>
#include <time.h>
#include <chrono>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

ll d;
vector<ll> c(26 + 1);
vector<vector<ll>> s(365 + 1, vector<ll>(26 + 1, 0));

ll scoring(vector<ll> t)
{
    ll ans = 0;
    vector<ll> last(d + 1, 0);

    for (int i = 1; i <= d; i++)
    {
        ans += s[i][t[i]];
        last[t[i]] = i;

        for (int j = 1; j <= 26; j++)
        {
            ans -= c[j] * (i - last[j]);
        }
    }

    return ans;
}

int main(void)
{
    srand(time(NULL));
    cin >> d;

    for (int i = 1; i <= 26; i++)
    {
        cin >> c[i];
    }

    for (int i = 1; i <= d; i++)
    {
        for (int j = 1; j <= 26; j++)
        {
            cin >> s[i][j];
        }
    }

    vector<ll> BestT(d + 1, 1);

    for (int i = 1; i <= d; i++)
    {
        BestT[i] = rand() % 26 + 1;
    }

    // printf("%lld\n", scoring(BestT));

    ll BestScore = scoring(BestT);

    auto start = chrono::system_clock::now();

    ll count = 0;
    while (1)
    {
        vector<ll> t(d + 1);
        t = BestT;

        t[rand() % d + 1] = rand() % 26 + 1;

        ll score = scoring(t);

        if (score > BestScore)
        {
            BestT = t;
            BestScore = score;
            count++;
        }

        auto end = std::chrono::system_clock::now(); // 計測終了時刻を保存
        auto dur = end - start;                      // 要した時間を計算
        auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(dur).count();

        if (msec >= 1950)
        {
            // printf("%lld\n", count);
            break;
        }
    }

    for (int i = 1; i <= d; i++)
    {
        printf("%lld\n", BestT[i]);
    }

    // printf("%lld\n", scoring(BestT));
}


Measured memory_bytes: 3804
#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>
#define int long long
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define vi vector<int>
#define vstr vector<string>
#define vbool vector<bool>
#define vvi vector<vector<int> >
#define mii map<int,int>
#define pb push_back
#define pii pair<int,int>
#define vpair vector<pii > 
#define mkp make_pair
#define scan(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) {cout<<a[i]<<' ';}cout<<'\n'
#define mem(a,v) memset(a,v,sizeof(a))
#define loop(i,a,b) for (int i = a; i < b; i++)
#define loope(i,a,b) for (int i = a; i <= b; i++)
#define FastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PRECISION std::cout.unsetf ( std::ios::fixed );std::cout.precision(9)
#define PI 3.14159265
#define S second
#define F first
#define CHECK cout<<"CHEDEDWB"<<endl
#define br '\n'
using namespace std;
int mod = 1e9+7;
int inf = 1e18;
int m_inf = INT_MIN;


int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin>>n;
	int a[n];
	loop(i,0,n)
	{
		cin>>a[i];
		if(a[i]==0)
			{
				cout<<0<<endl;
				return 0;
			}
	}
	long double p = 0;
	loop(i,0,n)
		p += log10(a[i]);
	if(p>18.1)
		{
			cout<<-1<<endl;
			return 0;
		}
	int ans = 1;
	for(int i = 0;i<n;i++)
		ans *= a[i];
	if(ans>1000000000000000000)
		{
			cout<<-1<<endl;
			return 0;
		}
	cout<<ans<<endl;
	return 0;
} 

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

#define N 10001
#define INF 1500001 
int n;

vector<pair<int, int>> A[N];
int color[N];
int d[N];

void dijkstra(int root) {
    priority_queue<pair<int, int>> Q;
    Q.push(make_pair(0, root));

    int treeSize = 1;
    while(!Q.empty()) {
        pair<int, int> addedInfo = Q.top();
        Q.pop();
        int added = addedInfo.second;

        if (color[added] != 1) {
            d[added] = -1 * addedInfo.first;
            color[added] = 1;

            for (vector<pair<int, int>>::iterator it = A[added].begin(); it != A[added].end(); it++) {
                pair<int, int> node_pair = *it;
                if (color[node_pair.first] == 0 && (d[added] + node_pair.second) < d[node_pair.first]) {
                    d[node_pair.first] = d[added] + node_pair.second;
                    Q.push(make_pair(-1 * d[node_pair.first], node_pair.first));
                }
            }
        }
    }
}

int main() {
    cin >> n;

    int w;
    int node;
    int k;
    int ad;
    for (int i = 0; i < n; i++) {
        color[i] = 0;
        d[i] = INF;

        cin >> node >> k;
        for (int j = 0; j < k; j++) {
            cin >> ad >> w;
            A[node].push_back(make_pair(ad, w));
        }
    }

    dijkstra(0);

    for (int i = 0; i < n; i++) {
        cout << i << " " << d[i] << endl;
    }

    return 0;
}



Measured memory_bytes: 8100
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first.first
#define yy first.second
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod ((__int128)1000000007)
using namespace __gnu_pbds;
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifdef LOCAL
//	freopen("in", "r", stdin);
#endif
}
typedef long long ll;
typedef ll _I;
typedef double ld;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a, b, c;

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



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void) {

	int H;
	int N;
	int A = 0;
	int i;


	cin >> H;
	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> A;
		H = H - A;

		if (H <= 0) {
			cout << "Yes";
			break;
		}

	}

	if (H > 0) {
		cout << "No";
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#define inf 1000000000

using namespace std;

int HP, HPmax;
int R, C;
char a[105][105];

int T;
map<char, int> trap;
int S;
int dmg[1005];
int P;
int potion[13];

int N;
int dp[1005][1 << 12];

int main(void)
{
	while(1){
		cin >> HP >> HPmax;
		if(HP == 0 && HPmax == 0) break;
		
		cin >> R >> C;
		for(int y = 0; y < R; y++){
			for(int x = 0; x < C; x++){
				cin >> a[x][y];
			}
		}
		
		cin >> T;
		char c; int d;
		trap.clear();
		for(int i = 0; i < T; i++){
			cin >> c >> d;
			trap[c] = d;
		}
		
		cin >> S;
		int x = 0, y = 0, cnt = 0, dir;
		const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
		for(int i = 0; i < S; i++){
			cin >> c >> d;
			if(c == 'R') dir = 0;
			if(c == 'U') dir = 1;
			if(c == 'L') dir = 2;
			if(c == 'D') dir = 3;
			for(int j = 0; j < d; j++){
				x += dx[dir], y += dy[dir];
				cnt++;
				dmg[cnt] = trap[a[x][y]];
			}
		}
		
		cin >> P;
		for(int i = 0; i < P; i++) cin >> potion[i];
		
		N = cnt;
		for(int i = 0; i <= N; i++){
			for(int s = 0; s < (1 << P); s++){
				dp[i][s] = -inf;
			}
		}
		dp[0][0] = HP;
		
		for(int i = 0; i <= N; i++){
			for(int j = 0; j < (1 << P); j++){
				if(dp[i][j] <= 0) continue;
				if(dp[i][j] - dmg[i+1] <= 0){
					for(int k = 0; k < P; k++){
						if(j & (1<<k)) continue;
						dp[i][j|(1<<k)] = max(dp[i][j|(1<<k)], min(HPmax, dp[i][j] + potion[k]));
					}
				}
				dp[i+1][j] = max(dp[i+1][j], dp[i][j] - dmg[i+1]);
			}
		}
		
		bool flag = false;
		for(int i = 0; i < (1<<P); i++){
			if(dp[N][i] > 0){
				flag = true;
				break;
			}
		}
		if(flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 19028
#include<bits/stdc++.h>
#define N 100005
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int l,n,x[N],Q,tim[N],nxt[N],hd,tl,q[N],blo[N],sig;
int main(){
	n=read(),sig=sqrt(n);
	for(int i=1;i<=n;++i)x[i]=read();
	l=read(),Q=read();
	hd=tl=1,q[tl]=n,tim[n]=0,nxt[n]=n+1,blo[n+1]=blo[n]+1;
	for(int i=n-1;i;--i){
		while(x[q[hd]]-x[i]>l)++hd;
		nxt[i]=q[hd],q[++tl]=i;
	}
	for(int i=1;i<=n;++i)blo[i]=(i-1)/sig+1;
	for(int i=n-1;i;--i)
		if(blo[nxt[i]]==blo[i])tim[i]=nxt[i]==n?1:tim[nxt[i]]+1,nxt[i]=nxt[nxt[i]];
		else tim[i]=1;
	while(Q--){
		int a=read(),b=read(),cnt=0;
		if(a>b)a^=b,b^=a,a^=b;
		while(blo[a]<blo[b])cnt+=tim[a],a=nxt[a];
		int sum=0;
		for(int i=a+1;i<=b;++i){
			if(sum+x[i]-x[i-1]>l)sum=0,++cnt;
			sum+=x[i]-x[i-1];
		}
		if(sum)++cnt;
		printf("%d\n",cnt);
	}
	return 0;
}

Measured memory_bytes: 2816
n,a,b=map(int,input().split())
mod=10**9+7

def cmb(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    #X//Y
    X=1
    Y=1
    for i in range(r):
        X*=(n-i)
        X%=mod
        Y*=(i+1)
        Y%=mod
        
    inv=pow(Y,mod-2,mod)
    return (X*inv)%mod
        
        


allp=pow(2,n,mod)-1
ans=(allp-cmb(n,a,mod)-cmb(n,b,mod))%mod
if n==2:
    ans=0

print(ans)

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

int main(){
  ll a,b,c,d; cin>>a>>b>>c>>d;
  ll ans = -1e18;
  ans = max(ans,a*c);
  ans = max(ans,a*d);
  ans = max(ans,b*c);
  ans = max(ans,b*d);
  cout << ans << endl;
}

Measured memory_bytes: 3580
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char str[100000];

    while (scanf("%s", str) != EOF){
        int joi = 0;
        int ioi = 0;

        for (int i = 0; i < strlen(str) - 2; i++){
            if (str[i] == 'J' && str[i + 1] == 'O' && str[i + 2] == 'I'){
                joi++;
            }
            if (str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I'){
                ioi++;
            }
        }

        printf("%d\n", joi);
        printf("%d\n", ioi);
    }

    return (0);
}

Measured memory_bytes: 984
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  string s; cin >> s;
  reverse(ALL(s));
  s += '<';
  reverse(ALL(s));
  s += '>';
  vector<int> len;
  char now = '<';
  int cnt = 1;
  FOR(i, 1, s.length()) {
    if (s[i] != now) {
      len.emplace_back(cnt);
      cnt = 0;
    }
    ++cnt;
    now = s[i];
  }
  len.emplace_back(cnt);
  assert(len.size() % 2 == 0);
  --len.front();
  --len.back();
  int n = s.length() + 1;
  vector<long long> sum(n + 1, 0);
  FOR(i, 1, n + 1) sum[i] = sum[i - 1] + i;
  long long ans = 0;
  for (int i = 0; i < len.size(); i += 2) {
    // cout << len[i] << ' ' << len[i + 1] << '\n';
    if (len[i] > len[i + 1]) {
      ans += sum[len[i]];
      ans += sum[max(len[i + 1] - 1, 0)];
    } else {
      ans += sum[len[i + 1]];
      ans += sum[max(len[i] - 1, 0)];
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 6168
#include <stdio.h>

int x,a,b ;

int main(void){

    scanf ("%d%d%d",&x,&a,&b) ;

    if ( x>a ){
        a = x-a ;
    } else {
        a = a-x ;
    }
    
    if ( x>b ){
        b = x-b ;
    } else {
        b = b-x ;
    }
    
    if ( a>b ){
        printf ("B\n") ;
    } else {
        printf ("A\n") ;
    }

    return 0 ;
    
}

Measured memory_bytes: 128
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double lb; 

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

int vector_finder(vector<ll> vec, ll number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
    if (index != vec.size()) { // 発見できたとき
        return 1;
    }
    else { // 発見できなかったとき
        return 0;
    }
}

int main() {
    ll x,n;
    cin >> x >> n;
    vector<ll> p(n);
    rep(i,n){
        cin >> p[i];
    }

    
    ll ans1 = x;
    ll ans2 = x-1;
    
    while(true){
        if(!vector_finder(p,ans1)){
            cout << ans1 << endl;
            return 0;
        }
        ans1++;
        if(!vector_finder(p,ans2)){
            cout << ans2 << endl;
            return 0;
        }
        ans2--;
    }
}


Measured memory_bytes: 3636
dataset = []
while True:
    x = int(input())
    if not(x >= 1 and x <= 10000):
        break
    elif len(dataset) >= 10000:
        break
    elif x is not 0:
        dataset.append(x)
    else:
        break

for index, number in enumerate(dataset):
    print("Case {0}: {1}".format(index+1, str(number)))

Measured memory_bytes: 8136
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P; //ペア　タイプでふ

int main()
{
    int a, b;
    cin>>a>>b;
    if(a<b)
    {
        cout << 0;
    }
    else
    {
        cout << 10;
    }
}

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

int main() {
  char c[2][3];
  cin >> c[0] >> c[1];
  
  if (c[0][0]==c[1][2] && c[0][1]==c[1][1] && c[0][2]==c[1][0]) cout <<"YES";
  else cout <<"NO";
}

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

int main() {
	long long bot = 0, top = 11, mid;
	while (bot + 1 < top) {
		mid = (bot + top) / 2;
		long long cur = 1;
		for (int i = 0; i < mid; i++) {
			cur *= 10;
		}
		printf("? %lld\n", cur);
		fflush(stdout);
		char ans;
		scanf(" %c", &ans);
		if (ans == 'Y') bot = mid;
		else top = mid;
	}
	int len = bot+1;
	if (len == 11) {
		bot = 0;
		top = 11;
		while (bot + 1 < top) {
			mid = (bot + top) / 2;
			long long cur = 0;
			for (int i = 0; i < mid; i++) {
				cur *= 10;
				cur += 9;
			}
			printf("? %lld\n", cur);
			fflush(stdout);
			char ans;
			scanf(" %c", &ans);
			if (ans == 'Y') top = mid;
			else bot = mid;
		}
		len = bot + 1;
	}
	bot = top = 1;
	for (int i = 0; i < len - 1; i++) bot *= 10;
	for (int i = 0; i < len; i++) top *= 10;
	bot--;
	top--;
	while (bot + 1 < top) {
		mid = (bot + top) / 2;
		printf("? %lld0\n", mid);
		fflush(stdout);
		char ans;
		scanf(" %c", &ans);
		if (ans == 'Y') top = mid;
		else bot = mid;
	}
	printf("! %lld\n", bot + 1);
}


Measured memory_bytes: 596
#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
LL i,j,k,m,n,p,a[200040];
int B(int x,int z)
{
	int s=0,y=x+z>>1;
	if(x<z)
	{
		for(i=0;i++<n;)
		{
			s+=a[i]/y;
		}
		if(s>k)return B(y+1,z);
		else return B(x,y);
	}
	else return y;
}
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(;i++<n;a[i]--)
	{
		cin>>a[i];
		m=max(m,a[i]);
	}
	cout<<B(1,m);
}

Measured memory_bytes: 5152
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rrep(i,n) REP(i,1,n+1)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
typedef vector<ll> Vl;
typedef vector<int> VI;
typedef tuple<int, int, int> TT;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
const int MAX = 500000;
const int inf = 1000000007;
const ll mod = 1000000007;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

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


string s, t;
int cnt;

int main() {

	cin >> s >> t;

	rep(i, s.size()){
		if (s[i] != t[i])cnt++;
	}

	cout << cnt << endl;

	return 0;
}



Measured memory_bytes: 3844
#include <stdio.h>
  
#define MAX 100000
  
void swap(int*,int*);
void Partition(int,int,int*);
  
int main(){
  int n,i,A[MAX];
  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d",&A[i]);
  }
  Partition(0,n-1,A);
  return 0;
}
  
void swap(int *a,int *b){
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
  
void Partition(int l,int r,int *A){
  int x = A[r],i = l,j;
  for(j = l ; j < r ; j++){
    if(A[j] <= x){
      swap(&A[i++],&A[j]);
    }
  }
  swap(&A[i],&A[r]);
  for(j = l ; j <= r ; j++){
    if(j > l){ printf(" "); }
    if(j == i){
      printf("[%d]",A[j]);
    }else{
      printf("%d",A[j]);
    }
  }
  printf("\n");
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef  long long ll;
const int INF = 1e9;

int main() {
  ll a, b, c;
  cin >> a >> b >> c;

  cout << ((4 * a * b < (c - a - b) * (c - a - b) && c - a - b > 0) ? "Yes"
                                                                    : "No")
       << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[]) {

        vector<int> v;

        int query, num,a;
        cin >> num;
        for(int i = 0; i < num; i++) {
                cin >> query;
                switch (query) {
                case 0:
                        cin >> a;
                        v.push_back(a);
                        break;
                case 1:
                        cin >> a;
                        cout << v[a] << endl;
                        break;
                case 2:
                        v.pop_back();
                        break;

                }
        }

        return 0;
}



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

int root(vector<int> v, int start) {
  while (v[start] != -1) {
    start = v[start];
  }
  return start;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> v(N, -1);
  int dups = 0;
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    int rootA = root(v, A - 1);
    int rootB = root(v, B - 1);
    if (rootA != rootB) {
      if (rootA > rootB) v[rootA] = rootB;
      if (rootA < rootB) v[rootB] = rootA;
    } else {
      dups++;
    }
  }
  cout << (N - M - 1 + dups) << endl;
  return 0;
}

Measured memory_bytes: 4060
fun main() {
  val (x, n) = readLine()!!.split(" ").map(String::toInt)
  var p = listOf<Int>()
  if(n!=0) p = readLine()!!.split(" ").map(String::toInt).toList()
  
  if(!p.contains(x)){
    println(x)
    return
  }
  
  for (i in 1 until 100) {
    if (!p.contains(x-i)){
      println(x-i)
      return
    }
    if (!p.contains(x+i)) {
      println(x+i)
      return
    }
  }
}

Measured memory_bytes: 36572
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define NDEBUG
#define debug(...)
#define IFD(...)
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <cassert>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <iostream>
#include <iomanip>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = static_cast<int>(a); i <= static_cast<int>(b); ++i)
#define FORD(i, b, a) for (int i = static_cast<int>(b); i >= static_cast<int>(a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int n;
    i64 m;
    cin >> n >> m;
    vector a_s(n, 0LL);
    rep(i, n)
    {
        cin >> a_s[i];
    }
    sort(a_s.begin(), a_s.end());

    vector sa(n + 1, 0LL);
    copy(a_s.begin(), a_s.end(), sa.begin() + 1);
    rep(i, n)
    {
        sa[i + 1] += sa[i];
    }

    if (m == (i64)n * n)
    {
        cout << 2 * n * sa[n] << '\n';
        return 0;
    }

    // 幸福度 > h なるペアの個数と幸福度の和
    auto cond = [&](i64 h) -> pair<i64, i64> {
        i64 cnt = 0, res = 0;
        int r = 0;
        for (int l = n - 1; l >= 0; --l)
        {
            while (r < n and not (a_s[l] + a_s[r] > h))
            {
                ++r;
            }
            cnt += n - r;
            res += (sa[n] - sa[r]) + (n - r) * a_s[l];
        }
        return {cnt, res};
    };

    // (幸福度 > h なるペアの個数) <= m
    i64 ng = -1, ok = 200'000;
    while (ok - ng > 1)
    {
        auto mid = (ok + ng) / 2;
        auto [cnt, tmp] = cond(mid);
        if (cnt <= m)
        {
            ok = mid;
        }
        else
        {
            ng = mid;
        }
    }
    auto [cnt, res] = cond(ok);
    debug(ng, ok, cnt, res);
    res += (m - cnt) * ok;

    cout << res << '\n';

    return 0;
}


Measured memory_bytes: 4780
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: u32,
        y: u32,
    }
    let na = n;
    for a in 0..=na {
        let va = 10000 * a;
        let nb = na - a;
        if va > y {
            break;
        }
        if va + 5000 * nb < y {
            continue;
        }
        for b in 0..=nb {
            let c = nb - b;
            let vb = va + 5000 * b;
            let vc = vb + 1000 * c;
            if vc > y {
                break;
            }
            if vc == y {
                println!("{} {} {}", a, b, c);
                return;
            }
        }
    }
    println!("-1 -1 -1")
}


Measured memory_bytes: 2140
def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

import sys

input=sys.stdin.readline

N=int(input())
data=[[0 for i in range(20)] for j in range(75)]
for i in range(N):
    n=input().rstrip().split(".")
    if len(n)==1:
        a=int(n[0])
        a*=10**9
        ind2=ind(2,a)
        ind5=ind(5,a)
        data[ind2][ind5]+=1
    else:
        a,b=int(n[0]),int(n[1])
        a=a*10**9+b*10**(9-len(n[1]))
        ind2=ind(2,a)
        ind5=ind(5,a)
        data[ind2][ind5]+=1
    #print(n,"check:{},{}".format(ind2,ind5))

ans=0
for i in range(75):
    for j in range(20):
        for k in range(75):
            for l in range(20):
                if i+k>=18 and j+l>=18:
                    if (i,j)!=(k,l):
                        ans+=data[i][j]*data[k][l]
                    else:
                        ans+=0
                        ans+=data[i][j]**2-data[i][j]

print(ans//2)


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

#define int long long
struct Fast{Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define SIZE(x) ll((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define SUM(x) accumulate(ALL(x), 0)

/* REPmacro*/
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define RREP(i, n) RFOR(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* alias */
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vs = vector<string>;
using str = string;

/* const */
const int INF = 1001001001;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

/* func */
template <typename T = int> inline T in(){T x; cin >> x; return x;}
template <typename T> inline void print(const T& x){cout << x << "\n";}
inline void printvec(const vi& vec){REP(i, SIZE(vec)) cout << vec.at(i) << ((i == SIZE(vec)) ? "\n" : " ");}
inline int lcm(int a, int b){return a / gcd(a, b) * b;}
bool is_prime(int n){if (n < 2) return false;FOR(i, 2, (int)(sqrt(n) + 1)){if (n % i == 0) return false;}return true;}


signed main(){
  int N = in();
  int ans = N * ( N - 1 ) / 2;
  print(ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VI = vector<int>;
using VVI = vector<VI>;
const lint MOD = 1e9 + 7;

map<lint, lint> memo;
lint rec(lint n) {
  if (memo.count(n)) return memo[n];
  lint res = 0;
  if (n % 2) {
    res = 2 * rec(n / 2) + rec(n / 2 - 1);
  } else {
    res = rec(n / 2) + 2 * rec(n / 2 - 1);
  }
  return memo[n] = res % MOD;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  lint n; cin >> n;
  memo[-1] = 0;
  memo[0] = 1;
  cout << rec(n) << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }


int modpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y % 2) res = 1LL * res * x % inf;
        y >>= 1;
        x = 1LL * x * x % inf;
    }
    return res;
}
 
int comb(int n, int k) {
    int ans = 1;
    for (int i = 1; i <= k; i++) {
        ans = 1LL * ans * (n+ 1 - i) % inf;  // *=n!/(n-k)!
        ans = 1ll *ans * modpow(i, inf - 2) % inf;// *=inv k!
    }
 
    return ans;
}
int main(){
  int n,a,b;
  cin>>n>>a>>b;
 // cout<<comb(n,3)<<endl;
 int ans=modpow(2,n)-1-comb(n,a)-comb(n,b);
  if(ans<=0)ans+=inf;
  if(ans<=0)ans+=inf;
  if(n==2)ans=0;
  cout<<ans<<endl;
}

Measured memory_bytes: 3600
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<assert.h>
#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<double> VD;
typedef pair<int, int> P1;
typedef long long int ll;

//number
#define INF 1e9
#define NUM 1000000007

//itr
#define all(x) begin(x),end(x)

//repeat
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

//max,min
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

//function

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

/*ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a * (b / g);
}*/

/*int dig(int a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}*/

//grid template
int x[] = { -1, 0, 1, 0 };
int y[] = { 0,-1,0,1 };
int xx[] = { -1,-1,1,1 };
int yy[] = { 1,-1,1,-1 };


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

  


Measured memory_bytes: 1024
n,m,k = map (int,input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 998244353
N = n-1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

mod = 998244353
ans = 0
#if k <=  n//2:
for i in range(k+1):
    ans += (cmb(n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
print(ans % mod)

Measured memory_bytes: 117572
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#include<bits/stdc++.h>
using namespace std;

#if defined(DAIJOBU)
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}



int main(){
	FIO
	
	vector<int> a;
	int q;
	cin >> q;
	while(q--){
		int op;
		cin >> op;
		if(op == 2)a.pop_back();
		else if(op == 0){
			int el;
			cin >> el;
			a.push_back(el);
		}else{
			int pos;
			cin >> pos;
			cout << a[pos] << '\n';
		}
	}
	return 0;
}



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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 1e5 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-12;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m;
	cin >> n >> m;
	ll d = 1;
	for(int i = 0; i < m; i++) d *= 2;
	cout << (100 * (n - m) + m * 1900) * d;
	return 0;
}


/*
6  3
1  1  3  3  3  5
10  2  3
                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/




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

using namespace std;
using ll = long long;

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

int main() {
  int n, k;
  cin >> n >> k;
  int v[n];
  rep(i, n) cin >> v[i];

  int ans = 0;

  for (int a = 0; a <= min(n, k); ++a) {
    vector<int> g;
    rep(i, a) g.push_back(v[i]);

    for (int b = 0; b <= min(n, k) - a; ++b) {
      vector<int> h;
      copy(g.begin(), g.end(), back_inserter(h));
      rep(i, b) h.push_back(v[n - i - 1]);
      sort(h.begin(), h.end());

      int res = k - (a + b);
      int cur = 0;
      int m = h.size();
      rep(i, min(res, m)) if (h[i] < 0)++ cur;
      int sum = 0;
      while (cur < m) sum += h[cur++];
      ans = max(ans, sum);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3604
#include<cstdio>
#include<cstring>
#include<cmath>
int main()
{
    int n,countn,dec,c;
    int t[100002],x[100002],y[100002];
    while(scanf("%d",&n)!=EOF)
    {
        countn=0;
        t[0]=0;x[0]=0;y[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&t[i],&x[i],&y[i]);
        }
        for(int i=0;i<n;i++)
        {
            dec=x[i+1]+y[i+1]-x[i]-y[i];
            if(dec<0)
                dec=-dec;
            c=t[i+1]-t[i];
            if(c>=dec)
                if((c-dec)%2==0)
                    countn++;
            //printf("dec=%d c=%d countn=%d",dec,c,countn);
        }
        if(countn==n)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,a,b,i,j;
    scanf("%lld%lld%lld",&n,&a,&b);
    if(a==b)
    {
        cout<<1<<endl;
    }
    else if(b<a)
    {
        cout<<0<<endl;
    }
    else if(n==1)
    {
        cout<<0<<endl;
    }
    else
    {
        long long int c=((b-a)*(n-2))+1;
        cout<<c<<endl;
    }
    return 0;
}


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

int main(){
   int n;
   cin >> n;
   
   set<string> s;
   rep(i, n) {
       string t; cin >> t;
       s.insert(t);
   }
   cout << s.size() << endl;
   
}


Measured memory_bytes: 19232
require 'prime'
m = 10000
cache = Prime.each(m).each_cons(2).select {|a,b|
		b-a == 2
}.reverse

while (n = gets.to_i)!=0
	p1,q1 = cache.bsearch {|_,q|
		n >= q
	}
	puts "#{p1} #{q1}" 
end

Measured memory_bytes: 6244
#pragma region head
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    using vi = vector<int>;
    using vll = vector<ll>;
    using pi = pair<int, int>;
    using pll = pair<ll,ll>;
    template <class T> using vv = vector<vector<T>>;
    #define rep(i,n) for(int i = 0; i < (int)(n); i++)
    #define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
    #define rrep(i,n) for(int i = (int)(n)-1; i >= 0; i--)
    #define rrepi(i,a,b) for(int i = (int)(b)-1; i >= (int)(a); i--)
    #define all(x) (x).begin(), (x).end()
    #define bit(n) (1LL<<(n))
    const int INF = 1002003004;
    const ll LINF = 1002003004005006007ll;
    struct preprocess{preprocess()
    {cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}}____;
#pragma endregion head

#pragma region library
#pragma endregion library

int main(){
    string s; cin >> s;
    int n = s.length();
    int l = 0,r = n,m = (n-1)/2;
    char sm = s[m];
    repi(i,m,n){
        if(s[i]!=sm) {r = i;break;}
    }
    rrepi(i,0,m){
        if(s[i]!=sm) {l = i+1;break;}
    }
    cout << min(n-l,r) << '\n';
    
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 1e6 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const long long LINF = 1e18 + 3141;
const long long MAXL = 1e18;
void solve(){
    ll a;
    long double b;
    cin >> a >> b;
    long long ans = a * b;
    cout << ans;
}

 
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}


Measured memory_bytes: 3752
#include<stdio.h>

int main(void){
  long long a,b,c,k;
  
  scanf("%lld %lld %lld %lld",&a,&b,&c,&k);
  
  if( k%2 == 0 ) printf("%lld\n",a-b);
  else           printf("%lld\n",b-a);
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0; i<(long long)(n); i++)
#define REP(i, k, n) for(long long i=(long long)(k); i<(long long)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define PQ(T) priority_queue<T>
#define PQS(T) priority_queue<T, vector<T>, greater<T> >
#define deci cout << fixed << setprecision(15);
typedef long long ll;
const ll inf = 1020304050607080910;
const int mod = 1000000007;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x,ll y){if(x>y)swap(x, y);while(x!=0){y%=x;swap(x, y);}return y;}
ll mpow(ll x,ll r){if(r==0)return 1;if(r%2==1){return x*mpow(x,r-1)%mod;}else{ll aa=mpow(x,r/2);return aa*aa%mod;}}

int main(){
	string S;
	int K;
	cin >> K >> S;
	if(S.size() <= K){
		cout << S << endl;
	}else{
		rep(i, K) cout << S[i];
		cout << "..." << endl;
	}
	return 0;
}


Measured memory_bytes: 3628