akhauriyash/Code-Regression huggingface dataset:
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(__,v.size()){rep(_,v[__].size())cout<<" "<<v[__][_];cout<<endl;}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define MOD 998244353
int dp[200010][3][3][2];
signed main(){
	string s;
	cin>>s;
	int n=s.size();
	if(n==2){
		if(s[0]==s[1])cout<<1<<endl;
		else cout<<2<<endl;
		return 0;
	}else if(n==3){
		if(s[0]==s[1]&&s[1]==s[2])cout<<1<<endl;
		else if(s[0]==s[1]||s[1]==s[2])cout<<6<<endl;
		else if(s[0]==s[2])cout<<7<<endl;
		else cout<<3<<endl;
		return 0;
	}
	dp[0][0][0][0]=1;
	dp[0][1][1][0]=1;
	dp[0][2][2][0]=1;
	rep(i,n-1)rep(j,3)rep(k,3)rep(l,2)rep(x,3)
		(dp[i+1][(j+x)%3][x][l|k==x]+=dp[i][j][k][l])%=MOD;
	int co=0,h=0;
	rep(i,n){
		(co+=s[i]-'a')%=3;
		if(i)h+=s[i-1]==s[i];
	}
	if(h==n-1){
		cout<<1<<endl;
		return 0;
	}
	int out=!h;
	rep(i,3)(out+=dp[n-1][co][i][1])%=MOD;
	cout<<out<<endl;
}















Measured memory_bytes: 28676
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
	int N;
	cin >> N;
	vector<ll> A(N);
	vector<ll> Asum(N);
	for(int i = 0; i < N; i++) {
		cin >> A[i];
		A[i] -= i + 1;
	}
	

	if(N == 1) {
		cout << 0 << endl;
		return 0;
	} else if(N == 2) {
		cout << abs(A[0] - A[1]) << endl;
		return 0;
	}

	sort(A.begin(), A.end());
 
	Asum[0] = A[0];
	for(int i = 1; i < N; i++) {
		Asum[i] = Asum[i - 1] + A[i];
	}


	ll ans = LLINF;
	for(int i = 0; i < N - 1; i++) {
		if(A[i] == A[i + 1]) continue;

		int tmp = N - 2*i - 2;
		if(tmp > 0)
			ans = min(ans, Asum[N - 1] - 2*Asum[i] - tmp * A[i + 1]);
		 else if(tmp < 0)
			ans = min(ans, Asum[N - 1] - 2*Asum[i] - tmp * (A[i] + 1));
		 else
			ans = min(ans, Asum[N - 1] - 2*Asum[i]);
	}
	ans = min(ans, Asum[N - 1] - N * A[0]);
	ans = min(ans, N * (A[N - 1] + 1) - Asum[N - 1]);
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3328
class Main{
  public static void main(String[] args){
    java.util.Scanner sc = new java.util.Scanner(System.in);
    String[] arr = split(sc.next());
    
    int min = 753;
    for(String tar : arr){
      min = Math.min(min,diff753(tar));
    }
    
    System.out.println(min);
  }
  
  static String[] split(String s){
    String[] res = new String[s.length()-2];
    for(int i = 0 ; i < s.length() - 2; i++){
      res[i] = s.substring(i,i+3);
    }
    return res;
  } 
  
  static int diff753(String str){
    int tar = Integer.valueOf(str);
    return Math.abs(tar - 753);
  }
}

Measured memory_bytes: 21716
#include <stdio.h>



int main(void)
{
	//変数の宣言
	char name[15];
	int a=0;
	int c=0;
	int all=0;
	int i,j;
	int len;
	
	//データの読み込み
	scanf("%s",&name);
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	
	
	//実際の処理
	
	len = strlen(name);
	
	if(name[0]=='A'){
		a++;
	}
	
	for(i=2;i<len-1;i++){
		if(name[i]=='C'){
			c++;
		}
	}
	
	for(i=0;i<25;i++){
		for(j=0;j<len;j++){
			if(name[j]=='A'+i){
				all++;
			}
		}
	}
	
	
//	printf("計算部分終了\n");
	
	//出力
	
	if(a==1&&c==1&&all==2){
		printf("AC");
	}else{
		printf("WA");
	}
	
//	printf("結果の出力終了\n");
	
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL x;
    cin >> x;
    if(x==0){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }


    return 0;
}


Measured memory_bytes: 3620
import sys

