akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, h int
	fmt.Scan(&n, &h)
	arr1, arr2 := make([]int, n + 1), make([]int, n + 1)
	for i := 1; i < n + 1; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		arr1[i], arr2[i] = a, b
	}
	sort.Sort(sort.IntSlice(arr1))
	sort.Sort(sort.IntSlice(arr2))
	ma := arr1[n]
	count := 0
	for i := n; i >= 0; i-- {
		x := arr2[i]
		if ma >= x {
			break
		}
		h -= x
		count++
		if h <= 0 {
			break
		}
	}
	if h <= 0 {
		fmt.Println(count)
	} else {
		mod := h % ma
		count += h / ma
		if mod != 0 {
			count++
		}
		fmt.Println(count)
	}
}

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

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

    ll n,k;
    cin >> n >> k;
    vector<ll> h(n);
    for (ll i = 0;i < n;i++){
        cin >> h[i];
    }
    sort(h.begin(), h.end());
    ll x = n-k+1;
    ll ans = h[n-1];
    for (ll i = 0; i < x; i++){
        ans = min(ans, h[i+k-1]-h[i]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3988
#include<bits/stdc++.h>
#define fr(i,x,y) for(int i=x;i<=y;++i)
#define rf(i,x,y) for(int i=x;i>=y;--i)
#define LL long long
using namespace std;
const int N=30;
struct data{
	int nt,to,w;
}a[N*N];
int b[N],head[N];
int n,m,cnt=0;

void add(int x,int y,int w){
	a[++cnt].to=y,a[cnt].w=w,a[cnt].nt=head[x],head[x]=cnt;
}

int main(){
	int L;scanf("%d",&L);
	int n=0,tmp=L;
	for(;L;L>>=1) n++;
	L=tmp;
	fr(i,1,n-1) add(i,i+1,1<<(i-1)),add(i,i+1,0);
	int gg=1<<(n-1);
	rf(i,n-1,1) if((L>>(i-1))&1) add(i,n,gg),gg+=(1<<(i-1));
	printf("%d %d\n",n,cnt);
	fr(u,1,n) for(int i=head[u];i;i=a[i].nt){
		printf("%d %d %d\n",u,a[i].to,a[i].w);
	}
	return 0;
}

Measured memory_bytes: 256
/* << IN THE NAME OF GOD >> */
#include <bits/stdc++.h>
using namespace std;



#define err(x) cerr << #x  << " = "<<  x << '\n'
#define out(x) cout << x << '\n'
#define forp(i, r, l) for(int i = int(r); i < int(l); i++)
#define forn(i, r, l) for(int i = int(r); i > int(l); i--)
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll ,ll> pll;
const int maxn = 5e5 + 120;
 

int n,res = INT_MAX ,a[maxn] ,b[maxn];
char c[maxn];

int main(){FAST;
    cin >> n;
    forp(i ,1 ,n+1){
        cin >> c[i];
        a[i] = a[i - 1],b[i] = b[i - 1];
        c[i] == 'E' ? a[i]++ : b[i]++;
    }
    
    forp(i ,1 ,n + 1)
        res = min(res ,b[i - 1] + a[n] - a[i]); 
    
    out(res);
    return 0;

}
 










Measured memory_bytes: 3840
//I am so vegetable
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PB push_back
#define IN insert
#define ER erase
#define CT count
#define EP empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = 3.141593;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    ll X=x;
    x=y; y=X-a/b*y;
}
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2) % mod; }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }

const int N = 1e5+5;
vector<int>edge[N];
int h[N];
int main() {
	//ofstream cout("E:\\acm dream\\out.txt",ios::out);
	FIO;
	int n,m;cin>>n>>m;
    _for(i,1,n+1)cin>>h[i];
    _for(i,0,m){
        int x,y;cin>>x>>y;
        edge[x].PB(y),edge[y].PB(x);
    }
    int sssss = 0;
    _for(i,1,n+1){
        int flag = 1;
        _sfor(it,edge[i]){
            if(h[it]>=h[i]){
                flag = 0;
                break;
            }
        }
        if(flag)++sssss;
    }
    cout<<sssss;
	return 0;
}


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

using namespace std;

typedef long long ll;

const int N = 2e5+5;

int n;
int k;
int ar[N];
int cnt[N];

int main(){
    scanf("%d%d " , &n , &k);
    int mn = 2e9;
    for(int i = 1; i <= n; i++){
        scanf("%d" , &ar[i]);
        mn = min(mn , ar[i]);
        cnt[ar[i]]++;
    }
    k--;
    long long ans = ( n - cnt[mn] + k - 1 ) / (k);
    //cout << n - cnt[mn] + 1 << "\n";
    printf("%lld\n" , ans);
}


