akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  ll n,k;
  cin >> n >> k;
  n++;
  ll ans=0;
  for(ll i=k; i<=n; i++){
    ll minsom = (1+i)*i/2;
    ll maxsom = (2*n-i+1)*i/2;
    ans += maxsom - minsom +1;
    if(ans >= 1000000007) ans%=1000000007;
  }
  cout << ans << endl;
}


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

int main()
{
	int A, B, C;

	cin >> A >> B >> C;

	if( C >= A && C <= B ) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


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

using namespace std;

int log(int n, int b) {
    if (n < b)
        return 1;
    return 1 + log(n / b, b);
}

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

    int n, b;
    cin >> n >> b;
    cout << log(n, b) << '\n';

    return 0;
}

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

int main() {
  int n,q,l,r;
  string st;
  cin >> n >> q >> st;
  vector<int> s(n+1,0);
  for(int i=0;i<n;i++) s[i+1] = s[i]+(st[i]=='A' && st[i+1]=='C');
  for(int i=0;i<q;i++){
    cin >> l >> r;l--;r--;
    cout << s[r] - s[l] << endl;
  }
}


Measured memory_bytes: 1408
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

char table[20][20];
	int W,H;

void dfs(int x,int y){
	if(table[x][y]!= '#')
		table[x][y]='#';
	int dx[4]={1,0,-1,0};
	int dy[4]={0,1,0,-1};
	rep(i,4)
		if(0<=x+dx[i]&&x+dx[i]<W&&0<=y+dy[i]&&y+dy[i]<H&&table[x+dx[i]][y+dy[i]]!='#')
			dfs(x+dx[i],y+dy[i]);
	return ;
}


