akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;
long long MOD = 1000000007;
long long modpow(long long a, long long b){
	long long ans = 1;
	while (b > 0){
		if (b % 2 == 1){
			ans *= a;
			ans %= MOD;
		}
		a *= a;
		a %= MOD;
		b /= 2;
	}
	return ans;
}
long long modinv(long long a){
	return modpow(a, MOD - 2);
}
vector<long long> mf = {1};
vector<long long> mfi = {1};
long long modfact(int n){
	if (mf.size() > n){
		return mf[n];
	} else {
		for (int i = mf.size(); i <= n; i++){
			long long next = mf.back() * i % MOD;
			mf.push_back(next);
			mfi.push_back(modinv(next));
		}
		return mf[n];
	}
}
long long modfactinv(int n){
	if (mf.size() > n){
		return mfi[n];
	} else {
		return modinv(modfact(n));
	}
}
int main(){
	int N, A, B, C, D;
	cin >> N >> A >> B >> C >> D;
	vector<vector<long long>> binom(N + 1, vector<long long>(N + 1, 0));
	for (int i = 0; i <= N; i++){
		binom[i][0] = 1;
		binom[i][i] = 1;
	}
	for (int i = 2; i <= N; i++){
		for (int j = 1; j < i; j++){
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
		}
	}
	vector<long long> dp(N + 1, 0);
	dp[0] = 1;
	for (int i = A; i <= B; i++){
		for (int j = N; j >= 0; j--){
			long long tmp = dp[j];
			for (int k = 0; k <= D; k++){
				if (j + i * k > N){
					break;
				}
				if (k >= C){
					dp[j + i * k] += tmp * modfactinv(k) % MOD;
					dp[j + i * k] %= MOD;
				}
				tmp *= binom[N - j - i * k][i];
				tmp %= MOD;
			}
		}
	}
	cout << dp[N] << endl;
}

Measured memory_bytes: 11472
import sys

input = sys.stdin.readline



S = input()
T = input()

S = S.replace('\n','')
T = T.replace('\n','')

s_list = list(S)
t_list = list(T)

itti = 0
min_count = 10**5
for i in range(len(s_list)):
    if i + len(t_list) > len(s_list):
        break
    count = 0
    for j in range(len(t_list)):
        if not s_list[i+j] == t_list[j]:
            count += 1
    min_count = min(count,min_count)

print(min_count)

Measured memory_bytes: 9020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;

int main() {
  ll A,B,C,K;
  cin >> A >> B >> C >> K;
  if (K % 2 == 0) {
    cout << A - B << endl;
  } else {
    cout << B - A << endl;
  }
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<long long> A(N);
  for (int i=0; i < N; i++){
    cin >> A.at(i);
  }
  
  for (int i = 0; i<N; i++){
    if (A.at(i) == 0){
      cout << 0 << endl;
      return 0;
    }
  }

  long long ans, limit;
  ans = 1;
  limit = 10;
  for (int i=1; i<18;i++)
    limit *= 10;
  
  for (int i=0; i < N; i++){
    if (limit / A.at(i) < ans) {
      cout << -1 << endl;
      return 0;
    }  
    ans *= A.at(i);
  }
  cout << ans << endl;
}

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

using namespace std;

