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

constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

pair<int, int> a[4] = {
	{1,0},{-1,0},{0,1},{0,-1}
};
int main() {
	int H, W;
	cin >> H >> W;
	vector<string> grid(H);
	vector<vector<int>> dist(H, vector<int>(W, 0));
	for (int i = 0; i < H; i++)cin >> grid[i];
	queue<pair<int, int>> q; //y,x
	for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
		if (grid[i][j] == '#')q.push({ i,j });
	}
	while (!q.empty()) {
		auto pos = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			pair<int, int> n = { pos.first + a[i].first,pos.second + a[i].second };
			if (n.first < 0 || n.first >= H || n.second < 0 || n.second >= W)continue;
			if (grid[n.first][n.second] == '#' || dist[n.first][n.second] != 0)continue;
			dist[n.first][n.second] = dist[pos.first][pos.second] + 1;
			q.push(n);
		}
	}
	int ans = -INF;
	for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
		ans = max(ans, dist[i][j]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 13456
def recursion(ary)
  counter = 0
  while ary.min != 0 do
    ary.map! { |x|  x-= 1 }
    counter += 1
  end
  if ary.first != 0 && ary.last != 0
    ary1 = ary[0..(ary.index(0) - 1)]
    counter += recursion(ary1)
    ary2 = ary[(ary.index(0) + 1)..-1]
    counter += recursion(ary2)
  elsif ary.length == 1
    return counter
  elsif ary.first == 0
    ary.shift
    counter += recursion(ary)
  elsif ary.last == 0
    ary.pop
    counter += recursion(ary)
  end
  counter
end
def main()
  n = gets.chomp.to_i
  h = gets.chomp.strip.split(' ').map(&:to_i)
  puts "#{recursion(h)}"
end
main

Measured memory_bytes: 3836
#include<bits/stdc++.h>
#define ll long long
using namespace std;
/*
int vistd[10004];
vector<int>a[10004];
vector<int>dis(10004,0);
void dfs(int k){
   if(vistd[k]==0){
    vistd[k]=1;
    for(int i=0;i<a[k].size();i++){
        if(!vistd[a[k][i]]){
/// to find the distance between each node and their children dis[a[k][i]]=dis[k]+1;
            dfs(a[k][i]);
        }
    }
   }

}
int freq[2004];
*/
int main()
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
int ans=0;
for(int i=0;i<k;i++)
    ans+=a[i];
cout << ans;



}


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

namespace ABC
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC095_A();
        }

        static void ABC095_A()
        {
            Console.WriteLine(Console.ReadLine().ToList().Count(x => x == 'o')*100+700);
        }
    }
}

Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  while(1) {
    int tmp = n;
    int check = tmp % 10;
    tmp /= 10;
    bool flag = true;
    while(tmp > 0) {
      if(tmp%10 != check) flag = false;
      tmp /= 10;
    }
    if(flag){ cout << n << endl; break; }
    ++n;
  }

  return 0;

}

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

int main(void)
{
	char str[1000];
	int n;
	int count;
	
	while (1){
		fgets(str, 1000, stdin);
		
		str[strlen(str) - 1] = ' ';
		
		if (strcmp("END OF INPUT ", str) == 0){
			break;
		}
		
		n = 0;
		while (str[n] != '\0'){
			count = 0;
			while (str[n] != ' '){
				count++;
				n++;
			}
			n++;
			printf("%d", count);
		}
		printf("\n");
	}
	
	return (0);
}

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

typedef long long lint;
#define M 1000000007

