akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
  
bool cmp(pair< int, int > a, pair< int, int > b)
{
  if(a.first != b.first) return(a.first > b.first);
  return(a.second < b.second);
}
int main()
{
  int N, p[100];
    
  while(scanf("%d", &N), N) {
    for(int i = 0; i < N; i++) {
      scanf("%d", &p[i]);
    }
      
    pair< int, int > dp[2][50001];
    fill_n(*dp, 2 * 50001, make_pair(-INF, INF));
    pair< int, int > *now = dp[0], *nxt = dp[1];
      
    now[0] = {0, 0};
    int reach = 0;
    for(int i = 0; i < N; i++) {
      int mod = p[i] % 1000;
      if(1 <= mod && mod <= 500) {
        int rev = 1000 - mod - 500;
        reach += rev;
        for(int j = reach; j >= rev; j--) {
          nxt[j] = min(nxt[j], {now[j - rev].first + 1, now[j - rev].second + p[i]}, cmp);
        }
      } else {
        int rev = (1000 - mod) % 1000;
        int need = (mod + 500) % 1000;
        reach += max(rev, need);
        for(int j = reach; j >= 0; j--) {
          nxt[j] = min(nxt[j], now[j], cmp);
        }
        for(int j = reach; j >= rev; j--) {
          nxt[j] = min(nxt[j], {now[j - rev].first, now[j - rev].second + p[i]}, cmp);
        }
        for(int j = need; j <= reach; j++) {
          nxt[j - need] = min(nxt[j - need], {now[j].first + 1, now[j].second + p[i]}, cmp);
        }
      }
      swap(now, nxt);
    }
    auto p = *min_element(now, now + 50000, cmp);
    printf("%d %d\n", p.first, p.second);
  }
}

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

using namespace std;


template<class M, class F = std::function<M(M, M)>>
class SegmentTree{
private:
  std::vector<M> data;
  F op;
  M e;
  int length;

public:
  SegmentTree(int n, const F op, const M& e) : op(op), e(e){
    length = 1;
    while(length < n) length <<= 1;
    data = std::vector<M>((length << 1) - 1, e);
  }

  void update(int index, const M& x){
    index += length - 1;
    data[index] = x;

    while(index){
      (--index) >>= 1;
      data[index] = op(data[(index << 1) + 1], data[(index << 1) + 2]);
    }
  }

  M query(int left, int right){
    M l = e, r = e;

    for(left += length - 1, right += length - 1; left < right; (--left) >>= 1, (--right) >>= 1){
      if((left ^ 1) & 1) l = op(data[left++], l);
      if((right ^ 1) & 1) r = op(data[--right], r);
    }

    return op(l, r);
  }
};


int main(){
  int N;
  cin >> N;
  
  vector<int> h(N), a(N);
  for(auto& e : h) cin >> e;
  for(auto& e : a) cin >> e;
  
  SegmentTree<long long> dp(N + 1, [](long long a, long long b){
    return max(a, b);
  }, 0);
  
  for(int i = 0; i < N; i++){
    long long beauty = dp.query(0, h[i]);
    dp.update(h[i], beauty + a[i]);
  }
  
  cout << dp.query(0, N + 1) << endl;
  
  return 0;
}

Measured memory_bytes: 5888
#include<cstdio>
#include<cstring>

char str[15];

int main(){
    scanf("%s",str+1);
    int len=strlen(str+1),cnt=0;
    if(str[1]!='A'||str[2]=='C'||str[len]=='C'){
        puts("WA");
        return 0;
    }
    for(int i=3;i<=len-1;i++){
        if(str[i]=='C'){
            if(cnt){
                puts("WA");
                return 0;
            }
            cnt++;
        }
    }
    if(!cnt){
        puts("WA");
        return 0;
    }
    for(int i=2;i<=len;i++){
        if(str[i]=='C') continue;
        if(str[i]<'a'||str[i]>'z'){
            puts("WA");
            return 0;
        }
    }
    puts("AC");
}


Measured memory_bytes: 128
#include"iostream"
#include"string"
using namespace std;

