akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> h(n);
  rep(i, n) cin >> h[i];

  vector<vector<int>> v(n, vector<int> ());

  rep(i, m){
    int from, to;
    cin >> from >> to;
    from--; to--;
    v[from].push_back(to);
    v[to].push_back(from);
  }

  ll res = 0;
  rep(i, n){
    bool flag = false;
    for(int to : v[i]){
      if(h[to] >= h[i]){
        flag = true;
        break;
      }
    }
    if(!flag) res++;
  }

  cout << res << endl;
}


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

#define maxn 311111
#define maxv (maxn*4)

int w,h,n;

struct point
{
	int x,y;
	point(int x=0,int y=0):x(x),y(y){}
	friend bool operator <(point x,point y)
	{
		return x.y<y.y;
	}
};

struct node
{
	int l,r,h;
	node(int l=0,int r=0,int h=0):l(l),r(r),h(h){}
	friend bool operator <(node x,node y)
	{
		return x.h<y.h;
	}
};

struct segment
{
	int mx[maxv];
	int addv[maxv];
	
	void clear()
	{
		memset(mx,0,sizeof(mx));
		memset(addv,0,sizeof(addv));
	}
	
	void dotag(int k,int delta)
	{
		addv[k]+=delta;
		mx[k]+=delta;
	}
	
	void push_down(int k)
	{
		if (!addv[k]) return;
		dotag(k<<1,addv[k]);
		dotag(k<<1|1,addv[k]);
		addv[k]=0;
	}
	
	void push_up(int k)
	{
		mx[k]=max(mx[k<<1],mx[k<<1|1]);
	}
	
	void modify(int pos,int val,int l=1,int r=n,int k=1)
	{
		if (l==r)
		{
			mx[k]=val;
			addv[k]=0;
			return;
		}
		push_down(k);
		int mid=(l+r)>>1;
		if (pos<=mid) modify(pos,val,l,mid,k<<1);
		else modify(pos,val,mid+1,r,k<<1|1);
		push_up(k);
	}
	
	void add(int L,int R,int delta,int l=1,int r=n,int k=1)
	{
		if (L<=l && r<=R)
		{
			dotag(k,delta);
			return;
		}
		push_down(k);
		int mid=(l+r)>>1;
		if (L<=mid) add(L,R,delta,l,mid,k<<1);
		if (mid<R) add(L,R,delta,mid+1,r,k<<1|1);
		push_up(k);
	}
	
	int getmax(int L,int R,int l=1,int r=n,int k=1)
	{
		if (L<=l && r<=R)
		{
			return mx[k];
		}
		push_down(k);
		int mid=(l+r)>>1;
		if (L<=mid && mid<R)
		{
			return max(getmax(L,R,l,mid,k<<1),getmax(L,R,mid+1,r,k<<1|1));
		}
		else if (L<=mid)
		{
			return getmax(L,R,l,mid,k<<1);
		}
		else
		{
			return getmax(L,R,mid+1,r,k<<1|1);
		}
		push_up(k);
	}
};

segment seg;
point p[maxn],tp[maxn];
node stk1[maxn],stk2[maxn];
int ans;

void work(int r)
{
	seg.clear();
	sort(p+1,p+1+n);
	int top1=0,top2=0;
	for(int i=1;i<=n;i++)
	{
		int cx=p[i].x,cy=p[i].y;
		if (i>1) ans=max(ans,seg.getmax(1,i-1)+cy*2);
		if (cx<=r)
		{
			int curh=r-cx;
			int low=-1;
			while (top1 && curh<stk1[top1].h)
			{
				int d=-2*(stk1[top1].h-curh);
				seg.add(stk1[top1].l,stk1[top1].r,d);
				low=stk1[top1].l;
				top1--;
			}
			if (low!=-1) stk1[++top1]=node(low,i-1,curh);
		}
		if (r<=cx)
		{
			int curh=cx-r;
			int low=-1;
			while (top2 && curh<stk2[top2].h)
			{
				int d=-2*(stk2[top2].h-curh);
				seg.add(stk2[top2].l,stk2[top2].r,d);
				low=stk2[top2].l;
				top2--;
			}
			if (low!=-1) stk2[++top2]=node(low,i-1,curh);
		}
		
		stk1[++top1]=node(i,i,r);
		stk2[++top2]=node(i,i,w-r);
		seg.modify(i,2*w-2*cy);
		
	}
}

int main()
{
	scanf("%d%d%d",&w,&h,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].x,&p[i].y);
	
	set<pair<int,int> > temp;
	for(int i=1;i<=n;i++) temp.insert(make_pair(p[i].x,p[i].y));
	if (!temp.count(make_pair(0,0))) p[++n]=point(0,0);
	if (!temp.count(make_pair(0,h))) p[++n]=point(0,h);
	if (!temp.count(make_pair(w,0))) p[++n]=point(w,0);
	if (!temp.count(make_pair(w,h))) p[++n]=point(w,h);
	
	work(w>>1);
	
	swap(w,h);
	for(int i=1;i<=n;i++) swap(p[i].x,p[i].y);
	
	work(h>>1);
	
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 36224
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N;
  cin >> N;
  map<char, ll> cnt;
  string S;
  rep(i, N){
    cin >> S;

    cnt[S[0]]++;
  }

  ll ans = 0;
  ans += cnt['M']*cnt['A']*cnt['R'];
  ans+= cnt['M']*cnt['A']*cnt['C'];
  ans+= cnt['M']*cnt['A']*cnt['H'];
  ans += cnt['M']*cnt['R']*cnt['C'];
  ans += cnt['M']*cnt['R']*cnt['H'];
  ans += cnt['M']*cnt['C']*cnt['H'];
  ans += cnt['A']*cnt['R']*cnt['C'];
  ans += cnt['A']*cnt['R']*cnt['H'];
  ans += cnt['A']*cnt['C']*cnt['H'];
  ans += cnt['R']*cnt['C']*cnt['H'];

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
  int a, b;
  cin >> a >> b;
  int ans = 0;
  if (a >= 13) ans = b;
  else if (6 <= a && a <= 12) ans = b/2;
  else if (a <= 5) ans = 0;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = INF+7;
