akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define INF 2000000000
typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1LL<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1LL<<(i))))
#define setbit1(n,i) ((n)|(1LL<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define DBG(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define fi first
#define se second
#define PI (acos(-1))
#define fastread ios::sync_with_stdio(false);cin.tie(NULL)
#define mod (1000000007)
#define asz 500005
template<class T,class V> ostream& operator<<(ostream &s,pair<T,V> a)
{
    s<<a.fi<<' '<<a.se;
    return s;
}
int main()
{
    fastread;
    ll T=1;
//    cin>>T;
    for(ll qq=1;qq<=T;qq++)
    {
        ll n;
        cin>>n;
        vi a(n);
        for(auto &x:a)cin>>x;
        sort(a.begin(),a.end());
        ll lo=0,hi=n-1;
        while(lo<hi){
            ll mid=(lo+hi)/2;
            ll cur=2*a[mid];
            int i=0;
            for(;i<n;i++){
                if(i==mid)continue;
                if(a[i]>cur)break;
                cur+=2*a[i];
            }
            if(i==n)hi=mid;
            else lo=mid+1;
        }
        cout<<n-lo<<endl;
    }
    return 0;
}

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

int main (){
    vector<int> n(3);
    rep(i,3) cin >> n[i]; 
    sort(n.begin(),n.end());
    if(n[0]==5&&n[1]==5&&n[2]==7) cout << "YES" << endl;
    else cout << "NO" <<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    m = 1
    k = int(n ** 0.5)

    ans = len(str(n))
    for i in range(k + 1, 0, -1):
        if n % i == 0:
            n = n // i
            m *= i
            tmp = max(len(str(m)), len(str(n)))
            ans = min(ans, tmp)
            break

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9356
# -*- coding: utf-8 -*-

N,K = list(map(int, input().rstrip().split()))
H_list = list(map(int, input().rstrip().split()))
#-----

sort_H = sorted(H_list, reverse=True)
cnt = 0

for i in range(K, len(sort_H)):
    cnt += sort_H[i]

print(cnt)


Measured memory_bytes: 26764
#include <bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define scd(x) scanf("%d",&x)
#define scdd(x,y) scanf("%d%d",&x,&y)
const int maxn=3e5+10;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
int arr[maxn],sum[maxn*4],val[maxn*4];
void push_up(int rt) {
    int l=lson,r=rson;
    sum[rt]=sum[l]+sum[r];
    val[rt]=min(val[l],val[r]);
}
void build(int rt,int l,int r) {
    if(l==r) {
        sum[rt]=1;
        val[rt]=l;
        return ;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(rt);
}
void update(int rt,int l,int r,int pos) {
    if(l==r) {
        sum[rt]=0;
        val[rt]=INF;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(lson,l,mid,pos);
    else update(rson,mid+1,r,pos);
    push_up(rt);
}
pii query(int rt,int l,int r,int ql,int qr) {
    if(ql<=l&&qr>=r) {
        return pii(sum[rt],val[rt]);
    }
    int mid=(l+r)/2;
    pii ans=pii(0,0);
    if(ql<=mid)ans=query(lson,l,mid,ql,qr);
    if(qr>mid&&ans.first==0)ans=query(rson,mid+1,r,ql,qr);
    return ans;
}
vector<int>vec;
multiset<int>s;
int find_pos(int x,int l,int r){
    int ans=-1;
    while(r>=l){
        int mid=(l+r)/2;
        if(arr[mid]>=x){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ans;
}
int main() {
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif // LOCAL
    int n;
    //cout<<(1<<18)<<endl;
    scd(n);
    int la=1<<n;
    for(int i=1; i<=la; i++) {
        scd(arr[i]);
        s.insert(arr[i]);
    }
    sort(arr+1,arr+la+1,greater<int>() );
   // build(1,1,la);
    bool flag=false;
    vec.clear();
    vec.push_back(arr[1]);
    //update(1,1,la,1);
    multiset<int>::iterator it=s.lower_bound(arr[1]);
    s.erase(it);
    while(!flag) {
        if(vec.size()==la) {
            flag=true;
            break;
        }
        int siz=vec.size();
        //sort(vec.begin(),vec.end(),greater<int>() );
        //cout<<"?"<<endl;
        for(int i=0; i<siz; i++) {
//            int pos=find_pos(vec[i],1,la);
//            if(pos==la){
//                flag=true;break;
//            }
//            pii ans=query(1,1,la,pos+1,la);
//            if(ans.first==0){
//                flag=true;break;
//            }
//            update(1,1,la,ans.second);

            multiset<int>::iterator it = s.lower_bound(vec[i]);
            if(it==s.begin()){
                flag=true;break;
            }
            it--;
            vec.push_back(*it);
            s.erase(it);
        }
    }
    if(vec.size()==la)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 15868
#include <iostream>
#include <vector>

int main() {
  unsigned N, K;
  std::cin >> N >> K;
  std::vector<long long> a(N);
  std::vector<long long> interval(N);
  std::vector<long long> left(N);
  std::vector<long long> right(N);
  for (unsigned i = 0; i < N; ++i) {
    std::cin >> a[i];
  }
  interval[K - 1] = 0ll;
  for (unsigned i = 0; i < K && i < N; ++i) {
    interval[K - 1] += a[i];
  }
  for (unsigned i = K; i < N; ++i) {
    interval[i] = interval[i - 1] - a[i - K] + a[i];
  }
  left[0] = 0ll;
  right[N - 1] = 0ll;
  for (unsigned i = 1; i < N; ++i) {
    left[i] = std::max(left[i - 1], left[i - 1] + a[i - 1]);
    right[N - i - 1] = std::max(right[N - i], right[N - i] + a[N - i]);
  }
  long long ans = 0ll;
  for (unsigned i = K - 1; i < N; ++i) {
    long long tmp = 0ll;
    tmp += left[i - K + 1];
    if (interval[i] > 0) {
      tmp += interval[i];
    }
    tmp += right[i];
    ans = std::max(ans, tmp);
  }
  std::cout << ans;
  return 0;
}

Measured memory_bytes: 3328
#include<cstdio>
int n,ans;
bool p[1000005]={1,1};
int main()
{
	int i,j;
	for(i=2;i<=997;i++)
		if(!p[i])
			for(j=i;j*i<1000000;j++)
				p[j*i]=1;
	while(~scanf("%d",&n))
	{
		ans=0;
		for(i=2;i<=n;i++)
			if(!p[i]) ans++;
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 3540
/*　　　　　　　{:i:i:|i:i:/l/l--　 　 　--l/li:i:i|i:i:i:i}
　　　　　　 　 {:rx|:i:i ィi芥ミ 　 　 .ィi芥ミｉ:ｉ|ﾍ:i:i:}
.　　　 　 　 　 ｛ﾏ|ｉ:  {::’:} 　 　 　{:‘::} :ｉ:i:|〉｝:/
　　 　 　 　 　 乂|:i:| ｀¨¨¨¨´ 　 　　｀¨¨¨´  :i:ｉ:|ｼ/
　 　 　 　 　 　 ﾉ:|:i|　　　　　　′　　　 　   |:i:i:|ﾂ
　　　　　　　　/:/|:i:| ､　　　 　_ _ 　　　　  |:i:i:|
　 　 　　 　 /:/ .|:i:|/ ＼　　　 　 　     ｨ〔|:i:/
　　 　 　  　 〈;/ く刈＿ 个 　   -   　＜}　./|/_〉
　　     　　 r-っ'~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ~ﾞ|___
　　 　     /／ニつ　　　　　　 ､　　　　　　　ノﾆﾆ　＼
.　　　     |　　ニ⊃ 　./　/　 ──   /　/　　..⊆ﾆﾆ　　:|
.　　　     |　　丁´　 /|￣|￣  ─‐ /|￣|￣ 　 .￣|丁 　|
.　　　     |　　ﾉ.  　 |￣|￣  ─‐  |￣|￣ 　 　.|八 　|
.　　　     |　　||. 　 |￣|￣ |￣| |￣|￣ 　   .|　|
.　 　 　   |  　||   　￣￣￣　￣ 　￣￣￣　　  .|　|  |
.　 　 　  　    ||＿＿＿＿＿＿＿＿＿＿＿＿______|__　　 ',
　 　      ,′　 | ７ﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆ}  ,′
.　　     {　　　|/　}ﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆ{/ 　 　
*///讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐讐。
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>

using namespace std;

#define rep(a) _rep(0,int(a))
#define repj(a) for(int j=0;j<int(a);j++)
#define _rep(a,b) for(int i=int(a);i<int(b);i++)
#define ll long long
#define fst first
#define snd second
#define pf(b) printf("%.12f\n",(double)b)
#define _GLIBCXX_DEBUG
const double pai = 3.1415926535897;
#define _cos(n) cos(n*pai/180)

//factorial(練習)　階乗
int fact(int n) {
	int a = 1;
	for (int i = 1;i <= n;i++) a *= i;
	return a;
}
int sa(int n, int m) {      //差！
	if (n < m)return m - n;
	else return n - m;
}

int n;
signed main() {
	cin >> n;
	if (n < 1200)cout << "ABC" << endl;
	else if (n < 2800)cout << "ARC" << endl;
	else cout << "AGC"<< endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
  int i,j,k,l;
  int n;
  int t1,t2;
  int p1,p2;
  int win[200]={0};
  int rank[200];

  cin>>n;
  for(i=0;i<n*(n-1)/2;i++){
    cin>>t1>>t2>>p1>>p2;

    if(p1>p2){
      win[t1-1]+=3;
    }
    else if(p1<p2){
      win[t2-1]+=3;
    }
    else{
      win[t1-1]++;
      win[t2-1]++;
    }
  }

  for(i=0;i<n;i++){
    rank[i]=1;
    for(j=0;j<n;j++){
      if(win[i]<win[j])rank[i]++;
    }
    cout<<rank[i]<<endl;
  }
  return(0);
}

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

int main()
{
  string s;
  char ans;
  cin >> s;
  int64_t k, tmp = 0;
  cin >> k;

  for (c : s)
  {
    if (c == '1')
    {
      ++tmp;
      continue;
    }
    else
    {
      ans = c;
      break;
    }
  }
  if (tmp >= k) cout << "1\n";
  else cout << ans << "\n";
}

Measured memory_bytes: 256
def Triple_Dots():
    K = int(input())
    S = input()
    S_list = list(S)
    output = ''
    if len(S_list) <= K:
        output = S
    else:
        for i in range(0, K):
            output += S_list[i]
        output += "..."
    print(output)
    
Triple_Dots()

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<string> u(12);
  vector<double> x(12);
  for(int i=0;i<N;i++)cin >> x[i] >> u[i];
  double ans=0;
  for(int i=0;i<N;i++){
    if(u[i]=="JPY"){ans+=x[i];}
    else{ans+=x[i]*380000;}
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
// https://beta.atcoder.jp/contests/abc071

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<char> chars;
    for (char c = 'a'; c <= 'z'; c++) chars.insert(c);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (chars.find(s[i]) != chars.end()) chars.erase(s[i]);
    }

    if (!chars.empty()) cout << *chars.begin() << endl;
    else cout << "None" << endl;

    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>


int main() {
	int n, q, S[10000], T[500];
	int i, j, count = 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++) {
		for (j = 0; j < n; j++) {
			if (T[i] == S[j]) {
				count++;
				break;
			}
		}
	}

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

	return 0;
}

Measured memory_bytes: 640
/**************************************************
 *
 *
 *
 *
 *
 **************************************************/
#include <stdio.h>
void swap(int H[], int i, int j){
  int tmp=H[i];
  H[i]=H[j];
  H[j]=tmp;
}
/**************************************************
 *配列array[p..r]をarray[p..q-1]の各要素がarray[q]以下
 array[q+1..r]の各要素がarray[q]より大きい
 *二つの部分に分割し, 添字qを返す
 *
 *
 *
 **************************************************/
int partition(int array[], int p, int r){
  int x=array[r];  //配列の最後の要素, これを基準にしてarrayを二つに分割する
  int i=p-1, j;  //i: x以下の配列の末尾の添字, j : 先頭
  for(j=i+1; j<r; ++j){
	if(array[j]<=x){
	  ++i;
	  swap(array, i, j);
	}
  }
  swap(array, i+1, r);
  return i+1;
}
int main(){
  /*
   *変数
   */
  int length;  //配列Aの長さ
  int A[100005];  //入力値を入れる配列
  int i;  //ループの制御変数
  int q;
  /*
   *数値の読み込み
   */
  /* 長さの読み込み */
  scanf("%d", &length);
  /* 入力値の読み込み */
  for(i=0; i<length; ++i){
	scanf("%d", &A[i]);
  }
  q=partition(A, 0, length-1);
  for(i=0; i<length; ++i){
	if(i!=0)
	  printf(" ");
	if(i==q)
	  printf("[%d]", A[i]);
	else
	  printf("%d", A[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    rep1(i, 9) {
        rep1(j, 9) {
            if (i*j==n) {
                puts("Yes");
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}

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


int main()
{
    int N, W; cin >> N >> W;
    int vi,wi;

    vector <long long > dp (W+1, 0);

    for(int i = 0; i < N; i++){
        cin >> wi >> vi;
        for(int j = W; j >= wi; j--){
            dp[j] = max (dp[j], dp[j-wi] + vi);
        }
    }
    cout << dp[W] << "\n";
    



    return 0;
}

Measured memory_bytes: 1024
n,a,b=map(int,input().split())
h=[int(input()) for _ in [0]*n]
c=a-b
from math import ceil

def b_search(a,b,value,lim):
    med=(a+b)//2
    if a==b:return a
    elif lim=="upper":
        if a+1==b:
            if value(b):return b
            else:return a
        elif value(med):return b_search(med,b,value,lim)
        else:return b_search(a,med-1,value,lim)
    else:
        if a+1==b:
            if value(a):return a
            else:return b
        elif value(med):return b_search(a,med,value,lim)
        else:return b_search(med+1,b,value,lim)
        
def value(x):
    return sum([max(ceil((i-x*b)/c),0) for i in h])<=x
    
print(b_search(1,10**9,value,"lower"))

Measured memory_bytes: 10976
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

int a[100][3];

int main() {
    int n;
    cin >> n;
    rep(i,n) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    for (int cx = 0; cx <= 100; cx++) {
        for (int cy = 0; cy <= 100; cy++) {
            int h = 0;
            bool ok = true;
            rep(i,n) {
                if (a[i][2] == 0) continue;
                int now = a[i][2] + abs(a[i][0]-cx) + abs(a[i][1]-cy);
                if (h == 0) {
                    h = now;
                    continue;
                }
                if (h != now) ok = false;
            }
            if (!ok) continue;
            rep(i,n) {
                int now = max(h - abs(a[i][0]-cx) - abs(a[i][1]-cy), 0);
                if (now != a[i][2]) ok = false;
            }
            if (ok) {
                cout << cx << " " << cy << " " << h << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
int main(void){
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);
    if(0<=a && a < b && b < c && c<=100){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 2060
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <queue>
#include <iomanip>
#include <iterator>

#define MOD 1000000007
#define INF 1000000001

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


template <class T>
ostream &operator<<(ostream &o, const vector<T>&obj) {
    o << "["; for (int i = 0; i < (int)obj.size(); ++i) o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const pair<T, U>&obj) {
    o << "(" << obj.first << ", " << obj.second << ")"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const map<T, U>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const queue<T>&obj) {
    queue<T> obj_cp = obj;
    bool first = true;
    o << "{";
    while (!obj_cp.empty()) { o << (!first ? ", " : "") << obj_cp.front(); obj_cp.pop(); first = false; }
    o << "}"; return o;
}

void print() {
    cout << "\n";
}
template<class Head, class... Body>
void print(Head head, Body... body) {
    cout << head << " ";
    print(body...);
}


int main(int argc, char const *argv[]) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    string ans;
    while (true) {
        C -= B;
        if (C <= 0) {
            ans = "Yes";
            break;
        }
        A -= D;
        if (A <= 0) {
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


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

#define N 100000

int main(void){
    vector<bool> prime(N+1,true);
    prime[0]=prime[1]=false;
    for (size_t i = 0; i <= sqrt(N); i++)
    {
        if (prime[i])
        {
            for (size_t j = 2; i*j <= N; j++)
            {
                prime[i*j]=false;
            }
        }
    }
    vector<int> likeCnt(N);
    for (size_t i = 1; i <= N; i++)
    {
        likeCnt[i]=likeCnt[i-1];
        if (i%2==1&&prime[i]&&prime[(i+1)/2])
        {
            likeCnt[i]++;
        }
    }
    /**************************************/
    int q;
    cin >> q;
    vector<int> l(q),r(q);
    for (size_t i = 0; i < q; i++)
    {
        cin >>l[i]>>r[i];
    }
    for (size_t i = 0; i < q; i++)
    {
        cout << likeCnt[r[i]]-likeCnt[l[i]-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    cunt_a=0
    cunt_b=0
    cunt_ba=0
    cunt_ab=0
    for i in range(n):
        s=input()
        if s[0]=='B' and s[-1]=='A':
            cunt_ba+=1
        elif s[0]=='B': 
            cunt_b+=1
        elif s[-1]=='A':
            cunt_a+=1
        for j in range(len(s)-1):
            if s[j:j+2]=="AB":
                cunt_ab+=1
    if cunt_a==0 and cunt_b==0 and cunt_ba>0:
        print(cunt_ab+cunt_ba-1)
    else:
        print(cunt_ab+cunt_ba+min(cunt_a,cunt_b))
    
if __name__=='__main__':
    main()

Measured memory_bytes: 41328
import java.util.*;
 public class Main {
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      
      int N = sc.nextInt();
      int M = sc.nextInt();
      int[] A = new int[N];
      int sum = 0;

      for(int i = 0;i < N;i++){
        A[i] = sc.nextInt();
        sum += A[i];
      }


      int count = 0;

      for(int i = 0;i < N;i++){
       if(A[i] * 4 * M >= sum){
         count++;
       }
      }

      if(count >= M){
         System.out.println("Yes");
      }else{
         System.out.println("No");
      }
   }
        
 }
 


Measured memory_bytes: 35936
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200050;
int gi(){
    char ch=getchar(); int x=0,q=0;
    while(ch<'0'||ch>'9') q=ch=='-'?1:q,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return q?-x:x;
}
map<ll,int>num;
int main(){
    int n=gi(),a; ll ans=0,s=0;
    for (int i=1; i<=n; ++i){
	a=gi(),++num[s],s+=a;
	ans+=num[s];
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 12800
using System;

namespace tst
{
    class Program
    {
        public static void Main()
        {
            string[] In1 = Console.ReadLine().Split(' ');
            int h = int.Parse(In1[0]);
            int n = int.Parse(In1[1]);
            string[] In2 = Console.ReadLine().Split(' ');
            int[] A = new int[n];
            int sum = 0;
            for(int i=0; i<n; i++)
            {
                A[i] = int.Parse(In2[i]);
                sum += A[i];
            }
            string mes = "No";
            if (h <= sum)
            {
                mes = "Yes";
            }
            Console.WriteLine(mes);
        }

    }
}

Measured memory_bytes: 18912
#include <stdio.h>
#include <string.h>
#include <math.h>

int main() {

    int a, b, c, x;
    scanf("%d %d %d %d", &a, &b, &c, &x);

    int cnt = 0;

    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {

            int goukei = 500 * i + 100 * j;
            int nokori = x - goukei;

            //printf("%d %d %d  %d\n", i, j, goukei, nokori);
            if (nokori >= 0) {
                if (nokori % 50 == 0 && nokori / 50 <= c) {
                    cnt++;
                }
            }else{
                break;
            }
        }
    }

    printf("%d", cnt);

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  if (n / 100 == n % 10) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
	    int n = in.readInt();
	    int t = in.readInt();
	    String s = Integer.toString(n) + Integer.toString(t); 
	    int a = Integer.valueOf(s);
	    for(int i = 1; i*i <= a; i++) {
	    	if(i*i == a) {
	    		System.out.println("Yes"); 
	    		return;
	    	}
	    }
	    System.out.println("No"); 
	}
}
class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	
	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

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

string func(string input){
  if(input.size()==2){
    return input;
  }else if(input.size()==3) {
    reverse(input.begin(), input.end());
    return input;
  }
}

int main(){
  string input;
  cin >> input;
  cout << func(input) << endl;

  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n, m := iScan(), iScan()
	a := IntHeap(iSScan(n))
	h := &a
	heap.Init(h)
	for i := 0; i < m; i++ {
		x := heap.Pop(h)
		heap.Push(h, x.(int)/2)
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans += heap.Pop(h).(int)
	}
	fmt.Println(ans)
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 5872
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

int charToInt(char ch){
  if(ch>='0'&&ch<='9')return ch-'0';
  return ch-'a'+10;
}
int intToChar(int a){
  if(a>=0&&a<=9)return a+'0';
  return a-10+'a';
}

int main(){
  int n;
  ll nums[9];
  cin>>n;
  for(int i=0;i<n;i++){
    ll res=0;
    memset(nums,0,sizeof(nums));
    for(int j=0;j<9;j++)
      scanf("%x",nums+j);
    for(int k=0;k<32;k++){
      ll tgt=0;
      for(int j=0;j<8;j++)
	tgt+=res^nums[j];
      int dig=(tgt>>k)&1;
      if(dig!=((nums[8]>>k)&1))res|=(1LL<<k);
    }
    printf("%x\n",res);
  }

  return 0;
}

Measured memory_bytes: 0
n=gets.to_i
as=[]
balls=[0]*(n+1)
gets.split.each do |m|
  m=m.to_i
  as.push(m)
  balls[m]+=1
end
all=balls.inject(0){|sum,bn| sum+(bn*(bn-1))/2}
as.each do |an|
  puts all-balls[an]+1
end


Measured memory_bytes: 23172
#include <bits/stdc++.h>
using namespace std;
typedef struct sword
{
	int damage,flag;
	bool operator < (const struct sword & a) const
	{
		return damage>a.damage;
	}
}SWORD,*PSWORD;
SWORD s[200001];
int main()
{
	int N,H,i,count=0,ans=0;
	scanf("%d %d",&N,&H);
	//读入
	for(i=0;i<N;i++)
	{
		scanf("%d",&s[count].damage);
		s[count++].flag=0;
		scanf("%d",&s[count].damage);
		s[count++].flag=1;		
	}
	//排序 
	sort(s,s+count);
	i=0;
	while(H>0)
	{
		H-=s[i].damage;
		ans++;
		if(s[i].flag==1)
			i++;
		else if(H>0)
		{
			ans+=H/s[i].damage;
			ans+=H%s[i].damage==0?0:1;
			break;
		}	
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(void)
{
	int a,b,l,s,t;

	while(scanf("%d %d",&a,&b)!=EOF){
		l = a>b ? a:b;
		s = a>b ? b:a;
		while(l%s !=0){
			t=l;
			l=s;
			s=t%l;
		}
		printf("%d %d\n",s,a*(b/s));
	}
return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
int main(){
        int n; cin >> n;
        bool d = true;
        for (int x = 0; x < n; ++x){
            int a; cin >> a;
            if (a % 2 == 0){
                if (a % 3 != 0 && a % 5 != 0){
                    d = false;
                }
            }
        }
        if (d) cout << "APPROVED" << endl;
        else cout << "DENIED" << endl;
    return 0;
}



Measured memory_bytes: 3664
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(ll  i = 0; i < (ll )(n); i++)
#define repi(i,a,b) for(ll  i=ll (a);i<ll (b);i++)
#define all(x) (x).begin(),(x).end()

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;

using namespace std;

long long modpow(long long x,long long n,long long mod)
{
  if(n==0)return 1;
  long long res=modpow(x*x%mod,n/2,mod);
  if(n&1)res=res*x%mod;
  return res;
}
int  main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll  n;
  ll  mod= 998244353;
  cin>>n;
  vector<ll >a(n);
  rep(i,n)cin>>a[i];
  ll  sa=0;
  rep(i,n)sa+=a[i];
  ll  l=sa/2;
  vector<ll >dp(l+1,0),dp2;
  dp[0]=1;
  dp2=dp;
  rep(i,n)
  {
    for(ll  j=l-a[i];j>=0;j--)
    {
      dp[j+a[i]]+=dp[j]*2%mod;
      dp[j+a[i]]%=mod;
      dp2[j+a[i]]+=dp2[j];
      dp2[j+a[i]]%=mod;
    }
    //for(auto i:dp)cout<<i<<" ";cout<<endl;

  }
  ll res=modpow(3,n,mod);
  rep(i,l+1)dp[i]=dp[i]*3%mod;
  for(auto i:dp){res+=mod-i;res%=mod;}
  if(!(sa&1))res+=dp2.back()*3;
  cout<<res%mod<<endl;


  return 0;

}


Measured memory_bytes: 1024
//header{{{
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#include <boost/sort/spreadsort/spreadsort.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
//#include <boost/graph/graph_utility.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
//using namespace boost::multiprecision;
//using namespace boost::math;

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
        boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define bsort boost::sort::spreadsort::spreadsort
#define int int_fast64_t
using pii = pair<int,int>;

constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;
template <class Func>

class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
 
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};
 
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;

template <typename T> using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using Umap = gp_hash_table<K, V>;
using Trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

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

struct negrightshift {
    inline int operator() (const int &x, const unsigned offset) {
        return -(x >> offset);
    }
};
//}}}


signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout.setf(ios_base::fixed);
    cout.precision(10);

    string s;
    cin >> s;

    if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R'){
        cout << 3 << '\n';
    }else if((s[0] == 'R' && s[1] == 'R') || (s[1] == 'R' && s[2] == 'R')){
        cout << 2 << '\n';
    }else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R'){
        cout << 1 << '\n';
    }else{
        cout << 0 << '\n';
    }
    
    return 0;
}

Measured memory_bytes: 3596
def partition(a, p, r)
  x = a[r]
  i = p-1
  for j in p..r-1
    if a[j] <= x
      i += 1
      tmp = a[i]
      a[i] = a[j]
      a[j] = tmp
    end
  end
  tmp = a[i+1]
  a[i+1] = a[r]
  a[r] = tmp
  return i+1
 end


n = gets.chomp.to_i
input_array = gets.chomp.split.map(&:to_i)

q = partition(input_array, 0, n-1)
n.times do |i|
  if i == q
    print "[#{input_array[i]}]"
  else
    print input_array[i]
  end
  if i < (n-1)
    print " "
  end
end
print "\n"

Measured memory_bytes: 17180
sx,sy,tx,ty = map(int,input().split())

fx,bx = 'L','R'
if sx < tx: fx,bx = bx,fx
fy,by = 'D','U'
if sy < ty: fy,by = by,fy

w = abs(sx-tx)
h = abs(sy-ty)

ans = ''
ans += fy * h
ans += fx * w
ans += by * h
ans += bx * (w+1)
ans += fy * (h+1)
ans += fx * (w+1)
ans += by
ans += fx
ans += by * (h+1)
ans += bx * (w+1)
ans += fy

print(ans)


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

int main(){

  string s;

  cin>>s;

  int f=0, cnt=0;
  for(int i=0;i<s.size();i++){
    if(f==0){
      if(s[i]=='A') f++;
    }
    if(f==1){
      if(s[i]=='Z'){
	cout<<"AZ";
	f--;
	cnt++;
      }
    }
  }
  if(cnt) cout<<endl;

  if(cnt==0) cout<<-1<<endl;
  
  return 0;
}

Measured memory_bytes: 3212
from collections import defaultdict
from bisect import *
def solve():
    mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    ends = [-1]
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]])
                ends.append(l[i+1])
    selist = [[-1,-1]]+sorted(selist,key=lambda x:x[1])
    # s_ind = {}
    # for i,(s,e) in enumerate(selist):
        # e_ind[e] = i
    # ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist))
    for i in range(1,len(selist)):
        dp[i] = (dp[i-1]+1)%mod
        ind = bisect_right(ends,selist[i][0])
        dp[i] += dp[ind-1]
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())

Measured memory_bytes: 52120
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


int main(){
    ll n,d,a;
    cin >> n >> d >> a;
    map<ll,ll> mon;
    for(int i = 0; i < n; i++){
        ll x,h;
        cin >> x >> h;
        mon[x] = h;
    }

    ll ans = 0;
    auto it = mon.begin();
    ll attack = 0;
    queue<pair<ll,ll>> cnt;
    while(it != mon.end()){
        while(cnt.size() != 0){
            auto rng = cnt.front();
            if(rng.first <= it->first){
                attack -= rng.second;
                cnt.pop();
            } else {
                break;
            }
        }

        ll hp = it->second - attack*a;

        if(hp > 0){
            ll num = hp/a;
            if(hp%a) num++;
            cnt.push({it->first+d*2L+1L,num});
            attack += num;
            ans += num;
        }
        it++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 17624
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int a=scan.nextInt();
    int b=scan.nextInt();
    int c=scan.nextInt();
    int num=scan.nextInt();
    int ans=0;
    if(num<=a){
      ans=num;
    }else{
      if(num<=a+b){
        ans=num-b;
      }else{
        ans=a-(num-(a+b));
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 35692
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define inp() for(int i=0;i<n;i++)cin>>a[i];
using namespace std;
signed main(){
	char sanada='i';
	string s;
	int k;
	cin>>s>>k;
	for(int i=0;i<s.size();i++){
		if(s[i]!='1'&&i<k){
			sanada=s[i];
			break;
		}
		else sanada='1';
	}
	if(sanada=='i')cout<<1<<endl;
	else cout<<sanada<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c;
    cin >> a >> b >> c;
    for(ll i = 0 ; i < c && i + a <= b;i++){
    	cout << i + a << endl;
    }
    a = max(b - c, a + c - 1);
    for(ll i = a + 1 ;i <= b;i++){
    	cout << i << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
int main(void) {
  int i,n,d[100000],r;
  scanf("%d",&n);
  for(int i=0;i<n;i++) {
    scanf("%d",&d[i]);
  }
  if(n % 2 == 0) {
      qsort(d,n,sizeof(int),compare_int);
      r = d[n/2]-d[n/2-1];
  } else {
    r = 0;
  }
  printf("%d\n",r);
  return 0;
}


Measured memory_bytes: 892
N,M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

MOD = 10**9+7

x_diff = 0
y_diff = 0

for i in range(N):
    x_diff += (2*i-N+1)*X[i]%MOD
    
for i in range(M):
    y_diff += (2*i-M+1)*Y[i]%MOD
    
print(x_diff*y_diff%MOD)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string N;
    int count = 0;
    cin >> N;
    for (int i = 0; i < N.size(); ++i) {
        if (N[i] == '2') ++count;
    }
    cout << count << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
int n;
pair<ll,ll> job[200005];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> job[i].second >> job[i].first;
    }
    sort(job,job+n);
    int ans = 0;
    ll sum = 0;
    for(int i = 0; i < n; ++i)
    {
        if(sum+job[i].second<=job[i].first)
        {
            sum+=job[i].second;
            ans++;
        }
    }
    if(ans==n)
        puts("Yes");
    else puts("No");
    return 0;
}


Measured memory_bytes: 3328
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU
import Data.Char (isSpace)

main :: IO ()
main = do
  let
    unsafeBinaryMinInt :: (Int -> Bool) -> (Int, Int) -> Int
    unsafeBinaryMinInt p = check
      where
        check :: (Int, Int) -> Int
        check ij@(i, _) | p i       = i
                        | otherwise = search ij
        search :: (Int, Int) -> Int
        search = snd . until ((==) <$> succ . fst <*> snd) halve
          where
            halve :: (Int, Int) -> (Int, Int)
            halve (i, j) | p m       = (i, m)
                         | otherwise = (m, j)
              where
                m = (i + j) `div` 2
  [_, k] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  as <- unsafeTextToVectorInt <$> T.getLine :: IO (VU.Vector Int)
  let
    as' = VU.map (subtract 1) as :: VU.Vector Int
    p :: Int -> Bool
    p i = (<= k) . VU.sum . VU.map (`div` i) $ as'
  print $  unsafeBinaryMinInt p (1, 10 ^ 9)

unsafeTextToVectorInt :: T.Text -> VU.Vector Int
unsafeTextToVectorInt = VU.unfoldr next
  where
    next :: T.Text -> Maybe (Int, T.Text)
    next s = case T.signed T.decimal s of
               Left _        -> Nothing
               Right (n, s') -> Just (n, T.dropWhile isSpace s')

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
{-# INLINE unsafeTextToInt #-}


Measured memory_bytes: 16616
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int min(int a,int b){return (a<b)?a:b;}
void calc_same(vector<int> v,vector<pair<int,int>>& p){
  int val,cnt;
  val=v[0];
  cnt=0;
  for(int i=0;i<v.size();i++){
    if(val!=v[i]){
      p.push_back(make_pair(cnt,val));
      cnt=1;
      val=v[i];
    }else{
      cnt++;
    }
  }
  p.push_back(make_pair(cnt,val));
  sort(p.begin(),p.end(),greater<pair<int,int>>());
}
int main(){
  int n,to,te,cnt,tmp;
  vector<pair<int,int>> odd_p,even_p;
  cin >> n;
  vector<int> even_v,odd_v;
  for(int i=0;i<n;i++){
    cin >> tmp;
    if(i%2==0){
      even_v.push_back(tmp);
    }else{
      odd_v.push_back(tmp);
    }
  }
  sort(even_v.begin(),even_v.end());
  sort(odd_v.begin(),odd_v.end());
  calc_same(even_v,even_p);
  calc_same(odd_v,odd_p);
  if(even_p[0].second!=odd_p[0].second){
    cout<<(n/2-even_p[0].first+n/2-odd_p[0].first) << endl;
  }else if(even_p.size()==1&&odd_p.size()==1){
    cout << n/2 << endl;
  }else if(even_p.size()==1){
    cout << (n/2-odd_p[1].first) << endl;
  }else if(odd_p.size()==1){
    cout << (n/2-even_p[1].first) << endl;
  }else{
    cout << min(n/2-even_p[0].first+n/2-odd_p[1].first,
                n/2-even_p[1].first+n/2-odd_p[0].first)<<endl;
  }
}


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

int main(){
	string a,b ;
	cin >> a >> b ;
	for(int i=0;i<b.size();i++) cout << a.at(i) << b.at(i) ;
	if(a.size()>b.size()) cout << a.at(a.size()-1) ;
	cout << endl ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

const ll INF = 1e9;

int main() {
	#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
	#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	ll n; cin >> n;
	vl a(n); REP(i, n) cin >> a[i];

	vvl dp(n + 1, vl(2, 0));
	dp[0][0] = 1;

	REP(i, n) {
		if (a[i] % 2 == 0) {
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][1] += dp[i][0];

			dp[i + 1][1] += dp[i][1];
			dp[i + 1][0] += dp[i][0];
			
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][0] += dp[i][0];
		} else {
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][0] += dp[i][0];
			
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][1] += dp[i][0];
			
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][1] += dp[i][0];
		}
	}

	cout << dp[n][1] << endl;

	return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf = 1<<30;
enum mod = 10L^^9 + 7;

void main() {
    int n, a;
    scan(n, a);
    auto x = readln.split.to!(int[]);
    x[] -= a;

    immutable ofs = n * 50;
    auto dp = new long[](ofs * 2 + 1);
    dp[x[0] + ofs] = 1;

    foreach (i ; 1 .. n) {
        if (x[i] > 0) {
            foreach_reverse (j ; x[i] .. 2*ofs + 1) {
                dp[j] += dp[j - x[i]];
            }
        }
        else {
            foreach (j ; 0 .. 2*ofs + 1 + x[i]) {
                dp[j] += dp[j - x[i]];
            }
        }

        dp[x[i] + ofs]++;
    }

    writeln(dp[ofs]);
}














































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 380
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[300200];
int a[300200];
int ans[300200];
signed main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int aa;
        cin >> aa;
        a[i] = aa;
    }
    for(int i = n; i >= 1; --i)
    {
        if (sum[i] != a[i])
            ans[i] = 1;
        for(int j = 1; j * j <= i; ++j)
        {
            if (i % j != 0)
                continue;
            sum[j] += ans[i];
            sum[j] %= 2;
            if (j != i / j)
            {
                sum[i / j] += ans[i];
                sum[i / j] %= 2;
            }
        }
        //cout << ans[i] << endl;
    }
    vector<int>kek;
    for(int i = 1; i <= n; ++i)
        if (ans[i] == 1)
            kek.push_back(i);
    cout << kek.size() << endl;
    for(auto i : kek)
        cout << i << " ";
    return 0;
}


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

void solve(int a,int b,char c){
	if(c=='+'){
		cout<<a+b<<endl;
	}
	else if(c=='-'){
		cout<<a-b<<endl;
	}
	else if(c=='*'){
		cout<<a*b<<endl;
	}
	else{
		cout<<a/b<<endl;
	}
}

int main() {
	// your code goes here
	int a,b;
	char c;
	cin>>a>>c>>b;
	while(c!='?'){
		solve(a,b,c);
		cin>>a>>c>>b;
	}
	return 0;
}

Measured memory_bytes: 3096
#include <iostream>
#include <map>
#include <set>
using namespace std;

int main(){
	int N,odd=0,even=0;
	cin>>N;
	while(N--){
		int inp;
		cin>>inp;
		if(inp%2)odd++;
		else even++;
	}
	if(odd%2==0) cout<<"YES";
	else cout<<"NO";
	cout<<"\n";
	return 0;
}

Measured memory_bytes: 384
// Contest.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include"iostream"
#include"string"
#include"vector"
#include"algorithm"

using namespace std;

int main()
{
	/*int n,k;
	cin >> n;
	vector<char>s(n);
	for (int j = 0; j < n; j++)  cin >> s[j];
	cin >> k;
	for (int i = 0; i < n; i++)
	{
		if (s[i] != s[k-1]) {
			s[i] = '*';
		}
	}

	for (int l = 0; l < n; l++)
	{
		cout << s[l] ;
	}*/
	int n,d;
	cin >> n>>d;

	if (n >= 2*d+1) {
		if (n % (2 * d + 1) != 0)
			cout << n / (2 * d + 1) + 1 << endl;
		if (n % (2 * d + 1) == 0)
			cout << n / (2 * d + 1) << endl;
	}

	if (n < 2 * d + 1)
		cout<<1<<endl;

	return 0;
}






Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()       
{
	int a,b,c,d,e,f,g,h,i;
	cin>>a>>b>>e;
	c=3*e-a-b;
	i=2*e-a;
	h=2*e-b;
	f=3*e-c-i;
	g=3*e-h-i;
	d=2*e-f;
	cout<<a<<" "<<b<<" "<<c<<"\n";
	cout<<d<<" "<<e<<" "<<f<<"\n";
	cout<<g<<" "<<h<<" "<<i<<"\n";
	return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split(" "))
A = list(map(int,input().split(" ")))

cnt = {}
A[0] %= M
for i in range(N-1):
    A[i+1] += (A[i])
    A[i+1] %= M

for i in range(N):
    if A[i] in cnt:
        cnt[A[i]] += 1
    else:
        cnt[A[i]] = 1

ans = 0
for v in cnt.values():
    ans += (v*(v-1)//2)

if 0 in cnt:
    ans += cnt[0]

print(ans)

Measured memory_bytes: 14696
import Control.Applicative

main :: IO ()
main = solve <$> readLn >>= print

solve :: Int -> Int
solve n = minimum . map (product . (zipWith (\x y -> x ^ (y-1)) [2,3,5])) $ f n
  where
    f 4 = [[4],[2,2]]
    f 6 = [[6],[3,2]]
    f 8 = [[8],[4,2],[2,2,2]]
    f 9 = [[9],[3,3]]
    f 10 = [[10],[5,2]]
    f 12 = [[12],[6,2],[4,3],[3,2,2]]
    f x = [[x]]



Measured memory_bytes: 3624
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,S = MI()
A = [0] + LI()
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(S+1):
        if j >= A[i]:
            dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-A[i]]
            dp[i][j] %= mod
        else:
            dp[i][j] = 2*dp[i-1][j]
            dp[i][j] %= mod

print(dp[-1][-1])


Measured memory_bytes: 135176