akhauriyash/Code-Regression huggingface dataset:
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<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 int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

map< int, int > prime_factor(int n) {
  map< int, int > ret;
  for(int i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN2(n,x);
  int ans = 1;
  for(auto p: prime_factor(x)){
    if(p.second >= n){
      while(p.second >= n){
        ans *= p.first;
        p.second -= n;
      }
    }
  }
  OUT(ans);
}

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

using namespace std;

const int N = 55;
const long long inf = 1e18;

long long a[N];

int main() {
  int n;
  scanf("%d", &n);
  long long mini = inf, maxi = -inf;
  int pmin = -1, pmax = -1;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", a + i);
    if (a[i] < mini) {
      mini = a[i];
      pmin = i;
    }
    if (a[i] > maxi) {
      maxi = a[i];
      pmax = i;
    }
  }
  vector<pair<int, int>> ans;
  int with = (abs(mini) < abs(maxi)? pmax : pmin);
  bool pos = (abs(mini) < abs(maxi)? 1 : 0);
  for (int i = 1; i <= n; i++) {
    if (i == with) continue;
    ans.emplace_back(with, i);
  }
  if (pos) {
    for (int i = 2; i <= n; i++) ans.emplace_back(i - 1, i);
  } else {
    for (int i = n - 1; i >= 1; i--) ans.emplace_back(i + 1, i);
  }
  printf("%d\n", ans.size());
  for (auto it : ans) printf("%d %d\n", it.first, it.second);

  return 0;
}


Measured memory_bytes: 256
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,p = map(int, input().split())
a = list(map(int, input().split()))
b = [i%2 for i in a]
n1 = b.count(1)
zero = 2 ** (n-n1)
r = 1
one = 0
while r <= n1:
  one += cmb(n1,r)
  r += 2
if p == 0:
  print(2**n - zero*one )
else:
  print(zero * one)

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

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,pi> pii;
typedef vector<int> vi;

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define forn(i, n) for(register int i=0; i<n; i++)
#define Forn(i, n) for(register int i=1; i<=n; i++)
#define foreach(it, a) for(__typeof((a).begin()) it=(a).begin(); it!=(a).end(); it++)
#define Foreach(it, a) for(__typeof((a).rbegin()) it=(a).rbegin(); it!=(a).rend(); it++)
#define INF 1999999999999999999LL

inline int in()
{
    char c=getchar();
    int neg=1, x=0;
    while(!isdigit(c)) (c=='-')?neg=-1, c=getchar():c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar();
    return neg*x;
}

const int MAX=2e5+5;

int N;
ll A[MAX], D, ret;
vector<pii> e;

namespace DSU
{
    int par[MAX];
    inline void init()
    {
        Forn(i, MAX-1)
            par[i]=i;
    }
    inline int find(int x)
    {
        return x==par[x]?x:par[x]=find(par[x]);
    }
    inline int unite(int x, int y)
    {
        x=find(x), y=find(y);
        if(x==y)
            return 0;
        par[x]=y;
        return 1;
    }
}

inline void solve(int l, int r)
{
    if(l==r)
        return;
    int m=l+r>>1, pl=-1, pr=-1;
    ll mnl=INF, mnr=INF;
    for(int i=l; i<=m; i++)
    {
        ll vl=A[i]-1LL*D*i;
        if(mnl>vl)
            mnl=vl, pl=i;
    }
    for(int i=m+1; i<=r; i++)
    {
        ll vr=A[i]+1LL*D*i;
        if(mnr>vr)
            mnr=vr, pr=i;
    }
    for(int i=l; i<=m; i++)
    {
        ll vl=A[i]-1LL*D*i;
        e.pb(mp(vl+mnr, mp(i, pr)));
    }
    for(int i=m+1; i<=r; i++)
    {
        ll vr=A[i]+1LL*D*i;
        e.pb(mp(mnl+vr, mp(pl, i)));
    }
    solve(l, m);
    solve(m+1, r);
}

int main()
{
    DSU::init();
    N=in(), D=in();
    Forn(i, N)
        A[i]=in();
    solve(1, N);
    sort(all(e));/*
    foreach(it, e)
        cout<<it->f<<" "<<it->s.f<<" "<<it->s.s<<endl;*/
    foreach(it, e)
        ret+=DSU::unite(it->s.f, it->s.s)*it->f;
    printf("%lld\n", ret);
    return 0;
}

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


