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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

vector<int> tree(4 * N, INF), lazy(4 * N, INF);

int join(int a, int b) {
    return min(a, b);
}

void propagate(int node, int l, int r) {
	if (lazy[node] != INF) {
		tree[node] = min(tree[node], lazy[node]);
		
		if (l != r) {
			lazy[node << 1] = min(lazy[node << 1], lazy[node]);
			lazy[(node << 1) + 1] = min(lazy[(node<<1) + 1], lazy[node]);
		}
		
		lazy[node] = INF;
	}
}

void update(int node, int l, int r, int x, int y, int newVal) {
	if (l > r) {
		return ;
	}

	propagate(node, l, r);

	if (l > y or r < x) {
		return;
	}

	if (l >= x and r <= y) {
		tree[node] = min(tree[node], newVal);
		
		if (l != r) {
			lazy[node << 1] = min(lazy[node << 1], newVal);
			lazy[(node << 1) + 1] = min(lazy[(node << 1) + 1], newVal);
		}

		return ;
	}

	int m = (l + r) >> 1;
	update(node << 1, l, m, x, y, newVal);
	update((node << 1) + 1, m + 1, r, x, y, newVal);
    tree[node] = join(tree[node << 1], tree[(node << 1) + 1]);
}

int query(int node, int l, int r, int x, int y) {
    if (l > r) {
        return INF;
    }

    propagate(node, l, r);

    if (l > y or r < x) {
    	return INF;
    }

    if (l >= x and r <= y) {
        return tree[node];
    }

    int m = (l + r) >> 1;
    int q1 = query(node << 1, l, m, x, y);
    int q2 = query((node << 1) + 1, m + 1, r, x, y);
    return join(q1, q2);
}

struct data {
	int s, t, x;
	bool operator< (const data& other) const {
		return x < other.x;
	}
} a[N];

int d[N];

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

	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		cin >> a[i].s >> a[i].t >> a[i].x;
	}

	sort(a, a + n);

	for (int i = 0; i < q; i++) {
		cin >> d[i];
	}

	for (int i = 0; i < q; i++) {
		int st = lower_bound(d, d + q, a[i].s - a[i].x) - d;
		int en = upper_bound(d, d + q, a[i].t - a[i].x - 1) - d - 1;
		if (st <= en) {
			update(1, 1, q, st + 1, en + 1, a[i].x);
		}
	}

	for (int i = 0; i < q; i++) {
		int ans = query(1, 1, q, i + 1, i + 1);
		cout << (ans == INF ? -1 : ans) << "\n";
	}
    return 0;
}

