akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MAX_N 200001
#define mod  998244353
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n, m, k;

// ax + by = gcd(a, b)
// if a = b*p + q then gcd(a, b) = gcd(b, q)
ll extgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1; y = 0; return a;
    } 
    ll p = a / b;
    ll g = extgcd(b, a - p * b, x, y);
    ll z = x - p * y;
    x = y; y = z;
    return g;
}

// assert m and a is prime with each other
inline ll modinv(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    x %= m;
    if(x < 0) x += m;
    return x;
}

vector<ll> fact, inv_fact;
void init_fact(ll n) {
    fact.resize(n);
    fact[0] = 1;
    for(ll i=1; i<n; i++) {
        fact[i] = i * fact[i-1] % mod;
    }
    inv_fact.resize(n);
    inv_fact[n-1] = modinv(fact[n-1], mod);
    for (ll i=n-2; i>=0; i--) {
        inv_fact[i] = (i + 1) * inv_fact[i+1] % mod;
    }
}

ll nPr(ll n, ll r) {
    if (n < r || n < 0 || r < 0) return 0;
    return fact[n] * inv_fact[n - r] % mod;
}

ll nCr(ll n, ll r) {
    if (n < r || n < 0 || r < 0) return 0;
    return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod;
}

ll nHr(ll n, ll r) {
    if (n == 0 && r == 0) return 1;
    return nCr(n + r - 1, r);
}

ll modpow(ll x, ll n) {
    if (n == 0) return 1;
    return modpow(x * x % mod, n / 2) * (n & 1 ? x : 1) % mod;
}

signed main(){
    cin >> n >> m >> k;
    init_fact(n);

    ll ret = 0;
    REP(i, k+1){
        ret += (((m * modpow(m - 1, n - 1 - i)) % mod) * nCr(n - 1, i)) % mod;
        ret %= mod;
    }
    cout << ret << endl;
    return 0;
}

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

int main() {
  int a,b,k;
  cin >> a >>b >> k;
  int cnt  = 0;
  int ans;
  for(int i = 100; i >=1 ;i--){
    if(a%i ==0 && b%i == 0) cnt++;
    if(cnt == k) {
      ans = i;
    break;
  }
  }
  cout << ans << endl;
}
  


Measured memory_bytes: 256
def getinputdata():

    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

#ますの数
n = int(arr_data[0][0])
#アリスの駒はマスの位置
a = int(arr_data[0][1])
#ボリスの駒は別のマスの位置
b = int(arr_data[0][2])

print("Alice" if (b-a)%2==0 else "Borys")


Measured memory_bytes: 3064
S = input()
total = 0

#bit search
for i in range(2 ** (len(S) - 1)):
  exp = S[0]
  for j in range(len(S) - 1):
    if i & (1 << j) != 0:
      exp += '+'
    exp += S[j + 1]
  total += eval(exp)
print(total)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

int main(){
    string s;cin>>s;
    cout << "2018/01/" << s[s.size()-2] << s[s.size()-1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin>>n;
  cout<<n*800-(n/15)*200<<endl;

  return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    string s;
    cin>>s;
    int n=s.size();
    int res=0;
    for(int i=0,j=s.size()-1;i<j;){
        if(s[i]==s[j]) i++,j--;
        else if(s[i]=='x') res++,i++;
        else if(s[j]=='x') res++,j--;
        else{
            cout<<-1<<endl;
            return 0;
        }
    }

    cout<<res<<endl;

}


Measured memory_bytes: 512
package main

import "fmt"

func getGcd(a, b int) (g int) {
	if a < b {
		g = getGcd(b, a)
	} else {
		if a%b == 0 {
			g = b
		} else {
			g = getGcd(b, a%b)
		}
	}
	return
}

func main() {
	var N int
	fmt.Scan(&N)
	a := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&a[i])
	}
	hp := a[0]
	for i := 1; i < N; i++ {
		hp = getGcd(hp, a[i])
		if hp == 1 {
			break
		}
	}
	fmt.Println(hp)
}


Measured memory_bytes: 5504
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  val n = inputs.head.toInt

  println(solve(n))

  def solve(n: Int): Long = {
    var ans = 0L

    (1 to n).foreach { i =>
      (i to n by i).foreach { j =>
        ans = ans + j
      }
    }

    return ans
  }
}


Measured memory_bytes: 55044
#include<stdio.h>

