akhauriyash/Code-Regression huggingface dataset:
# 入力
N, M = map(int, input().split())
K, A = zip(*(
    (int(t[0]), list(map(int, t[1].split())))
    for t in (input().split(maxsplit=1) for _ in range(N))
))

# 素直にカウント
ans = sum(
    all(k in a for a in A)
    for k in range(1, M + 1)
)

# 出力
print(ans)


Measured memory_bytes: 3060
def height(x, y ,h, Cx, Cy):
    return h + abs(x - Cx) + abs(y - Cy)


N = int(input())
lst_xyh = [tuple(map(int, input().split())) for _ in range(N)]
for Cx in range(101):
    for Cy in range(101):
        for x, y, h in lst_xyh:
            if h != 0:
                H = height(x, y, h, Cx, Cy)
                break
        for x, y, h in lst_xyh:
            if max(H - abs(x - Cx) - abs(y - Cy), 0) != h:
                break
        else:
            print(Cx, Cy, H)
            exit()


Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

//#define int long long

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0},  {1, 1},   {0, 1},  {-1, 1},
                         {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/*----------------------------------------------/
/- char         : %c  | char *       : %s  | short        : %hd
/- int          : %d  | long         : %ld | long long    : %lld
/- unsigned short:%hu | unsigned int : %u  | unsigned long: %lu
/- u_long long  : %llu| (octal)      : %o  | (hexadecimal): %x
/- float        : %f  | double       : %lf |
/----------------------------------------------*/

/*----------------------------------------------/
/- INT_MAX, LONG_MAX   : 1<<15 = 2.1*pow(10, 9)       (= 2147483647)
/- UINT_MAX, ULONG_MAX : 1<<16 = 4.2*pow(10, 9)       (= 4294967295)
/- LLONG_MAX           : 1<<63 = 9.2*pow(10, 18)      (= 9223372036854775807)
/- ULLONG_MAX          : 1<<64 = 1.8*pow(10, 19)      (= 18446744073709551615)
/----------------------------------------------*/

int main() {
	char c;
	cin >> c;
	if(c=='A'){
		cout << "T";
	}else if(c=='T'){
		cout << "A";
	}else if(c=='G'){
		cout << "C";
	}else if(c=='C'){
		cout << "G";
	}





    /* ====================================== */
    cout << endl;
    return 0;
}

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

int main(){
    // input
    ll n;
    cin >> n;
    vector<ll> a(n+1,0);
    vector<ll> sum(n+1,0);
    int sig = 1;
    rep(i, 1, n+1){
        cin >> a[i];
        sum[i] = sum[i-1] + sig*a[i];
        sig = -sig;
    }

    ll ans;
    rep(i, 1, n+1){
        if(i%2 == 1){
            ans = sum[n] - sum[i-1];
            ans -= sum[i-1];
        }else{
            ans = -(sum[n] - sum[i-1]);
            ans += sum[i-1];
        }
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int n, t;
    cin >> n >> t;
    vector<int> vec(n);
    rep(i, n) cin >> vec[i];
    int ans= n * t;
    rep(i, n-1){
        if(t > vec[i+1] - vec[i]){
            ans -= (vec[i] + t - vec[i+1]);
        }
    }
    out(ans);
}

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

#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;

const ll oo=1e18;
const int MOD=1000000007;
const int INF=1000000000;
const ld EPS=0.000000001;

int dp[100005],h[100005],n,k=2;

signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,0x3f3f,sizeof dp);
    dp[1]=0;
    h[0]=0;
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>h[i];
    for(int i=2;i<=n;++i) {
        for(int j=1;j<=min(k,i);++j) {
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<dp[n];
    return 0;
}


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

int main()
{
    int n, s=0, cost=0, mn=INT_MAX;
    cin>>n;
    int a[n];
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
        s+=a[i];
    }
    s/=n;
    for(int i=0;i<n;++i)
    cost+=(abs(a[i]-s)*abs(a[i]-s));
    mn = min(mn, cost);
    cost=0;
    s++;
    for(int i=0;i<n;++i)
    cost+=(abs(a[i]-s)*abs(a[i]-s));
    mn = min(mn, cost);
    cout<<mn<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

template <class F>
int upper_bound(int i0, int i1, F f) {
    while (i0 < i1) {
        int i = (i0 + i1) / 2;
        if (f(i)) i0 = i + 1; else i1 = i;
    }
    return i0;
}

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

    int n, x;
    cin >> n >> x;

    vector<ll> a(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[n - i];
    }
    for (int i = 0; i < n; i++) {
        a[i + 1] += a[i];
    }

    vector<ll> g(n + 1);
    auto f = [&](int k) {
        if (g[k]) return g[k];

        ll s = (ll)x * (n + k) + a[k] * 5;
        for (int i = k; i < n; i += k) {
            s += (a[min(i + k, n)] - a[i]) * ((i / k) * 2 + 3);
        }
        return g[k] = s;
    };

    int k = upper_bound(1, n, [&](int k) {
        return f(k + 1) - f(k) < 0;
    });
    cout << f(k) << endl;

    return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define INF 1000000001
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define REP(i, n) for(int i=0; i<n; i++)
#define RER(i, n) for(int i=n-1; i>=0; i--)
#define ALL(v) v.begin() v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, k;

signed main(){
	cin >> n >> k;
	int a[MAX_N], b, t, ret = INF;
	REP(i, n){
		cin >> a[i];
		if(a[i] == 1) b = i;
	}
	// i番目から連続するk個の領域を選んだ時、その左側にある要素数はi個, 右側にある要素数はn-k-i個
	// 選ぶにはi+k<nである必要がある
	for(int i=b; i>b-k; i--){
		int l, r, tmp = 1;
		l = i;
		r = n - k - i;
		if(r < 0) continue;
		tmp += (l%(k-1)==0) ? l / (k - 1) : l / (k - 1) + 1;
		tmp += (r%(k-1)==0) ? r / (k - 1) : r / (k - 1) + 1;
		ret = min(ret, tmp);
	}
	cout << ret << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
template <typename Int, Int MOD, int N>
struct comb_util {
	std::array<Int, N + 1> fc, ifc;

	comb_util() {
		fc[0] = 1;
		for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD;
		ifc[N] = inv(fc[N]);
		for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
	}

	Int fact(Int n) { return fc[n]; }

	Int inv_fact(Int n) { return ifc[n]; }

	Int inv(Int n) { return pow(n, MOD - 2); }

	Int pow(Int n, Int a) {
		Int res = 1, exp = n;
		for (; a; a /= 2) {
			if (a & 1) res = res * exp % MOD;
			exp = exp * exp % MOD;
		}
		return res;
	}

	Int perm(Int n, Int r) {
		if (r < 0 || n < r)
			return 0;
		else
			return fc[n] * ifc[n - r] % MOD;
	}

	Int binom(Int n, Int r) {
		if (n < 0 || r < 0 || n < r) return 0;
		return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD;
	}

	Int homo(Int n, Int r) {
		if (n < 0 || r < 0) return 0;
		return r == 0 ? 1 : binom(n + r - 1, r);
	}
};

using comb = comb_util<long long, 1000000007, 1000000>;
comb c;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int B, W;
	cin >> B >> W;
	int N = B + W;
	vector<int> X(N, 0);
	vector<int> Y(N, 0);
	vector<int> sumY(N + 1, 0);
	vector<int> sumX(N + 1, 0);
	int inv2 = (MOD + 1) / 2;
	for (int i = 0; i < N; i++) {
		if (i >= W - 1) {
			X[i] = c.pow(inv2, i + 1);
			X[i] = (X[i] * c.binom(i, W - 1)) % MOD;
		}
	}

	for (int i = 0; i < N; i++) {
		sumX[i + 1] = (sumX[i] + X[i]) % MOD;
	}
	for (int i = 0; i < N; i++) {
		if (i >= B - 1) {
			Y[i] = c.pow(inv2, i + 1);
			Y[i] = (Y[i] * c.binom(i, B - 1)) % MOD;
		}
	}
	for (int i = 0; i < N; i++) {
		sumY[i + 1] = (sumY[i] + Y[i]) % MOD;
	}
	cerr << sumY[N] << endl;
	vector<int> res(N);
	for (int i = 0; i < N; i++) {
		int a = sumX[i];
		//cerr << i << " " << sumX[i] << " " << sumY[i] << endl;
		int b = 1 - a - sumY[i];
		while (b < 0)b += MOD;



		res[i] = (b * inv2) % MOD;
		res[i] += a;
		if (res[i] >= MOD)res[i] -= MOD;
	}

	for (int i = 0; i < N; i++) {
		cout << res[i] << endl;
	}
}

Measured memory_bytes: 25600
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int count=0;
    int ans=0;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='R')
        count++;
        else
        {
            ans=max(ans,count);
            count=0;
        }
    }
    ans=max(ans,count);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3592
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        c: chars,
    }
    let d = vec![c[0] as u8 + 1];
    println!("{}", std::str::from_utf8(&d).unwrap());
}

