akhauriyash/Code-Regression huggingface dataset:
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    ll x;
    cin>>x;
    int t=0;
    ll a=100;
    while(a<x){
        a=(a+a/100);
        t++;
    }
    cout<<t;
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <algorithm>

using namespace std;

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

    int num = 1;

    for(int i = 0; i < N; i++){
        if(num < K){
            num *= 2;
        }else{
            num += K;
        }
    }

    cout << num << endl;

    return 0;
}


Measured memory_bytes: 256
S = input()
if S == "MON":
  print(6)
elif S == "TUE":
  print(5)
elif S == "WED":
  print(4)
elif S == "THU":
  print(3)
elif S == "FRI":
  print(2)
elif S == "SAT":
  print(1)
else:
  print(7)

Measured memory_bytes: 2940
s = input()
ans = 0
p = -1
i = 0
while i-p<len(s):
  if s[i]==s[p]:
    i += 1
    p -= 1
    continue
  elif s[i]=='x':
    i += 1
    ans += 1
  elif s[p]=='x':
    p -= 1
    ans += 1
  else:
    print(-1)
    break
else:
  print(ans)

Measured memory_bytes: 3316
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  string S;
  cin>>S;
  int rnum = 0;
  for(int i=0;i<N;++i) {
    if(S[i]=='R') rnum++;
  }
  int ans = 0;
  for(int i=0;i<rnum;++i) {
    if(S[i]=='W') ans++;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n;
    cin>>n;
    if(n>=400 && n<=599)
    {
        cout<<8<<endl;
    }
    else if (n>=600 && n<=799)
    {
        cout<<7<<endl;
    }
    else if (n>=800 && n<=999)
    {
        cout<<6<<endl;
    }
    else if (n>=1000 && n<=1199)
    {
        cout<<5<<endl;

    }
    else if (n>=1200 && n<=1399)
    {
        cout<<4<<endl;
    }
    else if (n>=1400 && n<=1599)
    {
        cout<<3<<endl;
    }
    else if (n>=1600 && n<=1799)
    {
        cout<<2<<endl;
    }
    else if (n>=1800 && n<=1999)
    {
        cout<<1<<endl;
    }
}


Measured memory_bytes: 3516
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			int M = sc.nextInt();
			Log[] logs = new Log[M];
			for (int i = 0; i < M; ++i) {
				int t = Integer.parseInt(sc.next());
				int s = Integer.parseInt(sc.next()) - 1;
				int d = Integer.parseInt(sc.next()) - 1;
				logs[i] = new Log(t, s, d);
			}
			Arrays.sort(logs);
			BitSet v = new BitSet(N);
			v.set(0);
			for (int i = 0; i < M; ++i) {
				if (v.get(logs[i].s)) v.set(logs[i].d);
			}
			System.out.println(v.cardinality());
		}
	}

	static class Log implements Comparable<Log> {
		int t, s, d;

		public Log(int t, int s, int d) {
			this.t = t;
			this.s = s;
			this.d = d;
		}

		public int compareTo(Log o) {
			return this.t - o.t;
		}
	}
}

Measured memory_bytes: 114412
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

priority_queue<ll, vector<ll>, greater<ll> > pq1; // min heap
priority_queue<ll> pq2;                           // max heap
ll a[333333], prefix1[333333], prefix2[333333];

int main(void)
{
    ll n, i;

	scanf("%lld" ,&n);
	for (i = 1; i <= 3 * n; i++)
		scanf("%lld" ,&a[i]);

	for (i = 1; i <= 2 * n; i++)
	{
		pq1.push(a[i]);
		prefix1[i] = prefix1[i - 1] + a[i];

		if (i > n)
		{
			prefix1[i] -= pq1.top();
			pq1.pop();
		}
	}

    for (i = n * 3; i >= n + 1; i--)
	{
		pq2.push(a[i]);
		prefix2[i] = prefix2[i + 1] + a[i];

		if (i < 2 * n + 1)
		{
			prefix2[i] -= pq2.top();
			pq2.pop();
		}
	}

	ll ans = -(1LL << 60);
    for (i = n; i <= 2 * n; i++)
        ans = max(ans, prefix1[i] - prefix2[i + 1]);

	printf("%lld" ,ans);
	return 0;
}

Measured memory_bytes: 8692
landform = [c for c in input()]
down = []
areas = []

for i in range(len(landform)):
    if landform[i] == '\\':
        down.append(i)
    if landform[i] == '/':
        if down:
            pair = down.pop()
            area = i - pair
            while areas and areas[-1][0] > pair:
                area += areas.pop()[1]
            areas.append([pair, area])

sum_area = 0
for area in areas:
    sum_area += area[1]
print(sum_area)

ans = []
ans.append(str(len(areas)))
ans += [str(area[1]) for area in areas]

print(' '.join(ans))



Measured memory_bytes: 6620
cards = [[False for i in range(13)] for j in range(4)]
pattern = ["S", "H", "C", "D"]

N=int(input())
i=0
while i<N:
    gara,num=input().split()
    num=int(num)
    cards[pattern.index(gara)][num-1] = True
    i+=1
for i in range(4):
    for j in range(13):
        if cards[i][j] == False:
            print(pattern[i], j+1)
    


Measured memory_bytes: 5604
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define MOD 998244353 
 
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
ordered_set<ll> ors;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ld PI=3.14159265359;
 
ll power(ll a, ll n, ll m)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(ans*a)%m;
        n>>=1;
        a=(a*a)%m;
    }
    return ans;
}
 
ll invmod(ll a, ll m)
{
    return power(a,m-2,m);
}
 
ll lp[1000001];
vector<ll> pr;
 
