akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n;
ll k, a[100005], b[100005], dp[100005][35];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	ll ma = 0;
	for (int i = 1; i <= n; i++) {
		bool ok = true;
		for (int p = 0; p < 30; p++) {
			if (k >> p & 1) continue;
			else if (a[i] >> p & 1) ok = false;
		}
		if (ok) ma += b[i];
	}
	for (int i = 1; i <= n; i++) {
		FOR(j, 30) {
			if (!(k >> j & 1)) continue;
			bool ok = true;
			if (a[i] >> j & 1) ok = false;
			for (int p = j+1; p < 30; p++) {
				if (k >> p & 1) continue;
				else if (a[i] >> p & 1) ok = false;
			}
			if (ok) dp[i][j] = dp[i-1][j] + b[i];
			else dp[i][j] = dp[i-1][j];
		}
	}
	for (int j = 0; 1 << j <= k; j++) {
		ma = max(ma, dp[n][j]);
	}
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 29184
"""解説から写経
D種類の配点の問題があり、それらを最低何問解けばG点以上取ることができるかを求める。
続くD行の入力から、配点iの問題数p[i]と追加点c[i]が与えられ、配点は100*(i+1)点となる。
追加点は配点i問題を全て解いたときに得られる追加点。

条件が成立する最小の問題数をansとし、とても大きな値で初期化しておく。
各配点の問題を全て解くか、解かないかを最初に決め、G点以上取れるかどうか、また、その時の解答数を確認していく。(bit全探索)
現在の点数、解答数、解かなかった問題の中で最も配点の高かったものをそれぞれ、s, num, rest_maxとする。
完全に解く問題を解き終えて、G点に満たなかった場合、配点[rest_max]をいくつか解くことでG点が取れるか確認していき、必要な解答数をneedとする。
この時、p[rest_max]-1より多く問題を解く必要があるなら、解答する問題の選択を間違えていると言えるので無視する。
num+needがansよりも少ない場合、ansの値を更新する。
"""
d, g = map(int, input().split())
pc = []
for _ in range(d):
    pc.append(tuple(map(int, input().split())))
ans = float('inf')
for bits in range(1 << d):
    s = 0
    num = 0
    rest_max = -1
    for i in range(d):
        p, c = pc[i]
        if bits >> i & 1:
            s += 100 * (i + 1) * p + c
            num += p
        else:
            rest_max = i
    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s + s1 - 1) // s1  # s1-1を足すのは切り上げ？
        if need >= pc[rest_max][0]:
            continue
        num += need
    ans = min(ans, num)
print(ans)


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

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

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

