akhauriyash/Code-Regression huggingface dataset:
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <map>
#include <stdio.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll mod = 1000000007;
pint dx[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};

ll min(ll a, ll b){
	if (a < b)
		return a;


		return b;
}

ll max(ll a, ll b) {
	if (a < b)
		return b;
	
	return a;
}



ll N, K;


string S;
ll sumdot[200005];
ll sumsh[200005];
int main() {
	cin >> N >> S;

	rep(i, N) {
		if (i == 0 && S[i] == '.') {
			sumdot[0] = 1;

		}
		else if(i == 0 && S[i] == '#') {
			sumsh[0] = 1;
		}

		if (S[i] == '.' && i != 0) {
			sumdot[i] = sumdot[i-1] + 1;
			sumsh[i] = sumsh[i - 1];
		}
		else if(S[i] == '#' && i != 0) {
			sumsh[i] = sumsh[i-1] +  1;
			sumdot[i] = sumdot[i - 1];
		}

	}
	ll ans = 0, dotnum = 0, shnum = 0;


	ans = inf;
	for (int i = 0; i < N; i++) {

		
			ans = min(sumsh[i] + sumdot[N - 1] - sumdot[i], ans);
			ans = min(sumdot[i] + sumdot[N - 1] - sumdot[i], ans);
	}
	
	if (N == 1) {

		cout << 0 << endl;
		return 0;
	}
	
	if (sumsh[N-1] == N) {
		cout << 0 << endl;
		return 0;
	}

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

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

int main(){
    string S;
    cin >> S;
    
    for(int i = 1; i <= S.size(); i++){
        if(S[i] == S[i-1]) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;



public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] array = new int[6 + 1];
		array[0] = 0;
		for (int i = 1; i < array.length; i++) {
			array[i] = scan.nextInt();
		}
		String order = scan.next();
		scan.close();
		Dice dice = new Dice(array);
		array = dice.roll(order);
		System.out.println(array[1]);
	}
}
	

class Dice {
	int[] num = new int[6 + 1];
	Dice() {
	}

	Dice(int[] array) {
		for (int i = 0; i < array.length; i++) {
			this.num[i] = array[i];
		}
	}
	
	public int[] getNum() {
		return this.num;
	}
	
	public int getNumber(int i) {
		return this.num[i];
	}
	
	// ??????????????¢??????????????????
	public int[] roll(String order) {
		int now_1 = 1;	int now_2 = 2;	int now_3 = 3;	int tmp;
		int[] array = getNum();
		char[] check = {'N', 'E', 'S', 'W'};
		for (int i = 0; i < order.length(); i++) {
			for (int j = 0; j < check.length; j++) {
				if (order.charAt(i) == check[j]) {
					switch (j + 1) {
						case 1:
							tmp = now_1;
							now_1 = now_2;
							now_2 = 7 - tmp;
							break;
						case 2:
							tmp = now_1;
							now_1 = 7 - now_3;
							now_3 = tmp;
							break;
						case 3:
							tmp = now_1;
							now_1 = 7 - now_2;
							now_2 = tmp;
							break;
						case 4:
							tmp = now_1;
							now_1 = now_3;
							now_3 = 7 - tmp;
							break;
					}
				}
			}
		}
		int[] cp_array = new int[array.length];
		cp_array[1] = array[now_1]; cp_array[2] = array[now_2];
		cp_array[3] = array[now_3]; cp_array[4] = array[7 - now_3];
		cp_array[5] = array[7 - now_2]; cp_array[6] = array[7 -now_1];
		return cp_array;
	}
	
