akhauriyash/Code-Regression huggingface dataset:
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    timesave;
    string s;
    cin>>s;
    if(s.size()>5&&s[3]==s[2]&&s[5]==s[4])
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}






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

const long long int MOD=1e9+7;

int main(){
  int n,W;
  bool done=false;
  cin>>n>>W;
  while(!done){
    done=true;
    vector<int> w(n);
    for(int i=0;i<n;i++) cin>>w[i];
    sort(w.begin(),w.end(),greater<int>());
    vector<int> sum(n+1);
    sum[n]=0;
    for(int i=0;i<n;i++){
      sum[n-i-1]=sum[n-i]+w[n-i-1];
    }
    vector<vector<long long int>> dp(n+1,vector<long long int>(W+1,0));
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
      for(int j=0;j<=W;j++){
	//cal dp[i][j]
	long long int nonput=dp[i-1][j];
	if(j+sum[i]+w[i-1]<=W){
	  nonput=0;
	}
	long long int put=0;
	if(j-w[i-1]>=0){
	  put=dp[i-1][j-w[i-1]];
	}
	dp[i][j]=nonput+put;
	dp[i][j]%=MOD;
      }
    }
    long long int res=0;
    for(int i=0;i<=W;i++){
      res+=dp[n][i];
      res%=MOD;
    }
    cout<<res<<endl;
  }
  
  return 0;
}

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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> pii;

#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(auto i=0;i<n;++i)
#define LOOP_IT(it,s) for(auto it=(s).begin();it!=(s).end();++it)


#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}


template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif



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


    string s;
    cin>>s;
    if(s=="ARC")
        cout<<"ABC";
    else
        cout<<"ARC";
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI acos(-1.0)
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  ll a,b,x;cin>>a>>b>>x;
  if(a%x==0){
    P(b/x-a/x+1);
  }else{
    P(b/x-a/x);
  }
  return 0;
}


Measured memory_bytes: 256
def main():
    pass
    N = int(input())
    A = list(map(int, input().split()))

    H = [0]*N
    for i in range(0,N):
        if i >= A[i]:
            H[i-A[i]] += 1

    ans = 0
    for k in range(0,N):
        Bk = k+A[k]
        if Bk < N:
            ans += H[Bk]

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 92804
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n = I()
    c = list(S())
    alldic = collections.Counter(c)
    allnum = alldic["R"]
    leftdic = collections.Counter(c[:allnum])
    leftnum = leftdic["R"]
    ans = allnum-leftnum
    print(ans)
main()

Measured memory_bytes: 85952
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ
int p[3110];
long long dp[3100][3100];
int v[3100][3100];
long long solve(int a,int b){
	if(a>=b)return 0;
	if(v[a][b])return dp[a][b];
	long long ret=-inf;
	ret=max(ret,-solve(a+1,b)+p[a]);
	ret=max(ret,-solve(a,b-1)+p[b-1]);
	
	v[a][b]=1;
	return dp[a][b]=ret;
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	long long ret=solve(0,a);
	printf("%lld\n",ret);
}

Measured memory_bytes: 110848
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 1000000007
#define ll long long int
#define pi pair <ll,ll>
#define vi vector <ll>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
#define SQ(a) (a)*(a)
#define ordered_set tree<ll, null_type,greater_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>       //greater_equal<ll> or less<ll>
// find_by_key()   order_of_key()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
/*bool comp(string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
}*/


 
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    ll i,j,m,t,l=0,x,prev=0,max1=0,flag=0,cnt=0,y,min1,q,sum=0,r,n,k,p,flag2=0,ind=0,b;
    cin>>n;
    ll a[n];
    ll dp[n]={0};
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++){
        dp[i]=min(abs(a[i]-a[i-1])+dp[i-1],abs(a[i]-a[i-2])+dp[i-2]);
    }
        
    cout<<dp[n-1];
    
 
    return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        sc.close();
        
        int ret = 3;
        if(a==b)
            ret--;
        if(a==c)
            ret--;
        if(b==c)
            ret--;
        if(ret==0)
            ret =1;
        System.out.println(ret);
    }
    
 }

