akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;
const ll mod=1000000007;

ll pow_mod(ll a,ll n){
  ll cur=1;
  ll mul=a;
  while(n){
    if(n%2)cur=(cur*mul)%mod;
    mul=(mul*mul)%mod;
    n/=2;
  }
  return cur;
}
ll div_mod(int a){
  return pow_mod(a,mod-2);
}
ll fact[1000001];

ll comb(ll a,ll b){
  if(a<0||b<0)return 0;
  else if(b==0)return 1;
  ll res=fact[a];
  res=(res*div_mod(fact[b]))%mod;
  res=(res*div_mod(fact[a-b]))%mod;
  return res;
}

int main(){
  fact[0]=1;
  for(int i=1;i<=1000000;i++)
    fact[i]=(fact[i-1]*i)%mod;
  int N,M,K;
  cin>>N>>M>>K;
  ll res=0;
  for(int p=0;p<=K;p++){
    ll a=1;
    a=a*comb(N+2*p,p)%mod;
    a=(a*(N+1))%mod;
    a=(a*div_mod(N+p+1))%mod;
    a=a*comb(M+2*(K-p),K-p)%mod;
    a=(a*(M+1))%mod;
    a=(a*div_mod(M-p+1+K))%mod;
    a=(a*comb(N+M+2*K,N+2*p))%mod;
    res=(res+a)%mod;
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 8644
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * Created 2017/06/01.
 */
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    ArrayList<Integer> ary = new ArrayList<>();

    for (int i = 0; i < 5; i++) {
      int input = sc.nextInt();
      ary.add(input);
    }

    int w = ary.get(0);
    int h = ary.get(1);
    int x = ary.get(2);
    int y = ary.get(3);
    int r = ary.get(4);

    //????????¨??????????¨????
    double cs = r * r * 3.14;
    int rs = w * h;
    int x_max = x + r;
    int y_max = y + r;

    //????????¨??????
    if (rs < cs) {
      System.out.println("No");
    } else if (x < 0 || y < 0) {
      System.out.println("No");
    } else if (w < x_max || h < y_max) {
      System.out.println("No");
    } else {
      System.out.println("Yes");
    }
  }
}

Measured memory_bytes: 26256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n;
char arr[200010][11];
int a[200010];
int c;
int maxx;

int compare(const void *a, const void *b)
{
	return strcmp(a, b);
}

int main(void)
{
	int i;
	
	scanf("%d", &n);

	for(i = 0; i < n; i++)
	{
		scanf("%s", arr[i]);
	}
	
	qsort((void *) arr, n, sizeof(arr[0]), compare);
	
	i = 0;
	
	while(i < n)
	{
		int cnt = 1;
		
		while(strcmp(arr[i], arr[i + cnt]) == 0)
			cnt++;
		
		a[i] = cnt;
		
		i += cnt;
		
		if(maxx < cnt)
			maxx = cnt;
	}
	
	for(i = 0 ; i < n ; i++)
	{
		if(a[i] == maxx)
		{
			printf("%s\n", arr[i]);
		}
	}
	
	return 0;
}

Measured memory_bytes: 4808
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)

int n;
vector<int> a(100010), b(100010), c(100010), d(100010);

void bfs(int p)
{
    queue<int> q;
    set<int> v;
    q.push(p);
    v.insert(p);
    int t = 0;
    while (!q.empty())
    {
        int s = q.front();
        d[s] = c[t];
        t++;
        q.pop();
        rep(i, n - 1)
        {
            if (a[i] == s && v.find(b[i]) == v.end())
            {
                q.push(b[i]);
                v.insert(b[i]);
            }
            if (b[i] == s && v.find(a[i]) == v.end())
            {
                q.push(a[i]);
                v.insert(a[i]);
            }
        }
    }
}

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

    cin >> n;
    rep(i, n - 1) cin >> a[i] >> b[i];
    rep(i, n) cin >> c[i];
    sort(c.begin(), c.end(), greater<int>());
    int m = 0;
    rep(i, n - 1) m += c[i + 1];
    cout << m << endl;

    bfs(a[0]);

    rep(i, n) cout << d[i + 1] << ' ';
    cout << endl;

    return 0;
}


Measured memory_bytes: 2432
import java.util.Scanner;
 
class Main {
	int n;
	int[][] abc;
	int[][] dp;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Main m = new Main(sc);
		m.solve();
	}
	Main(Scanner sc){
		n = sc.nextInt();
		abc = new int[n][3];
		dp = new int[n+1][3];
		for(int i=0;i<n;i++){
			abc[i][0] = sc.nextInt();
			abc[i][1] = sc.nextInt();
			abc[i][2] = sc.nextInt();
		}
		dp[0][0] = 0;
		dp[0][1] = 0;
		dp[0][2] = 0;
	}
	void solve(){
		for(int i=1;i<=n;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					if(j==k) continue;
					dp[i][j] = Math.max(dp[i][j], dp[i-1][k]+abc[i-1][j]);
				}
			}
		}
		System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]),dp[n][2]));
	}
}

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

using namespace std;

