akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

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

const int maxn = 2e5 + 5;
const int mod = 998244353;
int n,f[maxn],g[maxn];
ii a[maxn];
int bit[maxn];
void update(int x,int val){
    for( ; x < maxn ; x += x & -x)bit[x] = max(bit[x],val);
}
int query(int x){
    int res = 0;
    for( ; x > 0 ; x &= x - 1)res = max(res,bit[x]);
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i].first >> a[i].second;
    sort(a+1,a+n+1);
    f[n + 1] = 1;
    for(int i = n ; i >= 1 ; --i){
        int tmp = lower_bound(a+1,a+n+1,mp(a[i].first+a[i].second,0)) - a - 1;
        g[i] = max(i, query(tmp));
        update(i,g[i]);
//        cout << g[i] << " " << endl;
        f[i] = (f[i + 1] + f[g[i] + 1]) % mod;
    }
    cout << f[1];
}




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

using namespace std;

int main() {
  array<int, 32> arr = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin >> n;
  cout << arr[n-1] << '\n';
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int k = sc.nextInt();
    int p[] = new int[110];
    int cnt=0;
    for(int i =0;i<110;i++){
      p[i]=100000000;
    }
    for(int i=0;i<100;i++){
      if(a%(i+1)==0&&b%(i+1)==0){
        p[i]=i+1;
        cnt=cnt+1;
      }
    }
    Arrays.sort(p);
//    for(int i=0;i<10;i++){
//    System.out.println(p[i]);
//      }
    System.out.println(p[cnt-k]);
      
      
  }
  

  
}

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

using namespace std;
using ll = long long;

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

  string s;
  cin >> s;
  int k;
  cin >> k;
  int n = s.size();

  // dp[桁数][k(1〜9を何個含むか)][未満フラグ]
  vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(k + 2, vector<ll>(2)));

  // 初期条件
  // 最上位桁+1桁目を便宜上0とする。
  // このとき、未満フラグOffの数値が1種類存在することになる。
  dp[0][0][0] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      int D = s[i] - '0';

      for (int h = 0; h <= 9; h++) {
        // この桁を0にする場合
        // dp[i + 1][j][0 or 1]
        if (h == 0) {
          //未満フラグOnのものはそのまま引き継ぎ
          dp[i + 1][j][1] += dp[i][j][1];

          // 未満フラグOffのものの引き継ぎ方を決定
          if (h == D) {
            // 未満フラグOff→Offで引き継ぎ
            dp[i + 1][j][0] += dp[i][j][0];
          } else if (h < D) {
            // 該当桁の値Dが1以上なら未満フラグOff→Onで引き継ぎ
            dp[i + 1][j][1] += dp[i][j][0];
          }
        }
        // この桁を0以外にする場合([k]が変化する)
        // dp[i + 1][j + 1][0 or 1]
        else {
          // 未満フラグOnのものはそのまま引き継ぎ
          dp[i + 1][j + 1][1] += dp[i][j][1];

          if (h == D) {
            // 未満フラグOff→Offで引き継ぎ
            dp[i + 1][j + 1][0] += dp[i][j][0];
          } else if (h < D) {
            // 未満フラグOff→Onで引き継ぎ
            dp[i + 1][j + 1][1] += dp[i][j][0];
          }
        }
      }
    }
  }
  ll ans = dp[n][k][0] + dp[n][k][1];
  cout << ans << endl;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

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

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

int gcd(int a, int b){
	if (b == 0)return a;
	return gcd(b, a % b);
}