int main()
{
	string s;
	cin >> s;
	int ans = 700;
	for (int i = 0; i < 3; i++)
	{
		if (s.at(i) == 'o')ans += 100;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double ld;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)


int main() {
    ll L,R,d;
    cin >> L >> R >> d;

    ll ans=0;
    for(ll i=L;i<=R;i++){
        if(i%d == 0){
            ans++;
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 3592
# バイナリサーチで解く。
# Bの要素を基準にしてa<b<cとなるものを選ぶ。すべての配列はソート済みとして、
# a<bとなる最大のa, b<cとなる最小のcを選び、それら独立する事象の数の積を足していく

n = int(input())
A, B, C = [list(sorted(map(int, input().split())))  for _ in range(3)]

cnt = 0

def bs_left(lis, target):
    # ソート済みのlisのうちtargetがどこに入るか（index）
    # 要素がtargetと重複する場合はより小さいインデックスを返す。すなわち「lisのうちtarget未満となる最大の要素のインデックス」
    # ex) min(lis)=mとするとtarget<=mのとき0
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if lis[mid]<target:
            low = mid+1
        else:
            high = mid
    return low

def bs_right(lis, target):
    low, high = 0, len(lis)
    while low<high:
        mid = (low+high)//2
        if target<lis[mid]:
            high = mid
        else:
            low = mid+1
    return low

for b in B:
    # 探索のときにちゃんとみているので a!=b and b!=cみたいな条件は必要ない
    cnt += (bs_left(A, b) * (n-bs_right(C, b)))
print(cnt)

Measured memory_bytes: 23460
par = input().split()
N = int(par[0])
K = int(par[1])
i = 1
j = 1

countj = 0
tmpj = 0
counti = 0

while i <= N:
    j = 1
    j += tmpj
    while j < K:
        j *= 2
        countj += 1
    counti += (1/N) * ((1/2) ** countj)
    countj = 0
    tmpj += 1
    i += 1

print(counti)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b;
	cin >> a >> b;
	ll g = __gcd(a,b);
	cout << a*b/g << endl;
 }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1 << 18, C = 1e5 + 7;

int v[N], w[N]; //v - value, w - weight
int dp[520][C];

int memv[1 << 10], memw[1 << 10];

const int UP = 9;

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }   

    for (int i = 1; i <= n && i < (1 << UP); ++i) {
        for (int j = 0; j < C; ++j)
            dp[i][j] = dp[i/2][j];
        for (int j = C - 1; j >= w[i]; --j) {
            dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
        }   
        for (int j = 1; j < C; ++j)
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
    }   

    int q;
    cin >> q;
    while (q--) {

        int u, l;
        cin >> u >> l;

        vector <int> down;

        int t = u;
        while (t >= (1 << UP)) {
            down.app(t);
            t >>= 1;                            
        }   

        int ans = 0;

        int sz = down.size();
        for (int mask = 0; mask < (1 << sz); ++mask) {
            int sv = 0, sw = 0;
            if (mask) {
                int bit = __builtin_ctz(mask);
                int sub = mask - (1 << bit);
                sv = memv[sub] + v[down[bit]];
                sw = memw[sub] + w[down[bit]];
            }   
            memv[mask] = sv;
            memw[mask] = sw;

            if (sw <= l) {
                ans = max(ans, sv + dp[t][l - sw]);
            }   
        }   
        cout << ans << endl;

    }   
}

Measured memory_bytes: 205332
n, x = map(int, input().split())
a = list(map(int, input().split()))

ans = 0

if a[0] - x > 0:
    ans += a[0] - x
    a[0] = x

for i in range(n - 1):
    if a[i] + a[i + 1] > x:
        ans += a[i] + a[i + 1] - x
        a[i + 1] -= a[i] + a[i + 1] - x

print(ans)



Measured memory_bytes: 19956
s = gets.chomp.to_s
n = s.size
ans = 'Yes'
(0..n/2-1).each do |i|
  if s[i] != s[n-1-i]
    ans = 'No'
    break
  end
end
if ans == 'Yes'
  k = (n-1)/2
  (0..k/2-1).each do |i|
    if s[i] != s[k-1-i]
      ans = 'No'
      break
    end
  end
end
puts ans


Measured memory_bytes: 3836
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a<6)
            System.out.println("0");
        else if (a<13)
            System.out.println(b/2);
        else
            System.out.println(b);
    }
}


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

long cnt_balls(long range_ball, long blue, long red){
    long balls=blue+red;
    long cnt_set=range_ball/balls;
    long cnt_left=range_ball%balls;
    if(balls!=0){
        return cnt_set*blue+min(blue,cnt_left);
    }
    else{
        return 0;
    }
}

