akhauriyash/Code-Regression huggingface dataset:
t=int(input())
for loopi in range(t):
  n,a,b,c,d=list(map(int,input().split()))
  minest=10**40
  dd={n:0}
  while 1:
    newd={}
    for i in dd:
      if i%2:
        l=int((i-1)//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
        l=int((i+1)//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
      else:
        l=int(i//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a,l*d),newd[l])
        else:
          newd[l]=dd[i]+min(a,l*d)
      l=int((i-(i+1)%3+1)//3)
      if l in newd:
        newd[l]=min(dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d)
      l=int((i-(i+2)%5+2)//5)
      if l in newd:
        newd[l]=min(dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d)
    if 1 in newd:
      mmm=newd.pop(1)
      if minest>mmm:
        minest=mmm
    if 0 in newd:
      newd.pop(0)
    if len(newd)==0:
      break
    dd=newd
  print(minest+d)
    

Measured memory_bytes: 9712
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)


Measured memory_bytes: 130520
//  s.at(0) = toupper(s.at(0));//小文字なら大文字へ//大文字の場合はそのまま
//  s.at(i) = tolower(s.at(i));//大文字なら小文字へ//小文字の場合はそのまま
//s配列に格納した単語を、辞書順にソートする
//getline(cin, s);
//  sort(s.begin(), s.end());
//  string t = "keyence";//で文字列入力ができる
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;
  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  string s;
//  cin >> s;
//  cout << s.at(0) <<endl;
//  cout << s.at(0)-'0' <<endl;
//  Aが16？
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int kan_hyaku(int n){
  int kurai = 0;
  for(int i=0;i<3;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ju(int n){
  int kurai = 0;
  for(int i=0;i<2;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ichi(int n){
  int kurai = 0;
  for(int i=0;i<1;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int main() {
  ll k,a,b;
  cin >> k >> a >> b;
  if(k==1){
    cout << 2 << endl;
    return 0;
  }
  if(a >= b){
    cout << k + 1 << endl;
    return 0;
  }
  
  if(b-a <=2 ){
    cout << k + 1 << endl;
    return 0;
  }
    
  if(k<=a){
    cout << k+1 << endl;
    return 0;
  }
  else{
    if( (k-a-1)%2==0){
     cout << b + ((k-a-1)/2) *(b-a) <<endl;
    return 0;
    }
    else{
     cout << b + ((k-a-1)/2) *(b-a) + 1 << endl;
    return 0;
    }
  }
}

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

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

    int ans = 0;

    for(int i = 0; i < 8; i++) if( (1 << i) <= n )
        ans = 1 << i;

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

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll m = c-a,n = d-b;
    vector<vector<ll>> dp(m+1,vector<ll>(n+1,0));
    dp[0][0] = 1;
    rep(i,m){
        dp[i+1][0] = dp[i][0]*b%MOD2;
    }
    rep(i,n){
        dp[0][i+1] = dp[0][i]*a%MOD2;
    }
    rep(i,m){
        rep(j,n){
            dp[i+1][j+1] = (dp[i][j+1]*(b+j+1)%MOD2+dp[i+1][j]*(a+i+1)%MOD2-dp[i][j]*(a+i)*(b+j)%MOD2+MOD2)%MOD2;
        }
    }
    PRINT(dp[m][n]);
}


Measured memory_bytes: 73588
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    string S, T;
    cin >> S >> T;
    if (S.size() + 1 != T.size()) {
        cout << "No\n";
        return 0;
    }
    bool uguali = true;
    for (int i = 0; i < (int) S.size(); i++) if (S[i] != T[i]) uguali = false;
    if (uguali) cout << "Yes\n";
    else cout << "No\n";
}


Measured memory_bytes: 3652
n = int(input())
txy = [[int(x) for x in input().split()] for _ in range(n)]

b = [0,0,0]
for a in txy:
    t = a[0] - b[0]
    d = abs(a[1] - b[1]) + abs(a[2] - b[2])
    if d > t or d % 2 != t % 2:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 21156
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

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

    int n;
    cin >> n;
    long long ans = 1;
    for(long long i = 0; i < n; i++){
        ans = (ans * (i + 1)) % MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long int ll;

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

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define PI 3.14159265359

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;


int main() {
  double x;
  cin >> x;
  printf("%.6f\n", 2 * x * PI);
  return 0;
}

Measured memory_bytes: 3792
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int A, B, T;

		A = scan.nextInt();
		B = scan.nextInt();
		T = scan.nextInt();

		double time = T + 0.5;

		int baisu = (int) time / A;

		System.out.println(baisu * B);
	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 21716
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let _n: usize = it.next().unwrap().parse().unwrap();
    let w: usize = it.next().unwrap().parse().unwrap();
    let a: Vec<usize> = it.map(|s| s.parse().unwrap()).collect();
    const MOD: u64 = 998_244_353;
    let mut ans = 0u64;
    let mut dp = vec![0u64; w + 1];
    for a in a.chunks(34) {
        for &a in a.iter() {
            dp[0] += 1;
            if a <= w {
                unsafe {
                    for i in (a..(w + 1)).rev() {
                        *dp.get_unchecked_mut(i) += *dp.get_unchecked(i - a);
                    }
                }
            }
            ans = (ans + dp[w]) % MOD;
        }
        for v in dp.iter_mut() {
            *v %= MOD;
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>

#define INT_MAX 2147483647
#define INT_MIN -2147483648

int max(int a, int b);
int min(int a, int b);
int abs(int a);

int main() {
	int n;
	char s[105];

	scanf("%d", &n);
	scanf("%s", s);

	int maxi = 0;
	int curr = 0;
	for(int i = 0; i < n; i++) {
		if(s[i] == 'D') {
			curr--;
		}
		else if(s[i] == 'I'){
			curr++;
		}
		maxi = max(maxi, curr);
	}

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

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;	
}

int max(int a, int b) {
	return (a > b) ? a : b;
}

int min(int a, int b) {
	return (a < b) ? a : b;
}

int abs(int a) {
	return (a < 0) ? -a : a;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n;
  cin >> n;
  string s;
  cin >> s;

  string ans = "No";
  if(n%2==0){
    ll t = n/2;
    bool res = true;
    REP(i, t){
      if(s[i] != s[t+i])
        res = false;
    }

    if(res)
      ans = "Yes";
  }

  cout << ans << endl;
}


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

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

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // order_of_key
// #include <ext/pb_ds/tree_policy.hpp> // find by order
// using namespace __gnu_pbds; 
// #define ordered_set tree< pair<int, int> , null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>  

// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ull>(a, b)(rng)

typedef long double             ld;
typedef long long               ll;
typedef unsigned long long      ull;
typedef pair<ll, ll>            pll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vector<ii>>      vvii;
typedef vector< ll >            vll;
typedef vector< pll >           vpll;
 
#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second
 
template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}
 
template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> inline T russian(T a, T b, T mod) {ll res = 0; while(b){if(b&1) res = (res + a)%mod; a = (a+a)%mod; b>>=1;}return res;}
template <class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<typename T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return a; }
  
const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll N = 1e6+7;
const ll T = 1<<20;
const ll BIG_INF = 1e18 + 7;

ll n, m, k, q;
string s;
int tab[N];
int dp[N];

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

    cin >> n;

    for(int i = 1; i <= n; i++){
    	cin >> tab[i];
    	if(i <= 3)
    		dp[i] = abs(tab[i] - tab[1]);
    	else
    		dp[i] = min(abs(tab[i] - tab[i-1]) + dp[i-1], abs(tab[i] - tab[i-2]) + dp[i-2]);
    }
    cout << dp[n];

}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int k=0;
  for(int i=1;i<=9;i++)
    for(int j=1;j<=9;j++)
      if(i*j==n)
      {
        k=1;
      }
  if(k==1)
    cout<<"Yes";
  else
    cout<<"No";
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static final int MOD = 1000000007;
	static int N, total;
	static long[] pow10 = new long[801];
	static long[] fact = new long[201];
	static long[][] binom = new long[201][201];

	public static void main(String[] args) {
		pow10[0] = fact[0] = 1;
		for (int i = 1; i < pow10.length; ++i) {
			pow10[i] = pow10[i - 1] * 10 % MOD;
		}
		for (int i = 1; i < fact.length; ++i) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		for (int i = 0; i <= 200; ++i) {
			binom[i][i] = binom[i][0] = 1;
		}
		for (int i = 0; i <= 200; ++i) {
			for (int j = 1; j < i; ++j) {
				binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % MOD;
			}
		}
		N = sc.nextInt();
		int[] A = new int[N];
		int zi = -1;
		for (int i = 0; i < N; ++i) {
			A[i] = sc.nextInt();
			if (A[i] == 0) zi = i;
		}
		int ans = solve(A);
		if (zi != -1) {
			int[] B = new int[N - 1];
			int idx = 0;
			for (int i = 0; i < N; ++i) {
				if (i == zi) continue;
				B[idx++] = A[i];
			}
			ans += MOD - solve(B);
			ans %= MOD;
		}
		System.out.println(ans);
	}

	static int solve(int[] A) {
		int[] digits = new int[5];
		for (int i = 0; i < A.length; ++i) {
			digits[(A[i] + "").length()]++;
		}
		total = digits[1] + digits[2] * 2 + digits[3] * 3 + digits[4] * 4;
		int[][][] comb = new int[5][][];
		for (int i = 1; i <= 4; ++i) {
			if (digits[i] > 0) {
				comb[i] = calcComb(digits, i);
			}
		}
		long ret = 0;
		for (int i = 0; i < A.length; ++i) {
			int len = (A[i] + "").length();
			for (int j = 0; j < A.length; ++j) {
				long add = 0;
				for (int k = 0; k <= A.length - 1 - j; ++k) {
					add += binom[A.length - 1 - j][k] * fact[k];
					add %= MOD;
				}
				add *= A[i];
				add %= MOD;
				add *= fact[j];
				add %= MOD;
				for (int k = 0; k < total && k <= j * 4; ++k) {
					if (comb[len][j][k] == 0) continue;
					long addElem = add * pow10[k] % MOD;
					addElem *= comb[len][j][k];
					addElem %= MOD;
					ret += addElem;
				}
				ret %= MOD;
			}
		}
		return (int) ret;
	}

	static int[][] calcComb(int[] digits, int cur) {
		digits[cur]--;
		int[][] dp = new int[N][total + 1]; // dp[i][j] : j digits with i cards
		dp[0][0] = 1;
		int sum = 0;
		int idx = 0;
		for (int i = 1; i <= 4; ++i) {
			for (int j = 0; j < digits[i]; ++j, ++idx) {
				sum += i;
				for (int k = idx + 1; k > 0; --k) {
					for (int l = sum; l >= i; --l) {
						dp[k][l] += dp[k - 1][l - i];
						if (dp[k][l] >= MOD) dp[k][l] -= MOD;
					}
				}
			}
		}
		digits[cur]++;
		return dp;
	}
}

Measured memory_bytes: 28580
n,m=map(int, input().split())
x=list(map(int, input().split()))
x.sort()
alist=[]
for i in range(m-1):
  alist.append(x[i+1]-x[i])
alist.sort()
if n>=m:
  print(0)
else:
  print(sum(alist[0:m-n]))

Measured memory_bytes: 20352
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
using P = pair<ll, ll>;

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;}

const ll mod = 1000000007;
const int INF = 1<<29;

int main(){
  int N; cin >> N;
  set<int> res;
  for (int i = 0; i < N; ++i){
    int a; cin >> a;
    res.insert(a);
  }
  if (res.size() == N) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 11392
#include<stdio.h>
#include<string.h>
#include<math.h>

void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}





int main(void){
   int r;
   scanf("%d",&r);
   printf("%d",3*r*r);
   return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python3
##### Binary Indexed Tree #####
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

# 転倒数
def mergecount(A: list):
    if not A:
        return 0
    bit = Bit(max(A) + 1)
    cnt = 0
    for i, a in enumerate(A):
        cnt += i - bit.sum(a+1)
        bit.add(a, 1)
    return cnt

import re
print(sum(mergecount([*map(int, i)]) for i in re.split("[BC]", input().replace("A", "1").replace("BC", "0"))))

Measured memory_bytes: 12220
#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 n, m, k;
vector<vector<int>> to(100000, vector<int>(0));
vector<vector<int>> bu(100000, vector<int>(0));
vector<vector<int>> memo(100000, vector<int>(0));
vector<int> su(100000);
int ans = 0;
int l = 0;
 
int f(int x){
  	memo.at(x).at(0) = l;
    ans++;
    for(int i=0; i<to.at(x).size(); i++){
      if(memo.at(to.at(x).at(i)).at(0) == -1) f(to.at(x).at(i));
    }
    return 0;
}
 
int main(){
    cin >> n >> m >> k;
    int in0, in1;
    rep(i, n){
      memo.at(i) = {-1, -1};
      su.at(i) = 0;
    }
    rep(i, m){
      cin >> in0 >> in1;
      to.at(in0-1).push_back(in1-1);
      to.at(in1-1).push_back(in0-1);
    }
    rep(i, k){
      cin >> in0 >> in1;
      bu.at(in0-1).push_back(in1-1);
      bu.at(in1-1).push_back(in0-1);
    }
    rep(i, bu.size()){
    	sort(bu.at(i).begin(), bu.at(i).end());
    }
    rep(i, n){
        ans = -1;
        l = i;
    	if(memo.at(i).at(0) == -1){
          f(i);
          memo.at(l).at(1) = ans;
        }else{
          ans = memo.at(memo.at(i).at(0)).at(1);
        }
        rep(j, bu.at(i).size()){
          if(memo.at(bu.at(i).at(j)).at(0) == memo.at(i).at(0)) ans--;
        }
    	cout << ans - to.at(i).size() << ' ';
    }
    cout << endl;
    return 0;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back


int bexp(int a, int b)
{
	int res = 1;

	while (b)
	{
		if (b & 1) res = (res * a);

		a = (a * a); 
		b >>= 1;
	}
	return res;
}

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

#define N 1000010
#define MOD 1000000007


int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(10);

	string s, t;
	cin >> s >> t;

	int n = s.size(), m = t.size();

	pair<int, int> dp[n + 1][m + 1] = {};

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (s[i - 1] == t[j - 1])
			{
				dp[i][j].ff = dp[i - 1][j - 1].ff + 1;
				dp[i][j].ss = 1;
			}
			else
			{
				if (dp[i - 1][j].ff > dp[i][j - 1].ff)
				{
					dp[i][j].ff = dp[i - 1][j].ff;
					dp[i][j].ss = 2;
				}
				else
				{
					dp[i][j].ff = dp[i][j - 1].ff;
					dp[i][j].ss = 3;
				}
			}
		}
	}

	int i = n, j = m;
	string an;
	while (i > 0 && j > 0)
	{
		if (dp[i][j].ss == 1)
		{
			an += s[i - 1];
			i--, j--;
		}
		else if (dp[i][j].ss == 2)
			i--;
		else
			j--;
	}

	reverse(an.begin(), an.end());
	cout << an << endl;
	return 0;
}

Measured memory_bytes: 141056
#include<bits/stdc++.h>
#define st first
#define nd second
#define PQ priority_queue

using ll = long long ;
using namespace std;
using pii = pair<int,int>;
char c[(int)2e5 + 10];
int main(){
	scanf("%s", c);
	int val = 0;
	for(int i = 0; c[i] != '\0'; i++){
		val = (val + c[i] - '0') % 9;
	}
	printf(val == 0 ? "Yes" : "No");


}

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


using namespace std;


const int MAXN = 100 * 1000 + 13;




int n, a[MAXN], p[MAXN], b[MAXN];



int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i], p[i]--, a[i] = (i + 1) * 2 * n, b[i] = (n - i) * 2 * n;
	for (int i = 0; i < n; i++)
		a[p[i]] -= 2 * n - i - 1;
	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
	cout << endl;
	for (int i = 0; i < n; i++)
		cout << b[i] << ' ';
	return 0;
}

Measured memory_bytes: 896
input_NM = input().split(' ')
N = int(input_NM[0])
M = int(input_NM[1])
input_H = input().split(' ')
H = []
for i in range(len(input_H)):
  H.append(int(input_H[i]))
  
good = [1 for i in range(N)]#1:good,0:bad

for i in range(M):
  input_AB = input().split(' ')
  A = int(input_AB[0])
  B = int(input_AB[1])
  HA = H[A-1]
  HB = H[B-1]
#  min_AB = min(A,B)
  if HA > HB:
    min_AB = B-1
    if good[min_AB] == 1:
      good[min_AB] = 0
  elif HA < HB:
    min_AB = A-1
    if good[min_AB] == 1:
      good[min_AB] = 0
  else:
    if good[A-1] ==1:
      good[A-1] = 0
    if good[B-1] ==1:
      good[B-1] = 0

ng = 0
for i in range(len(good)):
  if good[i] != 0:
    ng = ng + 1

print(ng)
  
  

  

Measured memory_bytes: 21064
n = int(input())
s = input()
t = input()

ans = s + t
for i in range(n):
    is_same = True
    for j in range(i, n):
        if s[j] != t[j - i]:
            is_same = False
            break
    if is_same:
        ans = s[:i] + t
        break

print(len(ans))


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

##
## B - Frog2
## https://atcoder.jp/contests/dp/tasks/dp_b
##

import sys

def solve(N, K, nums):
    assert N > 0
    if N == 1:
        return 0
    costs = []; add = costs.append
    add(0)
    add(abs(nums[1] - nums[0]))
    #for i in range(2, min(K, N)):
    #    c = min( costs[j] + abs(nums[i] - nums[j]) for j in range(0, i) )
    #    costs.append(c)
    #for i in range(K, N):
    #    c = min( costs[j] + abs(nums[i] - nums[j]) for j in range(i-K, i) )
    #    costs.append(c)
    for i in range(2, N):
        c = min( costs[j] + abs(nums[i] - nums[j])
                     for j in range(max(i-K, 0), i) )
        add(c)
    return costs[-1]

def load(input):
    line = input.readline()
    N, K = [ int(s) for s in line.split() ]
    nums = [ int(s) for s in input.read().split() ]
    return N, K, nums

def main():
    N, K, nums = load(sys.stdin)
    result = solve(N, K, nums)
    print(result)

main()


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

using namespace std;

int solve(int N, std::vector<unsigned long long> &H){
    if(N == 1){
        return 0;
    }
    for(int i=N-2; i >= 0; --i){
        if(H[i] > H[i+1]){
            if(H[i] - H[i+1] > 1){
                return -1;
            }else{
                H[i]--;
            }
        }
    }
    return 0;
}

int main(){
    int N;
    cin >> N;
    std::vector<unsigned long long> H(N);

    for(int i=0; i < N; ++i){
        cin >> H[i];
    }
    int flag = solve(N, H);
    if(flag == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    base = [0] * N
    for i, a in enumerate(A):
        if i - a >= 0: base[i-a] += 1
    count = 0
    for i, a in enumerate(A):
        if i + a < N: count += base[i + a]
    print(count)

    return 0

if __name__ == "__main__":
    solve()

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

using namespace std;

//#define _FILES
#define PB push_back
#define MP make_pair
#define X first
#define Y second
const int MAXN = 2005;
vector<int> g[MAXN];
int dist[MAXN][MAXN];
int cur;

void calc(int v,int parent,int d)
{
    dist[cur][v] = d;
    for (int i=0;i<g[v].size();i++)
    {
        int to = g[v][i];
        if (to == parent) continue;
        calc(to, v, d + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    #ifdef _FILES
        freopen("","r",stdin);
        freopen("","w",stdout);
    #endif // _FILES
    int n, k;
    cin >> n >> k;
    for (int i=0;i<n-1;i++)
    {
        int u, v;
        cin >> u >> v;
        g[v].PB(u);
        g[u].PB(v);
    }
    for (int i=1;i<=n;i++)
    {
        cur = i;
        calc(i, 0, 0);
    }
    int mx = 0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            mx = max(mx, dist[i][j]);
        }
    }
    if (mx <= k)
    {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;

    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            if(dist[i][j] != k) continue;
            int cnt = 0;
            for (int jj=1;jj<=n;jj++)
            {
                if ((dist[i][jj] <= k) && (dist[j][jj] <= k)) cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << n - ans << endl;
    return 0;
}



Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n;
  cin >>n;
  vector<string>a(n);
  for(long long i=0;i<n;i++)cin>>a[i];
  long long m_kazu=0;
  long long a_kazu=0;
  long long r_kazu=0;
  long long c_kazu=0;
  long long h_kazu=0;
  map<string,long long>mp;
  for(string x:a){
    if(mp.count(x)){
      mp.at(x)++;
    }else{
      mp[x]=1;
      if(x[0]=='M')m_kazu++;
      if(x[0]=='A')a_kazu++;
      if(x[0]=='R')r_kazu++;
      if(x[0]=='C')c_kazu++;
      if(x[0]=='H')h_kazu++;
    }
  }
  long long kazu[5]={m_kazu,a_kazu,r_kazu,c_kazu,h_kazu};
  long long kotae=0;
  for(int a=0;a<3;a++){
    for(int b=a+1;b<4;b++){
      for(int c=b+1;c<5;c++){
        kotae+=kazu[a]*kazu[b]*kazu[c];
      }
    }
  }
  cout<<kotae<<endl;
  return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, d;
    cin >> n >> d;
    vector<long long> x(n), y(n);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        if (sqrt(x[i] * x[i] + y[i] * y[i]) <= d) {
            ++cnt;
        }
    }
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		mp[s]++;
	}
	cout<<mp.size()<<endl;
	return 0;
}

Measured memory_bytes: 19228
#include<bits/stdc++.h>
#define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
#define For(i,a,b) for (register int i=(a);i>=(b);i--)
#define mem(i,j) memset(i,j,sizeof(i))
#define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
#define fi first
#define se second
#define pii pair<int,int>
#define MP make_pair
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,a[N],ji,ou,pos,now,gcd;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
inline void yes() {if (now) printf("First\n");else printf("Second\n");exit(0);}
inline void no() {if (now) printf("Second\n");else printf("First\n");exit(0);}
inline int GCD(int x,int y)
{
	if (!y) return x;
	if (x<y) return GCD(y,x);
	return GCD(y,x%y);
}
inline void solve()
{
	ou=0,ji=0;
	FOR(i,1,n) ji+=(a[i]&1),ou+=(!(a[i]&1));
	if (!ou) no();
	if (ou&1) yes();
	if (!ji) no();
	if (ji>1) no();
	FOR(i,1,n) if (a[i]&1) {pos=i;break;}
	if (a[pos]==1) no();
	a[pos]--;
	gcd=a[1];
	FOR(i,2,n) gcd=GCD(gcd,a[i]);
	FOR(i,1,n) a[i]/=gcd;
	now^=1;
	solve();
	return;
}
int main()
{
	now=1;
	n=read();
	FOR(i,1,n) a[i]=read();
	solve();
	return 0;
}

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

#define   ll     long long int

const int N = 200005;
int ara[N];

int main( )
{
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> ara[i];
    }
    if (n % 2) {
        i = n;
        int fl = 0;
        while (i > 0) {
            if (fl) cout << ' ';
            cout << ara[i];
            fl = 1;
            i -= 2;
        }
        i = 2;
        while (i < n) {
            if (fl) cout << ' ';
            cout << ara[i];
            i += 2;
            fl = 1;
        }
    }
    else {
        i = n;
        int fl = 0;
        while (i > 0) {
            if (fl) cout << ' ';
            cout << ara[i];
            fl = 1;
            i -= 2;
        }
        i = 1;
        while (i < n) {
            if (fl) cout << ' ';
            cout << ara[i];
            i += 2;
            fl = 1;
        }
    }
    cout << '\n';
    return 0;
}


Measured memory_bytes: 2944
# coding: utf-8
# Your code here!
N = int(input())

if N >= 64:
    print(64)
elif N >= 32:
    print(32)
elif N >= 16:
    print(16)
elif N >= 8:
    print(8)
elif N >= 4:
    print(4)
elif N >= 2:
    print(2)
else:
    print(1)

Measured memory_bytes: 3060
#include <stdio.h>

int main(){
  int h,w;

  while(1){
    scanf("%d %d",&h,&w);
    if(h == 0 && w == 0)
      return 0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(i == 0 || j == 0 || i == h-1 || j == w-1)
          putchar('#');
        else
          putchar('.');
      }
      putchar('\n');
    }
   putchar('\n');
  }
  return 0;
}



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

int main(){
	int n;
	while(std::cin>>n){
		if(n==0)break;
		int sum=1,dice[6],dice_a[6];
		for(int i=0;i<6;i++)dice[i]=i+1,dice_a[i]=i+1;
		for(int i=0;i<n;i++){
			std::string str;
			std::cin>>str;
			if(str=="North"){
				dice[0]=dice_a[1];
				dice[1]=dice_a[5];
				dice[4]=dice_a[0];
				dice[5]=dice_a[4];
			}if(str=="East"){
				dice[0]=dice_a[3];
				dice[2]=dice_a[0];
				dice[5]=dice_a[2];
				dice[3]=dice_a[5];
			}if(str=="West"){
				dice[0]=dice_a[2];
				dice[2]=dice_a[5];
				dice[5]=dice_a[3];
				dice[3]=dice_a[0];
			}if(str=="South"){
				dice[0]=dice_a[4];
				dice[1]=dice_a[0];
				dice[5]=dice_a[1];
				dice[4]=dice_a[5];
			}if(str=="Right"){
				dice[1]=dice_a[2];
				dice[2]=dice_a[4];
				dice[4]=dice_a[3];
				dice[3]=dice_a[1];
			}if(str=="Left"){
				dice[1]=dice_a[3];
				dice[2]=dice_a[1];
				dice[4]=dice_a[2];
				dice[3]=dice_a[4];
			}
			for(int i=0;i<6;i++)dice_a[i]=dice[i];
			sum+=dice[0];
		}
		std::cout<<sum<<std::endl;
	}
	return 0;
}

Measured memory_bytes: 1212
n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
  l,r,d=map(int,input().split())
  G[l-1].append([r-1,d])
  G[r-1].append([l-1,-d])

dist=[None]*n
from collections import deque
for i in range(n):
  q=deque()
  if dist[i]==None:
    dist[i]=0
    q.append(i)
  while q:
    cur=q.popleft()
    for nx,nxd in G[cur]:
      if dist[nx]==None:
        dist[nx]=dist[cur]+nxd
        q.append(nx)
      elif dist[nx]!=dist[cur]+nxd:
        print("No")
        exit(0)
print("Yes")



Measured memory_bytes: 77308
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  int ans = 0;
  int A = 0, B = 0, AB = 0;
  REP(i, N){
    string s;
    cin >> s;

    REP(j, s.size()-1){
      if(s[j] == 'A' && s[j+1] == 'B') ans++;
    }
    if(s[0] == 'B' && s.back() == 'A') AB++;
    else if(s[0] == 'B') B++;
    else if(s.back() == 'A') A++;
  }

  if(AB != 0){
    if(A){
      ans++; A--;
    }
    if(B){
      ans++; B--;
    }
    ans += AB-1;
  }
  ans += min(A, B);

  cout << ans << "\n";

  return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

template<long long sz = 1000000007LL>
struct ModInt{
private:
	long long value;
	inline ModInt<sz> mpow(ModInt<sz> a, long long b){
		if (b == 0) return ModInt<sz>(1);
		ModInt<sz> tmp = mpow(a, b / 2);
		if (b % 2) return tmp * tmp * a;
		return tmp * tmp;
	}
public:
	ModInt(long long value = 0) : value((value % sz + sz) % sz) {}
	long long get(void) { return this->value; }
	constexpr ModInt<sz> operator+ (ModInt<sz> obj){
		return ModInt<sz>(this->value + obj.get());
	}
	constexpr ModInt<sz> operator+ (long long obj){ return (*this) + ModInt<sz>(obj); }
	constexpr ModInt<sz> operator- (ModInt<sz> obj){
		return ModInt<sz>((this->value - obj.get() + sz) % sz);
	}
	constexpr ModInt<sz> operator- (long long obj){ return (*this) - ModInt<sz>(obj); }
	constexpr ModInt<sz> operator* (ModInt<sz> obj){
		return ModInt<sz>(this->value * obj.get() % sz);
	}
	constexpr ModInt<sz> operator* (long long obj){ return (*this) * ModInt<sz>(obj); }
	constexpr ModInt<sz> operator/ (ModInt<sz> obj){
		return (*this) * mpow(obj, sz - 2);
	}
	constexpr ModInt<sz> operator/ (long long obj){ return (*this) / ModInt<sz>(obj); }
	constexpr ModInt<sz>& operator+= (ModInt<sz> obj){
		return *this = (*this) + obj;
	}
	constexpr ModInt<sz>& operator+= (long long obj){
		return *this = (*this) + obj;
	}
	constexpr ModInt<sz>& operator-= (ModInt<sz> obj){
		return *this = (*this) - obj;
	}
	constexpr ModInt<sz>& operator-= (long long obj){
		return *this = (*this) - obj;
	}
	constexpr ModInt<sz>& operator*= (ModInt<sz> obj){
		return *this = (*this) * obj;
	}
	constexpr ModInt<sz>& operator*= (long long obj){
		return *this = (*this) * obj;
	}
	constexpr ModInt<sz>& operator/= (ModInt<sz> obj){
		return *this = (*this) / obj;
	}
	constexpr ModInt<sz>& operator/= (long long obj){
		return *this = (*this) / obj;
	}
	ModInt<sz> pow(long long a){ return mpow(*this, a); }
	friend constexpr ostream& operator<< (ostream& os, const ModInt<sz>& data){
		return os << data.value;
	}
};

int main(void){
	int N; cin >> N;
	ModInt<> sum(0), sum2(0);
	while (N--){
		ll ai; cin >> ai;
		ModInt<> tmp(ai);
		sum += tmp;
		sum2 += tmp * tmp;
	}
	ModInt<> res = (sum * sum - sum2) / ModInt<>(2);
	cout << res << endl;
	return 0;
}

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

template<typename T> inline constexpr auto square(T x) { return (x) * (x); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const int MOD = 1000000007;
const int INF = INT_MAX;

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

	bool ans = false;
	rng(a, 1, 10) {
		int b = N / a;
		if ((N == a * b) && (b < 10)) ans = true;
	}

	if (ans) COL("Yes");
	else COL("No");

	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	string s;
	cin>>s;
	int n=s.size();
	int i=0;
	int ans=0;
	while(i<n){
		int cnt=1;
		while(i<n-1 && s[i]==s[i+1]){
			++i;
			++cnt;
		}
		ans+=cnt/3*2;
		if(cnt%3!=0){
			++ans;
			if(cnt%3==2){
				if(i==n-1){
					break;
				}
				++i;
				++ans;
			}
		}
		// DEBUG(ans);
		// DEBUG(i);
		++i;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 720
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
S = [[] for _ in range(H)]
direct = [(-1,0), (1,0), (0,-1), (0, 1)]

for i in range(H):
    S[i] = list(input())
ans = 'Yes'
for nh in range(H):
    for nw in range(W):
        if S[nh][nw] == '.':
            continue
        check = 0
        for dh, dw in direct:
            mh, mw =nh + dh, nw + dw
            if 0 > mh or mh > H-1 or 0 > mw or mw > W-1:
                continue
            if S[mh][mw] == '#':
                check = 1
        if not check:
            ans = 'No'
print(ans)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))

l = sum(a)
cur_l = 0
pre_l = 0
for i, ai in enumerate(a):
    cur_l += ai
    if l - 2*cur_l < 0:
        res = min(abs(l-2*cur_l), abs(l-2*pre_l))
        break
    pre_l = cur_l
print(res)

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

int main(){
  string s;
  cin >> s;
  sort(s.begin(), s.end());
  if (s.at(0) == s.at(1) && s.at(2) == s.at(3) && s.at(1) != s.at(2)) {
    cout << "Yes" << endl;
  } else cout << "No" << endl;
}


Measured memory_bytes: 3612
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int res = 1;
    int maxDividen = 0;
    for (size_t i = 1; i <= n; ++i) {
        size_t v = i;
        size_t op = 0;
        while (true) {
            if (v % 2 != 0) break;
            v = v / 2;
            ++op;
        }
        if (op > maxDividen) {
            maxDividen = op;
            res = i;
        }
    }

    cout << res << endl;
    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
// 2013/08/30 Tazoe

#include <iostream>
#include <algorithm>
using namespace std;

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

	for(int i=0; i<Q; i++){
		int c, a, n;
		cin >> c >> a >> n;

		int t = 0;

		int can = min(min(c, a), n);
		t += can;
		c -= can;
		a -= can;

		int cca = min(c/2, a);
		t += cca;
		c -= cca*2;

		int ccc = c/3;
		t += ccc;

		cout << t << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a,b;
    cin>>a>>b;

    if(a==1){
        a=14;
    }
    if(b==1){
        b=14;
    }

    if(a>b){
        cout<<"Alice"<<endl;
    }
    else if(b>a){   
        cout<<"Bob"<<endl;
    }
    else{
        cout<<"Draw"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC142B
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var N = input[0];
            var K = input[1];

            Console.WriteLine(Console.ReadLine().Split().Select(x => int.Parse(x)).Count(x => x >= K));
        }
    }
}


