akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

const int INF = 1001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    int ans = INF;
    rep(i, n - k + 1) chmin(ans, min(abs(a[i]), abs(a[i+k-1])) + a[i+k-1] - a[i]);
    cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		String b=stdIn.next();
		if(b.equals("A"))
			System.out.println("T");
		if(b.equals("T"))
			System.out.println("A");
		if(b.equals("G"))
			System.out.println("C");
		if(b.equals("C"))
			System.out.println("G");
	}
}

Measured memory_bytes: 21588
k = int(input())
cnt = 9
q = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

if k <= cnt:
    print(q[k-1])

while True:
    if cnt >= k:
        break
    num = q.pop(0)
    list_num = list(num)
    a = int(list_num[-1])
    for i in range(10):
        if abs(a-i) < 2:
            cnt += 1
            if i == 0:
                q.append(num+"0")
            elif i == 1:
                q.append(num +"1")
            elif i == 2:
                q.append(num +"2")
            elif i == 3:
                q.append(num+"3")
            elif i == 4:
                q.append(num+"4")
            elif i == 5:
                q.append(num+"5")
            elif i == 6:
                q.append(num+"6")
            elif i == 7:
                q.append(num+"7")
            elif i == 8:
                q.append(num+"8")
            elif i == 9:
                q.append(num+"9")

if k > 9:
    print(q[k-cnt-1])

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

typedef long long ll;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

   	string s, t;
   	cin >> s >> t;
   	int ans = 0;
   	for (int i = 0; i < (int)s.length(); ++i) {
   		if (s[i] != t[i]) ++ans;
   	}
   	cout << ans;
	return 0;
}

Measured memory_bytes: 3796
x,y,z = input().split()
x=int(x) 
y=int(y)
z=int(z)
if (x>=y and x>=z):
    print(10*x + y + z)
if (x<y and y>=z):
    print(x+10*y+z)
if (x<z and y<z):
     print(x+y+10*z)

Measured memory_bytes: 3060
import math

N = int(input())
tmp = 0
sum = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        tmp = math.gcd(i,j)
        for k in range(1,N+1):
            sum = sum + math.gcd(tmp,k)
            
print(sum)

Measured memory_bytes: 9048
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

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

        vector<int> p(n);
        int tmp = 0, m = 0;

        REP(i, n) {
                cin >> p[i];
                tmp += p[i];

                if (i >= k) {
                        tmp -= p[i - k];
                }
        
                m = max(m, tmp);
        }

        cout << fixed << setprecision(8) << (m + k) / 2.0 << endl;

        return 0;
}


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

#define debug(x) cout <<"DEBUG"<<" "<<#x<<":"<<x<<'\n'

//↓0-indexか1-indexでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   //0-index昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) //1-index昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-index降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-index降順
//rep2 -> 第二引数 m から n 回繰り返し ex) m=5 n=3 なら i=5,i=6,i=7 まで
#define rep2(i,m,n) for(int i = ((int)(m)); i < ((int)(n))+((int)(m)); i++)
#define SIZE(x) ((int)((x).size()))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;
template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

/* 円周率は M_PI を使おうね */
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;

/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(10);

    string s; cin >> s;
    ll c = 0LL, cnt = 0LL;
    if(s.size() < 3) {
        cout << '0' << '\n';
        return 0;
    }

    for(int i = 0; i < s.size()-1;) {

        //cout << s[i] << s[i+1] << s[i+2] << '\n';
        //イメージとしては、例えば
        //AAAAABCになったら遡ると5回ABCを作れる、を考える。
        //CBとかACとかが来たら遡ってABCを作ることが出来ない
        //最終的にはBCBCBCBCAAAABCAAAABCAAAACBCAAAみたいになる
        
        if(s[i]=='A') {
            ++c;
            ++i;
        }
        else if(s[i]=='B'&&s[i+1]=='C') {
            cnt += c;
            i += 2;
        }
        else {
            c = 0;
            ++i;
        }
    }
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define INF 10000000
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
vector<int> to[2000010];
vector<ll> cnt;
void dfs(int v,int p){
    cnt[v]+=cnt[p];
    for(int u : to[v]){
        if(u==p) continue;
        dfs(u,v);
    }
}
int main(){
    int N,Q;
    cin>>N>>Q;
    for(int i=1; i<N; i++){
        int a,b;
        cin>>a>>b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    cnt.resize(N+1);
    rep(i,Q){
        int p,x;
        cin>>p>>x;
        cnt[p]+=x;
    }
    dfs(1,0);
    for(int i=1; i<=N; i++){
        cout<<cnt[i]<<" ";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 66432
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
       Scanner sc=new Scanner(System.in);
       
       String s=sc.next();
       
       int count=s.lastIndexOf("Z")-s.indexOf("A")+1;
       System.out.println(count);
    }
}


Measured memory_bytes: 26576
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<math.h>
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
using namespace std;
int n,m;
struct nod
{
    int l,r,len;
    bool operator<(const nod &b)const
    {
        return len<b.len;
    }
}a[300005];
int lazy[1200005];
void pushdown(int now)
{
    lazy[ls(now)]+=lazy[now];
    lazy[rs(now)]+=lazy[now];
    lazy[now]=0;
}
void jia(int now,int l,int r,int st,int ed)
{
    if(l==r)
    {
        lazy[now]++;
        return;
    }
    if(st<=l&&ed>=r)
    {
        lazy[now]++;
        return;
    }
    if(lazy[now])pushdown(now);
    int mid=(l+r)>>1;
    if(st<=mid)jia(ls(now),l,mid,st,ed);
    if(ed>=mid+1)jia(rs(now),mid+1,r,st,ed);
}
int query(int now,int l,int r,int pos)
{
    if(l==r)return lazy[now];
    if(lazy[now])pushdown(now);
    int mid=(l+r)>>1;
    if(pos<=mid)return query(ls(now),l,mid,pos);
    else return query(rs(now),mid+1,r,pos);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].len=a[i].r-a[i].l+1;
    }
    sort(a+1,a+1+n);
    int flag=1,ans;
    printf("%d\n",n);
    for(int i=2;i<=m;i++)
    {
        while(flag<=n&&a[flag].len<=i)
        {
            jia(1,1,m,a[flag].l,a[flag].r);
            //printf("%d %d\n",a[flag].l,a[flag].r);
            flag++;
        }
        ans=0;
        //printf("%d %d\n",i,query(1,1,m,9));
        for(int j=i;j<=m;j+=i)
        {
            ans+=query(1,1,m,j);
            //printf("%d ",ans);
        }
        printf("%d\n",ans+(n-flag+1));
    }
}

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

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

    int ans = 0;
    if (n%1000 > 0) ans = 1000 - (n%1000);
    cout << ans << endl;
    return 0; 
}