Measured memory_bytes: 4352
n = int(input())
s = list(input())
R = s.count("R")
G = s.count("G")
B = s.count("B")
ans = R*G*B

for i in range(n-1):
    for j in range(i+1,n):
        k=j+(j-i)
        if k>=n: break
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans-=1
print(ans)

Measured memory_bytes: 9208
import std.stdio;
import std.conv;
import std.typecons;

alias Tuple!(int,int) elist;

elist [][] G;
bool [] vis;

int dfs(int n, int tag) {
	if(vis[n]) return 0;
	vis[n] = true;
	int res = 1;
	for(int i = 0; i < G[n].length; i++) {
		if(G[n][i][1] != tag)
			res += dfs(G[n][i][0], tag);
	}
	return res;
}

void main() {
	int N, M;
	readf("%d %d\n", &N, &M);
	G.length = N;
	vis.length = N;
	for(int i = 0; i < M; i++) {
		int a, b;
		readf("%d %d\n", &a, &b);
		a--; b--;
		G[a] ~= elist(b,i);
		G[b] ~= elist(a,i);
	}
	int res = 0;
	for(int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) vis[j] = false;
		if(N != dfs(0,i)) res++;
	}
	writeln(res);
}


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

const int MAX_N = 2e5 + 10;

int dp[MAX_N][2];
char str[MAX_N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> str;
	for (int i = 1; i <= n; ++i) {
		if (str[i - 1] == '.')
			dp[i][0] = dp[i - 1][0],
			dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + 1;
		else
			dp[i][0] = dp[i - 1][0] + 1,
			dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]);
	}
	cout << min(dp[n][0], dp[n][1]) << "\n";
	return 0;
}