int main(void){
    int n, m, c;
    cin >> n >> m >> c;

    vector<int> b(m);
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        int total = 0;
        for(int j = 0; j < m; j++){
            int tmp = a[i][j] * b[j];
            total += tmp;
        }
        if(total + c > 0){
            ans++;
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    string S; cin >> S;
    vector<string> V = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    for (int i = 0; i < V.size(); ++i) {
        if (S == V[i]) {
            cout << 7 - i << endl;
            break;
        }
    }
}


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

const int maxn = 200200;
int n, a[maxn], ans = 0;
map< int, int, greater<int> > s;

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%d", &a[i]), s[a[i]]++;
    for(auto p : s) {
        if(__builtin_popcount(p.first) == 1)
            ans += p.second / 2;
        else {
            int k = log2(p.first) + 1;
            int rem = (1 << k) - p.first;
            if(s.find(rem) != s.end()) {
                int mn = min(s[rem], p.second);
                s[rem] -= mn;
                ans += mn;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;

  cout << (e - a <= k ? "Yay!" : ":(") << endl;
  return 0;
}


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

c = N - K
l = []

for j in range(K, N):
        l.append(A[j - K])
        l.append(A[j])

L = len(l)
for i in range(0, L, 2):
    if l[i + 1] > l[i]:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 116936
#include <bits/stdc++.h>
#define prt_cs                  printf("Case %lld: ",cs)
#define sqr(x)                  (x)*(x)
#define ms(a,b)                 memset(a, b, sizeof(a))
#define db                      double
#define ll                      long long int
#define MOD                     100000007
#define PI                      2*acos(0.0)
#define pii                     pair< int, int >
#define READ                    freopen("in.txt","r",stdin)
#define WRITE                   freopen("out.txt","w",stdout)
#define gcd(a, b)               __gcd(a, b)
#define lcm(a, b)               (((a)*(b))/gcd(a,b))
#define MAX                     100005

using namespace std;

char a[MAX];

int main()
{
//    READ;
//    WRITE;
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]!=a[i-1])cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 384
#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>;
 
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};
 
int main() {
  int n, m;
  cin >> n >> m;
  UnionFind uf(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    uf.unite(a,b);
  }
 
  int ans = 0;
  rep(i,n) {
    if(!uf.same(0,i)){
      uf.unite(0, i);
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define pb push_back 
#define x first 
#define y second 
#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
const int dirx[] = {-2,-1,1,2, 1, -1};
const int diry[] = {0,1,1,0, -1, -1};
inline void debugMode() {
    #ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif
}

int n, a[100100], b;
string s;
bool u = 1;

int main(){
	//	debugMode();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> b;
	cin >> s;
	if (s.size() != n + b + 1) return cout << "No",0;
	for (int i = 0; i < s.size(); i++){
		if (i == n) u &= (s[i] == '-');
		else u &= (s[i] >= '0' && s[i] <= '9');
	}
	if (u) cout << "Yes";
	else cout << "No";
	return 0;
}


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

using namespace std;


int main(){
	
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int N;
	char ch[10];

	ch[2] = ch[4] = ch[5] = ch[7] = ch[9] = 'h';
	ch[0] = ch[1] = ch[6] = ch[8]  = 'p';
	ch[3] = 'b';

	cin>>N;
	cout<<ch[N%10]<<"on"<<endl;

	
	return 0;
}


Measured memory_bytes: 3120
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  string s;
  cin >>s;
  for(int i=0; i<a;i++){
    if(!('0'<=s[i] && s[i]<='9')) {cout <<"No"<<endl; return 0;}
  }

  if(s[a]!='-') {cout <<"No"<<endl; return 0;}

  for(int i=a+1; i<=a+b;i++){
    if(!('0'<=s[i] && s[i]<='9'))  {cout <<"No"<<endl; return 0;}
  }
  cout <<"Yes"<<endl;
}


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

int a[100001];
ll d[200100],t[200100];
int main(){
    int n,m;
    cin>>n>>m;
    rep(i,n){
        cin>>a[i];
    }
    ll sum=0;
    rep(i,n-1){
        int l=a[i],r=a[i+1];
        if(r<l) r+=m;
        sum+=r-l;
        ++d[l+2];
        --d[r+1];
        t[r+1]-=r-l-1;
    }
    FOR(i,1,2*m+1){
        d[i]+=d[i-1];
        t[i]+=d[i]+t[i-1];
    }
    ll mn=100010001000100010;
    FOR(i,1,m+1) mn=min(mn,sum-t[i]-t[i+m]);
    cout<<mn<<endl;
    return 0;
}

Measured memory_bytes: 3712
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=100;
int n;
int a[maxn+5][5];
bool check(){
	for(int i=1;i<=n-2;i++){
		if(a[i][0]!=a[i][1]) continue;
		if(a[i+1][0]!=a[i+1][1]) continue;
		if(a[i+2][0]!=a[i+2][1]) continue;
		return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&a[i][0],&a[i][1]);
	if(check()) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 1660
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ x, a, b ] <- map read . lines <$> getContents
	print $ ( x - a ) `mod` b


Measured memory_bytes: 508
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
int main(void){
    double r, area, length;
    cin >> r;
    area = r * r * M_PI;
    length = 2 * r * M_PI;
    cout << std::fixed << area << " " << length << endl;
    return 0;
}




Measured memory_bytes: 3236
#include <iostream>
#include <vector>

int main(int argc, char const *argv[]) {

    int A,B,C;
    std::cin >> A >> B >> C;

    std::vector<bool> calced_number(B);
    int calc_number = A % B;

    while(calced_number[calc_number] == false)
    {
        calced_number[calc_number] = true;
        calc_number = ( (calc_number + A) % B);
    }

    std::cout << (calced_number[C] ? "YES" : "NO" ) << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;


int main(void){
  int n,i,wh[200005]={};
  string s;
  
  cin >> n >> s;
  
  for (i=0;i<n;i++){
    if (s[i]=='.') wh[i+1]=wh[i]+1;
    else wh[i+1]=wh[i];
  }
  
  int syg,ans=1e9;
  for (i=0;i<=n;i++){
    syg=i-wh[i]+wh[n]-wh[i];
    ans=min(ans,syg);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1412
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n, m;
	HashMap<String, Integer> val;
	HashMap<String, LinkedList<String>> recipe;
	String item;

	void run(){
		for(;;){
			val=new HashMap<String, Integer>();
			recipe=new HashMap<String, LinkedList<String>>();
			n=sc.nextInt();
			if(n==0){
				break;
			}
			for(int i=0; i<n; i++){
				String s=sc.next();
				int d=sc.nextInt();
				val.put(s, d);
			}
			m=sc.nextInt();
			for(int j=0; j<m; j++){
				String s=sc.next();
				int k=sc.nextInt();
				LinkedList<String> list=new LinkedList<String>();
				for(int i=0; i<k; i++){
					String t=sc.next();
					list.add(t);
				}
				recipe.put(s, list);
			}
			item=sc.next();
			solve();
		}
	}

	void solve(){
		println(dfs(item)+"");
	}

	int dfs(String s){
		int res=INF;
		if(val.containsKey(s)){
			res=min(res, val.get(s));
		}
		if(recipe.containsKey(s)){
			int sum=0;
			for(String t : recipe.get(s)){
				sum+=dfs(t);
			}
			res=min(res, sum);
		}
		return res;
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
/* The journey is what brings us pleasure, not the destination <3 */

#include<bits/stdc++.h>

#define PI acos(-1)
#define _fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MOD 1000000007
#define MAX 1000000
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int tc;

int divs(int n){
    int lim=sqrt(n),now=0;
    for(int j=1; j<=lim; j++){
        if(n%j==0){
            now++;
            if(j*j!=n && (n/j)!=j)now++;
        }
    }
    return now;
}

void solve(){

    int n,ans=0;
    cin>>n;
    for(int i=1; i<n; i++){
        ans+=divs(n-i);
    }
    cout<<ans<<endl;
}

int main(){

    _fastIO;

    //cin>>tc; while(tc--)
    solve();

    return 0;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll bg=pow(10,9)+7;
#define ff(i,n) for(i=0;i<n;i++)
#define w(t) while(t--)
#define gg(n1,n2) cin>>n1>>n2;
#define gg3(n1) cin>>n1;
#define hh(n) cout<<n<<endl;
#define t top
#define p push
#define pb push_back
#define mp make_pair
int main() {
     ll i,n,j,k;
     cin>>n;
     ll arr[n];
     for(i=0;i<n;i++)
        cin>>arr[i];
     ll dp[n][n];
     ll sum[n][n];
     for(j=0;j<n;j++)
     {
          sum[0][j]=arr[j];
          for(i=1;i<n-j;i++)
             sum[i][j]=sum[i-1][j]+arr[i+j];
     }
     for(i=0;i<n;i++)
       dp[0][i]=0;
     for(i=1;i<n;i++)
     {
          for(j=0;j<n-i;j++)
          {
               k=0;
               dp[i][j]=dp[k][j]+sum[k][j]+dp[i-k-1][j+k+1]+sum[i-k-1][j+k+1];
               for(k=1;k<i;k++)
               {   
                    dp[i][j]=min(dp[i][j],dp[k][j]+sum[k][j]+dp[i-k-1][j+k+1]+sum[i-k-1][j+k+1]);
               }          
          }
     }
     cout<<dp[n-1][0];
	return 0;
}

Measured memory_bytes: 2688
#include <stdint.h>

int main(void)
{
  uint64_t a, b, k;
  
  scanf("%lu %lu %lu", &a, &b, &k);
 
  if(a>k)
  {
    a -= k;
  }
  else
  {
    k -= a;
    a = 0;
    if(b>k)
    {
      b -= k;
    }
    else
    {
      b = 0;
    }
  }
  
  printf("%lu %lu\n", a, b);
 
  return 0;
}

Measured memory_bytes: 128
Encodetable1 = {
  ' ' => '101',
  '\'' => '000000',
  ',' => '000011',
  '-' => '10010001',
  '.' => '010001',
  '?' => '000001',
  'A' => '100101',
  'B' => '10011010',
  'C' => '0101',
  'D' => '0001',
  'E' => '110',
  'F' => '01001',
  'G' => '10011011',
  'H' => '010000',
  'I' => '0111',
  'J' => '10011000',
  'K' => '0110',
  'L' => '00100',
  'M' => '10011001',
  'N' => '10011110',
  'O' => '00101',
  'P' => '111',
  'Q' => '10011111',
  'R' => '1000',
  'S' => '00110',
  'T' => '00111',
  'U' => '10011100',
  'V' => '10011101',
  'W' => '000010',
  'X' => '10010010',
  'Y' => '10010011',
  'Z' => '10010000'
}
Encodetable2 = {
  '00000' => 'A',
  '00001' => 'B',
  '00010' => 'C',
  '00011' => 'D',
  '00100' => 'E',
  '00101' => 'F',
  '00110' => 'G',
  '00111' => 'H',
  '01000' => 'I',
  '01001' => 'J',
  '01010' => 'K',
  '01011' => 'L',
  '01100' => 'M',
  '01101' => 'N',
  '01110' => 'O',
  '01111' => 'P',
  '10000' => 'Q',
  '10001' => 'R',
  '10010' => 'S',
  '10011' => 'T',
  '10100' => 'U',
  '10101' => 'V',
  '10110' => 'W',
  '10111' => 'X',
  '11000' => 'Y',
  '11001' => 'Z',
  '11010' => ' ',
  '11011' => '.',
  '11100' => ',',
  '11101' => '-',
  '11110' => '\'',
  '11111' => '?'
}

def encode1(str)
  encoded = String.new
  str.each_char{|c| encoded += Encodetable1[c] }
  while encoded.size % 5 != 0
    encoded += "0"
  end
  return encoded
end

def encode2(str)
  encoded = String.new
  source = encode1(str)
  while !source.empty?
    encoded += Encodetable2[source.slice!(0,5)]
  end
  return encoded
end

while input = $stdin.gets
  puts encode2(input.chomp)
end

Measured memory_bytes: 6560
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
#define N 
typedef long long ll;
ll ans=0;
int ch[1000005][27],cnt,len,tot=1,ed[1000005],siz[1000005],fa[1000005],f[1000005][27],id[1000005];
char s[1000005];
void add(char s[])
{
	int len=strlen(s);
	int x=1;
	for(int i=len-1;i>=0;i--)
	{
		int f=s[i]-'a';
		if(!ch[x][f])ch[x][f]=++tot,fa[tot]=x,id[tot]=f;
		x=ch[x][f];
	}
	ed[x]++;
}
void dfs(int x)
{
	
	if(x==0)return;//cout<<x<<endl;
	siz[x]=ed[x];
	for(int i=0;i<26;i++)
	{
		int v=ch[x][i];
		dfs(v);siz[x]+=siz[v];
		f[x][i]+=siz[v];
		for(int j=0;j<26;j++)
		{
			if(j!=i)
			f[x][j]+=f[v][j];
		}	
	}
	//if(x!=1) f[x][id[x]]=siz[x];
	/*
	for(int i=0;i<26;i++)
	{
		cout<<x<<' '<<i<<' '<<f[x][i]<<endl;
	}
	*/
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		add(s);
	}
	dfs(1);
	for(int i=2;i<=tot;i++)	
	if(ed[i])
	{
		ans+=f[fa[i]][id[i]]*ed[i];
		//cout<<i<<' '<<f[fa[i]][id[i]]<<" "<<ed[i]<<' '<<ans<<endl;
	}
	cout<<ans-n<<endl;
     return 0;
} 
/*
5
a
aa
aaa
aaaa
aaaaa
*/

Measured memory_bytes: 285184
import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
li = [na() for _ in range(n)]
tmp = list(itertools.permutations(li))
l = len(tmp)
s = 0
for rt in tmp:
    for i in range(n-1):
        s += ((rt[i+1][0] - rt[i][0]) ** 2 + (rt[i+1][1] - rt[i][1]) ** 2) ** 0.5

print(s/l)






Measured memory_bytes: 7972
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  int h,a;
  cin >> h >> a;
  cout << (h / a) + (h % a + h -1) / h << endl;

  return 0;
}


Measured memory_bytes: 256
import java.lang.Math.*

const val MOD = 1000000007L

fun main(args: Array<String>) {
    val n = readInt()
    val columnNum = n.toString().length
    var ans = 0
    (columnNum / 2).rep {
        ans = ans * 100 + 9
    }
    if (columnNum % 2 == 1) {
        ans += (n - pow(10.toDouble(), columnNum.toDouble() - 1)).toInt() + 1
    }
    println(ans)
}


fun readList() = readLine()!!.split(' ')
fun readInt() = readLine()!!.split(' ').map(String::toInt).first()
fun readIntList() = readList().map(String::toInt)
fun readLongList() = readList().map(String::toLong)
fun readDoubleList() = readList().map(String::toDouble)

fun readPair(): Pair<String, String> {
    val splite = readLine()!!.split(' ')
    return Pair(splite[0], splite[1])
}

fun <T> List<T>.copy() = this.map { it }

// 速度のためforEachは避ける
inline fun Int.rep(start: Int = 0, body: (Int) -> Unit) {
    for (i in start until this + start) {
        body(i)
    }
}

inline fun Long.rep(start: Long = 0, body: (Long) -> Unit) {
    for (i in start until this + start) {
        body(i)
    }
}

// 約数のList
fun divisor(value: Long): List<Long> {
    val max = sqrt(value.toDouble()).toLong()
    return (1..max)
        .filter { value % it == 0L }
        .map { listOf(it, value / it) }
        .flatten()
        .sorted()
}

// 範囲内の素数を取得
// fromだけ指定すると戻り値の個数で素数判定ができる
fun prime(from: Long, to: Long = from): List<Long> {
    return (from..to).filter { i ->
        val max = Math.sqrt(i.toDouble()).toLong()
        (2..max).all { j -> i % j != 0L }
    }
}

// 素因数分解
fun decom(value: Long): List<Long> {
    if (value == 1L) return listOf(1)
    val max = Math.sqrt(value.toDouble()).toLong()
    return prime(2, max).filter { value % it == 0L }
}

// 最大公約数
fun gcd(a: Long, b: Long): Long {
    return if (a % b == 0L) b else gcd(b, a % b)
}

// 文字列を入れ替え
fun swap(base: String, a: String, b: String): String {
    return base.map {
        when (it) {
            a.toCharArray()[0] -> b
            b.toCharArray()[0] -> a
            else -> it.toString()
        }
    }.joinToString()
}

Measured memory_bytes: 38300
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
	string s;
	cin>>s;
	int num=0;
	for (int i=0;i<s.size();i++){
		if (s[i]=='o'){
			num++;
		}
	}
	cout<<700+num*100<<endl;
	return 0;
}

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

using namespace std;

typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)

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

// aとbの最大公約数
ll gcd(ll a, ll b) {
	if (a < b) gcd(b, a);
	ll r;
	while ((r = a%b)) {
		a = b;
		b = r;
	}
	return b;
}

signed main(){

	int N;
	cin >> N;
	int ans = 0;
	rep(i, N){
		int a; cin >> a;
		if (i == 0) ans = a;
		else ans = gcd(ans, a);
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define db(...) " [" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "] "
using ii=long long;
const int M = 1 << 13;
ii mask[M];
void chmin(ii &a, ii b) { a = min(a, b); }
const ii inf = 1e18;
int main()
{
    fill(mask, mask + M, inf);
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        ii a, b;
        cin >> a >> b;
        int z = 0;
        for (int j = 0; j < b; ++j) {
            int x;
            cin >> x;
            z |= 1 << (x - 1);
        }
        chmin(mask[z], a);
        for (int k = z; k; k = z & (k - 1)) {
            chmin(mask[k], a);
        }
    }
    for (int j = 1; j < (1 << n); ++j) {
        for (int k = j; k; k = j & (k - 1)) {
            chmin(mask[j], mask[k] + mask[j &(~k)]);
        }
    }
    if (mask[(1 << n) - 1] == inf) {
        cout << -1 << "\n";
    }
    else {
        cout << mask[(1 << n) - 1] << "\n";
    }
}


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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for(int& i : a) cin >> i;
  sort(a.begin(), a.end());
  k = max(0, n - k); // 生き残るモンスターの数
  cout << accumulate(a.begin(), a.begin() + k, 0LL) << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)

int main()
{
  int k, a, b;
  cin >> k >> a >> b;
    for (int i = a; i <= b; i++)
    {
      if (i % k == 0)
      {
        cout << "OK" << endl;
        return 0;
      }
    }
    cout << "NG" << endl;
}



Measured memory_bytes: 3636
#include <stdio.h>

int main() {
  char s[10];
  int cnt = 0;
  
  scanf("%s", s);
  if(s[0] == '1') cnt++;
  if(s[1] == '1') cnt++;
  if(s[2] == '1') cnt++;
  
  printf("%d\n", cnt);
  
  return 0;
}

Measured memory_bytes: 128
c = [1868, 1912, 1926, 1989]

e, y = [int(num) for num in input().split()]
if e > 0:
    print(c[e - 1] + y - 1)
else:
    if y < c[1]:
        print('M{}'.format(y - c[0] + 1))
    elif y < c[2]:
        print('T{}'.format(y - c[1] + 1))
    elif y < c[3]:
        print('S{}'.format(y - c[2] + 1))
    else:
        print('H{}'.format(y - c[3] + 1))

Measured memory_bytes: 7740
#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <numeric>

int main()
{
    int n, m;
    std::cin >> n >> m;

    constexpr int64_t inf = 1ull << 60;

    std::vector<int64_t> dist(n, inf);
    dist[0] = 0;
    std::vector<std::unordered_map<int64_t, int64_t>> edge(n);

    std::vector<bool> loop(n, false);

    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        --a;
        --b;
        edge[a][b] = -c;
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (dist[j] == inf)
            {
                continue;
            }
            for (const auto e : edge[j])
            {
                dist[e.first] = std::min(dist[e.first], dist[j] + e.second);
            }
        }
    }
    const auto ans = -dist[n - 1];

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (dist[j] == inf)
            {
                continue;
            }
            for (const auto e : edge[j])
            {
                if (dist[j] + e.second < dist[e.first])
                {
                    dist[e.first] = dist[j] + e.second;
                    loop[e.first] = true;
                }
                if (loop[j])
                {
                    loop[e.first] = true;
                }
            }
        }
    }

    if (loop[n - 1])
    {
        std::cout << "inf" << std::endl;
    }
    else
    {
        std::cout << ans << std::endl;
    }
    return 0;
}