	public void print(int[] array) {
		for (int i = 1; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
}

Measured memory_bytes: 26200
/**
 * Created by karayuu on 2018/12/08
 */
fun main(args: Array<String>) {
    val count = readLine()!!.toInt()
    val items = mutableListOf<Int>()
    (1..count).forEach {
        val s = readLine()!!.toInt()
        items.add(s)
    }

    val max = items.max()!!
    val sum = items.sum()

    println(sum - max + max / 2)
}


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

using namespace std;

int n;
string ps[200];
int used[200];

int solve2(int p)
{
    vector<vector<int> > v;
    v.push_back(vector<int>());
    v[0].push_back(p);
    memset(used,-1,sizeof(used));
    used[p] = 0;
    int s = 1;
    for(int k = 1; s < n; k++)
    {
        v.push_back(vector<int>());
        for(int j = 0; j < v[k-1].size(); j++)
        {
            p = v[k-1][j];
            for(int i = 0; i < n; i++)
            {
                if(ps[p][i] == '1')
                {
                    if(used[i] == -1)
                    {
                        v[k].push_back(i);
                        used[i] = k;
                        s++;
                    }
                }
            }
        }
    }
    for(int i = 0;i < v.size();i++){
        for(int j = 0;j < v[i].size();j++){
            for(int k = 0;k < n;k++){
                if(ps[v[i][j]][k] == '1'){
                    if(used[k] != used[v[i][j]]-1 && used[k] != used[v[i][j]]+1) return -1;
                }
            }
        }
    }
    return v.size();
}

void solve()
{
    int i,j;
    string str;
    cin >> n;
    for(i = 0; i < n; i++)
        cin >> ps[i];
    long long ans = -1;
    for(i = 0; i < n; i++)
    {
        j = solve2(i);
        if(j > ans)
            ans = j;
    }
    cout << ans << endl;
}

int main()
{
    solve();
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
#include <utility>
#include <cstring>
#include <numeric>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define repll(i,n) for(long long int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
template <typename T_char>
char ToUpper (char cX) { return toupper(cX); }
//g++ -std=c++1z temp.cpp
//./a.exe
ll digit(ll a){
    ll count = 0;
    for (ll i = 0; i < a; i++)
    {   if (a == 0)
        {
            break;
        }else
        {
            a = a/10;
            count++;
        }
    }
    return count;
}
//桁数のカウント
//pow(x,n) == x^n
//sum = accumulate(v.begin(),v.end(),0);
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a,   b) * b;}



int main(void){ios::sync_with_stdio(false);cin.tie(0);
/////////////////////////////////////////////////////
ll n,m,sum = 0;
cin >> n >> m;
vector<pair<ll,ll> > pairs(n);
rep(i,n) cin >> pairs[i].first >> pairs[i].second;

Sort(pairs);

rep(i,n){
    if(pairs[i].second <= m){
        sum += pairs[i].first * pairs[i].second;
        m = m - pairs[i].second;
    }else{
        sum += pairs[i].first * m;
        break;
    }
}
cout << sum << endl;


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 1792
N, M = map(int, input().split())
list_Connect=[]
for i in range(M):
    A = list(map(int, input().split()))
    A.pop(0)
    list_Connect.append( A )

list_p = list(map(int, input().split()))

i = 0



state = []#スイッチ点灯の全組み合わせを入れる
sum=0

def func(i):
    global sum
    if i == N:
        flag = True
        for i in range(M):
            cnt= 0
            for j in list_Connect[i]:
                cnt += state[j-1]
            if cnt %2 != list_p[i]:
                flag = False
                break
        if flag == True:
           sum+=1
    else:
        state.append(1)
        func(i+1)
        state.pop(-1)
        state.append(0)
        func(i+1)
        state.pop(-1)

    return


func(0)
print (sum)

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  string s;
  cin>>s;
  map<char,int>m;
  for(auto it:s)m[it]++;
  bool ok=true;
  for(auto it:m)if(it.second!=2)ok=false;
  if(ok)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
from bisect import bisect_left

n = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += bisect_left(L, L[i] + L[j]) - j - 1

print(ans)


Measured memory_bytes: 3188
n = gets.to_i
abc = []
n.times do |i|
  a, b, c = gets.split(' ').map(&:to_i)
  abc << { a: a, b: b, c: c }
end
dp = [
  { a: 0, b: 0, c: 0 }
]

0.upto(n-1) do |i|
  a = [dp[i][:b] + abc[i][:a], dp[i][:c] + abc[i][:a]].max
  b = [dp[i][:a] + abc[i][:b], dp[i][:c] + abc[i][:b]].max
  c = [dp[i][:a] + abc[i][:c], dp[i][:b] + abc[i][:c]].max
  dp[i+1] = { a: a, b: b, c: c }
end

puts [dp[n][:a], dp[n][:b], dp[n][:c]].max


Measured memory_bytes: 59772
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int N,A,B;
    cin >> N >> A >> B;
    if((abs(A-B)-1)%2)cout << "Alice" << endl;
    else cout << "Borys" << endl;
    return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())
# x→yの順に処理していけば良い。
iki_x = tx - sx
iki_y = ty - sy
ans = ""
ans += "R" * iki_x
ans += "U" * iki_y
ans += "L" * iki_x
ans += "D" * iki_y
ans += "D"
ans += "R" * (iki_x + 1)
ans += "U" * (iki_y + 1)
ans += "L"
ans += "U"
ans += "L" * (iki_x + 1)
ans += "D" * (iki_y + 1)
ans += "R"
print(ans)


Measured memory_bytes: 38256
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    s.add(arr[i])
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  ans+=1
print(ans)

Measured memory_bytes: 219808
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

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

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

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

  sort(v, v + n);

