akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
	int N, L;

	cin >> N >> L;

	int idx =  - L;
	if (idx < 0)
	{
		idx = 0;
	}
	else if (N <= idx)
	{
		idx = N - 1;
	}
	idx++;


	int sum = 0;
	for (int i = 1; i <= N; ++i)
	{
		if (i != idx)
		{
			sum += L + i - 1;
		}
	}

	cout << sum;


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n, a, b, fsm = 0, oca = 0;
	string s;
	bool ans[100000] = {};
	cin >> n >> a >> b;
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'a') {
			if (i - oca < a + b)
				ans[i] = 1;
		}
		if (s[i] == 'b') {
			if (fsm < b && i - oca < a + b)
				ans[i] = 1;
			else if (i - oca < a + b)
				oca++;
			fsm++;
		}
		if (s[i] == 'c') {
			if (i - oca < a + b)
				oca++;
		}
	}
	for (int i = 0; i < n; i++) {
		if (ans[i])
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
    if(*(int *)a>*(int *)b)return -1;
    return 1;
}
int main()
{   
    int k,n;
    scanf("%d%d",&n,&k);
    int h[n];
    long long ans=0;
    for(int i=0;i<n;i++){
        scanf("%d",&h[i]);
    }
    qsort(h,n,sizeof(int),compare);
    for(int i=k;i<n;i++){
        ans+=h[i];
    }printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 1788
n = int(input())
a = list(map(int, input().split()))
mi = min(a)
ma = max(a)
if ma - mi >= 2:
  print('No')
elif ma - mi == 1:
  alone = a.count(mi)
  if alone < ma and (ma - alone) * 2 <= n - alone:
    print('Yes')
  else:
    print('No')
else:
  if mi * 2 <= n or mi == n-1:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 13964
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<map>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
string x,s[200001];
int cnt,n;
map <string,int> a;
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	while(n)
	{
		--n;
		cin>>x;
		if(a[x]==0)
		{
			s[++cnt]=x;
		}
		++a[x];
	}
	sort(s+1,s+1+cnt);
	int Max=0;
	for(int i=1;i<=cnt;++i)
	{
		Max=max(a[s[i]],Max);
	}
	for(int i=1;i<=cnt;++i)
	{
		if(a[s[i]]==Max)
		{
			cout<<s[i]<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 25472
#include<map>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int cnt[11];
int a,b,c;

int main()
{
	cin>>a>>b>>c;
	cnt[a]++;
	cnt[b]++;
	cnt[c]++;
	if(cnt[5]==2&&cnt[7]==1)
	{
		puts("YES");
	}
	else
	{
		puts("NO");
	}
}

Measured memory_bytes: 256
"use strict";

// read lines from stdin
const input = require("fs").readFileSync("/dev/stdin", "utf8").split("\n");

const X = parseInt(input[0]);

let i = 0;
const resultStockList = [];

while (true) {
  const result = Math.pow(i, 5);
  resultStockList.push(result);

  for (let j = 0; j < resultStockList.length; j++) {
    if (
      result - resultStockList[j] === X ||
      resultStockList[j] - result === X
    ) {
      console.log(`${i} ${j}`);
      return;
    }

    if (result + resultStockList[j] === X) {
      console.log(`${i} ${-j}`);
      return;
    }
  }

  i++;
}


Measured memory_bytes: 30456
import java.util.*;
import java.lang.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) {
        //コード
        Scanner scanner = new Scanner(System.in);
        Long n = scanner.nextLong();
        Long k = scanner.nextLong();

        List<Long> listA = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            listA.add(scanner.nextLong());
        }

        if (k > n) {
            System.out.println(0);
            System.exit(0);
        }

        if ( k == 0) {
            Long[] array = listA.toArray(new Long[listA.size()]);
            Long sum = Stream.of(array).mapToLong(Long::longValue).sum();
            System.out.println(sum);
            System.exit(0);
        }

        Collections.sort(listA);
        for(int i = 0; i < k; i++){
            int num = listA.size()-1;
            listA.remove(num);
        }

        Long[] array = listA.toArray(new Long[listA.size()]);
        Long sum = Stream.of(array).mapToLong(Long::longValue).sum();
        System.out.println(sum);
    }
}


Measured memory_bytes: 95216
S=str(input())
'dream' 'dreamer' 'erase' 'eraser'
hantei=True
while S:
  if S[-5:]=='dream':
    S=S[:-5]
  elif S[-7:]=='dreamer':
    S=S[:-7]
  elif S[-5:]=='erase':
    S=S[:-5]
  elif S[-6:]=='eraser':
    S=S[:-6]
  else:
    hantei=False
    break
print('YES' if hantei else 'NO')

