akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define ll long long
#define umapii unordered_map<int,int>
#define umapll unordered_map<ll,ll>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define vs vector<string>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvll vector<vll>
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define MP(a,b) make_pair(a,b)
#define debug(x)       cerr<< #x << " : " << x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[i].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";

/* ordered set: 
tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
member functions :
1. order_of_key(k) : number of elements strictly lesser than k
2. find_by_order(k) : k-th element in the set
*/

inline ll gcd (ll x , ll y){
    if (x < y) swap (x , y);
    while (y){
        ll temp = y;
        y = x % y;
        x = temp; 
    }
    return x;
}

inline ll modexp(ll x, ll ex , ll md) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % md;
        ex >>= 1ll;
        x = (x * x) % md;
    }
    return ans;
}

const int inf = 1e9 + 7;

void solve(){
    int A , B;
    cin >> A >> B;
       int H , M;
   cin >> H >> M;
   long double PI = acos(-1);
   long double minangle = ( (2 * PI) / 60 ) * M;
   long double hourangle =( (2 * PI) / 12 ) * H + ( (2 * PI) / (12 * 60.00) ) * M;

   long double angle = abs(minangle - hourangle);
   if (angle == 0){
    cout << fixed<<setprecision(20)<<abs(B - A) << endl;
   } else{
    cout << fixed<<setprecision(20) << sqrt( A*A + B*B - 2*A*B*cos(angle))<<endl;
   }

}
int main(){
    IOS;
    int T = 1;
    // cin >> T;
    for(int i = 1; i <= T; i++){
        // cout << "Case #" << i << ": ";
        solve();
    }

    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";       
}


Measured memory_bytes: 3856
n, m, k = gets.split.map(&:to_i)
desk_a = gets.split.map(&:to_i)
desk_b = gets.split.map(&:to_i)

acc = 0
dp_a = desk_a.map {|a| acc += a}
acc = 0
dp_b = desk_b.map {|b| acc += b}
dp_a.unshift(0)
dp_b.unshift(0)

result = 0
j = m

(0..n).each do |i|
  break if dp_a[i] > k
  j -= 1 while dp_b[j] > k - dp_a[i]
  result = [result, i + j].max
end

puts result

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

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<string> s(N);
  vector<int> t(N);
  for(int i = 0; i < N; i++) cin >> s[i] >> t[i];
  string X;
  cin >> X;
  int time = -1;
  for(int i = 0; i < N; i++){
    if(s[i] == X) time++;
    else if(time >= 0) time += t[i];
  }
  
  cout << time << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<string>
#include<string.h>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {
	int a, b, c;
	cin >> a >> b;
	a += b;
	if (a > 23) {
		a -= 24;
	}
	cout << a << endl;
	return 0;
}

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

int main(){
	char id[12], idd[12];

	scanf("%s %s", id, idd);
	int len=strlen(id);

	if(strlen(idd)==strlen(id)+1&&strncmp(id, idd, len)==0){
		printf("Yes");
	}else{
		printf("No");
	}

	return 0;
}


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

typedef long long ll;
typedef std::pair <int, int> pr;
const int N = 200054;

int n;
pr a[N];
bool fill[N];

inline ll min(const ll x, const ll y) {return x < y ? x : y;}

int main() {
	int i, u, v; ll ans, s = 0; bool ok = false;
	scanf("%d", &n);
	for (i = 0; i < n; ++i) scanf("%d%d", &u, &v), a[i] = pr(u, i), a[i + n] = pr(v, i + n);
	std::sort(a, a + 2 * n);
	for (u = i = 0; i < n; ++i) s += a[i].first, v = a[i].second % n, fill[v] ? ok = true : fill[v] = true, u += a[i].second < n;
	if (ok |= !u || u == n) ans = 0;
	else if (a[n].second % n == a[n - 1].second % n) ans = min(a[n].first - a[n - 2].first, a[n + 1].first - a[n - 1].first);
	else ans = a[n].first - a[n - 1].first;
	printf("%lld\n", ans + s);
	return 0;
}

Measured memory_bytes: 1920
#include <iostream>
using namespace std;
#define MAX 100005
#define NIL -1

struct Node { int p, l, r; };
typedef long long int ll;

Node T[MAX];
int N, D[MAX];
void print(int U) {
	cout << "node " << U << ": ";
	cout << "parent = " << T[U].p << ", ";
	cout << "depth = " << D[U] << ", ";
	if (T[U].p == NIL) cout << "root, ";
	else if (T[U].l == NIL) cout << "leaf, ";
	else cout << "internal node, ";
	cout << "[";
	for (int i = 0, c = T[U].l; c != NIL; i++, c = T[c].r) {
		if (i) cout << ", ";
		cout << c;
	}
	cout << "]" << endl;
}

