akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e9;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;


int n;
string s;
int am;
int a1;
int a2;
signed main(){
  cin >> n;
  cin >> s;
  int k = 0;
  REP(i,n){
    if(s[i]=='('){
      k--;
      a1++;
    }
    else{
      k++;
      a2++;
    }
    am = max(am,k);
  }
  REP(i,am) cout << '(';
  cout << s;
  REP(i,a1+am-a2) cout << ')';
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

int a[3], c[3];

int main(){
	while(scanf("%d%d%d",&a[0],&a[1],&a[2])){
		sort(a,a+3,greater<int>());
		if(a[0] >= a[1]+a[2]) break;
		if(a[0]*a[0] == a[1]*a[1]+a[2]*a[2]) c[0]++;
		else if(a[0]*a[0] < a[1]*a[1]+a[2]*a[2]) c[1]++;
		else c[2]++;
	}
	printf("%d %d %d %d\n", c[0]+c[1]+c[2],c[0],c[1],c[2]);
}

Measured memory_bytes: 1040
#include<bits/stdc++.h>
using namespace std;
long long rec(int i,long long cur,long long sum,const string s)
{
	if(i==s.size())
		return sum;
	int d=s[i]-'0';
	long long res=0;
	if(i+1!=s.size())
		res+=rec(i+1,cur*10+d,sum,s);
	res+=rec(i+1,0,sum+cur*10+d,s);
	return res;
}
int main()
{
	string s;
	cin>>s;
	cout<<rec(0,0,0,s)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

// #include <unordered_set>
// #include <unordered_map>

#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())

#define pb push_back
#define mp make_pair

int gcd(int a, int b) {
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int lcm(int a, int b) {
    int c = gcd(a, b);
    a /= c;
    return a * b;
}

typedef std::pair<int, int> P;
typedef long long ll;
typedef long double ld;

const int MOD = 1000000007;
const int INF = 1e9;
const ll LINF = INF * 1ll * INF;
const ld DINF = 1e200;
const double EPS = 1e-10;
const double PI = acos(-1.0);


#define int long long

using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};


signed main() {
    string s;
    cin >> s;

//    cout << s.size() <<endl;x
//    for (int i = 0; i < s.size(); i++) {
//        if (s[i] == 'k') {
//            if (s[i + 1] != 'e') {
//                for (int j = i + 2; j < s.size(); j++) {
//
//                }
//            }
//
//        }
//    }
    string tmp = "keyence";
//    cout << s.substr(0,7) << endl;
//    cout << s.substr(s.size()-7,s.size()) << endl;
//    if (s.substr(0, 7) == "keyence") {
//        cout << "YES" << endl;
//        return 0;
//    } else if (s.substr(s.size() - 7, s.size()) == "keyence") {
//        cout << "YES" << endl;
//        return 0;
//    }

//    if(s[0] == 'k' && s.substr(s.size()-6,s.size()) == "eyence"){
//        cout << "YES" <<endl;
//    }
//
    for (int i = 0; i < 8; i++) {

//        cout << i << endl;
//        cout << s.substr(0, i) << " " << tmp.substr(0, i) << endl;
//        cout << s.substr(s.size() - 7 + i, s.size()) << " " << tmp.substr(tmp.size() - 7 + i, tmp.size()) << endl;

        if (s.substr(0, i) == tmp.substr(0, i) && (s.substr(s.size() - 7 + i, s.size()) ==
                                                   tmp.substr(tmp.size() - 7 + i, tmp.size()))) {

            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}


Measured memory_bytes: 256
// Undone
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
#define MOD 1000000007
using namespace std;
int hashed(string hash, int a, int b, int c, int d) {
  stack<int> num;
  int x, y;
  for (int i = hash.length()-1; i >= 0; i--) {
    switch (hash[i]) {
      case 'a':
        num.push(a);
        break;
      case 'b':
        num.push(b);
        break;
      case 'c':
        num.push(c);
        break;
      case 'd':
        num.push(d);
        break;
      case '+':
        x = num.top(); num.pop();
        y = num.top(); num.pop();
        num.push(x|y);
        break;
      case '*':
        x = num.top(); num.pop();
        y = num.top(); num.pop();
        num.push(x&y);
        break;
      case '^':
        x = num.top(); num.pop();
        y = num.top(); num.pop();
        num.push(x^y);
        break;
    }
  }
  return num.top();
}

signed main() {
  string hash;
  while (cin >> hash, hash != ".") {
    int a[4];
    for (int i = 0; i < 4; i++) {
      char c; cin >> c;
      a[i] = c-'0';
    }
    int original = hashed(hash, a[0], a[1], a[2], a[3]);
    int ans = 0;
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            if (original == hashed(hash, i, j, k, l)) {
              ans++;
            }
          }
        }
      }
    }
    cout << original << " " << ans << endl;
  }
}




Measured memory_bytes: 3176
import math
from decimal import *

a, b, x = map(Decimal, input().split())
c = Decimal(2*(a*a*b-x)/a/a/a)

if x >= a*a*b/2:
    theta = math.degrees(math.atan(c))
else:
    theta = math.degrees(math.atan(a*b*b/2/x))
    
    