const ll LINF = 1e18;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define rall(v) v.rbegin(),v.rend()
#define MP make_pair
#define pb(n) push_back(n)
#define int long long

signed main(){
    int N;
    cin >> N;
    vector<int> A(3*N);
    rep(i,3*N) cin >> A[i];
    sort(rall(A));
    int ans = 0;
    for(int i=1;i<2*N;i += 2) ans += A[i];
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

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

	cout << 6 - a - b << endl;
	return 0;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll N;
char S[5555];
ll mk[10];
ll i, j, k,ans;
int main(){
    scanf("%lld%s", &N,S);
    
    fornum(i,0,N){
        if(S[i]=='R')
            ++mk[0];
        if(S[i]=='B')
            ++mk[1];
        if(S[i]=='G')
            ++mk[2];
    }
    ans = mk[0] * mk[1] * mk[2];
    fornum(i,0,N){
        fornum(j,0,N){
            if(i+j*2>=N)
                break;
            ll ia = i + j;
            ll ib = i + j * 2;
            if(S[i]!=S[ia]&&S[ia]!=S[ib]&&S[ib]!=S[i]){
                --ans;
            }
        }
    }
    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 3820
import numpy as np
import math

n = int(input())
x = list(map(int,input().split()))

p1_sum = []
p2_sum = []

p1 = math.floor((1/n) * sum(x))
p2 = math.ceil((1/n) * sum(x))

for i in x:
    p1_sum.append((p1 - i)** 2)
    p2_sum.append((p2 - i)** 2)

print(min(sum(p1_sum),sum(p2_sum)))

Measured memory_bytes: 21644
import java.util.Scanner;
import java.util.Arrays;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int[] H = new int[N];
		for (int i = 0; i < N; i++) {
			H[i] = sc.nextInt();
		}
		Arrays.sort(H);
		int l = 0;
		int r = H[N - 1] % B == 0 ? H[N - 1] / B : H[N - 1] / B + 1;
		while (r - l > 1) {
			long cnt = 0;
			int m = (r + l) / 2;
			for (int i = 0; i < N; i++) {
				int diff = H[i] - B * m;
				if(diff > 0){
					cnt += diff % (A - B) == 0 ? diff / (A - B) : diff / (A - B) + 1;
				}
			}
			if (cnt > m) {
				l = m;
			} else {
				r = m;
			}
		}
		System.out.println(r);
	}
}


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

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

    int sum,res=0;
    for(int i=0;i<=n;i++){
        int s=i;
        string str;
        str = to_string(s);
        sum=0;
        for(int j=0;j<str.size();j++)sum+=str[j]-'0';
        if(sum>=a && sum<=b)res+=i;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))

using namespace std;

#define MOD 1000000007

long n;
#define SZ 50

void mult( const ll a[SZ][SZ], const ll b[SZ][SZ], ll c[SZ][SZ] )
{
    long i, j, m;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            c[i][j] = 0;
            for(m=0; m<n; m++) {
                c[i][j] = (c[i][j] + (a[i][m]*b[m][j])%MOD ) %MOD;
            }
        }
    }
    return;
}

void pow0( const ll a[SZ][SZ], const ll k, ll ans[SZ][SZ] )
{
    long i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            ans[i][j]=(i==j)? 1: 0;
        }
    }
    if(k==0) {
        return;
    }
    else if(k==1) {
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                ans[i][j]=a[i][j];
            }
        }
        return;
    }

    ll tmp[SZ][SZ];
    pow0( a, 1, tmp );
    
    ll m=k;
    for(i=0; m>0; i++) {
        ll tmp2[SZ][SZ];
        if(i>0) {
            mult( tmp, tmp, tmp2 );
            pow0( tmp2, 1, tmp );
        }        
        if(m & 1) {
            mult( ans, tmp, tmp2 );
            pow0( tmp2, 1, ans ); 
        }
        m=m>>1;
    }

    return;
}

int main(int argc, char* argv[])
{
    ll k;
    scanf("%ld %lld", &n, &k );
    
    ll a[SZ][SZ];
    long i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            scanf("%lld", &(a[i][j]));
        }
    }

    ll ans[SZ][SZ];
    pow0( a, k, ans );

    ll sum = 0;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            sum = (sum + ans[i][j]) %MOD;
        }
    }

    printf("%lld\n", sum);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<iomanip>
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*
    long long a,c;
    double b;
    cin>>a>>b;
    c=b*100;
    cout<<fixed<<setprecision(0)<<floor(a*c/100)<<endl;
*/
    long long a;
    string s;
    cin>>a>>s;
    s.erase(1,1);
    long long b=stoll(s);
    cout<<a*b/100;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