  double ans = v[0];
  for(int i = 1; i < n; i++){
    ans = (ans + v[i]) / 2.0;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template <class T = int>
using V = vector<T>;
template <class T = int>
using VV = V<V<T>>;

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  lint m;
  cin >> m;
  V<lint> l(n), r(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> l[i] >> r[i];
  }
  auto vl = l, vr = r;
  auto v = l;
  v.insert(end(v), begin(r), end(r));
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
  for (auto &&e : l)
  {
    e = lower_bound(begin(v), end(v), e) - begin(v);
  }
  for (auto &&e : r)
  {
    e = lower_bound(begin(v), end(v), e) - begin(v);
  }
  for (auto &&e : vl)
  {
    e = lower_bound(begin(v), end(v), e) - begin(v);
  }
  for (auto &&e : vr)
  {
    e = lower_bound(begin(v), end(v), e) - begin(v);
  }
  sort(begin(vl), end(vl));
  sort(begin(vr), end(vr));

  map<int, int> mp;
  for (int i = 0; i < n; ++i)
  {
    mp[l[i]] = max<lint>(mp[l[i]], r[i]);
  }

  m = v.size() - 1;
  // cerr << m << endl;
  int x = 0, p = 0;
  auto itr = begin(mp);
  while (p < m)
  {
    int np = p;
    while (itr != end(mp) and itr->first <= p)
    {
      np = max(np, itr->second);
      ++itr;
    }
    p = np;
    // cerr << np << endl;
    ++x;
  }
  int y = 0;
  for (int i = 0; i < m; ++i)
  {
    int z = upper_bound(begin(vr), end(vr), i) - begin(vr);
    z += end(vl) - lower_bound(begin(vl), end(vl), i + 1);
    y = max(y, z);
    // cerr << i << ' ' << z << endl;
  }
  cout << x << ' ' << y + 1 << '\n';
}


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

int main() {
    ll n, a, b, i;
    cin >> n >> a >> b;

    if (abs(a-b) % 2 == 0) {
        i = abs(a-b) / 2;
    } else {
        ll d = min((a-1)+(b-1), (n-a)+(n-b));
        i = (d + 1) / 2;
    }
    cout << i << endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

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

		int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
		in.close();
		Set<Three> set = new HashSet<>();
		long ans = 0;

		while(true) {
			Three t = new Three(a, b, c);
			if(set.contains(t)) {
				System.out.println(-1);
				return;
			} else {
				set.add(t);
			}
			if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1) break;
			++ans;
			int a2 = a / 2, b2 = b / 2, c2 = c / 2;

			a = b2 + c2;
			b = a2 + c2;
			c = a2 + b2;
		}
		System.out.println(ans);
	}
}

class Three {
	int a, b, c;
	public Three(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + a;
		result = prime * result + b;
		result = prime * result + c;
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Three other = (Three) obj;
		if (a != other.a)
			return false;
		if (b != other.b)
			return false;
		if (c != other.c)
			return false;
		return true;
	}


}

Measured memory_bytes: 21844
#include <cstdio>

char s[2][4];

int main(){
	scanf("%s %s", s[0], s[1]);
	if(s[0][0] == s[1][2] && s[0][1] == s[1][1] && s[0][2] == s[1][0])
		printf("YES\n");
	else printf("NO\n");
}

Measured memory_bytes: 128
n = int(input())
m1, m2, m4 = 0, 0, 0

for a in input().split():
    x = int(a)
    if x % 2 == 0:
        if x % 4 == 0: m4 += 1
        else: m2 += 1
    else: m1 += 1

ans = m4 >= m1 if(m2) else m4 + 1 >= m1
print("Yes" if ans else "No")

Measured memory_bytes: 11480
N=gets.to_i
i=1
def contain?(n)
 if(n==0)
  return false
 elsif(n%10==3)
  return true
 else
  contain?(n/10)
end
end
while(i<=N)
 if(i%3==0||contain?(i))
  print" #{i}"
 end
 i=i+1
end
print"\n"



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

using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

ll cy(ll X, ll M) {
    vector<int> check(M, 0);
    ll ans = 0;
    while(check.at(X) == 0) {
        //cout << X << endl;
        check.at(X)++;
        X = (X*X)%M;
    }
    while(check.at(X) == 1) {
        check.at(X)++;
        X = (X*X)%M;
        ans++;
    }

    return ans;
}

ll stx(ll X, ll M) {
    vector<int> check(M, 0);
    ll ans = 0;
    while(check.at(X) == 0) {
        //cout << X << endl;
        check.at(X)++;
        X = (X*X)%M;
    }
    while(check.at(X) == 1) {
        check.at(X)++;
        X = (X*X)%M;
        ans++;
    }

    return X;
}

ll cyzero(ll X, ll M) {
    vector<int> check(M, 0);
    ll ans = 0;
    while(check.at(X) == 0) {
        //cout << X << endl;
        check.at(X)++;
        X = (X*X)%M;
        ans++;
    }

    return ans;
}

bool zeroc(ll N, ll X, ll M) {
    vector<int> check(M, 0);
    ll ans = 0;
    for(int i = 0; i < N && check.at(X) == 0; i++) {
        check.at(X)++;
        X = (X*X)%M;
        ans++;
        if(X == 0) {
            return 1;
        }
    }

    return 0;
}

ll sum(ll N, ll X, ll M) {
    vector<int> check(M, 0);
    ll ans = 0;
    for(int i = 0; i < N; i++) {
        //cout << X << endl;
        ans += X;
        X = (X*X)%M;
    }

    return ans;
}