void prime()
{
    repf(i,1,1000001) lp[i]=i;
    repf(i,2,1000001)
    {
        if(lp[i]==i)
        {
            for(ll j=2*i;j<1000001;j+=i)
            {
                if(lp[j]==j) lp[j]=i;
            }
        }
    }
    // repf(i,2,1000001) if(lp[i]==i) pr.pb(i);
}

const ll MX=200001;

vector<ll> v[MX];
ll depth[MX];
ll D[MX][22];
 
void dfs(ll x, ll p, ll h=0) {
    D[x][0]=p;
    depth[x]=h;
    repf(i,1,22)
    {
        if(D[x][i-1]!=-1 && D[D[x][i-1]][i-1]!=-1)
        {
            D[x][i]=D[D[x][i-1]][i-1];
        }
    }
    for(auto i:v[x]) {
        if(i==p) continue;
        dfs(i,x,h+1);
    }
}

ll walk(ll x, ll k)
{
    repf(i,0,22)
    {
        if((1<<i)&k)
        {
            x=D[x][i];
        }
    }
    return x;
}

ll lca(ll x, ll y)
{
    if(depth[x]>depth[y]) x=walk(x,depth[x]-depth[y]);
    if(depth[y]>depth[x]) y=walk(y,depth[y]-depth[x]);
    if(x==y) return x;
    repb(i,21,0)
    {
        if(D[x][i]!=D[y][i])
        {
            x=D[x][i];
            y=D[y][i];   
        }
    }
    return D[x][0];
}

void init() {
    prime();
}

void solve(ll tt) {
   ll n,x,m;
   cin>>n>>x>>m;
   bool vis[m]={false};
   vector<ll> v;
   ll sum=0;
   while(v.size()<n && !vis[x]) {
       v.pb(x);
       vis[x]=true;
       sum+=x;
       x=(x*x)%m;
   }
   ll ans=sum;
   ll sz=v.size();
   if(sz==n) {
       cout<<ans<<endl;
       return;
   }
   vector<ll> vtmp;
   sum=0;
   repf(i,0,sz) {
       if(v[i]==x) {
           repf(j,i,sz) sum+=v[j],vtmp.pb(v[j]);
           break;
       }
   }
//    cout<<sz<<endl;
   ll rem=n-sz;
   ll times=rem/vtmp.size();
   ll rr=rem%vtmp.size();
   ans+=sum*times;
   repf(i,0,rr) ans+=vtmp[i];
   cout<<ans<<endl;

} 
 
 
int main()
{
    // IOS;
    init();
    ll t=1;
    // cin>>t;
    repf(tt,1,t+1) {
        solve(tt);
    }
}     

Measured memory_bytes: 16892
#include "bits/stdc++.h"
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define ld           long double
#define vi           vector<int>
#define pii          pair<int,int>
#define pb           push_back
#define mp           make_pair
#define ff           first
#define ss           second
#define endl         '\n'
#define rep(i,s,e)   for(int i=(s);i<=(e);i++)
#define brep(i,s,e)  for(int i=(s);i>=(e);i--)
#define all(x)       (x).begin(),(x).end()
#define ball(x)      (x).rbegin(),(x).rend()
#define sz(x)        (int)x.size()
#define mem(x,y)     memset(x,(char)y,sizeof(x))
#define milf(x)      x.reserve(1LL<<14LL); x.max_load_factor(0.25); // less_equal
#define pbds         tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
mt19937              rng(chrono::steady_clock::now().time_since_epoch().count());
#define int          long long
const int INF = 0x3F3F3F3F3F3F3F3F;
const int MOD = 1e9+7;
ld EPS = 1e-12;


short rain()
{
    // int t;cin>>t;rep(test,1,t)
    {
        int n, m, k;
        cin >> n >> m >> k;
        vi a(n), b(m);
        for(auto &i:a)
            cin >> i;
        for(auto &i:b)
            cin >> i;
        // reverse( all(a) );
        // reverse( all(b) );
        int psm[m+1];
        psm[0] = 0;
        rep(i,1,m)
        {
            psm[i] = psm[i-1];
            psm[i] += b[i-1];
        }
        int ans = 0;
        rep(i,-1,n-1)
        {
            if( i>=0 )
                k -= a[i];
            if( k<0 )
                break;
            int LO = 0, HI = m, v = 0;
            while( LO<=HI )
            {
                int M = (LO+HI) >> 1LL;
                if( psm[M]<=k )
                    v = M, LO = M+1;
                else
                    HI = M-1;
            }
            ans = max( ans, i+1+v );
        }
        cout << ans << endl;
    }

    return 0;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("ip.txt","r",stdin);
    // freopen("op.txt","w",stdout);
    int tt = 1000*clock()/CLOCKS_PER_SEC;
    cout<<fixed<<setprecision(15);rain();
    cerr<<1000*clock()/CLOCKS_PER_SEC-tt<<"ms\n";
}

Measured memory_bytes: 8008
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin >> N;

    int res;

    int MAX = 0;

    int val = 1;

    for (int i = 1; i <= N; i++)
    {
        res =0;

        int k = i;
        while (true)
        {
            if (k % 2 == 0)
            {
                k = k / 2;
                res++;
            }
            else
            {
                break;
            }
        }
        if (MAX < res)
        {
            MAX = res;
            val = i;
        }
    }

    cout << val << endl;

    return 0;
}

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

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

	if(n%2 == 0) cout << 0.5 << endl;
	else cout << (double)((n+1)/2) / n << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;



int main()
{
	int N, A;
	map<int, bool> mp;
	bool ans = true;

	cin >> N;
	rep(i, N) {
		cin >> A;
		if (mp.count(A) > 0) ans = false;
		mp[A] = true;
	}

	cout << (ans ? "YES" : "NO") << endl;

	return 0;
}


