akhauriyash/Code-Regression huggingface dataset:
#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <array>
#include <set>
#include <queue>
#include <complex>
#include <iterator>
#include <random>
#include <time.h>
#include <tuple>
#include <functional>
#include <list>
#include <limits.h>
#define mp make_pair
#define ni(x) scanf("%d", &(x))
#define nii(x,y) scanf("%d%d",&(x),&(y))
#define mul(x,y) ((ll)(x)*(y)%mod)
#define mtp make_tuple
#define F(i,n) for(int i = 0; i < (n); i++)
#define FF(i,n) for(int i = 1; i <= (n); i++)
#define FE(i,n) for(int i = 0; i <= (n); i++)

#ifndef __GNUG__
int __builtin_popcount(int n) {
	int x = 0;
	while (n)n -= n&(-n), x++;
	return x;
}
#endif

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 1000003;
const int inf = 2012345678;
const ll infl = 9012345678901234567;
const double pi = 3.1415926535897932384626433832795;
//----------------------------------------------------------------------------//

int fact[mod], inv[mod], invfact[mod];

int modpow(int n, int e) {
	if (!e)return 1;
	int t = modpow(n, e / 2);
	t = mul(t, t);
	if (e & 1)t = mul(t, n); return t;
}

int main() {
#ifndef __GNUG__
	freopen("input.txt", "r", stdin);
#endif
	fact[0] = 1;
	for (int i = 1; i < mod; i++) fact[i] = mul(fact[i - 1], i);
	inv[1] = 1;
	for (int i = 2; i < mod; i++)inv[i] = mul(mod - mod / i, inv[mod%i]);
	invfact[0] = 1;
	for (int i = 1; i < mod; i++)invfact[i] = mul(invfact[i - 1], inv[i]);
	int Q; ni(Q);
	while (Q--) {
		int x, d; nii(x, d); int n; ni(n);
		if (d == 0) {
			printf("%d\n", modpow(x, n)); continue;
		}
		int ans = modpow(d, n);
		x = mul(x, inv[d]);
		if (x == 0 || x + n - 1 >= mod) {
			puts("0"); continue;
		}
		printf("%d\n", mul(ans, mul(fact[x + n - 1], invfact[x - 1])));
	}
	
	return 0;
}



Measured memory_bytes: 12672
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

def Base_10_to_n(X, n):
    X_dumy = X
    out = []
    while X_dumy>0:
        n_out = [X_dumy%n]
        n_out.extend(out)
        out = deepcopy(n_out)
        X_dumy = int(X_dumy/n)
    return out

n = INT()
m = Base_10_to_n(n, 26)
#print(m)
m = [i - 1 for i in m]
#print(m)
for i in reversed(range(1, len(m))):
    if m[i] < 0:
        m[i] += 26
        m[i - 1] -= 1
#print(m)
strt = 0
for i in range(len(m)):
    if m[i] < 0:
        strt = i + 1
    else:
        break
ans = ''
for i in m[strt:]:
    ans += chr(ord('a') + i)
print(ans)


Measured memory_bytes: 72664
n = gets.to_i
vs = gets.strip.split(/ /).collect{|item| item.to_i}

v1 = {}
v2 = {}

def put(table, v)
	if num = table[v]
		table[v] = num + 1
	else
		table[v] = 1
	end
end

(n / 2).times{|i|
	put(v1, vs[i * 2])
	put(v2, vs[i * 2 + 1])
}

v1 = v1.to_a.sort_by{|n, count| -count}
v2 = v2.to_a.sort_by{|n, count| -count}

if v1[0][0] != v2[0][0]
	puts n - v1[0][1] - v2[0][1]
else
	if v1.length > 1 && v2.length > 1
		x1 = v1[0][1] + v2[1][1]
		x2 = v1[1][1] + v2[0][1]
		puts n - [x1, x2].max
	elsif v1.length == 1 && v2.length == 1
		puts n / 2
	elsif v1.length == 1
		puts n - v2[1][1]
	else
		puts n - v1[1][1]
	end
end




Measured memory_bytes: 21492
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC167_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string T = Console.ReadLine();

            int lenS = S.Length;
            int lenT = T.Length;

            string subT = T.Substring(0, lenS);

            if (S == subT && lenS + 1 == lenT)
            {
                Console.WriteLine("Yes");
            } else {
                Console.WriteLine("No");
            }
            Console.ReadLine();
        }
        
    }
}

Measured memory_bytes: 25788
import sys
import math

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n, d = map(int, input().split())
    xl = [list(map(int, input().split())) for i in range(n)]

    count = 0
    for i in range(n):
        for j in range(i+1, n):
            sq = math.sqrt(sum([abs(xl[i][k] - xl[j][k])**2 for k in range(d)]))
            if sq == int(sq):
                count += 1

    print(count)


Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>b;i--)
#define mkp(a,b) make_pair(a,b)
#define all(v) v.begin(),v.end()
using namespace std;
bool compare(pair<int,int>& p1,pair<int,int>& p2)
{
    return p1.second<p2.second;
}
int main()
{
    fastio
    ll n;
    cin>>n;
    ll q=n/1000,r=n%1000;
    if(r==0)
        cout<<0<<"\n";
    else
    {
        cout<<(q+1)*1000-n<<"\n";
    }
}