int main() {
    ll N, X, M;
    cin >> N >> X >> M;
    if(zeroc(N, X, M)) {
        cout << sum(M, X, M) << endl;
        return 0;
    }
    ll ans;
    ll rt = cy(X, M);//通常の周期
    ll atama = cyzero(X, M) - rt;//最初何回？
    ll latekai = (N - atama)%rt;//最後何回？
    ll stX = stx(X, M);
    //cout << rt << ':' << atama << ':' << latekai << endl;
    if(rt > N) {
        cout << sum(N, X, M) << endl;
        return 0;
    }
    ans = sum(rt, stX, M)*((N - atama)/rt) + sum(atama, X, M) + sum(latekai, stX, M);

    cout << ans << endl;


    
    

    return 0;
}

Measured memory_bytes: 3992
// '#'のマスに上下左右で隣接するマスがいずれも'.'であるようなマスが存在すると失敗する
#include<iostream>
using namespace std;
const int MAX = 50;
int main(){
  char M[MAX][MAX];
  int dx[4] = {1,0,-1,0};
  int dy[4] = {0,1,0,-1};
  int H,W; cin >> H >> W;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++) cin >> M[i][j];
  }
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(M[i][j]=='.') continue;
      
      int count = 0;
      for(int t=0;t<4;t++){
        if(i+dy[t]<0 || i+dy[t]>=H || j+dx[t]<0 || j+dx[t]>=W) continue;
        if(M[i+dy[t]][j+dx[t]]=='#') count++;
      }
      if(count==0){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int tmp = 0;
		for(int i = 1; i<10; i++) {
			if(num%i==0) {
				int other = num/i;
				if(other<=9) {
					tmp = 1;
					System.out.println("Yes");
					break;
				}
			}
		}
		
		if(tmp == 0)
			System.out.println("No");
	}
}


Measured memory_bytes: 24020
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

string s, t;

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