Measured memory_bytes: 8916
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
#define reps(i,s,n) for(int (i) = (s); (i) < (n); ++(i))
#define rep(i,n) reps(i,0,n)
using ll = long long;
const int mod = 1e9+7;

int main(){
	string str1,s2,s3;
	cin >> str1;
	int ans = 0;
	for(int i = 2; i < str1.length(); i+=2){	
		s2 = str1.substr(0,(str1.length()-i) /2);
		s3 = str1.substr((str1.length()-i) /2,(str1.length()-i) /2);
		if(s2 == s3) break;
		//cout << s2 << endl;
		//cout << s3 << endl;
	}
	int cnt = s2.length() + s3.length();
	cout << cnt << endl;


	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    vector<int> a(4,0);
    rep(i,n){
        string s;
        cin >> s;
        if(s=="AC")a[0]++;
        else if(s=="WA")a[1]++;
        else if(s=="TLE")a[2]++;
        else a[3]++;
    }
    cout << "AC x " << a[0] << endl;
    cout << "WA x " << a[1] << endl;
    cout << "TLE x " << a[2] << endl;
    cout << "RE x " << a[3] << endl;
}

Measured memory_bytes: 3240
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<PII> VPI;
typedef vector<PLL> VPL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

#include <atcoder/all>

using namespace atcoder;
//typedef modint998244353 mint;

int op(int a, int b) { return max(a, b); }

int e() { return -1; }

int target;

bool f(int v) { return v < target; }

int main(){
  int N,K;
  cin>>N>>K;
  VI A(N);
  rep(i,N) cin>>A[i];
  segtree<int,op,e> S(300003);
  rep(i,300003) S.set(i,0);
  rep(i,N){
    int L=max(0,A[i]-K);
    int R=min(300000,A[i]+K);
    int tmp=S.prod(L,R+1);
    S.set(A[i],tmp+1);
  }
  cout<<S.all_prod()<<endl;
}


Measured memory_bytes: 9256
a, b, m = map(int, input().split())
reizo = list(map(int, input().split()))
renji = list(map(int, input().split()))
p = [list(map(int,input().split())) for i in range(m)]
ans = []
for i in range(m):
  cost = reizo[p[i][0] - 1] + renji[p[i][1] - 1] - p[i][2]
  ans.append(cost)
ans.append(min(reizo) + min(renji))
print(min(ans))

Measured memory_bytes: 42716
a, b, c, x, y = map(int, input().split())

# 購入金額
price_a_b = 0
price_mix = 0
price_c = 0

# Aピザ、BピザをそれぞれX,Y枚購入する
price_a_b = a*x + b*y

# ABピザを、MIN(X,Y)*2枚購入し、Aピザ、Bピザどちらかの不足分を購入する
price_mix = c*min(x, y)*2 + a*(x-min(x, y)) + b*(y-min(x, y))

# ABピザをMAX(X,Y)枚購入する
price_c = c*max(x, y)*2

print(min(price_a_b, price_mix, price_c))


Measured memory_bytes: 3060
def f(a,b,c):
  if a%2+b%2+c%2>0:
    return 0
  if a==b==c:
    return -1
  return f((b+c)//2,(c+a)//2,(a+b)//2)+1

a,b,c=map(int,input().split())
print(f(a,b,c))


Measured memory_bytes: 9116
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

int main()
{
    string c[3];
    for(int i = 0; i < 3; ++i)
        cin >> c[i];

    cout << c[0][0] << c[1][1] << c[2][2] << endl;
    return 0;
}

Measured memory_bytes: 256
#! /usr/bin/env python
# -*- coding: utf-8 -*-
a, b = map(int, input().split())

B = b - a
A = B - 1

x = ((1 + A) * A) / 2 - 0.5 * (a + b - B)

print(int(x))


# ans x
#
# a wo n honme
# b wo m honme tosuruto
#
# a+x = b+x+m
# m = a-b
# n = a-b-1
#
# a = 1+2+...+n - x
# b = 1+2+...+n+m - x
#
# a+b = 2(1+2+...+n) +m-2x
# 2x = -a-b+m+2(1+2+...+n)
# x = (1+2+...+n)-1/2a-1/2b+1/2m

Measured memory_bytes: 2940
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        if(A <= 9 && B <= 9){
            System.out.println(A*B);
        }else {
            System.out.println("-1");
        }
        sc.close();
    }
}