Measured memory_bytes: 3188
a1=list(map(int,input().split()))
a2=list(map(int,input().split()))
a3=list(map(int,input().split()))
a=[a1,a2,a3]
n=int(input())
bingo=[[0 for i in range(3)] for j in range(3)]
for k in range(n):
    x=int(input())
    for j in range(3):
        for i in range(3):
            if x==a[j][i]:
                bingo[j][i]+=1
for j in range(3):
    if sum(bingo[j])==3:
        print("Yes")
        exit()
for i in range(3):
    if bingo[0][i]+bingo[1][i]+bingo[2][i]==3:
        print("Yes")
        exit()
if bingo[0][0]+bingo[1][1]+bingo[2][2]==3 or bingo[0][2]+bingo[1][1]+bingo[2][0]==3:
    print("Yes")
    exit()
print("No")


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

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

typedef long long ll;
#define vl vector<ll>
#define vll vector< vector<ll> >
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)

int main() {

	int N; cin >> N;
	vl A(N), B(N), C(N);
	cin >> A[0] >> B[0] >> C[0];

	rep1(i, N) {
		int a, b, c;
		cin >> a >> b >> c;

		A[i] = max(B[i - 1], C[i - 1]) + a;
		B[i] = max(A[i - 1], C[i - 1]) + b;
		C[i] = max(B[i - 1], A[i - 1]) + c;

	}

	cout << max(max(A[N - 1], B[N - 1]), C[N - 1]) << endl;

}


Measured memory_bytes: 2560
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int main(){
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int search = 1;
  int ans = 0;
  rep(i,n){
    if(a[i]==search) search++;
    else ans++;
  }
  if(search == 1) ans = -1;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int l=0, m=0, n=0;
		
		int saving = 0, totalMonth = 0;
		
		while(true) {
			
			l = sc.nextInt();
			if(l == 0) {
				return;
			}
			
			saving = 0;
			totalMonth = 0;
			 
			for(int i = 1; i<=12; i++) {
				m = sc.nextInt();
				n = sc.nextInt();
				saving += m-n;
				
				if(totalMonth == 0 && saving >= l) {
					totalMonth = i;
				}
			}
			
			if(totalMonth > 0) {
				System.out.println(totalMonth);
			} else {
				System.out.println("NA");
			}
				
		}

	}

}

Measured memory_bytes: 42876
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <math.h>
#include <array>
#include <list>
#include <set>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> tup;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vp;
int tmpmin=1e9;
int main(int argc,char const* argv[])
{
  int s;
  int a[1000005];
  set<int> st;
  cin >> s;
  a[1]=s;
  st.insert(s);
  //cout << a[1] << endl;
  for(int i=2;i<=1000000;i++)
    {
      if(a[i-1]%2==0)
	{
	  a[i]=a[i-1]/2;
	  auto it=st.find(a[i]);
	  if(it!=st.end())
	    {
	      cout << i << endl;
	      return 0;
	    }
	  st.insert(a[i]);
	}
      else
	{
	  a[i]=3*a[i-1]+1;
	  auto it=st.find(a[i]);
	  if(it!=st.end())
	    {
	      cout << i << endl;
	      return 0;
	    }
	  st.insert(a[i]);
	}
      //cout << a[i] << endl;
    }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
		  public static void main(String[] args){
		    Scanner sc = new Scanner(System.in);
		    long a = sc.nextInt();
		    long b = sc.nextInt();
		    long ans = ((a+1)/2)*((b+1)/2)+(a/2)*(b/2);  
		    if (a==1||b==1) ans=1;
		    System.out.println(ans);
		  }
		}


Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n, m, x; cin >> n >> m >> x;
	vector<int> c(n);
	vector<vector<int> > a(n, vector<int>(m));
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
		for (int j = 0; j < m; ++j) cin >> a[i][j];
	}
	int ans = 1e9;
	for (int i = 0; i < (1 << n); ++i) {
		int tmp = 0;
		vector<int> t(m);
		for (int j = 0; j < n; ++j) {
			if (i & (1 << j)) {
				tmp += c[j];
				for (int k = 0; k < m; ++k) t[k] += a[j][k];
			}
		}
		bool f = true;
		for (int j = 0; j < m; ++j)
			if (t[j] < x) f = false;
		if (f) ans = min(ans, tmp);
	}
	cout << (ans == 1e9 ? -1 : ans) << endl;

	return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N;cin>>N;
  ll i,j,k,l;
  vector<ll> a(N);
  rep(i,N) cin>>a[i];

  ll sum=0;
  rep(i,N) sum+=a[i];

  bool judge=false;

  ll cnt=0;
  vector<ll> b(3,0);
  // rep(i,b.size()) cout<<b[i]<<endl;
  rep(i,N){
    if(a[i]!=b[0] and a[i]!=b[1] and a[i]!=b[2]){
      cnt++;
      if(b[0]==0) b[0]=a[i];
      else if(b[1]==0) b[1]=a[i];
      else if(b[2]==0) b[2]=a[i];
      else break;
    }
    else continue;
  }
  // rep(i,b.size()) cout<<b[i]<<endl;
  ll s = (b[0]^b[1])^b[2];
  if(cnt==0) judge=true;
  else if(cnt==1 and N%3==0 and sum==b[0]*2*N/3) judge=true;
  else if(cnt==3 and s==0 and N%3==0 and sum==(b[0]+b[1]+b[2])*N/3) judge=true;


  if(judge) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

