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

#define dfl(i,a,b)   for(int i=a;i>b;i--)
#define fl(i,a,b)    for(int i=a;i<b;i++)
#define ll           long long
#define ld           long double
#define endl         '\n'
#define pb           push_back
#define ff           first
#define ss           second
#define pii          pair<int,int>
#define pll          pair<ll,ll>
#define vi           vector<int>
#define vll          vector<long long>
#define all(x)       x.begin(),x.end()
#define mod          1000000007 
#define mx           1000005
#define mii          map<int,int>
#define mumii        multimap<int,int> 
#define mx2          65
#define inf          4e18
#define fast         ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define gt           greater<int>()
#define debug(x)     cout<<x<<endl;
#define scan(a,n)    fl(i,0,n)cin>>a[i];

//The ASCII value of the lowercase alphabet is from 97 to 122.
//The ASCII value of the uppercase alphabet is from 65 to 90.

bool isPrime(int n) 
{  
    if (n <= 1) 
        return false;
        
    if (n <= 3) 
        return true; 
 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
}

void solve()
{
     int n,x,y,ans;
     cin>>n>>x>>y;
     
     ans=y*((int)ceil((double)n/(double)x));
     cout<<ans;
     
     
}
int main()
{
	fast;
	int t=1;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3640
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect
import itertools


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    N = int(inputs[0])
    SSSS = 1000000007
    count = collections.Counter()

    for i in range(1, N+1):
        target = i
        is_end = False
        while not is_end:
            is_end = True
            for j in range(2, int(math.sqrt(target)+1)):
                if target % j == 0:
                    count[j] += 1
                    target = target // j
                    is_end = False
                    break
            if is_end and target != 1:
                count[target] += 1
    c = 1
    for k, v in count.items():
        c *= (v + 1)
        c = c % SSSS
    return c


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 40304
process.stdin.resume();
process.stdin.setEncoding('utf8');

const reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout,
});

reader.on('line', (line) => {
  let h = BigInt(line);
  let n = BigInt(0);

  for (let i = 0; i < 50; i++) {
    if (h === BigInt(1)) break;
    h /= BigInt(2);
    n += 1n;
  }

  const result = 2n ** (n + 1n) - 1n;

  const answer = String(result);
  console.log(answer);

  process.exit(0);
});


Measured memory_bytes: 30452
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
//using
using namespace std;
using vi = vector <int>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//グローバル変数宣言
 ll a=0,b=0,c=0,e=0,n=0,k=0;


int main(){
   string s;
   cin>>s;
   rep(i,s.size()){
      if (s[i]=='A'||s[i]=='G'||s[i]=='C'||s[i]=='T')
      {
         b++;
      }else {a=max(a,b);b=0;}
      if(i==s.size()-1)a=max(a,b);
   }
   print(a)
}


Measured memory_bytes: 3612
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int k = Integer.parseInt(br.readLine());
    br.close();
    System.out.println(solve(k));
  }

  static String solve(int k) {
    String ret = "";
    if (k < 10) {
      return String.valueOf(k);
    }
    int lunCnt = 9;
    int[][] dp = new int[32][10];
    for (int i = 0; i <= 9; i++) {
      dp[1][i] = 1;
    }
    int digit = 1;
    int pos = 0;
    int remain = 0;

    loop:
    {
      while (true) {
        digit++;
        for (int i = 0; i <= 9; i++) {
          for (int j = Math.max(0, i - 1); j <= Math.min(9, i + 1); j++) {
            dp[digit][i] += dp[digit - 1][j];
          }
          if (i != 0) {
            if (lunCnt + dp[digit][i] >= k) {
              remain = k - lunCnt;
              pos = i;
              break loop;
            } else {
              lunCnt += dp[digit][i];
            }
          }
        }
      }
    }
    ret += pos;
    digit--;
    while(digit > 0){
      for(int i = Math.max(0, pos - 1); i <= Math.min(9, pos + 1); i++){
        if(remain > dp[digit][i]){
          remain -= dp[digit][i];
        } else {
          ret += i;
          pos = i;
          break;
        }
      }
      digit--;
    }
    return ret;
  }
}