int check(int n)
{
	int ans=0;
	while(n!=0)
	{
		ans+=n%10;
		n/=10;
	}
	return ans;
}
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n%check(n)==0) cout<<"Yes";
	else cout<<"No";
}

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

int main() {
    char b;
    cin >> b;
    if (b=='A') cout << 'T';
    else if (b=='C') cout << 'G';
    else if (b=='T') cout << 'A';
    else if (b=='G') cout << 'C';
    return 0;
}


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

// マクロ
// forループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(ll)(b);i--)
// xにはvectorなどのコンテナ
#define ALL(x) (x)begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
// 出力
#define PRINT(x) cout<<(x)<<endl
#define PRINTA(x,n) REP(i,n)PRINT(x[i])
// 定数
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
// 略記
#define PB push_back
#define MP make_pair

int A, B, C, X, Y;

int main() {
    cin >> A >> B >> C >> X >> Y;
    int min_cost = 0;
    if (A + B < 2 * C) {
        min_cost += A * X + B * Y;
    }
    else if (X < Y) {
        min_cost += 2 * C * X;
        if (B < 2 * C) {
            min_cost += B * (Y - X);
        }
        else {
            min_cost += 2 * C * (Y - X);
        }
    }
    else {
        min_cost += 2 * C * Y;
        if (A < 2 * C) {
            min_cost += A * (X - Y);
        }
        else {
            min_cost += 2 * C * (X - Y);
        }
    }
    PRINT(min_cost);
    return 0;
}

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

#define long long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(x) (int)x.size()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define fill(a,v) memset(a,v,sizeof(a))
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define INF 0x3f3f3f3f//infinity for integers
#define JJ ios_base::sync_with_stdio(0); cin.tie(0)//input fast
#define MOD 1000000007
#define hash(n) unordered_map<int,int>mp(n)

int main()
{
	JJ;
	int n; cin>>n;
	
	string str;
	int ac=0,wa=0,tle=0,re=0;

	for(int i=0;i<n;i++){
		cin>>str;
		if(str=="AC")
			ac++;
		else if(str=="WA")
			wa++;
		else if(str=="TLE")
			tle++;
		else if(str=="RE")
			re++;
		
	}
	cout<<"AC x "<<ac<<endl;
	cout<<"WA x "<<wa<<endl;
	cout<<"TLE x "<<tle<<endl;
	cout<<"RE x "<<re<<endl;
	
	
}


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

#define whole(xs) xs.begin(),xs.end()
#define uniq(xs) ((xs).erase(unique((xs).begin(), (xs).end()), (xs).end()))

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < int(vs.size()); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    const int INF = 1<<28;

    int N;
    string S;
    bool input() {
        cin >> N;
        if (N == 0) return false;
        cin >> S;
        return true;
    }

    struct X {
        int bit;
        int n;
        X() {}
        X(int bit, int n) : bit(bit), n(n) {}
    };
    bool operator<(const X& a, const X& b) { return (a.bit == b.bit ? a.n < b.n : a.bit < b.bit); }
    bool operator==(const X& a, const X& b) { return a.bit == b.bit && a.n == b.n; }

    bool dominate(const X& a, const X& b) {
        return a.bit & (1 << b.n);
    }

    bool conflict(const X& a, const X& b) {
        assert((a.bit & b.bit) == 0);
        return dominate(a, b) && dominate(b, a);
    }

    X merge(const X& a, const X& b) {
        assert(dominate(a, b));
        return X(a.bit | b.bit, a.n);
    }

    void solve() {
        vector<string> ss;
        int p = 0;
        for (int i = 0; i < N; i++) {
            if (S[i] == 'u') {
                ss.push_back(S.substr(p, i - p));
                p = i + 1;
            }
        }

        int M = int(ss.size());

        vector<X> xs;
        for (int i = 0; i < M; i++) {
            const string& s = ss[i];
            int bit = 0;
            for (int j = 0; j < int(s.size()); j++) {
                int p = s[j] - '0';
                xs.push_back(X(bit, p));
                if (bit & (1 << p)) {
                    cout << "UNSAFE" << endl;
                    return;
                }
                bit |= (1 << p);
            }
        }

        for (int k = 0; k < 10; k++) {
            sort(whole(xs));
            uniq(xs);
            int T = xs.size();
            vector<bool> used(T, false);
            vector<X> ys;
            for (int i = 0; i < T; i++) {
                X x = xs[i];
                for (int j = i + 1; j < T; j++) {
                    X y = xs[j];
                    if (x.bit & y.bit) continue;
                    if (conflict(x, y)) {
                        cout << "UNSAFE" << endl;
                        return;
                    }
                    if (dominate(x, y)) {
                        xs.push_back(merge(x, y));
                    }
                }
            }
        }

        cout << "SAFE" << endl;
    }
}

int main() {
    while (input()) solve();
    return 0;
}

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

int main()
{
	int n, l;
	cin >> n >> l;
	string S[100];
	for (int i = 0; i < n; ++i)
	{
		cin >> S[i];
	}
	sort(S, S+n);
	for (auto o : S)
	{
		cout << o;
	}
	cout << endl;
	return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int count = 0;
        while(N != 0){
            N /= K;
            count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 22612
# https://kato-robotics.hatenablog.com/entry/2019/07/28/204812

S = input()

MOD = 10 ** 9 + 7

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        for x in range(10):
            for j in range(13):
                dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    else:
        x = int(S[i])
        for j in range(13):
            dp[i+1][(j * 10 + x) % 13] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])

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