struct mint {
  ll x;
  mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD)
      x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD - a.x) >= MOD)
      x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  /* 変数名.pow(n) */
  mint pow(ll t) const {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // 以降はMODが素数のみ
  mint inv() const {
    return pow(MOD - 2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};

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

  mint ans = 1;
  ll horyuu = 0;
  ll l = 0;
  ll r = 0;
  rep(i, 2 * N) {
    if (horyuu % 2 == 0) {
      if (S[i] == 'B') {
        horyuu++;
        l++;
      } else {
        ans *= horyuu;
        horyuu--;
        r++;
      }
    } else {
      if (S[i] == 'W') {
        horyuu++;
        l++;
      } else {
        ans *= horyuu;
        horyuu--;
        r++;
      }
    }
  }

  if (l != r) {
    cout << 0 << endl;
    return 0;
  }

  repp(i, 1, N) {
    ans *= i;
  }
  cout << ans.x << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<float.h>
using namespace std;


int main() {
    int n;
    cin >> n ;
    if (n % 28 == 1 || n % 28 == 2 || n % 28 == 3 || n % 28 == 5 || n % 28 == 6 || n % 28 == 9 || n % 28 == 10 || n % 28 == 17|| n % 28 == 13) {
        cout << "No" << endl;
   }
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#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>;
using Graph = vector<vector<int>>;

int main() {
    string s;
    cin >> s;
    int a=s[0] - '0', b=s[1] - '0', c=s[2] - '0', d=s[3] - '0';
    int n=3, sum=a;
    for(int bit = 0; bit < (1<<n); ++bit){
        if(1 & bit){
            sum+=b;
        }else{
            sum-=b;
        }if(2 & bit){
            sum+=c;
        }else{
            sum-=c;
        }if(4 & bit){
            sum+=d;
        }else{
            sum-=d;
        }
        if(sum==7){
            cout << a;
            if(1 & bit){
                cout << '+' << b;
            }else{
                cout << '-' << b;
            }
            if(2 & bit){
                cout << '+' << c;
            }else{
                cout << '-' << c;
            }
            if(4 & bit){
                cout << '+' << d << '=' << 7 << "\n";
            }else{
                cout << '-' << d << '=' << 7 << "\n";
            }
            return 0;
        }
        sum=a;
    }
}


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

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

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

const int N = (int)2e6 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int n, a[N], b[N];
ll ans;
char s[N];
int main()
{
	scanf("%s", &s);
	n = strlen(s);
	if(s[0] == '<'){
		for(int i = 0; i < n; i++)	
			if(s[i] == '<')
				a[i + 1] = max(a[i + 1], a[i] + 1);
			else
				break;
	}
	if(s[n - 1] == '>'){
		for(int i = n - 1; i >= 0; i--)
    		if(s[i] == '>')
				a[i] = max(a[i], a[i + 1] + 1);
			else
				break;
	}

	for(int i = 0; i < n; i++){
		if(s[i] == '>' && s[i + 1] <= '<'){
			a[i + 1] = 0;
			for(int j = i + 2; j <= n; j++)
				if(s[j - 1] == '<')
					a[j] = max(a[j], a[j - 1] + 1);		
				else
					break;
			for(int j = i; j >= 0; j--)
				if(s[j] == '>')
					a[j] = max(a[j], a[j + 1] + 1);		
				else
					break;
		}
	}
	for(int i = 0; i <= n; i++)
		ans += a[i];
	printf("%lld", ans);
	return 0;
}


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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int N;

int main(){ 
  cin >> N;
  if(N == 0){
    cout << 0 << endl;
    return 0;
  }
  string ans;
  while(N){
    int q = N / -2, r = N % -2;
    N = q;
    if(r < 0){
      r += 2;
      N+=1;
    }
    ans += r + '0';
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, L = map(int, readline().split())
    P = [list(map(int, readline().split())) for i in range(N)]
    C = [int(readline()) for i in range(N)]

    P.sort(key = lambda x: (x[0] - x[1]), reverse=1)

    INF = 10**18

    S = [0]*(N+1)
    s = 0
    for i in range(N):
        a, b = P[i]
        S[i+1] = s = s + (a - b)

    min1 = [INF]*(N+1)
    S0 = [0]*(N+1)
    s = 0; cur = INF
    for i in range(N):
        a, b = P[i]
        s += (a - b) - C[i]
        S0[i+1] = s
        min1[i+1] = cur = min(cur, s)

    N0 = 2**N.bit_length()
    data = [INF]*(N0*2)
    s = 0
    S1 = [0]*(N+1)
    for i in range(1, N):
        a, b = P[i]
        s += (a - b) - C[i-1]
        S1[i+1] = data[N0+i] = s
    for i in range(N0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])

    def query(l, r):
        L = l + N0; R = r + N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])

            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    if max(a for a, b in P) >= L:
        write("1\n")
        return

    ans = N+1
    k = N

    m = 0
    for i in range(N-1, -1, -1):
        a, b = P[i]
        m = max(m, a)
        if S[i] + m >= L and min1[i] > 0:
            ans = i+1
            k = i+1

    for i in range(k):
        a, b = P[i]
        left = 0; right = N+1
        while left+1 < right:
            mid = (left + right) >> 1
            if (S[mid] if mid < i+1 else S[mid]-(a-b)) < L-a:
                left = mid
            else:
                right = mid
        r = left
        if r == N:
            continue
        if r < i:
            if min1[r+1] > 0:
                ans = min(ans, r+2)
        else:
            if min1[i] > 0 and query(i+2, r+2) - S1[i+1] + S0[i] > 0:
                ans = min(ans, r+1)

    if ans == N+1:
        write("-1\n")
    else:
        write("%d\n" % ans)
solve()


Measured memory_bytes: 41676
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left
from itertools import combinations

n = ni()

cands = []
for i in range(1,10**5):
    cand = (i+1)*i // 2
    if cand > 10**5:
        break
    cands.append((i+1)*i // 2)
    
if not n in cands:
    print('No')

else:
    setnum = bisect_left(cands, n) + 2
    sets = list(combinations([i for i in range(1,setnum+1)], 2))
    grid = [[] for _ in range(setnum)]
    for i, (set1, set2) in enumerate(sets):
        grid[set1-1].append(i+1)
        grid[set2-1].append(i+1)
    
    print('Yes')
    print(setnum)
    for row in grid:
        print(len(row), *row)

Measured memory_bytes: 19800
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(){
    ll n, w;
    cin >> n >> w;
    vector<p> vp;
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        vp.push_back(p(a, b));
    }
    sort(vp.begin(), vp.end());
    ll count = 0;
    vector<vector<ll>> g(4), sum(4);
    for(ll i = 0; i < n; i++){
        ll a = vp[i].first, b = vp[i].second;
        g[count].push_back(b);
        if(a!=vp[i+1].first) count++;
    }
    sort(g[0].begin(), g[0].end(), greater<ll>());
    sort(g[1].begin(), g[1].end(), greater<ll>());
    sort(g[2].begin(), g[2].end(), greater<ll>());
    sort(g[3].begin(), g[3].end(), greater<ll>());
    //sum[0].push_back(0);sum[1].push_back(0);
    //sum[2].push_back(0);sum[3].push_back(0);
    for(ll i = 0; i < 4; i++){
        sum[i].push_back(0);
        for(ll j = 0; j < g[i].size(); j++){
            ll d = sum[i][sum[i].size()-1];
            ll e = g[i][j];
            sum[i].push_back(d+e);
            //cout << sum[i][sum[i].size()-1] << " ";
        }
        //cout << endl;
    }
    /*for(ll i = 0; i < 4; i++){
        for(ll j = 0; j < sum[i].size(); j++){
            cout << sum[i][j] << " ";
        }
        cout << endl;
    }*/
    ll minw = vp[0].first;
    ll MAX = 0;
    for(ll i = 0; i < sum[0].size(); i++){
        for(ll j = 0; j < sum[1].size(); j++){
            for(ll k = 0; k < sum[2].size(); k++){
                for(ll l = 0; l < sum[3].size(); l++){
                    if(w >= minw*i+(minw+1)*j+(minw+2)*k+(minw+3)*l){
                        MAX = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l], MAX);
                       //cout << minw*i+(minw+1)*j+(minw+2)*k+(minw+3)*l << endl;
                    }
                }
            }
        }
    }
    cout << MAX << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int r,g,b;
  int a;
  scanf("%d%d%d",&r,&g,&b);
  a=10*g+b;
  if(a%4==0){
    printf("YES\n");
  } else{
    printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 1608
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define UINF 18446744073709551615
#define F first
#define S second
#define ll long long
using namespace std;
ll n,m;
int main(){
	ll i;
	cin>>n>>m;
	if(n%2==0)
	{
		for(i=0;i<m;i++)
		{
			if(i<=m/2&&i*2!=m)
			{
				cout<<i+1<<" "<<n-i<<endl;
			}
			else
			{
				cout<<i+1<<" "<<n-i-1<<endl;
			}
		}
	}
	else
	{
		for(i=0;i<m;i++)
		{
			cout<<i+1<<" "<<n-i<<endl;
		}
	}
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define int ll

const ll MOD = 1000000007;
const ll INF_LL = (ll)1000000007 * 1000000007;
const int INF_INT = (int)1000000007;
const double PI = 3.14159265358979323846;

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define irep(itr, st) for (auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for (auto itr = (st).rbegin(); itr != (st).rend(); ++itr)

#define m0(x) memset((x), 0, sizeof((x)))
#define m1(x) memset((x), -1, sizeof((x)))

// xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define RALL(x) (x).rbegin(), (x).rend()  // sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())     // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))  //最大値を求める
#define MIN(x) *min_element(ALL(x))  //最小値を求める
#define all(x) (x).begin(), (x).end()

//略記
#define pb emplace_back  // vectorヘの挿入
#define mp make_pair     // pairのコンストラクタ
#define F first          // pairの一つ目の要素
#define S second         // pairの二つ目の要素

#define BITCOUNT __builtin_popcount
#define BITCOUNT_LL(x) __builtin_popcountll(x)

#define perm(c)             \
  sort(all(c));             \
  for (bool c##p = 1; c##p; \
       c##p = next_permutation(all(c)))  //順列 123 132 213 231 312 321

#define BIT(n) (1LL << (n))

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ": " << (A) << std::endl;
#else
#define PRINT(A)
#endif

//入力高速化
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

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

signed main() {
  int N, K; cin >> N >> K;
  vector<int> sum(N+1);
  rep(i, N) {
    int a;
    cin >> a;
    a++;
    sum[i+1] = sum[i] + a;
  }
  
  int max = 0;

  rep(i, N-K+1) {
    chmax(max, sum[i+K] - sum[i]);
  }

  double ans = (double)max/(double)2.0;

  cout << ans << endl;
}

Measured memory_bytes: 1792
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

ok = A[-1] * F[0]
ng = 0

while ok-ng>1:
    mid = (ok+ng)//2
    trainings = 0
    for i in range(N):
        t = A[i]-mid//F[i]
        if t > 0:
            trainings += t
    if trainings <= K:
        ok = mid
    else:
        ng = mid
trainings = 0
for i in range(N):
    t = A[i]-ng//F[i]
    if t>0:
        trainings += t
if trainings<=K:
    print(ng)
else:
    print(ok)

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

int main(){
	float a,b;
	cin>>a>>b;
	if(b==1){
		cout<<0<<endl;
	}
	else{
		float c=1,i=0;
		while(c<b){
			c+=a-1;
			i++;
		}
		cout<<i<<endl;
	}
	return 0;
}

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

int main(){
    int i,SUM=0,count=0;
    double a[101]={},sum=0,n;
    scanf("%lf",&n);
    for (i=0; i<n; i++) scanf("%lf",&a[i]);
    for (i=0; i<n; i++) sum+=a[i];
    sum/=n;
    if (sum>=(double)(int)sum+0.5) SUM=(int)sum+1;
    else SUM=(int)sum;
    for (i=0; i<n; i++) count+=(a[i]-SUM)*(a[i]-SUM);
    printf("%d",count);
    return 0;
}



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

using namespace std;

using i64 = long long;

const i64 MOD = i64(1e9) + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

vector<vector<vector<vector<pair<int,int>>>>> dp;
vector<vector<vector<vector<bool>>>> flag;

pair<int,int> f(int sx, int sy, int ex, int ey){
    if(flag[sx][sy][ex][ey])
        return dp[sx][sy][ex][ey];
    for(int i = sx + 1; i < ex; ++i){
        auto p1 = f(sx, sy, i, ey);
        auto p2 = f(i, sy, ex, ey);
        if(p1.second < 0 || p2.second < 0)
            continue;
        chmax(dp[sx][sy][ex][ey], make_pair(p1.first + p2.first, min(p1.second, p2.second)));
    }
    for(int j = sy + 1; j < ey; ++j){
        auto p1 = f(sx, sy, ex, j);
        auto p2 = f(sx, j, ex, ey);
        if(p1.second < 0 || p2.second < 0)
            continue;
        chmax(dp[sx][sy][ex][ey], make_pair(p1.first + p2.first, min(p1.second, p2.second)));
    }
    flag[sx][sy][ex][ey] = true;
    return dp[sx][sy][ex][ey];
}

bool solve(){
    int h, w, s;
    cin >> h >> w >> s;
    if(!h)
        return false;
    vector<vector<int>> v(h, vector<int>(w));
    int sum = 0;
    for(int i = 0; i < h; ++i)
        for(int j = 0; j < w; ++j){
            cin >> v[i][j];
            sum += v[i][j];
        }
    dp.assign(h, vector<vector<vector<pair<int,int>>>>(w, vector<vector<pair<int,int>>>(h + 1, vector<pair<int,int>>(w + 1, make_pair(-MOD, -MOD)))));
    flag.assign(h, vector<vector<vector<bool>>>(w, vector<vector<bool>>(h + 1, vector<bool>(w + 1, false))));

    vector<vector<int>> cumsum(h + 1, vector<int>(w + 1, 0));
    for(int i = 0; i < h; ++i)
        for(int j = 0; j < w; ++j)
            cumsum[i + 1][j + 1] = v[i][j];
    for(int i = 0; i < h; ++i)
        for(int j = 0; j <= w; ++j)
            cumsum[i + 1][j] += cumsum[i][j];
    for(int i = 0; i <= h; ++i)
        for(int j = 0; j < w; ++j)
            cumsum[i][j + 1] += cumsum[i][j];

    for(int i = 0; i < h; ++i)
        for(int j = 0; j < w; ++j)
            for(int k = i + 1; k <= h; ++k)
                for(int l = j + 1; l <= w; ++l){
                    int psum = cumsum[i][j] + cumsum[k][l] - cumsum[i][l] - cumsum[k][j];
                    if(sum - psum <= s)
                        dp[i][j][k][l] = make_pair(1, s - (sum - psum));
                }
    auto res = f(0, 0, h, w);
    cout << res.first << " " << res.second << endl;
    return true;
}

signed main(){
    while(solve());
}



Measured memory_bytes: 22056
// AOJ 1585 String in String
// 2018.5.20 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n)
{
	int i;
	char ob[20];

	if (!n) pc('0');
	else {
		i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
		while (i--) pc(ob[i]);
	}
	pc('\n');
}

int str(int *f, char *s)
{
	int x;
	char *p = s, c;

	*p++ = x = gc();
	while ((c = gc()) > ' ') {
		*p++ = c;
		if (c != x) x = -1;
	}
	*p = 0;
	*f = x;
	return p-s;
}

#define INF   0x10101010
#define MAX_L 100005

char text[MAX_L]; int len;
char pat[MAX_L]; int wp;
int  sa[MAX_L], rank[MAX_L<<1];

/* 接尾辞配列 */
// rank[i]～[i+k] と rank[j]～[j+k] を比較
int k; // comstruct_sa()内で設定
int compare_sa(int i, int j)
{
	if (rank[i] != rank[j]) return rank[i] < rank[j];
	return rank[i+k] < rank[j+k];
}

// for qsort()
int cmp(const void *a, const void *b)
{
	int i = *(const int *)a, j = *(const int *)b;
	
	if (rank[i] != rank[j]) return rank[i] - rank[j];
	return rank[i+k] - rank[j+k];
}

// 文字列Sの接尾辞配列saを構築。   len:　strlen(s)
int tmp[MAX_L];
void construct_sa(char *s, int *sa)
{
	int i;
	
	memset(rank, -1, sizeof(rank));
	for(i = 0; i <= len; i++) {
		sa[i] = i;
		if (i < len) rank[i] = s[i];
	}
	
	for(k = 1; k <= len; k *= 2) {
		qsort(sa, len+1, sizeof(int), cmp);
		
		tmp[sa[0]] = 0;
		for(i = 1; i <= len; i++) {
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1], sa[i]);
		}
		for(i = 0; i <= len; i++) rank[i] = tmp[i];
	}
}

// 接尾辞配列を用いた文字列検索　len = strlen(s), wt = strlen(t)
int lower_bound(int wt, char *t)
{
	int m, l = 0, r = len;

	while (l < r) {
		m = (l+r)>>1;
		if (memcmp(text+sa[m], t, wt) < 0) l = m+1; else r = m;
	}
	return l;
}

int upper_bound(int l, int wt, char *t)
{
	int m, r = len;

	while (l < r) {
		m = (l+r)>>1;
		if (memcmp(text+sa[m], t, wt) <= 0) l = m+1; else r = m;
	}
	l -= (memcmp(text+sa[l], t, wt) != 0);
	return l;
}

int main()
{
	int Q, l, r, ll, rr, ans;
	int xx, xp;

	len = str(&xx, text);
	if (xx < 0) construct_sa(text, sa);

	Q = in();
	while (Q--) {
		l = in(), r = in()+1, wp = str(&xp, pat);

		if (wp > r-l) goto done;
		if (wp == r-l) {
			pc('0' + (memcmp(pat, text+l, wp) == 0)), pc('\n');
			continue;
		}
	
		if (xx > 0) {
			if (xp < 0 || xp != xx || wp > len) goto done;
			out(r-l+1-wp);
			continue;
		}

		ll = lower_bound(wp, pat);
		rr = upper_bound(ll, wp, pat);
		if (ll > rr) goto done;

		if (l == 0 && r == len) out(rr-ll+1);
		else {
			ans = 0, r -= wp;
			while (ll <= rr) {
				if (sa[ll] >= l && sa[ll] <= r) ans++;
				ll++;
			}
			out(ans);
		}
		continue;
done:	pc('0'), pc('\n');
	}
	return 0;
}


Measured memory_bytes: 3780
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int h, w;
char a[1000][1000];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h>>w;
    for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin>>a[i][j];
            }
        }
    for(int i=0;i<=w+1;i++){
        cout<<'#';
    }
    cout<<"\n";
    for (int i = 0; i < h; i++)
    {
        cout<<'#';
        for(int j=0;j<w;j++){
            char c;
            cout<<a[i][j];
        }
        cout<<'#';
        cout<<"\n";
    }
    for(int i=0;i<=w+1;i++){
        cout<<'#';
    }
    cout<<"\n";
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);

    int H = sc.nextInt();
    int W = sc.nextInt();

    int h = sc.nextInt();
    int w = sc.nextInt();

    int X = H - h;
    int Y = W - w;
    int Z = X * Y;

    System.out.println(Z);

  }
}

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

