akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif
#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;
const int MO=1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<endl;}
inline int powerexp(int a,int b,int m){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
void solve(){
	string s;
	cin>>s;
	bool ok=((s[0]==s[1] and s[1]==s[2]) or (s[1]==s[2] and s[2]==s[3]));
	cout<<(ok?"Yes":"No")<<endl;
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
    IOS;
    solve();
    #ifdef LOCAL_DEFINE
    cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
    #endif
}

Measured memory_bytes: 256
#include<iostream>
 
using namespace std;
 
int main()
{
	int i,j,len,flag=1;
	char a[100];
	
	
	cin>>a;
	int count = 0;
	for(len=0;a[len]!='\0';++len);
	
	for(i=0,j=len-1;i<len/2;++i,--j)
	{
		if(a[j]!=a[i])
			count += 1;
	}
	
cout << count;
 
	return 0;
}

Measured memory_bytes: 256
//#include <fsociety>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
//end of libraries ;
#define INF 999999
#define N 3000003
#define F first
#define S second
#define pb push_back
#define ll long long
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
string s , sF , sE ;
bool check(string s1){
	for(int i = 0 ; i < s1.length() ; i++){
		if(s1[i]!=s1[s1.length()-i-1]) return false;
	}
	return true;
}
int main(){
fcin;
	cin>>s;
	for(int i = 0 ; i <=(s.length()-1)/2-1 ; i++){
		sF += s[i];
	}
	for(int i = (s.length() +3)/2 - 1 ; i < s.length() ; i++){
		sE += s[i];
	}
	// cout<<sF<<" "<<sE<<endl;
	// cout<<check(sF)<<endl;
	if(check(s) && check(sF) && check(sE)){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long i[11111111];
long long u[11111111];
long long o[11111111];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a,b,c,d=0,e=1,f=0;
  cin >>a>>i[0];
  for(int n=1;n<a;n++) cin >>i[n];
  sort(i,i+a);
  u[0]=i[0];
  for(int n=1;n<a;n++){
    u[n]=u[n-1]+i[n];
  }
  for(int n=a-1;n>=0;n--){
    if(2*u[n-1]<i[n]){
      d=n;
      break;
    }
  }
  cout <<a-d<<'\n';
  return (0);
}


Measured memory_bytes: 6400
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
#print(s)
a=1
for i in range(m):
    if i==0:
        s[0][1][1]=1
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
        s[i][1][1]=a
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
        s[i][1][1]=a
#print(s)
s=sorted(s,key=lambda x:x[0])
#print(s)
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])

Measured memory_bytes: 46748
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>>vvi;
const ll MOD=1000000007LL;
int main(){
  ll m;
  cin>>m;
  vector<ll> d(m),c(m);
  rep(i,m)cin>>d[i]>>c[i];
  ll num=0;
  ll sum=0;
  rep(i,m){
    num+=c[i];
    sum+=d[i]*c[i];
  }
  if(sum%9==0)num--;
  cout<<num-1+sum/9<<endl;
}
    

Measured memory_bytes: 3328
#pragma GCC optimize(2) //O2ÓÅ»¯£¿

#include<bits/stdc++.h>
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define BINF 0x7fffffff
#define INF 0x3f3f3f3f
#define LINF 9223372036854775807
#define END(s) {cout<<s;return 0;}
#define CON(s) {cout<<s;continue;}
#define BRE(s) {cout<<s;break;}
#define pb push_back
#define All(a) a.begin(),a.end()  //with A in CAPITAL!!!
#define sz(a) (int)a.size()
#define F first
#define S second
#define LOCAL_JUDGE 1 //remember to change
using namespace std;

map<long long,int> m;

