akhauriyash/Code-Regression huggingface dataset:
/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5,INF=(1<<29),SZ=2*N+10;

struct EDGE{
    int to,cap;
    EDGE *nxt,*rev;
    EDGE(){}
    EDGE(int _t,int _c,EDGE *_n,EDGE *_r):to(_t),cap(_c),nxt(_n),rev(_r){}
};
struct GRAPH{
    EDGE edg[4*N*2+10],*head[SZ],*ncnt;
    GRAPH(){ncnt=edg;}
    void AddEdge(int u,int v,int cap){
        EDGE *p=++ncnt,*q=++ncnt;
        *p=EDGE(v,cap,head[u],q);head[u]=p;
        *q=EDGE(u,  0,head[v],p);head[v]=q;
    }
    EDGE* operator [](int id){return head[id];}
};
GRAPH Gr;
EDGE *cop[SZ];
int dis[SZ];
vector< pair<int,int> > lnk[N+3];
int n,S,T,tot;
vector<int> tset[N+3];
int ans[N+3][2];
bool vis[N+3];

int Aug(int u,int in){
    if(u==T) return in;
    int out=0;
    while(cop[u]){
        EDGE *it=cop[u];cop[u]=cop[u]->nxt;
        int v=it->to;
        if(dis[v]!=dis[u]+1 || it->cap<=0) continue;
        int tov=Aug(v,min(in-out,it->cap));
        it->cap-=tov;it->rev->cap+=tov;
        out+=tov;
        if(out==in) break;
    }
    return out;
}
bool BFS(){
    for(int i=1;i<=T;i++) dis[i]=-1,cop[i]=Gr[i];
    queue<int> que;que.push(S);dis[S]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(EDGE *it=Gr[u];it;it=it->nxt){
            int v=it->to;
            if(dis[v]!=-1 || it->cap<=0) continue;
            dis[v]=dis[u]+1;
            if(v==T) return true;
            que.push(v);
        }
    }
    return false;
}
int Dinic(){
    int res=0;
    while(BFS())
        res+=Aug(S,INF);
    return res;
}
void DFS(int u){
    vis[u]=true;tot++;
    for(int i=(int)lnk[u].size()-1;i>=0;i--){
        int v=lnk[u][i].first,id=lnk[u][i].second;
        if(ans[id][0] || vis[v]) continue;
        ans[id][0]=u;ans[id][1]=v;
        DFS(v);
    }
}
int main(){
    // freopen("input.txt","r",stdin);
    scanf("%d",&n);
    S=n*2;T=S+1;
    for(int i=2;i<=n;i++) Gr.AddEdge(S,i,1);
    for(int i=1;i<n;i++) Gr.AddEdge(i+n,T,1);
    for(int i=1;i<n;i++){
        int num;scanf("%d",&num);
        while(num--){
            int u;scanf("%d",&u);
            Gr.AddEdge(u,n+i,1);
            tset[i].push_back(u);
        }
    }
    int res=Dinic();
    if(res<n-1) printf("-1\n");
    else{
        for(int i=1;i<n;i++){
            int E=i+n,u=-1;
            for(EDGE *it=Gr[E];it && u==-1;it=it->nxt)
                if(it->cap)
                    u=it->to;
            for(int j=(int)tset[i].size()-1;j>=0;j--)
                if(tset[i][j]!=u){
                    int v=tset[i][j];
                    lnk[u].emplace_back(v,i);
                    lnk[v].emplace_back(u,i);
                }
        }
        DFS(1);
        if(tot<n) printf("-1\n");
        else
            for(int i=1;i<n;i++)
                printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}


Measured memory_bytes: 40180
#include <stdio.h>

int main (void){

	int a[3];
	int i, j, temp = 0, count = 0;

	for(i = 0; i < 3; i++){
		scanf("%d", &a[i]);
	}

	for(i = 0; i < 2; i++){
		for(j = 1; j < 3; j++){
			
			if(a[i] < a[j]){
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;	
			}
		}
	}

	count = a[0] - a[1];
	a[1] = a[0];
	a[2] = a[2] + count;

	while(a[2] < a[0]){
		a[2] = a[2] + 2;
		count++;
	}

	if(a[0] == a[2]){
		printf("%d\n", count);
		return 0;
	}else if(a[2] > a[0]){
		count = count + 1;
		printf("%d\n", count);
		return 0;
	}

}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main(){
    long N;
    cin >> N;
    long count = 0;
    for(int i = 1; i < (N-i)/i; i++){
        if((N-i)%i == 0){
            count += (N-i)/i;
        }
    }
    cout << count;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int qmin(int a, int b){
	return (a < b) ? a : b;
}

int H, n;
int left_val[800800], right_val[800800];
int mn[800800];
int tp[800800]; // 0: same 1: increasing 2: decreasing 3: none

int get_val(int seg_L, int seg_R, int val_L, int val_R, int now_tp, int pos){
	if(now_tp == 0) return val_L;
	if(now_tp == 1) return val_L + pos - seg_L;
	if(now_tp == 2) return val_R + seg_R - pos;
	return 0;
}

void pushdown(int l, int r, int k){
	tp[k+k] = tp[k+k+1] = tp[k];
	left_val[k+k] = left_val[k], right_val[k+k+1] = right_val[k];
	int mid = (l+r) >> 1;
	right_val[k+k] = get_val(l, r, left_val[k], right_val[k], tp[k], mid);
	left_val[k+k+1] = get_val(l, r, left_val[k], right_val[k], tp[k], mid+1);
	mn[k+k] = qmin(left_val[k+k], right_val[k+k]);
	mn[k+k+1] = qmin(left_val[k+k+1], right_val[k+k+1]);
}
void update(int L, int R, int now_tp, int val_L, int val_R, int l, int r, int k){
//	cout << L << " " << R << " " << now_tp << " " << val_L << " " << val_R << " " << l << " " << r << " " << k << endl;
	if(r < L || R < l) return ;
	if(L <= l && r <= R){
		left_val[k] = get_val(L, R, val_L, val_R, now_tp, l);
		right_val[k] = get_val(L, R, val_L, val_R, now_tp, r);
		mn[k] = qmin(left_val[k], right_val[k]);
		tp[k] = now_tp;
//		cout << k << ": " << left_val[k] << " " << right_val[k] << " " << mn[k] << endl;
		return ;
	}
	if(tp[k] != 3) pushdown(l, r, k);
	int mid = (l + r) >> 1;
	update(L, R, now_tp, val_L, val_R, l, mid, k+k);
	update(L, R, now_tp, val_L, val_R, mid+1, r, k+k+1);
	left_val[k] = left_val[k+k], right_val[k] = right_val[k+k+1];
	mn[k] = qmin(mn[k+k], mn[k+k+1]);
	if(tp[k+k] == 0 && tp[k+k+1] == 0 && left_val[k+k+1] == right_val[k+k]) tp[k] = 0;
	else if(tp[k+k] == 1 && tp[k+k+1] == 1 && left_val[k+k+1] == right_val[k+k] + 1) tp[k] = 1;
	else if(tp[k+k] == 2 && tp[k+k+1] == 2 && left_val[k+k+1] == right_val[k+k] - 1) tp[k] = 2;
	else tp[k] = 3;
//	cout << k << ": " << left_val[k] << " " << right_val[k] << " " << mn[k] << endl;
}
int query(int pos, int l, int r, int k){
//	cout << l << " " << r << " " << k << " " << tp[k] << " " << left_val[k] << " " << right_val[k] << ": " << pos << endl;
	if(tp[k] != 3) return get_val(l, r, left_val[k], right_val[k], tp[k], pos);
	int mid = (l + r) >> 1;
	if(pos <= mid) return query(pos, l, mid, k+k);
	else return query(pos, mid+1, r, k+k+1);
}

int main(){
	ios::sync_with_stdio(false);
	cin >> H >> n;
	update(0, n-1, 0, 0, 0, 0, n-1, 1);
	rep(i, H){
		int L, R;
		cin >> L >> R;
		L--, R--;
		if(L == 0) update(L, R, 0, 0x3f3f3f3f, 0x3f3f3f3f, 0, n-1, 1);
		else{
			int val_L = query(L-1, 0, n-1, 1);
			update(L-1, R, 1, val_L, val_L + R - L + 1, 0, n-1, 1);
		}
		if(mn[1] >= 0x3f3f3f3f) cout << "-1" << endl;
		else cout << mn[1] + i + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 11824
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

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

int par[MAXN];
int rnk[MAXN];
int siz[MAXN];

void init(int n) {
    for(int i = 0; i < n; i++) {
        par[i] = i; // 自分自身が親 = representative
        siz[i] = 1;
        rnk[i] = 0;
    }
}

int root(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] =
                   root(par[x]); // par[x] =  で親を付け替え 再帰的にrootを検索
    }
}

bool same(int x, int y) { return root(x) == root(y); }

ll size(int x) {
    x = root(x);
    return siz[x];
}

void unite(int x, int y) {
    // find representatives
    x = root(x);
    y = root(y);

    if(x == y)
        return;

    if(rnk[x] < rnk[y]) {
        siz[y] += size(x);
        par[x] = y;
        // cout << "size of" << x << " " << ;
    } else {
        siz[x] += size(y);
        par[y] = x;

        if(rnk[x] == rnk[y])
            ++rnk[x];
    }
}

int main() {
    int N, M, A, B;

    cin >> N >> M;
    init(N + 1);
    for(int i = 0; i < M; i++) {
        cin >> A >> B;
        A--;
        B--;
        unite(A, B);
    }

    ll ans = 0;
    for(int i = 0; i < N; ++i) {
        ans = max(size(i), ans);
    }
    cout << ans << endl;
}


Measured memory_bytes: 5892
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define endl "\n"
typedef long long ll;
#define traceV(v) for(auto x:v)cout<<x<<" ";cout<<endl
#define traceM(mp) for(auto x:mp)cout<<x.first<<" "<<x.second<<endl

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

  int N; cin>>N;
  string S; cin>>S;

  int res = 0;
  rep(a,10)rep(b,10)rep(c,10){    // "000" ~ "999"
    string s = to_string(a)+to_string(b)+to_string(c);

    int i = 0;
    for(auto c : S) {
      if(s[i] == c) ++i;
      if(i==3) {
        ++res;
        break;
      }
    }
  }

  cout <<res <<endl;

  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
/*
template<class... T>
ostream& operator<<(ostream& os, tuple<T...>& t) {
	for (size_t i = 0; i < tuple_size< tuple<T...> >::value; ++i) {
		if (i) os << " ";
		os << get<0>(t);
	}
	return os;
}
*/
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

class Seg {
private:
    int size;
    vector<int> data;
public:
    int get(int l, int r, int n, int L, int R) {
        if (r <= L || R <= l) return 0;
        if (L <= l && r <= R) return data[n];
        int m = (l + r) / 2;
        return get(l, m, n*2+1, L, R) + get(m, r, n*2+2, L, R);
    }
    int get(int l, int r) {
        return get(0, size, 0, l, r);
    }
    void add(int pos, int val) {
        pos += size-1;
        while (1) {
            data[pos] += val;
            if (pos == 0) break;
            pos = (pos-1)/2;
        }
    }
    Seg(int n) {
        for (size = 1; size < n; size <<= 1);
        data = vector<int>(size*2-1, 0);
    }
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
    int n, q; cin >> n >> q;
    Seg seg(n);
    REP(i, q) {
        int com, x, y; cin >> com >> x >> y; --x;
        if (com == 0) {
            seg.add(x, y);
        }
        else {
            cout << seg.get(x, y) << endl;
        }
    }
}

Measured memory_bytes: 3736
s = input()
n = len(s)
s += "  "

possible = False
for i in range(n):
    if s[i] == s[i+1]:
        print('{} {}'.format(i+1,i+2))
        possible = True
        break
    elif s[i] == s[i+2]:
        print('{} {}'.format(i+1,i+3))
        possible = True
        break
if possible == False:
    print('-1 -1')

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

using namespace std;

int main(){
  long long mod=1000000000+7;
  long long n,k;
  cin >> n >> k;
  vector<long long> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  map<long long,long long> m;
  for(int i=0;i<n;i++){
    long long cnt=0;
    if(m[a[i]]==0){
      for(int j=0;j<n;j++){
        if(a[i]>a[j]){
          cnt++;
        }
      }
      m[a[i]]=cnt;
    }
  }
  vector<long long> b(n);
  for(int i=0;i<n;i++){
    long long s=a[i];
    long long cnt=0;
    for(int j=i+1;j<n;j++){
      if(s>a[j]){
        cnt++;
      }
    }
    b[i]=cnt;
  }
  long long sum=k*(k-1)/2;
  sum%=mod;
  long long ans=0;
  for(int i=0;i<n;i++){
    ans+=k*b[i];
    ans%=mod;
    ans+=sum*m[a[i]];
    ans%=mod;
  }
  cout << ans << endl;
}

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

int main () {
    int H,W;
    string w;
    for (int a=0;a<a+1;a++) {
        cin >> H >> W;
        if (H!=0 && W!=0) {
            for (int i=1;i<=W;i++) {
                w = w +"#";
            }
            for (int j=1;j<=H;j++) {
                cout << w << endl;
            }
            cout << endl;
            w = "";
        } else {
            break;
        }
    }
}


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

int main()
{
	int H, W;
	cin >> H >> W;
	vector<string> A( H );
	for( int i = 0; i < H; i++ ) {
		cin >> A[i];
	}

	int cnt = 0;
	for( int i = 0; i < H; i++ ) {
		for( int j = 0; j < W; j++ ) {
			if( A[i][j] == '#' ) cnt++;
		}
	}
	string ans = "Possible";
	if( cnt != H + W - 1 ) ans = "Impossible";

	cout << ans << endl;
}


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

#define BUF_SIZE 30

int get_int2(int *a1, int *a2) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%d %d", a1, a2);
#else
#error
#endif
  return 0;
}

int get_int3(int *a1, int *a2, int *a3) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%d %d %d", a1, a2, a3);
#else
#error
#endif
  return 0;
}