int main(){
    long N,A,B; cin >> N >> A >> B;
    cout << cnt_balls(N,A,B) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const ll inf=1e17;
int main(){
	int n,m;
	cin>>n>>m;
	vi in(n);
	rep(i,n)cin>>in[i];
	vi dp(n+1);
	rep(i,n)if(in[i]>0)dp[i+1]=in[i];
	rep(i,n)dp[i+1]+=dp[i];
	in.insert(in.begin(),0);
	rep(i,n)in[i+1]+=in[i];
	ll sum=dp[n],out=-inf;
	rep(i,n-m+1){
		ll t=sum-dp[i+m]+dp[i];
		out=max<ll>(out,t+max<ll>(0,in[i+m]-in[i]));
	}
	cout<<out<<endl;
}










Measured memory_bytes: 2688
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 0
while len(A) < 100000:
  n = len(A)
  for i in range(cnt, cnt + n):
    x = A[i] % 10
    A.append(int(str(A[i])+str(x)))
    if x > 0:
      A.append(int(str(A[i])+str(x-1)))
    if x <= 8:
      A.append(int(str(A[i])+str(x+1)))
  cnt += n
A.sort()
print(A[K-1])

Measured memory_bytes: 7996
#include <stdio.h>

int main(void)
{
	int W, H, x, y, r, flag = 0;

	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

	if (((x - r) < 0) || (W < (x + r)) || ((y - r) < 0) || (H < (y + r)))
	{
		flag = 1;
	}

	if (flag == 0)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 2132
s = list(input())
n = len(s)
mod = pow(10, 9) + 7
dp = [[0] * 13 for _ in range(n)]
if s[-1] == "?":
    for i in range(10):
        dp[-1][i] = 1
else:
    dp[-1][int(s[-1])] = 1
digit = 1
for i in range(n - 2, -1, -1):
    digit *= 10
    digit %= 13
    if s[i] == "?":
        for j in range(10):
            x = (j * digit) % 13
            for k in range(13):
                dp[i][k] += dp[i + 1][(k - x) % 13]
                dp[i][k] %= mod
    else:
        x = (int(s[i]) * digit) % 13
        for k in range(13):
            dp[i][k] = dp[i + 1][(k - x) % 13]
ans = dp[0][5]
print(ans)

Measured memory_bytes: 94080
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int N,M;
bool graph[60][60];
bool vis[60];

void dfs(int x){
  if(vis[x]){return;}
  vis[x]=true;
  for(int i=0;i<N;i++){
    if(graph[x][i]){dfs(i);}
  }
}

int main() {
  cin>>N>>M;
  vector<int>a(M),b(M);
  for(int i=0;i<M;i++){
    cin>>a[i]>>b[i];
    a[i]--;b[i]--;
    graph[a[i]][b[i]]=true;
    graph[b[i]][a[i]]=true;
  }
  int ans=0;
  for(int i=0;i<M;i++){
    graph[a[i]][b[i]]=false;
    graph[b[i]][a[i]]=false;
    for(int j=0;j<N;j++){
      vis[j]=false;
    }
    dfs(0);
    bool connected=true;
    for(int i=0;i<N;i++){
      if(!vis[i]){connected=false;}
    }
    if(!connected){ans++;}
    graph[a[i]][b[i]]=true;
    graph[b[i]][a[i]]=true;
  }
  cout<<ans<<endl;
  return 0;
}

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

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

   int cnt = 0;
   for (int i=0; i<3; i++){
      if (S.at(i) == T.at(i))
         cnt++;
   }

   cout << cnt << endl;
}



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

int main()
{
	ll n,k;
	cin >> n >> k;
	vector<ll> A(n);
	for(int i = 0;i<n;i++)
	{
		cin >> A[i];
		A[i]--;
	}
	vector<ll> B(n,-1);
	
	ll now = 0;
	for(ll i = 0;k!=0;i++)
	{
		k--;
		if(B[now]==-1)B[now]=i;
		else
		{
			ll m = i - B[now];
			k%=m;
			B[now] = i;
		}
		
		now = A[now];
	}
	cout<<now+1<<endl;;
}

Measured memory_bytes: 6428
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n;
    ll l;
    cin >> n >> l;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    if(n == 2) {
        if(l > a[0] + a[1]) {
            cout << "Impossible" << endl;
        } else {
            cout << "Possible" << endl << 1 << endl;
        }
        return 0;
    }
    bool x = false;
    int jj = -1;
    rep(i, n-1) {
        if(a[i] + a[i+1] >= l) {
            x = true;
            jj = i;
        }
    }

    
    vi ans;
    

    if(!x) {
        cout << "Impossible" << endl;
    } else {
        cout << "Possible" << endl;
        rep(i, jj) {
            ans.push_back(i);
        }
        for(int i = n-2; i>=jj; --i) {
            ans.push_back(i);
        }
        rep(i, n-1) {
            cout << ans[i]+1 << '\n';
        }
    }
}

Measured memory_bytes: 2168
using System;

namespace AtC167
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] ABCK;
            ABCK = Console.ReadLine().Split(' ');
            int A = int.Parse(ABCK[0]);
            int B = int.Parse(ABCK[1]);
            int C = int.Parse(ABCK[2]);
            int K = int.Parse(ABCK[3]);

            int ans = 0;
            if (A > K) ans = K;
            else if (A + B >= K) ans = A;
            else ans = A - (K - A - B);

            Console.WriteLine(ans);
    
        }
    }
}


Measured memory_bytes: 27528
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
  int num,tmp;
 
  cin >> num;

  int a[num][3];

  for(int i=0; i<num; ++i)
    cin >> a[i][0] >> a[i][1] >> a[i][2];


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

    sort(a[i],a[i]+3,greater<int>());
    
    if(a[i][0]*a[i][0] == a[i][1]*a[i][1] + a[i][2]*a[i][2]){
      cout << "YES\n";
    }else{
      cout << "NO\n";
    }
  }  

}

