akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair< vector<int>, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
vector<int> e(8);
bool a[16777216];
int vtoi(vector<int> vec){
  int ret = 0;
  REP(i,vec.size()){
    ret += vec[i]*pow(8,i);
  }
  return ret;
}
int main(void){
  REP(i,8)e[i] = i;
  memset(a,0,sizeof(a));
  queue<P> que;
  que.push(P(e,0));
  map< const string , int > data;
  while(!que.empty()){
    P nq = que.front();
    que.pop();
    vector<int> n = nq.first;
    string array;
    REP(i,8) array += '0'+n[i];
    int time = nq.second;
    data[array] = time;
    a[ vtoi(n) ] = true;
    int zeroi = -1;
    REP(i,8)if(n[i]==0) zeroi = i;
    if(zeroi<4){
      vector<int> tmp = n;
      swap(tmp[zeroi],tmp[zeroi+4]);
      if(!a[vtoi(tmp)])
        que.push(P(tmp,time+1));
    }
    if(zeroi>3){
      vector<int> tmp = n;
      swap(tmp[zeroi],tmp[zeroi-4]);
      if(!a[vtoi(tmp)])
        que.push(P(tmp,time+1));
    }
    if(zeroi!=0&&zeroi!=4){
      vector<int> tmp = n;
      swap(tmp[zeroi],tmp[zeroi-1]);
      if(!a[vtoi(tmp)])
        que.push(P(tmp,time+1));
    }
    if(zeroi!=3&&zeroi!=7){
      vector<int> tmp = n;
      swap(tmp[zeroi],tmp[zeroi+1]);
      if(!a[vtoi(tmp)])
        que.push(P(tmp,time+1));
    }
  }
  vector<int> in(8);
  while(cin>>in[0]){
    REP(i,7)cin>>in[i+1];
    string ary;
    REP(i,8) ary += '0' + in[i];
    cout<<data[ary]<<endl;
  }
  return 0;
}

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