Measured memory_bytes: 3764
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define int long long
#define ll getchar();getchar();return 0;
using namespace std;
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n%i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	int ans;
	for (int i = (min(x, y)); i >= 1; i--) {
		if (x%i == 0 && y%i == 0) {
			ans = i;
			break;
		}
	}
	return ans;
}
int yakusuunowa(int n) {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (n%i == 0)ans += i;
	}
	return ans;
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int ketanowa(int n) {
	int cnt = 0, sum = 0;
	for (int i = 10; i <= n * 10; i *= 10) {
		if (i == 10)cnt += n % i;
		else sum += (n%i - n % (i / 10)) / (i / 10);
	}
	return cnt + sum;
}
signed main() {
	int n,ans=1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		ans *= i;
		ans = ans % 1000000007;
	}
	cout << ans << endl;
	ll
}


Measured memory_bytes: 256
import math
a,b,h,m = map(int,input().split())
pi = math.pi
dh = 30 * h
dh += 0.5 * m
dm = 6 * m
diff = abs(dh - dm)
if diff > 180:
    diff = 360 - diff
x = b * b + a * a - 2 * a * b * math.cos(diff * pi / 180)
ans = math.sqrt(x)
print(ans)

Measured memory_bytes: 9520
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int main(void)
{
    int N,K;
    cin >> N >> K;
    int h[N];
    for(int i = 0;i < N; i++) cin >> h[i];
    sort(h,h+N);
    int min = INT_MAX;
    int maxmin;
    for(int i=0;i<N-K+1;i++){
        maxmin = h[i+K-1]-h[i];
        if(min > maxmin) min = maxmin;
    }

    cout << min << endl;

    return 0;
}