Measured memory_bytes: 3648
a,b = map(int,input().split())
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
print(pow(a,b,1000000007))


Measured memory_bytes: 5612
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;



int main(int argc, char* argv[]){
    std::vector<int> values;
    int N, M;

    cin >> N >> M;
    values.resize(N);

    long long sum = 0;
    for(int i = 0; i < N; ++i){
        cin >> values.at(i);
        sum += values[i];
    }

    double thresh = sum / (4.0 * M);
    std::sort(values.begin(), values.end());
    std::reverse(values.begin(), values.end());

    if(values[M - 1] >= thresh){
        cout << "Yes";
    }
    else{
        cout << "No";
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int N;
	cin >> N;
	
	vector<string> S(N);
	vector<vector<int>> cnt(N, vector<int>(2));
	vector<int> mn(N, INF);
	int allsum = 0;
	REP(i, N) {
		cin >> S[i];
		
		int s = 0;
		REP(j, S[i].size()) {
			++cnt[i][S[i][j] == ')'];
			s += S[i][j] == '(' ? 1 : -1;
			chmin(mn[i], s);
		}
		allsum += cnt[i][0] - cnt[i][1];
	}
	bool ans = allsum == 0;
	
	int bias = S.size() * 2;
	vector<vector<int>> ev(4 * S.size() + 1);
	REP(i, N) ev[bias - mn[i]].push_back(i);
	
	int nest = 0;
	vector<int> d, m; // nest >= m で +d できる。
	REP(t, ev.size()) {
		for (int i : ev[t]) {
			if (nest < t - bias) ans = false;
			else if (cnt[i][0] - cnt[i][1] >= 0) {
				nest += cnt[i][0] - cnt[i][1];
			}
			else {
				d.emplace_back(-(cnt[i][0] - cnt[i][1]));
				m.emplace_back(t - bias);
			}
		}
	}
	
	// d, m を処理
	vector<int> ord(d.size());
	iota(ALL(ord), 0);
	sort(ALL(ord), [&](int x, int y) {
		return m[x] - d[x] > m[y] - d[y];
	});
	
	for (int i : ord) {
		if (nest < m[i]) ans = false;
		nest -= d[i];
	}
	
	puts([&] {
		return ans;
	}() ? "Yes": "No");
	return 0;
}


Measured memory_bytes: 197976
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int N = S.size();
  int ans = N;
  for (int i = 1; i < N; i++){
    if (S[i - 1] != S[i]){
      ans = min(ans, max(i, N - i));
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3664
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    const int MOD = 1000000007;
    static void Main(string[] args)
    {
        new Program().Solve();
    }

    void Solve()
    {
        Scanner cin = new Scanner();
        int n = cin.NextInt();
        long[] x = new long[n];
        long[] y = new long[n];
        int allPatterns = n * (n - 1);
        List<Tuple<long, long>> diffPairs = new List<Tuple<long, long>>();

        if (n == 1)
        {
            Console.WriteLine(1);
            return;
        }

        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                x[i] = cin.NextLong();
                y[i] = cin.NextLong();
                continue;
            }
            x[i] = cin.NextLong();
            y[i] = cin.NextLong();
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == j)
                {
                    continue;
                }
                diffPairs.Add(Tuple.Create(x[i] - x[j], y[i] - y[j]));
            }
        }

        var diffUnique = diffPairs.Distinct();
        Dictionary<Tuple<long,long>, long> count = new Dictionary<Tuple<long, long>, long>();
        foreach (var num in diffUnique)
        {
            long c = diffPairs.Where(e => e.Item1 == num.Item1 && e.Item2 == num.Item2).Count();
            count.Add(num, c); // key: diffNum, value: count of this diff
        }
        
        long maxCount = count.Select(e => e.Value).Max();
        Console.WriteLine(n - maxCount);
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string Next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public char[] ArrayChar()
    {
        return Next().ToCharArray();
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextInt() + add;
        }
        return Array;
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextLong() + add;
        }
        return Array;
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 13920
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
	int n;
  cin >> n;
  long long int A[n];
  // reading into array
  for (int i= 0; i < n; i++)
  {
    cin >> A[i];
    A[i] -= i+1;
  }
  // sorting the array to find median
  sort(A,A+n);
  // finding median
  
  // 
  if(n % 2 == 0) {
    long int median;
    median = (A[n/2-1] + A[n/2])/2;
  //cout << median <<'\n';
  long long int res =0;
  for (int i= 0; i < n; i++)
  {
    (A[i]-median > 0)? res += A[i]-median : res += median-A[i];
  } 
    cout << res <<'\n';
  }
  else{
   long long int median,res = 0;
   median = A[n/2];
   //median1 = A[n/2]
   for (int i = 0; i < n; i++)
     res += abs(A[i]-median);
   cout << res <<'\n';
  }

  
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<pair<int, long long>> p;
    for (int i = 0; i < n; i++) {
        int c; cin >> c; p.emplace_back(c, i);
    }
    multiset<long long> s;
    s.insert(-1); s.insert(-1); s.insert(n); s.insert(n);
    for (int i = 0; i < n; i++) s.insert(i);
    sort(p.begin(), p.end());
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long l1, l2, r1, r2;
        long long mid = p[i].second;
        auto it = s.find(mid);
        l1 = *(--it); l2 = *(--it);
        it = s.find(mid);
        r1 = *(++it); r2 = *(++it);
        long long u = (r1 - mid) * (l1 - l2);
        long long v = (mid - l1) * (r2 - r1);
        ans += (u+v) * (i+1);
        s.erase(s.find(mid));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6512