int getCost(int arr[], int N, int target){
	int cost = 0;
    for(int i=0; i<N; i++){
        int diff = arr[i]-target;
    	cost += diff*diff;
    }
  	return cost;
}
int main(){
  int N;
  cin >> N;
  int arr[N];
  int min = 200;
  int max = -200;
  int minCost;
  for(int i=0; i<N; i++){
  	cin >> arr[i];
    if(arr[i] < min){
    	min = arr[i];
    }else if(arr[i] > max){
    	max = arr[i];
    }
  }
  minCost = getCost(arr, N, min);
  for(int i=min+1; i<=max; i++){
  	int cost = getCost(arr, N, i);
    if( cost < minCost ){
      minCost = cost;
    }
  }
  cout << minCost << '\n';
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  //入力を受け取る
  int N = 0;
  cin >> N; //現在のレート2002
  
  int A = 0;
  cin >> A;
  
  //マス目の計算
  cout << (N * N) - A;
  
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
 
using namespace std;
using S = set<long long>;
using D = deque<long long>;
using L = vector<long long>;
using M = map<int,long long>;
using A = vector<vector<long long>>;
using Q = priority_queue<long long>;
using U = unordered_map<int,long long>; //mapとの違いはkeyの順番を保持していない

#define sorted(vector) sort(vector.begin(),vector.end()) //O(nlongn)
#define sortedreverce(vector) sort(vector.rbegin(),vector.rend()) //O(nlongn)
#define vmin(vector) *min_element(vector.begin(),vector.end()) //O(N)
#define vmax(vector) *max_element(vector.begin(),vector.end()) //O(N)
#define vsum(vector) accumulate(vector.begin(),vector.end(),0) //O(N)
#define vcount(vector,a) count(vector.begin(), vector.end(),a) //O(N)
#define bisect_left(vector,a) (lower_bound(vector.begin(),vector.end(),a)-vector.begin())
#define bisect_right(vector,a) (upper_bound(vector.begin(),vector.end(),a)-vector.begin())
#define vfind(vector,a) find(vector.begin(), vector.end(), a) != vector.end() //遅いからあんまり使うな
//存在確認はmap!!!!!!!!!!!!!か配列に埋め込んでcontinueで回避
//__gcd(a,b)はコンパイラがGCC時のみ

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n,tmp,pre;
    cin>>n;
    cin>>pre;
    for(int i=0  ;i<n-1  ;i++){
        cin>>tmp;
        pre=__gcd(pre,tmp);
    }
    cout<<pre<<endl;
    
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 55
#define M 125555
int sz[N],su[N],dp[M],n,v,d,f[N],s[N],tp[N],ct,as;
bool cmp(int i,int j){return 1.0*su[i]/sz[i]<1.0*su[j]/sz[j];}
int solve(int s1,int r)
{
	if(s1<0)return -1e9;
	int as=0;
	for(int i=1;i<=r;i++)
	{
		int tp=s1/su[s[i]];
		if(tp>d&&sz[s[i]]!=n)tp=d;
		s1-=tp*su[s[i]],as+=tp*sz[s[i]];
		if(sz[s[i]]==n||tp<d)return as;
	}
	return as;
}
int main()
{
	scanf("%d%d%d%d",&n,&v,&d,&su[1]);sz[1]=1;
	for(int i=2;i<=n;i++)scanf("%d%d",&su[i],&f[i]),sz[i]=1;
	for(int i=n;i>=0;i--)
	{
		sz[f[i]]+=sz[i];
		if(su[f[i]]+su[i]>1e9)su[f[i]]=1e9+1;
		else su[f[i]]+=su[i];
	}
	for(int i=1;i<=n;i++)if(su[i]<=1e9)su[++ct]=su[i],sz[ct]=sz[i],s[ct]=ct;
	sort(s+1,s+ct+1,cmp);
	int fg=125000;
	for(int i=1;i<=fg;i++)dp[i]=1e9+2;
	as=solve(v,ct);
	for(int i=ct;i>=1;i--)
	{
		int mx=d;
		if(mx>50)mx=50;
		for(int t=16;t;t>>=1)
		{
			while(mx>=2*t||(mx&&t==1))
			{
				mx-=t;
				int st=t*sz[s[i]],st2=1ll*t*su[s[i]]>1e9?1e9+1:t*su[s[i]];
				if(st>fg||st2>v)continue;
				for(int j=fg-st;j>=0;j--)if(dp[j+st]>dp[j]+st2)dp[j+st]=dp[j]+st2;
			}
		}
	}
	d-=50;
	if(d<0)d=0;
	for(int i=0;i<=fg&&v>=dp[i];i++)as=max(as,i+solve(v-dp[i],ct));
	printf("%d\n",as);
}

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

int main() {
	int n; cin >> n;
	string s; cin >> s;
	bool p1[10] = { 0 };
	bool p2[10][10] = { 0 };
	bool p3[10][10][10] = { 0 };
	REP(i, n) {
		REP(j, 10) {
			REP(k, 10) {
				if (p2[j][k] == 1)
					p3[j][k][s[i] - '0'] = 1;
			}
			if (p1[j] == 1)
				p2[j][s[i] - '0'] = 1;
		}
		p1[s[i] - '0'] = 1;
	}
	int ans = 0;
	REP(i, 10) REP(j, 10) REP(k, 10) if (p3[i][j][k] == 1)ans++;
	cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
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;
}
const int INF=1e18;
const int MOD=1e9+7;
const int MAX=2000010;
int fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

int COM(int n,int k){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int powMOD(int n,int r){
    if(r==0)return 1;
    if(r%2==0)return powMOD(n,r/2)*powMOD(n,r/2)%MOD;
    if(r%2==1)return powMOD(n,r-1)*n%MOD;
}

signed main(){
  	COMinit();
    int a,b,c,d;cin>>a>>b>>c>>d;
    int ans=0;
    for(int i=a+1;i<=c+1;i++){
        ans+=COM(i+d,d)-COM(i+b-1,b-1);
        ans%=MOD;
    }
    if(ans<0)ans+=MOD;
    cout<<ans<<endl;
}


Measured memory_bytes: 47104
#include<iostream>
#include<algorithm>

using namespace std;

int main(void){

int n,x,a[10];

while(cin >> n,n){
fill(a,a+10,0);

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

for(int i=0;i<10;i++){
if(a[i]==0)cout <<"-"<<endl;
else {
for(int j=0;j<a[i];j++)cout <<"*";
cout << endl;
}
}
}

return 0;
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];
	bool ok[2] = {};
	for (int i = 0; i < 2; i++)
	{
		long long m = 0;
		for (int cnt = 0; cnt < n - 1; cnt++)
			if (cnt * 10 <= m)
				m = max(m, cnt * 10 + vec[cnt]);
		if (10 * (n - 1) <= m)
			ok[i] = true;
		if (i == 0)
			reverse(begin(vec), end(vec));
	}
	if (ok[0] && ok[1])
		cout << "yes" << endl;
	else
		cout << "no" << endl;

	return 0;
}



Measured memory_bytes: 5196
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
#include<fstream>
#include <set>
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
const int  MAXN =5e5+10;
const int mod = 1e9 + 7;
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf= 0x3f3f3f3f;
#define eps 1e-8
#define PI 3.1415926535898
#define lowbit(x) (x&(-x))
using namespace std ;
//getline(cin,s);
//set<ll>::iterator it;
//map<int,int>::iterator it;
typedef long long ll;
struct node{
	int l,r,id;
	bool operator < (const node &o)const
	{
		return r<o.r;
	}
}b[MAXN];
int n,q,a[MAXN],last[MAXN],ans[MAXN],need[MAXN];
void add(int x,int val)
{
	while(x<=n)
	{
		need[x]+=val;
		x+=lowbit(x);
	}
}
int get(int x)
{
	int sum=0;
	while(x)
	{
		sum+=need[x];
		x-=lowbit(x);
	}
	return sum;
}
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++)
	{
		scanf("%d %d",&b[i].l,&b[i].r);
		b[i].id=i;
	}
	sort(b+1,b+1+q);
	int r=1;
	for(int i=1;i<=q;i++)
	{
		int rr=b[i].r;
		while(r<=rr)
		{
			if(last[a[r]])	add(last[a[r]],-1);
			add(r,1);
			last[a[r]]=r;
			r++;
		}
		ans[b[i].id]=get(rr)-get(b[i].l-1);
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 17428
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;

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

int w,h;
int p[11][11];
int cnt[11][11];
int res;

struct square{
	int x,y,si;
	square(){}
	square(int xx,int yy,int ss){
		x=xx;
		y=yy;
		si=ss;
	}
	bool operator<(const square &s)const{
		return si<s.si;
	}
};

vector<square> sq; 
vector<square> usq;

bool check(int s,int y,int x){
	for(int i=y;i<y+s;i++){
		for(int j=x;j<x+s;j++){
			if(i>=h || j>=w)return false;
			if(p[i][j]==0)return false;
		}
	}
	return true;
}

bool cover(square a,square b){
	bool flag=false;
	bool flag2=false;
	if(a.x<=b.x && b.x+b.si<=a.x+a.si)flag=true;
	if(a.y<=b.y && b.y+b.si<=a.y+a.si)flag2=true;
	return (flag && flag2);
}

int hstar(int v){
	int n=0;
	int val[101];
	int c=0;
	for(;v<usq.size();v++){
		val[c]=0;
		for(int i=usq[v].x;i<usq[v].x+usq[v].si;i++){
			for(int j=usq[v].y;j<usq[v].y+usq[v].si;j++){
				if(p[j][i]==1)val[c]++;
			}
		}
		c++;
	}
	int rest=0;
	sort(val,val+c,greater<int>());
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			rest+=p[i][j];
		}
	}
	int l=0;
	for(l=0;rest>0;l++){
		rest-=val[l];
	}
	return l;
}