int main(){
	ios::sync_with_stdio(false);
	long long sum=0,res=0;
	int n;
	cin>>n;
	m[0]=1;
	rep(i,n){
		int x;
		cin>>x;
		sum+=x;
		res+=m[sum];
		m[sum]++;
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define vi vector<int>
const ll INF=1e9+5;
void min_self(ll &a,ll b)
{
    a=min(a,b);
    return;
}
int main()
{
    string s,t;
    cin>>s>>t;
    int n=s.length(),m=t.length();
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0) dp[i][j]=0;
            else if(s[i-1]==t[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int len=dp[n][m];
    char lcs[len];
    int idx=len;
    int i=n,j=m;
    while(i>0&&j>0)
    {
        if(s[i-1]==t[j-1])
        {
            lcs[idx-1]=s[i-1];
            i--;j--;idx--;
        }
        else if(dp[i-1][j]>dp[i][j-1])
        {
            i--;
        }
        else j--;
    }
    for(int i=0;i<len;i++)
    {
        cout<<lcs[i];
    }
    cout<<endl;
    return 0;
}





Measured memory_bytes: 35584
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
    if(*(int *)a>*(int* )b )return 1;
    return -1;
}
int main()
{   int n;
    scanf("%d",&n);
    int a[n],b[n];
    long long asum=0,bsum=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        asum+=a[i];
    }
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        bsum+=b[i];
    }
    long long stocka=0,stockb=0;
    for(int i=0;i<n;i++){
        if(a[i]==b[i])continue;
        if(a[i]>b[i]){
            stocka+=(a[i]-b[i]);
            //printf("@%d stocka %d\n",i,stocka);
        }else{
            stockb+=((b[i]-a[i]+1)/2);
            //printf("@%d stockb %d\n",i,stockb);
        }
    }
    //printf("stocka=%lld,stockb=%lld\n",stocka,stockb);
    if(bsum-asum>=stockb){
        printf("Yes");
        return 0;
    }else{
        printf("No");
        return 0;
    }
    

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>          // printf(), scanf()
#define MAX_N 100000

typedef struct node_tbl
{
	int parent;
	int left;
	int right;
} node;

const int nil = -1;
node t[MAX_N];
int d[MAX_N];

void
print(int u)
{
	int c;
	int i;

	printf("node %d: ", u);
	printf("parent = %d, ", t[u].parent);
	printf("depth = %d, ", d[u]);
	if (t[u].parent == nil)
		printf("root, [");

	else if (t[u].left == nil)
		printf("leaf, [");

	else
		printf("internal node, [");

	const char* sep = "";
	for (i = 0, c = t[u].left; c != nil; i++, c = t[c].right)
	{
		printf("%s%d", sep, c);
		sep = ", ";
	}

	printf("]\n");
}

void
rec(int u, int p)
{
	d[u] = p;
	if (t[u].right != nil)
		rec(t[u].right, p);

	if (t[u].left != nil)
		rec(t[u].left, p + 1);
}

int
main(int argc, char** argv)
{
	int n;
	int v;
	int c;
	int l, r;
	int i, j, k;

	scanf("%d", &n);
	for (i = 0; i < n; ++i)
		t[i].parent = t[i].left = t[i].right = nil;

	for (i = 0; i < n; ++i)
	{
		scanf("%d %d", &v, &k);
		for (j = 0; j < k; ++j)
		{
			scanf("%d", &c);
			if (j == 0)
				t[v].left = c;
			else
				t[l].right = c;

			l = c;
			t[c].parent = v;
		}
	}

	for (i = 0; i < n; ++i)
	{
		if (t[i].parent == nil)
		{
			r = i;
			break;
		}
	}

	rec(r, 0);
	for (i = 0; i < n; ++i)
		print(i);

	return 0;
}

Measured memory_bytes: 5296
#include<bits/stdc++.h>
#define optimize() ios_base ::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n";
using namespace std;


int main()
{
    optimize();
     long long int i,a,b,c,d;
     long long n=-1e18;
     cin>>a>>b>>c>>d;
     n=max({n,a*c,b*d,a*d,b*c});

     cout<<n;
     cout<<endl;

    return 0;
}



Measured memory_bytes: 3600
#include <stdio.h>

int main(void) {
	int i, j;
	int hit_cnt, blow_cnt;
	int a[4], b[4];
	while(scanf("%d %d %d %d\n%d %d %d %d", &a[0], &a[1], &a[2], &a[3], &b[0], &b[1], &b[2], &b[3]) != EOF){
		hit_cnt = 0;
		blow_cnt = 0;
		for(i = 0; i < 4; i++){
			for(j = 0; j < 4; j++){
				if(a[i] == b[j]){
					if(i == j) hit_cnt++;
					else blow_cnt++;
				}
			}
		}
		printf("%d %d\n", hit_cnt, blow_cnt);
	}
	return 0;
}

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

using namespace std;

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

ll n, x[200005], ii, jj, kk = 2, L1, R1, L2, R2, minn = 1e16, ans = 1e16;

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=1;i<n;i++) x[i] += x[i-1];
    for(int i=1;i<n-2;i++){
        minn = 1e16;
        for(int j=jj;j<i;j++){
            if(abs(x[j] - (x[i] - x[j])) < minn){
                minn = abs(x[j] - (x[i] - x[j]));
                jj = j;
            }
            else break;
        }
        minn = 1e16;
        for(int k=kk;k<n-1;k++){
            L2 = x[k] - x[i];
            R2 = x[n-1] - x[k];
            if(abs(R2 - L2) < minn){
                minn = abs(R2 - L2);
                kk = k;
            }
            else break;
        }
        //cout<<ii<<" "<<i<<" "<<kk<<"\n";
        L1 = x[jj];
        R1 = x[i] - x[jj];
        L2 = x[kk] - x[i];
        R2 = x[n-1] - x[kk];
        //cout<<L1<<" "<<R1<<" "<<L2<<" "<<R2<<"\n";
        ans = min(ans, max(max(L1, L2), max(R1, R2)) - min(min(L1, L2), min(R1, R2)));
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 1792
// #define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>;
#define rep0(TMS) for (int CNT = 0; CNT < (int)(TMS); CNT++)
#define rep(CNT, GOAL) for (int CNT = 0; CNT < (int)(GOAL); CNT++)
#define rep2(CNT, START, GOAL) for (int CNT = (int)(START); CNT < (int)(GOAL); CNT++)
#define rep3(CNT, START, GOAL) for (int CNT = (int)(START); CNT > (int)(GOAL); CNT--)
#define all(CONT) begin(CONT), end(CONT)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
void prec(const int &DIG) { cout << fixed << setprecision(DIG); cerr << fixed << setprecision(DIG); }
template <typename T> void CERR(const T &ELEM) { cerr << ELEM; }
#define dbl(OBJ) cerr << #OBJ << ": "; CERR(OBJ); cerr << "\n"
template <typename T, typename ...Ts> void CERR(const T &FIRST, const Ts &...REST) { CERR(FIRST); cerr << ", "; CERR(REST...); }
#define dbs(...) cerr << "(" << #__VA_ARGS__ << "): ("; CERR(__VA_ARGS__); cerr << ")\n"
#define itrep(ITR, CONT) for (auto ITR = begin(CONT); ITR != end(CONT); ITR++)
template <typename T> void CERR(const vector<T> &VEC) { cerr << "{ "; itrep(ITR, VEC) { CERR(*ITR); cerr << ", "; } cerr << "}"; }
#define YN(FLG) cout << (FLG ? "YES" : "NO") << "\n"
#define Yn(FLG) cout << (FLG ? "Yes" : "No") << "\n"
#define yn(FLG) cout << (FLG ? "yes" : "no") << "\n"
// const ll INF = LONG_LONG_MAX;
const int INF = INT_MAX;
// const ll MOD = 1000000007; // 998244353;

// #include <atcoder/all>
// using namespace atcoder;

int solve(int X) {
	return 360 / __gcd(X, 360);
}

int main() {
	// rep2(X, 1, 180) cout << X << ":" << solve(X) << endl;

	int X; cin >> X;
	cout << solve(X) << endl;
}

Measured memory_bytes: 3604
import java.util.Scanner;

class Main  {

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

    int a = sc.nextInt();
    int b = sc.nextInt();

    int max = a+b;
    if((a-b)>max)
    max = a-b;
    if((a*b)>max)
    max = a*b;
    System.out.println(max);

  }

}


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