enum query {
    QUERY_CONNECT,
    QUERY_JUDGE,
    QUERY_ALL,
};

struct vertex {
    int idx;
    int depth;
    int parent;
};

#define VERTEX_MAX 10000
#define QUERY_MAX 100000

int get_root(struct vertex ufind[], int idx) {
    struct vertex *v = &ufind[idx];
    int parent = idx;
    while(parent != v->parent) {
        parent = v->parent;
        v = &ufind[parent];
    }
    return parent;
}

void connect(struct vertex ufind[], int idx1, int idx2) {
    int root1 = get_root(ufind, idx1);
    int root2 = get_root(ufind, idx2);
    struct vertex *v1 = &ufind[root1];
    struct vertex *v2 = &ufind[root2];
    if(root1 == root2) return;
    // ensure that v1 and v2 are separated with each other.
    if(v1->depth >= v2->depth) { // v1 <- v2s
        v2->parent = v1->parent;
        if(v1->depth == v2->depth) {
            v1->depth++;
        }
        v2->depth = v1->depth;
    } else { // v2 <- v1s
        v1->parent = v2->parent;
        v1->depth = v2->depth;
    }
    return;
}

int judge(struct vertex ufind[], int idx1, int idx2) {
    return get_root(ufind, idx1) == get_root(ufind, idx2);
}