bool empty(){
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(p[i][j]==1)return false;
		}
	}
	return true;
}

void update(int v,int c){
	for(int i=usq[v].x;i<usq[v].x+usq[v].si;i++){
		for(int j=usq[v].y;j<usq[v].y+usq[v].si;j++){
			cnt[j][i]+=c;
		}
	}
}

void dfs(int v,int sum){
	if(empty()){
		res=min(sum,res);
		return;
	}
	if(v==(int)usq.size())return;
	if(sum+hstar(v)>=res)return;
	bool ok1=false,ok2=false;
	for(int i=usq[v].x;i<usq[v].x+usq[v].si;i++){
		for(int j=usq[v].y;j<usq[v].y+usq[v].si;j++){
			if(p[j][i]==1){
				ok1=true;
				if(cnt[j][i]==1)ok2=true;
			}
		}
	}
	update(v,-1);
	if(ok1){
		int tmp[11][11];
		memcpy(tmp,p,sizeof(p));
		for(int i=usq[v].x;i<usq[v].x+usq[v].si;i++){
			for(int j=usq[v].y;j<usq[v].y+usq[v].si;j++){
				p[j][i]=0;
			}
		}
		dfs(v+1,sum+1);
		memcpy(p,tmp,sizeof(p));
	}
	if(!ok2){
		dfs(v+1,sum);
	}
	update(v,1);
}

int main(void){
	while(1){
		scanf("%d%d",&w,&h);
		if(w==0 && h==0)break;
		sq.clear();
		usq.clear();
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				scanf("%d",&p[i][j]);
			}
		}
		for(int i=1;i<=min(w,h);i++){
			for(int j=0;j<h;j++){
				for(int k=0;k<w;k++){
					if(check(i,j,k)){
						sq.push_back(square(k,j,i));
					}
				}
			}
		}
		sort(sq.begin(),sq.end());
		for(int i=(int)sq.size()-1;i>=0;i--){
			bool flag=true;
			for(int j=0;j<usq.size();j++){
				if(cover(usq[j],sq[i]))flag=false;
			}
			if(flag)usq.push_back(sq[i]);
		}
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<usq.size();i++){
			update(i,1);
		}
		res=usq.size();
		sort(usq.begin(),usq.end());
		dfs(0,0);
		printf("%d\n",res);
	}
	return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> rain(N);
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        sum += A[i];
    }
    rain[0] = sum;
    for (int i = 1; i < N; i += 2)
    {
        rain[0] -= 2 * A[i];
    }

    for (int i = 1; i < N; i++)
    {
        rain[i] = 2 * A[i - 1] - rain[i - 1];
    }

    for (int i = 0; i < N - 1; i++)
    {
        cout << rain[i] << " ";
    }
    cout << rain[N - 1] << endl;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i > n; --i)