int main()
{
	std::string input, top, bot;
	std::cin >> input;
	int shuffles, size;
	while (input != "-") {
		std::cin >> shuffles;
		for (int i = 0; i < shuffles; i++) {
			std::cin >> size;
			top = input.substr(0, size);
			bot = input.substr(size);
			input = bot + top;
		}
		std::cout << input << "\n";
		std::cin >> input;
	}
    return 0;
}




Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
using ll=long long;
using P=pair<int,int>;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl '\n'
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
#define INF 1e9
#define DEBUG(x) cout<<"debug: "<<x<<endl
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

ll n, a, b;
int main(){
    cin >> n >> a >> b;
    ll sum = a+b;
    ll count = n/sum;
    ll q = n%sum;
    ll ans = a*count + min(a, q);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

struct State {
  int x, y, d, c;
  State(){}
  State(int x_, int y_, int d_, int c_) : x(x_), y(y_), d(d_), c(c_) {}
  bool operator>(const State& s) const {
    return c>s.c;
  }
};

const int S = 31;
const int INF = 1<<27;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

int H, W;
int G[S][S], C[4];

bool in(int x, int y) {
  return 0<=x && x<W && 0<=y & y<H;
}

int a() {
  int c[4][S][S];
  
  priority_queue<State, vector<State>, greater<State> > q;
  
  fill(c[0][0], c[4][0], INF);
  q.push(State(0,0,0,0));
  c[0][0][0] = 0;

  while(!q.empty()) {
    const State s = q.top(); q.pop();
    if(s.x == W-1 && s.y == H-1) return s.c;
    
    for(int i=0; i<4; i++) {
      State t = s;
      t.d = (s.d + i) % 4;
      t.x += dx[t.d], t.y += dy[t.d];
      t.c += i == G[s.y][s.x] ? 0 : C[i];
      if(in(t.x, t.y) && c[t.d][t.y][t.x] > t.c) {
	q.push(t);
	c[t.d][t.y][t.x] = t.c;
      }
    }
  }
  return -1;
}

int main() {
  while(cin >> W >>H, W+H ) {
    for(int i=0; i<H; i++) for(int j=0; j<W; j++) cin >> G[i][j];
    for(int i=0; i<4; i++) cin >> C[i];
    cout << a() << endl;
  }
  return 0;
}

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

signed main(){
  int n;
  string s;
  cin>>n>>s;
  
  vector<int> black(n+1,0);
  vector<int> white(n+1,0);

  for(int i=0;i<n;i++){
    black[i+1]=black[i]+(s[i]=='#');
    white[i+1]=white[i]+(s[i]=='.');
  }

  int ans=n;
  for(int i=0;i<=n;i++){
    int res=black[i]+(white[n]-white[i]);
    if(ans>res) ans=res;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 2180
using System;
using System.Collections.Generic;
using System.Linq;

class Progaram
{
    static void Main(string[] args)
    {
        var l = Console.ReadLine().Split(' ')
            .Select(x => int.Parse(x)).ToArray();
        var n = l[0]; var k = l[1];
        var nl = Console.ReadLine().Split(' ')
            .Select(x => int.Parse(x)).OrderBy(x => x).ToArray();
        var res = 0;
        for (var i = 0; k > i; i++)
        {
            res += nl[i];
        }
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 28732
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define INF 800000000
#define MAX 1000

int main(){
  string S;
  cin>>S;
  string T="CODEFESTIVAL2016";
  int count=0;
  for(int i=0;i<16;i++){
    if(S.at(i)!=T.at(i)){
      count++;
    }
  }
  cout<<count<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

int main(){
	int n;
	cin >> n;
	priority_queuer<pii> pq;
	rep(i, n){
		int a, b;
		cin >> a >> b;
		pq.emplace(b, a);
	}
	int i=0;
	int ans = 0;
	while(pq.size()){
		pii d = pq.top();
		pq.pop();
		if(i < d.second){
			i = d.first;
			++ans;
		}
	}

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




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

int main() {
    int h,w, i, j;

    cin >> h >> w;
    while(h!=0 || w!=0){
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
        cin >> h >> w;
    }
    return 0;
}


Measured memory_bytes: 3028
#include<iostream>
using namespace std;
int main()
{
  int H ,N;
  cin >> H >> N;
  
  int A[N];
  int sum=0;
  
  for(int i=0; i<N; i++){
    cin >> A[i];
    sum += A[i];
  }
  if(sum >=H){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#define MAXN 100
using namespace std;

typedef long long int lli;

int N, K, D[MAXN], A[MAXN][MAXN], cnt[MAXN], ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    for(int j = 0; j < K; ++j){
        cin >> D[j];
        for(int i = 0; i < D[j]; ++i){
            cin >> A[j][i];
            cnt[A[j][i] - 1]++;
        }
    }
    for(int j = 0; j < N; ++j){
        if(!cnt[j]) ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3684
X,Y = list(map(int, input().split()))

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
      
if (X+Y) % 3 > 0:
  print(0)
  exit(0)
  
K = (X+Y)//3

if X < K or Y < K:
  print(0)
  exit(0)

comb = Combination(int(1e6+10))
print(comb(K, X-K))

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

// バーガーの長さ L とパティー数 S
vector<long long> L, S;

// 再帰関数
long long rec(int N, long long X) {
    if (N == 0) return 1;

    if (X == 1) return 0;
    else if (X <= L[N-1] + 1) return rec(N-1, X-1);
    else if (X == L[N-1] + 2) return S[N-1] + 1;
    else if (X <= L[N-1] * 2 + 2) 
        return rec(N-1, X - L[N-1] - 2) + S[N-1] + 1;
    else return S[N-1] * 2 + 1;
}

int main() {
    int N;
    long long X;
    cin >> N >> X;

    // L と S を予め求めておく
    L.assign(N+1, 1), S.assign(N+1, 1);
    for (int n = 1; n <= N; ++n) {
        L[n] = L[n-1] * 2 + 3;
        S[n] = S[n-1] * 2 + 1;
    }

    cout << rec(N, X) << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
void parse(string S, vector<pair<int, vector<int>>> &C){
  int v = C.size();
  C.push_back(make_pair(-1, vector<int>(2, -1)));
  int N = S.size();
  int cnt = 0;
  int p = 0;
  for (int i = 0; i < N; i++){
    if (S[i] == '('){
      cnt++;
    }
    if (S[i] == ')'){
      cnt--;
    }
    if (S[i] == '[' && cnt == 0){
      p = i;
      break;
    }
  }
  string T = S.substr(1, p - 2);
  if (T != ""){
    C[v].second[0] = C.size();
    parse(T, C);
  }
  int q = p;
  while (S[q] != ']'){
    q++;
  }
  C[v].first = stoi(S.substr(p + 1, q - 1));
  string T2 = S.substr(q + 2, N - q - 3);
  if (T2 != ""){
    C[v].second[1] = C.size();
    parse(T2, C);
  }
  return;
}
void dfs1(vector<pair<int, vector<int>>> &T1, vector<pair<int, vector<int>>> &T2, vector<pair<int, vector<int>>> &T3, int u = 0, int v = 0){
  int w = T3.size();
  T3.push_back(make_pair(0, vector<int>(2, -1)));
  if (u != -1){
    T3[w].first += T1[u].first;
  }
  if (v != -1){
    T3[w].first += T2[v].first;
  }
  for (int i = 0; i < 2; i++){
    int c1 = -1;
    if (u != -1){
      c1 = T1[u].second[i];
    }
    int c2 = -1;
    if (v != -1){
      c2 = T2[v].second[i];
    }
    if (c1 != -1 && c2 != -1){
      T3[w].second[i] = T3.size();
      dfs1(T1, T2, T3, c1, c2);
    }
  }
  
  int cl1 = -1;
  if (u != -1){
    cl1 = T1[u].second[0];
  }
}
string dfs2(vector<pair<int, vector<int>>> &T3, int v = 0){
  string ans = "";
  ans += "(";
  if (T3[v].second[0] != -1){
    ans += dfs2(T3, T3[v].second[0]);
  }
  ans += ")";
  ans += "[";
  ans += to_string(T3[v].first);
  ans += "]";
  ans += "(";
  if (T3[v].second[1] != -1){
    ans += dfs2(T3, T3[v].second[1]);
  }
  ans += ")";
  return ans;
}
int main(){
  string A;
  cin >> A;
  string B;
  cin >> B;
  vector<pair<int, vector<int>>> T1;
  parse(A, T1);
  vector<pair<int, vector<int>>> T2;
  parse(B, T2);
  
  int N = T1.size();
  vector<pair<int, vector<int>>> T3;
  dfs1(T1, T2, T3);
  int M = T3.size();
  cout << dfs2(T3) << endl;
}


Measured memory_bytes: 3444
n, m = list(map(int, input().split()))

demands = []
for i in range(m):
    a, b = list(map(int, input().split()))
    demands.append((b, a))

demands = sorted(demands)
last_splited = -1
splited = 0

for end, start in demands:
    if last_splited < end and start >= last_splited:
        last_splited = end
        splited += 1

print(splited)


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

void solve(long long A, long double B)
{
    cout << fixed << std::setprecision(0) << floor(A * B) << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long A;
    scanf("%lld", &A);
    long double B;
    scanf("%Lf", &B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 3860
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std; 
int main() { 
  int maxc=0, maxs=0, c;
  string s;  
  multimap<string, int> a; 
  multimap<string, int>::iterator it, mc, ms;
  while(cin >> s) {   
    c = a.count(s);  
    if(c!=0) a.insert(make_pair(s, c+1));  
    else a.insert(make_pair(s, 1));
  }  
  for(it=a.begin(); it!=a.end(); it++) { 
    if(it->second > maxc) {
      maxc = it->second;  
      mc = it;  
    }  
    if(it->first.size() > maxs) {  
      maxs = it->first.size();   
      ms = it;  
    } 
  }  
  cout << mc->first << " " << ms->first << endl; 
  return 0;
}


Measured memory_bytes: 1200
#include <stdio.h>
void selection(int a[], int l, int r);
int main(void)
{
  int n, x;
  int a[110];
  scanf("%d %d", &n, &x);
  for (int i=0; i < n; i++) {scanf("%d", &a[i]);}
  selection(a,0,n);
  int ans = 0;
  for (int i=0;i<n;i++) {
    if (x >= a[i]) {
      ans++;
      x -= a[i];
      }
  }
  if (x > 0&&ans == n) {--ans;}
  printf("%d\n", ans);
  return 0;
}
void selection(int a[], int l, int r)
{
  for (int i=l; i < r-1; i++) {
    int min = i;
    for (int j=i+1; j < r; j++) { if (a[j] < a[min]) { min = j;} }
    int t = a[i];
        a[i] = a[min];
        a[min] = t;
  }
}


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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> Pair;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N, M, Q;
VL v, d, c;
vector<VL> con, color;

void paint(ll v, ll d, ll c) {
    if(color[v][d]) return;
    color[v][d] = c;
    if(d == 0) return;
    paint(v, d - 1, c);
    FOREACH(x, con[v]) paint(x, d - 1, c);
}

int main() {
    cin >> N >> M;
    con.resize(N);
    REP(i, M) {
        LCIN(a, b);
        con[--a].emplace_back(--b);
        con[b].emplace_back(a);
    }
    cin >> Q;
    REP(i, Q) {
        v.emplace_back(IN() - 1);
        d.emplace_back(IN());
        c.emplace_back(IN());
    }
    color.assign(N, VL(11, 0));
    REPR(i, Q - 1) paint(v[i], d[i], c[i]);
    REP(i, N) cout << color[i][0] << "\n";
}


Measured memory_bytes: 20980
# 入力
N = int(input())
S, P = (
    zip(*(
        (s, int(p))
        for s, p in (input().split() for _ in range(N))
    )) if N else
    ((), ())
)

ans = '\n'.join(
    str(i)
    for _, _, i in sorted(
        zip(
            S,
            P,
            range(1, N + 1)
        ),
        key=lambda t: (t[0], -t[1])
    )
)

# 出力
print(ans)


Measured memory_bytes: 3060
n = int(input())
a = list(map(int, input().split()))

sum_temp = 0
count = 0
left = 0

for i in range(n):

    while( i >= left):
        check = sum_temp & a[i]
        if check > 0:
            sum_temp -= a[left]
            left += 1
        else :
            count += (i-left) + 1
            sum_temp += a[i]
            break

print(count)

Measured memory_bytes: 24840
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
	ll n  ; 
	cin>>n ;
	ll a[100000+1] ;
	ll cou[100000+1] = {0};
	ll ans =0 ;
	rep(i ,n){
		ll temp ;
		cin>>temp ;
		a[temp] = 1  ;
		cou[temp]++;
		ans += temp;
	}
	int q ;
	cin>>q;
	while(q--){
		ll b , c ;
		cin>>b>>c;
		int tc = cou[b] ;
		ans -= b*tc;
		cou[b] = 0 ;
		cou[c] += tc ;
		ans += tc*c;
		cout<<ans<<endl;
	}

}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 4584
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<deque>
#include<map>
#include<iomanip>

#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 VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
const vector<VE> DIR{ {-1,0},{1,0},{0,-1},{0,1} };
const llong MOD = 1000000007;
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
template<class T>
int range_check(int val, int min, int max) {
	if (val < min) {
		return -1;
	}
	if (val > max) {
		return -1;
	}
	return val;
}
int main() {
	llong n, a, b;
	cin >> n >> a >> b;
	llong sets = n / (a + b);
	llong amari = n % (a + b);
	llong ans = sets * a;
	if (amari <= a) {
		ans += amari;
	}
	else {
		ans += a;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
a, b, c, d = gets.chomp.split.map(&:to_i)
ans = "No"
if (a - c).abs <= d
    ans = "Yes"
end
if a <= c and a <= b and b <= c
    if (b - a) <= d and (c - b) <= d
        ans = "Yes"
    end
end
if a >= c and c <= b and b <= a
    if (a - b) <= d and (b - c) <= d
        ans = "Yes"
    end
end
print(ans)

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector<ll> w(101);
vector<ll> v(101);
vector< vector<ll> > dp(101,vector<ll>(100001,-1));
ll calc(ll n,ll ww){
	if(n==0)
	return 0;
	if(ww==0)
	return 0;
	if(dp[n][ww]!=-1)
	return dp[n][ww];
	if((ww-w[n])>=0)
	dp[n][ww]=max(v[n]+calc(n-1,ww-w[n]),calc(n-1,ww));
	else
	dp[n][ww]=calc(n-1,ww);
	return dp[n][ww];
}
int main(){
	ll n,ww;
	cin>>n>>ww;
	for(int i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	cout<<calc(n,ww);
	return 0;
}

Measured memory_bytes: 81520
#include<stdio.h>
int main(void){
  int h,n,i,a[100000];
  scanf("%d %d",&h,&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<n;i++){
    h=h-a[i];
    if(h<=0){
      //printf("%d",h);
      printf("Yes");
      return 0;
    }
  }
  //printf("%d",h);
  printf("No");
  return 0;
}

Measured memory_bytes: 512
program sample
    implicit none
  
    integer(8) :: i,j,m,n,a,b
    integer(8),allocatable :: x(:),y(:)
  
    read(*,*) n,a,b
    if (a==0)then
        write(*,*)0
        stop
    end if

    m=(n/(a+b))*a
    if (mod(n,a+b)<=a)then
        m=m+mod(n,a+b)
    else
        m=m+a
    end if
  
    write(*,*) m
  
    stop
end program sample
  



Measured memory_bytes: 2832
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(int)(a); i!=(int)(b); i++)
#define RFOR(i, a, b) for(int i=(int)(a); i!=(int)(b); i--)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
using ll = long long;

struct node{
  int c, v, a, b;
  vector<node*> suc;
};

int main(){
  int n, m; cin >> n >> m;
  string s; cin >> s;
  vector<node> g(n);
  vector<bool> use(n, true);

  REP(i, n){
    g[i].c = s[i] == 'A';
    g[i].v = i;
  }

  REP(i, m){
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].suc.emplace_back(&g[b]);
    g[b].suc.emplace_back(&g[a]);
  }

  //既に満たしていない点をチェック
  stack<int> q;
  REP(i, n){
    REP(j, g[i].suc.size()){
      if(g[i].suc[j]->c) g[i].a++;
      else g[i].b++;
    }
    if(g[i].a==0 || g[i].b==0){
      q.push(i);
      use[i] = false;
    }
  }
  
  //条件を満たしていない点を取り除いて行く
  int cnt = 0;
  while(!q.empty()){
    int v = q.top(); q.pop();
    cnt++;
    REP(i, g[v].suc.size()){
      node* next = g[v].suc[i];
      if(v == next->v) continue;

      if(g[v].c == 1) next->a--;
      else next->b--;

      if(next->a == 0 || next->b == 0){
        if(use[next->v]){
          use[next->v] = false;
          q.push(next->v);
        }
      }
    }
  }

  if(cnt == n) cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;
}



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

int main(){
	int a[4][3][10];
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 3; j++){
			for (int k = 0; k < 10; k++){
				a[i][j][k] = 0;
			}
		}
	}
	int n, b, f, r, v;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> b >> f >> r >> v;
		a[b - 1][f - 1][r - 1] += v;
	}
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 3; j++){
			for (int k = 0; k < 10; k++){
				cout << " " << a[i][j][k];
			}
			cout << "\n";
		}
		if (i < 3){
			cout << "####################\n";
		}
	}
}

Measured memory_bytes: 3092
#include<cstdio>
#include<algorithm>
using namespace std;
static const int MAX_H = 1000;
static const int MAX_W = 1000;

int H, W, N;
int field[MAX_H][MAX_W];
int memo[MAX_H][MAX_W];

int main(){
	for(;;){
		scanf("%d %d %d", &H, &W, &N);
		if(H == 0 && W == 0 && N == 0) break;
		fill(memo[0], memo[H], 0);
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				scanf("%d", &field[i][j]);
			}
		}
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				if(i == 0 && j == 0) memo[i][j] = N - 1;
				if(memo[i][j] % 2 == 0){
					memo[i + 1][j] += memo[i][j] / 2;
					memo[i][j + 1] += memo[i][j] / 2;
				}else{
					if(field[i][j] == 0){
						memo[i + 1][j] += memo[i][j] / 2 + 1;
						memo[i][j + 1] += memo[i][j] / 2;
					}else{
						memo[i + 1][j] += memo[i][j] / 2;
						memo[i][j + 1] += memo[i][j] / 2 + 1;
					}
				}
			}
		}
		int i = 0, j = 0;
		for(;;){
			if(i == H || j == W){
				printf("%d %d\n", i + 1, j + 1);
				break;
			}
			if((memo[i][j] + field[i][j]) % 2 == 0) i++;
			else j++;
		}
	}
	return 0;
}


Measured memory_bytes: 10544
#include<stdio.h>

int main(){
  long n = 0;
  long c[1000] = {};
  long s[1000] = {};
  long f[1000] = {};
  long i = 0;
  long j = 0;
  long place;
  long time;
  long timea[1000] = {};
  scanf("%ld",&n);
  for(i=0;i<n-1;i++){
    scanf("%ld %ld %ld",&c[i],&s[i],&f[i]);
  }
  for(i=0;i<n-1;i++){
    place = i;
    time = 0;
    for(;place != n-1;place++){
      if(time < s[place]){
        time = s[place] + c[place];
      }else if(time % f[place] != 0){
        time += f[place] - (time % f[place]) + c[place];
      }else{
        time += c[place];
      }
    }
    timea[i] = time;
  }
  for(i=0;i<n;i++){
    printf("%ld\n",timea[i]);
  }
  return 0;
}
    
  

Measured memory_bytes: 256
//周♂雨扬是最强的！！！
//大佬祝您AK
//沈哲♂贝是最强的！！！
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<fstream>
using namespace std;
//ifstream fin(.in);
//ofstream fout(.out);
const long long mod=1000000007;
int n,num[100003],tong[100003];
long long ans=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
	}
	for(int i=1;i<=n;i++){
		tong[abs(i-1-(n-i))]++;
	}
	for(int i=0;i<=n;i++){
		if(tong[i]>0){
			ans=ans*tong[i]%mod;
		}
	}
	for(int i=1;i<=n;i++){
		tong[num[i]]--;
		if(tong[num[i]]<0){
			cout<<"0"<<endl;
			return 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}
//沈♂哲贝是最强的！！！
//大佬祝您AK
//周♂雨扬是最强的！！！

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


bool f(int a[],int n){
  rep(i,n){

    if(a[i]==0) return false;
  }

  return true;
}

int main(){
  int n,w,h;
  int a[1000000]={};
  int b[1000000]={};

  cin>>n>>w>>h;

  rep(i,n){
    int e,r,c;
    cin>>e>>r>>c;
    a[max(0,e-c)]++;
    a[e+c]--;
    b[max(0,r-c)]++;
    b[r+c]--;
  }

  rep(i,w+1){
    if(i==0) continue;
    a[i]+=a[i-1];
  }
  rep(i,h+1){
    if(i==0) continue;
    b[i]+=b[i-1];
  }

  if(f(a,w)||f(b,h)){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }

  return 0;
}



Measured memory_bytes: 10928
def gcd(a, b) -> int:
    return gcd(b % a, a) if a != 0 else b


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

if len(set(A)) == 1:
    print(A[0])
    exit()

ret = A[0]

for a in A[1:]:
    ret = gcd(ret, a)

print(ret)


Measured memory_bytes: 14252
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int X;
    static int[] A;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        X = sc.nextInt();
        A = sc.nextIntArray(N);

        System.out.println( solve() );
    }

    private static long solve() {
        int[][] cost = new int[N][N];

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

        for (int magic = 1; magic <= N-1; magic++) {
            for (int i = 0; i < N; i++) {
                int prevIndex = i - magic;
                if( prevIndex < 0 ) prevIndex+=N;
                cost[magic][i] = Math.min(cost[magic-1][i], A[prevIndex]);
            }
        }

        long ans = Long.MAX_VALUE;
        for (int magic = 0; magic <= N-1; magic++) {
            long sum = 0;
            for (int i = 0; i < N; i++) {
                sum += cost[magic][i];
            }
            ans = Math.min(((long)X) * magic + sum, ans);
        }
        return ans;
    }

    static class FastScanner {

        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 52820
using System;
using System.Collections.Generic;
using System.Linq;

namespace Test01
{   
    class Program
    {      
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] b = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            long sum = b[N - 2];

            for(int i = 0; i < N - 1; i++)
            {
                if (i == 0) sum += b[0];
                else sum += Math.Min(b[i], b[i - 1]);
            }

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 13396
# Quick sort クイックソート


class Card():

    def __init__(self, suit, num):
        self.suit = suit
        self.num = num
    
    def __repr__(self):
        return str(self.suit) + " " + str(self.num)


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j].num <= x.num:
            i += 1
            t = A[i]
            A[i] = A[j]
            A[j] = t
    A[r] = A[i + 1]
    A[i + 1] = x
    return i + 1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)


def mergesort(A, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    i1, i2 = 0, 0
    L = A[left:mid] + [Card("X", 2000000000)]
    R = A[mid:right] + [Card("X", 2000000000)]
    for j in range(left, right):
        if L[i1].num <= R[i2].num:
            A[j] = L[i1]
            i1 += 1
        else:
            A[j] = R[i2]
            i2 += 1


def compareCards(c1, c2):
    return c1.suit == c2.suit and c1.num == c2.num


def compareStacks(A, B):
    for i in range(len(A)):
        if not compareCards(A[i], B[i]):
            return False
    return True


n = int(input())
A, B = [], []
for i in range(n):
    suit, num = input().split()
    A += [Card(suit, int(num))]
    B += [Card(suit, int(num))]
quicksort(A, 0, n - 1)
mergesort(B, 0, n)
if compareStacks(A, B):
    print("Stable")
else:
    print("Not stable")
for a in A:
    print(a)



Measured memory_bytes: 47844
import java.util.Scanner;

import static java.lang.System.in;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        if(n<2){
            System.out.println(0);
            return;
        }
        long[][] dp = new long[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(i == j)
                    dp[i][j]=0;
                else{
                    long sum = sum(arr,i,j);
                    dp[i][j] = (long)10E18;
                    for (int k = i ; k < j ; k++) {
                        dp[i][j]  = Math.min(dp[i][k] + dp[k+1][j] + sum,dp[i][j]);
                    }
                }
            }
        }

        System.out.println(dp[0][n-1]);
    }
    private static long sum(int[] arr,int i,int k){
        long sum=0;
        for (int j = i; j <= k; j++) {
            sum  +=arr[j];
        }
        return sum;
    }
}

Measured memory_bytes: 38680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

const ll INF = 1e18;
void warshall_floyd(vector<vector<ll>>& d) {
  ll n = SZ(d);
  REP(i, n) REP(j, n) REP(k, n) if (d[j][k] > d[j][i] + d[i][k]) {
    d[j][k] = d[j][i] + d[i][k];
  }
}

int main() {
  ll n, m, r;
  cin >> n >> m >> r;
  vector<ll> a(r);
  REP(i, r) {
    cin >> a[i];
    a[i]--;
  }
  vector<vector<ll>> to(n, vector<ll>(n, INF));
  REP(i, n) { to[i][i] = 0; }
  REP(i, m) {
    ll u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    to[u][v] = c;
    to[v][u] = c;
  }
  warshall_floyd(to);
  ll ans = INF;
  sort(ALL(a));
  do {
    ll t = 0;
    REP(i, r - 1) { t += to[a[i]][a[i + 1]]; }
    ans = min(ans, t);
  } while (next_permutation(ALL(a)));
  cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
long long n,ans;
int l[maxn],len[maxn];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>l[i];
        len[l[i]]++;
    }
    for(int i=1;i<=2000;i++)
        len[i] += len[i-1];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)
                continue;
            int left = abs(l[i]-l[j]),r = l[i]+l[j]-1;
            ans += len[r]-len[left];
            if(l[i]>left && l[i]<=r)
                ans--;
            if(l[j]>left && l[j]<=r)
                ans--;
        }
    }
    cout<<ans/6<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main (void) {
string O, E;
cin >> O >> E;
for (int i = 0; i < min(O.length(), E.length()); i++) {
cout << O[i];
cout << E[i];
}
if (O.length() > E.length()) cout << O[O.length() - 1];
cout << endl;
return 0;
}