Measured memory_bytes: 21972
//
//  Created by TaoSama on 2016-09-24
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, a[N];

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    string s; int k;
    while(cin >> s >> k) {
        for(char& c : s) {
            int need = (26 - c + 'a') % 26;
            if(need <= k) {
                k -= need;
                c = 'a';
            }
        }
        s.back() = (s.back() - 'a' + k) % 26 + 'a';
        cout << s << endl;
    }

    return 0;
}


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

int main(){
		string s;
		cin>>s;
		int h=0;
		for(int i=0;i<s.size();i++){
			if(s[i]=='C') h=1;
			if(s[i]=='F'&&h==1){
				cout<<"Yes";
				return 0;
			}
		}
	cout<<"No";
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] h = new long[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextLong();
        }
        Arrays.sort(h);
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n - k + 1; i++) {
            ans = Math.min(ans, h[i + k - 1] - h[i]);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 60348
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#include<queue>
#include <numeric>
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define fore(i,a) for(auto &i:a)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 

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

LL lcm(LL a, LL b){
    LL g = gcd(a,b);
    return a/g *b;
}

int main(){
    long long N;
    cin >> N;
    long long ans=0;
    ans=(N-1)*(N)/2;
    cout << ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n=sc.nextInt();
			int r=sc.nextInt();
			if(n==0&&r==0) break;
			int[] card = new int[n];
			for(int i=0;i<n;++i){
				card[i]=i+1;
			}
			for(int i=0;i<r;++i){
				int p=sc.nextInt();
				int c=sc.nextInt();
				int[] copy = new int[n];
				for(int j=n-1;j>n-1-c;--j){
					copy[j]=card[n-p];
					card[n-p]=0;
					p++;
				}
				int flag=n-1;
				for(int j=n-1-c;j>=0;--j){
					if(card[flag]!=0){
						copy[j]=card[flag];
					} else {
						j++;
					}
					flag--;
				}
				card=copy.clone();
			}
			System.out.println(card[n-1]);
		}
	}
}


Measured memory_bytes: 37216
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <utility>
#include <climits>
#include <bitset>

#define P 1000000007

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int ui;

typedef vector<ull> vull;
typedef vector<ll> vll;
typedef vector<ui> vui;
typedef vector<long> vl;
typedef vector<int> vi;

typedef pair<ull, ull> pull;
typedef pair<ll, ll> pll;
typedef pair<ui, ui> pui;
typedef pair<long, long> pl;
typedef pair<int, int> pi;

template <class T>
void printv(vector<T> vc) {
    for (auto e: vc) cout << e << " ";
    cout << endl;
}

long gcd(long n, long m) {
    if (m == 0) return n;
    return gcd(m, n % m);
}

long lcm(long n, long m) {
	if ((n == 0) || (m == 0)) return 0;
	return ((n / gcd(n, m)) * m);
}

int main() {
    int N, M; cin >> N >> M;
    string S, T; cin >> S >> T;

    long l1 = lcm(max(N, M), min(N, M));
    long n = l1 / N;
    long m = l1 / M;
    long l2 = lcm(max(n, m), min(n, m));

    bool ok = true;
    for (long i = 0; i < l1 / l2 && ok; ++i) ok = S[l2 / n * i] == T[l2 / m * i];

    cout << (ok ? l1 : -1) << endl;

    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

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

  int x,n;
  cin>>x>>n;
  vector<int> ps(n);
  for(int i=0;i<n;i++) cin>>ps[i];

  for(int d=0;;d++){
    if(count(ps.begin(),ps.end(),x-d)==0) drop(x-d);
    if(count(ps.begin(),ps.end(),x+d)==0) drop(x+d);
  }
  abort();
  return 0;
}


