akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll a,c=0;
    cin>>a;
    for(int i=1;i<=a;i+=2){
        ll b=0;
        for(int j=1;j<=i;j++){
            if(i%j==0) b++;
        }
        if(b==8) c++;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	Main m = new Main();
	m.answer();
    }

    private Scanner scan = new Scanner(System.in);
    private final int N;

    public Main() {
	N = Integer.parseInt(scan.next());

	scan.close();
    }

    public final void answer() {
	int[] result = new int[N+1];
	for (int i = 1; i <= N; i++) {
	    int n = i;
	    while(n % 2 == 0) {
		result[i]++;
		n = n / 2;
	    }
	}
	int ans = 1;
	int max = 0;
	for (int i = 1; i <= N; i++) {
	    if(result[i] > max) {
		max = result[i];
		ans = i;
	    }
	}
	System.out.println(ans);
    }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
#define all(a) a.begin(), a.end()

const int MOD = 1e9+7;
const int INF = 1001001001;

int H, W;
char maze[50][50];

int bfs(int sx, int sy, int gx, int gy){
    int dist[50][50];
    fill(dist[0], dist[50], INF);
    dist[sx][sy] = 1;
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    deque<pii> q;
    q.emplace_back(sx, sy);
    while (!q.empty()){
        pii xy = q.front();
        int x = xy.first;
        int y = xy.second;
        q.pop_front();
        if (x == gx && y == gy){
            return dist[x][y];
        }
        rep(i, 0, 4){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < H && 0 <= ny && ny < W && dist[nx][ny] == INF && maze[nx][ny] == '.'){
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace_back(nx, ny);
            }
        }
    }
    return -1;
}

int main(){
    cin >> H >> W;
    int cnt = 0;
    rep(x, 0, H){
        rep(y, 0, W){
            cin >> maze[x][y];
            if (maze[x][y] == '.'){
                cnt++;
            }
        }
    }
    int num = bfs(0, 0, H-1, W-1);
    int ans = (num != -1) ? cnt-num : -1;
    cout << ans << endl;
}

Measured memory_bytes: 3636
from heapq import heappush, heappop
import math
def dijkstra(N, G, s):
    dist = [math.inf] * N
    que = [(0,s)]
    dist[s] = 0
    ans = [[] for i in range(N)]
    while que:
        c,v = heappop(que)
        if dist[v] < c:
            
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que,(dist[t],t))
    return dist
n = int(input())

g = [[]for i in range(n)]
for i in range(n):
    nums=list(map(int,input().split()))
    node=nums[0]
    for j in range(nums[1]):
        t=nums[j*2+2]
        c=nums[j*2+3]
        g[node].append([t,c])
   
ans = dijkstra(n,g,0)
for i in range(n):
    print(f'{i} {ans[i]}')

        



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

#define llint long long int

using namespace std;