# この２行は
#   a   1 0 1 0
#   b   1 1 0 0
# こうしても、作れる集合の内訳が変わらない
#   a   1 0 1 0
#   b^a 0 1 1 0
# {両方未選択, 上だけ選択, 下だけ選択, 両方選択}: {φ, a, b, a^b} == {φ, a, b^a, b}
# これは列方向に対しても同じことなので、掃き出し法チックなことをして
#   1 0 ... 0 0 0
#   0 1 ... 0 0 0
#   : :     : : :
#   0 0 ... 1 0 0
#   0 0 ... 0 0 0
# こんな形にできる
# ここで、行の選び方で'1'のある行を1つでも含むような選び方は、
# その'1'の場所の列(どれでもいいので1つ)を選択するかしないかで、
# 全体の和が偶数, 奇数となるパターンがちょうど半分ずつとなる。
# よって、以下が答え
# (行の全体の選び方 - '1'のある行を１つも含めない選び方) * 列の全体の選び方 / 2

n, m = map(int, input().split())
MOD = 998244353
rows = []
for line in sys.stdin:
    b = ''.join(line.rstrip().split())
    rows.append(int(b, base=2))

independent_row = 0
while rows:
    x = max(rows)
    if x == 0:
        break
    independent_row += 1
    y = 1 << (x.bit_length() - 1)
    rows = [r ^ x if r & y else r for r in rows if r != x]

ans = (pow(2, n + m - 1, MOD) - pow(2, n + m - independent_row - 1, MOD)) % MOD
print(ans)


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

using namespace std;

int main()
{
    //freopen("test.inp","r",stdin);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int dem = 0;
    while (s.find("ABC") != string::npos)
    {
        dem++;
        s.erase(s.find("ABC"), 3);
    }
    cout << dem;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    q = deque([s])
    dist = [-1]*N
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
                
                if s==V-1:
                    is_leaf[v] = False
        
    return dist

N, U, V = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)

is_leaf = [True]*N
d1 = bfs(V-1)
d2 = bfs(U-1)
ans = 0

for i in range(N):
    if not is_leaf[i] and d2[i]<=d1[i]:
        ans = max(ans, d1[i])
    
print(ans)

Measured memory_bytes: 64160
#include <bits/stdc++.h>
 
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<long long>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sll set<long long>
#define si set<int>
#define sti stack<int>
#define stkl stack<ll>
#define qi queue<int>
#define pb push_back
#define ff first
#define ss second
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll mod=1e9+7;
using namespace std;
int c=0;

void solve(){
	int n,l;
	cin>>n>>l;
	vector<string> a(n);
	for(int i=0;i<n;i++)
		cin>>a[i];

	sort(a.begin(), a.end());

	for(auto i:a)
		cout<<i;
	cout<<endl;

}
 
int main(){
    IOS;
    int q=1;
    //cin>>q;
    while(q--){
    	c++;
        solve();
    }
}


Measured memory_bytes: 3612
local mma = math.max
local s = io.read()
local n = #s
local a, b = {}, {}
for i = 1, n + 1 do a[i], b[i] = 0, 0 end
a[1] = 1
b[1] = 0
b[2] = 1
for i = 2, n do
  if s:sub(i - 1, i - 1) ~= s:sub(i, i) then
    a[i] = a[i - 1] + 1
  end
  a[i] = mma(a[i], b[i - 1] + 1)
  if 2 < i then
    b[i] = a[i - 2] + 1
    if 3 < i and s:sub(i - 3, i - 2) ~= s:sub(i - 1, i) then
      b[i] = mma(b[i], b[i - 2] + 1)
    end
  end
end
print(mma(a[n], b[n]))


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;

typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =998244353;
ll dp[1005][1005];
ll a[1005][1005];
ll pos[1005][1005];
ll calc(ll i,ll j)
{
	if(dp[i][j]!=-1)
		return dp[i][j];
	ll &res=dp[i][j];
		res=-2;

	if(calc(i,j-1)==-2||calc(a[i][j],pos[a[i][j]][i]-1)==-2)
	{
		cout<<-1;
		exit(0);
	}
	res=max(calc(i,j-1),calc(a[i][j],pos[a[i][j]][i])-1)+1;
	
	dp[a[i][j]][pos[a[i][j]][i]]=res;
	return res;


}
int main()
{	IOS
	 ll n;
	 cin>>n;
	 
	 for(ll i=1;i<=n;i++)
	 {
	 	for(ll j=1;j<=n-1;j++)
	 	{
	 		cin>>a[i][j];
	 		pos[i][a[i][j]]=j;
	 	}
	 }

	for(ll i=0;i<=n;i++)
	{
		for(ll j=0;j<=n;j++)
		{	
			if(j==0)
				dp[i][j]=0;
			else
				dp[i][j]=-1;
		}
	}	


	
	ll ans=0;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<n;j++)
		{	

			ans=max(calc(i,j),ans);
		}
	}
	cout<<ans;
	   


}
    
 
    
    


Measured memory_bytes: 23936
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int i,n,k,ans=1;
    cin>>n>>k;
    for(i=1;i<=n-1;i++){
    	ans*=(k-1);
    	
    }
    cout<<ans*k<<endl;
    return 0;
}

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