Measured memory_bytes: 1144
#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 <iomanip> // setprecision
#include <complex> // complex
#include <functional>
#include <math.h> 
#define enld '\n'
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  while(1){
    int N,M;
    string S;
    cin >> N;
    if(N == 0) break;
    cin >> M >> S;
    int ans = 0;
    for(int i=0; i<M; i++){
      if(S[i] == 'I'){
        for(int j=i+1; j<M; j++){
          if(S[j] == S[j-1]){
            int now = j-i;
            if(S[j-1] == 'O') now--;
            now /= 2;
            if(N <= now){
              ans += now+1 - N;
            }
            i = j-1;
            break;
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}


Measured memory_bytes: 4540
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <sstream>
#include <iomanip>

#define rep(i,n) for(int i = 0; i < n; i++)

typedef long long ll;

using namespace std;

int main(){
  int n, ans = 0;
  string s;
  cin >> n >> s;

  rep(i,1000){
    ostringstream ss;
    ss << setw(3) << setfill('0') << i;
    string e(ss.str());

    bool ok = false;
    int j = 0;
    for(auto &c:s){
      if(e[j] == c) j++;
      if(j==3){
	ok = true;
	break;
      }
    }
    if(ok) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();

    vector<int> a(9);
    rep(i, 9) cin >> a[i];
    int n, b;
    cin >> n;
    rep(i, n){
        cin >> b;
        rep(j, 9) if(a[j] == b) a[j] = 0;
    }

    bool f = 0;
    rep(i, 3){
        if((a[i]|a[i+3]|a[i+6]) == 0) f= 1;
        if((a[i*3]|a[i*3+1]|a[i*3+2]) == 0) f= 1;
        if((a[0]|a[4]|a[8])==0) f=1;
        if((a[2]|a[4]|a[6])==0) f=1;
    }
    cout << (f ? "Yes":"No") << endl;

}

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

long long n;
vector<long long> d;

long long solve();

int main() {
  cin >> n;
  d.resize(n);
  for(int i = 0; i < n; ++i) cin >> d[i];
  sort(d.begin(), d.end());
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long num = (n - 1) / 2;
  if(d[num] != d[num + 1])
    return d[num + 1] - d[num];
  else
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

int main(){
    double N,p=0;
    int K;
    cin>>N>>K;
    for(int i=1;i<=N;++i){
        if(i>=K)p+=(double)1/N;
        else {
            int j=i,count=0;
            while(j<K){
                j*=2;
                count++;
            }
            p+=(double)pow(0.5,count)/N;
        }
    }
    printf("%.10lf\n",p);
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	private static final String SPLIT_STR = " ";
	private static final String OPERATOR_EQUAL = "==";
	private static final String OUTPUT_TRUE = "Yes";
	private static final String OUTPUT_FALSE = "No";

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String x = sc.nextLine();

		sc.close();

		String[] split = x.split(SPLIT_STR);
		int a = Integer.parseInt(split[0]);
		int b = Integer.parseInt(split[1]);
		int c = Integer.parseInt(split[2]);

		String result = OUTPUT_FALSE;

		if (a < b && b < c) {
			result = OUTPUT_TRUE;
		}

		System.out.println(result);
	}
}



Measured memory_bytes: 26180
from collections import Counter
from sys import exit, stdin
N = int(stdin.readline().rstrip())
if N == 1:
    print(''.join(sorted(stdin.readline().rstrip())))
    exit()
S = [Counter(stdin.readline().rstrip()) for _ in range(N)]
inter_chars = {}
for i in range(0, N-1):
    inter_chars = S[i].keys() & S[i+1].keys()
ans = {}
for i in range(N):
    for c in inter_chars:
        if c not in ans:
            ans[c] = S[i][c]
        elif S[i][c] < ans[c]:
            ans[c] = S[i][c]
print(''.join(sorted(k*v for k, v in ans.items())))

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

const int N = 1e5 + 10;
int a[N], cnt = 1, mark[N], col[N];
vector<int> adj[N];

void dfs(int root) {
	mark[root] = cnt;
  	col[a[root]] = cnt;
  	for (int i = 0; i < adj[root].size(); i++) {
    	int u = adj[root][i];
     	if (!mark[u])
          	dfs(u);
    }
}

int main() {
	int n, m;
  	cin >> n >> m;
  	for (int i = 0; i < n; i++) {
      	cin >> a[i];
  		a[i]--;
	}
  	for (int i = 0; i < m; i++) {
      	int u, v;
    	cin >> u >> v;
      	u--;
      	v--;
      	adj[u].push_back(v);
      	adj[v].push_back(u);
    }
    for (int i = 0; i < n; i++)
    	if (!mark[i]) {
        	dfs(i);
        	cnt++;
        }
    int ans = 0;
    for (int i = 0; i < n; i++)
    	if (mark[i] == col[i]) 
        	ans++;
    cout << ans << "\n";
    return 0;
}

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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct Edge{int from, to; ll cost;};

const ll MOD = 1000000007;
const long double EPS = 10e-10;

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(n) cin >> a[i];

    ll ans = 0LL;
    rep(n){
        while(a[i] % 2LL == 0LL){
            a[i] /= 2LL;
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
A, B, C = map(int, input().split())
K = int(input())

flag = False
for i in range(0, K):
    a = A*2**i
    for j in range(0, K-i):
        b = B*2**j
        c = C*2**(K-i-j)
        if a < b < c:
            flag = True
            # print(a, b, c)
            break
    if flag:
        break
if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9124
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();
    set<string> st;
    bool flg = false;
    rep(i, 26) {
        rep(j, n) {
            if (s[j] == (char)('a' + i)) {
                rep(l, k) {
                    if (j + l >= n) break;
                    st.insert(s.substr(j, l+1));
                } 
            }
        }    
    }
    int cnt = 0;
    for (auto ans: st) {
        if (cnt == k -1) {
            cout << ans << endl;
            return 0;
        }
        ++cnt;
    }
    return 0;
}


Measured memory_bytes: 4804
a,b,c,x,y = [int(x) for x in input().split()]
res = 0
if a + b > 2 * c:
  res += min(x,y) * 2 * c
  if x == min(x,y):
    if b > 2 * c:
      res += (y - min(x,y)) * 2 * c
    else:
      res += (y - min(x,y)) * b
  else:
    if a > 2 * c:
      res += (x - min(x,y)) * 2 * c
    else:
      res += (x - min(x,y)) * a
else:
  res += a * x
  res += b * y
print(res)

Measured memory_bytes: 9100
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	t := nextIntArray()
	n, k := t[0], t[1]
	b := map[int]int{}
	for i := 0; i < n; i++ {
		t = nextIntArray()
		b[t[0]] += t[1]
	}
	keys := make([]int, n)
	for key := range b {
		keys = append(keys, key)
	}
	sort.Ints(keys)
	for _, v := range keys {
		if k <= b[v] {
			fmt.Println(v)
			return
		}
		k -= b[v]
	}
}

const size = 1000000

var reader = bufio.NewReaderSize(os.Stdin, size)

func nextLine() string {
	var line, buffer []byte
	isPrefix := true
	var err error
	for isPrefix {
		line, isPrefix, err = reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
	}
	return string(buffer)
}
func nextStringArray() []string {
	return strings.Split(nextLine(), " ")
}
func nextInt() int {
	n, _ := strconv.Atoi(nextLine())
	return n
}
func nextIntArray() []int {
	s := strings.Split(nextLine(), " ")
	n := len(s)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(s[i])
	}
	return a
}

func min(i, j int) int {
	if i > j {
		return j
	}
	return i
}


Measured memory_bytes: 12032
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using li = long long int;
using uli = unsigned long long int;
using namespace std;

int main() {
    fastIO;
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    rep(i, n) cin >> x.at(i);

    int total = 0;
    for (auto p : x) {
        total += min(abs(p - 0), abs(p - k)) * 2;
    }
    cout << total << endl;
}

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

int cost[10][10];

void warshall_floyd(){
    rep(k,10){
        rep(i,10){
            rep(j,10){
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
}

int main(){
    int h,w;
    cin >> h >> w;
    rep(i,10) rep(j,10) cin >> cost[i][j];
    int a[h][w];
    rep(i,h) rep(j,w) cin >> a[i][j];
    warshall_floyd();
    int all_cost = 0;
    rep(i,h){
        rep(j,w){
            if(a[i][j] != -1) all_cost += cost[a[i][j]][1];
        }
    }
    cout << all_cost << endl;
    return 0;
}


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

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    vector<int> L;
    for (int i = 0; i < N; i++){
        int tmp;
        cin >> tmp;
        L.push_back(tmp);
    }

    sort(L.begin(), L.end());
    int ans = 0;
    for (int i = 0; i < L.size() - 2; i++) {
        int a = L[i];
        for (int j = i + 1; j < L.size()-1; j++) {
            int b = L[j];
            for (int k = j + 1; k < L.size(); k++) {
                int c = L[k];
                if (a+b > c) {
                    ans++;
                }else {
                    break;
                }
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


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

using namespace std;

int n, k;
const int mod = 1e9 + 7;
vector<int> a; // maximum # of candies i-th child can take
vector<int> dp; // number of ways to divide i cookies

int main() {
	cin >> n >> k;
	a.assign(n, 0);
	dp.assign(k + 1, 0);
	
	dp[k] = 1; // one way to divide 0 cookies, k cookies left

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		vector<int> dp2(k + 5, 0);
		for (int left = 0; left <= k; left++) {

			int l, r;
			l = left - min(left, a[i]);
			r = left - 1;

			if (l <= r) {
				dp2[l] += dp[left];
				dp2[l] %= mod;

				dp2[r + 1] -= dp[left];
				dp2[r + 1] += mod;
				dp2[r + 1] %= mod;
			}

			/*for (int next = 1; next <= min(left, a[i]); next++) {
				dp[left - next] += dp[left];
				dp[left - next] %= mod;
			}*/
		}


		int tmp = 0;
		for (int j = 0; j <= k; j++) {
			tmp += dp2[j];
			tmp %= mod;

			dp[j] += tmp;
			dp[j] %= mod;
		}
	}

	cout << dp[0] << "\n";

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    //Double Factorial
    //这是第一次做 E 吧废物, 这次 D 简单人均 20 分钟 6 道呵呵
    //先看看能不能看懂题目吧
    //又是整型溢出的情况, 如何计算可以算出多少个 0 呢
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long v = sc.nextLong();
        System.out.println(helper(v));
        sc.close();
    }

    static long helper(long v) {
        if (v % 2 == 1) return 0;
        long count = 0;
        for (long i = 10; i <= v; i *= 5) {
            count += v / i;
        }
        return count;
    }
}


Measured memory_bytes: 22612
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)
	L := make([]int, n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := range L {
		sc.Scan()
		L[i], _ = strconv.Atoi(sc.Text())
	}
	sort.Ints(L)
	ans := 0
	// fmt.Println("n", n, "L", L)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			// L[i],L[j]は確定
			// L[k] < L[i]+L[j]なkを高速に見つけたい
			// lはソート済みなので、２分探索すればよい
			r := lowerbound(L, L[i]+L[j])
			l := j + 1
			ans += max(0, r-l)
		}
	}
	fmt.Println(ans)
}

// indexが条件を満たすかどうか？
func isOK(a []int, index, key int) bool {
	if a[index] >= key {
		return true
	}
	return false
}

func lowerbound(a []int, key int) int { // 条件を満たす最小のrightを求めたい
	left, right := -1, len(a)
	for right-left > 1 {
		mid := (right + left) / 2
		if isOK(a, mid, key) { // このindexは条件を満たす -> rightを狭める
			right = mid
		} else { // このindexは条件を満たさない -> leftを狭める
			left = mid
		}
	}
	return right
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  int N, A, B; std::cin >> N >> A >> B;
  std::string S; std::cin >> S;
  int p = 0, op = 0;
  for(int i = 0; i < N; ++i) {
    bool pass;
    switch(S[i]) {
    case 'c': pass = false; break;
    case 'a': pass = (p < A+B); if(pass) ++p; break;
    default:  pass = (p < A+B && op < B); if(pass) ++p, ++op;
    }
    std::cout << (pass? "Yes\n": "No\n");
  }
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h> 
 
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))


int main(){
    int N;
    cin>>N;
    vector<int>t(N+1),x(N+1),y(N+1);
    t[0]=x[0]=y[0]=0;
    REP(i,N){
        cin>>t[i+1]>>x[i+1]>>y[i+1];
    }
    REP(i,N){
        int dt=t[i+1]-t[i];
        int dx=abs(x[i+1]-x[i]);
        int dy=abs(y[i+1]-y[i]);
        if(dt<dx+dy||(dt%2!=(dx+dy)%2)){
            cout<<"No"<<endl;return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 1408
from itertools import permutations
N,M = map(int,input().split())
table=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)

def f(L,k):
    for a in L:
        if a==k:
            return True
    return False

S=[i for i in range(1,N)]
ans =0
for s in permutations(S,N-1):
    flag =True
    if not f(table[0],s[0]):
        continue
    for i in range(N-2):
        if not f(table[s[i]],s[i+1]):
            flag =False
    if flag:
        ans+=1
print(ans)

Measured memory_bytes: 3064
def primes(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2,n+1,i):
            is_prime[j] = False
    return is_prime

e = primes(10**5)

tc = 0
li = []

for i in range(len(e)):
    if i%2 == 0:
        li.append(tc)
    else:
        if e[i] and e[(i+1)//2]:
            tc += 1
        li.append(tc)

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(li[r]-li[l-1])


Measured memory_bytes: 5144
import scala.io.StdIn

object Main extends App{
  val w = StdIn.readLine()
  val result = w
    .groupBy((char:Char) => char)
    .mapValues(_.length)
      .filter(_._2 % 2 == 1)
  if (result.nonEmpty) println("No") else println("Yes")
}

Measured memory_bytes: 25564
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Math;


namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            int[] n = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int N = n[0];
            int Q = n[1];
            string s = ReadLine();
            int[] T = new int[N];//累積和,ACが出た回数を表す
            int ACcnt = 0;
            T[0] = ACcnt;
            for (int i = 1; i < N; i++)//線形探索
            {
                if (s[i]=='C' && s[i-1] == 'A')
                {
                    ACcnt++;
                }
                T[i] = ACcnt;
            }

            for (int i = 0; i < Q; i++)
            {
                int[] q = ReadLine().Split(' ').Select(int.Parse).ToArray();
                int ql = q[0];
                int qr = q[1];
                WriteLine(T[qr-1] - T[ql-1]);
            }
        }
    }
}


Measured memory_bytes: 18496
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
typedef long long ll;
const int MOD = 1000000007;
using namespace std;
class segment_tree{
public:
  int n;
  pair<ll, int>team[1 << 18];
  
  segment_tree(int n_){
    n = 1;
    while(n < n_) n *= 2;

    for(int i = 0;i < 2 * n;i++){
      team[i] = make_pair(0, 0);
    }

    for(int i = n - 1;i < 2 * n;i++){
      team[i] = make_pair(0, i - (n - 1));
    }
  }

  void update(int tid, int nscore){
    tid += n - 1;
    team[tid].first += nscore;
    
    while(tid > 0){
      tid = (tid - 1) / 2;
      if(team[tid * 2 + 1].first == team[tid * 2 + 2].first){
	if(team[tid * 2 + 1].second < team[tid * 2 + 2].second){
	  team[tid] = team[tid * 2 + 1];
	}else{
	  team[tid] = team[tid * 2 + 2];
	}
      }else{
	team[tid] = max(team[tid * 2 + 1], team[tid * 2 + 2]);
      }
    }
  }
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int num, r, l;
  ll ftime[100005] = {};
  int d, t, x;
  int now = 0;
  
  cin >> num >> r >> l;
  if(r != 0){
    segment_tree seg(num);
  
    for(int i = 0;i < r;i++){
      //cout << seg.team[1 + seg.n - 1].second << endl;
      cin >> d >> t >> x;
      ftime[seg.team[0].second] += (t - now);
      seg.update(d - 1, x);
      now = t;
    }
    
    ftime[seg.team[0].second] += (l - now);
    int mini = 0;
    for(int i = 0;i < num;i++){
      //cout << ftime[i] << ' ';
      if(ftime[mini] < ftime[i]){
	mini = i;
      }
    }
    cout << mini + 1 << endl;
  }else{
    cout << 1 << endl;
  }
  return 0;
}




Measured memory_bytes: 8092
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace abc163
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
            if (File.Exists("input.txt"))
            {
                Console.SetIn(new StreamReader("input.txt"));
            }
			solve_abc163A();
			Console.Out.Flush();

        }

        public static void solve_abc163B()
        {
        }

        public static void solve_abc163A()
        {
            int r = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine(2 * Math.PI * r);
        }
    }
}


Measured memory_bytes: 28516
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%s", $s);
$x = 0;
$max = 0;
for($i = 0; $i < $n; $i++) {
    $x = ($s[$i] == 'I') ? ++$x : --$x;
    $max = ($x > $max) ? $x : $max;
}
echo $max. PHP_EOL;

Measured memory_bytes: 4728
// atcoder/code-festival-2016-quala/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.setf(std::ios_base::fixed);
  std::cout.precision(15);

  int n;
  while (cin >> n) {
    vec<int> a(n);
    cin >> a;
    each (i, a) --i;

    int cnt = 0;
    for (int i = 0; i < a.size(); ++i) {
      cnt += (a[a[i]] == i);
    }
    cout << cnt / 2 << endl;
  }

  return 0;
}


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