int main(void) {
    int vs, qs;
    get_int2(&vs, &qs);
    int i;
    static struct vertex ufind[VERTEX_MAX];
    static int ans[QUERY_MAX];
    int ans_idx = 0;
    // init union find
    for(i = 0; i < vs; i++) {
        ufind[i].idx = i;
        ufind[i].depth = 1;
        ufind[i].parent = i;
    }
    for(i = 0; i < qs; i++) {
        int type, v1, v2;
        get_int3(&type, &v1, &v2);
        switch(type) {
            case QUERY_CONNECT:
                connect(ufind, v1, v2);
                break;
            case QUERY_JUDGE:
                ans[ans_idx++] = judge(ufind, v1, v2);
                break;
            default:
                break;
        }
    }

    for(i = 0; i < ans_idx; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}


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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

// 桁DP ver

const int N_MAX = 100010;
ll dp1[N_MAX]; // L未満確定
ll dp2[N_MAX]; // Lになりうる

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

    // input
    string s; cin >> s;
    ll L = s.size();
    
    dp1[0] = 0;
    dp2[0] = 1;

    FOR(i, 0, L){
        if(s[i]=='1'){
            dp2[i+1] = dp2[i] * 2;
            dp1[i+1] = dp1[i] * 3 + dp2[i] * 1;
        }else{
            dp2[i+1] = dp2[i];
            dp1[i+1] = dp1[i] * 3 + dp2[i] * 0;
        }

        dp1[i+1] %= mod;
        dp2[i+1] %= mod;
    }

    ll ans = dp1[L] + dp2[L];
    ans %= mod;
    p(ans);
    
    return 0;
}