print(theta)


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

#define ll long long
#define f(i, a, b) for(ll i=a;i<b;i++)
#define fi(i, a, b) for(ll i=b-1;i>=a;i--)
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define ml map<ll,ll>
#define pll pair<ll,ll>


int main()
{
   long  double a,b;
    cin>>a>>b;
  long  double res = a*b;
    cout<<((ll)(res));
 }


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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	string n;
	cin >> n;
	int len = n.size();
	int s = 0;
	rep(i,len){
		int a;
		a = ctoi(n[i]);
		s += a;
	}
    int x = atoi(n.c_str());
	if(x%s == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
pat = input()
if len(pat) == 1:
    print(0)            
else:
    #generate
    pat1 = "0"
    pat2 = "1"

    for i in range(len(pat)-1):
        if pat1[-1:]=="0":
            pat1 = pat1+"1"
        else:
            pat1 = pat1+"0"
        
    for i in range(len(pat)-1):
        if pat2[-1:]=="0":
            pat2 = pat2+"1"
        else:
            pat2 = pat2+"0"

    count1 = 0
    count2 = 0
    for s in range(len(pat)):
        if pat[s] != pat1[s]:
            count1 = count1 + 1

        if pat[s] != pat2[s]:
            count2 = count2 + 1


    if count1 <= count2:
        print(count1)

    else:
        print(count2)

Measured memory_bytes: 3316
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

void solveSingleCase(int caseNo)
{
    int N;
    cin >> N;
    VEC(int) A(N);
    READVEC(A);
    A.insert(BEGIN(A), 0);
    A.PB(0);
    
    int Dist = 0;
    FOR(i, 0, N + 1)
        Dist += abs(A[i] - A[i + 1]);

    FOR(i, 1, N + 1) {
        int Rem = abs(A[i] - A[i - 1]) + abs(A[i] - A[i + 1]);
        int Add = abs(A[i - 1] - A[i + 1]);
        cout << Dist - Rem + Add << endl;
    }
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 1656
# AOJ GRL_1_A Single Sourse Shortest Path
import heapq as hp

V, E, s = map(int, input().split())
graph = [[] for _ in range(V)]
INF = 0
for _ in range(E):
    a, b, d = map(int, input().split())
    graph[a].append((d, b)) 
    #graph[b].append((d, a)) #無向グラフならこれ使う
    INF = max(INF, d)

INF = INF*(E+1) + 1
D = [INF for _ in range(V)] # 頂点iへの最短距離がD[i]
D[s] = 0 
q = [] # しまっていく優先度付きキュー
hp.heappush(q, (0, s))

while q:
    nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
    if D[np] < nd: # 追加した後の残骸は見ない
        continue
    for d, p in graph[np]:
        if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
            D[p] = D[np] + d
            hp.heappush(q, (D[p], p))

for d in D:
    if d == INF:
        print('INF')
    else:
        print(d)


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

int main() {
  int n,x;
  cin>>n>>x;
  ll a[100005];
  rep(i,n) cin>>a[i];
  ll ans=0;
  rep(i,n-1){
    if(a[i]+a[i+1]<=x) continue;
    ll d=a[i]+a[i+1]-x;
    a[i+1]-=min(a[i+1],d);
    ans+=d;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int H, W;
char F[15][15];
char S[15][15];

bool yes = false;

bool useW[15], useH[15];
vector<pair<int, int> > matchH;

void recW(int cnt) {
    if (cnt == W) {
	yes = true;
    } else {
	REP (i, W) if (!useW[i]) for (int j=i+1; j<W; j++) if (!useW[j]) {
	    bool ok = true;
	    EACH (e, matchH) {
		if (F[e->first][i] != F[e->second][j]
			|| F[e->first][j] != F[e->second][i]) {
		    ok = false;
		    break;
		}
	    }

	    if (ok) {
		useW[i] = useW[j] = true;
		recW(cnt+2);
		if (yes) return;
		useW[i] = useW[j] = false;
	    }
	}
    }
}

void solveW() {
    if (W & 1) {
	REP (i, W) {
	    bool ok = true;
	    EACH (e, matchH) {
		if (F[e->first][i] != F[e->second][i]) {
		    ok = false;
		    break;
		}
	    }
	    if (ok) {
		useW[i] = true;
		recW(1);
		if (yes) return;
		useW[i] = false;
	    }
	}
    } else {
	recW(0);
    }
}

void recH(int cnt) {
    if (cnt == H) {
	solveW();
    } else {
	REP (i, H) if (!useH[i]) {
	    useH[i] = true;
	    for (int j=i+1; j<H; j++) if (!useH[j]) {
		useH[j] = true;
		matchH.emplace_back(i, j);
		recH(cnt+2);
		if (yes) return;
		useH[j] = false;
		matchH.pop_back();
	    }
	    useH[i] = false;
	    break;
	}
    }
}

void solveH() {
    if (H & 1) {
	REP (i, H) {
	    useH[i] = true;
	    matchH.emplace_back(i, i);
	    recH(1);
	    if (yes) break;
	    useH[i] = false;
	    matchH.pop_back();
	}
    } else {
	recH(0);
    }
}

void MAIN() {
    scanf("%d%d", &H, &W);
    REP (i, H) scanf("%s", F[i]);

    solveH();
    puts(yes? "YES": "NO");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int N = 1407;
const int K = 38;
int ans[N][K];

int main(){
	ans[0][0] = 1;
	repp(i,0,K){
		repp(j,1,K){
			ans[i*(K-1)+j][0] = i+1;
		}
	}
	repp(j,0,K){
		repp(s,1,K){
			ans[j][s] = j*(K-1)+s+1;
		}
	}
	repp(i,1,K){
		repp(j,1,K){
			repp(s,1,K){
				ans[i*(K-1)+j][s] = K+(s-1)*(K-1)+1+(j+K-2+(i-1)*(s-1))%(K-1);
			}
		}
	}
	
	cout << N << ' ' << K << endl;
	repp(i,0,N){
		repp(j,0,K){
			cout << ans[i][j] << (j+1==K?'\n':' ');
		}
	}
	return 0;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,a;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a;
		n-=a;
	}
	if(n<0){
		cout<<-1<<endl;
	}else{
		cout<<n<<endl;
	}
}


Measured memory_bytes: 3664
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstdio>

using std::endl;

#define ll long long int
#define FOR(a, s, n) for(int a = s; a < n; ++a)
#define LEP(a, n) for(int a = 0; a < n; ++a)
#define INF 1145141919810
#define MOD 1000000007
#define OUT std::cout
#define IN std::cin
#define itn int
#define fro for
#define sdt std
#define asn ans

int A, B, buf;

int main()
{
	LEP(a, 4)
	{
		IN >> buf;
		A += buf;
	}
	LEP(a, 4)
	{
		IN >> buf;
		B += buf;
	}

	OUT << std::max(A, B) << endl;
	
	return 0;
}

Measured memory_bytes: 3072
#include <iostream>

using namespace std;

int main(){
  string s, t;
  int a, b;
  string u;
  std::cin >> s >> t;
  std::cin >> a >> b;
  std::cin >> u;
  std::cout << ((s == u)? a-1 : a) << ' ' << ((t == u)? b-1 : b) << '\n';
  return 0;
}


Measured memory_bytes: 888
"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

N = int(input())
S = input()

E_list = [0] * N 
W_list = [0] * N

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list[i] = n
    else:
        W_list[i] = n

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list[i] = n
    else:
        E_list[i] = n

print(min([e+w for e,w in zip(E_list, W_list)]))

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

int compare_int(const void *a,const void *b){
		return *(int*)a-*(int*)b;
}

struct tm{
		int a;
		int n;
};

int main(){
		int n,i,c=0,l[2001],j;
		long long ans=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)scanf("%d",&l[i]);
		qsort(l,n,sizeof(int),compare_int);
	/*	struct tm ll[1010];
		ll[0].a=l[0];
		ll[0].n=1;
		for(i=1;i<n;i++){
				if(l[i]!=l[i-1]){
						ll[++c].a=l[i];
						ll[c].n=0;
				}
				ll[c].n++;
		}c++;
		for(i=0;i<c;i++){
				for(j=i+1;j<c;j++){
						int r=c,le=j,q=0,k;
						while(r-le>1){
								int mid=(r+le)/2;
								if(ll[mid].a>=ll[i].a+ll[j].a)r=mid;
								else le=mid;
						}
						for(k=j+1;k<r;k++)q+=ll[k].n;
						ans+=(q*ll[i].n*ll[j].n);
						ans+=ll[i].n*ll[j].n*(ll[j].n-1)/2;
						if(ll[i].a*2>ll[j].a)ans+=ll[j].n*ll[i].n*(ll[i].n-1)/2;
				}
		}*/
		for(i=0;i<n;i++){
				for(j=i+1;j<n;j++){
						int r=n,le=j,q=0;
						while(r-le>1){
								int mid=(r+le)/2;
								if(l[mid]>=l[i]+l[j])r=mid;
								else le=mid;
						}
						ans+=le-j;
				}
		}
		printf("%lld\n",ans);
		return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt();
    vector <double > v(n);
    generate(all(v),nxt);
    double test=0;
    for(int i=0;i<n;i++)
    {
        test+=(1/v[i]);
    }
    test=1/test;
    cout<<setprecision(15)<<test<<endl;
    
    
    return 0;   
}


 
 


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

#define ll long long
#define forn(i, n) for (ll i = 0; i < (ll) n; ++i)
#define sz(a) static_cast<int>(a.size())

char buff[(int) 2e6 + 17];
const ll inf = (ll) 1e9 + 7ll;

const int maxn = (int) 2e5 + 17;

int n;
string s;
int ps[maxn];

bool read() {
    if (scanf("%s", buff) != 1)
        return false;

    return true;
}

void solve() {
    s = buff;
    n = sz(s);
    s = "#" + s;
    unordered_map<int, int> dp;
    dp.rehash(2281488);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        ps[i] = ps[i - 1] ^ (1 << (s[i] - 'a'));

        if (!dp.count(ps[i]))
            dp[ps[i]] = inf;

        for (int j = 0; j < 26; ++j) {
            auto t = ps[i] ^ (1 << j);

            if (dp.count(t))
                dp[ps[i]] = min(dp[ps[i]], dp[t] + 1);
        }
    }

    printf("%d\n", max(1, dp[ps[n]]));
}

int main() {
#if SEREZHKA
    freopen("file.in", "r", stdin);
#endif

    while (read())
        solve();

    return 0;
}


Measured memory_bytes: 25788
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int n, a, b;
	scanf("%d %d %d", &n, &a, &b);

	int Acost = n * a;
	int Bcost = b;

	if (Acost < Bcost) {
		printf("%d", Acost);
	}
	else {
		printf("%d", Bcost);
	}
}

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

int cnt, n, ab, a, b;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j < s.size(); j++)
			if (s[j] == 'B' && s[j-1] == 'A')
				cnt++;
		if (s[0] == 'B' && s[(int)s.size() - 1] == 'A')
			ab++;
		else if (s[0] == 'B')
			b++;
		else if (s[(int)s.size() - 1] == 'A')
			a++;
	}