Measured memory_bytes: 3596
n = int(input())
a, b = [], []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
a.sort()
b.sort()
if n & 1:
    print(b[n // 2] - a[n // 2] + 1)
else:
    a = list(map(lambda x: x * 2, a))
    b = list(map(lambda x: x * 2, b))
    print((b[n // 2 - 1] + b[n // 2]) // 2 
            - (a[n // 2 - 1] + a[n // 2]) // 2 + 1)


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

int n;

struct node
{
	int id, pid, k, d;
	int* cid;
	string type;
}N[100005];

void GetDepth(node& GN)
{
	GN.d = 0;
	node temp = GN;

	while (temp.pid != -1)
	{
		GN.d++;
		temp = N[temp.pid];
	}
}

void GetType(node& GN)
{
	if (GN.pid == -1)
		GN.type = "root";
	else if (GN.k == 0)
		GN.type = "leaf";
	else
		GN.type = "internal node";
}

void print()
{
	for (int i = 0; i < n; i++)
	{
		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";

		if (N[i].k != 0)
		{
			for (int j = 0; j < N[i].k - 1; j++)
				cout << N[i].cid[j] << ", ";
			cout << N[i].cid[N[i].k - 1];
		}

		cout << "]" << endl;
	}	
}

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

	int place;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		N[i].pid = -1;
	
	for (int i = 0; i < n; i++)
	{
		cin >> place;
		N[place].id = place;
		cin >> N[place].k;

		if (N[place].k > 0)
			N[place].cid = new int[N[place].k];

		for (int j = 0; j < N[place].k; j++)
		{
			cin >> N[place].cid[j];
			N[N[place].cid[j]].pid = N[place].id;
		}			
	}

	for (int i = 0; i < n; i++)
		GetDepth(N[i]);

	for (int i = 0; i < n; i++)
		GetType(N[i]);	

	print();

	return 0;
}



Measured memory_bytes: 11464
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}

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

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

  int pos = 0;

  while (pos < n) {
    if (s[pos] == 'B' && s[pos + 1] == 'C') {
      t += 'D'; pos += 2;
    } else {
      t += s[pos]; ++pos;
    }
  }

  int64 ans = 0;
  int cur = 0;

  for (int i = 0; i < (int) t.size(); ++i) {
    if (t[i] == 'A') {
      ++cur;
    } else if (t[i] == 'D') {
      ans += cur;
    } else {
      cur = 0;
    }
  }
  print(ans);

  return 0;
}

Measured memory_bytes: 916
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve(S, T):
    d = dict()
    for s, t in zip(S, T):
        if s in d and d[s] != t:
            return False
        else:
            d[s] = t

    return True


def main():
    S = readline().strip()
    T = readline().strip()

    if solve(S, T) and solve(T, S):
        print('Yes')
    else:
        print('No')

    return


if __name__ == '__main__':
    main()


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

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

    ll A, B, N;
    cin >> A >> B >> N;

    ll x = min(B - 1LL, N);

    cout << A * x / B << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
int main(){
  std::string in;
  std::cin >> in;
  for(int i=0;i<in.size();i++){
    std::cout << in[i];
    if(i==3){
      std::cout << " ";
    }
  }
  std::cout << std::endl;
  return 0;
}


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


ans=[-1,-1,-1]
q1=min(Y//10000,N)
for i in range(q1+1):
    r1=Y-10000*i
    q2=min(r1//5000,N-i)
    for j in range(q2+1):
        r2=r1-5000*j
        #print(r1,q1,r2)
        if r2==1000*(N-i-j):
            check=1
            ans[0]=i
            ans[1]=j
            ans[2]=N-i-j
            break
    else:
        continue
    break

print(*ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

/* modとる */
inline ll modu(ll a){
    return(a % mod + mod) % mod;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N = in<ll>(),K = in<ll>();
    ll sum = 0;
    for(ll i = K;i < N+2;i++){
        sum = modu(sum + modu(1 + (i * (2*N-i+1) - i*(i-1))/2));
    }
    cout << sum << "\n";
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
 
#define N  100010
int main () {
	int n,m,h[N],ma[N];
 cin>>n>>m;
 for(int i=1;i<=n;i++){
   	cin>>h[i];
 ma[i]=0;
 }
 for(int i=0;i<m;i++){
 int a,b;
 cin>>a>>b;
 ma[a]=max(ma[a],h[b]);
 ma[b]=max(ma[b],h[a]);
 }
 int ans=0;
 for(int i=1;i<=n;i++){
 ans+=h[i]>ma[i];
 }
 cout<<ans<<endl;
}


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

template <typename T> struct Segtree {
	Segtree(int n):base(1){
		while (base < n) base *= 2;
		nodes.resize(base*2, T::id());
	}
	void setLeaf(int i, T x) {
		nodes[base+i] = x;
		for (auto v=(base+i)/2; v>0; v/=2)
			nodes[v] = T::merge(nodes[v*2], nodes[v*2+1]);
	}
	T readRange(int left, int right) const { return implRR(left, right, 0, base, 1); }
	T implRR(int left, int right, int i, int e, int v) const {
		if (left >= e or right <= i) return T::id();
		if (left <= i and right >= e) return nodes[v];
		return T::merge(implRR(left, right, i, (i+e)/2, v*2), implRR(left, right, (i+e)/2, e, v*2+1));
	}
	template <typename F> int find(int left, int right, bool last, F f) const { return implF(left, right, last, f, 0, base, 1); }
	template <typename F> int implF(int left, int right, bool last, F f, int i, int e, int v) const { 
		if (left >= e or right <= i) return -1;
		if (left <= i and right >= e) return implF2(left, right, last, f, i, e, v);
		auto i1 = i;
		auto j1 = (i+e)/2;
		auto v1 = 2*v;
		auto i2 = (i+e)/2;
		auto j2 = e;
		auto v2 = 2*v+1;
		if (last)
			swap(i1, i2), swap(j1, j2), swap(v1, v2);
		auto r = implF(left, right, last, f, i1, j1, v1);
		return r == -1 ? implF(left, right, last, f, i2, j2, v2) : r;
	}
	template <typename F> int implF2(int left, int right, bool last, F f, int i, int e, int v) const { 
		if (not f(nodes[v])) return -1;
		if (e - i == 1) return i;
		auto i1 = i;
		auto j1 = (i+e)/2;
		auto v1 = 2*v;
		auto i2 = (i+e)/2;
		auto j2 = e;
		auto v2 = 2*v+1;
		if (last)
			swap(i1, i2), swap(j1, j2), swap(v1, v2);
		auto r = implF2(left, right, last, f, i1, j1, v1);
		return r == -1 ? implF2(left, right, last, f, i2, j2, v2) : r;
	}
	int base;
	vector<T> nodes;
};

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

template <typename T> struct Max {
	T x;
	static Max id() { return {numeric_limits<T>::min()}; }
	static Max merge(const Max& a, const Max& b) { return {max(a.x, b.x)}; }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto n = load<int>();
	auto perm = loadMany<int>(n);
	auto segtree = Segtree<Max<int>>(n);
	for (auto i=0; i<n; ++i)
		segtree.setLeaf(i, {perm[i]});
	auto score = 0ll;
	for (auto i=0; i<n; ++i) {
		auto val = perm[i];
		auto ileft = segtree.find(0, i, true, [&](auto v){ return v.x > val; });
		auto iright = segtree.find(i+1, n, false, [&](auto v){ return v.x > val; });
		if (iright == -1)
			iright = n;
		auto jleft = segtree.find(0, ileft, true, [&](auto v){ return v.x > val; });
		auto jright = segtree.find(iright+1, n, false, [&](auto v){ return v.x > val; });
		if (jright == -1)
			jright = n;
		auto l1 = i - ileft - 1;
		auto l2 = i - jleft - 1;
		auto r1 = iright - i - 1;
		auto r2 = jright - i - 1;
		score += max((long long)(l2 - l1) * (r1 + 1), 0ll) * val;
		score += max((long long)(r2 - r1) * (l1 + 1), 0ll) * val;
	}
	cout << score << '\n';
}


Measured memory_bytes: 1664
#include <iostream>
//#include <cstdio>
//#include <cstdlib>
//#include <cmath>
//#include <cstring>
//#include <vector>
//#include <set>
//#include <map>
//#include <stack>
//#include <queue>
//#include <string>
//#include <algorithm>
//#include <bitset>
using namespace std;

#define loop(n)          for(int i = 0; i < (n); i++)
#define lp(x, s, e)      for(int x = (s); x < (e); x++)

int arr[1000000];

void init() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}




int main()
{
    init();
    int n;
    cin >> n;
    int a = 0, w = 0, t = 0, r = 0;
    loop(n)
    {
        string x;
        cin >> x;
        if (x[0] == 'A')
            a++;
        else if (x[0] == 'T')
            t++;
        else if (x[0] == 'W')
            w++;
        else
            r++;
    }
    cout << "AC" << " " << "x" << " " << a << "\n";
    cout << "WA" << " " << "x" << " " << w << "\n";
    cout << "TLE" << " " << "x" << " " << t << "\n";
    cout << "RE" << " " << "x" << " " << r << "\n";
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> h(n);
  for(int i = 0;i<n;i++){
    cin >> h.at(i);
  }
  vector<int> good_view(n);//goodなら0
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    if(h.at(a-1)>=h.at(b-1)){
      good_view.at(b-1)=1;
    }
    if(h.at(a-1)<=h.at(b-1)){
      good_view.at(a-1)=1;
    }
  }
  int count=0;
  for(int i=0;i<n;i++){
    if(good_view.at(i)==0){
      count++;
    }
  }
  cout << count << endl;  
}

Measured memory_bytes: 4000
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		long n = sc.nextLong();
		
		// 計算
		long result = 0;
		ArrayList<NumList> list = new ArrayList<NumList>();
    	for(long m = 2; m <= sqrt(n); m++){
    		if(n == 1) break;
    		if(n%m == 0){
    			NumList numList = new NumList(m, 0);
    			while(n%m == 0){
    				n = n/m;
    				numList.num2++;
    			}
    			list.add(numList);
    		}
    	}
    	if(n != 1) list.add(new NumList(n, 1));
    	
    	for(NumList N : list){
    	    long a = N.num2;
    	    result += func(a);
    	}
		//System.out.println("func:" + func(3));
		
		// 出力
		System.out.println(result);
	}
	
	static long func(long a){
	    long temp = Double.valueOf(floor(sqrt(a))).longValue();
	    //System.out.println("temp:" + temp);
	    //System.out.println("2a:" + 2*a);
	    while(temp*(temp+1) <= 2*a){
	        temp++;
	        //System.out.println("loop temp:" + temp);
	    }
	    return temp -1;
	}

	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}

class NumList {
	long num1;
	long num2;
	
	NumList(long num1, long num2){
		this.num1 = num1;
		this.num2 = num2;
	}
}



Measured memory_bytes: 26256
// Version.10.32.47.06.04.20.
#include <bits/stdc++.h>
#define N 666
using namespace std;
const int mod = 1e9 + 7;

int n, m, cnt[N], p[N], ffac[N], f[N][N];

inline int num(int l, int r) { return cnt[r] - cnt[l - 1]; }

int main() {

    cin >> n >> m;
    int K = (n - m) << 1;
    for (int i = 1; i <= n * 2; ++i)
        p[i] = i, cnt[i] = 1;
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        cnt[u] = cnt[v] = 0;
        p[u] = v, p[v] = u;
    } m = n << 1;

    for (int i = ffac[0] = 1; i <= m; ++i) {
        cnt[i] += cnt[i - 1];
        if (i % 2 == 0)
            ffac[i] = 1ll * ffac[i - 2] * (i - 1) % mod;
    }
    
    long long ans = 0;
    for (int i = 1; i <= m; ++i)
        for (int j = i + 1; j <= m; ++j) {
            f[i][j] = 0;
            int ok = 1, c = num(i, j);
            for (int k = i; ok && k <= j; ++k)
                if (p[k] < i || p[k] > j)
                    ok = 0;
            if (!ok || !ffac[c]) continue;
            f[i][j] = ffac[c];
            for (int k = i + 1; k < j; ++k)
                f[i][j] = (f[i][j] - 1ll * f[i][k] * ffac[num(k + 1, j)] % mod + mod) % mod;
            // f[i][j] = 1ll * f[i][j] * ffac[K - c] % mod;
            ans = (ans + 1ll * f[i][j] * ffac[K - c]) % mod;
            // cout << i << " " << j << " " << f[i][j] << endl;
        }

    cout << ans << endl;


return 0;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
"""
Created on Fri Aug 10 01:03:03 2018

@author: Yuki
"""


N = int(input())
A = sorted([int(i) for i in input().split()])
import collections
#N = 5
#A = sorted([2, 4, 1, 4, 2])
cnt_dict = collections.Counter(A)
res_cnt = 0
for key in cnt_dict.keys():
    if key == cnt_dict[key]:
        pass
    else:
        if key < cnt_dict[key]:
            res_cnt += cnt_dict[key] - key
        else:
            res_cnt += cnt_dict[key]
print(res_cnt)

Measured memory_bytes: 18552
N = int(input())
P = list(map(int,input().split()))

Q = [i+1 for i in range(N)]
for i in range(N):
    for j in range(i,N):
        P[i], P[j] = P[j], P[i]

        if P == Q:
            print("YES")
            exit()

        P[i], P[j] = P[j], P[i]

print("NO")

Measured memory_bytes: 9200
use proconio::marker::*;
use proconio::*;

fn main() {
    input! {
        n: usize,
    };

    let mut ans = 0;

    for i in 1..=n {
        println!("{}", f(i));
    }
}

fn f(n: usize) -> usize {
    let mut res = 0;

    for x in 1..=100 {
        for y in x..=100 {
            for z in y..=100 {
                if x * x + y * y + z * z + x * y + x * z + y * z == n {
                    if x == y && y == z {
                        res += 1;
                    } else if x == y || y == z || x == z {
                        res += 3;
                    } else {
                        res += 6;
                    }
                }
            }
        }
    }

    res
}


Measured memory_bytes: 2108
#include <stdio.h>
#include <algorithm>
long long e = 10000000;
int n, m, t, d;
long long a, b, c;
long long  ans;
long long x[300000];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a);
		x[t] = a * e + 1;
		t++;
	}
	for (int i = 0; i < m; i++) {
		scanf("%lld%lld", &b, &c);
		x[t] = c * e + b;
		t++;
	}
	std::sort(x, x + n + m);
	d = n + m - 1;
	for (int i = 0; i < n; i++) {
		ans += x[d] / e;
		x[d]--;
		if ((x[d] % e) == 0)d--;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long a = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        long[] ary = new long[n];
        for (int i = 0; i < n; i++) {
            ary[i] = Long.parseLong(sc.next());
        }
        long l = 0;
        long r = Integer.MAX_VALUE;
        while (l < r - 1) {
            long temp = (l + r) / 2;
            long cnt = 0;
            for (int i = 0; i < n; i++) {
                long h = ary[i];
                if (h > b * temp) {
                    if ((h - b * temp) % (a - b) == 0) {
                        cnt += (h - b * temp) / (a - b);
                    } else {
                        cnt += (h - b * temp) / (a - b) + 1;
                    }
                }
            }
            if (temp >= cnt) {
                r = temp;
            } else {
                l = temp;
            }
        }
        System.out.println(r);
    }
}

Measured memory_bytes: 48884
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define All(x) (x).begin(),(x).end()
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>inline void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);	
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************
const int maxn=1e6+5,mod=1e9+7;
int n;
int f[maxn],sum[maxn];
int main(){
	read(n);
	sum[0]=f[0]=1;
	rep(i,1,n){
		f[i]=f[i-1];
		if(i>=3)f[i]=(f[i]+sum[i-3])%mod;
		sum[i]=(sum[i-1]+f[i])%mod;
	}
	int ans=0;
	per(i,n,0){
		if(i==n)ans=(ans+f[i])%mod;
		else if(i==n-1){
			ans=(ans+1ll*(n-1)*f[i])%mod;
		}else {
			int j=n-i;
			ans=(ans+1ll*(n-j+1)*f[i])%mod;
			ans=(ans+1ll*(n-1)*(n-1)%mod*f[i])%mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8064
import java.math.BigDecimal;
import java.util.*;

public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int N = sc.nextInt();
        long[] values = new long[N];

        long sum = 0;
        for (int i = 0; i < N; i++) {
            long value =  sc.nextLong();
            values[i] = value;
            sum += value;
        }
        long mid = Math.round(((double) sum) / ((double) N));

        long ans = 0;
        for (int i = 0; i < N; i++) {
            long diff = Math.abs(values[i] - mid);
            ans += (diff * diff);
        }
        System.out.println(ans);
    }

}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int main() {
  int n;
  cin >> n;
  int r = n % 10;
  string res;
  if (r == 3) {
    res = "bon";
  } else if (r == 0 || r == 1 || r== 6 || r == 8) {
    res = "pon";
  } else {
    res = "hon";
  }
  cout << res << endl;

  return 0;
}



Measured memory_bytes: 3580
import sys
from collections import defaultdict


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return list(map(int, input().split()))


def main():
    n = int(input())

    aa = input_ints()
    m = defaultdict(lambda: 0)
    s = 0
    for a in aa:
        m[a] += 1
        s += a

    q = int(input())
    for _ in range(q):
        b, c = tuple(input_ints())
        s += (c - b) * m[b]
        m[c] += m[b]
        del m[b]
        print(s)


main()


Measured memory_bytes: 23976
N = int(input())
A = [[None]*2 for i in range(N)]
for i in range(N):
    A[i][1],A[i][0] = map(int,input().split())

A.sort()

zum = 0
now = 0
for i in range(N):
    zum += A[i][1]
    now = A[i][0]
    if zum > now:
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 72172
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;
int P[200005];

int main(void) {

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> P[i];
	}

	int min_val = N;

	long long int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (min_val >= P[i]) { ans++; }
		min_val = min(min_val, P[i]);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define N 3005
double prob[N], dp[N][N];


int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> prob[i];
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        double rp = 1 - prob[i];
        for(int j  = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j] * rp + (j? dp[i - 1][j - 1] * prob[i] : 0);
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }
    double ans = 0;
    for(int i = (n + 1) / 2; i <= n; i++) ans += dp[n][i];
    printf("%0.10lf\n", ans);
}