Measured memory_bytes: 20608
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

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

    cin >> a >> b >> c;

    if (a <= c && a+b >= c) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int d;
  int t;
  int s;
  
  cin >> d;
  cin >> t;
  cin >> s;
  
  if (d <= t * s){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 3552
#include <stdio.h>
int main(){
  long long N, sum = 0;
  scanf("%lli", &N);
  for (int i = 1; i <= N; i++) {
    if (i%3 != 0 && i%5 != 0) {
      sum += i;
    }
  }
  printf("%lli", sum);
  return 0;
}

Measured memory_bytes: 1712
/*
 * Author: .-O_O-.
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define en end()
#define f first
#define s second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define nx cout<<"\n"
#define int long long
// void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
                                                     
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]"<<endl;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
const ll mod = 1000000007;
const ll N = 200005;
const ll mm = 1e+18;
void solve()
{
    map<int,int>mp;
    rep1(i,100)rep1(j,100)rep1(k,100){
        int f=i*i+j*j+k*k+i*j+i*k+j*k;
        mp[f]++;
    }
    int n;
    cin>>n;
    rep1(i,n) cout<<mp[i]<<"\n";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        //nx;
    }
    return 0;
}

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

using namespace std;

using ll = long long;

const int MAX_N = 301;
int n;
double dp[MAX_N][MAX_N][MAX_N];

double Solve(array<int, 3> &cnt) {
    if (cnt[0] + cnt[1] + cnt[2] == 0) return 0.0;
    if (dp[cnt[0]][cnt[1]][cnt[2]] != 0)
        return dp[cnt[0]][cnt[1]][cnt[2]];

    double &res = dp[cnt[0]][cnt[1]][cnt[2]];
    res = 0.0;
    for (int i = 0; i <= 2; ++i)
        if (cnt[i] != 0) {
            --cnt[i];
            if (i != 0) ++cnt[i - 1];
            res += Solve(cnt) * (cnt[i] + 1);
            ++cnt[i];
            if (i != 0) --cnt[i - 1];
        }
    res = res / (double)n + 1.0;
    int n0 = n - (cnt[0] + cnt[1] + cnt[2]);
    if (n0 != 0) res *= n / (double)(n - n0);

    return  res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(10) << setiosflags(ios::fixed);

    cin >> n;

    array<int, 3> cnt = {0, 0, 0};
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        ++cnt[a - 1];
    }

    cout << Solve(cnt) << endl;

    return 0;
}


Measured memory_bytes: 213248
#include <iostream>
#include <string>
#include <vector>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  S[3] = '8';
  cout << S << endl;

  return 0;
}


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

int main()
{
    int n, sol = 0;
    long long d, x, y;
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        cin >> x >> y;
        if(x * x + y * y <= d * d) {
            sol++;
        }
    }
    cout << sol;
    return 0;
}

Measured memory_bytes: 3632
N = int(input())

Works = [dict(zip(["require", "limit"], [int(_) for _ in input().split()])) for i in range(N)]

def solve(Works):
    Works.sort(key=lambda x: x["limit"])
    acc = 0
    for w in Works:
        acc += w["require"]
        if acc > w["limit"]:
            return "No"
    return "Yes"

print(solve(Works))

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

int main() {
  int N;
  cin >> N;
  string answer = "No";
  for (int i=1; i<10; i++) {
    for (int j=1; j<10; j++) {
      if (N==i*j) {
        answer = "Yes";
        break;
      }
    }
    if (answer == "Yes") {
      break;
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))
    b = sorted(a)
    for i in range(len(a)):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])


if __name__ == "__main__":
    main()

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

using namespace std;
const double PI = 3.14159265358979323846264338327950288;

class Solution {
public:
	void solve() {
		double r;
		cin >> r;
		cout << setprecision(12) << 2.0 * PI * r << "\n";

		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 3780
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int N;cin>>N;
    int a[N],b[N];
    for(int i=0;i<N;i++){
        cin >> a[i];
      	b[i] = a[i];
    }
    sort(a,a+N);
    double m=(a[(N/2)-1]+a[N/2])/2;
    for(int i=0;i<N;i++){
        if(b[i]>m) cout << a[(N/2)-1] << endl;
        if(b[i]<=m) cout << a[(N/2)] << endl; 
    }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, l, r) for (int i = l; i <= (int)(r); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

ll dp[2005][2005];

int main(){
    int n;
    cin >> n;
    P p[n];
    rep(i, n){
        int a;
        cin >> a;
        p[i] = P(a, i);
    }

    sort(p, p+n, greater<>());

    dp[0][0] = 0;

    rep(xi, n){
        rep(i, xi+1){
            dp[xi-i+1][i] = max(dp[xi-i+1][i], dp[xi-i][i] + (ll) p[xi].first * abs(p[xi].second - (xi-i)));
            dp[xi-i][i+1] = max(dp[xi-i][i+1], dp[xi-i][i] + (ll) p[xi].first * abs(p[xi].second - (n-i-1)));
        }
    }
    
    ll ans = 0;
    rep(i, n+1) chmax(ans, dp[n-i][i]);

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

Measured memory_bytes: 26244
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S,T;
  cin >> S >> T;
  char R1[26];
  char R2[26];
  for(int i=0; i<26;i++){
    R1[i] = -1;
    R2[i] = -1;
  }
  for(int i=0; i<S.size(); i++){
    if(R1[S[i]-'a'] < 0){
      R1[S[i]-'a'] = T[i];
    }else{
      if(R1[S[i]-'a'] != T[i]){
        cout << "No" << endl;
        return 0;
      }
    }
    if(R2[T[i]-'a'] < 0){
      R2[T[i]-'a'] = S[i];
    }else{
      if(R2[T[i]-'a'] != S[i]){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
const int INF = 1<<29;
using namespace std;
using ll = long long;
ll l , a[500001];
int main(){
    ll ans = 0;
    int n;
    cin >> n;
    int a[n + 1] , b , c = 0;
    for(int i = 0; i < n + 1; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b;
        ans += min(c , a[i]);
        a[i] = max(a[i] - c , 0);
        ans += min(b , a[i]);
        c = max(b - a[i] , 0);
    }
    ans += min(a[n] , c);
    cout << ans << endl;
}


Measured memory_bytes: 3988
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
using namespace std;
using ll=long long;

int main(){
    int a,b;
    cin>>a>>b;
    if((a+b)%2==0){
        cout<<(a+b)/2<<endl;
    }
    else{
        cout<<"IMPOSSIBLE"<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
n = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(n-2):
  if (P[i] < P[i+1]) and (P[i+1] < P[i+2]):
    ans += 1
  elif (P[i] > P[i+1]) and (P[i+1] > P[i+2]):
    ans += 1
print(ans)

Measured memory_bytes: 3316
n = int(input())
a = input().split()
a = [int(m) for m in a]

a.sort()
sym = 0
symc = 0
delc = 0
for i in range(n):
    if i == 0 and n == 1:
        if a[i] == 1:
            delc = 0
        else:
            delc = 1
    elif i == 0:
        sym = a[i]
        symc += 1
    elif a[i] != a[i - 1]:
        if symc < a[i - 1]:
            delc += symc
        elif symc > a[i - 1]:
            delc += symc - a[i - 1]
        sym = a[i]
        symc = 1
        if i == n - 1:
            if symc < a[i]:
                delc += symc
            elif symc > a[i]:
                delc += symc - a[i]
    elif i == n - 1:
        symc += 1
        if symc < a[i]:
            delc += symc
        elif symc > a[i]:
            delc += symc - a[i]
    else:
        symc += 1

print(delc)

Measured memory_bytes: 14148
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = (int(x)-1 for x in input().split())
  graph[a].append(b)
  graph[b].append(a)

from collections import deque
def bfs(s:int)->list:
  dist = [-1]*n
  dist[s] = 0
  que = deque([s])
  while que:
    u = que.popleft()
    for v in graph[u]:
      if dist[v] != -1: continue
      dist[v] = dist[u] + 1
      que.append(v)
  return dist

dfen = bfs(0)
dsnu = bfs(n-1)
pfen = 0
psnu = 0
for i in range(n):
  if dfen[i] <= dsnu[i]: pfen += 1
  else: psnu += 1
ans = 'Fennec' if pfen > psnu else 'Snuke'
print(ans)

Measured memory_bytes: 33692
#include <bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define ppb pop_back
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	int n,k[100005],dp[100005],a;
	cin>>n>>a;
	
	for (int i=0;i<n;i++) 
	{
		cin>>k[i];
		dp[i]=1e9;
	}
	dp[0]=0;
	dp[1]=abs(k[0]-k[1]);
	for (int i=2;i<n;i++)
	{
		for (int j=1;j<=a && i-j>=0;j++)
		{
			dp[i]=min(dp[i],dp[i-j]+abs(k[i]-k[i-j]));
		}
		
	}
	cout<<dp[n-1];
	return 0;
}

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

int main() {
    int n=0;
    int count=0;
    string s;
    cin >> n >> s;
    for(int i = 0; i < n-2; i++){
        if(s.at(i)=='A'){
            if(s.at(i+1)=='B'){
                if(s.at(i+2)=='C'){
               // cout << count;
                count += 1;
               // cout << count;
               // cout << i << endl;
                }
            }
        }
    }
    cout << count;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
void func(vector<int>& c){
  sort(c.begin(), c.end());
  vector<vector<int> > t(m, vector<int>(n + 1));
  for(int i = 0; i < m; i++){
    t[i][0] = 0;
  }
  for(int j = 0; j <= n; j++){
    t[0][j] = j;
  }
  for(int i = 1; i < m; i++){
    for(int j = 0; j <= n; j++){
      if(j - c[i] < 0) t[i][j] = t[i - 1][j];
      else t[i][j] = min(t[i - 1][j], t[i][j - c[i]] + 1);
    }
  }
  cout << t[m - 1][n] << endl;
  return;
}

void solve(){
  cin >> n >> m;
  vector<int> c(m);
  for(int i = 0; i < m; i++){
    cin >> c[i];
  }
  func(c);
}

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



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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

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

    int N;
    cin >> N;

    int tot = 0;

    vi w(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i];
        tot += w[i];
    }

    int pref = 0, ans = INT_MAX;
    for (int i = 0; i < N - 1; i++) {
        pref += w[i];
        ans = min(ans, abs(pref - (tot - pref)));
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#![allow(non_snake_case)]
use proconio::input;
// use std::collections::HashMap;

fn main() {
    input! {
        N: usize,
        W: i64,
        wvs: [(i64, i64); N],
    }

    const MAX_N: usize = 100;
    const MAX_V: i64 = 100 * 1000;

    // dp[n][v] : n番以下の品物を選んで、価値vを実現するときの最大のw?
    // 間違い。
    // dp[n][v] : n番以下の品物を選んで、価値v以上を実現するときの最小のw
    let mut dp: Vec<Vec<i64>> = Vec::new();
    for _n in 0..MAX_N {
        let vec = vec![0; MAX_V as usize + 1];
        dp.push(vec);
    }

    let w0 = wvs[0].0;
    let v0 = wvs[0].1;

    // dp[0][0]はw0じゃないので注意
    dp[0][0] = 0;

    for v in 1..(v0 + 1) {
        dp[0][v as usize] = w0;
    }

    for v in (v0 + 1)..(MAX_V + 1) {
        dp[0][v as usize] = W + 1;
    }

    for n in 1..N {
        let this_w = wvs[n].0;
        let this_v = wvs[n].1;

        for v in 0..(MAX_V + 1) {
            let cand_stay = dp[n - 1][v as usize];
            let cand_take = if v >= this_v {
                dp[n - 1][(v - this_v) as usize] + this_w
            } else {
                W + 1
            };

            dp[n][v as usize] = std::cmp::min(cand_stay, cand_take);
        }
    }

    for v in (0..MAX_V + 1).rev() {
        let cand = dp[N - 1][v as usize];
        if cand <= W {
            println!("{}", v);
            return;
        }
    }



}


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

using namespace std;

int main()
{
    long n, k, res = 0;
    cin>>n>>k;
    for (int i = 1; i<=n; i++)
    {
        long x;
        cin>>x;
        res += 2* min(x, k - x);
    }
    cout<<res;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

bool check(string str) {
  int n = str.size();
  REP(i, n/2) {
    if (str[i] != str[n-i-1]) {
      return false;
    }
  }
  return true;
}

int main() {
  int a, b;
  string ast, bst;
  cin >> a >> b;
  int ans = 0;

  for (int i = a; i <= b; ++i) {
    if (check(to_string(i))) {
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define REP(i, n) for (LL i = 0; i < (LL)(n); i++)
#define FOR(i, m, n) for (LL i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
#define SUM(x) accumulate(x.begin(), x.end(),0)
#define vLL(v,n) vector<LL> v(n); REP(i,n)cin>>v[i];
#define vstr(v,n) vector<string> v(n); REP(i,n)REP(i,n)cin>>v[i];
LL INF = 1e9 + 1;
LL MOD = 1e9+7;
  LL a,b,c,d,e,n,m,l,r,x,y,z,ans=0,ans2=0,count;
string s,S,t;
int main() {
ios_base::sync_with_stdio(false);
LL h ,w,k;
  cin >> h>>w>>k;
  vector<vector<char>>c(h,vector<char>(w));
  REP(i,h)REP(j,w)cin>>c[i][j];
  REP(ma,1 << h){
      REP(mb,1 << w){
         int cnt =0;
         REP(i,h){
             REP(j,w){
                 if ((( ma >> i) & 1) == 0&&((mb >> j) & 1) == 0&&c[i][j]=='#'){
                     cnt++;
                  }
             }
         }
           if(cnt==k)ans++;
      }
  }
  cout << ans;
}

Measured memory_bytes: 3656
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <list>
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;

const double PI  = 3.141592653589793238463;
const int INF = 1000000007;

using ull = unsigned long long;
using ll = long long;

using Int = int;
using Double = double;

using P = pair<Int, Int>;
using V = vector<Int>;
using M = vector<V>;

int solve(string s){
    int i_A = 0;
    while(s[i_A] != 'A'){
        i_A++;
    }
    int i_Z = s.size() - 1;
    while(s[i_Z] != 'Z'){
        i_Z--;
    }
    return i_Z - i_A + 1;
}

int main(int argc, char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    cout << solve(s) << endl;

    return 0;
}


Measured memory_bytes: 788
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n;
    cin>>n;
    rep(i,n/4+1){
        rep(j,n/7+1){
            if(i*4+j*7==n){
                cout<<"Yes";
                return 0;
            }
        }
    }
    cout<<"No";
}

Measured memory_bytes: 3620
n = int(input())
record=[[[0 for r in range(10)] for f in range(3)] for b in range(4)]
for i in range(n):
    b,f,r,v = [int(x) for x in input().split()]
    record[b-1][f-1][r-1]+=v
for b in range(4):
    for f in record[b]: print(" "+" ".join([str(x) for x in f]))
    if b != 3:
        print("".join(["#" for x in range(20)]))

Measured memory_bytes: 7736
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second

int main(){
    string S;
    cin >> S;
    int max_l = 0;
    int N = S.length();
    for(int start = 0; start < N; start++){
        int count = 0;
        for(int now = start; now < N; now++){
            char a = S[now];
            if(a == 'A' or a == 'C' or a == 'G' or a == 'T') count++;
            else break;
        }
        max_l = max(max_l, count);
    }
    cout << max_l << endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using ll = long long;
#define rep(i ,n) for(ll i = 1 ; i <= (n) ; i ++ )
#define all(x) (x).begin(),(x).end()

using namespace std;
using Graph = vector<vector<int>>;


int main() {
  ll x;
  cin>>x;
  ll a,b;
  ll y=sqrt(x);
 // cout <<y<<endl;
  rep(i,y){
    if(x%i==0){
     
      for(ll j = 0 ; j <=pow(x,0.6)  ; j ++ ){
      //  cout<<pow(x,0.2)<<endl;
        if(j*j*j*j+j*j*j*(j-i)+j*j*(j-i)*(j-i)+j*(j-i)*(j-i)*(j-i)+(j-i)*(j-i)*(j-i)*(j-i)==x/i){
          a=j;
          b=j-i;
          break;
        }
      }
       if(!(a==0&&b==0)) break; 
    }
  }
  
  cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 4044
// ref. https://www.youtube.com/watch?v=JQmQjJd-sLA

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  string s;
  cin >> s;
  ll n = s.size();
  ll K;
  cin >> K;

  // dp[i][j][l] .. use [0, i). j .. count of not 0 is k. l=0: equal, l=1: smaller.
  vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(4, vector<ll>(2)));
  dp[0][0][0] = 1;

  rep(i, n) rep(j, 4) rep(k, 2) {
    ll nd = s[i]-'0';
    rep(d, 10) {
      ll ni = i+1;
      ll nj = j;
      ll nk = k;
      if (d != 0) { ++nj; }
      if (nj > K) { continue; } // we need only [0, K]
      if (k == 0) {
        if (d > nd) { continue; } // larger value.
        if (d < nd) { nk = 1; } // becomes smaller
      }
      dp[ni][nj][nk] += dp[i][j][k];
    }
  }

  cout << dp[n][K][0] + dp[n][K][1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>


using namespace std;


int main(){
  long long N;
  string ans;
  cin >> N;
  while(true){
    long long tmp, mod;
    tmp = --N;
    mod = tmp % 26;
    tmp = tmp / 26;
    // cout << tmp << mod << endl;
    ans += char('a' + mod);
    N = tmp;
    if (N == 0){
      break;
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}


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

int main(){
    int a,b,c,x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                int total = 500*i + 100*j + 50*k;
                if(total==x) ans++;
            }
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[500005],n,maxv;
int main(){
    scanf("%d",&n);
    while(n--){
        int num;
        scanf("%d",&num);
        a[num]++,a[num-1]++,a[num+1]++;
    }
	for(int i=0;i<=500000;i++)if(a[i]>maxv) maxv=a[i];
    printf("%d\n",maxv);
    return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
k,a,b = map(int, input().split())

if a >= b:
  print(k+1)
else:
  if k<=a:
    print(k+1)
  elif a+2 > b:
    print(k+1)
  else:
    saisyomade=a+1
    kk=k-saisyomade
    print(b+(kk//2)*(b-a)+kk%2)


Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int expression(string &s, string::iterator &begin) {
    int ret = 0;
    if (*begin >= '0') ret = *begin - '0';
    if (*begin == '-') {
        ret = 2 - expression(s, ++begin);
    }
    if (*begin == '(') {
        ret = expression(s, ++begin);
        begin++;
        if (*begin == '*') {
            ret = min(ret, expression(s, ++begin));
        } else if (*begin == '+') {
            ret = max(ret, expression(s, ++begin));
        }
        begin++;
    }
    return ret;
}

int solve(string S) {
    int ret = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                string s;
                for (int l = 0; l < S.length(); l++) {
                    if (S[l] == 'P') s.push_back('0' + i);
                    else if (S[l] == 'Q') s.push_back('0' + j);
                    else if (S[l] == 'R') s.push_back('0' + k);
                    else s.push_back(S[l]);
                }
                string::iterator begin = s.begin();
                int tmp = expression(s, begin);
                if (tmp == 2) ret++;
            }
        }
    }
    return ret;
}

int main(void) {
    string s;
    vector<int> ans;
    while (1) {
        cin >> s;
        if (s[0] == '.') break;
        ans.push_back(solve(s));
    }
    for (auto &i : ans) {
        cout << i << endl;
    }
}


Measured memory_bytes: 3076
n = int(input())
a = list(map(int,input().split()))
a.sort()
tmp = []
i =n-1
while i >0:
    if a[i] == a[i-1]:
        tmp.append(a[i])
        i -=2
    else:
        i -=1
if len(tmp)>=2:
    print(tmp[0]*tmp[1])
else:
    print(0)
    

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

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

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for(auto &e : A) cin >> e;
    for(int i = 1; i < N; ++i) A[i] = gcd(A[i], A[i - 1]);
    cout << A[N - 1] << '\n';
    return 0;
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int N,W;
    int dp[105][305] = {{}};
    Scd2(N,W);
    int w,v;
    int w_min = INF;
    int w_flow = 0;
    Rep(i,N){
        Scd2(w,v);
        w_min = min(w,w_min);
        w -= w_min;
        for(int ai = i+1; ai >= 0; ai--)
        for(int bi = w_flow; bi >= 0; bi--){
            dp[ai+1][bi+w] = max( dp[ai+1][bi+w], dp[ai][bi]+v );
        }
        w_flow += w;
    }

    int ans = 0;
    Rep(ai,N+2){
        if( ai*w_min > W ) break;
        Rep(bi,305){
            if( ai*w_min + bi > W ) break;
            ans = max(dp[ai][bi],ans);
        }
    }

    printf ("%d\n", ans);

    return 0;
}



Measured memory_bytes: 384
x1,y1,x2,y2=map(int,input().split())
v=[x2-x1,y2-y1]
x3,y3=x2-v[1],y2+v[0]
x4,y4=x3-v[0],y3-v[1]
print(x3,y3,x4,y4)

Measured memory_bytes: 3060
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main() {
	vector<int> n(3);
	for (int i = 0; i < 3; i++) {
		cin >> n.at(i);
	}
	sort(n.begin(), n.end());
	int ans = n.at(0) + n.at(1) + n.at(2) * 10;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
void quicksort(int a[],int left,int right){
    int i=left,j=right;
    int tmp,pivot=a[i+(j-i)/2];
    while(1){
        while(a[i]<pivot)
            i++;
        while(a[j]>pivot)
            j--;
        if(i>=j)
            break;
        tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
        i++;
        j--;
    }
    if(left<i-1)
        quicksort(a,left,i-1);
    if(j+1<right)
        quicksort(a,j+1,right);
}
int main(void){
    int N,K;
    scanf("%d",&N);
    int d[N];
    for(int i=0;i<N;i++){
        scanf("%d",&d[i]);
    }
    quicksort(d,0,N-1);
    
    K=d[N/2]-d[N/2-1];
    printf("%d\n",K);
    return 0;
}


Measured memory_bytes: 512
/*  ***  In The Name of God ... ***  */ 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define endl '\n' 
template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

const int maxn = 1e5 + 10 ;

int q ;

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> q;
	cout << 48 - q ; 
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
int n,x;

int main()
{
    while(true)
    {
        scanf("%d %d", &n, &x);
        if(n == 0 && x == 0) break;
        
        int count=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                for(int k=j+1;k<=n;k++)
                {
                    if(x==i+j+k)count++;
                }
            }
        }
        
        std::cout<<count<<"\n";
        
    }
}