//	cout << a << ' ' << b << ' ' << ab << endl;
	if (!a && !b) {
		cout << cnt + max(0, ab - 1);
	}
	else if (!a || !b) {
		cout << cnt + ab;
	}
	else
		cout << cnt + ab + min(a, b);
	cout << endl;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
constexpr int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

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

int main() {
    int X;
    cin >> X;
    int i, sum = 0;
    for(i = 1; sum < X; i++) {
        sum += i;
    }
    i--;
    cout << i << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 100000000000
#define int long long int
#define hell (int)(1e9+7)

using namespace std;

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    for(int j=1;j<n-1;j++){
        int r,g,b;
        r=g=b=0;
        for(int k=j+1;k<n;k++){
            r+=s[k]=='R';
            g+=s[k]=='G';
            b+=s[k]=='B';
        }
        for(int i=j-1;i>=0;i--){
            if(s[i]==s[j])
                continue;
            if(s[i]=='R'){
                if(s[j]=='B')
                    ans+=g;
                else
                    ans+=b;
            }
            else if(s[i]=='G'){
                if(s[j]=='B')
                    ans+=r;
                else
                    ans+=b;
            }
            else{
                if(s[j]=='R')
                    ans+=g;
                else
                    ans+=r;
            }
            if(j+j-i<n)
                ans-=s[j+j-i]!=s[i]&&s[j+j-i]!=s[j];
        }
    }
    cout<<ans;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}


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