Measured memory_bytes: 2048
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
xyc = [[int(i) for i in input().split()] for _ in range(M)]

ret = min(a) + min(b)
for x, y, c in xyc :
  ret = min(ret, a[x-1] + b[y-1] - c)
print(ret)

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
    if(X / D / K >= 1) {
        ll temp = X / D - K;
        ll temp2 = X % D;
        if(X < 0) cout << temp2 + temp * D << endl;
        else cout << temp2 + temp * D << endl;
    } else {
        ll temp = X % D;
        ll temp2 = K - X / D;
        if(temp2 % 2) cout << D - temp << endl;
        else cout << temp << endl;
    }
    return 0;
}


Measured memory_bytes: 3628
#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define MGN 8
#define LINF (LONG_MAX/2)
using namespace std;
typedef long long ll; typedef unsigned long long ull;
typedef vector<int> vi; typedef vector<vi> vvi; 
typedef vector<ll> vl; typedef vector<vl> vvl;
typedef vector<double> vd; typedef vector<string> vs;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef vector<bool> vb; typedef vector<vb> vvb;
template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
    return left.second > right.second;}
vs split(string str, char sep) {
    vs v; stringstream ss(str); string t;
    while (getline(ss, t, sep)) v.push_back(t);
    return v;}
vs re_search_g(string s, regex re) {
    vs ret; smatch mc; auto it = s.cbegin();
    while (regex_search(it, s.cend(), mc, re)) {
        ret.push_back(mc[0]);
        it += mc.position(0) + mc.length();}
    return ret;}
#endif

void init_global_B() {}


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

    string S; cin >> S;

    regex re("[ACGT]+");
    vs mc = re_search_g(S, re);

    int ans = 0;
    for (string m : mc){
        ans = max(ans, (int)m.size());
    }

    cout << ans  << endl;    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
const int MAXK=10010;
long long dp[MAXK][110];
int d,a[MAXK];
string k;

inline long long dfs(int pos,int rest,bool limit){
	if(pos==-1) return rest==0;
	if(!limit && dp[pos][rest]!=-1) return dp[pos][rest];
	int up=limit?a[pos]:9;
	long long res=0;
	for(register int i=0;i<=up;++i)
		(res+=dfs(pos-1,(rest+i)%d,limit&&i==a[pos]))%=MOD;
	return dp[pos][rest]=res%MOD;
}

inline long long solve(){
	for(register int i=k.size()-1;i>=0;--i) a[k.size()-1-i]=k[i]-'0';
	return dfs(k.size()-1,0,1);
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>k;
	cin>>d;
	cout<<(solve()-1+MOD)%MOD<<endl;
	return 0;
}

Measured memory_bytes: 13232
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (1<<30)