Measured memory_bytes: 9600
using namespace std;

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

#define int long long
#define double long double
typedef pair<int, int> ii;
typedef vector<int> vi;

int n;
int t[102];
int v[102];
int dp[252][50003];
int tab[50003];
int sum;
//double x[102];
//double speed[102];
int INF = 1000000000;

int compute(int time, int speed) {
    if (speed < 0 || speed > 200) return -INF;
    if (time == sum) {
        if (speed == 0) return 0;
        else return -INF;
    }
    if (dp[speed][time] != -1) return dp[speed][time];
    int index = tab[time];
    if (speed > v[index]) return -INF;
    
    int ans = -INF;
    if (speed < v[index]) ans = max(ans, compute(time + 1, speed + 1));
    ans = max(ans, compute(time + 1, speed));
    if (speed > 0) ans = max(ans, compute(time + 1, speed - 1));
    ans += speed;
    //printf("%lld %lld %lld: %lld\n", index, speed, time, ans);
    return dp[speed][time] = ans;
}
/*
double maxSpeed(double speed, int index) {
    double ans = (double) min(speed + t[index], (double) v[index]);
    int cnt = 0;
    for (int i = index + 1; i < n; i++) {
        cnt += t[i - 1];
        x[index] = min(x[index], cnt - ans + v[i]);
    }
    cnt = 0;
    for (int i = index + 1; i < n; i++) {
        cnt += t[i - 1];
        double tmp = (cnt + speed + v[i]) / 2.;
        if (tmp < ans) {
            ans = tmp;
            x[index] = tmp - speed;
        }
    }
    return ans;
} */

signed main() {
    //freopen("out.txt", "w", stdout);
    scanf("%I64d", &n);
    sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%I64d", &t[i]);
        t[i] *= 2;
        //x[i] = (double) INF;
        for (int j = sum; j < sum + t[i]; j++) {
            tab[j] = i;
        }
        sum += t[i];
    }
    for (int i = 0; i < n; i++) {
        scanf("%I64d", &v[i]);
        v[i] *= 2;
    }
    
    for (int i = 0; i <= 251; i++) {
        for (int j = 0; j <= 50001; j++) {
            dp[i][j] = -1;
        }
    }
    /*
    t[n] = 0; v[n] = 0;
    n++; */
    
    /*
    for (int i = 0; i < n; i++) {
        speed[i] = maxSpeed((i == 0) ? 0: min(speed[i - 1], (double) v[i]), i);
    }
    
    double ans = 0; */
    
    /*for (int i = 0; i < n; i++) {
        cout << speed[i] << " " << x[i] << "\n";
    } */
    
    /*
    double curSpeed = 0;
    for (int i = 0; i < n - 1; i++) {
        double diff = speed[i] - curSpeed;
        if (diff > 0) ans += diff * diff / 2. + curSpeed * diff; // first triangle
        curSpeed = speed[i];
        //cout << ans << "\n";
        if (min(x[i], (double) t[i]) > diff) {
            ans += (min(x[i], (double) t[i]) - diff) * speed[i]; // second triangle
        }
        //cout << ans << "\n";
        if (x[i] < t[i]) {
            ans += (t[i] - x[i]) * (t[i] - x[i]) / 2. + (t[i] - x[i]) * (speed[i] - (t[i] - x[i]));
            curSpeed = curSpeed - (t[i] - x[i]);
        }
        //cout << ans << "\n";
    } */
    
    printf("%.20lf\n", compute(0, 0) / 4.);
}


Measured memory_bytes: 100864
r, D, x_2000 = gets.chomp.split(" ").map(&:to_i)

x_2001to2010 = [x_2000]

for i in 1..10 do
  x_2001to2010[i] = x_2001to2010[i-1] * r - D
  puts x_2001to2010[i]
end


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

using namespace std;

long long arr[100002];

int main(){
    long long n, ans = 0;
    cin >> n;
    for(long long i = 0; i < n; ++i){
        long long tmp; cin >> tmp;
        arr[tmp]++;
    }
    for(long long i = 1; i < 100000; ++i){
        ans = max(ans, arr[i - 1] + arr[i] + arr[i + 1]);
    }
    cout << ans;
    return 0;

}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int INF = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < 2*n; ++i) {
        int a;
        cin >> a;
        v.emplace_back(a);
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += v[i*2];
    }
    cout << ans << "\n";
    return 0;
}


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