int main(void)
{
  int n,i,k;
  char m;
  int s[14]={},h[14]={},c[14]={},d[14]={};

  cin >> n;
  for(i=1;i<=n;i++){
    cin >> m >> k;
    if(m=='S' && 1<=k && k<=13) s[k]=1;
    if(m=='H' && 1<=k && k<=13) h[k]=1;
    if(m=='C' && 1<=k && k<=13) c[k]=1;
    if(m=='D' && 1<=k && k<=13) d[k]=1;
  }
  for(i=1;i<=13;i++) if(s[i]==0) cout << "S " << i << endl;
  for(i=1;i<=13;i++) if(h[i]==0) cout << "H " << i << endl;
  for(i=1;i<=13;i++) if(c[i]==0) cout << "C " << i << endl;
  for(i=1;i<=13;i++) if(d[i]==0) cout << "D " << i << endl;

  return 0;
}

Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 998244353;

int main(){
    ll N; cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll al = 0;;
    for (int i = 0; i < N; i++) {
        al = al ^ A[i];
    }

    ll ans;
    for (int i = 0; i < N; i++) {
        ans = al ^ A[i];
        printf("%lld ", ans);
    }
    printf("\n");
}


Measured memory_bytes: 4696
N = int(input())
List = [list(map(int,input().split())) for i in range(N)]

import copy

List.sort(key=lambda x:x[0])

result = float('inf')


for i in range(N):
    if N == 1:
        result = 1
        break
    for j in range(N-i-1):
        p = List[i+j+1][0] - List[i][0]
        q = List[i+j+1][1] - List[i][1]
        tmp_list = copy.deepcopy(List)
        cost = 0
        
        for k in range(N):
            if [tmp_list[0][0] + p, tmp_list[0][1] + q] in List:
                tmp_cost = 0
            else:
                tmp_cost = 1
            cost += tmp_cost
            del tmp_list[0]
        if result > cost:
            result = cost
                    
print(result)

Measured memory_bytes: 3540
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
    

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        string A, B, C;
        A = cin.next();
        B = cin.next();
        C = cin.next();
        Console.WriteLine("{0}{1}{2}", char.ToUpper(A[0]), char.ToUpper(B[0]), char.ToUpper(C[0]));

    }




}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iomanip>
using namespace std;