int main() {
  string s;
  cin>>s;
  int ans,cnt,e;
  ans=0;
  cnt=0;
  e=s.size();
  for(int i=2;i<=e-2;i++) {
    if(s.at(i)=='C') {
      ans++;
    }
  }
  for(int i=0;i<e;i++) {
    if(isupper(s.at(i))) {
      cnt++;
    }
  }
  if(s.at(0)=='A'&&ans==1&&cnt==2) {
    cout<<"AC"<<endl;
  }
  else {
    cout<<"WA"<<endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main (String args[]){
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long x= sc.nextLong();
		long[] a = new long[2*(int)n];
		for (int i = 0; i<n; i++) {
			a[i]=sc.nextLong();
			a[i+(int)n]=a[i];
		}
		long[][] costs = new long[(int)n][(int)n];
		for (int i = (int)n; i<2*n; i++) {
			long best=a[i];
			for (int j=0; j<n; j++) {
				best=Math.min(best, a[i-j]);
				costs[i-(int)n][j]=best;
			}
		}
		long best = n*1000000000;
		for (int j = 0; j<n;j++) {
			long curr = j*x;
			for (int i = 0; i<n; i++) {
				curr+=costs[i][j];
			}
			best=Math.min(best, curr);
		}
		System.out.println(best);
	}
}

Measured memory_bytes: 43520
#include <stdio.h>
#define MAX 10000

int main(){
	int i,j;
	int n1,n2,cnt;
	int num1[MAX],num2;
	
	scanf("%d",&n1);
	for(i=0;i<n1;i++){
		scanf("%d",&num1[i]);
	}
	
	cnt = 0;
	scanf("%d", &n2);
	while(n2--){ //インクリメントを後置に変更
		scanf("%d", &num2);
		for(j = 0; j < n1; ++j) {
			if(num1[j] == num2) {
			++cnt;
			
			break;
			}
		}	
	}
  	printf("%d\n", cnt);
 	return 0;
}


Measured memory_bytes: 2052
#include <bits/stdc++.h>
#define optimize ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long
#define ld long double
#define vi vector<int>
#define si set<int>
#define vc vector<char>
#define vll vector<ll>
#define vd vector<double>
#define pb push_back
#define lp(i,a,b) for(int i = a ; i <= b ; i ++)
#define rlp(i,a,b) for(int i = b ; i >= a ; i --)
#define a_sort(v) sort(v.begin(), v.end())
#define d_sort(v) sort(v.rbegin(), v.rend())
#define pii pair<int,int>
#define pi 3.14159265358979323846264338327950
using namespace std ;
// #define debug

const int MOD = 1E9 + 7 ;
const int N = 1E5 ;

void g(ll t){if(t){g((t-1)/26);putchar(97+(t-1)%26);}}
int main() {
    #ifdef debug
    freopen("input.txt", "r", stdin) ;
    freopen("output.txt", "w", stdout) ;
    #endif // debug
    optimize

    ll col ; cin >> col ;
    g(col) ;
}


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

int main(void){
    int n,a,b;
    int min,max;
    cin >> n >> a >> b;
    if(a >= b){
        max = b;
    }else{
        max = a;
    }
    
    min = a + b - n;
    if(min < 0){
        min = 0;
    }

    cout << max << " " << min;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct unionfind {
    vector<int> par, t;
    vector<ll> s;
    unionfind(int n)
        : par(n, -1), s(n), t(n) {}

    int find(int x) {
        if (par[x] < 0)
            return x;
        else
            return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        s[x] += s[y];
        t[x] += t[y];
        par[y] = x;
    }
    int size(int x) {
        return -par[find(x)];
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<ll> x(n), y(m);
    vector<pair<ll, pair<int, int>>> p(m);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b >> y[i];
        a--, b--;
        p[i] = {y[i], {a, b}};
    }
    sort(p.begin(), p.end());
    unionfind dsu(n);
    for (int i = 0; i < n; i++) {
        dsu.s[i] = x[i];
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int a, b;
        tie(a, b) = p[i].second;
        dsu.unite(a, b);
        int q = dsu.find(a);
        dsu.t[q]++;
        if (dsu.s[q] >= p[i].first) {
            ans += dsu.t[q];
            dsu.t[q] = 0;
        }
    }
    cout << m - ans << endl;
    return 0;
}

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  for (int i = A; i <= B; i++) {
    if (i >= A + K && i <= B - K) continue;
    cout << i << endl;
  }
}


Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int main()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    rep(i,n){
        cin >> vec[i];
    }
    int MAX = *max_element(vec.begin(), vec.end());
    int MIN = *min_element(vec.begin(), vec.end());
    cout << abs(MAX - MIN) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
constexpr int64_t MOD = 1000000007;

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

  //std::string S;
  //cin >> S;
  int32_t N;
  cin >> N;

  vector<int> P(N);
  for (int i = 0; i < N; i++) {
    cin >> P[i];
  }
  vector<int> Q(N);
  for (int i = 0; i < N; i++) {
    cin >> Q[i];
  }
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    vec[i] = i + 1;
  }
  vector<int> big;
  vector<int> small;
  bool same = true;
  for (int i = 0; i < N; i++) {
    if (P[i] > Q[i]) {
      big = P;
      small = Q;
      same = false;
      break;
    } else if (P[i] < Q[i]) {
      big = Q;
      small = P;
      same = false;
      break;
    }
  }
  if (same) {
    cout << 0 << endl;
    return 0;
  }

  int64_t cnt = 0;
  int64_t s = -1;
  int64_t t = -1;
  do {
    if (s == -1) {
      bool found = true;
      for (int i = 0; i < N; i++) {
        if (small[i] != vec[i]) {
          found = false;
          break;
        }
      }
      if (found) {
        s = cnt;
        cnt++;
      } else {
        cnt++;
      }
    }
    else {
      bool found = true;
      for (int i = 0; i < N; i++) {
        if (big[i] != vec[i]) {
          found = false;
          break;
        }
      }
      if (found) {
        t = cnt;
        break;
      } else {
        cnt++;
      }
    }
  } while(next_permutation(vec.begin(), vec.end()));

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