#define pt pair<int, int>
#define x first
#define y second
#define what_is(x) cerr << #x << " is " << x << endl;
#define endl '\n'
#define int long long

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

	int n, k, temp, ans = 0;
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;
		ans += temp >= k;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
		Solve s = new Solve();
		s.solve();
	}
}

class Solve{
	Scanner in = new Scanner(System.in);

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

	void solve(){
		while(in.hasNext()){
			m = in.nextInt(); n = in.nextInt();
			if(n == 0 && m == 0) return;
			int[][] f = new int[n][m];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < m; j++) f[i][j] = in.nextInt();
			}

			ans = 0;
			for(int i = 0; i < n; i++){
				for(int j = 0; j < m; j++){
					int[][] v = f;
					calc(i, j, v, 0);
				}
			}

			System.out.println(ans);
		}
	}
	void calc(int x, int y, int[][] v, int num){
		ans = Math.max(ans, num);
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx >= 0 && nx < m && ny >= 0 && ny < n && v[ny][nx] == 1){
				v[ny][nx] = 0;
				calc(nx, ny, v, num + 1);
				v[ny][nx] = 1;
			}
		}
	}
}

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

int N;
int V[21],C[21];


int main()
{
    cin >> N;
    for(int i = 0; i < N; i++) cin >> V[i];
    for(int i = 0; i < N; i++) cin >> C[i];

    int sum = 0;
    for(int i = 0; i < N; i++)
    {
        int a = V[i] - C[i];
        sum += (a < 0 ? 0 : a);
    }

    cout << sum << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int c[n - 1], s[n - 1], f[n - 1];
    for (int i = 0; i < n - 1; i++)
        cin >> c[i] >> s[i] >> f[i];
    for (int i = 0; i < n; i++)
    {
        int t = 0;
        for (int j = i; j < n - 1; j++)
        {
            if (t < s[j]) t = s[j];
            else if (t % f[j] != 0) t = t + f[j] - t % f[j];
            t += c[j];
        }
        cout << t << endl;
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1e9+7;
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
 
int main(){
  int N;
  cin >> N;
  string str;
  map<string, int> S;
  REP(i, N){
    cin >> str;
    S[str]++;
  }
  int M = 0;
  for (auto itr = S.begin(); itr != S.end(); itr++){
    M = max(M, itr->second);
  }
  for (auto itr = S.begin(); itr != S.end(); itr++){
    if (M == itr->second){
      cout << itr->first << endl;
    }
  }
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A,B,C,K;
    cin >> A >> B >> C >> K;
    if(K<=A) cout << K << "\n";
    else if(K<=A+B) cout << A << "\n";
    else cout << A-(K-B-A) << "\n";
}

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

using namespace std;

int main()
{
	string s, as = "\0";

	cin >> s;

	for (size_t i = 0; i < s.length(); i += 2)
	{
		as += s[i];
	}
	
	cout << as << endl;

	return 0; 
}

Measured memory_bytes: 576
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		double r;
		r=scan.nextDouble();
		System.out.println(String.format("%.6f",r*r*Math.PI)+" "+String.format("%.6f",2*r*Math.PI));
		scan.close();
	}

}



Measured memory_bytes: 28048
#include <stdio.h>
    int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
     
    if(a==c) printf("%d",b);
    else
    if(b==c) printf("%d",a);
    else
    printf("%d",c);
     
     
    return 0;
    }

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

int main() {
  int ans = 1000000;
  string s,t;
  cin >> s >> t;

for (int i= 0; i < s.size(); i++) {
  if (i + t.size() > s.size()){
    break;
  }
  int cnt = 0;
  for (int j = 0; j < t.size(); j++){
    if (s[i+j] != t[j]) cnt++;
  }
  ans = min(ans, cnt);
}
cout << ans << endl;
}


Measured memory_bytes: 3552
# x_(n+1) = 2*a_n - x_n
def xn(ans,a,n):
  for i in range(n-1):
    ans[i+1]=2*a[i]-ans[i]
  return ans
  

n = int(input())
A = list(map(int,input().split()))
ans = [0]*n
ans[0] = sum(A)-2*sum(A[1:n:2])
ans = xn(ans,A,n)
print(" ".join(list(map(str,ans))))

Measured memory_bytes: 19144
#include <iostream>
#include <iomanip>
#include <numeric>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)
ll gcd(ll a, ll b)
{
    ll x, y;
    x = max(a, b);
    y = min(a, b);
    if (x % y == 0)
    {
        return y;
    }
    gcd(y, x % y);
}
int main()
{
    ll a, b;
    cin >> a >> b;
    cout << a * b / gcd(a, b) << endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  int ans = 10000000;
  for(int i = -100; i < 101; i++){
    int sum = 0;
    for(auto k : a) sum += (k - i) * (k - i);
    ans = min(ans, sum);
  }
  
  cout << ans << endl;
}


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