Measured memory_bytes: 36972
#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++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef pair<int, int> p;
typedef priority_queue<p> pq;
typedef priority_queue<p, vector<p>, greater<p>> gpq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string youbi[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

    string s;
    cin >> s;

    REP(i, 7)
    {
        if(youbi[i] == s)
        {
            cout << 7 - i << endl;
            break;
        }
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF=2E17;
typedef pair<int,int> Pair;
typedef long long int LL;
const int MAX=100010;

int main(){
    LL N,C;
    LL x[MAX]={};
    LL v[MAX]={};
    cin >> N >> C;
    for(LL i=0;i<N;i++){
        cin >> x[i+1] >> v[i+1];
    }
    LL CW[MAX]={};
    LL CCW[MAX]={};
    x[N+1]=C;
    for(LL i=0;i<N;i++){
            CW[i+1]=CW[i]+v[i+1]-x[i+1]+x[i];
            CCW[i+1]=CCW[i]+v[N-i]-(x[N-i+1]-x[N-i]);
    }
    LL CWM[MAX]={};
    LL CCWM[MAX]={};
    for(LL i=0;i<N;i++){
        CCWM[i+1]=max(CCWM[i],CCW[i+1]);
        CWM[i+1]=max(CWM[i],CW[i+1]);
    }
    LL ans=0;
    for(LL i=0;i<=N;i++){
        ans=max(ans,CW[i]+CCWM[N-i]-x[i]);
        ans=max(ans,CW[i]);
    }
    for(LL i=0;i<=N;i++){
        ans=max(ans,CCW[i]+CWM[N-i]-(C-x[N-i+1]));
        ans=max(ans,CCW[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <list>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define F first
#define S second

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


typedef struct _za{
  int x,y;
  bool operator<(const _za&r)const{return this->x<r.x;};
}za;


vector<za> se,dan;

main(){
  int an,bn,r;
  while(cin>>an>>bn,an|bn){
    cin>>r;
    se.resize(an);
    dan.resize(bn);
    rep(i,an)cin>>se[i].x>>se[i].y;
    rep(i,bn)cin>>dan[i].x>>dan[i].y;


    sort(se.begin(),se.end());
    sort(dan.begin(),dan.end());

    int ans=0;

    rep(i,an){
      int xn=se[i].x,yn=se[i].y;
      za t={xn-4*r-2,0};
      int tt=distance(dan.begin(),lower_bound(dan.begin(),dan.end(),t));
      for(int j=tt;j<bn;j++){
	if(xn+4*r+3<dan[j].x)break;
	else{
	  int dxn=xn-dan[j].x,dyn=yn-dan[j].y;
	  if(dxn*dxn+dyn*dyn<=16*r*r)++ans;
	}
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 2608
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define ff first
#define ss second
#define p pair<int,int>
#define pb push_back
#define endl '\n'
#define w(t) ll test;cin>>test;while(test--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define pi acos(-1)

int main()
{
    fast;
    string a,b;
    cin>>a>>b;
    int cnt=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])cnt++;
    }
    cout<<cnt<<endl;
}



Measured memory_bytes: 3884
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll N,D,X;
  cin>>N>>D>>X;
  ll a[N];
  rep(i,N) cin>>a[i];
  ll ans;
  ll count=0;
  for(int i=0;i<N;i++){
    ll j=1;
    while(D>=1+a[i]*j){
      j++;
    }
    count+=j;
  }
  ans=count+X;
  cout<<ans<<endl;
}


Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 998244353;
const ll INF = 1000000000000000;
ll N;

string s;

ll pow(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return pow(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = pow(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll pow_ll(ll x, ll y)
{
	if (y == 0) return 1;
	return x * pow_ll(x, y - 1);
}

ll div(ll x)
{
	return pow(x, mod - 2);
}



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

	if (N % 2 == 1)
	{
		cout << "No" << endl;
	}
	else
	{
		bool jud = true;
		for (int i = 0; i < N / 2; i++)
		{
			if (s[i] != s[i + N / 2])
			{
				jud = false;
			}
		}
		if (jud)
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}

	int xxx;
	cin >> xxx;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;

using namespace std;
using ll = long long;
typedef pair <int, int> pii;
int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll n, m;
	char tmp;
	ll memo[1003][1003] = { {} };
	ll memox[1003] = {};
	ll memoy[1003] = {};
	ll x[1000006] = {};
	ll y[100005] = {};
	ll z[100005] = {};
	string s;
	//IntStack yStack;
	//charStack Stack;
	cin >> a;
	x[0] = a;
	b = 1;
	while (true)
	{
		if (a%2==0)
		{
			for (int i = 0; i < b; i++)
			{
				if (a/2==x[i])
				{
					cout << b+1 << endl;
					return 0;
				}
			}
			x[b] = a / 2;
			b++;
			a /= 2;
		}
		else
		{
			for (int i = 0; i < b; i++)
			{
				if (a*3+1 == x[i])
				{
					cout << b+1 << endl;
					return 0;
				}
			}
			x[b] = a*3+1;
			b++;
			a = a * 3 + 1;
		}
	}




	//cout << a*b/2 << endl;

	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

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

using namespace std;

int main(){

int N,T;
int t[101];
int c[101];
int ans = 1001;
int ansT;
std::string s1 = "TLE";

cin >> N >> T;

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


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

if(t[i] <= T && c[i] < ans){
ans = c[i];
ansT = t[i];
}
}

if(ans == 1001){
printf("%s",s1.c_str());
}else{
cout << ans << endl;
}
}

Measured memory_bytes: 256
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        dic_last = {}
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
                    hh = H1[i] * (mod2+1) + H2[i]
                    if hh not in dic_last:
                        dic_last[hh] = [0] * 26
                    for j in range(26):
                        if cnt[i][j] > 0:
                            dic_last[hh][j] += 1
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 * (mod2+1) + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                if h in dic_last:
                    ans += dic_last[h][last]
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 192632
# ABC154 -virtual
# A
if True:
    S,T=input().split()
    A,B=map(int,input().split())
    U=input()
    if U==S:
        A-=1
    else:
        B-=1
    print(A,B)
# B
if False: print('x'*len(input()))
# C
if False:
    N=int(input())
    A=[int(i) for i in input().split()]
    print('YES' if len(A)==len(set(A)) else 'NO')
# D
# E
# F

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

void dfs(int len, int n, string s) {
    if (len == n) {
        cout << s << endl;
    } else {
        char mx = 'a';
        rep (i, s.size()) {
            chmax (mx, s[i]);
        }
        for (char c = 'a'; c <= mx + 1; ++c) {
            dfs(len+1, n, s+c);
        }
    }
}

int main() {
    int n;
    cin >> n;
    string t = "a";
    dfs(1, n, t);
}

Measured memory_bytes: 1536
import java.util.*;

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

        int n = Integer.parseInt(sc.next());
        String s = sc.next();
        int[] ch = new int[26];
        int l = 0;
        int r = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Arrays.fill(ch, 0);
            l = 0;
            r = 0;
            for (int j = 0; j < i; j++) {
                if (ch[(int) s.charAt(j) - 97] == 0) {
                    ch[(int) s.charAt(j) - 97]++;
                    l++;
                }
            }
            // Arrays.fill(ch, 0);
            for (int j = i; j < n; j++) {
                if (ch[(int) s.charAt(j) - 97] == 1) {
                    ch[(int) s.charAt(j) - 97]++;
                    r++;
                }
            }
            // System.out.println(l + " " + r + " " + ans);
            ans = Math.max(ans, Math.min(l, r));
        }
        // int m = Integer.parseInt(sc.next());
        // int[] a = new int[n];
        // int ans = 0;

        // for (int i = 0; i < n; i++) {
        // a[i] = Integer.parseInt(sc.next());
        // }

        System.out.println(ans);

        sc.close();
    }
}

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

int main() {
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	int ans = 0;
	for (int i = 0; i < k; i++) {
		if (i < a) ans++;
		else if (i < a+b) ;
		else if (i < a+b+c) ans--;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 3644
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC157
{
    class Program
    {
        static void Main(string[] args)
        {
            b();
        }

        public static void b()
        {
            int[] a1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] a2 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] a3 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            bool[] b1 = { false, false, false };
            bool[] b2 = { false, false, false };
            bool[] b3 = { false, false, false };
            int n = int.Parse(Console.ReadLine());
            bool flg = false;
            for(int i = 0; i < n; i++)
            {
                int a = int.Parse(Console.ReadLine());
                for(int j = 0; j < 3; j++)
                {
                    if(a1[j] == a)
                    { b1[j] = true; }
                    if(a2[j] == a)
                    { b2[j] = true; }
                    if(a3[j] == a)
                    { b3[j] = true; }
                }
            }
            if(b1[0] == true && b1[1] == true && b1[2] == true)
            { flg = true; }
            if(b2[0] == true && b2[1] == true && b2[2] == true)
            { flg = true; }
            if(b3[0] == true && b3[1] == true && b3[2] == true)
            { flg = true; }
            if(b1[0] == true && b2[1] == true && b3[2] == true)
            { flg = true; }
            if(b1[2] == true && b2[1] == true && b3[0] == true)
            { flg = true; }
            if(b1[0] == true && b3[0] == true && b2[0] == true)
            { flg = true; }
            if (b1[1] == true && b2[1] == true && b3[1] == true)
            { flg = true; }
            if(b1[2] == true && b2[2] == true && b3[2] == true)
            { flg = true; }
            if(flg == true)
            { Console.WriteLine("Yes"); }
            else
            { Console.WriteLine("No"); }
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

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

	ll A;
	long double B;
	cin >> A >> B;
	cout << ll(A*B) << endl;

	return 0;
}

Measured memory_bytes: 3748
#include <iostream>
using namespace std;
const int N=4002;
const int inf=1e9;
int n,a[N],dp[N][N],cost[N][N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n<<1;i++){
        char str[2]; int x; scanf("%s%d",str,&x);
        if(str[0]=='B') a[i]=x;
        if(str[0]=='W') a[i]=x+n;
    }
    //for(int i=1;i<=n<<1;i++) printf("%d ",a[i]); printf("\n");
    for(int i=1;i<=n<<1;i++){
        for(int j=i+1;j<=n<<1;j++){
            cost[a[i]][a[j]]++;
        }
        for(int j=1;j<=n;j++){
            cost[a[i]][j]+=cost[a[i]][j-1];
        }
        for(int j=n+2;j<=n<<1;j++){
            cost[a[i]][j]+=cost[a[i]][j-1];
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=0;i<=n<<1;i++){
        for(int j=0;j<=i;j++){
            //printf("dp[%d][%d]=%d\n", i,j,dp[i][j]);
            // 1~j 1~i-j
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+cost[n+i-j+1][j]+((i==j)?0:cost[n+i-j+1][n+i-j]));
            dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+cost[j+1][j]+((i==j)?0:cost[j+1][n+i-j]));
        }
    }
    cout<<dp[2*n][n]<<endl;
}










Measured memory_bytes: 125312
#!/usr/bin/env python3
import heapq


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    Q = int(input())
    sum_b = 0
    sum_al = 0
    sum_ar = 0
    hl = []
    hr = []
    for _ in range(Q):
        buf = input()
        if buf[0] == '1':
            _, a, b = map(int, buf.split())
            sum_b += b
            if len(hl) == 0:
                heapq.heappush(hl, -a)
                sum_al += a
                continue
            if len(hr) == 0:
                heapq.heappush(hr, a)
                sum_ar += a
                if -hl[0] > hr[0]:
                    hl[0], hr[0] = -hr[0], -hl[0]
                    sum_al, sum_ar = sum_ar, sum_al
                continue

            if a < -hl[0]:
                heapq.heappush(hl, -a)
                sum_al += a
            elif a > hr[0]:
                heapq.heappush(hr, a)
                sum_ar += a
            else:
                #if len(hl) <= len(hr):
                heapq.heappush(hl, -a)
                sum_al += a
                #else:
                #    heapq.heappush(hr, a)

            while len(hr) > len(hl):
                tmp = heapq.heappop(hr)
                sum_ar -= tmp
                heapq.heappush(hl, -tmp)
                sum_al += tmp
            while len(hl) > len(hr)+1:
                tmp = heapq.heappop(hl)
                sum_al -= -tmp
                heapq.heappush(hr, -tmp)
                sum_ar += -tmp

        else:
            tmp_al = -hl[0]*len(hl)-sum_al if len(hl) != 0 else 0
            tmp_ar = sum_ar-(-hl[0])*len(hr) if len(hl) != 0 else 0
            #print(hl, sum_al, hr, sum_ar)
            print(-hl[0], tmp_al+tmp_ar+sum_b)

if __name__ == '__main__':
    main()


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

int main(){
	int h, w;
	cin >> h >> w;
	vector<vector<int>> mapH(h, vector<int>(w));
	vector<vector<int>> mapW(h, vector<int>(w));
	vector<vector<int>> map(h, vector<int>(w));
	int max = 0;
    vector<string> st(h);
	for(int i=0; i<h; i++){
      cin >> st.at(i);
      int kp = 0;
      for(int j=0; j<w; j++){
        if(st.at(i).at(j) == '.'){
        	kp++;
        	mapW.at(i).at(j) = kp;
        }else{
        	kp = 0;
        	mapW.at(i).at(j) = kp;
        }
      }
      int max = mapW.at(i).at(w-1);
      int f = 0;
      for(int j=w-1; j>=0; j--){
        if(st.at(i).at(j) == '.'){
          	if(f == 0) max = mapW.at(i).at(j);
        	f = 1;
        	mapW.at(i).at(j) = max;
        }else{
        	f = 0;
        	mapW.at(i).at(j) = 0;
        }
      }
    }
	for(int j=0; j<w; j++){
      int kp = 0;
      for(int i=0; i<h; i++){
        if(st.at(i).at(j) == '.'){
        	kp++;
        	mapH.at(i).at(j) = kp;
        }else{
        	kp = 0;
        	mapH.at(i).at(j) = kp;
        }
      }
      int max = mapH.at(h-1).at(j);
      int f = 0;
      for(int i=h-1; i>=0; i--){
        if(st.at(i).at(j) == '.'){
          	if(f == 0) max = mapH.at(i).at(j);
        	f = 1;
        	mapH.at(i).at(j) = max;
        }else{
        	f = 0;
        	mapH.at(i).at(j) = 0;
        }
      }
    }
	for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
    	map.at(i).at(j) = mapW.at(i).at(j) + mapH.at(i).at(j);
      	if(map.at(i).at(j) > max) max = map.at(i).at(j);
    }
    }
	cout << max-1 <<endl;
}

Measured memory_bytes: 51456
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << ": " << endl
#define rep(i,n) for(int i=0; (i)<(n); ++(i))
#define rrep(i,n) for(int i=(n); (i)>=0; --(i))
#define reps(i,s,n) for(int i=(s); (i)<(n); ++(i))
#define maxi(v) distance(v.begin(), max_element(v.begin(), v.end()))
#define mini(v) distance(v.begin(), min_element(v.begin(), v.end()))
#define maxemt(v) *max_element(v.begin(), v.end())
#define minemt(v) *min_element(v.begin(), v.end())
#define lb(v,x) v[lower_bound(v.begin(), v.end(), x) - v.begin()]
#define ub(v,x) v[upper_bound(v.begin(), v.end(), x) - v.begin()]
template<class T> inline bool print(T& x){ cout << x << endl; return true; }
template<class T> inline bool print_(T& x){ cout << x << " "; return true; }
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 int INF = 1e9;
const ll llINF = 1LL<<60;
const int MOD = 1e9+7;
const double EPS = 1e-9;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
  }
ll lcm(ll x, ll y){
  return x / gcd(x,y) * y;
}
ll comb(ll n, ll r){
  if (r*2>n) r=n-r;
  ll x=1, y=1;
  reps(i,1,r+1){ x *= (n-i+1); y *= i; }
  return x / y;
}


int main(){
  int n; cin >> n;
  vector<int> a(n); rep(i,n) cin >> a[i];
  int cnt4=0, cnt2=0;
  rep(i,n){
    if(a[i]%4==0) cnt4++;
    else if(a[i]%2==0) cnt2++;
  }
  if(cnt4 >= n/2) cout << "Yes";
  else if(cnt2 >= n-cnt4*2) cout << "Yes";
  else cout << "No";
  
return 0;
}


Measured memory_bytes: 640
n,tt = map(int, input().split( ))
t = tuple(map(int, input().split( )))
ans  = 0
ti = 0;
for i in range(n):
    if t[i] >= ti+tt:
        ans += tt 
    else:
        ans += t[i] - ti
    ti = t[i]
print(ans+tt)

Measured memory_bytes: 93136
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main() {
  string s;
  int k;
  cin >> s >> k;
  priority_queue<string, vector<string>, greater<string>> p;
  string t = "?"; int c = 0;
  rep(i, s.size()){
    string u = "";
    rep(j, min(5, (int)s.size()-i)){
      u += s[i+j];
      p.push(u);
    }
  }
  while(c < k){
    if(t != p.top()){
      t = p.top();
      p.pop();
      ++c;
    }
    else p.pop();
  }
  cout << t << "\n";
  return 0;
}

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

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

ll LCM(ll a, ll b) { return a * b / GCD(a, b); }

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> a(N);
    ll prevcnt = 0;
    rep(i, N) {
        cin >> a[i];
        ll copy = a[i];
        ll cnt = 0;
        while (copy % 2 == 0) {
            copy /= 2;
            cnt++;
        }
        if (i != 0 && prevcnt != cnt) {
            cout << 0 << endl;
            return 0;
        }
        prevcnt = cnt;
    }

    ll lcm = a[0] / 2;
    rep(i, N) { lcm = LCM(lcm, a[i] / 2); }

    ll cnt = (M / lcm + 1) / 2;
    cout << cnt << endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  
  for(int i = 0 ; i < n; i++){
    cin >> a[i];
  }
  
  sort(a.begin(), a.end());
  
  int sum = 0;
  for(int i = 0; i < n-1; i++){
    sum += (a[i+1] - a[i]);
  }
  
  cout << sum << endl;
}
  

Measured memory_bytes: 256
piza = list(map(int,input().split()))
x = piza[0] * piza[3] + piza[1] * piza[4]
y = piza[2] * 2 * max(piza[3],piza[4])
if piza[3] >= piza[4]:
	z = piza[2] * (2 * piza[4]) + piza[0]*(piza[3]-piza[4])
else:
	z = piza[2] * (2 * piza[3]) + piza[1]*(piza[4]-piza[3])
print(min(x,y,z))

Measured memory_bytes: 3064
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    n: i64,
  }

  puts!("{}\n", n * (n - 1) / 2);
}