Measured memory_bytes: 256
S = [c for c in input()]
N = len(S)
L = []
R = []
S.append('f')

count = 0
for i in range(N):
  if S[i] == '<' and S[i + 1] == '<':
    count += 1
  elif S[i] =='<' and S[i + 1] == '>':
    count += 1
    L.append(count)
    count = 0
  elif S[i] == '>' and S[i + 1] == '<':
    count -= 1
    L.append(count)
    count = 0
  elif S[i] == '>' and S[i + 1] == '>':
    count -= 1
  elif S[i] == '<' and S[i + 1] == 'f':
    count += 1
    L.append(count)
  elif S[i] == '>' and S[i + 1] == 'f':
    count -= 1
    L.append(count)

M = len(L)
if L[0] < 0:
  R.append(abs(L[0]))

for j in range(M-1):
  if L[j] > 0:
    R.append(max([abs(L[j]),abs(L[j + 1])]))
    R.append(min([abs(L[j]),abs(L[j + 1])])-1)
if L[-1] > 0:
  R.append(abs(L[-1]))

print(sum([(1+k)*k//2 for k in R]))

Measured memory_bytes: 13616
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
public class Program
{
    public static void Main(string[] args)
    {
        string arr = Console.ReadLine();
        Console.WriteLine(arr.Count(i => i == '1'));
    }
}

Measured memory_bytes: 11220