const int MAXN = 1e5 + 7;
set<int> G[MAXN]; 
set<int> T[MAXN];

int main() {
    //ifstream cin("E.in");

    int n; cin >> n;

    for(int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        G[a].insert(b);
        G[b].insert(a);
    }

    for(int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        T[a].insert(b);
        T[b].insert(a);
    }

    queue<pair<int, int>> Q;
    set<pair<int, int>> seen;

    for(int i = 0; i < n; ++i)
        for(auto node : G[i])
            if(T[i].find(node) != T[i].end()) {
                auto edge = make_pair(min(node, i), max(node, i));
                if(seen.find(edge) == seen.end()) {
                    Q.push(edge);
                    seen.insert(edge);
                }
            }
    
    int many = 0;

    while(not Q.empty()) {
        auto edge = Q.front();
        Q.pop();

        int a = edge.first, b = edge.second;
            
        if(T[a].empty() or T[b].empty())
            continue;

        many++;

        if(T[a].size() > T[b].size())
            swap(a, b);
        
        vector<pair<int, int>> check;

        for(auto node : T[a]) {
            if(node != b) {
                T[b].insert(node);
                T[node].insert(b);
                T[node].erase(a);
                check.push_back(make_pair(min(b, node), max(b, node)));
            }
        }

        for(auto node : G[a]) {
            if(node != b) {
                G[b].insert(node);
                G[node].insert(b);
                G[node].erase(a);
                check.push_back(make_pair(min(b, node), max(b, node)));
            }
        }
        
        T[b].erase(a);
        G[b].erase(a);

        T[a].clear();
        G[a].clear();
        
        for(auto temp : check) {
            int x = temp.first;
            int y = temp.second;
            if(G[x].find(y) != G[x].end() and T[x].find(y) != T[x].end()) {
                if(seen.find(temp) == seen.end()) {
                    Q.push(temp);
                    seen.insert(temp);
                }
            }
        }
    }
        
    if(many == n - 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }    
}

Measured memory_bytes: 30592
# ABC 87, B - coins

a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if 500 * i + 100 * j + 50 * k == x:
                count += 1

print(count)


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

typedef long long ll;
typedef unsigned long long ull;
#define fr first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const ll MOD = 1000000007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    int l = 0, r = 1000000000;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        int cuts = 0;
        for (int i = 0; i < n; i++) {
            int d = v[i] / mid;
            if (v[i] % mid == 0) d--;
            cuts += d;
        }
        if (cuts <= k) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r;
    return 0;
}


Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
int a[100002];
long long dp[100002][3];
char s[2];
int main(){
    int n;
    scanf("%d", &n);
    scanf("%d", &a[1]);

    for(int i=1;i<=n;i++) dp[i][0] = dp[i][1] = dp[i][2] = -1e18;
    dp[1][0] = a[1];

    for(int i=2;i<=n;i++){
        scanf("%s", s);
        scanf("%d", &a[i]);
        if(s[0] == '-'){
            dp[i][0] = max(dp[i-1][0] - a[i], dp[i-1][1] + a[i]);
            dp[i][1] = max(dp[i-1][0] - a[i], max(dp[i-1][1] + a[i], dp[i-1][2] - a[i]));
            dp[i][2] = max(dp[i-1][2] - a[i], dp[i-1][1] + a[i]);
        }
        else{
            dp[i][0] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i]);
            dp[i][1] = max(dp[i-1][1] - a[i], dp[i-1][2] + a[i]);
            dp[i][2] = dp[i-1][2] + a[i];
        }
        dp[i][0] = max(dp[i][0], -(long long)1e18);
        dp[i][1] = max(dp[i][1], -(long long)1e18);
        dp[i][2] = max(dp[i][2], -(long long)1e18);
    }   
    printf("%lld\n", max(max(dp[n][0], dp[n][1]), dp[n][2]));
}

Measured memory_bytes: 2944
N = int(input())
A = list(map(int,input().split()))
B = set(A)

from collections import Counter
cnt_A = Counter(A)

All = 0
cnt = 0
for a in B:
    cnt = cnt_A[a]
    All +=  cnt*(cnt-1)//2

for k in range(N):
    ans_k = 0
    cnt = cnt_A[A[k]]
    ans_k = cnt - 1
    Ans = All - ans_k
    print(Ans)


Measured memory_bytes: 92008
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int R = Integer.parseInt(tokens[0]);
		int G = Integer.parseInt(tokens[1]);
		int B = Integer.parseInt(tokens[2]);
		int N = Integer.parseInt(tokens[3]);

		in.close();
		long count = 0;
		for (int r = 0; r <= Math.floorDiv(N, R); r++) {
			for (int g = 0; g <= Math.floorDiv(N, G); g++) {
				if (r * R + g * G > N) {
					break;
				}
				if((N-R*r-G*g) % B == 0) {
					++count;
				}
			}
		}
		System.out.println(count);
	}

}

Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


#define MAX(a,b) (((a)>(b))?(a):(b))

typedef struct s_path
{
	int start;
	int end;
	int len;
} t_path;

typedef struct s_vert
{
	int name;
	int *list;
	int num;
} t_vert;