Measured memory_bytes: 17888
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;

int d[28],data[31];

int main(){
	for(int i=0;i<28;i++){ scanf("%d",&d[i]); data[d[i]]++; }
	for(int i=1;i<=30;i++) if(data[i]==0) printf("%d\n",i);
}

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

using P = pair<int,int>;

bool solve(){
    int n, m, p, q, r;
    cin >> n;
    if(n==0) return false;
    cin >> m >> p >> q >> r;
    vector<P> v = {P(0,r)}, tmp;  // [a,b)
    for(int i=0;i<m;i++){
        int x, y;
        cin >> x >> y;
        tmp.clear();
        for(auto &e : v){
            int a = e.first, b = e.second;
            if(b <= x){
                int d = n-x;
                tmp.emplace_back(P(a+d,b+d));
            }else if(a >= y){
                tmp.emplace_back(P(a-y,b-y));
            }else{
                if(a < x) tmp.emplace_back(P(a+n-x,n));
                tmp.emplace_back(P(max(a,x)-x+n-y,min(b,y)-x+n-y));
                if(b > y) tmp.emplace_back(P(0,b-y));
            }
        }
        v = tmp;
    }
    int ans = 0;
    p--;
    for(auto &e : v){
        int a = e.first, b = e.second;
        ans += max(min(q,b)-max(p,a),0);
    }
    cout << ans << endl;
    return true;
}

int main(){
    while(solve());
    return 0;
}



Measured memory_bytes: 3148