void rec(int U, int P) {
	D[U] = P;
	if (T[U].r != NIL) rec(T[U].r, P);
	if (T[U].l != NIL) rec(T[U].l, P + 1);
}

int main() {
	int i, j, D, V, C, L, R;
	cin >> N;
	for (i = 0; i < N; i++) {
		T[i].p = T[i].l = T[i].r = NIL;
	}
	for (i = 0; i < N; i++) {
		cin >> V >> D;
		for (j = 0; j < D; j++) {
			cin >> C;
			if (j == 0) T[V].l = C;
			else T[L].r = C;
			L = C;
			T[C].p = V;
		}
	}
	for (i = 0; i < N; i++) {
		if (T[i].p == NIL) R = i;
	}

	rec(R, 0);
	for (i = 0; i < N; i++) {
		print(i);
	}
}


Measured memory_bytes: 7768
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };

string s;

signed main(){
    cin>>s;
    for(int i=0;i<26;++i){
        char c = 'a' + i;
        if(s.find(c)==string::npos){
            cout<<c<<endl;
            return 0;
        }
    }
    cout<<"None"<<endl;
}


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

int main(){
  int r, g, b;
  cin >> r >> g >> b;
  
  string ans = "NO";
  
  if((100*r + 10*g + b) %4 == 0){
    ans = "YES";
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
program onepercent;
var
    x, current : int64;
    counter : longint;

begin
    readln(x);
    counter := 0;
    current := 100;
    while not(current >= x) do begin
        current := current + (current div 100);
        counter += 1;
    end;
    writeln(counter);
end.

Measured memory_bytes: 1388
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 1000000001

int pertition(int*, char*, int, int);
void quickSort(int*, char*,int, int);
int check(int,int*, char*, int*, char*);
void merge(int *, char *, int, int, int);
void mergeSort(int *, char *, int, int);

main(){
  int n, i, r, *Ad, *cpyAd;
  char *Ac, *cpyAc;

  scanf("%d", &n);
  Ad = malloc(sizeof(int)*n);
  Ac = malloc(sizeof(char)*n);
  cpyAd = malloc(sizeof(int)*n);
  cpyAc = malloc(sizeof(char)*n);

  for(i=0; i<n; i++){
    scanf(" %c", Ac+i);
    scanf("%d", Ad+i);
    cpyAc[i] = Ac[i];
    cpyAd[i] = Ad[i];
    //printf("i=%d\n", i);
  }

  quickSort(Ad, Ac, 0, n-1);
  
  if(check(n, Ad, Ac, cpyAd, cpyAc)) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0; i<n; i++){
    printf("%c %d\n", Ac[i], Ad[i]);
  }

  return 0;
}

void quickSort(int *A, char *A2, int p, int r){
  int q;

  if(p < r){
    q = partition(A, A2, p, r);
    quickSort(A, A2, p, q-1);
    quickSort(A, A2, q+1, r);
  }
}

int partition(int *A, char *A2, int p, int r){
  int x = A[r];
  int i = p-1;
  int j, tmp;
  char tmp2;

  for(j=p; j<r; j++){
    if(A[j] <= x){
      i = i+1;
      tmp = A[i];
      tmp2 = A2[i];
      A[i] = A[j];
      A[j] = tmp;
      A2[i] = A2[j];
      A2[j] = tmp2;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;
  tmp2 = A2[i+1];
  A2[i+1] = A2[r];
  A2[r] = tmp2;

  return i+1;
}

int check(int n, int *Ad, char *Ac, int *oriAd, char *oriAc){
// 安定なソートであるMergeSortの結果と比較する
// 安定 : 1
// 安定でない : 0
  int i;

mergeSort(oriAd, oriAc, 0, n);

#ifdef DEBUG
  printf("\n****** MergeSort ******\n");
  for(i=0; i<n; i++) printf("%c %d\n", oriAc[i], oriAd[i]);
  printf("\n***********************\n");
#endif

  //アルファベットについて一致するか判定
  for(i=0; i<n; i++){
    if(/*QuickSort*/Ac[i] != /*MergeSort*/oriAc[i]) return 0;
  }
  return 1;
}

void merge(int *arryA, char *arryB, int left, int mid, int right){
  int n1, n2, i, j, k, *arryL, *arryR;
  char *arryLc, *arryRc;

  n1 = mid - left;
  n2 = right - mid;

  arryL = (int *)malloc(sizeof(int)*(n1 + 1));
  arryR = (int *)malloc(sizeof(int)*(n2 + 1));
  arryLc = (char *)malloc(sizeof(char)*(n1 + 1));
  arryRc = (char *)malloc(sizeof(char)*(n2 + 1));
  for(i=0; i<n1; i++){
    arryL[i] = arryA[left+i];
    arryLc[i] = arryB[left+i];
    //printf("++ arrLc[%d] = %c\n", i, arryB[left+i]);
  }
  for(i=0; i<n2; i++){
    arryR[i] = arryA[mid+i];
    arryRc[i] = arryB[mid+i];
    //printf("++ arrRc[%d] = %c\n", i, arryB[mid+i]);
  }
  arryL[n1] = INFINITY;
  arryR[n2] = INFINITY;

  i=0;//L
  j=0;//R

  for(k=left; k<right; k++){
    if(arryL[i] <= arryR[j]){
      arryA[k] = arryL[i];
      arryB[k] = arryLc[i];
      i++;
    }
    else{
      arryA[k] = arryR[j];
      arryB[k] = arryRc[j];
      j++;
    }
  }

  free(arryL);
  free(arryR);
  free(arryLc);
  free(arryRc);
}

void mergeSort(int *arryA, char *arryB,int left, int right){
  int mid;

  if(left+1 < right){
    mid = (right + left) / 2;
    mergeSort(arryA, arryB, left, mid);
    mergeSort(arryA, arryB, mid, right);
    merge(arryA, arryB, left, mid, right);
  }
}

Measured memory_bytes: 1916
#include<cstdio>
typedef long long ll;
const int mod=1000000007;
char s[100050];
int c[26];
int main(){
	int n,i,j,res,ans=0;
	scanf("%d%s",&n,s);
	for(i=0;i<n;++i){
		for(res=1,j=0;j<26;j++)if(j!=s[i]-'a')res=(ll)res*(c[j]+1)%mod;
		ans=(ans+res)%mod;
		++c[s[i]-'a'];
	}
	printf("%d\n",ans);
	return 0;
}

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

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

  vector<tuple<string,int,int>> vec(N);

  rep(i,N){
    string s;
    int p;
    cin >> s >> p;
    vec.at(i) = make_tuple( s , 100 - p , i + 1 );
  }

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

  rep(i,N){
    int x;
    tie(ignore,ignore,x) = vec.at(i);
    cout << x << endl;
  }


 
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n
        self.__connected=n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        self.__connected-=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

    def connected(self):
        return self.__connected

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        uf.unite(x,y)
    print(uf.connected())
resolve()

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
int A;

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

    std::cin >> N;

    int nn = 0, n = 1001001001;
    ll sum = 0;

    for(int i=0;i<N;++i){
        std::cin >> A;

        sum += std::abs(A);
        n = std::min(n, std::abs(A));

        if(A < 0){
            nn += 1;
        }
    }

    if(nn % 2 == 1){
        sum -= 2ll * n;
    }

    std::cout << sum << std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};


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

    int n;
    cin >> n;
    vector<vector<int>> a(2,vector<int> (n));
    rep(i,2){
        rep(j,n){
            cin >> a[i][j];
        }
    }
    int res = 0;
    int ans = 0;
    int tmp = 0;
    rep(i,n){
        rep(j,n){
            if(j == i) {
                ans += a[tmp][j];
                tmp += 1;
            }
            ans += a[tmp][j];
        }
        res = max(res,ans);
        ans = 0;
        tmp = 0;
    }
    cout << res << endl;



    cout << endl;
    return 0;
}


Measured memory_bytes: 256
# define _CRT_SECURE_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
#ifdef __MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
using namespace std;

# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<" :"<<x<<endl;
# define EPS 1e-12



template<class T> void debug(T a) { for (auto i : a)cout << i << endl; }

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };

typedef pair< double, vi > pdv;
int n;
int dis[17] = {}, num[17] = {}, vol[17] = {};
pdv memo[1 << 15][16];

double calcw(int bit)
{
	double ans = 0.0;
	for (int i = 0; i < n; i++)
	{
		if (bit & 1 << i)ans += vol[i] * 20.0;
	}
	return ans;
}

pdv dp(int bit, int prev)
{
	if (__builtin_popcount(bit) == n)return pdv(0.0, {});
	if (memo[bit][prev].first >= 0.0)return memo[bit][prev];

	double w = calcw(bit);
	double speed = 2000.0 / (70.0 + w);
	pdv ans(9999999999.0, {});
	for (int i = 0; i < n; i++)
	{
		if (bit & 1 << i)continue;
		pdv s = dp(bit | 1 << i, i);
		s.first += 1.0*abs(dis[i] - dis[prev]) / speed;
		if (ans.first > s.first)
		{
			ans = s;
			ans.second.push_back(num[i]);
		}
	}

	return memo[bit][prev] = ans;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i] >> dis[i] >> vol[i];
	}
	for (int i = 0; i < 1 << 15; i++)
	{
		for (int j = 0; j < 16; j++)
		{
			memo[i][j] = pdv(-1.0, {});
		}
	}
	pdv ans = dp(0, n);
	reverse(ALL(ans.second));
	for (int i = 0; i < n; i++)
	{
		if (i)cout << " ";
		cout << ans.second[i];
	}
	cout << endl;
}

Measured memory_bytes: 29516
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