int main(){
    int N;
    cin>>N;
    if(65<=N&&N<=90){
        cout<<"1"<<endl;
    }else if(97<=N&&N<=122){
        cout<<"2"<<endl;
    }else{
        cout<<"0"<<endl;
    }
    return 0;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const ll INF = 1LL << 60;


int main() {
    int n; cin >> n;
    V<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    V<ll> sums(n + 1);
    for(int i = 0; i < n; i++){
        sums[i + 1] = sums[i] + a[i];
    }

    ll ans = INF;
    for(int i = 1; i <= n; i++){
        ll x = sums[i];
        ll y = sums[n] - sums[i];
        ans = min(ans, abs(y - x));
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 6432
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	int n;
	cin>>n;
	REP(i, n) {
		int out = 0;
		int score = 0;
		vector<bool> rui(3, false);
		while(out < 3) {
			string hoge;
			cin>>hoge;
			if(hoge == "HIT") {
				if(rui[2]) {
					++score;
				}
				for(int j = 1; j >= 0; --j) {
					rui[j + 1] = rui[j];
				}
				rui[0] = true;
			} else if (hoge == "OUT") {
				++out;
			} else if(hoge == "HOMERUN") {
				score++;
				REP(j, 3) {
					if(rui[j]) ++score;
					rui[j] = false;
				}
			}
		}
		cout<<score<<endl;
	}
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first 
#define S second
#define int unsigned long long

int32_t main(){
	int n, ans = 0;
	cin >> n;
	int a[n];
	map <int, int> mp; 
	for (int i = 0; i < n; i++){
		cin >> a[i];
		mp[a[i]] ++;
	}
	for (int i = 1; i <= n; i++){
		ans += (mp[i] * (mp[i] - 1)) / 2;
	}
	//cout << ans << endl;
	for (int i = 0; i < n; i++){
		cout << ans - (mp[a[i]] - 1) << endl;
	}
}


Measured memory_bytes: 16640
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int x=0;
		if(a == b){
			x++;
		}
		if(a == c){
			x++;
		}
		if(b == c){
			x++;
		}
		if(x == 3){
			System.out.println(1);
		}else{
			System.out.println(3-x);
		}
		
	}

}

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int INF = 1000000;
const double PI=3.14159265359;
ll dp[1100][1100]={0};

int main(){

  ll h,w;cin>>h>>w;
  string a[h];rep(i,0,h)cin>>a[i];

  dp[0][0]=1;

  rep(i,0,h){
    rep(j,0,w){
      if(IN(0,h,i+1)&&a[i+1][j]=='.'){
        dp[i+1][j]+=dp[i][j];
        dp[i+1][j]%=mod;
      }
      if(IN(0,w,j+1)&&a[i][j+1]=='.'){
        dp[i][j+1]+=dp[i][j];
        dp[i][j+1]%=mod;
      }

    }
  }

  out(dp[h-1][w-1]);

  return 0;
}


Measured memory_bytes: 9856
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: u32 = read();
    let K: usize = read();
    println!("{}", K * (K - 1).pow(N - 1))
}


Measured memory_bytes: 2084
#include <stdio.h>

#define MAX 100000

typedef struct
{
  char name[10];
  int time;
}Process;

Process p[MAX];

int head=0,tail=0;

int main()
{
  int n,qt,pt,t=0,i;
  Process A;

  scanf("%d%d",&n,&qt);

  for(i=0;i<n;i++)
    {
      scanf("%s",p[i].name);
      scanf("%d",&p[i].time);
    }

  tail=n;
  
  while(head!=tail)
    {
      pt=p[head].time;
      p[head].time-=qt;
      if(p[head].time<=0)
	{
	  t+=pt;
	  printf("%s %d\n",p[head].name,t);
	  if( (head+1)==MAX )
	    {
	      head = 0;
	    }
	  else head++;
	}
      else
	{
	  t+=qt;
	  A=p[head];
	  if( (head+1)==MAX )
	    {
	      head = 0;
	    }
	  else head++;
	  p[tail]=A;
	  if(tail+1==MAX)tail=0;
	  else tail++;
	}
    }
  
  return 0;
}





Measured memory_bytes: 3304
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    ll N;
    cin >> N;
    ll ans = 0;
    for (ll i = 1; i*i <= N; ++i) {
        if (N%i)continue;
        ll j = N / i;
        if (i < j - 1) {
            ans += j - 1;
        }
    }
    cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
const int MAXN = 2005;
int n,k;
bitset<10005>legal[MAXN];
char s[MAXN][10005];
char opt[10005],t[20005];
int anslen;
int ext[20005],len[2005],tlen;
struct Node{
	int x,y;
};
inline int cmp(Node a,Node b)
{
	if(!a.y && !b.y)return 0;
	int p=a.x+a.y;
	if(!a.y || !b.y){
		if(a.x>=b.x)return 0;
		if(b.y)return -cmp(b,a);
		int len=ext[p];
		if(a.x+len>=b.x)return 0;		
		else return t[ext[p]]<t[p+ext[p]] ? 1 : -1;
	}
	if(a.x==b.x)return 0;
	if(a.x>b.x)return -cmp(b,a);
	int len=ext[p];
	if(a.x+len<b.x)return t[ext[p]]<t[p+ext[p]] ? 1 : -1;
	p=b.x-a.x;
	len=ext[p];
	if(b.x+len>=a.x+a.y)return 0;
	return t[ext[p]]<t[p+ext[p]] ? -1 : 1;
}
bool operator < (const Node &a,const Node &b)
{
	return cmp(a,b)>0;
}
bool operator == (const Node &a,const Node &b)
{
	return cmp(a,b)==0;
}
inline void exkmp()
{
	ext[0]=tlen;
//	cout<<tlen<<endl;
	int k=0,p;
	while(k+1<tlen&& t[k+1]==t[k])++k;
	ext[1]=k;
	p=1;
	for(int i=2;i<tlen;++i){
		int len=ext[i-p];
		if(i+len<p+ext[p])ext[i]=len;
		else {
			int j=p+ext[p]-i;
			j=max(0,j);
			while(i+j<tlen && t[i+j]==t[j])++j;
			ext[i]=j;
			p=i;
		}
	}
}
Node stk[100005];
bool ok[100005];
int top;
int main()
{	
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%s",s[i]),len[i]=strlen(s[i]);
	legal[n+1][0]=1;
	for(int i=n;i;--i){
		legal[i]|=(legal[i+1]<<len[i]);
		legal[i]|=legal[i+1];
	}
	ok[0]=true;
	anslen=0;
	for(int i=1;i<=n;++i){
/*		cout<<"Now  "<<i<<endl;
		cout<<len[i]<<" "<<anslen<<endl; */
//		cout<<"Nowbest:   ";
//		for(int j=0;j<anslen;++j)cout<<opt[j];
//		cout<<endl;
		for(int j=0;j<len[i];++j)t[j]=s[i][j];
		for(int j=0;j<anslen;++j)t[j+len[i]]=opt[j];
		t[anslen+len[i]]='\0';		
		tlen=anslen+len[i];
//		cout<<tlen<<endl;
		exkmp();
//		cout<<"entered"<<endl;
//		cout<<opt<<endl;
//		for(int i=0;i<=opt.size();++i)
//			cout<<is[i];
//		cout<<endl;
		top=0;
		for(int j=0;j<=anslen && j<=k;++j){
			if(ok[j] && legal[i+1][k-j]){
				Node now=(Node){j,0};
				while(top>0 && now<stk[top])--top;
				if(!top || now==stk[top])stk[++top]=now;
			}
//				int sta=cmp(i,j+len[i]);				
//				cout<<sta<<" ";
				
/*				if(sta==1 || j==anslen){
					if(sta==1){		
						for(int k=j+1;k<=anslen;++k)is[k]=0;
						for(int k=j;k<j+len[i];++k)opt[k]=s[i][k-j];
						anslen=j+len[i];
						is[anslen]=1;
						flag=true;					
					}else{
						lastpos=j;
						is[j+len[i]]=1;
					}
					break;
				}else if(sta==-2){
					is[j+len[i]]=true;
				}else if(sta==-1){
					lastpos=j;
					is[j+len[i]]=1;
				}
*/
			
		}
		for(int j=0;j<=anslen && j+len[i]<=k;++j){
			if(ok[j] && legal[i+1][k-j-len[i]]){						
				Node now=(Node){j,len[i]};
				while(top>0 && now<stk[top])--top;
				if(!top || now==stk[top])stk[++top]=now;

			}
		}
//		cout<<endl;
		if(!top)continue;	   
		if(stk[top].y){
			for(int j=0;j<stk[top].y;++j)opt[stk[top].x+j]=s[i][j];
		}		
		for(int i=0;i<=anslen;++i)ok[i]=0;
		anslen=stk[top].x+stk[top].y;
		for(int i=1;i<=top;++i)
			ok[stk[i].x+stk[i].y]=true;
	}	
	for(int i=0;i<anslen;++i)
		printf("%c",opt[i]);
	puts("");
	return 0;
}