using namespace std;

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

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

  // dp[l][r] := [l, r) から開始したときの X-Y の得点
  vector<vector<long long>> dp(n + 10, vector<long long>(n + 10, 0));
  // 区間が短い順に埋める
  for (int len = 1; len <= n; len++) {
    for (int l = 0; l + len <= n; l++) {
      int r = l + len;
      // First
      if (len % 2 == n % 2) {
        dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1]);
      } else { // second
        dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1]);
      }
    }
  }
  cout << dp[0][n] << endl;

  return 0;
}

Measured memory_bytes: 71168
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A1 = list(map(int, sys.stdin.readline().split()))
A2 = list(map(int, sys.stdin.readline().split()))

A1 = np.array(A1)
A2 = np.array(A2)

ans = 0
for i in range(N):
    ans = max(ans, A1[:i+1].sum() + A2[i:].sum())
print(ans)


Measured memory_bytes: 23296
#include<stdio.h>

int main(void){
    char op;
    int a, b, ans;
    
    while(1){
        scanf("%d %c %d", &a, &op, &b);
        
        switch(op){
          case '+':
            ans = a + b;
            break;
          case '-':
            ans = a - b;
            break;
          case '*':
            ans = a * b;
            break;
          case '/':
            ans = a / b;
            break;
        }
        
        if(op == '?') break;
        else printf("%d\n", ans);
    }
    
    return 0;
}

Measured memory_bytes: 600
from subprocess import*
call(('pypy3','-c',"""
n=int(input())
p=list(map(float,input().split()))
dp=[[0]*-~n for _ in range(n)]
dp[0][1]=p[0]
dp[0][0]=1-p[0]
for i in range(1,n):
  dp[i][0]=dp[i-1][0]*(1-p[i])
  for j in range(1,n+1):
    dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][-~n//2:]))
"""))

Measured memory_bytes: 263792
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n;
	cin>>n;
	vint v(n);
	rep(i,n) cin>>v[i];
	sort(ALL(v));
	cout<<v[n-1]-v[0]<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;


int main(){
    int a[5],b[5],min;
    int minf;
    min = 9;
    for(int i = 0; i < 5; i++){
        cin >> a[i];
        for(int j = 0; j < 700; j ++){
            if(a[i] >= j * 10 && a[i] < (j+1)*10){
                b[i] = 10*(j+1);
            }
            }
        }
        int n;
     for(int i = 0; i < 5; i++){
         n = a[i]-b[i]+10;
         if(n == 0) 
         {n = 10;
         b[i]-= 10;}
         if(min >= n){
             min = n;
             minf = i;
         }
     }
    int sum = 0;
    for(int i = 0; i < 5; i++){
        if(i == minf){
            sum += a[i];
             

        }
        else{
            sum += b[i];
             
        }
    }
    cout << sum << "\n";
    
    return 0;
}

Measured memory_bytes: 256
// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N-1);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    for(int i=0;i<N;i++){
        cin >> B[i];
    }
    for(int i=0;i<N-1;i++){
        cin >> C[i];
    }
    int sat = B[A[0]-1];
    for(int i=1;i<N;i++){
        sat += B[A[i]-1];
        if(A[i-1]+1 == A[i]){
            sat += C[A[i-1]-1];
        }
    }  
    cout << sat << endl;
}

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

using namespace std;
using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const ll inf = 1e9+7;
const ll mod = 1e9+7;

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

    int S=(s.size()-2)/2;

    repr(i,S,1){
        if(s.substr(0,i)==s.substr(i,i)){
            cout<<i*2<<endl;
            return 0;
        }
    }



}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long LL;
LL a,b,c,d;

LL gcd(LL x,LL y){
    if(x>y){
        LL t=x;
        x=y;
        y=t;
    }if(x==0) return y;
    return gcd(y%x,x);
}

int main(){
    cin>>a>>b>>c>>d; a--;
    LL l=c*d/gcd(c,d);
    LL A=a,B=b;
    A-=a/c;
    A-=a/d;
    A+=a/l;
    B-=b/c;
    B-=b/d;
    B+=b/l;
    cout<<B-A<<endl;
    return 0;
}

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

const int INF = 1000000000;
int d[110][110];

int main(){
  int n; cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      d[i][j] = INF;
      if(i == j) d[i][j] = 0;
    }
    int u, k; cin >> u >> k;
    for(int j=0; j<k; j++){
      int v, c; cin >> v >> c;
      d[u][v] = c;
    }
  }
  for(int k=0; k<n; k++){
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  for(int i=0; i<n; i++){
    cout << i << " " << d[0][i] << endl;
  }
}


Measured memory_bytes: 3124
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1000000000
using namespace std;


struct edge{int to, cost;};
vector<edge> A[100000];
int d[100000];
typedef pair<int,int> P;

int main(){
  int V,E,R;
  cin >> V >> E >> R;
  for(int i=0;i<E;i++){
    int s,t,d;
    cin >> s >> t >> d;
    edge a;
    a.to=t;
    a.cost=d;
    A[s].push_back(a);
  }
  priority_queue<P, vector<P>, greater<P>> que;
  fill(d,d+V,INF);
  d[R]=0;
  que.push(P(0,R));
  while(!que.empty()){
    P p=que.top();que.pop();
    int v=p.second;
    if(d[v] < p.first)continue;
    for(int i=0;i < A[v].size();i++){
      edge e = A[v][i];
      if(d[e.to] > d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(P(d[e.to],e.to));
      }
    }
  }
  for(int i=0;i<V;i++){
    if(d[i]==INF){
      cout << "INF" << endl;
    }else{
      cout << d[i] << endl;
    }
  }
}