Measured memory_bytes: 256
A,B,C = map(int,input().split())
K = int(input())
for bit in range(1<<K):
    Bt = B
    Ct = C
    for i in range(K):
        if bit & (1<<i): #Bの場合
            Bt *= 2
        else:
            Ct *= 2
    if  A<Bt and Bt<Ct:
        print('Yes')
        exit()
print('No')

Measured memory_bytes: 61664
// https://atcoder.jp/contests/abc079/tasks/abc079_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    // リュカ数
    vector<ll> fib(87);
    fib[0] = 2;
    fib[1] = 1;
    FOR(i, 2, 87) fib[i] = fib[i - 1] + fib[i - 2];
    cout << fib[n] << endl;

    return 0;
}


Measured memory_bytes: 256
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<string>
#include<math.h>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
using namespace std;
const int INF=100000000;
char a[20][20];
int h,w;
void dfs(int x,int y){
  if(x<0||y<0||x>=w||y>=h)return ;
  if(a[y][x]=='.'){
    a[y][x]='$';
  }else return ;
  dfs(x+1,y);
  dfs(x-1,y);
  dfs(x,y+1);
  dfs(x,y-1);
}
int main(){
  while(cin>>w>>h,h!=0){
    int sx,sy;
    rep(i,h)rep(j,w){
      cin>>a[i][j];
      if(a[i][j]=='@')sx=j,sy=i;
    }
    int ans=0,k=0;
    a[sy][sx]='.';
    dfs(sx,sy);
    rep(i,h){
      rep(j,w){
	if(a[i][j]=='$')ans++;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3000
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int[] T = new int[N];
		int[] X = new int[N];
		int[] Y = new int[N];
		for(int i = 0;i < N;i++) {
			T[i] = Integer.parseInt(sc.next());
			X[i] = Integer.parseInt(sc.next());
			Y[i] = Integer.parseInt(sc.next());
			if(!(T[i]%2==(X[i] + Y[i])%2)
					|| X[i] + Y[i] > T[i]) {
				System.out.println("No");
				sc.close();
				return;
			}
		}
		sc.close();
		System.out.println("Yes");
	}
}

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

#define ll long long 
#define sz(x) ((int)x.size())
#define inf (1000*1000*1000+9)
#define infl (1ll*inf*inf)
#define all(a) a.begin(),a.end()
#define fast_io ios_base::sync_with_stdio(NULL); cin.tie(NULL)


void solve(){
	ll a,b; cin>>a>>b; 
	ll g=__gcd(a,b); 
	int c=0; 
	for(ll d=2;d*d<g;d++){
		if(g%d==0) c++; 
		while(g%d==0) g/=d; 
	}	
	if(g>1) c++; 
	cout<<c+1<<endl; 
}

int main(){
	clock_t beg=clock(); 
	fast_io; 
	solve(); 	
	clock_t end=clock(); 
	fprintf(stderr, "%lf\n", (double)(end-beg)/(CLOCKS_PER_SEC));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)x.size())

int main() {
    ll nax=1e5+7;
    int A,B,q;
    ll a[nax],b[nax];
		cin>>A>>B>>q;
		rep(i,0,A) cin>>a[i];
		rep(i,0,B) cin>>b[i];
		sort(a,a+A);
		sort(b,b+B);
		rep(i,0,q) {
			ll x,ans=1e17;
			cin>>x;
			int p1=lower_bound(a,a+A,x)-a;
			int p2=lower_bound(b,b+B,x)-b;
			if(p1>0&&p2>0) ans=min(ans,x-min(a[p1-1],b[p2-1]));
			if(p1<A&&p2<B) ans=min(ans,max(a[p1],b[p2])-x);
			if(p1>0&&p2<B) ans=min(ans,min(abs(x-a[p1-1]),abs(x-b[p2]))*2+max(abs(x-a[p1-1]),abs(x-b[p2])));
			if(p2>0&&p1<A) ans=min(ans,min(abs(x-a[p1]),abs(x-b[p2-1]))*2+max(abs(x-b[p2-1]),abs(x-a[p1])));
			cout<<ans<<'\n';
		}
		return 0;
}


Measured memory_bytes: 2816
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

//

int32_t main() {
  FAST_IO;
  int n;
  str s, t;
  cin >> n >> s >> t;
  str ans = "";
  rep(i, n) {
    ans += s[i];
    ans += t[i];
  }
  cout << ans << '\n';
  rtn 0;
}


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

using namespace std;

int a[5][5],c[5][5];

int main(int argc, char *argv[]) {
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++) {
			cin>>c[i][j];	
			a[i][j]=c[i][i];
		}
	sort(*(a+1)+1,*(a+3)+4);
	int flag=0;
	for(int a1=0;a1<=a[3][3];a1++) 
		for(int a2=0;a2<=a[3][3];a2++) 
			for(int a3=0;a3<=a[3][3];a3++) 
				for(int b1=0;b1<=a[3][3];b1++) {
					if((a1+b1)!=c[1][1]||(a2+b1)!=c[2][1]||(a3+b1)!=c[3][1])
						continue;
					else
						for(int b2=0;b2<=a[3][3];b2++) {
							if((a1+b2)!=c[1][2]||(a2+b2)!=c[2][2]||(a3+b2)!=c[3][2])
								continue;
							else
								for(int b3=0;b3<=a[3][3];b3++) {
									if(a1+b3==c[1][3]&&a2+b3==c[2][3]&&a3+b3==c[3][3]) {
										//cout<<a1<<" "<<a2<<" "<<a3<<" "<<b1<<" "<<b2<<" "<<b3<<endl;
										cout<<"Yes"<<endl;
										flag=1;
										return 0;	
									}	
								}
						}	
				}
	cout<<"No"<<endl;
	return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
    string s;
    cin >> s;
    int a = 0, b = 0, c = 0;
    int n = sz(s);
    rep(i,n) {
        if(s[i] == 'a') a++;
        if(s[i] == 'b') b++;
        if(s[i] == 'c') c++;
    }
    if(max({a,b,c}) - min({a,b,c}) <= 1) 
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

Measured memory_bytes: 3760
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = N/1000;
        int B = (N/100)%10;
        int C = (N/10)%10;
        int D = N%10;
        
        if(A+B+C+D==7){
        	System.out.println(A+"+"+B+"+"+C+"+"+D+"=7");
        }else if(A+B+C-D==7){
        	System.out.println(A+"+"+B+"+"+C+"-"+D+"=7");
        }else if(A+B-C+D==7){
        	System.out.println(A+"+"+B+"-"+C+"+"+D+"=7");
        }else if(A+B-C-D==7){
        	System.out.println(A+"+"+B+"-"+C+"-"+D+"=7");
        }else if(A-B+C+D==7){
        	System.out.println(A+"-"+B+"+"+C+"+"+D+"=7");
        }else if(A-B+C-D==7){
        	System.out.println(A+"-"+B+"+"+C+"-"+D+"=7");
        }else if(A-B-C+D==7){
        	System.out.println(A+"-"+B+"-"+C+"+"+D+"=7");
        }else if(A-B-C-D==7){
        	System.out.println(A+"-"+B+"-"+C+"-"+D+"=7");
        }
    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#define ll long long
using namespace std;
const int MAXN = 200005, MAXM = 40;

struct Node
{
    ll a, b;
};

int cmp(Node &n1, Node &n2)
{
    return n2.a * n1.b + n2.a < n1.a * n2.b + n1.a;
}

vector<int> A;
vector<Node> B;
ll fa[MAXN], fb[MAXM];

int main()
{
    int n, t;
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i++)
    {
        ll a, b;
        scanf("%lld%lld", &a, &b);
        if (a == 0) A.push_back(b);
        else B.push_back({ a, b });
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), cmp);

    for (int i = 1; i < MAXM; i++) fb[i] = 1e15;
    for (int i = 0; i < B.size(); i++)
    {
        for (int j = MAXM - 1; j >= 0; j--)
        {
            if (fb[j] > t) continue;
            fb[j + 1] = min(fb[j + 1], fb[j] + 1 + (fb[j] + 1) * B[i].a + B[i].b);
        }
    }

    for (int i = 1; i <= A.size(); i++)
        fa[i] = fa[i - 1] + A[i - 1] + 1;
    
    int ans = 0;
    for (int i = 0; i <= A.size(); i++)
    {
        for (int j = 0; j <= MAXM - 1; j++)
        {
            if (fa[i] + fb[j] <= t)
                ans = max(ans, i + j);
        }
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 6512
import math
k = int(input())
if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    a = 0
    result = -1
    for i in range(k):
        a = (a*10 + 7)%k
        if a == 0:
            result = i+1
            break

    print(result)


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

using namespace std;

typedef long long ll;

vector<ll> a;
vector<ll> p;

ll f(ll n, ll x) {
    if(n==0)
        return 1;
    if(x==1)
        return 0;
    if(x <= 1 + a[n-1]) {
        return f(n-1,x-1);
    }
    if(x == a[n-1]+2) {
        return p[n-1] + 1;
    }
    return p[n-1] + 1 + f(n-1, x-2-a[n-1]);
}

int main() {
    ll n,x; cin >> n >> x;
    a.push_back(1);
    p.push_back(1);
    for(int i = 1; i <= n; i++) {
        a.push_back(a[i-1]*2 + 3);
        p.push_back(p[i-1]*2 + 1);
    }

    cout << f(n, x) << endl;
}


Measured memory_bytes: 256
n = gets.chomp
k = gets.chomp.to_i

size = n.size

dp = Array.new(size + 1) { Array.new(2) { Array.new(k + 2, 0)} }
dp[0][0][0] = 1

size.times do |i|
  2.times do |s|
    (k + 1).times do |j|
      l = s.zero? ? n[i].to_i : 9
      (l + 1).times do |d|
        dp[i+1][!s.zero? || d < l ? 1 : 0][d.zero? ? j : j + 1] += dp[i][s][j]
      end
    end
  end
end

puts dp[size][0][k] + dp[size][1][k]

Measured memory_bytes: 3836
#include<iostream>
#include<algorithm>
using namespace std;
int main(){int n,d[100],i=0,a=1;cin>>n;for(;i<n;i++)cin>>d[i];sort(d,d+n);for(i=n-2;i>=0;i--)if(d[i]!=d[i+1])a++;cout<<a;}


Measured memory_bytes: 256
s = input()
K = int(input())
subs = []
for i in range(0, len(s)):
    for j in range(i+1, K+i+1 if i + K <= len(s) else len(s)+1):
        subs.append(s[i:j])
subs = list(set(subs))
subs.sort()
print(subs[K-1])

Measured memory_bytes: 5068
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

q = ii()
rmax = 0
qer = []
for i in range(q):
    l,r = mi()
    qer.append([l,r])
    if rmax < r:
        rmax = r

# rmaxまで計算
# 奇数かつ4n-1ではない
# 4n+1

# 素数表
import math
primeList = [2,3,5,7,11,13]
for i in range(17,rmax+1,2):
    for j in primeList:
        if j > math.sqrt(i):
            primeList.append(i)
            break
        if i % j == 0:
            break

# print(primeList)
        
def checksim(x,pl):
    if x in pl and (x+1)//2 in pl:
        return 1
    return 0

tans = [0] * (rmax+1)
tans[3] = 1
for i in range(5,rmax+1,4):
    if checksim(i, primeList):
        tans[i] = 1

# cumsum
ans = [0]*(rmax+1)
tcumsum = 0
for i in range(rmax+1):
    if tans[i] == 1:
        tcumsum += 1
    ans[i] = tcumsum

for i in qer:
    print(ans[i[1]] - ans[i[0]-1])

Measured memory_bytes: 91092
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdint>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <cstdlib>
#include <sstream>

#include <boost/range/irange.hpp>
using boost::irange;

#include <boost/utility/string_ref.hpp>
using boost::string_ref;

using namespace std;

template<class T, size_t N, class F>
struct compare_n
{
    bool operator() (const T& t1, const T& t2, const F& f)
    {
        return f(get<N>(t1), get<N>(t2));
    }
};

template<class T>
using less_1st = compare_n<T, 0, less<T>>;

template<class T>
using less_2nd = compare_n<T, 1, less<T>>;

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

    int a,b,c;
    cin >> a >> b >> c;
    
    const int m = max(a, max(b, c));
    const int x = 3 * m % 2 == (a + b + c) % 2 ? m : m + 1;
    
    cout << ((3 * x - a - b - c) / 2) << '\n';

    return 0;
}



