akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

ll calc(int x, int y)
{
    ll ans = INF;

    reple(i, 1, x - 1)
    {
        {
            ll h = (ll)x - (ll)i;
            vll v(3);
            v[0] = (ll)y * (ll)i;
            v[1] = (ll)y * (h / 2);
            v[2] = (ll)y * (h / 2 + h % 2);

            chmin(ans, *max_element(all(v)) - *min_element(all(v)));
        }

        {
            ll h = (ll)x - (ll)i;
            vll v(3);
            v[0] = (ll)i * (ll)y;
            v[1] = h * (y / 2);
            v[2] = h * (y / 2 + y % 2);

            chmin(ans, *max_element(all(v)) - *min_element(all(v)));
        }
    }

    return ans;
}

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

    int H, W;
    cin >> H >> W;

    ll ans = INF;
    chmin(ans, calc(H, W));
    chmin(ans, calc(W, H));

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3588
#include<iostream>
#include<iomanip>

using namespace std;
using ll=long long;

#define rep(i, a, n) for (int i = (a); i < (n); ++i)

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n;
  cin>>n;
  int cnt=0;
  rep(i,1,n+1)cnt+=i;
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define fi first
#define se second
#define db double
#define ld long db
#define ri register int
#define rep(i,a,b) for(ri i=(a);i<=(b);++i)
#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))
#define REP(i,a,b) for(ri i=(a);i>=(b);--i)
#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))
using namespace std;

inline int read(){
	ri x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}

const int N=1e5+5;
int n,k,a[1000],ans;
char s[N],rev[1000],c;
bool vis[N];

int main()
{
	n=read();k=read();a['r']=read();a['s']=read();a['p']=read();
	scanf("%s",s+1);rev['r']='p';rev['s']='r';rev['p']='s';
	rep(i,1,n){
		if(i<=k||!vis[i-k]||s[i]!=s[i-k]){
			c=rev[s[i]];ans+=a[c];vis[i]=1;
		}
	}
	cout<<ans;
	return 0; 
}

Measured memory_bytes: 384
N = int(input())

patterns = []
patterns.append(1)

f = 6
a = 6
while a <= N:
    patterns.append(a)
    a *= f

f = 9
a = 9
while a <= N:
    patterns.append(a)
    a *= f

dp = [float('inf')] * (N + 1)
dp[0] = 0
for n in range(1, N + 1):
    for p in patterns:
        if n - p < 0:
            continue

        dp[n] = min(dp[n - p] + 1, dp[n])


print(dp[-1])


Measured memory_bytes: 9580
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

int N;
long long ans;

int main(){
    cin>>N;
    vector<int> A(N),B(N),C(N);
    rep(i,N)cin>>A[i];
    rep(i,N)cin>>B[i];
    rep(i,N)cin>>C[i];
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    sort(C.begin(),C.end());
    rep(i,N){
        ans+=(lower_bound(A.begin(),A.end(),B[i])-A.begin())*(C.end()-upper_bound(C.begin(),C.end(),B[i]));
    }
    out(ans);
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(){
  int n,max=1,semimax=1,i;
  int a[200001],b[200001];
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    b[i]=a[i];
  }
  
  qsort(b,n,sizeof(int),compare_int);
  
  max=b[n-1];
  semimax=b[n-2];
  
  for(i=0;i<n;i++){
    if(a[i]==max)printf("%d\n",semimax);
    else printf("%d\n",max);
  }
  
  return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
int main () {
  double A, B, H, M;
  cin >> A >> B >> H >> M;
  double d = abs(H * 30 + M * 0.5 - M * 6);
  d = d / 180 * M_PI;
  cout << setprecision(100) << sqrt(pow(A, 2) + pow(B, 2) - A * B * 2 * cos(d)) << endl;
  return 0;
}

Measured memory_bytes: 4228
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>

using namespace std;


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

int64_t lcm(int64_t a, int64_t b) {
    return a * b / gcd(a, b);
}

int main(int argc, char **argv) {
    int n, k;
    cin >> n >> k;

    int sum{0};
    for (int i=0; i<n-1; ++i) {
        sum += i;
    }

    if (sum < k) {
        cout << "-1" << endl;
        return 0;
    }
    int dif = sum - k;
    cout << (dif + n - 1) << endl;
    bool break_flag{false};
    for (int i=1; i<n+1; ++i) {
        for (int j=i+1; j<n+1; ++j) {
            cout << i << " " << j << endl;
            if (i != 1) {
                --dif;
                if (dif == 0) {
                    break_flag = true;
                    break;
                }
            }
        }
        if (dif == 0 || break_flag) break;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int a[1005],b[1005]={0},m,n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int j=n;j>=1;j--){
		b[j]=b[j+1]+a[j];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=a[i]*b[i+1];		
	}
	cout<<ans<<endl;
	return 0; 
} 

Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
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;}
typedef pair<ll,ll> P;


int main()
{
    int n;
    cin>>n;
    map<int,int>mp;
    rep(i,n)
    {
        int a;
        cin >> a;
        if(mp[a]==0)mp[a]=1;
        else if(mp[a]=1)mp.erase(a);
    }
    cout<<mp.size();
    return 0;
}