Measured memory_bytes: 2000
N = int(input())
xu = [list(map(str,input().split())) for i in range(N)]

ans = 0

for i in range(N):
    if xu[i][1] == 'JPY':
        ans += int(xu[i][0])
    else:
        ans += float(xu[i][0])*380000
        
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()

const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s,rs,p,rp,l,rl;
    cin>>s;
    int n=s.length();
    p=s.substr(0,n/2);
    l=s.substr(n/2+1);
    rs=s;
    rp=p;
    rl=l;
    reverse(All(s));
    reverse(All(p));
    reverse(All(l));
    if(s==rs&&p==rp&&l==rl)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


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

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int res = 0;
  for (int i = 0; i < (n); ++i){
    if(s[i] != s[i+1]) res++;
    else continue;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 512
import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for n in range(1,N):
  b=L[n]
  for k in range(n):
    a=L[k]
    index=bisect.bisect_left(L,a+b)
    ans+=max(0,index-n-1)
print(ans)

Measured memory_bytes: 3188
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for a in range(A + 1):
  for b in range(B + 1):
    for c in range(C + 1):
      charge = 500 * a + 100 * b + 50 * c
      if charge == X:
        ans += 1
print(ans)

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

#define INF 9223372036854775807
#define int long long
#define pi 3.14159265

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> W(s.size()+1, 0);
    vector<int> E(s.size()+1, 0);
    for(int i = 1; i <= n; i++){
        if(s[i-1] == 'E'){
            E[i]++;
        }else{
            W[i]++;
        }
        E[i]+=E[i-1];
        W[i]+=W[i-1];
    }
    int best = INF;
    for(int i = 1; i <= n; i++){
        best = min(best, W[i-1]+(E[n]-E[i]));
    }
    cout << best << endl;
}


Measured memory_bytes: 5396
N, X = map(int, input().split())
blu = []
scores = []
opponent = 0
for i in range(N):
    b, l, u = map(int, input().split())
    blu.append((b, l, u))
    scores.append(((X-b)*u + l*b, i))
    opponent += b * l

scores_sorted = sorted(scores, reverse=True)
cum = [scores_sorted[0][0]]
for i in range(1, N):
    cum.append(cum[-1] + scores_sorted[i][0])


def calc_X(k):
    ret = -opponent
    n = k // X
    m = k % X
    if n == N:
        return cum[n-1] - opponent

    for i in range(N):
        temp = 0
        b, l, u = blu[i]
        if n > 0:
            if scores[i][0] >= scores_sorted[n-1][0]:
                temp = (cum[n] - opponent) - scores[i][0]
            else:
               temp = cum[n-1] - opponent
        else:
            temp = -opponent
        if m > b:
            temp += (m-b) * u + b * l
        else:
            temp += (m-b) * l + b * l
        ret = max(ret, temp)
    return ret
        
left = 0
right = N*X

while right - left > 1:
    mid = (left + right) // 2
    if calc_X(mid) >= 0:
        right = mid
    else:
        left = mid

if calc_X(left) >= 0:
    print(left)
else:
    print(right)


Measured memory_bytes: 82904
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
#include <math.h>
#include <cctype>
using namespace std;
#define int long long
#define forn(i, n) for (int i = 0; i < n; ++i)

const int mod = 1e9 + 7;

vector<int> f(2e5 + 10), inv_f(2e5 + 10);

int bin_pow(int x , int n){
    if(n == 0)
        return 1;
    else if(n % 2)
    {
        // n нечет тогда bin_pow от n- 1
        int temp = bin_pow(x,n-1);
        return (x * temp)%mod;
    }
    else{
        int temp = bin_pow(x,n/2);
        return (temp * temp)% mod;
        // когда n чет binpown(n/2) * (binpow9n/2))
    }
}

int inv(int a) {
    // a ^ (mod - 2) % (mod) = 1 / a
    // mod простое число
    // a и mod взаимнопростые
    return bin_pow(a, mod - 2);
}

int c(int n, int k) {
    return f[n] * inv_f[k] % mod * inv_f[n - k] % mod;
}

int32_t main() {
    ios::sync_with_stdio(false);
    f[0] = 1;
    for (int i = 1; i < f.size(); i++) {
        f[i] = f[i - 1] * i % mod;
    }
    for (int i = 0; i < f.size(); i++) {
        inv_f[i] = inv(f[i]);
    }
    int h,w,n;
    cin >> h >> w >> n;
    vector<pair<int,int>>a(n);
    forn(i,n){
        cin >> a[i].first >> a[i].second;
        a[i].first--;
        a[i].second--;
    }
    a.push_back({h - 1, w - 1});
    n++;
    sort(a.begin(), a.end());
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
        dp[i] = c(a[i].first + a[i].second, a[i].first);
        for (int j = 0; j < i; j++) {
            if (a[j].first <= a[i].first && a[j].second <= a[i].second) {
                dp[i] -= dp[j] * c(a[i].first - a[j].first + a[i].second - a[j].second,
                                    a[i].first - a[j].first) % mod;
                dp[i] += mod;
                dp[i] %= mod;
            }
        }



    }
    cout << dp.back() << endl;
    return 0;
}

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

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
using namespace std;

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int N, X;
vector<int> x;