Measured memory_bytes: 4592
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vvi vector<vi>
#define pai(k) pair<k,k>
#define mod 1000000007
#define mpai make_pair
#define p1 first
#define p2 second
#define pb push_back
#define umap(x,y) unordered_map<x,y>
static void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);}

class graph{
	vector<int>adj[200001];
public:
	// graph(int n){
	// 	for(int i=0;i<n;i++)
	// 		adj[i]=vector<int>();
	// }
	void addedge(int a, int b){
		adj[a].pb(b);
		adj[b].pb(a);
	}
	int dfs(int node, vector<int>&visited){
		visited[node]=1;
		int ans=0;
		for(auto i:adj[node]){
			if(!visited[i])
				ans += dfs(i,visited);
		}
		return 1+ans;
	}
	int solve(int n){
		vector<int>visited(n+1,0);
		int maxans=0;
		for(int i=0;i<n;i++){
			if(!visited[i])
			{
				// cout<<"g";	
				// exit(0);
				maxans = max(maxans, dfs(i,visited));
				// count+=1;
			}
		}
		return maxans;
	}

};


int main()
{
fast();


    int n=0,a,b,m;
    cin>>n>>m;
    if(m==0)
    	cout<<"1\n";
    else{
    graph g;
    for(int i=0;i<m;i++){
	cin>>a>>b;
	g.addedge(a-1,b-1);
}
// cout<<"h";
// exit(0);
int ans =g.solve(n);
cout<<ans<<"\n";
}

return 0;
}


Measured memory_bytes: 24296
import java.io.*;
import  java.util.*;
 
import static java.lang.System.in;
 
class Main{
    static long[] X,sum;
    static Edge[] edges;
    static int[] id,unconnected;
    public static void main(String[] args)throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        sum = new long[n+1];
        edges = new Edge[m];
        id = new int[n+1];
        unconnected = new int[n+1];
 
        for(int i=1;i<=n;i++) {
            sum[i] = sc.nextLong();
            id[i] = i;
        }
        for(int i=0;i<m;i++){
            int a = sc.nextInt(), b = sc.nextInt();
            long y = sc.nextLong();
            edges[i] = new Edge(a,b,y);
        }
        Arrays.sort(edges);
        for(int i=0;i<m;i++){
            Edge e = edges[i];
            union(e.left,e.right,e.weight);
        }
        int ans = unconnected[find(1)];
        System.out.println(ans);
    }
    static int find(int p){
        while(p!=id[p]){
            id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }
    static void union(int p, int q, long Y){
        int i = find(p), j = find(q);
        if(i==j){
            if(Y>sum[i]) unconnected[i]++;
        } else{
            if(Y<=sum[i]+sum[j]) unconnected[i]=0;
            else unconnected[i]+=1+unconnected[j];
            sum[i] += sum[j];
            id[j] = i;
        }
    }
    static class Edge implements Comparable<Edge>{
        int left, right;
        long weight;
        public Edge(int l, int r, long w){
            this.left = l; this.right = r;
            this.weight = w;
        }
        public int compareTo(Edge e){
            return Long.compare(this.weight,e.weight);
        }
    }
}

Measured memory_bytes: 108884
#!/mnt/c/Users/moiki/bash/env/bin/python
#FROM : https://atcoder.jp/contests/dp/submissions/3971457
import sys
import numpy as np
N,W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))

dp = np.full(N*1000 + 1 , W+1, dtype=np.int64)
# print(dp)
dp[0] = 0
for w,v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])


# from pdb import set_trace; set_trace()
print( ((dp<=W) * np.arange(N*1000 + 1)).max() )


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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
long myPow(long x, long n, long m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}


int main(){
    long long m,n;
    cin>>m>>n;

    cout<<myPow(m,n,mod)<<endl;;

    return 0;

}
/*


*/



Measured memory_bytes: 3112
#include <chrono>
#include <vector>
#include <iostream>

using namespace std;
using namespace std::chrono;