Measured memory_bytes: 4864
#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
	int num;
  	int ele1, ele2;
  	int res = 0;
  	int max = 0;
  	cin>>num;
  	for (int i =0; i< num; i++)
    {
      cin>>ele1>>ele2;
      if(ele1 == ele2)
      {
        res ++;
        if(res > max)
          max = res;
      }
      else
      {
        res = 0;
      }
    }
  if(max >= 3)
      	cout<<"Yes";
      else
        cout<<"No";
}

Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p[10000]={0};
int main()
{
	 LL n,a,b;
	 cin>>n>>a>>b;
	 vector<LL>v1,v2,v3;
	 for(LL i=0;i<n;i++)
	 {
	 	 cin>>p[i];
	 	 if(p[i]<=a)
	 	 v1.push_back(p[i]);
	 	 else if(p[i]>a&&p[i]<=b)
	 	   v2.push_back(p[i]);
	 	   else
	 	   if(p[i]>b)
	 	   v3.push_back(p[i]);
	 }
//	 sort(v1.begin(),v1.end());
//	 sort(v2.begin(),v2.end());
//	 sort(v3.begin(),v3.end());
LL ans=min(v3.size(),min(v1.size(),v2.size()));
	cout<<ans;
 } 

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

int main() {
  long long a,b;
  cin>>a>>b;
  if(a<=0&&0<=b){
    cout<<"Zero"<< endl;
    return 0;
  }
  long long x=0;
  for(long long i=a;i<=b;i++){
    if(i<0){
      x++;
    }
  }
  if(x%2==0){
    cout<<"Positive"<< endl;
  }
  else{
    cout<<"Negative"<< endl;
  }
}


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

using namespace std;

int main() {
int a, b, c;
cin >> a >> b >> c;
unordered_set<int> s;
s.insert(a); s.insert(b); s.insert(c);
if(s.size()==2) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;


}

Measured memory_bytes: 256
S = input()
N = len(S)