Measured memory_bytes: 13028
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A;
        A = new int[n];
        int Sum, check = 0;
        for(int i = 0; i < n; i++){
            A[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int[] m;
        m = new int[q];
        for(int i = 0; i < q; i++){
            m[i] = sc.nextInt();
        }
        int[] flag;
        flag = new int[n];
        for(int i = 0; i < q; i++){
            for(int j = 0; j < n; j++){
                flag[j] = 0;
            }
            while(true){
                check = 0;
                flag[0]++;
                for(int k = 1; k < n; k++){
                    if(flag[k-1] == 2){
                        flag[k]++;
                        flag[k-1] = 0;
                    }
                }
                if(flag[n-1] == 2){
                    break;
                }
                Sum = 0;
                for(int k = 0; k < n; k++){
                    if(flag[k] == 1){
                        Sum += A[k];
                    }
                }
                if(Sum == m[i]){
                    System.out.println("yes");
                    check = 1;
                    break;
                }
            }
            if(check == 0){
                System.out.println("no");       
            }
        }
    }
}


Measured memory_bytes: 27996
#include <stdio.h>
#include <stdlib.h>
#define N 1000000000
int *S, n;
int binarySearch(int);
int main(){
  int *T;
  int q;
  int i,j,k;
  int cnt = 0;
  int left,right,mid;

  scanf("%d",&n);
  if(n > 100000)
    exit(1);
  S = (int*)malloc(sizeof(int) * n);
  for(i = 0; i < n; i++){
    scanf("%d",&S[i]);
    if(S[i] > N)
      exit(1);
  }

  scanf("%d",&q);
  if(q > 50000)
    exit(2);
  T = (int*)malloc(sizeof(int) * q);
  for(i = 0; i < q; i++){
    scanf("%d",&T[i]);
    if(T[i] > N)
      exit(1);
      for(j = 0; j < i; j++){
	if(T[i] == T[j]){
	  printf("Tは互いに異なる要素を入力してください\n");
	  exit(1);
	}
      }
  }

  for(i = 0; i < q; i++){
    if(binarySearch(T[i]))
      cnt++;
  }

  printf("%d\n",cnt);
  return 0;
}

int binarySearch(int key){
  int left = 0;
  int right = n;
  int mid;
  while(left < right){
    mid = (left + right) / 2;
    if(key == S[mid])
      return 1;
    else if(key < S[mid])
      right = mid;
    else
      left = mid + 1;
  }
  return 0;
}



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

int main()
{
	int n,asum=0,bsum=0;
    cin>>n;
	for(int i=1;i<=n;i++)
	{
		if(i%2==0)
			asum++;
		else
		{
			bsum++;
		}
		
	}
	cout<<asum*bsum<<endl;
	
	
	return 0;
}
	

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=35;
int n,m,k[MAXN];
int a[MAXN][MAXN];
int cnt[MAXN],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&k[i]);
		for(int j=1;j<=k[i];j++){
			scanf("%d",&a[i][j]);
			cnt[a[i][j]]++;
		}
	}
	for(int i=1;i<=m;i++)
		if(cnt[i]==n)ans++;
	printf("%d\n",ans);
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    int c = Integer.parseInt(str[2]);
    System.out.println(a+b>=c?"Yes":"No");
  }
}

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

using namespace std;

int main()
{
    string s;
    cin>>s;
    string t;
    cin>>t;
    int razlicni=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
        {
            razlicni++;
        }
    }
    cout<<razlicni<<endl;
}


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

char f(vector<string> S,int i,int j){
  int num = 0;
  int H = S.size(), W = S.at(0).size();
  if(S.at(i).at(j)=='#'){
    return '#';
  }else{
    if(S.at(i).at(j-(j>0))=='#') num++;
    if(S.at(i).at(j+(j<W-1))=='#') num++;
    if(i>0&&S.at(i-1).at(j)=='#') num++;
    if(i>0&&j>0&&S.at(i-1).at(j-1)=='#') num++;
    if(i>0&&j<(W-1)&&S.at(i-1).at(j+1)=='#') num++;
    if(i<(H-1)&&S.at(i+1).at(j)=='#') num++;
    if(i<(H-1)&&j>0&&S.at(i+1).at(j-1)=='#') num++;
    if(i<(H-1)&&j<(W-1)&&S.at(i+1).at(j+1)=='#') num++;
    char Num = '0'+num;
    return Num;
  }
}
    