using namespace std;
using ll = long long int;
using P = pair<int, int>;

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

int main(void){

    int n, k, s;
    cin >> n >> k >> s;

    roop(i, k){
        cout << s << " ";
    }

    roop(i, n-k){
        if(s == 1000000000){
            if(i == n-k) cout << 1 << endl;
            else cout << 1 << " ";
        }else{
            if(i == n-k) cout << s+1 << endl;
            else cout << s+1 << " ";
        }
    }

    return 0;
}

Measured memory_bytes: 1280
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    cin >> a >> b;
    if(a > 0 && b > 0){
        cout << "Positive" << endl;
    }else if(a < 0 && b < 0){
        if((abs(b-a)+1) % 2 == 0){
            cout << "Positive" << endl;
        }else{
        cout << "Negative" << endl;
        }
        }else {
        cout << "Zero" << endl;
    }
}


Measured memory_bytes: 256
import itertools

N=int(input())
P=list(map(int, input().split()))
Q=list(map(int, input().split()))

L=list(itertools.permutations([i for i in range(1,N+1)]))

tempP=0
tempQ=0

for i in range(len(L)):

	if list(L[i])==P:
		tempP=i
	if list(L[i])==Q:
		tempQ=i

print(abs(tempP-tempQ))

Measured memory_bytes: 13848
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s, t;
  cin >> s >> t;
  int a, b;
  cin >> a >> b;
  string u;
  cin >> u;
  if(s == u) a--;
  else b--;
  cout << a << " " << b << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