Sa = S[0:(N-1)//2]
Sb = S[(N+3)//2 -1:]

#print(S, Sa, Sb)

def parind(X):
  T = len(X)
  for i in range(T):
    if X[i] != X[T-i-1]:
      return False
  return True

print('Yes' if parind(S) and parind(Sa) and parind(Sb) else 'No')

Measured memory_bytes: 3060
#include <math.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <climits>
using namespace std ;
#define ld long double
#define _ ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL);
#define inp(a) for(auto& i : a) cin >> i;
#define out(a) for(auto i : a){cout << i << ' ';}cout << endl;
#define dbg(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
#define LOCAL
//#define int long long
const int N = 2e5+7 ;
const int INF = 1e9 ;
const int MOD = INF + 7 ;
string s ;
vector<vi> g ;
//int res ;
//vector<bool> vis ;
int n , m ;

/* solution 1 complete search
int dfs(int x, int cnt){
	if(cnt == sz(vis)){
		return 1 ;
	}
	int ans = 0 ;
//	vis[x] = true ;
	for(int i : g[x]){
		if(!vis[i]){
			vis[i] = true ; 
			dfs(i,cnt+1) ;
			vis[x] = false ;
		}
	}
	
	return ans ;
}
*/
// solution2 dp 
int dp[9][1<<9] ;

int dfs(int x, int cnt){
	if(dp[x][cnt] >= 0 ) return dp[x][cnt] ;
	if(cnt == (1 << n ) -1) return 1 ; // if all vetex are visited 
	
	int res = 0 ;
	for(int i : g[x]){
		if((cnt >> i) & 1) continue ;
		res += dfs(i, cnt | (1 << i)) ;
	}
	return dp[x][cnt] = res ;
}
int32_t main(){_
//	int n,k,m ;
	cin >> n >> m ;
	g = vector<vector<int> > (n,vector<int>()) ;
//	vis = vector<bool>(n) ;
	
	for(int i = 0 ; i< m ; i++){
		int x , y ;
		cin >> x >> y ;
		x-- ; y-- ;
		g[x].pb(y) ;
		g[y].pb(x) ;
	}
	ms(dp,-1) ;
	cout << dfs(0,1) << endl ;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans[ohara],a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl,f[ohara];
struct edge{int to,cost;};
map<pair<ll,ll>,ll> mp1;
map<pair<ll,ll>,ll> mp2;
map<pair<pair<ll,ll>,ll>,ll> mp3;

//-------------------------↓↓↓↓↓↓------------------------

void func(ll sp){
    rrep(i,2,n+1){
        if(!f[i]){
            if(sp%i==0){
                while(1){
                    sp/=i;
                    ans[i]++;
                    if(sp%i!=0)break;
                }
            if(sp<=1)break;
            }
        }
    }
    return ;
}

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

    cin>>n;
    pos=0;
    rrep(i,2,10000){
        if(!f[i]){
            for(int j=i+i;j<=10000;j+=i){
                f[j]=true;
            }
        }
    }
    rrep(i,2,n+1){
        func(i);
    }
    rep(i,n+1){
        ans[i]++;
    }
    rep(i,n+1){
        if(ans[i]>=75)cnt++;
    }
    rep(i,n+1){
        rrep(j,0,n+1){
            if(i==j)continue;
            if((ans[i]>=3&&ans[j]>=25))pos++;
        }
    }
    cnt+=pos;
    pos=0;
    rep(i,n+1){
        rrep(j,0,n+1){
            if(i==j)continue;
            if((ans[i]>=5&&ans[j]>=15))pos++;
        }
    }
    cnt+=pos;
    pos=0;
    rep(i,n+1){
        rrep(j,0,n+1){
            rrep(k,0,n+1){
                if(i==j||i==k||j==k)continue;
                if((ans[i]>=3&&ans[j]>=5&&ans[k]>=5))pos++;
            }
        }
    }
    cnt+=pos/2;
    Cout(cnt);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int a[10]={1,2,4,8,16,32,64,128,256,512};
int w;
int main(){
  int b[10];
  int i,j;
  while(scanf("%d",&w)!=EOF){
    j=0;
    for(i=0;i<10;i++)b[i]=0;
    for(i=9;i>=0;i--){
      if(w>=a[i]){
	w-=a[i];
	b[j]=a[i];
	j++;
      }
    }
    for(i=j-1;i>0;i--)printf("%d ",b[i]);
    printf("%d\n",b[i]);
  }
  return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include <utility>

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

    std::vector<std::pair<std::pair<std::string, int>,int>> p;
    for(int i = 0; i < n; i++){
        std::string temp;
        int t;
        std::cin >> temp >> t;
        p.push_back(make_pair(make_pair(temp, -t), i));
    }

    std::sort(p.begin(),p.end());
    for(auto a : p) std::cout << a.second + 1 << std::endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//大小比較(大)
long long int big(long long int a, long long int b) {
	if (a >= b) {
		return a;
	}
	else {
		return b;
	}
}

//大小比較(小)
long long int small(long long int a, long long int b) {
	if (a >= b) {
		return b;
	}
	else {
		return a;
	}
}

main() {
	long long int n, m,k=7;
	char str[5];
	scanf("%s", str);

	if (str[0] == 'o') { k++; }
	else {  }

	if (str[1] == 'o') { k++; }
	else { }
	if (str[2] == 'o') { k++; }
	else { }
	
	printf("%lld", k*100);
}


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

#define rep(i,n) for(int i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;

const int INF = 1001001001;

ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

int f(int x){
    int res = 0;
    while(x%2 == 0){
        x /= 2;
        res++;
    }
    return res;
}

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

    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    rep(i,n){
        a[i] = a[i]/2;
    }

    int t = f(a[0]);
    rep(i,n){
        if(t != f(a[i])){
            cout << 0 << endl;
            return 0;
        }
        a[i] >>= t;
    }
    m >>= t;
    
    ll l = 1;
    rep(i,n){
        l = lcm(l,a[i]);
        if(l > m){
            cout << 0 << endl;
            return 0;
        }
    }
    m /= l;
    int ans = (m+1)/2;
    cout << ans << endl;

    cout << endl;
    return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#define rep(i,j,k) for(register int i = j; i <= k; i++) 
#define dow(i,j,k) for(register int i = j; i >= k; i--)
#define fi first
#define se second
//#define P pair<ull,ull>
//#define PP pair<int,pair<int,int> >
//#define mp(a,b) make_pair(a,b)
#define ll long long
#define ull unsigned long long
using namespace std;
 
inline int read() { 
	int s = 0, t = 1; char c = getchar();
	while( !isdigit(c) ) { if( c == '-' ) t = -1; c = getchar(); }
	while( isdigit(c) ) s = s * 10 + c - 48, c = getchar();
	return s * t;
}

const int N = 2e5+5, p = 1e9+7;
ll fac[N] = {1}, ni[N] = {1,1};
inline ll C(int n,int m) { 
	return fac[n] * ni[m] % p * ni[n-m] % p;
}
inline ll tran(int x1,int y1,int x2,int y2) { 
	return C(x2-x1+y2-y1,y2-y1);
}

int main() {
	int n = read(), m = read(), h = read(), w = read();
	rep(i,1,n+m) fac[i] = fac[i-1] * i % p;
	rep(i,2,n+m) ni[i] = (p - p / i) * ni[p % i] % p;
	rep(i,2,n+m) ni[i] = ni[i-1] * ni[i] % p;
	
	ll ans = 0;
	rep(i,1,n-h) { 
		(ans += tran(1,1,i,w) * tran(i,w+1,n,m)) %= p;
	} 
	cout<<ans<<endl;
	return 0; 
}

Measured memory_bytes: 3328
#pragma comment(linker, "/STACK:512000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#ifdef AIM
#include <sys/resource.h>
#endif
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
  string s = FILENAME;
//    assert(!s.empty());
  freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif

#ifdef AIM
  const rlim_t kStackSize = 256 * 1024 * 1024;
  struct rlimit rl;
  int result;

  result = getrlimit(RLIMIT_STACK, &rl);
  if (result == 0)
  {
    if (rl.rlim_cur < kStackSize)
    {
      rl.rlim_cur = kStackSize;
      result = setrlimit(RLIMIT_STACK, &rl);
      if (result != 0)
      {
        fprintf(stderr, "setrlimit returned result = %d\n", result);
      }
    }
  }
#endif

  precalc();
  cout.precision(10);
  cout << fixed;
  //cin >> t;
  int testNum = 1;
  while (t--) {
      //cout << "Case #" << testNum++ << ": ";
      solve(true);
  }
  cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
  cout.flush();
  auto end = clock();

  usleep(10000);
  print_stats(end - start);
  usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

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

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

//#define int li
//const int mod = 1000000007;

void solve(__attribute__((unused)) bool read) {
  string s;
  cin >> s;
  for (char& c : s) {
    if (c == '?') {
      c = 'D';
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_multiset tree<long long , null_type,less_equal<long long >, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set tree<long long , null_type,less<long long >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;++i)
#define mod 1000000007
const double pi =3.14159265358979323846;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    double a,b,h,m; cin>>a>>b>>h>>m;
    //long double rad = pi * 2 * ((long double)h / 12.0 + ((long double) m / 60.0) / 12.0 - (long double)m / 60.0);
    double theta2=(double)(m*pi)/(30.0);//cout<<theta2<<"\n";
    double theta1=(double)((h*pi)/(6.0) + theta2/(12.0));// cout<<theta1<<"\n";

    long double c=a*a + b*b - (long double)(2*a*b*cos(abs(theta1-theta2)));
    long double res=sqrt(c);
    cout <<fixed;
    cout<<setprecision(20)<<res<<"\n";
    return 0;
}
/**pair<ll,ll>fib(ll n)
{
    if(n==0) return {0,1};
    pair<ll , ll >p=fib(n/2);
    ll c=p.first*(2*p.second - p.first) ;
    ll d=p.second*p.second + p.first*p.first;
    if(n&1) return {d,c+d};
    else return {c,d};
}**/
/**ll biexp(ll a,ll n)
{
    if(n==0) return 1;
    ll res=1;
    while(n>0)
    {
        if(n%2!=0) res*=a;
        a=a*a;
        n=n/2;
    }
    return res;
}**/
/** sieve implementation**/
/**    ll N=100000;
    vector<ll>lp(N+1,0);
    vector<ll>pr;
    for(ll i=2;i<=N;++i)
    {
        if(lp[i]==0)
        {
            lp[i]=i;
            pr.push_back(i);
        }
        for(ll j=0;j<pr.size() and i*pr[j]<=N ;++j)
        {
            lp[i*pr[j]]=pr[j];
        }
    }
    **/
/**bool isprime(ll n)
{
    if(n<2) return false;
    for(ll i=2;i*i<=n;++i)
    {
        if(n%i==0) return false;
    }
    return true;
}**/
/**factors in sqrt(n);
    ll N=100000;
    vector<vector<ll> >factors(N+1);
    for(ll j=1;j<=N;++j)
    {
        for(ll x=1;x*x<=j;++x)
         {
            if(j%x==0)
            {
                factors[j].push_back(x);
                if(j/x != x) factors[j].push_back(j/x);
            }
         }
    }
**/
/**
vector<pair<ll,ll>>primefactors(ll n)
{
    vector<pair<ll,ll> >res; ll ct=0;
    if(!(n&1))
    {
        while(!(n&1))
        {
            ct++; n/=2;
        }
        res.push_back({2,ct});
    }
    ct=0;
    for(ll i=3;i*i<=n;i+=2)
    {
        while(n%i==0)
        {
            ct++; n/=i;
        }
        if(ct>0) res.push_back({i,ct});
        ct=0;
    }
    if(n!=1) res.push_back({n,1});
    return res;
}**/


Measured memory_bytes: 4228
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin >> n;
  string a,b,c;
  cin >> a >> b >>c;
  ll ans = 0;
  REP(i,n){
      if(a[i]!=b[i])ans++;
      if(a[i]!=c[i]&&b[i]!=c[i])ans++;
  }
  cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include<cstdio>
#include<map>

using namespace std;

int main()
{   map< string,int> s;
    int n;
    scanf("%d",&n);
    int i;
    char ch[20];
    int y=0;
    for(i=0;i<n;i++)
    {
        scanf("%s",ch);
        if(s[ch]!=1)
        {   y++;
        s[ch]=1;
        }
    }
    printf("%d\n",y);
    return 0;
}


Measured memory_bytes: 19352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define mat(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define each(x,y) for(auto &(x):(y))
#define var(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { cin >> first; Scan(rest...); }
#define vec(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define em emplace
#define pb pop_back
#define fi first
#define se second
#define get(a, i) get<i>(a)
#define bit_count __builtin_popcount
#define mt make_tuple
inline string zero(int a,string s,char c='0'){return string(a-len(s),c)+s;}
inline string zero(int a,int t,char c='0'){return zero(a, to_string(t), c);}
inline string zero(int a,ll t,char c='0'){return zero(a, to_string(t), c);}
#define mini min_element
#define maxi max_element
#define sum accumulate
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
template <class T> inline void print(T t){cout << t << "\n";}
template <class H, class... T> inline void print(H h, T... t){cout << h << " ";print(t...);}
int v[510][510];
void solve() {
	var(int, h, w);
	rep(i, 1, h + 1) {
		rep(j, 1, w + 1) {
			cin >> v[i][j];
		}
	}
	vector<vi> ans;
	rep(i, 1, h) {
		rep(j, 1, w + 1) {
			if (v[i][j] & 1) {
				ans.eb(vi{i, j, i + 1, j});
				++v[i + 1][j];
			}
		}
	}
	rep(j, 1, w) {
		if (v[h][j] & 1) {
			ans.eb(vi{h, j, h, j + 1});
			++v[h][j + 1];
		}
	}
	print(len(ans));
	each(a, ans) {
		print(a[0], a[1], a[2], a[3]);
	}
}
int main() {
	solve();
	return 0;
}


Measured memory_bytes: 10032
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    A = list(map(int,input().split()))

    dp = [0] * (N+1)
    box = []
    for i in reversed(range(1,N+1)):
        las = N//i
        dp[i] = A[i-1]
        if las >= 2:
            sum = 0
            for j in range(2,las+1):
                sum += dp[i*j] % 2

            dp[i] -= sum
            dp[i] %= 2

        if dp[i] == 1:
            box.append(i)

    print(len(box))
    if len(box) > 0:
        print(*box)


if __name__ == "__main__":
  main()

Measured memory_bytes: 72028
#include<iostream>

#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define p(s) std::cout << s << endl;

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

    int res=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(500*i+100*j+50*k==x) res++;
            }
        }
    }
    p(res)
}

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

using namespace std;

typedef long long ll;
int n;
int f(int i)
{
  return i%10+i/10%10+i/100%10+i/1000%10+i/10000%10;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n;
  int ans = 1e9;
  for (int i = 1; i < n; i++)
  {
    int j = n-i;
    ans = min(ans, f(i)+f(j));
  }
  cout<<ans;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int a,b,c,d,dummy;
    dummy=scanf("%d %d %d %d",&a,&b,&c,&d);
    while(1){
        c-=b;
        if(c<=0){
            printf("Yes");
            break;
        }
        a-=d;
        if(a<=0){
            printf("No");
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1724
from collections import defaultdict


def combi(n):
    if n < 2:
        return 0
    return n * (n-1) // 2


N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)

for a in A:
    d[a] += 1

whole = sum(list(map(combi, list(d.values()))))

diff = []
for i in range(N):
    diff.append(combi(d[A[i]]) - combi(d[A[i]] - 1))

for x in diff:
    print(whole - x)

Measured memory_bytes: 26780
/*
 *
 *
 */

#include <bits/stdc++.h>

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(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 ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SQ(n) (n) * (n)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

int main() {
  double n;
  cin >> n;
  int cnt = 0;
  while(n > 1) {
    n /= 3;
    cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3208
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main()
{
	int n;
	int a[100];
	cin >> n;
	for(int i=0;i<n;i++)
	{
		int t;
		cin >> t;
		for(int j=0;j<t;j++)
		{
			cin >> a[j];
		}
		int max=0,min=0;
		for(int j=1;j<t;j++)
		{
			int x=a[j]-a[j-1];
			if(x>max)max=x;
			if(x<min)min=x;
		}
		cout << max << ' ' << abs(min) << endl;
	}
	return 0;
}

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int a, b;
	cin >> a >> b;
	if(a + b == 15) cout << "+" << endl;
	else if(a * b == 15) cout << "*" << endl;
	else cout << "x" << endl;
	return 0;	
}


Measured memory_bytes: 256
# B - Coins
# https://atcoder.jp/contests/abc087/tasks/abc087_b

# A 500円玉
# B 100円 
# C 50円
A = int(input())
B = int(input())
C = int(input())
X = int(input())

i = 0

for a in range(A+1):
    if (a * 500) == X:
        i += 1
        break

    for b in range(B+1):
        if (a * 500) + (b * 100) == X:
            i += 1
            break

        for c in range(C+1):
            if (a * 500) + (b * 100) + (c * 50)== X:
                i += 1
                break

print(i)

Measured memory_bytes: 3064
#include <iostream>
#include <string>

using namespace std;

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

    int i1 = 0;
    int i2 = original.size()-1;
    int changed = 0;
    for(;i1 < i2;i1++,i2--){
        if(original[i1]!=original[i2]){
            changed++;
        }
    }
    cout << changed << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template<class T>using vv = vector<vector<T>>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)

int main() {
  int in(H); int in(W); int in(D);

  vv<int> A(H, vi(W, 0));
  map<int, pii> m;
  rep(i, H) rep(j, W) {
    int in(A);
    m[A] = pii(i, j);
  }
  vector<ll> cost(H*W+1, 0);
  rep(i, H*W-D+1)
    cost[i+D] = cost[i] + abs(m[i].first - m[i+D].first) + abs(m[i].second - m[i+D].second);
  int in(Q);
  rep(i, Q) {
    int in(l); int in(r);
    cout << cost[r] - cost[l] << endl;
  }

  return 0;
}


Measured memory_bytes: 7808
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(long long N, std::vector<long long> A)
{
}

int main()
{
    long long N;
    scanf("%lld", &N);

    vector<ll> cnt(60);
    for (ll i = 0; i < N; i++)
    {
        ll tmp;
        cin >> tmp;

        for (ll j = 0; j < 60; j++)
        {
            if (tmp & (ll)1 << j)
            {
                cnt[j]++;
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i < 60; i++)
    {
        if(cnt[i] == 0 || cnt[i] == N){
            continue;
        }else{
            ll tmptmp = 1;
            tmptmp = mulMod(tmptmp,cnt[i]);
            tmptmp = mulMod(tmptmp,N-cnt[i]);
            tmptmp = mulMod(tmptmp,powMod(2,i));
            ans += tmptmp;
            ans %= MOD;
        }
    }

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


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

int main()
{
	int N;
	cin >> N;
	map<string, int> list;
	vector<string> strs(N, "");

	repeat(i, N) {
		string s;
		cin >> s;
		strs[i] = s;
	}

	sort(strs.begin(), strs.end());
	int count = 1, max = 1;
	list[strs[0]] = count;
	for(int i = 1; i < N; i++) {
		if (strs[i-1] == strs[i]) {
			count++;
		} else {
			count = 1;
		}
		list[strs[i]] = count;
		if (count > max) max = count;
	}
	string prevStr = "";
	repeat(i, N) {
		if (max == list[ strs[i] ] && prevStr != strs[i]) {
			prevStr = strs[i];
			cout << strs[i] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 26752
n,q = gets.chomp.split(" ").map(&:to_i)
s = gets.chomp
r = []
l = []
q.times do |i|
  l[i],r[i] = gets.chomp.split(" ").map(&:to_i)
end
arr = Array.new(n,0)
pre = ""
cnt = 0
n.times do |i|
  if pre == "A" && s[i] == "C"
    cnt += 1
  end
  arr[i] = cnt
  pre = s[i]
end

q.times do |i|
  if l[i] >= 2
    puts arr[r[i]-1] - arr[l[i]-1]
  else
    puts arr[r[i]-1]
  end
end

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

using i64 = long long;

const int N = 1e5 + 5;

int n, k;

i64 l[N], r[N], s[N], v[N];

int main() {
#ifdef HOME
	freopen("agc8b.in", "r", stdin);
	freopen("agc8b.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	i64 ant(0);

	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
		s[i] = s[i - 1] + v[i]; }

	for (int i = 1; i <= n; ++i)
		l[i] = max(l[i - 1] + v[i], l[i - 1]);
	for (int i = n; i >= 1; --i)
		r[i] = max(r[i + 1] + v[i], r[i + 1]);

	for (int i = 1; i + k - 1 <= n; ++i) {
		ant = max(ant, l[i - 1] + r[i + k] + s[i + k - 1] - s[i - 1]);
		ant = max(ant, l[i - 1] + r[i + k]); }

	cout << ant << endl;

	return 0; }


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

const int MAXN = 21 + 10, MAXSTATUS = (1 << 21) + 10, P = 1e9 + 7;

int n, a[MAXN][MAXN], f[MAXSTATUS];

void add(int& a, int b) { a = a + b > P ? a + b - P : a + b; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    int MAXS = 1 << n;
    f[0] = 1;
    for (int S = 1; S < MAXS; ++S) {
        int tmp = __builtin_popcount(S);
        for (int i = 1; i <= n; ++i) {
            if ((S & (1 << (i - 1))) && a[tmp][i]) {
                add(f[S], f[S ^ (1 << (i - 1))]);
            }
        }
    }
    printf("%d\n", f[MAXS - 1]);
    return 0;
}

Measured memory_bytes: 8448
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	string dummy1, s, dummy2;	
	cin >> dummy1 >> s >> dummy2;

	cout << dummy1.front() << s.front() << dummy2.front() << endl;


	return 0;

}


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

int main()
{
    int N;
    cin >> N;
    int t = N, c = 0;
    while(t > 0)c += t % 10, t /= 10;
    if(N % c == 0)cout << ("Yes") << endl;
    else cout << ("No") << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-9;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

ll num[12525252];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int n;
  cin>>n;
  FOR(i, 1, n+1){
    for(int j=i; j<n+1; j+=i){
      ++num[j];
    }
  }
  ll ans=0;
  FOR(i, 1, n+1){
    ans+=i*num[i];
  }
  cout<<ans<<'\n';
  return 0;
}


Measured memory_bytes: 81748
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

// #define fisier 1

using namespace std;

typedef long long ll;

const int mod = 998244353;
const double dancila = 3.14159265359; // PI 
const double eps = 1e-9;

int n, m, k;

ll pw(ll b, ll e)
{
	ll ans = 1;
	while(e)
	{
		if(e & 1)
			ans = (ans * b) % mod;
		b = (b * b) % mod;
		e >>= 1;
	}
	return ans;
}
ll fact[200002], inv[200002];
ll C(ll n, ll k)
{
	return ((((fact[n] * inv[k]) % mod) * inv[n-k]) % mod);
}
int main()
{

    #ifdef fisier
        ifstream cin("input.in");
        ofstream cout("output.out");
    #endif

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

	cin >> n >> m >> k;
	fact[0] = inv[0] = 1;
	for(int i = 1; i <= n; ++i)
	{
		fact[i] = (fact[i-1] * i) % mod;
		inv[i] = pw(fact[i], mod - 2);
	}
	ll ans = 0;
	for(int i = 0; i <= k; ++i)
	{
		int cc = n - i;
		ll coef = 1LL * m * pw(m-1, cc-1);
		coef %= mod;
		coef = coef * C(n-1, i);
		ans = (ans + coef) % mod;
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 6772
/*
 * Author:  vawait
 * Created Time:  2015/8/22 16:45:15
 * Problem: test.cpp
 */
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define red(i, a, b) for (int i = (a); i >= (b); --i)
#define clr( x , y ) memset(x,y,sizeof(x))
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define sqr(x) ((x) * (x))
typedef long long lint;
const int maxn = 600;
int n , m , f[maxn];

int find(int t)
{
    return f[t] == t ? t : f[t] = find( f[t] );
}

void init()
{
    int x , y;
    rep(i,1,n) f[i] = i;
    rep(i,1,m) {
        scanf("%d%d",&x,&y);
        f[find(x)] = find( y );
    }
}

void work()
{
    int ans = m - n;
    rep(i,1,n) if ( find( i ) == i ) ans ++;
    printf("%d\n",ans);
}

int main()
{
    while ( cin >> n >> m ) {
        init();
        work();
    }
    return 0;
}

Measured memory_bytes: 1228
#include <iostream>

char S[5];

int main(void){
    std::cin >> S;
    if(S[0] == 'S' and S[1] == 'S' and S[2] == 'S'){ std::cout << "0\n"; return 0; }
    else if(S[1] == 'S'){ std::cout << "1\n"; return 0; }
    int cnt = 1;
    if(S[0] == 'R') ++cnt; if(S[2] == 'R') ++cnt;
    std::cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 3596
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// 自分の得意な言語で
		// Let's チャレンジ！！

		Scanner sc = new Scanner(System.in);
		int nm1 = sc.nextInt();
		String[] strArr = sc.next().split("");

		int count = 0;
		for (int i = 0; i < strArr.length - 2; i++) {
			if ("A".equals(strArr[i]) && "B".equals(strArr[i + 1]) && "C".equals(strArr[i + 2])) {
				count++;
			}
		}

		System.out.println(count);

	}
}

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

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const LL mod = 1000000007;

int main()
{
    int n;
    cin >> n;
    VVI v(n, VI(26, 0));
    REP(i, n) {
        string S;
        cin >> S;
        REP(j, S.size()) v[i][S[j]-'a']++;
    }
    
    REP(i, 26) {
        int m = v[0][i];
        REP(j, n) {
            m = min(m, v[j][i]);
        }
        REP(j, m) cout << (char)('a'+i);
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
int64_t GCD(int64_t a,int64_t b){
    return b == 0 ? a : GCD(b, a % b);
   
}
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    vector<int> L(n);//L[i]=a[0]~a[i-1]の最大公約数  
    vector<int> R(n);//R[i]=a[i+1]~a[n-1]の最大公約数   
    L[0]=0,R[n-1]=0;
    for(int i=1;i<=n-1;i++){
        L[i]=GCD(L[i-1],a[i-1]);
    }
    for(int i=n-2;i>=0;i--){
        R[i]=GCD(R[i+1],a[i+1]);
    }
    /*
    rep(i,n){
        cout<<L[i]<<" ";
    }
    cout<<endl;
    rep(i,n){
        cout<<R[i]<<" ";
    }
    */
    int at;
    int gcdmax=0;
    //O(N^2)かかっちゃう
    for(int i=0;i<n;i++){
        //cout<<GCD(L[i],R[i])<<" ";
        if(GCD(L[i],R[i])>gcdmax){
            gcdmax = GCD(L[i],R[i]);
        }
    }
    cout << gcdmax<<endl;
}

Measured memory_bytes: 1408
class Rect
  def initialize(x1,y1,x2,y2)
    @xs = (x1..x2)
    @ys = (y1..y2)
  end
  def include?(x,y)
    @xs.include?(x) and @ys.include?(y)
  end
end

class Link
  attr_reader(:name)
  def initialize(x1,y1,x2,y2,s)
    @rect = Rect.new(x1,y1,x2,y2)
    @name = s
  end
  def hit?(x,y)
    @rect.include?(x,y)
  end
end

class Page
  def initialize(s)
    @name = s
    @links = []
  end
  def add_link(x1,y1,x2,y2,s)
    link = Link.new(x1,y1,x2,y2,s)
    @links << link
  end
  def point(x,y)
    target = @links.find{|link| link.hit?(x,y)}
    return nil if target==nil
    return target.name
  end
end

class PageBuf
  attr_reader(:name)
  attr_accessor(:back, :forward)
  def initialize(name)
    @name = name
    @back = self
    @forward = self
  end
  def set_next(pbuf)
    self.forward = pbuf
    pbuf.back = self
    pbuf
  end
end

loop{
  n = gets.to_i
  break if n==0
  pages = {}
  
  h, w = gets.split.map(&:to_i)
  home = nil
  n.times{
    name, cs = gets.split
    home = name if home==nil
    page = Page.new(name)
    cs.to_i.times{
      args = gets.split
      lname = args.pop
      x1,y1,x2,y2 = args.map(&:to_i)
      page.add_link(x1,y1,x2,y2,lname)
    }
    pages[name] = page
  }
  m = gets.to_i
  pbuf = PageBuf.new(home)
  m.times{
    op, *args = gets.split
    cur = pages[pbuf.name]
    case op
      when "click"
        x, y = args.map(&:to_i)
        link = cur.point(x,y)
        if link
          nbuf = PageBuf.new(link)
          pbuf = pbuf.set_next(nbuf)
        end
      when "back"
        pbuf = pbuf.back
      when "forward"
        pbuf = pbuf.forward
      when "show"
        puts pbuf.name
    end
  }
}


Measured memory_bytes: 6900
#include <bits/stdc++.h>
using namespace std;
int main() {
 int N, X;
 cin >> N >> X;
 
 vector<int> A(N);
 int i=0;
 int count =0;
 while (i<N){
   cin >> A.at(i);
   count += A.at(i);
   i++;
 }
 
 sort(A.begin(), A.end());
 int j = (X - count)/A.at(0);
 
 cout << N + j << endl;


}

Measured memory_bytes: 256
#![allow(unused_imports)]

use std::cmp;
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::io::stdin;
use std::ops::*;
use std::process::exit;
use std::str::FromStr;

fn main() {
    let (n, m): (usize, usize) = input_two();
    let mut ab: Vec<(usize, usize)> = input_lines_two(n);
    ab.sort();
    let mut rest = m;
    let mut ans = 0;

    for (p, c) in ab {
        if c >= rest {
            ans += rest * p;
            break;
        } else if c < rest {
            ans += c * p;
            rest -= c;
        }
    }

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

pub fn input<T: FromStr>() -> T {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().ok().unwrap()
}

pub fn input_vec<T: FromStr>() -> Vec<T> {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim()
        .split_whitespace()
        .map(|x| x.parse().ok().unwrap())
        .collect::<Vec<_>>()
}

pub fn input_lines<T: FromStr>(l: usize) -> Vec<T> {
    let mut res = Vec::new();
    for _i in 0..l {
        res.push(input());
    }
    res
}

pub fn input_lines_two<T: FromStr, U: FromStr>(l: usize) -> Vec<(T, U)> {
    let mut res = Vec::new();
    for _i in 0..l {
        res.push(input_two());
    }
    res
}

pub fn input_lines_three<T: FromStr, U: FromStr, V: FromStr>(l: usize) -> Vec<(T, U, V)> {
    let mut res = Vec::new();
    for _i in 0..l {
        res.push(input_three());
    }
    res
}

pub fn input_two<T: FromStr, U: FromStr>() -> (T, U) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let s: Vec<&str> = buf.split_whitespace().collect();
    (
        s[0].parse::<T>().ok().unwrap(),
        s[1].parse::<U>().ok().unwrap(),
    )
}

pub fn input_three<T: FromStr, U: FromStr, V: FromStr>() -> (T, U, V) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let s: Vec<&str> = buf.split_whitespace().collect();
    (
        s[0].parse::<T>().ok().unwrap(),
        s[1].parse::<U>().ok().unwrap(),
        s[2].parse::<V>().ok().unwrap(),
    )
}

pub fn input_four<T: FromStr, U: FromStr, V: FromStr, W: FromStr>() -> (T, U, V, W) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let s: Vec<&str> = buf.split_whitespace().collect();
    (
        s[0].parse().ok().unwrap(),
        s[1].parse().ok().unwrap(),
        s[2].parse().ok().unwrap(),
        s[3].parse().ok().unwrap(),
    )
}


Measured memory_bytes: 6396
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,r,s,p,t;

int main(){
  ll ans=0;
  cin >> n >> k;
  cin >> r >> s >>p;
  
  string t;cin>>t;


  

  char tt='w';
  int duup=0;
  for(int j=0;j<k;j++){

  tt='w';
  for(int i=j;i<n;i+=k){
    if (t[i]!=tt){
      duup=0;
      if (t[i]=='r')ans+=p;
      if (t[i]=='s')ans+=r;
      if (t[i]=='p')ans+=s;
    }else{
      duup=1-duup;
      if (duup==0){
        if (t[i]=='r')ans+=p;
        if (t[i]=='s')ans+=r;
        if (t[i]=='p')ans+=s;
      }
    }
    tt=t[i];
  }

  }


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


Measured memory_bytes: 512