Measured memory_bytes: 22016
#include<stdio.h>
#include<omp.h>

#pragma omp parallel

int main(){
 
    int n;
    scanf("%d",&n);
    int a[n];
    int rain[n+1];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        rain[i]=0;
    }
    

    int sum=0;
    for(int i=0;i<n;i++){
        if(i%2==0){
            sum+=a[i];
        }else{
            sum-=a[i];
        }
    }
    rain[n]=sum;

    for(int i=n-1;i>=0;i--){
        rain[i]=2*a[i]-rain[i+1];
    }
    //
/*
    for(int i=0;i<n;i++){
        rain[i] = sum;

        for(int j=i+1;j<n+i;j+=2){
            rain[i]-=2*a[j%n];
        }

        if(rain[i]<0){
            rain[i]=rain[i]*(-1);
        }
    }
    */
    for(int i=0;i<n;i++){
        printf("%d ",rain[i]);
    }
    printf("\n");
    
    return 0;
}

Measured memory_bytes: 2048
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue>

#define N 300005
#define M 8000005

#define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1)

#define mk make_pair
#define pb push_back
#define fi first		
#define se second

using namespace std;

int fa[N],t[N];

long long size[N]; 

struct Node{
		int x,y,w;
}B[N];

int i,j,m,n,p,k;

int cmp(Node a,Node b)
{
		return a.w<b.w;
}

int get(int x)
{
		return fa[x]==x?x:fa[x]=get(fa[x]);
}

int main()
{
		scanf("%d%d",&n,&m);
		for (i=1;i<=n;++i) scanf("%lld",&size[i]);
		for (i=1;i<=m;++i) scanf("%d%d%d",&B[i].x,&B[i].y,&B[i].w);
		sort(B+1,B+m+1,cmp);
		for (i=1;i<=n;++i) fa[i]=i;
		for (i=1;i<=m;++i)
		{
				int x=get(B[i].x),y=get(B[i].y);
				if (x==y)
				{	
					if (B[i].w<=size[x]) ++p;
					else t[x]++;
				}
				else
				{
						fa[y]=x;
						t[x]+=t[y];
						size[x]+=size[y];
						t[x]++;
						if (B[i].w<=size[x]) p+=t[x],t[x]=0;
				}
		}
		printf("%d\n",m-p);
}

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

int main()
{
    int n,k;
    std::cin>>n>>k;
    std::vector<int> h(n);
    for(int i=0;i<n;i++)std::cin>>h[i];
    int res = 0;
    for(int i=0;i<n;i++){
        if(h[i]>=k)res++;
    }
    std::cout<<res<<std::endl;
}


Measured memory_bytes: 640
#import sys
#input = sys.stdin.readline
n = int(input())
l = [d for d in input()]
k = set(l[:-2])
c = 0
for kk in list(k):
    i = l[:-2].index(kk)
    o = set(l[i + 1:-1])
    for oo in list(o):
        ii = l[i + 1:-1].index(oo) + (i + 1)
        p = set(l[ii + 1:])
        c += len(p)
print(c)


Measured memory_bytes: 91632
#include<stdio.h>

void quicksort(int data[],int left,int right);

