akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    int ans = 0;
    int maxe = 0;
    rep(i, n) {
        int h;
        cin >> h;
        if(h >= maxe) ans++;
        maxe = max(h, maxe);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
fib_table = [0 for _ in range(45)]
fib_table[0], fib_table[1] = 1, 1
for i in range(2, 45):
  fib_table[i] = fib_table[i-1]+fib_table[i-2]
n = int(input())
print(fib_table[n])


Measured memory_bytes: 5604
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define INF 1000000100
#define rep(i,n) for (int i=0;i<n;i++)

int main(){
    int N,M;
    cin >> N >> M;
    int A[N],B[N];
    vector<P> v;
    rep(i,N){
        cin >> A[i] >> B[i];
        v.push_back(make_pair(B[i],A[i]));
    }
    sort(v.begin(),v.end(),[](P& lhs, P& rhs){return lhs.second < rhs.second;});
    priority_queue<P,vector<P> > q;
    ll ans = 0;
    int ind=0;
    rep(now,M){
        while(now+1==v[ind].second && ind<v.size()){
            q.push(v[ind]);
            ind++;
        }
        if(q.empty()) continue;
        P p = q.top();q.pop();
        ans += p.first;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5972
#include <stdio.h>

#define MAX (1<<(2*12))

void init();
void insert(char *str);
int find(char *str);
int get_key(char *str);

const int hash[] = {
    0  /* A */
    ,0 /* B */
    ,1 /* C */
    ,0 /* D */
    ,0 /* E */
    ,0 /* F */
    ,2 /* G */
    ,0 /* H */
    ,0 /* I */
    ,0 /* J */
    ,0 /* K */
    ,0 /* L */
    ,0 /* M */
    ,0 /* N */
    ,0 /* O */
    ,0 /* P */
    ,0 /* Q */
    ,0 /* R */
    ,0 /* S */
    ,3 /* T */
};

char dic[MAX];

int main(){
    char cmd[7];
    char str[13];
    int n;
    int i;

    init();

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s %s",cmd,str);
        if(cmd[0]=='i'){
            insert(str);
        }else if(cmd[0]=='f'){
            printf(find(str)?"yes\n":"no\n");
        }
    }

    return 0;
}

void init(){
    int i;
    for(i=0;i<MAX;i++)dic[i]=0;
}

void insert(char *str){
    dic[get_key(str)]=1;
}

int find(char *str){
    return dic[get_key(str)];
}

int get_key(char *str){
    int key;
    int idx;

    key=1;
    for(idx=0;str[idx];idx++){
        key<<=2;
        key+=hash[str[idx]-'A'];
    }

    return key;
}

Measured memory_bytes: 18096
/**
 * 降参。
 * 解説の方法を試す
 *
 * xorが0のビットのみ、1,1に分けると結果が増えることは理解した。
 *
 * 0ビットの最大化を求めるのに行標準形を使えるのは、
 * 1.貪欲でいい理由は、同じビットが立っているデータがあった場合、後の候補に今の選択(A)を取り消して他の候補を選んだ場合(A+B)、というデータが残るため
 * 2.その選択が可能である理由は、全行のxorはどう計算しようが、各行が高々1回xorされるだけで算出できるため。
 *
 *   例: 行標準形計算後
 *
 *     1 0 1 0 A
 *     0 1 1 0 A+B
 *     0 0 1 0 A+C
 *     0 0 0 1 A+B+C+D
 *
 *     全行のxor = A+A+B+A+C+A+B+C+D = D (xorなので、2回足すと0に戻る)
 *
 * 計算量は、
 *   その桁の1が立っているデータを探す O(N)
 *   他のデータをxorして、その桁を0にする O(N)
 * を桁数(=60ビット)繰り返せばいいので、全体でO(N)
 *
 */
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long long int> as(n);
  long long int as_xor = 0;

  for (int i = 0; i < n; i++) {
    cin >> as[i];
    as_xor ^= as[i]; // 全Aのxorを出しておいて
  }

  // 0の部分を抽出する
  long long int mask = ~as_xor;
  for (int i = 0; i < n; i++) {
    as[i] &= mask;
  }

  long long int zero_xor = 0;

  for (long long int i = (1ll<<60); i > 0; i>>=1) { //上のビットから順に処理していき
    auto const a_ite = find_if(as.begin(), as.end(), [i](const auto& a){ return (a&i) != 0; });

    if (a_ite != as.end()) { //今のビットが1のデータが見つかったら
      const auto a = *a_ite;

      if ((zero_xor&i) == 0) { // まだビットが立っていない場合は追加 (貪欲)
        zero_xor ^= a;
      }

      for (auto& a2 : as) { //行標準形にするため、xorしてこの桁を0にしていく
        if ((a2&i) != 0) {
          a2 ^= a;
        }
      }

      remove(as.begin(), as.end(), 0); // 高速化のため0のデータは消しておく...効果あるか？
    }
  }

  long long int result = as_xor + 2 * zero_xor; // 結果は、ビットが1の部分(as_xor)と、ビットが0だった部分(zero_xor, 2個に分けるので足して2倍になる)

  cout << result << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>

using namespace std;

int main() {
  int N;
  cin >> N;
  int cnt = 0;
  for (int i = 1; i <= N; ++i) {
    int value;
    cin >> value;
    if (value != i) ++cnt;
  }
  if (cnt <= 2) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
    
  return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;

class Program
{
    static void Solve()
    {
        var inputs = ReadInts();
        var A = inputs[0];
        var B = inputs[1];

        var ans = 0;

        for (var i = 0; i < 2; i++)
        {
            if (A > B)
            {
                ans += A;
                A--;
            }
            else
            {
                ans += B;
                B--;
            }
        }

        Console.WriteLine(ans);
    }

    static void Main(string[] args)
    {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }

    public static string Read() { return Console.ReadLine(); }
    public static int ReadInt() { return int.Parse(Read()); }
    public static long ReadLong() { return long.Parse(Read()); }
    public static double ReadDouble() { return double.Parse(Read()); }

    public static string[] Reads() { return Console.ReadLine().Split(' '); }
    public static int[] ReadInts() { return Reads().Select(_ => int.Parse(_)).ToArray(); }
    public static long[] ReadLongs() { return Reads().Select(_ => long.Parse(_)).ToArray(); }
    public static double[] ReadDoubles() { return Reads().Select(_ => double.Parse(_)).ToArray(); }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a; i<=b; ++i)
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
using vl=vector<ll>;
using vp=vector<pll>;
const ll INF=1e18;

struct node{
    ll lz,val;
    node():lz(INF),val(0){}
    void updt(node& a,node& b){
        val=min(a.val,b.val);
    }
};
struct seg{
    ll base;
    vector<node> v;
    seg(ll n, ll* arr=NULL){
        base=1;
        while(base<n) base<<=1;
        v.resize(base<<1);
        if(arr==NULL) return;
        FOR(i,1,n) v[base+i-1].val=arr[i];
        for(ll i=base-1; i; --i){
            v[i].updt(v[i<<1],v[i<<1|1]);
        }
    }
    void lazy(ll vi,ll s,ll e){
        ll& lz=v[vi].lz;
        if(!lz) return;
        if(s!=e){
            v[vi<<1].lz=min(v[vi<<1].lz,lz);
            v[vi<<1|1].lz=min(v[vi<<1|1].lz,lz);
        }
        v[vi].val=min(v[vi].val,lz);
        lz=INF;
    }
    void updt(ll l,ll r,ll val){updt(l,r,val,1,base,1);}
    void updt(ll l,ll r,ll val,ll s,ll e,ll vi){
        if(l<=s && e<=r){
            v[vi].lz=min(v[vi].lz,val);
            lazy(vi,s,e);
            return;
        }
        lazy(vi,s,e);
        if(r<s || e<l) return;
        ll m=s+e>>1;
        updt(l,r,val,s,m,vi<<1);
        updt(l,r,val,m+1,e,vi<<1|1);
        v[vi].updt(v[vi<<1],v[vi<<1|1]);
    }
    ll query(ll l,ll r){return query(l,r,1,base,1);}
    ll query(ll l,ll r,ll s,ll e,ll vi){
        if(r<s || e<l) return 0;
        lazy(vi,s,e);
        if(l<=s && e<=r) return v[vi].val;
        ll m=s+e>>1;
        ll lval=query(l,r,s,m,vi<<1);
        ll rval=query(l,r,m+1,e,vi<<1|1);
        return lval+rval;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,q;
    cin>>n>>q;
    ll tmp[n+5];
    FOR(i,1,n) tmp[i]=n;
    seg bot(n-1,tmp),right(n-1,tmp);
    ll ans=0;
    while(q--){
        ll a,b;
        cin>>a>>b;
        if(a==1){
            ll tmp=bot.query(b,b);
            ans+=tmp-2;
            right.updt(2,tmp-1,b);
        }
        else{
            ll tmp=right.query(b,b);
            ans+=tmp-2;
            bot.updt(2,tmp-1,b);
        }
    }
    cout<<(n-2)*(n-2)-ans;
    return 0;
}

Measured memory_bytes: 21156
import math

N=int(input())

print(N * (N-1) //2 - N//2)

if N%2:
  for i in range(1,N):
    print('{} {}'.format(i, N))
  N=N-1
  
for i in range(1, N):
  for j in range(i+1, N+ 1):
    if i+j != N+1:
	    print('{} {}'.format(i, j))

Measured memory_bytes: 3336
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uld = unsigned long long;
using P = pair<int,int>;
ll MAX(ll a,ll b,ll c){return max(a,max(b,c));}
ll MIN(ll a,ll b,ll c){return min(a,min(b,c));}
const ll mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
int main(){
    int a,b;
    cin >> a >> b;
    cout << a*b << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int Q;
    cin >> Q;
    vec<int> f(1e5 + 7, 0);
    vec<int> s(1e5 + 7, 0);
    f[0] = 0;
    f[1] = 0;
    for (int i = 2; i <= 1e5 + 3; ++i) {
        if (f[i] == 0) {
            f[i] = i;
            s[i] = 1;
        }
        for (int j = i + i; j <= 1e5 + 3; j += i)
            f[j] = i;
    }
    for(int i=1e5+3;i>=3;i-=2){
        if(s[i] == 1 && s[(i+1)/2] == 1){
            s[i] = 1;
        } else {
            s[i] = 0;
        }
    }
    s[2] = 0;
    for(int i=3;i<=1e5+3;++i) s[i+1]+=s[i];

    rep(_, Q) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
}


Measured memory_bytes: 4040
#include<stdio.h>
int N,M,i,j,a[100],n[100],b;
int main(void){
	scanf("%d%d",&N,&M);
 	for(i=0;i<M;i++){
	scanf("%d",&a[i]);
	}
	for(i=0;i<M;i++){
	for(j=0;j<N;j++){
	scanf("%d",&b);
	if(b==a[i]){
	n[j]+=1;
	}else{
	n[a[i]-1]+=1;
	}
}
}
	for(i=0;i<N;i++){
	printf("%d\n",n[i]);
}
	
	return 0;
}

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

//var 
double x,a;

int main(){
	a = 100;
	cin >> x;
	for(int i = 1; i<=4000; i++){
		a*=1.01;
		a = floor(a);
		if(a>=x){
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 3736
n,m=map(int,input().split())
ball_in_boxes = [1]*n
redball_flag = [False]*n
redball_flag[0] = True
for _ in range(m):
    x,y = map(int,input().split())
    if redball_flag[x-1]: # x番目の箱に赤いボールが入っている可能性がある
        redball_flag[y-1] = True
    ball_in_boxes[x-1] -= 1
    ball_in_boxes[y-1] += 1

    if ball_in_boxes[x-1] == 0: # x番目の箱にボールが入っていないので
        redball_flag[x-1] = False
print(redball_flag.count(True))


Measured memory_bytes: 10324
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define SORT(c) sort((c).begin(),(c).end())
#define MOD 1000000007 //S.size() 配列名.Length()
using namespace std;
typedef unsigned long long ll;

ll func(ll m, ll n){
	if(n == 1) return m;
	if(n % 2 == 0){
		return func(m, n / 2) * func(m, n / 2) % MOD;
	}
	else {
		return m * func(m, n - 1) % MOD;
	}
}

int main(void){

	ll n, m;
  cin >> n >> m;
	cout << func(n, m) <<endl;
}



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

template<typename T>
istream& operator >> (istream& istr, vector<T>& v){
    for(T& x: v) istr >> x;
    return istr;
}

template<typename T, typename U>
istream& operator >> (istream& istr, pair<T,U>& p){
    istr >> p.first >> p.second;
    return istr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<T>& v){
    if(!v.empty()){
        ostr << v.front();
        for(auto itr = ++v.begin(); itr != v.end(); itr++)
            // ostr << *itr;
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, pair<T,U>& p){
    // ostr << p.first << p.second;
    ostr << p.first << ", " << p.second;
    return ostr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<vector<T>>& vv){
    if(!vv.empty()){
        ostr << vv.front();
        for(auto itr = ++vv.begin(); itr != vv.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, vector<pair<T,U>>& vp){
    if(!vp.empty()){
        ostr << vp.front();
        for(auto itr = ++vp.begin(); itr != vp.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<double> vd;
// vll x(n); x[i]=a;
typedef vector<vll> vvll;
typedef vector<vc> vvc;
typedef vector<vd> vvd;
// vvll x(m,vi(n)); x[i][j]=a;
typedef pair<ll,ll> pll;
typedef pair<double,double> pd;
typedef vector<pll> vpll;
typedef vector<pd> vpd;
// vpll x(n); x[i]={a,b}; x[i].first/second;

#define PI 3.1415926535897932
// cout << fixed << setprecision(10) << PI << endl;
#define EPS 1e-12
#define INF (ll)1e+12
#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORR(i,a,b) for(ll i=(b)-1; i>=(a); i--)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()
// sort(all(x));

ll sum(vll &v){return accumulate(all(v), 0LL);}

int main(){
    ll n, s, tmp;
    cin >> n;
    vll a(n), b(n,0), c(n,0);
    cin >> a;
    REP(i,n) a[i]--;
    REP(i,n) b[a[i]]++;
    REP(i,n) c[i]=b[i]*(b[i]-1)/2;
    s=sum(c);
    REP(i,n){
        tmp = c[a[i]]*2/b[a[i]];
        cout << s-tmp << endl;
    }
    return 0;
}


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

int main(){
  char a,b;
  cin >> a >> b;
  if(a == 'H' && b == 'H') cout << 'H' << endl;
  else if(a == 'D' && b == 'D') cout << 'H' << endl;
  else cout << 'D' << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
ll n,m,vis[N],x,dp[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>x,vis[x]=1;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dp[i]=dp[i-1]+((i>=2)?dp[i-2]:0);
        }else{
            dp[i]=0;
        }
        dp[i]%=mod;
    }
    cout<<dp[n];
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

void solve(){
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	while(k--){
		vector<int> b(n);
		for(int i=0;i<n;i++){
			int d = a[i];
			b[max(i-d,0)] += 1;
			if(i+d+1 < n){
				b[i+d+1] -= 1;
			}
		}
		for(int i=1;i<n;i++){
			b[i] += b[i-1];
		}

		if(a == b){
			break;
		}
		a = b;
	}
	for(int i:a){
		cout<<i<<" ";
	}
	cout<<endl;
}

int main(){
	fastread;
	int t = 1;
	// cin>>t;
	for(int i=1;i<=t;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}



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

int cnt, k;
long long a[300000];

void dfs(int x, int y, long long num, int last)
{
	if (x > y)
	{
		if (num <= 3234566667) a[++cnt] = num;
		return;
	}
	for (int i = last - 1; i <= last + 1; ++i)
		if (i <= 9 && i >= 0)
			dfs(x + 1, y, num * 10 + i, i);
}

int main()
{
	for (int i = 1; i <= 10; i++)
		for (int j = 1; j <= 9; j++)
			dfs(2, i, j, j);
    sort(a + 1, a + 1 + cnt);
    scanf("%d", &k);
    printf("%lld", a[k]);
}

Measured memory_bytes: 1024
def many_formulas(s)
  chars = s.chars
  plus = Array.new(s.size - 1) { false }
  sum = 0
  f = ->(i) {
    if plus.size == i
      formula = ''
      chars.each_with_index do |c, i|
        if i < plus.size && plus[i]
          formula += c + '+'
        else
          formula += c
        end
      end
      sum += eval(formula)
      return
    end

    plus[i] = true
    f.call(i + 1)
    plus[i] = false
    f.call(i + 1)
  }

  f.call(0)
  sum
end

puts many_formulas(gets.chomp)


Measured memory_bytes: 2044
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
struct Nums{
	int a,b,c;
	Nums(int _a,int _b,int _c){
		a=_a;
		b=_b;
		c=_c;
	}
	bool operator<(const Nums& other) const{
		if(a!=other.a) return a<other.a;
		else if(b!=other.b) return b<other.b;
		else return c<other.c;
	}
};
int main(){
	int N[3],K;
	ll A[3][1001];
	scan(N[0]>>N[1]>>N[2]>>K);
	rep(i,3){
		rep(j,N[i]){
			scan(A[i][j]);
		}
		sort(A[i],A[i]+N[i],greater<ll>());
	}
	priority_queue<pair<ll,Nums> > Q;
	Q.push(mp(A[0][0]+A[1][0]+A[2][0],Nums(0,0,0)));
	map<Nums,bool> alre;
	alre[Nums(0,0,0)]=1;
	rep(i,K){
		pair<ll,Nums> Qtop=Q.top();
		Q.pop();
		prin(Qtop.first);
		int i1=Qtop.second.a,i2=Qtop.second.b,i3=Qtop.second.c;
		if(i1+1<N[0]&&alre[Nums(i1+1,i2,i3)]==0){
			Q.push(mp(A[0][i1+1]+A[1][i2]+A[2][i3],Nums(i1+1,i2,i3)));
			alre[Nums(i1+1,i2,i3)]=1;
		}
		if(i2+1<N[1]&&alre[Nums(i1,i2+1,i3)]==0){
			Q.push(mp(A[0][i1]+A[1][i2+1]+A[2][i3],Nums(i1,i2+1,i3)));
			alre[Nums(i1,i2+1,i3)]=1;
		}
		if(i3+1<N[2]&&alre[Nums(i1,i2,i3+1)]==0){
			Q.push(mp(A[0][i1]+A[1][i2]+A[2][i3+1],Nums(i1,i2,i3+1)));
			alre[Nums(i1,i2,i3+1)]=1;
		}
	}
	return 0;
}


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

int main(){
  int n, t;
  cin >> n >> t;
  pair<int,int> s[n];
  for(int i=1;i<=n;i++){
    cin>>s[i].first>>s[i].second;
  }
  sort(s+1,s+n+1);
  int dp[t+3000];
  dp[0] = 0;
  int ans=0;
  for(int i=0; i<=n; i++){
    ans=max(ans,dp[t-1]+s[i].second);
      for(int j=t-1;j>=s[i].first;j--){
        dp[j]=max(dp[j],dp[j-s[i].first]+s[i].second);
      }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define INT_MAX (1<<31) - 1

using namespace std;


const int MAX_N = 1 << 17;

class SegTree{
private:
    int dat[2*MAX_N - 1];
public:
    int n;
    SegTree(int n);
    void update(int k, int a);
    int query(int a, int b, int k, int l, int r);
};

SegTree::SegTree(int n_){
    n = 1;
    // 葉の数 n を2のべき乗にする
    while(n < n_) n *= 2;
    for(int i=0; i<2*n-1; i++) dat[i] = INT_MAX;
}

// 配列arrのk番目の値をaに変更
void SegTree::update(int k, int a){
    // arr[k]に対応する葉の節点
    k += n - 1;
    // 葉をaに更新
    dat[k] = a;
    // 木を登りながら各節点の最小値を更新
    while (k > 0){
        k = (k - 1) / 2;
        dat[k] = min(dat[2*k+1], dat[2*k+2]);
    }
}

// [a, b) の最小値を求める
int SegTree::query(int a, int b, int k, int l, int r){
    if (r <= a || b <= l) return INT_MAX;
    if (a <= l && r <= b) return dat[k];
    else{
        // vl:左の子の値, vr:右の子の値 をそれぞれ再帰的に求める
        int vl = query(a, b, 2*k+1, l, (l+r)/2);
        int vr = query(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
}

int main(){
    int n, q; cin >> n >> q;
    vector<int> ans;
    SegTree s(n);
    for(int i=0; i<q; i++){
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0){
            s.update(x, y);
        }else{
            ans.push_back(s.query(x, y+1, 0, 0, s.n));
        }
    }
    for(int i=0; i<ans.size(); i++) cout << ans[i] << endl;

}



Measured memory_bytes: 4288
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007

int main(){
  int N;
  cin>>N;
  int a=0,b=0,c=0,d=0;
  for(int i=0;i<N;i++){
    string S;
    cin>>S;
    if(S=="AC"){
      a++;
    }else if(S=="WA"){
      b++;
    }else if(S=="TLE"){
      c++;
    }else{
      d++;
    }
  }
  cout<<"AC x "<<a<<endl;
  cout<<"WA x "<<b<<endl;
  cout<<"TLE x "<<c<<endl;
  cout<<"RE x "<<d<<endl;
}


Measured memory_bytes: 3632
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S = input()
    sum_d = 0
    for d in range(1,N//2+1):
        for i in range(N-2*d):
            if S[i] != S[i+d] and S[i+d] != S[i+2*d] and S[i+2*d] != S[i]:
                sum_d += 1

    r = 0
    g = 0
    b = 0
    for c in S:
        if c == 'R':
            r += 1
        elif c == 'G':
            g += 1
        elif c == 'B':
            b += 1

    print(max(r*g*b-sum_d,0))



if __name__ == '__main__':
    main()

Measured memory_bytes: 73372
#include <bits/stdc++.h>
#define N 100006
using namespace std;
char s[N];
long long n,m,k,x,y,l,r,cnt,ans,g[N],f[N],p[N];
inline int read()
{
	int x=0,c=getchar();while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();return x;
}
void print(long long x)
{
	if(x>9)print(x/10);putchar(x%10+48);
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	ans=min(1LL*m*k*(n&1),1LL*n*m*(k&1));
	print(min(ans,1LL*n*k*(m&1)));
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
res = 0
for x in A:
    res ^= x

for i in range(60):
    if (res >> i) & 1:
        for j in range(N):
            if A[j] >> i & 1:
                A[j] ^= 1 << i
start_point = 0
for i in range(60, -1, -1):
    X = 1 << i
    for j in range(start_point, N):
        if A[j] >> i & 1:
            A[start_point], A[j] = A[j], A[start_point]
            for k in range(N):
                if A[k] >> i & 1 and k!=start_point:
                    A[k] ^= A[start_point]
            start_point += 1
            break
plus=0
for x in A:
    plus ^=x
print(res+plus*2)

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

int N;
int F[102][10];
int P[102][11];
long long calc(int S) {
    long long ret = 0;
    int sum = 0;
    rep(i, N) {
        int cnt = 0;
        rep(j, 10) if ((S >> j & 1) && F[i][j]) { cnt++; }
        sum += cnt;
        ret += P[i][cnt];
        // if(S==32) printf("%d: %d, %d\n", __LINE__, cnt, P[i][cnt]);
        // cnts.push_back(cnt);
    }
    if (sum) {
        // if(S==32) cout << S << ": " << ret << ", " << sum << endl;
        return ret;
    }
    return -1e18;
}
int main() {
    cin >> N;
    rep(i, N) rep(j, 10) cin >> F[i][j];
    rep(i, N) rep(j, 11) cin >> P[i][j];
    // rep(i, N) rep(j, 10) printf("P[%d][%d] = %d\n", i, j, P[i][j]);

    long long ans = -1e18;
    rep(S, 1 << 10) if (S) {
        ans = max(ans, calc(S));
    }

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


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back

const int maxm = 1000000000 + 7;


using namespace std;


int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	
	int a,b,x;

	cin>>a>>b>>x;

	if(a>x || (x-a) >= b)
	{
		cout<<"NO"<<endl;
	}

	else
	{
		cout<<"YES"<<endl;
	}
  


}

Measured memory_bytes: 3620
if __name__ == "__main__":
    n = int(input())
    xs = sorted(list(map(int, input().split())))

    min_total_energy = 1e9
    for p in range(xs[0], xs[-1] + 1):
        total_energy = 0
        for i in range(n):
            total_energy += (xs[i] - p)**2
        min_total_energy = min(min_total_energy, total_energy)

    print(min_total_energy)


Measured memory_bytes: 2940
// B - Two Colors Card Game
// https://atcoder.jp/contests/abc091/tasks/abc091_b
#include <bits/stdc++.h>
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007      //10^9+7
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define Vec(K, L, N, S) vector<L> K(N, S)
#define rt sqrt
#define pb push_back
#define eb emplace_back
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using P = pair<string, lli>;
using vs = vector<string>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli a, b, c, h, m, n, ans = 0, count = 1;
  cin >> n;
  vs s(n);
  rep(i, 0, n)
  {
    cin >> s[i];
  }
  cin >> m;
  vs t(m);
  rep(i, 0, m)
  {
    cin >> t[i];
  }
  auto calc = [&](string z) {
    lli buff = 0;
    for (string e : s)
    {
      if (e == z)
        buff++;
    }
    for (string f : t)
    {
      if (f == z)
        buff--;
    }
    return buff;
  };
  for (string z : s)
  {
    ans = max(ans, calc(z));
  }
  cout << ans << endl;
}

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

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1){
        c = c - b;
        if(c<=0){
            cout<<"Yes"<<endl;
            break;
        }
        a = a - d;
        if(a<=0){
            cout<<"No"<<endl;
            break;
        }
    }


}

Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <utility>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
   
 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n,k,r,s,p;
  long long sum=0;
  string t;
  vector<vector<bool> > out(100000,vector<bool>(3,false));

  cin>>n>>k>>r>>s>>p>>t;

  int nasu;
  for(nasu=0;nasu<k;nasu++){
     if(t[nasu]=='r'){
	out[nasu][1]=true;
	sum+=p;
      
    }
	
    if(t[nasu]=='s'){
	out[nasu][2]=true;
	sum+=r;
    }
    
    if(t[nasu]=='p'){
	out[nasu][3]=true;
	sum+=s;
      }
  }
  
  for(int i=nasu;i<n;i++){
    if(t[i]=='r'){
      if(!out[i-k][1]){
	out[i][1]=true;
	sum+=p;
      }
    }
	
    if(t[i]=='s'){
      if(!out[i-k][2]){
	out[i][2]=true;
	sum+=r;
      }
    }
    
    if(t[i]=='p'){
      if(!out[i-k][3]){
	out[i][3]=true;
	sum+=s;
      }
    }
  }
  cout<<sum<<'\n';
  return 0;
}


Measured memory_bytes: 7552
import math
s = list(map(int, input()))

sumofsum = 0

N = len(s)
def combin(n, k):
    com = math.factrial(n) * math.factrial(n - k) / math.factrial(k)
    return con

for i in range(N):
    for j in range(N - i):
        if j == 0:
            if i == 0:
                sumofsum += (10 ** (N - i - j - 1)) * s[i]
            else:
                sumofsum += (10 ** (N - i - j - 1) )* (2 ** (i))* s[i]
        else:
            if i == 0:
                sumofsum += (10 ** (N - i - j - 1)) * (2 ** (j - 1)) * s[i]
            else:
                sumofsum +=( 10 ** (N - i - j - 1)) * (2 ** (i))* (2 ** (j - 1)) * s[i]


print(sumofsum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);++i)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
  
const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
 
const int MAX=510000;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
   
  string s;
  cin >> s;
  ll sum =0;
  int n=s.size();
  rep(i,n) sum+=s[i]-'0';
  if(sum%9==0)cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 3764
#include<iostream>
#include<cstring>
  
using namespace std;
  
const int Height = 5100;
const int Width = 5;
char field[Height][Width];
int top,ans;
int dx[] = {1,0};
int dy[] = {0,-1};
  
void print(int h, int w){
  
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++) cout << field[i][j];
    cout << endl;
  }
  cout << endl; 
}

bool isInside(int h, int w){ return 0<=h&&h<Height&&0<=w&&w<Width;}

int getH(int d, int len, int pos){
  for(int i = top+10; i>=0; i--){
    int h = i;
    int w = pos;
    for(int j = 0; j < len; j++){
      if(field[h][w] != '?' || !isInside(h,w)) return i+1;
      h += dy[d];
      w += dx[d];
    }
  }
  return 0;
}
 
void down(int n){
  
  for(int i = n; i <= top+6; i++)
    for(int j = 0; j < Width; j++) field[i][j] = field[i+1][j];
   top--;
}
 
void erase(){
 
  for(int i = 0; i <= top+6; i++){
    bool f = true;
    for(int j = 0; j < Width; j++) if(field[i][j] == '?') f = false;
    if(f){
      ans -= 5;
      down(i--);
    }
  }
}
  
void put(int d, int len, int pos){
  
  int nex = getH(d,len,pos);
  top = max(top,nex);
  
  int h = nex;
  int w = pos;
  
  for(int i = 0; i < len; i++){
    field[h][w] = '.';
    h += dy[d];
    w += dx[d];
  }
}
  
int main(){
  
  int n;
  while(cin >> n && n){
    memset(field,'?',sizeof(field));
    ans = top = 0;
     
    while(n--){
      int d, len, pos;
      cin >> d >> len >> pos;
      ans += len;
      put(d-1,len,pos-1);
      erase();
    }
    cout << ans << endl;
    //  print(10,5);
  }
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 998244353;


ll modPow(ll a, ll n, ll p) {
  if (n == 0) return 1;
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  ll t = modPow(a, n / 2, p);
  return (t * t) % p;
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll fact[200003];
ll ifact[200003];
ll Combination(ll a,ll b) {
  ll s = (fact[a] * ifact[b]) % Mod;
  return (s * ifact[a-b]) % Mod;
}


int main() {
  fact[0] = 1;
  ifact[0] = 1;
  for (int i = 1; i <= 200003; i++) {
    fact[i] = fact[i-1] * i;
    fact[i] %= Mod;
    ifact[i] = modinv(fact[i],Mod);
  }
  ll N,M,K;
  cin >> N >> M >> K;
  if (M == 1) {
    if (N-1 == K) {
      cout << 1 << endl;
      return 0;
    } else {
      cout << 0 << endl;
      return 0;
    }
  }
  ll ans = 0;
  for (int i = 0; i <= K; i++) {
    ll res = 1;
    res *= M;
    res *= modPow(max(1ll,M-1),N-1-i,Mod);
    res %= Mod;
    res *= Combination(max(1ll,N-1),i);
    res %= Mod;
    ans += res;
    ans %= Mod;
  }
  if (ans < 0) {
    ans += Mod;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6772
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	while(	cin>>s)
	{
	int flag=1;
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		if(i%2==0)
		{
			if(s[i]=='L')
			{
				flag=0;
				break;
			}
			
		}
		else
		{
			if(s[i]=='R')
			{
				flag=0;
				break;
			}
		}
	}
	if(flag==1)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
 int a,b,c,d;
  cin >> a >> b >> c >> d;
  int e = a+b;
  if(e>=d){
    cout << min(a, d) << endl;
  }
 else{
   cout << a - d + e << endl;
 }
}


Measured memory_bytes: 3628
X,N = map(int, input().split())
p = []
if N > 0:
  p = list(map(int, input().split()))
a = list(range(0, 111))
a = [item for item in a if item not in p]
res = a[0]
m = abs(res - X)
for i in a:
  j = abs(i - X)
  if j < m:
    m = j
    res = i
    
print(res)

Measured memory_bytes: 9096
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;

namespace ConsoleAppKEYENCEString
{
    class Program
    {
        static void Main(string[] args)
        {

            // 整数の入力
            //int a = int.Parse(Console.ReadLine());
            // スペース区切りの整数の入力
            //string[] input = Console.ReadLine().Split(' ');
            //int b = int.Parse(input[0]);
            //int c = int.Parse(input[1]);
            // 文字列の入力
            string s = Console.ReadLine();
            //
            // プログラム
            //
            string ans="NO";
            string keyence = "keyence";
            string word;
            for(int i = 0; i < s.Length; i++)
            {
                for(int j = 0; j < (s.Length-i); j++)
                {
                    word = s.Remove(i,j);
                    if (word.Equals(keyence))
                    {
                        ans = "YES";
                        //Console.WriteLine("入力:" + s);
                        //Console.WriteLine(word);
                        //Console.WriteLine(ans);
                    }
                }
            }
            //出力
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i > 0; i--)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
void solve() {
  ll N;
  cin >> N;
  vector<string> s(N);
  REP(i, N) {
    cin >> s[i];
  }
  map<string, ll> counter;
  for(auto si: s) {
    sort(ALL(si));
    counter[si]++;
  }
  ll sum = 0;
  for(auto c: counter) {
    ll v = c.second;
    sum += v * (v - 1) / 2;
  }
  cout << sum << endl;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 16640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int times = 1;
		try {
			Scanner sc = new Scanner(System.in);
			while (true) {
				int x = Integer.parseInt(sc.next());
				if (x == 0) {
					break;
				} else {
					System.out.println("Case " + times + ": " + x);
					times += 1;
				}
			}
			sc.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 27844
n = int(input())
w = list(map(int, input().split()))
ans = sum(w)
for i in range(1, n):
    w1 = w[:i]
    w2 = w[i:]
    if abs(sum(w1)-sum(w2)) < ans:
        ans = abs(sum(w1)-sum(w2))
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>

#define nl '\n'

#define PI 3.14159265

using namespace std;

int x, y;

int main(){
    cin >> x >> y;
    cout << x + (y/2);

}

//g++ -std=c++14 comp.cpp -o b; ./b.exe


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

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

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

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

struct Data
{
    pll g;
    double theta;
};

Data D[105];

int main()
{
    ll N;
    cin >> N;
    REP(i, N)
    {
        ll x, y;
        cin >> x >> y;
        double c = x / sqrt(x * x + y * y);
        D[i].g = pll(x, y);
        D[i].theta = acos(c);
        if (y <= 0)
            D[i].theta = 2.0 * M_PI - D[i].theta;
    }

    sort(D, D + N, [](Data a, Data b) { return a.theta < b.theta; });

    double max = 0;
    REP(i, N)
    {
        double x = 0, y = 0;
        REP(j, N)
        {
            x += D[(i + j) % N].g.first;
            y += D[(i + j) % N].g.second;
            max = std::max(max, sqrt(x * x + y * y));
        }
    }
    cout << OF64 << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_N (int)1e6
const int INF = (int)1e9 + 1;

typedef struct {
    int f, s;
} Pair;

int PairCmp( const void* a, const void* b ) { return ((Pair*)a)->f - ((Pair*)b)->f; }

int n, q;
Pair tmp[MAX_N];
int s[MAX_N];//下からi番目のスコア: s[i]
int f[MAX_N];//i番の人がスコア何番目か: f[i]

int m = 0;
int leader[MAX_N];//リーダーの番号をスコア順で記録

void Insert( int v ) {
    int i = 0, j;
    for ( ; i<m; ++i ) {
	if ( leader[i] > v ) break;
    }
    for ( j=m; j>i; --j ) {
	leader[j] = leader[j-1];
    }
    leader[i] = v;
    ++m;
}

void Erase( int v ) {
    int i = 0, j;
    for ( ; i<m; ++i ) {
	if ( leader[i] == v ) break;
    }
    for ( j=i+1; j<m; ++j ) {
	leader[j-1] = leader[j];
    }
    --m;
}

int LowerBound( int v ) {
    int l = 0, r = n;
    while ( r - l > 1 ) {
	int mid = ( l + r )/2;
	if ( s[mid] >= v ) r = mid;
	else l = mid;
    }
    return v <= s[l] ? l : r;
}

int UpperBound( int v ) { return LowerBound(v+1); }

int main() {

    int i;
    char op[10];
    int arg;

    scanf("%d %d", &n, &q);

    for ( i=0; i<n; ++i ) {
	scanf("%d", &tmp[i].f);
	tmp[i].s = i;
    }
    qsort( tmp, n, sizeof(Pair), PairCmp );

    for ( i=0; i<n; ++i ) {
	s[i] = tmp[i].f;
	f[tmp[i].s] = i;
    }

    while ( q-- ) {

	scanf("%s %d", op, &arg);

        if      ( op[0] == 'A' ) Insert( f[arg-1] );
        else if ( op[0] == 'R' ) Erase( f[arg-1] );
        else {//CHECK

            int fail_r = -1, succ_r = INF;//条件を満たさない最大のr と 満たす最小のr

            while ( succ_r - fail_r > 1 ) {
		
                int mid = (succ_r + fail_r)/2;//新しいr

                int count = 0; //リーダーによってカバーされる生徒の総数
		int prev = -1; //リーダーのうちスコアが一つ下の人のインデックス
                for ( int i=0; i<m; ++i ) {

		    int idx = leader[i];

		    //全スコア中でリーダーからr引いたスコアの人のインデクス
                    int l_idx = LowerBound( s[idx] - mid );

		    //全スコア中でリーダーのスコアのすぐ下の人のインデクス
                    int r_idx = UpperBound( s[idx] ) - 1;

                    if ( l_idx <= prev ) l_idx = prev + 1;//一つ下のリーダーの手前まで

                    count += r_idx - l_idx + 1;//カウントにリーダー自身を含める
		    
                    prev = r_idx;
                }

                if ( n - count <= arg ) succ_r = mid;
                else fail_r = mid;
            }

	    if ( succ_r == INF ) printf("NA\n");
	    else printf("%d\n", succ_r);
        }
    }
    
    return 0;
}



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

using namespace std;

typedef pair<long long, int> P; // cordinate, index

int main() {
    int N,K;
    cin >> N >> K;

    vector<P> x,y,z;

    for(int i=0 ;i<N; ++i) {
        long long a,b,c,d,e,f;
        cin >> a >> b >> c >> d >> e >> f;
        x.push_back(P(a,i));
        y.push_back(P(b,i));
        z.push_back(P(c,i));
        x.push_back(P(d,i));
        y.push_back(P(e,i));
        z.push_back(P(f,i));
    }

    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    sort(z.begin(),z.end());

    vector<int> rnkx[N];
    vector<int> rnky[N];
    vector<int> rnkz[N];

    long long valx[2*N],valy[2*N],valz[2*N];

    for(int i=0; i<(int)x.size(); ++i) {
        P px=x[i];
        P py=y[i];
        P pz=z[i];
        rnkx[px.second].push_back(i);
        rnky[py.second].push_back(i);
        rnkz[pz.second].push_back(i);
        valx[i]=(i<2*N-1?x[i+1].first-x[i].first:0);
        valy[i]=(i<2*N-1?y[i+1].first-y[i].first:0);
        valz[i]=(i<2*N-1?z[i+1].first-z[i].first:0);
    }

    int mp[2*N][2*N][2*N];

    for(int i=0; i<2*N; ++i) {
        for(int j=0; j<2*N; ++j) {
            fill(mp[i][j],mp[i][j]+2*N,0);
        }
    }

    for(int i=0; i<N; ++i) {
        for(int mpx=rnkx[i][0]; mpx<rnkx[i][1]; ++mpx) {
            for(int mpy=rnky[i][0]; mpy<rnky[i][1]; ++mpy) {
                for(int mpz=rnkz[i][0]; mpz<rnkz[i][1]; ++mpz) ++mp[mpx][mpy][mpz];
            }
        }
    }

    long long ans=0;
    for(int i=0; i<2*N; ++i) {
        for(int j=0; j<2*N; ++j) {
            for(int k=0; k<2*N; ++k) {
                if(mp[i][j][k]>=K) ans+=valx[i]*valy[j]*valz[k];
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 7084
#include <stdio.h>

#define N 100000

int S[N],T[N];

int n,q;

int binarySearch(int);

int main(){

  int i,j,c=0;

  scanf("%d",&n);

  for(i=0; i<n; i++){
    scanf("%d",&S[i]);
  }
  
  scanf("%d",&q);
  
  for(i=0; i<q; i++){
    scanf("%d",&T[i]);
  }


 for(i=0; i<q; i++){
   
    if(binarySearch(T[i]) == 1) c++;
  }

  printf("%d\n",c);


  return 0;
}

int binarySearch(int key){

  int left=0,right=n;
  int mid;

  while(left < right){
    mid = (left + right)/2;

    if(S[mid] == key) return 1;
    else if(key < S[mid]) right = mid;
    else left = mid +1;
  } 

  return 0;
}

Measured memory_bytes: 1188
import java.util.*
import java.math.*
import java.lang.Math.*

private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = { readLine()!!.toInt() }
private val readLong: ()->Long = { readLine()!!.toLong() }
private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readListLong: ()->List<Long> = { readLine()!!.split(' ').map(String::toLong) }
private val errPrintln: (String)->Unit = { msg -> System.err.println(msg) }
private val MOD = 1e9.toLong()+7


fun solveC(N: Int, A:Int, B:Int, C:Int, L:List<Int>): Int {
    var res = Int.MAX_VALUE

    val X = ArrayList<Int>()
    val Y = ArrayList<Int>()
    val Z = ArrayList<Int>()

    fun dfs(n: Int) {
        if (n>=N) {
            if (X.size == 0 || Y.size == 0 || Z.size == 0) return

            var cost = (X.size-1 + Y.size-1 + Z.size-1) * 10
            cost += abs(A-X.sum()) + abs(B- Y.sum()) + abs(C - Z.sum())
            res = min(res, cost)
            return
        }

        for(i in 0 until 4) {
            when (i) {
                0-> {
                    X.add(L[n])
                }
                1 -> {
                    Y.add(L[n])
                }
                2 -> {
                    Z.add(L[n])
                }
            }

            dfs(n + 1)

            when (i) {
                0-> {
                    X.removeAt(X.lastIndex)
                }
                1 -> {
                    Y.removeAt(Y.lastIndex)
                }
                2 -> {
                    Z.removeAt(Z.lastIndex)
                }
            }
        }
    }

    dfs(0)

    return res
}


fun main(args: Array<String>) {
    val (N,A,B,C) = readListInt()
    val L = Array<Int>(N){0}
    for(i in 0 until N) {
        L[i] = readInt()
    }

    val ans = solveC(N, A, B, C, L.toList())

    println(ans)
}


Measured memory_bytes: 41512
N=int(input())
Agents=list(map(int,input().split()))


##Miss 1
# from itertools import combinations

# comb = list(combinations([i for i in range(N)],2))

# cnt=0
# for i in comb:
#     if Agents[i[0]] + Agents[i[1]] == abs(i[0] - i[1]):
#         print(i[0],i[1])
#         cnt+=1

# print(cnt)

# Miss 2
# for i in range(0,N):
#     k=Agents[i]-(i+1)
#     if k<i:
#         k=i+1
#     for j in range(k,N):
#         if Agents[i]+Agents[j]==abs(i-j):
#             # print(i,j,Agents[i],Agents[j])
#             cnt+=1


L={}
for i in range(N):
    s = i+1 + Agents[i] 
    if s in L:
        L[s]+=1
    else:
        L[s]=1

R={}
for j in range(N):
    s= j+1 - Agents[j]
    if s in R:
        R[s]+=1
    else:
        R[s]=1
cnt=0

for key,value in L.items():
    cnt += R.get(key,0) * value
# for key,value in L.items():
#     for key2,value2 in R.items():
#         if int(key) < int(key2) and value == value2:
#             cnt+=1


print(cnt)


Measured memory_bytes: 59344
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M (1000000007)
#define N (100010)
int n,a[N];
double ans;

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	ans=a[1];
	for (int i=2;i<=n;++i){
		ans=(ans+a[i])/2;
	}
	printf("%lf",ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int n; cin >> n;
    int t[n + 1], x[n + 1], y[n + 1];
    t[0] = 0, x[0] = 0, y[0] = 0;

    bool traveling = true;

    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> x[i] >> y[i];
        // 時刻iと時刻i-1の差分を計算
        int dt = t[i] - t[i - 1];
        int ds = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);

        // 旅行がプラン実行が不可能な場合
        if ((dt < ds) || (ds % 2 == 0 && dt % 2 != 0) || (ds % 2 != 0 && dt % 2 == 0)) traveling = false;
    }

    if (traveling) cout << "Yes" << endl;
    else           cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

long long N;
vector<pair<long long, long long>> E;

int main() {
	cin >> N;
	for (long long i = 2; i * i <= N; i++) {
		if (N % i != 0) continue;
		int cnt = 0;
		while (N % i == 0) { N /= i; cnt++; }
		E.push_back(make_pair(i, 1LL * cnt));
	}
	if (N >= 2) E.push_back(make_pair(N, 1LL));

	long long Answer = 0;
	for (int i = 0; i < E.size(); i++) {
		long long maxn = 0;
		for (int j = 1; j <= 100; j++) {
			if (j * (j + 1) / 2 <= E[i].second) maxn = j;
		}
		Answer += maxn;
	}
	cout << Answer << endl;
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;

int main(){
	int H,W;
	cin >> H >> W;
	while(H != 0 || W != 0){
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
		cin >> H >> W;
	}
	return 0;
}


Measured memory_bytes: 3084