Measured memory_bytes: 3640
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.function.Supplier;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();

        Result counterResult = count(num, scanner::next);
        counterResult.counter.entrySet().stream()
                .filter(e -> e.getValue() != null)
                .filter(e -> e.getValue() == counterResult.maxCount)
                .map(Map.Entry::getKey)
                .sorted(Comparator.naturalOrder())
                .forEach(System.out::println);
    }

    static Result count(int num, Supplier<String> resultSupplier) {
        HashMap<String, Integer> counter = new HashMap<>();
        int maxCount = 0;
        for (int i = 0; i < num; i++) {
            String result = resultSupplier.get();
            int value = counter.getOrDefault(result, 0);
            counter.put(result, ++value);
            if (maxCount < value) {
                maxCount = value;
            }
        }
        return new Result(maxCount, counter);
    }

    static class Result {
        int maxCount;
        Map<String, Integer> counter;

        public Result(int maxCount, Map<String, Integer> counter) {
            this.maxCount = maxCount;
            this.counter = counter;
        }
    }
}

Measured memory_bytes: 89148
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin>>n;
    
    int dp[3]={};
int a[n][3];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>a[i][j];
            
        }
        
    }
    if(n==1)cout<<max(a[0][0],max(a[0][1],a[0][2]));
    else{
    dp[0]=a[0][0];
    dp[1]=a[0][1];//cout<<dp[1]<<" ";
    dp[2]=a[0][2];
    int dp1[3]={};
    for(int i=1;i<n;i++)
    {
    
        dp1[0]=max(dp[1]+a[i][0],dp[2]+a[i][0]);
         dp1[1]=max(dp[0]+a[i][1],dp[2]+a[i][1]);
         dp1[2]=max(dp[0]+a[i][2],dp[1]+a[i][2]);
        dp[0]=dp1[0];dp[1]=dp1[1];dp[2]=dp1[2];
    }//cout<<dp[0]<<" "<<dp[1]<<" "<<dp[2]<<" ";
    cout<<max(dp1[0],max(dp1[1],dp1[2]));
    
    
}}


Measured memory_bytes: 1408
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <cmath>
#include <iomanip>
using namespace std;
#define sL(i) i << 1
#define sR(i) i << 1 | 1
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pair<int,int>, int> ppi;
const int MOD = 1e9 + 7;
const int INF = 2e9 + 5;

string s;
int w;
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> w;
    string res;
    for (int j = 0; j < s.length(); j += w) {
        res += s[j];
    }
    cout << res;
}

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

int main(){
	int i,j,k,n,m,l,x,y,z; string s;
	cin >> x;

	double f = 0;
	rep(i, 32){
		REP(j, 2, 10){
			if(i >= 3 && j>= 6) continue;
			if(pow(i, j) <= x){
				f = max(f, pow(i, j));
			}
		}
	}
	cout << f << endl;
}

Measured memory_bytes: 256
while 1:
	n = input()
	if n == 0: break
	N = [input() for i in range(n)]
	s = input()
	l,r= 0,n-1
	c = 0
	while l <= r:
		i = (l + r)/2
		c += 1
		if N[i] == s:
			break
		elif N[i] < s:
			l = i + 1
		else:
			r = i - 1
	print c

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

long long mod = 998244353;
long long A,B,C,D;
long long dp[3030][3030];

int main(){
  cin >> A >> B >> C >> D;
  dp[A][B] = 1;
  for (long long i = A; i <= C; i++){
    for (long long j = B; j <= D; j++){
      if ((i > A)||(j > B)){
        dp[i][j]=
          (i * dp[i][j-1] % mod
          + j * dp[i-1][j] % mod
          - (i - 1) * (j - 1) * dp[i-1][j-1] % mod + mod) % mod;
      }
    }
  }
  cout << dp[C][D];
}