int main()
{
    int n,k,i,j,test,data[100010]={0},min=2100000000;
	scanf("%d %d",&n,&k);
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&(data[i]));
	}
	quicksort(data,0,n-1);//降順
	
	for(j=0;j<=(n-k);j++)
	{
		test=data[j]-data[j+k-1];
		if(test<min)min=test;
	}
	printf("%d",min);
}


void quicksort(int data[],int left,int right)
{
	int i,j;
	int std,work;
	if(left<right)
	{
		i=left,j=right;
		std=data[(i+j)/2];//基準
		do
		{
			while(data[i] > std)i++;
			while(data[j] < std)j--;
			if(i<=j)
			{
				if(i<j)
				{
					work=data[i];
					data[i]=data[j];
					data[j]=work;
				}
				i++; j--;
			}
		}while(i<=j);
		if(left<j)quicksort(data,left,j);
		if(i<right)quicksort(data,i,right);
	}
}

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

int fib[44],n;
int main() {
  fib[0] = 1;
  fib[1] = 1;
  for (int i = 1; i <= 44; ++i) {
	if (i >= 2) fib[i] = fib[i-1] + fib[i-2];
	}
	cin >> n;
	cout << fib[n] << endl;
	}

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

long long gcd(long long a, long long b){
    if (b == 0) return a;
    else return gcd(b, a%b);
}