int main(){
    int N;
    cin >> N;
    lint T[100000],A[100000];
    for(int i=0;i<N;i++) cin >> T[i];
    for(int i=0;i<N;i++) cin >> A[i];

    lint TMax[100000],TMin[100000],AMax[100000],AMin[100000];
    TMax[0]=TMin[0]=T[0];
    for(int i=1;i<N;i++){
        if(T[i]>TMax[i-1]) TMax[i]=TMin[i]=T[i];
        else{
            TMin[i]=1;
            TMax[i]=T[i];
        }
    }
    AMax[N-1]=AMin[N-1]=A[N-1];
    for(int i=N-2;i>=0;i--){
        if(A[i]>AMax[i+1]) AMax[i]=AMin[i]=A[i];
        else{
            AMin[i]=1;
            AMax[i]=A[i];
        }
    }
    lint pat=1;
    for(int i=0;i<N;i++){
        lint max,min;
        max=(TMax[i]<AMax[i]?TMax[i]:AMax[i]);
        min=(TMin[i]>AMin[i]?TMin[i]:AMin[i]);
        if(max<min){
            cout << 0 << endl;
            return 0;
        }else pat=(pat*(max-min+1))%M;
    }
    cout << pat << endl;
    
    return 0;
}//

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,l;
    cin>>n>>l;
    string s;
    std::deque<string> deq;
    for (int i=0;i<n;i++) {
        cin>>s;
        deq.emplace_back(s);
    }
    sort(deq.begin(),deq.end());
    string ans="";
    for (int j=0;j<n;j++) {
        ans+=deq[j];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
typedef long long s64;
const int ONE=1000005;
const s64 INF=1e18;
#define next nxt
int get()
{
    int res = 1, Q = 1; char c;
    while((c=getchar())<48||c>57)
        if(c=='-') Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48&&c<= 57)
        res=res*10+c-48;
    return res*Q;
}
struct power
{
    s64 a,b;
    bool operator <(power A) const
    {
        if(A.a!=a) return a<A.a;
        return b<A.b;
    }
};
vector <power> A[ONE],R;
int n;
int x,y;
s64 l,r,K;
int next[ONE],first[ONE],go[ONE],w[ONE],tot;
int size[ONE],fat[ONE];
void Add(int u,int v,int z)
{
        next[++tot]=first[u],first[u]=tot,go[tot]=v,w[tot]=z;
        next[++tot]=first[v],first[v]=tot,go[tot]=u,w[tot]=z;
}
int dist[ONE];
int len_x,len_y;
s64 a1,b1,a2,b2;
int Find()
{
        if(len_y==0) return len_y;
        int l=0,r=len_y-1;
        while(l<r-1)
        {
            int mid=l+r>>1;
            a2=A[y][mid].a,b2=A[y][mid].b;
            if(b1+a2+dist[x]+dist[y]<=K) l=mid;
            else r=mid;
        }
        a2=A[y][r].a,b2=A[y][r].b;if(b1+a2+dist[x]+dist[y]<=K) return r;
        a2=A[y][l].a,b2=A[y][l].b;if(b1+a2+dist[x]+dist[y]<=K) return l;
        return len_y;
}

void Update(int u)
{
        x=0,y=0;
        for(int e=first[u];e;e=next[e])
            if(go[e]!=fat[u])
                if(!x) x=go[e];else y=go[e];
        if(size[x]>size[y]) swap(x,y);
        len_x=A[x].size(),len_y=A[y].size();
        R.clear();
        for(int i=0;i<len_x;i++)
        {
            a1=A[x][i].a,b1=A[x][i].b;
            if(Find()>=len_y) continue;
            R.push_back((power){a1+dist[x],b2+dist[y]});
            R.push_back((power){b2+dist[y],a1+dist[x]});
        }
        sort(R.begin(),R.end());
        int len=R.size();
        s64 maxx=INF;
        for(int i=0;i<len;i++)
            if(R[i].b<maxx)
                A[u].push_back(R[i]),maxx=R[i].b;
}
void Dfs(int u, int father)
{
        size[u]=1;
        int pd=0;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father) continue;
            fat[v]=u,dist[v]=w[e];
            Dfs(v,u);
            size[u]+=size[v],pd++;
            if(pd==2) Update(u);
        }
        if(!pd) A[u].push_back((power){0,0});
}
int Check()
{
        for(int i=1;i<=n;i++)
            A[i].clear();
        Dfs(1,0);
        return A[1].size()>0;
}
int main()
{
        n=get();
        for(int i=2;i<=n;i++)
        {
            x=get(),y=get();
            Add(i,x,y),r+=y;
        }
        while(l<r-1)
        {
            K=l+r>>1;
            if(Check()) r=K;
            else l=K;
        }
        K=l;
        if(Check()) printf("%lld",l);
        else printf("%lld",r);
}

Measured memory_bytes: 70132
package main

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