Measured memory_bytes: 74540
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{

    int A,B;
    cin >> A >> B;
    out(6-A-B);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
char a[1100000];
struct lll
{
    int weizhi;
    char s[5];
}TM[1100000];
int len1=1;
int panduan()
{
    int kaishi=1;
    int jieshu=len1-1;
    while(kaishi<jieshu)
    {
        if(TM[kaishi].s[0]!=TM[jieshu].s[0])
            return 0;
        kaishi++;
        jieshu--;
    }
    return 1;
}
int main()
{
    cin>>a+1;
    int len=strlen(a+1);
    for(int i=1;i<=len;i++)
    {
        if(a[i]!='x')
        {
            TM[len1].s[0]=a[i];
            TM[len1++].weizhi=i;
        }
    }
    if(panduan()==0)
    {
        cout<<"-1"<<endl;
        return 0;
    }
    int sum=0;
    int kaishi=1;
    int jieshu=len1-1;
    //cout<<mid1<<"_"<<mid2<<endl;
    while(kaishi<jieshu)
    {
        sum+=(int)fabs((TM[kaishi+1].weizhi-TM[kaishi].weizhi)-(TM[jieshu].weizhi-TM[jieshu-1].weizhi));
        //cout<<TM[kaishi].weizhi<<"_"<<TM[jieshu].weizhi<<endl;
        kaishi++;
        jieshu--;
        //cout<<sum<<endl;
    }
    int sum1=0;
    int sum2=0;
    for(int i=1;i<=len;i++)
    {
        if(a[i]!='x')
            break;
        sum1++;
    }
    for(int i=len;i>=1;i--)
    {
        if(a[i]!='x')
            break;
        sum2++;
    }
    sum+=(int)fabs(sum1-sum2);
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h> //ABC 124_a
using namespace std;
int main(){
	int A,B,X;
	cin>>A>>B;
	X=max(A,B);
	if(X+X-1>=A+B)
		cout<<X+X-1;
	else
		cout<<A+B;
	return 0;
}

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

int main(){
    int ar[4][4] ;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin >> ar[i][j] ;
        }
    }
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            for(int k=0;k<=100;k++){
                int b[4] ;
                int a[4] ;
                a[1] = i ;
                a[2] = j ;
                a[3] = k ;
                b[1] = ar[1][1] - i ;
                b[2] = ar[1][2] - i ;
                b[3] = ar[1][3] - i ;
                int ok = true ;
                for(int u=1;u<4;u++){
                    for(int e=1;e<4;e++){
                        if ( a[u]+b[e] != ar[u][e] ){
                            ok = false ;
                        }
                    }
                }
                if ( ok ) {
                    cout << "Yes" << endl;
                    return 0 ;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0 ;
}


Measured memory_bytes: 256
N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")

for i in range(N):
  for j in range(i+1,N):
    k=j+(j-i)
    if k<=N-1:
      if S[j]!=S[i] and S[j]!=S[k] and S[k]!=S[i]:
          ans-=1
print(ans)

Measured memory_bytes: 9196
class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)
  def initialize
    @n,@m = gets.to_s.split.map{ |v| v.to_i }
    @a,@b = Array.new(n){ gets.to_s.split.map{ |v| v.to_i } }.transpose
    @c,@d = Array.new(m){ gets.to_s.split.map{ |v| v.to_i } }.transpose
  end

  def len(a,b,c,d)
    (a-c).abs + (b-d).abs
  end

  def solve
    ans = []
    n.times do |i|
      lens = m.times.map{|j|len(a[i],b[i],c[j],d[j])}
      mini = lens.min
      k = lens.find_index(mini)
      ans << k + 1
    end
    ans
  end

  def show(ans)
    ans.each do |a|
      puts a
    end
  end
end

Problem.new.instance_eval do
  show(solve)
end

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

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

int main(){
  char d[10][10];
  rep(i,3){
    rep(j,3){
      cin >> d[i][j];
    }
  }
  cout << d[0][0] << d[1][1] << d[2][2] << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // A - Blackjack

        Scanner sc = new Scanner(System.in);

        int a1 = sc.nextInt();
        int a2 = sc.nextInt();
        int a3 = sc.nextInt();

        System.out.println((a1 + a2 + a3) > 21 ? "bust" : "win");
    }

}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }


void func(long long N){

}

int main(){
    int n;
    cin >> n;
    int t = n % 10;
    if (t==3) puts("bon");
    else if (t==0||t==1||t==6||t==8) puts("pon");
    else puts("hon");
    return 0;
}


Measured memory_bytes: 3632
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        char[] s=sc.next().toCharArray();
        int x=sc.nextInt(), y=sc.nextInt();
        sc.close();
        int n=s.length;
        ArrayList<Integer> xl=new ArrayList<>();
        ArrayList<Integer> yl=new ArrayList<>();
        boolean b=true;
        boolean xb=false;
        int count=0;
        int xc=0, yc=0;
        for(int i=0;i<n;i++){
            if(b){
                if(s[i]=='F'){
                    x--;
                } else{
                    b=false;
                }
            } else{
                if(s[i]=='F'){
                    count++;
                } else{
                    if(xb){
                        if(count>0){
                            xl.add(count);
                            xc+=count;
                        }
                    } else{
                        if(count>0){
                            yl.add(count);
                            yc+=count;
                        }
                    }
                    xb=!xb;
                    count=0;
                }
            }
        }
        if(count>0){
            if(xb){
                xl.add(count);
                xc+=count;
            } else{
                yl.add(count);
                yc+=count;
            }
        }
        if((xc-x)%2!=0 || (yc-y)%2!=0 || xc<x || yc<y){
            System.out.println("No");
            return;
        }
        xc=(xc-x)/2;
        yc=(yc-y)/2;
        // System.out.println("xc:"+xc+", yc:"+yc);
        int xn=xl.size(), yn=yl.size();
        boolean okx=false, oky=false;
        if(xn!=0){
            boolean[][] dpx=new boolean[xn][8001];
            for(int i=0;i<xn;i++){
                for(int j=0;j<=8000;j++){
                    if(j==0||j==xl.get(i)){
                        dpx[i][j]=true;
                    }
                    if(i>0 && dpx[i-1][j]){
                        dpx[i][j+xl.get(i)]=true;
                        dpx[i][j]=true;
                    }
                }
            }
            okx=dpx[xn-1][xc];
            // System.out.println("xl");
            // for(int i:xl){
            //     System.out.println(i);
            // }
        } else{
            okx=xc==0;
        }
        if(yn!=0){
            boolean[][] dpy=new boolean[yn][8001];
            for(int i=0;i<yn;i++){
                for(int j=0;j<=8000;j++){
                    if(j==0||j==yl.get(i)){
                        dpy[i][j]=true;
                    }
                    if(i>0 && dpy[i-1][j]){
                        dpy[i][j+yl.get(i)]=true;
                        dpy[i][j]=true;
                    }
                }
            }
            oky=dpy[yn-1][yc];
            // System.out.println("yl");
            // for(int i:yl){
            //     System.out.println(i);
            // }
        } else{
            oky=yc==0;
        }
        if(okx&&oky){
            System.out.println("Yes");
        } else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 69992
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    string s;
    int x, y;
    cin >> s >> x >> y;

    int n = s.size();

    vector<int> h = {0}, v = {};
    {
        char o = 'h';
        rep(i, n) {
            if (s[i] == 'T') {
                if (o == 'v') {
                    o = 'h';
                    h.push_back(0);
                } else {
                    o = 'v';
                    v.push_back(0);
                }
            } else {
                if (o == 'v') {
                    v.back()++;
                } else {
                    h.back()++;
                }
            }
        }
    }


    auto check = [](vector<int> seq, int start, int target) -> bool {
        set<int> prev;
        prev.insert(start);
        for (int j : seq) {
            set<int> next;
            for (int i : prev) {
                next.insert(i + j);
                next.insert(i - j);
            }
            prev = next;
        }
        return prev.find(target) != prev.end();
    };

    int first = h[0];
    h.erase(h.begin());
    bool ok_h = check(h, first, x);
    bool ok_v = check(v, 0, y);

    bool ok = ok_h && ok_v;
    cout << (ok ? "Yes" : "No") << endl;

}