Measured memory_bytes: 256
def run():
  ofs = 1000
  H, W = map(int, input().split())
  dp = [[0 for w in range(W)] for h in range(H)]
  a = [list(map(int, input().split())) for i in range(H)]
  b = [list(map(int, input().split())) for i in range(H)]
  c = [[abs(a[i][j] - b[i][j]) for j in range(W)] for i in range(H)]
  dp[0][0] = (1 << ofs + c[0][0]) | (1 << ofs - c[0][0])
  for h in range(1, H):
    dp[h][0] = (dp[h-1][0] << c[h][0]) | (dp[h-1][0] >> c[h][0])
  for w in range(1, W):
    dp[0][w] = (dp[0][w-1] << c[0][w]) | (dp[0][w-1] >> c[0][w])
  for h in range(1, H):
    for w in range(1, W):
      v = c[h][w]
      dp[h][w] = (dp[h-1][w] << v) | (dp[h-1][w] >> v)
      dp[h][w] |= (dp[h][w-1] << v) | (dp[h][w-1] >> v)
  s = list(bin(dp[-1][-1] >> ofs))
  for i in range(len(s)):
    if s[-1-i] == '1':
      print(i)
      break

if __name__ == '__main__':
  run()

Measured memory_bytes: 9832
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] l = new int [n];
        int[] r = new int [n];
        for (int i = 0; i < n; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += r[i] - l[i] + 1;
        }
        System.out.println(ans);
    }
}

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