signed main()
{
    cin >> N >> X;
    x.resize(N);
    rep(i, N)
    {
        cin >> x[i];
    }

    rep(i, N)
    {
        x[i] = abs(x[i] - X);
    }

    int ans = x[0];
    rep(i, N)
    {
        ans = __gcd(ans, x[i]);
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
  while(true) {
    int X, Y, S; cin >> X >> Y >> S;
    if(X == 0 && Y == 0 && S == 0) break;
    int ans = 0;
    for(int a = 1; a <= S - 1; ++a) {
      for(int b = 1; b <= S - 1; ++b) {
        int za = a * (100+X) / 100;
        int zb = b * (100+X) / 100;
        if(za + zb == S) {
          int na = a * (100+Y) / 100;
          int nb = b * (100+Y) / 100;
          ans = max(ans, na+nb);
        }
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1160
#include<cstdio>
#include<cstring>
typedef long long ll;
int n, m;
char a[200200];
char b[200200];
int main()
{
	ll ans = 0;
	scanf("%s", &a[1]);
	n = strlen(&a[1]);
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == 'A')
		{
			b[++m] = '(';
		}
		else if (a[i] == 'B' && i < n && a[i + 1] == 'C')
		{
			b[++m] = ')';
			i++;
		}
		else b[++m] = a[i];
	}
	ll open_count = 0;
	for (int i = 1; i <= m; i++)
	{
		if (b[i] == '(') open_count++;
		else if (b[i] == ')') ans += open_count;
		else open_count = 0;
	}
	printf("%lld\n", ans);
	return 0;
}


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

vector<vector<int>> Graph;  //有向グラフ
vector<int> dp; //深さ(最大距離)
int N, M;
int x, y;
int MAX = 0;

void dsf(int n){
  if(Graph[n].size() == 0) return;
  if(dp[n] > 0) return;

  for(int j = 0; j < Graph[n].size(); j++){
    dsf(Graph[n][j]); 
    dp[n] = max(dp[n], dp[Graph[n][j]]+1);
  }
  return;
}
    

int main(){
  cin >> N >> M;
  Graph.resize(N+1, vector<int>()); 
  dp.resize(N+1, 0);

  for(int i = 0; i < M; i++){ cin >> x >> y; Graph[x].push_back(y); }
  for(int i = 1; i <= N; i++){ dsf(i); MAX = max(MAX, dp[i]); }
  cout << MAX << endl;
  return 0;
}
  







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


bool pred(const pair<string, int>& lhs,
const pair<std::string, int>& rhs)
{
return lhs.second < rhs.second;
}
int main(){

int n;
set<string>ss;

cin>>n;
map <string,int>mapp;
string s;
for(int i=0;i<n;i++){
   cin>>s;
   mapp[s]++;

}
int r;

if(!mapp.empty())
  r=(int)max_element(mapp.begin(), mapp.end(), pred)->second;


for(auto c:mapp){

   if(c.second==r){
       ss.insert(c.first);      
 
   }

}

for(auto c:ss)cout<<c<<endl;




}

Measured memory_bytes: 36608
#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;

int main(void){
	double x1, y1, x2, y2;
	cin >>x1 >>y1 >>x2 >>y2;
	cout <<fixed <<setprecision(10) <<sqrt(pow(x1-x2, 2)+pow(y1-y2, 2)) <<endl;
    return 0;
}

Measured memory_bytes: 1284
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int h, w; 
int n, m;
int main(){
    string s;
    cin >> s;
    cin >> m;
    n = s.size();
    for(int i=0; i<n; i+=m){
        cout << s[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)
odd = ['R', 'U', 'D']
even = ['L', 'U', 'D']

for i in range(0, N, 2):
    if S[i] not in odd:
        print('No')
        exit()

for i in range(1, N, 2):
    if S[i] not in even:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(a&&c){
        c-=b;
        if(c<=0){
            cout<<"Yes"<<endl;
            return 0;
        }
        a-=d;
        if(a<=0){
            cout<<"No"<<endl;
            return 0;
        }

    }
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin >> a;
    vector<string> b(a);
    vector<int> c(a);
    for(int i = 0; i < a; i++){
        cin >> b[i] >> c[i];
    }
    string d;
    cin >> d;
    int j = 0;
    for(int i = 0; i < a; i++){
        if(b[i] == d)
        {
            j = i;
            break;
        }
    }
    int sum = 0;
    for(int i = j + 1; i < a; i++){
        sum += c[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int frogBU(int h[],int n)
{
    int dp[n+1]={0};
    dp[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    return dp[n-1];
}
int main()
{
    int n;
    cin>>n;
    int h[n+2];
    for(int i=0;i<n;i++)
        cin>>h[i];
    cout<<frogBU(h,n);
}


Measured memory_bytes: 4364
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
const int INF = 1e9;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v(n+2,0);
    rep(i,n) cin >> v[i+1]; 
    int ans = -INF;
    for(int i = 0; i <= n; i++){
        for(int j = i+1; j <= n+1; j++){
            int c = i+n+1-j;
            if(c > k) continue;
            int value = 0;
            vector<int> a;
            for(int k = 1; k <= i; k++) {
                a.push_back(v[k]);
                value += v[k];
            }
            for(int k = n; k >= j; k--){
                a.push_back(v[k]);
                value += v[k];
            }
            sort(a.begin(),a.end());
            rep(i,min(k-c,(int)a.size())) {
                if(a[i] < 0) value -= a[i];
            }
            ans = max(ans,value);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args) {
        int N = int.Parse(Console.ReadLine());
        string[] v = Console.ReadLine().Split(' ');

        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = int.Parse(v[i]);
        }

        int cnt = bubbleSort(A);
        for (int i = 0; i < A.Length; i++) {
            if (i > 0) { Console.Write(" "); }
            Console.Write(A[i]);
        }
        Console.WriteLine("");
        Console.WriteLine(cnt);
    }

    static int bubbleSort(int[] A) {
        int cnt = 0;

        int flag = 1;
        while (flag == 1) {
            flag = 0;
            for (int j = A.Length - 1; j >= 1; j--) {
                if (A[j] < A[j - 1]) {
                    int v = A[j - 1];
                    A[j - 1] = A[j];
                    A[j] = v;
                    flag = 1;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}



Measured memory_bytes: 17996
#include<bits/stdc++.h>
using namespace std;
int a,b;

int main(){
  while(1){
    cin>>a>>b;
    if(!a&&!b)break;
    int ans=(1e9);
    for(int i=1;i*i<=a;i++){
      if((a%i))continue;
      for(int j=1;j*j<=b;j++){
	if((b%j))continue;
	vector<int> s;
	s.push_back(i);
	s.push_back(a/i);
	s.push_back(j);
	s.push_back(b/j);
	sort(s.begin(),s.end());
	int sum=0;
	for(int i=1;i<s.size();i++)
	  sum+=(s[i]-s[i-1])*(s[i]-s[i-1]);
	ans=min(ans,sum);
      }
   }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3148
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int N = in.i();
        int M = in.i() * 2;
        boolean[] b = new boolean[N + 1];
        int c = 0;
        for (int i = 0; i < M; i++) {
            int a = in.i();
            if (b[a]) {
                c--;
            } else {
                c++;
            }
            b[a] = !b[a];
        }
        out.println(c == 0 ? "YES" : "NO");
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    int i() {
        char c = next();
        boolean minus = c == '-';
        int n = minus ? 0 : c - '0';
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }
}


Measured memory_bytes: 35272
#include "iostream"
using namespace std;
 
int main(){
 
  int sum=0;
  int H,N,A;
  
  cin >> H >> N;

  for(int i=1; i<=N;i++){
    
    cin >> A;
    
    sum+=A;
    
  }
  
  if(sum>=H)cout << "Yes";
  else cout << "No";

  return 0;
  
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    Scanner scan = new Scanner(System.in);
    int N;
    ArrayList<Integer> H = new ArrayList<>();
    int K;
    int min;

    Main(){
        N = scan.nextInt();
        K = scan.nextInt();

        for(int i = 0; i < N; i++){
            H.add(scan.nextInt());
        }

        System.out.println(minmize(N, K, H));
        /*
        for(int i = 0; i < H.size(); i++){
            System.out.println(H.get(i));
        }*/
    }

    public long minmize(int N, int K, ArrayList<Integer> H){
        long sumhp = 0;
        Collections.sort(H);
        for(int i = 0; i < H.size() - K; i++){
            sumhp += H.get(i);
        }
        return sumhp;

    }


    public static void main(String[] args){
        new Main();
    }
}

Measured memory_bytes: 91980
def f(n):
  if n % 2 == 0:
    return n//2
  else:
    return 3*n + 1

s = int(input())

old = [s]
n = s
for i in range(2, 1000001):
  n = f(n)
  if n in old:
    print(i)
    exit()
  old.append(n)

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    int n;cin>>n;
    ll c,k;cin>>c>>k;
    vector<ll> t(n);
    for(int i=0;i<n;i++) cin>>t[i];
    sort(t.begin(),t.end());
    ll res=1,st=0;
    for(int i=1;i<n;i++){
        if(i>=st+c){
            st=i;
            res++;
            continue;
        }
        if(t[i]>t[st]+k){
            st=i;
            res++;
            continue;
        }
        continue;
    }
    cout<<res<<endl;
}


Measured memory_bytes: 1024
def check(x, y):
    for i in range(6):
        order = [0, 0, 0]
        for j in range(3):
            if {x[j], x[-j-1]} != {y[z[i][j]], y[-z[i][j]-1]}:
                break
            if x[j] == y[z[i][j]]:
                order[j] = 1
                if x[j] == x[-j-1]:
                    order[j] = 2
        else:
            if 2 in order or z[i][3] == sum(order) % 2:
                return True
    return False

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    x[i] = list(map(int, input().split()))
z = [[0, 1, 2, 1], [0, 2, 1, 0], [2, 1, 0, 0], [1, 0, 2, 0], [2, 0, 1, 1], [1, 2, 0, 1]]
different = True
for i in range(n):
    for j in range(i+1, n, 1):
        if check(x[i], x[j]):
            break
    else:
        continue
    print('No')
    break
else:
    print('Yes')

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

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = (int) 1e5 + 10;
int n, a[MAXN];
char S[MAXN];

int main() {
    scanf("%s", S + 1);
    n = strlen(S + 1);

    for (int i = 1; i <= n; ++i) a[i] = S[i] - 48;
    for (int i = n + 1; i >= 1; --i) a[i] ^= a[i - 1];
    if (*max_element(a + 1, a + 1 + n + 1) == 0) {
        printf("%d\n", n);
        return 0;
    }

    int ans = (int) 1e9;
    for (int i = 1; i <= n + 1; ++i) {
        if (a[i] == 1) {
            ans = min(ans, max(i - 1, n + 1 - i));
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 768
N = int(input())
csf = [tuple(map(int, input().split())) for _ in range(N - 1)]

for i in range(N):
    t = 0
    for C, S, F in csf[i:]:
        if t < S:
            t = S + C
        elif t == S or t % F == 0:
            t += C
        else:
            t += F - t % F + C
    print(t)


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	int32 p, m, c;
	cin >> p >> m >> c;
	cout << p+m+c << endl;
}



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

int N, Q;
string S;
int l, r;

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

	int cnt[100005]; memset(cnt, 0, sizeof(cnt));

	for (int i = 1; i < N; i++) {
		cnt[i] = cnt[i-1];
		if (S[i] == 'C' && S[i - 1] == 'A') cnt[i]++;
	}

	for (int i = 0; i < Q; i++) {
		cin >> l >> r;
		l--; r--;
		if (S[l] == 'A' && S[l + 1] == 'C') cout << cnt[r] - cnt[l + 1] + 1 << endl;
		else cout << cnt[r] - cnt[l + 1] << endl;
	}
}

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

int main(void){
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x : a){
		cin >> x;
	}
	sort(a.rbegin(), a.rend());
	int ans = 0;
	for(int i= 0; i < n; ++i){
		if(i%2==0) ans += a[i];
		else ans -= a[i];
	}
	cout << ans << endl;
	return 0;
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v),end()
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;

template<typename A,typename B> inline void chmin(A &a,B b){if(a>b) a=b;}
template<typename A,typename B> inline void chmax(A &a,B b){if(a<b) a=b;}
//-----------------------------------------------------------------------

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

    int n; cin>>n;
    set<string> st;
    REP(i,n){
        string s; cin>>s;
        st.insert(s);
    }
    
    int m; cin>>m;
    bool locked=true;
    REP(i,m){
        string s; cin>>s;
        if(st.count(s)){
            locked=!locked;
            cout<<(locked?"Closed by ":"Opened by ");
        } else{
            cout<<"Unknown ";
        }
        cout<<s<<endl;
    }
        
}

Measured memory_bytes: 3268
require 'pp'

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end

N, M, Q = gets_i_list
abcd_list = []
Q.times do
  abcd_list.push gets_i_list
end

a_max_list = (1..M).to_a
a_list_combi = a_max_list.repeated_combination(N).to_a

d_max_total = 0
a_list_combi.each do |a_list|
  d_total = 0
  abcd_list.each_with_index do |abcd|
    a, b, c, d = abcd
    b_a = a_list[b-1] - a_list[a-1]
    if b_a == c
      d_total += d
    end
  end
  d_max_total = [d_total, d_max_total].max
end

puts d_max_total


Measured memory_bytes: 33228
n = int(input())
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = map(int,input().split())
a.reverse()
b.reverse()
count = 0
for i in range(n):
    if (a[i]+count)%b[i] == 0:
        pass
    elif a[i]+count > b[i]:
        count += (b[i]*(((a[i]+count)//b[i])+1))-(a[i]+count)
    else:
        count += b[i] - (a[i]+count)
print(count)

Measured memory_bytes: 11124
from functools import lru_cache

def pleaseAC(ary):
    v = 0
    for i in ary:
        v += kitaichi(i)
    return v

@lru_cache(maxsize=1001)
def kitaichi(n):
    return sum(range(1,n+1)) / n

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))


    best = 0
    best_val = sum(P[:K])
    tmp = best_val
    for i in range(1, N-K+1):
        prev = P[i-1]
        suc = P[i+K-1]
        tmp = tmp-prev+suc
        if best_val < tmp:
            best_val = tmp
            best = i

    print(pleaseAC(P[best:best+K]))



main()

Measured memory_bytes: 26324
n=int(input())
a=list(map(int,input().split()))
d={}
ans=0
for i in range(n):
    if i+a[i] in d.keys():
        d[i+a[i]]+=1
    else:
        d[i+a[i]]=1
    if i-a[i] in d.keys():
        ans+=d[i-a[i]]
print(ans)




Measured memory_bytes: 40268
fun main(args: Array<String>) {
    readLine()
    val xs = readLine()!!.split(' ').map { it.toLong() }

    var l = -1000000001L
    var r = 1000000001L

    while ((r - l) >= 3) {
        val m0 = (l * 2 + r) / 3
        val m1 = (l + r * 2) / 3

        if (f(xs, m0) < f(xs, m1)) {
            r = m1
        } else {
            l = m0
        }
    }

    println((0..3).map { f(xs, l + it) }.min())
}

private fun f(xs: List<Long>, b: Long): Long {
    return xs.mapIndexed { i, x -> Math.abs(x - (b + i + 1)) }.sum()
}

Measured memory_bytes: 152400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}
 
vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}
 
int main() {
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a,b);
  auto f = factorize(g);
  int ans = f.size() + 1;
  cout << ans << endl;
  return 0;
}


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




























int main() {
    int N;
    cin >> N;
    vector<long long> x(N), y(N), sum(N), sa(N);
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        sum[i] = x[i] + y[i];
        sa[i] = y[i] -x[i];
    }
    sort(sum.begin(), sum.end());
    sort(sa.begin(), sa.end());

    long long result1, result2;
    result1 = sum[N - 1] - sum[0];
    result2 = sa[N - 1] - sa[0];
    long long ans = max(result1, result2);
    cout << ans <<endl;
}

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

typedef struct _Node {
  char value[20];
  struct _Node *left;
  struct _Node *right;
} Node;

Node *root;

void insert_body(Node *r, Node *p)
{
  if (strcmp(r->value, p->value) >= 0) {
    if (r->left == NULL)
      r->left = p;
    else
      insert_body(r->left, p);
  } else {
    if (r->right == NULL)
      r->right = p;
    else
      insert_body(r->right, p);
  }
}

void insert(string str)
{
  Node *p = (Node *)malloc(sizeof(Node));
  strcpy(p->value, str.c_str());
  p->left = NULL;
  p->right = NULL;
  insert_body(root, p);
}

bool find(Node *r, string str)
{ 
  if (r == NULL) return false;
  int cmp = strcmp(r->value, str.c_str());
  if (cmp == 0) return true;
  if (cmp > 0)  return find(r->left, str);
  else          return find(r->right, str);
}

int main()
{
  int n; cin >> n;
  Node rb = { "*", NULL, NULL };
  root = &rb;

  while (n--) {
    string op, str;
    cin >> op >> str;
    if (op[0] == 'i') {
      insert(str);
    } else if (op[0] == 'f') {
      cout << (find(root, str)?"yes":"no") << endl;
    } else {
      cerr << "error: " << op << endl;
    }
  }

  return EXIT_SUCCESS;
}



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

int main() {
  ll n, a, b, i, diff, ans = 0;
  cin >> n >> a >> b;
  vector<ll> x(n);
  for (i = 0; i < n; i++) {
    cin >> x[i];
  }
  for (i = 0; i < n - 1; i++) {
    diff = x[i + 1] - x[i];
    ans += min(diff * a, b);
  }
  cout << ans << "\n";
  return 0;
}

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

#define max 100

//qsort(d, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}

int main()
{
    int i, j, k, num, flag=0, ans=0;
    char s[max];
    
    scanf("%s", s);
    
    num=strlen(s);
   
    //条件1
    for (i=0; i<num; i++) {
        if(s[i]==s[num-1-i])
            flag++;
    }
    
    if(flag==num)
        ans++;
    
    flag=0;
    //条件2
    j=(num-1)/2;
    for(i=0; i<j; i++){
        if(s[i]==s[j-1-i])
            flag++;
    }
    
    if(flag==j-0)
        ans++;
    
    flag=0;
    
    //printf("%d,", flag);
    
    //条件3
    j=(num+3)/2;
    for(i=j-1; i<num; i++){
        if(s[i]==s[num-1-i])
            flag++;
    }
    
    if(flag==num-j+1)
        ans++;
   
    //printf("%d", flag);
    
    if(ans==3)
        printf("Yes");
    else
        printf("No");
    
    return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define rep(i, n) for(int i=0;i<n;i++)
typedef long long ll;
#define intv vector<v>
#define llv vector<long long>
#define intvv vector<vector<int>>
#define llvv vector<vector<long long>>
using namespace std;


int main(){
    int n, k;
    cin >> n >> k;
    double ans = 0;
    for(int i=1;i<=n;i++){
        double temp = 1.0 / n;
        int j = i;
        while(j < k){
            j *= 2;
            temp /= 2;
        }
        ans += temp;
    }
    printf("%.12f\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, i, j, v;
    long long wt, w;
    cin >> n >> w;
    vector<long long> dp(100000, 1000000000000);
    for(i = 0; i < n; ++i) {
        cin >> wt >> v;
        for(j = 99999; j >= 0; --j)
            dp[j] = min((j>=v ? dp[j-v] : 0) + wt, dp[j]);
    }
    for(i = 99999; i>=0 && dp[i]>w; --i);
    cout << i+1;
    return 0;
}

Measured memory_bytes: 4028
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() (int, error) {
	return strconv.Atoi(nextString())
}

func call(n int) {
	i := 1
	x := i

	mode := "CHECK_NUM"

	for {
		// fmt.Println(mode, x)
		// CHECK_NUM
		if mode == "CHECK_NUM" {
			mode = "INCLUDE3"
			x = i
			if x%3 == 0 {
				fmt.Print(" ", i)
				mode = "END_CHECK_NUM"
			}
		}

		// INCLUDE3
		if mode == "INCLUDE3" {
			if x%10 == 3 {
				fmt.Print(" ", i)
				mode = "END_CHECK_NUM"
			}
			if mode == "INCLUDE3" {
				x /= 10
				if x > 0 {
					mode = "INCLUDE3"
				} else {
					mode = "END_CHECK_NUM"
				}
			}
		}

		// END_CHECK_NUM
		if mode == "END_CHECK_NUM" {
			i++
			if i <= n {
				mode = "CHECK_NUM"
			} else {
				fmt.Println("")
				break
			}
		}
	}

}

func main() {
	scanner.Split(bufio.ScanWords)
	n, _ := nextInt()
	call(n)
}



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

const int N = 1e5+7;
int a[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    long long ans = 0;
    for (int i=1; i<=n; i++) {
        cin>>a[i];
        if (a[i] == 0)  continue;
        else if (a[i]%2) ans += a[i]/2, a[i] = 1;
        else        ans += a[i]/2-1, a[i] = 2;
    }

    for (int i=1; i<=n; i++) {
        if (a[i] == 0)  continue;
        if (a[i] == 2)  ans++;
        else if (a[i] == 1 && a[i+1])   ans++, a[i+1]--;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 640