int main(){
  string s;cin>>s;
  string a="YAKI";
  bool ch=true;
  for(int i=0;i<4;++i){
    if(s[i]!=a[i])ch=false;
  }
  if(ch)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=225;
char s[N][N];
int n,m,sum[N][N],f[2][N][N][N];
bool chk(int x1, int y1, int x2, int y2)
{
	int s=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
	return !s||s==(x2-x1+1)*(y2-y1+1);
}
inline int G(int a, int i, int j, int x, int p)
{	return min(f[a][i][p][x],f[a][p+1][j][x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j) sum[i][j]+=(s[i][j]=='.');
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
			for(int l=1,r;l<=m;l=r)
			{
				r=l;
				while(chk(i,l,j,r)&&r<=m) ++r;
				for(int p=l;p<r;++p) f[0][i][j][p]=r-1;
				if(l==r) f[0][i][j][l]=l-1,++r;
			}
	for(int a=1;;++a)
	{
		if(f[~a&1][1][n][1]>=m)
		{
			printf("%d\n",a-1);
			return 0;
		}
		for(int x=1;x<=m;++x)
			for(int i=1;i<=n;++i)
				for(int j=i,p=i;j<=n;++j)
				{
					while(p+1<j&&G(~a&1,i,j,x,p)<=G(~a&1,i,j,x,p+1)) ++p;
					if(f[~a&1][i][j][x]==m) f[a&1][i][j][x]=m;
					else f[a&1][i][j][x]=max(f[~a&1][i][j][f[~a&1][i][j][x]+1],G(~a&1,i,j,x,p));
				}
	}
}


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

int64_t Combination(int n, int r) {
  int64_t x = 1;
  int64_t b = 1;
  for (int i=1; i<=r; i++) {
    x *= (n - i + 1);
    b *= i;
  }
  return x/b;
}
    
int main() {
  int N;
  cin >> N;
  vector<string> s(N);
  for (int i=0; i<N; i++) {
    cin >> s[i];
    sort(s.at(i).begin(), s.at(i).end());
  }
  
  map<string,int> a;
  for (int i=0; i<N; i++) {
    if (a.count(s[i])) {
      a[s[i]]++;
    }
    
    else {
      a[s[i]] = 1;
    }
  }
  int64_t ans = 0;
  for (int i=0; i<N; i++) {
    if (-a.count(s[i])+1) {
      continue;
    }
    else if (a.at(s[i]) - 1) {
      ans += Combination(a.at(s[i]), 2);
      a.erase(s[i]);
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 18176
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000009;
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  int x, y;
  int box[100005] = {};
  int num_box[100005];
  int ans = 0;

  box[1] = 1;
  for(int i = 0;i < 100005;i++)num_box[i] = 1;
  
  cin >> n >> m;
  for(int i = 0;i < m;i++){
    cin >> x >> y;
    box[y] += box[x];
    num_box[y] ++;
    num_box[x] --;
    if(num_box[x] == 0)box[x] = 0;
  }

  for(int i = 1;i <= n;i++){
    if(num_box[i] > 0 && box[i] > 0){
      ans++;
    }
  }

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



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

int main(){
  int n;
  cin >> n;
  for(int i=1; i<=3500; ++i) for(int j=i; j<=3500; ++j){
    ll r = 4*i*j - n*(i+j);
    ll l = (ll)n*i*j;
    if(r>0 && l%r == 0){
      cout << i << " " << j << " " << l/r << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
int main(){
    int group;//クラスの人数
    int HowMany;//グループの人数
    cin >> group;
    int GP = group / 3;
    if(GP >= 1){
        HowMany += GP;
         cout << HowMany << endl;
        
    }else{
        HowMany = 0;
        cout << HowMany << endl;
    }
   

}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
   int W,H,C,K1,K2,n1,n2,i,A;
   scanf("%d %d %d",&W,&H,&C);
   K2=0;
   K1=W*H;
   if(W<H){
       A=W;
       W=H;
       H=A;
   }
   i=H;
   for(i=H;K1!=K2;i--){
       n1=W/i;
       n2=H/i;
       K2=n1*n2*i*i;
   }
   printf("%d\n",n1*n2*C);
   return 0;
}



Measured memory_bytes: 3228
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << endl;
}
const int mod = 1e9 + 7;

int main(){
	ll n,m; cin >> n >> m;
	ll ans = n*(n-1)/2 + m*(m-1)/2;
	cout << ans << endl;
}

Measured memory_bytes: 256
def out(c, n):
    for i in range(n):
        print(c, end='')

sx, sy, tx, ty = map(int, input().split())

out('U', ty - sy)
out('R', tx - sx)
out('D', ty - sy)
out('L', tx - sx)

out('L', 1)
out('U', ty - sy + 1)
out('R', tx - sx + 1)
out('D', 1)
out('R', 1)
out('D', ty - sy + 1)
out('L', tx - sx + 1)
out('U', 1)

print()


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];

  int ans = 0;

  while (true) {
    bool odd = false;
    for (int i = 0; i < N; i++) {
      if (A[i] % 2 == 1) {
        odd = true;
        break;
      }
    }

    if (odd) break;

    ans++;
    for (int i = 0; i < N; i++) {
      A[i] /= 2;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            SolveA();
            //SolveB();
            //SolveC();
            //SolveD();
        }
        private const long MOD = 1000000007;

        static void SolveA()
        {
            int n = ReadAndParseInt();
            var a = ReadAndParseIntArr();

            int[] table = { 399, 799, 1199, 1599, 1999, 2399, 2799, 3199 ,4800};
            int[] colorTotals = new int[table.Length];
            for(int i=0;i<a.Length;++i)
            {
                int rate = a[i];
                for(int j=0;j<table.Length;++j)
                {
                    if( rate <= table[j])
                    {
                        colorTotals[j]++;
                        break;
                    }
                }
            }
            int staticColorTotal = 0;
            for(int i=0;i<table.Length-1;++i)
            {
                if( colorTotals[i] >= 1)
                {
                    staticColorTotal++;
                }
            }

            int min = staticColorTotal;
            if( colorTotals[colorTotals.Length-1] >= 1)
            {
                if( staticColorTotal == 0)
                {
                    min = 1;
                }
            }
            int max = staticColorTotal + colorTotals[colorTotals.Length - 1];
            Console.WriteLine($"{min} {max}");
        }

        #region よく使う便利関数
        private static bool isPrime(long x)
        {
            if (x == 2) { return true; }
            if (x < 2 || x % 2 == 0) { return false; }
            long i = 3;
            while (i * i <= x)
            {
                if (x % i == 0) { return false; }
                i = i + 2;
            }
            return true;
        }
        private static long lcm(long x, long y)
        {
            return x / gcd(x, y) * y;
        }
        private static long gcd(long x, long y)
        {
            return y > 0 ? gcd(y, x % y) : x;
        }
        private static long pow(long x, long n)
        {
            if (n == 0) { return 1; }
            long res = pow(x * x % MOD, n / 2);
            if (n % 2 == 1)
            {
                res = res * x % MOD;
            }
            return res;
        }
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        #endregion
    }
}

Measured memory_bytes: 13140
function Main(input) {
  var args = input.split('\n');
  var n = parseInt(args.shift());
  var v = args.shift().split(' ').map(m => parseInt(m));
  var c = args.shift().split(' ').map(m => parseInt(m));
  var xy = v.map((n, i)=> n - c[i])
  .filter(f => f > 0);
  console.log(xy.length === 0 ? 0 : xy.reduce((ac, cv) => ac += cv));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

const int N = 2e5 + 10;
int a, b, c, d, n;
char s[N];

bool check(int x, int y) {
	for (int i = x + 2; i < y; i++) {
		if (s[i] == '#' && s[i - 1] == '#') return 0;
	}
	return 1;
}

bool solve() {
	if (check(a, c) && check(c, d)) {
		if (d < c) {
			for (int i = b; i <= d; i++) {
				if (s[i] == '.' && s[i - 1] == '.' && s[i + 1] == '.') return 1;
			}
			return 0;
		}
		return 1;
	}
	return 0;
}

int main() {
	n = read(), a = read(), b = read(), c = read(), d = read();
	scanf("%s", s + 1);
	printf("%s\n", solve() ? "Yes" : "No");
	return 0;
}

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

using namespace std;

long long x, ans;

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

    cin >> x;

    ans = 0;

    ans += 2 * (x / 11);

    x %= 11;

    if (x > 0) {
        ans++;

        x -= 6;
    }

    if (x > 0) {
        ans++;

        x -= 5;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define ll long long

void solve()
{
    ll N;
    cin >> N;
    vector<string> s(N);
    vector<ll> t(N);
    string X;

    for (ll i = 0; i < N; i++)
    {
        cin >> s.at(i) >> t.at(i);
    }

    cin >> X;
    bool sleep = false;
    ll count = 0;
    for (ll i = 0; i < N; i++)
    {
        if (sleep)
        {
            count += t.at(i);
        }
        if (s.at(i) == X)
        {
            sleep = true;
        }
    }

    cout << count << endl;

    return;
}

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


Measured memory_bytes: 256
ary = [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]
puts ary[gets.to_i - 1]

Measured memory_bytes: 1788
#include<stdio.h>

int main(){
  int a, b, c, d, e, ave;
  scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
  if(a < 40){
    a = 40;
  }
  if(b < 40){
    b = 40;
  }
  if(c < 40){
    c = 40;
  }
  if(d < 40){
    d = 40;
  }
  if(e < 40){
    e = 40;
  }
  ave = (a + b + c + d + e) / 5;
  printf("%d\n", ave);
  return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
set<pair<ll,ll>> st;
map<pair<ll,ll>,int> pt;
ll ans[100000];
int main() {
	
	ll h,w,n,x,y;
	cin>>h>>w>>n;
	for(int i=0;i<n;i++){
	    cin>>x>>y;
	    pt[make_pair(x,y)]++;
	    st.insert({x,y});
	    st.insert({x,y-1});
	    st.insert({x,y-2});
	    st.insert({x-1,y});
	    st.insert({x-1,y-1});
	    st.insert({x-1,y-2});
	    st.insert({x-2,y});
	    st.insert({x-2,y-1});
	    st.insert({x-2,y-2});
	}
	ll Tot=max(0ll,h-2)*max(0ll,w-2);
	for(set<pair<ll,ll>>::iterator it=st.begin();it!=st.end();it++){
	    x=(*it).first;
	    y=(*it).second;
	    int cnt=0;
	    if(x<1||x>h-2||y<1||y>w-2){
	        continue;
	    }
	    for(int i=0;i<=2;i++){
	        for(int j=0;j<=2;j++){
	            if(pt.find({x+i,y+j})!=pt.end()){
	              cnt++;       
	            }
	        }
	    }
	    ans[cnt]++;
	}
	ll tot=0;
	for(int i=1;i<=9;i++){
	    tot+=ans[i];
	}
	ans[0]=Tot-tot;
	for(int i=0;i<=9;i++){
	    cout<<ans[i]<<"\n";
	}
	return 0;
}

Measured memory_bytes: 62720
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  i64 N;
  cin >> N;
  N--;

  string r;

  r = 'a' + N % 26;

  N = N / 26 - 1;
  while (N >= 0) {
    r.insert(r.begin(), 'a' + (N % 26));
    N = N / 26 - 1;
  }

  cout << r;

}
#endif


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

#素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


#何通りあるか
def tori(A):
    cn=A
    k=1
    while cn>0:
        k+=1
        cn-=k
    return k-1

bunkai=factorization(N)

result=0
if N==1:
    print(0)
else:
    for j in range(len(bunkai)):
        result+=tori(bunkai[j][1])
    print(result)

Measured memory_bytes: 9524
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int INF = 2000000000;
const int num = 10000;
int n, k, u, v, w;
int c[num];
int d[num];
vector <pair<int, int> > ve[num];
int main() {
	priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	fill(d, d + num, INF);
	d[0] = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			cin >> v >> w;
			ve[u].push_back(make_pair(v, w));
		}
	}
	fill(c, c + num, 0);
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		int f = q.top().first;
		int s = q.top().second;
		q.pop();
		c[s] = 1;
		if (d[s] < f) continue;
		for (int i = 0; i < ve[s].size(); i++) {
			int fi = ve[s][i].first;
			int se = ve[s][i].second;
			if (c[fi]) continue;
			if (d[fi] > d[s] + se) {
				d[fi] = d[s] + se;
				q.push(make_pair(d[fi], fi));
			}
		}
	}
	for (int i = 0; i < n; i++) cout << i << " " << d[i] << endl;
	return 0;
}

Measured memory_bytes: 8036
#include<iostream>
#include<algorithm>
using namespace std;
int a[100001];
int main()
{
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n;i>=n-m+1;i--) sum+=a[i];
    cout<<sum;
    return 0;
}

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

using namespace std;

int cnt[25];
int main()
{
    int w,d,sum,mid;
    while(scanf("%d%d",&w,&d),w!=0&&d!=0){
        sum=0;
        memset(cnt,0,sizeof cnt);
        for(int i=0;i<w;i++){
            scanf("%d",&mid);
            sum+=mid;
            cnt[mid]++;
        }
        for(int i=0;i<d;i++){
            scanf("%d",&mid);
            if(cnt[mid]>0) cnt[mid]--;
            else sum+=mid;
        }
        printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 1184
#include<stdio.h>

int n, A[50];

int main(){
 int q, m, i;
  scanf("%d", &n);
  for(i=0; i<n; i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for(i=0; i<q; i++) {
    scanf("%d", &m);
    if(Exhaustive(0, m)) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}


int Exhaustive(int i, int m){
  if(m==0) return 1;
  if(i>=n) return 0;
  int res = Exhaustive(i+1, m) || Exhaustive(i+1, m-A[i]);
  return res;
}

Measured memory_bytes: 580
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int long long i=0;i<n;i++)
typedef int long long ll;
using namespace std;
int main(){
    map<int,int> m;
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll i=0;i<n;i++){
        ll j;
        cin>>j;
        m[j]++;
    }
    vector<ll> v;
    for(auto itr=m.begin();itr!=m.end();itr++){
        v.push_back(itr->second);
    }
    sort(v.rbegin(),v.rend());
   // cout<<v[v.size()-1];
    ll o=v.size();
    while(k<o){
        
        ans+=v[o-1];
        o--;
        
      
    }
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 11768
#include<iostream>
#include<map>
using namespace std;
typedef pair<int,int> P;
int w,h,s;
int sum;
P pmax(P a,P b){
	if(a>b)
	return a;
	return b;
}
int u[35][35];
P dp[33][33][33][33];
//must
//sum-local<=s
//plus=s-(sum-local)
P ret(P a,P b,int cnt){
	if(dp[a.first][a.second][b.first][b.second].first!=-1)
		return dp[a.first][a.second][b.first][b.second];
	P ans(1,cnt);
	int s1=0,s2=0;
	for(int i=a.first;i<b.first;i++){
		
		for(int j=a.second;j<=b.second;j++){
			s1+=u[i][j];
		}
		if(sum-s1>s||sum-(cnt-s1)>s)
			continue;
		P x=ret(a,P(i,b.second),s1),y=ret(P(i+1,a.second),b,cnt-s1);
		ans=pmax(ans,P(x.first+y.first,min(x.second,y.second)));
	}
	for(int i=a.second;i<b.second;i++){
		for(int j=a.first;j<=b.first;j++){
			s2+=u[j][i];
		}
		if(sum-s2>s||sum-(cnt-s2)>s)
			continue;
		P x=ret(a,P(b.first,i),s2),y=ret(P(a.first,i+1),b,cnt-s2);
		ans=pmax(ans,P(x.first+y.first,min(x.second,y.second)));
	}
	return dp[a.first][a.second][b.first][b.second]=ans;
}
int main(){
	while(cin>>h>>w>>s,h||w||s){
		sum=0;
		for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
		for(int k=0;k<h;k++)
		for(int l=0;l<w;l++)
		dp[i][j][k][l]=P(-1,0);
		for(int i=0;i<h;i++)
		for(int j=0;j<w;j++){
			cin>>u[i][j];
			sum+=u[i][j];
		}
		P ans=ret(P(0,0),P(h-1,w-1),sum);
		cout<<ans.first<<" "<<s-(sum-ans.second)<<endl;
	}
	return 0;
}

Measured memory_bytes: 9000
d,g=map(int,input().split())
p = [list(map(int,input().split())) for __ in range(d)]
ans_l = []
min_num = 1001

for i in range(2**d):
    num=0
    pt=0
    q=-1
    for j in range(d):
        if ((i>>j)&1):
            num+=p[j][0]
            pt+=p[j][0]*(j+1)*100+p[j][1]
        else:
            q=j
    if pt>=g:
        ans_l.append([num,pt])
    elif q > -1:
        for k in range(p[q][0]):
            num+=1
            pt+=(q+1)*100
            if pt>=g:
                ans_l.append([num, pt])
ans_l.sort()
print(ans_l[0][0])


Measured memory_bytes: 3316
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

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

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

ll a, b;

ll solve(ll x){
    return (a * x / b) - a * (x / b);
}

ll ternary_search(ll l, ll r){
    ll left = l, right = r;

    // calculate maximum value
    for(int i=0; i<100; i++){
        if(solve((left * 2 + right) / 3) > solve((left + right * 2) / 3)){
            right = (left + right * 2) / 3;
        }
        else{
            left = (left * 2 + right) / 3;
        }
    }

    return solve((left + right) * 0.5);
}

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

    ll n; cin>>a>>b>>n;

    cout << ternary_search(0, n + 1) << endl;

    return 0;
}

Measured memory_bytes: 3600
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func check(Y, X, h, w int, s []string) int {
	ret := 0
	dx := []int{-1, -1, -1, 0, 0, 0, 1, 1, 1}
	dy := []int{-1, 0, 1, -1, 0, 1, -1, 0, 1}
	for i := 0; i < 9; i++ {
		x := X + dx[i]
		y := Y + dy[i]
		if x < 0 || x >= w || y < 0 || y >= h {
			continue
		}
		if s[y][x] == '#' {
			ret++
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	H, W := getInt(), getInt()
	s := make([]string, H)
	for i := 0; i < H; i++ {
		s[i] = getString()
	}
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if s[i][j] == '#' {
				fmt.Print(string('#'))
			} else {
				n := check(i, j, H, W, s)
				fmt.Print(string(n + '0'))
			}
		}
		out()
	}
}


Measured memory_bytes: 1808
#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 <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
   string S;
   cin >> S;
   for(int i=0;i<S.size();i++){
      cout << 'x';
   }
   cout << endl;
   return 0;
}


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

struct DP
{
    int prev_workday;
    int daycount;
};
using vdp = std::vector<DP>;

vdp left_schedule(int N, int K, int C, const std::string &S)
{
    int k, count = 0, skip = 0;
    vdp work(N);
    for (int i = 0; i < N; i++)
    {
        if (skip <= 0 && S[i] == 'o')
        {
            count++;
            k = i;
            skip = C;
        }
        else if (skip > 0)
        {
            --skip;
        }
        work[i].daycount = count;
        work[i].prev_workday = k;
        
    }
    return work;
}

vdp right_schedule(int N, int K, int C, const std::string &S)
{
    int k, count = 0, skip = 0;
    vdp work(N);
    for (int i = N - 1; i >= 0; i--)
    {
        if (skip <= 0 && S[i] == 'o')
        {
            count++;
            k = i;
            skip = C;
        }
        else if (skip > 0)
        {
            --skip;
        }        
        work[i].daycount = count;
        work[i].prev_workday = k;
    }
    return work;
}

bool is_valid(const vdp &min_sche, const vdp &max_sche, int N, int K, int C, int i)
{
    int skip = C + 1;
    if (i > 0 && i < N - 1)
    {
        skip = max_sche[i+1].prev_workday - min_sche[i-1].prev_workday;
    }

    int left_daycount = 0, right_daycount = 0;
    if (i > 0) left_daycount = min_sche[i-1].daycount;
    if (i < N-1) right_daycount = max_sche[i+1].daycount;
    
    int kth = K + ((skip <= C) ? 1 : 0);
    return left_daycount + right_daycount >= kth;
}

int main()
{
    int N, K, C;
    std::cin >> N >> K >> C;
    std::string S;
    std::cin >> S;

    vdp min_sche = left_schedule(N, K, C, S);
    vdp max_sche = right_schedule(N, K, C, S);
    
    for (int i = 0; i < N; i++)
    {
        if (!is_valid(min_sche, max_sche, N, K, C, i))
        {
            std::cout << (i+1) << std::endl;
        }
    }
}

Measured memory_bytes: 4996
import java.io.*;
import java.util.*;

public class Main {

    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException exp) {
                    throw new RuntimeException(exp);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {    //throws FileNotFoundException {
        InputStream inputStream = System.in;    //new FileInputStream("input.txt");
        OutputStream outputStream = System.out; //new FileOutputStream("output.txt");
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        Task newTask = new Task();
        newTask.solve(in, out);

        out.close();
    }

    private static class Task {
        //.constant
        private final int INF = Integer.MAX_VALUE;
        private final int MOD = (int)1e9 + 7;

        //.data

        //.code
        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();

            int ans = 0;
            for (int i = 1; i * i <= n; ++i) {
                ans = i * i;
            }

            out.println(ans);

        }//end

    }

}

Measured memory_bytes: 22996
def f_fork_in_the_road():
    # 参考: https://www.onakasuitacity.com/abc144-f/
    N, M = [int(i) for i in input().split()]
    Nodes = [[int(i) for i in input().split()] for j in range(M)]

    edges = [[] for _ in range(N)]
    for s, t in Nodes:
        edges[s - 1].append(t - 1)

    # editorial の DP テーブルの確率部分
    probability = [0] * N
    probability[0] = 1.0
    for v in range(N):
        for next_vertex in edges[v]:
            probability[next_vertex] += probability[v] / len(edges[v])

    # 期待値
    expected_value = [0] * N
    for v in range(N - 2, -1, -1):
        for next_vertex in edges[v]:
            expected_value[v] += expected_value[next_vertex]
        expected_value[v] = 1 + expected_value[v] / len(edges[v])

    ans = expected_value[0]
    for v in range(N):
        if len(edges[v]) <= 1:
            continue
        # 各頂点 v に対して、v から出る辺 vw のうち
        # w での期待値が最大のものの分を差分から引く。残りは足す
        v_max_expected = max(((expected_value[w], w) for w in edges[v]))[1]
        expected_diff = 0.0
        outdegree = len(edges[v])
        for next_vertex in edges[v]:
            if next_vertex == v_max_expected:
                expected_diff -= expected_value[next_vertex] / outdegree
            else:
                expected_diff += expected_value[next_vertex] / (outdegree * (outdegree - 1))
        ans = min(ans, expected_value[0] + probability[v] * expected_diff)
    return round(ans, 10)

print(f_fork_in_the_road())

Measured memory_bytes: 37144
#ifndef AC_ABC_LIB_HPP
#define AC_ABC_LIB_HPP

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> sys_args(int argc, char **argv) {
    std::vector<std::string> args;

    for (int i = 1; i < argc; ++i)
        args.emplace_back(argv[i]);

    return args;
}

#endif  // AC_ABC_LIB_HPP

using namespace std;

int get_max(int& a, int& b) {
    return (a < b ? b-- : a--);
}

int main(int argc, char **argv) {
    int a, b, res = 0;
    std::cin >> a >> b;

    res += get_max(a, b);
    res += get_max(a, b);

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
from collections import Counter
from itertools import accumulate

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

c = Counter([0] + [x % M for x in accumulate(A)])
ans = 0
for v in c.values():
    ans += v * (v - 1) // 2
print(ans)

Measured memory_bytes: 16596
#include<bits/stdc++.h>
#define M 200002
using namespace std;
int A[M],Mx[M],Mx1[M];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	for(int i=1;i<=n;i++){
		Mx[i]=max(Mx[i-1],A[i]);
		Mx1[n-i+1]=max(Mx1[n-i+2],A[n-i+1]);
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",max(Mx[i-1],Mx1[i+1]));
	return 0;
}

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

int main()
{
    ll n,i,j,t,dp[100];
    while(cin>>n)
    {
        dp[0]=2;
        dp[1]=1;
        for(i=2;i<=86;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        cout<<dp[n]<<endl;
    }


}


Measured memory_bytes: 256