akhauriyash/Code-Regression huggingface dataset:
def solve(string):
    s = string.replace("?", "d").lower()
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    mod = 10**9 + 7
    for i, _s in enumerate(s):
        dp[0][i + 1] = dp[0][i] % mod
        dp[1][i + 1] = dp[1][i] % mod
        dp[2][i + 1] = dp[2][i] % mod
        dp[3][i + 1] = dp[3][i] % mod
        if _s == "d":
            dp[0][i + 1] *= 3
            dp[1][i + 1] *= 3
            dp[2][i + 1] *= 3
            dp[3][i + 1] *= 3
        if _s in ["a", "d"]:
            dp[1][i + 1] += dp[0][i]
        if _s in ["b", "d"]:
            dp[2][i + 1] += dp[1][i]
        if _s in ["c", "d"]:
            dp[3][i + 1] += dp[2][i]
    return str(int(dp[3][-1] % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 21332
mod = 10**9+7
n, m = map(int, input().split())
l = [0]*n
for _ in range(m):
  l[int(input())-1] = 1

s = 0
t = 1

for i in range(n):
  if l[i] > 0:
    t, s = 0, t
  else:
    t, s = (s+t)%mod, t

print(t)

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

int32_t main(){
    boost;

    
    //code

    int n , m , a ,b;
    cin >> n >> m;
    int g[n+1] = {0};
    for(int i = 0 ; i < n ; ++i){
    	cin >> a >> b;
    	if(a > b) swap(a,b);
    	g[a]++;
    	g[b+1]--;
    }

    int cnt = 0;
    for(int i = 1 ; i <= n ; ++i){
    	g[i] += g[i-1];

    	if(g[i] == n)
    		cnt++;

    	// cout << g[i] << " ";
    }

    cout << cnt;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <stdlib.h>
#include <map>
using namespace std;

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

	bool flag = true;
	int ccnt = 0;

	if (S[0] != 'A') {
		flag = false;
	}
	if ('A' <= S[1] && S[1] <= 'Z') {
		flag = false;
	}
	if ('A' <= S[S.length() -1] && S[S.length() - 1] <= 'Z') {
		flag = false;
	}

	if (flag) {
		for (int i = 2; i < S.length() - 1; i++)
		{
			if (S[i] == 'C') {
				ccnt++;
			}
		}
	}
	if (ccnt != 1) {
		flag = false;
	}

	if(flag){
		cout << "AC" << endl;
	}
	else {
		cout << "WA" << endl;
	}
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
using ll = long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

  
bool cmp(const pair<string, pair<int, int> >& s1, const pair<string, pair<int, int> >& s2){
  return (s1.first.compare(s2.first)) < 0 || (s1.first.compare(s2.first)==0 && s1.second.first > s2.second.first);
}


int main () {
  int n;
  cin >> n;
  vector<pair<string, pair<int, int> > > store(n);
  REP(i, n){
    cin >> store[i].first >> store[i].second.first;
    store[i].second.second = i+1;
  }
  sort(store.begin(), store.end(), cmp);
  REP(i, n){
    cout << store[i].second.second << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
typedef long long ll;
const int m=1e9+7;
int main()
{
	ll n,ans;
	scanf("%d",&n);
	ans=1;;
	for(int i=1;i<=n;i++)
	{
		ans=ans*i%m;
		}	
	printf("%lld\n",ans);
	return 0;
 } 

Measured memory_bytes: 128
// 3 - Dpによる解法　O(N^2)

#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;

// ???
int main(){
    int n;
    string s;
    cin >> n >> s;

    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int i = 1; i < n; i++){
        if(s[0] == s[i])    dp[0][i] = 1;
    }

    for(int i = 1; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(s[i] != s[j])    continue;
            if(i < j-dp[i-1][j-1])  dp[i][j] = dp[i-1][j-1]+1;
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 98176
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
one_or_two = [0] + [1] + [2] + [-1] * n
for i in range(3, n + 3):
    one_or_two[i] = (one_or_two[i-1] + one_or_two[i-2]) % mod
if m == 0:
    print(one_or_two[n])
    exit()
ans = 1
if a[0] > 1:
    ans *= one_or_two[a[0]-1]
for i in range(1, m):
    if a[i] - a[i-1] == 2:
        continue
    if a[i] - a[i-1] == 1:
        ans = 0
        break
    ans *= one_or_two[a[i] - a[i-1] - 2]
    ans %= mod
if n - a[-1] > 1:
    ans *= one_or_two[n - a[-1] - 1]
print(ans % mod)

Measured memory_bytes: 16720
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int a[100001],b[100001],c[100001],dp[100001];

inline int read ( ) {
	int x = 0 , w = 1 ; char c = '-' ;
	
	while ( c < '0' || c > '9' ) { c = getchar ( ) ; if ( c == '-' ) w = -1 ; }
	while ( c >= '0' && c <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ( c ^ '0' ) , c = getchar ( ) ; }
	
	return x * w ;
}

int main()
{
	int n;
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++) c[i]=read();
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	sort(c+1,c+n+1);
	int ax=0;
	long long ans=0;
	for(int i=1;i<=n;i++){
		while(ax<n&&a[ax+1]<b[i]) ax++;
		dp[i]=ax;
	}
	int bx=0;
	long long ans2=0;
	for(int i=1;i<=n;i++){
		while(bx<n&&b[bx+1]<c[i]) bx++,ans2+=(long long)dp[bx];
		ans+=ans2;
	}
	printf("%lld",ans);
}


Measured memory_bytes: 2424
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
    FI(); /// skip this line for compile
    int n,k,x,y;
    cin >> n >> k >> x >> y;
    if(n<k) cout << n*x << endl;
    else{
        cout << x*k+(n-k)*y << endl;
    }
    return 0;
}



Measured memory_bytes: 3668
#include<iostream>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<string>
using namespace std;
int main(void){
   
    int a,b;
    cin>>a;
    string c;
    cin>>c;
    if(c=="+"){
        cin>>b;
        cout<<a+b<<endl;
    }else{
        cin>>b;
        cout<<a-b<<endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long int dp[3000][3000][2];
int main() {
	long long int n,s=0;
	cin>>n;
	long long int a[n],i;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	for(i=0;i<n;i++)
	{
		dp[i][i][0]=a[i];
		dp[i][i][1]=0;
	}
	for(long long int rminusl=1;rminusl<n;rminusl++)
	{
		for(long long int l=0;l<n-rminusl;l++)
		{
			long long int r=l+rminusl;
			dp[l][r][0]=max(a[l]+dp[l+1][r][1],a[r]+dp[l][r-1][1]);
			dp[l][r][1]=min(dp[l+1][r][0],dp[l][r-1][0]);
		}
	}
	long long int x=2*dp[0][n-1][0]-s;
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 85372
import java.util.Scanner;

public class Main {
	
	static boolean[] prime=new boolean[1000000];
	static void primes(int x) {
		for(int i=2; x*i<1000000; i++) {
			prime[x*i]=false;
		}
	}
	
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
                for(int i=2; i<1000000; i++) {
                	prime[i]=true;
                }
                for(int i=2; i<1000000; i++) {
                	if(prime[i]) {
                		primes(i);
                	}
                }
                prime[0]=prime[1]=false;
                
                while(sc.hasNext()) {
                	int a=sc.nextInt();
                	int d=sc.nextInt();
                	int n=sc.nextInt();
                	if(a+d+n==0) break;
                	int count=0;
                	int ans=0;
                	for(int i=0; i<1000000; i++) {
                		if(prime[a+d*i]) {
                			count++;
                		}
                		if(count==n) {
                			ans=a+d*i;
                			break;
                		}
                	}
                	System.out.println(ans);
                	
                }
                
        }
    }
}


Measured memory_bytes: 31456
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n,m := scanInt(), scanInt()
	a := scanInts(n)

	val := a[0]/2
	for i := 1; i < n; i++ {
		e := euclidean(val,a[i]/2)
		val = val*(a[i]/2)/e
	}

	val2 := a[0]
	for i := 1; i < n; i++ {
		e := euclidean(val2,a[i])
		val2 = val2*a[i]/e
	}

	for i := 0; i < n; i++ {
		if val%a[i]==0 {
			fmt.Println(0)
			return
		}
	}

	fmt.Println(m/val-m/val2)
}

func euclidean(a,b int) int {
	r, x := a%b, b
	for r != 0 {
		x, r = r, x%r
	}
	return x
}


Measured memory_bytes: 3072
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    ll x;
    cin >> x;
    ll ans = (x/11)*2; // 2回で11
    x %= 11;
    if (x > 6) {
        ans += 2;
    } else if (x > 0) {
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val lst = readLine()!!.split(" ").map(String::toInt)

    if(lst[0] + lst[1] < lst[2] + lst[3]) println("Right")
    else if(lst[0] + lst[1] == lst[2] + lst[3]) println("Balanced")
    else println("Left")
}

Measured memory_bytes: 37784
import sys
if __name__ == "__main__":
    N = int(input())
    evidences = list(map(int, input().split()))
    evidences = list(sorted(evidences))
    unique_evidence = set(evidences)
    if (evidences[-1] - evidences[0] > 1):
        print ("No")
        sys.exit()
    if (len(unique_evidence) == 1):
        group = evidences[0];
        # all unique
        if (group == N - 1):
            print ("Yes")
            sys.exit()
        if (N - 2 * group < 0):
            print ("No")
            sys.exit()
        print ("Yes")
        sys.exit()
    # evidences[-1] - evidences[0] > 1
    min_val = min(evidences)
    max_val = max(evidences)

    min_val_cnt = 0
    max_val_cnt = 0
    for val in evidences:
        if (val == min_val):
            min_val_cnt += 1
        else:
            max_val_cnt += 1
    # violate not unique
    if (max_val_cnt <= 1):
        print ("No")
        sys.exit()
    #rest cat
    rest = N
    rest -= min_val_cnt

    min_group = min_val_cnt + 1
    max_group = min_val_cnt + (max_val_cnt // 2)
    if min_group <= evidences[-1] and evidences[-1] <= max_group:
        print ("Yes")
        sys.exit()
    print ("No")


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

/* 考察メモ
1の個数が最大になったら，それ以外をずっと取り除くのが最善
一番後ろにある大きな数を取り除く貪欲法で問題ない

max(t, 0)の総和
 */
int N;
vector<int64_t> a;
struct BIT{
  vector<int64_t> bit;int64_t size;
  BIT(int64_t n){
    size=n;bit=vector<int64_t>(n+1);
  }
  //a[i]=x
  void add(int64_t i,int64_t x){
    i+=1;
    while(i<=size)bit[i]+=x,i+=i&-i;
  }

  int64_t get(int64_t i) {
    return sum(i + 1) - sum(i);
  }
  //a[k] (k<i)の和
  int64_t sum(int64_t i){
    int64_t s=0;
    while(i>0)s+=bit[i],i-=i&-i;
    return s;
  }
};

int main() {
  cin >> N;
  a.resize(N);
  for(auto &num: a)cin >> num;
  vector<int64_t> ca(a);
  sort(ca.begin(), ca.end());
  ca.erase(unique(ca.begin(), ca.end()), ca.end());
  unordered_map<int64_t, int64_t> compress;
  for(size_t i = 0; i < ca.size(); i++) {
    compress[ca[i]] = i;
  }
  BIT bit(ca.size() + 1);
  BIT cnt(ca.size() + 1);
  for(size_t i = 0; i < a.size(); i++) {
    bit.add(compress[a[i]], a[i]);
    cnt.add(compress[a[i]], 1);
  }
  int64_t last = 0;
  int64_t diff = 0;
  for(size_t i = 0; i < a.size(); i++) {
    // a[i]以下の和
    int64_t target = a[i] - diff;
    if(target < 0) {
      cout << 0 << endl;
      continue;
    }
    diff += target;
    target = diff;
    int64_t target_ofs = lower_bound(ca.begin(), ca.end(), target) - ca.begin();
    int64_t sum = bit.sum(target_ofs);
    int64_t sum2 = cnt.sum(ca.size() + 1) - cnt.sum(target_ofs);
    int64_t cur = sum +  sum2 * target;
    cout << cur - last << endl;
    last = cur;
  }
  return 0;
}

Measured memory_bytes: 8356
#include<bits/stdc++.h>
using namespace std ;
int main()
{
    int score1[4] = {0} ;
    int score2[2] = {0} ;

    for ( int i = 0 ; i < 4 ; i++ )
    {
        cin >> score1[i] ;
    }
    for ( int i = 0 ; i < 2 ; i++ )
    {
        cin >> score2[i] ;
    }

    sort( score1 , score1+4 ) ;
    reverse( score1 , score1+4 ) ;
    cout << score1[0] + score1[1] + score1[2] + max( score2[0],score2[1] ) << endl ;

    return 0 ;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef complex<double> xy_t;
const lint mod = 1e9 + 7;

const int MAX = 5010;
const lint INF = mod * mod;
int n;
lint a[MAX];
vector<int> G[MAX];
lint dp[MAX][MAX][2], dp2[MAX][2];
int ch_num[MAX];

void dfs(int v, int prev){
    for(int nv: G[v])if(nv != prev) dfs(nv, v);
    int ch_tmp = 1;
    dp[v][0][a[v] < 0] = a[v];
    for(int nv: G[v])if(nv != prev){
        rep(j, ch_tmp)rep(cj, ch_num[nv])rep(k, 2)rep(ck, 2){
            dp2[j+cj][k|ck] = min(dp2[j+cj][k|ck], dp[v][j][k] + dp[nv][cj][ck]);
            if((!ck && dp[nv][cj][ck] < INF) || dp[nv][cj][ck] < 0){
                dp2[j+cj+1][k] = min(dp2[j+cj+1][k], dp[v][j][k]);
            }
        }
        ch_tmp += ch_num[nv];
        rep(j, ch_tmp)rep(k, 2){
            dp[v][j][k] = dp2[j][k];
            dp2[j][k] = INF;
        }
    }
    ch_num[v] = ch_tmp;
}

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%lld", &a[i]);
    rep(i, n-1){
        int u, v;
        scanf("%d%d", &u, &v);
        G[--u].push_back(--v);
        G[v].push_back(u);
    }
    rep(i, n)rep(k, 2){
        rep(j, n) dp[i][j][k] = INF;
        dp2[i][k] = INF;
    }
    dfs(0, -1);
    int ans = n;
    rep(i, n){
        if(dp[0][i][0] < INF) ans = min(ans ,i);
        if(dp[0][i][1] < 0) ans = min(ans, i);
    }
    printf("%d\n", ans);
}

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

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

int n;

int main() {
  cin >> n;
  vector<vector<int>> cur;
  cur.resize(1);
  if(n & 1) {
    range(i, 1, n) {
      if(i > n - i) break;
      cur.back().push_back(i);
      cur.back().push_back(n - i);
      cur.resize(cur.size() + 1);
    }
    cur.back().push_back(n);
  } else {
    cur.clear();
    range(i, 1, n) {
      if(i > n + 1 - i) break;
      cur.resize(cur.size() + 1);
      cur.back().push_back(i);
      cur.back().push_back(n + 1 - i);
    }
  }
  int sz = cur.size();
  vector<pair<int, int>> res;
  range(i, 0, sz) {
    range(j, 0, i) {
      for(int u : cur[i]) {
        for(int v : cur[j]) {
          res.emplace_back(u, v);
        }
      }
    }
  }
  cout << res.size() << endl;
  for(auto s : res) cout << s.first << " " << s.second << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(void){
    // Here your code !
    int n,k;
    cin >> n >> k;
    vector<int> d(10,0);
    for(int i = 0; i < k; i++){
        int t;
        cin >> t;
        d[t] = 1;
    }
    
    for(int i = n; i < 1000000; i++){
        string s = to_string(i);
        int j;
        for(j = 0; j < s.length(); j++){
            if(d[s[j]-'0']){
                break;
            }
        }
        if(j == s.length()){
        cout << i << endl;
        break;
        }
    }
}


Measured memory_bytes: 888
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

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

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<ll> > d(n, vector<ll>(n, INF));
    forn(i, n) d[i][i] = 0;
    forn(i, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    vector<vector<ll> > e = d;
    forn(k, n)
    {
        forn(i, n)
        {
            forn(j, n)
            {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int ans = 0;
    forn(i, n)
    {
        forn(j, n)
        {
            if (i < j && e[i][j] != INF)
            {
                if (d[i][j] < e[i][j]) ans++;
            }
        }
    }
    cout << ans;
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


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

const int inf = 1e9;
const ll linf = 1e18;

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

    int n; cin >> n;
    ll lucas[n + 1];
    lucas[0] = 2, lucas[1] = 1;
    for (int i = 2; i <= n; i++) {
        lucas[i] = lucas[i-1] + lucas[i-2];
    }
    cout << lucas[n] << endl;
    return 0;
}

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


int main() {
    double r;
    cin >> r;
    long double area = r * r * M_PI;
    long double circle = 2.0 * r * M_PI;
    cout << fixed << setprecision(6) << area << " " << circle << endl;
    return 0;
}


Measured memory_bytes: 3276
#include<stdio.h>
#include<math.h>

int main(void)
{
	int a,b,n;
	scanf("%d%d",&a,&b);
	if(b==100)
		n=a*1000+b;
	else if(b>=10)
		n=a*100+b;
	else
		n=a*10+b;
	if(sqrt(n)==(int)sqrt(n))
		printf("Yes");
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 128
from collections import *
n=int(input())
a=list(map(int,input().split()))
b=set(a)
d=defaultdict(int)
mx=0
for i in a:
  d[i]+=1
for i in b:
  mx=max(mx,d[i-1]+d[i]+d[i+1])
print(mx)


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

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


Measured memory_bytes: 4836
n = int(input())
s = input()
c = [0]
for i in range(n):
    if s[i] == '(':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1] - 1)
print(max(0, -min(c)) * '(' + s + max(0, c[-1] - min(c)) * ')')


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

#define ll long long
#define mod 1000000007
#define pll pair<long long,long long>
#define pdd pair<long double,long double>
#define vll vector<ll>
#define rep(i,j,n) for(int i=j;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define inf 1e17
#define N 100010
priority_queue<pll,vector<pll>,greater<pll> >pq;
priority_queue<ll,vector<ll>,greater<ll> >pq1;

ll result(ll a, ll b, ll p){
    ll ans=1;
    if(b==(-1))
        b=p-2;
    while(b){
        if(b&1){
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

ll T,n,m;

int main(){
    if(fopen("input.txt", "r"))
    freopen("input.txt", "r", stdin),
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll k;
    cin >> n >> k;
    ll a[n+1];
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    ll d = 1;
    vector<ll>par(n+1, -1), lev(n+1,0);
    par[1] = 0;
    lev[1] = 0;
    
    while(1){
        if(par[a[d]] != -1)
            break;
        par[a[d]] = d;
        lev[a[d]] = lev[d] + 1;
        
        d = a[d];
    }
    ll last = d;
    par[a[d]] = last;
    ll rec = a[d];
    d = 1;
    while(1){
        if(d == rec)
            break;
        d = a[d];
        k--;
        if(k==0)
            break;
    }
    if(k==0){
        cout << d;
        return 0;;
    }
    else{
        ll p = lev[last] - lev[rec] + 1;
        k%=p;
        while(k--){
            d = a[d];
        }
        cout << d;
    }
    
}


Measured memory_bytes: 7956
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    if n == 1:
        print('Yes')
        sys.exit()
    for i in range(2, 10):
        if n % i ==0:
            if n / i < 10:
                print('Yes')
                sys.exit()

    print('No')

if  __name__=='__main__':
    main()


Measured memory_bytes: 5192
#include <stdio.h>
int n, m, i, j, k, ans;
int main(){
	scanf("%d%d", &n, &m);
	for(i=1; i<=m/i; i++){
		if(m%i == 0){
			if(i>k && m/i>=n) k = i;
			if(m/i>k && i>=n) k = m/i;
			if(k > ans) ans = k;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w, m = map(int, readline().split())
    row = [0] * h
    col = [0] * w
    target = [[] for _ in range(h)]

    for _ in range(m):
        ch, cw = map(int, readline().split())
        ch, cw = ch - 1, cw - 1
        row[ch] += 1
        col[cw] += 1
        target[ch].append(cw)

    ans = 0
    c_max = max(col)
    max_cnt = col.count(c_max)

    for r in range(h):
        cnt_r = row[r]
        cnt_c = c_max
        rem = max_cnt
        for c in target[r]:
            if col[c] == c_max:
                rem -= 1
        if rem > 0:
            ans = max(ans, cnt_r + cnt_c)
        else:
            ans = max(ans, cnt_r + cnt_c - 1)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 112488
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str=sc.next();
        int output=0;
        for(int i=0;i<str.length();i++){
            for(int j=i+1;j<str.length()+1;j++){
                if(str.substring(i,j).replaceAll("A", "").replaceAll("C","").replaceAll("G", "").replaceAll("T","").length()==0){
                    if(output<j-i){
                        output=j-i;
                    }
                }
            }
        }
        System.out.println(output);
    }
}

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

struct node {
  int key;
  struct node *parent, *left, *right;
};

struct node *tree, *z;

void insert(struct node *T, struct node *z);
void inorder(struct node *p);
void preorder(struct node *p);

int main(int argc, char*argv[])
{
  int m, i;
  char cmd[6 + 1];

  tree = NULL;

  scanf("%d", &m);

  for (i = 0; i < m; i++) {
    scanf("%s", cmd);

    if (!strcmp(cmd, "insert")) {
      z = (struct node *)malloc(sizeof(struct node));
      scanf("%d", &(z->key));
      z->parent = NULL;
      z->left = NULL;
      z->right = NULL;
      insert(tree, z);
    } else if (!strcmp(cmd, "print")) {
      inorder(tree);
      printf("\n");
      preorder(tree);
      printf("\n");
    }
  }

  return 0;
}

void insert(struct node *T, struct node *z)
{
  struct node *x, *y;

  y = NULL;
  x = tree;
  while (x != NULL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;

  if (y == NULL) tree = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;
}

void inorder(struct node *p)
{
  if (p->left != NULL) inorder(p->left);
  printf(" %d", p->key);
  if (p->right != NULL) inorder(p->right);
}

void preorder(struct node *p)
{
  printf(" %d", p->key);
  if (p->left != NULL) preorder(p->left);
  if (p->right != NULL) preorder(p->right);
}

Measured memory_bytes: 24040
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
int main(){
   int a,b;
   cin >> a>> b;
   char c[105];
   rep(i,a){
     scanf("%s",c);
     printf("%s\n%s\n",c,c);
   }

   return 0;
  }

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
)

func main() {
	sc.Split(bufio.ScanWords)
	if nextInt()*nextInt()%2 == 1 {
		fmt.Println("Odd")
	} else {
		fmt.Println("Even")
	}
}

func nextInt() int {
	i, err := strconv.Atoi(nextWord())
	pnc(err)
	return i
}

func nextWord() string {
	sc.Scan()
	return sc.Text()
}

func pnc(err error) {
	if err != nil {
		panic(err)
	}
}


Measured memory_bytes: 1772
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] nm = scanner.nextLine().split(" ", 2);
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        boolean[] like = new boolean[m+1];
        Arrays.fill(like, true);

        for (int i = 0; i < n; i++) {
            String[] line = scanner.nextLine().split(" ", -1);
            int k = Integer.parseInt(line[0]);

            boolean[] lineLike = new boolean[m+1];
            for (int j = 1; j <= k; j++) {
                int a = Integer.parseInt(line[j]);
                lineLike[a] = true;
            }
            for (int j = 1; j <= m; j++) {
                if (!lineLike[j]) {
                    like[j] = false;
                }
            }
        }

        int num = 0;
        for (int i = 1; i <= m; i++) {
            if (like[i]) {
                num++;
            }
        }
        System.out.println(num);
    }
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll S[105];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    memset(S, 0, sizeof(S));
    vector<pll> e;
    REP(i, N - 1) {
        e.push_back(pll(1, i + 2));
    }
    K -= (N - 2) * (N - 1) / 2;
    if (K > 0) {
        cout << -1 << endl;
        return 0;
    }
    ll left = 2;
    ll right = 3;
    while (K++ < 0) {
        e.push_back(pll(left, right++));
        if (right > N) {
            left++;
            right = left + 1;
        }
    }

    cout << e.size() << endl;
    REP(i, e.size()) {
        cout << e[i].first << " " << e[i].second << endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
	double dept;
	int i;
	
	dept = 100000;
	scanf("%d", &i);
	
	for (; i > 0; i--) {
		dept *= 1.05;
		dept += 999;
		dept = (int)(dept / 1000);
		dept *= 1000;
	}
	
	printf("%.0lf\n", dept);

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int dp[3001][3001];

int main(void){
	string str1, str2;
	cin >> str1 >> str2;

	for(int i=1; i<=str1.length(); i++){
		for(int j=1; j<=str2.length(); j++){
			if(str1[i-1] == str2[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
			} else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	//cout << dp[str1.length()][str2.length()] << endl;

	//復元操作
	string res = "";
	int i = (int)str1.size(), j = (int)str2.size();
	while(i > 0 && j > 0){
		if(dp[i][j] == dp[i-1][j]) {
			--i;
		}else if(dp[i][j] == dp[i][j-1]) {
			--j;
		}else {
			res = str1[i-1] + res;
			--i, --j;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 35456
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
#define m 1000000007
#define MAXN 1000001
#define satya ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cil(a,b) (((a-1)/b)+1)
//#define init int t;cin>>t;while(t--)
#define in(a) ll a;scanf("%lld",&a)
#define ine(a,b) ll a,b;scanf("%lld lld",&a,&b)



ll spf[MAXN]; 

void sieve1() 
{ 
	spf[1] = 1; 
	for (int i=2; i<MAXN; i++) 

		spf[i] = i; 

	for (int i=4; i<MAXN; i+=2) 
		spf[i] = 2; 

	for (int i=3; i*i<MAXN; i++) 
	{ 
		if (spf[i] == i) 
		{ 
			for (int j=i*i; j<MAXN; j+=i) 

				if (spf[j]==j) 
					spf[j] = i; 
		} 
	} 
} 

ll  getFactorization(int x) 
{ 
	vector<int> ret; 
	long long int p=0;
	while (x != 1) 
	{ 
		ret.push_back(spf[x]); 
		x = x / spf[x]; 
	} 
	sort(ret.begin(),ret.end());
	for(int i=0;i<ret.size()-1;i++) 
	{
	    if(ret[i]!=ret[i+1])
	    p=p+ret[i];
	}
	p=p+ret[ret.size()-1];
	return p;
} 

ll d[1000055],u=0;
void Sieve(int n) 
{ 
	bool prime[n+1]; 
//	ll u=0;
	memset(prime, true, sizeof(prime)); 

	for (int p=2; p*p<=n; p++) 
	{ 
		if (prime[p] == true) 
		{ 
			for (int i=p*2; i<=n; i += p) 
				prime[i] = false; 
		} 
	} 

	for (int p=2; p<=n; p++) 
	if (prime[p]) 
	{
	    d[u]=p;
	    u++;
	}
} 

ll minverse(ll x,ll n,ll M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return minverse((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*minverse((x*x)%M,(n-1)/2,M))%M;

}
ll prime(ll n){
    ll i;
    if(n==1||n==0)
    return 0;
    for(i=2;i<sqrt(n);i++)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}
int main() {
       satya;
     //sieve1(); 
     //Sieve(100);
    	   
ll n,k;
cin>>n>>k;
if(k==1)
cout<<0<<endl;
else
{
    cout<<n-k<<endl;
}
    return 0;
}

Measured memory_bytes: 256
N=int(input())
X=list(map(int,input().split()))

Xsorted=sorted(X)

ans1=Xsorted[(N-1)//2]
ans2=Xsorted[(N-1)//2+1]

for i in range(N):
    if X[i]<=ans1:
        print(ans2)
    else:
        print(ans1)



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

int main(){
    int N;
    while(cin>>N,N){
        int ans=0;
        for(int i=1;i<N;i++){
            int sum=0;
            for(int j=i;sum<N;j++)sum+=j;
            if(sum==N)ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
using System;
using System.IO;

class Solve
{
    static void Main(string[] args) {
        var arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int A = arr[0], B = arr[1];
        var S = Console.ReadLine();
        var x = int.TryParse(S.AsSpan(0, A), out _) && int.TryParse(S.AsSpan(A + 1, B), out _);
        var y = S[A] == '-';
        var z = S.Length == A + B + 1;
        var answer = x && y && z ? "Yes" : "No";
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();
    }
}

Measured memory_bytes: 27704
#include<bits/stdc++.h>
using namespace std;
int main(){
	map<char,char> temp;
	temp['A']='a';temp['B']='b';temp['C']='c';
	int N,K;string S;cin>>N>>K>>S;
	for(int i=0;i<N;i++){
        if(i==K-1){
            cout<<temp[S.at(K-1)];
        }else{
            cout<<S.at(i);
        }
    }cout<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int k,n;
    cin>>k>>n;
    int a[n],d[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    d[0]=k-a[n-1]+a[0];
    for(int i=1;i<n;i++){
        d[i]=a[i]-a[i-1];
    }
    sort(d,d+n);
    cout<<k-d[n-1];
}


Measured memory_bytes: 1792
a = int(input())

l = [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
     ]

print(l[a - 1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h, w;
    cin >> h >> w;
    vector<vector<int>> vf(h+1, vector<int>(w+1));
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            cin >> vf[i][j];
        }
    }

    int count = 0;
    vector<string> ans;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w-1; j++)
        {
            if(vf[i][j] % 2 == 1)
            {
                count++;
                vf[i][j+1]++;
                stringstream ss;
                ss << i << " " << j << " " << i << " " << j+1;
                ans.push_back(ss.str());
            }
        }
    }
    for(int i = 1; i <= h-1; i++)
    {
        if(vf[i][w] % 2 == 1)
        {
            count++;
            vf[i+1][w]++;
            stringstream ss;
            ss << i << " " << w << " " << i+1 << " " << w;
            ans.push_back(ss.str());
        }
    }
    cout << count << endl;
    for(int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << endl;
    }
}



Measured memory_bytes: 9972
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int n;
 cin>>n;
int count=0;
 for(int i=1;i<=n;i++)
 {
  int element;
  cin>>element;
  if(i&1 && element&1)
  {
    count++;
  }
 }
 cout<<count<<endl;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = ~(1<<31);
const int MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main(){
	int a,b;
	cin >> a >> b;
	int x = 1,ans = 0;
	while(x < b){
		x += a-1;
		ans++;
	}
	cout << ans << endl;

	return 0;
}

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

class Shop {
public:
  long price;
  int number;
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<Shop> shops(n);
  
  for (size_t i = 0; i < n; i++) {
    cin >> shops[i].price >> shops[i].number;
  }
  
  sort(shops.begin(), shops.end(), [](const Shop& x, const Shop& y) { return x.price < y.price;});

  long cost = 0;

  for (size_t i = 0; i < n; i++) {
    if (shops[i].number > m) {
      cost += m * shops[i].price;
      break;
    } else {
      cost += shops[i].number * shops[i].price;
      m -= shops[i].number;
    }
  }
  cout << cost << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
  int sum = 0, a;
  for (int i = 0; i < 3; i++){
    cin >> a;
  	sum += a;
  }
 
  sum >= 22 ? cout << "bust\n" : cout << "win\n";
  
  return 0;
}

Measured memory_bytes: 256
//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu) FUNC(printe) FUNC(printe0);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

struct Node{
	char chr;
	Node* par = nullptr;
	map<char, pair<int, Node*>> dests;
    int nums[27] = {};
    bool leaf = false;
	Node(){ }
	Node(Node* n):Node() { par = n; }
	Node* make(string& str, vector<int>& azs, int idx = 0){
		chr = str[idx];
        azs[chr - 'a']--;
        for(int i = 0; i < 27; i++){
            nums[i] += azs[i] > 0;
        }
        printde(chr, nums);
		if((int)str.size() == idx + 1){ leaf = true; return this; }
		char next = str[idx + 1];
		if(dests.count(next)){
			dests[next].first++;
		}else{
			Node* n = new Node(this);
			dests[next] = {1, n};
		}
		return dests[next].second -> make(str, azs, idx + 1);
	}

	ll calc(){
        ll ret = 0;
        printde(chr, dests.size());
        if(leaf){
            // par->calc2(chr);
            ret = par->nums[chr - 'a'] - 1;
            printde(chr, ret, par->chr, par->nums[chr - 'a']);
            // ret = par->dests[chr].first - 1;
            // printde(chr, ret, par->dests[chr].first);
        }
        for(auto& dest : dests){
            ret += dest.second.second->calc();
        }
        return ret;
    }
};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    Node root;
    vector<int> azs(27);
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        s += 'a' + 26;
        reverse(s.begin(), s.end());
        azs.assign(27, 0);
        for(auto& c : s){
            azs[c - 'a']++;
        }
        root.make(s, azs);
    }
    cout << root.calc() << '\n';
}
/*
a
ba
abc
dabc
eabdc
*/


Measured memory_bytes: 249568
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> S(n);
    rep(i, n) cin >> S[i];
    int q;
    cin >> q;
    vector<int> T(q);
    rep(i, q) cin >> T[i];
    
    int ans = 0;
    rep(i, q) {
        if (binary_search(S.begin(), S.end(), T[i])) ++ans;
    }
    cout << ans << endl;
    return 0;
}



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

using namespace std;

bool check(int num) {
    vector<bool> flags(3, false);
    while (num > 0) {
        int tmp = num % 10;
        switch (tmp) {
            case 3:
                flags[0] = true;
                break;
            case 5:
                flags[1] = true;
                break;
            case 7:
                flags[2] = true;
                break;
        }
        num /= 10;
    }
    if (flags[0] && flags[1] && flags[2]) {
        return true;
    } else
        return false;
}

void make_numbers(long current, int max, int& count) {
    if (current <= max) {
        if (current > 0 && check(current))
            ++count;
        long tmp = current * 10;
        make_numbers(tmp + 3, max, count);
        make_numbers(tmp + 5, max, count);
        make_numbers(tmp + 7, max, count);
    }
}

int main() {
    int n;
    cin >> n;

    int count = 0;
    make_numbers(0, n, count);
    cout << count << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair

int main(){
	char s;
	cin >> s;
	if(isupper(s)){
		cout << 'A' << endl;
	}
	else cout << 'a' << endl;
}


Measured memory_bytes: 3616
"use strict";

function Main(input) {
  let num = Math.floor(input/100);
  let rest = input%100;
  // 5の根拠は余りの最大値
  if(rest <= num * 5){
  	console.log(1);
  }else {
    console.log(0);
  }
  
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 11468
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE RecordWildCards       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import qualified Data.Foldable               as F
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    [a, b, q] <- map read.words <$> getLine :: IO [Int]
    sstsxs <- U.unfoldrN (a + b + q) (B.readInt.B.dropWhile isSpace) <$> B.getContents
    let (ss, tsxs) = U.splitAt a sstsxs
    let (ts, xs) = U.splitAt b tsxs
    putStr.unlines.map show.U.toList $ solve ss ts xs

inf :: Int
inf = 0x3f3f3f3f3f3f3f3f

solve :: U.Vector Int -> U.Vector Int -> U.Vector Int -> U.Vector Int
solve ss ts xs = U.map f xs
  where
    f x = minimum $ s2t x ++ t2s x
    s2t x = do
        !s <- [prevIx x ss, nextIx x ss]
        !t <- [prevIx s ts, nextIx s ts]
        return $! abs (s - x) + abs (t - s)
    t2s x = do
        !t <- [prevIx x ts, nextIx x ts]
        !s <- [prevIx t ss, nextIx t ss]
        return $! abs (t - x) + abs (s - t)

prevIx :: Int -> U.Vector Int -> Int
prevIx x xs
    | x < U.head xs = inf
    | otherwise = U.unsafeIndex xs $ upperBound 0 (U.length xs - 1) (\i -> U.unsafeIndex xs i <= x)

nextIx :: Int -> U.Vector Int -> Int
nextIx x xs
    | U.last xs < x = inf
    | otherwise = U.unsafeIndex xs $ lowerBound 0 (U.length xs - 1) (\i -> x <= U.unsafeIndex xs i)

-------------------------------------------------------------------------------
lowerBound :: (Integral i) => i -> i -> (i -> Bool) -> i
lowerBound low high p = go low high
  where
    go !low !high
        | high <= low = high
        | p mid       = go low       mid
        | otherwise   = go (mid + 1) high
      where
        h = toInteger high
        l = toInteger low
        mid = fromIntegral $ l + div (h - l) 2

upperBound :: (Integral i) => i -> i -> (i -> Bool) -> i
upperBound low high p
    | p high = high
    | otherwise = lowerBound low high (not.p) - 1


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

using namespace std;

const int MX = 100 * 1000 + 7;

bool p[MX];
int s[MX];

int main() {
    for (int i = 2; i < MX; i++) {
        p[i] = true;
    }
    for (int i = 2; i < MX; i++) {
        s[i] = s[i - 1];
        if (i % 2 == 1 && p[i] && p[(i + 1) / 2]) {
            s[i]++;
        }
        if (p[i]) {
            for (int j = i + i; j < MX; j += i) {
                p[j] = false;
            }
        }
    }
    int q;
    cin >> q;
    for (int qq = 0; qq < q; qq++) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
}

Measured memory_bytes: 1152
def solve(n, a_list):
    res = 100000000
    for p in range(101):
        r = sum([(a_list[i] - p) ** 2 for i in range(n)])
        if r < res:
            res = r

    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(2, [1, 4]) == 5
    assert solve(7, [14, 14, 2, 13, 56, 2, 37]) == 2354


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 3064