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


int main() {
  int N;
  string S;
  cin>>N>>S;
  
  int sum=1;
  for(int i=0;i<N-1;i++){
    if(S.at(i)!=S.at(i+1)) sum++;
  }
    
  cout<<sum<<endl;
}

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

int main()
{
	for (int i = 0; i < 3; i++){
		int hin, min, sin, hout, mout, sout, total;
		cin >> hin >> min >> sin >> hout >> mout >> sout;

		total = hout * 3600 + mout * 60 + sout - hin * 3600 - min * 60 - sin;

		cout << total / 3600 << " " << (total % 3600) / 60 << " " << total % 60 << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#ABC109-C
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)

n,X = map(int,input().split())
x = list(map(int,input().split())) 

x.append(X)
x.sort()

kosa = []

for i in range(1,n+1):
    k = (x[i]-x[i-1])
    kosa.append(k)
    
print(gcd(*kosa))

Measured memory_bytes: 20564
//#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, n; cin >> a >> b >> n;
	int k =min(b-1, n);
	int ans = k * a / b;
	cout << ans << endl;
}


Measured memory_bytes: 3648
#include<stdio.h>

int main(){

	int i,k,H,W;
	
	while (1){
		scanf("%d %d", &H, &W);
		if (H == 0 && W == 0)break;
		for (i = 0; i < H; i++){
			for (k = 0; k < W; k++){
				if ((k+i)%2==0){
					printf("#");
				}
				else{
					printf(".");
				}
			}
			printf("\n");
		}

		printf("\n");

	}

	return 0;

}


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

int main(){	
	int n,k;
	cin >> n >> k;
	vector<int> p(n);
	rep(i,n){ cin >> p[i];}
	sort(p.begin(), p.end());
	int ans = 0;
	rep(i,k){
		ans += p[i];
	}
	cout << ans << endl;
	return 0;
}




Measured memory_bytes: 3520
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
  string s;
  cin >> s;
  string ans;
  int len = s.size();
  bool check = false;
  rep(i, len){
    if(s.at(i) != 'A'){
      ans += s.at(i);
      check = false;
    }
    else if(check || ans == "K" || ans =="KI"){
      cout << "NO" << endl;
      return 0;
    }
    else
      check = true;
    
  }
  if(ans == "KIHBR")
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;


int main() {

    fast
    int n,k;
    cin>>n>>k;

    int temp;
    int cnt=0;

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

            cin>>temp;
            if(temp>=k)cnt++;
    }

    cout<<cnt;


	return 0;
}


/*
ll  modularExponentiation(ll x,ll n,ll M)
{

    ll result=1;

    while(n>0)
    {

	if(n%2==1)

 result=(result*x)%M;

  x=(x*x)%M;

  n=n/2;

}

  return result;
}



*/




Measured memory_bytes: 256
// ==============================================
// Library
// ==============================================
#define _CRT_SECURE_NO_WARNINGS

// When you are using the gcc compiler, you need only the following lines.
// #include <bits/stdc++.h>

// When you are using other compilers, you need the following line instead.
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// competitive macro
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i ,n) for (int i = (n) - 1; i >= 0; i--)
#define LL long long
#define ULL unsigned long long

// If you use this function, "cin" speeds up.
// However, you can not mix "cin" and "scanf", "cout" and "printf".
void fastIOS()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
}
// ==============================================
// ==============================================

array<int, 123> asciiBet = {};

int main()
{
	fastIOS();
	
	string w;
	cin >> w;
	int wSize = w.size();

	REP(i, wSize)
	{
		asciiBet[w[i]]++;
	}

	bool fBeatiful = true;
	FOR(i, 'a', 'z' + 1)
	{
		if (asciiBet[i] % 2 == 0)
			continue;
		else
		{
			cout << "No" << "\n";
			return 0;
		}
	}

	cout << "Yes" << "\n";
	return 0;
}

Measured memory_bytes: 256
NM = list(map(int, input().split()))
from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    # reduce(mul, 範囲)で範囲までの階乗計算
    # range (n, n-r, -1) -> n から n-rまで，逆順
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def main():

    kiki = 0
    gugu = 0

    if NM[0] > 1:
        gugu = cmb(NM[0], 2)
    if NM[1] > 1:
        kiki = cmb(NM[1],2)


    print(kiki+gugu)