N = int(input())
A = list(map(int, input().split()))
dic = {}
for nums in A:
  if nums in dic:
    dic[nums] += 1
  else:
    dic[nums] = 1
  if nums-1 in dic:
    dic[nums-1] += 1
  else:
    dic[nums-1] = 1
  if nums+1 in dic:
    dic[nums+1] += 1
  else:
    dic[nums+1] = 1
b = list(dic.values())
print(max(b))

Measured memory_bytes: 18752
# coding: utf-8
# Your code here!
import heapq

N,M=map(int,input().split())
ans=0
l=[1,M]

for i in range(2,-int(-M**0.5//1)):
    if M%i==0:
        l.append(i)
        l.append(int(M/i))

for item in l:
    if (M-N*item)>=0:
        ans=max(ans,item)
    else:
        pass
print(ans)




Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
#define PAI 3.14159265358979
// ver1.6
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int n;
  cin >> n;
  int nowa,nowb;
  cin >> nowa >> nowb;
  int a,b;
  int bai;
  rep(i,0,n-1){
    cin >> a >> b;
    bai = max((nowa-1)/a + 1,(nowb-1)/b + 1);
    nowa = a*bai;
    nowb = b*bai;
  }
  cout << nowa + nowb << endl;
}


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

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= b; ++i)
#define fo(i,a,b) for(int i = a; i<= b; ++i)
#define pii pair<ll,ll> 
#define vec(a) vector<a >
#define all(a) a.begin(),a.end()
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;
using ll = long long;
ll md=MD;