#define UN unsigned
#define ll long long
#define mod 1000000007
#define pii pair<int, int>
#define pb push_back
//~ #define x first
//~ #define y second
const int N = 500000;

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);
	
	ll n = 0, cnt = 0, p = 2;
	cin >> n;

	while((p*p) <= n){
		ll e = 0;
		while(n%p == 0){
			e++;
			n /= p;
		}
		ll m = 1, cnt2 = 1;
		while(m*(m+1) <= 2LL * e){
			m++;
			cnt++;
		}
		cnt2--;
		cnt += cnt2;
		p++;
	}

	if(n != 1) cnt++;

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 3696
N = int(input())
A = list(map(int, input().split()))
S = []
cnt = 0
for i in range(N):
    cnt += A[i]
    S.append(cnt)
S.sort()
n = S[0]+1
num = 0
ans = 0
for i in range(N):
    if S[i] == 0:
        ans += 1
    if n == S[i]:
        num += 1
    else:
        ans += (num-1)*num//2
        n = S[i]
        num = 1
ans += (num-1)*num//2
print(ans)

Measured memory_bytes: 26136
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define LOOP_IT(s) for(auto it=(s).begin();it!=(s).end();++it)

bool chk(string s)
{
    string sr=s;
    reverse(all(sr));
    return (sr==s);
}
int main(int argc,char* argv[])
{
    ZOOM

    string s,s1="",s2="";
    cin>>s;
    int n = s.size();

    for(int i=0;i<n;++i)
    {
        if(i<(n-1)/2)
            s1.pb(s[i]);
        if(i>=(n+3)/2-1)
            s2.pb(s[i]);
    }




    if(chk(s1)&&chk(s2)&&chk(s))
        cout<<"Yes";
    else
        cout<<"No";


    return 0;
}



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

using namespace std;

int n, k;

vector<pair<int, int>> points;

long long const inf = LLONG_MAX;