if __name__ == '__main__':
    main()

Measured memory_bytes: 3572
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define reps(i,x) for(ll i=1;i<=(ll)(x);i++)
#define rrep(i,x) for(ll i=((ll)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(ll)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
ll h[100005];
ll dp[100005];
int main() {
    ll n, k;
    cin >> n >> k;
    reps(i, n){
        cin >> h[i];
    }
    sort(h, h+n+1);

    ll mn = 1L << 60;
    reps(i, n -k+1){
        mn = min(mn,h[k-1+i]-h[i]);
    }
    cout << mn << endl;
}



Measured memory_bytes: 1024
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node {int parent, left, right;};

Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int u, int d){
  if(u==NIL) return;
  D[u]=d;
  setDepth(T[u].left, d+1);
  setDepth(T[u].right, d+1);
}

int setHeight(int u){
  int h1=0,h2=0;
  if(T[u].left!=NIL) h1+=setHeight(T[u].left)+1;
  if(T[u].right!=NIL) h2+=setHeight(T[u].right)+1;
  return H[u]=(h1>h2?h1:h2);
}

int getSibling(int u){
  if(T[u].parent==NIL) return NIL;
  if(T[T[u].parent].left!=u&&T[T[u].parent].left!=NIL) return T[T[u].parent].left;
  if(T[T[u].parent].right!=u&&T[T[u].parent].right!=NIL) return T[T[u].parent].right;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",getSibling(u));
  int deg=0;
  if(T[u].left!=NIL) deg++;
  if(T[u].right!=NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].parent==NIL){
    printf("root\n");
  }
  else if(T[u].left==NIL&&T[u].right==NIL){
    printf("leaf\n");
  }
  else printf("internal node\n");
}

int main(){
  int v,l,r,root=0;
  scanf("%d",&n);

  for(int i=0;i<n;i++) T[i].parent=NIL;

  for(int i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].left=l;
    T[v].right=r;
    if(l!=NIL) T[l].parent=v;
    if(r!=NIL) T[r].parent=v;
  }

  for(int i=0;i<n;i++) if(T[i].parent==NIL) root=i;

  setDepth(root,0);
  setHeight(root);

  for(int i=0;i<n;i++) print(i);

  return 0;
}



Measured memory_bytes: 2712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}
const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int>vec;
    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    sort(vec.begin(),vec.end());
    if(vec.size()%2!=0){
        for(int i = 1;i < n;i+=2){
            if(vec[i] != vec[i+1]){
                cout << 0 << endl;
                return 0;
            }
        }
        if(vec.size() == 1){
            cout << 1 << endl;
            return 0;
        }
        ll ans = 2;
        for(int i = 1;i < (vec.size()-1)/2;i++){
            ans *=2;
            ans %=1000000007;
        }
        cout << ans << endl;
        //ll ans = pow(2,(vec.size()-1)/2);
        //cout << ans%1000000007  << endl;
    }else{
        for(int i = 0;i < n;i+=2){
            if(vec[i] != vec[i+1]){
                cout << 0 << endl;
                return 0;
            }
        }
        if(vec.size() == 1){
            cout << 1 << endl;
            return 0;
        }
        ll ans = 2;
        for(int i = 1;i < vec.size()/2;i++){
            ans *=2;
            ans %=1000000007;
        }
        cout << ans << endl;
        //ll ans = pow(2,vec.size()/2);
        //cout << ans%1000000007  << endl;
    }
}





Measured memory_bytes: 892
// Problem : D - Moving Piece
// Contest : AtCoder - AtCoder Beginner Contest 175
// URL : https://atcoder.jp/contests/abc175/tasks/abc175_d
// Memory Limit : 1024 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e18
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