Measured memory_bytes: 640
//Compete against Yourself.
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int a, b;

int32_t main(){_
   
   cin >> a >> b;

   if (a * 500 >= b){
        cout<<"Yes";
     }  
     else{
      cout<<"No";
     }
   

   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll long long
#define MOD 1000000007
#define EPS 0.000001
#define f first
#define s second
#define in(n) scanf("%lld", &n)
#define ina(arr,n) for(ll x = 0; x < n; x++) in(arr[x]);
#define loop(i,n) for(ll i=0;i<n;i++)
#define leep(i,n) for(ll i=1;i<=n;i++)

ll int powe(int i)
{
    ll res=1;
    for(int k=0;k<i;k++)
    {
        res=(res*2)%MOD;
    }
    return res;
}

unsigned long long int sumXOR(unsigned ll int arr[], int n)
{
    unsigned long long int sum = 0;
    for (int i = 0; i < 70; i++)
    {
        //  Count of zeros and ones
       unsigned ll zc = 0, oc = 0;

        // Individual sum at each bit position
        unsigned long long int idsum = 0;
        for (int j = 0; j < n; j++)
        {
            if (arr[j] % 2 == 0)
                zc++;
            else
                oc++;
            arr[j] /= 2;
        }

        // calculating individual bit sum
        unsigned ll int power=powe(i);
        idsum = (((oc * zc)%MOD) *power)%MOD;

        // final sum
        sum =(sum+idsum)%MOD;
    }
    return sum;
}

int main()
{

 int n;
 cin>>n;
 unsigned ll int arr[n];
 for(int i=0;i<n;i++)cin>>arr[i];
 cout<<sumXOR(arr,n);
}


Measured memory_bytes: 2560
S = input()
l, r = int(S[:2]), int(S[2:])
if 0<l<13 and 0<r<13:
    print("AMBIGUOUS")
elif 0<l<13:
    print("MMYY")
elif 0<r<13:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 9120
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=2e5+50;
typedef long long ll;
int n;
int a[maxn];
ll cnt[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),++cnt[a[i]];
    ll now=0;
    for(int i=1;i<=n;++i)
    {
        now+=cnt[i]*(cnt[i]-1)/2;
    }
    for(int i=1;i<=n;++i)
    {
        int x=a[i];
        now-=cnt[x]*(cnt[x]-1)/2;
        --cnt[x];
        now+=cnt[x]*(cnt[x]-1)/2;
        printf("%lld\n",now);
        now-=cnt[x]*(cnt[x]-1)/2;
        ++cnt[x];
        now+=cnt[x]*(cnt[x]-1)/2;
    }
    return 0;
}