Measured memory_bytes: 4352
#include<cstdio>

int main()
{
	int n; scanf("%d", &n);
	int ans = 0;
	
	for(int i = 1; i <= n; i++){
		int input; scanf("%d", &input);
		if((i & 1) and (input & 1)) ans++;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 1688
from collections import deque
import numpy as np
stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
n = int(input())

c = np.zeros([10, 10])
# 先頭i末尾jの値
for i in range(1, n+1):
    str_i = str(i)
    head = int(str_i[0])
    tail = int(str_i[-1])
    c[head, tail] += 1
count = 0
for i in range(1, 10):
    for j in range(1, 10):
        count += c[i, j]*c[j, i]
print(int(count))


Measured memory_bytes: 14404
n,m=map(int,input().split())
A=list(map(int,input().split()))
ans=0
for i in range(40,-1,-1):
    cnt=0
    for j in A:
        if j%(1<<(i+1))>=(1<<i):
            cnt+=1
    a=cnt
    if m>=2**i and cnt<=n-cnt:
        a=n-cnt
        m-=2**i
    ans+=a*(2**i)
print(ans)

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

import sys
nyuryoku = [int(i) - 1 for i in sys.stdin]

N = nyuryoku[0] + 1
a_list = nyuryoku[1:]


cnt_push = 0
button_list = [False] * N
i = 0
#cur_but_posi = a_list[0]

while True:
    if button_list[i] == False:
        button_list[i] = True
        cnt_push += 1
        if a_list[i] == 1:
            break
        i = a_list[i]
    else:
        cnt_push = -1
        break

print(cnt_push)

"""
import sys

l = [int(i) - 1 for i in sys.stdin]

N = l[0] + 1

a = l[1:]

done = [False] * N

i = 0

ans = 0

while True:
    if done[i] == False:
        done[i] = True
        ans += 1
        if a[i] == 1:
            break
        i = a[i]
    else:
        ans = -1
        break

print(ans)
"""


Measured memory_bytes: 14484
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#define REP(i,a) for(int i = 0; i < (a); i++)
using namespace std;

int search(int a[], int n, int key){
	int i = 0;
	a[n] = key;
	while(a[i] != key)i++;
	return i != n;// i != n なら True
}

int main(){
	int n;
	cin >> n;
	int s[n];
	REP(i,n) cin >> s[i];
	int q;
	cin >> q;
	int t[q];
	REP(i,q) cin >> t[i];
	int sum = 0;
	REP(i,q){
		if(search(s, n, t[i]))sum++;
	}
	cout << sum << endl;
}


Measured memory_bytes: 3132
import collections
K = int(input())

q = collections.deque()
for i in range(9):
    q.append(i+1)
while(q):
    x = q.popleft()
    k = x % 10
    for j in range(3):
        if k == 0 and j == 0:
            continue
        elif k == 9 and j == 2:
            continue
        else:
            if j == 0:
                q.append(x*10+k-1)
            elif j == 1:
                q.append(x*10 + k)
            else:
                q.append(x*10+k+1)
    #     print(q)
    # print(x)
    K -= 1
    if K == 0:
        print(x)
        break


Measured memory_bytes: 18624
#include <bits/stdc++.h>
using namespace std;
struct process {
    string pname;
    int time;
};

const int MAX = 100010;
process qu[MAX];
int head = 0, tail = 0;

void init() {
    head = tail = 0;
}

void enqueue(process x) {
    qu[tail].pname = x.pname;
    qu[tail].time = x.time;

    tail++;
    if(tail == MAX) tail = 0;
}

process dequeue() {
    process res = qu[head];
    ++head;
    if(head == MAX) head = 0;
    return res;
}

int main() {
    init();

    int n, q;
    cin >> n >> q;
    process x;
    for(int i = 0; i < n; i++) {
        cin >> x.pname >> x.time;
        enqueue(x);
    }
    int total_time = 0;
    while(head != tail) {
        x = dequeue();
        int c = min(x.time, q);
        x.time -= c;
        total_time += c;
        if(x.time > 0) {
            enqueue(x);
        } else {
            cout << x.pname << " " << total_time << endl;
        }
    }
}


Measured memory_bytes: 6968
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if (a & 1) {
      cout << "first" << endl;
      return 0;
    }
  }

  cout << "second" << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

int main() {
	int N, M;
	cin >> N >> M;

	int s, c, X = 11;
	if (N == 1) {
		if (M == 0) {
			cout << 0 << endl;
			return 0;
		}
		for (int i = 0;i < M;i++) {
			cin >> s >> c;
			if (X == 11)
				X = c;
			else if (X != c) {
				cout << -1 << endl;
				return 0;
			}
		}
		cout << X << endl;
		return 0;
	}

	vector<int> A(N, 0), B(N, 0);
	A[0] = 1;
	for (int i = 0;i < M;i++) {
		cin >> s >> c;
		if (B[s - 1] && A[s - 1] != c) {
			cout << -1 << endl;
			return 0;
		}
		if (s == 1 && c == 0) {
			cout << -1 << endl;
			return 0;
		}
		A[s - 1] = c;
		B[s - 1] = 1;
	}
	for (int i = 0;i < N;i++) {
		cout << A[i];
	}
	cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,a,count=0;cin>>N;
  for(int i=0;i<N;i++){
    cin>>a;
    if(a%2==0)count++;
  }
  int ans=pow(3,N)-pow(2,count);
  cout<<ans<<endl;
}

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

using namespace std;

int main(void) {
	int m,max,min;
	cin >> m >> min >> max;
	while (m != 0 || min != 0 || max != 0) {
		vector<int> P(m);
		for (int i = 0; i < m; ++i) {
			cin >> P[i];
		}
		int ret;
		int gap;
		for (int n = min; n < max+1; ++n) {
			if (n == min) {
				ret = n;
				gap = P[n-1] - P[n];
			}
			else if (gap <= P[n-1] - P[n]) {
				ret = n;
				gap = P[n-1] - P[n];
			}
		}
		cout << ret << endl;
		cin >> m >> min >> max;
	}
	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a) for(int i = 0; i < a; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b; cin>>a>>b;
    if(a!=2&&b!=2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(ll i=0;i<(ll)n;++i)
const ll INF = 999999999999999;

int main(){
  ll n;
  cin >> n;
  map<ll,ll> a;
  vector<ll> m;
  rep(i,n){
    ll num;
    cin >> num;
    a[num]++;
    if( a[num] == 1 ) m.push_back(num);
  }
  ll ans = 0;
  rep(i,m.size()){
    ll num = m.at(i);
    if( a[num] > num ){
      ans += a[num] - num;
    }else if( a[num] < num ){
      ans += a[num];
    }
  }
  cout << ans << "\n";
  
  return 0;
}

Measured memory_bytes: 7028
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
signed main(){
    int a,b,c,d;
    cin>>a>>b;
    if(a>b)cout<<a-1<<endl;
    else cout<<a<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100010
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N],inv[N],ans,sum;
int main(){
	n=read();
	inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	for(int i=1;i<=n;++i){
		ans=(ans+1LL*sum*(a[i]-a[i-1]))%mod;
		sum=(sum+inv[i])%mod;
	}
	for(int i=1;i<n;++i){
		ans=1LL*ans*i%mod;
	}
	printf("%d\n",ans);
	return 0;
}



Measured memory_bytes: 4436
import sys
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline()
def read(): return int(input())
def reads(): return [int(i) for i in input().split()]

N, Y = reads()

x_max = min(N, Y//10000)
y_max = min(N, Y//5000)

ans = (-1, -1, -1)

for x in range(x_max+1):
	for y in range(min(y_max+1, N-x+1)):
		if 10000*x + 5000*y + 1000*(N-x-y) == Y:
			ans = (x, y, N-x-y)
			break

print(str(ans[0])+' '+str(ans[1])+' '+str(ans[2]))

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iterator>
#include <fstream>
#include <math.h>

#include <random>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <list>
#include <bitset>
#include <unordered_set>
#include <unordered_map>

#include <random>
#include <ctime>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

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

#define FOR(i, from, to) for (int i = from; i < to; i++)
#define ROF(i, from, to) for (int i = from; i > to; i--)

const long double PI = 3.141592653589793238463;
const int INF = 0x3f3f3f3f;
const int INFS = 1000000000;
const ll M = 1000000007;
const ll LLINF = 1000000000000000000;
const double EPS = 1e-8;

#define int long long

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, a, b;
    cin >> n >> a >> b;
    vector<int> x(n);
    FOR(i, 0, n)
        cin >> x[i];
    int ans = 0;
    FOR(i, 1, n)
        ans += min(b, (x[i] - x[i - 1]) * a);
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 4004
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
ll INF=1LL<<60;
ll MOD=1000000007;



int main(){
    string s;
    cin >> s;
    ll K;
    cin >> K;
    ll N=s.size();

    vector<ll> num(N,0);
    for(ll i=0;i<N;i++){
        num[i]=s[i]-'0'
    ;}                 

    //未満フラグ、
    vector<vector<ll>> dp(2, vector<ll>(4, 0));
    dp[1][0]=1;
    dp[1][1]=num[0]-1;
    dp[0][1]=1;

    for(ll j=1;j<N;j++){
        vector<vector<ll>> dp2(2, vector<ll>(4, 0));
        if(num[j]!=0){
            //0の追加
            for(ll i=0;i<4;i++){
                dp2[1][i]+=dp[0][i]
            ;}
            for(ll i=0;i<4;i++){
                dp2[1][i]+=dp[1][i]
            ;}
            //numの追加
            for(ll i=1;i<4;i++){
                dp2[0][i]+=dp[0][i-1]
            ;}
            for(ll i=1;i<4;i++){
                dp2[1][i]+=dp[1][i-1]
            ;}
            //1からnum-1の追加
            for(ll i=1;i<4;i++){
                dp2[1][i]+=dp[0][i-1]*(num[j]-1)+dp[1][i-1]*(num[j]-1)
            ;}
            //num+1から9の追加
            for(ll i=1;i<4;i++){
                dp2[1][i]+=dp[1][i-1]*(9-num[j])
            ;}

        }
        else if(num[j]==0){
            //0の追加
            for(ll i=0;i<4;i++){
                dp2[1][i]+=dp[1][i];
                dp2[0][i]+=dp[0][i];
            ;}
            //1から9の追加
            for(ll i=1;i<4;i++){
                dp2[1][i]+=dp[1][i-1]*9
            ;}
        }
        for(ll i=0;i<4;i++){
            dp[1][i]=dp2[1][i];
            dp[0][i]=dp2[0][i]
        ;}

    ;}

    cout<<dp[0][K]+dp[1][K]<<endl;
    

    return 0;
}


Measured memory_bytes: 3636
using System;

namespace Q3
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string input1 = Console.ReadLine();
            string input2 = Console.ReadLine();

            int count = 1;
            for(int i = 0; i < input2.Length - 1; i++)
            {
                if (input2[i] != input2[i + 1])
                    count++;
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main(){
  int n;
  cin >> n;
  double t,a;
  cin >> t >> a;
  vector<double> v(n);
  for(int i = 0; i < n; i++){
    int in;
    cin >> in;
    v[i] = t - in * 0.006;
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    double p = v[ans];
    double q = v[i];
    if(abs(a-q) < abs(a-p))ans = i;
  }
  cout << ans+1 << endl;
}


Measured memory_bytes: 256
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d+1) for _ in range(c+1)]
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b]*b
    dp[i][b] %= mod
for i in range(a,c+1):
    for j in range(b+1,d+1):
        dp[i][j] += dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %= mod
print(dp[c][d])

Measured memory_bytes: 133788
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    ll n,m;
    cin>>n>>m;
    ll total=m*1900+(n-m)*100;
    ll ans=total*pow(2,m);
    cout<<ans<<endl;

}

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

vector<vector<vector<int>>>dp;
int main() {
	int N, M; cin >> N >> M;
	dp = vector<vector<vector<int>>>(N+1, vector<vector<int>>(M + 1, vector<int>(M+1, -1e9)));
	dp[0][M][0] = 0;
	vector<tuple<int, int, int>>musics;
	for (int i = 0; i < N; ++i) {
		int a, b, c; cin >> a >> b >> c;
		musics.emplace_back(a,b, c);
	}
	for (int music = 0; music < N; ++music) {
		for (int two = 0; two <= M; ++two) {
			for (int one = 0; one <= M; ++one) {
				for (int usetwo = 0; usetwo <= min(8,two); ++usetwo) {
					for (int useone = 0; useone <= min(8-usetwo, one); ++useone) {
						for (int destwo = 0; destwo <= min(8,two - usetwo); ++destwo) {
							int plus = 0;
							if (usetwo == 0 && useone == 0)plus = get<2>(musics[music]);
							else {
								plus += get<1>(musics[music])*useone;
								plus += get<0>(musics[music])*usetwo;
							}
							dp[music + 1][two - usetwo-destwo][usetwo+destwo] = max(dp[music + 1][two - usetwo-destwo][usetwo+destwo], dp[music][two][one] + plus);

						}
					}
				}
			}
		}
	}
	int ans = -1e9;
	for (int i = 0; i <= M; ++i) {
		for (int j = 0; j <= M; ++j) {
			ans = max(ans, dp[N][i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

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

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7,maxn = 100000000;
const double PI = acos(-1);

ll fexp(ll base, ll p){
    ll ans = 1;

    while (p){
        if (p&1) ans*= base;
        base*=base;
        p >>= 1;
    }
    return ans;
}


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    vector<pii> student(n), check(m);

    for (auto& it : student) cin >> it.ff >> it.ss;

    for (auto& it : check) cin >> it.ff >> it.ss;

    for (pii stu: student){
        int dist = oo, ans;
        for (int i=0; i<m; i++){
            if (abs(stu.ff - check[i].ff) + abs(stu.ss - check[i].ss) < dist){
                dist = abs(stu.ff - check[i].ff) + abs(stu.ss - check[i].ss);
                ans = i+1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
ll n,m;
vector<ll> dp;
vector<bool> a;

int main(){
  cin >> n >> m;
  a.resize(n+1,true);
  rep(i,m){
    ll tmp; cin >> tmp;
    a[tmp] = false;
  }
  dp.resize(n+1,0);
  dp[0] = 1;
  
  for(ll from = 0; from < n;from++){
    for(ll to = from+1; to <= min(n,from+2);to++){
      if(a[to]){
        dp[to] += dp[from]; dp[to] %= 1000000007; 
      }
    }
  }
//  rep(i,n+1){
//    cout << dp[i] << " ";
//  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 1024