int main(void){
    int x , a;

    cin >> x >> a;

    if(x<a){
        cout << 0;
    }else
    {
        cout << 10;
    }
    
    
    return 0;
}

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

int main() {
  string A, B, C; cin >> A >> B >> C;
  
  if (A[A.size() - 1] == B[0] && B[B.size() - 1] == C[0]) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
  return 0;
}

Measured memory_bytes: 256
S=input()
T=input()

Rs = {}
Rt = {}

for s,t in zip(S,T):
    
    if s in Rs.keys() and Rs[s] != t:
        print("No")
        exit()
    if t in Rt.keys() and Rt[t] != s:
        print("No")
        exit()

    if not s in Rs.keys():
        Rs[s] = t
    if not t in Rt.keys():
        Rt[t] = s

ress = [""] * len(S)
rest = [""] * len(S)
for i,s in enumerate(S):
    ress[i] = Rs[s]

for i,t in enumerate(T):
    rest[i] = Rt[t]
print("Yes" if "".join(ress)==T and "".join(rest)==S else "No")

Measured memory_bytes: 6704
#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 N;
  double ans = 0.0, A;
  cin >> N;
  rep(i, N){
    cin >> A;
    ans += 1.0 / A;
  }
  ans = 1.0 / ans;
  cout << setprecision(16) << ans << endl;
}

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