int main() {
  auto start = high_resolution_clock::now();

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
    --v[i];
  }

  int ans = 0;
  int last = 0;
  for (int i = 0; i < n; ++i) {
    if (v[i] == i) {
      ++last;
    } else {
      ans += (last + 1) / 2;
      last = 0;
    }
  }
  ans += (last + 1) / 2;

  cout << ans << endl;

  cerr << "Total execution time : " << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << " ms" << endl;

  return 0;
}


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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define FOR(i, a, b) for (ll i = (a), i < (N): i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N, A;
    cin >> N >> A;
    N %= 500;
    if (N <= A) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int L, n;
int x[N];
long long fromFront[N];
long long fromBack[N];

long long getFront(int i, int j)
{
  if(i > j)
    return 0LL;
  return fromFront[j] - (i > 0 ? fromFront[i - 1] : 0);
}

long long getBack(int i, int j)
{
  if(i > j)
    return 0LL;
  return fromBack[i] - (j + 1 < n ? fromBack[j + 1] : 0);
}

int main()
{
  scanf("%d%d", &L, &n);
  long long ans = 0;
  for(int i = 0 ; i < n ; i++)
      scanf("%d", x + i);
  for(int it = 0 ; it < 2 ; it++){
    for(int i = 0 ; i < n ; i++){
      fromFront[i] = x[i];
      if(i)
        fromFront[i] += fromFront[i - 1];
    }
    for(int i = n - 1 ; i >= 0 ; i--){
      fromBack[i] = L - x[i];
      if(i + 1 < n)
        fromBack[i] += fromBack[i + 1];
    }
    for(int i = 0 ; i < n ; i++){
      int len = n - i;
      int mid = i + len / 2;
      long long cur = getFront(i, mid - 1) + getBack(mid + 1, n - 1);
      cur *= 2LL;
      if(len & 1) cur += getFront(mid, mid);
      else cur += getBack(mid, mid);
      ans = max(ans, cur);
    }
    for(int i = 0 ; i < n ; i++)
      x[i] = L - x[i];
    reverse(x, x + n);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true;
    for (auto next_v : G[v]) {
        if (seen[next_v]) continue;
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    // 全頂点が訪問済みになるまで探索
    int count = 0;
    seen.assign(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue; // v が探索済みだったらスルー
        dfs(G, v); // v が未探索なら v を始点とした DFS を行う
        ++count;
    }
    cout << count-1 << endl;
}


Measured memory_bytes: 9556
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define vi vector<int>
#define Sort(v) sort(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;




int main(){
    int w,h,x,y,r;
    cin >> w >> h >> x >> y >> r;
    
    if(x>=r && w>=x+r && y>=r && h>=y+r) cout << "Yes" << endl;
    else cout << "No" << endl;
}









Measured memory_bytes: 3096
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=0;i<n;i++){
            for(int j=1;j<=k && i+j<n;j++){
                dp[i+j] = Math.min(dp[i+j], dp[i]+Math.abs(a[i+j]-a[i]));
            }
        }
        System.out.println(dp[n-1]);
    }
}

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