int main(){
    int N;
    cin >> N;
    long long t;
    cin >> t;
    for (int i = 1; i < N; i++) {
        long long u;
        cin >> u;
        long long g = gcd(t, u);
        t = t / g * u;
    }
    cout << t << "\n";
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
l=[0 for i in range(n)]
for x in a:
    l[x] += 1
p = [(0 if i % 2 == 0 else 2) for i in range(n // 2 * 2)]
if n % 2 == 1: p = [1] + p
if l != p:
    print(0)
    import sys
    sys.exit()


def mod_power(x, a, p):
    if a == 0:
        return 1
    t = mod_power(x, a // 2, p)
    if a % 2 == 0:
        return t * t % p
    else:
        return x * t * t % p

ans = 1
# for i in range(n // 2):
#     ans *= 2
#     ans %= 10 ** 9 + 7
# print(ans)
print(mod_power(2,n//2,10**9+7))


Measured memory_bytes: 14008
n = int(input())
a = [int(m) for m in input().split()]
ans = 1
vector = 0
for i in range(1, n):
    if i == 1:
        if a[i - 1] < a[i]:
            vector = 1
        elif a[i - 1] > a[i]:
            vector = -1
    else:
        if vector == 0:
            if a[i - 1] < a[i]:
                vector = 1
            elif a[i - 1] > a[i]:
                vector = -1
        elif vector == 1:
            if a[i - 1] > a[i]:
                vector = 0
                ans += 1
        elif vector == -1:
            if a[i - 1] < a[i]:
                vector = 0
                ans += 1
print(ans)

Measured memory_bytes: 14480
using System;
	using System.Collections.Generic;


class A
{
	public static void Main ()
	{
	

		int n = int.Parse (Console.ReadLine ());
		int tCount = 0;
		int hCount = 0;


		for (int i=0; i<n; i++) {
			string[] s = Console.ReadLine ().Split(' ');

			if (string.Compare (s[0], s[1]) == 0) {
				tCount++;
				hCount++;
			} else if (string.Compare (s[0], s[1]) > 0) {
				tCount = tCount + 3;
			} else {
				hCount = hCount + 3;
			}
		}
		Console.WriteLine (tCount + " " + hCount);
	}
}

Measured memory_bytes: 9848
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 long long function1(string str,int * n)
 {
     int key=0;
     long long int result=0;
     for(int i=0;str[i]!='\0';i++)
     {
         if(key==1)
             *n=*n+1;
         if(str[i]!='.')
         {
            result=result*10+(int)str[i]-'0';
             //cout<<result<<"\n";
         }
         if(str[i]=='.')
             key=1;
     }
     return result;
 }
int main()
{
    int n=0;
   string str1,str2;
    cin>>str1;
    cin>>str2;
    long long int number1=function1(str1,&n),number2=function1(str2,&n);
    number1=number1*number2;
    int multiple=1;
    for(int i=0;i<n;i++,multiple=multiple*10);
    number1=number1/multiple;
    cout<<number1;
}
 
 


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n+1,0);
    rep(i,n){
        cin >> a.at(i+1);
        --a.at(i+1);
    }
    for(i = 0;i < n;++i){
        a.at(i+1) += a.at(i);
        a.at(i+1) %= k;
    }
    map<ll, vector<ll>> spare;
    for(i = 0;i <= n;++i){
        spare[a.at(i)].push_back(i);
    }
    ll ans = 0;
    for(auto x:spare){
        ll m = x.second.size();
        if(m > 1){
            for(i = 0;i < m;++i){
                ll now = x.second.at(i);
                ll ind = lower_bound(all(x.second), now + k) - x.second.begin() - 1;
                ans += ind - i;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 26744
#include <bits/stdc++.h>
using namespace std;
 
int H=1, W=1;
 
int main() {
for (; H*W!=0;) {
    cin >> H >> W;
    if (H*W!=0) {
        for (int i=0; i<W; i++) cout << '#';
        cout << endl;
        for (int i=2; i<H; i++) {
            cout << '#';
            for (int j=2; j<W; j++) cout << '.';
            cout << '#' << endl;
        }
        for (int i=0; i<W; i++) cout << '#';
        cout << endl << endl;
    }
}
}


Measured memory_bytes: 3100
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<stack>
#include<set>
#include<fstream>
#include<map>
#include<vector>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;

int bs(int n) {
	int lb = 0, ub = 114514;
	while (ub - lb > 1) {
		int mi = (lb + ub) / 2;
		if (mi*(mi+1)/2<n)lb = mi;
		else ub = mi;
	}
	return ub;
}

signed main() {
	int n; cin >> n;
	while (n) {
		int a = bs(n);
		cout << a << endl;
		n -= a;
	}
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
public class Test
{
    public static void Main()
    {
        long foo = 0;
        Console.WriteLine("{1}",Console.ReadLine(),new long[]{0}.Concat(Console.ReadLine().Split().Select(s => long.Parse(s))).Select(i=> { foo += i;return foo; }).GroupBy(v=>v).Select(g=>g.LongCount()).Where(i=>i>1).Select(i=>i*(i-1)/2).Sum());
    }
}


Measured memory_bytes: 54556
#include<stdio.h>
long long MIN(long long a,long long b){return a<b?a:b;}
long long MAX(long long a,long long b){return a<b?b:a;}
int main(){
  long long n,m,i,j,s,f=0,d[200010],c[200010];
  scanf("%lld %lld",&n,&m);
  for(i=0;i<n;i++)scanf("%lld",&d[i]);
  while(m--){
    for(i=0;i<n;i++)c[i]=0;
    for(i=0;i<n;i++){
      c[MAX(0  ,i-d[i])  ]++;
      c[MIN(n-1,i+d[i])+1]--;
    }
    for(i=s=f=0;i<n;i++){
      s+=c[i];
      d[i]=s;
      if(s-n)f=1;
    }
    if(f==0)goto END;
  }
 END:;
  for(i=0;i<n;i++)printf("%lld ",d[i]);
  printf("\n");
  return 0;
}



Measured memory_bytes: 4832
/* Bismillahir Rahmanir Rahim */

#include <bits/stdc++.h>

#define rep(i, n)	for(int i=0;i<n;i++)
#define repn(i, n)	for(int i=1;i<=n;i++)
#define set(i, n)	memset(i, n, sizeof(i))

#define pb	push_back
#define f	first
#define s	second

using namespace std;

void scanF(int &x){
    register int c = getchar_unlocked();
    x = 0;
    for(;(c<48 || c>57);c = getchar_unlocked());
    for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
}

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

const int N = 100007;
const int oo = 1e9;

int a[N], n;

int main(){
	scanF(n);
	long long sum = 0;
	rep(i, n) scanF(a[i]);
	rep(i, n) sum += a[i];
	long long ff = n;
	ff = (ff * (ff + 1LL)) / 2LL;
	if(sum % ff != 0LL){
		printf("NO\n");
		return 0;
	}
	int dx = 0, fn = oo + 1;
	rep(i, n) if(a[i] < fn) fn = a[i], dx = i;
	while(1){
		int minus = 0, mn = oo + 1, fx = -1;
		for(int i=dx;i<n;i++){
			minus++;
			a[i] -= minus;
			if(a[i] < mn){
				mn = a[i];
				fx = i;	
			}
		}
		for(int i=0;i<dx;i++){
			minus++;
			a[i] -= minus;
			if(a[i] < mn){
				mn = a[i];
				fx = i;
			}
		}
		if(mn <= 0) break;
		dx = fx;
	}
	int zero = 0;
	for(int i=0;i<n;i++) zero += (a[i] == 0);
	if(zero == n) printf("YES\n");
	else printf("NO\n");
	return 0;
}



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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define repll(i,n) for(ll i = 0; i < n; i++)
#define REPll(i,n) for(ll i = 1; i < n; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n") 
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  int n;
  cin >> n;
  vl a(n), b(n);
  rep(i,n) cin >> a[i] >> b[i];
  reverse(all(a));
  reverse(all(b));
  ll ans = 0;
  rep(i,n){
    a[i] += ans;
    if(a[i] % b[i] == 0) continue;
    ans += b[i] - (a[i] % b[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

map< ll , ll > f;

ll n,p,ans,sum,v;
string s;

ll expBin( ll A , ll B ){
    if( !B ) return 1LL;
    ll myAns = expBin( A , B/2 );
    myAns = (myAns*myAns)%p;
    if( B&1 ) myAns = (myAns*A)%p;
    return myAns;
}

int main()
{

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

    cin >> n >> p >> s;

    if( p==2 || p==5 ){
        for(ll i=0; i<n; i++){
            if( (s[i]-'0')%p == 0 ) ans+=i+1;
        }
        cout << ans;
        return 0;
    }

    f[ 0 ]++;
    for(ll i=0; i<n; i++){
        sum = (sum*10)%p;
        sum = ( sum + s[i]-'0' )%p;
        v = (sum* expBin( expBin( 10 , i%(p-1) ) , p-2 ))%p;
        ans+=f[ v ];
        f[ v ]++;
    }

    cout << ans;

    return 0;
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) ((v).begin(),(v).end())
#define COUT(x) cout<<(x)<<"\n"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin >>n;
    vector<int> a(n),b(n);
    ll sum_a=0,sum_b=0;
    REP(i,n){
        cin >> a[i];
        sum_a+=a[i];
    }
    REP(i,n){
        cin >> b[i];
        sum_b+=b[i];
    }
    int ans=0;
    if(sum_a<sum_b)ans=-1;
    else{
        vector<int> diff;
        ll sum_diff=0;
        REP(i,n){
            if(a[i]<b[i]){
                sum_diff+=(b[i]-a[i]);
                ans++;
            }
            else if(a[i]>b[i]){
                diff.emplace_back(a[i]-b[i]);
            }
        }
        sort(diff.begin(),diff.end(),greater<>());
        if(ans!=0){
            for(int x:diff){
                sum_diff-=x;
                ans++;
                if(sum_diff<=0)break;
            }
        }
    }
    COUT(ans);
    return 0;
}

Measured memory_bytes: 1536
package main

import "fmt"

func solve() int {
	var N, X int
	fmt.Scan(&N, &X)

	cnt := 0
	for i := 0; i < N; i++ {
		var L int
		fmt.Scan(&L)
		cnt += L
		if X < cnt {
			return i + 1
		}
	}
	return N + 1
}

func main() {
	ans := solve()
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int a[2000];
int check(int n)
{
	int last=-1;
	while(n)
	{
		int x=n%10;
		if(last==-1||x==last-1)
		last=x;
		else
		return 0;
		n/=10;
	}
	return 1;
}
int main()
{
	int n,ans=-1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(check(a[i]*a[j]))
				ans=max(ans,a[i]*a[j]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3224
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define bitcnt(v) __builtin_popcount(v)
#define all(v) v.begin(), v.end()

int n, mod = 1e9 + 7;; 
vector<vector<int>> graph;
ll dp[100003][2];
// B -- W
// W -- B/W

// state only depends on which vertex we are at and whether its parent is colored black

ll solve(int u, int p, bool p_black){
	if(dp[u][p_black] != -1) return dp[u][p_black];
	ll ways_white = 1;
	for(int v : graph[u]){
		if(v == p) continue;
		ways_white *= solve(v,u,0);
		ways_white %= mod;
	}
	ll ways_black = 0;
	if(!p_black){
		ways_black = 1;
		for(int v : graph[u]){
			if(v == p) continue;
			ways_black *= solve(v,u,1);
			ways_black %= mod;
		}
	}
	return dp[u][p_black] = (ways_black + ways_white) % mod;
}


void solution(){
	cin >> n;
	graph = vector<vector<int>>(n);
	for(int i = 0; i < n-1; i++){
		int u, v; cin >> u >> v;
		u--; v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	memset(dp,-1,sizeof(dp));
	cout << solve(0,-1,0) << endl;

}	


int main(){ 

	fio;
	int t;
	t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++){
		// cout << "Case #" << i << ": ";
		solution();
	} 
	return 0;
}


Measured memory_bytes: 18428
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<string>
#include<map>
#include<queue>

using namespace std;

typedef long long int ll;

int main(void){

    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    ll total = 0;

    for(int i = 0;i < n;i++){
        cin >> h[i];
        total += h[i];
    }

    sort(h.begin(), h.end(), greater<int>());

    if(n < k){
        cout << 0 << endl;
        return 0;
    }

    for(int i = 0;i < k;i++){
        total -= h[i];
    }

    cout << total << endl;

    return 0;
}

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

using namespace std;

const int MAX = 10001;
int cnt[MAX];

int main(){
  memset(cnt, 0, sizeof(cnt));
  int n; scanf("%d\n", &n);
  int lim = 0;
  while(n--){
    int tmp;
    scanf("%d",&tmp);
    cnt[tmp]++;
    lim = max(lim, tmp);
  }
  bool f = true;
  for(int i = 0; i <= lim; i++)
    while(cnt[i]--){
      if(!f) printf(" ");
      else f = false;
      printf("%d",i);
    }
  printf("\n");
  return 0;
}

Measured memory_bytes: 1240
N = int(input())
Dishes = []
for i in range(N):
    a, b = map(int, input().split())
    add = a + b
    Dishes.append([add, a, b])


Dishes.sort(key=lambda x: x[0], reverse=True)


T_point, A_point = 0, 0
for i, (add, a, b) in enumerate(Dishes):
    if i % 2 == 0:
        T_point += a
    else:
        A_point += b


print(T_point - A_point)


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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);

    int n;
    cin>>n;
    vector <string> v(n);
    map <string,int> mp;
    set <string> st;
    int mx=0;
    loop(i,0,n)
    {
        cin>>v[i];
        mp[v[i]]++;
        mx=max(mx,mp[v[i]]);
    }

    for(auto p:mp)
    {
        if(p.second==mx)
        {
            st.ins(p.fi);
        }
    }

    for(auto s:st) cout<<s<< "\n";


    return 0;
}


Measured memory_bytes: 40616
#include "iostream"
using namespace std;
int main() {
	long long N;
	cin >> N;
	long long n = N % 10;
	long long m = N / 10;
	if (n == 9||m == 9) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}	return 0;
}

Measured memory_bytes: 256
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True
# False:Cython はCの型に対する除算・剰余演算子に関する仕様を、(被演算子間の符号が異なる場合の振る舞いが異なる)Pythonのintの仕様に合わせ、除算する数が0の場合にZeroDivisionErrorを送出します。この処理を行わせると、速度に 35% ぐらいのペナルティが生じます。 True:チェックを行いません。

ctypedef long long LL
from libcpp.vector cimport vector
ctypedef vector[LL] vec


import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.readline #文字列読み込む時はこっち

def ints(): return map(int,readline().split())


cdef class UnionFind:
    cdef:
        public LL N,n_groups
        public vec parent

    def __init__(self, LL N):
        self.N = N  # ノード数
        self.n_groups = N  # グループ数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = vec(N,-1)  # idxが各ノードに対応。

    cdef LL root(self, LL A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    cdef LL size(self, LL A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    cdef bint unite(self,LL A,LL B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる
        self.n_groups -= 1

        return True

    cdef bint is_in_same(self,LL A,LL B):
        return self.root(A) == self.root(B)


cdef LL N,M,_



N, M = ints()
cdef UnionFind uf = UnionFind(N)
cdef LL a,b
for _ in range(M):
    a,b=ints()
    uf.unite(a-1, b-1)

print(-min(uf.parent))

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode


Measured memory_bytes: 20256