int main() {
  int N, M;
  
  cin >> N >> M;
  
  int L_max = -1, R_min = N;
  
  for (int i = 0; i < M; i++) {
    int in_L, in_R;
    
    cin >> in_L >> in_R;
    
    L_max = max(L_max, in_L);
    R_min = min(R_min, in_R);
  }
  
  if (R_min >= L_max) {
    cout << (R_min - L_max + 1) << endl;
  } else {
    cout << 0 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define pq 	priority_queue<int, vector<int>, greater<int> >
using namespace std;

int main()
{
ll n;
cin>>n;
ll h[n+1];h[0]=0;
for(ll i=1;i<n+1;i++)

{
cin>>h[i];}
ll dp[n+5]={0};
dp[1]=0;
dp[2]=abs(h[1]-h[2]);
for(ll i=3;i<n+1;i++)
{
	dp[i]=min((abs(h[i]-h[i-1])+dp[i-1]),(abs(h[i]-h[i-2])+dp[i-2]));
}

cout<<dp[n];
	
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define MOD (1000000007l)
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)

using namespace std;

ll calc_gcd(ll a, ll b) {
  while (true)
    if (a)
      b %= a, swap(a, b);
    else
      return b;
}

ll calc_lcm(ll a, ll b) { return a * b / calc_gcd(a, b); }

void solve() {
  ll a, b;
  cin >> a >> b;
  cout << calc_lcm(a, b) << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}


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

int main()
{
    int a,b,c,d;

    scanf("%d%d",&a,&b);
    scanf("%d%d",&c,&d);

    printf("%d\n",(a*b)-((b*c)+((a-c)*d)));


    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = [int(input()) for _ in range(n)]
s_0 = [num for num in s if num % 10 != 0]
if len(s_0) == 0: print(0)
elif sum(s) % 10 == 0: print(sum(s) - min(s_0))
else: print(sum(s))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define puts(i) cout<<i<<endl
#define pi 3.14159265358979323846264338
#define pb push_back
#define mp make_pair
#define inf 10000
using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;

ll divisor=1000000007;

int main(){
	int n;
	cin>>n;
	int a[n];
	rep(i,n)cin>>a[i];
	int x=0;
	rep(i,n)x^=a[i];
	rep(i,n){
		int ans=x^a[i];
		puts(ans);
	}
}


Measured memory_bytes: 4292
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<vector> 
#include<algorithm> 
#define N 10005 
#define LL long long 
#define inf 1<<29 
#define eps 1e-7 
using namespace std; 
vector<int>v[100005]; 
int get_sg(int u,int pre){ 
    int ret=0; 
    for(int i=0;i<v[u].size();i++){ 
        if(v[u][i]!=pre) 
            ret^=(1+get_sg(v[u][i],u)); 
    } 
    return ret; 
} 
int main(){ 
    int n; 
  
        scanf("%d",&n); 
        for(int i=1;i<=n;i++) 
            v[i].clear(); 
        for(int i=1;i<n;i++){ 
            int x,y; 
            scanf("%d%d",&x,&y); 
            v[x].push_back(y); 
            v[y].push_back(x); 
        } 
        if(get_sg(1,-1)) 
            puts("Alice"); 
        else 
            puts("Bob"); 
     
    return 0; 
} 

Measured memory_bytes: 11904
"""
参考
blog名  あっとのTECH LOG   2020-01-24 
url     https://at274.hatenablog.com/entry/2020/01/24/060000
id:     AT274
"""

#初期入力
N = int(input())
 
#
import numpy as np
count = np.zeros((10,10),dtype=np.int64) 
for i in range(1,N+1):
    n_left =str(i)[0]   #左端の数字（N)
    n_right =str(i)[-1] #右端の数字（N)
    count[int(n_left) , int(n_right)] +=1

count_T_copy =count.T.copy()
ans =np.sum(count *count_T_copy)
print(ans)

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

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

    int n;
    cin >> n;
    for (int i = 1; i <= 50000; i++) {
        if ((int)(i * 1.08) == n) {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}


Measured memory_bytes: 256
void main()
{
    long n, m, d;
    rdVals(n, m, d);

    double result = (m - 1) * (d ? 2 * (n - d) : n).to!double;
    result /= n, result /= n;

    writefln("%.15f", result);
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;
enum double eps = 1.0e-9;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

char S[SIZE];

ll dp[SIZE][4];

int main(){

	scanf("%s",S);

	ll len;
	for(len = 0; S[len] != '\0'; len++);

	for(int i = 0; i <= len; i++){
		for(int k = 0; k < 4; k++){

			dp[i][k] = 0;
		}
	}

	dp[0][0] = 1;

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

		//状態を進めない
		for(int k = 0; k <= 3; k++){
			if(S[i] != '?'){

				dp[i+1][k] += dp[i][k];
				dp[i+1][k] %= MOD;

			}else{

				dp[i+1][k] += 3*dp[i][k];
				dp[i+1][k] %= MOD;
			}
			//printf("dp[%d][%d]:%lld\n",i,k,dp[i][k]);
		}

		//状態を進める
		if(S[i] == 'A' || S[i] == '?'){

			dp[i+1][1] += dp[i][0];
			dp[i+1][1] %= MOD;

		}
		if(S[i] == 'B' || S[i] == '?'){

			dp[i+1][2] += dp[i][1];
			dp[i+1][2] %= MOD;

		}
		if(S[i] == 'C' || S[i] == '?'){

			dp[i+1][3] += dp[i][2];
			dp[i+1][3] %= MOD;
		}
	}

	printf("%lld\n",dp[len][3]);

	return 0;
}


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

typedef long long ll;
typedef char keytype;

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

/* a[0], ..., a[n-1] の数の最大公約数 */
int ngcd(int n, int a[])
{
    int i, d;

    d = a[0];
    for (i = 1; i < n && d != 1; i++)
        d = gcd(a[i], d);
    return d;
}

void quicksort(keytype a[], int first, int last)
{
    int i, j;
    keytype x, t;

    x = a[(first + last) / 2];
    i = first;  j = last;
    for ( ; ; ) {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i >= j) break;
        t = a[i];  a[i] = a[j];  a[j] = t;
        i++;  j--;
    }
    if (first  < i - 1) quicksort(a, first , i - 1);
    if (j + 1 < last) quicksort(a, j + 1, last);
}

int is_prime(int x){
    if(x <= 1) return 0;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return 0;
    }
    return 1;
}

int is_substr(char s[], char t[], int i){
    int flag = 1;

    if(s[i] == '\0') flag = 0;

    for(int j = 0; j < strlen(t); ++j, ++i){
        if(s[i] != t[j]){
            flag = 0;
            break;
        }
    }
    return flag;
}

// factor list, number of factors, natural number
void factorize(int ftr[], int *num, int n){
    int a = 2, cnt = 0;

    while(n >= a){
        if(n % a == 0){
            n = n / a;
            ftr[cnt++] = a;
        }else{
            a++;
        }
    }
    *num = cnt;
}

//#define N 5
//int p[N + 1];
int nextperm(int p[], int N)  /* 辞書式順序で次の順列 */
{
    int i, j, t;

    i = N - 1;
    p[0] = 0;  /* 番人 */
    while (p[i] >= p[i + 1]) i--;
    if (i == 0) return 0;  /* 完了 */
    j = N;
    while (p[i] >= p[j]) j--;
    t = p[i];  p[i] = p[j];  p[j] = t;
    i++;  j = N;
    while (i < j) {
        t = p[i];  p[i] = p[j];  p[j] = t;  i++;  j--;
    }
    return 1;  /* 未了 */
}

void comb(int size1, int size2, int v[size1][size2]){
  for(int i = 0; i < size1; i++){
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for(int k = 1; k < size1; k++){
    for(int j = 1; j < k; j++){
      v[k][j] = (v[k-1][j-1] + v[k-1][j]);
    }
  }
}

int abs_val(int a, int b){
    if(a > b) return a - b;
    else return b - a;
}

const int inf = 1012345678;
int main(){
    int a, b;

    scanf("%d %d", &a, &b);

    int ans = 2 * a - 1;
    if(a == b) ans = a + b;
    else if(b - a >= 1) ans = 2 * b - 1;

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 1708
def gcd(a, b)
  return a if b == 0
  gcd(b, a % b)
end

def lcm(a, b)
  a * b / gcd(a, b)
end

n = gets.to_i
t = n.times.map { gets.to_i }

puts n == 1 ? t[0] : t.each_cons(2).reduce(1) {|r, (t1, t2)| lcm(r, lcm(t1, t2))}

Measured memory_bytes: 1788
#include <stdio.h>

int main(void){
	int n, a, num[50] = {0};
	long sum = 0;
	long dp[51][2501] = {{0}};
	// long dp[51][51][2501];

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

	// dp[0][0][0] = 1;
	// for(int i=1; i <= n; i++) {
	//  for(int j=0; j <= i; j++) {
	//      for(int k=0; k <= i*50; k++) {
	//          if(k < num[i-1]) {
	//              dp[i][j][k] = dp[i-1][j][k];
	//          }else if(j >= 1 && k >= num[i-1]) {
	//              dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-num[i-1]];
	//          }
	//      }
	//  }
	// }
	//
	// for(int i=1; i <= n; i++) {
	//  sum += dp[n][i][i*a];
	// }

	dp[0][0] = 1;
	for(int i=1; i <= n; i++) {
		for(int j=i; j > 0; j--) {
			for(int k=num[i-1]; k <= j*50; k++) {
				dp[j][k] += dp[j-1][k-num[i-1]];
			}
		}
	}

	for(int i=1; i <= n; i++) {
		sum += dp[i][i*a];
	}
	printf("%ld", sum);

	return 0;
}


Measured memory_bytes: 1152
import java.util.ArrayList;
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());
		
		ArrayList<Integer> A = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			A.add(Integer.parseInt(sc.next()));
		}
		
		for (int h = 0; h < n; h++) {
            if (h == n - 1) {
                System.out.println(A.get(h));
            } else {
                System.out.print(A.get(h) + " ");
            }
        }
		
		for (int i=1; i<A.size();i++) {
			int v = A.get(i);
			int j = i-1;
			
			while(j>=0 && A.get(j)>v) {
				A.set(j+1, A.get(j));
				j--;
			}
			A.set(j+1, v);
			for (int h = 0; h < n; h++) {
	            if (h == n - 1) {
	                System.out.println(A.get(h));
	            } else {
	                System.out.print(A.get(h) + " ");
	            }
	        }
		}
    }
}