void solve(){
    int n,k;
    cin>>n>>k;
    vi p(n),c(n);
    for(int &i : p) cin>>i, i--;
    for(int &i : c) cin>>i;
    int ans = -inf;
    for(int i=0;i<n;i++){
        vi scores;
        int cur = i, score = 0;
        int f = 0;
        for(int j=0;j<k;j++){
            if(cur == i && f)  break;
            cur = p[cur];
            score += c[cur];
            scores.pb(score);
            f = 1;
        }
        int cycle = sz(scores);
        int best = -inf;
        for(int j : scores) best = max(best,j);
        if(scores.back() > 0 && cur == i){
            int loops = k/cycle;
            int alt = best+(loops-1)*scores.back();
            best = max(best,alt);
            int extra = k%cycle;
            int tmp = loops*scores.back();
            int tmp1 = 0;
            for(int j=0;j<extra;j++) tmp1 = max(tmp1,scores[j]);
            best = max(best,tmp+tmp1);
        }
        ans = max(ans,best);
    }
    cout<<ans;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3792
#include <stdio.h>

int main(void)
{
        int n,d,x,i,j,c;

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

        int a[n];

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

        c=0;
        for(i=0;i<n;i++){
                for(j=0;a[i]*j+1<=d;j++){
                        c++;
                }
        }
        printf("%d\n",c+x);
        return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

const ll BIG = 1000000007LL;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

const int Max = 110;
ll A, B, C, D;

ll gcd(ll a, ll b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    
    return b ? gcd(b, a % b) : a;
}

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

// vに最も近くv以下のxの倍数
ll closest_less(ll v, ll x) {
    return (v / x) * x;
}

// vに最も近くv以上のxの倍数
ll closest_more(ll v, ll x) {
    return (v + x - 1) / x * x;
}

ll count(ll u, ll l, ll x) {
    ll up = closest_less(u, x);
    ll lp = closest_more(l, x);
    // printf("%lld, %lld\n", up, lp);
    if (up < l || lp > u) return 0;
    return (closest_less(u, x) - closest_more(l, x)) / x + 1;
}

int main(int argc, const char * argv[]) {
    cin >> A >> B >> C >> D;

    ll all = B - A + 1;
    ll cC = count(B, A, C);
    ll cD = count(B, A, D);
    ll cCD = count(B, A, lcm(C, D));

    ll ans = all - cC - cD + cCD;

    // printf("%lld,%lld,%lld,%lld\n", all, cC, cD, cCD);
    output(ans);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
typedef pair<int, int> P;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int X[N];
  FOR(i,0,N) {
    cin >> X[i];
  }
  int ans = 2e9;
  FOR(P,1,101) {
    int cost = 0;
    FOR(i,0,N) {
      cost += (X[i] - P) * (X[i] - P);
    }
    ans = min(ans, cost);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 int arr[100000+5]={0};
 int arr_2[100000+5];
  
int main()
{
 int n,k;
 while(cin>>n>>k)
 {
   if(n==0&&k==0) break;
   int num;
   int count=0;
   bool flag_2=false;
   for(int i=0;i<k;i++)
   {
     cin>>num;
     if(num==0) flag_2=true;
     else
     {
       //count++;
       arr[num]++; 
       arr_2[i]=num;
     }         
   }
   if(!flag_2)
   {
     int sum=0;
     int max=0;
     for(int i=1;i<=n;i++)
     {
       
       while((i<=n)&&arr[i])
       {
         sum++;
         i++;               
       }       
       if(sum>max) max=sum;
       sum=0; 
     }       
     cout<<max<<endl;    
   }
   else
   {
     int blank[100000+5];
     int seg[100000+5];
     int sum;
     int sum_2;
     int max=0;
     int cnt=0;
     int cnt_2=0;
     int start,end;
     sort(arr_2,arr_2+k);
     for(int i=0;i<k;i++)
     {
       if(i==0&&arr_2[i]!=1) blank[cnt++]=1;
       else if(i==0) blank[cnt++]=0;
       else
       {
         int temp=arr_2[i]-arr_2[i-1];
         if(temp==2) blank[cnt++]=1;
         else if(temp>2) blank[cnt++]=2;    
       }        
     }
     //int temp=n-arr_2[k-1];
     //if(temp>=1) blank[cnt++]=1;
     for(int i=1;i<k;i++)
     {
       sum=1;
       while((i<k)&&(arr_2[i]-arr_2[i-1]==1))
       {
         sum++;
         i++;
       }
       seg[cnt_2++]=sum;          
     }
     for(int i=0;i<cnt_2;i++)
     {
       if(i==0) max=seg[i]+1;
       else
       {
         if(blank[i]==1) 
         {
           sum_2=seg[i]+1+seg[i-1];
           if(sum_2>max) max=sum_2;                
         }    
         else if(blank[i]==2)
         {
           sum_2=seg[i]+1;
           if(sum_2>max) max=sum_2;     
         }
       }
     }
     cout<<max<<endl;
   }  
 }
 //while(1);     
 return 0;  
}
 

Measured memory_bytes: 4012
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;
  vll as(n), bs(n);
  rep(i,n) cin >> as[i];
  rep(i,n) cin >> bs[i];

  vll fs = as;
  Sort(fs);

  ll a, b;
  ll now = 1;
  do {  
    if(fs == as){
      a = now;
    }
    if(fs == bs){
      b = now;
    }
    now++;
  } while (next_permutation(fs.begin(), fs.end()));

  cout << abs(a-b) << endl;

  return 0;
}


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

int main() {
    int a, b; cin >> a >> b;
    if (a + b == 15) cout << "+" << endl;
    else if (a * b == 15) cout << "*" << endl;
    else cout << "x" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int n;
	cin >>n;
	cout << a[n-1];
} 

Measured memory_bytes: 256
import math


def main():
    n = int(input())
    # n, k = map(int, input().split())
    # h = list(map(int, input().split()))
    # s = input()
    # h = [int(input()) for _ in rane(n)]

    d = []
    for _ in range(n):
        j, k = map(int, input().split())
        d.append([j, k])

    count = 0
    for i in range(n):
        if d[i][0] == d[i][1]:
            count += 1
            if count == 3:
                print("Yes")
                exit()
        else:
            count = 0

    print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 62744
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace std::chrono;

#define ll long long
#define ld long double
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#ifdef LL
const ll inf = 1e9;
#else 
const ll inf = 1e18;
#endif

const int mod = 1e9 + 7;
const int mod2 = 998244353;

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

// lower bound returns first element greater than the value

high_resolution_clock::time_point curTime() { return high_resolution_clock::now(); }
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} //Just add this as a third argument to sort() while sorting an array of pairs; NO NEED FOR ANY ARGUMENTS;
template <typename T>
T fact(T a, T mod){ int res = 1, i; for (i = 2; i <= a; i++){ res *= i; res%=mod;} return res; }
template <typename T>
ll powmod(T a,T b,ll m){ ll ans=1; while(b>0){if(b&1){ans*=a;ans%=m;}a*=a;a%=m;b>>=1;} return ans; }
template <typename T>
ll power(T a, T b){ ll ans=1; while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;}
template <typename T>
T gcd(T a,T b){ return (b?__gcd(a,b):a); }
template <typename T>
T lcm(T a, T b){ return (a*(b/gcd(a,b))); }
template <typename T>
T cl(T a, T b){ return (a+b-1)/b; }
template <typename T>
T set_bits(T a)
{ return __builtin_popcount(a); }
template <typename T>
T add_self(T& a, T b, T mod){ a+=b; if(a>=mod){ a-=mod; } }
template <typename T>
T to_upper(T s){ transform(s.begin(), s.end(), s.begin(), ::toupper); return s; }
template <typename T>
T to_lower(T s){ transform(s.begin(), s.end(), s.begin(), ::tolower); return s; }

void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}
void sub_self(int& a, int b) {
    a -= b;
    if(a < 0) {
        a += mod;
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> dp(k + 1);
    // dp[i] - the number of ways such that we used i candies so far
    dp[0] = 1;
    for(int child = 0; child < n; ++child) {
        int up_to;
        scanf("%d", &up_to);
        vector<int> fake(k + 1);
        for(int used = k; used >= 0; --used) {
            int tmp = dp[used];
            int L = used + 1;
            int R = used + min(up_to, k - used);
            if(L <= R) {
                add_self(fake[L], tmp);
                if(R + 1 <= k) {
                    sub_self(fake[R+1], tmp);
                }
            }
            //~ for(int i = L; i <= R; ++i) {
                //~ add_self(dp[i], tmp);
            //~ }
        }
        int prefix_sum = 0;
        for(int i = 0; i <= k; ++i) {
            add_self(prefix_sum, fake[i]);
            add_self(dp[i], prefix_sum);
        }
    }
    printf("%d\n", dp[k]);
}


Measured memory_bytes: 4136
#include <stdio.h>


int main()
{	 
	long long x, y;
	int ans = 0;
	
	scanf("%lld%lld", &x, &y);
	while(x <= y){
		ans++;
		x <<= 1;
	}
	printf("%d\n", ans);	
		
	return 0;
}

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

int main(){
	int min=101; 
	int num[3][3]={0};
	int a[3]={0};
	int b[3]={0};
	for(int k=0;k<3;k++){
		cin>>num[k][0]>>num[k][1]>>num[k][2];
		if(num[k][0]<min){
			min=num[k][0];
		}
	}
	while(1){
		if(min==-1){
			cout<<"No"<<endl;
			break;
		}
		b[0]=min;
		for(int k=0;k<3;k++){
			a[k]=num[k][0]-min;
		}
		for(int k=1;k<3;k++){
			b[k]=num[0][k]-a[0];
		}
		if(b[1]==num[1][1]-a[1]&&b[1]==num[2][1]-a[2]){
			if(b[2]==num[1][2]-a[1]&&b[2]==num[2][2]-a[2]){
				cout<<"Yes"<<endl;
				break;
			}
		}
		min--;
	}

	return 0;
	
}

Measured memory_bytes: 256
# B - Common Raccoon vs Monster

# モンスターの体力はHであり、N種類の必殺技で戦う
# i番目の技で体力をAi減らすことができる
# 体力を0にできるならYes、できないならNoを出力する


H, N = map(int, input().split())
A = list(map(int, input().split()))

answer = H - sum(A)

if answer <= 0:
    print('Yes')
else:
    print('No')


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

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define int ll
#define endl "\n"
#define all( x ) x.begin(), x.end()
#define rev_all( x ) x.rbegin(), x.rend()
#define fast ios::sync_with_stdio(0);cin.tie(0);

typedef unsigned long long ull;

const int mod = 1e9 + 7;
const int inf = 1e12 + 5;
const long double PI = 3.141592653589793;

void solve(){
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  while(b <= a && k>0){
    b*=2;
    k--;
  }
  while(c <= b && k > 0){
    c*=2;
    k--;
  }
  cout << ((b > a && c > b) ? "Yes" : "No") << endl;
}
signed main(){
  fast;
  int t = 1;
  //cin >> t;
  for(int i = 1; i <= t; i++){
    solve();
  }
}

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

public class Main{
    static int answer(int[] A, int n){
        int[] dp = new int[n];
        dp[n-1] = 0;
        dp[n-2] = Math.abs(A[n-1] - A[n-2]);
        for(int i=n-3;i>=0;i--){
            dp[i] = Math.min(dp[i+2]+Math.abs(A[i+2]-A[i]),dp[i+1]+Math.abs(A[i+1]-A[i]) );
        }
        // for(Integer i:dp){
        //     System.out.print(i+" ");
        // }
        return dp[0];
    }
    public static void main(String[] args) throws IOException{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] A = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0;i<n;i++){
                A[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(answer(A,n));
    }
}


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

int main()
{
	int i, j, k, l, m, n, p, q,N;
	long long int sum, flag,cc,cnt;
	sum = 0;
	flag = 0;
	cc = 0;
	cnt = 1;
	cin >> N;
	vector<int>A(N);
	for (i = 0; i<N; i++) {
		cin >> A[i];
	}
	int ans[101] = {};
	int temp;
	temp = A[0];
	for (i = 1; i < N; i++) {
		if (A[i] == temp) {
			cnt++;
		}
		else {
			temp = A[i];
			sum += cnt / 2;
			cnt = 1;
		}
	}
	sum += cnt / 2;
	cout << sum << endl;


    return 0;
}



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

using namespace std;

int main() {
  long long n, ipt, cnt;
  vector<long long> d;

  cin >> n;

  for (long long i = 0; i < n; i++)
  {
    cin >> ipt;
    d.push_back(ipt);
  }

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

  cnt = 1;
  for (long long i = 0; i < n - 1; i++)
  {
    if (d[i] != d[i + 1])
    {
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
N, M = gets.split.map(&:to_i)

if N == 1 && M == 1
  puts 1
elsif N == 2 || M == 2
  puts 0
else
  n = N > 2 ? (N - 2) : 1
  m = M > 2 ? (M - 2) : 1
  puts n * m
end


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


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

    int sum=0;
    for(int i=0; i<N+1; i++){
        sum +=abs(A[i]-A[i+1]);
    }

    for(int i=1; i<N+1; i++){
        cout << sum - abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]) << endl;
    }
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	void Solve() {
		string s = "abcdefghijklmnopqrstuvwxyz";
		char c; cin >> c;
		auto i = s.find(c);
		i++;
		cout << string("") + s[i] << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x): x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    var(i64, X);
    i64 ans = 0;
    ans += (X / 500) * 1000;
    X %= 500;
    ans += (X / 5) * 5;

    print(ans);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
const int MAX_C = 2010;
long long Com[MAX_C][MAX_C];

void calc_com() {
  memset(Com, 0, sizeof(Com));
  Com[0][0] = 1;
    for (int i = 1; i < MAX_C; ++i) {
        Com[i][0] = 1;
        for (int j = 1; j < MAX_C; ++j) {
            Com[i][j] = (Com[i-1][j-1] + Com[i-1][j]) % mod;
        }
    }
}
int main(){
  int N, K;
  cin >> N >> K;
  ll ans[K];
  calc_com();
  rep(i, K){
    ans[i] = (Com[N-K+1][i+1]*Com[K-1][i])%mod;
    cout << ans[i] << endl;
  }
  
}

Measured memory_bytes: 31872
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  string t;
  cin >> t;
  rep(i, t.size()){
    if(t[i] == '?'){
      t[i] = 'D';
    }
  }
  cout << t << endl;
}

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

int main(){
long long int k=100;
  long long int x;
  cin >> x;
  int roop=0;
  while(true){
    if(k>=x){
     cout << roop << endl;
     return 0;
    }
    roop++;
    k+=k*0.01;
  }
}

Measured memory_bytes: 3196
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]

dp = [[-1, -1, -1] for _ in range(N)]
dp[0] = [abc[0][0], abc[0][1], abc[0][2]]

for i in range(1, N):
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])+abc[i][0]
    dp[i][1] = max(dp[i-1][0],dp[i-1][2])+abc[i][1]
    dp[i][2] = max(dp[i-1][1],dp[i-1][0])+abc[i][2]