int n;
string s, t;
 
int main(int argc, char **argv) {
	cin >> s;
	n = s.length();
	vector<pair<int, char>> s2;
	vector<int> xs;
	int cnt = 0;
	REP(i, n) {
		if (s[i] != 'x') {
			s2.push_back(MP(i, s[i]));
			xs.push_back(cnt);
			cnt = 0;
		}
		else {
			++cnt;
		}
	}
	xs.push_back(cnt);
	bool f = true;
	REP(i, s2.size()) f &= s2[i].S == s2[s2.size() - 1 - i].S;
	if (!f) {
		cout << -1 << endl;
		return 0;
	}
	int res = 0;
	REP(i, xs.size()) res += abs(xs[i] - xs[xs.size() - 1 - i]);
	cout << (res / 2) << endl;
	return 0;
}
 

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

int main() {
    int A, B, K; cin >> A >> B >> K;
    if (B - A + 1 < K * 2) {
        int N = B - A + 1;
        rep(i, N) cout << A + i << endl;
    }
    else {
        rep(i, K) cout << (A + i) << endl;
        rep(i, K) cout << (B - K + i + 1) << endl;
    }
    return 0;
}

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

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

    int n;
    cin >> n;
    vector<ll> a(n + 1);
    ll dp[n + 1][5] = {};

    rep(i, 1, n + 1) {
        cin >> a[i];
        dp[0][0] += a[i];
    }
    rep(i, 0, n + 1) rep(j, 0, 5) dp[i][j] = dp[0][0];

    rep(i, 1, n + 1) {
        dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]);
        dp[i][2] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
        dp[i][3] = min(dp[i - 1][2], dp[i - 1][3]);
        dp[i][4] =
            min({dp[i - 1][1], dp[i - 1][2], dp[i - 1][3], dp[i - 1][4]});
        if (a[i] == 0) {
            dp[i][1] += 2;
            dp[i][3] += 2;
            dp[i][2]++;
        } else if (a[i] % 2 == 0) {
            dp[i][1] -= a[i];
            dp[i][3] -= a[i];
            dp[i][2] -= a[i] - 1;
        } else if (a[i] % 2 == 1) {
            dp[i][1] -= a[i] - 1;
            dp[i][3] -= a[i] - 1;
            dp[i][2] -= a[i];
        }
    }
    cout << min({dp[n][1], dp[n][2], dp[n][3], dp[n][4]}) << endl;

    return 0;
}