int main(){
  int H,W;
  cin >> H >> W;
  vector<string> S(H);
  for(int i=0; i<H; i++){
    cin >> S.at(i);
  }
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cout << f(S,i,j);
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 3604
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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








int main(){
    int N, Z, W; std::cin >> N >> Z >> W;
    std::vector<int> a(N);
    for(int i(0); i < N; ++i) std::cin >> a[i];
    int ans(std::abs(a[N-1] - W));
    if(N > 1) chmax(ans, std::abs(a[N-1] - a[N-2]));
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

int main(){
    int n,ans=1;
    cin >>n ;
    char a[n],tmp;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    tmp=a[0];
    for(int i=0;i<n;i++){
        if(tmp!=a[i]){ans++;tmp=a[i];}
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

#define P 1000000007
#define N_MAX 10000000
ll fac[N_MAX+1], inv[N_MAX+1], finv[N_MAX+1];
ll comb(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (((fac[n]*finv[n-k])%P)*finv[k])%P;
}
void init(){
  fac[0] = finv[0] = fac[1] = finv[1] = inv[1] = 1;
  for(int i = 2; i <= N_MAX; i++){
    fac[i] = (fac[i-1]*i)%P;
    inv[i] = ((-(P/i)*inv[P%i])%P+P)%P;
    finv[i] = (finv[i-1]*inv[i])%P;
  }
}
ll pp(ll a, ll b){
  return (a * b)%P;
}
//-------------------------------------------------------------------
vll dp(3001, 0), num(3001, -1);
vvl G = vv(3001, 0, 0, ll), d;

ll f(ll now){
  if(num[now]!=-1) return num[now];
  ll ret = 0;
  for(int i=0;i<G[now].size();i++){
    ll to = G[now][i];
    ll x = d[now][0] - d[to][0], y = d[now][1] - d[to][1];
    ret = (ret + pp(f(to), comb(x+y, y)))%P;
  }
  return num[now] = (comb(d[now][0]+d[now][1], d[now][0]) - ret + P)%P;
}
int main(int argc, char const *argv[]) {
  ll h, w, n;std::cin >> h >> w >> n;
  init();
  d.resize(n, vll(2, 0));
  re(i, n) {
    scanf("%lld %lld", &d[i][0], &d[i][1]);
    d[i][0]--, d[i][1]--;
  }
  d.push_back(vll{h-1, w-1});
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      if(i==j) continue;
      if(d[i][0]<=d[j][0]&&d[i][1]<=d[j][1]) G[j].push_back(i);
    }
  }
  std::cout << f(n) << '\n';
  return 0;
}


Measured memory_bytes: 283648
N, D = map(int, input().split())
X = [list(map(int,input().split())) for i in range(N)]
ans = 0
for i in range(N):
  for j in range(i+1,N):
    tmp = 0
    for k in range(D):
      tmp += abs(X[i][k]-X[j][k])**2
    tmp = tmp**0.5
    if tmp == int(tmp):
      ans += 1
print(ans)
   


Measured memory_bytes: 3060
import itertools
s = input()
n = len(s) -1
result = 0
comb = list(itertools.product(["+", ""], repeat = n))
for b in comb:
    temp = ""
    for i in range(n):
        temp += s[i] + b[i]
    temp += s[-1]
    result += eval(temp)

print(result)

Measured memory_bytes: 3064
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let s: String = read();
    let c = s.chars().collect::<Vec<char>>();

    if c[0] == c[c.len()-1] {
        println!("Yes")
    } else {
        println!("No")
    }
}


Measured memory_bytes: 4352
import sys


def LI():
    return list(map(int, input().split()))


N, K, S = LI()
if K == 0:
    if S == 10**9:
        for i in range(N):
            print(1, end=" ")
    else:
        for i in range(N):
            print(10**9, end=" ")
    sys.exit()
for i in range(K):
    print(S, end=" ")
if S == 10**9:
    for i in range(N-K):
        print(S-1, end=" ")
else:
    for i in range(N-K):
        print(S+1, end=" ")


Measured memory_bytes: 9272
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

typedef long long ll;

#define MOD 1000000007

class Comb{
private:
  ll *fac,*finv,*inv;
public:
  Comb(){
    fac = new ll[1000000];
    finv = new ll[1000000];
    inv = new ll[1000000];
    fac[0] = 1;
    for(int i=1;i<1000000;i++){
      fac[i] = i*fac[i-1];
      fac[i] %= MOD;
    }
    inv[1] = 1;
    for(int i=2;i<1000000;i++){
      inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
    }
    finv[0] = 1;
    for(int i=1;i<1000000;i++){
      finv[i] = inv[i]*finv[i-1];
      finv[i] %= MOD;
    }
  }
  ll calc(ll n,ll k){
    ll c = fac[n];
    c *= finv[k];c %= MOD;
    c *= finv[n-k];c %= MOD;
    return c;
  }
};

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

int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  ll big = c-a-b;
  if(big <= 0){
    cout << "No" << endl;
  }
  else if(4*a*b < big*big) cout << "Yes"  << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	int X, Y, Z;
	cin >> X >> Y >> Z;
	X -= Z;
	cout << X / (Y + Z) << endl;
}