print(max(dp[N-1]))

Measured memory_bytes: 47280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 100005;

int main() {
    int n; cin >> n;
    vint a(n+2,0);
    REP(i,n+1) cin >> a[i];
    int sum = 0;
    REP(i,n+2) sum += abs(a[i]-a[i-1]);
    REP(i,n+1) {
        int dif = abs(a[i]-a[i-1])+abs(a[i+1]-a[i]);
        cout << sum-dif+abs(a[i-1]-a[i+1]) << endl;
    }
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long n,l;
    cin>>n>>l;
    string ans="";
    string s[n];
    f(i,0,n){
        cin>>s[i];
    }
    sort(s,s+n);
    f(i,0,n){
        ans+=s[i];
    }
    cout<<ans<<endl;
    return 0;
}


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

// 比較関数


int main(){
 typedef std::pair<long long int, long long int> pair;
    vector<pair> pair_vec;
 long long  int a,b,d=0,sum=0;
  long long int n,m;cin>>n>>m;
for(int i=0;i<n;i++){
  cin>>a>>b;
    pair_vec.push_back(pair(a,b));
 // cout<<a<<b;
}
    

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

   
     for(int i=0;i<n;i++){
       if(pair_vec[i].second<m){
         sum += pair_vec[i].first * pair_vec[i].second;
         m -= pair_vec[i].second;
       }
       else{
         sum += m * pair_vec[i].first;
         m=0;
         break;
       }
     }
         
     cout<<sum<<endl;
     
     
}