int len_of_vert(int i, t_vert *vs, int *flag, int *dp)
{
	if (vs[i].num == 0)
		return (0);
	if(flag[i] != 0)
	{
		return (dp[i]);
	}
	flag[i] = 1;
	int max = 0;
	int tmp = 0;
	int index = 0;
	while (index < vs[i].num)
	{
		tmp = len_of_vert(vs[i].list[index], vs, flag, dp);
		if (max < tmp)
			max = tmp;
		index++;
	}
	dp[i] = max + 1;
	return (max + 1);
}

int main(void)
{
	int n, m;

	scanf ("%d %d",&n, &m);
	t_vert vs[n+1];
	int x[m],y[m];
	int index = 0;
	int flag[n+1];
	int dp[n+1];
	while (index < n + 1)
	{
		vs[index].num = 0;
		flag[index] = 0;
		dp[index] = 0;
		index++;
	}
	index = 0;
	while (index < m)
	{
		scanf("%d %d",&(x[index]),&(y[index]));
		vs[x[index]].num = vs[x[index]].num + 1;
		index++;
	}
	index = 0;
	while (index < n+1)
	{
		vs[index].list = (int *)malloc(sizeof(int)*(vs[index].num));
		index++;
	}
	int i = 0;
	int j = 0;
	int k[n+1];
	while (j < n+1)
	{
		k[j] = 0;
		j++;
	}
	//printf("AAA\n");
	i = 0;
	while (i < m)
	{
		//printf("i:%d\n",i);
		//printf("x[i];%d\n",x[i]);
		//printf("k[x[i]];%d\n",k[x[i]]);
		//printf("vs[x[i]].num;%d\n",vs[x[i]].num);
		if (vs[x[i]].num > k[x[i]])
		{
			vs[x[i]].list[k[x[i]]] = y[i];
			k[x[i]] = k[x[i]] + 1;
		}
		i++;
	}
	//printf("BBB\n");
	i = 1;
	j = 0;
	int max = 0;
	int p_len = 0;
	i = 0;
	while (i < n+1)
	{
		p_len = len_of_vert(i, vs, flag, dp);
		max = MAX(p_len,max);
		//printf("i;%d\n",i);
		i++;
	}
	printf("%d\n",max);
	return (0);
}


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

typedef long long ll;
const int MAX_H = 300;
const int MAX_W = 300;
const int MAX_Q = 100000;

int main() {
	int H, W, D, Q, L[MAX_Q], R[MAX_Q];
	std::map<int, std::pair<int, int>> A;

	std::cin >> H >> W >> D;
	for(int i = 0; i < H; ++i) {
		for(int j = 0; j < W; ++j) {
			int a;
			std::cin >> a;
			A[a] = std::make_pair(i, j);
		}
	}
	std::cin >> Q;
	for(int i = 0; i < Q; ++i) {
		std::cin >> L[i] >> R[i];
	}

	ll d[MAX_H * MAX_W + 1] = {};
	for(int i = D + 1; i <= H * W; ++i) {
		auto p1 = A[i - D], p2 = A[i];
		d[i] = d[i - D] + std::abs(p1.first - p2.first) + std::abs(p1.second - p2.second);
	}

	for(int i = 0; i < Q; ++i) {
		std::cout << d[R[i]] - d[L[i]] << std::endl;
	}
}

Measured memory_bytes: 8192
def num_divisors_table(n):
    table = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1

    return table
N = int(input())
table = num_divisors_table(N)
ans = 0
for i in range(1,N+1):
    ans += i*table[i]
print(ans)

Measured memory_bytes: 145960
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    ans = sum([1/i for i in A])
    print(1/ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import math


def gcd3(n1, n2, n3):
    return math.gcd(n1, math.gcd(n2, n3))


if __name__ == "__main__":
    k = int(input())
    res = dict()
    sum_ = 0

    for i in range(1, k+1):
        for j in range(i, k+1):
            for l in range(j, k+1):
                if i == j and j == l:
                    sum_ += gcd3(i, j, l)
                elif i != j and j != l and i != l:
                    sum_ += gcd3(i, j, l) * 6
                else:
                    sum_ += gcd3(i, j, l) * 3

    print(sum_)



Measured memory_bytes: 9200
use scanner::Scanner;

fn main() {
    let mut sc = Scanner::new();
    let s = sc.read::<String>();
    println!("{}", if s.len() == 3 { s.chars().rev().collect::<String>() } else { s });
}

mod scanner {
    pub struct Scanner<'a> {
        s: String,
        words: ::std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new() -> Scanner<'a> {
            let s = String::new();
            let words = unsafe { ::std::mem::transmute(s.split_whitespace()) };
            Scanner { s: s, words: words }
        }

        pub fn read<T: ::std::str::FromStr>(&mut self) -> T {
            match self.words.next() {
                Some(x) => x.parse().ok().unwrap(),
                None => {
                    self.load();
                    self.read()
                }
            }
        }

        fn load(&mut self) {
            self.s.clear();
            ::std::io::stdin().read_line(&mut self.s).unwrap();
            self.words = unsafe { ::std::mem::transmute(self.s.split_whitespace()) };
        }
    }
}


Measured memory_bytes: 4352
# -*- coding:utf-8 -*-
s = list(input())
alphabet = [ chr(tmp) for tmp in range(97, 97+26) ]
candinate = []
for tmp1 in alphabet:
    if tmp1 not in s:
        pass
    else:
        sentence = [ a for a in s ]
        ans = 0
        while True:
            if ''.join([tmp1 for tmp3 in range(len(sentence))]) == ''.join(sentence):
                candinate.append(ans)
                break
            for tmp2 in range(len(sentence)-1):
                if sentence[tmp2] == tmp1:
                    pass
                elif sentence[tmp2+1] == tmp1:
                    sentence[tmp2] = sentence[tmp2+1]
                else:
                    pass
            sentence.pop()
            ans += 1
