akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
const ll maxs = 1e5+5;

ll n;
ll arr[maxs][3];

int main()
{
    cin >> n;
    for(ll i=0;i<n;i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    
    for(ll i=n-2;i>=0;i--) {
        arr[i][0] += max(arr[i+1][1],arr[i+1][2]);
        arr[i][1] += max(arr[i+1][0],arr[i+1][2]);
        arr[i][2] += max(arr[i+1][0],arr[i+1][1]);
    }

    cout << max(arr[0][0],max(arr[0][1],arr[0][2]));
    
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

vector<string> ans;
map<string, bool> mp;
int n;

void dfs(string cur, int maxchar)
{

    if (cur.size() == n)
    {
        assert(mp[cur] == false);
        mp[cur] = true;
        ans.push_back(cur);
        return;
    }
    // cerr << cur << " " << maxchar << endl;
    rep(i, n)
    {
        if (i > maxchar + 1)
        {
            break;
        }
        if (i > maxchar)
        {
            dfs(cur + (char)('a' + i), i);
        }
        else
        {
            dfs(cur + (char)('a' + i), maxchar);
        }
    }
}

int main()
{
    cin >> n;
    dfs("", -1);
    sort(ALL(ans));
    for (auto s : ans)
    {
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 15092
n = int(input())
k = int(input())
x = [int(i) for i in input().split()]
ans = 0
for i in range(n):
    tgt = x[i]
    cost_a = 2*abs(tgt)
    cost_b = 2*abs(tgt-k)
    ans += min(cost_a,cost_b)
print(ans)

Measured memory_bytes: 3060
from heapq import heappush, heappop
s = input()
K = int(input())
N = len(s)
heap = []
cnt = 0
for i in range(N):
	for j in range(i+1, min(i+K+1, N+1)):
		heappush(heap, s[i:j])

already = []
while True:
	w = heappop(heap)
	if w not in already:
		already.append(w)
	if len(already)>=K:
		break

print(already[-1])


Measured memory_bytes: 4552
n,T = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(n)]
ans = 1001
for i in range(n):
	if c[i][1] <= T:
		ans = min(ans,c[i][0])
if ans == 1001:
	print("TLE")
else:
	print(ans)
	


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>

using namespace std;


int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	string now = s.substr(0, 1);
	int answer = 1;

	for (int i = 1; i < n; i++) {
		if (s.substr(i, 1) != now) {
			now = s.substr(i, 1);
			answer++;
		}
	}

	cout << answer << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include<cmath>
#define N 100005
#define A 1000005
#define MOD 998244353 //1000000007 // //100000000
#define INF 1000000000000000000
#define ll long long
//#define M_PI 3.141592653589793238463

using namespace std;

#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define itr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define mem(a, b) memset(a, (ll)b, sizeof(a))
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount
#define ANS(s) {cout << s << "\n"; return;}

//~~~~~~fancy print~~~~~~~//
#define printpii(a) cout << a.ft << " " << a.sd << endl;
#define printpiii(a) cout << a.ft << " " << a.sd.ft << " " << a.sd.sd << endl;
#define print(a, n) rep(i, n) cout << a[i] << " "; cout << endl;
#define printv(v) for(auto x: v)cout << x << " "; cout << endl;
#define printm(a, n, m) rep(i, n) { rep(j, m) cout << a[i][j] << "\t"; cout << endl;}

ll dx[4] = {0, 0, 1, -1};
ll dy[4] = {1, -1, 0, 0};

void fast(){ios_base::sync_with_stdio(false);cin.tie(0);cout << setprecision(12) << fixed;}


void solve(){
    string s;
    cin >> s;
    if(s[0] != 'A') ANS("WA");
    ll f = 0;
    for(ll i = 2; i < s.size()-1; i++){
        if(s[i] == 'C'){
            if(f == 1) {ANS("WA");}
            else f = i;
        }
    }
    if(f == 0) ANS("WA");
    for(ll i = 1; i < s.size(); i++){
        if(i != f && s[i] >= 'A' && s[i] <= 'Z') ANS("WA");
    }
    ANS("AC");

}
main(){
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    fast();
    ll t = 1; //cin >> t;
    while(t--){
        solve();
    }
}


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

#define N 2000000

int A[N],j=0;

int Parent(int i){
  return i/2;
}

int Left(int i){
  return 2*i;
}

int Right(int i){
  return 2*i+1;
}

void exchange(int x,int y){
  int tmp;

  tmp=A[x];
  A[x]=A[y];
  A[y]=tmp;
}

void heapIncreaseKey(int i,int key){
  if(key<A[i])  return;
  A[i]=key;
  while(i>1 && A[Parent(i)]<A[i]){
    exchange(i,Parent(i));
    i=Parent(i);
  }
}

void maxHeapInsert(int key){
  j++;
  A[j]=INT_MIN;
  heapIncreaseKey(j,key);
}

void maxHeapify(int i){
  int l=Left(i);
  int r=Right(i);
  int largest;

  if(l<=j && A[l]>A[i]) largest=l;
  else largest=i;

  if(r<=j && A[r]>A[largest])largest=r;

  if(largest!=i){
    exchange(i,largest);
    maxHeapify(largest);
  }
}

int heapExtractMax(){
  int max;

  if (j<1) return 0;
  max=A[1];
  A[1]=A[j];
  j--;
  maxHeapify(1);
  return max;
}

main(){
  char str[20];
  int x;
  
  while(1){
    scanf("%s",str);
    if(strcmp(str,"end")==0) break;

    if(str[0]=='i') {
      scanf("%d",&x);
      maxHeapInsert(x);
    }
    else printf("%d\n",heapExtractMax());
  }
  return 0;
}

Measured memory_bytes: 4696
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
queue<int> q;
vector<vector<int> > v(101);
int dp[101];
int n, t = 0;
int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		int u, k; cin >> u >> k;
		for (int j = 0; j < k;j++) {
			int x; cin >> x;
			v[u].push_back(x);
		}
	}
	memset(dp, -1, sizeof(dp));
	q.push(1); dp[1] = 0;
	while (!q.empty()) {
		int a = q.front(); q.pop();
		for (int i = 0; i < v[a].size();i++) {
			if (dp[v[a][i]] == -1) {
				dp[v[a][i]] = dp[a] + 1;
				q.push(v[a][i]);
			}
		}
	}
	for (int i = 1; i <= n;i++) {
		cout << i << " " << dp[i] << endl;
	}
}

Measured memory_bytes: 3152
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define mod 1000000007
ll dp[10010];
ll dp2[10010];
int main(){
    int n,k;
    cin >> n >> k;
    vector<int>a;
    ll sm = 0;
    rep(i,n){
        int tmp;
        cin >> tmp;
        if(tmp<k){
            a.PB(tmp);
        }
        sm += (ll)tmp;
    }
    if(sm<k){
        cout << n << endl;
        return 0;
    }
    n = a.size();
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=2*k;j++){
            dp2[j] = dp[j];
            dp[j] = 0;
        }
        for(int j=0;j<=2*k;j++){
            dp[j] += dp2[j];
            dp[j] %= mod;
            dp[j+a[i-1]] += dp2[j];
            dp[j+a[i-1]] %= mod;
        }
    }
    for(int i=0;i<=2*k;i++){
        dp2[i] = 0;
    }
    ll s= 0;
    for(int i=k;i<=2*k;i++){
        s += dp[i];
        s %= mod;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=2*k;j++){
            if(j<a[i-1]){
                dp2[j] = dp[j];
            }else{
                dp2[j] = (mod+dp[j]-dp2[j-a[i-1]])%mod;
            }
        }
        ll ss = 0;
        for(int j=k;j<=2*k;j++){
            //cerr << dp2[i][j] << " ";
            ss += dp2[j];
            ss %= mod;
        }
        if(s==(ss*2%mod)){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
def main():
    A, B = map(int, input().split())
    s, t, a, b = '.', '#', A, B
    if A > B:
        s, t, a, b = t, s, b, a
    S = 100
    T = [[s] * S for _ in range(S)]
    
    a -= 1
    for i in range(b):
        X, Y = (i * 4)// len(T) * 4, ((i * 4)% len(T))
        T[X][Y:Y+3] = [t] * 3
        T[X+1][Y:Y+3] = [t] * 3
        T[X+2][Y:Y+3] = [t] * 3
        if a > 0:
            T[X+1][Y+1] = s
            a -= 1
    print(len(T), len(T[0]))
    for t in T:
        print(''.join(t))
main()


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int min_update(vector<int> const& as, int n) {
  multiset<int> mods;
  for (auto a : as)
    if (a % n != 0)
      mods.insert(a % n);
  int ops = 0;
  while (!mods.empty()) {
    int smallest = *begin(mods),
        largest = *rbegin(mods);
    mods.erase(begin(mods));
    mods.erase(prev(end(mods)));
    if (smallest < n - largest) {
      ops += smallest;
      mods.insert(largest + smallest);
    }
    else if (smallest == n - largest) {
      ops += smallest;
    }
    else {
      ops += n - largest;
      mods.insert(smallest - (n - largest));
    }
  }
  return ops;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> as(n);
  int total = 0;
  for (auto& a : as) {
    cin >> a;
    total += a;
  }
  
  int ans = 1;
  for (int i = 1; i * i <= total; i++) {
    if (total % i != 0) continue;
    int min_op = min_update(as, i);
    if (min_op <= k)
      ans = max(ans, i);
    int min_op_l = min_update(as, total / i);
    if (min_op_l <= k)
      ans = max(ans, total / i);
  }

  if (min_update(as, total) <= k)
    ans = total;
  cout << ans << endl;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
start=[]
end=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start.append(b)
    elif b==N:
        end.append(a)

startset=set(start)
endset=set(end)
if startset & endset:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')  

Measured memory_bytes: 21828
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func swap(a int64, b int64) (int64, int64) {
	return b, a
}

func gcd(a int64, b int64) int64 {
	if b > a {
		a, b = swap(a, b)
	}
	if b == 0 {
		return a
	} else {
		return gcd(a%b, b)
	}
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func min(nums ...int64) int64 {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int64(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int64) int64 {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int64(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func nextLong() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func nextByte() byte {
	sc.Scan()
	s := sc.Bytes()
	return s[0]
}

func main() {
	sc.Split(bufio.ScanWords)
	//ans := 1
	N := nextLong()
	K := nextLong()
	MOD := int64(1e9 + 7)
	ans := int64(0)
	for i := K; i <= (N + 1); i++ {
		ans += ((N+1)*(N)/int64(2) - (N-i+1)*(N-i)/int64(2)) % MOD //最大値
		ans -= ((i) * (i - 1) / int64(2)) % MOD                    //最小値
		ans = (ans + int64(1) + MOD) % MOD                         //微調整用
	}
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 1772
#include <bits/stdc++.h>
#include <set>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);

void solve() {
  int n; cin >> n;
  int t = n,x = 0;
  while (t>0) {
    x += t%10;
    t /= 10;
  }
  if (n%x == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

}

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



Measured memory_bytes: 256
// 134 B - Golden Apple 2019/07/20

#include <bits/stdc++.h>
#define rep(i ,n) for(int i=0;i<(int)(n);++i)
using namespace std;
typedef long long int int64;
typedef unsigned long long uint64;

int main(){
    int n; cin >> n;
    int d; cin >> d;
    int range=2*d+1;
    if((n%range)==0){
    cout << n/range << endl;
    } else {
        cout << (int)(n/range)+1 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "No" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int Roundup(int a,int b){
    return (a+b-1)/b;
}


signed main(void){
    int N,D,A;
    int x,h;
    vector<pair<int,int>> XH;
    vector<int> X,H;
    cin >> N >> D >> A;
    REP(i,N){
        cin >> x >> h;
        h=Roundup(h,A);
        XH.push_back({x,h});
    }
    sort(XH.begin(),XH.end());
    REP(i,XH.size()){
        X.push_back(XH[i].first);
        H.push_back(XH[i].second);
    }
    vector<int> Hs;
    Hs.push_back(H[0]);
    REP(i,N-1){
        Hs.push_back(H[i+1]-H[i]);
    }
    /*REP(i,Hs.size()){
        cout << Hs[i] << " ";
    }cout << endl;*/
    int Ans=0;
    int now=0;
    REP(i,Hs.size()){
        now+=Hs[i];
        //cout << now << endl;
        if(now<=0)continue;
        auto it = std::upper_bound(X.begin(), X.end(), X[i]+2*D);
        if(Hs.size()>it-X.begin()){
            Hs[(int)(it-X.begin())]+=now;
        }
        Hs[i]-=now;
        Ans+=now;
        now=0;
        
        /*cout << i MM Ans<< endl;
        REP(j,Hs.size()){
            cout << Hs[j] << " ";
        }cout << endl;*/
    }
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 11372
using System;

namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputData = Console.ReadLine();
            var splitInputData = inputData.Split(' ');
            var A = int.Parse(splitInputData[0]);
            var B = int.Parse(splitInputData[1]);
            if ((A < 1 || A > 9) || (B < 1 || B > 9))
            {
                Console.WriteLine(-1);
            }
            else
            {
                Console.WriteLine(A * B);
            }
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <math.h>


main()
{
long long int sum;
int n,m,min,max;

scanf("%d %d",&n,&m);
min=m;
max=m;
sum=m;
n--;
while(n--){
	scanf("%d",&m);
	if(min>m)min=m;
	if(max<m)max=m;
	sum+=m;
}
printf("%d %d %lld\n",min,max,sum);
}


Measured memory_bytes: 2744
from collections import defaultdict
n, m = map(int, input().split())
r = set()
r.add(1)
d = defaultdict(int)
for i in range(m):
  x, y = map(int, input().split())
  d[x] -= 1
  d[y] += 1
  if x in r:
    r.add(y)
  if d[x] == -1 and x in r:
    r.remove(x)
ans = len(list(r))
for e in d:
  if d[e] == -1 and e in r:
    ans -= 1
print(ans)

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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 310, M = N * N;

int n, m, k, d;
int g[N][N];
PII point[M];
vector<vector<LL>> h;

int main()
{
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			scanf("%d", &g[i][j]);
			point[g[i][j]] = {i, j};
		}
	point[0] = point[d];
	
	h.resize(d + 10);
		
	for (int i = 0; i < d; i ++ )
	{
		h[i].resize((n * m + d - 1) / d + 10);
		h[i][0] = 0;
		for (int j = 0; i + (j + 1) * d <= n * m; j ++ )
		{
			PII st = point[i + j * d], ed = point[i + (j + 1) * d];
			h[i][j + 1] = abs(st.F - ed.F) + abs(st.S - ed.S);
			h[i][j + 1] += h[i][j];
		}
	}
	
	scanf("%d", &k);
	while (k -- )
	{
		int l, r;
		scanf("%d%d", &l, &r);
		int t = l % d;
		l /= d, r /= d;
		printf("%lld\n", h[t][r] - h[t][l]);
	}
	return 0;
}

Measured memory_bytes: 12032
import math
n,m = map(int,input().split())
nb = math.factorial(n)
mb = math.factorial(m)
if abs(n-m) <= 1:
	if n % 2 == m % 2:
		print((nb * mb * 2)%(10**9+7))
	else:
		print((nb * mb)%(10**9+7))
else:
	print('0')

Measured memory_bytes: 5192
# -*- coding: utf-8 -*-
"""
Created on Fri Apr 24 22:56:49 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

N, *A = map(int, open(0).read().split())

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

b = np.arange(N+1)[:, None]
c = np.arange(N+1)[None, :]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))

for s in range(1,total+1):
    prev = dp
    a = s - S_bc
    dp = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1, 1:] += prev[1:, :-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a<0] = 0
#    print(s,dp)

ans = dp[count[2],count[3]]
print(ans)


Measured memory_bytes: 21148
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llu unsigned long long
#define ld double
#define llu unsigned long long
#define rep(i,x,y)  for(int i=int(x);i<int(y);++i)
#define For(i,x,y)  for(int i=int(x);i<=int(y);++i)
#define FOr(i,x,y)  for(int i=int(x);i>=int(y);--i)
#define pi acos(-1) 
#define mk make_pair
#define pa pair<ll,ll>
#define lf else if
#define IL inline
#define max(x,y)    ((x)<(y)?(y):(x))
#define min(x,y)    ((x)<(y)?(x):(y))
#define sqr(x)      ((x)*(x))
#define Mul(x,y)    ((x)=1LL*(x)*(y)%mod)
#define Add(x,y)    ((x)=((x)+(y))%mod)
#define E(x)        return writeln(x),0
#define LL			(long long)
#define p(x)        printf("~%lld~\n",LL(x))
#define pp(x,y)     printf("~~%lld %lld~~\n",LL(x),LL(y))
#define ppp(x,y,z)  printf("~~~%lld %lld %lld~~~\n",LL(x),LL(y),LL(z))
#define pppp(a,b,c,d)	printf("~~~%lld %lld %lld %lld\n",LL(a),LL(b),LL(c),LL(d))
#define f_in(x)     freopen(x".in","r",stdin)
#define f_out(x)    freopen(x".out","w",stdout)
#define open(x)     f_in(x),f_out(x)
#define fi first
#define se second
#define GuYue		puts("\nGuYueNa________________________________________________________________________________")
#define y1			fafa____
typedef complex<double> E;
namespace SHENZHEBEI{
#ifdef LOCAL
    struct _{_(){freopen("cf.in","r",stdin);}}_; 
#endif 
#define NEG 1
    static const int GYN=2333333;
    char SZB[GYN],*S=SZB,*T=SZB;
    inline char gc(){   if (S==T){  T=(S=SZB)+fread(SZB,1,GYN,stdin); if (S==T) return '\n';  }   return *S++;    }
#if NEG
    inline ll read(){    ll x=0,g=1; char ch=gc();   for (;!isdigit(ch);ch=gc()) if (ch=='-') g=-1;  for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x*g; }
    inline void write(ll x){    if (x<0) putchar('-'),x=-x;  if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#else
    inline ll read(){    ll x=0; char ch=gc();   for (;!isdigit(ch);ch=gc());    for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x;   }
    inline void write(ll x){    if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#endif
    inline char readchar(){ char ch=gc();   for(;isspace(ch);ch=gc());  return ch;  }
    inline ll readstr(char *s){ char ch=gc();   int cur=0;  for(;isspace(ch);ch=gc());      for(;!isspace(ch);ch=gc())  s[cur++]=ch;    s[cur]='\0';    return cur; }
	void Print(long long *a,int s,int t){For(i,s,t)printf("%lld ",a[i]);puts("");}
	void Print(int *a,int s,int t){For(i,s,t)printf("%d ",a[i]);puts("");}
	void Print(char *a,int s,int t){For(i,s,t)putchar(a[i]);puts("");}
	void writeln(ll x){write(x);putchar('\n');}
}using namespace SHENZHEBEI;
const ll N=100010;
ll n,pos,x[N],p[N],L,R,ans;
int main(){
	n=read(),pos=read();
	For(i,1,n)x[i]=read(),p[i]=read();
	L=1,R=n;
	for(;L<=R;){
		if (x[R]<=pos)return writeln(ans+pos-x[L]),0;
		if (x[L]>=pos)return writeln(ans+x[R]-pos),0;
		ans+=x[R]-x[L];
		if (p[L]>=p[R])	for(;L<R&&p[L]>=p[R];)	p[L]+=p[R--];
		else			for(;L<R&&p[L]<p[R];)	p[R]+=p[L++];
	}writeln(ans);
}

Measured memory_bytes: 3840
n = int(input())
x = list(map(int, input().split())) 
flag = 1
i = 0
v = 0
j = n-1
cont = 0
for i in range(n):
    for k in range(n-1, i, -1):
        if x[k] < x[k-1]:
            v = x[k-1]
            x[k-1] = x[k]
            x[k] = v
            cont = 1 + cont
print(*x)
print(cont)


Measured memory_bytes: 5596
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])

ans = 0
for h in range(H):
    for w in range(W):
        a = A[h][w]
        if a != -1:
            ans += C[a][1]
print(ans)


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

#define all(x) (x).begin(), (x).end()
#define szof(x) int32_t((x).size())
#define str(x) to_string(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const ll MOD998 = 998244353;
const int INF = 1e9;
const ll LLINF = 1e18;

mt19937_64 rng((uint) chrono::steady_clock::now().time_since_epoch().count());

template <class T>
T rnd(T l, T r) {
	return uniform_int_distribution<T>(l, r)(rng);
}

void run() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &x : a) {
		cin >> x;
	}
	vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(2)));
	vector<vector<bool>> used(n, vector<bool>(n));
	function<void(int, int)> rec = [&](int l, int r) {
		if (used[l][r]) {
			return;
		}
		if (l == r) {
			dp[l][r][0] = a[l];
			dp[l][r][1] = -a[l];
		} else {
			rec(l + 1, r);
			rec(l, r - 1);
			dp[l][r][0] = max(a[l] + dp[l + 1][r][1], a[r] + dp[l][r - 1][1]);
			dp[l][r][1] = min(dp[l + 1][r][0] - a[l], dp[l][r - 1][0] - a[r]);
		}
		used[l][r] = 1;
	};
	rec(0, n - 1);
	cout << dp[0][n - 1][0] << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout.precision(10); cout << fixed;
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		run();
	}
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
	return 0;
}


Measured memory_bytes: 495176
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();
        int count = 0;

        for(int i = 0; i <= a; i++){
            int rest1 = x;
            rest1 = rest1 - 500*i;
            if(rest1 < 0 || rest1 > 100*b + 50*c){
                continue;
            }

            for(int j = 0; j <= b; j++){
                int rest2 = rest1;
                rest2 = rest2 - 100*j;
                if(rest2 < 0 || rest2 > 50*c){
                    continue;
                }

                if(rest2 % 50 == 0 && rest2 / 50 <= c){
                    count++;
                }
            }
        }

        System.out.println(count);
        sc.close();
    }

}


Measured memory_bytes: 23380
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f40;
const long long mod=1e9+7;
const long double PI = acos(0);
template <class T>void UNIQUE(vector<T> &x){
	sort(all(x));
	x.erase(unique(all(x)), x.end());
}

// }}} End Header
int main() {
	string s;
	cin >> s;
	reverse(all(s));
	ll cnt = 0, ans = 0;

	rep(i,s.size()){
		if(s[i] == 'B'){
			ans+=(i-cnt);
			cnt++;
		}
	}


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

Measured memory_bytes: 3728
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;

int main(){
    int n, l;
    cin>>n>>l;
    string a[110];
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n);
    string ans;
    for(int i=0; i<n; i++) ans+=a[i];
    cout<<ans<<endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int px[24],py[24],kx,ky;
int num[24][4] = {0};

int H,W,N,ans;
int field[12][12] = {0};

int dx[] = {0,-1,0,1} , dy[] = {1,0,-1,0};
bool done[12][12];

map<int,int> memo[24];

int dfs(int pos,int bit){
	if(memo[pos].find(bit) != memo[pos].end() )return memo[pos][bit];
	if(bit==(1<<N)-1){
		rep(d,4){
			int cx = px[pos]+dx[d] , cy = py[pos]+dy[d];
			while( field[cy][cx] != -1){
				if(field[cy][cx] == 64)return 1;
				cy += dy[d] , cx += dx[d];
			}
		}
		return 0;
	}
	int ans = 0;
	rep(d,4){
		int cx = px[pos]+dx[d] , cy = py[pos]+dy[d];
		while( field[cy][cx] == -2 || done[cy][cx] == 1 || field[cy][cx] == 64){
			cy += dy[d] , cx += dx[d];
		}
		if(field[cy][cx] != -1){
			done[cy][cx] = 1;
			ans += dfs(field[cy][cx],bit | (1<<field[cy][cx]) );
			done[cy][cx] = 0;
		}
	}
	if(__builtin_popcount(bit) < 15){
		return memo[pos][bit] = ans;
	}else{
		return ans;
	}
}

int main(){
	while(cin >> W >> H ,W){
		N = ans = 0;
		rep(i,24)rep(j,4)num[i][j] = -1;
		rep(i,12)rep(j,12)field[i][j] = -1;
		rep(i,H)rep(j,W){
			int t;
			cin >> t;
			switch(t){
			case 0:
				field[i+1][j+1] = -2;
				break;
			case 1:
				field[i+1][j+1] = N;
				px[N] = j+1, py[N] = i+1;
				N++;
				break;
			case 2:
				kx = j+1 , ky = i+1;
				field[i+1][j+1] = 64;
				break;
			}
		}
		px[N] = kx , py[N] = ky;
		rep(i,24)memo[i].clear();
		cout << dfs(N,0) << endl;
	}
}

Measured memory_bytes: 12000
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

// reference: http://ir5.hatenablog.com/entry/20171209/1512821837

struct Scanner<'a> {
    cin: StdinLock<'a>,
}
 
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }
 
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }
 
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

use std::mem;
use std::cmp;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let mut R: usize = sc.read();
    let mut C: usize = sc.read();
    let mut K: usize = sc.read();
    let mut A = vec![vec![0; C]; R];
    for i in 0..K {
        let r: usize = sc.read();
        let c: usize = sc.read();
        let v: usize = sc.read();
        A[r-1][c-1] = v;
    }
    let mut dp = vec![vec![vec![0; 4]; C + 5]; R + 5];

    for i in 0..R {
        for j in 0..C {
            for k in (0..3).rev() {
                dp[i][j][k + 1] = cmp::max(dp[i][j][k + 1], dp[i][j][k] + A[i][j]);
            }
            for k in 0..4 {
                dp[i + 1][j][0] = cmp::max(dp[i + 1][j][0], dp[i][j][k]);
                dp[i][j + 1][k] = cmp::max(dp[i][j + 1][k], dp[i][j][k]);
            }
        }
    }

    let mut ans = 0;
    for k in 0..4 {
        ans = cmp::max(ans, dp[R - 1][C - 1][k]);
    }
    println!("{}", ans);
}

Measured memory_bytes: 707488
n, m = map(int, input().split())
x = [[] for _ in range(n)]
for q in range(m):
    a, b = map(int, input().split())
    x[b-1].append(a-1)
r = p = 0
for i in range(n):
    for j in x[i]:
        if j >= p:
            r += 1
            p = i
print(r)

Measured memory_bytes: 16688
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <iostream>
#include <limits>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef stringstream ss;
const int mii = numeric_limits<int>::min();
const int mai = numeric_limits<int>::max();
const ll mil = numeric_limits<long long>::min();
const ll mal = numeric_limits<long long>::max();

#define REP(i, a, b) for(long long i=a; i<=b; ++i)
#define RREP(i, a, b) for(long long i=a; i>=b; --i)
#define PB(x) push_back(x)
#define MP(x, y) make_pair(x, y)

int main(int argc, char **argv) {
    ll x, y, a, b, c;
    cin >> x>>y>>a>>b>>c;
    ll p[100001] = {0};
    ll q[100001] = {0};
    ll r[100001] = {0};

    REP(i, 1, a) {
        cin >> p[i];
    }
    REP(i, 1, b) {
        cin >> q[i];
    }
    REP(i, 1, c) {
        cin >> r[i];
    }

    sort(&p[1], &p[1]+a, greater<ll>());
    sort(&q[1], &q[1]+b, greater<ll>());
    sort(&r[1], &r[1]+c, greater<ll>());

    vector<ll> e;



    REP(i, 1, x)
        e.PB(p[i]);

    REP(i, 1, y)
        e.PB(q[i]);

    REP(i, 1, min(x+y, c))
        e.PB(r[i]);

    sort(e.begin(), e.end(), greater<ll>());

    ll tot = 0;
    REP(i, 0, x+y-1)
        tot += e[i];

    cout << tot <<endl;

    return 0;
}

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

int main() {
    int n;
    int b[200000];
    cin >> n;
    for(int i=0;i<n;i++) cin >> b[i];
    int count = 0;
    int mc = 0;
    for(int j=0;j<n-1;j++){
        if(b[j] >= b[j+1]){
            count++;
        }
        if(count > mc){
            mc = count;
        }
        if(b[j] < b[j+1]){
            count = 0;
        }
    }
    if(count >= mc) mc = count;
    cout << mc << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long s,xone,yone,xtwo,ytwo,zero;
  zero=0;
  cin>>s;
  xtwo=1000000000;
  yone=s/1000000000;
  
  if(yone==1000000000){
    ytwo=yone;
    xone=0;
  }
  else{
    ytwo=yone+1;
    xone=s%xtwo;
  }
  cout<<xone;
  cout<<" "<<zero;
  cout<<" "<<zero;
  cout<<" "<<yone;
  cout<<" "<<xtwo;
  cout<<" "<<ytwo;
}

Measured memory_bytes: 256
N, A, B = map(int, input().split())
S = input()

sm = 0
foreign = 1

for i in S:
    if i == 'c':
        print('No')
    elif sm < A + B:
        if i == 'b':
            if foreign <= B:
                print('Yes')
                sm += 1
                foreign += 1
            else:
                print('No')
        else:
            print('Yes')
            sm += 1
    else:
        print('No')

Measured memory_bytes: 4016
n, k = map(int, input().split())

if k <= n:
    if n%k == 0:
        ans = 0
    else:
        tmp = n//k
        ans = min(abs((n-k*tmp)), abs((n-(k*(tmp+1)))))
else:
    ans = min(abs(n), abs(n-k))

print(ans)

Measured memory_bytes: 9172
using System;
using System.Linq;
class aoj
{
    static void Main()
    {
        int[] c = new int[8];
        c[0] = 1;c[1] = 2;c[2] = 1;c[3] = 2;c[4] = 1;c[5] = 4;c[6] = 1;c[7] = 4;
        while (true)
        {
            string a = Console.ReadLine();
            if (String.IsNullOrEmpty(a)) break;
            int[] b = a.Split(' ').Select(int.Parse).ToArray();
            int[] f = new int[3];
            f[0] = 1000000000;
            for (int i = 0; i < 8; i++)
            {
                int e = 0;
                char[] h = new char[8];
                for (int j = 0; j < 8; j++)
                {
                    int d = j + i;
                    if (d >= 8)
                        d -= 8;
                    int g = b[j] - c[d];
                    if (g < 0)
                        g = 0;
                    e += g;
                    h[j] = (char)(c[d] + '0');
                }
                if (f[0] > e)
                {
                    f[0] = e;
                    f[1] = i;
                    string k = new string(h);
                    f[2] = int.Parse(k);
                }
                if (f[0] == e)
                {
                    string k = new string(h);
                    int l = int.Parse(k);
                    if (f[2] > l)
                    {
                        f[1] = i;
                        f[2] = l;
                    }
                }
            }
            int m = f[1];
            for (int i = 0; i < 8; i++)
            {
                int n = m + i;
                if (n >= 8)
                    n -= 8;
                if (i == 0)
                    Console.Write(c[n]);
                else
                    Console.Write(" " + c[n]);
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 9480
#include <iostream>
#include <map>

using namespace std;

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

    map<int, int> table;
    int count = 0;
    table[s] = count;
    count++;
    int nowS = s;
    while(true){
        if(nowS % 2 == 0){
            nowS = nowS / 2;
        }else{
            nowS = nowS * 3 + 1;
        }
        // cout << "nowS = " << nowS << " count = " << count << endl;
        if(table.find(nowS) == table.end()){
                table[nowS] = count;
                count++;
        }else{
            cout <<  count+1 << endl;    
            return 0;
        }
    }
    return 0;
}

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

string s, t;

vector<int> z_function(const string& s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> s >> t;
    auto t_z = z_function(t);
    int n = t.size();
    int m = s.size();
    while (s.size() <= n+m) {
        s += s;
    }
    int period_len = n;
    for (int i = 1; i < n; i++) {
    	//cout << i << ": " << t_z[i] << '\n';
    	if (t_z[i] == n-i && (n % i) == 0) {
    		period_len = min(period_len,i);
    	}
    }
    int num_periods = n / period_len;
    string p = t.substr(0,period_len);
    //cout << p << endl;
    if (s.size() % p.size() == 0) {
    	string r = p;
    	while (r.size() < s.size()) r += p;
        //check if s is cycle of r    
        auto r_z = z_function(r+'#'+s+s);
        for (int i = r.size()+1; i < r_z.size(); i++) {
            if (r_z[i] == r.size()) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    s += s;
    s += s;
    while (p.size() <= s.size()) p += p;
    //cout << (p+'#'+s) << endl;
    auto s_z = z_function(p+'#'+s);
    int ans = 0;
    for (int i = p.size()+1; i < s_z.size(); i++) {
    	int d = s_z[i] / period_len;
    	d /= num_periods;
    	//cout << i << ' ' << s_z[i] << ": " << d << '\n';
    	ans = max(ans,d);
    }
    cout << ans << '\n';
}



Measured memory_bytes: 179304
main = do
  n <- readLn
  s <- getLine
  t <- getLine
  let result = map (\x -> solve (drop x s) t) [0..n]
  out result [n..2*n]

solve :: String -> String -> Bool
solve [] _ = True
solve (s:ss) (t:ts) = if s == t
                        then solve ss ts
                        else False

out :: [Bool] -> [Int] -> IO ()
out (True:bs) (i:is) = print i
out (False:bs) (i:is) = out bs is


Measured memory_bytes: 508
#include <stdio.h>

int main (int argc, char* argv[]) {
  char s[4];
  scanf("%s", s);

  int cnt = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (s[i] == s[j]) cnt++;
    }
  }

  if (cnt == 8) printf("Yes\n");
  else printf("No\n");

  return 0;
}


Measured memory_bytes: 128
/*
    ????????°??§???????????¨????????????
*/

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include <float.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iterator>
#include <vector>
#include <map>
#include <utility>
#define LLU unsigned long long int
#define LL long long int
#define LD long double
using namespace std;
#define Lfmax DBL_MAX
#define LLUmax ULLONG_MAX
#define LLmax LLONG_MAX
#define dmax INT_MAX
#define vd vector<int>
#define vLL vector<long long int>
#define vLLU vector<unsigned long long int>
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define debug printf("asd\n")
#define debugd(a) printf("--%d\n",a)
#define debugdd(a,b) printf("--%d %d\n",a,b)
#define debugarr(a,b) for(int i=0 ; i<b ; i++)printf("%d ",a[i]);printf("\n")
#define newline printf("\n")
#define forin(a,b,c) for(int a=b ; a<c ; a++)
#define forde(a,b,c) for(int a=b ; a>=c ; a--)
#define UPC(a) (a>='A' && a<='B')
#define LWC(a) (a>='a' && a<='b')

inline void scd(int &a){scanf("%d",&a);}
inline void scdd(int &a,int &b){scanf("%d %d",&a,&b);}
inline void sctd(int &a,int &b,int &c){scanf("%d %d %d",&a,&b,&c);}
inline void sctd(LL &a,LL &b,LL &c){scanf("%I64d %I64d %I64d",&a,&b,&c);}
inline void scdlld(LL &a,LL &b){scanf("%I64d %I64d",&a,&b);}
inline void sclld(LL &a){scanf("%I64d",&a);}

inline void prd(int a){printf("%d",a);};
inline void prdd(int a,int b){printf("%d %d",a,b);};
inline void prtd(int a, int b, int c){printf("%d %d %d",a,b,c);};
inline void prtlld(LL a, LL b, LL c){printf("%I64d %I64d %I64d",a,b,c);};
inline void prdlld(LL a, LL b){printf("%I64d %I64d",a,b);};
inline void prtlld(LL a){printf("%I64d",a);};

#define scarrd(a,b) for(int index=0 ; index<b ; index++)scanf("%d",&a[index])
#define prarr(a,b) for(int i=0 ; i<b ; i++)printf("%d ",a[i])
#define iniarr(a,b) for(int i=0 ; i<b ;i++)a[i]=0
#define arr(a,b) int *a=(int *)malloc(b*sizeof(int))
#define llarr(a,b) long long int *a=(long long int *)malloc(b*sizeof(long long int))
#define st(a,b) char *a=(char *)malloc(b*sizeof(char))
#define grav 9.8
#define pi 3.14159265

int d=0;

void merge(int *a, int left,int mid, int right)
{
	int mile=mid-left;
	int rimi=right-mid;
	int l[mile+1],r[rimi+1];
	for(int i=0 ; i<mile ; i++)
	{
		l[i]=a[left+i];
	}
	for(int i=0 ; i<rimi ; i++)
	{
		r[i]=a[mid+i];
	}
	l[mile]=dmax;
	r[rimi]=dmax;
	
	int x=0,y=0;
	for(int i=left ; i<right ; i++)
	{
		if(l[x]<=r[y])
		{
			d++;
			a[i]=l[x];
			x++;
		}
		else
		{
			d++;
			a[i]=r[y];
			y++;
		}
	}
}

void mergeSort(int *a,int left,int right)
{
	//debugdd(left,right);
	if((left+1)<right)
	{
		//debug;
		int mid=(left+right)/2;
		mergeSort(a,left,mid);
		mergeSort(a,mid,right);
		merge(a,left,mid,right);
	}
	
}

int main()
{
	int n;
	scd(n);
	int a[n+1];
	forin(i,0,n)
	scd(a[i]);
	
	mergeSort(a,0,n);
	forin(i,0,n-1)
	printf("%d ",a[i]);
	printf("%d\n",a[n-1]);
	printf("%d\n",d);
	
	return 0;
}

Measured memory_bytes: 7036
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define INT(str) stoi((str), 0)
#define INTB(str) stoi((str), 0, 2) // 2進数の文字列を int に

int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main() {
  int k;
  cin >> k;
  cout << a[k-1] << endl;
}

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

// clang-format off
#define range(i, l, r) for (int i = (int)l; i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = ((int)(r) - 1); i >= (int)l; --(i))

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

inline void br(ostream &os = cerr) { os << endl; }

using int32 = int;
using int64 = long long;

const int mod     = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

const int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

void solver() {
  int64 N = input(), A = input(), B = input();

  vector<int64> X(N);
  cin >> X;

  int64 ans = 0;
  range(i, 1, N) {
    ans += min((X[i] - X[i - 1]) * A, B);
  }

  cout << ans << endl;
}

signed main(int argc, char *argv[]) {
  solver();
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
	string s;
	cin>>s;
	if(s[s.size()-1]=='s') s+="es";
	else s+="s";

	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
const int mod = 998244353;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
int n;
ll f[3];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n; f[1] = f[2] = -1e18;
	rep(i, 1, n) {
		char ch = '+'; int x;
		if(i != 1) cin >> ch;
		cin >> x;
		if(ch == '-') x = -x;
		f[0] += x, f[1] -= x, f[2] += x;
		if(ch == '-') {
			f[2] = std::max(f[1], f[2]);
			f[1] = std::max(f[0], f[1]);
		}
		f[1] = std::max(f[1], f[2]);
		f[0] = std::max(f[0], f[1]);
	}
	cout << f[0] << '\n';
}


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

int dx[]={-1,0,0,1};
int dy[]={0,1,-1,0};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int h,w;
	cin>>h>>w;
	int ch,cw,dh,dw; cin>>ch>>cw>>dh>>dw; ch--; cw--; dh--; dw--;
	char gr[h][w];
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin>>gr[i][j];
		}
	}
	int dist[h][w];
	memset(dist,-1,sizeof(dist));
	deque<pair<int,int> > q;
	dist[ch][cw]=0;
	q.push_back({ch,cw});
	while(!q.empty()){
		int x=q.front().first, y=q.front().second; q.pop_front();
		for(int i=0; i<4; i++){
			int nx=x+dx[i], ny=y+dy[i];
			if(nx<0||nx>=h||ny<0||ny>=w) continue;
			if(gr[nx][ny]=='#') continue;
			if(dist[nx][ny]==-1||dist[x][y]<dist[nx][ny]){
				dist[nx][ny] = dist[x][y];
				q.push_front({nx,ny});
			}
		}
		for(int i=-2; i<=+2; i++){
			for(int j=-2; j<=+2; j++){
				if(i==0&&j==0) continue;
				int nx=x+i, ny=y+j;
				if(nx<0||nx>=h||ny<0||ny>=w) continue;
				if(gr[nx][ny]=='#') continue;
				if(dist[nx][ny]==-1||dist[x][y]+1<dist[nx][ny]){
					dist[nx][ny] = dist[x][y]+1;
					q.push_back({nx,ny});
				}
			}
		}
	}
	cout<<dist[dh][dw];
}

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);

    REP(i, n)
    cin >> a.at(i);
    reverse(a.begin(), a.end());
    REP(i, n - 1)
    cout << a.at(i) << " ";
    cout << a.at(n - 1) << endl;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


int main()
{
	int cnt=0;
	string s;
	cin>>s;
	for(int i=0;i<3;i++)
	{
		if(s[i]=='1')cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 256
open System

let [| n; k; |] = stdin.ReadLine().Split() |> Array.map float

seq{1.0..n} |> Seq.map (fun x -> k / x) |> Seq.map (fun x -> match log x / log 2.0 with y when y < 0.0 -> 0.0 | y -> y )
|> Seq.map (fun x -> Math.Ceiling x) |> Seq.map (fun x -> 2.0 ** x) 
|> Seq.sumBy (fun x -> 1.0 / x / n)
|> stdout.WriteLine

Measured memory_bytes: 11476
#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> p(m);
  for (int i = 0; i < m; i++) {
    cin >> p[i].first >> p[i].second;
  }
  sort(p.begin(), p.end());

  for(int x = 0; x < 1000; ++x) {
    vector<int> v(3);
    int digit = 1;
    int nx = x/10;
    v.push_back(x%10);
    while(nx) {
      ++digit;
      v.push_back(nx%10);
      nx /= 10;
    }
    if (digit != n) continue;

    reverse(v.begin(), v.end());

    bool ok = true;
    for(int i = 0; i < m; i++)
     {
      if (v[p[i].first - 1] != p[i].second) ok = false;
    }
    if (ok) {
      cout << x << endl;
      return 0;
    }
  }

  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[m];
		int[] b = new int[m];
		boolean [] fromOne = new boolean[n];
		boolean[] possible = new boolean[n];
		for(int i = 0; i < m; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			if(a[i] == 1 || b[i] == 1) fromOne[Math.max(a[i], b[i]) - 1] = true;
			if(a[i] == n || b[i] == n) possible[Math.min(a[i], b[i]) - 1] = true;
		}
		for(int i = 0; i < n; i++) {
			if(fromOne[i] == true && possible[i] == true) {
				System.out.println("POSSIBLE");
				return;
			}
		}
		System.out.println("IMPOSSIBLE");
	}
}


Measured memory_bytes: 97200
from collections import *
import sys
from bisect import *
input=sys.stdin.readline
from math import *
t=1
while(t):
    t-=1
    n,m,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    prea=[a[0]]
    preb=[b[0]]
    for i in range(1,n):
        prea.append(prea[-1]+a[i])
    for j in range(1,m):
        preb.append(preb[-1]+b[j])
    r=0
    for i in range(n):
        if(k-prea[i]<0):
            break
        re=k-prea[i]
        rr=bisect_right(preb,re)
        r=max(r,i+1+rr)
    for i in range(m):
        if(k-preb[i]<0):
            break
        re=k-preb[i]
        rr=bisect_right(prea,re)
        r=max(r,i+1+rr)
    print(r)


Measured memory_bytes: 136276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> int_pair;
typedef pair<ll,ll> ll_pair;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
const int N=100;
const int W=10000;
int n,w,v[N],wi[N];
int dp[N+1][W+1];
 


//nap some ok
struct nap{
	vector<ll> v,w;
	ll N,W;
	vector< vector<ll> > dp;
	nap(ll n,ll wmax){
		N=n;W=wmax;
		v.resize(n);
		w.resize(n);
		vector<ll> wv(W+1,0);
		FOR(i,0,n+1){
			dp.push_back(wv);
		}
	}
	void calc(){
		FOR(i,0,N){
			FOR(j,0,W+1){
				if(j<w[i]){
					dp[i+1][j]=dp[i][j];
				}else{
					dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
				}
			}
		}
	}
	ll maxval(ll w){
		return dp[N][w];
	}


};


int main(){
	cin>>n>>w;
	nap na(n,w);
	FOR(i,0,n){
		cin>>na.v[i]>>na.w[i];
	}
	na.calc();
	cout<<na.maxval(w)<<endl;
	return 0;
}


Measured memory_bytes: 13124