akhauriyash/Code-Regression huggingface dataset:
import Control.Applicative
import Data.List
import Data.Map.Strict (Map, (!))
import qualified Data.Map.Strict as M

main :: IO ()
main = solve <$> getLine >>= print

solve :: String -> Int
solve s = let imp = M.fromList [('K',0),('U',0),('P',0),('C',0)]
              mp = foldl' (\m c -> M.insertWith (+) c 1 m) imp s
          in minimum $ map (mp !) "KUPC"



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

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

    vector<long long> A(N);
    vector<long long> B(N);
    map<long long, long long> count;
    for (long long i = 0; i < N; i++)
    {
        cin >> A[i];
        B[i] = A[i] - i;
        count[B[i]]++;
    }
    long long ans = 0;
    for (long long i = 0; i < N; i++)
    {
        count[B[i]]--;
        ans += count[-(A[i] + i)];
    }
    cout << ans << endl;
}


Measured memory_bytes: 28904
#include <bits/stdc++.h>
#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 INF 999999999
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;



int main(){
  string s,t;
  cin >> s;
  cin >> t;
  cout << (t+s);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define mod 1000000007
#define maxN 100011

int n, m, i;
ll x[maxN], y[maxN];

ll solve(int dim, ll *data) {
    ll ans = 0;
    ll sum = 0;
    ll i;

    sort(data + 1, data + dim + 1);

    for (i = 1; i <= dim; i++) {
        ans += (i - 1) * data[i] + mod - sum;
        ans %= mod;

        sum += data[i];
        sum %= mod;
    }

    return ans;
}

int main()
{
 //   freopen("test.in","r",stdin);

    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) scanf("%lld", &x[i]);
    for (i = 1; i <= m; i++) scanf("%lld", &y[i]);

    ll ans = (solve(n, x) * solve(m, y)) % mod;
    printf("%lld", ans);

    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	long long n;
	cin >> n;
	int ans=1;
	for(long long i=1;i*i<=n;i++)
	{
		if(n%i==0)
			ans=i;
	}

	cout << ans+n/ans-2 << endl;




}

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

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}
int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}

//vc alp(26) ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  int N;cin>>N;
  vi r(N),l(N);rep(i,N)cin>>l[i]>>r[i];
  int ans=0;
  rep(i,N){
    ans+=r[i]-l[i]+1;
  }
  cout<<ans<<endl;
  
}







Measured memory_bytes: 256
#include<stdio.h>
int Merge(int *,int,int,int);
int MergeSort(int *,int,int);
int sum=0;
int main()
{
  int i,n;
  int S[500000];

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

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

int MergeSort(int *A,int left,int right)
{  
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    MergeSort(A,left,mid);
    MergeSort(A,mid,right);
    Merge(A,left,mid,right);
  }
  else return 0;
}

int Merge(int *A,int left,int mid,int right){
  int k,n1,n2,L[500000],R[500000],i,j;
  n1=mid-left;
  n2=right-mid;
  for(i=0;i<n1;i++){
    L[i]=A[left+i];
  }
  for(i=0;i<n2;i++){
    R[i]=A[mid+i];
  }
  L[n1]=R[n2]=(1e9)+1;
  i=j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      sum++;
    }
    else{
      A[k]=R[j];
      j++;
      sum++;
    }
  }
}


Measured memory_bytes: 5668
import java.io.*;
import java.util.*;

public class Main {
    static class Writer {
        PrintWriter cout;

        Writer() throws IOException {
            cout = new PrintWriter(System.out);
        }

        Writer(String name) throws IOException {
            cout = new PrintWriter(new FileWriter(name));
        }

        StringBuilder out = new StringBuilder();

        void print(Object a) {
            out.append(a);
        }

        void close() {
            cout.print(out.toString());
            cout.close();
        }
    }

    static class Reader {
        BufferedReader in;

        Reader() throws IOException {
            in = new BufferedReader(new InputStreamReader(System.in));
        }

        Reader(String name) throws IOException {
            in = new BufferedReader(new FileReader(name));
        }

        StringTokenizer tokin = new StringTokenizer("");

        String next() throws IOException {
            if (!tokin.hasMoreTokens()) {
                tokin = new StringTokenizer(in.readLine());
            }
            return tokin.nextToken();
        }

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

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