using namespace std;

int main()
{
  string S;
  cin >> S;

  int N = S.size();
  long long MOD = 1e9 + 7;

  long long dp[100010][4] = {};

  for (int i = N; i >= 0; i--) {
    for (int j = 3; j >= 0; j--) {
      if (i == N) {
        dp[i][j] = (j == 3 ? 1 : 0);
      } else {
        dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3LL : 1LL);
        if (j < 3 && (S[i] == "ABC"[j] || S[i] == '?')) {
          dp[i][j] += dp[i+1][j+1];
        }
        dp[i][j] %= MOD;
      }
    }
  }
  cout << dp[0][0] << endl;
  return(0);
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll A, B;
  cin >> A >> B;
  ll g = __gcd(A,B);
  ll s = g;
  ll ans = 1;
  for(ll i=2; i<=sqrt(s); i++){
    if(g%i==0){
      ans+=1;
      while(g%i==0){
        g/=i;
      }
    }
  }
  if(g>1){
    ans++;
  }
  cout << ans;
  
}

Measured memory_bytes: 256
N=int(input())
S=input()

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)



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

using namespace std;

int main() {
	int a[6];
	for (int i = 1; i <= 5; ++i)
		cin >> a[i];
	int res = 1e9 + 7;
	sort(a + 1, a + 6);
	do {
		int tmp = 0;
		for (int i = 1; i <= 5; ++i) {
			if (tmp % 10) tmp = (tmp / 10 + 1) * 10;
			tmp += a[i];
		}
		res = min(res, tmp);
	}
	while (next_permutation(a + 1, a + 6));
	cout << res;
	return 0;
}


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