Measured memory_bytes: 3968
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <iomanip>
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1001001000;
const int MOD = 1000000007;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

using Graph = vector<vector<int>>;
//再帰とかグラフを使うときは予めNの最大値のグローバル配列を取っておく
int N;
vector<int> E[200001];
vector<bool> seen;
typedef pair<int, int> P;
int D[101];
//頂点状態を表すcolor[]において、0は未訪問、1は訪問中、2は完了を表す。
int color[101];
int find_time = 0;

int main() {
    int H, N; cin >> H >> N;
    int A[10001], B[10001];
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    //体力をi減らすための魔力の最小値をdp
    int dp[114514];
    for (int i = 0; i < 114514; i++) dp[i] = INF;
    dp[0] = 0;
    
    for (int i = 0; i <= H; i++) {
        for (int j = 0; j < N; j++) {
            chmin(dp[i + A[j]], dp[i] + B[j]);
        }
    }
    int count = 0;
    for (int i = 0; i < 114514-H; i++) {
        dp[H] = min(dp[H], dp[H + i]);
    }

    //for (int i = 0; i < H; i++) cout << dp[i] << endl;
    cout << dp[H] << endl;
}


Measured memory_bytes: 5376
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include <cmath>
#include <limits>
#include <numeric>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    int n;
    ll a[100005]={};
    ll b[100005]={};
    scanf("%d",&n);
    ll sum=0;
    ll rem=0;
    REP(i,n+1){
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    REP(i,n)scanf("%lld",&b[i]);
    for(int i=n-1;i>=0;i--){
        if(a[i+1]>=b[i]){
            a[i+1]-=b[i];
            rem+=a[i+1];
        }
        else{
            if(a[i+1]>=0)b[i]-=a[i+1];
            a[i]-=b[i];
        }
    }
    if(a[0]>0)rem+=a[0];
    printf("%lld\n",sum-rem);
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char inp;
  cin>>inp;
  if(inp>='A'&&inp<='Z')
    cout<<'A';
  if(inp>='a'&&inp<='z')
    cout<<'a';
    cout<<endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <map>
using namespace std;
int main() {
	long long int ans = 0;
	long long int n;
	vector<long long int> a(4),min(2);
	cin >> a[0] >> a[1] >> a[2] >> a[3] >> n;
	a[0] *= 8;
	a[1] *= 4;
	a[2] *= 2;
	min[0] = a[0];
	min[1] = a[0];
	for (int i = 1; i < 4;i++) {
		if (min[0] > a[i]) {
			min[0] = a[i];
		}
		if (min[1] > a[i] && i < 3 ) {
			min[1] = a[i];
		}
	}
	min[1] /= 2;
	if (n > 2) {
		ans = (n / 2)*min[0];
	}
	if (n%2==1) {
		ans += min[1];
	}

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



Measured memory_bytes: 256
from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

N, K, L = map(int, input().split())

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    p, q = map(int, input().split())
    road.unite(p-1, q-1)

for j in range(L):
    r, s = map(int, input().split())
    train.unite(r-1, s-1)

pair = [(road.find(i), train.find(i)) for i in range(N)]
# print(pair)
c = Counter(pair)
# print(c)
ans = [c[i] for i in pair]
# print(ans)
print(*ans)


Measured memory_bytes: 163620
#include<iostream>

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

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

int main() {
	string S;
	cin >> S;
	int Max = 0, acgt = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') {
			acgt++;
			Max = max(Max, acgt);
		}
		else acgt = 0;
	}
	cout << Max;
}