ll exp(ll a,ll b){ll r=1ll;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b>>=1;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll Min(ll a,ll b){if(a<b)return a; return b;}
ll Max(ll a,ll b){if(a>b)return a; return b;}
int32_t main() {
    IOS;

        ll n,xr=0;
        cin>>n;
        vll v(n);
        rep(i,0,n-1) cin>>v[i];
        rep(i,0,n-1)xr^=v[i];
        vll ans(n);
        rep(i,0,n-1)ans[i]=v[i]^xr;
        rep(i,0,n-1)cout<<ans[i]<<" ";



        cout<<'\n';
    return 0;
}

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

#define MAX_N 100000

using namespace std;

int main(void)
{
    int N;
    int p[MAX_N];
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        p[i]--;
    }
    int answer = 0;
    for (int i = 0; i < N; i++) {
        if (p[i] == i) {
            answer++;
            i += 1;
        }
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

ll N;
vector<vector<ll>> seg(26);

// 要求区間 [a, b) 中の要素の和を答える
// k := 自分がいるノードのインデックス
// 対象区間は [l, r) にあたる
ll getsum(ll a, ll b, ll i, ll k = 0, ll l = 0, ll r = -1){
    
    // 最初に呼び出されたときの対象区間は [0, N)
    if(r < 0){
        r = N;
    }
    
    // 要求区間と対象区間が交わらない -> 適当に返す
    if(r <= a || b <= l){
        return 0;
    }
    
    // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
    if(a <= l && r <= b){
        return seg.at(i).at(k);
    }

    // 要求区間が対象区間の一部を被覆 -> 子について探索を行う
    // 左側の子を vl ・ 右側の子を vr としている
    // 新しい対象区間は、現在の対象区間を半分に割ったもの
    ll vl = getsum(a, b, i, 2*k+1, l, (l+r)/2);
    ll vr = getsum(a, b, i, 2*k+2, (l+r)/2, r);
    return vl + vr;
}

int main()
{
    ll n, Q;
    string S;
    cin >> n >> S >> Q;
    ll c = 0;
    while(true){
        if(pow(2, c) >= n){
            N = pow(2, c);   
            break;
        }
        else{
            c++;
        }
    }
    rep(i, 26){
        seg.at(i).resize(2*N-1, 0);
    }
    rep(i, 26){
        rep(j, n){
            if(S.at(j) == 'a' + i){
                seg.at(i).at(j+N-1) = 1;
            }
        }
    }
    rep(i, 26){
        for(ll j = N - 2; j >= 0; j--){
            seg.at(i).at(j) = seg.at(i).at(2*j+1) + seg.at(i).at(2*j+2);
        }
    }
    rep(i, Q){
        ll type;
        cin >> type;
        if(type == 1){
            ll iq;
            char cq;
            cin >> iq >> cq;
            iq--;
            ll x = iq;
            x += N - 1;
            seg.at(S.at(iq)-'a').at(x) = 0;
            while(x > 0){
                x = (x - 1) / 2;
                seg.at(S.at(iq)-'a').at(x) = seg.at(S.at(iq)-'a').at(2*x+1) + seg.at(S.at(iq)-'a').at(2*x+2);
            }
            S.at(iq) = cq;
            x = iq + N - 1;
            seg.at(cq-'a').at(x) = 1;
            while(x > 0){
                x = (x - 1) / 2;
                seg.at(cq-'a').at(x) = seg.at(cq-'a').at(2*x+1) + seg.at(cq-'a').at(2*x+2);
            }
        }
        else{
            ll lq, rq;
            cin >> lq >> rq;
            lq--;
            rq--;
            ll cnt = 0;
            rep(j, 26){
                if(getsum(lq, rq+1, j) >= 1){
                    cnt++;
                }
//                cout << getsum(lq, rq+1, j) << endl;
            }
            cout << cnt << endl;
        }
    }
}

Measured memory_bytes: 217528
#include<bits/stdc++.h>
#define endl enjoy_codeforces
using lint=long long;
void cmx(int&x,int y){if(x<y)x=y;}
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::vector<int>cost={0,2,5,5,4,5,6,3,7,6};
    std::vector<int>ckd(10);
    int n,m;std::cin>>n>>m;
    while(m--){
        int x;std::cin>>x;
        ckd.at(x)=true;
    }
    std::vector<int>dp(n+1,-1);
    dp.at(0)=0;
    for(int i=0;i<=n;i++){
        if(dp.at(i)==-1)continue;
        for(int j=1;j<=9;j++){
            if(!ckd.at(j)||n<i+cost.at(j))continue;
            cmx(dp.at(i+cost.at(j)),dp.at(i)+1);
        }
    }
    std::string ans;
    for(int i=n;i>0;){
        for(int j=0,k=0;j<=10;j++){
            if(j==10){
                ans.push_back('0'+k);
                i-=cost.at(k);
                break;
            }
            if(ckd.at(j)&&cost.at(j)<=i&&dp.at(i)==dp.at(i-cost.at(j))+1)k=j;
        }
    }
    std::cout<<ans<<'\n';
}
/*
 * dp[ 使用本数 ] = 最大桁数 を DP です。
 * dp[ 現在の使用本数 + この数字の使用本数 ] <cmx- dp[ 現在の使用本数 + 1 ] です。
 * 不可能は -1 を入れておきましょう。
 * 復元です。
 * dp[ N ] から始めて、値が 1 減少する中で数字が最大のもので遷移です。
 */



Measured memory_bytes: 256
N, Q = list(map(int, input().split()))
S = input()
T = [list(map(int, input().split())) for _ in range(Q)]

total_list = []
total = 0
try:
  for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
      total += 1
    total_list.append(total)

  for i in range(Q):
    l, r = T[i][0], T[i][1]
    if l != 1:
      print(total_list[r-2]-total_list[l-2])
    else:
      print(total_list[r-2])
except IndexError:
  print(0)

Measured memory_bytes: 30728
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
#include <list>
//AtCoderC++.cpp

using namespace std;

inline int ceileing(int a, int b) {
	return a % b == 0 ? a / b : a / b + 1;
}

int main() {
	int N; cin >> N ;
	cout << "ABC" << N << endl;
}

Measured memory_bytes: 256
S=input()

O=0
E=0

for i in range(len(S)):
    if i%2==0:
        if S[i]=="0":
            O+=1
        else:
            E+=1
    else:
        if S[i]=="0":
            E+=1
        else:
            O+=1
print(min(O,E))

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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            int n = int.Parse(Console.ReadLine()) % 10;

            switch (n)
            {
                case 2:
                case 4:
                case 5:
                case 7:
                case 9:
                    Console.WriteLine("hon");
                    break;
                case 0:
                case 1:
                case 6:
                case 8:
                    Console.WriteLine("pon");
                    break;
                default:
                    Console.WriteLine("bon");
                    break;
            }

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27548
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as BS
main=do
 [n,m]<-map read.words<$>getLine
 ab<-replicateM m (map BS.unpack.BS.words<$>BS.getLine)
 putStrLn(if (g "0" True (sort (foldr (++) [] ab))) then "YES" else "NO")
  where g _ b [] = b
        g a b (c:l) = if a==c then (g c (not b) l) else (b&&(g c False l))

Measured memory_bytes: 85372
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

N, A, B = map(int, input().split())
ans = 0
for nn in range(1, N + 1):
    ns = list(str(nn))
    ns = list(map(int, ns))
    # print(ns)
    if A <= sum(ns) and sum(ns) <= B:
        ans += nn
print(ans)


Measured memory_bytes: 9192
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int N;
    vector<int> h;
    cin >> N;
    int count = 0;

    for (size_t i = 0; i < N; i++) {
        int x;
        cin >> x;
        h.push_back(x);
    }

    int M = *max_element(h.begin(), h.end());
    for (size_t i = 1; i <= M; i++) {
        bool prev = false;
        for (size_t j = 0; j < N; j++) {
            if (i <= h[j]) {
                if (!prev) {
                    count++;
                }
            }
            prev = (i <= h[j]);
        }
    }
    cout << count << "\n";
}

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

int a[2], k;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> a[0] >> a[1] >> k;
	for(int i=0; i<k; ++i){
		int j = i%2;
		if(a[j] % 2 == 1) --a[j];
		a[1-j] += a[j] / 2;
		a[j] /= 2;
	}
	cout << a[0] << " " << a[1] << "\n";
}