    public static void main(String args[]) throws IOException {
        Reader in = new Reader();
        /*Writer out = new Writer();*/
        long n = in.nextInt();
        long m = in.nextInt();
        long maxd = 1;
        long max = (long) Math.floor((double) m / (double) n);
        if (n == 1) {
            maxd = m;
        } else {
            if (n * 2 <= m && m % 2 == 0)
                maxd = 2;
            for (long d = 3; d <= max; d++) {
                if (m % d == 0)
                    maxd = d;
            }
        }
        System.out.print(maxd);
    }
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  vpll ab(n), cd(m);
  rep(i,n){
    ll a,b; cin>>a>>b;
    ab[i]={a,b};
  }
  rep(i,m){
    ll c,d; cin>>c>>d;
    cd[i]={c,d};
  }
  rep(i,n){
    ll a=ab[i].first, b=ab[i].second;
    ll min=INF, res=0;
    rep(j,m){
      ll c=cd[j].first, d=cd[j].second;
      if(chmin(min,abs(a-c)+abs(b-d))){
        res=j+1;
      }
    }
    cout<<res<<endl;
  }
}

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

string s, ans;

int main() {
  cin >> s;

  int len = s.length();
  ans = "";
  
  for (int i = 0; i < len; i++) {
    ans += "x";
  }

  printf("%s", ans.c_str());

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct aaa{
	int x,y;
}a[200001];
int n,m,i,j,k,x,y,mp[501][501],g[501],flag,ans;
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
	for(i=1;i<=n;i++){
		mp[i][i]=1;
		for(j=m;j;j--){
			x=mp[i][a[j].x];y=mp[i][a[j].y];
			if(x&&y){
				g[i]=1;break;
			}
			if(x)mp[i][a[j].y]=1;
			if(y)mp[i][a[j].x]=1;
		}
	}
	for(i=1;i<=n;i++){
		if(g[i])continue;
		for(j=i+1;j<=n;j++){
			if(g[j])continue;
			flag=1;
			for(k=1;k<=n;k++)if(mp[i][k]&&mp[j][k])flag=0;
			ans+=flag;
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 1792
(let ((n (read))
      (m (read))
      (c (read))
      (b (make-array 0 :element-type 'integer
                       :adjustable t
                       :fill-pointer 0))
      (ans 0))
  (loop repeat m do
        (vector-push-extend (read) b))
  (loop repeat n do
        (let ((temp c))
          (dotimes (i m)
            (incf temp (* (aref b i) (read))))
          (if (< 0 temp) (incf ans))))
  (princ ans))


Measured memory_bytes: 7784
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    let vec: Vec<&str> = buf.split_whitespace().collect();
    let fst = vec[0].chars().nth(0);
    let snd = vec[0].chars().nth(1);
    let trd = vec[0].chars().nth(2);

    if snd != fst && trd != fst && trd != snd {
        println!("Yes", );
    }else{
        println!("No", );
    }
    //
    // let mut contain_a: bool = false;
    // let mut contain_b: bool = false;
    // let mut contain_c: bool = false;
    //
    // if fst == "a".chars().nth(0){
    //     contain_a = true;
    // }else if fst == "b".chars().nth(0){
    //     contain_b = true;
    // }else if fst == "c".chars().nth(0){
    //     contain_c = true;
    // }
    //
    // if snd == "a".chars().nth(0){
    //     contain_a = true;
    // }else if snd == "b".chars().nth(0){
    //     contain_b = true;
    // }else if snd == "c".chars().nth(0){
    //     contain_c = true;
    // }
    //
    // if trd == "a".chars().nth(0){
    //     contain_a = true;
    // }else if trd == "b".chars().nth(0){
    //     contain_b = true;
    // }else if trd == "c".chars().nth(0){
    //     contain_c = true;
    // }
    //
    // if contain_a && contain_b && contain_c{
    //     println!("Yes", );
    // }else{
    //     println!("No", );
    // }

}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);
//cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[200010];
ll kai[200010];
ll beki(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k%2==1){
            ret*=now;
            ret%=mod;
        }
        now*=now;
        now%=mod;
        k/=2;
    }
    return ret;
}
ll gyaku(ll n){
    return beki(n,mod-2);
}
void nckinit(ll n){
    kai[0]=1;
    kai[1]=1;
    for(int i=2;i<=n;i++){
        kai[i]=kai[i-1]*i;
        kai[i]%=mod;
    }
    gya[n]=gyaku(kai[n]);
    for(int i=n-1;i>=1;i--){
        gya[i]=gya[i+1]*(i+1);
        gya[i]%=mod;
    }
    gya[0]=1;
}
ll nck(ll n,ll k){
    if(k<0)return 0;
    if(k==0||n==k)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod;
    ret*=gya[k];
    ret%=mod;
    return ret;
}
ll npk(ll n,ll k){
    if(k<0)return 0;
    if(k==0)return 1;
    ll ret=kai[n];
    ret*=gya[n-k];
    ret%=mod;
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,x;cin>>n>>x;
    ll s[n];rep(i,0,n)cin>>s[i];
    nckinit(n+1);
    sort(s,s+n);
    reverse(s,s+n);
    ll dp[n+1][100001];
    rep(i,0,n+1){
        rep(j,0,100001)dp[i][j]=0;
    }
    dp[0][x]=1;
    rep(i,0,n){
        rep(j,0,100001){
            dp[i+1][j]+=dp[i][j]*(n-1-i);
            dp[i+1][j]%=mod;
            dp[i+1][j%s[i]]+=dp[i][j];
            dp[i+1][j%s[i]]%=mod;
        }
    }
    ll ans=0;
    rep(i,0,100001){
        ans+=dp[n][i]*i;
        ans%=mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 157312
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define erep(i, n) for (int i = 0; i <= (n); i++)
#define erep1(i, n) for (int i = 1; i <= (n); i++)
using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<double> a(n);
    double sum = 0;
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    double pot = sum / (4 * m);
    int count = n;
    rep(i, n) {
        if(a[i]<pot){
            count--;
        }
    }
    if(count>=m){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
}

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

bool chk(string &s, int l)
{
  map<string, pair<int, int> > hi;
	for (int i=0;i+l<=s.length();i++){
		string p = s.substr(i,l);
      auto I = hi.find(p);
      if (I == hi.end()) hi[p] = {i,i};
      else I->second.second = i;
    }
  
  for (auto &p : hi){
if (p.second.second - p.second.first >= l) return true;
  }
  return false;
}

int main()
{
  int n; string s; cin >> n >> s;
  
  int l = 0, r = n;
  while (l + 1 < r){
int m = (l + r) / 2;
    if (chk(s, m)) l = m;
    else r = m;
  }
  cout << l << endl;
	return 0;
}

Measured memory_bytes: 9460
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S],H=0,[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r();p=map(int,f[2:].split())
  if'0'==f[0]:print(g(n,E,*p))
  else:c,d,e=p;E[c],E[d]=E[c]+[(e,d)],E[d]+[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


Measured memory_bytes: 6312
#include <iostream>
#include <stack>

using namespace std;

int main() {

    stack<int> stk;
    string s;

    while (cin >> s) {

        if (s[0] >= '0' && s[0] <= '9') {
            stk.push(stoi(s));
        } else {
            int a, b;
            a = stk.top();
            stk.pop();
            b = stk.top();
            stk.pop();
            switch (s[0]) {
                case '+':
                    stk.push(a + b);
                    break;
                case '-':
                    stk.push(b - a);
                    break;
                case '*':
                    stk.push(a * b);
                    break;
            }
        }
    }

    cout << stk.top() << endl;
}


Measured memory_bytes: 3192
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

//nCrを返す関数.
long long int comb(long long int n, long long int r){
	if(n < r || n < 0)
		return 0;
	long long int x = 1, y = 1;
	if (n-r < r) r = n - r;
	for (long long int i = 0; i < r; i++)
	{
		x = x * (n - i);
		y = y * (i + 1);
	}
	return x / y;
}


int main(){
	string s;
	cin >> s;
	vector<int> a(1,0);
	char now = 'R';
	rep(i, s.size())
	{
		if(now == s[i]){
			a.back()++;
		} else {
			if(now=='R'){
				a.push_back(1);
				now = 'L';
			} else {
				a.push_back(1);
				now = 'R';
			}
		}
	}
	vector<int> ans(s.size(), 0);
	int c = 0;
	for (int i = 0; i < a.size();i+=2)
	{
		c += a[i];
		ans[c - 1] += (a[i] + 1) / 2 + a[i+1] / 2;
		ans[c] += a[i] / 2 + (a[i + 1] + 1) / 2;

		c += a[i + 1];
	}
	print(ans);
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

void solve(){
	int n, last, a, b;
	ll ans = 0ll;
	scanf("%d%d%d%d", &n, &a, &b, &last);
	REP(i, 1, n){
		int tmp;
		scanf("%d", &tmp);
		ans += min((ll)b, (ll)a * (ll)(tmp - last));
		last = tmp;
	}
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
	int main() {
		int n;
		int a[1001];
		cin >> n;
		for (int i = 0;i < n;i++)cin >> a[i];
		for (int i = 0;i < n;i++) {
			if (a[i] % 2 != 0)continue;
			if (a[i] % 3 != 0 && a[i] % 5 != 0) {
				cout << "DENIED" << endl;
				return 0;
			}
		}
		cout << "APPROVED" << endl;
		return 0;
}

Measured memory_bytes: 256
def calc(n, a, b):
    if n == 1:
        return b
    ls = [0 for i in range(n + 1)]
    ls[0] = 2
    ls[1] = 1
    for i in range(2, n + 1):
        ls[i] = ls[i - 1] + ls[i - 2]
    return ls[-1]

n = int(input())
print(calc(n, 2, 1))

Measured memory_bytes: 3064
S = input()
Q = int(input())
bs = ''
fs = ''
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten += 1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                fs += query[2]
            else:
                bs += query[2]
        else:
            if hanten % 2 == 0:
                bs += query[2]
            else:
                fs += query[2]
if hanten % 2 == 0:
    print(fs[::-1]+S+bs)
else:
    print(bs[::-1]+S[::-1]+fs)

Measured memory_bytes: 9876
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(string s) {
  s[5] = s[13] = ' ';
  cout << s << endl;
}

int main() {
  string s;
  cin >> s;
  solve(s);
  return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

/*** chmax, chmin ***/
// a < b ならば a を b で更新
// 更新されたら true を返す
template <typename T>
bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b; 
		return true;
	}
	return false;
}
// a > b ならば a を b で更新
// 更新されたら true を返す
template <typename T>
bool chmin(T &a, const T &b) {
	if (a > b) {
		a = b; 
		return true;
	}
	return false;
}
/*** chmax, chmin ここまで ***/


void Main()
{
	int n;
  	cin >> n;
  	auto digit = [&] (int x) {
      	return (int)floor(log10(x))+1;
    };
  	auto top = [&] (int x){
      	int p = pow(10,digit(x)-1);
		return x/p;
    };
  	auto inside = [&] (int x){
      	int d = digit(x);
      	if(d<=2) return 0;
      	int xtemp = x;
      	int temp = pow(10,digit(x)-1);
      	xtemp %= temp;
      	xtemp = (xtemp - (xtemp%10))/10;
      	return xtemp;
    };
  
  	int d = digit(n);
  	int t = top(n);
  	// cout << d << " " << t << endl;
  	auto f = [&] (int i, int j){
      	// i ではじまり j でおわる, n 以下の数はいくつあるか？
      	int ans = 0;
      	if(d == 0) return 0;
      	else if(d == 1){
			if(i == j && i <= n) return 1;
          	else return 0;
        }
      	
      	if(i == j) ans++;
      
      	if(i < t) ans += (pow(10,d-1)-1)/9;
      	else if(i > t && d >= 3) ans += (pow(10,d-2)-1)/9;
      	else if (i == t){
			ans += (pow(10,d-2)-1)/9;
          	ans += inside(n);
          	if(j <= n%10) ans++;
        }
      	return ans;
    };
      
  	ll count = 0;
  	rep3(i,1,9){
    	rep3(j,1,9){
          	// cout << "(" << i << "," << j << ": " << f(i,j) << ")  ";
        	count += f(i,j) * f(j,i);
        }
    }
  	cout << count << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 256
n = int(input())
full_set=set([x for x in range(1,14)])
cards={"S":[],"H":[],"C":[],"D":[]}
for i in range(n):
    suit,num = input().split()
    cards[suit].append(int(num))
for suit in ["S","H","C","D"]:
    suit_set = set(cards[suit])
    for num in sorted(list(full_set - suit_set)): print(suit,num)

Measured memory_bytes: 7736
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vl vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;
  std::cin >> n;
  for(int i=1;i<=n;i++){
    if(n%i==0){
      ll t = n/i;
      if(i<=9&&t<=9){
        std::cout << "Yes" << '\n';
        return 0;
      }
    }
  }
  std::cout << "No" << '\n';
  return 0;
}


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

int main(){
    int lo, hi;
    scanf("%d", &lo);
    hi = lo;
    for(int i = 0; i < 4; i++){
            int x;
        scanf("%d", &x);
        lo = min(x, lo);
        hi = max(x, hi);
    }
    int k;
    scanf("%d", &k);
    if(k < hi - lo){
        printf(":(");
    }else{
        printf("Yay!");
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin >> n;
    vector <long long> a(n);
    for(long long i = 0; i < n; i++){
        cin >> a[i];
    }
    vector <long long> step(n,0);
    for(long long i = 1; i < n; i++){
        long long before = a[i-1]+step[i-1];
        long long current = a[i]+step[i];
        if(before>current){
            step[i]=before-current;
        }
    }
    long long ans = 0;
    for(long long i = 0; i < n; i++){
        ans += step[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6416
#include <bits/stdc++.h>
using namespace std;
typedef bitset<10> bts;

int main() {
    // try every pattern in terms of when Josino's shop open
    // the number of patterns is 2**10
    
    int n; cin >> n;
    bts f[n]; 
    int p[n][11];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            int f_ij; cin >> f_ij;
            f[i].set(j, (f_ij > 0));
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 11; j++) {
            int p_ij; cin >> p_ij;
            p[i][j] = p_ij;
        }
    }

    int p_max = -10000000 * n;
    for (int i = 1; i < 1 << 10; i++) {
        bts pat(i);
        int p_cur = 0;
        for (int j = 0; j < n; j++) {
            int same = 0;
            for (int k = 0; k < 10; k++) {
                if (pat[k] && f[j][k]) same++;
            }
            p_cur += p[j][same];
        }
        p_max = max(p_max, p_cur);
    }

    cout << p_max << endl;
}

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

int main(){
    int n, h;
    cin >> n >> h;
    vector<int> as(n);
    vector<int> bs(n);
    int a, b;
    for (int i = 0; i < n; i++){
        cin >> a >> b;
        as[i] = a;
        bs[i] = b;
    }
    sort(as.begin(), as.end(), greater<int>());
    sort(bs.begin(), bs.end(), greater<int>());
    int attack = as[0];
    int ans = 0;
    int now = 0;
    while (1){
        if (h <= 0) break;
        ans++;
        if (now >= n || attack > bs[now]) h -= attack;
        else {
            h -= bs[now];
            now++;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define whole(s) (s).begin(), (s).end()
using namespace std;
typedef vector<ll> vx;
int main() 
{
    int N, Q;
    cin >> N >> Q;
 
    vx b;
    ll q;
    b.pb(N);
    for (int i = 0; i < Q; i ++) 
    {
        scanf("%lld", &q);
        while (b.size() && b.back() >= q) b.pop_back();
        b.pb(q);
    }
 
    vx res(N+1), t(N);
    t[b.size()-1] = 1;
    for (int i = b.size(); i --;) 
    {
        ll k = b[i];
        while (k > b[0]) 
        {
            int j;
            j = lower_bound(whole(b), k) - (b.begin()+1);
            t[j] += k / b[j] * t[i];
            k %= b[j];
        }
        res[k] += t[i];
    }
 
    for (int i = N; --i;) 
        res[i] += res[i+1];
    
 
    for (int i=1; i<=N; i++) 
        printf("%lld\n",res[i]);
 
    return 0;
}

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

using namespace std;

int main(){
    int n, d, x;
    cin >> n >> d >> x;
    int m[n], soma = n;
    for(int i = 0, y; i < n; i++){
        cin >> y;
        soma += (d - 1) / y;
    }
    cout << soma + x << "\n";
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.BigDecimal;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		double a = sc.nextDouble() / 3;
        double ans = a * a * a;
        System.out.println(String.format("%.12f", ans));
    }
}

Measured memory_bytes: 37372
from sys import stdin

n, x = map(int, stdin.readline().rstrip().split())
a = list(map(int, stdin.readline().rstrip().split()))

ans = 0
a.sort()
for i, ai in enumerate(a):
    if x < ai:
        break
    if i == n - 1:
        if x > ai:
            break
    x -= ai
    ans += 1

print(ans)

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


int main(){
    vector<int> num;
    for(long long int i=1;;i++){
        if(i*(i+1)*(i+2)/6>1e6)
            break;
        num.push_back(i*(i+1)*(i+2)/6);
    }
    vector<int> dp1(1e6+1,1e7);
    vector<int> dp2(1e6+1,1e7);
    dp1[0]=0,dp2[0]=0;
    for(int i=1;i<dp1.size();i++){
        for(int r=0;r<num.size() ;r++){
            if(num[r]>i) break;
            dp1[i]=min(dp1[i],dp1[i-num[r]]+1);
            if(num[r]%2==1){
                dp2[i]=min(dp2[i],dp2[i-num[r]]+1);
            }
        }
    }
    int n;
    while(cin>>n,n){
        cout<<dp1[n]<<" "<<dp2[n]<<endl;
    }
    return 0;
}

Measured memory_bytes: 10592
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;

int main()
{
	int y, x;
	while (1) {
		cin >> y >> x;
		if (y == 0 && x == 0)break;
		for (size_t i = 0; i < y; i++)
		{
			if (i == 0||i==y-1) {
				for (size_t i = 0; i < x; i++)
				{
					cout << '#';
				}
			}
			else {
				for (size_t i = 0; i < x; i++)
				{
					if(i==0||i==x-1){ cout << '#'; }
					else { cout << '.'; }
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

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

using namespace std;
const double PI=3.14159265358979323846;

int main() {

	int N;

	cin >> N;

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

	int tmp;
	for (int i = 0; i < N - 1; i++) {
		cin >> tmp;
		buka[tmp-1] += 1;
	}

	for (int i = 0; i < N; i++) {
		cout << buka[i] << endl;
	}
}

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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) REP (i, 0, n)
#define mset(a, n) memset(a, n, sizeof(a))

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;

int main() {
	string str;
	getline(cin, str);
	rep(i, str.size()) {
		if (str[i] >= 'a' && str[i] <= 'z') {
			str[i] = str[i] - ('a' - 'A');
		}
	}
	cout << str << endl;
}

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

mod = 10**9+7

a9 = 1
a8 = 1
a10 = 1
for _ in range(N):
    a9 = a9 * 9 % mod
    a8 = a8 * 8 % mod
    a10 = a10 * 10 % mod

ans = (a10 - 2*a9 + a8) % mod
print(ans)

Measured memory_bytes: 9180
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using node = tuple< ll, ll, ll>;
const ll inf = numeric_limits< ll >::max()/3;

int main(void){
  string s;
  cin >> s;
  for(int i = 0;i < (int)s.size()-1;++i){
    if(s.substr(i,2) == "AC"){
      puts("Yes");
      return 0;
    }
  }
  puts("No");
  return 0;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m,q=map(int,input().split())
    LR=[tuple(map(int,input().split())) for i in range(m)]
    PQ=[tuple(map(int,input().split())) for i in range(q)]
    dp=[[0]*(n+1) for _ in range(n+1)] #i(1-)以上j(1-)以下の間に完全に含まれる列車の本数
    for l,r in LR:
        dp[l][r]+=1
    for i in range(n+1):
        for j in range(n):
            dp[i][j+1]+=dp[i][j]
    for i in range(n-1,0,-1):
        for j in range(n+1):
            dp[i][j]+=dp[i+1][j]
    for p,q in PQ:
        print(dp[p][q])

if __name__=='__main__':
    main()

Measured memory_bytes: 40360
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    A,B,C,x,y = LI()
    ans = float("inf")
    for c in range(0,2*(x+y+1),2):
        resa = max(0,x-(c >> 1))
        resb = max(0,y-(c >> 1))
        s = resa*A+resb*B+c*C
        if s < ans:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 39408
N = int(input())
A = [int(x) for x in input().split()]


def solve(A, N):
    S = [0]*N
    answer = 0
    total = 0
    for i in range(N):
        total += A[i]
        S[i] = total
        if total == 0:
            d = 1 if S[i-1] < 0 else -1
            A[i] += d
            answer += 1
            total += d
        else:
            # S[i-1] < 0 and S[i] > 0
            # S[i-1] > 0 and S[i] < 0
            # S[i-1] > 0 and S[i] > 0
            if S[i-1] < 0 and S[i] < 0:
                answer += -S[i]+1
                total += -S[i]+1
            elif S[i-1] > 0 and S[i] > 0:
                answer += S[i]+1
                total += -(S[i]+1)
        S[i] = total
        #print(i, answer, "S[i-1]=%d"%S[i-1], "S[i]=%d"%S[i], sep="\t")
    return answer

if A[0] == 0:
    A[0] = -1
    m1 = solve(A, N) + 1
    A[0] = +1
    m2 = solve(A, N) + 1
    print(min(m1, m2))
else:
    m1 = solve(A, N)
    t = abs(A[0])
    A[0] = 1 if A[0] < 0 else -1
    m2 = solve(A, N) + t+1
    print(min(m1, m2))
    


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  int64_t result = A.at(0);
  for (int i = 2; i < N; i++) {
    result += A.at(i / 2);
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 4056
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    ll f[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    reverse(a,a+n);
    for(int i=0;i<n;i++){
        cin>>f[i];
    }
    sort(f,f+n);
    ll ma=a[0]*f[n-1],mi=-1LL;
    ll mid=(ma+mi+1)/2;
    ll unko;
    while(ma!=mid){
        ll k1=k;
        bool maki=true;
        for(int i=0;i<n;i++){
            if(a[i]*f[i]>mid){
                unko=mid/f[i];
                unko=a[i]-unko;
                if(k1<unko){
                    maki=false;
                }else{
                    k1-=unko;
                }
            }
        }
        if(maki){
            ma=mid;
        }else{
            mi=mid;
        }
        mid=(ma+mi+1)/2;
    }
    cout << ma<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long 
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back 
#define mp make_pair
#define inf 2000000009
#define mod 1000000007
using namespace std;

int main()
{ 
    fast;
   ll n,x,ans=1;
   cin>>n;

  ll match[n+2]={0};
  match[0]=3;

  for(ll i=0;i<n;i++)
  {
  	cin>>x;
  	ans=(ans*match[x])%mod;
  	match[x]--;
  	match[x+1]++;
  }
  cout<<ans<<endl;
   }

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

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

int main(){
    long long N,K,X,X1,X2,ans=0,keep1,keep2;
    cin >> X >> N;
    vector<long>p(N);
    FOR(i,N)cin >> p[i];
    if(count(p.begin(),p.end(),X) == 0){
        ans = X;
    }else{
        X1=X;
        X2=X;
        while(true){
            X1--;
            X2++;
            if(count(p.begin(),p.end(),X1) == 0){
                ans = X1;
                break;
            }
            if(count(p.begin(),p.end(),X2) == 0){
                ans = X2;
                break;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3512
int main(){
  int a,b,c;
 
  scanf("%d%d",&a,&b);
  if(b > a){
    c = a; 
    a = b; 
    b = c;
  }
  if(b != 0){
    c = gcd(a,b);
  }
  printf("%d\n",c);
  return 0;
}

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

Measured memory_bytes: 592
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1000000000;

int main(){
  int N, K;
  cin >> N >> K;
  int h[N];
  for(int i = 0; i < N; i++){
    cin >> h[i];
  }
  sort(h, h+N);
  int ans = INF;
  for(int i = 0; i <= N - K; i++){
    ans = min(ans, h[i+K-1] - h[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
N, K = map(int, input().split())
A = list(map(int, input().split()))

def is_ok(arg):
  cnt = 0
  for i in range(N):
    cnt += (A[i]-1)//arg
  if(cnt <= K):
    return True
  else:
    return False

def meguru_bisect(ng, ok):
  while(abs(ok-ng) > 1):
    mid = (ok+ng)//2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ans = meguru_bisect(0, 10**9)
print(ans)

Measured memory_bytes: 104040
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    unsigned A, B;
    cin >> A >> B;

    if(A > 8 || B > 8)
    {
        cout << ":(" << endl;
    } else
    {
        cout << "Yay!" << endl;
    }
    
    return 0;
}


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

int main(){
  char a[11],b[11],c[11];
  scanf("%s %s %s",a,b,c);
  int A=strlen(a);
  int B=strlen(b);
  if(a[A-1]==b[0]&&b[B-1]==c[0]) printf("YES");
  else printf("NO");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()

int charNum(int x, int y, vector<set<int>> &cha) {
  int ans = 0;
  for (int i = 0; i < 26; i++) {
    auto pos = cha[i].lower_bound(x);
    if (pos != cha[i].end() && *pos < y) ans++;
  }
  return ans;
}

int main() {
  int n, q;
  string s;
  cin >> n >> s >> q;
  vector<set<int>> cha(26);
  vector<int> ans;
  rep(i, n) {
    int x = s.at(i) - 'a';
    cha[x].insert(i);
  }
  rep(i, q) {
    int x;
    cin >> x;
    if (x == 1) {
      int y;
      char z;
      cin >> y >> z;
      int a = s.at(y - 1) - 'a';
      s.at(y - 1) = z;
      cha[a].erase(y - 1);
      cha[z - 'a'].insert(y - 1);
    } else {
      int y, z;
      cin >> y >> z;
      int res = charNum(y - 1, z, cha);
      ans.push_back(res);
    }
  }
  rep(i, ans.size()) { cout << ans.at(i) << endl; }
}

Measured memory_bytes: 24452
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
#define vecout(v,n) for(int i=0; i<n; i++)cout<<v[i]<<" "; cout<<endl;

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}




signed main() {
	int n, a, b;
	cin >> n >> a >> b;
	cout << max((n-2) * (b-a) + 1,0ll) << endl;
}



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

using namespace std;

#define C

#ifdef C
int A[100][100] = {};
int Cu[100] = {};
int R[100] = {};
int main(void)
{
	int r, c;
	int tmp;
	int sum = 0;
	cin >> r >> c;
	for (size_t i = 0; i < r; i++)
	{
		for (size_t j = 0; j < c; j++)
		{
			cin >> tmp;
			A[i][j] = tmp;
			Cu[j] += tmp;
			R[i] += tmp;
			sum += tmp;
		}
	}
	for (size_t i = 0; i < r ; i++)
	{
		for (size_t j = 0; j < c; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << R[i] << endl;
	}
	for (size_t i = 0; i < c; i++)
	{
		cout << Cu[i] << " ";
	}
	cout << sum << endl;


	return 0;

}
#endif // C

Measured memory_bytes: 3116
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container;

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

alias sread = () => readln.chomp();
enum MOD = 10 ^^ 9 + 7;

void main()
{
    long N, M;
    scan(N, M);
    auto uf = UnionFind(N);
    foreach (_; 0 .. M)
    {
        long X, Y, Z;
        scan(X, Y, Z);
        uf.unite(X - 1, Y - 1);
    }
    uf.size.writeln();
}

struct UnionFind
{
    private long[] rank;
    long[] data;
    long size;

    this(long N)
    {
        this.rank = new long[](N);
        this.data = iota!long(N).array;
        this.size = N;
    }

    long find(long x)
    {
        if (data[x] == x)
            return x;
        long r = this.find(data[x]);
        data[x] = r;
        return r;
    }

    void unite(long x, long y)
    {
        long rx = find(x);
        long ry = find(y);
        if (rx != ry)
        {
            this.size--;
            if (rank[rx] == rank[ry])
            {
                data[rx] = ry;
                rank[ry]++;
            }
            else if (rank[rx] < rank[ry])
                data[rx] = ry;
            else
                data[ry] = rx;
        }
    }

    bool isSame(long x, long y)
    {
        return this.find(x) == this.find(y);
    }
}


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

int main(){
    int q,n,p,d,x;
    
    deque <int> A;
    
    cin>>q;
    
    for(int i=0;i<q;i++){
        cin>>n;
        
        if(n==0){
            cin>>d>>x;
            if(d==0)A.push_front(x);
            else if(d==1)A.push_back(x);
        }
        else if(n==1){
            cin>>p;
            cout<<A.at(p)<<endl;
        }
        else if(n==2){
            cin>>d;
            if(d==0)A.pop_front();
            else if(d==1)A.pop_back();
        }
    }
    return 0;
}


Measured memory_bytes: 4560
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;

// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 

#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 

#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 


#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)

#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>

// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)1e5+5

void solve(){
    ll n;
    cin>>n;
    ll k;
    cin>>k;
    ll a[n];
    loop(i,0,n) cin>>a[i];
    ll x[n]={0}, y[n]={0}, ans = 0;
    loop(i,0,n){
        loop(j,0,i){
            if(a[j] > a[i]){
                y[i]++;
            }
        }
        loop(j,0,n){
            if(a[j] > a[i]){
                x[i]++;
            }
        }
    }
    loop(i,0,n){
        ll val = k*(k-1)/2;
        val = val%mod;
        ans = (ans + (y[i]*k)%mod)%mod;
        ans = (ans + (x[i]*(val))%mod)%mod;
    }
    print(ans%mod);
}

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

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



Measured memory_bytes: 256