Measured memory_bytes: 256
#include<cstdio>
int main(){
    char s[101];
    scanf("%s",s);
    int tmpk,k,mink=10000;
    for(char c='a';c<='z';c++){
        tmpk=0;
        k=0;
        for(int i=0;s[i]!='\0';i++){
            if(s[i]!=c)tmpk++;
            else tmpk=0;
            if(tmpk>k)k=tmpk;
        }
        if(mink>k)mink=k;
    }
    printf("%d",mink);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr lint mod = 1e9 + 7;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }
inline lint invm(lint a, lint p = mod) { a %= p; return a == 1 ? 1 : -p / a * invm(p % a) % p; }
inline lint powm(lint a, lint n, lint p = mod) { return !n ? 1 : powm(a * a % p, n >> 1, p) * (n & 1 ? a : 1) % p; }

V<lint> fact, ifact;
void init_table(int n) {
  fact.assign(n + 1, 1), ifact.assign(n + 1, 1);
  for (int i = 2; i < n + 1; ++i) fact[i] = i * fact[i - 1] % mod;
  ifact[n] = invm(fact[n]);
  for (int i = n; i > 2; --i) ifact[i - 1] = i * ifact[i] % mod;
}

lint comb(lint n, lint r) {
  if (r < 0 or r > n) return 0;
  return fact[n] * ifact[r] % mod * ifact[n - r] % mod;
}