Measured memory_bytes: 256
N, M = map(int, input().split())
s = []
for _ in range(M):
    inp = [int(x) for x in input().split()][1:]
    lst_ = [0] * N
    for i in inp:
        lst_[i - 1] = 1
    s.append(lst_)


p = [int(i) for i in input().split()]
count = 0

for i in range(2 ** N):
    lst = [0]*M
    for j in range(N):
        if i & 1:
            for k in range(M):
                lst[k] += s[k][j]
        i >>= 1
    flag = 1
    for j in range(M):
        flag *= 1 - (lst[j] & 1)^ p[j]
    if flag:
        count += 1

print(count)

Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod;
#define mul(a,b) a=a*b%mod;
vector<ll> a,b,c;
void make_edge(ll x,ll y,ll z){
    a.push_back(x+1);
    b.push_back(y+1);
    c.push_back(z);
}
int main(){
  ll L; cin>>L;
  ll n=0,x=1;
  for(;x<=L;n++){x*=2;}
  for(int i=0;i<n-1;i++){
      make_edge(i,i+1,(1<<(n-i-2)));
      make_edge(i,i+1,0);
  }
  for(int i=1;i<n;i++){
      if((L&(1LL<<(n-1-i)))==0)continue;
      ll p=L/(1LL<<(n-i));
      p*=(1<<(n-i));
      make_edge(0,i,p);
  }
  cout<<n<<" "<<a.size()<<endl;
  for(int i=0;i<a.size();i++){
      cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
n = gets.to_s.to_i
a = gets.to_s.split.map{|i|i.to_i}

c = Array.new(2*10**5+1,0)
a.each do |k|
  c[k] += 1
end

s = 1
c.each{|k| s += k * (k-1)/2 if k > 0}

a.each do |k|
  puts s - c[k]
end

Measured memory_bytes: 23172
#include <stdio.h>
#include <math.h>
#define MAX 1000

int main(){
   int n;
   int i, j=0, sum;
   int score[MAX];
   double ave, tmp;
   double dev[MAX];

   while(1){
       scanf("%d", &n);
       if(n==0)break;
       sum=0;
       for(i=0;i<n;i++){
           scanf("%d", &score[i]);
           sum+=score[i];
       }
       ave=(double)sum/(double)n;
       tmp=0.0;
       for(i=0;i<n;i++){
           tmp+=pow(score[i]-ave, 2);
       }
       dev[j++]=sqrt(tmp/(double)n);
   }
   for(i=0;i<j;i++){
       printf("%f\n", dev[i]);
   }
   return 0;
}



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

#define INF 1.1e9
#define LINF 1.1e18
#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 pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

int p,q,a,n,num[7],ans;

void dfs(int x,int y,int z) {
	int sum=0;
	REP(i,x) sum+=y/num[i];
	if(p*y==sum*q) ans++;
	if(p*y<sum*q) return;
	if(x==n) return;
	FOR(i,z,a+1) {
		if(i*y<=a) {
			num[x]=i;
			dfs(x+1,y*i,i);
		}
		else break;
	}
}

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

	while(true) {
		cin>>p>>q>>a>>n;
		if(p==0&&q==0) break;
		ans=0;
		dfs(0,1,1);
		cout<<ans<<endl;
	}

	return 0;
}



Measured memory_bytes: 3152
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn];
inline void init(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
} 
inline void solve(){
	int temp=n; n=0;
	for (int i=1;i<=temp;i++){
		if (a[i]==a[i+1]){
			a[++n]=a[i];
			i++;
		}
	}
	if (n<2) puts("0");
		else printf("%lld\n",1ll*a[n]*a[n-1]);
}
int main(){
	init();
	solve();
	return 0;
} 

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> P;
typedef pair<double, P> E;
const double EPS = 1e-10;
double px[200], py[200], pz[200];
double vx[200], vy[200], vz[200];
double r[200], vr[200];
bool vanish[200];
double ans[200];
int main() {
	int n;
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> px[i] >> py[i] >> pz[i] >> vx[i] >> vy[i] >> vz[i] >> r[i] >> vr[i];
		}
		vector<E> ev;
		for (int i = 0; i < n; i++) {
			ans[i] = r[i] / vr[i];
			ev.emplace_back(r[i] / vr[i], P(i, -1));
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				double a = pow(vx[j] - vx[i], 2) + pow(vy[j] - vy[i], 2) + pow(vz[j] - vz[i], 2) - pow(vr[i] + vr[j], 2);
				double b = (px[j] - px[i])*(vx[j] - vx[i]) + (py[j] - py[i])*(vy[j] - vy[i]) + (pz[j] - pz[i])*(vz[j] - vz[i]) + (r[i] + r[j])*(vr[i] + vr[j]);
				double c = pow(px[j] - px[i], 2) + pow(py[j] - py[i], 2) + pow(pz[j] - pz[i], 2) - pow(r[i] + r[j], 2);
				double t = -1;
				if (b*b -  a*c + EPS > 0) {
					double x = (-b + sqrt(b*b - a*c)) / a;
					double y = (-b - sqrt(b*b - a*c)) / a;
					if (x > EPS) t = x;
					if (y > EPS && (t == -1 || t >= y)) t = y;
				}
				if (t > EPS) ev.emplace_back(t, P(i, j));
			}
		}
		sort(ev.begin(), ev.end());
		memset(vanish, 0, sizeof(vanish));
		for (auto e : ev) {
			if (e.second.second == -1) {
				if (vanish[e.second.first]) continue;
				vanish[e.second.first] = 1;
				ans[e.second.first] = min(ans[e.second.first], e.first);
			}
			else {
				if (vanish[e.second.first] || vanish[e.second.second]) continue;
				vanish[e.second.first] = 1;
				vanish[e.second.second] = 1;
				ans[e.second.first] = min(ans[e.second.first], e.first);
				ans[e.second.second] = min(ans[e.second.second], e.first);
			}
		}
		for (int i = 0; i < n; i++) {
			printf("%.15lf\n", ans[i]);
		}
	}
}


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