func main() {
	N := getStdinInt()
	A := getStdinIntArr()
	B := getStdinIntArr()
	C := getStdinIntArr()

	ans := 0
	prev := -1
	for i := 0; i < N; i++ {
		idx := A[i]
//		fmt.Printf("b:idx=%d\n", idx)
		ans += B[idx-1]
//		fmt.Printf("val=%d\n", B[idx-1])
		if prev != -1 && (prev+1) == idx {
			if (prev - 1) < len(C) {
//				fmt.Printf("c:idx=%d, len=%d\n", prev-1, len(C))
				ans += C[prev-1]
//				fmt.Printf("c:val=%d\n", C[prev-1])
			}
		}
		prev = idx
	}
	fmt.Printf("%d\n", ans)
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}
func getStdinInt2() (int, int) {
	list := getStdinIntArr()
	return list[0], list[1]
}
func getStdinInt3() (int, int, int) {
	list := getStdinIntArr()
	return list[0], list[1], list[2]
}
func getStdinInt64() int64 {
	str := getStdin()
	rtn, _ := strconv.ParseInt(str, 10, 64)
	return rtn
}
func getStdinIntU64() uint64 {
	str := getStdin()
	rtn, _ := strconv.ParseInt(str, 10, 64)
	return uint64(rtn)
}
func getStdinInt64_2() (int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1]
}
func getStdinInt64_3() (int64, int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1], list[2]
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}
func getStdinIntArr64() []int64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}
func getStdinIntArrU64() []uint64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]uint64, len(list))
	for idx, val := range list {
		r, _ := strconv.ParseInt(val, 10, 64)
		rtn[idx] = uint64(r)
	}
	return rtn
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}
func max64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}
func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}
func abs64(n int64) int64 {
	if n < 0 {
		return -n
	}
	return n
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


Measured memory_bytes: 2180
n,m = map(int,input().split())
a = list(map(int,input().split()))
p = [[aa,1] for aa in a]
for _ in range(m):
  b = list(map(int,input().split()))
  b.reverse()
  p.append(b)
p.sort()
p.reverse()
rest = n
score = 0
for pp in p:
  use = min(pp[1],rest)
  rest -= use
  score += pp[0] * use
print(score)

Measured memory_bytes: 42452
import java.util.Scanner;

public class Main {
	static int[] s = new int[200]; // オペランド100個と演算子99個が収まる容量
	static int top = 0;
	static int max = 200;

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

		while (sc.hasNext()) {
			if (sc.hasNextInt()) {
				int num = sc.nextInt();
				push(num);

			} else {
				String str = sc.next();
				int a = pop();
				int b = pop();

				switch (str) {
				case "+":
					push(b + a);
					break;

				case "-":
					push(b - a); // LIFO（後入れ先出し）

					break;
				case "*":
					push(b * a);
					break;
				}
			}
		}
		System.out.println(pop());

	}

	/* 配列によるスタックの実装 */

	private static void initialize() {
		top = 0;
	}

	private static boolean isEmpty() {
		return top == 0;
	}

	private static boolean isFull() {
		return top >= max - 1;
	}

	private static void push(int x) {
		if (!isFull()) {
			top++;
			s[top] = x;
		} else {
			System.err.println("容量オーバーです。");
		}
	}

	private static int pop() {
		int ret = -1;
		if (!isEmpty()) {
			ret = s[top];
			top--;
		} else {
			System.err.println("中身が空です。");
		}
		return ret;
	}

}


Measured memory_bytes: 26716
fun main() {
    val n = readLine()!!.toInt()
    val an = readLine()!!.split(" ").map(String::toLong)
    // 派手はない頂点の最大値
    val maxArr = LongArray(n + 1)
    maxArr[an.lastIndex] = an.last()
    for (i in an.lastIndex - 1 downTo 0) {
        maxArr[i] = maxArr[i + 1] + an[i]
    }

    // 根しかない場合
    if (n == 0) {
        if (an.first() == 1L) {
            println(1)
            return
        } else {
            println(-1)
            return
        }

    }
    // 根がおかしい場合
    if (0 < n) {
        if (an[0] == 1L) {
            println(-1)
            return
        }
    }

    // 根はループで処理しない
    var count = 1L
    var previousValue = 1L
    for (i in 1 until an.lastIndex) {
        // 前回の葉ではない頂点から、必要な葉の数が作れるか？
        if (previousValue * 2 < an[i]) {
            println(-1)
            return
        }

        val maxCurrentValue = previousValue * 2 - an[i]

        val currentValue = Math.min(maxCurrentValue, maxArr[i + 1])
//        println("$currentValue ${an[i]}")
        count += (currentValue + an[i])
        previousValue = currentValue
    }

    if(previousValue * 2 < an.last()){
        println(-1)
        return
    }
    count += an.last()

    println(count)
}

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