print(min(candinate))

Measured memory_bytes: 3064
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
    remain = B[i] - A[i]
    if remain > 0:
        ans += A[i]
        ans += min(remain, A[i+1])
        A[i+1] = max(0, A[i+1] - remain)
    else:
        ans += B[i]
print(ans)


Measured memory_bytes: 18468
use std::cmp::Ordering;

fn binary_seatch(arr: &Vec<i32>, target: i32) -> Option<u32> {
    let n = arr.len();

    if n <= 0 {
        return None;
    }

    let i_center = n / 2;
    let s_center = arr[i_center];

    match s_center.cmp(&target) {
        Ordering::Less => binary_seatch(&arr[(i_center + 1)..n].to_vec(), target),
        Ordering::Equal => Some(i_center as u32),
        Ordering::Greater => binary_seatch(&arr[0..i_center].to_vec(), target),
    }
}

fn evaluate(inputs_s: Vec<i32>, inputs_t: Vec<i32>) {
    let mut n = 0;
    for &t in &inputs_t {
        match binary_seatch(&inputs_s, t) {
            Some(_) => n += 1,
            None => (),
        }
    }
    println!("{}", n);
}

fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();

    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let inputs_s: Vec<i32> = line.split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();

    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();

    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    let inputs_t: Vec<i32> = line.split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();

    // println!("{:?}", inputs_s);
    // println!("{:?}", inputs_t);

    evaluate(inputs_s, inputs_t);
}



Measured memory_bytes: 7044
#include<iostream>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<limits.h>
using namespace std;

int main() {
    int a,b,c,k;
    cin>>a>>b>>c;
    if(a+b+c>=22)
        cout<<"bust"<<endl;
    else
        cout<<"win"<<endl;
    return 0;
}