int main(void){
    int j, n;
    int max = -1000000, min = 1000000;
    long int sum = 0;
    
    scanf("%d", &n);
    
    while(n--){
        scanf("%d", &j);
        if (max <= j)
            max = j;
        if (min >= j)
            min = j;
        sum = sum + j;
    }
    printf("%d %d %ld\n", min, max, sum);
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int N; cin >> N;
  ll a[N]; rep(i,N) cin >> a[i];

  ll reso = 0, rese = 0;
  vector<ll> vo, ve;

  int pos = 0; 
  while(a[pos]<0&&pos<N) { 
    vo.push_back(1); pos++;
    if (pos<N) { vo.push_back(1); pos++; }
  }
  if (pos<N) reso += a[pos];
  while(pos<=N-1) {
    if (pos==N-1) break;
    else if (pos==N-2) { vo.push_back(2); break; }
    else if (pos==N-3) {
      if (a[pos+2]>0) { reso += a[pos+2]; vo.push_back(2); }
      else { vo.push_back(3); vo.push_back(2); }
      pos += 2;
    }
    else {
      if (a[pos+2]>0) { reso += a[pos+2]; vo.push_back(2); }
      else vo.push_back(3);
      pos += 2;
    }
  }

  pos = 1; ve.push_back(1);
  while(a[pos]<0&&pos<N) { 
    ve.push_back(1); pos++;
    if (pos<N) { ve.push_back(1); pos++; }
  }
  if (pos<N) rese += a[pos];
  while(pos<=N-1) {
    if (pos==N-1) break;
    else if (pos==N-2) { ve.push_back(2); break; }
    else if (pos==N-3) {
      if (a[pos+2]>0) { rese += a[pos+2]; ve.push_back(2); }
      else { ve.push_back(3); ve.push_back(2); }
      pos += 2;
    }
    else {
      if (a[pos+2]>0) { rese += a[pos+2]; ve.push_back(2); }
      else ve.push_back(3);
      pos += 2;
    }
  }

  // cout << reso << endl; debug(all(vo));
  // cout << rese << endl; debug(all(ve));

  if (reso==0&&rese==0) {
    int mp = 0; rep(i,N) if (a[mp]<a[i]) mp = i;
    cout << a[mp] << endl;
    cout << N-1 << endl;
    per(i,N+1) { if (i<=mp+1) break; cout << i << endl; }
    rep(i,mp) cout << 1 << endl;
  }
  else {
    if (reso>=rese) {
      cout << reso << endl;
      cout << vo.size() << endl;
      for (auto x: vo) cout << x << endl;
    }
    else {
      cout << rese << endl;
      cout << ve.size() << endl;
      for (auto x: ve) cout << x << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define M 1000000007
//#define M 998244353
const int inf=4e18;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int x,y,z;cin>>x>>y>>z;
	cout<<z<<' '<<x<<' '<<y<<endl;
}

Measured memory_bytes: 256
#!usr/bim/python
#! -*- coding: utf-8 -*-

nk = raw_input()
nk = nk.split()
n,k = map(int,nk)

a = raw_input()
a = a.split()
a = map(int,a)

d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

l = d.values()

ans = 0

if len(l) <= k:
    pass
else:
    l.sort()
    for i in range(len(l)-k):
        ans += l[i]

print ans


Measured memory_bytes: 34812
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int x;
    cin >> x;
    int ans = 1;
    for (int i = 2; i * i <= x; i++)
    {
        int n = i * i;
        while (1)
        {
            if (n * i > x)
                break;
            n *= i;
        }
        ans = max(ans, n);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#define rep(i,n)  for(int i=0; i<n; i++)
#define N 100000
#define ROOT_N 317
using namespace std;

bool is_prime[N+1];

void sieve(){
    rep(i, N) is_prime[i] = true;
    is_prime[1] = false;
    for(int i = 2; i <= ROOT_N; i++){
        if(not is_prime[i]) continue;
        int j = i + i;
        while(j <= N){
            is_prime[j] = false;
            j += i;
        }
    }
}
        
int main(void){
    sieve();
    int parent[ROOT_N];
    rep(i, ROOT_N) parent[i] = 0;
    bool is_like_2017[N];
    rep(i, N) is_like_2017[i] = i%2 == 1 and is_prime[i] and is_prime[(i+1)/2];
    rep(i, N+1){
        parent[i/ROOT_N] += is_like_2017[i];
    }
    
    int q, l, r;
    cin >> q;
    rep(i, q){
        int cnt = 0;
        cin >> l >> r;
        int j = l;
        while(j <= r){
            // cout << "a" << j << endl;
            if(j%ROOT_N == 0 and j+ROOT_N <= r){
                cnt += parent[j/ROOT_N];
                j += ROOT_N;
            }
            else{
                cnt += is_like_2017[j];
                j++;
            }
        }
        cout << cnt << endl;
    }
    
}

Measured memory_bytes: 768
def main(argv)
  (x, y) = gets.chomp.split(' ').map(&:to_i)

  if y == 1 then
    puts (-1).to_s
    return
  end

  if x < y then
    puts x.to_s
  elsif x == y then
    puts (-1).to_s
  else # x > y
    if x % y == 0 then
      puts (-1).to_s
    else # x % y > 0
      puts x.to_s
    end
  end
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1788
# 2309

inputted = list(map(int, input().split()))
N = inputted[0]
M = inputted[1]
A = list(map(int, input().split()))

total_votes = sum(A)
can_select = lambda votes: not (votes < total_votes / (4 * M))
answer = 'Yes' if len(list(filter(can_select, A))) >= M else 'No'

print(answer)


Measured memory_bytes: 3060
use std::io::{self, BufRead};

fn main() {
    let mut tuples = Vec::new();

    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
    for i in 1..n + 1 {
        let a = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
        for _ in 0..a {
            let x_y = lines.next().unwrap().unwrap();
            let mut x_y = x_y.split_whitespace().map(|s| s.parse::<usize>().unwrap());
            let x = x_y.next().unwrap();
            let y = x_y.next().unwrap();
            tuples.push((i, x, y));
        }
    }

    let mut ans = 0;
    for bit in 0..1 << n {
        let mut people = vec![0; n + 1];
        let mut sum = 0;
        for i in 0..n {
            if bit & 1 << i != 0 {
                people[i + 1] = 1;
                sum += 1;
            }
        }

        let valid = !tuples
            .iter()
            .any(|t| people[t.0] == 1 && people[t.1] != t.2);

        if valid && sum > ans {
            ans = sum;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>

int main () {
	int N, T, tp, t;
	scanf ("%d %d", &N, &T);
	long long sum = 0;
	scanf ("%d", &tp);
	for (int i=1; i<N; i++) {
		scanf ("%d", &t);
		int tmp = t - tp;
		sum += (tmp>T)?T:tmp;
		tp = t;
	}
	printf ("%lld\n", sum+T);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <map>
#include <set>
using namespace std;

int main() {
    map<string, set<int> > dict;

    string word;
    int page;

    while (cin >> word >> page) {
        dict[word].insert(page);
    }

    for (map<string, set<int> >::iterator it = dict.begin(); it != dict.end(); ++it) {
        cout << it->first << endl;
        for (set<int>::iterator it2 = it->second.begin(); it2 != it->second.end();) {
            cout << *it2;
            ++it2;
            if (it2 != it->second.end()) {
                cout << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1228
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

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

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


int main() {
    string s;
    cin >> s;
    int begin, end;
    rep(i, s.size()) {
        if (s.at(i) == 'A') {
            begin = i;
            goto next;
        }
    }
    next:
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s.at(i) == 'Z') {
            end = i;
            goto last;
        }
    }
    last:
    cout << end - begin + 1 << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long long ll; 
typedef vector<ll> vi; 
typedef pair<int, int> ii; 
typedef vector<ii> vii; 
typedef vector<vi> vvi;
#define F first
#define S second
#define pb emplace_back
#define M 1000000007
#define watch(x) cout << (#x) << " is " << (x) << endl
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr(i,a,b) for(int i = a; i<= b; i++)
#define all(c) c.begin(), c.end()
 

 
main() {
IOS;
    
    int a, b;
    cin >> a >> b;
    cout << max(max(a+b,a-b), a*b);
    
}
 
/*  Check for base cases such as n == 1
and cases like it where code can fail */

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		bool chk = true;
		for(int i=0;i<N;i++){
			chk &= check(T[i+1],T[i],X[i+1],X[i],Y[i+1],Y[i]);
		}
		Console.WriteLine(chk ? "Yes" : "No");
		
		
	}
	
	bool check(int t1, int t0, int x1, int x0, int y1, int y0){
		if(t1 % 2 != (x1 + y1) % 2) return false;
		if(t0 % 2 != (x0 + y0) % 2) return false;
		return Math.Abs(y1-y0) + Math.Abs(x1-x0) <= (t1 - t0) ;
		
	}
	
	
	
	int N;
	int[] T,X,Y;
	public Sol(){
		N = ri();
		T = new int[N+1];
		X = new int[N+1];
		Y = new int[N+1];
		for(int i=0;i<N;i++){
			var d = ria();
			T[i+1] = d[0];
			X[i+1] = d[1];
			Y[i+1] = d[2];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 15276
#include <stdio.h>

int main(void){
    int N, a[100005], b[100005], c, i;
    scanf("%d", &N);
    for (i=1; i<=N; i++) b[i]=0;
    c=0;
    for (i=1; i<=N; i++) {
        scanf("%d", &a[i]);
        if (a[i]>N) {
            c++;
            continue;
        }
        b[a[i]]++;
    }
    for (i=1; i<=N; i++) {
        if (b[i]>=i) {
            c+=b[i]-i;
            // printf("%d: %d\n", i, b[i]-i);
        }
        else {
            c+=b[i];
            // printf("%d: %d\n", i, b[i]);
        }
        // printf("%d\n", c);
    }
    printf("%d", c);
    return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include <string> 
#include <vector>  
#include<math.h>

#define INF 1000000000
#define LM 55555
using namespace::std;


long Lmax(long x, long y) {
	if (x > y)return x;
	return y;
}

int max(int x, int y) {
	if (x > y)return x;
	return y;
}

long Lmin(long x, long y) {
	if (x < y)return x;
	return y;
}


int min(int x, int y) {
	if (x < y)return x;
	return y;
}

int abs(int a) {
	if (a < 0) {
		return -a;
	}
	return a;
}

long long A,B,C,H,W,X,Y,N, M,num,x,ans,a[10000];
string s[1000], t;

int main() {
	//cin >>H>>W;
	//if (H == 0) {
	//	cout << W << endl;
	//	return 0;
	//}
	//int i = 1;
	//if (H == 1) {
	//	cout << 100 * W << endl;
	//}

	//if (H == 2) {
	//	cout << 10000 * W << endl;
	//}

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> a[i];
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			num++;
		}
	}

	cout << num<<endl;
	return 0;
}




Measured memory_bytes: 384
# frozen_string_literal: true

# ABC 140 B - Buffet

STDIN.gets

input_a = STDIN.gets.split(' ').map(&:to_i)
input_b = STDIN.gets.split(' ').map(&:to_i)
input_c = STDIN.gets.split(' ').map(&:to_i)

s = input_b.inject(:+)

(0..input_a.length - 2).each do |idx|
  s += input_c[input_a[idx] - 1] if input_a[idx + 1] - input_a[idx] == 1
end

puts s


Measured memory_bytes: 1788
// 2014/07/18 Tazoe

#include <iostream>
using namespace std;

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

	bool C[4][13];
	for(int i=0; i<4; i++){
		for(int j=0; j<13; j++){
			C[i][j] = false;
		}
	}

	for(int i=0; i<n; i++){
		char c;
		int m;
		cin >> c >> m;

		if(c=='S'){
			C[0][m-1] = true;
		}
		else if(c=='H'){
			C[1][m-1] = true;
		}
		else if(c=='C'){
			C[2][m-1] = true;
		}
		else if(c=='D'){
			C[3][m-1] = true;
		}
	}

	for(int i=0; i<4; i++){
		for(int j=0; j<13; j++){
			if(!C[i][j]){
				if(i==0){
					cout << "S ";
				}
				else if(i==1){
					cout << "H ";
				}
				else if(i==2){
					cout << "C ";
				}
				else if(i==3){
					cout << "D ";
				}

				cout << j+1 << endl;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   string s,t;
   cin>>s>>t;
   int ans=0;
   for(int i=0;i<s.length();i++)
   {
       if(s[i]!=t[i])ans++;
   }
   cout<<ans<<endl;

}


Measured memory_bytes: 3892
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

int comp(const void *a, const void *b){return (*(int*)a>*(int*)b)-(*(int*)a<*(int*)b);}
int compr(const void *a, const void *b){return (*(int*)a<*(int*)b)-(*(int*)a>*(int*)b);}

#define putchar(c) putc_unlocked((c), stdout)
#define getchar() getc_unlocked(stdin)
uint32_t nextpint(void){ char c=getc_unlocked(stdin); while(c<'0'||'9'<c) c=getc_unlocked(stdin); uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getc_unlocked(stdin); } return x; }
uint64_t nextplong(void){ char c=getc_unlocked(stdin); while(c<'0'||'9'<c) c=getc_unlocked(stdin); uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getc_unlocked(stdin); } return x; }
uint32_t nextstr(char *s){ char c=getc_unlocked(stdin); while(c==' '||c=='\n') c=getc_unlocked(stdin); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getc_unlocked(stdin); } *s='\0'; return len; }
uint32_t nextstrln(char *s){ char c=getc_unlocked(stdin); while(c==' '||c=='\n') c=getc_unlocked(stdin); uint32_t len=0; while(c!='\n'){ *s++=c; len++; c=getc_unlocked(stdin); } *s='\0'; return len; }

void printint(int x){ if(x<0){x=-x; putc_unlocked('-', stdout);}else if(x==0){putc_unlocked('0', stdout);} int d=0; char s[10]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putc_unlocked(s[i], stdout); putc_unlocked('\n', stdout); }
void printlong(long x){ if(x<0){x=-x; putc_unlocked('-', stdout);}else if(x==0){putc_unlocked('0', stdout);} int d=0; char s[20]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putc_unlocked(s[i], stdout); }

inline int max2(const int a, const int b){return a>b?a:b;}
inline int min2(const int a, const int b){return a>b?b:a;}
inline int dif2(const int a, const int b){return a>b?a-b:b-a;}
inline int abs2(const int a){return a>=0?a:-a;}

#define P 1000000007

int k[200000];
int rk[200000];

int getk(int a, int x){
	if(x==1) return a;
	int b = getk(a, x/2);
	b = ((long)b)*b%P;
	if((x&1)==0){
		return b;
	}else{
		return ((long)b)*a%P;
	}
}
 
int comb(int a, int b){
	if(a<b) return 0;
	return ((long)k[a])*rk[b]%P*rk[a-b]%P;
}

void init(int n){
	k[0]=1;
	for(int i=1; i<=n; i++){
		k[i]=k[i-1]*((long)i)%P;
	}	
	rk[n]=getk(k[n], P-2);
	for(int i=n-1; i>=0; i--){
		rk[i]=((long)rk[i+1])*(i+1)%P;
	}
}

int main(void){
	int n=nextpint();
	int a=1;
	for(int i=0; i<n; i++){
		int A=nextpint();
		if(A==a) a++;
	}
	printint(a==1?-1:n-a+1);
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    static int n;
    static int[] a;
    static int[][] costW, costB;
    static char[] c;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        c = new char[2*n+1];
        a = new int[2*n+1];
        for(int i=1;i<=2*n;i++){
            c[i] = sc.next().charAt(0);
            a[i] = sc.nextInt();
        }
        init();
        int[] white = new int[n+1], black = new int[n+1];
        for(int i=1;i<=2*n;i++){
            if(c[i]=='W') white[a[i]]=i;
            else black[a[i]]=i;
        }
        // dp[i][j]: put the first i black and j white balls in the idx of 1~i+j
        int[][] dp = new int[n+1][n+1];
        for(int i=1;i<=n;i++) dp[i][0] = dp[i-1][0]+costB[black[i]-1][i]+costW[black[i]-1][0];
        for(int j=1;j<=n;j++) dp[0][j] = dp[0][j-1]+costB[white[j]-1][0]+costW[white[j]-1][j];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                // candidate1: put the black i as the (i+j)-th ball
                int can1 = dp[i-1][j]+costB[black[i]-1][i]+costW[black[i]-1][j];
                // candidate2: put the white j as the (i+j)-th ball
                int can2 = dp[i][j-1]+costB[white[j]-1][i]+costW[white[j]-1][j];
                dp[i][j] = Math.min(can1,can2);
            }
        }
        System.out.println(dp[n][n]);
    }
    // costW[i][j]: how many white balls with value >j that have idx<=i (1<=i<=2*n)
    static void init(){
        costW = new int[2*n+1][n+1];
        costB = new int[2*n+1][n+1];
        for(int i=1;i<=2*n;i++){
            for(int j=0;j<=n;j++){
                costW[i][j] = costW[i-1][j];
                costB[i][j] = costB[i-1][j];
            }
            if(c[i]=='W') {
                for(int j=0;j<a[i];j++) costW[i][j]++;
            }
            else{
                for(int j=0;j<a[i];j++) costB[i][j]++;
            }
        }
    }
}


Measured memory_bytes: 124316
fun main(args: Array<String>) {
    abc146f()
}

fun abc146f() {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    val s = readLine()!!.reversed().map { it == '0' }.toBooleanArray()

    val moves = mutableListOf<Int>()
    var i = 0

    while (i < s.lastIndex) {
        var move = Math.min(m, s.lastIndex - i)
        while (!s[i + move]) {
            move--
            if (move <= 0) return println(-1)
        }
        moves.add(move)
        i += move
    }

    val answer = moves.reversed().joinToString(" ")

    println(answer)
}


Measured memory_bytes: 41596
import std.algorithm;
import std.math;
import std.range;
import std.ascii;
import std.array;
import std.container;
import std.conv;
import std.numeric;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stderr.writeln(arg);
}

class UnreliableRollingHash(ulong P) {
    // fast but unreliable rolling hash
    // base is P, modulus is 2^64
    ulong[] H;
    this(in string s) { 
        auto N = s.length;
        this.H = new ulong[](N + 1);
        foreach (int i, c; s) {
            H[i + 1] = (H[i] * P + cast(int)(c - 'a' + 1));
        }
    }
    ulong hash(int l, int r) { // [l, r)
        return H[r] - H[l] * pow(P, r - l);
    }
}

void main() {
    int N, M; scanf("%d %d\n", &N, &M);
    auto s = readln.chomp;
    auto hasher = new UnreliableRollingHash!991(s);
    int l = 0, r = 1;
    bool[ulong] appeared;
    foreach (_; 0 .. M) {
        auto q = readln.chomp;
        switch (q) {
            case "L++": l++; break;
            case "L--": l--; break;
            case "R++": r++; break;
            case "R--": r--; break;
            default: assert(false);
        }
        appeared[hasher.hash(l, r)] = true;
    }
    writeln(appeared.keys.length);
}

Measured memory_bytes: 28404
#include <iostream>

using namespace std;

int main(void) {
        int W, H;
        int x, y, r;
        int w, h;

        cin >> W >> H >> x >> y >> r;
        
        w = W - x;
        h = H - y;
        
        if(r > w || r > h || x < 0 || y < 0) {
                cout << "No" << endl;
        } else {
                cout << "Yes" << endl;
        }

        return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using  namespace  std;
using ll=long long;
int main(){
  vector<int> a(3);
  int sum=0;
  for (int i=0;i<3;i++)cin>>a.at(i);
  sort(a.begin(),a.end(),greater<int>());
  for(int i=1;i<3;i++){
    sum+=a.at(i-1)-a.at(i);
}
  cout<<sum<<endl;
}

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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector< ii >
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }

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

int32_t main(){
  DESYNC;
  int n;
  cin >> n;
  for(int i=1; i<=n; i++){
    if(n%i) continue;
    int j = n/i;
    if(0 < i && i < 10 && 0 < j && j < 10){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}




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

int main(){
  int N, sum=0, max=0;
  cin >> N;
  for(int i=0; i<N; i++){
    int x; cin >> x;
    if(x>max) max = x;
    sum+=x;
  }
  sum-=max;
  if(max<sum) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
c = []
for i in range(3):
  c.append(list(map(int,input().split())))

ans = "Yes"
if not(c[0][0] - c[1][0] == c[0][1] - c[1][1] == c[0][2] - c[1][2]):
  ans = "No"
elif not(c[1][0] - c[2][0] == c[1][1] - c[2][1] == c[1][2] - c[2][2]):
  ans = "No"
elif not(c[0][0] - c[0][1] == c[1][0] - c[1][1] == c[2][0] - c[2][1]):
  ans = "No"
elif not(c[0][1] - c[0][2] == c[1][1] - c[1][2] == c[2][1] - c[2][2]):
  ans = "No"
  
print(ans)

Measured memory_bytes: 3064
N = int(input())
mod = 10 ** 9 + 7

# 直大さんの解説風
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
dp[0][3][3][3] = 1

for Length in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                if dp[Length][i][j][k] == 0:
                    continue

                for d in range(4):  # 追加する文字
                    if d == 1 and j == 0 and k == 2:
                        continue
                    if d == 2:
                        if j == 0 and k == 1:
                            continue
                        if j == 1 and k == 0:
                            continue
                        if i == 0 and k == 1:
                            continue
                        if i == 0 and j == 1:
                            continue

                    dp[Length + 1][j][k][d] += dp[Length][i][j][k]
                    dp[Length + 1][j][k][d] %= mod

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)


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

typedef long long ll;
int A,B,C;

int main(){
  int a,b,c,d,e,f;
  while( cin >> a >> b >> c >> d >> e >> f && (a||b||c||d||e||f) ){
    A=a+d; B = b+e; C = c+f;
    //    cout<< A << " "<< B << " " << C << endl;
    int n = min(A,min(B,C));
    int res = 0;
    res = max( res, A/3 + B/3 + C/3 );
    for(int i=n;i>max(-1,n-4);i--){
      res = max( res, i + (A-i)/3 + (B-i)/3 + (C-i)/3 );
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1160
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        String[] lines = getStdin();
        String str = lines[0];
        int n = Integer.parseInt(str);
        String[] sss = new String[n];
        int nums = 1;
        for (int i = 1; i <= n; i++){
            sss[i - 1] = lines[i];
        }     
        Arrays.sort(sss);
        for (int j = 1; j <= n - 1; j++){
            if(!(sss[j-1].equals(sss[j]))){
                nums++;
            }
        }
        System.out.println(nums);
   }
  private static String[] getStdin() {
    Scanner scanner = new Scanner(System.in);
    ArrayList<String> lines = new ArrayList<>();
    while (scanner.hasNext()) {
      lines.add(scanner.nextLine());
    }
    return lines.toArray(new String[lines.size()]);
  }
}

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

int main()
{
    int N, result;
    cin >> N;
    result = 0;
    rep(i, N)
    {
        int l, r;
        cin >> l >> r;
        result += (r - l) + 1;
    }

    cout << result << endl;
}


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

#define NIL -1


int c[1003][1003];
char s[1002];
char t[1002];

int max(int a,int b){
    if(a>b)return a;
    else return b;
}
int seq(int x,int y){
    if(x==-1||y==-1) return 0;
    if(c[x][y]==NIL){
        if(s[x]==t[y])c[x][y]=seq(x-1,y-1)+1;
        else c[x][y]=max(seq(x-1,y),seq(x,y-1));
        
    }
    return c[x][y];
}


int main(){
    int q;
    scanf("%d",&q);
    int i;
    for(i=1;i<=q;i++){
        int j,k;
        for(j=0;j<=1000;j++)for(k=0;k<=1000;k++)c[j][k]=NIL;
    
        scanf("%s %s",s,t);
        printf("%d\n",seq (strlen(s)-1,strlen(t)-1));
        
       
        
    }
    return 0;
}

Measured memory_bytes: 4620
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 

		char[] s = sc.next().toCharArray();
		char[] p = sc.next().toCharArray();
		
		boolean flag = false;
		for (int i = 0; i < s.length; i++) {
			if (s[i] == p[0]) {
				flag = true;
				for (int j = 0; j < p.length; j++) {
					if (s[(i + j) % s.length] != p[j]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					break;
				}
			}
		}

		if (flag) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

		sc.close();
	}
}

Measured memory_bytes: 17320
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int  n ;
  cin >> n ;
  vector<ll> a(n) ;
  vector<ll> b(n+1,0) ;
  REP(i,n){
    cin >> a[i] ;
    b[a[i]]++ ; 
  }
  ll sum = 0 ;
  REP(i,n+1){
    sum += b[i]*(b[i]-1)/2 ;
  }
  REP(i,n){
    cout << sum-b[a[i]]+1 <<endl ;
  }
    
  
  
  
  
  
  return 0 ;
}


Measured memory_bytes: 5760
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


mod = 10**9 + 7


def factorize_dict(n):
    b = 2
    fct = defaultdict(lambda: 0)
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b += 1
    if n > 1:
        fct[n] += 1
    return fct


def main():
    N = in_n()

    prime = defaultdict(int)
    for n in range(1, N + 1):
        d = factorize_dict(n)
        for k, v in d.items():
            prime[k] += v

    ans = 1
    for v in prime.values():
        ans *= (v + 1)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
  string s;
  string a[] ={ "ii", "ww", "()", ")("};

  cin >> s;
  int len = s.length()/2, ans=0;
  for( int i=0;i<len;i++ ){
    int j = s.length()-i-1;
    for( int k=0;k<4;k++ ){
      if( s[i]==a[k][0] && s[j] != a[k][1] )
	ans++;
    }
  }
  if( s.length()%2 && s[len] != 'i' && s[len] != 'w' )
    ans++;

  cout << ans << endl;
}

Measured memory_bytes: 1192
object Main extends App {
    val in = io.Source.stdin.getLines.map(_.split(" ").map(_.toInt))
    for (Array(a, b, n) <- in) {
        var i = n
        var rem = a % b
        var res = 0
        while (i > 0) {
            rem *= 10
            res += rem / b
            rem %= b
            i -= 1
        }
        println(res)
    }
}

Measured memory_bytes: 44196
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
import bisect
ans = 0
for b in B:
    i = bisect.bisect_left(A,b)
    j = bisect.bisect_right(C,b)
    ans += i * (N-j)

print(ans)

Measured memory_bytes: 23164
#include<bits/stdc++.h>
#define For(i, l, r) for (register int i = l, _r = r; i <= _r; ++i)
#define Ford(i, l, r) for (register int i = r, _l = l; i >= _l; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 20;
ll h,w,ans;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
	return x * f;
}

int main()
{
	h=read(),w=read();
	if(h==1||w==1)
	{
		ans=1;
	}
	else if(w%2)
	{
		if(h%2)
			ans=w*(h/2)+w/2+1;
		else
			ans=w*(h/2);
	}
	else
	{
		ans=h*(w/2);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip> 
#include <algorithm>

using namespace std;
const int MAX = 3001;
double dp[MAX];
double c[MAX];
double re;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j > 0;j--)
			dp[j] =dp[j]*(1-c[i]) + dp[j - 1] * c[i];
		dp[0] = dp[0] * (1 - c[i]);
	}
	for (int i = n / 2 + 1; i <= n; i++)
		re += dp[i];
	
	cout <<setprecision(10) << re;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 998244353;

ll modpow(ll a, ll b, ll m = mod) {
  ll r = 1;
  while (b > 0) {
    if (b & 1) r = (r * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return r;
}

ll modinv(ll x, ll m = mod) {
  ll b = m;
  ll u = 1;
  ll v = 0;
  ll tmp;
  while (b) {
    ll t = x / b;
    x -= t * b;
    tmp = x;
    x = b;
    b = tmp;
    u -= t * v;
    tmp = u;
    u = v;
    v = tmp;
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

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

  ll n, m, k;
  cin >> n >> m >> k;

  vector<ll> factorial(400001);
  factorial[0] = 1;
  for (int i = 1; i <= 400000; i++) factorial[i] = (factorial[i-1] * i) % mod;

  vector<ll> n1ci(k+1);
  for (int i = 0; i <= k; i++) n1ci[i] = (((factorial[n-1] * modinv(factorial[(n-1)-i])) % mod) * modinv(factorial[i])) % mod;

  ll ans = 0;
  for (int i = 0; i <= k; i++) {
    ans = (ans + (((n1ci[i] * m) % mod) * modpow(m - 1, n - i - 1)) % mod) % mod;
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
  int K,A,B;
  cin >> K;
  cin >> A >> B;

  string res = "NG";

  for(int i=A; i<=B; i++){
    if(i%K==0){
      res = "OK";
      break;
    }
  }

  cout << res << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    int n, m, L = 0, R = INT_MAX, l, r;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> l >> r;
        L = max(L, l);
        R = min(R, r);
    }
    int ans = R - L + 1;
    if (ans < 0) ans = 0;
    cout << ans << endl;
    return 0;
}

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

int main() {
    int n, y;
    cin >> n >> y;
    for (int i = 0;  i <= n; i++) {
        for (int j = 0; i + j <= n; j++) {
            if(i*10000 + j*5000 + (n-i-j)*1000 == y){
                printf("%d %d %d\n", i, j, n-i-j);
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << "\n";
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Eric
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CSwitches solver = new CSwitches();
        solver.solve(1, in, out);
        out.close();
    }

    static class CSwitches {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            boolean[][] optionsByM = new boolean[m][n];
            boolean[] p = new boolean[m];
            for (int i = 0; i < m; i++) {
                int k = in.nextInt();
                for (int j = 0; j < k; j++) {
                    optionsByM[i][in.nextInt() - 1] = true;
                }
            }

            for (int i = 0; i < m; i++) {
                p[i] = in.nextInt() == 1;
            }

            int max = (int) Math.pow(2, n);
            long comb = 0;
            for (int i = 0; i < max; i++) {
                boolean ok = true;
                for (int j = 0; j < m; j++) {
                    if (!solveMe(optionsByM[j], p[j], i, n))
                        ok = false;
                }
                if (ok)
                    comb++;
            }
            out.println(comb);
        }

        private boolean solveMe(boolean[] options, boolean p, int switches, int n) {
            int nb = 0;
            for (int i = 0; i < n; i++) {
                if (options[i] && (switches & (1 << i)) == (1 << i))
                    nb++;
            }
            boolean ans = nb % 2 == 1;
            return ans == p;
        }

    }
}



Measured memory_bytes: 21844
#include<stdio.h>

int arr[200000];
int a[200000];
int main(){
  int N,suma=0;
  scanf("%d",&N);
  for(int i = 0;i < N;i++){
    scanf("%d",a+i);
  }
  for(int i = N;i > 0;i--){
    int sum = 0;
    for(int j = i*2;j <= N;j += i){
      sum += arr[j-1];
    }
    arr[i-1] = (sum & 1)^a[i-1];
    suma += arr[i-1];
  }
  printf("%d\n",suma);
  for(int i = 0;i < N;i++){
    if(arr[i]){printf("%d ",i+1);}
  }
  return 0;
}


Measured memory_bytes: 2432
n, m = map(int, input().split())
road = [[] for _ in range(n)]
result = [0] * n
def search(loc):
    result[loc] = 1
    if sum(result) == n:
        result[loc] = 0
        return 1
    
    cnt = 0
    for r in road[loc]:
        if result[r] == 0:
            cnt += search(r)
    result[loc] = 0
    return cnt
    

for _ in range(m):
    a, b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
print(search(0))


Measured memory_bytes: 3064
x = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort(reverse=True)
    return divisors

d = make_divisors(x)
for i in d:
    for a in range(1, 10000):
        b = a-i
        if a**5-b**5 == x:
            print(a, b)
            exit()


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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long

static const ll MAX = 1000000;
static const ll INFTY = 1e12;
static const ll MOD = 1000000007;

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;


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

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
deque<pair<int, int>> que;

typedef vector<vector<int> > Matrix;

const ll INF = 1e18;

int main() {

  int N, T, A;
  cin >> N;
  cin >>  T >> A;
  double min_ = 10000000;
  double ondo;
  int ans=0;
  REP(i, N){
    int h; cin >> h;
    ondo = T - h * 0.006;
    if(abs(A-ondo)<min_){
      min_ = abs(A-ondo);
      ans = i+1;
    }
  }
  cout << ans << endl;

}

/*
みんな、くるくるぱーにな〜れ
　∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/



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

long long N, A[87];
long long dp[87];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	dp[1] = 1000;
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1];
		for (int j = 1; j <= i - 1; j++) {
			long long V = dp[j] / A[j];
			long long W = dp[j] + (A[i] - A[j]) * V;
			dp[i] = max(dp[i], W);
		}
	}
	cout << dp[N] << endl;
	return 0;
}

Measured memory_bytes: 3644
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    char[][] A = new char[8][8];
    for (int i = 0; i < H; i++) {
      A[i] = sc.next().toCharArray();
    }
    int count = 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (A[i][j] == '#') {
          count++;
        }
      }
    }
    if (count == H + W - 1) {
      System.out.println("Possible");
    } else {
      System.out.println("Impossible");
    }
  }
}

Measured memory_bytes: 23764