int main() {
    int n, q;
    string s;
    cin >> n >> s >> q;
    vector<set<int>> position(26);
    for (int i = 0; i < n; ++i) {
        position[s[i] - 'a'].insert(i);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int before; char after;
            cin >> before >> after;
            --before;
            position[s[before] - 'a'].erase(before);
            s[before] = after;
            position[s[before] - 'a'].insert(before);
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            int ans = 0;
            for (int j = 0; j < 26; ++j) {
                auto it = position[j].lower_bound(l);
                if (it != position[j].end() && *it < r) ++ans;
            }
            cout << ans << endl;
        }
    }
}


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

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

    vector<int> p;

    if (n == 2) 
    {
        cout << "YES" << endl;
        return 0;
    }

    for (int i = 0; i < n; i++)
    {
        cin >> pi;
        p.push_back(pi);
    }
    
    int first = -1, second = -1, temp;

    for (int i = 1; i < n; i++)
    {
        if (p[i] < p[i-1])
        {
            first = i;
            break;
        }
    }

    if (first == -1)
    {
        cout << "YES" << endl;
        return 0;
    }

    for (int i = first+1; i < n; i++)
    {
        if (p[i] < p[i-1])
        {
            second = i;
            break;
        }
    }

    first--;

    if (second >= 0 && second <= n)
    {
        temp = p[first];
        p[first] = p[second];
        p[second] = temp;
    }
    else
    {
        temp = p[first];
        p[first] = p[first+1];
        p[first+1] = temp;
    }
    

    for (int i = 1; i < n; i++)
    {
        if (p[i] < p[i-1])
        {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;

}


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

using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair <int, int> pii;

const int INF=0x3f3f3f3f;

ll pot[70];

int main() {
    ll x, y;
    scanf("%lld %lld", &x, &y);
    pot[0]=1;
    for (int i=1; i<=62; ++i) pot[i]=pot[i-1]*2;
    ll lo=0, hi=62, mid, sol;
    while (lo<hi) {
        mid=(lo+hi)/2;
        if (x*pot[mid]>0 && x*pot[mid]<=y) {
            lo=mid+1;
            sol=mid;
        }
        else {
            hi=mid;
        }
    }
    printf("%lld", lo);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	int n;
	char a[21][50] = 
	{"1","1","2","6","24","120","720","5040","40320","362880","3628800",
		"39916800","479001600","6227020800","87178291200","1307674368000","20922789888000","355687428096000","6402373705728000","121645100408832000","2432902008176640000"
	};
	while(scanf("%d",&n) != EOF){
		printf("%s\n",a[n]);
	}
	return 0;
}

Measured memory_bytes: 1000
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline void LB(vector<T>& v, T& a) { return *lower_bound(ALL(v),a); }
template <typename T> inline void LBP(vector<T>& v, T& a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline void UB(vector<T>& v, T& a) { return *upper_bound(ALL(v),a); }
template <typename T> inline void UBP(vector<T>& v, T& a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; }
template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int r;
  cin >> r;
  cout << 3*r*r << endl;

  return 0;
}

Measured memory_bytes: 256
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  if(s[0]==s[1] && s[2]==s[3] && s[0]!=s[2]){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  string s;
  ll x,y;
  cin>>s>>x>>y;
  vll a(0);
  vll b(0);
  ll cu=0;
  ll aa=0;
  ll bb=0;
  s=s+'T';
  rep(i,sz(s)){
    if(cu==0&&s[i]=='T'){
      x-=aa;
      cu++;
      aa=0;
      continue;
    }
    if(s[i]=='T'&&cu%2==0){
      if(aa){
        a.pb(aa);
        aa=0;
      }
      cu++;
    }
    else if(s[i]=='T'){
      if(bb){
        b.pb(bb);
        bb=0;
      }
      cu++;
    }
    else if(cu%2==0)aa++;
    else bb++;
  }
  vvll dp(sz(a)+2,vll(8001));
  dp[0][0]=1;
  for(int i=0;i<sz(a);i++){
    for(int j=0;j<=abs(x);j++){
      if(j>=a[i]){
        if(dp[i][j-a[i]]) dp[i+1][j]=1;
      }
      if(j+a[i]<=8000){
        if(dp[i][j+a[i]]) dp[i+1][j]=1;
      }
    }
  }
  vvll ddp(sz(b)+2,vll(8001));
  ddp[0][0]=1;
  for(int i=0;i<sz(b);i++){
    for(int j=0;j<=abs(y);j++){
      if(j>=b[i]){
        if(ddp[i][j-b[i]]) ddp[i+1][j]=1;
      }
      if(j+b[i]<=8000){
        if(ddp[i][j+b[i]]) ddp[i+1][j]=1;
      }
    }
  }
  if(dp[sz(a)][abs(x)]&&ddp[sz(b)][abs(y)]){
    COUT("Yes");
  }
  else COUT("No");
}


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

int main(void) {
    int64_t N;
    double value;
    cin >> N;
    vector<int64_t> v(N);
    

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

    sort(v.begin(), v.end());
    value = ((double)v[0]+v[1])/2;

    for(int i=2;i<N;i++) {
        value = (value+v[i])/2;
    }

    cout << setprecision(16) << value << "\n";
    

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int lef=j+1;
            int r=lower_bound(a+1,a+n+1,a[i]+a[j])-a;
            ans+=r-lef;
        }
    }
    cout<<ans;
}

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