Measured memory_bytes: 2420
#include <cstdio>

int main(void){
	
	char c[4];
	char d[4];
	
	scanf("%s",c);
	scanf("%s",d);
	
	if(c[0]==d[2] && c[1]==d[1] && c[2]==d[0]){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<(n);i++)
using namespace std;
int main(){
    int k;
	string s; cin>>s>>k;
	vector<set<int>> a(26);
	rep(i,s.size()) a[s[i]-'a'].insert(i);
 
	set<string> ans;
	rep(p,26){
	    range(l,1,k+1){
    	    for(auto i:a[p]) if(i+l<=s.size()) ans.insert(s.substr(i,l));
	    }
	    if(ans.size()>=k) break;
	}
	auto itr=ans.begin();
	rep(i,k-1)itr++;
    cout<<*itr<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define int long long
#define F first
#define S second
string s;
main(){
	int ans=0,cnt=0,index,pp=0,xx=0,c=0,idx,cc=1;
	string s;
	cin>>s;
	ans=s.size();
	for(int i=0;i<s.size()-1;i++){
		if(s[i]!=s[i+1]){
			ans=min(ans,max(i+1,(int)s.size()-1-i));
			//return 0;
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

vector<int> edges[1234567];

int dfs(int v) {
  vector<int> children;
  for (int to : edges[v]) {
    children.push_back(dfs(to) + 1);
  }
  std::sort(children.begin(), children.end());
  std::reverse(children.begin(), children.end());
  int ret = 1;
  for (int i = 0; i < (int) children.size(); i++) ret = std::max(ret, children[i] + i);
  return ret;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x;
    scanf("%d", &x);
    --x;
    edges[x].push_back(i);
  }
  printf("%d\n", dfs(0) - 1);
}


Measured memory_bytes: 40064
#include <iostream>

using namespace std;

int main() {
    int n,a[200005]={},x;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 4396
import collections
import itertools
n = int(input())
s = []
for _ in range(n):
    s.append(input())
s = [i[0] for i in s if i[0] in "MARCH"]
l = collections.Counter(s)
c = 0
for i,j,k in itertools.combinations(l.keys(), 3):
    c += l[i]*l[j]*l[k]
print(c)

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

int main(){
    int N, x;
    cin >> N >> x;
    vector<int> a(N+1, 0);
    for (int i = 1; i <= N; i++) cin >> a[i];
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        if (a[i] + a[i-1] > x) {
            ans += a[i] + a[i-1] - x;
            a[i] = x - a[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}

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

void solve(){
    
}

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

    int n;
    cin>>n;
    set<int> st;
    for(int i=0; i<n; i++){
        int temp;
        cin>>temp;
        st.insert(temp);
    }
    if(st.size() == n){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
       
    return 0;
}

Measured memory_bytes: 12980
l=list(map(int,input().split()))
d=list(map(int,input().split()))
u={i for i in range(10)}
d_bar=u-set(d)
d_bar={str(i) for i in d_bar}
n=l[0]
n_set=set(str(n))
while True:
    if n_set<=d_bar:
        print(n)
        break
    n=n+1
    n_set=set(str(n))
    

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((LL)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	return modpow(x, MOD-2);
}

int main(){
	int N;
	cin >> N;
	vector<LL> line(N);
	foreach(i, line)cin>>i;
	LL ans = *max_element(ALL(line));
	LL ans2=0;
	foreach(i, line){
		if(abs(ans/2 - ans2) > abs(ans/2 - i))ans2 = i;
	}
	cout << ans << " " << ans2 << endl;
	return 0;
}


Measured memory_bytes: 1024
N,Q=map(int,input().split())
S=input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for q in range(Q):
  l,r=map(int,input().split())
  print(t[r-1] - t[l-1])

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

typedef long long ll;

int main() {
    int N; 
    cin >> N;
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 3 != 0 && i % 5 != 0) ans += i;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 3632
MOD = 1_000_000_007

s = gets.rstrip

# count div 13
dp = Array.new(13, 0)
dp[0] = 1
newdp = Array.new(13, 0)

md = Array.new(130) {|i| [i % 13, i / 10] }


s.length.times do |i|
  if s[i] == '?'
    newdp.fill(0)

    sum = dp.reduce(0, :+)

    md.each do |i, j|
      newdp[i] += dp[j]
    end

    newdp.each_with_index {|x, i|
      dp[i] = x % MOD
    }
  else
    digit = s[i].to_i
    newdp.fill(0)

    13.times do |i|
      newdp[(10 * i + digit) % 13] = dp[i]
    end
    newdp.each_with_index {|x, i|
      dp[i] = x % MOD
    }
  end
end

p dp[5]


Measured memory_bytes: 3964
using System;
using System.Linq;
using System.Collections.Generic;
namespace aizu
{
    public class No0100
    {
        public static void Main()
        {
            string countString;
            while((countString = Console.ReadLine()) != string.Empty && countString != "0") {
                long count = long.Parse(countString);
                if(count == 0) {
                    break;
                }
                long[] value = Enumerable.Repeat<long>(-1, 4000).ToArray();
                List<int> numbers = new List<int>(4000);
                for(int i=0; i < count; ++i) {
                    long[] input = (from q in Console.ReadLine().Split() select long.Parse(q)).ToArray<long>();
                    if(value[input[0]] == -1) {
                        numbers.Add((int)input[0]);
                        value[input[0]] = 0;
                    }
                    if(value[input[0]] < 1000000) {
                        value[input[0]] += input[1] * input[2];
                    }
                }
                List<int> output = (from q in numbers where value[q] >= 1000000 select q).ToList();
                if(output.Count == 0) {
                    Console.WriteLine("NA");
                }
                else {
                    output.ForEach(number => Console.WriteLine(number));
                }
            }
        }
    }
}

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

int main() {
  string s;
  string t;
  cin >> s >> t;
  
  int n = s.size();
  vector<int> vs(n), vt(n);
  vector<int> ms(26, 0), mt(26, 0);
  int cs = 0, ct = 0;

  rep(i, n) {
    int si = s[i] - 'a';
    if (ms[si] == 0) ms[si] = ++cs;
    vs[i] = ms[si];

    int ti = t[i] - 'a';
    if (mt[ti] == 0) mt[ti] = ++ct;
    vt[i] = mt[ti];
  }
  bool ok = true;
  rep(i, n) if (vs[i] != vt[i]) ok = false;
  if (ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 5448
class UnionFind(T) {
	T[] arr;
	this(ulong n) {
		arr.length = n;
		arr[] = -1;
	}
	T root(T x) {
		return arr[x] < 0 ? x : root(arr[x]);
	}
	bool same(T x, T y) {
		return root(x) == root(y);
	}
	bool unite(T x, T y) {
		x = root(x);
		y = root(y);
		if(x == y) return false;
		if(arr[x] > arr[y]) swap(x, y);
		arr[x] += arr[y];
		arr[y] = x;
		return true;
	}
	T size(T a) {
		return -arr[root(a)];
	}
}

alias Edge = Tuple!(long, "a", long, "b", long, "cost");

struct Graph {
	ulong n; // 頂点の数
	Edge[] es; // 辺集合
}

// requires: UnionFind
long kruskal(Graph g) {
	auto uf = new UnionFind!long(g.n);
	long min_cost = 0;

	foreach(e; g.es.sort!((a, b) => a.cost < b.cost)()) {
		if(!uf.same(e.a, e.b)) { // 辺を追加しても閉路ができないなら、採用する。
			uf.unite(e.a, e.b);
			min_cost += e.cost;
		}
	}

	return min_cost;
}

void main() {
	auto ip = readAs!(int[]), V = ip[0], E = ip[1];
	Edge[] es;
	foreach(i; 0..E) {
		auto ip2 = readAs!(int[]), s = ip2[0], t = ip2[1], w = ip2[2];
		es ~= Edge(s, t, w);
	}
	auto g = Graph(V, es);
	writeln(g.kruskal());
}

// ===================================

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

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 5864
#define _USE_MATH_DEFINES
#include<cmath>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

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

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digitsum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
int getdigit(ll a) {
	return to_string(a).size();
}
int countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}
int to_num(char c) {
	if (c >= '0' && c <= '9')return (c - '0');
	else return -1;
}

int main() {
	IOS;
	int sx, sy, gx, gy;
	cin >> sx >> sy >> gx >> gy;
	int dx = gx - sx;
	int dy = gy - sy;
	REP(i, dx)cout << 'R';
	REP(i, dy)cout << 'U';
	REP(i, dx)cout << 'L';
	REP(i, dy)cout << 'D';
	cout << 'D';
	REP(i, dx + 1)cout << 'R';
	REP(i, dy + 1)cout << 'U';
	cout << 'L';
	cout << 'U';
	REP(i, dx + 1)cout << 'L';
	REP(i, dy + 1)cout << 'D';
	cout << 'R' << endl;
}



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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
//     int tc = 1;
//     cin >> tc;
//     while(tc--) {
        
//     }
    
    string s;
    cin >> s;
    int sum = 0;
    for(char c : s) {
        int d = c - '0';
        sum = (sum + d) % 9;
    }
    if(sum % 9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 3756