akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define MAX 100
#define NOT -1
#define FND -2
#define CMP -3

int n, route;
int G[MAX+1][MAX+1];
int d[MAX+1][2];
int p[MAX+1];

void make_graph(void){
  scanf("%d", &n);

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      scanf("%d", &G[i][j]);
      if(G[i][j] == -1) G[i][j]=INT_MAX;
    }
  }
}

void prim(void){
  int u, m, mst=0;

  for(int i=0; i<n; i++){
    d[i][0]=INT_MAX;
    d[i][1]=0;
    p[i]=-1;
  }
  
  d[0][0]=0; d[0][1]=FND;
  
  while(true){
    u=-1;
    m=INT_MAX;
    
    for(int i=0; i<n; i++){
      if(d[i][0] < m && d[i][1] != CMP){
	u=i; m=d[i][0];
      }
    }

    if(u == -1) break;
    d[u][1]=CMP;

    for(int i=0; i<n; i++){
      if(d[i][1] != CMP && G[u][i] != INT_MAX){
	if(d[i][0] > G[u][i]){
	  d[i][0]=G[u][i];
	  d[i][1]=FND;
	  p[i]=u;
	}
      }
    }

  }

  for(int i=0; i<n; i++){
    if(p[i] != -1) mst+=G[i][p[i]];
  }

  printf("%d\n", mst);
}

int main(void){
  make_graph();
  prim();
  
  return 0;
}



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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

#define N 200001
ll ans = 0;
ll a[N];
int choose, n;
unordered_map<int, unordered_map<int, ll>> dp;
unordered_map<int, unordered_map<int, bool>> can_find;

bool haveProcessed(int cur, int more) {
	return can_find.find(cur) != can_find.end() && can_find[cur].find(more) != can_find[cur].end();
}

bool calc(int cur, int more, ll *max_val) {

	if (more == 0) {
		*max_val = 0;
		return true;
	}

	int rest_arr_size = n - cur;

	if (more > (rest_arr_size - rest_arr_size/2))
		return false;

	if (cur >= n) {
		return false;
	}

	if (haveProcessed(cur, more)) {
		*max_val = dp[cur][more];
		return can_find[cur][more];
	}


	ll val_with_rest, val_with = LONG_MIN;
	ll val_without_rest, val_without = LONG_MIN;

	bool can_find_with = calc(cur + 2, more - 1, &val_with_rest);
	if (can_find_with) {
		val_with = a[cur] + val_with_rest;
	}

	bool can_find_without = calc(cur + 1, more, &val_without_rest);
	if (can_find_without) {
		val_without = val_without_rest;
	}

	*max_val = max(val_with, val_without);

	can_find[cur][more] = can_find_with || can_find_without;
	dp[cur][more] = *max_val;

	return can_find[cur][more];
}

int main() {

	IOS

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	choose = n/2;

	ll max_val = 0;
	calc(0, choose, &max_val);

	cout << max_val;

	return 0;
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left!=NIL) x=x->left;
  return x;

}

Node treeMaximum(Node x){
  while(x->right!=NIL) x=x->right;
  return x;

}

Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;

  if(k<u->key) return treeSearch(u->left,k);
  else return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL) return treeMinimum(x->right);
  
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
    return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right == NIL) y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent = y->parent;

  if(y->parent==NIL) root=x;
  else if(y==y->parent->left) y->parent->left = x;
  else y->parent->right = x;

  if(y!=z) z->key=y->key;

}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while (x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL) root =z;
  else if(z->key<y->key) y->left=z;
  else (y->right = z);
}

void inorder(Node u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 24040
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

template <typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n = 0) : n(n), d(n + 1) {}
  void add(int i, T x = 1) {
    for(i++; i <= n; i += i & -i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for(i++; i; i -= i & -i) {
      x += d[i];
    }
    return x;
  }
};