Measured memory_bytes: 70656
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T, class U> inline bool chmax(T& a,U b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T& a,U b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int n, r;
    cin >> n >> r;
    if (n < 10) {
        cout << r + (100 * (10 - n)) << endl;
    } else {
        cout << r << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <iomanip>
#include <fstream>
using namespace std;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef pair<int,int> PII;
typedef long long int64;
typedef vector<int> VI;

int main() {
	//freopen("test.in","r",stdin);
	int t;
	cin >> t;
	if (t>=30) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
	int n;
	int r[100];
	int ans = 0;
 
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> r[i];
	}
	sort(r,r+n );
	//for (auto i : r)cout << i << " ";
 
	int last = 0;
	for (int i =0;i<n;i++)
	{
		if (r[i] == last)continue;
		else
		{
			last = r[i]; ans++;
			
		}
 
	}
 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1000000001
#define ll long long
using namespace std;
using pint = pair<int, int>;

int main()
{
  ll N;
  cin >> N;
  string S;
  cin >> S;
  vector<ll> e_sum(N, 0);
  vector<ll> w_sum(N, 0);
  for (ll i = 0; i < N; ++i)
  {
    if (S[i] == 'W')
    {
      w_sum.at(i) += 1;
    }
    else
    {
      e_sum.at(i) += 1;
    }
  }
  for (ll i = 0; i < N - 1; ++i)
  {
    w_sum.at(i + 1) += w_sum.at(i);
    e_sum.at(i + 1) += e_sum.at(i);
  }
  ll e_num = e_sum.at(N - 1);
  ll ans = INF;
  for (ll i = 0; i < N; ++i)
  {
    if (i == 0)
    {
      ans = e_num - e_sum.at(0);
      continue;
    }
    ans = min(ans, w_sum.at(i - 1) + (e_num - e_sum.at(i)));
    // cout << ans << endl;
  }
  cout << ans << endl;
  // cout << e_num << e_sum.at(0) << endl;
}


Measured memory_bytes: 5380
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;

signed main(){
  int n;
  cin>>n;
  vector<int> c(n),s(n),f(n);
  REP(i,n-1)cin>>c[i]>>s[i]>>f[i];
  vector<int> ans(n);
  REP(i,n-1){
    int tmp=s[i]+c[i],cnt;
    LOOP(j,i+1,n-1){
      if(tmp>=s[j]){
        for(cnt=0;;cnt++){
          if((tmp+cnt)%f[j]==0)break;
        }
        tmp+=cnt+c[j];
      }else{
        tmp=s[j]+c[j];
      }
    }
    ans[i]=tmp;
  }
  ans[n-1]=0;
  REP(i,n)cout<<ans[i]<<endl;

  return 0;
}


Measured memory_bytes: 384
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
 
#[allow(non_snake_case, unused_variables)]
fn main() {
    let mut s: String = read();
    println!("{} {}", &s[0..4], &s[4..12]);
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

signed main()
{
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    A *= B;
    C *= D;
    printf("%lld\n", (A > C) ? A : C);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]

P = [-1]*n
for i, a in enumerate(A):
    P[a] = i

#print(P)

R = [[n]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in range(n):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            R[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(R)

L = [[-1]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in reversed(range(n)):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            L[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(L)
ans = 0
for i in range(n-1):
    p = P[i]
    l1 = L[i][0]
    l2 = L[i][1]
    r1 = R[i][0]
    r2 = R[i][1]
    ans += ((l1-l2)*(r1-p)+(r2-r1)*(p-l1))*(i+1)
print(ans)


Measured memory_bytes: 43632
#include <iostream>

using namespace std;

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

    int p[25];
    int pn = 0;
    for (int i = 2; i <= 100; i++) {
        bool f = true;
        for (int j = 0; j < pn; j++) {
            if (i % p[j] == 0) {
                f = false;
                break;
            }
        }

        if (f) {
            p[pn++] = i;
        }
    }

    int c2 = 0, c4 = 0, c14 = 0, c24 = 0, c74 = 0;
    for (int i = 0; i < pn; i++) {
        int c = 0, x = n;
        while (x) {
            x /= p[i];
            c += x;
        }

        if (c >= 2) {
            c2++;
        }
        if (c >= 4) {
            c4++;
        }
        if (c >= 14) {
            c14++;
        }
        if (c >= 24) {
            c24++;
        }
        if (c >= 74) {
            c74++;
        }
    }

    int ans = c4 * (c4 - 1) / 2 * (c2 - 2);
    ans += c14 * (c4 - 1);
    ans += c24 * (c2 - 1);
    ans += c74;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
from math import gcd
def main():
  n = int(input())
  a1 = int(n*(n+1)/2)
  a2 = 0
  for i in range(1,n):
    for j in range(i+1,n+1):
      a2 += gcd(i,j)
  a2 = a2*6
  a3 = 0
  for i in range(1,n-1):
    for j in range(i+1,n):
      for k in range(j+1,n+1):
        a3 += gcd(gcd(i,j),k)
  a3 = a3 * 6
  print(a1+a2+a3)
main()

Measured memory_bytes: 9200
def judge(A, x, k):
    ans = 0
    for a in A:
        ans += a // x
        if a % x == 0:
            ans -= 1
        if ans > k:
            return False
    return True

n, k = map(int, input().split())
A = list(map(int, input().split()))
l = 0
r = max(A)
while r - l != 1:
    x = (r + l) // 2
    if judge(A, x, k):
        r = x
    else:
        l = x
print(r)

Measured memory_bytes: 30784
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5;
struct PAIR{ll A,B;}seq[N+5];
bool cprPAIR(PAIR cprA,PAIR cprB){return cprA.B-cprA.A>cprB.B-cprB.A;}
int n;
ll ans,Min=ll(1e10);
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&seq[i].A,&seq[i].B),
		ans+=seq[i].A,
		Min=seq[i].A>seq[i].B? min(Min,seq[i].B):Min;
	if(Min==ll(1e10)) printf("0\n");
	else printf("%lld\n",ans-Min);
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
	long long int n, t, k;
	cin >> n >> k;
	if(n%k==0)cout << "0" << endl;
	else 
	{
		n=n%k;
		do{
			t=n;
			n=n-k;
			if(n<0)n=-n;
		}while(n<t);
		cout << t << endl;
	}
	
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#define WTF 12

using namespace std;

int n;
int q;
int v[1<<18], w[1<<18];
vector<pair<int, int>> dp[1<<WTF];

int fxxk(int x, vector<pair<int, int>>& brute_force) {
  if (x < (1 << WTF)) {
    return x;
  }
  int l = brute_force.size();
  for (int i = 0; i < l; i++) {
    brute_force.push_back({brute_force[i].first + w[x], brute_force[i].second + v[x]});
  }
  return fxxk(x/2, brute_force);
}

void solve(int u) {
    if (!dp[u].empty()) {
      return;
    }
    if (dp[u/2].empty()) {
      solve(u/2);
    }
    vector<pair<int, int>> wtf1, wtf2;
    for (pair<int, int> pii: dp[u/2]) {
      int ww = pii.first;
      int vv = pii.second;
      wtf1.push_back(pii);
      wtf2.push_back({ww + w[u], vv + v[u]});
    }
    int i = 0;
    int j = 0;
    while (true) {
      if (i == wtf1.size() && j == wtf2.size()) {
        break;
      } else if (i == wtf1.size()) {
        dp[u].push_back(wtf2[j++]);
      } else if (j == wtf2.size()) {
        dp[u].push_back(wtf1[i++]);
      } else if (wtf1[i] < wtf2[j]) {
        dp[u].push_back(wtf1[i++]);
      } else {
        dp[u].push_back(wtf2[j++]);
      }
    }
    for (int i = 1; i < dp[u].size(); i++) {
      if (dp[u][i].second < dp[u][i-1].second) {
        dp[u][i].second = dp[u][i-1].second;
      }
    }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &v[i], &w[i]);
  }
  dp[1].push_back({0, 0});
  dp[1].push_back({w[1], v[1]});
  for (int i = 1; i <= n && i < (1 << WTF); i++) {
    solve(i);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int u, l;
    scanf("%d %d", &u, &l);
    if (u < (1 << WTF)) {
      auto it = lower_bound(dp[u].begin(), dp[u].end(), make_pair(l+1, 0));
      if (it == dp[u].begin()) {
        printf("0\n");
      } else {
        printf("%d\n", (--it) -> second);
      }
    } else {
      vector<pair<int, int>> brute_force;
      brute_force.push_back({0, 0});
      brute_force.push_back({w[u], v[u]});
      int k = fxxk(u/2, brute_force);
      sort(brute_force.begin(), brute_force.end(), [] (auto x, auto y) {
        if (x.first == y.first) {
          return y.second < x.second;
        } else {
          return x.first < y.first;
        }
      });
      for (int j = 1; j < brute_force.size(); j++) {
        if (brute_force[j].second < brute_force[j-1].second) {
          brute_force[j].second = brute_force[j-1].second;
        }
      }
      int llllllll = brute_force.size();
      int p1 = dp[k].size() - 1;
      int p2 = 0;
      int ans = 0;
      while(p2 < llllllll && p1 >= 0) {
        if (dp[k][p1].first + brute_force[p2].first > l) {
          --p1;
        } else {
          ans = max(ans, dp[k][p1].second + brute_force[p2].second);
          ++p2;
        }
      }
      printf("%d\n", ans);
    }
  }
}


Measured memory_bytes: 92656
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  int sum, b;
  sum =0;
  b = 0;
  cin >> b >> a;
  for(int i=0;i<b-2;i++){
    if(a.at(i)=='A'&&a.at(i+1)=='B'&&a.at(i+2)=='C')
      sum=sum+1;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
using lint=long long;
using ld=long double;
template<class T>using numr=std::numeric_limits<T>;

lint mod=1'000'000'007;

lint inverse(lint x){/*{{{*/
    assert(x%mod);
    lint y=1,u=mod,v=0;
    while(x){lint q=u/x;u-=q*x;std::swap(u,x);v-=q*y;std::swap(v,y);}
    assert(x==0&&std::abs(u)==1&&std::abs(y)==mod&&std::abs(v)<mod);
    return v<0?v+mod:v;
}
lint normalized(lint x){if(x<=-mod||mod<=x)x%=mod;if(x<0)x+=mod;return x;}
struct mint{
    lint value;
    mint()=default;
    mint(lint x):value(normalized(x)){}
};
std::ostream&operator<<(std::ostream&os,mint x){return os<<x.value;}
mint operator+(mint x,mint y){lint z=x.value+y.value;if(mod<=z)z-=mod;return mint{z};}
mint operator-(mint x,mint y){lint z=x.value-y.value;if(z<0)z+=mod;return mint{z};}
mint operator*(mint x,mint y){return mint{x.value*y.value%mod};}
mint operator/(mint x,mint y){return mint{x.value*inverse(y.value)%mod};}
mint&operator+=(mint&x,mint y){return x=x+y;}
mint&operator-=(mint&x,mint y){return x=x-y;}
mint&operator*=(mint&x,mint y){return x=x*y;}
mint&operator/=(mint&x,mint y){return x=x/y;}
bool operator==(mint x,mint y){return x.value==y.value;}
bool operator!=(mint x,mint y){return x.value!=y.value;}
mint power(mint x,lint y){mint z=1;for(;y;y>>=1){if(y&1)z*=x;x*=x;}return z;}/*}}}*/

int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n;std::cin>>n;
    std::vector<std::vector<lint>>g(n);
    for(lint i=0;i<n-1;i++){
        lint u,v;std::cin>>u>>v;u--,v--;
        g.at(u).push_back(v);
        g.at(v).push_back(u);
    }
    using array=std::array<mint,2>;
    using moly=std::vector<array>;
    auto grow=[&](moly& a) {
        assert((!a.empty()&&a.at(0)==array{0,0}));
        for(lint j=0;j<2;j++){
            mint coeff=1;
            for(lint i=2;i<(lint)a.size();i+=2){
                a.at(0).at(!j)+=coeff*a.at(i).at(j);
                coeff*=i+1;
            }
        }
        return a;
    };
    auto shift=[&](moly& a){
        a.insert(a.begin(),{0,0});
    };
    auto mul=[&](moly const&a, moly const&b){
        lint l=a.size(),m=b.size();
        moly c(l+m-1);
        for(lint i0=0;i0<l;i0++){
        for(lint j0=0;j0<2;j0++){
        for(lint i1=0;i1<m;i1++){
        for(lint j1=0;j1<2;j1++){
            c.at(i0+i1).at((j0+j1)%2)+=a.at(i0).at(j0)*b.at(i1).at(j1);
        }}}}
        return c;
    };
    moly id={{1,0}};
    std::vector<moly>dp(n,id);
    auto dfs=[&](auto&&f,lint x,lint p)->void{
        for(lint y:g.at(x)){
            if(y==p)continue;
            f(f,y,x);
            dp.at(x)=mul(dp.at(x),dp.at(y));
        }
        shift(dp.at(x));
        grow(dp.at(x));
    };
    dfs(dfs,0,0);
    std::cout<<dp.at(0).at(0).at(1)-dp.at(0).at(0).at(0)<<'\n';
}


Measured memory_bytes: 277760
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<f64> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut dp: Vec<f64> = vec![0.0; n + 1];
    dp[0] = 1.0;
    for i in 0..n {
        for omote in (0..i + 1).rev() {
            dp[omote + 1] += dp[omote] * a[i];
            dp[omote] = dp[omote] * (1.0 - a[i]);
        }
    }

    let mut ans: f64 = 0.0;
    for omote in 0..n + 1 {
        if omote > (n - omote) {
            ans += dp[omote];
        }
    }
    println!("{:.10}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long ll;

const int MOD = 998244353;

int K, N;
ll C[4001][4001];

ll solve(int t) {
	int a = max(1, t - K);
	int b = t / 2;
	int cnt = b - a + 1;
	ll res = C[N + K - 1][K - 1];
	for (int i = 1; i <= cnt; i++) {
		int s = (i % 2 == 1) ? -1 : 1;
		if (2 * i <= N) {
			ll add = (((s * C[cnt][i]) % MOD) * C[N - 2 * i + K - 1][K - 1]) % MOD;
			res = (res + add) % MOD;
		}
	}
	return (res + MOD) % MOD;
}

int main() {
	scanf("%d %d", &K, &N);
	C[0][0] = 1;
	for (int i = 1; i <= 4000; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	for (int t = 2; t <= 2 * K; t++) {
		printf("%lld\n", solve(t));
	}
	return 0;
}


Measured memory_bytes: 123520
def stair(n) :
    if n == 1 :
        return 1
    elif n == 2 :
        return 2
    elif n == 3 :
        return 4
    elif n == 4 :
        return 7
    elif n == 5 :
        return 13
    elif n == 6 :
        return 24
    elif n == 7 :
        return 44
    elif n == 8 :
        return 81
    else :
        return stair(n-1)+stair(n-2)+stair(n-3)

while True :
    n = int(input())
    if n == 0 :
        break
    kaisu = stair(n)
    if kaisu % 10 == 0 :
        day = kaisu // 10
    else :
        day = kaisu // 10 + 1
    if day % 365 == 0 :
        year = day // 365
    else :
        year = day // 365 + 1
    print(year)



Measured memory_bytes: 5588