int main()
{
    string S, T;

    cin >> S >> T;

    int min = T.length();

    for (int i = 0; i < S.length() - T.length() + 1; i++)
    {
        int count = 0;

        for (int j = 0; j < T.length(); j++)
        {
            if (S[i + j] != T[j])
            {
                count++;
            }
        }
        if (count < min)
        {
            min = count;
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 3600
import java.util.*

fun main(args: Array<String>) {
    val list: List<Int> = readLine()!!.split(" ").map { it.toInt() }

    val A = list[0].toDouble() / 0.08
    val A2 = (list[0] + 1 ).toDouble() / 0.08
    val B = list[1].toDouble() / 0.10
    val B2 = (list[1] + 1 ).toDouble()/ 0.10

    when{
        A <= B && B < A2 -> print(Math.round(B).toInt())
        B <= A && A < B2 -> print(Math.round(A).toInt())
        else -> print("-1")
    }
}

Measured memory_bytes: 37948
#include<stdio.h>
#define LENGTH 20

int main() {
	int p[LENGTH];
	int n;
	int result;
	int i;
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &p[i]);
	}
	for (i = 0; i < n - 2; i++) {
		if ((p[i + 1] < p[i] && p[i + 1]> p[i + 2]) || (p[i + 1] > p[i] && p[i + 1] < p[i + 2]))
			result++;
	}
	printf("%d", result);
}

Measured memory_bytes: 128
#define q(x,y)(f[x]*h[y]%m*h[(x)-(y)]%m)
long long H,W,A,B,i=2,f[1<<18],g[1<<18],h[1<<18],r,z=2e5,m=1e9+7;
main(){
for(f[0]=f[1]=g[1]=1;i<z;i++)f[i]=f[i-1]*i%m,g[i]=g[m%i]*(m-m/i)%m;
for(h[0]=i=1;i<z;i++)h[i]=h[i-1]*g[i]%m;
for(scanf("%d%d%d%d",&H,&W,&A,&B),i=0;i<W-B;i++)r=(r+q(A+i-1,i)*q(W-i+H-A-2,H-A-1))%m;
i=!printf("%d\n",r);
}

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

using namespace std;

const int INF = 1000000000;
const int MAX_V = 5003;
int cost[MAX_V][MAX_V];
int cosn[5003][5003];
int d[MAX_V];
bool used[MAX_V];
int V;
int s[5003][2];
vector<int> vec[5003];

void dijkstra(int s){
	fill(d,d+V+1,INF);
	fill(used,used+V+1,false);
	d[s] = 0;
	while(true){
		int v = -1;
		for(int u = 1;u <= V;u++){
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		if(v == -1)break;
		used[v] = true;
		for(int u = 1;u <= V;u++){
			d[u] = min(d[u],d[v]+cost[v][u]);
		}
	}
}

void dfs(int from,int to,int nau){
	cost[from][to] = s[from][0];
	cosn[from][to] = nau;
	if(nau == s[from][1])return;
	for(int i = 0;i < vec[to].size();i++){
		int ne = vec[to][i];
		if(cost[from][ne] == INF || cosn[from][ne] > nau+1){
			dfs(from,ne,nau+1);
		}
	}
}

int main(){

	int k;
	cin >> V >> k;
	for(int i = 0;i <= V;i++){
		for(int j = 0;j <= V;j++){
			cost[i][j] = INF;
			cosn[i][j] = INF;
		}
	}
	for(int i = 1;i <= V;i++)cin >> s[i][0] >> s[i][1];

	for(int i = 0;i < k;i++){
		int a,b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for(int i = 1;i <= V;i++){
		for(int j = 0;j < vec[i].size();j++){
			int ne = vec[i][j];
			dfs(i,ne,1);
		}
	}
	dijkstra(1);
	cout << d[V] << endl;
	for(int i = 1;i <= V;i++){
//		cout << d[i] << endl;
	}
	for(int i = 1;i <= V;i++){
		for(int j = 1;j <= V;j++){
//			cout << cost[i][j] << " ";
		}
//		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 197112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){
        a=b;
        return true;
    }
    return false;
}

int main(){
    ll N;
    cin >> N;
    vector<ll> L(N);
    vector<ll> count(1001,0);
    rep(i,N){
        cin >> L[i];
        count[L[i]]++;
    }
    rep(i,1000){
        count[i+1]+=count[i];
    }
    sort(L.begin(),L.end());
    reverse(L.begin(),L.end());
    ll ans=0;
    rep(i,N){
        rep2(j,i+1,N){
            if (L[j]*2>L[i]){
                ans+=N-j-1-count[L[i]-L[j]];
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
 
#define mod(cans) cans%10**9+7
#define debug(x) cout << "Debug" << x << "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define cin_pl(n,x) rep(i,n){cin>>x[i];}
#define cins(s,n) rep(i,n)cin>>s.at[i];
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define prians(Answer) cout<<Answer<<"\n"
#define TF(X) X==1?cout<<"Yes\n":cout<<"No\n"
#define elcon else{continue;}
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vector<int> > matrix;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
typedef greater<int> gi;
typedef vector<unsigned> vu;


ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
bool is_prime(const unsigned n){
    switch(n){
        case 0:
        case 1: return false;
        case 2: return true;
    }
 
 
    for(unsigned i=2;i<n;++i){
        if(n%i == 0) return false;
    }
 
    return true;
}
 


int main()
{
    int a,b;cin>>a>>b;
    cout<<a*b;
    



    
}

Measured memory_bytes: 3636
//2018-1-18
//miaomiao
//
#include <bits/stdc++.h>
using namespace std;

#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)

#define M 18
#define N (200000+5)

int n, m, dn, pos[N], dis[M], nxt[N][M], beg[N], endd[N];
int f[1<<M];

bool Solve(int l, int r){
	if(l == 1 && r == n) return true;

	f[0] = 0;
	
	int tmp;
	For(i, 1, (1<<dn)-1){
		f[i] = 0;
		For(j, 1, dn) if(i & (1<<(j-1))){
			tmp = f[i ^ (1<<(j-1))] + 1;
			if(tmp >= l && tmp <= r) tmp = r+1;

			f[i] = max(f[i], nxt[tmp][j]);
			if(f[i]+1 >= l && f[i]+1 <= r) f[i] = r;
		}
		if(f[i] >= n) return true;
	}
	return false;
}

int main(){
	scanf("%d%d", &n, &m);
	For(i, 1, n) scanf("%d", &pos[i]);
	
	int st, ed, cnt = 0;
	for(int d = m; d >= 0; d >>= 1){
		st = 1; if(d != m) dis[++dn] = d;

		while(st <= n){
			ed = st;
			while(ed < n && pos[ed+1]-pos[ed] <= d) ++ed;
			For(i, st, ed) nxt[i][dn] = ed;
			
			if(d == m){
				beg[++cnt] = st; endd[cnt] = ed;
			}
			st = ed+1;
		}

		if(!d) break;
	}

	For(i, 1, dn) nxt[n+1][i] = n+1;
//	For(i, 1, n) For(j, 1, dn) printf("nxt[%d][%d] = %d\n", i, j, nxt[i][j]);

	if(cnt > dn+1){
		For(i, 1, n) puts("Impossible"); return 0;
	}

	For(si, 1, cnt){
	//	printf("%d -> %d free\n", beg[si], end[si]);
		if(Solve(beg[si], endd[si])){
			For(i, beg[si], endd[si]) puts("Possible");
		}else{
			For(i, beg[si], endd[si]) puts("Impossible"); 
		}
	}
	
	return 0;
}

Measured memory_bytes: 18816
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<k;i++)
int n;int S[100000];
int binarysearch(int key){
    int left=0,right=n;
    while(left<right){
        int mid=(left+right)/2;
        if(S[mid]==key)return 1;
        else if(S[mid]<key)left=mid+1;
        else right=mid;
    }
    return 0;
}
int main(){
    int q,ans=0,x;
    cin>>n;
    rep(i,0,n)cin>>S[i];
    cin>>q;
    rep(i,0,q){
        cin>>x;
        if(binarysearch(x))ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;

template <typename T>std::string NumberToString ( T Number ){std::ostringstream ss; ss << Number;return ss.str(); }

int main(){

   ios::sync_with_stdio(0);
   cin.tie(0);

   // freopen ("input.txt", "r", stdin);
   
   long long int n;

   cin >> n;

   long long int coins500 = n/500;
   long long int remain = n - (coins500 * 500) ;
   long long int coins5 = remain/5;
   cout << (coins5 * 5 + coins500 * 1000) << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <iomanip>
#include <utility>
#include <cmath>

int main(){
    using Coord = std::pair<double, double>;
    uint num_city;
    std::cin >> num_city;
    std::vector<Coord> cities;
    for (uint i = 0; i < num_city; i++){
        double x, y;
        std::cin >> x >> y;
        cities.push_back(Coord(x, y));
    }
    double mean_dist = 0;
    for (uint i = 0; i < num_city - 1; i++){
        for (uint j = i + 1; j < num_city; j++){
            double x_diff = cities.at(i).first - cities.at(j).first;
            double y_diff = cities.at(i).second - cities.at(j).second;
            mean_dist += std::sqrt(x_diff * x_diff + y_diff * y_diff) / num_city;
        }
    }
    mean_dist *= 2;
    std::cout << std::fixed << std::setprecision(6) << mean_dist << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <set>
#include <math.h>
#define pai arccos(-1);
#define keta(n) cout << fixed << setprecision((n));
#define ll long long;
int main()
{
  int n,a;
  cin>>n>>a;
  if(n%500>a)cout<<"No";
  else cout<<"Yes";
 
}


Measured memory_bytes: 256
/*       Don't try to hack it :|

            _/﹋\_
            (҂`_´)
            <,︻╦╤─҉- - - - - - - - - - - - - - -
            _/﹋\_
*/
//@Yuvraj Garg

#include <bits/stdc++.h>

#define ull unsigned long long int
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define itr vi:iterator
#define vpll vector < pair<long long,long long> >
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define pdd pair<double, double>
#define retrun return // Bcoz of typing error :(
#define foo() cout << "Err\n"

#define rep(i, n)    for(ll i = 0; i < (n); ++i)
#define repA(i, a, n)  for(ll i = a; i <= (n); ++i)
#define repD(i, a, n)  for(ll i = a; i >= (n); --i)

using namespace std;  

void solve(int t){
    int n;
    cin >> n;
    vi v(n);
    int count = 0;
    rep(i, n) cin >> v[i];
    sort(all(v));
    cout << v[n/2]-v[n/2-1];
}

int main(){

    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    int t, tmp = 0;
    // cin >> t;
    t = 1;
    while(tmp++ < t){
        solve(tmp-1);
        // cout << "\n";        
    }
    // cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cstdlib>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <bitset>
#define ll long long
using namespace std;


int main(){//cout<<1<<endl;
  ll A,B,K;
  cin>>K>>A>>B;
  if(A+2>=B){
    cout<<K+1<<endl;
    return 0;
  }
  ll kukki=1;
  ll money=0;
  for(int i=0;i<K;i++){
    //cout<<money<<" "<<kukki<<endl;
    if(money==1){
      money=0;kukki += B;
      continue;
    }
    
    if(kukki < A) {
      kukki++;
      continue;
    }
    
    if(kukki >=A and i<=K-2 ) {
      money++;kukki = kukki-A;continue;
    }
    
    kukki++;
    
  }
  
  cout<<kukki<<endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define MAX 100
int is[MAX];
int main(void) {
	string s;
	cin >> s;
	int c = 0, res = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == 'S') {
			++c;
		}
		else {
			if (c > 0) {
				--c;
				++res;
			}
		}
	}
	cout << s.length() - res*2 << endl;
	return 0;

}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, x;
  cin >> n >> x;
  int m[n];
  for(int i=0; i<n; ++i){
    cin >> m[i];
    x -= m[i];
  }
  sort(m, m+n);
  cout << n+x/m[0] << endl;
}

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

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()

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

  ll N,D;
  ll ans = 0;

  cin >> N >> D;

  ans = (ll)ceil((double)N/(2*D+1));

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
 
#define rp(i, k, n) for (int i = k; i < n; i++)
using ll = long long;
using ld = double;

template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7ll;
// const ll MOD = 998244353;
const double PI=3.14159265358979323846;



int main() {
    int n; cin >> n;
    int m; cin >> m;
    vector<int> A(n+10);
    rp(i, 0, n) {
        int a; cin >> a;
        A[i+1] = (A[i] + a) % m;
    }
    ll res = 0;
    map<int, int> cnt;
    cnt[0] = 1;
    rp(i, 0, n) {
        int a = A[i+1];
        if(cnt.find(a) == cnt.end()) cnt[a] = 1;
        else {
            res += cnt[a];
            cnt[a]++;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 6624
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int n,a[110],b[110];
string s;

int main(){
	while(cin>>n&&n){
		cin>>s;
		rep(i,n)cin>>a[i]>>b[i],a[i]--,b[i]--;
		for(int i=n-1;i>=0;i--){
			int x=b[i]-a[i];
			s[a[i]]='a'+(s[a[i]]-'a'+x)%26;
			s[b[i]]='a'+(s[b[i]]-'a'+x)%26;
			swap(s[a[i]],s[b[i]]);
		}
		cout<<s<<endl;
	}
}

Measured memory_bytes: 0
#include <stdio.h>

int main()
{
	int i, N, Q, A, B, C, count[100001] = {};
	long long sum = 0;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d", &A);
		count[A]++;
		sum += A;
	}
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%d %d", &B, &C);
		sum += (long long)(C - B) * count[B];
		count[C] += count[B];
		count[B] = 0;
		printf("%lld\n", sum);
	}
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2072
#include<bits/stdc++.h>
    using namespace std;
     
    #define ll long long
    vector<ll>height,dp,b;
    vector<ll>tree;
    
    void treeupdate(int indx,int s,int  e,int updi,ll upd ){
        if(s==e) {
            tree[indx]=upd;
            
        }
        else{
            int mid=(s+e)/2;
            int le=2*indx,ri=le+1;
            if(updi<=mid) treeupdate(le,s,mid,updi,upd);
            else treeupdate(ri,mid+1,e,updi,upd);
            tree[indx]=max(tree[le],tree[ri]);
        }
    }
    // void treeupdate(int idx, int L, int R, int ii, ll upd)
    // {
    // 	if(L == R)
    // 	{
    // 		tree[idx] = upd;
    // 		return;
    // 	}
    // 	int le = 2*idx + 1, ri = le + 1, mid = (L + R) / 2;
    // 	if(ii <= mid)
    // 		treeupdate(le, L, mid, ii, upd);
    // 	else treeupdate(ri, mid + 1, R, ii, upd);
    // 	//
    // 	tree[idx] = max(tree[le], tree[ri]);
    // }
    ll treemax(int ind,int l,int r,int ql,int qr){
        if(ql>r||qr<l) return 0;
        if(ql<=l&&qr>=r) return tree[ind];
        else{
            int mid=(l+r)/2;
            return max(treemax(2*ind,l,mid,ql,qr),treemax(2*ind+1,mid+1,r,ql,qr));
        }
    }
    // ll treemax(int idx, int L, int R, int QL, int QR)
    // {
    // 	if(L >= QL && R <= QR)
    // 	{
    // 		return tree[idx];
    // 	}
    // 	if(L > QR || R < QL)
    // 		return 0;
    // 	int le = 2*idx + 1, ri = le + 1, mid = (L + R) / 2;
    // 	ll a1 = treemax(le, L, mid, QL, QR);
    // 	ll a2 = treemax(ri, mid + 1, R, QL, QR);
    // 	//
    // 	return max(a1, a2);
    // }
    long long findbase(long long k){
        long long ans=0;
        
        while(k){
             k=k>>1;
            ans++;
        }
        return ans;
    }
    int main(){
        ll n;
        cin>>n;
        height.resize(n);
        dp.resize(n);
        b.resize(n);
        // cout<<findbase(n);
        tree.resize(int(2e5 + 2)<<2);
        // tree.resize(100);
        for(int i=0;i<n;i++){
            cin>>height[i];
        }
        for(int i=0;i<n;i++){
            cin>>b[i];
            // dp[i]=b[i];
        }
        for(int i=0;i<n;i++){
            dp[i]=(height[i]>1)?(treemax(1,1,n,1,height[i]-1)+b[i]):b[i];
            treeupdate(1,1,n,height[i],dp[i]);
            // cout<<dp[i]<<"X";
        }
        ll ans=0;
        for(int i=0;i<dp.size();i++){
        //   cout<<tree[i];
            ans=max(ans,dp[i]);
        }
        cout<<ans;
        
        // cout<<treemax(0);
        return 0;
    }

Measured memory_bytes: 11136
def d_equals(N, M, P, S):
    class UnionFind(object):
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の親(parent)はi番
            self.rank = [0] * N  # 初期状態では全頂点がランク0(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):  # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    p = [0] + P
    ans = 0
    uf = UnionFind(N + 1)
    for a, b in S:
        uf.union(a, b)  # Pのa番とb番は繋がっている
    for i in range(1, N + 1):
        if uf.is_same(p[i], i):
            # 2つが同じ連結成分に属するなら何回かswapしてp_i=iにできる
            # 最初からp_i=iの場合、unionしてなくてもこの条件は成立
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(M)]
print(d_equals(N, M, P, S))

Measured memory_bytes: 31436
#include<iostream>
#include<cstdio>
using namespace std;
int main(){

  int cards[4][14]={0};

  int n;
 
  cin>>n;

  int a,r;

  char c;

  
  for(int i=0;i<n;i++){
    cin>>c>>r;

    if(c=='S')a=0;
    if(c=='H')a=1;
    if(c=='C')a=2;
    if(c=='D')a=3;

    cards[a][r]=1;
  
  }
  char egara[4]={'S','H','C','D'};


  for(int i=0;i<4;i++){
    for(int j=1;j<14;j++){

      if(cards[i][j]==0){
	cout<<egara[i]<<" "<<j<<endl;
      }
    }
  }



  return 0;
}

Measured memory_bytes: 3032
n,t = list(map(int, input().split()))
lst = list(map(int, input().split()))
dif = [None for i in range(n-1)]
for i in range(n-1):
    dif[i] = lst[i+1]-lst[i]

ans = 0
for i in range(n-1):
    ans += min(t,dif[i])
ans += t

print(ans)


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

int main(){
  ll a,b,c,k;
  cin>>a>>b>>c>>k;
  ll ans=0;
  if(a>k){
    ans=k;
  }
   else if(a+b>=k){
   ans=a;
  }
  else {
   ans=(2*a)+b-k;
  }
  cout<<ans<<endl;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> t(n), x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> x[i] >> y[i];
	}
	for (int i = n - 1; i >= 1; i--) {
		t[i] -= t[i - 1];
		x[i] -= x[i - 1];
		y[i] -= y[i - 1];
	}
	bool r = true;
	for (int i = 0; i < n; i++) {
		r &= t[i] >= abs(x[i]) + abs(y[i]) && t[i] % 2 == (abs(x[i]) + abs(y[i])) % 2;
	}
	cout << (r ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 1408
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        var a = sc.NextChar();
        var b = sc.NextChar();

        int aa = int.Parse(new string(a, b - '0'));
        int bb = int.Parse(new string(b, a - '0'));
        Console.WriteLine(Math.Max(aa, bb));
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 11220
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<set>
#include <valarray>
#include<stack>

using namespace std;

void Solution()
{
    int w,h;
    
    while(cin>>h>>w, h)
    {
        int f[h][w + 1];
        
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w+1; j++)
            {
                if(j == w)
                {
                    f[i][j] = 0;
                    continue;
                }
                
                char t;
                
                cin>>t;
                
                if(i == 0)
                {
                    if(t == '*')
                    {
                        f[i][j]=0;
                    }
                    else
                    {
                        f[i][j]=1;
                    }
                }
                else
                {
                    if(t == '*')
                    {
                        f[i][j] = 0;
                    }
                    else
                    {
                        f[i][j] = f[i - 1][j] + 1;
                    }
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < h; i++)
        {
            stack<int> pos,height;
            
            for(int j = 0; j < w + 1; j++)
            {
                if(pos.empty())
                {
                    pos.push(j);
                    height.push(f[i][j]);
                }
                else if(height.top()<f[i][j])
                {
                    pos.push(j);
                    height.push(f[i][j]);
                }
                else if(height.top()>f[i][j])
                {
                    int he,p;
                    while(!height.empty() && height.top() > f[i][j])
                    {
                        p=pos.top();
                        pos.pop();
                        
                        he=height.top();
                        height.pop();
                        
                        ans=max(ans,he*(j-p));
                    }
                    
                    height.push(f[i][j]);
                    pos.push(p);
                }
            }
        }
        cout<<ans<<endl;
    }
    
}

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

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

int numofdigits(long long x) {
  int cnt = 0;
  while (x > 0) {
    x /= 10;
    cnt++;
  }
  return cnt;
}

int main() {
  long long N;
  cin >> N;

  int ans = -100;
  for (long long i = 1; i * i <= N; i++) {
    if (N % i != 0) continue;
    long long j = N / i;
    ans = max(numofdigits(i), numofdigits(j));
  }

  cout << ans << endl;
}

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

int main() {

  int N;
  cin>>N;
  int a[N], count = 0, com = 1000000000;
  
  for(int i = 0; i < N; i++) {
    cin>>a[i];
    if(com < a[i]) count++;
    com = a[i];
  }

  cout<<count<<endl;

  return 0;
}



Measured memory_bytes: 3476
def main():
    n = int(input())
    a = list(map(int, input().split()))
    neg = []
    pos = []
    for v in a:
        if v < 0:
            neg.append(v)
        else:
            pos.append(v)
    ans = []
    neg.sort()
    x, y = 0, len(neg)-1
    if len(pos) == 0:
        ans.append([neg[y], neg[x]])
        p = neg[y] - neg[x]
        pos.append(p)
        x += 1
        y -= 1
    for i in range(x, y):
        ans.append([pos[0], neg[i]])
        pos[0] -= neg[i]
    if y-x+1 > 0:
        pos.append(neg[y])
    pos.sort()
    for i in range(len(pos)-2):
        ans.append([pos[i], pos[i+1]])
        pos[i+1] = pos[i] - pos[i+1]
    if len(pos) > 1:
        ans.append([pos[len(pos)-1], pos[len(pos)-2]])
        pos[len(pos)-1] = pos[len(pos)-1] - pos[len(pos)-2]
    print(pos[len(pos)-1])
    for p, q in ans:
        print(p, q)

if __name__ == "__main__":
    main()


Measured memory_bytes: 23260
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
# @lru_cache(None)






h,w=l()
A=[input() for i in range(h)]
ans=0
for i in range(h):
    for j  in  range(w):
        if(A[i][j]=="#"):
            ans+=1



if ans==h+w-1:
    print("Possible")
else:
    print("Impossible")

Measured memory_bytes: 5124
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

#define FOR(i, s, e) for(int i=s; i<e; i++)
#define REF(i, s, e) for(int i=s; i>e; i--)
typedef long long ll;

int n, k;
string s;
vector<int> nums01;


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

	cin >> n >> k;
	cin >> s;

	//先頭、末尾"0"なら0を入れる(両端を1の個数にするため)
	if (s[0] == '0') nums01.push_back(0);
	for (int i = 0; i < s.size();) {
		
		int end_i = i;
		//cout << end_i << endl;
		//s[i]と同じ数字が何個つづくか
		while (end_i < s.size() && s[end_i] == s[i]) end_i++;
		nums01.push_back(end_i - i);
		i = end_i;

	}
	if (s.back() == '0') nums01.push_back(0);

	//nums01: 0,2,4...に1の連続数、1,3,5...に0の連続数を格納
	//cout << "nums01:" << endl;
	//FOR(i, 0, nums01.size()) cout << nums01[i] << endl;

	//累積和: sums[0]は0
	vector<int> sums(nums01.size()+1, 0);
	FOR(i, 0, nums01.size()) sums[i+1] = sums[i] + nums01[i];

	//cout << "sums:" << endl;
	//FOR(i, 0, sums.size()) cout << sums[i] << endl;

	//cout << "res:" << endl;
	//nums01の2k+1個以下の要素の合計値計算
	int res = 0;
	for (int left = 0; left < sums.size(); left += 2) {
		int right = left + 2 * k + 1;
		if (right >= sums.size()) right = sums.size() - 1;

		//cout << left << ", " << right << endl;		
		//cout << sums[right] - sums[left] << endl;
		res = max(res, sums[right] - sums[left]);
	}
	cout << res << endl;

}

Measured memory_bytes: 1272
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int A = sc.nextInt();
			final int B = sc.nextInt();
			
			System.out.println(Math.max(0, A - 2 * B));
		}
	}

	public static class Scanner implements Closeable {
		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());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl

#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define gap cout<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())



int main(){
    int n;
    string s;
    int q;
    cin>>n;
    cin>>s;
    cin>>q;
    map<char,set<int>> mp;
    fo(i,n){
        mp[s[i]-'a'].insert(i+1);
    }
    char tmp;
    int l,r;
    int index;
    int what;
    fo(i,q){
        cin>>what;
        if(what==1){
            cin>>index>>tmp;
            fo(i,26){
                
                auto it=mp[i].lower_bound(index);
                if(it==mp[i].end()) continue;
                int tm1=*it;
                if(tm1==index) mp[i].erase(index);
               
                
            }

            mp[tmp-'a'].insert(index);

        }
        if(what==2){
            cin>>l>>r;
            int ans=0;
            fo(i,26){
                
                auto it=mp[i].lower_bound(l);
                if(it==mp[i].end()) continue;
                int tm1=*it;
                if(tm1<=r) ans++;
               
                
            }
            cout<<ans<<endl;
        }

    }
    
}

Measured memory_bytes: 26244
from collections import deque
K = int(input())
Q = deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    x = Q.popleft()
    if x%10!=0:
        Q.append(10*x + x%10 - 1)
    Q.append(10*x + x%10)
    if x%10!=9:
        Q.append(10*x + x%10 + 1)
print(x)

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

bool isPalindrome(int x){
    if(x%10 == x/10000 && (x%10000 - x%1000)/1000 == (x%100 - x%10)/10){
        return true;
    }
    return false;
}
int main(){
    int a, b, cnt;
    cin >> a >> b;
    cnt = 0;
    for(int i=a; i<=b; i++){
        if(isPalindrome(i)){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
# 部分点

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    n = int(input())
    *x, r = map(int, input().split())

    dist_to_r_edge = [r - x_ for x_ in x]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )

    f = 1
    for i in range(1, n):
        f = (f * i) % MOD

    print(ret * f % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 66456
#include<bits/stdc++.h>
#define debug1 cout<<"?"<<endl;
#define debug2 cout<<"?"<<i<<endl;
#define PII pair<int,int>
typedef long long ll;
const int maxn=2e5+9;
const double pi=acos(-1);
const int mod=1e9+7;
const int INF=1e9;
const double ep=1e-7;
using namespace std;
ll n,m,a[maxn];
bool check(ll x)
{
	ll cnt=0;
	for(ll i=n;i>=1;i--)
	{
		ll num=x-a[i];
		ll k=lower_bound(a+1,a+1+n,num)-a;
		if(k>i)return 0;
		cnt=cnt+(i-k)*2+1;
		if(cnt>=m)return 1;
	}
	return 0;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	ll l=1,r=1e10,num=0,sum[maxn]={0};
	for(ll i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid))l=mid+1,num=mid;
		else r=mid-1;
	}
	ll ans=0,cnt=0;
	for(ll i=1;i<=n;i++)
	{
		ll num1=num-a[i]+1;
		ll k=lower_bound(a+1,a+1+n,num1)-a;
		if(k>n)continue;
		if(k<=i)ans=ans+(sum[n]-sum[i])*2+a[i]*(n-i+1)*2,cnt=cnt+(n-i)*2+1;
		else ans=ans+(sum[n]-sum[k-1])*2+a[i]*(n-k+1)*2,cnt=cnt+(n-k+1)*2;
	}
	ans=ans+num*(m-cnt);
	printf("%lld\n",ans);
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)


int main(){

    int a;
    cin >> a >> a;
    string s;
    while(cin>>s){
        cout << s << "\n"
             << s << endl;
    }

    return 0;
}

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

int main(){
    int n,x,t;
    cin >> n >> x >> t;
    int ans;

    ans=(n/x)*t;
    if(n%x!=0){
        ans+=t;
    }
    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <numeric>
#include <set>
#include <unordered_set>
#include <queue>
#include <boost/math/constants/constants.hpp>
#include <boost/math/common_factor_rt.hpp>
 
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, n, m) for(int i=n; i<m; ++i)
 
int main() {
  ll N;
  cin >> N;

  ll sum = 0;
  
  rep(i,N+1){
    if(i%3!=0 && i%5!=0){
      sum+=i;
    }
  }
  
  cout << sum << endl;
  
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<stdlib.h>
   
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef node* Node;
#define NIL NULL
  
node array[500000];
int size=0;
  
Node root = NIL;
   
Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
}
   
Node treeSearch(Node u, int k){
  Node i=u;
  while(i!=NIL){
    if(i->key==k)return i;
    else if(i->key<k)i=i->right;
    else i=i->left;    
  }
  return NIL;
}
   
Node treeSuccessor(Node x){
  if(x->right!=NIL)return treeMinimum(x->right);
  Node y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}
   
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL||z->right==NIL)y=z;
  else y=treeSuccessor(z);
     
  if(y->left!=NIL)x=y->left;
  else x=y->right;
   
  if(x!=NIL)x->parent=y->parent;
     
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent->left=x;
  else y->parent->right=x;
   
  if(y!=z)z->key=y->key;
     
  //free(y);
}
   
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
   
  z = &array[size++];
  z->key = k;
  z->left = NIL;
  z->right = NIL;
   
  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;  
}
  
  
void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
  
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
  
  
int main(){
  int n,x;
  char str[20];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s", str);
    if(str[0]=='f'){
      scanf("%d",&x);
      Node t=treeSearch(root,x);
      if (t!=NIL) printf("yes\n");
      else printf("no\n");
    }else if(str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }else if(str[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(str[0]=='d'){
      scanf("%d",&x);
      treeDelete(treeSearch(root,x));
    }
  }
  
  return 0;
}


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

int main() {
	int N;
	long long ans = 0, A = 0, B = 0, BA = 0;
	string S[10000];
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
		if (S[i][0] == 'B' && S[i][S[i].size() - 1] == 'A') BA++;
		else if (S[i][0] == 'B') B++;
		else if (S[i][S[i].size() - 1] == 'A') A++;
		for (int j = 0; j < S[i].size() - 1; j++) {
			if (S[i].substr(j, 2) == "AB") ans++;
		}
	}
	if (BA > 0) {
		if (A == 0 && B == 0) {
			cout << ans + BA - 1;
			return 0;
		}
		ans += BA - 1;
		B++, A++;
		N -= (BA - 1);
	}
	if (N == B || N == A) ans += min(min(A, B), max(A, B) - 1);
	else ans += min(A, B);
	cout << ans;
}

Measured memory_bytes: 768
/*30人の受講生がいて各受講生には1番から30番までの出席番号がふられている．この授業の課題を28人の学生が提出した．
提出した28人の出席番号から提出していない2人の出席番号を求めるプログラムを作成せよ.*/
#include<iostream>
using namespace std;
int main(){
    int a[31];
    for(int i=1;i<31;i++){
       a[i]=i;
    }
    for(int i=0;i<31;i++){
       int s;
       cin>>s;
       for(int j=1;j<31;j++){
          if(a[j]==s){
            a[j]=0;
          }
       }
    }
    for(int i=1;i<31;i++){
       if(a[i]==0){}
       else{
         cout<<a[i]<<endl;
       }
    }
}


Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
#include<assert.h>
#include<random>
using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve(void)
{
  int H,W,K;
  cin>>H>>W>>K;
  // vector<vector<char> > vv (H,vector<char>(W,0));
  vector<vector<int> > data (H,vector<int>(W,0));  
  int cnt = 0;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      char X;cin>>X;
      if(X == '#')
      {
        cnt++;
        data[i][j] = cnt;
      }
    }
  }
  for (int i = 0; i < H; i++)
  {
    for (int j = 1; j < W; j++)
    {
      if(data[i][j] == 0)
      {
        data[i][j] = data[i][j-1];
      }
    }
    
  }

  for (int i = 0; i < H; i++)
  {
    for (int j = W-2; j >= 0; j--) 
    {
      if(data[i][j] == 0)data[i][j] = data[i][j+1];
    }
  }
  for (int i = 1; i < H; i++)
  {
    if(data[i].back() == 0)data[i] = data[i-1];
  }
  for (int i = H-2; i >= 0; i--) 
  {
    if(data[i].back() == 0)data[i] = data[i+1];
  }
  
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      if(j != 0)cout<<" ";
      cout<<data[i][j];
    }
    cout<<endl;
    
  }
  
    
  
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


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

using namespace std;

const int MAX_C = 60;
const int MAX_T = 150;
 
int c[MAX_C],t[MAX_T];
 
void init_c(){
    for(int i = 0 ; i < MAX_C ; i++){
	c[i] = i*i*i;
    }
}
 
void init_t(){
    for(int i = 2 ; i < MAX_T ; i++){
	t[i-2] = i*(i-1)*(i-2)/6;
    }
}
 
int main(){
    int n;
 
    init_c();
    init_t();
 
    while(cin >> n ,n){
	int ans = 0;
	for(int i = 0 ; i < MAX_C ; i++){
	    for(int j = 0 ; j < MAX_T-2 ; j++){
		if(c[i]+t[j] <= n){
		    ans = max(ans , c[i] + t[j]);
		}
	    }
	}
	cout << ans << endl;
    }
    return 0;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int is_sum(int sum){
    int res = 0;
    while(sum > 0){
        res += sum%10;
        sum/=10;
    }
    return res;
}
signed main()
{   
    gearup;
    int n,l;cin>>n>>l;
    vector<string> s(n);
    rep(i,n)cin>>s[i];
    sort(all(s));
    rep(i,n)cout<<s[i];
    cout<<endl;
}


Measured memory_bytes: 3664