int main() {
  ll n, k;
  cin >> n >> k;
  BIT<ll> b(n);
  vl a(n);
  rep(i, n) cin >> a[i];
  vl sa = a, sb = a;
  sort(all(sa));
  sort(all(sb));
  sa.erase(unique(all(sa)), sa.end());
  ll t = 0, s = 0;
  rep(i, n) {
    ll in = lower_bound(all(sa), a[i]) - sa.begin();
    t += b.sum(n - 1) - b.sum(in);
    b.add(in);
    ll in2 = lower_bound(all(sb), a[i]) - sb.begin();
    s += in2;
  }
  mint ans = mint(t) * k + mint(s) * k * (k - 1) / 2;
  cout << ans << endl;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n,m;
  cin >> n >> m;
  mat a(n,vec(m));
  for(ll i=0;i<n;i++) for(ll j=0;j<m;j++) cin >> a[i][j];
  vec num(n);
  set<ll> check;
  ll ans=inf;
  for(ll i=0;i<m;i++) {
    map<ll,ll> cnt;
    for(ll j=0;j<n;j++) {
      while(check.count(a[j][num[j]])) {
        num[j]++;
      }
      cnt[a[j][num[j]]]++;
    }
    ll tans=0,id;
    for(ll j=1;j<=m;j++) {
      if(tans<cnt[j]) {
        tans=cnt[j];
        id=j;
      }
    }
    check.insert(id);
    ans=min(tans,ans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1e9+7;

int main(){
    int A,B,K,cnt=0;
    cin >> A >> B >> K;
    vector<int> l;
    for(int i=1; i<=100; i++){
        if(A%i==0 && B%i==0){
            l.push_back(i);
        }
    }
    cout << l[l.size()-K];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
using LP=pair<ll,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N;
    cin>>N;
    vector<vector<int>> a(N,vector<int>(N));
    rep(i,N)rep(j,N){
        cin>>a.at(i).at(j);
    }
    ll MX=1;
    rep(i,N)MX*=2;
    vector<vector<ll>> dp(N+1,vector<ll>(MX));
    dp[0][0]=1;
    vector<vector<ll>> flist(N+1,vector<ll>(0));
    rep(i,MX){
        int cnt=0;
        rep(j,N){
            if(i&1ll<<j)cnt++;
        }
        flist.at(cnt).pb(i);
    }
    rep(male,N){
        for(ll S:flist.at(male)){
            rep(female,N){
                if(S & 1ll<<female)continue;
                if(a.at(male).at(female)==0)continue;
                dp[male+1][S|1ll<<female]+=dp[male][S];
                dp[male+1][S|1ll<<female]%=MOD;
            }
        }
    }
    cout<<dp[N][MX-1]<<endl;
}

Measured memory_bytes: 389012
x1, y1, x2, y2 = map(int, input().split())
d = (x2 - x1, y2 - y1)

d = (-d[1], d[0])
x3, y3 = x2 + d[0], y2 + d[1]

d = (-d[1], d[0])
x4, y4 = x3 + d[0], y3 + d[1]

print(x3, y3, x4, y4)


Measured memory_bytes: 3060
n,b,f[50001];main(a){for(;++a<50001;)if(!f[a])for(b=a;b+a<50001;)f[b+=a]=1;for(;~scanf("%d",&n);n&&printf("%d\n",b))for(b=0,a=1;a++<n/2;)f[a]+f[n-a]||b++;}

Measured memory_bytes: 596
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;

const double EPS = 1e-9;

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

	string S, T;
	cin >> S >> T;
	int Q;
	cin >> Q;

	vector<vector<int>> IMOS(2);
	IMOS[0].push_back(0), IMOS[1].push_back(0);

	rep(i, 0, SZ(S))
	{
		IMOS[0].push_back(IMOS[0][i]);
		if (S[i] == 'A')IMOS[0][i + 1]++;
		else IMOS[0][i + 1] += 2;
	}
	rep(i, 0, SZ(T))
	{
		IMOS[1].push_back(IMOS[1][i]);
		if (T[i] == 'A')IMOS[1][i + 1]++;
		else IMOS[1][i + 1] += 2;
	}

	int a, b, c, d;
	rep(i, 0, Q)
	{
		cin >> a >> b >> c >> d;
		a--, c--;
		if ((IMOS[0][b] - IMOS[0][a]) % 3 == (IMOS[1][d] - IMOS[1][c]) % 3)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 5852
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using Graph = std::vector<std::vector<int>>;
using WGraph = std::vector<std::vector<std::pair<int, long long>>>;
using ll = long long;
using namespace std;

int main() {
    int n = 1e5;
    std::vector<bool> is_prime(n+1, true);
    is_prime.at(0) = is_prime.at(1) = false;
    for (long long i=2; i<=n; i++) {
        if (is_prime.at(i)) {
            for (long long j=2*i; j<=n; j+=i) {
                is_prime.at(j) = false;
            }
        }
    }
    vector<int> cnt(n+1);
    for (int i=1; i<n+1; i++) {
        if (is_prime.at(i) && is_prime.at((i+1)/2)) {
            cnt.at(i) = cnt.at(i-1) + 1;
        } else {
            cnt.at(i) = cnt.at(i-1);
        }
    }
    int q = 0, l = 0, r = 0;
    cin >> q;
    vector<int> ans(q);
    for (int i=0; i<q; i++) {
        cin >> l >> r;
        ans.at(i) = cnt.at(r) - cnt.at(l-1);
    }
    for (int x : ans) {
        cout << x << endl;
    }
    return 0;
}
 

Measured memory_bytes: 1408
#include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main() {
	int x, y, z;
	cin >> x >> y >> z;
	if(x && y && !z || !x && !y && z) cout << "Open" << endl;
	else cout << "Close" << endl;
}

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

int main(){
    int N;
    cin >> N;
    if(N<10){
        cout << N << endl;
    }else if(N<100){
        cout << 9 << endl;
    }else if(N<1000){
        cout << N-90 << endl;
    }else if(N<10000){
        cout << 909 << endl;
    }else if(N<100000){
        cout << N-9090 << endl;
    }else{
        cout << 90909 << endl;
    }
}

Measured memory_bytes: 256
from collections import deque
Sa=deque(list(input()))
Sb=deque(list(input()))
Sc=deque(list(input()))
win="A"
play=Sa.popleft()
while True:
    if play=="a":
        if len(Sa)==0:
            break
        else:
            play=Sa.popleft()
    elif play=="b":
        if len(Sb)==0:
            win="B"
            break
        else:
            play=Sb.popleft()
    else:
        if len(Sc)==0:
            win="C"
            break
        else:
            play=Sc.popleft()
    
print(win)    
    

Measured memory_bytes: 3316
N,X = map(int,input().split())
all_x = list(map(int,input().split()))

def gcd(a,b):
  while(b>0):
    a,b = b,a%b
  return a

for i in range(N):
  tmp = abs(X-all_x[i])
  if(i == 0):
    ans = tmp
  else:
    ans = gcd(ans,tmp)
print(ans)  

Measured memory_bytes: 15020
#include <iostream>
#include <set>
#include <string>
using namespace std;
string rev(string str){
	for(int k=0;k<str.length()/2;k++){
		char temp;
		temp=str[k];
		str[k]=str[str.length()-1-k];
		str[str.length()-1-k]=temp;
	}
	return str;
}
int main(){
	int m;
	cin>>m;
	for(int i=0;i<m;i++){
		string str,s,t,u;
		set<string> train;
		cin>>str;
		for(int j=0;j<str.length();j++){
			s=str.substr(0,j);
			t=str.substr(j);
			u=t+s;
			train.insert(u);
			u=rev(s)+t;
			train.insert(u);
			u=t+rev(s);
			train.insert(u);
			u=s+rev(t);
			train.insert(u);
			u=rev(t)+s;
			train.insert(u);
			u=rev(s)+rev(t);
			train.insert(u);
			u=rev(t)+rev(s);
			train.insert(u);
		}
		cout<<train.size()<<endl;
	}
	return 0;
}

Measured memory_bytes: 1296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
using P = pair <int, int>;
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) {return  b ? gcd(b,a%b) : a;}
const long long INF = 1LL << 60;
const int mod = 1000000007;
const double PI = acos(-1.0);
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


main(){
    int n,m,x;
    cin >> n >> m>>x;
    int ans = 100100000;
    vector<vector<int>>a(n,vector<int>(m));
    vector<int>c(n);
    rep(i,n){
         cin >> c[i];
         rep(j,m){
              cin >> a[i][j];
         }
    } 
    for(int bit = 0 ;bit<(1<<n);++bit){
         bool ok = true;
         int cnt = 0;
         vector<int>A(m,0);
         rep(i,n){
              if(bit&(1<<i)){
                   cnt+=c[i];
                   rep(j,m){
                        A[j]+=a[i][j];
                   }
              }
         }
         rep(i,m){
              if(A[i]<x)ok = false;
         }
         if(ok) ans = min (ans,cnt);
    }
    if(ans==100100000) cout << -1 <<endl;
    else cout << ans <<endl;
}

Measured memory_bytes: 3544
#include <stdio.h>

int main (int argc,char **argv)
{
	int a,b,c;

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

	if ((c >= a) && (c <= b))
	{
		printf("Yes\n");
	}

	else 
	{
		printf("No\n");
	}

	return 0;
}

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  sort(v.begin(), v.end());
  vector<int> ans(n + 1);
  map<int, int> mp;
  for (int i = 0; i < n; i++) mp[v[i]]++;
  map<int, vector<int>> mpinv;
  for (auto &pr : mp) {
    mpinv[pr.second].push_back(pr.first);
  }
  vector<int> par(n + 1);
  int rest = 0;
  for (int i = 1; i <= n; i++) par[i] = n / i;
  int j = 1;
  for (int part = 1; part <= n; part++) {
    int base = mp.size() + rest / part;
    ans[base] = max(ans[base], part);
    if (mpinv.find(part) != mpinv.end()) {
      for (auto &k : mpinv[part]) {
        auto it = mp.find(k);
        rest += it->second;
        mp.erase(it);
      }
    }
  }
  for (int i = n - 1; i > 0; i--) ans[i] = max(ans[i], ans[i + 1]);

  for (int i = 1; i <= n; i++) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 19056
# include"stdio.h"

int main(){
    int n,sum=0;
    scanf("%d",&n);
    int t[n];
    for(int i=0;i<n;i++)
        scanf("%d",&t[i]);
    for(int i=0;i<n;i++)
        sum+=t[i];
    int m;
    scanf("%d",&m);
    int d[m][2];
    for(int i=0;i<m;i++)
        scanf("%d %d",&d[i][0],&d[i][1]);
    for(int i=0;i<m;i++){
        printf("%d\n",sum+d[i][1]-t[d[i][0]-1]);
    }
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

void b_maximum_sum(void) {
	int a[3];
	int k;
	int max = 0;
	int sum = 0;
	cin >> a[0] >> a[1] >> a[2] >> k;

	sort(a, a + 3, greater<int>());

	for (int i = 1; i <= k; i++) {
		a[0] = a[0] << 1;
	}

	cout << a[0] + a[1] + a[2] << endl;
}

int main()
{
	b_maximum_sum();
    return 0;
}

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



Measured memory_bytes: 2588
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
int main(){
  int N;  cin>>N;
  vector<int> a(N);
  rep(i,0,N) cin>>a[i];
  int M;  cin>>M;
  vector<int> b(M), c(M);
  rep(i,0,M) cin>>b[i]>>c[i];
  map<ll,ll> ma;
  ll sum=0;
  rep(i,0,N){
    ma[a[i]]++;
    sum += a[i];
  }
  rep(i,0,M){
    int bf=b[i];
    int af=c[i];
    ll n=ma[bf];
    sum -= n*bf;
    sum += n*af;
    ma[bf]=0;
    ma[af] += n;
    cout<<sum<<endl;
  }
  return 0;
}


Measured memory_bytes: 10336
#include<stdio.h>
int main(){
	int n,m,i,a,b,ans;
	scanf("%d %d",&n,&m);
	int h[n+1];
	int count[n+1];
	for(i=1;i<=n;i++){
	scanf("%d",&h[i]);
	count[i]=1;
	}
	for(i=1;i<=m;i++){
		scanf("%d %d",&a,&b);
		if(h[a]>=h[b]){
			count[b]=0;
		}
		if(h[a]<=h[b])
		count[a]=0;
	}
	for(i=1,ans=0;i<=n;i++){
		if(count[i]==1)
		ans++;
	}
	printf("%d",ans);
}


Measured memory_bytes: 2476
S = input()

N = len(S)
# [0:N//2] == [(N+1)//2:N]
A = int(N//2)
B = int((N+1)//2)
flag = True
if S[0:A] == S[B:N][::-1]:
    N = A
    A = int(N // 2)
    B = int((N + 1) // 2)
    if S[0:A] == S[B:N][::-1]:
        print("Yes")
        flag = False

if flag:
    print("No")


Measured memory_bytes: 38256
#include <iostream>

using namespace std;

int main() {
	int n, b, f, r, v;
	int mem[4][3][10] = {0};

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> b >> f >> r >> v;

		mem[b - 1][f - 1][r - 1] += v;
	}

	for (int j = 0; j < 4; j++) {
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 10; l++) {
				cout << " " << mem[j][k][l];
			}
			cout << endl;
		}
		if(j < 3)
			cout << "####################" << endl;
	}
}


Measured memory_bytes: 3124
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

int n;
vi nums;
vi dp;
int mn = 1e8;

int solve(int p) {
	if (dp[p] != -1) return dp[p];
	if (p < mn) return 0;
	
	int ans = 0;
	for (int i: nums) if (i <= p) {
		if (!solve(p-i)) ans = 1;
	}
	
	return dp[p] = ans;
}

int main() {
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int k; cin >> n >> k;
	nums.resize(n); dp.resize(k+1, -1);
	for_(i, 0, n) cin >> nums[i];
	for (int i: nums) mn = min(mn, i);
	
	if (solve(k)) cout << "First";
	else cout << "Second";
	cout << endl;
	

	return 0;
}


Measured memory_bytes: 9804
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <complex>

using namespace std;
using ll = long long;

const int MN = 200200;
vector<int> g[MN];
int sz[MN], rt[MN];
void dfs(int p, int b) {
    sz[p] = 1;
    rt[p] = b;
    for (int d: g[p]) {
        if (d == b) continue;
        dfs(d, p);
        sz[p] += sz[d];
    }
}

vector<int> g2[MN];

bool ispath(int s) {
    if (g2[s].size() >= 2) return false;
    if (g2[s].size() == 0) return true;
    int b = -1;
    int p = s;
    while (true) {        
        for (int d: g2[p]) {
            if (d == b) continue;
            b = p;
            p = d;
            break;
        }
        if (g2[p].size() == 1) return true;
        if (g2[p].size() > 2) return false;        
    }
}

bool solve() {
    int n, u, v;
    cin >> n >> u >> v; u--; v--;
    if (n % 2) return false;
    static int A[MN], B[MN];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        A[i] = a; B[i] = b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(u, -1);
    int st = v;
    while (true) {
        if (sz[st] > n/2) {
            return false;
        }
        if (sz[st] == n/2) {
            break;
        }
        st = rt[st];
    }

    for (int i = 1; i < n; i++) {
        int a = A[i], b = B[i];
        if (rt[b] == a) swap(a, b);
        if (a == st) continue;
        g2[a].push_back(b);
        g2[b].push_back(a);
    }
    return (ispath(u) && ispath(v));
}

int main2() {
    if (solve()) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

int main() {
    static ll eord, enew;
    const int sz = 256*1024*1024;
    static unsigned char *p = (unsigned char*)malloc(sz);
    enew = ((ll)(p+sz-1) & ~0xff);
    __asm__ volatile("mov %%rsp, %0" : "=r"(eord));
    __asm__ volatile("mov %0, %%rsp" : : "r"(enew));
    main2();
    __asm__ volatile("mov %0, %%rsp" : : "r"(eord));
    return 0;
}

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

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// dp[i][j]: i番目の店までで100円以下の小銭の総額がjとなるような買い方の{500円玉の枚数,-購入金額}の最大値
// 遷移は a)500円玉を得られるように買う b)1000円札のみで買って小銭を稼ぐ c)買わない
// bでも500円玉を得られる場合がある
int n, p[100];
pii dp[101][50050];

signed main() {
	while (1) {
		cin >> n;
		if (n==0) break;
		rep(i,n) cin >> p[i];
		rept(i,n) rept(j,50000) dp[i][j] = {-1,0};
		dp[0][0] = {0,0};
		rep(i,n) rept(j,50000) if (dp[i][j].fi!=-1) {
			int g = dp[i][j].fi, u = -dp[i][j].se;
			// 500円玉を得る
			if (j>=(p[i]+500)%1000) chmax(dp[i+1][j-(p[i]+500)%1000], mp(g+1, -(u+p[i])));
			// 1000円札のみ
			if (1<=p[i]%1000 && p[i]%1000<=500) chmax(dp[i+1][j+(500-p[i]%1000)], mp(g+1, -(u+p[i])));
			if (500<p[i]%1000) chmax(dp[i+1][j+(1000-p[i]%1000)], mp(g, -(u+p[i])));
			// 買わない
			chmax(dp[i+1][j], mp(g, -u));
		}
		pii res = mp(0,0);
		rept(i,50000) chmax(res, dp[n][i]);
		cout << res.fi << ' ' << -res.se << ln;
	}
}


Measured memory_bytes: 42584
# 二分探索
import bisect

#################
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

#リストをソート
a=sorted(a)
b=sorted(b)
c=sorted(c)

count=0
#a[i]の個数
for i in range(n):
    a_count = bisect.bisect_left(a, b[i])
    c_count = bisect.bisect_right(c, b[i])
    count+=a_count*(len(c)-c_count)

print(count)


Measured memory_bytes: 29696
// #include <iostream>
// #include <string>
// #include <math.h>
// #include <map>
// #include <vector>
// #include <tuple>
// #include <algorithm>
// #include <queue>
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define vi vector<int>
#define vlli vector<lli>
#define pii pair<int, int>
#define plli pair <lli, lli>
#define F(i,n) for(lli (i)=0;(i)<(n);(i)++)
#define FR(i,n) for(lli (i)=(n)-1;(i)>=0;(i)--)
#define FSG(i,a,b) for(lli (i)=(a);(i)<(b);(i)++)
#define FSGR(i,a,b) for(lli (i)=(b)-1;(i)>=(a);(i)--)
#define VAL(n) cout << n << endl;
#define VALD(n) cout << #n << ": " << n << endl;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
int main(){
  int N;
  cin >> N;
  int p[N];
  int pos = 0;
  int num = 0;
  int cnt = 0;
  string res = "YES";
  F(i, N){
    cin >> p[i];
    if(p[i] != i+1){
      if(cnt == 0){
        pos = i;
        num = p[i];
        cnt++;
      }
      else if(cnt == 1 && i == num-1 && p[i] == pos+1){
        cnt++;
      }
      else{
        res = "NO";
      }
    }
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#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>;

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

bool match(char a, char b) {
    return a == b || a == '?' || b == '?';
}

// mismatch
bool ab[8010], ac[8010], bc[8010];

int main() {
    string a, b, c;
    cin >> a >> b >> c;

    int na = a.size(), nb = b.size(), nc = c.size();
    int w = max({na, nb, nc}) * 2;

    rep(i,na) rep(j,nb) if ( ! match(a[i], b[j])) ab[i-j+w] = true;
    rep(i,na) rep(j,nc) if ( ! match(a[i], c[j])) ac[i-j+w] = true;
    rep(i,nb) rep(j,nc) if ( ! match(b[i], c[j])) bc[i-j+w] = true;

    int mn = INT_MAX;
    for (int i=-w; i<=w; ++i) {
        for (int j=-w; j<=w; ++j) {
            if (ab[i+w] || ac[j+w] || bc[j-i+w]) continue;
            int l = min({0, i, j});
            int r = max({na, i+nb, j+nc});
            mn = min(mn, r-l);
        }
    }
    cout << mn << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define min(a, b) (a > b ? b : a)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) { rep(_, n) cout << a[_] << " "; cout << endl; }
#define outp(a, n) { cout << endl; rep(_, n) cout << a[_].F << " " << a[_].S << endl; }
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)
#define LB(v, n) (int)(lower_bound(all(v), n) - v.begin())
#define UB(v, n) (int)(upper_bound(all(v), n) - v.begin())
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    double ans = 1;
    
    double tmp = 0;
    rep(i, n) tmp += 1.0 / a[i];
    ans /= tmp;
    out(FIX(6) << ans);
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll R,G;
    cin >>R>>G;
    
    cout << G*2-R << endl;


    return 0;
    

}

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

int ex(char x){
  return int(x-'0');
}

int main(){
  string S;
  cin >> S;
  reverse(S.begin(),S.end());
  int N = S.size();
  vector<vector<ll>> A(N,vector<ll>(13,0));
  ll P=1;
  if(S[0]=='?'){
    for(int i=0;i<10;i++){
      A[0][i] = 1;
    }
  }else{
    A[0][ex(S[0])] = 1;
  }
  for(int i=1;i<N;i++){
    P = P * 10 % 13;
    if(S[i]!='?'){
      ll x = ex(S[i])*P%13;
      for(int j=0;j<13;j++){
        A[i][(j+x)%13] = A[i-1][j]%MOD;
      }
    }else{
      for(int j=0;j<13;j++){
        for(int k=0;k<10;k++){
          A[i][(k*P+j)%13] += (A[i-1][j]%MOD);
          A[i][(k*P+j)%13] %= MOD;
        }
      }
    }
    for(int j=0;j<13;j++){
      A[i][j] %= MOD;
    }
  }
  //for(int j=0;j<13;j++){
  //  cout << j << " : ";
  //  for(int i=0;i<N;i++){
  //    cout << A[N-i-1][j] << " , " ;
  //  }
  //  cout << endl;
  //}
  cout << A[N-1][5]%MOD << endl;
}

Measured memory_bytes: 13696
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
        long v = sc.nextLong();
        long b = sc.nextLong();
        long w = sc.nextLong();
        long t = sc.nextLong();
        String ans = "NO";
        if(a < b){
            long oni = v * t + a;
        	long nige = w * t + b;
        	if(oni >= nige){
            	ans = "YES";
            }
        }else{
            long oni = a - v * t;
        	long nige = b - w * t;
        	if(oni <= nige){
            	ans = "YES";
            }
        }
        System.out.println(ans);
    }
} 

Measured memory_bytes: 35588
n=int(input())
lst=list(map(int,input().split()))
if n%2==0:
    cnt=[0]*n
    for i in range(n):
        p=lst[i]
        if p%2==0:
            print(0)
            exit()
        cnt[p]+=1
        if cnt[p]>=3:
            print(0)
            exit()
    print(pow(2,n//2,10**9+7))
else:
    cnt=[0]*n
    for i in range(n):
        p=lst[i]
        if p%2==1:
            print(0)
            exit()
        cnt[p]+=1
        if p==0:
            if cnt[0]>=2:
                print(0)
                exit()
        else:
            if cnt[p]>=3:
                print(0)
                exit()
    print(pow(2,n//2,10**9+7))

Measured memory_bytes: 83252
#include <stdio.h>

int roundUp(int x){
    if(x%1000!=0) return x=x-(x%1000)+1000;
    else return x;
}

int main(void){
    int n;
    int x=100000;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        x*=1.05;
        x=roundUp(x);
    }
    printf("%d\n",x);
    return 0;
}


Measured memory_bytes: 2112
public class Main {
	public static void main(String[] args) {

		final int N = new java.util.Scanner(System.in).nextInt();
		double floor = N / 1.08;
		double ceil = (N+1) / 1.08;

		int initialNum = (int) floor;

		while(true) {
			if(floor <= initialNum && initialNum < ceil) {
				System.out.println(initialNum);
				break;
			}
			initialNum++;
			if(initialNum >= ceil) {
				System.out.println(":(");
				break;
			}
		}


	}
}


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

const int mod=998244353;
const int MAXN=400010;
using ll = long long;
ll popsum[MAXN];

using PII = pair<int,int>;
using PIII = pair<PII,int>;
set<PIII> st;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    popsum[0] = 0;
    ll po10 = 0;
    for (int i=1;i<=n;i++) {
        if (!po10) {
            po10=1;
        } else {
            po10=po10*10%mod;
        }
        popsum[i]=(popsum[i-1]+po10)%mod;
    }
    ll ans=popsum[n];
    st.insert({{1,n},1});
    st.insert({{n+1,n+1},-1});
    queue<PIII> q;
    for (int i=1;i<=m;i++) {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        l = n+1-l;
        r = n+1-r;
        swap(l,r);
        PIII p{{l,r},x};
        auto it = st.upper_bound(p);
        if (it->first.first > l) {
            --it;
        }
        int xb = it->second;
        int lb = it->first.first;
        int rb = it->first.second;
        while (lb <= r) {
            // printf("%d %d %d\n",lb,rb,xb);
            int low = max(l,lb);
            int high = min(r,rb);
            ans+=(popsum[high]-popsum[low-1]+mod)%mod*((ll)x-xb+mod)%mod;
            ans%=mod;
            it = st.erase(it);
            if (lb<=l-1) {
                q.push({{lb,l-1},xb});
            }
            if (r+1<=rb) {
                q.push({{r+1,rb},xb});
            }
            if (it==st.end()) {
                break;
            }
            xb = it->second;
            lb = it->first.first;
            rb = it->first.second;
        }
        while (!q.empty()) {
            st.insert(q.front());
            q.pop();
        }
        st.insert(p);
        printf("%lld\n",ans);
    }
    return 0;
}

Measured memory_bytes: 17852
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;

int main() {
	ll i, j;
	int A, B;
	cin >> A >> B;
	A--;
	B--;
	int ans = B / A;
	if (B % A != 0)
		ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define scd second
#define fst first
#define pb push_back
#define mkp make_pair
#define all(x) x.begin(), x.end()
#define VT(T) vector<T>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
typedef vector<ll> vlong;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vint> vvint;
typedef vector<vlong> vvlong;
typedef list<int> lint;
typedef list<ll> llong;
typedef list<pii> lpii;
typedef list<pll> lpll;
typedef list<lint> llint;
typedef list<llong> lllong;
 
ll const LINF=numeric_limits<long long int>::max();
int const INF=numeric_limits<int>::max();
 
ll gcd(ll a, ll b){
	return b ? gcd(b,a%b) : a;
}
 
ll pow_mod(ll a, ll e, ll m){
	ll res=1;
	while(e){
		if(e&1) res=res*a%m;
		a=a*a%m;
		e>>=1;
	}
	return res;
}
 
ll inv_mod(ll b, ll m){
	b%=m;
	ll x=0, y=1, r, q, a=m;
	while(b){
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		r=x;
		x=y;
		y=r-q*y;
	}
	x+=m;
	return x%m;
}

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

	int n;
	cin>>n;
	ll fact=0, mod=1e9+7;
	unordered_map<int,int> pcnt;
	while(n--){
		int a;
		cin>>a;
		fact+=inv_mod(a, mod);
		for(int i=2; i*i<=a; i++){
			int cnt=0;
			while(a%i==0){
				cnt++;
				a/=i;
			}
			pcnt[i]=max(pcnt[i],cnt);
		}
		pcnt[a]=max(pcnt[a],1);
	}
	fact%=mod;
	ll ans=1;
	for(auto x : pcnt){
		ans=ans*pow_mod(x.fst,x.scd,mod)%mod;
	}
	cout<<ans*fact%mod<<endl;
}

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

int main() {
    long long a, b, c, d;
	cin >> a >> b >> c >> d;
	long long x=a*c;
	long long y=a*d;
	long long z=b*c;
	long long w=b*d;
	long long ans, ans2;
	ans=max(x, y);
	ans2=max(z, w);
	ans=max(ans, ans2);
	cout << ans << endl;
}


Measured memory_bytes: 3620
#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() {
  int n;
  cin >> n;
  vector<string> s(10);
  s[0] = "pon";
  s[1] = "pon";
  s[2] = "hon";
  s[3] = "bon";
  s[4] = "hon";
  s[5] = "hon";
  s[6] = "pon";
  s[7] = "hon";
  s[8] = "pon";
  s[9] = "hon";
  cout << s[n % 10] << endl;
  return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  return 0;

}

Node treeMaximum(Node x){
  return 0;

}

Node treeSearch(Node u, int k){
  return 0;

}

Node treeSuccessor(Node x){

  return 0;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  return ;

}

void insert(int k){
  Node y=NIL;
  Node x=root;
  Node z;

  z= malloc(sizeof(struct node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL){
    root=z;
  }
  else if(z->key < y->key){
    y->left=z;
  }
  else{
    y->right=z;
  }
}






void inorder(Node u){
  if(u->key==NIL) return;

  if(u->left!=NIL){ //<-ifがないとせぐる
    inorder(u->left);
  }
  printf(" %d",u->key);
  if(u->right!=NIL){ //<-ifがないとせぐる
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u->key==NIL) return;
  printf(" %d",u->key);
  
  if(u->left != NIL){ //<-ifがないとせぐる
    preorder(u->left);
    }
  
    if(u->right != NIL){ //<-ifがないとせぐる
    preorder(u->right);
    }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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

int main() {
  int H, W; cin >> H >> W;
  string S[H];
  for (int i = 0; i < H; i++) cin >> S[i];
  
  int dp[H][W];
  for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) dp[i][j] = 1000000;
  if (S[0][0] == '#') dp[0][0] = 1;
  else dp[0][0] = 0;
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      if (i == 0 && j == 0) continue;
      if (i == 0) {
        if (S[i][j] == '#' && S[i][j - 1] == '.') dp[i][j] = dp[i][j - 1] + 1;
        else dp[i][j] = dp[i][j - 1];
      }
      else if (j == 0) {
        if (S[i][j] == '#' && S[i - 1][j] == '.') dp[i][j] = dp[i - 1][j] + 1;
        else dp[i][j] = dp[i - 1][j];
      }
      else {
        if (S[i][j] == '#' && S[i - 1][j] == '.') dp[i][j] = dp[i - 1][j] + 1;
        else dp[i][j] = dp[i - 1][j];
        if (S[i][j] == '#' && S[i][j - 1] == '.') dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
        else dp[i][j] = min(dp[i][j], dp[i][j - 1]);
      }
    }
  }
  cout << dp[H - 1][W - 1] << endl;
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <queue>
using namespace std;

int M;
long long K;
long long b[1<<18];

int main() {
    cin >> M >> K;
    if (M == 0) {
        if (K == 0) cout << 0 << " " << 0 << endl;
        else cout << -1 << endl;
    } else if (M == 1) {
        if (K == 0) cout << 0 << " " << 0 << " " << 1 << " " << 1 << endl;
        else cout << -1 << endl;
    } else if (K >= 1<<M) {
        cout << -1 << endl;
    } else {
        long long cnt = 0;
        for (int i=0; i<(1<<M); ++i) {
            if (K == i) continue;
            else {
                b[cnt] = i;
                ++cnt;
            }
        }
        for (int i=0; i<(1<<M)-1; ++i) cout << b[i] << " ";
        cout << K << " ";
        for (int i=(1<<M)-2; i>=0; --i) cout << b[i] << " ";
        cout << K << endl;
    }

    return 0;
}

Measured memory_bytes: 2816
N,Y=map(int,input().split())
flag=False
for i in range(0,N+1):
    for j in range(0,N+1-i):
        k=N-i-j
        if i*10000+5000*j+k*1000==Y:
            flag=True
            break
    if flag:
         break

if flag:
    print(str(i)+' '+str(j)+' '+str(k))
else:
    print('-1 -1 -1')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using ll = long long;
int main()
{
	int n;
    cin >> n;
    
    int arr[n];
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    
    ll sum = 0;
    for(int i = 1; i < n; i++)
    {
        if(arr[i] < arr[i - 1])
        {
            sum += (arr[i - 1] - arr[i]) * 1LL;
            arr[i] = arr[i - 1];
        }
    }
    
    cout << sum << endl;
    
	return 0;
}

Measured memory_bytes: 4328
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 30
#define INFTY (1<<21)
int main(){
	int a1, b1, c1, d1, x1, x2, y2, y1, n, m; 
	int dai[MAX][MAX];
	char v;
	for (int i = 0;i<MAX;i++){
		for(int l=0;l<MAX;l++){
			dai[i][l] = INFTY;
		}
	}
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> a1 >> v >> b1 >> v >> c1 >> v >>  d1;
		dai[a1-1][b1-1] = c1;
		dai[b1-1][a1-1] = d1;
	}
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			for (int k = 0; k < m; k++){
				dai[j][k] = min(dai[j][k], dai[j][i] + dai[i][k]);
			}
		}
	}
	cin >> x1 >> v >> x2 >> v >> y1 >> v >> y2;
	cout << y1 - (y2 + dai[x1-1][x2-1]+dai[x2-1][x1-1]) << endl;
	return 0;
}

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

int a[100009];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	long long ans = 0;
	for (int i = 0; i < n - 1; i++) {
		ans += 1LL * a[i] / 2;
		if (a[i] % 2 == 1 && a[i + 1] > 0) {
			ans++; a[i + 1]--;
		}
	}
	ans += 1LL * a[n - 1] / 2;
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <assert.h>
#include <cstdio>

// #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;

inline bool chmin(ll &a, ll b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

inline bool chmax(ll &a, ll b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

//桁数取得
template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}
//整数乗
ll llpow(ll a, ll n)
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        ll rep = a;
        for (ll i = 1; i < n; i++)
        {
            rep *= a;
        }
        return rep;
    }
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

template <typename T>
T amarinasi(T a, T b)
{
    if (a % b == 0)
    {
        return a / b;
    }
    else if (a % b > 0)
    {
        return a / b + 1;
    }
    else
    {
        return a / b - 1;
    }
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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

int main()
{
    ll a, b;
    cin >> a >> b;
    cout << a * b << endl;
}

Measured memory_bytes: 3584