int main()
{
int days,n;
cin>>days>>n;
int ans=0;;
while(n--)
{	int a;
	cin>>a;
	ans+=a;
}

if(days-ans >= 0)cout<<days-ans<<endl;
else cout << -1 << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
using namespace std;


int main()
{
	int n,maxCnt=0,cnt=0;
	cin >> n;
	vector<string>s(n);
	for (int i = 0; i < n;i++)cin >> s[i];
	s.push_back("}");
	int m;
	cin >> m;
	vector<string>t(m);
	sort(s.begin(), s.end());//"#"は前に来てしまう。
	for (int i = 0; i < m;i++)cin >> t[i];
	for (int i = 0; i < n; i++) {
		if(s[i] != s[i + 1]) {
			cnt = count(s.begin(),s.end(),s[i]) - count(t.begin(),t.end(),s[i]);
			maxCnt = max(maxCnt,cnt);
		}
	}
	cout << maxCnt << endl;
} 

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

S = input()
K = int(input())

def prefixlen(s, c):
    """文字列sの文字cのみからなる接頭辞の長さ"""
    count = 0
    for x in s:
        if x != c: break
        count += 1
    return count

l = prefixlen(S, '1')
print(S[l] if l < K else '1')


Measured memory_bytes: 2940
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, S, E) for (int(X) = (S); (X) < (E); ++(X))
#define rrep(X, S, E) for (int(X) = (E)-1; (X) >= (S); --(X))
#define itrep(X, Y) for (auto(X) = (Y).begin(); (X) != (Y).end(); (X)++)
#define all(X) (X).begin(), (X).end()
#define chmin(X, Y) (X) = min(X, Y);
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll INF = 9 * 1e18;
const ll MOD = 1e9 + 7;

void solve(long long N, long long K, long long Q, std::vector<long long> A) {
  ll ans = INF;

  rep(i, 0, N) {
    ll Y = A[i];

    multiset<ll> all;
    multiset<ll> sec;
    rep(j, 0, N) {
      if (A[j] >= Y) {
        sec.insert(A[j]);
      } else {
        if (sec.size() >= K) {
          int ssize = sec.size() - K + 1;
          auto iter = sec.begin();
          rep(k, 0, ssize) {
            all.insert(*iter);
            iter++;
          }
        }
        sec.clear();
      }
    }

    if (sec.size() >= K) {
      int ssize = sec.size() - K + 1;
      auto iter = sec.begin();
      rep(k, 0, ssize) {
        all.insert(*iter);
        iter++;
      }
    }

    if (all.size() >= Q) {
      auto iter = all.begin();
      rep(i, 0, Q - 1) { iter++; }
      ll X = *iter;
      chmin(ans, X - Y);
    }
  }
  print(ans);
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  long long Q;
  scanf("%lld", &Q);
  std::vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  solve(N, K, Q, std::move(A));
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

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

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

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

int main(){
  ll a = in();
  ll b = in();
  ll n = in();
  ll t = min(b-1,n);
  cout << t*a/b-a*(t/b) << endl;
  return 0;
}


Measured memory_bytes: 3764
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Q_Flowers solver = new Q_Flowers();
        solver.solve(1, in, out);
        out.close();
    }

    static class Q_Flowers {
        long[] t;

        public long get(int r) {
            long ans = 0;
            while (r >= 0) {
                ans = Math.max(t[r], ans);
                r = (r & (r + 1)) - 1;
            }
            return ans;
        }

        public void set(int pos, long val) {
            while (pos < t.length) {
                t[pos] = Math.max(val, t[pos]);
                pos |= pos + 1;
            }
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni();
            int[] h = in.na(n);
            int[] a = in.na(n);
            t = new long[n + 3];
            for (int i = 0; i < n; i++) {
                long best = get(h[i] - 1);
                set(h[i], a[i] + best);
            }
            out.println(get(n));
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

    }
}



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