Measured memory_bytes: 31284
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,d,cnt=0;
    cin>>n>>d;
    d*=d;
    while(n--)
    {
        ll x,y;
        cin>>x>>y;
        ll z=(x*x)+(y*y);
        if(z<=d)
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


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


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.
        nHr % mod = (n + r - 1)Cr % mod.
    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.
    Returns:
        The total number of combinations.
    Landau notation: O(n)
    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if r > (n - r):
        return count_combination(n, n - r, mod)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 0

    for i in range(1, k + 1):
        blue_count = count_combination(k - 1, i - 1)
        remain_red = n - k - (i - 1)

        if n - k + 1 >= i:        
            red_count = count_combination(remain_red + i, remain_red)
        else:
            red_count = 0
        
        ans = blue_count * red_count
        ans %= mod
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 100100100100100100;
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;
 
int main () {
    
    string s; cin >>s;
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        if (s[i] == '1') {
            ans++;
        }    
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <math.h>
using namespace std;
int main()
{
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;
    cout << s1[0] << s2[1] << s3[2];
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

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

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* Li Chao Tree */

template<typename T>
struct LiChaoTree {
  using Line = pair<T, T>; // first * x + second

  int segn2;
  vector<Line> data;
  vector<T> X;

  template<typename S>
  LiChaoTree(vector<S> pos) {
    int N = pos.size();
    for (segn2 = 1; segn2 < N; segn2 *= 2);
    data.assign(segn2 * 2, {0, LLINF});
    X.assign(segn2, INF);
    for (int i=0; i<(int)pos.size(); i++)
      X[i] = pos[i];
  }

  inline T f(Line line, T x) {
    return line.first * x + line.second;
  }

  void addLine(int a, int b, Line line, int l = 0, int r = -1, int k = 0) {
    if (r == -1) r = segn2;
    int m = (l + r) / 2;

    if (r <= a || b <= l) return;
    if (l < a || b < r) {
      addLine(a, b, line, l, m, k*2+1);
      addLine(a, b, line, m, r, k*2+2);
      return;
    }
    if (data[k].second == LLINF) { //isNull
      data[k] = line;
      return;
    }

    bool fl = f(line, X[l])   < f(data[k], X[l]);
    bool fm = f(line, X[m])   < f(data[k], X[m]);
    bool fr = f(line, X[r-1]) < f(data[k], X[r-1]);

    if (fl == fr) {
      if (fl) data[k] = line;
      return;
    }
    if (fm) swap(data[k], line);

    if (fl ^ fm) addLine(a, b, line, l, m, 2*k+1);
    else addLine(a, b, line, m, r, 2*k+2);
  }

  void addLine(Line line) { addLine(0, segn2, line); }

  T query(int k) {
    T x = X[k], res = LLINF;
    k += segn2-1;

    while(1){
      if (data[k].second != LLINF) //isNotNull
        res = min(res, f(data[k], x));
      if (!k) break;
      k = (k - 1) / 2;
    }

    return res;
  }
};

ll dp[SIZE];

int main(){
  int N;
  ll C, h[SIZE];
  vector<ll> pos;

  scanf("%d%lld", &N, &C);

  for (int i=0; i<N; i++) {
    scanf("%lld", h+i);
    pos.push_back(h[i]);
  }

  dp[0] = 0;

  LiChaoTree<ll> tree(pos);

  for (int i=0; i<N-1; i++) {
    tree.addLine({-2*h[i], h[i]*h[i] + C + dp[i]});
    dp[i+1] = tree.query(i+1) + h[i+1]*h[i+1];
  }

  cout << dp[N-1] << endl;

  return 0;
}


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

using namespace std;

#define mod 1000000007
#define inf 1e18


int main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  int x, n;
  cin >> x >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);

  int i = x;
  int j = x;

  while (1 == 1) {
    if (binary_search(a, a + n, i) != true) {
      cout << i << endl;
      break;
    } else if (binary_search(a, a + n, j) != true) {
      cout << j << endl;
      break;
    } else {
      i--;
      j++;
    }
  }

  return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
const lint MOD = pow(10, 9) + 7;

lint gcd(lint a, lint b) {
	//aとbの最大公約数を返す
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(a % b, b);
}

lint lcm(lint a, lint b) {
	//aとbの最小公倍数を返す
	return a / gcd(a, b) * b;
}

int main() {
	lint a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long
#include "string"

int32_t main(){
	boost;
	string s;
	cin>>s;
	int n = s.size();
	vector<int>dp(n,0);
	for(int i=0;i<n;){
		int j = i;
		while(j < n && s[i] == s[j])
			j++;
		if(s[i] == 'R')
			dp[j-1] = j - i;
		else
			dp[i] = j - i;
		i = j;
	}

	int maxi = 0;
	for(int i=1;i<n;i++)
		maxi = max(maxi,dp[i]+dp[i-1]);
	for(int i=1;i<n;i++){
		if(s[i] != 'L' or s[i-1] != 'R')
			continue;
		int sum = dp[i] + dp[i-1];
		if(sum %2 == 0)
			dp[i] = dp[i-1] = sum/2;
		else{
			if(dp[i] % 2 == 1){
				dp[i] = 1;
				dp[i-1] = 0;
			}
			else{
				dp[i-1] = 1;
				dp[i] = 0;
			}
			dp[i] += sum/2;
			dp[i-1] += sum/2;
		}
	}
	for(int &i :dp)
		cout<<i<<" ";
	cout<<endl;
}

Measured memory_bytes: 4264
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int main() {
  int N;
  while(cin >>N && N){
    bool f = 0;
    vector<int> v(N);
    REP(i, N) { cin >>v[i]; if(v[i] >= 2) f = 1; }
    if(!f) { cout <<"NA" <<endl; continue; }
    int cnt = 0;
    REP(i, N) if(v[i] >= 1) cnt++;
    cout <<cnt + 1 <<endl;
  }
  return 0;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int64_t N, K;
  cin >> N >> K;

  vector<long double> cum_sum(N + 1, 0.0);
  for (size_t n = 0; n < N; ++n) {
    int64_t p;
    cin >> p;
    cum_sum[n + 1] = cum_sum[n] + ((1.0l + p) / 2.0l);
  }
  long double res = 0.0;
  for (size_t k = 0; k <= N - K; ++k) {
    long double val = cum_sum[k + K] - cum_sum[k];
    if (res < val) {
      res = val;
    }
  }
  
  cout << setprecision(25) << res << endl;
  
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

struct mint {
    const int mod = 1e9 + 7;
    long long x;
    
    mint (long long x = 0) : x((x % mod + mod) % mod) {
        
    }
    
    mint& operator=(const long long a) {
        x = a % mod;
        return *this;
    }
    
    mint& operator=(const mint a) {
        x = a.x % mod;
        return *this;
    }
    
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    
    mint& operator-=(const mint a) {
        if ((x += (mod - a.x)) >= mod) x -= mod;
        return *this;
    }
    
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    
    mint inv() const {
        return pow(mod - 2);
    }
    
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, m;
    cin >> n >> m;
    vector<ll> s(n), t(m);
    rep(i, n) cin >> s[i];
    rep(i, m) cin >> t[i];
    vector<vector<mint>> dp(n + 1, vector<mint>(m + 1, 0));
    dp[0][0] = 1;
    rep(i, n + 1) {
        rep(j, m + 1) {
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
            if ((i > 0) && (j > 0)) {
                dp[i][j] -= dp[i - 1][j - 1];
                if (s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    cout << dp[n][m].x << endl;
    return 0;
}


Measured memory_bytes: 62976
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define show(x) cout << x << '\n'
#define showh(x) cout << x << ' '
#define go(i, a, n) for (ll i = a; i < n; i++)
#define gor(i, a, n) for (ll i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define ff first
#define ss second
auto t1 = chrono::high_resolution_clock::now();
bool prime[1000001];
ll expo(ll a, ll b)
{
  a = a % mod;
  b = b % mod;
  if (b == 0)
    return 1;
  if (b % 2)
    return ((a % mod) * (expo((a * a) % mod, b / 2) % mod)) % mod;
  return expo((a * a) % mod, b >> 1) % mod;
}
ll mul(ll a, ll b)
{
  a = a % mod;
  b = b % mod;
  if (b == 0)
    return 0;
  if (b % 2)
    return ((a % mod) + (mul((a + a) % mod, b >> 1) % mod)) % mod;
  return mul((a + a) % mod, b >> 1) % mod;
}

bool ispoweroftwo(ll x)
{
  return x && !(x & (x - 1));
}
ll xorcal(ll n)
{
  if (n % 4 == 0)
    return n;
  if (n % 4 == 1)
    return 1;
  if (n % 4 == 2)
    return n + 1;
  if (n % 4 == 3)
    return 0;
}
void sieve(ll n)
{
  memset(prime, true, sizeof(prime));
  prime[0] = false;
  prime[1] = false;
  for (ll i = 2; i * i <= n; i++)
  {
    if (prime[i] == true)
    {
      for (ll j = i * i; j <= n; j += i)
        prime[j] = false;
    }
  }
}
bool isprime(ll n)
{
  if (n <= 1)
    return false;
  if (n <= 3)
    return true;

  if (n % 2 == 0 or n % 3 == 0)
    return false;

  for (ll i = 5; i * i <= n; i += 6)
  {
    if (n % i == 0 or n % (i + 2) == 0)
      return false;
  }
  return true;
}

ll modinverse(ll a, ll m)
{
  ll m0 = m;
  ll y = 0, x = 1;

  if (m == 1)
    return 0;

  while (a > 1)
  {
    ll q = a / m;
    ll t = m;

    m = a % m;
    a = t;
    t = y;

    y = x - q * y;
    x = t;
  }

  if (x < 0)
    x += m0;

  return x;
}

ll gcd(ll a, ll b)
{
  if (a == 0)
    return b;
  return (b % a, a);
}
bool ispalindrome(string s)
{
  string t = s;
  reverse(t.begin(), t.end());
  if (t == s)
    return true;
  return false;
}
void binary(ll a[], ll n)
{
  gor(i, 0, 64)
  {
    ll k = n >> i;
    a[i] = k & (ll)1;
  }
}
ll countBits(ll n)
{
  if (n == 0)
    return 0;
  return 1 + countBits(n & (n - 1));
}
bool isPower(unsigned int n)
{
  // Base case
  if (n <= 1)
    return true;

  // Try all numbers from 2 to sqrt(n) as base
  for (int x = 2; x <= sqrt(n); x++)
  {
    unsigned p = x;

    // Keep multiplying p with x while is smaller
    // than or equal to x
    while (p <= n)
    {
      p *= x;
      if (p == n)
        return true;
    }
  }
  return false;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll n;
  cin >> n;
  ll sum = 0;
  go(i, 1, n + 1)
  {
    if (i % 3 != 0 and i % 5 != 0)
      sum += i;
  }
  show(sum);
  auto t2 = chrono::high_resolution_clock::now();
  auto duration = chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
  clog << "Time taken = " << duration * 1.0 / 1000 << " seconds" << endl;
  return 0;
}


Measured memory_bytes: 3868
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;


int main(){
    int N; cin >> N;
    int cnt=0;
    bool F = true;
    for(int i = 1; i <= N; i+=2){
        bool flag3 = false, flag5 = false, flag7 = false, flag=false;
        int num = i;
        if(i%10==7) i += 4;
        while(num != 0){
            int d = num % 10;
            if(d == 3) flag3 = true;
            else if(d == 5) flag5 = true;
            else if(d == 7) flag7 = true;
            else {
                flag = true;
                break;
            }
            num /= 10;
        }
        if(flag) continue;
        if(flag3 && flag5 && flag7) {
            cnt++;
            //cout << i << endl;
            if(i % 1000000000 == 77777753) i = 333333355;
            else if(i % 100000000 == 7777753 && F) {i = 33333355; F=false;}
            //else if(i % 1000000 == 777753) i = 3333355;
            //else if(i % 100000 == 77753) i = 333355;
            //else if(i % 10000 == 7753) i = 33355;
            else if(i%10==7) i += 10;
        }
    }
    cout << cnt << endl;
}

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

int main(){
	int N;
	cin >> N;
	if(N >= 195) cout << 5 << endl;
	else if(N >= 189) cout << 4 << endl;
	else if(N >= 165) cout << 3 << endl;
	else if(N >= 135) cout << 2 << endl;
	else if(N >= 105) cout << 1 << endl;
	else cout << 0 << endl;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int X,Y,Z,N;
ll A[101010],B[101010],C[101010];
pair<int,int> P[101010];
ll XS,YS,ZS;
set<pair<int,int>> XX,YY,ZY;
int inz[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>Z;
	N=X+Y+Z;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		P[i]={B[i]-A[i],i};
	}
	
	sort(P,P+N);
	FOR(i,N) {
		x=P[i].second;
		if(i<X) {
			XS+=A[x];
			XX.insert({A[x]-C[x],x});
		}
		else {
			YS+=B[x];
			YY.insert({B[x]-C[x],x});
			
			if(YY.size()>Y) {
				auto it=YY.begin();
				ZY.insert(*it);
				x=it->second;
				YY.erase(it);
				YS-=B[x];
				ZS+=C[x];
				inz[x]=1;
			}
			
		}
	}
	
	ll ret=XS+YS+ZS;
	
	for(i=X;i<X+Z;i++) {
		x=P[i].second;
		if(inz[x]==1) {
			ZS-=C[x];
			ZY.erase({B[x]-C[x],x});
			inz[x]=0;
		}
		else {
			YS-=B[x];
			auto it=*ZY.rbegin();
			ZY.erase(it);
			inz[it.second]=0;
			ZS-=C[it.second];
			YS+=B[it.second];
		}
		
		XS+=A[x];
		XX.insert({A[x]-C[x],x});
		auto it=XX.begin();
		x=it->second;
		XX.erase(it);
		XS-=A[x];
		ZS+=C[x];
		
		ret=max(ret,XS+YS+ZS);
	}
	
	
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 8448
import java.util.Arrays;

public class Main {


  private static void solve() {
    int n = ni();
    int x = ni();
    int[] a = na(n);
    
    Arrays.sort(a);
    int cnt = 0;
    for (int v : a) {
      if (x >= v) {
        x -= v;
        cnt ++;
      }
    }
    if (cnt == n && x > 0) { cnt --;}
    System.out.println(Math.max(0, cnt));
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

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

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 22484
#include <bits/stdc++.h>
using namespace std;
int main() {

    int n;
    string s;
    cin>>n>>s;
    int ans=0;

    for(int i=0;i<s.size();i++){
        if(s[i-1]!=s[i])
            ans++;
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 512
package main

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

func main() {
	fmt.Println(answer(os.Stdin))
}

func answer(r io.Reader) int {
	sc := bufio.NewScanner(r)
	sc.Split(bufio.ScanWords)

	// catch a first input line representing the length of slices to be passed in second input.
	n := nextInt(sc)

	// catch a second input line representing the elements of slices.
	A := make([]int, n)
	for i := 0; i < n; i++ {
		A[i] = nextInt(sc)
	}

	// catch a third input line representing the length of slices to be passed in fourth input.
	q := nextInt(sc)

	// catch a fourth input line representing the elements of slices.
	count := 0
	for j := 0; j < q; j++ {
		key := nextInt(sc)
		if !binarySearch(A, n, key) {
			continue
		}
		count++
	}
	return count
}

func binarySearch(A []int, lenA, key int) bool {
	left, mid, right := 0, 0, lenA
	for left < right {
		mid = (left + right) / 2
		if key == A[mid] {
			return true
		} else if key > A[mid] { // to search second half of the slice
			left = mid + 1
			continue
		}
		// to search first half of the slice
		right = mid
	}
	return false
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return n
}



Measured memory_bytes: 2708
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define S 2000005
#define M 998244353
#define nl cout<<"\n";
#define er  cout<<"\n***********\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test lli t;  cin>>t; while(t--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Y cout<<"Yes\n";
#define N cout<<"No\n";
#define print(x)                 cout<<#x<<": "<<x<<endl;
#define print2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define print3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define print4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define print5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl;
#define print6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl;
lli dp[S][2];
void solve()
{
     //RRRWWW
     
     lli n;cin>>n;
     string str;cin>>str;
     str='&'+str;
     lli r=0;
     for(lli i=1;i<=n;i++)
     {
        if(str[i]=='R') r++;
     }
     lli ct=0,ct1=0;
     for(lli i=r+1;i<=n;i++)
     {
        if(str[i]=='R') ct++;
     }

     for(lli i=1;i<=r;i++)
     {
        if(str[i]=='W')
            ct1++;
     }

     cout<<max(ct,ct1);


}
int main()
{
    fast
    #ifndef ONLINE_JUDGE
     freopen("inputa.txt", "r", stdin);
     freopen("outputa.txt", "w", stdout);
    #endif    
     
     // test
     {
          solve();
          nl
     }
}
//a+b=a?b+2?(a&b)
//__builtin_popcount(number)
//cout<<fixed<<setprecision(8)<<output<<"\n";




Measured memory_bytes: 3880
n = int(input())
seq = [int(x) for x in input().split()]
div4 = sum((1 for i in seq if i % 4 == 0))
div2 = sum((1 for i in seq if i % 2 == 0 and i % 4 != 0))
odd = n - div4 - div2
ans = "Yes"
if n == 2:
    if div4 == 0:
        if div2 != 2:
            ans = "No"
elif n == 3:
    if div4 == 0:
        if div2 != 3:
            ans = "No"
elif odd - div4 == 1 and odd+div4 == n:
    pass 
elif div4 < odd:
    ans = "No"
elif (div4 - odd) + div2 < 1:
    ans = "No"
print(ans)

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

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

int MOD = 1e9 + 7;
ll INF = 1e18;

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

ll dp[100010][10];

int main(){
    string s; cin>>s;
    int n=s.size();

    string t="ABC";

    for(int i=n; i>=0; i--){
        for(int j=3; j>=0; j--){
            if(i == n){
                if(j == 3) dp[i][j] = 1;
                else dp[i][j] = 0;
            }
            else{
                if(s[i] == '?') dp[i][j] = 3*dp[i+1][j];
                else dp[i][j] = dp[i+1][j];

                if(j < 3){
                    if(s[i] == '?' || s[i] == t[j]) dp[i][j] += dp[i+1][j+1];
                }
            }
            dp[i][j] %= MOD;
        }
    }
    cout << dp[0][0] % MOD << endl;
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  char a;
  cin >> a;
  if(isupper(a)) cout << 'A' << endl;
  else cout << 'a' << endl;
  return 0;
}

Measured memory_bytes: 3632
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N

def intinput():
    return int(input())

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

N = intinput()
a = listintinput()
print(max(a)-min(a))


Measured memory_bytes: 2940
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;
use std::collections::HashSet;

fn f(n: usize) -> usize {
    if n%2 == 0 {
        n/2
    } else {
        3*n + 1
    }
}

fn main() {
    input!{
      s: usize,
    }

    let mut set = HashSet::new();
    set.insert(s);
    let mut prev = s;
    for m in 2..1000001 {
        let v = f(prev);
        prev = v;
        if set.contains(&v) {
            return println!("{}", m);
        }
        set.insert(v);
    }
    panic!("error");
}


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

int main(){

    long long N;
    cin >> N;
    vector<long long> A(N);
    for(size_t i = 0; i < N; i++){
        cin >> A[i];
        A[i] -= (i + 1);
    }
    sort(A.begin(), A.end());

    long long mean1 = A[N / 2];
    long long mean2 = mean1 - 1;

    long long sum1 = 0, sum2 = 0;
    for(int i = 0; i < N; i++) sum1 += abs(A[i] - mean1);
    for(int i = 0; i < N; i++) sum2 += abs(A[i] - mean2);

    cout << min(sum1, sum2) << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;
    int tmp;
    bool result = false;
    vector<bool>test(int(pow(10, 9)), false);
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        if (test[tmp-1]) {
            result = true;
            break;
        }
        test[tmp-1] = true;
    }
    if (result) {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
    }
    return 0;
}

Measured memory_bytes: 122368
N,M = map(int,input().split())
A = [-1]*N
for _ in range(M):
    s,c = map(int,input().split())
    if A[s-1] !=-1 and A[s-1] != c:
        print(-1)
        exit()
    A[s - 1] = c
if N>1 and A[0] == 0:
    print(-1)
    exit()
ans = 0
if N>1 and A[0] == -1:
    A[0] = 1
for a in A:
    if a == -1:
        a = 0
    ans+=a
    ans*=10
print(ans//10)
        
    
    


    
    
        


Measured memory_bytes: 38256
a, b = map(int, input().split())

aa=int(0)
x=max([a, b])
y=min([a, b])

if (x+y)%3 ==0 and x <= y*2:
    aa=int(1)

n=int((x+y)/3)
k=int((n-(x-y))/2)


def comb(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * pow(denom, mod-2, mod)) % mod

if aa==1:
    print(comb(n,k))
else:
    print(aa)


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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    vector<int> v(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        v[a]++, v[b]++;
    }

    bool ans = true;
    rep(i, N) {
        if (v[i] % 2 == 1) ans = false;
    }

    if (ans) {
        puts("YES");
    } else {
        puts("NO");
    }
}

Measured memory_bytes: 640
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 1;
	int s;
	bool fi[10000];
	REP(i, 10000) fi[i] = false;
	cin >> s;
	while(fi[s] == false){
		fi[s] = true;
		ans++;
		if(s % 2 ==0) s/=2;
		else s = s*3+1; 
	}
    cout << ans << endl;
}

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

int main(){
	int a, b, c, n;
	cin >> a >> b >> c >> n;
	if(abs(c-a)<=n || abs(c-b)<=n && abs(b-a)<=n)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
ls = [int(input()) for i in range(n)]
ls.sort()
a = 0
for j in range(n-k+1):
    if j ==0:
        a = ls[j+k-1] - ls[j]
    else:
        if ls[j+k-1] - ls[j] < a:
            a = ls[j+k-1] - ls[j]
print(a)

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

int main(){
  int n,k,x,y;
  cin>>n>>k>>x>>y;
  
  
  if(n>k){
    cout<<k*x+(n-k)*y<<endl;
  }
  else{
    cout<<n*x<<endl;
  }
}


Measured memory_bytes: 256
main = do
  a <- readLn :: IO Int
  b <- readLn
  c <- readLn
  d <- readLn
  e <- readLn
  let round10 :: Int -> Int
      round10 x = 10 * ((x + 9) `quot` 10)
      mod10' :: Int -> Int
      mod10' x | x `mod` 10 == 0 = 10
               | otherwise = x `mod` 10
      m = minimum $ map mod10' [a,b,c,d,e]
  print $ (sum $ map round10 [a,b,c,d,e]) - (10 - m)


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

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

  vector<string> str(N);

  for(int i = 0;i < N;i++){
    cin >> str.at(i);
  }

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

  for(int i = 0;i < N;i++){
    cout << str.at(i);
  }

  cout << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
	int N;
	std::string s;
	std::cin >> N >> s;
	int red = 0, blue = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R')red++;
		else blue++;
	}
	if (red > blue)std::cout << "Yes";
	else std::cout << "No";
	return 0;
}

Measured memory_bytes: 256