using namespace std;

int main()
{
   string inpstr;
   int removable_box = 0;
   cin >> inpstr;
   int str_size = inpstr.size();
   stack<char> char_stk;
   char_stk.push(inpstr[0]);
   for(int i = 1; i < str_size;i++)
   {
        if(char_stk.empty())
        {
            char_stk.push(inpstr[i]);
            continue;
        }
        if((inpstr[i] == '0' && char_stk.top() == '1') || (inpstr[i] == '1'&& char_stk.top() == '0'))
        {
            removable_box  = removable_box + 2;
            char_stk.pop();

        }
        else
        {
            char_stk.push(inpstr[i]);
        }

   }

    cout << removable_box;


    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <iomanip>

using namespace std;

int main(void) {
    int N, M;
    cin >> N >> M;
    vector< tuple<int,int,int> > city;
    for(int i=0; i<M; i++) {
        int P, Y;
        cin >> P >> Y;
        city.emplace_back(P, Y, i);
    }
    sort(city.begin(), city.end());
    get<1>(city[0]) = 1;
    for(int i=1; i<M; i++) {
        if(get<0>(city[i]) == get<0>(city[i-1])) {
            get<1>(city[i]) = get<1>(city[i-1]) + 1;
        } else {
            get<1>(city[i]) = 1;
        }
    }
    sort(city.begin(), city.end(),[](auto const &lhs, auto &rhs) {return get<2>(lhs) < get<2>(rhs);});
    for(int i=0; i<M; i++) {
        cout << setfill('0');
        cout << setw(6) << get<0>(city[i]) << setw(6) << get<1>(city[i]) << endl;
    }
    return 0;
}


Measured memory_bytes: 2804
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld double
#define ff first
#define ss second
ll mod = 1000000007;
void fun(){
	int w,h,n;
	cin>>w>>h>>n;
	int l=0,r=w,u=h,d=0;
	for(int i=1;i<=n;++i){
		int x,y,a;
		cin>>x>>y>>a;
		if(a==1){
			l=max(l,x);
		}
		else if(a==2){
			r=min(r,x);
		}
		else if(a==3){
			d=max(d,y);
		}
		else if(a==4){
			u=min(u,y);
		}
	}
	if(u-d>0 and r-l>0)cout<<(u-d)*(r-l)<<"\n";
	else cout<<"0\n";
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t=1; //cin>>t;
	while(t--){
		fun();
	}
	return 0;
}



Measured memory_bytes: 3660
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()

int main() {
		string S;
		cin >> S;

		int ans = 1e9;
		for (char c = 'a'; c <= 'z'; c++) {
				int cnt_max = 0;
				int cnt = 0;
				for (const auto& e: S) {
						if (c == e) {
								cnt_max = max(cnt_max, cnt);
								cnt = 0;
						} else {
								cnt++;
						}
				}
				cnt_max = max(cnt_max, cnt);
				ans = min(ans, cnt_max);
		}
		cout << ans << endl;

		return 0;
}


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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a;
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputDoubleArray(a,N) double a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
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; }

int main(){
  //accumulateを用いる時は、第3引数がint型かどうか注意しましょう！！（自戒）
  
  //input
  inputInt(N);
  
  vector<long> a(N,0), b(N,0);
  
  for(int i=0; i<N; i++){
    cin >> a[i];
    b[i] = abs(a[i]);
  }
  
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());//最も絶対値が小さいa[i]を走査。
  
  int minus = lower_bound(a.begin(),a.end(),0)-a.begin();
  long ans = 0;
  
  if(minus % 2 == 0 || b[0] == 0){//全て正の整数になる時
    ans = accumulate(b.begin(),b.end(),0LL);
  }else{
    ans = accumulate(b.begin(),b.end(),0LL) - b[0]*2;
  }
  
  //output
  output(ans);
  
  return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
template<typename T> void chkmax(T &x,T y){x=x>y?x:y;} 
int a[20];