ll solve() {
    ll X;
    cin >> X;
    ll a = 100, c = 0;
    while ( a < X ) {
        a += a / 100LL;
        c++;
    }
    ll ans = c;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

int n, h[500];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    sort(h, h+n, greater<int>());
    long long int ans = 1;
    for(int i = 0; i < n; i++){
        ans += (( h[i] - i/4 > 0 ) ? ( h[i] - i/4 ) : 0);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
const ll mod=1000000007;
ll gcd(ll a,ll b){if(a<b)swap(a,b);while((a%b)!=0){a=b;b=a%b;}return b;}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main(){
  ll n,x; cin>>n>>x;
  vector<ll> a(n);
  ll ans=0;
  rep(i,n) cin>>a[i];
  rep(i,n-1){
    ll k=a[i]+a[i+1];
    if(k>x){
      ans+=k-x;
      if(a[i+1]<k-x)
      a[i+1]=0;
      else
      a[i+1]-=k-x;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <cassert>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
#include <type_traits>
#include <fstream>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}

struct UnionFind {
public:
  std::vector<ll> par;
  std::vector<ll> rank;
  std::vector<ll> size;
  std::vector<ll> diff_weight;

  UnionFind(ll N){
    par         = std::vector<ll>(N+1, 0LL);
    rank        = std::vector<ll>(N+1, 0LL);
    size        = std::vector<ll>(N+1, 1LL);
    diff_weight = std::vector<ll>(N+1, 0LL);
    for (ll i = 0; i <= N; i++) par[i] = i;
  }

  ll find(ll x){
    if (par[x] == x) return x;
    ll root = find(par[x]);
    diff_weight[x] += diff_weight[par[x]];
    par[x] = root;
    return root;
  }

  void unite(ll x, ll y, ll w) {
    w += get_weight(x);
    w -= get_weight(y);

    x = find(x);
    y = find(y);
    if (x == y) return;

    size[x] += size[y];
    size[y] = size[x];

    if (rank[x] < rank[y]) std::swap(x, y), w = -w;
    if (rank[x] == rank[y]) rank[x]++;

    par[y] = x;
    diff_weight[y] = w;
    //print(x, y, diff_weight[x], diff_weight[y]);

    return;
  }

  bool is_same(ll x, ll y){
    return find(x) == find(y);
  }

  ll get_size(ll x){
    return size[find(x)];
  }

  ll get_weight(ll x){
    find(x);
    return diff_weight[x];
  }

  ll get_diff(ll x, ll y){
    //print("diff", y, x, get_weight(y), get_weight(x));
    return get_weight(y) - get_weight(x);
  }
};

int main(int argc, char* argv[])
{
  ll N, M;
  std::cin >> N >> M;

  std::vector< std::pair<ll, ll> > vp(M);
  for (ll i = 0; i < M; i++) {
    ll a, b;
    std::cin >> a >> b;
    a--; b--;
    vp[i].first  = a;
    vp[i].second = b;
  }

  ll cnt = 0;
  for (ll d = 0; d < M; d++) {
    UnionFind info(N);
    for (ll i = 0; i < M; i++) {
      if (i == d) continue;
      info.unite(vp[i].first, vp[i].second, 0);
    }
    if (info.get_size(0) < N) cnt++;
  }

  print(cnt);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>   
#define ll long long int  
#define mkp make_pair 
#define mod 1000000007 
#define maxn 100001 
#define ff first
#define ss second
using namespace std;     
bool check(int i,int j,int k){  
    return (i!=j&&j!=k&&k!=i);
    } 

int main(){    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);    
  int n; 
  cin>>n; 
  ll arr[n];   
  for(int i=0;i<n;++i)cin>>arr[i];
  ll ans=0;  
  for(int i=0;i<n;++i){
      for(int j=i+1;j<n;++j){
          for(int k=j+1;k<n;++k){ 
  if(arr[i]+arr[j]>arr[k]&&arr[i]+arr[k]>arr[j]&&arr[j]+arr[k]>arr[i]&&check(arr[i],arr[j],arr[k]))++ans;
          } 
     } 
  }
  cout<<ans<<"\n";          
       
return 0;  
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
int main(){
    int n; cin >> n;
    int res = 0;
    n %= 1000;
    res = 1000 - n;
    if(res==1000){res = 0;}
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

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

  vector< pair<double, int> > GPA(N);
  for(int i=0; i<N; i++) {
    double val; cin >> val;
    GPA[i] = make_pair(val, i);
  }
  sort(GPA.begin(), GPA.end());

  vector<int> ans(N);
  for(int i=0; i<N; i++) {
    int id = GPA[i].second;

    int lb = lower_bound(GPA.begin(), GPA.end(), make_pair(GPA[i].first, -1)) - GPA.begin();
    int ub = upper_bound(GPA.begin(), GPA.end(), make_pair(GPA[i].first, N+1)) - GPA.begin();

    // printf("lb = %d, ub = %d\n", lb, ub);
    ans[id] = 3*lb + (ub-lb-1);
  }
  for(int i=0; i<N; i++) cout << ans[i] << endl;
  return 0;
}



Measured memory_bytes: 4704
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;

int n;
long long dp[100][21] = {0};
int numbers[100];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	dp[0][numbers[0]] = 1;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 0; j <= 20; j++) {
			if (j + numbers[i] <= 20)dp[i][j] += dp[i - 1][j + numbers[i]];
			if (j - numbers[i] >= 0 )dp[i][j] += dp[i - 1][j - numbers[i]];
		}
	}
	cout << dp[n - 2][numbers[n - 1]] << endl;
}

Measured memory_bytes: 3112
#define MAX_N 200000
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(int argc, const char * argv[]) {
    int N, K;
    int A[MAX_N];
    cin >> N >> K;
    for (int i=0; i<N; i++) {
        cin >> A[i];
    }
    
    int B[MAX_N];
    fill(B, B+MAX_N, 0);
    for (int i=0; i<N; i++) {
        B[A[i]] += 1;
    }
    sort(B, B+MAX_N, greater<int>());
    
    int ans = 0;
    for (int i=K; i<N; i++) {
        ans += B[i];
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792