Measured memory_bytes: 3572
#include <stdio.h>
int main(void) 
{
	int a, b, c, x, count = 0;
	scanf("%d %d %d", &a, &b, &c);
	for (x = a; x <= b; x++) {
		if (c % x == 0) {
			count++;
		}
	}
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
	int n,a,b,ans=0;
	cin>>n>>a>>b;
	vector<int>x(n);
	for(int i=0;i<n;i++){
		cin>>x[i];
	}
	for(int i=1;i<n;i++){
		ans+=min(b,(x[i]-x[i-1])*a);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#line 1 "template.cpp"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  string s;
  cin >> s;
  int q;
  cin >> q;
  bool isRev = false;
  vector<char> front, back;
  REP(i, q) {
    int com;
    cin >> com;
    if (com == 1) {
      isRev = !isRev;
    } else {
      int f;
      char c;
      cin >> f >> c;
      if (!isRev) {
        if (f == 1) {
          front.push_back(c);
        } else {
          back.push_back(c);
        }
      } else {
        if (f == 2) {
          front.push_back(c);
        } else {
          back.push_back(c);
        }
      }
    }
  }
  if (isRev) {
    REP(i, (int)back.size()) { cout << back[back.size() - i - 1]; }
    reverse(s.begin(), s.end());
    cout << s;
    REP(i, (int)front.size()) { cout << front[i]; }
  } else {
    REP(i, (int)front.size()) { cout << front[front.size() - i - 1]; }
    cout << s;
    REP(i, (int)back.size()) { cout << back[i]; }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

int main() {
	ll x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	priority_queue<P, vector<P>, greater<P>> q;
	priority_queue<ll> p;
	ll ans = 0;
	vector<ll> aa(a), bb(b), cc(c);
	REP(i, a) cin >> aa[i];
	REP(i, b) cin >> bb[i];
	REP(i, c) cin >> cc[i];
	sort(ALL(aa), greater<ll>());
	sort(ALL(bb), greater<ll>());
	REP(i, x) {
		q.push(P(aa[i], 0));
		ans += aa[i];
	}
	REP(i, y) {
		q.push(P(bb[i], 1));
		ans += bb[i];
	}
	REP(i, c) {
		p.push(cc[i]);
	}
	while (!p.empty()) {
		if (q.top().first >= p.top())break;
		P now = q.top();
		q.pop();
		ans -= now.first;
		q.push(P(p.top(), now.second));
		ans += p.top();
		p.pop();
	}
	cout << ans << endl;
}


Measured memory_bytes: 8432
{-# OPTIONS_GHC -Odph #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE NumDecimals #-}
module Main (main) where
import Control.Applicative
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BS
import Data.Function (fix)
import Data.Maybe (fromJust)
import Data.Vector ((!),Vector())
import qualified Data.Vector as V
import Debug.Trace (traceId)
import Debug.Trace (traceShowId)
import System.IO (hFlush)
import System.IO (stdout)
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Mutable as MV
import qualified Control.Monad.ST as ST
import qualified Debug.Trace as Log
import qualified Data.Vector.Generic as GV

getInt :: IO Int
getInt = fst . fromJust . BS.readInt <$> BS.getLine


main :: IO ()
main = do
  let !t1 = V.force $ dpTable 1e6
      !t2 = V.force $ dpTableOdd 1e6
  -- print fs
  fix $ \continue -> do
    x <- getInt
    if (x == 0)
      then return ()
      else do
      putStrLn $ show (t1 V.! x) ++ ' ':show (t2 V.! x)
      hFlush stdout
      continue

f :: Int -> Int
f !n = (n * (n+1) * (n+2)) `div` 6

fs :: Vector Int
fs = V.map f $ V.enumFromTo 1 200

fsOdd :: Vector Int
fsOdd = V.filter odd $ fs

dpTable :: Int -> V.Vector Int
-- dpTable n | traceShow n False = undefined
dpTable n = constructN'' n ge
  where
    ge :: V.Vector Int -> Int
    ge !v
      | k == 0 = 0
      | otherwise       = 1 + V.foldl' (\l r -> min l $!g r) maxBound fs
      where
        k = V.length v
        g !fi
          | k - fi >= 0 = v V.! (k - fi)
          | otherwise   = maxBound

-- constructN' :: Int -> (V.Vector a -> a) -> V.Vector a
-- constructN' !n fun = ST.runST $ do
--     v  <- MV.new n
--     flip fix 0 $ \loop !len -> do
--       if len == n
--         then V.freeze v
--         else do
--         v' <- V.unsafeFreeze v
--         let !x = fun (V.unsafeTake len v')
--         x `seq` MV.write v len x
--         GV.elemseq v' x $ loop (len+1)

constructN'' :: Int -> (V.Vector a -> a) -> V.Vector a
constructN'' !n fun = ST.runST $ do
    v  <- MV.new n
    v' <- V.unsafeFreeze v
    flip fix 0 $ \loop !len -> do
      if len == n
        then return v'
        else do
        let v'' = V.unsafeTake len v'
            !x = fun v''
        GV.elemseq v'' x $ MV.write v len x
        loop (len+1)
    
dpTableOdd :: Int -> V.Vector Int
dpTableOdd n = constructN'' n ge
  where
    ge !v
      | V.length v == 0 = 0
      | otherwise       = 1 + V.foldl' (\l r -> min l (g r)) maxBound fsOdd -- [ v V.! (k - fi) | fi <- fs, k - fi >= 0]
      where
        k = V.length v
        g fi
          | k - fi >= 0 = v V.! (k - fi)
          | otherwise   = maxBound
       
       

Measured memory_bytes: 27304
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
bool hoge(vector<vector<char>> s,int a,int b){
    for(int i = 1;i<=a;i++){
        for(int j = 1;j<=b;j++){
            if(s[i][j]=='#'&&s[i+1][j] == '.'&&s[i-1][j] == '.'&&s[i][j+1] == '.'&&s[i][j-1] == '.') return false;
        }
    }
    return true;
}
int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char>> s;
    vector<char> ss;
    for(int i = 0;i<w+2;i++){
        ss.push_back('.');
    }
    for(int i = 0;i<h+2;i++){
        s.push_back(ss);
    }
    for(int i = 1;i<=h;i++){
        for(int j = 1;j<=w;j++){
            cin >> s[i][j];
        }
    }
    if(hoge(s,h,w)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import operator 
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(m)]
C = [[sum(map(operator.mul, tuple(A[i]), list(zip(*B))[j])) for j in range(l) ] for i in range(n) ]
print ('\n'.join([' '.join(map(str,i)) for i in C]))


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

using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(vr) vr.begin(),vr.end()

typedef long long ll;
namespace myrand
{
    mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
    ll Int(ll l,ll r) { return uniform_int_distribution<ll> (l,r)(mt); }
}
using namespace myrand;
auto ss=chrono::system_clock::now();
double remain_time()
{
    auto en=chrono::system_clock::now();
    return (chrono::duration_cast<chrono::nanoseconds>(en-ss).count()*1e-9);
}
string s,t;
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin >> s >> t;
   cout << t + s;
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int d; cin >> d;
  cout << "Christmas";
  rep(i, 25-d) cout << " Eve";
  cout << endk;
  return 0;
}


Measured memory_bytes: 3540
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <sstream>
typedef long long ll;
using namespace std;
 
int main(int argc, char const *argv[])
{
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    int x = c-a;
    int y = d-b;
    printf("%d %d %d %d\n", c-y, d+x, a-y, b+x);
    return 0;
}

Measured memory_bytes: 256
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define df 0
#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
typedef long int li;

void make_parents(int a,vector<int>& par,const vector<vector<int>>& adj){
  for(int v:adj.at(a)){
    if(par.at(a)==v)continue;
    par.at(v)=a;
    make_parents(v,par,adj);
  }
}

void color(int a,const vector<int>& par,const vector<vector<int>>& adj,
	   const map<pair<int,int>,int>& dict,vector<int>& col){
  int c=-1;
  if(a!=0){
    int x=a,y=par.at(a);if(x>y)swap(x,y);
    c=col.at(dict.at(make_pair(x,y)));
  }
  int i=1;
  for(int v: adj.at(a)){
    if(v==par.at(a))continue;
    if(i==c)i++;
    int x=a,y=v;if(x>y)swap(x,y);
    col.at(dict.at(make_pair(x,y)))=i;
    color(v,par,adj,dict,col);
    i++;
  }
}


int main(){
  if(df) printf("*debug mode*\n");
  map<pair<int,int>,int> dict;
  int n; cin >>n;
  vector<vector<int>> adj(n);
  rep(i,n-1){
    int a,b; cin >>a >>b; a--; b--;if(a>b)swap(a,b);
    dict[make_pair(a,b)]=i;
    adj.at(a).push_back(b);
    adj.at(b).push_back(a);
  }
  int m=0;
  rep(i,n) if(m<adj.at(i).size()) m=adj.at(i).size();
  cout << m;
  vector<int> par(n),col(n-1);
  
  make_parents(0,par,adj);
  color(0,par,adj,dict,col);
  rep(i,n-1){
    printf("\n%d",col.at(i));
  }
}

/// confirm df==0 ///


Measured memory_bytes: 14080
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	string s; cin >> s;
	int ans = 700;
	if(s[0] == 'o') ans += 100;
	if(s[1] == 'o') ans += 100;
	if(s[2] == 'o') ans += 100;

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	
    	int a = sc.nextInt(), b = sc.nextInt(), h = sc.nextInt();
    	
    	System.out.println((a + b) * h / 2);
    }
}

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> L(N);
  for (int i = 0; i < N; i++) {
    cin >> L[i];
  }

  int D = 0;
  int ans = 1;

  for (int i = 0; i < N; i++) {
    if (D + L[i] <= X) {
      ans += 1;
      D += L[i];
    } else {
      break;
    }
  }

  cout << ans << endl;
};


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define x first
#define y second
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_
#define tm dolor_sit_amet_
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 300;
const int P = 998244353;
char s[mxN+3]; int a[mxN+3];
llong f[mxN+3][mxN+3][mxN+3],g1[mxN+3][mxN+3][mxN+3],g2[mxN+3][mxN+3][mxN+3];
int n,m,lim;

void updsum(llong &x,llong y) {x+=y-P,x+=(x>>31)&P;}

int main()
{
	scanf("%s",s+1); lim = read(); n = strlen(s+1); m = 0;
	for(int i=1; i<=n; i++)
	{
		if(s[i]=='1') {a[m+1]++;}
		else {m++;}
	}
	lim = min(lim,n-m);
	f[0][0][0] = 1ll;
	int s = 0;
	for(int i=1; i<=m; i++)
	{
		for(int j=0; j<=lim; j++)
		{
			for(int k=0; k<=n-m-s; k++) if(f[i-1][j][k])
			{
				updsum(g1[i][j][max(0,k-a[i])],f[i-1][j][k]);
				updsum(g1[i][j][k],P-f[i-1][j][k]);
				updsum(g2[i][j][k],f[i-1][j][k]);
			}
		}
		s += a[i];
		for(int j=0; j<=lim; j++)
		{
			for(int k=0; k<=n-m-s; k++)
			{
				if(k) {updsum(g1[i][j][k],g1[i][j][k-1]);}
				if(j&&k) {updsum(g2[i][j][k],g2[i][j-1][k-1]);}
				f[i][j][k] = (g1[i][j][k]+g2[i][j][k])%P;
			}
		}
	}
	llong ans = 0ll;
	for(int j=0; j<=lim; j++) for(int k=0; k<=a[m+1]; k++) {updsum(ans,f[m][j][k]);}
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
  long long l,r;
  cin>>l>>r;
  int ans=30000;
  r=min(r,l+4038);
  for(long long i=l;i<=r;i++){
    for(long long j=i+1;j<=r;j++){
      int x=i*j%2019;
      ans=min(ans,x);
    }
  }
  cout<<ans<<endl;
}
    
    
    
 


Measured memory_bytes: 256
k = gets.chomp.to_i

if k <= 9
  puts k
  exit
end

# 1桁目
arr = []
1.upto(9){|i| arr << i }

k -= 10 

# 2桁目以降
while true do
  tmp_arr = []
  arr.each do |a|
    q = a % 10
    if q == 0
      tmp_arr << a * 10 + q
      tmp_arr << a * 10 + (q + 1)
    elsif q == 9
      tmp_arr << a * 10 + (q - 1)
      tmp_arr << a * 10 + q
    else
      tmp_arr << a * 10 + (q - 1)
      tmp_arr << a * 10 + q
      tmp_arr << a * 10 + (q + 1)
    end
  end
  if k < tmp_arr.length
    puts tmp_arr[k]
    exit 0
  end
  k -= tmp_arr.length
  arr = tmp_arr
end



Measured memory_bytes: 16068
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

len_set = set(L[x] for x in A)

INF = 10**18
can_make = [-INF]*(N+1)
can_make[0] = 0 # 何桁で作れるか

for n in range(1,N+1):
  for x in len_set:
    if n-x >= 0 and can_make[n] < can_make[n-x] + 1:
        can_make[n] = can_make[n-x] + 1

answer = []

A.sort(reverse = True)
# なるべく大きいのを使いたい。作れる桁数が減らないようにする。
for a in A:
  x = L[a]
  while N-x >= 0 and can_make[N] == can_make[N-x]+1:
    answer.append(str(a))
    N -= x
      
answer = ''.join(answer)
print(answer)

Measured memory_bytes: 3676
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <map>

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 998244353;
static const ll INF = 1000000000000000000LL;
using namespace std;

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

    vector  <ll> kai(N+1,0);

    REP(i,N)
    {
        ll tmp;
        cin >> tmp;
        if(i == 0 && tmp != 0)
        {
            cout << 0 << endl;
            return 0;
        }

        ++kai[tmp];
    }


    if(kai[0] > 1)
    {
        cout << 0 << endl;
        return 0;
    }
    ll res = 1;
    ll cnt = 1;
 
    for(ll i = 1; i <= N; ++i)
    {
        if(cnt >= N)break;
        if(kai[i] == 0)
        {
            cout << 0 << endl;
            return 0;
        }
        cnt += kai[i];

        ll tmp2=1;

        for(int j = 0; j < kai[i]; ++j)
        {
            tmp2 *= kai[i-1];
            tmp2 %= MOD;
        }

        res *= tmp2;
        res %= MOD;
    }

	cout << res << endl;
    return 0;    
}

Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