Measured memory_bytes: 3924
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const int N = 1e5;
int a[N+5];

int main()

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

    int a, b, k, check;

    cin >> a >> b >> k;

    vector <int> v;

    for (int i = 0; i < k; i++) {

        if (a+i > b) break;

        v.push_back(a+i);

        check = a+i;
    }

    for (int i = 0; i < k; i++) {

        if (b-i < a || b-i <= check) break;

        v.push_back(b-i);
    }

    sort(v.begin(), v.end());

    for (auto x : v) cout << x << "\n";

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

    public static void main(String[] args) throws Exception {

        try {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String[] input = br.readLine().split(" ");
            int aToB = Integer.parseInt(input[0]);
            int bToC = Integer.parseInt(input[1]);
            int areaOfRightTriangle = aToB * bToC / 2;

            System.out.println(areaOfRightTriangle);
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N;
    cin >> N;
    vector< vector<long long> > A( N, vector<long long>(3) );

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < 3; j++ ) {
            cin >> A[i][j];
        }
    }

    vector< vector<long long> > dp( N, vector<long long>(3,0) );

    dp[0][0] = A[0][0];
    dp[0][1] = A[0][1];
    dp[0][2] = A[0][2];

    for ( int i = 1; i < N; i++ ) {
        for ( int j = 0; j < 3; j++ ) {
            for ( int k = 0; k < 3; k++ ) {
                if ( j == k ) { continue; }
                dp[i][j] = max( dp[i][j], dp[i-1][k] + A[i][j] );
            }
        }
    }

    cout << max( max( dp[N-1][0], dp[N-1][1] ), dp[N-1][2] ) << endl;

    return 0;
}