int main(){
	long long n;read(n);int l=0;
	while(n){a[++l]=n%10;n/=10;}
	rep(i,1,l/2)swap(a[i],a[l-i+1]);
	
	int now=0;int ans=0;
	rep(i,1,l){
		now+=a[i]-1;chkmax(ans,now+(l-i)*9);now++;
		if(l==i)chkmax(ans,now);
	}	
	write(ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstring>
#include <tuple>
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const long long INF = 1e18L + 5; // 10^18
#define fastIN  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fastIN
   // freopen("input.in","r",stdin);
    string s;
    cin>>s;
    int c=0;
    for(int i=0,j=s.size()-1;i<j;i++,j--){
        if(s[i]!=s[j])
           c++;
    }
    cout<<c;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S;

	int N = S.length();
	rep(i, 0, N) printf("x");
	printf("\n");

}







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

ll n, ans;

void dfs(ll x, int binary) {
    if (x > n) return;
    if (binary == 7) ans++;
    
    dfs(10 * x + 3, binary|1);
    dfs(10 * x + 5, binary|2);
    dfs(10 * x + 7, binary|4);
}

int main() {
    cin >> n;
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

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

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}



int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    
    reverse(s.begin(), s.end());
    
    ll count=0,now_count;
    
    rep(i,n){
        if(s[i]=='1') count++;
    }
    
    vector<ll> aaa(n+1,0);
    
    ll now=1;
    now_count=count+1;
    rep(i,n){
        if(s[i]=='0') aaa[i]=now;
        now=now*2%now_count;
    }
    
    now=1;
    now_count=count-1;
    if(now_count!=0){
        rep(i,n){
            if(s[i]=='1') aaa[i]=now;
            now=now*2%now_count;
        }
    }
    
    ll purasu=0,mainasu=0;
    
    
    now=1;
    now_count=count+1;
    rep(i,n){
        if(s[i]=='1') purasu+=now;
        purasu=purasu%now_count;
        now=now*2%now_count;
    }
    
    now=1;
    now_count=count-1;
    if(count-1!=0){
        rep(i,n){
            if(s[i]=='1') mainasu+=now;
            mainasu=mainasu%now_count;
            now=now*2%now_count;
        }
    }else{
        mainasu=0;
    }
    
    
    for(ll i=n-1;i>=0;i--){
        ll nownow;
        if(s[i]=='1'){
            if(count-1==0){
                cout << '0' << endl;
                continue;
            }
            nownow=(mainasu-aaa[i]+count-1)%(count-1);
        }else{
            nownow=(purasu+aaa[i]+count+1)%(count+1);
        }
        
        ll ans=1;
        while(nownow){
            ll abc=nownow;
            ll c=0;
            while(abc){
                if(abc%2==1) c++;
                abc/=2;
            }
            nownow=nownow%c;
            ans++;
        }
        cout << ans << endl;
    }
    
    
    return 0;
}











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

using namespace std;

int main() {

    int A, B, K;
    cin >> A >> B >> K;


    int a = A;
    int b = B;
    int k = K;

    int count = 0;
    int m = min(a, b);
    int ans;

    while (1) {
        if (A % m == 0 && B % m == 0) {
            count++;
            if (count == K) {
                ans = m;
                break;
            }
        }
        m--;
        if (m < 1) {
            return 0;
        }
    }
    cout << ans << endl;

}


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

int main(){
    ll n , m , l ;
    cin >> n >> m >> l ;
    if(n <= m * l )cout << "Yes" << endl ;
    else cout << "No" << endl; 
    //vector<ll> A(n) ; 
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <queue>

using namespace std;

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;
typedef pair<int, int> pii;

int N;

int main(){
    cin >> N;
    vector<bool> ps(N+1, true);

    ps[0] = false;
    ps[1] = false;
    for(int i = 2; i * i <= N; i ++){
        for(int j = 2 * i; j <= N; j += i){
            ps[j] = false;
        }
    }
    vector<ll> fps(N + 1);
    rep(i, ps.size()){
        if(ps[i]){
            int tmp = i;
            for(int j = i; j <= N; j *= i){
                fps[i] += N / j;
            }
        }
    }

    ll ans = 0;
    ll tmp = 0;
    rep(i, fps.size()){
        rep(j, fps.size()){
            rep(k, fps.size()){
                if(fps[i] >= 2 && fps[j] >= 4 && fps[k] >= 4 && i != j && i != k && j != k){
                    tmp ++;
                }
            }
        }
    }
    ans += tmp / 2;

    tmp = 0;
    rep(i, fps.size()){
        rep(j, fps.size()){
            if(fps[i] >= 2 && fps[j] >= 24 && i != j){
                tmp ++;
            }
        }
    }
    ans += tmp;

    tmp = 0;
    rep(i, fps.size()){
        rep(j, fps.size()){
            if(fps[i] >= 4 && fps[j] >= 14 && i != j){
                tmp ++;
            }
        }
    }
    ans += tmp;

    tmp = 0;
    rep(i, fps.size()){
            if(fps[i] >= 74) {
                tmp++;
            }
    }
    ans += tmp;
    cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int s[N],sz[N];
int find(int x){
	return x==s[x]?x:s[x]=find(s[x]);
}
vector<int>e[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) s[i]=i,sz[i]=1;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		int fu=find(u),fv=find(v);
		if(fu!=fv) s[fu]=fv,sz[fv]+=sz[fu];
		//e[u].pb(v),e[v].pb(u);
	}
	int mx=0;
	for(int i=1;i<=n;i++)
		mx=max(mx,sz[i]);
	cout<<mx<<endl;
 	return 0;
}