Measured memory_bytes: 9600
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dish = new int[n];
        int[] sat = new int[n];
        int[] plus = new int[n - 1];
        for (int i = 0; i < n; i++) {
            dish[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            sat[i] = sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            plus[i] = sc.nextInt();
        }
        int sum = 0;
        int before = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int current = dish[i];
            sum += sat[current - 1];
            if (before + 1 == current) {
                sum += plus[before - 1];
            }
            before = current;
        }
        System.out.println(sum);
    }
}


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

typedef pair<int, int> P;

const int INF = 1<<10;

int H, W, N;
char field[1010][1010];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
int vt[1010][1010];
int sx, sy;
int cnt = 0;

int bfs() {
  for (int i = 1; i <= N; i++) {
    queue<P> q;
    for (int y = 0; y < H; y++)
      for (int x = 0; x < W; x++) vt[y][x] = INF;
    q.push(P(sx, sy));
    vt[sy][sx] = 0;
    bool flag = false;

    while (!q.empty() && !flag) {
      int x = q.front().first;
      int y = q.front().second;
      int c = vt[y][x];
      q.pop();
      for (int j = 0; j < 4; j++) {
        int nx = x + dx[j], ny = y + dy[j];
        if (nx < 0 || nx >= W || ny < 0 || ny >= H || vt[ny][nx] != INF ||
            field[ny][nx] == 'X') continue;
        if (field[ny][nx] == '0' + i) {
          sx = nx; sy = ny;
          cnt += c + 1;
          flag = true;
          break;
        }
        q.push(P(nx, ny));
        vt[ny][nx] = c + 1;
      }
    }
  }
}