void kazoeru(vector<string> hoge,vector<string> kakunin){
    int n=hoge.size();
    
    for(int i=0;i<n;i++){
        cout<<hoge.at(i);
        if(i<n-1) cout<<" ";
    }
    
    cout<<endl;
    
    string safe="Stable";
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int a=0;a<n;a++){
                for(int b=a+1;b<n;b++){
                    if(kakunin.at(i).at(1)==kakunin.at(j).at(1) && kakunin.at(i)==hoge.at(b) && kakunin.at(j)==hoge.at(a)) safe="Not stable";
                }
            }
        }
    }
    
    cout<<safe<<endl;
}

int main(){
    int n;
    cin>>n;
    vector<string> hoge(n);
    for(int i=0;i<n;i++) cin>>hoge.at(i);
    vector<string> fuga=hoge;
    vector<string> kakunin=hoge;
    
    bool flag=true;
    
    while(flag){
        flag=false;
        
        for(int i=n-1;i>0;i--){
            if(hoge.at(i).at(1)<hoge.at(i-1).at(1)){
                string pre=hoge.at(i);
                hoge.at(i)=hoge.at(i-1);
                hoge.at(i-1)=pre;
                
                flag=true;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        int minj=i;
        for(int j=i;j<n;j++){
            if(fuga.at(minj).at(1)>fuga.at(j).at(1)){
                minj=j;
            }
        }
        
        string pre=fuga.at(i);
        fuga.at(i)=fuga.at(minj);
        fuga.at(minj)=pre;
    }
    
    kazoeru(hoge,kakunin);
    kazoeru(fuga,kakunin);
    
    return 0;
}


Measured memory_bytes: 3188
for i in range(10000):
    a,b,c = input().split()
    a = int(a)
    c = int(c)
    if b == "/":
        print(a//c)
    elif b == "+" :
        print(a+c)
    elif b == "-":
        print(a-c)
    elif b == "*":
        print(a*c)
    else:
        break



Measured memory_bytes: 5592
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int res = -1;
    for(int i=999;i>=111;i-=111){
      if( i>=n ){ res = i; }
    }
    System.out.println(res);
  }
}


Measured memory_bytes: 21716
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define Imax 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}
int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}