int main() {
    int x,y,z;
    cin>>x>>y>>z;
    int count =0;
    x-=z;
    while(x>0){
        x-=y+z;
        if(x<0)break;
        count++;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

	cin >> a >> b >> c;
	if ((a == b && b != c) || (b == c && b != a) || (a == c && a != b)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

/*ここまでテンプレ*/



/*ここからmain関数*/

int main()
{
	int N, K;
	cin >> N >> K;
	cout << N - K + 1;

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cstdint>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <memory>
#include <numeric>
#include <vector>

// constexpr std::int64_t INF = 1ull << 50;
constexpr int INF = 1 << 20;

auto main() -> int {
  int AB, BC, CA;
  std::cin >> AB >> BC >> CA;

  std::cout << (AB * BC / 2) << std::endl;
}


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

int main(){
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    rep(i,n){
        cout << s[i] << t[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   998244353
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}

//=============================================ASIFAZAD==============================================//

int32_t main()
{
    io;
    int a, b, c, k;
    cin>>a>>b>>c>>k;
    while(b <= a && k)
    {
        b *= 2;
        k--;
    }
    while(c <= b && k)
    {
        c *= 2;
        k--;
    }
    if(b > a && c > b)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

Measured memory_bytes: 3664
import Data.Maybe
import qualified Data.Vector.Unboxed as V
import qualified Data.ByteString.Char8 as BS

main = do
  [n,maxWeight] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  -- 1 <= n <= 100, 1 <= maxWeight <= 10^9
  items <- V.replicateM n $ do
    [wi,vi] <- map (read . BS.unpack) . BS.words <$> BS.getLine
    -- 1 <= wi <= w, 1 <= vi <= 10^3
    return (wi, vi :: Int)
  let totalValue = V.sum $ snd $ V.unzip items -- 10^3 * 100 = 10^5
      result :: V.Vector Int
      result = V.dropWhile (== maxWeight + 1) $ V.reverse $ V.foldl'
               (\vec (wi,vi) ->
                  -- vec ! v : 価値 v を得るために必要な最小の重さ
                  V.generate (totalValue + 1)
                                (\v -> let w0 = fromMaybe 0 (vec V.!? v)
                                           w1 = fromMaybe 0 (vec V.!? (v - vi))
                                       in if w1 + wi <= maxWeight
                                          then min w0 (w1 + wi)
                                          else w0))
               (V.cons 0 $ V.replicate totalValue (maxWeight + 1)) items
  print $ V.length result - 1


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

int main () {

    long long N, A, B;
    scanf("%lld %lld %lld", &N, &A, &B);

    long long h[N], h_max = INT_MIN;
    for (long long i = 0; i < N; i++) {
        scanf("%lld", &h[i]);
        h_max = max(h_max, h[i]);
    }

    long long ok = 4000000000, ng = 0;
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        long long additional_attack_time = 0;

        for (long long i = 0; i < N; i++) {
            if (h[i] - B * mid > 0) {
                additional_attack_time += (h[i] - B * mid + (A - B - 1))/(A - B);
            }
            if (additional_attack_time > mid) break;
        }

        if (additional_attack_time > mid) ng = mid;
        else ok = mid;
    }
    printf("%lld\n", ok);

    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
     
    public class Main {
        static int binarySearchRightMost(int arr[],int key){
            int l=0,r=arr.length-1;
            while (l<r){
                int mid=Math.floorDiv(l+r,2);
                if(arr[mid]>key){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            return r-1;
     
        }
     
        public static void main(String[] args) {
    //        int arr[]={1,2,3,4,4,4,6,7};
    //        System.out.println(binarySearchRightMost(arr,4));
            Scanner scanner=new Scanner(System.in);
            int a=scanner.nextInt();
            int b=scanner.nextInt();
    //        int arr[]=new int[b];
            for(int j=0;j<b;j++){
                a-=scanner.nextInt();
                if(a<=0){
                    System.out.println("Yes");
                    break;
                }
            }
            if(a>0){
                System.out.println("No");
            }
    //        System.out.println(a%b==0?Math.floorDiv(a,b):Math.floorDiv(a,b)+1);
        }
    }

Measured memory_bytes: 49016
#include <bits/stdc++.h>
#define rep(i, n) for (ll(i) = 0; (i) < (n); (i)++)
#define all(x) (x).begin(), (x).end()
#define print(x) cout << (x) << endl;

typedef long long ll;
const ll INF = 99999999999999;
const ll MOD = 1000000007;

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll number1, ll number2)
{
    return number1 * number2 / gcd(number1, number2);
}
template <class T>
bool contain(const std::string &s, const T &v)
{
    // contain(to_string(N), '3')
    return s.find(v) != std::string::npos;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    return 0;
}

int vector_finder(std::vector<int> vec, int number)
{
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance(vec.begin(), itr);
    if (index != vec.size())
    { // 発見できたとき
        return 1;
    }
    else
    { // 発見できなかったとき
        return 0;
    }
}

using namespace std;

int main()
{
    int n, x, l, r, ans = 0;
    cin >> n;

    vector<vector<int>> data(n, vector<int>(2));
    vector<int> norobot(n, 0);
    rep(i, n)
    {
        int a, b;
        cin >> a >> b;
        data.at(i).at(0) = a + b;
        data.at(i).at(1) = a - b;
    }

    sort(all(data));
    int tmp = -1000000001;
    rep(i, n)
    {
        r = data.at(i).at(0);
        l = data.at(i).at(1);
        if (i == 0)
        {
            ans++;
            tmp = r;
        }
        else
        {
            if (tmp <= l)
            {
                ans++;
                tmp = r;
            }
        }
    }

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

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

int main() {
  int n;
  cin >> n;
  long long int sum;
  long long int a;
  bool zero = false;
  bool over = false;
  cin >> a;
  sum = a;
  if(a==0) {
    cout << 0 << endl;
    return 0;
  }
  for(int i=0; i<n-1; i++) {
    cin >> a;
    //1000000000000000000
    if(a==0) zero = true;
    else if(sum > 1000000000000000000/a) {
      over = true;
    }
    sum*=a;
  }
  if(zero) {
    cout << 0 << endl;
    return 0;
  }
  if(over) {
    cout << -1 << endl;
    return 0;
  }
  cout << sum << endl;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if (n != 1)
    res[n] = 1;
  return res;
}

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

  map<ll, ll> num_ind;
  repp(i, 2, N) {
    map<ll, ll> m = prime_factor(i);
    for (auto iter = m.begin(); iter != m.end(); iter++) {
      ll num = iter->fi;
      ll ind = iter->se;
      num_ind[num] += ind;
    }
  }

  vector<ll> ind;

  for (auto iter = num_ind.begin(); iter != num_ind.end(); iter++) {
    ll index = iter->se;
    ind.pb(index + 1);
  }

  int M = ind.size();
  int ans = 0;

  ll a = 0, b = 0;
  rep(i, M) {
    if (ind[i] >= 5)
      a++;
    if (ind[i] >= 3)
      b++;
  }
  ans += a * (a - 1) * (b - 2) / 2;

  a = 0, b = 0;
  rep(i, M) {
    if (ind[i] >= 25)
      a++;
    if (ind[i] >= 3)
      b++;
  }
  ans += a * (b - 1);

  a = 0, b = 0;
  rep(i, M) {
    if (ind[i] >= 15)
      a++;
    if (ind[i] >= 5)
      b++;
  }
  ans += a * (b - 1);

  a = 0;
  rep(i, M) {
    if (ind[i] >= 75)
      a++;
  }
  ans += a;

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long int n,k;
	cin>>n>>k;
	n=n*500;
	if(n>=k)
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
}

Measured memory_bytes: 3592
s = list(input())
n = len(s)

convertor = {'1': '0', '0': '1'}

prev = s[0]
ans = 0

for i in range(1, n):
    if s[i] == prev:
        s[i] = convertor[s[i]]
        ans += 1
    prev = s[i]

print(ans)

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#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 sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
const ll inf = 1e9;
int main(void){
    int n,m;cin>>n>>m;
    vector<ll> dp(20000,inf);
    dp[0]=0;
    rep(i,m){
        int a,b;cin>>a>>b;
        int tmp=0;
        rep(j,b){
            int c;cin>>c;c--;
            tmp+=(1<<c);
        }
        for(int j=0;j<=(1<<n);j++){
            chmin(dp[j|tmp],dp[j]+a);
        }
    }
    if(dp[(1<<n)-1]==inf)cout<<-1<<endl;
    else cout<<dp[(1<<n)-1]<<endl;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000009

int solve(int A[], int K, int N) {
	 int dp[N];
	 dp[0]=0;
	 dp[1]=abs(A[1]-A[0]);
	 for(int i=2; i<N; ++i) {
	 	  dp[i] = INF;
	 	  for(int j=1; j<=min(K,i);++j) {
	 	  	 dp[i] = min(dp[i], dp[i-j] + abs(A[i] - A[i-j]));
			}
	 }
	 return dp[N-1];
}

int main() {
	 int N, K;
	 cin >> N >> K;
	 int A[N];
	 for(int i=0; i < N; i++) cin >> A[i];
	 cout<<solve(A, K, N)<<endl;
	 return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 50
#define INF 9999999

int n,r[MAX][MAX],v[MAX],mini,mn,maxnum,minnum;
bool visit[MAX];

int dijkstra(int s,int g){
    for(int i = 0 ; i < MAX ; i++){
        v[i] = INF;
        visit[i] = false;
    }
    
    v[s] = 0;
    while(true){
        mini = INF;
        for(int i = 0 ; i <= maxnum ; i++){
            if(v[i] < mini && !visit[i]){
                mini = v[i];
                mn = i;
            }
        }
        
        if(mini == INF) break;
        visit[mn] = true;
        
        for(int i = 0; i <= maxnum ; i++){
            int t = r[mn][i]+v[mn];
            if(t < v[i]) v[i] = t;
        }
    }
    
    return v[g];
}


int main(){
    int a,b,c;
    
    while(cin >> n,n){
        for(int i = 0 ; i < MAX ; i++)
            for(int j = 0 ; j < MAX ; j++)
                r[i][j] = INF;
        
        maxnum = 0;
        minnum = INF;
        for(int i = 0 ; i < n ; i++){
            cin >> a >> b >> c;
            r[a][b] = c;
            r[b][a] = c;
            maxnum = max(maxnum,max(a,b));
            minnum = min(minnum,min(a,b));
        }
        
        int mx = INF, e;
        for(int i = 0; i <= maxnum ; i++){
            int sum = 0,num = i;
            for(int j = 0 ; j <= maxnum ; j++){
                if(i == j) continue;
                if(dijkstra(i,j)!=INF) sum += dijkstra(i,j);
            }
            if(sum < mx){
                mx = sum;
                e = num;
            }
        }
        cout << e << ' ' << mx << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll , ll> pll ;

const ll N = 2e5 + 30 , Mod = 1e9 + 7 ;
const ll SQ = 330 ;

ll p[N] ;
int main () {
    ios::sync_with_stdio(0), cin.tie(0) ;
    ll n ;
    cin >> n ;
    for (int i = 1;  i <= n ;i ++) cin >> p[i];
    ll cnt = 0 ;
    ll ans = 0 ;
    for (int i = 1;  i <= n ; i ++) {
    	if (p[i] != i) {
    		ans += (cnt + 1) / 2 ;
    		cnt = 0 ;
		}
		else cnt ++ ;
	}
    cout << ans + (cnt + 1)  / 2 ;
    return (0) ;
}

Measured memory_bytes: 1024
# abc136 C: Build Stairs

import sys


N = int(input())
array = list(map(int,input().split()))

level = 0
for i in range(len(array)-1):
    #level = max(array[i], level)
    #print("Check", array[i], array[i+1], level)
    if array[i] + 1 <= array[i+1]:
        level = array[i]
        continue
    elif array[i] == array[i+1]:
        if level <= array[i] - 1:
            array[i] -= 1
            level = array[i]
        else:
            continue
    elif array[i] - 1 == array[i+1]:
        if level <= array[i] - 1:
            array[i] -= 1
            level = array[i]
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 14400
#include <cstdio>
#include <functional>
#include <vector>
#include <queue>
#include <utility>

int main(){
  int Q;
  scanf("%d", &Q);

  std::vector<long> lsv, rsv;
  lsv.reserve(400002);
  rsv.reserve(400002);
  std::priority_queue<long> ls(std::less<long>({}), std::move(lsv));
  std::priority_queue<long, std::vector<long>, std::greater<long>> rs(std::greater<long>({}), std::move(rsv));
  long qs,a,b;
  scanf("%ld%ld%ld", &qs, &a, &b);
  ls.push(a);
  rs.push(a);
  long min_val = b;
  for(int qi = 0; qi < Q-1; qi++){
    scanf("%ld", &qs);
    if(qs == 1){
      scanf("%ld%ld", &a, &b);
      auto lend = ls.top();
      auto rbegin = rs.top();
      if(a < lend){
        ls.pop();
        rs.push(lend);
        ls.push(a); ls.push(a);
        min_val += lend-a+b;
      }else if(a > rbegin){
        rs.pop();
        ls.push(rbegin);
        rs.push(a); rs.push(a);
        min_val += a-rbegin+b;
      }else{
        ls.push(a); rs.push(a);
        min_val += b;
      }
    }else{
      printf("%ld %ld\n", ls.top(), min_val);
    }
  }

  return 0;
}



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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    ll sum = 0;
    REP(i, S.length()) {
        sum += S[i] - '0';
    }

    if (sum % 9 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL << 62)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll countDigit(ll n) { return floor(log10(n) + 1); } 
typedef pair <ll,ll> P;
static const ll dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) { 
        os << v[i]; 
        if (i != (int)v.size() - 1) 
            os << " "; 
    } 
    return os; 
} 

ll nCrModp(ll n, ll r, ll p)
{
    ll C[r+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (ll i = 1; i <= n; i++)
    {
        for (ll j = min(i, r); j > 0; j--)
            C[j] = (C[j] + C[j-1])%p;
    }
    return C[r];
}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main()
{
    ll A, B;
    cin >> A >> B;
    print(lcm(A,B));
    return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    cnt += max(bisect_left(L, L[i]+L[j]) - (j+1), 0)

print(cnt)

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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pf printf
#define sc scanf
#define sf(n) scanf("%d",&n)
#define sff(n1,n2) scanf("%d %d",&n1,&n2)
#define sfff(n1,n2,n3) scanf("%d %d %d",&n1,&n2,&n3)
#define sl(n) scanf("%lld",&n)
#define sll(n1,n2) scanf("%lld %lld",&n1,&n2)
#define slll(n1,n2,n3) scanf("%lld %lld %lld",&n1,&n2,&n3)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,n) for(i=1;i<=n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define nl puts("");
#define pb push_back
#define MOD 1000000007
#define fi first
#define se second
#define N 100005
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define sz(x) x.size()
#define pi pair<int,int>
#define pii pair<pair<int,int>,pair<int,int> >
#define line puts("-------");
#define db(x) cout<<#x<<" :: "<<x<<"\n";
#define dbb(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define fr freopen("input.txt","r",stdin);
#define fw freopen("output.txt","w",stdout);
typedef long long int ll;
using namespace std;
int ara[N],tree[4*N];
void build(int node,int a,int b)
{
    if(a>b)
        return;
    if(a==b)
    {
        tree[node]=ara[a];
        return;
    }
    int mid=(a+b)/2;
    build(node*2,a,mid);
    build(node*2+1,1+mid,b);
    tree[node]=__gcd(tree[node*2],tree[node*2+1]);
}
int query(int node,int a,int b,int i,int j)
{
    if(a>b || a>j || b<i)
        return 0;
    if(a>=i && b<=j)
        return tree[node];
    int mid=(a+b)/2;
    int q1=query(node*2,a,mid,i,j);
    int q2=query(1+node*2,1+mid,b,i,j);
    return __gcd(q1,q2);
}
int main()
{

    int i,n;
    sf(n);
    for(i=0;i<n;i++)
        sf(ara[i]);
    if(n==2)
    {
        pf("%d\n",max(ara[0],ara[1]));
        return 0;
    }
    build(1,0,n-1);
    int mx=max(query(1,0,n-1,1,n-1),query(1,0,n-1,0,n-2));
    for(i=1;i<n-1;i++)
    {
        int l=query(1,0,n-1,0,i-1);
        int r=query(1,0,n-1,i+1,n-1);
        mx=max(mx,__gcd(l,r));
    }
    pf("%d\n",mx);
}


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

using namespace std;

const int N = 11;
int n;
long double x[N];

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

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> x[i];
        string u;
        cin >> u;
        if(u == "BTC")
            x[i] *= 380000;
    }

    long double ans = 0;
    for(int i = 0; i < n; i++)
        ans += x[i];

    cout << fixed << setprecision(10) << ans;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

//Node treeMinimum(Node x){


//}

//Node treeMaximum(Node x){


//}

Node treeSearch(Node u, int k){
  Node a;
  if(u->key==k) a=u->key;
  else if(u->key > k){
    if(u->left!=NIL) a=treeSearch(u->left,k);
    else a=NIL;
  }else if(u->key < k){
    if(u->right!=NIL) a=treeSearch(u->right,k);
    else a=NIL;
  }
  return a;
}

//Node treeSuccessor(Node x){


//}

//void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



//}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x!=NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }
  z->parent=y;

  if(y==NIL) root=z;
  else if(z->key < y->key) y->left=z;
  else y->right=z;
}

void inorder(Node u){
  if(u->left!=NIL) inorder(u->left);
  printf(" %d",u->key);
  if(u->right!=NIL) inorder(u->right);
}
void preorder(Node u){
  printf(" %d",u->key);
  if(u->left!=NIL) preorder(u->left);
  if(u->right!=NIL) preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
      } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      //treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20440
n=int(input())
import sys
w=[input()for i in range(n)]

r=set(w)
o=''
m=''
if len(r) != len(w):
    
    print('No')
    sys.exit()

for i in range(n-1):
    o=w[i]
    m=w[i+1]
    if o[-1] != m[0]:
        print('No')
        sys.exit()
    
        
        
print('Yes')

Measured memory_bytes: 3064
#include<stdio.h>

int main(void){

int ai,n,i,min,max;

long sum;

scanf("%d",&n);

for(i=0;i<n;i++){

scanf("%d",&ai);

if(i==0){

min=ai;

max=ai;

sum=ai;

}

else{

sum=sum+ai;

if(min>ai){

min=ai;

}

if(max<ai){

max=ai;

}

}

}

printf("%d %d %ld\n",min,max,sum);

return 0;

}
  

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll a,b,k;
    scanf("%lld%lld%lld",&a,&b,&k);
    ll x = min(a,k);
    a -= x;
    k -= x;
    x = min(b,k);
    b -= x;
    k -= x;
    printf("%lld %lld\n",a,b);

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,ans,sum,a[N],b[N],dp[105][105];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int dfs(int len,int lim,int zero,int last)
{
	if(len==0)return (zero==0);
	if(!lim&&!zero&&dp[len][last]!=-1)return dp[len][last];
	int ma=9;
	if(lim)ma=a[len];
	int res=0;
	for(int i=0;i<=ma;i++)
	{
		if(zero)
		{
			res+=dfs(len-1,lim&(i==ma),zero&(i==0),i);
		}
		else{
			if(abs(i-last)<=1)res+=dfs(len-1,lim&(i==ma),zero&(i==0),i);
		}
	}
	if(!lim&&!zero)dp[len][last]=res;
	return res;
}
int solve(int n)
{
	int len=0;
	while(n)
	{
		a[++len]=n%10;
		n=n/10;
	}
	return dfs(len,1,1,0);
}
signed main()
{
	memset(dp,-1,sizeof(dp));
	n=read();
	int l=1,r=1e18;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(solve(mid)<n)l=mid+1;
		else r=mid;
	}
	cout<<l;
	return 0;
}


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

using ll = long long;

const ll INF = 1e18;

const int S = 1 << 18;
ll seg[2*S];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, Q; cin >> N >> Q;
	vector<pair<pair<ll, ll>, ll>> blocks(N);
	for (int i = 0; i < N; i++) {
		ll s, t, x; cin >> s >> t >> x;
		s -= x, t -= x;
		blocks[i] = {{s,t}, x};
	}
	vector<ll> D(Q);
	for (int q = 0; q < Q; q++) {
		cin >> D[q];
	}

	for (int i = 0; i < 2 * S; i++) {
		seg[i] = INF;
	}

	for (int i = 0; i < N; i++) {
		ll s = blocks[i].first.first, t = blocks[i].first.second, x = blocks[i].second;
		int si = int(lower_bound(D.begin(), D.end(), s) - D.begin());
		int ti = int(lower_bound(D.begin(), D.end(), t) - D.begin());
		for (int a = S+si, b = S+ti; a < b; a /= 2, b /= 2) {
			if (a & 1) {
				seg[a] = min(seg[a], x);
				a++;
			}
			if (b & 1) {
				--b;
				seg[b] = min(seg[b], x);
			}
		}
	}
	for (int i = 1; i < S; i++) {
		seg[2*i+0] = min(seg[2*i+0], seg[i]);
		seg[2*i+1] = min(seg[2*i+1], seg[i]);
	}
	for (int i = 0; i < Q; i++) {
		if (seg[S+i] == INF) cout << -1 << '\n';
		else cout << seg[S+i] << '\n';
	}
	return 0;
}


Measured memory_bytes: 12288
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<pair<int, int> > > vvp;
typedef vector<pair<int, int> > vp;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<vector<ll> > vvl;
typedef vector<ll> vl;
typedef vector<vector<bool> > vvb;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define yn(f) (f?"yes":"no")
#define YN(f) (f?"YES":"NO")
#define Yn(f) (f?"Yes":"No")
#define inf (1000000007)
#define nil -1
string to_str(vi& alf) {
	string str = "";
	for (int i = 0; i < alf.size(); i++)
	{
		str += to_string(alf[i]);
	}
	return str;
}
ll f(ll x) {
	if (x==1) {
		return 0;
	}
	else {
		ll sum = 1;
		ll sum2 = 1;
		for (int i = 0; i < 2; i++)
		{
			sum *= x - i;
			sum2 *= i+1;
		}
		return sum/sum2;
	}
}
int main() {
	int n;
	cin >> n;
	vs S(n);
	set<string> SS;
	rep(i, 0, n) {
		cin >> S[i];
		SS.insert(S[i]);
	}
	int smcount = S.size() - SS.size();
	map<string, ll> C;
	for (int i = 0; i < n; i++)
	{
		vi alf(26,0);
		for (int j = 0; j < 10; j++)
		{
			char temp = S[i][j]-'a';
			alf[temp]++;
		}
		C[to_str(alf)]++;
	}
	ll count = 0;
	for (auto x : C) {
		count += f(x.second);
	}
	cout << count << endl;
}


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

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  rep(i, m) {
    int a;
    cin >> a;
    sum += a;
  }
  int ans = n - sum;
  if(ans >= 0) cout << ans << endl;
  else cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e2+5;
char s[MAXN];
ll n,k;
bool fl;
int main(){
	scanf("%s",s+1);
	scanf("%lld",&k);
	n=strlen(s+1);
	for (int i=2;i<=n;i++){
		if (s[i]!=s[i-1]) fl=1;
	}
	for (int i=1;i<=n;i++) s[i+n]=s[i];
	ll cnt1=0,cnt2=0;
	for (int i=1;i<=n;i++){
		if (s[i]==s[i-1]) s[i]='#',cnt1++;
	}
	for (int i=n+1;i<=2*n;i++){
		if (s[i]==s[i-1]) s[i]='#',cnt2++;
	}
	if (!fl) printf("%lld\n",cnt1*((k+1ll)/2ll)+cnt2*(k/2ll));
	else printf("%lld\n",cnt1+cnt2*(k-1ll));
	return 0;
}


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

#define ll long long

int cnt[200005];
int arr[200005];

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

    int n;
    ll k;
    vector <int> v;

    cin >> n >> k;

    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    v.push_back(1);
    int x = arr[1];
    v.push_back(x);
    cnt[1] = 1;
    cnt[x] = 1;
    ll len = 1;
    int rep;
    while(true)
    {
        v.push_back(arr[x]);
        cnt[arr[x]]++;
        len++;
        rep = arr[x];
        if(cnt[arr[x]] >= 2)
            break;
        x = arr[x];
    }
//    for(int i = 0; i < v.size(); i++)
//        cout << v[i] << " ";
//    cout << "\n";

    int bal=0, cycle_len = 0, j = 0;
    for(int i = 0; i < v.size(); i++)
    {
        if(rep == v[i])
        {
            if(bal == 0)
                j = i;
            bal++;
        }
        if(bal == 1)
            cycle_len++;
        if(bal == 2)
            break;
    }
//    cout << "==>len : " << len << "\n";
//    cout << "==>" << cycle_len << "\n";
//    cout << "j : " << j << "\n";
    if(k <= len)
    {
        cout << v[k] << "\n";
    }
    else
    {
        int i = (ll)(k-(len-cycle_len)) % cycle_len;
        //cout << "i : " << i << "\n";
        cout << v[j+i] << "\n";
    }
    return 0;
}



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

//const double PI = acos(-1);
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second

ll n,a,b,c,d;
ll dp[1010][1010];
ll K[1010];
ll cc[1010][1010];
ll inv[1010];

ll mul(ll _a, ll _b) {
  if (_b == 0) return 1LL;
  if (_b == 1) return _a;
  ll ans = mul(_a, _b/2);
  ans *= ans;
  ans %= MOD;
  if (_b&1) ans *= _a;
  return ans % MOD;
}

ll C(ll _n, ll _k) {
  if (cc[_n][_k] != 0LL) return cc[_n][_k];
  if (_n == _k) return cc[_n][_k] = 1;
  return cc[_n][_k] = (K[_n] * ((inv[_k] * inv[_n-_k]) % MOD)) % MOD;
}

ll get(ll groups, ll mem, ll from) {
  ll ans = 1;

  REP(i,groups) {
    ans *= C(from, mem);
    ans %= MOD;
    from -= mem;
  }

  return (ans * inv[groups]) % MOD;
}

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

  cin >> n >> a >> b >> c >> d;
  dp[0][0] = 1;

  K[1] = 1;
  inv[1] = 1;
  for (ll i = 2; i <= n; i++) {
    K[i] = K[i-1]*i;
    K[i] %= MOD;
    inv[i] = mul(K[i], MOD-2);
  }

  for (ll i = 1; i <= b; i++) {
    if (i < a) {
      dp[i][0] += dp[i-1][0];
      dp[i][0] %= MOD;
      continue;
    }
    REP(j,n+1) {
      dp[i][j] += dp[i-1][j];
      dp[i][j] %= MOD;
      ll k = c;
      while (k <= d && j + k * i <= n) {
        dp[i][j+k*i] += dp[i-1][j] * get(k, i, n-j);
        dp[i][j+k*i] %= MOD;
        k++;
      }
    }
  }
  cout << dp[b][n] << endl;
  return 0;
}


Measured memory_bytes: 15360
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int M, N;
	long long x[1000], y[1000], z[1000];
	long long ans[8][1000];
	long long tmp[8] = { 0 };
	long long max = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> x[i] >> y[i] >> z[i];
	}

	for (int i = 0; i < N; i++)
	{
		ans[0][i] = (x[i] + y[i] + z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[1][i] = (x[i] + y[i] - z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[2][i] = (x[i] - y[i] + z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[3][i] = (x[i] - y[i] - z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[4][i] = (-x[i] + y[i] + z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[5][i] = (-x[i] + y[i] - z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[6][i] = (-x[i] - y[i] + z[i]);
	}
	for (int i = 0; i < N; i++)
	{
		ans[7][i] = (-x[i] - y[i] - z[i]);
	}
	
	for (int i = 0; i < 8; i++)
	{
		sort(ans[i], ans[i] + N, greater<long long>());
		//cout <<"p"<< ans[i] << " " << ans[i] + N << ans[i]-(ans[i] + N) << endl;
		for (int j = 0; j < M; j++)
		{
			tmp[i] += ans[i][j];
		}
	}

	for (int i = 0; i < 8; i++)
	{
		if (max < tmp[i])
			max = tmp[i];
	}

	cout << max << endl;

	return 0;
}

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


int main()
{
	string str;
	cin >> str;
	
	str.insert(str.begin(), '0');
	int n = str.size();

	vector<vector<int>> dp(n, vector<int>(2));
	dp.at(0).at(0) = 0;
	dp.at(0).at(1) = 1;
	for (int i = 1; i < n; i++) {
		int num = str[i] - '0';
		dp.at(i).at(0) = min(dp.at(i - 1).at(0) +  num, dp.at(i - 1).at(1) + (10 - num));
		dp.at(i).at(1) = min(dp.at(i - 1).at(0) + num + 1, dp.at(i - 1).at(1) + (9 - num));
	}

	int ans = dp.at(n - 1).at(0);
	cout << ans << endl;

}


Measured memory_bytes: 55940
#include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> P;
vector<int> anscands;
int main(void)
{
  vector<pair<int,int> > ones;
  int N,K;
  bool seeone=false;
  string S;
  int ans=0;
  cin >> N >> K;
  cin >> S;
  int l=0,r=0;
  ones.push_back(make_pair(1,1));
  for(int i=0;i<N;i++)
    {
      if(S[i]=='1')
	{
	  if(!seeone)
	    {
	      l=i+1;
	      r=i+1;
	    }
	  seeone=true;
	  if(i==N-1)
	    {
	      r=i+1;
	      ones.push_back(make_pair(l,r));
	    }
	}
      else
	{
	  if(seeone)
	    {
	      r=i;
	      ones.push_back(make_pair(l,r));
	      l=0,r=0;
	      seeone=false;
	    }
	}
    }
  if(S[N-1]=='0')
    {
      ones.push_back(make_pair(N,N));
    }
  int osize=int(ones.size());
  /*for(int i=0;i<osize;i++)
    {
      cout << ones[i].first << ' ' << ones[i].second << endl;
      }*/
  for(int i=0;i<max(osize-K,1);i++)
    {
      if(i+K>=osize)
	{
	  ans=max(ans,ones[osize-1].second-ones[i].first+1);
	}
      else
	{
	  ans=max(ans,ones[i+K].second-ones[i].first+1);
	}
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n) for(ll i=0;i<(n);i++)
#define For1(i,n) for(ll i=1;i<(n);i++)
#define MOD 1000000007

ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll pattern(ll now,ll mae,ll &k,ll &ans,vector<vector<ll>> &vec){
    if(now==0){
        ans = k;
        For(i,vec.at(0).size()){
            ans=(ans*(k-1-i))%MOD;
        }
        For(i,vec.at(0).size()){
            pattern(vec.at(0).at(i),0,k,ans,vec);
        }
    }
    else{
        For(i,vec.at(now).size()-1){
            ans=(ans*(k-2-i))%MOD;
        }
        For(i,vec.at(now).size()){
            if(vec.at(now).at(i)!=mae){
                pattern(vec.at(now).at(i),now,k,ans,vec);
            }
        }        
    }
    return ans;
}
int main(){
    ll n,k;cin>>n>>k;
    vector<vector<ll>> vec(n);
    For(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        vec.at(a).push_back(b);
        vec.at(b).push_back(a);
    }
    ll a=0;
    a=pattern(0,-1,k,a,vec);
    cout<<a%MOD<<endl;
}


Measured memory_bytes: 12800
/*
            _ _  ___            __ _ _  _       _     
 _   _  ___| | |/ _ \__      __/ _| | || |  ___| |__  
| | | |/ _ \ | | | | \ \ /\ / / |_| | || |_/ __| '_ \ 
| |_| |  __/ | | |_| |\ V  V /|  _| |__   _\__ \ | | |
 \__, |\___|_|_|\___/  \_/\_/ |_| |_|  |_| |___/_| |_|
 |___/                 

 */

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define ll long long
#define int long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector< vector<int> > vvi;
typedef vector< pair<int, int> > vpi;
#define MAXN 300005
#define MOD 1000000007
#define INF 1000000000000000007


signed main(){
	fast
	int n;
	cin>>n;
	string temp;
	map<vi, int> mp;
	For(i, 0, n){
		cin>>temp;
		vector<int> v(26, 0);
		For(i, 0, 10){
			int ind = temp[i]-'a';
			v[ind]++;
		}
		if(mp.find(v)==mp.end()){
			mp[v]=1;
		}else{
			mp[v]++;
		}
	}
	int ans = 0;
	tr(mp){
		int val = it->second;
		ans+=(val*(val-1))/2;
	}
	cout<<ans<<endl;
    return 0;
}
    



Measured memory_bytes: 29952
///A drunk man will find his way home, but a drunk bird may get lost forever...
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define int long long
#define sz(x) (int)x.size()
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	string s;
	cin >> s;
	for(int i = 0; i < 3; i++){
		if(s[i] == s[i + 1]){
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
	return 0;
}


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

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    string str;
    
    if(A + B + C == 17){
        str = "YES";
    }
    else{
        str ="NO";
    }
    cout << str << endl;
}

Measured memory_bytes: 764
//Name: Spellcasters
//Level: 2
//Category: 二分探索
//Note:

/**
 * r_i をソートしておき、各r_iについて、S-r_iより大きいものの個数を数えればよい。
 * このとき、(i,j)と(j,i)はすべて重複して数えているので、最後に2で割る。
 * r_i*2 > Sのときは(i,i)を数えてしまうので、忘れずに取り除く。
 *
 * オーダーは O(N log N)。
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool solve() {
    int N, S;
    if(!(cin >> N >> S)) return false;
    if(!N && !S) return false;

    vector<int> rs(N);
    for(int i = 0; i < N; ++i) {
        cin >> rs[i];
    }
    sort(begin(rs), end(rs));

    int ans = 0;
    for(int i = 0; i < N; ++i) {
        ans += distance(lower_bound(begin(rs), end(rs), S-rs[i]+1), end(rs));
        if(rs[i]*2 > S) --ans;
    }
    cout << ans/2 << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
int a[100010];

int main()
{
	read(n);
	for(int i=1; i<=n; ++i) read(a[i]);
	ll s = 0;
	for(int i=1; i<=n+1; ++i) s+=abs(a[i]-a[i-1]);
	for(int i=1; i<=n; ++i){
		printf("%lld\n", s - abs(a[i]-a[i-1]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]));
	}
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e3;
int n;

void read()
{
    cin >> n;
}

void solve()
{
    if(n % 2)
        cout << fixed << setprecision(10) << double(n/2 + 1) / double(n) << endl;
    else
        cout << "0.500000000\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define int ll
#define INF (ll)(1e18)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

struct Node
{
	vector<int> con;
	bool tag;
	Node()
	{
		con.clear();
		tag=false;
	}
}; vector<Node> tree;

void build(int n)
{
	tree.resize(n);
	int a,b;
	For(i,1,n-1)
	{
		cin>>a>>b; a--; b--;
		tree[a].con.emplace_back(b);
		tree[b].con.emplace_back(a);
	}
}

queue<int> bfs(queue<int> que)
{
	queue<int> q;
	while(!que.empty())
	{
		int now=que.front(); que.pop();
		for(auto i:tree[now].con)
			if(!tree[i].tag) {q.emplace(i); tree[i].tag=true;}
	}
	return q;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	build(n);
	queue<int> b,w;
	b.emplace(0); tree[0].tag=true;
	w.emplace(n-1); tree[n-1].tag=true;
	int cntw=0,cntb=0;
	while(!b.empty() || !w.empty())
	{
		b=bfs(b); cntb+=sz(b);
		w=bfs(w); cntw+=sz(w);
	}
	if(cntb>cntw) cout<<"Fennec\n";
	else cout<<"Snuke\n";
	return 0;
}











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

int main() {
    ll n, k;
    cin >> n >> k;
    map<ll, ll> m;
    rep(i, n) {
        ll a, b;
        cin >> a >> b;
        m[a] += b;
    }

    ll cnt = 0;
    for (auto e : m) {
        cnt += e.second;
        if (k <= cnt) {
            cout << e.first << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 7456
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=n; i--)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
#define v2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

int a, b, c;
string s;
int main() {
	cin>>a>>b>>c;
	if(a==b and b==c){
		p("Yes");
	}else{
		p("No");
	}
	return 0;
}


Measured memory_bytes: 256