int main(void){
	while(cin >> W >> H,W|H){
		int pre=0,sx,sy;
		rep(y,H){
			rep(x,W){
				cin >> table[x][y];
				if(table[x][y]=='#')
					pre++;
				if(table[x][y]=='@')
					sx=x,sy=y;
			}
		}
		dfs(sx,sy);
		int post=0;
		rep(y,H)
			rep(x,W)
				if(table[x][y]=='#')
					post++;
		cout << post-pre << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

const int N = 2010;

int ans[N] = {0};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, x, y;
	cin >> n >> x >> y;
	for(int i = 1 ; i <= n ; i++) {
		for(int j = i + 1 ; j <= n ; j++) {
			int v[3] = {abs(i-j), 
				abs(i-x) + abs(j-y)+1, 
				abs(i-y) +abs(j-x)+1};
			int mn = min(v[0], min(v[1], v[2]));
			ans[mn]++;
		}
	}
	for(int k = 1 ; k < n; k++) {
		cout << ans[k] << "\n";
	}
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
if n & 1:
    b[n // 2] = a[0]
    for i in range(1, n // 2 + 1):
        b[n // 2 + i] = a[i * 2 - 1]
        b[n // 2 - i] = a[i * 2]
else:
    for i in range(n // 2):
        b[i] = a[n - 1 - 2 * i]
        b[n // 2 + i] = a[2 * i]
print(b[0], end = "")
for i in b[1:]:
    print("", i, end = "")
print()


Measured memory_bytes: 26180
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

int main(int argc, char const *argv[])
{
  int a, b;
  cin >> a >> b;
  if (b % a == 0)
  {
    cout << a + b << endl;
  }
  else
  {
    cout << b - a << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N,K=list(map(int,input().split()))
R,S,P=list(map(int,input().split()))
T=input()

kanri=[]
for i in range(N):
   kanri.append(1)

score=0
for i in range(N):
   if i<K:
      if T[i]=="r":
         score+=P
      elif T[i]=="s":
         score+=R
      else:
         score+=S

   elif i>=K:
      if T[i]==T[i-K] and kanri[i-K]==1:
         kanri[i]=0
      elif T[i]==T[i-K] and kanri[i-K]==0:
         if T[i]=="r":
            score+=P
         elif T[i]=="s":
            score+=R
         else:
            score+=S 
      else:
         if T[i]=="r":
            score+=P
         elif T[i]=="s":
            score+=R
         else:
            score+=S      
print(score)


Measured memory_bytes: 4212
#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) { return false; }
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a.begin(), a.end());
  int x = a.back();
  a.pop_back();
  int k = a[0];
  for (int y : a) {
    if (min(k, x - k) < min(y, x - y)) {
      k = y;
    }
  }
  printf("%d %d\n", x, k);
  return true;
}

int main() {
  while (solve());
  return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
#define C first.first
#define F first.second
#define X second.first
#define Y second.second
#define INF (1<<29)
int W,H;
char fie[101][101];
int mvc[101][101];
int dmx[]={1,0,-1,0,1,-1,1,-1};
int dmy[]={0,1,0,-1,1,-1,-1,1};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int h[101][101][1<<5];
int gx,gy;
int MC;
bool check(int x,int y){
  if(x < 0 || y < 0 || x>=W || y>=H ) return true;
  return false;
}
void printmv(){
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++)
      printf("%2d ",mvc[j][i]);
    puts("");
  }   
}
void printh(){
  for(int k=0;k<(1<<MC);k++)
    for(int i=0;i<H;i++)
      for(int j=0;j<W;j++)
	printf("h[%d][%d][%d]=%d\n",j,i,k,h[j][i][k]);
}
int solve(int x,int y){
  // printmv();
  queue<PP> q;
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      for(int k=0;k<(1<<MC);k++)
	h[j][i][k]=INF;
  q.push(PP(P(0,0),P(x,y)));
  h[x][y][0]=0;
  while(!q.empty()){
    PP p = q.front(); q.pop();
    x = p.X; y = p.Y;
    for(int i=0;i<4;i++){
      int nx = x + dx[i], ny = y + dy[i];
      if( check(nx,ny) ) continue;
      if( fie[nx][ny] == '#') continue;
      if( '0' <= fie[nx][ny] && fie[nx][ny] <= '5' ){
	int mc = fie[nx][ny]-'0';
	int st = (p.F | (1<<mc));
	if( h[nx][ny][st] > p.C + mvc[x][y] ){
	  h[nx][ny][st] = p.C + mvc[x][y];
	  q.push(PP(P(p.C+mvc[x][y],st),P(nx,ny)));
	}
      } else {
	if( h[nx][ny][p.F] > p.C + mvc[x][y] ){
	  h[nx][ny][p.F] = p.C + mvc[x][y];
	  q.push(PP(P(p.C+mvc[x][y],p.F),P(nx,ny)));
	}
      }
    }
  }
  //  printh();
  // cout << gx << " " << gy << " " << (1<<MC)-1 << " " << h[gx][gy][(1<<MC)-1]<<"\n";
  return h[gx][gy][(1<<MC)-1];
}
void mark(int x,int y,int c){
  for(int i=0;i<8;i++){
    int nx = x+dmx[i], ny = y + dmy[i];
    if(check(nx,ny)) continue;
    mvc[nx][ny]=max(mvc[nx][ny],c);
  }
  if(c==3){
    for(int i=0;i<8;i++){
      int nx = x+dmx[i], ny = y + dmy[i];
      if(check(nx,ny)) continue;
      mark(nx,ny,c-1);
    }
  }
}
int main(){
  int sx,sy;
  cin >> W >> H;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> fie[j][i];
      mvc[j][i]=1;
    }
  }
  MC=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(fie[j][i]=='#'){
	mark(j,i,3);
      } else if(fie[j][i]=='S'){
	sx = j;
	sy = i;
      } else if(fie[j][i]=='M'){
	fie[j][i]='0'+MC;
	MC++;
      } else if(fie[j][i]=='G'){
	gx = j;
	gy = i;
      }
    }
  }
  cout << solve(sx,sy) << "\n";
}

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

const int INF = 2e9;

int main(){
    string s;
    string t;
    cin >> s >> t;
    int a = s.size();
    t = t.substr(0,a);
    if(s == t)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int h, w, n;
int ans[100][100];
P getXY(int p) {
  int x = p / w;
  int y = p / w % 2 == 0 ? p % w : w - (p % w + 1);
  return P(x, y);
}

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

  cin >> h >> w >> n;
  int xy = 0;
  REP(i, n) {
    int a;
    cin >> a;

    REP(j, a) {
      P p = getXY(xy);
      ans[p.first][p.second] = i + 1;
      xy++;
    }
  }

  REP(i, h) {
    REP(j, w) {
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
}


Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main() {
  string S; cin >> S;
  bool flag = true;
  for(int i = 0; i < (S.size()+1)/2; ++i){
    if (S[i] != S[S.size()-i-1]) {
      flag = false;
      break;
    }
  }
  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;




int main(void) {
	ll n, suma = 0, sumb = 0;
	cin >> n;
	vector<ll>a(n), b(n);
	for (int i = 0;i < n;i++) cin >> a[i];
	for (int i = 0;i < n;i++)cin >> b[i];
	ll num1 = 0, num2 = 0;
	for (int i = 0;i < n;i++) {
		if (a[i] > b[i])num1 += a[i] - b[i];
		else num2 += (b[i] - a[i]) / 2;
	}
	if (num1 <= num2)cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 384
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1--d//K)

Measured memory_bytes: 75356
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, k, p[200009], boss[200009], dat[200009];
set<int> st;

int fun(int x)
{
	if (x != boss[x])
		boss[x] = fun(boss[x]);
	return boss[x];
}

void gun(int x, int y)
{
	x = fun(x);
	y = fun(y);
	if (x > y) swap(x, y);
	boss[y] = x;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		if (i < k) st.insert(p[i]);
		boss[i] = i;
	}
	for (int i = k; i < n; i++) {
		bool f1 = false, f2 = false;
		auto tmp = st.begin();
		if (*tmp == p[i - k]) f1 = true;
		st.erase(p[i - k]);
		st.insert(p[i]);
		tmp = st.end();
		tmp--;
		if (*tmp == p[i]) f2 = true;
		if (f1 && f2) {
			gun(i, i - 1);
		}
	}

	int cur = 0;
	dat[0] = cur;
	st.clear();
	for (int i = 1; i < n; i++) {
		if (p[i] <= p[i - 1]) cur++;
		dat[i] = cur;
	}
	for (int i = k - 1; i < n; i++) {
		if (dat[i] == dat[i - k + 1])
			st.insert(i);
	}
	int pre = -1;
	for (auto t : st) {
		if (pre < 0) {
			pre = t;
			continue;
		}
		if (fun(t) == fun(pre)) {
			pre = t;
			continue;
		}
		gun(boss[t], boss[pre]);
		pre = t;
	}
	int cnt = 0;
	for (int i = k - 1; i < n; i++) {
		if (fun(i) == i) cnt++;
	}
	cout << cnt << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 12032
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();

		char[] c = s.toCharArray();

		int max = 0;
		int cnt = 0;
		for (int i = 0; i < s.length(); i++) {
			if (c[i] == 'I') cnt++;
			if (c[i] == 'D') cnt--;
			if (max < cnt) max = cnt;
		}

		System.out.println(max);

		sc.close();
	}

}


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

int digit_num(ll num){
    ll digits = 0;

    while(num > 0){
        num /= 10;
        digits++;
    }
    return digits;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll res = 1e9;

    for(int a = 1; a <= sqrt(N) + 1; ++a){

        if(N % a == 0){
            ll b = N / a;
            ll d_num = max(digit_num(a), digit_num(b));
            if(d_num < res) res = d_num;
        }
    }
    cout << res << endl;

}

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

// 型名の省略
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> P;
typedef pair<lint, lint> Plint;
 
const int MOD = 1e9+7;
const int INF = 1<<18;
const lint INFLINT = 1LL<<60;
const double PI=acos(-1.0);
 
// cinとcoutの高速化
#define endl "\n"
struct cinacc{cinacc(){cin.tie(0);ios::sync_with_stdio(false);}}cinaccc;
struct coutacc{coutacc(){cout.setf(ios::fixed);cout.precision(12);}}coutaccc;
 
// 繰り返し
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define reps(i,n) for(lint i=0;i<=(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>0;i--)
#define rreps(i,n) for(lint i=(lint)(n)-1;i>=0;i--)

#define pb push_back

#define ALL(s) (s.begin(), s.end())
#define SZ(s) (s.size())

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;}

// Union-Find-Tree
class UnionFind {
	vector<int> par;
	UnionFind(int n):par(n){rep(i,n)par[i]=i;}
	int root(int x){if(par[x]==x)return x;return par[x]=root(par[x]);}
	void unite(int x,int y){int rx=root(x);int ry=root(y);if(rx==ry)return;par[rx]=ry;}
	bool same(int x,int y){return root(x)==root(y);}
};

// Final Weapon!
// #define int lint

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> x(n);
    rep(i, n) cin >> x[i];
    
    sort(x.begin(), x.end(), greater<int>());
    
    bool flg = true;
    rep(i, n) {
        ans += (flg ? x[i] : -x[i]);
        flg = !flg;
    }
    
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define oo 0x3f3f3f3fLL
#define sz(s) (int)(s.size())
#define RT(s) return cout<<s,0
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}

const int N = 2e3 + 9;
vector<int> adj[N];
vector<int> dis[N];
int n;
void bfs(int node) {
	vector<int> &len = dis[node];
	len = vector<int>(n + 1, oo);
	len[node] = 0;
	queue<int> q;
	q.push(node);
	while (sz(q)) {
		node = q.front();
		q.pop();
		for (int ch : adj[node]) {
			if (len[ch] > len[node] + 1) {
				len[ch] = len[node] + 1;
				q.push(ch);
			}
		}
	}
}
int main() {
	run();
	int x, y;
	cin >> n >> x >> y;
	for (int i = 1; i < n; i++)
		adj[i].push_back(i + 1), adj[i + 1].push_back(i);
	adj[x].push_back(y);
	adj[y].push_back(x);
	map<int, int> mp;
	for (int i = 1; i <= n; i++)
		bfs(i);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			mp[dis[i][j]]++;
	for (int k = 1; k < n; k++)
		cout << mp[k] << endl;
}


Measured memory_bytes: 16128
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	int n=in(),ans=0;
	int i=1;
	if(n&1){cout<<0;return 0;}
	n/=2;
	while(n>0)
	{
		ans+=(n/5);
		n/=5;
	}
	cout<<ans;
	
}

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

kabu = 0
money = 1000

for i in range(1,n):
    if a[i] < a[i-1]:
        money += kabu*a[i-1]
        kabu = 0
    elif a[i] > a[i-1]:
        kabu += money//a[i-1]
        money -= money//a[i-1]*a[i-1]
    else:
        pass
    
if kabu != 0:
    money += kabu*a[n-1]
print(money)


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

int main() {
  int a, b;
  while(scanf("%d %d", &a, &b) != EOF) {
    a += b;
    b = 0;
    while(a != 0) {
      a /= 10;
      b++;
    }
    printf("%d\n", b);
  }
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main(){
  int n, w;
  cin >> n >> w;
  int stanw;
  vector<vector<int>> dp(n+1,vector<int>(301,-INF));
  dp[0][0] = 0;
  for(int i=0; i<n; ++i){
    int wi, vi;
    cin >> wi >> vi;
    if(i == 0) stanw = wi;
    for(int j=i+1; j>=1; --j){
      if(stanw *j > w) continue;
      for(int k=0; k<=300; ++k){
        if(stanw *j +k > w) break;
        if(k >= wi-stanw){
          dp[j][k] = max(dp[j][k], dp[j-1][k-(wi-stanw)] +vi);
        }
      }
    }
  }
  int ans = 0;
  for(int i=0; i<=n; ++i) for(int j=0; j<=300; ++j){
    if(dp[i][j] > 0){
      //cout << "i:" << i << " j:" << j << " dp:" << dp[i][j] << endl;
      ans = max(ans, dp[i][j]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3740
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (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; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int n,a,b;
  cin >> n >> a >> b;
  ll h[n];
  rep(i,n)cin >> h[i];
  ll l = 0;
  ll r = 1e9;
  int d = a - b;
  while(l+1<r){
    ll m = (l+r)/2;
    ll c = 0;
    rep(i,n){
      ll res = max(h[i]-b*m,0LL);
      c += (res+d-1)/d;
    }
    if(c<=m)r=m;
    else l=m;
  }
  cout << r << endl;
}

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

int main(){
  int n,g,p[11],c[11]; cin>>n>>g;
  for(int i=0;i<n;i++){
    cin>>p[i]>>c[i];
  }int ans=100000000;
  for(int bit=0;bit<(1<<n);bit++){
    int sum=0,num=0,rest_max;
    for(int i=0;i<n;i++){
      if(bit &(1<<i)){
        sum+=100*(i+1)*p[i]+c[i];
        num+=p[i];
      }else rest_max=i;
    }
    if(sum<g){
      int s=100*(rest_max+1);
      int x=(g-sum+s-1)/s;
      if(x>=p[rest_max]){
        continue;
      }num+=x;
    }
    ans=min(ans,num);
  }cout<<ans<<endl;
}

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

using namespace std;

int CMMDC(int a, int b)
{
    int r;
    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    long long a, b, d, S = 1, n;
    cin >> a >> b;
    n = __gcd(a,b);
    for( d = 2; d * d <= n; d++ ){
        if( n % d == 0 ){
            S++;
            while( n % d == 0 ){
                n /= d;
            }
        }
    }
    if( n != 1 ){
        S++;
    }
    cout << S;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define debug(x) cerr<<#x<<' '<<x<<'\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
const int maxn=2e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
ll qpow(ll a,int b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll book[maxn];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n;
    rep(i,1,n) cin>>book[i];
    sort(book+1,book+1+n);
    int now=2;
    ll ans=0;
    ll inv=qpow(2,mod-2);
    per(i,n,1) {
        ll add=qpow(2,now-2)*now%mod;
        add=add*qpow(2,i-1)%mod;
        add=inv*add%mod;
        ans+=add*book[i]%mod;
        ans%=mod;
        now++;
    }
    ans=ans*qpow(2,n)%mod;
    cout<<ans<<'\n';
    return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
const long long md=1e9+7;
string s;
long long ans,num[101010],cnt[5],p;
int main()
{
	cin>>s;
	num[0]=1;
	for(int i=1;i<=100010;i++)
	{
		num[i]=(num[i-1]*3)%md;
	}
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='A')
		{
			cnt[0]=(cnt[0]+num[p])%md;
		}
		else if(s[i]=='B')
		{
			cnt[1]=(cnt[1]+cnt[0])%md;
		}
		else if(s[i]=='C')
		{
			ans=(ans+cnt[1])%md;
		}
		else
		{
			ans=(ans*3+cnt[1])%md;
			cnt[1]=(cnt[1]*3+cnt[0])%md;
			cnt[0]=(cnt[0]*3+num[p])%md;
			p++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1280
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    if op=='+':
        print(a+b)
    elif op =='-':
        print(a-b)
    elif op=='*':
        print(a*b)
    elif op=='/':
        print(a//b)
    elif op=='?':break



Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  if(A >= 13){
    cout << B << endl;
  }
  if(A >= 6 && A <= 12){
    cout << B / 2 << endl;
  }
  if(A < 6){
    cout << 0 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N,K;
  cin>>K>>N;
  vector<ll> A(N);
  
  for(ll i=0;i<N;i++) {
cin>>A[i];
  }
  ll m=0;
  for(ll i=0;i<N-1;i++) {
m=max(m,A[i+1]-A[i]);
  }
  m=max(m,K+A[0]-A[N-1]);
  cout<<K-m<<endl;
}
  

Measured memory_bytes: 4836
fun main(args: Array<String>) = panasonic2020d()

fun panasonic2020d() {
    val n = readLine()!!.toInt()

    fun dfs(string: String, max: Char): List<String> {
        return if (string.length == n) {
            listOf(string)
        } else {
            ('a'..max).map { dfs(string + it, if (it == max) max + 1 else max) }.flatten()
        }
    }

    val answer = dfs("", 'a').sorted().joinToString(System.lineSeparator())

    println(answer)
}


Measured memory_bytes: 58824
s = list(input())

# count BC from left
bc_cnt = 0
res = 0
for i in range(len(s)-2, -1, -1):
    if s[i] == "B":
        if s[i+1] == "C":
            bc_cnt += 1
        else:
            bc_cnt = 0
    elif s[i] == "A":
        if s[i+1] == "C":
            bc_cnt = 0
    else:
        if s[i+1] == "C":
            bc_cnt = 0
    if s[i] == 'A':
        res += bc_cnt
print(res)


Measured memory_bytes: 62064
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int c[500001][26];

inline int lowbit(int x){
	return x&(-x);
}

inline void add(int p,int k){
	while(p<=n){
		++c[p][k];
		p+=lowbit(p);
	}
}
inline void amend(int p,int k,int f){
	while(p<=n){
		++c[p][k];
		--c[p][f];
		p+=lowbit(p);
	}
}

inline int sum(int p,int k){
	int ans=0;
	while(p){
		ans+=c[p][k];
		p-=lowbit(p);
	}
	return ans;
} 
inline int ask(int l,int r){
	int ss=0;
	for(int i=0;i<26;++i)if(sum(r,i)-sum(l-1,i))++ss;
	return ss;
}

int main(){
	memset(c,0,sizeof(c));
	register int m,f,a,b;
	register char c;
	cin>>n>>s>>m;
	s=' '+s;
	int i;
	for(i=1;i<=n;++i)add(i,s[i]-'a');
	while(m--){
		cin>>f>>a;
		if(f==1){
			cin>>c;
			amend(a,c-'a',s[a]-'a');
			s[a]=c;
		}
		else{
			cin>>b;
			cout<<ask(a,b)<<endl;
		}
	}
}

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

typedef long long ll;

int main() {
    int N;
    ll K;
    cin >> N >> K;
    vector<int> A(N), F(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> F[i];
    sort(A.begin(), A.end());
    sort(F.begin(), F.end());
    ll lo = -1, hi = 1e12;
    while (lo + 1 < hi) {
        ll mi = (lo + hi) / 2;
        //cout << lo << " " << mi << " " << hi << endl;
        ll s = 0;
        rep(i, N) {
            ll x = 1LL * A[i] * F[N - 1 - i];
            if (x > mi) s += (x - mi + F[N - 1 - i] - 1) / F[N - 1 - i];
        }
        if (s > K) lo = mi;
        else hi = mi;
    }
    cout << hi << endl;
}

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

long long n,a,m,k,q,b,c=1,a1,a2,b1,b2;
float qq,ww,ff=2,qs;
string ss,s1,s2;
int main(){
    cin>>n;
    vector<ll>v(n,0);
    for (int i=0; i<n; i++){
        cin>>v[i];
    }
    sort(v.begin(), v.end());
    if (n%2==1){
        cout<<0;
    }
    else{
        a=n/2;
        if (v[a]==v[a-1]){
            cout<<0;
        }
        else{
            cout<<v[a]-v[a-1];
        }
    }
}


Measured memory_bytes: 1024
import sys
k=int(input())
d={}
ans=1
mod=7%k
mod1=7%k
d[mod1]=1
ch=0
  
while mod1!=0:
  mod=(mod*10)%k
  mod1=mod1+mod
  if mod1>=k:
    mod1=mod1%k
  if mod1 in d:
    ch+=1
    break
  if mod1 not in d:
    d[mod1]=1
  ans+=1
  
if ch==0:
  print(ans)
else:
  print(-1)
    

Measured memory_bytes: 92732
import std.stdio, std.array, std.conv, std.typecons, std.algorithm;

long impl(long n, long w, const ref long[] ws, const ref long[] vs, ref long[][] dp) {
    if(dp[n][w] == -1) {
        const auto prev_w = w-ws[n-1];
        const auto yes = prev_w >= 0 ? impl(n-1, prev_w, ws, vs, dp) + vs[n-1] : -1;
        const auto no = impl(n-1, w, ws, vs, dp);
        dp[n][w] = max(yes, no, dp[n][w]);
    }
    return dp[n][w];
}

long solve(long n, long w, const ref long[] ws, const ref long[] vs) {
    auto dp = new long[][](n+1, w+1);
    foreach(ref v ; dp[]) { v[] = -1;}
    dp[0][] = 0;
    return impl(n, w, ws, vs, dp);
}

void main() {
    immutable i1 = readln.split.to!(long[]);
    immutable n = i1[0], w = i1[1];
    auto ws = new long[n];
    auto vs = new long[n];

    for(auto i = 0; i < n; i++) {
        auto input = readln.split.to!(long[]);
        ws[i] = input[0];
        vs[i] = input[1];
    }

    writeln(solve(n, w, ws, vs));
}


Measured memory_bytes: 79996
n,m=map(int,input().split())
ks_list=[]
for i in range(m):
    sub_list=list(map(int,input().split()))
    sub_list=sub_list[1:]
    ks_list.append(sub_list)
p_list=list(map(int,input().split()))
ans=0
for i in range(2**n):
    s_list=[]
    for j in range(n):
        s_list.append(i&1)
        i=i>>1
    count=1
    for j in range(m):
        Sum=0
        for x in ks_list[j]:
            Sum=Sum+s_list[x-1]
        if Sum%2==p_list[j]:
            count=count
        else:
            count=0
    ans=ans+count
print(ans)
    


Measured memory_bytes: 41712
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]

dp=[[-1,-1,-1] for i in range(n)]
dp[0]=[l[0][0],l[0][1],l[0][2]]

for i in range(1,n):
 for j in range(3):
  for k in range(3):
   if j==k:
    continue
   dp[i][j]=max(dp[i][j],dp[i-1][k]+l[i][j])

print(max(dp[-1]))

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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))

typedef long long ll;

using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin>>n;
  
  string s[n] = {""};
  rep(i,n) cin>>s[i];
  
  int az = 26;
  int azc[az] = {0};
  
  rep(i,az) {
    char alp = (char)('a'+i);
    int c;
    
    rep(i,n) {
      string S = s[i];
      
      int alpc = count(all(S), alp);
      if(i==0) {
        c = alpc;
      } else {
        c = min(c, alpc);
      }      
    }
    
    azc[i] = c;
  }
  
  rep(i,az) {
    
    int c = azc[i];
    rep(j,c) cout<<(char)('a'+i);
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[100][100],p,w,h;
int fn(int x,int y){
  if(0){
  }else if(a[x][y]==-2){
    a[x][y]=p+1;
  }else if(a[x][y]==-1){
    if(x==0||x==w-1||y==0||y==h-1)
      return 1;
    a[x][y]=p;
    if(fn(x-1,y)||fn(x,y-1)||fn(x+1,y)||fn(x,y+1))
      return 1;
  }
  return 0;
}
int fm(int x,int y){
  if(0){
  }else if(a[x][y]==-2){
    if(x==0||x==w-1||y==0||y==h-1)
      return 1;
    a[x][y]=p;
    if(fm(x-1,y)||fm(x,y-1)||fm(x+1,y)||fm(x,y+1))
      return 1;
  }
  return 0;
}
int main(){
  int i,j,k;
  char c;
  while(cin>>w>>h&&w+h){
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	cin>>c;
	if(0){
	}else if(c=='#'){
	  a[j][i]=-2;
	}else if(c=='.'){
	  a[j][i]=-1;
	}else if(c=='&'){
	  a[j][i]=0;
	}
      }
    }
    for(p=0;;){
      for(j=0;j<h;j++){
	for(k=0;k<w;k++){
	  if(a[k][j]==p){
	    if(k==0||k==w-1||j==0||j==h-1)
	      break;
	    if(fn(k-1,j)||fn(k,j-1)||fn(k+1,j)||fn(k,j+1))
	      break;
	  }
	}
	if(k!=w)
	  break;
      }
      if(j!=h)
	break;
      p++;
      for(j=0;j<h;j++){
	for(k=0;k<w;k++){
	  if(a[k][j]==p){
	    if(k==0||k==w-1||j==0||j==h-1)
	      break;
	    if(fm(k-1,j)||fm(k,j-1)||fm(k+1,j)||fm(k,j+1))
	      break;
	  }
	}
	if(k!=w)
	  break;
      }
      if(j!=h)
	break;
    }
    cout<<p<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x)      x.begin(), x.end()
#define rep(i,n)    for (int i = 0; i < (n); ++i)
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}

signed main()
{
    // ios::sync_with_stdio(false); cin.tie(nullptr);
    i64 n;
    cin >> n;

    for (i64 a = 1; a <= 3500; ++a) {
        for (i64 b = 1; b <= 3500; ++b) {
            i64 x = a*b*n;
            i64 y = (4*a*b - a*n - b*n);
            if (x > 0 && y > 0 && x % y == 0) {
                const i64 c = x / y;
                cout << a << ' ' << b << ' ' << c << endl;
                return 0;
            }
        }
    }

    return 0;
}



Measured memory_bytes: 764
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct UnionFind {
    vector<int> id;
    vector<vector<int> > groups;
    int gn; //number of groups
    UnionFind(int n){
        id = vector<int>(n);
        groups = vector<vector<int> >(n);
        gn = n;
        for(int i=0;i<n;++i){
            id[i]=i;
            groups[i]={i};
        }
    }
    void unite(int a, int b) {
        if(same(a,b)) return;
        gn--;
        int x = id[a];
        int y = id[b];
        if(groups[x].size()<groups[y].size()) swap(x,y);
        for(int j : groups[y]){
            id[j] = x;
            groups[x].push_back(j);
        }
        groups[y].clear();        
    }
    bool same(int a, int b) {
        return id[a] == id[b];
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    UnionFind fr(n);
    vint cfr(n,0);
    REP(i,m){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        fr.unite(a,b);
        cfr[a]++;
        cfr[b]++;
    }
    vint ans(n);
    REP(i,n){
        int t = (int)fr.groups[fr.id[i]].size()-1;
        ans[i]= t-cfr[i];
    }
    REP(i,k){
        int c,d;
        cin >> c >> d;
        c--;
        d--;
        if(fr.same(c,d)){
            ans[c]--;
            ans[d]--;
        }
    }
    REP(i,n-1){
        cout << ans[i] << " ";
    }
    cout << ans[n-1] << endl;

    return 0;
}

Measured memory_bytes: 8440
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
using namespace std;

ll calc_profit(vvi Profit,vi count){
    ll ans = 0;
    for(int i = 0; i < Profit.size(); i++){
        ans += Profit[i][count[i]];
    }

    return ans;
}

int main(){
    int N; cin >> N;
    vector<vector<int>> Stores(N,vi(10));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 10; j++){
            cin >> Stores[i][j];
        }
    }
    vvi Profit(N,vi(11));
    rep(i,N) rep(j,11) cin >> Profit[i][j];

    ll max = -int_INF;
    for(int k = 1; k < (1 << 10); k++){
        bitset<10> bs(k);
        vi Count(N);

        for(int p = 0; p < 10; p++){
            if(bs[p] == true){
                for(int q = 0; q < N; q++){
                    if(Stores[q][p] == true){
                        Count[q]++;
                    }
                }
            }
        }

        int prof = calc_profit(Profit,Count);
        max < prof ? max = prof:1;
    }

    cout << max << endl;
    sysp;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep2(i,n) REP(i,1,n+1)
#define rep3(i,n) REP(i,0,n+1)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define repll(i,n) REPLL(i,0,n)
#define repll2(i,n) REPLL(i,1,n+1)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define Size(s) (int) s.size()

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

int main() {
    int n;
    cin >> n;
    vector<pii> v;

    rep(i, n) {
        int a;
        cin >> a;
        v.push_back(MP(a, i));
    }

    sort(v.begin(), v.end());

    int mid = v[n / 2].first;

    vector<pii> ans;

    for (auto i : v) {
        if (i.first < mid) {
            ans.push_back(MP(i.second, v[n / 2].first));
        } else {
            ans.push_back(MP(i.second, v[(n - 1) / 2].first));
        }
    }

    sort(ans.begin(), ans.end());

    for (auto x : ans) cout << x.second << endl;

    return 0;
}

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

typedef long long ll;
ll K;
string S;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> S >> K;
    int cnt1=0;
    for(int i=0; i<S.size(); i++){
        if(S[i]=='1') cnt1++;
        else break;
    }
    if(K<=cnt1){
        cout << 1 << endl;
    }else{
        cout << S[cnt1] << endl;
    }

}


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

int main() {
	ll ans,n;
	cin>>n;
	vector<ll> v(4,0);
	for(ll i=0;i<n;i++) {
	    string s;
	    cin>>s;
	    if(s=="AC")
	    v[0]++;
	    else if(s=="WA")
	    v[1]++;
	    else if(s=="TLE")
	    v[2]++;
	    else
	    v[3]++;
	}

	cout<<"AC x "<<v[0]<<endl;
	cout<<"WA x "<<v[1]<<endl;
	cout<<"TLE x "<<v[2]<<endl;
	cout<<"RE x "<<v[3]<<endl;
	
	return 0;
}


Measured memory_bytes: 3628
// https://atcoder.jp/contests/keyence2020
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

// 終了時間、開始時間 の順にセット
using interval = pair<int, int>;
vector<interval> interval_scheduling(vector<interval> J) {
    vector<interval> A;
    // 終了時間が早い順にソート
    sort(ALL(J));
    // 次の開始時間
    int f = 0;
    for (auto &x : J) {
        if (x.second >= f) {
            A.push_back(x);
            f = x.first;
        }
    }
    return A;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<interval> J;
    REP(i, N) {
        int X, L;
        cin >> X >> L;
        // 終了時間、開始時間の順にセット
        J.push_back({X + L, max(0LL, X - L)});
    }
    vector<interval> ans = interval_scheduling(J);
    cout << ans.size() << endl;

    return 0;
}


Measured memory_bytes: 6512
#include<bits/stdc++.h>
#define endl "\n"
#define int long  long 

using namespace std ; 
	 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ;

	string s1 , s2  ; 
	cin >> s1 >> s2 ; 
	int cnt= 0 ; 
	for(int i = 0; i < s1.size() ; ++i)
	{
		if(s1[i] != s2[i])
			cnt++ ; 
	}
	cout <<  cnt ; 
}       





Measured memory_bytes: 3784
f = set(range(0,3000,4))
h = set(range(0,3000,100))
fh = set(range(0,3000,400))
lp = (f -h).union(fh)
 
a = False
while True:
  f,l = list(map(int, input().split()))
  if f == 0 and l == 0:
    break
  if a:
    print ('')
  t = set(range(f,l+1))
  it = sorted(list(lp.intersection(t)))
  for y in it:
    print(y)
  if len(it) == 0:
    print('NA')
  a = True

Measured memory_bytes: 8072
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<template<class...> class ContT, class ValueT, size_t Dim>
struct vec_type
{
    using type = ContT<typename vec_type<ContT, ValueT, Dim-1>::type>;
};

template<template<class...> class ContT, class ValueT>
struct vec_type<ContT, ValueT, 0>
{
    using type = ValueT;
};

template<class ValueT, size_t Dim = 1>
using vec_t = typename vec_type<std::vector, ValueT, Dim>::type;


template<class ValueT, size_t Dim, class = typename std::enable_if<Dim == 0>::type>
auto make_vec(ValueT value = ValueT()) -> ValueT
{
    return value;
}

template<class ValueT, size_t Dim, class... Rest>
auto make_vec(size_t size0, Rest... rest)
{
    auto vec = make_vec<ValueT, Dim-1>(rest...);
    return std::vector(size0, vec);
}

int diffabs(int l, int r)
{
    if (l < r) return r-l;
    else return l-r;    
}


///////////////////////////////////////////////////

int main()
{
    int N;
    cin >> N;
    vi a(N);
    for (int i = 0; i < N; i++)
        cin >> a[i];

    int all = 0;
    for (int i = 0; i < N; i++)
        all ^= a[i];

    for (int i = 0; i < N; i++)
    {
        int ans = a[i] ^ all;
        cout << ans << endl;
    }
}

Measured memory_bytes: 3940
#include <cstring>
#include <iostream>
using namespace std;
int main () {
	int n, q;
	while (cin >> n >> q, n || q) {
		int counts[101];
		memset(counts, 0, sizeof(counts));
		for (int i = 0; i < n; i++) {
			int m;
			cin >> m;
			for (int j = 0; j < m; j++) {
				int d;
				cin >> d;
				counts[d]++;
			}
		}
		int mcount = 0, mindex = -1;
		for (int i = 0; i <= 100; i++) {
			if (mcount < counts[i]) {
				mcount = counts[i];
				mindex = i;
			}
		}
		if (q <= mcount) {
			cout << mindex << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>

using namespace std;

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

  unsigned long uTotal = 0;
  float fTotal = 0.0f;
  for (int i = 0; i < N; i++) {
    float x;
    string u;
    cin >> x >> u;

    if (u == "JPY") {
      uTotal += x;
    } else {
      fTotal += x * 100000000;
    }
  }

  fTotal *= 380000.0;
  fTotal /= 100000000;
  fTotal += uTotal;

  cout << fTotal << endl;
  
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<int, int> > vpi;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, i, tmp;
    cin >> n;

    vpi a(n);
    for (i=0;i<n;i++) {
        cin >> tmp;
        a[i] = make_pair(tmp, i + 1);
    }
    sort(a.begin(), a.end());
    for (auto p: a){
        cout << p.second << " ";
    }
    cout << endl;
    
    
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
main()
{
    int a,b,c,d,e,f,r,t,g,h,j,i;
    cin>>a>>b;
    if(b>=10&&b<100)
    {
        c=a*100;
        d=c+b;
    }
    else if(b<10)
    {
        c=a*10;
        d=c+b;
    }
    else{
        c=a*1000;
    d=c+b;}
    e=sqrt(d);
    if(e*e==d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
    int m,n1,n2,a[201];
    cin >> m >> n1 >> n2; 
    do{
        int maxg=n2;
        for (int i=1;i<=m;i++)
            cin >> a[i];
        for (int i=0;i<n2-n1+1;i++){
            if (a[maxg]-a[maxg+1]<a[n2-i]-a[n2-i+1])
                maxg=n2-i;
       }
       cout << maxg << endl;
       cin >> m >> n1 >> n2; 
    }while(!(m==0 && n1==0 && n2==0));
    return 0;
}


Measured memory_bytes: 3080
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}


int main(){
	desperate_optimization(10);
	int A,B;
	cin>>A;
	int ans = 0;
	for(int i = 0;i < A;i++) {
		cin>>B;
		while(B % 2 == 0) {
			B /= 2;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

int n,W;
int v[101],w[101];
int dp[101][10001];

int main(){
 ios::sync_with_stdio(false);
 cin.tie(0);
 cin>>n>>W;
 for(int i=0;i<n;i++){
  cin>>v[i]>>w[i];
 }
 for(int i=0;i<n;i++){
  for(int j=0;j<=W;j++){
   if(j<w[i]){
    dp[i+1][j]=dp[i][j];
   }else dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
  }
 }
 int ans=0;
 for(int i=0;i<=W;i++){
  ans=max(ans,dp[n][i]);
 }
 cout<<ans<<endl;
 return 0;
}

Measured memory_bytes: 7040
N,T = gets.split(" ").map(&:to_i)
routes = []
a = nil
N.times do
  routes << gets.split(" ").map(&:to_i)
end
cost_min = routes[0][0]
for i in 0...N
  if (routes[i][1] <= T && routes[i][0] < cost_min) || (routes[i][1] < T && routes[i][0] <= cost_min)then cost_min = routes[i][0] ; a ||= 1 end
end
puts a ? cost_min : "TLE"

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

typedef tuple<ll, ll, ll> T;

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



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;cin>>s;
    REP(i,s.size()-1){
        if(s[i]==s[i+1]){
            cout<<i+1<<" "<<i+2<<endl;
            return 0;
        }
    }
    REP(i,s.size()-2){
        if(s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<endl;
            return 0;
        }
    }
    cout<<-1<<" "<<-1<<endl;

}


Measured memory_bytes: 512
x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
result = []

def func1():
    E = [a+b for a in A for b in B]
    E.sort()
    if len(E) > k: E = E[-k:]
    F = [c+e for c in C for e in E]
    F.sort()
    return F[-k:][::-1]

[print(val) for val in func1()]


Measured memory_bytes: 166700
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

#define fr(i,a,b) for(int i=a;i<b;++i)
/////////////////

int const N = 141;

int a[N][N];

int h, w, c[N * N], n;

void solve(){
	cin >> h >> w;
	cin >> n;
	fr(i, 0, n) cin >> c[i];
	int col = 0;
	fr(i, 0, h*w){
		if(c[col] == 0) ++col;
		int x = i % w;
		int y = i / w;
		if(y&1) x = (w - 1 - x);
		a[y][x] = col;
		--c[col];
	}
	fr(i, 0, h){
		if(i) cout << endl;
		fr(j, 0, w){
			if(j) cout << " ";
			cout << a[i][j] + 1;
		}
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;



int main(){
  int N;
  vector<ll> v;
  cin >> N;
  rep(i,N){
    ll a;
    cin >> a;
    v.push_back(a);
  }

  ll ret = 0;
  rep(i,N){
    ret += v[i]-1;
  }
  cout << ret << endl;
  
  return 0;
}


Measured memory_bytes: 256