int main() {
  cin >> H >> W >> N;
  for (int y = 0; y < H; y++) {
    cin >> field[y];
    for (int x = 0; x < W; x++) {
      if (field[y][x] == 'S') {
        sx = x; sy = y;
      }
    }
  }

  bfs();
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 8016
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

struct P{
    long long a1, a2, a3, a4;
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long X;
    int K, Q;
    cin >> X >> K;
    vector<long long> r(K+1);
    r[0] = 0;
    for(int i=1; i<=K; i++) cin >> r[i];

    cin >> Q;
    vector<long long> t(Q);
    vector<long long> a(Q);
    for(int i=0; i<Q; i++) cin >> t[i] >> a[i];

    vector<P> A(K+1);
    A[0] = {0, X, 0, X};
    for(int i=1; i<=K; i++){
        int dt = r[i] - r[i-1];
        if(i % 2 == 1){
            long long a1 = max(A[i-1].a1 - A[i-1].a3 + dt, A[i-1].a1);
            long long a2 = max(A[i-1].a1 - A[i-1].a3 + dt, A[i-1].a2);
            long long a3 = max(A[i-1].a3 - dt, 0LL);
            long long a4 = max(A[i-1].a4 - dt, 0LL);
            A[i] = {a1, a2, a3, a4};
        }else{
            long long a1 = min(X - A[i-1].a4 + A[i-1].a2 - dt, A[i-1].a1);
            long long a2 = min(X - A[i-1].a4 + A[i-1].a2 - dt, A[i-1].a2);
            long long a3 = min(A[i-1].a3 + dt, X);
            long long a4 = min(A[i-1].a4 + dt, X);
            A[i] = {a1, a2, a3, a4};
        }
    }

    for(int i=0; i<Q; i++){
        int id = upper_bound(r.begin(), r.end(), t[i]) - r.begin() - 1;
        P p = A[id];
        long long dt = t[i] - r[id];
        if(id % 2 == 0) dt = -dt;
        if(a[i] <= p.a1) cout << min(X, max(0LL, p.a3 + dt)) << endl;
        else if(a[i] >= p.a2) cout << min(X, max(0LL, p.a4 + dt)) << endl;
        else cout << min(X, max(0LL, p.a3 + a[i] - p.a1 + dt)) << endl;
    }
    return 0;
}

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

int main () {
	char a [11];
	char b[11];
	char c[11];
	scanf ("%s %s %s",&a,&b,&c);
		int len1 = strlen(a);
	int len2 = strlen(b);
	
	if (a[len1-1] == b[0] && b[len2-1] == c[0]) {
		printf("YES");
	}
	else printf ("NO");

	return 0;
}

Measured memory_bytes: 1732
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a[:]
ans=10**20
for i in range(n):
    for j in range(n):
        b[j]=min(b[j],a[j-i])
    ans=min(ans,sum(b)+x*i)
print(ans)

Measured memory_bytes: 43884
N,K = map(int,input().split())
d = []
A = []
for i in range(K):
    d.append(int(input()))
    A.append(list(map(int,input().split())))

S = [1 for _ in range(N)]
for i in range(K):
    for j in range(len(A[i])):
        S[A[i][j]-1] = 0

print(sum(S))


Measured memory_bytes: 9212
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

long long getDigit(long long a){
	int res = 0;
	while(a > 0){
		res += a % 10;
		a/=10;
	}
	return res;
}

int main(){
	vector<pair<double, long long>> v;
	range(i,1,10000){
		v.emplace_back(i * 1.0 / getDigit(i), i);
	}

	long long base = 10000, ni = 99;
	rep(k,15){
		range(i,1,10){
			rep(j,10){
				rep(k,10){
					long long temp =
						i * base +
						j * base / 10 +
						k * base / 100 + ni;
					v.emplace_back(static_cast<double>(temp) / getDigit(temp), temp);
				}
			}
		}
		base *= 10;
		ni = ni * 10 + 9;
	}
	//cout << i << ' ' << static_cast<double>(i) / getDigit(i) << endl;
	sort(all(v));
	long long maxi = -1;

	vector<long long> ans;
	for(auto i : v){
		if(maxi < i.second){
			maxi = i.second;
		}else{
			continue;
		}
		ans.emplace_back(i.second);
		//cout << i.second << endl;
		//cout << i.first << ' ' << i.second << endl;
	}

	int n;
	cin >> n;
	rep(i,n){
		cout << ans[i] << endl;
	}
}


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

int main(){
  int n;
  double a = 0.5;
  
  cin >> n;
  
  if(n % 2 != 0){
    a = (double(n / 2 + 1) / double(n));
  }
  
  cout << a << "\n";
  
  return 0;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,K,a[202020];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int mi=0x3f3f3f3f,ans=0;
	for(int i=1;i<=n;i++)
		if(a[i]<mi) mi=a[i],ans++;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>

using namespace std;

int main(void){
    int N;
    cin>>N;
    VI d(N);
    rep(i,N)cin>>d[i];
    VI G(N-1),R(N-1);
    G[0]=d[0],R[N-2]=d[N-1];
    for(int i=0;i<N-2;i++){
        G[i+1]=max(d[i+1],G[i]-10);
    }
    for(int i=N-2;i>=1;i--){
        R[i-1]=max(d[i],R[i]-10);
    }
    sort(G.begin(),G.end());
    sort(R.begin(),R.end());
    if(G[0]>=10&&R[0]>=10){
        cout<<"yes"<<endl;
    }else{
        cout<<"no"<<endl;
    }
    return 0;

}




Measured memory_bytes: 6276
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

// DAME:
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    int pre = 0;
    reverse(s.begin(), s.end());
    rep(i, n){
        int tmp = s[i] - '0' + pre;
        if (tmp>5){
            ans += 10-tmp;
            pre = 1;
        }else if (tmp==5){
            if (s[i+1]-'0' >= 5){
                ans += 10-tmp;
                pre = 1;
            }else{
                ans += tmp;
                pre = 0;
            }
        }else{
            ans += tmp;
            pre = 0;
        }
    }
    if (pre==1) ans++;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1948
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if(a<b){
        for(int i = 0; i < b; i++){
            cout << a;
        }
        cout << endl;

    }else{
        for(int i = 0; i < a; i++){
            cout << b;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3616
import Data.List
import Data.Bits
main = mapM_ (print . solve) . lines =<< getContents
solve::String->Int
solve s = sum . zipWith f [0..] . tails $ s where
  n = length s
  f i = sum . zipWith g [1..] . tail . inits where
    g k t = read t * h i * h (n-i-k)
h = shiftL 1 . max 0 . subtract 1

Measured memory_bytes: 764
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
using ll = long long;

int main(){
  int N,M;
  cin >> N >> M;
  vector<set<int>> load(N);
  int A,B;
  for(ll i=0;i<M;i++){
    cin >> A >> B;
    --A; --B;
    load.at(A).insert(B);
    load.at(B).insert(A);
  }

  vector<int> flag(N,-1);
  flag.at(0)=0;
  vector<int> dist(N,-1);
  dist.at(0)=0;

  queue<int> q;
  q.push(0);

  while(!q.empty()){
    int now=q.front();
    q.pop();

    for(int next: load.at(now)){
      if(dist.at(next)==-1){
	q.push(next);
	dist.at(next)=dist.at(now)+1;
	flag.at(next)=now+1;
      }
    }
  }
  
  for(int i=1;i<N;i++){
    if(flag.at(i)==-1){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  for(int i=1;i<N;i++) cout << flag.at(i) << endl;
  
  return 0;
}


Measured memory_bytes: 27796
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout(val) cout << std::fixed << std::setprecision(20) << val;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };

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

  int n; cin >> n;
  string s; cin >> s;

  vector<set<int> > table = vector<set<int> >(10);
  rep(i, n) {
    table[s[i] - '0'].insert(i);
  }

  int ans = 0;
  rep(i, 10) {
    if(table[i].size() == 0) continue;
    int firstInd = *(table[i].begin());

    rep(j, 10) {
      std::set<int>::iterator secondIt = table[j].upper_bound(firstInd);
      if(secondIt == table[j].end()) continue;
      int secondInd = *secondIt;

      rep(k, 10) {
        std::set<int>::iterator thirdIt = table[k].upper_bound(secondInd);
        if(thirdIt == table[k].end()) continue;
        ++ans;
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 1664
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] array = new int[3][3];
		int sum = 0;
		for(int i = 0;i<3;i++) {
			for(int j = 0;j<3;j++) {
				array[i][j] = sc.nextInt();
			}
		}
		int n = sc.nextInt();
		int[] array2 = new int [n];
		for (int i=0;i<n;i++) 
			array2[i] = sc.nextInt();
		
		for (int i = 0;i<3;i++) {
			for(int j = 0;j<3;j++) {
				for(int k =0;k<n;k++) {
					if(array[i][j] == array2[k]) {
						array[i][j] = 0;
					}
				}
			}
		}
		for(int i = 0;i<3;i++) {
			if(array[i][0]==array[i][1]&&array[i][1]==array[i][2]&&array[i][2]==0) {
				sum++;
			}
		}
		for(int i = 0;i<3;i++) {
			if(array[0][i]==array[1][i]&&array[1][i]==array[2][i]&&array[2][i]==0) {
				sum++;
			}
	}
		if(array[0][0]==array[1][1]&&array[1][1]==array[2][2]&&array[2][2]==0) {
			sum++;
		}
		if(array[0][2]==array[1][1]&&array[1][1]==array[2][0]&&array[2][0]==0) {
			sum++;
		}
		if(sum>=1)
			System.out.println("Yes");
		
		else
			System.out.println("No");
}
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> act(3,vector<int>(N));
    
    rep(i,N)cin>>act[0][i]>>act[1][i]>>act[2][i];
    vector<pair<int,int>> indices;
    indices.pb(mp(1,2));
    indices.pb(mp(0,2));
    indices.pb(mp(0,1));

    vector<vector<int>> dp(1e5+5,vector<int>(3,-1));
    rep(a,3)dp[0][a]=act[a][0];
    
    rep(i,N){
        rep(a,3){
            int act1=indices[a].first,act2=indices[a].second;
            dp[i+1][a]=max(dp[i][act1]+act[a][i+1],dp[i][act2]+act[a][i+1]);
        }
    }
    cout<<max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2])<<endl;
 //   system("pause");
    return 0;
}

Measured memory_bytes: 6908
#include<iostream>
#include<vector>
#include<string>
#include<map>
#define REP(i, j) for(int (i)=0; (i)<(j); ++(i))
using namespace std;
typedef pair<int, int> P;

vector<int> v[2], parent[2], depth[2];

int find(int a, int f){
  if(parent[f][a] == a) return a;
  else return parent[f][a] = find(parent[f][a], f);
}

void merge(int a, int b, int f){
  int pa = find(a, f), pb = find(b, f);
  if(pa == pb) return ;

  if(depth[f][pa] > depth[f][pb]) swap(pa, pb);
  if(depth[f][pa] == depth[f][pb]) ++depth[f][pa];
  parent[f][pb] = pa;
}

void init_union_find(int V, int f){
  v[f] = vector<int>(V);
  parent[f] = vector<int>(V);
  depth[f] = vector<int>(V, 1);
  REP(i, V) parent[f][i] = i;
}

int main(){
  int N, K, L; cin >>N >>K >>L;
  init_union_find(N, 0);
  init_union_find(N, 1);
  REP(i, K){
    int f, t; cin >>f >>t;
    merge(f - 1, t - 1, 0);
  }
  REP(i, L){
    int f, t; cin >>f >>t;
    merge(f - 1, t - 1, 1);
  }

  map<P, int> M;
  REP(i, N) M[P(find(i, 0), find(i, 1))]++;

  REP(i, N) cout <<M[P(find(i, 0), find(i, 1))] <<(i == N - 1 ? "" : " ");
  cout <<endl;
  return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<58;
const double eps = 1e-13;

LL v[100009];
LL cv[100009];
LL rv[100009];
vector<pair<int,LL> > rd[100009],cd[100009];
vector<pair<int,LL> > adj[100009];
LL cmin;
pair<PII,LL> d[100009];

void dfs(int x){
	cmin=min(cmin,v[x]);
	for(PII i:adj[x]){
		if((v[i.F]!=-INF)&&(v[i.F]!=v[x]+i.S)){
			printf("No");exit(0);
		}
		if(v[i.F]!=-INF)continue;
		v[i.F]=v[x]+i.S;
		dfs(i.F);
	}
}

void dfsr(int x){
	for(PII i:adj[x]){
		if(rv[i.F]!=-INF)continue;
		rv[i.F]=cmin-v[i.F];
		dfsr(i.F);
	}
}

void dfsc(int x){
	for(PII i:adj[x]){
		if(cv[i.F]!=-INF)continue;
		cv[i.F]=cmin-v[i.F];
		dfsc(i.F);
	}
}

int main(){
	//RF("1_21.txt");
	DRII(n,m);
	DRI(k);
	REP(i,k){
		DRIII(y,x,c);y--;x--;
		d[i]=MP(MP(y,x),c);
		rd[y].PB(MP(x,c));
		cd[x].PB(MP(y,c));
	}
	REP(i,m){
		cv[i]=v[i]=-INF;
	}
	REP(i,n){
		sort(ALL(rd[i]));
		REPP(j,1,SZ(rd[i])){
			adj[rd[i][j-1].F].PB(MP(rd[i][j].F,rd[i][j].S-rd[i][j-1].S));
			adj[rd[i][j].F].PB(MP(rd[i][j-1].F,rd[i][j-1].S-rd[i][j].S));
		}
	}
	REP(i,m){
		if(v[i]==-INF){
			cmin=INF;
			v[i]=INF;
			dfs(i);
			cv[i]=cmin-v[i];
			dfsc(i);
		}
	}
	REP(i,max(n,m)){
		rv[i]=v[i]=-INF;
		adj[i].clear();
	}
	REP(i,m){
		sort(ALL(cd[i]));
		REPP(j,1,SZ(cd[i])){
			adj[cd[i][j-1].F].PB(MP(cd[i][j].F,cd[i][j].S-cd[i][j-1].S));
			adj[cd[i][j].F].PB(MP(cd[i][j-1].F,cd[i][j-1].S-cd[i][j].S));
		}
	}
	REP(i,n){
		if(v[i]==-INF){
			cmin=INF;
			v[i]=INF;
			dfs(i);
			rv[i]=cmin-v[i];
			dfsr(i);
		}
	}
	//REP(i,n)printf("%lld ",rv[i]);puts("");
	//REP(i,n)printf("%lld ",cv[i]);puts("");
	REP(i,k){
		if(d[i].S+cv[d[i].F.S]+rv[d[i].F.F]<0){
			printf("No");return 0;
		}
	}
	printf("Yes");
}


Measured memory_bytes: 22400
#include <iostream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

#define mp make_pair

const int maxn = 100005;

int px[maxn],py[maxn],f[maxn];

pair<int,int> sx[maxn],sy[maxn];

int fnd(int x){
	if (f[x]==x)return x;
	return f[x]=fnd(f[x]);
}

int n;

int dist(int u,int v){
	return min(abs(px[u]-px[v]),abs(py[u]-py[v]));
}

int unit(int x,int y){
	x=fnd(x);
	y=fnd(y);
	if (x==y)return 0;
	f[x]=y;
	return 1;
}

int main(){
	scanf("%d",&n);
	for (int i=0;i<n;++i){
		scanf("%d%d",&px[i],&py[i]);
		f[i]=i;
		sx[i]=mp(px[i],i);
		sy[i]=mp(py[i],i);
	}
	sort(sx,sx+n);
	sort(sy,sy+n);
	set < pair < int , pair < int , int > > >st;
	for (int i=0;i<n-1;++i){
		st.insert(mp(dist(sx[i].second,sx[i+1].second),mp(sx[i].second,sx[i+1].second)));
		st.insert(mp(dist(sy[i].second,sy[i+1].second),mp(sy[i].second,sy[i+1].second)));
	}
	long long res=0;
	while ((int)st.size()){
		auto cur= *(st.begin());
		st.erase(cur);
		int u=cur.second.first,v=cur.second.second;
		res += unit(u,v) * dist(u,v);
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 12920
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    import itertools
    n = int(input())
    # indexの中身 を 使うときは, list じゃなくて、 tuple じゃないとだめええ
    p = tuple(map(int,input().split()))
    q = tuple(map(int,input().split()))
    # 初期リスト
    num = [i + 1 for i in range(n)]
    per = list(itertools.permutations(num))
    # permutations 全て tuple だから 合わせろ!
    print(abs(per.index(q) - per.index(p)))



if __name__ == '__main__':
  main()


Measured memory_bytes: 8052