const int INF = 1 << 28;

int n, d, x;
int p[10][10];
int dp[100010];

int main()
{
	cin >> n >> d >> x;
	for (int i = 0; i < d; i++){
		for (int j = 0; j < n; j++){
			cin >> p[i][j];
		}
	}

	for (int i = 0; i < d - 1; i++){
		for (int j = 0; j <= x; j++){
			dp[j] = j;
		}
		for (int j = 0; j < n; j++){
			for (int k = p[i][j]; k <= x; k++){
				dp[k] = max(dp[k], dp[k - p[i][j]] + p[i + 1][j]);
			}
		}
		int t = 0;
		for (int k = 0; k <= x; k++){
			t = max(t, dp[k]);
		}
		x = t;
	}

	cout << x << endl;
}

Measured memory_bytes: 3176
n = int(input())
d = list(map(int, input().split()))
c = [0, 0, 0]
for x in d:
	if x % 4 == 0:
		c[2] += 1
	elif x % 2 == 0:
		c[1] += 1
	else:
		c[0] += 1

# print(c)
if c[0] - 1 <= c[2] and c[1] == 0:
	print("Yes")
elif c[0] > c[2]:
	print("No")
else:
	print("Yes")

# 0 2 0 1
# 1 1 2 0 2 0 2 0 2 1 1
# 1 1 1 1  

Measured memory_bytes: 14352
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')

def main():
  a, b = map(int, readline().split())
  print(max(a+a-1,a+b,b+b-1))
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 5076
from collections import Counter

R = lambda: map(int, input().split())
R()
d = Counter(R())
s = sum(k * v for k,v in d.items())
q, = R()
for _ in range(q):
  b, c = R()
  s += (c - b) * d[b]
  print(s)
  d[c]+=d[b]
  d[b] = 0


Measured memory_bytes: 22188
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse

int main () {

    ll n,a,b;cin>>n>>a>>b;

    ll cur,ans=0;

    rep(i,n) {
        ll x;cin>>x;
        if (i==0) {
            cur=x;
        } else {
            ans+=min(a*(x-cur),b);
            cur=x;
        }
    }

    cout<<ans<<endl;

}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

S = input()

for i in range(len(S)):
	if S[i] == "A":
		left = i
		break

for i in range(len(S)-1, -1, -1):
	if S[i] == "Z":
		right = i
		break

print(right-left+1)