lint mulcomb(lint n, lint r) {
  if (n < 1 or r < 0) return 0;
  return fact[r + n - 1] * ifact[r] % mod * ifact[n - 1] % mod;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  lint n, k; cin >> n >> k;
  if (n < k) return cout << 0 << '\n', 0;
  init_table(n + k);
  lint res = 0;
  for (lint i = 0; i < k + 1; ++i) (res += (k - i & 1 ? -1 : 1) * comb(k, i) * powm(i, n) % mod) %= mod;
  cout << emod(res * ifact[k]) << '\n';
}


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

int main(){
    string x;cin>>x;
    int i=0;
    int k=x.size();
    while(i<k){
      if(i>=0&&i<k-1){
        if(x.substr(i,2)=="ST"){
            x.replace(i,2,"");
            i=i-2;
            k=x.size();
            }
    }
    i++;
    }
    cout<<x.size()<<endl;
}

Measured memory_bytes: 640
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	long[] p10 = new long[19];

	void run() {
		p10[0] = 1;
		for (int i = 1; i < p10.length; ++i) {
			p10[i] = p10[i - 1] * 10;
		}
		Scanner sc = new Scanner(System.in);
		System.out.println(calc(sc.nextLong()));
	}

	long calc(long d) {
		long ans = 0;
		for (int i = 1; i <= 19; ++i) {
			ans += solve(d, i);
		}
		return ans;
	}

	long solve(long d, int len) {
		long comb = 1;
		boolean f = true;

		while (len > 0) {
			long x = -999999;
			boolean update = false;
			if (len != 1) {
				for (long i = -9; i <= 9; ++i) {
					if (d % 10 == i * (p10[len - 1] - 1) % 10
							&& Math.abs(d - i * (p10[len - 1] - 1)) <= p10[len - 1] - 1) {
						x = i;
						if (update)
							throw new AssertionError();
						update = true;
					}
				}
			} else {
				if (d == 0) {
					return comb * (f ? 9 : 10);
				} else {
					return 0;
				}
			}
			if (!update) {
				return 0;
			}
			d -= x * (p10[len - 1] - 1);
			long cnt = 0;
			for (int i = 0; i <= 9; ++i) {
				if (f && i == 0)
					continue;
				if (i + x >= 0 && i + x <= 9) {
					++cnt;
				}
			}
			comb *= cnt;
			f = false;
			len -= 2;
			if (d % 10 != 0) {
				throw new AssertionError();
			}
			if (len > 1) {
				d /= 10;
			}
		}
		if (d != 0) {
			return 0;
		} else {
			return comb;
		}
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}