Measured memory_bytes: 256
using System;
class aoj
{
    static void Main()
    {
        int[] all = new int[20];
        int j = 0;
        while (true)
        {
            int two = 0, five = 0;
            int b = int.Parse(Console.ReadLine());
            if (b==0) break;
            for(int i = 1; i <= b; i++)
            {
                int c = i;
                while (true)
                {
                    if (c % 2 == 0)
                    {
                        two++;
                        c /= 2;
                    }
                    else
                        break;
                }
                while (true)
                {
                    if (c % 5 == 0)
                    {
                        five++;
                        c /= 5;
                    }
                    else
                        break;
                }
            }
                all[j] = five;
                j++;
        }
        for(int k = 0; k < j; k++)
        {
            Console.WriteLine(all[k]);
        }
    }
}

Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int mod=1000000007 ;

void solve(){
	
	
	int n;
	cin>>n ;

	vector<int> v(n) ;

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

	vector<int> temp(n) ;

	temp=v ;

	int mx=v[0] ;

	for(int i=1;i<n;i++){
		if(v[i]<mx){
			v[i]=mx ;
		}

		mx=max(v[i],mx) ;
	}

	ll ans=0 ;
	for(int i=0;i<n;i++){
		ans+=v[i]-temp[i] ;
	}

	cout<<ans ;
}


int main(){


	
	int y ;

	y=1 ;
	//cin>>y ;

	while(y--)
	{	
		solve() ;
	}

}

Measured memory_bytes: 4760
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=500005,MAXM=1000005;

struct Edge
{
	int u,v,c;
	Edge(){}
	bool operator < (const Edge &t)const
	{return c<t.c;}
};

int N,M;
vector<int> adj[MAXN];
void AddEdge(int u,int v)
{
	adj[u].push_back(v);
	adj[v].push_back(u);
	//printf("                          %d<->%d\n",u,v);
}
Edge E[MAXM];

int fa[MAXN];
int id[MAXN];
bool vis[MAXN];
int Root(int x)
{
	if(fa[x]==0)
		return x;
	return fa[x]=Root(fa[x]);
}

int dis[MAXN];
queue<int> Q;
void BFS()
{
	dis[1]=0;
	Q.push(1);
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		for(int i=0;i<(int)adj[u].size();i++)
		{
			int v=adj[u][i];
			if(dis[v]==0x3F3F3F3F)
			{
				dis[v]=dis[u]+1;
				Q.push(v);
			}
		}
	}
}

int main()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
		scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].c);
	sort(E+1,E+M+1);
	
	int last=1,vcnt=N;
	for(int i=2;i<=M+1;i++)
	{
		if(E[i].c!=E[i-1].c)
		{
			for(int j=last;j<i;j++)
				fa[E[j].u]=fa[E[j].v]=id[E[j].u]=id[E[j].v]=vis[E[j].u]=vis[E[j].v]=0;
			for(int j=last;j<i;j++)
			{
				int r1=Root(E[j].u),r2=Root(E[j].v);
				if(r1!=r2)
					fa[r1]=r2;
			}
			for(int j=last;j<i;j++)
			{
				if(fa[E[j].u]==0&&id[E[j].u]==0)
					id[E[j].u]=++vcnt;
				if(fa[E[j].v]==0&&id[E[j].v]==0)
					id[E[j].v]=++vcnt;
			}
			for(int j=last;j<i;j++)
			{
				if(!vis[E[j].u])
				{
					AddEdge(E[j].u,id[Root(E[j].u)]);
					vis[E[j].u]=true;
				}
				if(!vis[E[j].v])
				{
					AddEdge(E[j].v,id[Root(E[j].v)]);
					vis[E[j].v]=true;
				}
			}
			last=i;
		}
	}
	
	memset(dis,0x3F,sizeof dis);
	BFS();
	
	if(dis[N]<0x3F3F3F3F)
		printf("%d\n",dis[N]/2);
	else
		puts("-1");
	
	return 0;
}


Measured memory_bytes: 34176
#include <bits/stdc++.h>
using namespace std;
string s,t,s1;
int main(){
	int a;
  cin>>a>>s>>t;
  s1=s+s;
  for(int k=0;k<a;k++)
  {
  	  s1[k*2]=s[k];s1[k*2+1]=t[k];
  }
  
   cout<<s1;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(m)]

ans = [0 for i in range(n)]
balls = [1 for i in range(n)]
ans[0] = 1

for x, y in xy:
    x -= 1
    y -= 1
    if ans[x] == 1 and balls[x] > 0:
        ans[y] = 1
    if balls[x] > 0:
        balls[x] -= 1
        balls[y] += 1
        if balls[x] == 0:
            ans[x] = 0

print(sum(ans))

Measured memory_bytes: 29000
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