Measured memory_bytes: 13968
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

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

  int A[n];
  int B[n];
  int C[n];

  for (int i = 0; i < n; i++)
  {
    cin >> A[i];
  }
  for (int i = 0; i < n; i++)
  {
    cin >> B[i];
  }
  for (int i = 0; i < n-1; i++)
  {
    cin >> C[i];
  }
  
  int res = 0;
  for (int i = 0; i < n; i++)
  {
    res += B[A[i]-1];

    if(i > 0 && A[i]-A[i-1]==1){
      res += C[A[i-1]-1];
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
N =int(input())
ab =[[int(i)for i in input().split()]for _ in range(N)]
ab.sort(key=lambda x:x[1])
t=0
sta = True
for a,b in ab:
    t += a
    if t > b:
        sta =False
        break
if sta:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 41176
/**
 * Created by hiramekun at 10:43 on 2019-10-18.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n, m;
    cin >> n >> m;
    vl imos(n);
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        imos[a]++, imos[b]--;
    }

    ll now = 0;
    rep(i, n - 1) {
        now += imos[i];
        if (now % 2 != 0) {
            cout << "NO" << '\n';
            return;
        }
    }
    cout << "YES" << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#include <climits>
#include <memory>
#include <numeric>
#include <utility>


#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
#define PI 3.14159265358979323846264338327950L;
const int INF2 = 1001001001;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;



int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 2 == 0) {
		x /= 2;
		ret++;
	}

	return ret;
}

int a[12][12];
int D;
ll G;
vector<ll> P, C;

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

	cin >> a >> k;
	

	cout << a+1-k << endl;


	

}
	

Measured memory_bytes: 256
a = int(input())
l = list(map(int,input().split()))

b = sum((i % 2 != 0)  for i in l)
bb = sum((i % 2 == 0)  for i in l)
bbbb  = sum((i % 4 == 0)  for i in l)

bb -= bbbb
if bbbb+1 >= b + (bb != 0):print("Yes")
else:print("No") 

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

/*
long long cp(vector<long long> a, vector<long long> b, long long n, long long k){
	long long mod=1000000007;
	if(k<0 || k>n){
		return 0;
	}else{
		return (((a[n]*b[k])%mod)*b[n-k])%mod;
	}
	
}
*/

int main() {
	long long n,i,j,k,l,r,ans,cur,key,mod=1000000007;
	cin >> n;
	vector<long long> a(n+2),b(n+2),c(32);
	
	for(i=1; i<=n+1; i++){
		cin >> cur;
		if(a[cur]==0){
			a[cur]=i;
		}else{
			l=a[cur]; r=i; break;
		}
	}

    a[0]=1; b[0]=1;
    for(i=1; i<=n+1; i++){
      a[i]=(a[i-1]*i)%mod;
    }
    c[0]=a[n+1];
    
    cur=mod-2;
    b[n+1]=1;
    for(i=1; i<32; i++){
    	if(cur%2){
    		b[n+1]=(b[n+1]*c[i-1])%mod;
    	}
    	c[i]=c[i-1]*c[i-1]%mod;
    	cur/=2;
    }
    
    
    for(i=n; i>=0; i--){
    	b[i]=(b[i+1]*(i+1))%mod;
    }
    
	for(k=1; k<=n+1; k++){
		if(k-1>l+n-r){
			cout << (((a[n+1]*b[k])%mod)*b[n+1-k])%mod << endl;
		}else{
			cur=(((a[n+1]*b[k])%mod)*b[n+1-k])%mod-(((a[l+n-r]*b[k-1])%mod)*b[l+n-r-k+1])%mod;
			if(cur<0) cur+=mod;
			cout << cur << endl;
		}
		//cout << cp(n+1,k) - cp(a,b,l+n-r,k-1) << endl;
	}
	
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
 
void solve(){
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(a * n,b); 
}
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

Measured memory_bytes: 256
import math
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))

hq = []
for i in range(n):
  heapq.heappush(hq, a[i]*(-1))

for i in range(m):
  b = heapq.heappop(hq)
  b = ((-1)*b)//2
  heapq.heappush(hq, b*(-1))

ans = 0
for i in hq:
  ans += i *(-1)
print(ans)


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

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

const double EPS = 1e-14;
const double PI  = acos(-1.0);


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

  vector<int> v(n);
  REP (i, n) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());

  vector<int> x;

  x.push_back(v[0]);
  int l = 1;
  int r = n - 1;
  while (l <= r) {
    int lb = abs(v[l] - *x.begin());
    int le = abs(v[l] - *(x.end() - 1));
    int rb = abs(v[r] - *x.begin());
    int re = abs(v[r] - *(x.end() - 1));
    if (le <= lb && rb <= lb && re <= lb) {
      x.insert(x.begin(), v[l]);
      l++;
    } else if (lb <= le && rb <= le && re <= le) {
      x.push_back(v[l]);
      l++;
    } else if (lb <= rb && le <= rb && re <= rb) {
      x.insert(x.begin(), v[r]);
      r--;
    } else {
      x.push_back(v[r]);
      r--;
    }
  }

  LL ans = 0;
  FOR (i, 1, x.size()) {
    ans += abs(x[i] - x[i - 1]);
  }

  cout << ans << endl;

}


Measured memory_bytes: 1276