akhauriyash/Code-Regression huggingface dataset:
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    count = 0
    for i in range(2, n+1):
        if prime[i]:
            count += 1
            for j in range(2*i, n+1, i):
                prime[j] = False
    return prime


def count(p):
    cnt = 0
    n = N
    while n > 0:
        n //= p
        cnt += n
    return cnt


N = int(input())
prime = sieve(N)
ans = 0

# case 1: p^74
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 74:
        break
    ans += 1

# case 2: p^2 q^4 r^4
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N):
        if not prime[q] or p == q:
            continue
        if count(q) < 4:
            break
        for r in range(q+1, N+1):
            if not prime[r] or p == r:
                continue
            if count(r) < 4:
                break
            ans += 1

# case 3: p^4 q^14
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 4:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 14:
            break
        ans += 1

# case 3: p^2 q^24
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 24:
            break
        ans += 1

print(ans)


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

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

  int ans = 0;

  if(a[0] == 'R'){
    ans++;
    if(a[1] == 'R'){
      ans++;
      if(a[2] == 'R'){
        ans++;
      }
    }
  }
  else{
    if(a[1] == 'R'){
      ans++;
      if(a[2] == 'R'){
        ans++;
      }
    }
    else{
      if(a[2] == 'R'){
        ans++;
      }
    }
  }

  cout << ans << endl;

  /*int N = 3;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }*/

  /*for (int i = 0; i < vec.size(); i ++){
    cout << vec.at(i) << endl;
  }

  for (int i = 0; i < vec.size()-1; i ++){
    cout << vec.at(i) << " ";
  }
  cout << vec.at(vec.size() - 1) << endl;*/
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <bitset>
#include <cstdio>
#include <sstream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <cctype>
#include <iomanip>
#include <list>
#include <cstring>

#define INF 2000000000
#define ull unsigned long long int
#define vi vector<int>
#define vii vector<ii>
#define int long long int

#define UNVISITED 0
#define OPENED 1
#define CLOSED 2

#define PI 3.14159265359

#define D(x) cout<<#x<<" : "<<x<<endl
#define P(x) cout << x << endl;

using namespace std;

vector <int> t;

int eval(int t0) {
	
	int prevSum = t0;
	int rep = 0;
	for(int i= 1; i < t.size(); i++) {
		int currSum = prevSum + t[i];
		if(prevSum < 0) {
			if(currSum == 0) {
				currSum = 1; rep++;
			}
			else if(currSum < 0){
				rep += abs(currSum)+1;currSum = 1; 
			}
		}
		else if(prevSum > 0) {
			if(currSum == 0) {
				currSum = -1; rep++;
			}
			else if(currSum > 0){
				rep += abs(currSum)+1; currSum = -1; 
			}
		}
		//cout << currSum << " " << rep << endl;
		prevSum = currSum;
	}	
	return rep;
}

signed main () {
	int n; cin >> n; int a;
	for(int i= 0; i <n; i++) {
		cin >> a; 
		t.push_back(a);
	}
	//cout << eval(t[0]) << endl;
	if(t[0] == 0) cout << min(eval(1)+1, eval(-1)+1) << endl;
	else cout << min(min(eval(t[0]), eval(1)+abs(1-t[0])), eval(-1)+abs(-1-t[0])) << endl;;
	
	
	return 0;
}

Measured memory_bytes: 1400
#include <cmath>
#include <iostream>

using namespace std;

#define list_zero(p, n)                                                        \
    for(int i = 0; i < n; i++)                                                 \
        p[i] = 0;

#define hbreak(input) (int)(input / 100);
#define digit(input) (int)(1 + log10(input));

int list_sum(int *p, int n) {
    int sum;
    for(int i = 0; i < n; i++)
        sum = p[i];
    return sum;
}