int main(void){
    long long int n;
    int ans = 100000;
    cin >> n;
    string s;
    int a = int(sqrt(double(n)));
    for(int i = 1; i <= a; i++){
        if(n%i==0){
            s = to_string(n/i);
            int b = s.length();
            ans = min(ans, b);
            //cout << i << ' ' << ans << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll inf = 12345678999999;
const ll wall = -12345678;
bool agct(string s)
{
	for(int i=0;i<s.size();i++)
	{
		if(s[i]!='A'&&s[i] != 'C'&&s[i]!='G'&&s[i]!='T')
			return false;
	}
	return true;
}
int main()
{
	string s;
	cin>>s;
	ll ma = wall;
	//主要的问题是，你能不能列举出所有的情况？ 
	//答案是否定的。
	//为什么不能呢？ 
	for(int pos = 0;pos<s.size();pos++)
	{
		for(int len = 0;len<=s.size();len++)
		{
			string h = s.substr(pos,len);
			if(agct(h))
			{
				ll m = h.size();
				ma = max(ma,m);
			}
		}
	 } 
	cout<<ma<<endl;
	return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){

  int n;
  cin >> n;
  vector<ll> l(n),r(n);
  rep(i,n)cin >> l[i] >> r[i];
  sort(ALL(l));
  sort(ALL(r));
  if(n & 1){
    cout << r[(n)/2]-l[(n)/2]+1 << endl;
  }else{
    cout << fixed<< setprecision(20);
    long double k = (r[(n-1)/2]+r[(n)/2])/2.0-(l[n/2]+l[(n-1)/2])/2.0;
    k *= 2;
    k = k+1;
    ll res = k;
    cout << fixed << setprecision(20);
    cout << res << endl;
  }




  




  return 0;
}


Measured memory_bytes: 6384
#include <iostream>
#include <cstdio>

#include <cstring>
#include <string>

#include <cmath>
#include <algorithm>

#include <vector>
#include <queue>

#include <utility>
#include <map>

// #include <bits/stdc++.h>

#define LL long long
#define vi vector<int>
#define set0(x) memset((x),0,sizeof((x)))
#define set1(x) memset((x),1,sizeof((x)))
#define setmin(x) memset((x),-1,sizeof((x)))
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second

#define MOD 1000000007

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	int n;
	int a[300100];
	LL ans=0;
	cin>>n;
	for(int i=1;i<=3*n;i++) cin>>a[i];
	sort(a+1,a+3*n+1);
	for(int i=3*n-1;i>=n+1;i-=2){
		ans+=a[i];
	}
	cout<<ans<<endl;
	return 0;
}

//1 2 3 4 5 6 7 8 9
//
//1 2 3 4 5 6 7 8 9 10 11 12
//11 9 7 5
//3*3-

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

class Union_Find{
private:
    std::vector<long long> data; //data[i] : 頂点iの親
    long long res;
public:
    Union_Find(int n){
        data.resize(n,-1);
        res = (long long)n * (n-1) / 2;
    }
    //頂点iの親を返す
    int root(int i){
        if(data[i] < 0)return i;
        else return data[i] = root(data[i]);
    }
    //連結
    void unit(int i,int j){
        i = root(i);
        j = root(j);
        if(i != j){
            res -= data[i]*data[j];
            data[i] += data[j];
            data[j] = i;
        }
    }
    long long r_res(){return res;}
};

int main()
{
    int n,m;
    std::cin>>n>>m;
    Union_Find uni(n);
    std::vector<std::pair<int,int>> hashi(m);
    std::vector<long long> ans(m);
    for(int i = 0; i < m; i++){
        std::cin >> hashi[i].first >> hashi[i].second;
        hashi[i].first--;
        hashi[i].second--;
    }
    for(int i = m - 1;i >= 0; i--){
        ans[i] = uni.r_res();
        uni.unit(hashi[i].first,hashi[i].second);
    }
    for(int i = 0; i < m; i++)std::cout<<ans[i]<<std::endl;
}


Measured memory_bytes: 3712
#include <iostream>
using namespace std;
#define MAX 250

int parent(int i){ return i/2;}	//??????id???????????¢??°
int left(int i){ return i*2; }	//????????????id???????????¢??°
int right(int i){ return i*2+1; }	//????????????id???????????¢??°

int main(){
	int H,i;
	int A[MAX+1];	//A[]???1???????????????????????????+1??????

	//??\???
	cin >> H;
	for(int i=1; i<=H; i++) cin >> A[i];
	
	for(int i=1; i<=H; i++){
		cout << "node " << i << ": key = " << A[i] << ", ";
		if(parent(i) >= 1) cout << "parent key = " << A[parent(i)] << ", ";
		if(left(i) <= H) cout << "left key = " << A[left(i)] << ", ";
		if(right(i) <= H) cout << "right key = " << A[right(i)] << ", ";
		cout << endl; 
	}

	return 0;
}

Measured memory_bytes: 1160
import sys
input=sys.stdin.readline
N=int(input())
ALL=0
bit=[0 for i in range(31)]

for i in range(N):
    a=int(input())
    ALL^=a
    B=100
    for j in range(31):
        if a//(2**(30-j))==1:
            B=j
        a%=(2**(30-j))
    bit[B]=1
#print(bit)
all=[0 for i in range(31)]
for j in range(31):
    if ALL//(2**(30-j))==1:
        all[j]+=1
    ALL%=(2**(30-j))
#print(all)
cnt=0
ans=0
for i in range(31):
    if (all[i]+cnt)%2==1:
        if bit[i]>=1:
            ans+=1
            cnt+=1
        else:
            print(-1)
            exit()
print(ans)

Measured memory_bytes: 41068
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const ll LLINF = 1LL<<60;
vector<int> dp;//dp[i + 1] : i円にするための最小動作
int main() {
    int N; cin >> N;
    dp.resize(N + 1);
    rep(i, N)dp[i + 1] = INF;
    for(int i = 1; i <= N; ++i) {
        for(int six = 1;six <= N;six *= 6) {
            if(i >= six){
                dp[i] = min(dp[i], dp[i - six] + 1);
            }
        }
        for(int nine = 1;nine <= N;nine *= 9) {
            if(i >= nine){
                dp[i] = min(dp[i], dp[i - nine] + 1);
            }
        }
    }
    cout << dp[N] << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;
int main(void){
    int a;
    int b;
    cin >> a >> b;
    cout << max({a+b,a-b,a*b}) << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

int main() {
  int n, A, B;
  string s;
  cin >> n >> A >> B >> s;
  int cnt_all = 0, cnt_b = 0;
  rep(i, n) {
    if (s[i] == 'c') puts("No");
    else if (s[i] == 'a') {
      if (cnt_all < A+B) {
        puts("Yes");
        cnt_all++;
      } else puts ("No");
    }
    else {
      if (cnt_all < A+B && cnt_b < B) {
        puts("Yes");
        cnt_all++;
        cnt_b++;
      } else {
        puts("No");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ


int main(){
	int a,b;scanf("%d%d",&a,&b);
	init_C(4100);
	for(int i=2;i<=2*a;i++){
		long long ret=0;
		int pr=min((i-1)/2,(2*a-i+1)/2);

		for(int j=0;j<=min(pr,b);j++){
			long long ks=Comb(pr,j)*pw(2,j)%mod;
			int rem=b-j;
			int hk=j+a-pr*2;
			if(i%2==0)hk--;
			ret=(ret+ks*Comb(rem+hk-1,hk-1))%mod;
			if(i%2==0){
				ret=(ret+ks*Comb(rem+hk-2,hk-1))%mod;
			}
		//	printf("%lld ",ret);
		}
		printf("%lld\n",ret);
	}
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LLMAX (1ll << 60) - 1
#define INTMAX (1 << 30) - 1
#define MOD 1000000007 
#define NMAX 1000*100+1

#define numberOfSetBits(S) __builtin_popcount(S) // __builtin_popcountl(S) __builtin_popcountll(S)
#define MSET(x,y) memset(x,y,sizeof(x))
#define gcd(a,b) __gcd(a,b)
#define all(x)  x.begin(),x.end()
#define isOn(S, j) (S & (1 << j))
#define endl '\n'
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}

#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define vvii vector<vii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define mc(a,b,c) mp(mp(a,b),c)


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x,t,m,y,z;
    string s;
    cin>>s;
    n = s.size();
    ll ans = n;
    for(int i=0;i<n-1;i++){
        if(s[i]^s[i+1]){
            ans=min(ans,max(i+1ll,n-i-1));
        }
    }
    cout<<ans;
    return 0;
}

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

using namespace std;

#define int long long
#define ar array



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

    string s;
    cin >> s;
    vector<int> curr;int var = 0;
    for(int i = 0;i < s.length();i++){
        if(s[i]=='R') var++;
        else{
            if(var>0) curr.push_back(var);
            var=0; 
        }
    }    
    if(var>0) curr.push_back(var);
    sort(curr.begin(), curr.end(), greater<int>());    
    if(curr.size()>=1)cout << curr[0]<<"\n";
    else cout << "0\n";
    return 0;
}


Measured memory_bytes: 3640
#約数8個なので、8、2*4、2*2*2
#8の場合、最小の奇数は3^7で200より大きい
#2*4の場合、最小の奇数は3^3*5^1、次は3^3*7^1、それより大きい場合は200より大きくなる
#2*2*2の場合、最小の奇数は3^1*5^1*7^1、3^1*5^1*11^1,3^1*5^1*13^1それより大きい場合は200より大きくなる

n=int(input())

if n>=195:
    print(5)
elif n>=189:
    print(4)
elif n>=165:
    print(3)
elif n>=135:
    print(2)
elif n>=105:
    print(1)
else:
    print(0)


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

int main() {
  ll x,ans; cin >> x;
  ans = x/11*2;
  if (x%11>0) ans++;
  if (x%11>6) ans++;
  cout << ans << endl;
}

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

using namespace std;
typedef long long ll;

ll a[1000010];
ll n, k;

bool check(ll len) {
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i] / len;
        if (a[i] % len == 0) {
            sum--;
        }
    }
    return sum <= k;
}


int main() {

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll l = 1;
    ll r = 1e9;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << (check(l) ? l : r);

}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int n; cin >> n;
	map<P,int> mp;
	vector<P> p(n);
	double a;
	REP(i,n){
		cin >> a;
		ll b=(a*1000000000+0.1);
		int d2=0, d5=0;
		while(b%2==0){
			b/=2;
			d2++;
		}
		while(b%5==0){
			b/=5;
			d5++;
		}
		d2=min(18,d2);
		d5=min(18,d5);
		mp[{d2,d5}]++;
		p[i]={d2,d5};
	}
	ll ans=0;
	REP(i,n){
		for(int j=max(0ll,18-p[i].first);j<=18;j++){
			for(int k=max(0ll,18-p[i].second);k<=18;k++){
				ans+=mp[{j,k}];
				if(p[i].first==j&&p[i].second==k)
					ans--;
			}
		}
	}
	cout << ans/2 << endl;
	return 0;
}

Measured memory_bytes: 6372
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    while(true){
        ll a,b;cin >> a >>b;
        if(a==0&&b==0)break;
        ll cnt=0;
        for(int i=1;i<=a;i++){
            for(int j=i+1;j<=a;j++){
                for(int k=j+1;k<=a;k++){
                    if(i+j+k==b)cnt++;
                }
            }
        }
        cout << cnt <<endl;
    }
}



Measured memory_bytes: 3112
/* ITP1_6_A:Reversing Numbers */
/* 20181122 */

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void) {
	int A[100], n, i;
	i = 0;

	scanf("%d", &n);
	while(i < n) {
		scanf("%d", &A[i++]);
	}

	while(i--) {
		if(i) {
			printf("%d ", A[i]);
		} else {
			printf("%d", A[i]);
		}
	}

	printf("\n");

	return 0;
}


Measured memory_bytes: 2136
#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <iomanip>
using namespace std;

#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define pb push_back

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

const int mod = (int)1e9 + 7;
const int mod2 = 998244353;

ll exp(ll taban, ll us, ll md) {
    ll carpan = taban % md;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % md;
        temp /= 2;
        carpan = (carpan*carpan) % md;
    }
    return res;
}
 