long long getInterior(int x1, int y1, int x2, int y2) {

	long long leftx = min(x1, x2);
	long long lefty = min(y1, y2);
	long long rightx = max(x1, x2);
	long long righty = max(y1, y2);

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		int x = points[i].first;
		int y = points[i].second;
		if (x >= leftx && x <= rightx && y >= lefty && y <= righty)
			++cnt;
	}

	if (cnt >= k) {
		return (rightx - leftx) * (righty - lefty);
	} else
		return LLONG_MAX; 

}

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

	cin >> n >> k;

	points.resize(n);

	for (int i = 0; i < n; ++i) {
		cin >> points[i].first >> points[i].second;
	}

	long long answer = inf;

	vector<pair<int, int>> iterate(n * n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			iterate[i * n + j] = make_pair(points[i].first, points[j].second);
		}
	}

	for (int left = 0; left < n * n; ++left) {
		for (int right = 0; right < n * n; ++right) {
			answer = min(answer, getInterior(iterate[left].first, iterate[left].second, iterate[right].first, iterate[right].second));
		}
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

int gcd(int a, int b)
{
    if (a < b)
        int c = a, a = b, b = c;

    return a % b == 0 ? b : gcd(b, a % b);
}

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

    int n, a[112345];

    int g[112345];

    cin >> n;
    REP(i, n)
    cin >> a[i];

    g[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        g[i] = gcd(g[i - 1], a[i]);
    }

    int h[112345];
    h[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        h[i] = gcd(h[i + 1], a[i]);
    }

    int res = max(g[n - 2], h[1]);

    for (int i = 1; i < n - 1; i++)
    {
        res = max(res, gcd(g[i - 1], h[i + 1]));
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = (n) - 1; i >= 0; i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define all(ar) ar.begin(), ar.end()
#define rall(ar) ar.rbegin(), ar.rend()
#define sz(x) ((long long)x.size())
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
 
auto clk=clock();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll INF = 1e18L+5;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
 
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<int> vint;
typedef vector<string> vs;
typedef vector<vi> vvi;

ll modexp(ll base,ll power){
    if(base==0)
        return 0ll;
    if(power==0)
        return 1ll;
    ll res=1;
    while(power){
        if(power&1)
            res = (res*base)%MOD;
        base = (base*base)%MOD;
        power /= 2;
    }
    return res;    
}
 
void solve(){
    ll n;
    cin>>n;
    vi x;
    vi y;
    rep(i,n){
    	ll a,b;
    	cin>>a>>b;
    	x.pb(a+b);
    	y.pb(a-b);
    }
    ll maxx = *max_element(all(x));
    ll minx = *min_element(all(x));
    ll maxy = *max_element(all(y));
    ll miny = *min_element(all(y));
    // debug(maxx);
    // debug(minx);
    // debug(maxy);
    // debug(miny);

    cout<<max(maxx-minx,maxy-miny);
}
    
 
int main () 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<setprecision(11);
    ll t = 1;
    // cin>>t;
    while(t--)
        solve();
 
    // cout<<endl<<endl<<"Time elapsed: "<<((double)(clock()-clk)/CLOCKS_PER_SEC)*1000<<"ms"<<endl;
    return 0;
}

Measured memory_bytes: 6764
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
using ll = long long;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	string s;
	cin>>n>>s;
	ll res=1;
	for(int i=1; i<n; ++i){
		res+=(s[i]!=s[i-1]);
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 512
#include<stdio.h>

int main(void){
	int n,i,j,k,play[200][4];
	scanf("%d",&n);
	for(i=0; i<n; i++){
		scanf("%d%d%d",&play[i][0],&play[i][1],&play[i][2]);
		play[i][3]=0;
	}
	for(i=0; i<3; i++){
		for(j=0; j<n; j++){
			for(k=0; k<n; k++){
				if(play[j][i]==play[k][i] && j!=k){
					play[j][3]-=play[j][i];
					break;
				}
			}
			play[j][3]+=play[j][i];
		}
	}
	for(i=0; i<n; i++){
		printf("%d\n",play[i][3]);
	}
	return 0;
}

Measured memory_bytes: 596
# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

average = 0
for i in range(n):
    average += a[i]
average = average / n

ans = 0
tmp = 10000
for i in range(n):
    if abs(a[i] - average) < abs(tmp - average):
        tmp = a[i]
        ans = i
print(ans)


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

int main()
{
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    
    vector<int> inputs = { a, b, c, d, e };
    for (int i = 0; i < inputs.size(); ++i) {
        if (inputs[i] == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3564
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
const double eps=1e-10;
double adj[21][21];
double hero[20];
bool visited[20]={false};
#define MAOU 20

bool backTrack(int last,double r,int now,int n,
	   bool *visited){
  rep(i,n){
    if ( visited[i]==false && adj[MAOU][i]<=r)return false;
    if ( visited[i]==false &&  adj[MAOU][i]<=r+adj[last][i])return false;
  }
  if ( now == n)return true;
  
  rep(i,n){
    if ( visited[i]==true)continue;
    visited[i]=true;
    if ( backTrack(i,r+adj[last][i],now+1,n,visited))return true;
    visited[i]=false;
  }
  return false;
}

inline double dist(int x,int y){
  return sqrt(x*x+y*y);
}

inline int solve(int n,int *x,int *y,int rx,int ry,int mx,int my){
  rep(i,n){
    adj[i][i]=0;
    adj[MAOU][i]=adj[i][MAOU]=dist(x[i]-rx,y[i]-ry);
    REP(j,i+1,n){
      adj[i][j]=adj[j][i]=dist(x[i]-x[j],y[i]-y[j]);
    }
    hero[i]=dist(mx-x[i],my-y[i]);
    if ( hero[i]+eps>adj[MAOU][i])return false;
    visited[i]=false;
  }
  
  rep(i,n){
    visited[i]=true;
    if ( backTrack(i,hero[i],1,n,visited))return true;
    visited[i]=false;
  }
  return false;
}

main(){
  int n,mx,my,rx,ry;
  while(scanf("%d%d%d%d%d",&n,&mx,&my,&rx,&ry) && n){
    int x[n],y[n];
    rep(i,n)scanf("%d%d",&x[i],&y[i]);
    if ( solve(n,x,y,rx,ry,mx,my))puts("YES");
    else puts("NO");
  }
}

Measured memory_bytes: 844
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    ll K;
    cin >> K;

    queue<ll> q;
    for (int i = 1; i <= 9; i++) {
        q.push(i);
    }

    int cnt = 0;

    while (true) {
        ll x = q.front();
        q.pop();
        cnt++;
        // printf("%lld\n", x);

        if (cnt == K) {
            cout << x << endl;
            break;
        }

        int d = x % 10;
        x *= 10;

        if (d > 0) {
            q.push(x + d - 1);
        }

        q.push(x + d);

        if (d < 9) {
            q.push(x + d + 1);
        }
    }

    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>
#include <chrono>
#include <set>


#define rep(i,p,q) for(ll i = p;i < q;i++)
#define ll long long

using namespace std;

vector<vector<ll>> graph;
vector<ll> query;
vector<ll> ans;
vector<ll> visited;


const long long MAX_N = 1 << 17;

long long dat[2 * MAX_N - 1];

ll ecd(ll a, ll b) {
	if (a < b) swap(a, b);
	if (b == 0) return a;
	else {
		return ecd(b, a % b);
	}
}

ll pow(ll a, ll b) {
	vector<ll> d = vector<ll>((ll)(log(b)) + 2);
	d[0] = a;
	rep(i, 1, d.size()) d[i] = d[i - 1] * d[i - 1];
	ll ret = 1;
	rep(i, 0, log(b) + 1) {
		if (b & 1 << i) ret *= d[i];
	}
	return ret;
}

const long MAX = 1000001;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//145 D
int main(void) {
	ll x, y;
	cin >> x >> y;
	ll ans = 0;
	COMinit();
	rep(i, 0, x+1) {
		ll j = x - i;
		if (j % 2 == 1)continue;
		j /= 2;
		if (2 * i + j == y) {
			ans += COM(i + j, i);
			ans %= MOD;
		}
		
	}
	cout << ans << endl;
}

Measured memory_bytes: 24832
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
int main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a%2==0||b%2==0||c%2==0)
	{
		printf("0");
	}
	else
	{
		printf("%lld",min(a*b,min(a*c,b*c)));
	}
	return 0;
}

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

  int N , M ;
  double ans = 0 ;
  ll B = 0 ;
  int count = 0 ;
  cin >> N >> M ;
  int A[N] ;
  rep(i,N){
    cin >> A[i] ;
    B += A[i] ;
  }
  ans = (double) 1 /(4*M) ;
  //cout << ans << endl;
  rep(i,N){
    if( (double)A[i]/B >= ans )count++ ;
  }
  if(count >= M )cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main(int,char**){
	std::vector<int> vec(10);
	for(int i(0);i<10;++i) std::cin >> vec[i];
	std::sort(vec.begin(),vec.end());
	std::cout << vec[9] << std::endl<< vec[8] << std::endl<< vec[7] << std::endl;
	return 0;
}

Measured memory_bytes: 0
H, W = gets.split.map(&:to_i)
as = H.times.map{gets.chomp}

huse = {}
wuse = {}
H.times do |i|
    W.times do |j|
        if as[i][j] == '#'
            huse[i] = true
            wuse[j] = true
        end
    end
end

huse.keys.sort.each do |i|
    puts wuse.keys.sort.map{|j| as[i][j]}.join
end

Measured memory_bytes: 1916
// AOJ DSL_2_G RSQ and RAQ
// 2018.5.18 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(long long n)
{
	int i;
	char ob[40];

	if (!n) pc('0');
	else {
		i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
		while (i--) pc(ob[i]);
	}
	pc('\n');
}

#define MAX_N 100005

int s, t, x;
long long ans;

typedef struct { int l, r; long long w; int f; } NODE;
NODE node[1<<19];

void segTree(int k, int l, int r) 
{
	int m;

	node[k].l = l, node[k].r = r;
	if (node[k].l == node[k].r) return;
	m = (l + r) >> 1;
    segTree( k << 1, l, m);
    segTree((k << 1) | 1, m+1, r);
}

void down(int k) 
{
    node[ k << 1     ].f += node[k].f;
    node[(k << 1) | 1].f += node[k].f;
    node[ k << 1     ].w += (long long)node[k].f * (node[ k << 1     ].r - node[ k << 1     ].l + 1);
    node[(k << 1) | 1].w += (long long)node[k].f * (node[(k << 1) | 1].r - node[(k << 1) | 1].l + 1);
    node[k].f = 0;
}

void ask_point(int k)
{
	int m;

    if (node[k].l == node[k].r) {
        ans = node[k].w;
        return;
    }
    if (node[k].f) down(k);
    m = (node[k].l + node[k].r) >> 1;
    if (s <= m) ask_point(k << 1);
    else ask_point((k << 1) | 1);
}

void change_point(int k) 
{
	int m;

    if (node[k].l == node[k].r) {
        node[k].w += x;
        return;
    }
    if (node[k].f) down(k);
    m = (node[k].l + node[k].r) >> 1;
    if (s <= m) change_point(k << 1);
    else change_point((k << 1) | 1);
    node[k].w = node[k << 1].w + node[(k << 1) | 1].w;
}

void ask_interval(int k)
{
	int m;

    if (node[k].l >= s && node[k].r <= t) {
        ans += node[k].w;
        return;
    }
    if (node[k].f) down(k);
    m = (node[k].l + node[k].r) >> 1;
    if (s <= m) ask_interval(k << 1);
    if (m < t) ask_interval((k << 1) | 1);
}

void change_interval(int k) 
{
	int m;

	if (node[k].l >= s && node[k].r <= t) {
        node[k].w += (node[k].r - node[k].l + 1) * x;
        node[k].f += x;
        return;
    }
    if (node[k].f) down(k);
    m = (node[k].l + node[k].r) >> 1;
    if (s <= m) change_interval(k << 1);
    if (m < t) change_interval((k << 1) | 1);
    node[k].w = node[k << 1].w + node[(k << 1) | 1].w;
}

int main()
{
	int n, q, op;

	n = in();
    segTree(1, 1, n);

	q = in();
	while (q--) {
		op = gc() & 1, gc();
		if (op) {
			ans = 0;
			s = in(), t = in();
			if (s == t) ask_point(1);
			else ask_interval(1);
			out(ans);
		} else {
			s = in(), t = in(), x = in();
			if (s == t) change_point(1);
			else change_interval(1);
		}
	}
	return 0;
}



Measured memory_bytes: 7764
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

int main() {

    int A, B, res;
    cin >> A >> B;
    B -= 1;
    A -= 1;
    res = B / A + (B % A ? 1:0);
    cout << res;
    return 0;
}

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

typedef unsigned long long ll;

struct Rail {
  int from, to;
  int yen, sunuke;
  ll cost;

  bool operator<(const Rail &r) const {
    return this->cost>r.cost;
  }
};

const int N = 100001;
vector<Rail> adj_list[N];

vector<ll> dijkstra(int start, bool changed) {
  vector<ll> res(N);
  bool visited[N] = { 0 };

  priority_queue<Rail> q;
  Rail s = { start, start, 0, 0, 0 };
  q.push(s);
  while (!q.empty()) {
    Rail run_rail = q.top();
    q.pop();

    int c = run_rail.to;
    if (visited[c])
      continue;
    visited[c] = true;
    res[c] = run_rail.cost;

    for (auto r : adj_list[c]) {
      r.cost = run_rail.cost + (changed ? r.sunuke : r.yen);
      q.push(r);
    }
  }

  return res;
}

int main() {
  int n, m, start, goal;
  cin >> n >> m >> start >> goal;
  start--, goal--;
  for (int i=0; i<m; i++) {
    int u, v, yen, sunuke;
    scanf("%d %d %d %d", &u, &v, &yen, &sunuke);
    u--, v--;

    Rail r = { u, v, yen, sunuke, 0 };
    adj_list[u].push_back(r);
    Rail r2 = { v, u, yen, sunuke, 0 };
    adj_list[v].push_back(r2);
  }
  vector<ll> yen_min = dijkstra(start, false);
  vector<ll> sunuke_min = dijkstra(goal, true);

  vector<ll> res(n);
  ll max_sunuke = 0;
  for (int i=n-1; i>=0; i--) {
    ll s = 1000000000000000 - yen_min[i] - sunuke_min[i];
    max_sunuke = max(max_sunuke, s);
    res[i] = max_sunuke;
  }
  for (auto r : res) {
    cout << r << endl;
  }
  return 0;
}



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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  ll n; cin >> n;
  ll front = 0, back = 0;
  vll a(n); rep(i, n) { cin >> a[i]; back += a[i]; }
  ll ans = MAX;
  for(ll i = 0;i < n;i++)
  {
    front += a[i];
    back -= a[i];
    ans = min(ans, llabs(front - back));
  }
  fin(ans)
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}


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

using namespace std;

int n;

int mcxi2int(string str,int pt)
{
	if( pt >= str.size() )
		return 0;
	if( str[pt] >= '2' && str[pt] <= '9' )
		pt++;

	int d;

	if(str[pt] == 'm')
		d = 1000;
	else if(str[pt] == 'c')
		d = 100;
	else if(str[pt] == 'x')
		d = 10;
	else
		d = 1;

	if( pt-1 >= 0 && str[pt-1] >= '2' && str[pt-1] <= '9')
		return d*(str[pt-1]-'0') + mcxi2int(str, pt+1);
	else
		return d + mcxi2int(str, pt+1);
}

string int2mcxi(int k)
{
	int i = k;
	string str = "";

	if( i >= 1000 )
	{	
		if( i/1000 >= 2)
			str += '0' + i/1000;

		str += 'm';
	}

	i = i%1000;

	if( i >= 100 )
	{
		if( i/100 >= 2)
			str += '0' + i/100;

		str += 'c';
	}

	i = i%100;

	if( i >= 10 )
	{
		if( i/10 >= 2)
			str += '0' + i/10;

		str += 'x';
	}

	i = i%10;

	if( i >= 1 )
	{
		if( i >= 2)
			str += '0' + i;

		str += 'i';
	}
	

	return str;
}


int main()
{
	cin >> n;

	for( int i = 0; i < n; i++)
	{
		string mcxi1, mcxi2;

		cin >> mcxi1 >> mcxi2;

		string out = int2mcxi(mcxi2int(mcxi1, 0) + mcxi2int(mcxi2, 0));

		cout << out << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
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};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
// << fixed << setprecision
// --------------------------------------
ll n, x, m;

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

  cin >> n >> x >> m;

  ll ans = x;

  vector<ll> memo(m + 1, -1);
  vector<ll> sum;
  sum.push_back(0);
  sum.push_back(x);
  memo[x] = 1;
  ll xx = x;
  REP(i, min(n - 1, m + 10)) {
    xx = xx * xx % m;
    if(memo[xx] != -1) {
      ans += xx;
      sum.push_back(ans);
      ans += ((n - (i + 2)) / (i + 2 - memo[xx])) * (sum[i + 2] - sum[memo[xx]]);
      ans += sum[memo[xx] + ((n - (i + 2)) % (i + 2 - memo[xx]))] - sum[memo[xx]];
      break;
    } else {
      ans += xx;
      sum.push_back(ans);
      memo[xx] = i + 2;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 4620
def sumd(x):
    s = str(x)
    ret = 0
    for i in range(len(s)):
        ret += int(s[i])
    return ret


n, a, b = map(int, input().split())
ans = 0
for i in range(1, n+1):
    if a <= sumd(i) <= b:
        ans += i
print(ans)

Measured memory_bytes: 3060
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    S = input().rstrip()
    Q = int(input())

    dq = deque(S)

    reverse = 0

    for _ in range(Q):
        Query = iter(input().rstrip().split())
        T = next(Query)
        if T == '1':
            reverse = 1 - reverse
            # # Sの前後を反転する
            # if len(dq) >= 2:
            #     head = dq.popleft()
            #     tail = dq.pop()
            #     dq.appendleft(tail)
            #     dq.append(head)

        else:
            F, C = Query
            if F == '1':
                # Sの先頭にC
                if reverse:
                    dq.append(C)
                else:
                    dq.appendleft(C)

            else:
                # Sの末尾にC
                if reverse:
                    dq.appendleft(C)
                else:
                    dq.append(C)

    if reverse:
        dq = reversed(list(dq))

    res = ''.join(dq)
    print(res)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 10356
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX=500000;
const int NIL=-1;

class node
{
public:
	int loc;//location
	int l;
	int r;
};

class point
{
public:
	int id;
	int x;
	int y;
	point(){}
	point(int inid,int inx,int iny):id(inid),x(inx),y(iny){}
};

int n;
point P[MAX];
node T[MAX];
int np=0;

bool lessX(const point &p1,const point &p2)
{
	return p1.x<p2.x;
}
bool lessY(const point &p1,const point &p2)
{
	return p1.y<p2.y;
}

int make2Dtree(int l,int r,int depth)
{
	if(l>=r)return NIL;
	int mid=(l+r)/2;
	int t=np++;
	
	if(depth%2==0)sort(P+l,P+r,lessX);
	else sort(P+l,P+r,lessY);
	
	T[t].loc=mid;
	T[t].l=make2Dtree(l,mid,depth+1);
	T[t].r=make2Dtree(mid+1,r,depth+1);
	
	return t;
}

void find(int v,int sx,int tx,int sy,int ty,int depth,vector<int> &ans)
{
	int x=P[T[v].loc].x;
	int y=P[T[v].loc].y;
	if(sx<=x&&x<=tx&&sy<=y&&y<=ty)ans.push_back(P[T[v].loc].id);
	
	if(depth%2==0)
	{
		if(T[v].l!=NIL&&sx<=x)find(T[v].l,sx,tx,sy,ty,depth+1,ans);
		if(T[v].r!=NIL&&x<=tx)find(T[v].r,sx,tx,sy,ty,depth+1,ans);
	}
	else
	{
		if(T[v].l!=NIL&&sy<=y)find(T[v].l,sx,tx,sy,ty,depth+1,ans);
		if(T[v].r!=NIL&&y<=ty)find(T[v].r,sx,tx,sy,ty,depth+1,ans);
	}
	
	return;
}

int main() {
	cin>>n;int x,y;
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		P[i]=point(i,x,y);
		T[i].l=T[i].r=NIL;
	}
	np=0;
	int root=make2Dtree(0,n,0);
	int q;cin>>q;
	int sx,tx,sy,ty;
	vector<int> ans;
	for(int i=0;i<q;i++)
	{
			scanf("%d%d%d%d",&sx,&tx,&sy,&ty);
			ans.clear();
			find(root,sx,tx,sy,ty,0,ans);
			sort(ans.begin(),ans.end());
			for(int j=0;j<ans.size();j++)printf("%d\n",ans[j]);
			printf("\n");
	}
	return 0;
}



Measured memory_bytes: 14528