vector<ll> divisor(ll n){
	vector<ll> res;
	for(ll i = 1; i * i <= n; i++) {
		if(n % i == 0){
			res.pb(i);
			if(i != n / i)res.pb(n / i);
		}
	}
	return res;
}

int main(){
	ll n;cin>>n;

	ll ans = 0;
	vector<ll> q = divisor(n - 1LL);
	ans += (q.size() - 1LL);
	vector<ll> a = divisor(n);
	for(ll i = 1; i < a.size(); i++) {
		ll tmp = n;

		while(tmp % a[i] == 0){
			tmp /= a[i];
		}
		if(tmp % a[i] == 1){
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}

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

#define int             long long
#define w(x)            int x; cin>>x; while(x--)
#define mk(arr,n,type)  type *arr=new type[n];
#define mod             pow(10,9)+7
#define inf             1e18
#define endl			"\n"
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >

void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main() {
	c_p_c();
	int n;
	cin >> n;
	map<int, int>m;
	int *arr = new int[n];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum += arr[i];
		m[arr[i]]++;
	}
	int q;
	cin >> q;
	for (int z = 0; z < q; z++) {
		int b, c;
		cin >> b >> c;
		int temp = m[b];
		sum = sum + (c - b) * temp;
		m[b] = 0;
		m[c] = m[c] + temp;
		cout << sum << endl;
	}
	return 0;
}


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

ll N;

ll solve(ll num, int keta, int n3, int n5, int n7, bool zero) {
    if (keta == 9) {
        if (num <= N and n3 > 0 and n5 > 0 and n7 > 0) return 1LL;
        else return 0;
    }

    ll ret = 0;
    ll b = powl(10, keta);
    if (zero) {
        ret += solve(num, keta+1, n3, n5, n7, zero);
    }
    else {
        // 0
        ret += solve(num, keta+1, n3, n5, n7, true);

        // 3
        ret += solve(num+3*b, keta+1, n3+1, n5, n7, zero);

        // 5
        ret += solve(num+5*b, keta+1, n3, n5+1, n7, zero);

        // 7
        ret += solve(num+7*b, keta+1, n3, n5, n7+1, zero);
    }

    return ret;
}

int main() {
    cin >> N;
    cout << solve(0, 0, 0, 0, 0, false) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int p = 1;
    long long ans = 0;
    while (n--) {
        int a; cin >> a;
        if (a == p) p++;
        else if (a > p) { ans += (a-1)/p; if (p == 1) p++; }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n,h = map(int,input().split())
a = []
b = []

for i in range(n):
    a_,b_ = map(int,input().split())
    a.append(a_)
    b.append(b_)
b.sort(reverse = True)
max_a = max(a)
ans =0

for i in range(n):
    ans +=1
    if max_a > b[i]:
        ans -=1
        break
    h -= b[i]
    if h <= 0:
        break
    
if h > 0: 
    d,f = divmod(h,max_a)
    ans += d
    if f != 0:
        ans +=1
print(ans)

Measured memory_bytes: 16944
//package Atcoder;
import java.util.*;
import java.io.*;
public class Main
{
	static final int mod=(int)1e9+7;
	static final int inf=(int)1e9;
	static final long INF=(long)1e18;
	public static void main(String[] args)
	{
		FastScanner fs=new FastScanner();
		int k=fs.nextInt();
		long s=0;
		for(int i=1;i<=k;i++)
		{
			for(int j=1;j<=k;j++)
			{
				for(int h=1;h<=k;h++)
				{
					s=s+fs.gcd(i,fs.gcd(j,h));
				}
			}
		}
		System.out.println(s);
	}
}
class FastScanner 
{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() 
		{
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		
		long pow(long x,long n)
		{
			long res=1;
			while(n>0)
			{
			   	if(n%2!=0)
			   	{
			   		res=(res*x);n--;
			   	}
			   	else
			   	{
			   		x=(x*x);n/=2;
			   	}
			}
			return res;
		}
		int gcd(int a,int b)
		{
			if(b==0)
			{
				return a;
			}
			return gcd(b,a%b);
		}
		long longgcd(long a,long b)
		{
			if(b==0)
			{
				return a;
			}
			return longgcd(b,a%b);
		}
		int[] sort(int arr[])
		{
			ArrayList<Integer> list = new ArrayList<Integer>();
			for(int i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		char[] charsort(char arr[])
	        {
	    	ArrayList<Character> list = new ArrayList<>();
	    	for(char c:arr)list.add(c);
	    	Collections.sort(list);
	    	for(int i=0;i<list.size();i++)
	    	{
	    		arr[i]=list.get(i);
	    	}
	    	return arr;
	        }
		long[] longsort(long arr[])
		{
			ArrayList<Long> list = new ArrayList<Long>();
			for(long i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		public int nextInt() 
		{
			return Integer.parseInt(next());
		}
		public int[] readArray(int n)
		{
			int[] arr=new int[n];
			for (int i=0; i<n; i++) arr[i]=nextInt();
			return arr;
		}	
		public long nextLong()
		{
			return Long.parseLong(next());
		}
		public long[] longreadArray(int n) 
		{
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
}

Measured memory_bytes: 32804
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;cin >> x >> y;
  if(x==y){
    cout << "Yes" << endl;
    return 0;
  }
  else{
    if(x==1||x==3||x==5||x==7||x==8||x==10||x==12){
      if(y==1||y==3||y==5||y==7||y==8||y==10||y==12){
        cout << "Yes" << endl;
        return 0;
      }
      else{
        cout << "No" << endl;
        return 0;
      }
    }
    if(x==4||x==6||x==9||x==11){
      if(y==4||y==6||y==9||y==11){
        cout << "Yes" << endl;
        return 0;
      }
      else{
        cout << "No" << endl;
        return 0;
      }
    }
    if(x==2&&y==2){
      cout << "Yes" << endl;
      return 0;
    }
    else {
      cout << "No" << endl;
      return 0;
    }
  }
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

const ull mod = 1000000007;

int main(void)
{
	int n;
	cin >> n;
	vector<ull> vs(n);
	rep(i, n) cin >> vs[i];
	const ll di = 62;
	vector<ull> one(di, 0);
	vector<ull> zero(di, 0);
	rep(i, n) {
		ull a = vs[i];
		rep(bits, di)
		{
			if (a & 1) {
				one[bits]++;
			}
			else {
				zero[bits]++;
			}
			a >>= 1;
		}
	}
	ull sum = 0;
	rep(i, di){
		ull seed = ((ull)1 << (ull)i) % mod;
		ull mul = (one[i] * zero[i]) % mod;
		sum += ((mul * seed) % mod);
		sum %= mod;
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 2560
#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
#include<string>
#include<limits.h>
#include<cmath>
#include<queue>
#define rep(i,n) for (int i=0; i<n; i++)
using namespace std;
typedef long long ll;

int main(){

  int n; cin >> n;
  cout << ceil(n/2.0)/n;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll x; cin >> x;

    vector<ll> num;

    rep(i,300){
        num.push_back(i*i*i*i*i);
    }

    ll n = num.size();

    rep(i,n){
        rep(j,n){
            if(num[i] - num[j] == x){
                cout << i << " " << j << endl;
                return 0;
            }
            if(num[i] + num[j] == x){
                cout << i << " " << -j << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3640
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int product = a*b;
    if (product % 2 == 0) {
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  string s, t; cin >> s >> t;
  reverse(ALL(s));
  reverse(ALL(t));
  bool ok = false;
  REP(i, s.length()-t.length() +1) {
    REP(j, t.length()) {
      if (s[i+j] != t[j] && s[i+j] != '?') {
        ok = false;
        break;
      }
      ok = true;
    }
    if (ok) {
      REP(j, t.length()) {
        s[i+j] = t[j];
      }
      break;
    }
  }
  if (!ok) {
    cout << "UNRESTORABLE\n";
  } else {
    for (char &c : s) if (c == '?') c = 'a';
    reverse(ALL(s));
    cout << s << "\n";
  }
  return 0;
}


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

int n;
long long total = 0;
std::vector<int> d;
std::vector<int> cur;
int k = 2;

void combination_cnt(int start, int cnt){
    if(cnt == k){
        total += d[cur[0]] * d[cur[1]];
        return;
    }
    for(int i = start; i < n; i++){
        cur.push_back(i);
        combination_cnt(i+1, cnt+1);
        cur.pop_back();
    }
}

int main(void){
    std::cin >> n;
    d.resize(n);
    for(int i = 0; i < n; i++){
        std::cin >> d[i];
    }
    combination_cnt(0, 0);
    std::cout << total << std::endl;

    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int ans=0;
int n;

void dfs(int i, string s){
    if(i>9) return;
    int x7=0, x5=0, x3=0;
    for(auto c:s)if(c == '7') x7++; else if(c == '5')x5++; else if(c=='3') x3++;
    if(x7>=1 && x5>=1 && x3>=1 && stoi(s)<=n) ans+=1; 
    dfs(i+1, s+'7');
    dfs(i+1, s+'5');
    dfs(i+1, s+'3');
}

int main(){
    cin >> n;
    dfs(0, "");
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0; return gcd(a, b, x, y);}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}
void YN(bool z){cout<<(z?"YES":"NO");}
void Yn(bool z){cout<<(z?"Yes":"No");}
void yn(bool z){cout<<(z?"yes":"no");}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 0;
int x, a, b;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> x >> a >> b;
  cout << (x-a)%b << endl;
  return 0;
}

Measured memory_bytes: 256
import itertools
n,m,x = map(int,input().split())
boollist = list(map(list,itertools.product([True,False],repeat = n)))
itemlist = []
for i in range(n):
    itemlist.append(list(map(int,input().split())))

a = 10**8
for i in range(len(boollist)):
    unders = [0 for i in range(m)]
    money = 0
    for j in range(n):
        if boollist[i][j]:
            money += itemlist[j][0]
            for k in range(m):
                unders[k] += itemlist[j][k+1]
    if min(unders) >= x and money < a:
        a = money
if a == 10**8:
    print(-1)
else:
    print(a)


Measured memory_bytes: 9624
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!

#include <bits/stdc++.h>
using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;

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

ll n, ans;
vll l;

void func() {
    cin >> n; n <<= 1;
    l.resize(n);
    for (ll i = 0; i < n; i++) {
        cin >> l[i];
    }
    sort(l.begin(), l.end(), greater<ll>());
    ans = 0;
    for (ll i = 0; i < n; i += 2) {
        ans += min(l[i], l[i + 1]);
    }
    cout << ans << endl;
}

int main() {
    fast_io; cout.precision(32);
    ll t = 1; // cin >> t;
    for (ll i = 1; i <= t; i++) {
        func();
    }
}


Measured memory_bytes: 256
N,M=map(int,input().split())
E=[list(map(int,input().split())) for _ in range(N)]
E.sort(key=lambda x:x[0])
#print(E)
count=0
for i in range(N):
    if M>E[i][1]:
       count=count+E[i][0]*E[i][1]
       M=M-E[i][1]
    else:
        count=count+E[i][0]*M
        break
print(count)

Measured memory_bytes: 64600
N = int( input() )

AC = 0
WA = 0
TLE = 0
RE = 0
for i in range( N ):
  a = input()
  if a == "AC":
    AC += 1
  elif a =="WA":
    WA += 1
  elif a == "TLE":
    TLE += 1
  elif a == "RE":
    RE += 1

print( "AC x {}".format( AC ) )
print( "WA x {}".format( WA ) )
print( "TLE x {}".format( TLE ) )
print( "RE x {}".format( RE ) )


Measured memory_bytes: 9200
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

cnt = 0
for i in range(len(S)//2):
	if S[i] != S[~i]:
		cnt += 1
print(cnt)


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

class Main
{
	static Scanner sc;
	
	public static void main( String[] args ) throws IOException
	{
	sc = new Scanner( new BufferedReader( new InputStreamReader( System.in ) ) );
		int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
		if(a < b && b < c) System.out.printf("Yes\n");
		else System.out.printf("No\n");
	}
}


Measured memory_bytes: 26140
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
int main()
{
    fastio();
  
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll a[5];
        cn(a,5);
        for(int i=0;i<5;i++)
        {
            if(a[i]==0)
            {
                cout<<i+1<<endl;
                break;
            }
        }
    }
    
}

Measured memory_bytes: 3596
N,M = gets.chomp.split(" ").map(&:to_i)
x,y = M.times.map{gets.split.map(&:to_i)}.transpose
a = Array.new(N+1,1)
b = Array.new(N+1,0)
b[1] = 1
M.times do |i|
  a[y[i]] += 1
  b[y[i]] = 1 if b[x[i]] == 1
  a[x[i]] -= 1
  b[x[i]] = 0 if a[x[i]] == 0
end
puts b.inject(:+)


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

int main()
{
    string N;
    cin >> N;
    int count = 0;
    for(int i = 0; i < N.size(); i++) {
        if(N[i] == '2') {
            count += 1;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int n;
  int i;
  scanf("%d",&n);
  for(i=1;i<10;i++){
    if(n%i==0){
      if(n/i<10){
        printf("Yes");
        return 0;
      }
    }
  }
  printf("No");
  return 0;
}


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

#define DEBUG 0

#if DEBUG
  #define DLOG(...) fprintf(stderr, __VA_ARGS__)
  #define DFUNC(fname, ...) fname(__VA_ARGS__)
#else
  #define DLOG(...)
  #define DFUNC(fname, ...)
#endif

ll N, M;
vector<ll> A;

typedef pair<ll,ll> myPair;
priority_queue<myPair, vector<myPair>, greater<myPair>> pque;

int main() {
#if !DEBUG
  ios_base::sync_with_stdio(false);
#endif

  cin >> N >> M;
  ll sum = 0;
  for (ll i = 0; i < N; i++)  {
    ll a;
    cin >> a;
    sum += a;
    pque.push(make_pair(a,1));
  }
  for (ll i = 0; i < M; i++) {
    ll b, c;
    cin >> b >> c;
    ll x = 0;
    while (x < b) {
      myPair p = pque.top();
      if (c <= p.first)  break;
      pque.pop();
      if (x + p.second <= b) {
	sum += (c - p.first) * p.second;
	x += p.second;
      }else {
	sum += (c - p.first) * (b - x);
	pque.push(make_pair(p.first, p.second - (b-x)));
	x = b;
      }
    }
    pque.push(make_pair(c, x));
  }
  cout << sum << endl;

  return 0;
}



Measured memory_bytes: 2420
N, A, B = map(int, input().split())
D = A - B

H = [int(input()) for _ in range(N)]

def f(n):
    needed_attacks = 0
    for h in H:
        r = h - B * n
        if r < 0:
            r = 0

        if r % D == 0:
            needed_attacks += r // D
        else:
            needed_attacks += r // D + 1

    return needed_attacks <= n

s = 0
e = max(H) // B + 1

while e - s > 1:
    m = (s + e) // 2
    if f(m):
        e = m
    else:
        s = m

print(e)


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

int g[10][10];
int n, m;

int dfs(int S, int pre) {
  if (S == (1 << n) - 1) return 1;
  int ans = 0;
  REP(i,n) {
    if (!(S >> i & 1) && g[pre][i]) {
      ans += dfs(S|1<<i,i);
    }
  }
  return ans;
}

int main() {
  while (cin >> n >> m) {
    memset(g,0,sizeof(g));

    REP(i,m) {
      int a, b;
      cin >> a >> b;
      a--;b--;
      g[a][b] = g[b][a] = 1;
    }

    cout << dfs(1<<0, 0) << endl;
  }
}


Measured memory_bytes: 3640
import java.util.*

fun main(args: Array<String>) {
    val reader = Scanner(System.`in`)
    val S = reader.next()
    val T = reader.next()
    
    var count = 0
    
    repeat(S.length){
        if(S[it] != T[it]){
            count++
        }    
    }
    
    println(count)
}

Measured memory_bytes: 41628
#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 <math.h> // sqrt()
#include <iomanip>
#define rep(i , n) for (int i = 1; i <= (int)(n); i++)
#define repz(i , n) for (int i = 0; i < (int) n; i++)
#define repi(i , r, n) for (int i = r; i <= (int)(n); i++)
#define repd(i , r, n) for (int i = r; i >= (int)(n); i--)



using namespace std;
int main(){
 int n;
  cin >> n;
  int64_t A[n];
  int64_t B[n];
  int64_t C[n];
  repz( i , n) cin >> A[i];
  repz( i , n) cin >> B[i];
  repz( i , n) cin >> C[i];
  sort(A, A + n);
  sort(C, C + n);
    int64_t ans = 0; int64_t a = 0; int64_t c = 0;
    for ( int64_t i : B){
        a = lower_bound(A, A + n, i ) - A ;
        c = upper_bound(C, C + n , i) - C;
        ans += a * (n - c);
    }
    cout << ans << endl;


    
}

Measured memory_bytes: 5984
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
#define maxn 200005
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
ll n,k,a[maxn],b[maxn];
int main()
{
    n=read(),k=read();reg int i;
    for(i=1;i<=n;++i)a[i]=read();
    for(i=1;i<=n;++i)b[i]=read();
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    reverse(b+1,b+1+n);
    reg ll l,r,mid,res;
    l=-1;r=1e15;
    while(l<r-1)
    {
        mid=(l+r)/2;res=0;
        for(i=1;i<=n;++i)
            res+=max(0ll,a[i]-mid/b[i]);
        if(res>k)l=mid;
        else r=mid;
    }printf("%lld\n",r);
	return 0;
}


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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

llong N;
vector<llong> a, rui;
vector<vector<llong> > memo;

llong dp(llong frt, llong bck){
	if(bck == frt)
		return 0;
	if(memo[frt][bck] != -1)
		return memo[frt][bck];

	llong ret = inf;
	for(int i = frt; i < bck; i++)
		ret = min(ret, dp(frt,i) + dp(i+1,bck));

	// cerr << frt << " " << bck << " : " << ret << endl;
	return memo[frt][bck] = ret + rui[bck] - rui[frt-1];
}

int main(){
	cin >> N;
	a.resize(N+1);
	memo.resize(N+1,vector<llong>(N+1,-1));
	rui.resize(N+1,0);
	for(int i = 1; i <= N; i++){
		cin >> a[i];
		rui[i] = rui[i-1] + a[i];
	}

	cout << dp(1ll,N) << endl;

	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include<vector>
#include<string>

using namespace std;


int main() {
	int N,A,B;
	cin >> N>>A>>B;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		int a = 0;
		int b = i;
		while (b > 0) {
			cerr << b << " " << flush;
			a += b%10;
			b /= 10;
		}
		if (A <= a && a <= B)ans+=i;
	}
	cout << ans;
	return 0;
}



/*int binSearch(vector<int> A, int key) {
	int left = 0, right = A.size();
	int abort = 0;
	sort(A.begin(), A.end());
	while (left + 1 < right) {// || [left,right) || > 1
		int mid = (left + right) / 2;
		if (A[mid] > key)right = mid;
		else
			left = mid;
	}
	return left || A[left] == key ? left : -1;
}*/

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

def main():
    N, M, *AB = map(int, read().split())
    
    uf = UnionFind(N)
    for a, b in zip(*[iter(AB)] * 2):
        a -= 1
        b -= 1
        uf.union(a, b)
        
    print(uf.group_count() - 1)
    
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 96040
// https://atcoder.jp/contests/abc160
// ABC 160
// D. Line++

#include <iostream>
#include <algorithm>

using namespace std;

int ans[2003];

int main(int argc, const char* argv[]) {

    int N, X, Y;
    cin >> N >> X >> Y;
    for(int i = 1; i < N; i++)
        ans[i] = 0;
    

    for(int i = 1; i <= N; i++) {
        for(int j = i+1; j <= N; j++) {
            int direct = abs(i - j);
            int shortcut1 = abs(i - X) + abs(j - Y) + 1;
            int shortcut2 = abs(j - X) + abs(i - Y) + 1;
            int shortcut = min(shortcut1, shortcut2);
            int dist = min(direct, shortcut);
            ans[dist]++;
        }
    }

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

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

int main(){
    int H, W;
    while(true){
        cin >> H >> W;
        if (H == 0 && W == 0) break;
        for (int i = 0; i < H; ++i){
            for (int j = 0; j < W; ++j){
                cout << "#";
            }
            cout << endl;
        }
        std::cout << std::endl;
    }

    return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#define N 100
using namespace std;

int main(){
 
 string x;
 
while(1){
    int a=0;
    cin>>x;
    if(x=="0") break;
    
    int n = x.size();
    for(int i=0;i<n;i++){
        a+=x[i]-'0';
    }
    cout<<a<<endl;
}
 
  return 0;
}


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

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



int main() {
    string S;

    ll Q;

    bool is_reversed = false;

    cin >> S >> Q;

    string ans = S;

    int T, F;
    string add;

    for (ll i = 0; i < Q; i++) {
      cin >> T;

      if (T == 1) {
        is_reversed = !is_reversed;
      } else if (T == 2) {
        cin >> F >> add;
        
        if ((F == 1 && !is_reversed) || (F == 2 && is_reversed)) {
          ans.insert(0, add);
        } else if ((F == 2 && !is_reversed) || (F == 1 && is_reversed)) {
          ans += add;
        }
      }
    }
    

    if (is_reversed) {
      reverse(ans.begin(), ans.end());
    }
    


    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ll, ll> pll;
#define all(c) begin(c), end(c)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define rep(i, n) for (ll i = 0; i < ll(n); i++)

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

const ll mod = 1000000007;
struct mint {
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    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 {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

struct combination {
    vector<mint> fact, ifact;
    // init struct with "n" of "nCk" (maximum number in other words)
    combination(int n) : fact(n + 1), ifact(n + 1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    // c(n,k) returns mint that contains nCk (mod p (= 1e9+7)) in x
    // i.e.) mint num = c(n,k), then num.x == nCk (mod p (= 1e9+7))
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }

    // nPk - permutation
    mint p(int n, int k) {
        return fact[n] * ifact[n - k];
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    unordered_map<ll, ll> pcounter;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
        ll tmp = a[i];
        for (ll i = 2; i * i <= tmp; i++){
            ll cnt = 0;
            while(tmp % i == 0){
                tmp /= i;
                cnt++;
            }
            if(pcounter[i] < cnt){
                pcounter[i] = cnt;
            }
        }
        if(tmp > 1 && pcounter[tmp] == 0){
            pcounter[tmp] = 1;
        }
    }

    mint lcmv(1);
    for (auto p : pcounter) {
        if (p.second == 0) continue;
        lcmv *= mint(p.first).pow(p.second);
    }

    mint ans;
    rep(i,n){
        ans += lcmv / mint(a[i]);
    }
    cout << ans.x << endl;
}


Measured memory_bytes: 4048
#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 int INF = 1001001001;

vector<int> to[100005]; //グラフ
int main() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    to[a].push_back(b); //無向グラフの作成
    to[b].push_back(a); //無向グラフの作成
  }

  queue<int> q;
  vector<int> dist(n, INF);
  vector<int> pre(n, -1);
  dist[0] = 0;
  q.push(0);
  while (!q.empty()) {
    int v = q.front(); //キューの前から取り出す
    q.pop();
    for (int u : to[v]) {
      if (dist[u] != INF) //すでに数字が書かれているならば何もやらない
        continue;
      dist[u] = dist[v] + 1; //書かれていないならば、前の層+1を書く。
      pre[u] = v; //どこから来たかを記入する。ここがいつものBFSと違うところ。
      q.push(u);
    }
  }

  /*ここから出力*/
  cout << "Yes" << endl;
  rep(i, n) {
    if (i == 0)
      continue;
    int ans = pre[i];
    ++ans;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 10644