int main() {
    int h[6] = {0, 0, 0, 0, 0, 0};
    int input;
    int sum, lst;
    cin >> input;

    int max = input / 100;

    for(h[0] = 0, lst = list_sum(h, 6); h[0] <= (max - lst); h[0]++) {
        for(h[1] = 0, lst = list_sum(h, 6); h[1] <= (max - lst); h[1]++) {
            for(h[2] = 0, lst = list_sum(h, 6); h[2] <= (max - lst); h[2]++) {
                for(h[3] = 0, lst = list_sum(h, 6); h[3] <= (max - lst);
                    h[3]++) {
                    for(h[4] = 0, lst = list_sum(h, 6); h[4] <= (max - lst);
                        h[4]++) {
                        for(h[5] = 0, lst = list_sum(h, 6); h[5] <= (max - lst);
                            h[5]++) {
                            sum = h[0] * 100 + h[1] * 101 + h[2] * 102 +
                                  h[3] * 103 + h[4] * 104 + h[5] * 105;
                            // cout << h[0] << h[1] << h[2] << h[3] << h[4] <<
                            // h[5]
                            //      << endl;
                            // cout << summ << endl;
                            if(input == sum) {
                                // cout << h[0] << ',' << h[1] << ',' << h[2]
                                //      << ',' << h[3] << ',' << h[4] << ','
                                //      << h[5] << endl;
                                cout << '1' << endl;
                                return 0;
                            }
                        }
                        h[5] = 0;
                    }
                    h[4] = 0;
                }
                h[3] = 0;
            }
            h[2] = 0;
        }
        h[1] = 0;
    }
    cout << '0' << endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import deque

K=input()

#ポイント：隣接リストがわかればdfsができる
L=[]
q=deque()
for i in range(1,10):
    L.append(i)
    q.append(i)
cnt=0
while q and cnt<10**5:
    fro=q.popleft()
    ichi_no_kurai=fro%10
    for i in range(max(0,ichi_no_kurai-1),min(ichi_no_kurai+2,10)): #隣接リストを作る
        L.append(fro*10+i)
        q.append(fro*10+i)
        cnt+=1

print L[K-1]


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

int main() {
  string s, t;
  int a, x = 0;

  cin >> s >> t;
  a = s.size();

  for (size_t i = 0; i < a; i++) {
    if (s.at(i)!=t.at(i)) {
      x++;
    }
  }

  cout << x << endl;
}


Measured memory_bytes: 3920
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
   int n;
   cin>>n;
   long long int ans = 1;
   for(int i=n;i>=1;i--){
       ans *= i;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 3004
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
 
typedef long long ll;
 
using namespace std;
 
int main() {
	int a, b, cnt = 0;
	cin >> a >> b;
	
	vector<int> data(a);
	
	for (int i = 0; i < a; i++) {
		cin >> data[i];
	}
	
	for (int i = 0; i < a; i++) {
		if (data[i] >= b) {
			cnt++;
		}
	}
	
	cout << cnt << endl;
 
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 1e9+7;


int main(){
	//ios_base::sync_with_stdio(false);
	int A, B, C, ans=0;

	cin >> A >> B >> C;

	cout << A*B/2 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int main(void)
{	
	while (1) {
		int n;
		cin >> n;		
		if (n == 0) break;
		
		int s[1000];
		for (int i = 0; i < n; i++) cin >> s[i];
		
		double m = 0;
		for (int i = 0; i < n; i++) {
			m += s[i];
		}
		m /= n;
		
		double aan = 0;
		for (int i = 0; i < n; i++) {
			aan += pow((s[i] - m), 2);
		}
		
		double a = sqrt(aan / n);
		
		cout << fixed << a << endl;
	}
		
	return 0;
}

Measured memory_bytes: 3248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N;
int f[5005];
vector<int> p;
multiset<int> st;

int win(vector<int> &a, vector<int> &b) {
    int index = 0;
    for(int i = 0; i < b.size(); i++) {
        if(b[i] > a[index]) index++;
    }
    return index;
}

void g(int index) {
    vector<int> F, F2;
    for(int i = index; i < N; i++) F.push_back(f[i]);
    for(int i = index + 1; i < N; i++) F2.push_back(f[i]);
    sort(F.begin(), F.end());
    sort(F2.begin(), F2.end());
    int maxi = win(F, p);
    //cerr << maxi << endl;
    if(p.back() > f[index]) {
        int ok = 0;
        int ng = p.size();
        while(ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if(p[mid] <= f[index]) {
                ok = mid;
                continue;
            }
            vector<int> copy;
            for(int i = 0; i < p.size(); i++) {
                if(i == mid) continue;
                copy.push_back(p[i]);
            }
            if(win(F2, copy) + 1 == maxi) ok = mid;
            else ng = mid;
        }
        cout << p[ok];
        p.erase(p.begin() + ok);
        return;
    } else {
        int ok = 0;
        int ng = p.size();
        while(ng - ok > 1) {
            int mid = (ok + ng) / 2;
            vector<int> copy;
            for(int i = 0; i < p.size(); i++) {
                if(i == mid) continue;
                copy.push_back(p[i]);
            }
            //cerr << endl << "check: " << index << " " << mid << " " << win(F2, copy) << " " << maxi << endl;
            if(win(F2, copy) == maxi) ok = mid;
            else ng = mid;
        }
        cout << p[ok];
        p.erase(p.begin() + ok);
    }
}


int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    p.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> f[i];
    }
    for(int i = 0; i < N; i++) {
        cin>> p[i];
        st.insert(p[i]);
    }
    sort(p.begin(), p.end());
    for(int i = 0; i < N; i++) {
        if(i != 0) cout << " ";
        g(i);
    }
    cout << endl;
    /*
    for(int i = 1; i <= N; i++) {
        if(i != 1) cout << " ";
        auto itr = st.lower_bound(f[i] + 1);
        if(itr != st.end()) {
            cout << *itr;
            st.erase(itr);
        } else {
            itr = st.begin();
            cout << *itr;
            st.erase(itr);
        }
    }
    //cout << endl;
    */
    return 0;
}


Measured memory_bytes: 3576
#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 ans = 0;
  string s;
  cin >> s;
  rep(i, s.size()) ans += s[i] - '0';

  cout << (ans % 9 == 0 ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 3696
n=int(input())
p=list(map(int,input().split()))
c=0
a=[]
b=[]
for i in range(n):
    if p[i]!=i+1:
        c+=1
        a.append(i+1)
        b.append(p[i])
if c==0 or c==2:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 38384
#include <stdio.h>
int main(void){
    // Your code here!
    int H,W;
    int i,j;
    
    while(1){
        scanf("%d %d",&H,&W);
        
        if(H==0&&W==0) break;
        
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                if((i%2==0&&j%2==0)||(i%2==1&&j%2==1)){
                    printf("#");
                }
                else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int main() {
    int a, b, q;
    cin >> a >> b >> q;

    vector<ll> s(a+2), t(b+2);
    s[0] = t[0] = -INF;
    for(int i = 1; i <= a; i++) {
        cin >> s[i];
    }
    for(int i = 1; i <= b; i++) {
        cin >> t[i];
    }
    s[a+1] = t[b+1] = INF;
    
    vector<vector<ll>> u(2, vector<ll>(2));
    vector<ll> ans(q, INF);
    rep(h, q) {
        ll x;
        cin >> x;

        auto sepos = lower_bound(s.begin(), s.end(), x);
        int idse = sepos - s.begin(); 
        u[0][1] = s[idse];
        /*auto swpos = sepos--;
        int idsw = swpos - s.begin();*/
        u[0][0] = s[idse-1];
        auto tepos = lower_bound(t.begin(), t.end(), x);
        int idte = tepos - t.begin();
        u[1][1] = t[idte];
        //auto twpos = tepos--;
        u[1][0] = t[idte-1];

        rep(i, 2) {
            rep(j, 2) {
                rep(k, 2) {
                   ll dist = 0;
                   dist += abs(u[i][j] - x) + abs(u[i][j] - u[i^1][k]);
                   ans[h] = min(ans[h], dist);
                }
            }
        }
    }
    
    rep(i, q) {
        cout << ans[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3712
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		sc.nextLine();
		// Aの総時間
		BigInteger[] asums = new BigInteger[n+1];
		asums[0] = BigInteger.ZERO;
		BigInteger [] bsums = new BigInteger[m+1];
		bsums[0] = BigInteger.ZERO;
		
		for (int i = 1; i < n + 1; i++) {
			int tmp = sc.nextInt();
			asums[i] = asums[i-1].add(BigInteger.valueOf(tmp));
		}
		sc.nextLine();
		for (int i = 1; i< m + 1; i++) {
			int tmp = sc.nextInt();
			bsums[i] = bsums[i-1].add(BigInteger.valueOf(tmp));
		}
		
		BigInteger bigK = BigInteger.valueOf(k);
		int ans = 0;
		int bstart = m;
		for (int i = 0; i < n + 1; i++) {
			BigInteger sum = BigInteger.ZERO;
			// Aから0冊、1冊、2冊・・・
			sum = sum.add(asums[i]);
			for (int j = bstart; j >= 0; j--) {
				// Bからm冊、m-1冊、m-2冊・・・降順に
				BigInteger target = sum.add(bsums[j]);
				if (target.compareTo(bigK) <= 0) {
					if (ans < i + j) {
						// 更新
						ans = i + j;
					}
					bstart = j;
					break;
				}
			}
		}
		System.out.println(ans);
	}
	
}


Measured memory_bytes: 88716
fun intList(): List<Int> = readLine()!!.split(" ").map(String::toInt)

fun main() {
    val (x, y) = intList()

    var isTrue = false

    for(i in 0..x) {
        val turtleCount = i
        val craneCount = x - i

        if(turtleCount * 4 + craneCount * 2 == y) isTrue = true
    }

    println(if(isTrue) "Yes" else "No")
}

Measured memory_bytes: 36436
#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 watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 100005

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	string s; cin>>s;
	int n=s.length();
	
	ll sum=0;
	int cnt=1;
	vector<pair<ll,char>> v;
	
	forn(i,1,n){
		if(s[i]==s[i-1]){
			cnt++;
		}
		else{
			v.pb({cnt,s[i-1]});
			cnt=1;
		}
	}
	v.pb({cnt,s[n-1]});
	
	for(int i=0;i<v.size();i++){
		ll x=v[i].F; 
		sum+=x*(x+1)/2;
		if(i<v.size()-1 && v[i].S=='<' && v[i+1].S=='>'){
			sum-=min(v[i].F,v[i+1].F);
		}
	}
	
	cout<<sum<<'\n';
	
	return 0;
}


Measured memory_bytes: 6408
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(a)			a.begin(), a.end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define	MAX_QWORD		((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, ll>	P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
static int d[31][31];
static int c[501][501];
static int cList[3][31];
int N, C;
int getSumOne(int idx, int col)
{
	int sum = 0;
	REP(i, 31) {
		if (i != col) {
			sum += (cList[idx][i] * d[i][col]);
		}
	}
	return sum;
}

int main()
{
	int a, b, x;
	cin >> a >> b >> x;

	int sum = a + b;
	if (a <= x && x <= sum) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
#define DUMP1(A) do { for (auto &a : A) cout << a << ' '; cout << '\n'; } while (0)
#define DUMP2(A) do { for (auto &row : A) { DUMP1(row); } } while (0)
int main() {
    int N; cin >> N;
    vector<Int> A(N + 1); for (auto &a : A) cin >> a;
    vector<Int> S = A;
    for (int i = N - 1; i >= 0; i--) {
        S[i] += S[i + 1];
    }
    S.push_back(0);
    Int ans = 0;
    Int curr = 1;
    for (int i = 0; i < N + 1; i++) {
        ans += curr;
        if (curr < A[i]) { ans = -1; break; }
        curr = min<Int>(S[i + 1], 2 * (curr - A[i]));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5576
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll a[100];
int main() {
	int n;ll x; cin >> n >> x;
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);
	int out = 0;
	rep(i, n-1) {
		if (a[i] <= x) {
			out++; x -= a[i];
		}
	}
	if (a[n - 1] == x)out++;
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 256
from operator import itemgetter
import sys

N, M = map(int, input().split())


cng = []
L_max=0
R_min=float('inf')
for i in range(M):
    L, R = map(int, input().split())
    if(L_max<=L):
        L_max=L
    if(R_min>=R):
        R_min=R
        

if(R_min-L_max<0):
    print(0)
else:
    print(R_min-L_max+1)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
int main() {
	int n;
	cin >> n;
	map<int, int> k;
	map<int, int> g;
	int i;
	V a(n);
	for (i = 0; i < n; i++) {
		cin >> a[i];
		int I = i + 1;
		if (I % 2 != 0) k[a[i]]++;
		else g[a[i]]++;
	}
	int kmode = -1;
	int kk = 0;
	int gmode = -1;
	int gk = 0;
	for (auto c : k) {
		if (kk < c.second) {
			kmode = c.first;
			kk = c.second;
		}
	}
	for (auto c : g) {
		if (gk < c.second) {
			gmode = c.first;
			gk = c.second;
		}
	}
	if (kmode != gmode) {
		int ans = 0;
		for (i = 0; i < n; i++) {
			int I = i + 1;
			if (I % 2 != 0 && a[i] != kmode) ans++;
			if (I % 2 == 0 && a[i] != gmode) ans++;
		}
		cout << ans;
	}
	else {
		int ks = -1;
		int kc = 0;
		int gs = -1;
		int gc = 0;
		for (auto c : k) {
			if (kc < c.second && c.first != kmode) {
				ks = c.first;
				kc = c.second;
			}
		}
		for (auto c : g) {
			if (gc < c.second && c.first != gmode) {
				gs = c.first;
				gc = c.second;
			}
		}
		int ans1 = 0;
		int ans2 = 0;
		for (i = 0; i < n; i++) {
			int I = i + 1;
			if (I % 2 != 0 && kmode != a[i]) ans1++;
			if (I % 2 == 0 && gs != a[i]) ans1++;
		}
		for (i = 0; i < n; i++) {
			int I = i + 1;
			if (I % 2 != 0 && ks != a[i]) ans2++;
			if (I % 2 == 0 && gmode != a[i]) ans2++;
		}
		cout << min(ans1, ans2);
	}
	return 0;
}

Measured memory_bytes: 5376
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
  int time;
  cin >> time;

  for (int j = 0; j < time; j++) {
    int t;
    cin >> t;

    int height = 0, n, h, max = 0, min = 0;
    for (int i = 0; i < t; i++) {
      cin >> n;
      if (i != 0) {
        h = n - height;
        if (h >= 0 && h > max) {
          max = h;
        } else if (h <= 0 && h < min) {
          min = h;
        }
      }
      height = n;
    }

    cout << max << ' ' << -min << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
mod = 10 ** 9 + 7

n, a, b = map(int, input().split())


def choose(n, a, mod=mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod)


ret = pow(2, n, mod)
ret -= 1
ret -= choose(n, a)
ret -= choose(n, b)
ret %= mod

print(ret)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-8
#define inf INT_MAX
#define mod 1000000009
using namespace std;

int main() {
	speed;
	string s;
	cin >> s;
	int a = stoi(s.substr(0, 2)), b = stoi(s.substr(2));
	if (a <= 12 && b <= 12 && a >= 1 && b >= 1)
		cout << "AMBIGUOUS";
	else if (a <= 12 && a >= 1)
		cout << "MMYY";
	else if (b <= 12 && b >= 1)
		cout << "YYMM";
	else
		cout << "NA";
	cout << '\n';
	return 0;
}

Measured memory_bytes: 256
S = input()

# 最初が0のパターン
count = 0
for i in range(0, len(S), 2):
    if S[i] != "0":
        count += 1
for i in range(1, len(S), 2):
    if S[i] != "1":
        count += 1
ans = count
# 最初が1のパターン
count = 0
for i in range(0, len(S), 2):
    if S[i] != "1":
        count += 1
for i in range(1, len(S), 2):
    if S[i] != "0":
        count += 1
ans = min(ans, count)
print(ans)


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

typedef long long ll;
#define vec vector<int>
#define vecll vector<ll>
#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define llrep(i,n)   for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define prt_dbl(i,var) cout<<fixed<<setprecision(i)<<var<<endl;
#define dpair pair<double,double>

template <typename Val>
Val gcd(Val a, Val b) {
//use ll or int for gcd
    if (b==0) return a;
    else return gcd(b, a%b);
}
template <typename Val>
Val vec_max(vector<Val> v){
  return *max_element(v.begin(),v.end());
}
template <typename Val>
Val vec_min(vector<Val> v){
  return *min_element(v.begin(),v.end());
}
template <typename Val>
void show_vec(vector<Val> *v){
  cout<<endl;
  rep(i,v->size()){
    cout<<v->at(i)<<" ";
  }
  cout<<endl;
}

template <typename Val,typename Number>
void count_vector(vector<Val>* A,vector<pair<Number,Val>>*R){
  sort(A->begin(),A->end());
  int count = 1;
  rep(i,A->size()){
    if(i<A->size()-1){
      if(A->at(i)==A->at(i+1))count++;
      else{
        R->emplace_back(count,A->at(i));
        count = 1;
      }
    }else{
      R->emplace_back(count,A->at(i));
    }
  }
}


struct Point{
  int x;
  int y;
};


//---------------------------------------------------------------
int main(){
  ll A,B,N,x;
  cin>>A>>B>>N;

  if(N>=B){
    x = B-1;
  }else{
    x = N;
  }

  ll ans = (A*x)/B;

  cout<<ans<<endl;




}


Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

#define INF (long long int)1e09

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set; // insert erase find count
using std::queue;
using std::priority_queue;
using std::stack;

template <typename T> using Vec = vector<T>; // c++11
typedef pair<long long int, long long int> PII;

int main(void) {
    long long int n;
    long long int k;
    cin >> n >> k;
    Vec<PII> coord(n);
    set<long long int> sx;
    set<long long int> sy;
    for (long long int i = 0; i < n; i++) {
        cin >> coord[i].first >> coord[i].second;
        sx.insert(coord[i].first);
        sy.insert(coord[i].second);
    }
    
    long long int ans = 4 * 1e18 + 1;
    for (auto itr_xs = sx.begin(); itr_xs != sx.end(); itr_xs++) {
        for (auto itr_xe = itr_xs; itr_xe != sx.end(); itr_xe++) {
            for (auto itr_ys = sy.begin(); itr_ys != sy.end(); itr_ys++) {
                for (auto itr_ye = itr_ys; itr_ye != sy.end(); itr_ye++) {
                    long long int x_min = *itr_xs;
                    long long int x_max = *itr_xe;
                    long long int y_min = *itr_ys;
                    long long int y_max = *itr_ye;

                    long long int count = 0;
                    for (long long int i = 0; i < n; i++) {
                        long long int tx = coord[i].first;
                        long long int ty = coord[i].second;
                        if (tx < x_min || tx > x_max || ty < y_min || ty > y_max) {
                        } else {
                            count++;
                        }
                    }
                    if (count >= k) {
                        ans = min(ans, (x_max - x_min) * (y_max - y_min));  
                    }
                }
            }
        }
    }
    cout << ans << endl;



    return 0;
}



Measured memory_bytes: 256
import Control.Applicative

data YesNo = Yes | No deriving (Show)

solver :: Int -> Int -> Int -> YesNo
solver a b c
  | a < b && b < c = Yes
  |otherwise       = No

main :: IO()
main = do
  (a:b:c:_) <- map (read :: String -> Int) . words <$> getLine
  print $ solver a b c

Measured memory_bytes: 3596
def main():
    n = int(input())
    hpy = []
    for _ in range(n):
        tmp = list(map(int,input().split()))
        hpy.append(tmp)
    # a:0, b:1, c:2
    dp = [[0] * 3 for i in range(n) ]
    dp[0][0] = hpy[0][0]
    dp[0][1] = hpy[0][1]
    dp[0][2] = hpy[0][2]
    for i, abc in enumerate(dp):
        if i ==n-1:
            break
        a = max(abc[1], abc[2]) + hpy[i+1][0]
        b = max(abc[2], abc[0]) + hpy[i+1][1]
        c = max(abc[0], abc[1]) + hpy[i+1][2]
        dp[i+1][0] = a
        dp[i+1][1] = b
        dp[i+1][2] = c
    print(max(dp[n-1]))


if __name__=='__main__':
    main()


Measured memory_bytes: 75864
#include <iostream>
#include<algorithm>
using namespace std;
long long a[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int num=0;
    for(int i=0;i<n-1;i++)
    {
        if(a[i]*2>=a[i+1])
            a[i+1]+=a[i];
        else
        {
            num=i+1;
            a[i+1]+=a[i];
        }
    }
    cout<<n-num<<endl;
    return 0;
}

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


using namespace std;

using ll   = long long;
using ii   = pair < int , int >;
using i3   = pair < int , ii >;
using li   = pair < ll , int >;
using lii  = pair <  ll,  ii >;
using vi   = vector < int >;
using vl   = vector < ll >;
using vli  = vector < li >;
using vii  = vector < ii >;
using vi3  = vector < i3 >;
using vlii = vector < lii >;

const int N = 1e5 + 5;
const ll INF = 1e17;
const double eps = 1e-12 , PI = acos(-1);

int n , m;


void A(){
    scanf("%d %d" , &n , &m);

    printf("%d\n" , n <= 9 && m <= 9 ? n*m : -1);
}

void B(){
    scanf("%d" , &n);

    for(int i = 1 ; i*i <= n ; i ++){
            if(n%i == 0){
                    if(i <= 9 && n/i <= 9){
                            printf("Yes\n");
                            return;
                    }
            }
    }
    printf("No\n");
}

void C(){
    ll x;
    scanf("%lld" , &x);

    ll ans = INF;
    for(ll i = 1ll ; i*i <= x ; i ++){
            if(x%i == 0){
                    ans = min(ans , i + x/i);
            }
    }

    printf("%lld\n" , ans - (1ll * 2));
}

main(){

    //A();
    //B();
    C();

    return 0;
}


Measured memory_bytes: 256
fn main() {
    let mut sc = Scanner::new();
    let a: Vec<usize> = sc.read::<String>()
        .chars()
        .map(|c| (c as usize) - ('a' as usize))
        .collect();
    let mut pos = vec![vec![]; 26];
    let n = a.len();
    for i in 0..n {
        pos[a[i]].push(i + 1);
    }

    let mut k = vec![0; n + 2];
    let mut vis = vec![false; 26];

    for i in (0..n).rev() {
        let j = i + 1;
        vis[a[i]] = true;

        let mut ok = true;
        for &b in &vis {
            ok = ok && b;
        }
        if ok {
            for i in 0..vis.len() {
                vis[i] = false;
            }
            k[j - 1] = k[j] + 1;
        } else {
            k[j - 1] = k[j];
        }
    }

    let mut cur_pos = 0;
    let mut ans: Vec<usize> = Vec::new();
    for _ in 0..(k[0] + 1) {
        for c in 0..26 {
            let p: usize = match pos[c].binary_search(&(cur_pos + 1)) {
                Ok(p) => pos[c][p],
                Err(p) => if p < pos[c].len() {
                    pos[c][p]
                } else {
                    n
                },
            };

            if p == n || k[cur_pos] == k[p] + 1 {
                cur_pos = p;
                ans.push(c);
                break;
            }
        }
    }

    for &a in &ans {
        let c = ((a as u8) + ('a' as u8)) as char;
        print!("{}", c);
    }
    println!();
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            ptr: 0,
            length: 0,
            buf: vec![0; 1024],
            small_cache: vec![0; 1024],
        }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool {
        b == b'\n' || b == b'\r' || b == b'\t' || b == b' '
    }

    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)])
                    .parse()
                    .unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}


Measured memory_bytes: 10492
#include <iostream>
using namespace std;
int main() {
	int a, b;
	double x,y,f;
	cin >> a >> b;
	x = a;
	y = b;
	f = x / y;
		cout << a / b <<" "<< a % b <<" ";
		printf("%.20lf\n",f);
}


Measured memory_bytes: 3248
import copy

n,m=map(int,input().split())
l=[]
for i in range(m):
    x,y=map(int,input().split())
    l.append([x,y])

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*(n)
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):
        return self.find(x)==self.find(y)
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

ans=0
for i in range(m):
    uf=UnionFind(n)
    x=copy.deepcopy(l)
    x.pop(i)
    for a,b in x:
        uf.union(a-1,b-1)
    y=l[i][0]-1
    z=l[i][1]-1
    if uf.same_check(y,z):
        ans+=1

print(m-ans)

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp(a,b) make_pair(a,b)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

int main(){
	ll H,W,N; cin>>H>>W>>N;
	vector<vector<ll>> field(H,vector<ll>(W,0));
	ll place=0;//塗る場所、HWまで
	rep1(i,N){
		ll a; cin>>a;
		//i色でa個塗るよ
		rep1(j,a){
			place++;
			ll gyo=ceil(place/(double)W)-1;
			ll retu;
			if(gyo%2==0){
				retu=(place-1)%W;
			}else{
				retu=W-1-(place-1)%W;
			}
			field[gyo][retu]=i;
		}
	}
	rep(i,H){
		rep(j,W){
			printf("%lld ",field[i][j]);
		}
		cout<<endl;
	}
}

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

int main(){
  int a, b, t, s;
  cin >> a >> b >> t;
  s=(t+0.5)/a;
  printf("%d\n", s*b);

  return 0;
}

Measured memory_bytes: 3772
#include "bits/stdc++.h"
// #include "boost/math/common_factor.hpp" // gcd, lcm
using namespace std;

// #define int long long

signed main(void) {
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int n;
  int s;
  array<int, 1000000> a;
  // cin >> s;

  int t, x;
  cin >> t >> x;

  cout << (double)t / (double)x << endl;

  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    d = dict()
    pairs = list()

    # KeyInsight:
    # 1〜Nまでの整数について、先頭と末尾の数字のペアをカウントする
    # ex: (1, 9), (9, 1)
    # (x, y)に対応する(y, x)の個数を加算する
    for i in range(1, n + 1):
        s = str(i)
        first = s[0]
        second = s[-1]
        pairs.append((first, second))

        if (first, second) not in d.keys():
            d[(first, second)] = 1
        else:
            d[(first, second)] += 1

    ans = 0

    for first, second in pairs:
        if (second, first) in d.keys():
            ans += d[(second, first)]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 17304
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S,T;
  cin >> S >> T;
  int n,count;
  n = S.length();
  count = 0;
  
  for (int i = 0; i < n; i++) {
    if(S[i]!=T[i]){
        count += 1;
    }
  }
  
        cout << count << endl;
}

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

using namespace std;


typedef long long ll;
ll mod=1e9+0LL;
ll MOD=1e18+0LL;
double pi=acos(-1);
ll md=1000000007;
ll gcd(ll a,ll b){
    //if(b>a) swap(a,b);
    return b==0?abs(a):gcd(b,a%b);
}
ll pow(ll a ,ll n)
{
    if(n==0) return 1;
    if(n%2==0)
    {
        ll b=pow(a,n/2);
        return (b*b)%md;
    }
    return (pow(a,n-1)*a)%md;
}
int main()
{
    int cs=1;
    //scanf("%d",&cs);
    while(cs--)
    {
        int a,b,c,k;
        cin>>a>>b>>c>>k;
        ll sum=0;
        sum+=min(k,a);
        k-=min(k,a);
        k-=min(k,b);
        sum+=min(k,c)*(-1);
        cout<<sum;

    }
}


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

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

    ll tmp = n / (a + b);
    ll res = n % (a + b);

    cout << tmp * a + min(res,a) << endl;
    return 0;
   
}

Measured memory_bytes: 256
import sys

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline()
    # ans = 0
    # for i in range(N-1):
    #     if S[i] == S[i+1]:
    #         ans += 1
    ans = N - 1 - S.count('LR') - S.count('RL')
    ans = min(N-1, ans+K*2)
    print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
using namespace std;
typedef long long ll;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
//freopen("","r",stdin);
//freopen("","w",stdout);
int main(){
    fast;
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(int i = 0; i < n - 2; i++)
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
            ans++;
    cout << ans << '\n';
    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    string S = in<string>();
    if(S == "zyxwvutsrqponmlkjihgfedcba"){
        cout << -1 << "\n";
    }else if(S.size() == 26){
        string before = S;
        next_permutation(ALL(S));
        int stop = 0;
        REP(i,26){
            if(S[i] != before[i]){
                stop = i;
                break;
            }
        }
        cout <<S.substr(0,stop+1)<< "\n";
    }else{
        vector<bool> AS(26);
        REP(i,S.size()){
            AS[S[i] - 'a'] = 1;
        }
        REP(i,26){
            if(AS[i] == 0){
                char plus = i + 'a';
                S += plus;
                break;
            }
        }
        cout << S << "\n";
    }
}

Measured memory_bytes: 256
from collections import Counter
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
Flg = "YES"

c1 = Counter(D)
c2 = Counter(T)

for i, val in c2.items():
    if(c1[i] < val):
        Flg = "NO"
        break
print(Flg)

Measured memory_bytes: 57056
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>

using namespace std;


long long mul_inv(long long a, long long b)
{
	long long b0 = b, t, q;
	long long x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

long long division(long long a, long long b, long long p) {		// (a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
	long long ans, inv;
	inv = mul_inv(b, p);
	ans = ((a % p) * inv) % p;
	return ans;
}



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

	long long n, m, k, i, j, ans, MOD = 998244353, s, x;
	cin >> n >> m >> k;

	vector<long long> fact(n + 1), f(n + 1);
	
	fact[0] = 1;
	for (i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;

	// f[i] = M * (M - 1) ^ (i - 1)
	x = 1;
	for (i = 1; i <= n; i++) {
		f[i] = (m * x) % MOD;
		x = (x * (m - 1)) % MOD;
	}

	ans = 0;
	for (i = 0; i <= k; i++) {
		s = (f[n - i] * division((division(fact[n - 1], fact[i], MOD)), fact[n - 1 - i], MOD)) % MOD;
		ans = (ans + s) % MOD;
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 5928
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n){
    Int res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

int to[26];

int main(){
    cin.tie(0);
    
    memset(to, -1, sizeof(to));
    string S, T;
    cin >> S >> T;
    int flag = 1;
    for (int i = 0; i < S.length(); i++){
        if (to[T[i] - 'a'] == -1) to[T[i] - 'a'] = S[i] - 'a';
        else if (to[T[i] - 'a'] != S[i] - 'a') flag = 0;
    }
    for (int i = 0; i < 26; i++){
        for (int j = i+1; j < 26; j++){
            if (to[i] == to[j] && to[i] != -1) flag = 0;
        }
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
} 


Measured memory_bytes: 1020
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {  
    long long int x;
    cin >> x;
    long long int res = 0;
    res += x / 11 * 2;
    x %= 11;
    if (x > 6) {
        res += 2;
    } else if (x > 0) {
        res += 1;
    } 
    cout << res << endl;
}




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

string A[50], B[50];

int main() {
  int N, M;
  cin >> N >> M;
  for (int n = 0; n < N; n++) cin >> A[n];
  for (int m = 0; m < M; m++) cin >> B[m];
  
  for (int y = 0; y <= N - M; y++) {
    for (int x = 0; x <= N - M; x++) {
      
      int cnt = 0;
      for (int dx = 0; dx < M; dx++) {
        if (A[x + dx].substr(y, M) == B[dx]) cnt++;
      }
      if (cnt == M) {
        cout << "Yes" << endl;
        return 0;
      }
      
    }
  }
  cout << "No" << 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++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;



int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    bool k=true;
    while(a>=0 && c>=0){
        c-=b;
        if(c<=0){
            k=true;
            break;
        }
        a-=d;
        if(a<=0){
            k=false;
            break;
        }
    }

    string ans =k?"Yes":"No";
    cout<<ans<<endl;

    return 0;
}

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

using namespace std;

typedef long long ll;

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

#define range(i, a, b, s) for (int i = (a), __##i = (b); i < __##i; i += (s))
#define down(i, a, b, s) for (int i = (a), __##i = (b); __##i < i; i += (s))

const int maxn = 2e3 + 2;
const int mod = 1e9 + 7;

ll n, m, a[maxn], b[maxn], sum[maxn][maxn], dp[maxn][maxn];

ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }

int main(int argc, char const *argv[]) {
  // freopen("E.txt", "r", stdin);

  while (cin >> n >> m) {
    range(i, 0, n, 1) cin >> a[i];
    range(i, 0, m, 1) cin >> b[i];
    a[n] = b[m] = -1;

    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));
    range(i, 0, n + 1, 1) {
      range(j, 0, m + 1, 1) {
        if (a[i] == b[j]) {
          dp[i][j] = 1;
          if (i >= 1 && j >= 1) dp[i][j] = add(dp[i][j], sum[i - 1][j - 1]);
        }
        sum[i][j] = dp[i][j];
        if (i >= 1) sum[i][j] = add(sum[i][j], sum[i - 1][j]);
        if (j >= 1) sum[i][j] = add(sum[i][j], sum[i][j - 1]);
        if (i >= 1 && j >= 1) sum[i][j] = sub(sum[i][j], sum[i - 1][j - 1]);
      }
    }
    // range(i, 0, n + 1, 1) {
    //   range(j, 0, m + 1, 1) { cout << dp[i][j] << ", "; }
    //   cout << endl;
    // }
    cout << dp[n][m] << endl;
  }
  return 0;
}

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

ll gcd(ll m, ll n) {//最大公約数
    if (n == 0)return m;
    return gcd(n, m % n);
}//gcd

int main() {
  ll n,x;
  cin>>n>>x;
  vector<ll> a(n);
  rep(i,n){
    ll A;
    cin>>A;
    a[i]=abs(A-x);
  }
  ll ans=a[0];
  rep(i,n-1){
    ans=gcd(ans,a[i+1]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1024