int main(){
  int n;
  double t,a;
  cin>>n>>t>>a;
  vector<double> h(n);
  rep(i,0,n) cin>>h[i];
  int good=-1;
  double sa=10000000;
  rep(i,0,n){
    if(fabs(t-h[i]*0.006-a)<sa){
      good=i+1;
      sa=fabs(t-h[i]*0.006-a);
    }
  }
  cout<<good;
  
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(arr):
    if len(arr) == 0:
        return 0
    tmp = min(arr)
    for i in range(len(arr)):
        arr[i] -= tmp
    n_arr = []
    strt = 0
    flag = True if arr[0] != 0 else False
    for i in range(len(arr)):
        if arr[i] == 0 and flag:
            n_arr.append(arr[strt:i])
            flag = False
        if arr[i] != 0 and not flag:
            flag = True
            strt = i
    if flag:
        n_arr.append(arr[strt:])
    s = tmp
    for i in n_arr:
        s += func(i)
    return s

n = INT()
h = LIST()
ans = func(h)
print(ans)

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

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

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

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

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

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

ll ngcd(vector<ll> a) {
  ll res = a[0];
  for(ll i=1; i<a.size() && res!=1; i++) res = gcd(a[i], res);
  return res;
}
ll nlcm(vector<ll> a){
  ll res = a[0];
  for(ll i=1; i<a.size(); i++) res = lcm(a[i], res);
  return res;
}
bool is_prime(ll n) {
  if(n < 2) return false;
  for (ll i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}
ll digsum(ll n) {
  ll res=0;
  while(n) res += n%10, n /= 10;
  return res;
}
ll digcnt(ll n){
  ll res=0;
  while(n) res++, n /= 10;
  return res;
}
vector<ll> divisor(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  return res;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  set<ll> s;
  bool ok=true;
  rep(i,n){
    ll a; cin>>a;
    if(s.count(a)) ok=false;
    s.insert(a);
  }
  if(ok) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  int n,m;
  cin >> n >> m;
  vector<ll>s(n),t(m);
  rep(i,n) cin >> s[i];
  rep(i,m) cin >> t[i];
  
  vvl dp(n+1,vl(m+1,0));
  
  rep(i,n){
    rep(j,m){
      dp[i+1][j+1] = dp[i+1][j]+dp[i][j+1];
      if(s[i]==t[j]) dp[i+1][j+1]++;
      else{
        dp[i+1][j+1] -= dp[i][j];
        dp[i+1][j+1] += MOD;
      }
      dp[i+1][j+1] %= MOD;
    }
  }
  
  cout << dp[n][m]+1 << endl;
  
  return 0;     
}


Measured memory_bytes: 31616
using System;

namespace AtCoderBeginnerContest165
{
    class Program
    {
        static void Main(string[] args)
        {
            int K = int.Parse(Console.ReadLine());
            String[] AandB= Console.ReadLine().Split(' ');
            int A = int.Parse(AandB[0]);
            int B = int.Parse(AandB[1]);
            
            for(int i = 0; K*i <= B; i++){
               if(K*i >= A && K*i <= B){
                    Console.WriteLine("OK");
                    return;
               }      
            }
            Console.WriteLine("NG");
        }
    }
}


Measured memory_bytes: 27540
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define ll long long

int main(){
#ifndef ONLINE_JUDGE
	freopen("C:\\Users\\User\\Documents\\input.txt","r",stdin);
#endif
	int T,i,j;
	int n,k;
	cin>>n>>k;

	vector<bool> dp(k+1,0);
	vector<int> a(n);

	for(i=0;i<n;++i){
		scanf("%d",&a[i]);
	} 

	for(i=1;i<=k;++i){
		for(int x: a){
			if(x<=i && !dp[i-x]) dp[i]=1;
		}
	}
	printf("%s\n",dp[k] ? "First" : "Second");

return 0;
}

Measured memory_bytes: 3620
//#pragma GCC optimize ("-O3","unroll-loops")
// #pragma GCC target("avx")
#include<bits/stdc++.h>
 
using namespace std;
 
#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
 
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 1e9+7; const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 2e18;

int A[90][90],B[90][90];
bool dp[90][90][40000];
void solve() {
	
	int H,W;cin>>H>>W;
	REP(i,H)REP(j,W){
		cin>>A[i][j];
	}
	REP(i,H)REP(j,W){
		cin>>B[i][j];
	}
	dp[0][0][20000+A[0][0]-B[0][0]]=1;
	dp[0][0][20000+B[0][0]-A[0][0]]=1;
	REP(i,H){
		REP(j,W){
			REP(S,35000){
				if(dp[i][j][S]){
					dp[i+1][j][S+A[i+1][j]-B[i+1][j]]=1;
					dp[i+1][j][S-A[i+1][j]+B[i+1][j]]=1;
					dp[i][j+1][S+A[i][j+1]-B[i][j+1]]=1;
					dp[i][j+1][S-A[i][j+1]+B[i][j+1]]=1;
				}
			}
		}
	}
	ll ans=INF;
	REP(S,40000){
		if(dp[H-1][W-1][S]){
			ans=min(ans,abs(20000-S));
		}
	}
	print(ans);
}
 
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}

Measured memory_bytes: 283392
#include <stdio.h>
#include <limits.h>
 
int main(void){
  int n;
  scanf("%d", &n);
  int min = INT_MAX;
  int max = INT_MIN;
  
  for(int i = 0; i < n; i++){
    int a;
    scanf("%d", &a);
    if(a < min) min = a;
    if(max < a) max = a;
  }
  
  printf("%d\n", max - min);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <iterator>
#define r(i,n) for(int i=0;i<n;i++)
#define R(i,c,n) for(int i=c;i<n;i++)
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

int main(){
  ios::sync_with_stdio(false);
	cin.tie(0);
  long long int k,a,b;
  cin >> k >> a >> b;
  if(b-a<3 || a >= k) {
    cout << k+1 << endl;
    return 0;
  }
  long long int count = 1;
  k -= a-1;
  count = a;
  int tmp = ceil(k/2);
  k -= tmp*2;
  count += tmp*(b-a);
  if(k>0){
    count ++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256