Measured memory_bytes: 23764
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

class Main {
	public static void main(String[] args) {
		// long time = System.currentTimeMillis();
		new Main().run();
		// System.err.println(System.currentTimeMillis() - time);
	}

	void run() {
		Scanner sc = new Scanner();
		int n = sc.nextInt();
		long[][] a = new long[n][2];
		for (int i = 0; i < n; ++i) {
			a[i][0] = sc.nextLong();
			a[i][1] = sc.nextLong();
		}
		Arrays.sort(a, new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return Long.compare(o1[0] + o1[1], o2[0] + o2[1]);
			}
		});
		long INF = Long.MAX_VALUE / 3;
		long[] f = new long[n + 1];
		Arrays.fill(f, INF);
		f[0] = 0;

		for (int i = 0; i < n; ++i) {
			for (int j = n - 1; j >= 0; --j) {
				if (f[j] == INF || f[j] > a[i][0])
					continue;
				f[j + 1] = Math.min(f[j + 1], f[j] + a[i][1]);
			}
		}

		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			if (f[i] == INF)
				break;
			ans = i;
		}
		System.out.println(ans);
	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
#define N      510
// #define inf    0x7f7f7f7f
#define int    long long
using namespace std;
int a[N][N] = {};
int read()
{
    int  s = 0, w = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-')
        c = getchar();
    if (c == '-')
        c = getchar(), w = -1;
    while (c <= '9' && c >= '0')
        s = (s << 3) + (s << 1) + c - '0', c = getchar();
    return s * w;
}
int n;
int b[N][N] = {}, c[N][N] = {};
int f[N][N] = {};
signed main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j)
                a[i][j] = read();
    for (int i = 1; i <= n; ++i)
        for (int j = n; j >= i + 1; --j)
        {
            b[i][j] = b[i][j + 1];
            for (int k = 1; k <= i; ++k)
                b[i][j] += a[j][k];
        }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n + 1; ++j)
        {
            c[i][j] = c[i][j - 1];
            for (int k = i; k <= j - 1; ++k)
                c[i][j] += a[k][j];
        }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            if (f[i][j] < 1e18)
                for (int k = j + 1; k <= n + 1; ++k)
                    f[j][k] = min(f[j][k], f[i][j] + c[j + 1][k] + b[j][k + 1] - b[i][k + 1]);
    int minn = 1e18;
    for (int i = 0; i <= n; ++i)
        minn = min(minn, f[i][n + 1]);
    printf("%lld\n", minn);
    return 0;
}


Measured memory_bytes: 8448
A, B, Q = [int(_) for _ in input().split()]
S = [int(input()) for i in range(A)]
T = [int(input()) for i in range(B)]
Q = [int(input()) for i in range(Q)]

import bisect

def calc_nearest_distance(xs, ys):
    result = []
    for x in xs:
        i = bisect.bisect(ys, x)
        if i == 0:
            d = abs(ys[i] - x)
        elif i < len(ys):
            d = min(abs(ys[i - 1] - x), abs(ys[i] - x))
        else:
            d = abs(ys[i - 1] - x)
        result.append(d)
    return result

sn = calc_nearest_distance(S, T)
tn = calc_nearest_distance(T, S)

def solve(q, S, T, sn, tn):
    nsp = bisect.bisect(S, q)
    ntp = bisect.bisect(T, q)

    rs = []

    if 0 <= nsp < len(S):
        rs.append(abs(S[nsp] - q) + sn[nsp])
    if 0 <= nsp - 1 < len(S):
        rs.append(abs(S[nsp - 1] - q) + sn[nsp - 1])

    if 0 <= ntp < len(T):
        rs.append(abs(T[ntp] - q) + tn[ntp])
    if 0 <= ntp - 1 < len(T):
        rs.append(abs(T[ntp - 1] - q) + tn[ntp - 1])

    return min(rs)

for q in Q:
    print(solve(q, S, T, sn, tn))


Measured memory_bytes: 25196
import collections
def func(a,b,c):
    g=0
    l=[a,b,c]
    d=collections.Counter(l)
    x=len(d)
    if x==3:
        g=2
    elif x==2:
        g=1
    return g
N=int(input())
A=input()
B=input()
C=input()
count=0
for i in range(N):
    count+=func(A[i],B[i],C[i])
print(count)


Measured memory_bytes: 3316
def solve():
    N, T, S = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]
    dp = {0: 0}
    
    for fun, time in a:
        for _t, _f in dp.copy().items():
            new_time = _t + time
            new_fun = fun + _f
            if _t < S < new_time:
                new_time = S + time
            if new_time <= T and (new_time not in dp or new_fun > dp[new_time]):
                dp[new_time] = new_fun

    print(max(dp.values()))


if __name__ == "__main__":
    solve()

Measured memory_bytes: 8972