Measured memory_bytes: 11136
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
int n;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}  

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key){
    return u;
  }
  if(k < u->key){
    return treeSearch(u->left,k);
  }
  else{
    return treeSearch(u->right,k);
  }
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL){
    return treeMinimum(x->right);
  }
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void transplant(Node u,Node v){
  if(u->parent == NIL){
    root = v;
  }
  else if(u == u->parent->left){
    u->parent->left = v;
  }
  else{
    u->parent->right = v;
  }
  if(v != NIL){
    v->parent = u->parent;
  }
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left == NIL){
    transplant(z,z->right);
  }
  else if(z->right == NIL){
    transplant(z,z->left);
  }
  else{
    y = treeMinimum(z->right);
    if(y->parent != z){
      transplant(y,y->right);
      y->right = z->right;
      y->right->parent = y;
    }
    transplant(z,y);
    y->left = z->left;
    y->left->parent = y;
  }
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  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){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){

  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


int main(){
  int i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
a = list(map(int, input().split())) + [-N]
last = T
res = N
for t in range(N):
  x = T
  for i in range(T):
    if i == last: continue
    if a[x] <= a[i] and (a[i] > 0): x = i
  if x == T: x = last
  a[x] -= 1
  res -= x != last or (t == 0)
  last = x
print(res)

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

using namespace std;

typedef long long ll;

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

ll lcm(ll a,ll b){
	return a*b/(gcd(a,b));
}

int main(){
	int a[3],m[3];
	while(cin>>a[0]>>m[0]>>a[1]>>m[1]>>a[2]>>m[2]&&!(a[0]==0&&a[1]==0&&a[2]==0&&m[0]==0&&m[1]==0&&m[2]==0)){
		int x,y,z;
		x=y=z=1;
		ll cnt=1;
		int nx=(a[0]*x)%m[0];
		int ny=(a[1]*y)%m[1];
		int nz=(a[2]*z)%m[2];
		x=nx,y=ny,z=nz;

		while(1){
			if(x==1)
				break;
			nx=(a[0]*x)%m[0];
			x=nx;
			cnt++;
		}
		int xLoop=cnt;
		cnt=1;
		while(1){
			if(y==1)
				break;
			ny=(a[1]*y)%m[1];
			y=ny;
			cnt++;
		}
		int yLoop=cnt;
		cnt=1;
		while(1){
			if(z==1)
				break;
			nz=(a[2]*z)%m[2];
			z=nz;
			cnt++;
		}
		int zLoop=cnt;

		ll ret=lcm(zLoop,lcm(xLoop,yLoop));
		cout<<ret<<endl;

		//while(1){
		//	if(x==1&&y==1&&z==1){
		//		break;
		//	}
		//	nx=(a[0]*x)%m[0];
		//	ny=(a[1]*y)%m[1];
		//	nz=(a[2]*z)%m[2];
		//	x=nx,y=ny,z=nz;
		//	cnt++;
		//}
		//cout<<cnt<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

const LL inf = 1123456789012;
LL N, S;

LL f(LL b, LL n)
{
	LL res = 0;
	while (n > 0)
	{
		res += n % b;
		n /= b;
	}
	return res;
}

int main()
{
	in >> N >> S;
	if (N == S) out << N + 1 << std::endl;
	else
	{
		for (LL b = 2; b <= sqrt(N); ++b)
		{
			if (f(b, N) == S)
			{
				out << b << std::endl;
				return 0;
			}
		}
		LL ans = inf;
		for (LL alp = 1; alp <= sqrt(N); ++alp)
		{
			LL b = (N - S) / alp + 1;
			if (b < 2) continue;
			if (f(b, N) == S) ans = std::min(ans, b);
		}
		out << (ans == inf ? -1 : ans) << std::endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(410000)

h,w = map(int,input().split())
F = []
for i in range(h):
  F.append(list(input()))
  
V = [[False]*w for _ in range(h)]

def dfs(y,x,c):      
  V[y][x] = True
  black = 0
  white = 0
  if c =='#':
    black+=1
  else:
    white+=1
  for dy,dx in [(-1,0),(0,1),(1,0),(0,-1)]:
    ny = y + dy
    nx = x + dx
    if 0<=ny<h and 0<=nx<w:      
      if F[ny][nx]!=c and V[ny][nx] == False:
        nc = '#'
        if c =='#':
          nc = '.'
        bn,wn = dfs(ny,nx,nc)
        black += bn
        white += wn  
  return black,white
        
ans = 0
for i in range(h):
  for j in range(w):
    if F[i][j] == '#':      
      black,white = dfs(i,j,'#')
      ans += black*white
      
print(ans)      

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;
const ll 	N 		= 	2*1e6;

/*vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
*/
// <------------- Declare Variables Here ------------> //

ll T=1;
ll n,x,y,m;
string s,t;
vll a;

ll prime[N];

// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n;

	for(ll i=0;i<=55555;i++) prime[i]=1;
	prime[0] = prime[1] = 0;

	for(ll i=2;i<=55555;i++) {
		if(prime[i]) {
			for(ll j=i*i;j<=55555;j+=i) prime[j]=0;
			if(i%5 == 1) a.pb(i);
		}
	}

	a.resize(n);
	DISP(a);
}

int main() {
	fastio;randomINT;
	//cin>>T;
	while(T--) {
		MAIN();
	}
	return 0;
}



Measured memory_bytes: 4128
N = int(input())
W = list(map(int, input().split()))
result = 10 ** 9
for i in range(N - 1):
    s1 = sum(W[:i + 1])
    s2 = sum(W[i + 1:])
    result = min(abs(s1 - s2), result)
print(result)


Measured memory_bytes: 2940