// 抽象セグメント木
template<typename T>
struct SegmentTree {
private:
	int sz, n;
	vector<T> data;
	function<T(T, T)> f;
	T identity_element;
public:
	/* constructor */
	SegmentTree(
		vector<T> v, // initial data
		T identity_element, // identity element
		function<T(T, T)> f // operation
	) {
		sz = v.size();
		n = 1; while (n < sz) n <<= 1;
		this->f = f;
		this->identity_element = identity_element;
		data.resize(2 * n - 1, identity_element);
		for (int i = 0; i < sz; ++i)
			data[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; --i)
			data[i] = f(data[2 * i + 1], data[2 * i + 2]);
	}
	/* update query */
	void update(int idx, const T val) {
		idx += n - 1;
		data[idx] = val;
		while (idx) {
			idx = (idx - 1) >> 1;
			data[idx] = f(data[2 * idx + 1], data[2 * idx + 2]);
		}
	}
	/* get query */
	T get(int left, int right, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (r <= left || right <= l) return identity_element;
		if (left <= l && r <= right) return data[k];
		T val_l = get(left, right, 2 * k + 1, l, (l + r) / 2);
		T val_r = get(left, right, 2 * k + 2, (l + r) / 2, r);
		return f(val_l, val_r);
	}
};

ll count_pair(vector<int>& a) {
	int sz = a.size();
	SegmentTree<ll> seg(
		vector<ll>(2 * sz + 1, 0), 0, [&](ll a, ll b) { return a + b; }
	);
	ll res = 0;
	for (int i = 0; i < sz; ++i) {
		res += seg.get(0, a[i] + sz);
		seg.update(a[i] + sz, seg.get(a[i] + sz, a[i] + sz + 1) + 1);
	}
	return res;
}

int N;
vector<int> a;

void input() {
	cin >> N;
	a.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> a[i];
}

// k以下が半分より多くある数列の個数
ll count(int k) {
	vector<int> _a(N + 1, 0);
	for (int i = 1; i <= N; ++i)
		_a[i] = a[i - 1] <= k ? 1 : -1;
	for (int i = 1; i <= N; ++i)
		_a[i] += _a[i - 1];
	return count_pair(_a);
}

signed main() {
	input();
	ll border = (ll)N * (N + 1LL) / 2 / 2 + 1LL;
	int ng = 0, ok = 1000000000;
	while (ok - ng > 1) {
		int mid = ng + (ok - ng) / 2;
		if (count(mid) >= border) ok = mid;
		else ng = mid;
	}
	cout << ok << endl;
	return 0;
}

Measured memory_bytes: 8604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int N;
    cin >> N;
    string moji = "ACL";
    string ans = "";

    rep(i,N){
        ans += moji;
    }
    cout << ans;
}

Measured memory_bytes: 3572
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<P> VP;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,n,0)

#define LFOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RLFOR(i,b,a) for(ll i=(b)-1;i>=(a);--i)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_back
#define EACH(i,c) REP(i,(int)(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define dump(x) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define dump2(x,y) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x)\
			<< " , " << #y << " = " << (y) << "\n";

const int INF = 1e9;
const double EPS = 1e-10;

int n,a,b;
ll ans;
int main() {
	cin >> n >> a >> b;
	int last;
	cin >> last;
	REP(i, n - 1){
		int x;
		cin >> x;
		if(x - last > b/a) ans += b;
		else ans += ll(x - last) * a;
		last = x;
	}
	cout << ans << endl;
}


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

using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;

#define out(a) cout << a << endl
#define out1(a) cout << a
#define in(a) cin >> a
#define in2(a, b) cin >> a >> b
#define in3(a, b, c) cin >> a >> b >> c
#define rep(i, N) for (ll i = 0; i < (ll)N; i++)
#define rep1(i, N) for (ll i = 1; i <= (ll)N; i++)
#define repi(i, j, N) for (ll j = (ll)i + 1; j < (ll)N; j++)
#define all(v) v.begin(), v.end()

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

constexpr int inf = 1e9;
constexpr ll linf = 1e18;
constexpr ll mod = 1e9 + 7;

void solve();

int main()
{
    solve();
}

void solve()
{
    int n, m;
    in2(n, m);
    int s[m], c[m];
    rep(i, m) in2(s[i], c[i]);
    int a[n];
    rep(i, n) a[i] = 0;
    int flag = 0;
    int count[3];
    rep(i, 3) count[i] = 0;
    rep(i, m)
    {
        if (a[s[i] - 1] == 0)
        {
            if (count[s[i] - 1] != 0 && c[i] != 0)
            {
                flag = -1;
            }
            a[s[i] - 1] = c[i];
            if (c[i] == 0)
            {
                count[s[i] - 1] = 1;
            }
        }
        else
        {
            if (a[s[i] - 1] != c[i])
            {
                flag = -1;
            }
        }
    }
    if (flag == 0)
    {
        if (n == 1)
        {
            out(a[0]);
        }
        else
        {
            if (a[0] == 0 && count[0] == 1)
            {
                out("-1");
            }
            else if (a[0] == 0 && count[0] == 0)
            {
                a[0] = 1;
                rep(i, n)
                {
                    cout << a[i];
                }
                cout << endl;
            }
            else
            {
                rep(i, n)
                {
                    cout << a[i];
                }
                cout << endl;
            }
        }
    }
    else
    {
        out(flag);
    }
}

Measured memory_bytes: 256
// AOJ NTL_1_B
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B

#include <iostream>