int main(void) {
    char *buf;
    char *p;
    int i;
    char before;
    int cnt = 0;
    int fin = 0;

    buf = malloc(100003);
    p = fgets(buf, 100003, stdin);

    before=buf[0];
    for(i=1;;i++){
        switch(buf[i]) {
            case 'B':
            case 'W':
                if(before != buf[i]){
                    before = buf[i];
                    cnt++;
                }
                break;
            default:
                fin = 1;
        }

        if(fin) break;
    }

    printf("%d\n", cnt);
    free(buf);

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = std::vector<int>;
using VI2D = std::vector<vector<int>>;
using VLL = std::vector<long long>;
using VLL2D = std::vector<vector<long long>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T, std::size_t N>
struct make_vector_type {
	using type =
		typename std::vector<typename make_vector_type<T, (N - 1)>::type>;
};

template <typename T>
struct make_vector_type<T, 0> {
	using type = typename std::vector<T>;
};

template <typename T, size_t N>
auto make_vector_impl(const std::vector<std::size_t>& ls, T init_value) {
	if constexpr(N == 0) {
		return std::vector<T>(ls[N], init_value);
	} else {
		return typename make_vector_type<T, N>::type(
			ls[N], make_vector_impl<T, (N - 1)>(ls, init_value));
	}
}

template <typename T, std::size_t N>
auto make_vector(const std::size_t (&ls)[N], T init_value) {
	std::vector<std::size_t> dimensions(N);
	for(int i = 0; i < N; i++) {
		dimensions[N - i - 1] = ls[i];
	}
	return make_vector_impl<T, N - 1>(dimensions, init_value);
}

template <typename T>
std::vector<T> make_vector(std::size_t size, T init_value) {
	return std::vector<T>(size, init_value);
}

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max<T>(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min<T>(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

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

	cout << !t << endl;
	return 0;
}


Measured memory_bytes: 3624
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    div, m = divmod(rem, x)
                    if div:
                        stack.append((div, d*m+cost+y))
                    if m:
                        stack.append((div+1, d*(x-m)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


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

#define int long long

using namespace std;

const int N = (int)2e5;

int n, k, ans, cnt[N+5];

signed main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cnt[i%k]++;
	ans += cnt[0]*cnt[0]*cnt[0];
	if(k % 2 == 0)
		ans += cnt[k/2]*cnt[k/2]*cnt[k/2];
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
    float N,M, a[1002], sel=0,sum=0;
   std::cin>>N>>M;

   for(int i = 1;i<=N; i++){
    std::cin>>a[i];
    sum+=a[i];
   }

   sum = sum/(4*M);

   for(int i = 1;i<=N; i++){
    if(a[i]>=sum)
        sel++;
    if(sel == M)
            break;
   }
   if(sel == M)
   std::cout<<"Yes";
   else
    std::cout<<"No";
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int n,i,j,sum=0,max=0;
  scanf("%d",&n);
  char s[n+1];
  scanf("%s",s);
  for(i=1;i<n;i++){
    int a[27]={0};
    sum = 0;
    for(j=0;j<i;j++) a[s[j]-'a']=1;
    for(j=i;j<n;j++){
      if(a[s[j]-'a']==1){
        sum ++;
        a[s[j]-'a']=0;
      }
    }
    max= (max>sum)? max:sum;
  }
  printf("%d",max);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

//----------------------------------------------------------------

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> dp(n + 10);
    vector<int> a(m + 2);
    a[0] = -1;
    ll tmp = 1;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    a[m + 1] = n + 1;
    for (int i = 0; i < m + 1; i++)
    {
        for (int j = a[i] + 1; j < a[i + 1]; j++)
        {
            if (j == a[i] + 1)
            {
                dp[j] = tmp;
            }
            else if (j == a[i] + 2)
            {
                dp[j] = tmp;
            }
            else
            {
                dp[j] = (dp[j - 2] + dp[j - 1]) % mod;
            }
        }
        tmp = dp[a[i + 1] - 1] % mod;
    }
    cout << tmp << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <numeric>
#include <ctype.h>
#include <cstdlib>
#include <string.h>


using namespace std;


int main()
{
	int count = 0, a = 0, b = 0;
	string input;

	cin >> input;
	cin >> count;

	for (int i = 0; i < count; i++)
	{
		string order;

		cin >> order >> a >> b;

		if (order == "print")
		{
			for (int i = a; i <= b; i++)
				cout << input[i];
			cout << endl;
		}
		else if (order == "reverse")
		{
			int b2 = b;
			string _input = input;

			for (int i = a ; i <= b; i++)
			{
				input[i] = _input[b2--];
			}
		
		}
		else if (order == "replace")
		{
			string cha;
			cin >> cha;

			input.replace(input.begin() + a, input.begin() + b + 1, cha);
		}


	}
	

	
}

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

int main()
{
    long long X;
    cin >> X;
    long long P = 100, step = 0;
    while (P < X)
    {
        P += P / 100;
        step++;
    }
    cout << step << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
inline int lowbit(int x){return x&-x;}
long long tr[N],a[N],d[N];
long long n,m;
int query(int x){
	int ans=0;
	while (x){
		ans+=tr[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int k){
	while (x<=n+n+1){
		tr[x]+=k;
		x+=lowbit(x);
	}
}
bool check(int x){
	long long tot=0;
	memset(tr,0,sizeof tr);
	d[0]=n+1;
	for (int i=1;i<=n;++i){
		if (a[i]<x) d[i]=-1;
		else d[i]=1;
		d[i]+=d[i-1];
	}
	add(d[0],1);
	for (int i=1;i<=n;++i){
		tot+=query(d[i]);
		add(d[i],1);
	}
	return (tot>=m/2);
}
int main(){
	scanf("%d",&n);
	m=(n+1)*n/2;
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	if (n==1){printf("%d\n",a[1]);return 0;}
	int l=1,r=1e9;
	while (l<r){
		int mid=(l+r+1)>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
}



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

using namespace std;

using ll = long long;

int main(){
    ll n; cin >> n;
    ll arr[n], arr1[n];
    for(ll i = 0; i < n; ++i){
        cin >> arr[i];
    }
    for(ll i = 0; i < n; ++i){
        cin >> arr1[i];
    }
    ll ans = accumulate(arr, arr + n, 0) + arr1[n - 1];
    ll ans1 = accumulate(arr1, arr1 + n, 0) + arr[0];
    ll rans;
    rans = max(ans, ans1);
    for(ll i = 1; i < n; ++i){
        ans1 = ans1 - arr1[i - 1] + arr[i];
        rans = max(rans, max(ans, ans1));
    }
    cout << rans;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
const ll inf = 1LL<<60;
ll H,W;
vector<vector<char>> S;
vector<vector<ll>> ct;
queue<pair<ll,ll>> Q;
ll ma=0;

void bfs(){
    

    while(!Q.empty()){
        auto tmp = Q.front();Q.pop();
        ll x = tmp.first, y = tmp.second;

        ll dx[4]={1,0,-1,0};
        ll dy[4]={0,1,0,-1};
        for(int j=0;j<4;j++){
            ll tx=x+dx[j],ty=y+dy[j];
            if(tx>=W || tx<0 || ty>=H || ty<0) continue;
            else {
                if(S[ty][tx]=='.'){
                    ct[ty][tx]=ct[y][x]+1;
                    ma=max(ma,ct[ty][tx]);
                    S[ty][tx] = '#';
                    Q.push(make_pair(tx,ty));
                }
            }
        }
    }
}

int main() {
    cin >> H >> W;
    ll blk=0;
    S.assign(H,vector<char>(W));
    ct.assign(H,vector<ll>(W));
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> S[i][j];
            if(S[i][j]=='#') Q.push(make_pair(j,i));
        }
    }
    bfs();
    cout << ma << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  int minimum = 100000000;
  for (int i = 0; i < N; i++) {
    int target;
    int count = 0;
    target = vec.at(i);
    
    while (target % 2 == 0){
      target /= 2;
      count++;
    }    
    minimum =  min(minimum, count);
  }
 
  cout << minimum << endl;
}

Measured memory_bytes: 256
# coding: utf-8


def main():
    n = int(input())
    nums = list(map(int, input().split(' ')))    

    max_number = max(nums)
    min_number = min(nums)
    min_sums = []
    for p in range(min_number, max_number+1):
        sum_ = 0
        for x in nums:
            sum_ += (x - p) ** 2
        min_sums.append(sum_)

    print(min(min_sums))

    return 0


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main (void) {
    int N;
    cin >> N;
    int X;
    X = ((int)((N/1.08)*100) % 10 > 0) ? N / 1.08 + 1 : N / 1.08;
    if ((int)(X*1.08) == N) {
        cout << X << endl;
    } else {
        cout << ":(" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[n+5];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,greater<int>());
long long sum=0;
for(int i=0;i<k;i++) sum+=a[i];
cout<<sum<<endl;
return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<algorithm>
#include<bitset>
#include<queue>
#include <math.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);cout << fixed;
#define dbset(x) for(int i=0 ; i<x.size(); i++) cerr << x[i] << " "; cerr << endl;
#define inf 1000000007
#define INF 1000000000000000000LL
#define PI 3.14159265358979323846
#define mod 1000000007
#define mod1 1000696969
#define flusz fflush(stdout);
#define VI vector<int>
#define VPI vector < pair<int,int> >
#define PII pair<int, int>
#define PIII pair<pair<int,int>,int>
#define BIT bitset<N>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define M (L+R)/2
#define endl '\n'
#define REP(x, y) for(int x = 0; x < (y); ++x)
#define FOR(x, y, z) for(int x = y; x <= (z); ++x)
#define FORR(x, y, z) for(int x = y; x >= (z); --x)
using namespace std;

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

#define int long long
const int N = 1000*1000 + 7;

int test;

string s,ss;

void solve()
{
	cin >> s;

	int res = 0;

	int cou = 0;

	REP(i,s.size()){
		if (s[i] == 'A'){
			cou++;
			continue;
		}

		if (s[i] == 'B' && i != s.size() - 1 && s[i + 1] == 'C'){
			i++;
			res += cou;
			continue;
		}

		cou = 0;
	}

	cout << res;

    return;
}

int32_t main()
{
    boost

    test=1;

	for(int i=1; i <= test; i++){
        solve();
	}

    return 0;
}


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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        long ans = in.nl();
        for (int i = 0; i < n-1; i++) {
            ans = lcm(ans, in.nl());
        }
        out.println(ans);
    }
    public static long lcm(long a, long b){
        return a*(b/gcd(a,b));
    }
    public static long gcd(long a, long b){
        long c;
        if(a < b){
            c = a;
            a = b;
            b = c;
        }
        while(b > 0){
            c = a;
            a = b;
            b = c%b;
        }
        return a;
    }
    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 21076
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
int n,c1,c2=0;
	cin>>n;
  char s[n+1];
  int i=0;
  rep(i,n){
  cin>>s[i];
  }
  i=0;
  rep(i,n){
	if(s[i]=='R'){
	c1++;
    }
    if(s[i]=='B'){
	c2++;
    }
  }
  if(c1>c2)cout<<"Yes"<<endl;
  if(c2>=c1)cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define NUMX 753
int main(void){

	char num[11];
	char cnum[3];
	int i;
	int lovenum = NUMX;
	int ans = 800;
	
	fgets(num,11,stdin);
	//fputs(num,stdout);
	//printf("\n");
	
	for(i=0;num[i+2] != '\0';i++){
		//printf("%c%c%c\n",num[i],num[i+1],num[i+2]);
		cnum[0] = num[i];
		cnum[1] = num[i+1];
		cnum[2] = num[i+2];
		
		if(ans > abs(lovenum - atoi(cnum))){
			ans = abs(lovenum - atoi(cnum));
		}
		
	}

	printf("%d",ans);
	
	return 0;
}



Measured memory_bytes: 128
def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

Measured memory_bytes: 133508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll factorial[670000];

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    ll x1, y1;
    ll d = exgcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

ll inverse(ll a)
{
	ll x, y, g = exgcd(a, MOD, x, y);
	return (x % MOD + MOD) % MOD;
}

ll binomial_coefficient(ll n, ll k)
{
	return factorial[n] * inverse(factorial[k]) % MOD * inverse(factorial[n - k]) % MOD;
}

int main()
{
	ll x, y;
	cin >> x >> y;
	if (2 * x >= y && 2 * y >= x && (2 * x - y) % 3 == 0 && (2 * y - x) % 3 == 0) {
		ll n = (2 * x - y) / 3, m = (2 * y - x) / 3;
		factorial[0] = 1;
		for (ll i = 1; i <= n + m; i++) {
			factorial[i] = factorial[i - 1] * i % MOD;
		}
		cout << binomial_coefficient(n + m, m);
	} else
		cout << 0;
	return 0;
}

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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, t, u;
	int a, b;
	cin >> s >> t;
	cin >> a >> b;
	cin >> u;
	if(s==u)a--;
	else b--;
	cout << a <<" "<<b <<"\n";
} 

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < n;i++)
int main() {
	int x, y, z;
	cin >> x >> y >> z;
	cout << (x - z) / (y + z) << endl;
}

Measured memory_bytes: 256
// khodaya khodet komak kon
#include <bits/stdc++.h>
#include <stdio.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 1e4 + 10;
const ll INF = 1e18;
const ll LOG = 20;
ll a[] = {0, 2, 5, 5, 4, 5, 6, 3 ,7, 6};
ll n, m;
vl B;
bool dp[N / 2][N];
ll v;
str C[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
int main(){
	IOS;
	scanf("%lld %lld", &n, &m);
	for (int i = 0; i < m; i++){
		scanf("%lld", &v);
		B.pb(v);	
	}
	dp[0][0] = 1;
	for (auto u:B){
		dp[1][a[u]] = 1;
	}
	//cout << "YES";
	for (int i = 2; i <= n / 2 + 1; i++){
		for (int j = 2; j <= min(n,(ll)i * 7); j++){
			for (auto u:B){
				//cout << i << ' ' << j << ' ' << u << '\n';
				if (j - a[u] < 0) continue;
				dp[i][j] = (dp[i][j] | dp[i - 1][j - a[u]]);
			}
		}
	}
	//cout << "YES";
	str ans = "";
	ll Max = -1;
	for (int i = 1; i <= n / 2 + 1; i++){
		if (dp[i][n]) Max = i;
	}
	//cout << Max << '\n';
	ll Sum = n;
	ll dig = Max;
	sort(all(B));
	//cout << dp[5][17] << '\n';
	while (Sum != 0){
		for (int i = B.size() -1; i >= 0; i--){
			//cout << Sum << ' ' << B[i] << '\n';
			if (Sum - a[B[i]] < 0) continue;
			//cout << dig << ' ' << Sum - a[B[i]] <<' ' << B[i] <<  '\n';
			if (dp[dig - 1][Sum - a[B[i]]] == 1){
				//cout << "YES";
				Sum -= a[B[i]];
				dig --;
				ans += C[B[i]];
				i = -1;
				
			}
			
		}
	}
	cout << ans;
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




Measured memory_bytes: 48128
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int main()
{
    int n, t;
    cin >> n >> t;
    VI v(n);
    rep(i, n) { cin >> v[i]; }
    sort(ALL(v));
    ll ans = 1;
    for (int i = n - 1; i >= 0; i--) {
        ll tmp = upper_bound(v.begin() + i, v.end(), v[i] + t) - lower_bound(v.begin() + i, v.end(), v[i]);
        ans *= tmp;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3484
def count(list, item):
    c = 0
    for i in list:
        if i == item:
            c += 1
    return c

def remove_item(list, item):
    list = [i for i in list if i != item]
    return list

#入力
N = int(input())
s = []
for i in range(N):
    s.append(input())
M = int(input())
t = []
for j in range(M):
    t.append(input())
best = 0

while(len(s) != 0):
    #sの最初の要素の青、赤のカードに書かれている数の差を求める
    w = s[0]
    n_s = count(s,w)
    n_t = count(t,w)
    #もらえる金額の更新
    if n_s - n_t > best:
        best = n_s - n_t
    #s,tから今調べた要素を削除する
    s = remove_item(s,w)
    t = remove_item(t,w)

print(best)

Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

int main() {
	string s;
	cin >> s;
	for (char c : s) {
		if (c == ',') c = ' ';
		cout << c;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 998244353;

struct SegTree {
    int siz;
    vector<int> node;

    SegTree(int n) : siz(1) {
        while (siz < n)
            siz *= 2;
        node.resize(2 * siz - 1, INT_MIN);
    }

    void update(int k, int x) {
        k += siz - 1;
        node[k] = x;
        while (k > 0) {
            k = (k - 1) >> 1;
            node[k] = max(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    int query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0)
            r = siz;

        if (r <= a || b <= l)
            return INT_MIN;
        if (a <= l && r <= b)
            return node[k];
        int vl = query(a, b, 2 * k + 1, l, (l + r) >> 1);
        int vr = query(a, b, 2 * k + 2, (l + r) >> 1, r);
        return max(vl, vr);
    }
};

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

    int N;
    cin >> N;

    vector<pii> range(N);
    for (int i = 0; i < N; ++i) {
        int X, D;
        cin >> X >> D;
        range[i] = {X, X + D};
    }

    sort(range.begin(), range.end());
    vector<int> rpos(N);
    for (int i = 0; i < N; ++i)
        rpos[i] = range[i].first;

    SegTree seg(N);
    vector<ll> dp(N + 2);
    dp[N] = 1;
    for (int i = N - 1; i >= 0; --i) {
        int idx = lower_bound(rpos.begin(), rpos.end(), range[i].second) - rpos.begin();
        if (i + 1 == idx)
            idx = i + 1;
        else
            idx = seg.query(i + 1, idx);
        (dp[i] += dp[i + 1] + dp[idx]) %= MOD;
        seg.update(i, idx);
    }

    cout << dp[0] << endl;
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    int i;
    string a;
    for(i=0;i<s.size();i++){
        a+=s.at(i);
        if((s.at(i)=='B')&&(a.size()==1)){
            a+='0';
        }
        if(s.at(i)=='B'){
            a.erase(a.size()-2);

        }
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
#142_E
n, m = map(int, input().split())
inf = 10 ** 10
keys = [0 for _ in range(m)]
A = [] 

for i in range(m):
    a, _ = map(int, input().split())
    keys[i] = sum([2 ** (int(c) - 1) for c in input().split()])
    A.append(a)
    
dp = [[inf for _ in range(2 ** n)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(0, m):
    for key in range(2 ** n):
        dp[i+1][key] = dp[i][key]
        
    for key in range(2 ** n):
        dp[i+1][key | keys[i]] = min(dp[i+1][key | keys[i]],
                                     dp[i][key] + A[i])

if dp[m][2 ** n - 1] == inf:
    print(-1)
else:
    print(dp[m][2 ** n - 1])

Measured memory_bytes: 78808
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

a, b = map(int, input().split())

if a<=0 and b>=0:
    print('Zero')
    exit()

if a>0 and b>0:
    print('Positive')
    exit()


if (b-a)%2 == 0:
    print('Negative')
else:
    print('Positive')

Measured memory_bytes: 3060
#include<iostream>
#include<cstring>

using namespace std;
#define M 1046527
#define L 14

char st[M][L];

int h1(int key){return key%M;}
int h2(int key){return 1+key%(M-1);}
// i is number of collision （used to search next space）
int h(int key,int i){return (h1(key)+i*h2(key))%M;}

int getChar(char ch){
  if(ch == 'A') return 1;
  else if (ch == 'C') return 2;
  else if (ch == 'G') return 3;
  else return 4;
}

long long getKey(char str[]){
  long long sum = 0;
  for(long long i = 0,p = 1;i<strlen(str);i++,p*=5)
    sum+=p*getChar(str[i]);
  return sum;
}

int insert(char str[]){
  long long key = getKey(str), i = 0, hi;
  for(;;i++){
    hi = h(key,i);
    if(strcmp(st[hi],str)==0)return 1; //if equal it exist
    else if(strlen(st[hi])==0){
      strcpy(st[hi],str);
      return 0;
    }
  }
  return 0;
}
int find(char str[]){
  long long key, i, hi;
  key = getKey(str);
  for(i=0;;i++){
    hi = h(key,i);
    if(strcmp(str,st[hi])==0) return hi;
    else if(strlen(st[hi])==0) return 0;
  }
  return 0;
}

int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    char cmd[10];
    char str[L];
    cin>>cmd>>str;
    if(cmd[0]=='i')
      insert(str);
    else if(find(str))
      cout<<"yes\n";
    else
      cout<<"no\n";
  }
  return 0;
}



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

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<char>> Ai(N, vector<char>(N));
    vector<vector<char>> Bi(M, vector<char>(M));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Ai.at(i).at(j);
        }
    }
    for(int i = 0; i < M; i++){
        for(int j = 0; j < M; j++){
            cin >> Bi.at(i).at(j);
        }
    }
    bool exist = false;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i + M - 1 >= N || j + M - 1 >= N) continue;

            bool match = true;
            for(int li = 0; li < M; li++){
                for(int lj = 0; lj < M; lj++){
                    if(Ai.at(i + li).at(j + lj) != Bi.at(li).at(lj)) match = false;
                }
            }
            if(match) exist = true;
        }
    }
    
    if(exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
  int i;
  string s,t;
  cin >> s >> t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end(),greater<char>());
  if (s<t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
// Problem : D - Replacing
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

/*
 * author :Sadik Hassan(_sad_)
 *
*/
#include "bits/stdc++.h"
using namespace std;
using   ll =          long long;
using   ld =          long double;
#define nl            "\n"
#define pb            push_back
#define fi            first
#define se            second
#define MP            make_pair
#define PI            (acos(-1.0))
#define rep1(i,n)     for(int i=1;i<=n;i++)
#define rep(i,n)      for(int i=0;i<n;i++)
#define SZ(s)         (int)s.size()
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define w(t)          int t;cin>>t;while(t--)
#define TSU(s)        transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSL(s)        transform(s.begin(),s.end(),s.begin(),::tolower);
#define _SAD()     	  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cout<<fixed<<setprecision(15);

typedef vector<int> vi;
typedef vector<ll> vii;
typedef set<int> si;
typedef set<ll> sii;
/*---------------------------------------------------------------------*/

const int N = (int)2e5+5;
const int MOD =(int)1e9+7;
const ll INF = (ll)1e18+5;
map<int,ll>mp,bp;
int main()
{
    _SAD()
	int n;
	cin>>n;
	vii a(n);
	ll ans=0;
	rep(i,n)
	{
		cin>>a[i];
		ans+=a[i];
		mp[a[i]]++;
		//bp[a[i]]=a[i];
	}
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(mp[x]>0)
		{
            ans-=(x*mp[x]);
            ans+=(mp[x]*y);
            mp[y]+=mp[x];
            mp[x]=0;
		}
		cout<<ans<<nl;
	}
    return 0;
}


Measured memory_bytes: 9756
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  int A[N];
  for(int i=0;i<N;++i) cin>>A[i];
  int even=0, odd=0;
  map<int, int> amap;
  vector<int> arr;
  for(int i=0;i<N;++i) {
    if(amap[A[i]]==0) arr.push_back(A[i]);
    amap[A[i]]++;
  }
  for(int i=0;i<arr.size();++i) {
    if(amap[arr[i]]%2==0) even++;
    else odd++;
  }
  if(even%2==0) cout<<even+odd<<endl;
  else cout<<even+odd-1<<endl;
}



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

vector<int> a;

int func(int W) {
	int A, B, C;
	int res = 0;
	A = W - a[0]; B = W - a[1]; C = W - a[2];
	if (A < 0) {
		res += abs(A);
	}
	else {
		if (A % 2 == 0) res += A / 2;
		else res += (A + 1) / 2 + 1;
	}
	if (B < 0) {
		res += abs(B);
	}
	else {
		if (B % 2 == 0) res += B / 2;
		else res += (B + 1) / 2 + 1;
	}
	if (C < 0) {
		res += abs(C);
	}
	else {
		if (C % 2 == 0) res += C / 2;
		else res += (C + 1) / 2 + 1;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	a.resize(3);
	rep(i, 3) cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 1e5;
	for (int i = a[0]; i <= a[2]; i++) {
		ans = min(ans, func(i));
	}
	cout << ans << endl;
}


Measured memory_bytes: 256