Measured memory_bytes: 9840
#include <iostream>                                                                                                       

int main(){
   int N;
   std::cin >> N;
   int V[N], C[N];
   int ans = 0;
   for(int i=0; i<N; ++i)
      std::cin >> V[i];
   for(int i=0; i<N; ++i)
      std::cin >> C[i];
   for(int i=0; i<N; ++i){
      if(V[i]>C[i]) ans += V[i] - C[i];
   }   
   std::cout << ans << std::endl;
   
   return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

while (true) {
int H = sc.nextInt();
int W = sc.nextInt();
if (H == 0 && W == 0) {
break;

}int i, j;
for ( i = 0; i < W; i++) {
    System.out.printf("#");
    }System.out.printf("\n");

for ( j = 0 ; j < H-2; j++) {
    System.out.printf("#");
for ( i = 0 ; i < W-2; i++){
    System.out.printf(".");
}System.out.printf("#");
System.out.printf("\n");
}

for ( i = 0; i < W; i++) {
    System.out.printf("#");
    }System.out.printf("\n");
    System.out.printf("\n");
}
}
}


Measured memory_bytes: 60672
#include<bits/stdc++.h>
using namespace std;
     
#define int long long
#define hell 1000000007 
#define endl "\n"
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX_SIZE 100001


 
int min(int a, int b)
{
    if(a>b)
        return b;
    return a;
}
     
int max(int a, int b)
{    
    if(a>b)
        return a;
    return b;
}


int32_t main()
{
    int n;
    string s;
    cin>>n>>s;

    if(n<3200)
        cout<<"red";
    else
        cout<<s;

return 0;
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i > 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  vector<double> v(n);
  REP(i, n) {
    cin >> v[i];
  }
  sort(ALL(v));
  while (v.size() != 1) {
    double a = (v[0] + v[1]) / 2.0;
    v.erase(v.begin());
    v[0] = a;
  }
  cout << v[0] << endl;
  return 0;
}

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

int n;
vector< vector<int> > a;

int Prim() {
  vector<int> color(n);
  vector<int> d(n, 1000000000);
  vector<int> p(n);
  d[0] = 0, p[0] = -1;

  while (true) {
    int min_cost = 1000000000, u;
    for (int i = 0; i < n; i++) if (color[i] != 2 && d[i] < min_cost) min_cost = d[i], u = i;
    if (min_cost == 1000000000) break;
    color[u] = 2;
    for (int v = 0; v < n; v++)
      if (color[v] != 2 && a[u][v] != -1)
        if (a[u][v] < d[v]) d[v] = a[u][v], p[v] = u, color[v] = 1;
  }

  int ans = 0;
  for (int i = 0; i < n; i++) if(p[i]!=-1 )ans += a[i][p[i]];

  return ans;
}

int main() {
  cin >> n;
  a.resize(n, vector<int>(n));
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
  cout << Prim() << endl;
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x ,n) for(int i = x; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){
    int n,m,a,b;
    cin >> n >> m;
    int ans[55]={};
    rep(i,m){
        cin >> a >> b;
        ans[a]++;
        ans[b]++;
    }
    rep2(i,1,n+1)cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 3548
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue>
#include <set> 
#include <stack>
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 

#include <math.h>
#include <stdlib.h>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long 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; }

//INT_MAX	2,147,483,647 = 2*1.0e9

vector<vector<int>> chPos(26);

int main(){
  string s, t;
  cin >> s >> t;

  int lenS = s.length();
  
  for(int i = 0; i < lenS; i++){
    int cInt = s[i] - 'a';
    chPos[cInt].push_back(i);
  }
  //2回に分けるのは、vectorの中身がソートされた状態にするため
  for(int i = 0; i < lenS; i++){
    int cInt = s[i] - 'a';
    chPos[cInt].push_back(i+lenS);
  }

  long long ans = 0;
  int curPos = 0;

  int lenT = t.length();
  for(int i = 0; i < lenT; i++){
    int cInt = t[i] - 'a';
    if(chPos[cInt].size() == 0){
        cout << -1 << endl;
        return 0;
    }
    curPos = *lower_bound(chPos[cInt].begin(), chPos[cInt].end(), curPos)+1;
    if(curPos > lenS){
        curPos -= lenS;
        ans += lenS;
    }
  }

  ans += curPos;
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1724
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final char[] tmp = scanner.next().toCharArray();
        final Integer[] array = IntStream.range(0, 4)
                .mapToObj(i -> tmp[i] - '0')
                .toArray(Integer[]::new);

        System.out.println(recursive(array, 1, array[0], Integer.toString(array[0])) + "=7");
    }

    private static String recursive(final Integer[] array, final int index, final int sum, final String formula) {
        if (index == 3) {
            if (sum + array[3] == 7) {
                return formula + "+" + array[3];
            }
            if (sum - array[3] == 7) {
                return formula + "-" + array[3];
            }
            return null;
        }

        final String plus = recursive(array, index + 1, sum + array[index], formula + "+" + array[index]);
        if (plus != null) {
            return plus;
        }

        return recursive(array, index + 1, sum - array[index], formula + "-" + array[index]);
    }
}


Measured memory_bytes: 29396