namespace cplib {
    template <typename T, typename U>
    T pow(T m, U n) {
        T res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res *= m;
            }
            m *= m;
            n /= 2;
        }
        return res;
    }
    
    template <int64_t mod>
    class ModInt {
        public:
        int64_t val;

        ModInt(): val(0) {}
        ModInt(int64_t init_val): val(
            init_val >= 0? init_val % mod: mod - (-init_val) % mod
        ) {}

        bool operator !() {return val != 0;}
        ModInt operator -() {return ModInt(-val);}
        bool operator ==(ModInt rhs) {return val == rhs.val;}
        bool operator !=(ModInt rhs) {return val != rhs.val;}

        ModInt& operator ++() {
            val++;
            if (val == mod) val = 0;
            return *this;
        }
        ModInt operator ++(int) {
            ModInt res = *this;
            val++;
            if (val == mod) val = 0;
            return res;
        }
        ModInt& operator --() {
            if (val == 0) val = mod;
            val--;
            return *this;
        }
        ModInt operator --(int) {
            ModInt res = *this;
            if (val == 0) val = mod;
            val--;
            return res;
        }

        ModInt& operator +=(ModInt rhs) {
            val += rhs.val;
            if (val >= mod) val -= mod;
            return *this;
        }
        ModInt& operator -=(ModInt rhs) {
            val -= rhs.val;
            if (val < 0) val += mod;
            return *this;
        }
        ModInt& operator *=(ModInt rhs) {
            val = (val * rhs.val) % mod;
            return *this;
        }
        ModInt& operator /=(ModInt rhs) {
            int64_t base = rhs.val, res = 1, pow = mod - 2;
            while (pow > 0) {
                if (pow % 2 == 1) res = (res * base) % mod;
                base = (base * base) % mod;
                pow /= 2;
            }
            val = (val * res) % mod;
            return *this;
        }

        ModInt operator +(ModInt rhs) {return ModInt(*this) += rhs;}
        ModInt operator -(ModInt rhs) {return ModInt(*this) -= rhs;}
        ModInt operator *(ModInt rhs) {return ModInt(*this) *= rhs;}
        ModInt operator /(ModInt rhs) {return ModInt(*this) /= rhs;}

        friend std::istream& operator >>(std::istream& is, ModInt& target) {
            int64_t init_val;
            is >> init_val;
            target = ModInt(init_val);
            return is;
        }
        friend std::ostream& operator <<(std::ostream& os, ModInt source) {
            os << source.val;
            return os;
        }
    };
}

int main() {
    using mint = cplib::ModInt<1000000007>;

    mint m;
    int64_t n;
    std::cin >> m >> n;

    std::cout << cplib::pow(m, n) << std::endl;
    return 0;
}



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


#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,n,m) for (int i=n; i<(int)(m); i++)
#define INF 1000000007
#define mp make_pair

typedef long long ll;
typedef long double ld;
ll dy[4]={-1,1,0,0};
ll dx[4]={0,0,1,-1};

/*---------- template ----------*/
int H,W;
char field[1010][1010];
int around_zero_num[1010][1010];

int main(){
    cin >> H >> W;
    REP(i,H){
        cin >> field[i];
    }
    queue<pair<int,int> > que;
    REP(i,H){
        REP(j,W){
            FOR(k,i-1,i+2){
                FOR(l,j-1,j+2){
                    if(i==k&&j==l) continue;
                    if(k<0||l<0||H<=k||W<=l) around_zero_num[i][j]++;
                    else if(field[k][l]=='.') around_zero_num[i][j]++;
                }
            }
        }
    }
    
    //?£??????????
    REP(i,H){
        REP(j,W){
            if(field[i][j]!='.'&&int(field[i][j]-'0')<=around_zero_num[i][j]){
                que.push(mp(i,j));
            }
        }
    }
    
    int ans=0;
    while(que.size()!=0){
//        cout << endl;
//        REP(i,H) cout << field[i] << endl;
//        
//        cout << endl;
//        REP(i,H){REP(j,W){
//            cout << around_zero_num[i][j];
//        }cout<<endl;}
        
        //?£??????????
        vector<pair<int,int> > broke;
        while(que.size()!=0){
            auto x = que.front();
            que.pop();
            if(field[x.first][x.second]!='.'&&int(field[x.first][x.second]-'0')<=around_zero_num[x.first][x.second]){
                broke.push_back(x);
            }
        }
        set<pair<int,int> > se;
        if(broke.size()!=0) ans++;
        //?£???????????????????
        for(auto x: broke){
            field[x.first][x.second]='.';
            FOR(i,x.first-1,x.first+2){
                FOR(j,x.second-1,x.second+2){
                    if(i==x.first&&j==x.second) continue;
                    if(i<0||j<0||H<=i||W<=j) continue;
                    if(field[i][j]=='.') continue;
                    se.insert(mp(i,j));//?¬??¢???????????????????
                    around_zero_num[i][j]++;
                }
            }
        }
        for(auto x: se) que.push(x);
    }
//    cout << endl;
//    REP(i,H) cout << field[i] << endl;
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8116