int n, k, x, ans=0;

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

	for(int i=0; i<n; i++){
		cin >> x;
		ans += min(x*2, (k-x)*2);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define gc getchar()
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
inline int read(){char ch=gc;int w=1,s=0;while(!isdigit(ch)){if(ch=='-') w=-1;ch=gc;};while(isdigit(ch)){s=s*10+ch-'0';ch=gc;} return w*s;}
ll ANS[550][550];
ll lcm(ll a,ll b){return (ll)((__int128)a*b/__gcd(a,b));}
int N,np[101010],prime[100010],cnt;
int Hang[100010],Lie[100001];
inline void Init(int n)
{
	np[1]=1;
	for(rint i=2;i<=n;++i){
		if(!np[i]) prime[++cnt]=i;
		for(rint j=1;j<=cnt&&i*prime[j]<=n;++j){
			np[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	}
}int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
int seq[1000010];
int main()
{
	N=read();N+=2;
	Init(100100);
//	for(rint i=1;i<=N;++i) Hang[i]=prime[i],Lie[i]=prime[i+N];
	int a=1,b=(N<<1)+2;int tot=0;
	while(a<b)
	{
		seq[++tot]=prime[a++];
		seq[++tot]=prime[b--]; 
	} 
	for(rint i=1;i<=N;++i)
	{
		for(rint j=1;j<=N;++j)
		{
			if(!((i+j)&1))
			{
				int mid1=(i+j)>>1;
				int mid2=(N-i+j+1)>>1;
				ANS[i][j]=1ll*seq[mid1]*seq[mid2+N];
			}
		}
	}
	for(rint i=1;i<=N;++i){
		for(rint j=1;j<=N;++j)
		{
			if(!ANS[i][j])
			{
				ll res=1;
				for(rint d=1;d<=4;++d)
				{
					int ni=i+dx[d],nj=j+dy[d];
					if(ni<1||nj<1||ni>N||nj>N) continue;
					res=lcm(ANS[ni][nj],res);
				}
				ANS[i][j]=res+1;
			}
			if(i>1&&i<N&&j>1&&j<N)
			cout<<ANS[i][j]<<" ";
		}
		if(i>1&&i<N)
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 6656
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stdio.h>

using namespace std;

const int INF = 1e9 + 5;

int main(){

    int n;
    scanf("%d", &n);
    vector<int> h(n);
    for(int &x : h){
        scanf("%d", &x);
    }

    vector<int> dp(n, INF); 
    dp[0] = 0;
    for(int i = 0; i < n; ++i){
        for(int j : {i+1, i+2}){
            if(j < n){
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

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

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

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;

    ll ans = 0;
    if (8 * Q > D && 4 * H > D && 2 * S > D) {
        ans += N / 2 * D;
        N %= 2;
    }
    if (4 * Q > S && 2 * H > S) {
        ans += N * S;
        N = 0;
    }
    if (2 * Q > H) {
        ans += N * 2 * H;
        N = 0;
    }

    ans += N * 4 * Q;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import copy
from collections import deque

def dfs(E):
    connected = []
    connected.append(1)
    S = deque([])
    S.append(1)
    while len(S):
        v = S.pop()
        for vv in E[v-1]:
            if vv not in connected:
                connected.append(vv)
                S.append(vv)
    
    return len(connected)


N, M = map(int,input().split())
E = [[] for _ in range(N)]
bridge = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = bridge[i]
    E[a-1].append(b)
    E[b-1].append(a)

count = 0
for i in range(M):
    E2 = copy.deepcopy(E)
    a, b = bridge[i]
    E2[a-1].remove(b)
    E2[b-1].remove(a)
    if dfs(E2) != N:
        count += 1

print(count)


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

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; i++) cin >> l[i] >> r[i];

  vector<int> AC(S.size() + 1);
  for (int i = 1; i <= S.size(); i++) if (S[i - 1] == 'A' && S[i] == 'C') AC[i] = 1;
  for (int i = 1; i <= S.size(); i++) AC[i] += AC[i - 1];

  for (int i = 0; i < Q; i++) cout << AC[r[i] - 1] - AC[l[i] - 1] << endl;
}


Measured memory_bytes: 2176
#!/usr/bin/env python3
#ABC88 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
dx = [1,0,-1,0]
dy = [0,1,0,-1]
maze = [list(input()) for _ in range(h)]
d = [[inf]*w for _ in range(h)]
d[0][0] = 1
que = deque()
que.append((0,0))
while que:
    x,y = que.popleft()
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != '#' and d[ny][nx] == inf:
                d[ny][nx] = d[y][x] + 1
                que.append((nx,ny))

cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            cnt += 1
if d[-1][-1] == inf:
    print(-1)
else:
    print(cnt - d[-1][-1])


Measured memory_bytes: 40944
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
 
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
typedef int64_t ll;
 #define trace(x) cerr << #x << ": " << x << " " << endl;

#define endl '\n'
#define int ll
ll mod=1e9+7;
ll mod1=1e9+5;
ll power(ll a,ll b)
{
    if(b==0) return 1;
    else if(b%2==0)
        return power((((a%mod)*(a%mod))%mod),b/2)%mod;
    else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
}


int32_t main()
{
    IOS
 
       
            
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;++i)
    cin>>a[i];
    map<int,int> m;
    for(int i=0;i<n;++i)
    {
        int p;
        cin>>p;
        m[i+1]=p;
    } 
    map<int,int> m1;
    for(int i=0;i<n-1;++i)
    {
        int p;
        cin>>p;
        m1[i+1]=p;

    }
    int ans=0;
    ans+=m[a[0]];
    for(int i=1;i<n;++i)
    {
        ans+=m[a[i]];
        if(a[i]==a[i-1]+1)
            ans+=m1[a[i-1]];
    }
    cout<<ans;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<vector>
using namespace std;
 
int main() {
  int a,b,c,e;
  cin>>a>>b>>c;
  int d[a];
      for(int i=0;i<a;i++){
        d[i]=0;
      }
  for(int i=0;i<c;i++){
    cin>>e;
    d[e-1]++;
  }
    for(int i=0;i<a;i++){
      if(d[i]>c-b)cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
    }
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

template<typename T>
void O(T t){
  cout << t << endl;
}

const int mod = 1000000007;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,a,b;
  cin >> n >> a >> b;
  vector<ll> x(n);
  rep(i,n){
    cin >> x[i];
  }
  ll k = 0;
  rep(i,n-1){
    if((x[i+1] - x[i]) * a > b){
      k += b;
    }
    else{
      k += (x[i+1] - x[i]) * a;
    }
  }
  cout << k << endl; return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
R = defaultdict(int)
for a in A:
    R[a] += 1
Q = int(input())
for i in range(Q):
    b,c = map(int,input().split())
    cnt = R[b]
    del R[b]
    R[c] += cnt
    if i == 0:
        ans = 0
        for key in R.keys():
            ans += (R[key]*key)
        print(ans)
    else:
        ans = ans - cnt*b + cnt*c
        print(ans)


Measured memory_bytes: 94708
import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;

class Main{public static void main(String[] args){new Solver();}}

class Solver{
	ScanReader reader=new ScanReader(System.in);
	PrintWriter writer=new PrintWriter(System.out);
	Solver(){main(); writer.flush();}
	
	void main(){
		while(reader.hasNext()){
			int n=Integer.parseInt(reader.next());
			List<String> us=new ArrayList<String>(n);
			for(int i=0;i<n;i++) us.add(reader.next());
			int m=Integer.parseInt(reader.next());
			List<String> ts=new ArrayList<String>(m);
			for(int i=0;i<m;i++) ts.add(reader.next());
			
			boolean open=false;
			for(int i=0;i<m;i++){
				if(us.indexOf(ts.get(i))==-1)
					writer.println("Unknown "+ts.get(i));
				else{
					writer.println((open?"Closed":"Opened")+" by "+ts.get(i));
					open^=true;
				}
			}
		}
	}
}

class ScanReader{
	BufferedReader br;
	StringTokenizer st;
	public ScanReader(InputStream in){
		br=new BufferedReader(new InputStreamReader(in));
		st=null;
	}
	public boolean hasNext(){
		while(st==null || !st.hasMoreTokens()){
			try{
				if(!br.ready())
					return false;
				st=new StringTokenizer(br.readLine());
			}
			catch(IOException e){
				throw new RuntimeException(e);
			}
		}
		return true;
	}
	public String nextLine(){
		hasNext();
		return st.nextToken("");
	}
	public String next(){
		hasNext();
		return st.nextToken();
	}
}

Measured memory_bytes: 9732
#include <bits/stdc++.h>
#define F(i,a,b) for(ll i=a;i<=(b);++i)
#define dF(i,a,b) for(ll i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-7
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 10007;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 

int n;
int a[maxn],b[maxn];

int main(){
	cin>>n;
	F(i,1,n){
		cin>>a[i]>>b[i];
	}
	bool flg = 0;
	F(i,1,n){
		if(i<=n-2&&a[i]==b[i]){
			if(a[i+1]==b[i+1]){
				if(a[i+2]==b[i+2]){
					flg = 1;
				}
			}
		}
		if(flg) break;
	}
	if(flg) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 3600
h,w,k=map(int,input().split())
subcounter=0
counter=1
anslist=[]
c=1
for i in range(h):
    s=input()
    flag=False
    for _ in range(w):
      if s[_]=="#":
        flag=True
        subcounter+=1
    if flag:       
        uselist=[]
        #len(s)=w
        for i in range(w):
            if s[i]==".":
                uselist.append(counter)
            elif s[i]=="#" and counter<subcounter:
                uselist.append(counter)
                counter+=1
            else:
                uselist.append(counter)
        for _ in range(c):
            anslist.append(uselist)
        c=1
        counter+=1
    elif not flag:
        
        c+=1
howmany=len(anslist)
for _ in range(h-howmany):
  anslist.append(anslist[-1])
  
for some in anslist:
    print(*some)

Measured memory_bytes: 7504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll MOD=1e9+7;
const ll INF=1ll<<60;

//
//　定数, 変数 *********************************************
int K;
string S;
// *********************************************************
int main(){

    // 入力スタンダード
    cin >> K >> S;
    
    if(S.size() <= K){
        cout << S << endl;
    }else{
        cout << S.substr(0,K) + "..." << endl;
    }
    



    return 0;
}

Measured memory_bytes: 3628
Sp = input()
T = input()

if len(Sp) < len(T):
    print('UNRESTORABLE')
    exit(0)

candidates = []
for i in range(len(Sp) - len(T) + 1):
    x = Sp[i:i + len(T)]

    if all((x[idx] == '?' or x[idx] == T[idx] for idx in range(len(T)))):
        candidate = (Sp[:i] + T + Sp[i + len(T):]).replace('?', 'a')
        candidates.append(candidate)

if candidates:
    candidates.sort()
    print(candidates[0])
else:
    print('UNRESTORABLE')


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

int main(void)
{
    string s, t;
    cin >> s >> t;

    for(int i = 0; i < s.size(); ++i)
    {
        if(s[i] != t[i])
        {
            cout << "No" << endl;
            return 0;
        } 
    }
    
    if(s.size()+1 == t.size())
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}



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

int H,W,A[200000],B[200000],C[200000];
set<pair<int,int>>st;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;

int main(){
	cin>>H>>W;
	for(int i=0;i<H;i++){
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
	}
	for(int i=0;i<W;i++){
		C[i]=i;
		pq.push({0,i});
		st.insert({i,i});
	}
	for(int i=0;i<H;i++){
		auto it=st.lower_bound({A[i],-1});
		int t=-1;
		while(it!=st.end()&&it->first<=B[i]){
			t=it->second;
			C[it->second]=-1;
			auto it2=it;
			it++;
			st.erase(it2);
		}
		if(B[i]!=W-1&&t!=-1){
			C[t]=B[i]+1;
			st.insert({B[i]+1,t});
			pq.push({B[i]+1-t,t});
		}
		while(!pq.empty()&&pq.top().first+pq.top().second!=C[pq.top().second]){
			pq.pop();
		}
		if(pq.empty()){
			cout<<-1<<endl;
		}
		else{
			cout<<i+1+pq.top().first<<endl;
		}
	}
}


Measured memory_bytes: 16784
N,K = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
ans = 10**20
for i in range(N-K+1):
  ans = min(ans,min(abs(x[i])+abs(x[i+K-1]-x[i]),abs(x[i+K-1])+abs(x[i]-x[i+K-1])))
print(ans)

Measured memory_bytes: 14384
h,w=map(int,input().split())
m=[[1 if c=="#" else 0 for c in input()] for _ in range(h)]

n=[i[:] for i in m]
for i in range(1,h):
  n[i][0]=n[i-1][0]+int(m[i-1][0]-n[i][0]==-1)
for j in range(1,w):
  n[0][j]=n[0][j-1]+int(m[0][j-1]-n[0][j]==-1)
for i in range(1,h):
  for j in range(1,w):
    n[i][j]=min(n[i-1][j]+int(m[i-1][j]-n[i][j]==-1),n[i][j-1]+int(m[i][j-1]-n[i][j]==-1))
print(n[-1][-1])

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

using namespace std;

int main()
{
	string a, b;
	cin >> a >> b;

	int n = stoi(a + b);
	for (int x = 1; x * x <= n; ++x) {
		if (x * x == n) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <typeinfo>
//#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int main()
{
  int x, y;
  cin >> x >> y;
  cout << x + y / 2 << endl;
  return 0;
}

Measured memory_bytes: 256