Measured memory_bytes: 256
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define fi first
#define se second
#define cl clear()
#define sqr(a) (a*a)
#define mk make_pair
#define po pop()
#define pu push
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
string en="\n";
string sp=" ";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<long long>
#define vs  vector<string>
#define MX LLONG_MAX
#define MN LLONG_MIN
#define MOD 1000000007
#define vp(vi,x) cin>>x; vi.pb(x);
#define bsearch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
LL ceil2(LL a,LL b){LL c=a/b; if(a%b)c++; return c; }
LL bpow(LL a,LL b){if(b==0)return 1;LL r=bpow(a,b/2);if(b%2)return r*r*a;else return r*r;}
LL binpow(LL a,LL b){LL r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
LL binpow(LL a,LL b,LL m){a%=m;LL r=1;while(b>0){if(b&1) r=r*a%m;a=a*a%m; b>>=1;}return r;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
LL fun(LL a,LL b,LL c)
{
    LL r=a*a+b*b+c*c+a*b+b*c+c*a;
    return r;
}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,p,q,a,b,c=0;
    bool f=0,ff=0;string st,s1,s2,s3; char ch;
    map<LL,LL>mp;
    Rep(i,100)
    {
        Rep(j,100)
        {
            Rep(k,100)
            {
                c=fun(i,j,k);
                if(c>10000)break;
                mp[c]++;
            }
        }
    }
    while(cin>>n)
    {
        Rep(i,n)
        {
            cout<<mp[i]<<en;
        }
    }
}




Measured memory_bytes: 4152
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

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

    sort(a, a + N);
   
    int dis = a[N - 1] - a[0];

    cout << dis << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> int_pair;
typedef pair<ll,ll> ll_pair;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const int N=100001;
ll n,a[N],ans=1;
ll dp[N];

int main(){
	cin>>n;
	FOR(i,0,n){
		cin>>a[i];
	}
	fill(dp,dp+n,1e9+1);
	FOR(i,0,n){
		*lower_bound(dp,dp+n,a[i])=a[i];
	}
	cout<<lower_bound(dp,dp+n,1e9+1)-dp<<endl;
	return 0;
}


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

/*
 */

public class ALDS1_9_B
{
    public static void Main(string[] args)
    {
        //var exStdIn = new System.IO.StreamReader( "input.txt" );
        //System.Console.SetIn( exStdIn );

        int n = int.Parse(Console.ReadLine());
        int[] values = Console.ReadLine().Split(' ').Select(value => int.Parse(value)).ToArray();

        for (int i = n / 2 - 1; i >= 0; i--)
        {
            MaxHeapify(values, i, n);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
        {
            sb.AppendFormat(" {0}", values[i]);
        }
        Console.WriteLine(sb.ToString());
    }

    private static void MaxHeapify(int[] values, int i, int n)
    {
        int leftId = (i + 1) * 2 - 1;
        int rightId = leftId + 1;
        int largest = i;
        if (leftId < n && values[leftId] > values[i])
        {
            largest = leftId;
        }
        if (rightId < n && values[rightId] > values[largest])
        {
            largest = rightId;
        }
        if (largest != i)
        {
            int tmp = values[i];
            values[i] = values[largest];
            values[largest] = tmp;
            MaxHeapify(values, largest, n);
        }
    }
}



Measured memory_bytes: 71024
#include <bits/stdc++.h>
using namespace std;
//他の方のを参考にしました(>_<)
int main(){
  int K, S, ans=0;
  cin >> K >> S;
  
  for(int i=max(0, S-2*K) ; i<=min(K, S) ; i++)     //←ここは自分で考えました
    for(int j=max(0, S-K-i) ; j<=min(K, S-i) ; j++) //←ここは自分で考えました
      if(S-K<=i+j && i+j<=S)                        //←ここはパクリました
        ans++;
  
  cout << ans << endl;
}


Measured memory_bytes: 256
//define		FILE_INPUT_DEFINE
#ifdef		FILE_INPUT_DEFINE
#include	<fstream>
#endif		// FILE_INPUT_DEFINE

#include	<iostream>
#include	<algorithm>

using namespace std;

int		A[500001];
int		H;


void maxHeapify(int i)
{
	int		l = i * 2;
	int		r = i * 2 + 1;
	int		largest = i;

	if (l <= H)
	{
		if (A[largest] < A[l])
		{
			largest = l;
		}
	}

	if (r <= H)
	{
		if (A[largest] < A[r])
		{
			largest = r;
		}
	}

	if (largest != i)
	{
		int		temp(A[i]);
		A[i] = A[largest];
		A[largest] = temp;

		maxHeapify(largest);
	}
}

void buildMaxHeap()
{
	for (int i = H / 2; i >= 1; --i)
		maxHeapify(i);
}

int main()
{
#ifdef		FILE_INPUT_DEFINE
	// input from txt
	std::ifstream in(R"(C:\Temp\input.txt)");
	std::cin.rdbuf(in.rdbuf());
#endif		// FILE_INPUT_DEFINE

	cin >> H;

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

	buildMaxHeap();

	for (int i = 1; i <= H; ++i)
	{
		cout << " " << A[i];
	}
	cout << "\n";

	return 0;
}

Measured memory_bytes: 5024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int f[MAX_N]={};
int b[MAX_N]={};

int main() {
    int r,d,x;
    cin>>r>>d>>x;
    rep(i,10){
        x=r*x-d;
        cout<<x<<endl;
    }
	return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <vector>

class Point {
  public:
    int x;
    int y;
    int h;
    Point() {}
    Point(int _x, int _y, int _h) { x = _x; y = _y; h = _h; }
};

int calc_top_height(const Point* p, int cx, int cy)
{
  return p->h + abs(p->x - cx) + abs(p->y - cy);
}

bool is_correct_height(const Point* example, const Point* top)
{
  return std::max(top->h - abs(example->x - top->x) - abs(example->y - top->y), 0) == example->h;
}

bool check_all(const std::vector<Point>* p, const Point* top)
{
  for (const auto& pp : *p) {
    if (!is_correct_height(&pp, top)) {
      return false;
    }
  }
  return true;
}

int main()
{
  int n;
  std::cin >> n;
  std::vector<Point> p;
  for (int i = 0; i < n; i++) {
    int x, y, h;
    std::cin >> x >> y >> h;
    p.emplace_back(x, y, h);
  }
  const Point* base_point = nullptr;
  for (const auto& pp : p) {
    if (0 < pp.h) {
      base_point = &pp;
      break;
    }
  }
  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      int top_height = calc_top_height(base_point, cx, cy);
      Point top(cx, cy, top_height);
      if (check_all(&p, &top)) {
        std::cout << top.x << ' ' << top.y << ' ' << top.h << '\n';
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a[200200];
LL sum[200200]={0},ans=(1LL<<60);
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<n;i++)
    {
        LL snuke=sum[i]-sum[0],raccon=sum[n]-sum[i];
        ans=min(ans,abs(snuke-raccon));
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+7;
ll pow_mod(ll a,ll n)
{
    long long res=1,t=a;
    while(n){
        if(n&1) res=(res*t);
        t=(t*t);
        n/=2;
    }
    return res;
}
int main()
{
    ll n,k;
    cin>>n>>k;
    if(n==1) {cout<<k<<endl; return 0;}
    ll sum;
    sum=k*pow_mod(k-1,n-1);
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.slice(0,-1)).split("\n");
var obj={};
obj[" "]="101";
obj["'"]="000000";
obj[","]="000011";
obj["-"]="10010001";
obj["."]="010001";
obj["?"]="000001";
obj["A"]="100101";
obj["B"]="10011010";
obj["C"]="0101";
obj["D"]="0001";
obj["E"]="110";
obj["F"]="01001";
obj["G"]="10011011";
obj["H"]="010000";
obj["I"]="0111";
obj["J"]="10011000";
obj["K"]="0110";
obj["L"]="00100";
obj["M"]="10011001";
obj["N"]="10011110";
obj["O"]="00101";
obj["P"]="111";
obj["Q"]="10011111";
obj["R"]="1000";
obj["S"]="00110";
obj["T"]="00111";
obj["U"]="10011100";
obj["V"]="10011101";
obj["W"]="000010";
obj["X"]="10010010";
obj["Y"]="10010011";
obj["Z"]="10010000";

obj["00000"]="A";
obj["00001"]="B";
obj["00010"]="C";
obj["00011"]="D";
obj["00100"]="E";
obj["00101"]="F";
obj["00110"]="G";
obj["00111"]="H";
obj["01000"]="I";
obj["01001"]="J";
obj["01010"]="K";
obj["01011"]="L";
obj["01100"]="M";
obj["01101"]="N";
obj["01110"]="O";
obj["01111"]="P";
obj["10000"]="Q";
obj["10001"]="R";
obj["10010"]="S";
obj["10011"]="T";
obj["10100"]="U";
obj["10101"]="V";
obj["10110"]="W";
obj["10111"]="X";
obj["11000"]="Y";
obj["11001"]="Z";
obj["11010"]=" ";
obj["11011"]=".";
obj["11100"]=",";
obj["11101"]="-";
obj["11110"]="'";
obj["11111"]="?";

Arr.forEach(function(v){
   var arr=v.split("");
   var str="";
   for(var i=0;i<arr.length;i++){
      str+=obj[arr[i]];
   }
   while(str.length%5!=0){
      str+="0";
   }
   str=str.replace(/(.....)/g,function(s){
   return obj[s];
   });
   console.log(str);
});

Measured memory_bytes: 10628
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    int n; cin >> n;
    vector<LL> a(3 * n);
    rep(i, 3 * n) {
        cin >> a[i];
    }

    vector<LL> left_sums(n * 2 + 1, 0);
    priority_queue<LL, vector<LL>, greater<LL>> que_left;
    rep(i, n) {
        left_sums[i + 1] = left_sums[i] + a[i];
        que_left.push(a[i]);
    }
    loop(i, n, n * 2) {
        LL mini = que_left.top();
        if (a[i] > mini) {
            left_sums[i + 1] = left_sums[i] - mini + a[i];
            que_left.pop();
            que_left.push(a[i]);
        } else {
            left_sums[i + 1] = left_sums[i];
        }
    }

    vector<LL> right_sums(n * 2 + 1, 0);
    priority_queue<LL> que_right;
    rep(i, n) {
        right_sums[i + 1] = right_sums[i] + a[n * 3 - 1 - i];
        que_right.push(a[n * 3 - 1 -i]);
    }
    loop(i, n, n * 2) {
        LL maxi = que_right.top();
        if (a[n * 3 - 1 - i] < maxi) {
            right_sums[i + 1] = right_sums[i] - maxi + a[n * 3 - 1 - i];
            que_right.pop();
            que_right.push(a[n * 3 - 1 - i]);
        } else {
            right_sums[i + 1] = right_sums[i];
        }
    }

    LL res = -9223372036854775808LL;
    loop(i, n, n * 2 + 1) {
        res = max(res, left_sums[i] - right_sums[n * 3 - i]);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 8052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

int main() {
    double R;
    cin >> R;
    cout << fixed;
    cout << setprecision(10) << R * 2 * PI << endl;
}

Measured memory_bytes: 3784
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long L = scan.nextLong();
		long R = scan.nextLong();
		
		long min = Long.MAX_VALUE;
		
		if(Math.abs(L - R) >= 2019) {
			System.out.println(0);
			scan.close();
			return;
		}
		
		for(long i = L; i < R; i++) {
			for(long j = i + 1; j <= R; j++) {
				if(min > (i * j) % 2019) {
					min = (i * j) % 2019;
				}
			}
		}
		
		System.out.println(min);
		scan.close();
	}

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
// =======================
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long int
#define ull unsigned long long int 
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define ss second
#define setbits(x) _builtin_popcount(x)
#define parity(x) _builtin_parity(x)
#define leadzero(x) __builtin_clz(x)
#define trailzero(x) __builtin_ctz(x)
#define endl "\n"
#define elif else if
// =======================
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pl;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pl>    vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
typedef map<int, int> mii;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
  uniform_int_distribution<int> uid(0,lim-1);
  return uid(rang);
}
int mpow(int base, int exp); 
void yes(){ cout << "YES\n"; }
void no(){  cout << "NO\n";  }

const int mod = 1'000'000'007;
const int N = 3e5, M = N;
// =======================
int arr[100005][3];
int f[100005][3];
int n;
void solve() {
  cin >> n;
  fo(i,n){
    fo(j,3){
     cin >> arr[i][j];
    }
  }
  f[0][0] = arr[0][0];
  f[0][1] = arr[0][1];
  f[0][2] = arr[0][2];
  Fo(i,1,n){
    f[i][0] = arr[i][0] + max(f[i-1][1], f[i-1][2]);
    f[i][1] = arr[i][1] + max(f[i-1][0], f[i-1][2]);
    f[i][2] = arr[i][2] + max(f[i-1][1], f[i-1][0]);
  }
  cout << max({f[n-1][0], f[n-1][1], f[n-1][2]});
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

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

    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}


Measured memory_bytes: 5984
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <fstream>

using namespace std;

#define ll long long
#define INF 2000000000
#define LINF 2000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define dum(x) cout<<#x<<'='<<x<<endl
#define dum2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define dum3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl

//ifstream in("Text.txt");cin.rdbuf(in.rdbuf());


int main() {
    string S;
    int K;
    cin >> S >> K;

    set<string> st;
    rep(i, S.size()) {
        for (int j = 1; j <= K; j++) {
            st.insert(S.substr(i, j));
        }
    }
    auto itr = st.begin();
    rep(i, K - 1) {
        itr++;
    }

    cout << *itr << endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define INF 1e8
typedef long long int ll;
const double PI = acos(-1);

using Graph = vector<vector<int>>;
int main() {
  int n;
  cin >> n;
  if (n % 2 == 0)
    cout << n / 2 << endl;
  else
    cout << n / 2 + 1 << endl;
}


Measured memory_bytes: 3620