ll ebob(ll a, ll b){
    if(!a)return b;
    return ebob(b%a, a);
}

ll ekok(ll a, ll b){
    return (a*b)/ebob(a, b);
}
ll mul(ll a, ll b, ll md){
	return a*b % md;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	int a, b, k, c; cin>>a>>b>>k>>c;
	int ans = min(a, c);
	c -= min(a, c);
	c -= min(b, c);
	ans -= min(k, c);
	cout<<ans<<endl;
}

Measured memory_bytes: 3688
#include<stdio.h>
int main(){
    int i, j;
    int n, q;
    int s[20000];
    int t[20000];
    int count = 0;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d", &s[i]);
    }
    scanf("%d", &q);
    for(i=0; i<q; i++){
        scanf("%d", &t[i]);
    }
    for(i=0; i<q; i++){
        for(j=0; j<n; j++){
            if(t[i]==s[j]){
                count += 1;
                break;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  while(cin>>n&&n){
    string s[11] = {};
    ll a;
    rep(i,n){
      cin >> a;
      s[a] += '*';
    }
    rep(i,10){
      if(s[i].size()){
      cout << s[i]<<endl;
      }
      else cout << '-'<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=100010;
int a[N],b[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main() {
    int n;
    long long la=0;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),b[i]=gi();
    for(int i=n;i;i--)
	la+=(b[i]-(a[i]+la)%b[i])%b[i];
    cout<<la;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String w = sc.next();
		char c = w.charAt(0);
		int cc = 0;
		for(int i = 0 ; i < w.length() ; i++){
			if(c == w.charAt(i)){
				cc++;
			}
			String a = c + "";
			if(i == w.length() - 1){
				w = w.replaceAll(a , "");
				if(cc % 2 != 0){
					System.out.println("No");
					break;
				}
				if(w.length() != 0){
					c = w.charAt(0);
					cc = 1;
					i = 0;
				} else if(w.length() == 0){
					System.out.println("Yes");
					break;
				}
			}
		}
		sc.close();
	}
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a,b,c[N][N];
int main()
{
    scanf("%d%d",&a,&b);
    for(int i=1;i<=50;i++)
        for(int j=1;j<=100;j++)
        c[i][j]=1;
    for(int i=51;i<=100;i++)
        for(int j=1;j<=100;j++)
        c[i][j]=2;
    a--;b--;
    for(int i=1;i<50&&a;i+=2)
        for(int j=1;j<=100&&a;j+=2)
    {
        a--;c[i][j]=2;
    }
    for(int i=52;i<=100&&b;i+=2)
        for(int j=1;j<=100&&b;j+=2)
    {
        b--;c[i][j]=1;
    }
    assert(a==0&&b==0);
    printf("100 100\n");
    for(int i=1;i<=100;i++)
        for(int j=1;j<=100;j++)
        printf(j==100?"%c\n":"%c",c[i][j]==1?'#':'.');
}


Measured memory_bytes: 256
K,N = map(int,input().split())
A = [int(n) for n in input().split()]

max = K-A[N-1]+A[0]

for i in range(1,N):
    if max < A[i] - A[i-1]:
        max = A[i] - A[i - 1]


print(K-max)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char a;
    cin >> a;
    if ( a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u' ) cout << "vowel\n";
    else cout << "consonant\n";
}



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

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

const int N = 1e5 + 5, inf = 1e9;

int n, deg[N][2], num, root, col[N];
bool vis[N];
vector <int> adj[N], g[N];

void reset() {
	for (int i = 0; i < n; i++)
		adj[i].clear();
	num++;
}

int dfs_1(int v) {
	vector <int> uno;
	if((deg[v][0] % 2 == 0))
		uno.push_back(v);
	for (auto e : adj[v]) {
		int u = dfs_1(e);
		if(u != inf)
			uno.push_back(u);
	}
	int sz = uno.size();
	while(sz > 1) {
		int x = uno[sz - 1], y = uno[sz - 2];
		uno.pop_back();
		uno.pop_back();
		g[x].push_back(y);
		g[y].push_back(x);
		sz -= 2;
	}
	if(sz)
		return uno[0];
	else
		return inf;
}

void dfs_2(int v) {
	vis[v] = 1;
	for (auto u : g[v]) {
		if(!vis[u]) {
			col[u] = col[v] * -1;
			dfs_2(u);
		}
	}
}

void build() {
	for (int i = 0; i < n; i++) {
		int par;
		cin >> par;
		par--;
		if(par == -2)
			root = i;
		else
			adj[par].push_back(i), deg[par][num]++;
	}
	if(num) {
		for (int i = 0; i < n; i++) {
			if((deg[i][0] & 1) != (deg[i][1] & 1)) {
				cout << "IMPOSSIBLE\n";
				exit(0);
			}
			deg[i][0] &= 1;
		}
	}
	dfs_1(root);
	reset();
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);	
	cin >> n;
	build();
	build();
	for (int i = 0; i < n; i++) {
		deg[i][0] &= 1;
		if(!deg[i][0] && !vis[i]) {
			col[i] = 1;
			dfs_2(i);
		}
	}
	cout << "POSSIBLE\n";
	for (int i = 0; i < n; i++)
		cout << col[i] << " ";
	cout << "\n";
}


Measured memory_bytes: 17024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
typedef pair<int,int> P;
#define mod 1000000007


int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    int sum=0;
    int ans=inf;
    rep(i,n){
        int x;
        cin>>x;
        a[i]=x;
    }
    for(int s=1;s<=100;s++){
        int sum=0;
        rep(i,n) sum+=(a[i]-s)*(a[i]-s);
        ans=min(sum,ans);
    }
    cout << ans <<endl;



    return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;


using ll = long long;

#define int ll

using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;



const int N = 2e5 + 11, mod = 998244353, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 6e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);


//template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, k, ans, f[N], rf[N];
void add(int &a, int b) {
  b %= mod;
  a += b;
  a %= mod;
  if (a < 0) a += mod;
}
int mult(int a, int b) {
  a %= mod;
  b %= mod;
  a *= b;
  a %= mod;
  return a;
}
int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
main() {
  file("threesum");
  ios;
  cin >> n >> m >> k;
  f[0] = 1;
  fo(i, 1, n, 1) f[i] = f[i - 1] * i % mod;
  rf[n] = power(f[n], mod - 2);
  foo(i, n - 1, 0, 1) rf[i] = rf[i + 1] * (i + 1) % mod;
  auto c = [&](int n, int k) { return (f[n] * rf[k] % mod * rf[n - k] % mod); };
  fo(i, 0, k, 1) {
    int cnt = n - i;
    cnt = c(n - i + i - 1, i);
    ans += cnt * m % mod * power(m - 1, n - i - 1) % mod;
    ans %= mod;
  }
  cout << ans;
  return 0;
}
/**
010

https://ioi2019.az/source/Tasks/Day1/Shoes/shoes.pdf - 100
https://ioi2019.az/source/Tasks/Day1/Split/split.pdf - 40
*/


Measured memory_bytes: 6712
#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

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

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


signed main()
{
   int H, W, K;
   cin >> H >> W >> K;

   vec<int> fibo(W,0);
   fibo[0] = 1; fibo[1] = 1;
   rep(i, 2, W) {
      fibo[i] = fibo[i-1] + fibo[i-2];
   }

   vec<vec<int>> dp(H+1, vec<int>(W,0));
   dp[0][0] = 1;
   rep(h, 0, H) {
      rep(w, 0, W) {
         if (w == 0) {
            dp[h+1][w  ] = mod( dp[h+1][w  ] + fibo[w  ] * fibo[W-w-1] * dp[h][w] );
            dp[h+1][w+1] = mod( dp[h+1][w+1] + fibo[w  ] * fibo[W-w-2] * dp[h][w] );
         } else if (w == W-1) {
            dp[h+1][w-1] = mod( dp[h+1][w-1] + fibo[w-1] * fibo[W-w-1] * dp[h][w] );
            dp[h+1][w  ] = mod( dp[h+1][w  ] + fibo[w  ] * fibo[W-w-1] * dp[h][w] );
         } else {
            dp[h+1][w-1] = mod( dp[h+1][w-1] + fibo[w-1] * fibo[W-w-1] * dp[h][w] );
            dp[h+1][w  ] = mod( dp[h+1][w  ] + fibo[w  ] * fibo[W-w-1] * dp[h][w] );
            dp[h+1][w+1] = mod( dp[h+1][w+1] + fibo[w  ] * fibo[W-w-2] * dp[h][w] );
         }
      }
   }

   dump(dp)
   cout << dp[H][K-1] << endl;

   return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
 
struct Point{int x, y;} p[55];
bool lessx(Point &a, Point &b){return a.x < b.x;}

int main(){
  int n, k, v[55], i, j, l, m, cnt;
  long long ans = 4e18;
  scanf("%d%d", &n, &k);
  for(i = 0; i < n; i++){
    scanf("%d%d", &p[i].x, &p[i].y);
    v[i] = p[i].y;
  }
  sort(p, p+n, lessx);
  sort(v, v+n);
  for(i = 0; i <= n-k; i++){
    for(j = i+k-1; j < n; j++){
      for(l = 0; l <= n-k; l++){
        cnt = 0;
        for(m = l; m < n && cnt < k; m++) if(v[i] <= p[m].y && p[m].y <= v[j]) cnt++;
        if(cnt < k) break;
        ans = min(ans, ((long long) v[j] - v[i])*(p[m-1].x - p[l].x));
      }
    }
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
ll pm(int n,int p){
    ll ret = 1;
    ll now = n;
    while(p){
        if(p & 1){
            ret *= now;
            ret %= mod;
        }
        now *= now;
        now %= mod;
        p >>= 1;
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll>v(n + 5,0);
    fr(i,1,n+1) {
        cin >> v[i];
    }
    ll dp[n+ 5][3] = {};
    for (int i = 1 ; i < n+5 ; i++) {
        for (int j = 0 ; j < 3 ; j++) {
            dp[i][j] = -1e18;
        }
    }
    dp[1][0] = v[1];
    dp[2][0] = v[2];
    dp[0][0] = 0;
    for(int i = 3 ; i <= n ; i++) {
        for (int j = 0 ; j <= 2 ; j++) {
            for (int k = 0 ; k <= j ; k++) {
                if (i >= k+2) {
                    //cout << i <<
                    //cout << v[i] << endl;
                    dp[i][j] = max(dp[i][j],dp[i-k-2][j-k]+v[i]);
                }
            }
            //cout << i <<' '<<j<<' '<<dp[i][j]<<endl;
        }

    }
    if (n & 1) {
        ll ans = max({dp[n-1][0],dp[n-2][0],dp[n][2]});
        cout << ans << '\n';
    }
    else {
        ll ans = max({dp[n-1][0],dp[n][0],dp[n][1]});
        cout << ans << '\n';
    }
}

Measured memory_bytes: 9520
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    if(n%1000==0)
    {
        cout<<0;
    }
    else
    {
        cout<<1000-n%1000;
    }

    return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>

#define LE 250001
#define RI 250001
#define N 500000
#define INFTY 2100000000

//void merge(int *,int,int,int);
//void margeSort(int *,int,int);
int g=0;

void merge(int *A, int left,int mid,int right){
  int i,L[LE],R[RI],k,j,n1,n2;
  //printf("???????????????\n\n");
  n1 = mid - left;
  n2 = right - mid;

  //L[0...n1], R[0...n2] ?????????

  for(i=0;i<n1;i++) L[i] = A[left+i];
  for(i=0;i<n2;i++) R[i] = A[mid+i];

 /* for(i = 0; i<(n1-1);i++){
    L[i] = A[left + i];
    printf("???????????????\n\n");
  }*/

 // for(i = 0;i<(n2-1);i++){
    //printf("???????????????\n\n");
    //R[i] = A[mid + i];
    L[n1] = INFTY;
    R[n2] = INFTY;
    i = 0;
    j = 0;
  //}

  for(k = left;k<right;k++){
    g++;
    if( L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
    }
    else{
      A[k] = R[j];
      j = j + 1;
    }
  }
  }

void mergeSort(int *A,int left,int right){
  int mid;
  if(left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}


int main(){
  int n,a[N],i,m;

  scanf("%d",&n);

  for(i=0;i<n;i++) scanf("%d",&a[i]);

  //m = (n-1)/2;

  mergeSort(a,0,n);

  for(i=0;i<n-1;i++) printf("%d ",a[i]);
  printf("%d\n",a[n-1]);
  printf("%d\n",g);
  return 0;
}

Measured memory_bytes: 4504