Measured memory_bytes: 3164
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<queue>
#include<string>
#include<unordered_set>
#include<vector>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000;

ll N, M;

int main() {
    cin >> N >> M;
    if(N==M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
object Main {
  val Offset: Int = 'a' - 'A'
  val EOT: String = "END_OF_TEXT"

  def main(args: Array[String]): Unit = {
    val target = io.StdIn.readLine().toLowerCase
    val count =
      Iterator.continually(io.StdIn.readLine())
        .takeWhile(_ != EOT)
        .flatMap(toLowerCaseWords)
        .count(_ == target)

    println(count)
  }

  def toLowerCaseWords(line: String): Seq[String] = {
    import collection.mutable
    val words = mutable.Buffer.empty[String]
    var length = 0
    val buf = new Array[Char](1000 + 1)
    line.foreach { c =>
      if ('A' <= c && c <= 'Z' || 'a' <= c && c <= 'z') {
        buf(length) = c.toLower
        length += 1
      } else if (length > 0) {
        if (length <= 10) {
          words += String.valueOf(buf.take(length))
        }
        length = 0
      }
    }
    if (length > 0) {
      words += String.valueOf(buf.take(length))
    }
    words
  }
}

Measured memory_bytes: 44076
#define REP(i, t, n)  for (int i = t; i < n; i++)
#define ALL(n)        (n).begin(),(n).end()
#include <limits.h>
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <functional>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef bool               BOOL;
typedef short              WORD;
typedef unsigned short     U_WORD;
typedef long               DWORD;
typedef unsigned long      U_DWORD;
typedef long long          QWORD;
typedef unsigned long long U_QWORD;

#define N_MAX (100000)
#define INF   (10000000000000000)

typedef struct {
  DWORD  dwTo;
  QWORD  qwDist;
}EDGE;

typedef enum {
  NUM_TYPE_ODD,
  NUM_TYPE_EVEN,
}NUM_TYPE;

typedef enum {
  WHITE = 0,
  BLACK,
  NONE,
}COLOR;

DWORD  N;
vector<EDGE>  vGraph[N_MAX + 1];
vector<COLOR> vColorGraph;


void dfs(NUM_TYPE eNumType, COLOR eColor, DWORD dwVertex) 
{
  if (vColorGraph[dwVertex] == NONE) {
    vColorGraph[dwVertex] = eColor;
  } else {
    return;
  }

  for (auto iterEdge : vGraph[dwVertex]) {
    NUM_TYPE eNextNumType;
    COLOR   eNextColor;

    switch (eNumType) {
    case NUM_TYPE_ODD:
      if (iterEdge.qwDist % 2 == 1) {
        // 奇数の場合
        eNextNumType = NUM_TYPE_EVEN;

      } else {
        // 偶数の場合
        eNextNumType = NUM_TYPE_ODD;
      }
      break;
    case NUM_TYPE_EVEN:
      if (iterEdge.qwDist % 2 == 1) {
        // 奇数の場合
        eNextNumType = NUM_TYPE_ODD;

      } else {
        // 偶数の場合
        eNextNumType = NUM_TYPE_EVEN;
      }
      break;
    }
    
    if (eNextNumType == NUM_TYPE_ODD) {
      dfs(NUM_TYPE_ODD, BLACK, iterEdge.dwTo);
    } else {
      dfs(NUM_TYPE_EVEN, WHITE, iterEdge.dwTo);
    }  
  }

}

void solve_main()
{
  QWORD qwAns = 0;
  DWORD Q;
  vector<QWORD> vecMaxDistance;
  
  cin >> N;


  REP(i, 0, N - 1) {
    DWORD tmpA, tmpB, tmpDist;
    cin >> tmpA >> tmpB >> tmpDist;

    vGraph[tmpA].push_back(EDGE{ tmpB, tmpDist});
    vGraph[tmpB].push_back(EDGE{ tmpA, tmpDist});

  }

  vColorGraph.resize(N + 1);
  REP(i, 0, N + 1) {
    vColorGraph[i] = NONE;
  }

  dfs(NUM_TYPE_EVEN, WHITE, 1);

  REP(i, 1, N + 1) {
    cout << vColorGraph[i] << endl;
  }

}

int main()
{
#ifdef FOR_IDE
  ifstream in("input.txt");
  std::cin.rdbuf(in.rdbuf());
#endif

  solve_main();
  return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
int main(){
    cout<<fixed<<setprecision(6);

    int n;
    cin>>n;

    double x;
    string y;

    double sum=0;

    for (int i=0;i<n;i++) {
        cin>>x>>y;
        if(y=="JPY"){
            sum+=x;
        }
        else if(y=="BTC"){
            sum+=x*380000;
        }
    }

    cout <<sum<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

const ll mod = 1e9+7;
ll mul(ll a, ll b) {
    return a * b % mod;
}
ll fact(ll n) {
    if (n == 0) return 1;
    return n * fact(n-1) % 1000000007;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // メインプログラムここから
    ll n; cin >> n;
    cout << fact(n) << endl;
    // ここまで
}


Measured memory_bytes: 1792
a,b=map(int,input().split())

def factorization(n):
    if n < 2:
        return []

    res = []

    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res.append(i)
            n //= i

    if n > 1:
        res.append(n)

    return res

def gcd(A, B):
    if B == 0:
        return A
    else:
        return gcd(B, A % B)

g=gcd(a,b)
l=factorization(g)

print(len(set(l))+1)

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int main(){
    int n;
    cin >> n;
    int ans = 0, maxi = 0;
    rep(i, n){
        int p;
        cin >> p;
        ans += p;
        maxi = max(maxi, p);
    }
    ans -= maxi / 2;
    cout << ans << endl;
    return 0;
}

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


// パスカルの三角形
long long pas3[4002][4002] = {0};
#define MOD (1000000000+7)


void calc_pas() {
	pas3[0][0] = 1;
	for (int i = 1; i <= 4001; i++) {
		for (int j = 0; j <= i; j++) {
			if (j==0) {
				pas3[i][j] = pas3[i-1][j];
			} else {
				pas3[i][j] = pas3[i-1][j-1]+pas3[i-1][j];
			}
			pas3[i][j] %= MOD;
		}
	}
}

long long choose(int x, int y) {
	return pas3[x][y];
}

// x個をyグループに分割する、グループ0個可
long long fd(int x, int y) {
	if (x<0) return 0;
	if (y<=0) return 0;
	return choose(x+y-1, y-1);
}

// x個をyグループに分割する、グループ内0個不可
long long f(int x, int y) {
	if (y<=0) return 0;
	return fd(x-y, y);
}

// redの分け方の合計
long long S(int red, int i) {
	if (red<=1) return 1;
	return (f(red, i-1) + f(red, i) + f(red,i) + f(red, i+1))%MOD;
}


int main(void) {
	int N, K;
	cin >> N >> K;

	calc_pas();

	int red = N-K;
	for (int i = 1; i <= K; i++) {
		if ((red+1)<i) cout << 0 << endl;
		else {
			long long ans = S(N-K, i) *  f(K, i) % MOD;
			cout << ans << endl;
		}
	}
  return 0;
}


Measured memory_bytes: 123648
/*****************************************************
 *     created by: nayakashutosh9
 * "Winners Never Quit and Quitters Never Win".
*****************************************************/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define endl '\n'
#define mod 1000000007
#define inf 1e18
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 300005;
/**********************************************************************************************/

vector<int> a;
void solve() {
	int n; cin >> n;
	a.clear(); a.resize(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		for (int j = i + 1; j < n - 1; j++) {
			for (int k = j + 1; k < n; k++) {
				unordered_set<int> vis;
				vis.insert(a[i]);
				vis.insert(a[j]);
				vis.insert(a[k]);
				if (vis.size() == 3 && a[i] + a[j] > a[k]) ans++;
			}
		}
	}
	cout << ans << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1, z = 1;
	// cin >> t; cin.ignore();
	while (t--) {
		// cout << "Case #" << (z++) << ": ";
		// clock_t start = clock();
		solve();
		// clock_t end = clock();
		// cout << (end-start) << endl;
		//print execution time in ms
	}

	return 0;
}

Measured memory_bytes: 3616
#include<cstdio>
using namespace std;
#define N 605
#define mod 1000000007
int dp[N][N][N],c1,n,is[N],a,b;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		if(a>b)a^=b^=a^=b;
		if(b==-1)c1++;
		else if(a==-1)is[n*2-b+1]=1;
		else is[n*2-a+1]=is[n*2-b+1]=2;
	}
	dp[0][0][0]=1;
	for(int i=1;i<=n*2;i++)
	for(int j=0;j<=i&&j<=n;j++)
	for(int k=0;k<=i;k++)
	if(dp[i-1][j][k])
	{
		if(is[i]==2)dp[i][j][k]=dp[i-1][j][k];
		else if(is[i]==1){dp[i][j+1][k]=(dp[i-1][j][k]+dp[i][j+1][k])%mod;if(k)dp[i][j][k-1]=(dp[i][j][k-1]+dp[i-1][j][k])%mod;}
		else
		{
			if(k)dp[i][j][k-1]=(dp[i][j][k-1]+dp[i-1][j][k])%mod;
			if(j)dp[i][j-1][k]=(dp[i][j-1][k]+1ll*dp[i-1][j][k]*j)%mod;
			dp[i][j][k+1]=(dp[i][j][k+1]+dp[i-1][j][k])%mod;
		}
	}
	int as=dp[n*2][0][0];
	for(int i=1;i<=c1;i++)as=1ll*as*i%mod;
	printf("%d\n",as);
}//

Measured memory_bytes: 858240
package main

import "fmt"
import "strings"

func main() {
	var s string
	fmt.Scan(&s)

	keys := strings.Split(s, "")

	ret := make([]string, 0, len(keys))
	for _, k := range keys {
		if k == "0" {
			ret = append(ret, "0")
		}
		if k == "1" {
			ret = append(ret, "1")
		}
		if k == "B" {
			if len(ret) == 0 {
				continue
			}
			ret = ret[0 : len(ret)-1]
		}
	}

	fmt.Println(strings.Join(ret, ""))
}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
graph = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

# print(graph)
v = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    v[p - 1] += x
# print(v)


seen_points = [True] * N
seen_points[0] = False
stack = [0]

while stack:
    now = stack.pop()
    for i in graph[now]:
        if seen_points[i]:
            seen_points[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)


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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int n, k; cin >> n >> k;
  vector<P> v(n);
  REP(i,n) {
    int a,b; cin >> a >> b;
    v[i] = P(a,b);
  }
  SORT(v);
  int counter = 0;
  for(auto& itr : v) {
    counter += itr.second;
    if(counter >= k) {
      cout << itr.first << endl;
      return 0;
    }
  }
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

cnt = [0] * N
for i in range(N):
	cnt[A[i] - 1] += 1

cmbr2 = [0] * (N + 1)
for i in range(1, N + 1):
	cmbr2[i] = cmbr2[i - 1] + i - 1

cmb = [0] * N
for i in range(N):
	cmb[i] = cmbr2[cnt[i]]

asum = sum(cmb)
for i in A:
	print(asum - cmbr2[cnt[i - 1]] + cmbr2[cnt[i - 1] - 1])

Measured memory_bytes: 26140
"use strict";
main(require("fs").readFileSync("/dev/stdin", "utf8").replace(/\r?\n$/, "").split(/\r?\n/));

function main(lines){
	lines.some(function(line){
		if(line == "0") return true;
		console.log(line.split("").reduce(function(a,b){return a+ +b;}, 0));
	});
}

Measured memory_bytes: 17092