typedef long long ll;
#define mod 1000000007

int main() {
  int N, K;
  cin >> N >> K;
  string S; cin >> S;
  rep(i, 0, N) {
    if(i + 1 == K) cout << char(S[i] + 32);
    else cout << S[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,s=0,c=0;
    cin >> n>> m;
    int a[n+2];
    for(int i=0; i<n; i++)
    { cin >> a[i];
        s=s+a[i];
    }
 
    
   

    for(int i=0; i<n; i++) 
        if(a[i]*4*m >= s) 
            c++;
 
    if(c>=m) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
int main(void) {
    double r;
    cin >> r;
    double a = M_PI * r * r;
    double c = 2 * M_PI * r;
    cout << fixed;
    cout << setprecision(6);
    cout << a << ' ' << c << endl;
    return 0;
}



Measured memory_bytes: 3268
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#include <vector>

#define Flash ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define F first
#define S second
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define sz size()
#define mp make_pair
#define y1 asdf
#define rc(x) return cout << x, 0

const long long MXN = 2e3 + 1;
const long long MNN = 1e5 + 1;
const long long MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const long long OO = 1e9 + 500;

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

string s;
int cnt, sum;

void input(){

    cin >> s;

}

int main() {
    input();
    reverse(all(s));
    if(s.sz == 1) rc(s[0]);
    for(int i = 0; i < s.sz - 1; i ++){
        cnt += 9;
        if(s[i] == '9') sum ++;
    }
    int t = s[s.sz - 1] - '0';
    if(sum == s.sz - 1) t ++;
    cout << cnt + t - 1;
    EX;
}


Measured memory_bytes: 256
//#pragma GCC optimize ('O3')
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 100 + 5;
const int M = 1e7 + 5;
const ll OO = 2e18;
const int mod = 998244353;

int n,m,r[N],c[N];
char a[N][N];

int main() {

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

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if(a[i][j]=='#') {
                ++r[i], ++c[j];
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        bool ok = 0;
        for (int j = 0; j < m; ++j) {
            if(r[i] && c[j]) {
                ok = 1;
                cout << a[i][j];
            }
        }
        if(ok) cout << '\n';
    }

    return 0;

}

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

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

using namespace std;

const int INF = 1 << 30;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 44;

int memo[N+1];

int fib(int n) {
	if (memo[n] != 0) return memo[n];
	else return memo[n] = fib(n-1) + fib(n-2);
}

int main() {
	int n; cin >> n;
	rep(i, n+1) memo[i] = 0;
	memo[0] = memo[1] = 1;
	cout << fib(n) << endl;
}



Measured memory_bytes: 3108
#include <cstdio>
#include <cstring>

using namespace std;

char T[200005];

int main() {
    scanf("%s", T);
    for (int i = 0; i < strlen(T); i++) {
        if (T[i] == '?') T[i] = 'D';
    }
    printf("%s\n", T);
    return 0;
}


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

#define MAX_N 100
#define MAX_W 10000

int main() {
    int N, W;
    cin >> N >> W;
    int w[MAX_N+1], v[MAX_N+1];
    for (int i = 0; i < N; i++) {
        cin >> v[i] >> w[i];
    }
    int dp[MAX_N+1][MAX_W+1];
    fill((int*)dp, (int*)(dp+MAX_N+1), 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            if (w[i] <= j) {
                dp[i+1][j] = max(max(dp[i][j-w[i]] + v[i], dp[i][j]), dp[i+1][j-w[i]] + v[i]);
            } else {
                dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
            }
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}



Measured memory_bytes: 7044
#include <bits/stdc++.h>
#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)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;

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;
}

map<int64_t, int> prime_factor(int64_t n)
{
  map<int64_t, int> ret;
  for (int64_t i = 2; i * i <= n; i++)
  {
    while (n % i == 0)
    {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1)
    ret[n] = 1;
  return ret;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};

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

  ll count[1000];
  rep(i, 1000){
    count[i] = 0;
  }
  
  repi(i, 1, n + 1)
  {
    for (auto p : prime_factor(i))
    {
      while (p.second--)
      {
        count[p.first]++;
      }
    }
  }

  mint ans = {1};
  repi(i, 2, n + 1)
  {
    if (count[i] != 0)
      ans *= (count[i] + 1);
  }

  cout << ans.x << 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;
typedef pair<ll, ll> P;

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

ll N;
vector<ll> F(44, 0);

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

void fibo(ll n) {
  if (n == 0) F[0] = 1;
  else if (n == 1) F[1] = 1;
  else F[n] = F[n-1] + F[n-2];
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  rep(i, N) {
    fibo(i);
  }
  if(N < 2) cout << 1 << endl;
  else cout << F[N-1]+F[N-2] << endl;
  return 0;
}



Measured memory_bytes: 3204
#!/usr/bin/env python
# coding: utf-8
#


def main(n, input_list):
    slime_list = []
    l = list(map(int, input_list.split(' ')))
    # 何色続いているかでカウントする
    slime_list.append([l[0], 1])
    for i in range(1, len(l)):
        if l[i] == slime_list[-1][0]:
            slime_list[-1][1] += 1
        else:
            slime_list.append([l[i], 1])
    retval = 0
    for i in range(len(slime_list)):
        if 1 == slime_list[i][1] % 2:
            retval += (slime_list[i][1] - 1) / 2
        elif 0 == slime_list[i][1] % 2:
            retval += slime_list[i][1] / 2

    print(int(retval))

if __name__ == '__main__':
    try:
        n = int(input().strip())
        input_list = input().strip()
        main(n, input_list)
    except EOFError:
        pass


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		long ans = (long) (k * Math.pow(k-1, n-1));
		System.out.println(ans);
	}
}

Measured memory_bytes: 35840
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
int main() {
	int n;
	cin >> n;
	dsu d(n);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int b, l, r;
		cin >> b >> l >> r;
		if (b == 0) {
			d.merge(l, r);
	    }
		else {
			if (d.same(l, r)) {
				cout << "1" << endl;
			}
			else {
				cout << "0" << endl;
			}
		}
	}
}


Measured memory_bytes: 4000
ar = list(map(int,input().split(" ")))
ar.sort()
count = 0
count += (ar[2] - ar[0]) // 2
count += (ar[2] - ar[1]) // 2
if (ar[2] - ar[0]) % 2 == 0 and (ar[2] - ar[1]) % 2 == 0:
    print(count)
elif (ar[2] - ar[0]) % 2 == 0 or (ar[2] - ar[1]) % 2 == 0:
    print(count + 2)
else:
    print(count + 1)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <numeric>
using namespace std;
#define lint long long
#define ll long long
#define pq priority_queue
long long INF = 1e10;
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
/****************temporary declaration & definitoins*******************/

/**************************define functions****************************/

/****************************main function*****************************/
int main(void) {
	string S; cin >> S;
	ll N = S.size();
	vector<ll> B;
	for (int i = S.size() - 1; i >= 0; i--) {
		if (S[i] == 'B') B.push_back(i);
	}
	ll ans = 0;
	for (int i = 0; i < B.size(); i++) {
		ans += (N-1 - i) - B[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2680
N, W = map(int, input().split())

INF = 9999999999
MAXN = 110
MAXV = 100010
weights = [0]*(MAXN)
values = [0]*(MAXN)

dp = [[INF]*(MAXV) for i in range(MAXN)]
dp[0][0] = 0

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_v in range(MAXV):
        if sum_v >= values[i]:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-values[i]]+weights[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],
                             dp[i][sum_v])
ans = 0
for sum_v in range(MAXV):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Measured memory_bytes: 121624
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <assert.h>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
  ll n,k;
  cin>>n>>k;
  ll a = n%k;
  cout << min(a,abs(a-k)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int x;
    int i;
    int min = 10000;
    int max = 1;
    int sum = 0;
    for(i=0;i<3;i++){
        scanf("%d",&x);
        sum += x;
        if(x<min) min = x;
        if(x>max) max = x;
    }
    printf("%d %d %d\n",min,sum-(min+max),max);
    
}



Measured memory_bytes: 2080
#include <bits/stdc++.h>
#define ll long long int
#define ld double
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
int main()
{
	boost;
	int n, i;
	string s;
	cin >> s;
	n = s.length();
	int ans1 = 0;
	int ans2 = 0;
	fo(i, 0, n){
		if(i % 2 == 0)
		ans1 += (s[i] == '0');
		else
		ans1 += (s[i] == '1');	
	}
	fo(i, 0, n){
		if(i % 2 == 0)	
		ans2 += (s[i] == '1');
		else
		ans2 += (s[i] == '0');
	}
	cout << min(ans1, ans2);
}


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

using namespace std;

#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 All(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int n,k;
   cin >> n >> k;
   vector<int> x(n);
   rep(i,n)cin >> x[i];
   int ans = 0;
   rep(i,n){
      if(x[i] * 2 < abs(k-x[i]) * 2){
         ans += x[i]*2;
      }else{
         ans += abs(k-x[i])*2;
      }
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
vector<int> v[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m;
	cin >> n >> m;
	while (m--)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (auto& x : v[1])
	{
		if (x == n) puts("POSSIBLE"), exit(0);
		for (auto& y : v[x])
		{
			if (y == n) puts("POSSIBLE"), exit(0);
		}
	}
	puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 12016
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

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

      int a,b,c;
      cin >> a >> b >> c;
      int x = gcd(a,b);
      if(c%x==0)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    
  return 0;
}


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

typedef struct node{
  int *children;
  int n_children;
  int depth;
  int parent;
}Node;

void depth_plus(Node *a, int x, int d) {
  int i;
  (a+x)->depth += d;
  for (i = 0; i < (a+x)->n_children; i++) {
    depth_plus(a,((a+x)->children)[i], d);
  }
}

int main()
{
  int i,j,n,id,n_children,child;
  Node *a;
  scanf("%d",&n);
  a = (Node*)malloc(sizeof(Node) * n);
  for (i = 0; i < n; i++) {
    (a+i)->children = NULL;
    (a+i)->depth = 0;
    (a+i)->parent = -1;
  }

  for (i = 0; i < n; i++) {
    scanf("%d %d",&id,&n_children);
    (a+id)->n_children = n_children;
    if(n_children != 0)
      (a+id)->children = (int*)malloc(sizeof(int) * n_children);
    for(j = 0; j < n_children; j++) {
      scanf("%d",&child);
      ((a+id)->children)[j] = child;
      depth_plus(a,child,(a+id)->depth+1);
      (a+child)->parent = id;
    }
  }

  for (i = 0; i < n; i++) {
    printf("node %d: parent = %d, depth = %d, ",i,(a+i)->parent,(a+i)->depth);
    if((a+i)->parent == -1) {
      printf("root, [");
    }else if((a+i)->n_children > 0){
      printf("internal node, [");
    }else{
      printf("leaf, [");
    }
    for (j = 0; j < (a+i)->n_children; j++) {
      printf("%d", ((a+i)->children)[j]);
      if(j != (a+i)->n_children-1) printf(", ");
    }
    printf("]\n");
  }


  
  return 0;
}

Measured memory_bytes: 3424
from collections import defaultdict
from heapq import heappop, heappush, heapify


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    n, m, s, t = map(int, input().split())
    trains = [list(map(int, input().split())) for i in range(m)]

    g_yen = Graph()
    g_snuuk = Graph()

    for train in trains:
        u, v, a, b = train
        g_yen.add_edge(u, v, a)
        g_yen.add_edge(v, u, a)
        g_snuuk.add_edge(u, v, b)
        g_snuuk.add_edge(v, u, b)

    d_yen = Dijkstra(g_yen, s)
    d_snuuk = Dijkstra(g_snuuk, t)

    cost_sum = []
    for i in range(1, n+1):
        cost_sum.append([d_yen.dist[i] + d_snuuk.dist[i], i])

    heapify(cost_sum)
    c, l = heappop(cost_sum)
    for i in range(n):
        while l<=i:
            c, l = heappop(cost_sum)
        print(10**15 - c)


if __name__ == '__main__':
     main()
    






Measured memory_bytes: 145404
# coding: utf-8
a = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
b = list([int(input()) for _ in range(n)])
ans = "No"

# ana check
for bi in b:
    for i in range(3):
        for j in range(3):
            if a[i][j] == bi:
                a[i][j] = "hole"

# tate bingo
for j in range(3):
    if a[0][j] == "hole":
        if a[1][j] == "hole" and a[2][j] == "hole":
            ans = "Yes"

# yoko bingo
for i in range(3):
    if a[i][0] == "hole":
        if a[i][1] == "hole" and a[i][2] == "hole":
            ans = "Yes"

# naname bingo
if a[0][0] == "hole" and a[1][1] == "hole" and a[2][2] == "hole":
    ans = "Yes"
if a[0][2] == "hole" and a[1][1] == "hole" and a[2][0] == "hole":
    ans = "Yes"

print(ans)


Measured memory_bytes: 3064
#include"bits/stdc++.h"

#define rep(i, N) for(int i = 0;i < N;i++)

typedef long long ll;

const int mod = 1e9 + 7;

using namespace std;



int main(void) {
	int x;
	int ans = 0;
	rep(i, 5) {
		cin >> x;
		if (x == 0) {
			ans = i + 1;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3632
N = gets.to_i
H = N.times.map{ gets.split.map(&:to_i) }

result = H.inject do |estimate, headline| 
  m = 2.times.map{|i| (estimate[i] + headline[i] - 1) / headline[i] }.max
  2.times.map{|i| headline[i] * m }
end
puts result.inject(&:+)


Measured memory_bytes: 2172
#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); ++i)
#define pb push_back
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
#define reverse(v) reverse(v.begin(),v.end())
typedef long long ll;
typedef long double la;
using namespace std;

const int INF = 100000000;

int main(){
	while(true){
		int n;
		cin >> n;
		if(n == 0){
			break;
		}
		
		int T[10][10];

		rep(i,10){
			rep(j,10){
				if(i == j){
					T[i][j] = 0;
				}else{
					T[i][j] = INF;
				}
			}
		}

		int m = 0;

		rep(i,n){
			int a,b,c;
			cin >> a >> b >> c;
			T[a][b] = T[b][a] = c;

			if(a + 1 > m){
				m = a + 1;
			}
			if(b + 1 > m){
				m = b + 1;
			}
		}
		
		rep(k,m){
			rep(i,m){
				rep(j,m){
					if(T[i][j] > T[i][k] + T[k][j]){
						T[i][j] = T[i][k] + T[k][j];
					}
				}
			}
		}

		int city = 0;
		int mn = INF;

		rep(i,m){
			int sum = 0;
			rep(j,m){
				sum += T[i][j];
			}
			if(mn > sum){
				mn = sum;
				city = i;
			}
		}

		cout << city << " " << mn << endl;
	}

	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
 

  // input
  string s1,s2,s3;
  cin>>s1>>s2>>s3;

  char cwk1=s1.at(0);
  char cwk2=s2.at(0);
  char cwk3=s3.at(0);

  cout<<(char)toupper(cwk1)<<(char)toupper(cwk2)<<(char)toupper(cwk3)<<endl;

	return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#include <math.h>
#include <float.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
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; }

const int MOD = 1000000007;

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(){
    ll N, P; cin >> N >> P;

    auto pf = prime_factorize(P);

    ll ans = 1;
    for(auto p : pf){
        for(ll i = 0; i < p.second / N; i++) ans *= p.first;
    }

    cout << ans << endl;

}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define FAST ios_base::sync_with_stdio(false);cin.tie(0);
    const double EPS = 1e-9;
    const double PI = acos(-1);
    const int knightDir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2}};
    //const int dx[]={0,0,0,1,1,1,-1,-1,-1};
    //const int dy[]={-1,0,1,-1,0,1,-1,0,1};
    const int dx[] = {0 , 1 , 0 , -1};
    const int dy[] = {1 , 0 , -1 , 0};
    //#define MOD         1000000007LL
    #define MAX         1000005
    const ll MOD = 1000000000 + 7;
    
    int main()
    {
        FAST
        int t;
        t = 1;

        while(t--)
        {
           double d , t , s;
           cin >> d >> t >> s;
           
           if(d / s <= t)cout <<"Yes\n";
           else cout <<"No\n";
        }
    }



Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define itn int
#define asn ans
bool dbg = false;

int N, x, a[2020];

void solve() {
    vi now(N), nxt(N);
    for (int i = 0; i < N; i++) {
        now[i] = a[i];
    }
    int ans = INF;
    for (int r = 0; r < N; r++) {
        int scr = r * x;
        for (int i = 0; i < N; i++) {
            scr += now[i];
        }
        chmin(ans, scr);
        for (int i = 0; i < N; i++) {
            nxt[i] = min(now[i], now[(i + 1) % N]);
        }
        swap(nxt, now);
    }
    cout << ans << endl;
}

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

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

    solve();
    return 0;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

map<int,int>A;
int main()
{
	int N,mx=-1,res=0;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		int a;
		scanf("%d",&a);
		mx=max(mx,a);
		A[a]++;
	}
	for(int i=0;i<=mx;i++)
	{
		res=max(A[i]+A[i+1]+A[i+2],res);
	}
	cout<<res<<endl;
}


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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

ll fact(ll n) 
{
    ll ret = 1;
    while(n > 0)
    {
        ret *= n;
        ret %= MOD;
        n--;
    }
    return ret;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    ll N, M; cin >> N >> M;
    ll ans;
    if(N == M)
    {
        ans = 2 * fact(N) % MOD * fact(M) % MOD;
    }
    else if(abs(N-M) == 1)
    {
        ans = fact(N) % MOD * fact(M) % MOD;
    }
    else
    {
        ans = 0;
    }
    cout << ans << endl; 
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main() {
  string S;
  string T;
  int ans=0;
  T.length()==3;
  S.length()==3;
  cin>>S>>T;
  for(int i=0 ; i<3 ; i++) {
    if(T[i]==S[i]) ans++;
  }
  cout<<ans;
}


Measured memory_bytes: 256
//
//  main.cpp
//  ALDS1_6_B
//
//  Created by ptyuan on 2018/10/29.
//  Copyright © 2018 YY. All rights reserved.
//

#include <iostream>
#include <cstdio>

int partition(int *A, int p, int r) {
    int x = A[r];
    int i = p - 1;
    for (int j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i++;
            int temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }
    A[r] = A[i + 1];
    A[i + 1] = x;
    return i + 1;
}

int main(int argc, const char * argv[]) {
    int n = 0;
    int A[100000];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", A + i);
    }
 
    int p = partition(A, 0, n - 1);
    for (int i = 0; i < n; i++) {
        int indexValue = A[i];
        if (i > 0) {
            printf(" ");
        }
        if (i == p) {
            printf("[%d]", indexValue);
        } else {
            printf("%d", indexValue);
        }
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 3612
n=int(input())
a=list(map(int,input().split()))
num=[0]*100005
ans=sum(a)

for _ in a:
  num[_-1]+=1

q=int(input())

for i in range(q):
  b,c=map(int,input().split())
  
  if b<=c:
    ans+=(abs(c-b))*num[b-1]
    
  else:
    ans-=(abs(c-b))*num[b-1]
    
  print(ans)
  
  num[c-1]+=num[b-1]
  num[b-1]=0

Measured memory_bytes: 20896
n = int(input())
list_a = list(map(int, input().split()))
state = 0
count = 1
for i in range(n-1):
    if state == 0:
        if list_a[i] == list_a[i+1]:
            continue
        elif list_a[i] < list_a[i+1]:
            state = "plus"
        else:
            state = "minus"
    if state == "plus":
        if list_a[i] > list_a[i+1]:
            count += 1
            state = 0
        else:
            continue
    if state == "minus":
        if list_a[i] < list_a[i+1]:
            count += 1
            state = 0

print(count)


Measured memory_bytes: 14224
#include <stdio.h>
#define ll long long

ll max(ll a, ll b){
	if(a>b)return a;
	else return b;
}

int main(void){
	int N,W;
	int i,j;
	int item[100][2];

	scanf("%d %d",&N, &W);
	for(i=0; i<N; i++) { scanf("%d %d",&item[i][0],&item[i][1]); }


	ll dp[101][W+1];
	for(i=0; i<=W; i++)for(j=0; j<N+1; j++)dp[j][i]=0;

	for(i=1; i<=N; i++){
		for(j=0; j<=W; j++){
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
			if(j-item[i-1][0]>=0) dp[i][j]=max(dp[i][j], dp[i-1][j-item[i-1][0] ]+item[i-1][1]);
		}
	}

	ll ans=0;
	for(i=0; i<=W; i++){ans=max(ans, dp[N][i]); }
	printf("%lld\n",ans );
}




Measured memory_bytes: 79104
from sys  import stdin,stdout

import bisect

import math

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)
                
def gcd(a,b):
    while b:
        a=a%b
        b,a=a,b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r
    
def solve():
    s=input()
    m=0
    y=0
    if (int(s[-1])>=1 and int(s[-2])==0) or (int(s[-2])==1 and int(s[-1])<=2):
        m=1
    if (int(s[0])==0 and int(s[1])>=1) or (int(s[0])==1 and  int(s[1])<=2):
        y=1
    if m and y:
        print("AMBIGUOUS")
    elif m and not y:
        print("YYMM")
    elif y and not m:
        print("MMYY")
    else:
        print("NA")
        
    



for _ in range(1):
    solve()
    


Measured memory_bytes: 9220
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

bool cmp(pair<int, long long int> a, pair<int, long long int> b) {
    if(a.second!=b.second) {
        return a.second>b.second;
    } else {
        return a.first>b.first;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<long long int> A(N);
    vector<long long int> S(N+1, 0);
    for(int n=0; n<N; n++) {
        cin >> A[n];
    }
    sort(A.begin(), A.end());
    
    for(int n=0; n<N; n++) {
        S[n+1] = A[n]+S[n];
    }
    
    
    vector<pair<int, long long int> > BC(M);
    for(int m=0; m<M; m++) {
        cin >> BC[m].first >> BC[m].second;
    }
    
    sort(BC.begin(), BC.end(), cmp);
    
    // //debugging
    // for(int m=0; m<M; m++) {
    //     cout << BC[m].second << endl;
    // }
    
    long long int sum=0;
    int count=0;
    int m=0;
    int count_sum=0;
    while(m<M) {
        count = lower_bound(A.begin()+count_sum, A.end(), BC[m].second)-A.begin()-count_sum;
        count = min(count, BC[m].first);
        if(count_sum+count>N) break;
        count_sum += count;
        
        if(count<=0) break;
        // cout << "sum = " << sum << " -> " ;
        sum += BC[m].second * count;
        // cout << sum << endl;
        
        m++;
    }

    // cout << sum << endl;
    sum += S[N] - S[count_sum];
    // cout << S[N] - S[count_sum] << endl;

    cout << sum << endl;
    
    return 0;
    
}

Measured memory_bytes: 3328
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int x=input.nextInt();
        int a=input.nextInt();
        int b=input.nextInt();
        if(b<x){
            System.out.print("delicious");
        }
        else{
            if((b-a)<=x){
                System.out.print("safe");
            }
            else{
                System.out.print("dangerous");
            }
        }
    }
}


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

int main()
{
    int X,Y;
    int leg;
    char* out = "No";

    cin >> X >> Y;

    for (int i=0; i<=X; i++){
        leg = 2*i + 4*(X-i);
        if (leg == Y) {
            out = "Yes";
            break;
        }
    }

    cout << out;

    return 0;
}


Measured memory_bytes: 3640