akhauriyash/Code-Regression huggingface dataset:
/*
    WRITER:kakitamasziru/OxOmisosiru
*/
#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 <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
//#include <unordered_map> // unordered_map
//#include <unordered_set> // unordered_set
#include <bitset> // bitset
//#include <cctype> // isupper, islower, isdigit, toupper, tolower
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1001001000;
const int MOD = 1000000007;
typedef pair<long,long> P;
//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}
long long nCr(long long n, long long r) {
    long long A = 1, B = 1;
    //Aが分子Bが1/r!
    //n!はi = 1;i<=nでする
    for (long long i = n-r+1; i <= n; i++) {
        A = A * i % MOD;
    }
    for (long long i = 1; i <= r; i++) {
        B = B * i % MOD;
    }
    B = mod_pow(B, MOD - 2);
    B %= MOD;
    //Bは割るのではなく掛ける
    return (A * B) % MOD;
}

int main() {
    int N;cin >> N;
    long long ans = 0;
    for(int i = 1;i<=N;i++){
        if(i%3 == 0 || i%5 == 0){
        }
        else ans += i;
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef long double ld;

using namespace std;

const ll maxn = 200 * 1001;
const ll INF = 1e18;
const ll mod = 1e9+7;

vector<ll> g[maxn];
ll a[maxn], d[maxn];
ll n , m , k;

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

    cin>> n; ll F = 1;
    for(ll i = 0; i < n; i++)
    {
	    cin>> a[i];
		if(i && a[i] != a[i-1])
			F = 0; 
	}
	if(F)
		return cout<< n, 0;
    reverse(a, a+n);

    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[j-1] <= a[i] && a[i] <= d[j])
            d[j] = a[i];
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (d[i] < INF)
            ans = i;
    }

    cout<< ans;
}







Measured memory_bytes: 6912
import java.util.Scanner;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		int x = Integer.parseInt(a+b);
		for(int i=0; i<1000; i++){
			if(i*i == x){
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");
 
	}
}

Measured memory_bytes: 21716
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<functional>
#include<map>
#include<iomanip>
#include<limits>
#include<unordered_set> 
#include<cmath>
using namespace std;
//long long p = 998244353;
long long p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define qin pair<pin,int>
#define V vector
#define Endl endl
#define veb vector<bool>
#define fcout cout << fixed << setprecision(15)
#define rev(s) reverse(s.begin(),s.end())
#define lower(h,val) lower_bound(h.begin(),h.end(),val)-h.begin()
#define upper(h,val) upper_bound(h.begin(),h.end(),val)-h.begin()
int max_kai = 150000;
vel kai(max_kai, 1);
vel inv_kai;
int rui(int a, int n, int mod) {
    if (n == 0) { return 1 % mod; }
    int x = rui(a, n / 2, mod);
    x *= x; x %= mod;
    if (n % 2 == 1) { x *= a; x %= mod; }
    return x;
}
vel pa;
int root(int x) {
    if (pa[x] == -1) { return x; }
    int ans = root(pa[x]); pa[x] = ans;
    return ans;
}
void marge(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) { pa[x] = y; }
}
int gcd(int x, int y) {
    if (x < y) { return gcd(y, x); }
    if (y == 0) { return x; }
    return gcd(y, x % y);
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
vel uni(vel x) {
    if (x.size() == 0) { return x; }
    sor(x);
    int n = x.size();
    vel ans(1, x[0]);
    for (int j = 1; j < n; j++) {
        if (x[j - 1] != x[j]) { ans.push_back(x[j]); }
    }
    x = ans;
    return x;
}
void pr(vel& v) {
    int n = v.size();
    if (n != 0) {
        cout << v[0];
        rep(i, n - 1) {
            cout << " " << v[i + 1];
        }
        cout << endl;
    }
}
signed main(){
    int n; cin >> n;
    int ans = 0;
    rep(i, n) {
        int x; cin >> x;
        ans += x - i-1;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3728
#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int ans[maxn];
int main (){
    int n;
    cin>>n;
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                int x=i*i+j*j+k*k+i*j+i*k+j*k;
                ans[x]+=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf ("%d\n",ans[i]);
    }





}


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

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

#define vint(v, n) vector<int> v(n); REP(i,n) cin >> v[i];
#define vvint(v, w, n) vector<int> v(n); vector<int> w(n); REP(i,n) cin >> v[i] >> w[i];
#define vlint(v, n) vector<ll int> v(n); REP(i,n) cin >> v[i];
#define vdouble(v, n) vector<double> v(n); REP(i,n) cin >> v[i];
#define vvdoube(v, n1, n2) vector<vector<double> > v(n1, vector<double>(n2, 0)); REP(i,n1) REP(j,n1) cin >> v[i][j];
#define string(x) string x; cin >> x;
#define vstring(v, n) vector<string> v(n); REP(i,n){string a; std::cin >> a; v.push_back(a); }

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end(), std::greater<int>()
#define len(v) (v).length()
#define FIND(s, n) (s.find(n) != s.end())
#define SORT(a) sort(all(a))

static const string abet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
static const long long MOD = 1000000007;
static const double PI=3.1415926535897932;
static const int INF = 0x3f3f3f3f;
static const int INFTY = (1 << 29);
static const long long LINFTY = (1LL << 32);

static const int dy4[]={0, 0, 1, -1};
static const int dx4[]={1, -1, 0, 0};
static const int dx8[] = {1, 1, 1, 0, 0, -1, -1, -1};
static const int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

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

  int N;
  cin >> N;
  long long num = 1;
  REP(i, N){
    num %= MOD;
    num *= i+1;
    num %= MOD;
  }
  cout << num << endl;

}


Measured memory_bytes: 256
/*
 *  AUTHOR : MANAV PATEl
*/
#include<bits/stdc++.h>
#include<functional>
//#include<boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

namespace fastio {

	template <class T> istream &operator>>(istream &os, vector<T> & vec) {
		for (auto &u : vec)os >> u;
		return os;
	}
	template <class T> ostream &operator<<(ostream &os, const vector<T> & vec) {
		for (auto &u : vec)os << u << " ";
		return os;
	}
	template<class T1, class T2> inline istream& operator>>(istream& os, pair<T1, T2>& p) {
		return os >> p.first >> p.second;
	}
	template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
		return os << p.first << " " << p.second;
	}
	template <class T> ostream &operator<<(ostream &os, set<T> & con) {
		for (auto &u : con) os << u << " ";
		return os;
	}
	void re() {}
	template <typename T, typename... args> void re(T& x, args&... tail) {
		cin >> x;
		re(tail...);
	}
	void pr() {}
	template <typename T> void pr(const T& x) {
		cout << x;
	}
	template <typename T, typename... args> void pr(const T& x, const args&... tail) {
		cout << x << " ";
		pr(tail...);
	}
	template <typename... args> void prln(const args&... tail) {
		pr(tail...);
		cout << "\n";
	}
}
using namespace fastio;

typedef long long int ll;
typedef long double ld;

const ll mod = 1e9+7;
const ll mod1 = 998244353;

#define fill(a)  memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back

int main()
{
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	cin.tie(0);
	ll n, a;
  	cin >> n >> a;
  	a = 2*a + 1;
  	cout << ceil((ld)n/a);
}



Measured memory_bytes: 512
import sys
import itertools
import bisect
from operator import itemgetter
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

N,M = IL()

ans = N*(N-1)//2 + M*(M-1)//2
print(ans)

Measured memory_bytes: 38384
n,q = map(int,input().split())
s = input()
ios = [0]*n
for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ios[i] += 1
    ios[i+1] = ios[i]
ios = [0] + ios
for i in range(q):
    l,r = map(int,input().split())
    print(ios[r-1]-ios[l-1])

Measured memory_bytes: 53976
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,p[N],q[N],t[N],f[N],a,b,tot;
void dfs(int cur)
{
    if(a&&b)return ;
    if(cur==n+1){
        tot++;
        int i;for(i=1;i<=n;i++)if(t[i]!=p[i])break;
        if(i==n+1)a=tot;
        for(i=1;i<=n;i++)if(t[i]!=q[i])break;
        if(i==n+1)b=tot;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!f[i]){
            t[cur]=i;
            f[i]=1;
            dfs(cur+1);
            f[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++)cin>>q[i];
    dfs(1);
    cout<<abs(a-b);
    return 0;
}

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

using namespace std;

 vector<bool> arr;

void Eratosthenes(int N){
    arr.resize(N+1);
	for(int i = 0; i < N; i++){
		arr[i] = 1;
	}
    arr[0] = 0; arr[1] = 0;
	for(int i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(int j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}

}

int main(){
 int Q; cin >> Q;
 Eratosthenes(1000010);
  int sum[1000010]; sum[0] = 0; sum[1] = 0;
  for(int i = 2; i < 1000010; i++){
    if(arr[i] && arr[(i+1)/2]){sum[i] = sum[i-1] + 1;}
    else{ sum[i] = sum[i-1];}}
  //sum[x] はx以下の条件を満たす整数の総数
  for(int i = 0; i < Q; i++){
    int l,r; cin >> l >> r;
       cout << sum[r] - sum[l-1] << endl;}
  return 0;}


Measured memory_bytes: 4608
#include<bits/stdc++.h>
#define ll long long int 
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a;i<n;i++)
#define ve vector
#define ss second 
#define ff first
#define pf pop_front
#define pob pop_back
#define psf push_front
#define it vector<ll>:: iterator
#define res(x) cout<<x<<'\n'
#define read(t) ll t;cin>>t
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    read(n);
    ll a[n][3];
    f(i,0,n){
        f(j,0,3){
            cin>>a[i][j];
        }
    }
    ll dp[n][3];
    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for(int i=1;i<n;i++){
       dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
       dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
       dp[i][2]=max(dp[i-1][1],dp[i-1][0])+a[i][2];
    }
    int i=n-1;
     if(dp[i][0]>dp[i][1] && dp[i][0]>dp[i][2]){
        cout<<dp[i][0];
    }
    else if(dp[i][1]>dp[i][0] && dp[i][1]>dp[i][2]){
        cout<<dp[i][1];
    }
    else{
    cout<<dp[i][2];
    }
    return 0;
    }

Measured memory_bytes: 8300
loop do
    m0, t0, p0, r = gets.split.map &:to_i
    break if m0 == 0
    submission = (0..t0).map {Hash.new(-1)}

    r.times do
        m, t, p, j = gets.split.map &:to_i
        if j == 0
            submission[t][p] = m - submission[t][p] - 1 
        else
            submission[t][p] -= 20
        end
    end 
    
    point = (1..t0).map do |t| 
        tmp = submission[t].select{|p, m| m >= 0}
        [-tmp.size, tmp.values.inject(0, :+), t]
    end 

    point.sort!
    puts point.group_by{|c, m, _| [c, m]}.map{|_, a| a.map(&:last).sort.reverse * '='} * ',' 
end

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

using ll = long long;
using namespace std;

void solve() {
   ll n, p;
   cin >> n >> p;

   vector <ll> v(n);
   int even = 0;
   int odd = 0;
   for(int i = 0; i < n; i++) {
      cin >> v[i];
      v[i] %= 2;
      even += v[i] == 0;
      odd += v[i] == 1;
   }

   if(odd == 0) {
      if(p == 1) {
         cout << 0 << endl;
      } else {
         cout << (1LL << n) << endl;
      }
   } else {
      cout << (1LL << (n - 1)) << endl;
   }
}


int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solve();
   }
 
   return 0;
}

Measured memory_bytes: 3632
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x[1005],y[1005],p[36],len;
bool f[2];
inline int abs(int a1)
{
	return a1>0?a1:-a1;
}
inline void print(int x1,int y1)
{
	for(int i=1;i<=len;i++)
		if(abs(x1)>abs(y1))
		{
			if(x1>0)
				putchar('R'),x1-=p[i];
			else
				putchar('L'),x1+=p[i];
		}
		else
		{
			if(y1>0)
				putchar('U'),y1-=p[i];
			else
				putchar('D'),y1+=p[i];
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		f[(x[i]+y[i])%2]=1;
	}
	if(f[1]&&f[0])
	{
		printf("-1\n");
		return 0;
	}
	for(int i=30;i>=0;i--)
		p[++len]=(1<<i);
	if(f[0])
		p[++len]=1;
	printf("%d\n",len);
	for(int i=1;i<len;i++)
		printf("%d ",p[i]);
	printf("%d\n",p[len]);
	for(int i=1;i<=n;i++)
	{
		print(x[i],y[i]);
		printf("\n");
	}
}

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

int main(){
    int n; cin >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ans=max(ans,abs(a[i]-a[j]));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

const int DEBUG = 0;

int main(void){
  int h, w, n;
  cin >> h >> w >> n;
  vector<PI> rem(n);
  REP(i, 0, n) {
    int u, v;
    cin >> u >> v;
    v--;
    rem[i] = PI(u, v);
    assert ((u + v) % 2 == 1);
  }
  assert (w % 2 == 0);
  sort(rem.begin(), rem.end());
  VI ary(w);
  REP(i, 0, w / 2) { ary[i] = i * 2; }
  REP(i, 0, w / 2) { ary[w / 2 + i] = w - 1 - 2 * i; }
  REP(i, 0, n) {
    PI t = rem[i];
    int bias = t.first / 2;
    int flipped = t.first % 2;
    int v = t.second;
    int mapped_v = w - 1 - v / 2;
    if (flipped) {
      mapped_v = v / 2;
    }
    int x = mapped_v;
    int y = flipped ? w - 1 - x : w - x;
    assert (0 <= y && y < w);
    x = (x + w - bias % w) % w;
    y = (y + w - bias % w) % w;
    if (DEBUG) { cerr << "x=" << x << ", y=" << y << endl; }
    swap(ary[x], ary[y]);
    if (DEBUG) {
      cerr << "step " << t.first << ":";
      REP(i, 0, w) {
	cerr << " " << ary[i];
      }
      cerr << endl;
    }
  }
  VI inv(w, -100);
  REP(i, 0, w) {
    int bias = (h / 2) % w;
    int flipped = h % 2;
    int mapped_i;
    if (i % 2 == 1) {
      mapped_i = w - 1 - i / 2;
    } else {
      mapped_i = i / 2;
    }
    if (flipped) {
      mapped_i = w - 1 - mapped_i;
    }
    int x = (mapped_i + w - bias % w) % w;
    inv[ary[x]] = i;
    if (DEBUG) {
      cerr << i << " ==> " << x << "(" << ary[x] << ")" << endl;
    }
  }
  REP(i, 0, w) {
    cout << inv[i] + 1 << endl;
  }
}

Measured memory_bytes: 5964
#include <stdio.h>

int main() {
	int inNum1, inNum2;
	
	scanf("%d %d", &inNum1, &inNum2);
	
	if (inNum1 > 1001 || inNum1 < -1001 || inNum2 > 1001 || inNum2 < -1001 ) {
		printf("error\n");
		return 0;
	}
	
	if (inNum1 > inNum2) {
		printf("a > b\n");
	} else if (inNum1 < inNum2) {
		printf("a < b\n");		
	} else {
		printf("a == b\n");		
	}
}


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

int div_sum(int n) {
  int sum = 0;
  while ( n > 0) {
    sum += n % 10;
    n /= 10; 
  }
  return sum;
}


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

  string ans = "No";
  if( n % div_sum(n) == 0 ) ans = "Yes"; 


  cout << ans << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ld = long long;
bool go(vector<ld> v, ld val, int n, int f)
{
	int pieces = f;
	for(int i = 0;i < n;i++)
	{
		if(v[i] <= val)return true;
		int x = (v[i]/val);pieces -= x;
		if(pieces <  0)
			return false;
	}
	return pieces >= 0;
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	while(t--)
	{
		int n,f;
		cin >> n >> f;
		vector<ld> v(n);
		for(ld &x: v)
		{
			cin>>x;
		}
		sort(v.begin(),v.end(),greater<ld>()); 
		ld l = 1,r = 1e9;
		int ans = 0;
		while(l <= r)
		{
			ld mid = (ld)((l+r)/2);
			if(go(v,mid,n,f))ans = mid,r = mid - 1;
			else l = mid + 1;
		}
		cout << ans ;
	}
}


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

int p[100001],s[100001],l,r;
long long f[100001];
int main(){
	int n,e,t;scanf("%d%d%d",&n,&e,&t);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	long long z=2e9;
	for(int i=1;i<=n;i++){
		s[++r]=i;
		for(;2*(p[i]-p[s[l]])>=t;l++)
			z=min(z,f[s[l]-1]-2*p[s[l]]);
		f[i]=f[s[l]-1]+t;
		f[i]=min(f[i],2*p[i]+z);
	}
	cout<<f[n]+e;
}

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


ll L[50], P[50];

int main() {
  ll N,X;
  cin >> N >> X;
  L[0] = 1;
  P[0] = 1;
  for(ll i=1; i<N+1; ++i ) {
    L[i] = 3 + 2 * L[i-1];
    P[i] = 1 + 2 * P[i-1];
  }
  ll ans = 0;
  for(ll i=N; i>0; --i ) {
    if ( X == 1 ) {
      break;
    } else if ( X < L[i-1] + 1 ) {
      X = X - 1;
    } else if ( X == L[i-1] + 1 ) {
      ans += P[i-1] ;
      break;
    } else if ( X <= L[i-1] + 2 ) {
      ans += P[i-1] + 1;
      break;
    } else if ( X < 2*L[i-1] + 2 ) {
      X = X - (L[i-1]+2);
      ans += P[i-1] + 1;
    } else {
      ans += P[i];
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    d, t, s = get_int_multi()
    if d <= t * s:
        print("Yes")
    else:
        print("No")

    #print(time.time() - start)


if __name__ == '__main__':
    main()

Measured memory_bytes: 11088
N = str(int(input()))

if N[-1] == '2':
  print('hon')
elif N[-1] == '4':
  print('hon')
elif N[-1] == '5':
  print('hon')
elif N[-1] == '7':
  print ('hon')
elif N[-1] == '9':
   print('hon')
elif N[-1] == '3':
   print('bon')
else:
   print('pon')


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

int main() {
  int K,A,B;
  cin >>K >>A >>B;
  if(A%K==0){
    cout <<"OK" <<endl;
  }
  else if(B%K==0){
    cout <<"OK" <<endl;
  }
  else{
    for(int i=A; i<B+1; i++){
      if(i%K==0){
        cout <<"OK" <<endl;
        return 0;
      }
    }
    cout <<"NG" <<endl;
  }
}

Measured memory_bytes: 3636
n = int(input())
t = 0
h = 0
for i in range(n):
    li = [x for x in list(input().split())]
    if li[0] < li[1]:
        h += 3
    elif li[0] > li[1]:
        t += 3
    else:
        h += 1
        t += 1
print(t, h)



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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);

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


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c;
    cin >> a>> b>>c;

    if( a + b >= c){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}


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

int main() {
  string a,b,c;cin>>a>>b>>c;
  cout<<(char)toupper(a[0])<<(char)toupper(b[0])<<(char)toupper(c[0])<<endl;
}

Measured memory_bytes: 3564
mod = 10 ** 9 + 7
n = int(input())
c = [int(input()) for _ in range(n)]
import copy
cc = copy.deepcopy(c)
color_sum = {i: 0 for i in range(10 ** 6)}
dp = [1 for _ in range(n + 1)]
color_sum[cc[0]] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    if cc[i - 2] == cc[i - 1]:
        continue
    dp[i] += color_sum[cc[i - 1]]
    dp[i] %= mod
    color_sum[c[i - 1]] += dp[i - 1]
    color_sum[c[i - 1]] %= mod
print(dp[n])

Measured memory_bytes: 108980
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while (1) {
        c -= b;
        if (c <= 0) break;
        a -= d;
        if (a <= 0) break;
    }
    cout << (c <= 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3636
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

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

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int d;
    cin>>d;
    if(d==22)
        cout<<"Christmas Eve Eve Eve"<<endl;
    else if(d==23)
        cout<<"Christmas Eve Eve"<<endl;
    else if(d==24)
        cout<<"Christmas Eve"<<endl;
    else if(d==25)
        cout<<"Christmas"<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

vector<pair<int,ll>> g[100005];
int color[100005];
int num[100005];

int low,up;

bool dfs(int u,int c,int tmp){

  if(color[u]!=-1){
    if(color[u]==c) return tmp==num[u];
    int z;
    if(c) z=tmp-num[u];
    else z=num[u]-tmp;

    if(z%2||z<=0) return false;
    if(low==up&&z/2!=low) return false;
    if(z/2<low||z/2>up) return false;
    low=up=z/2;
    return true;
  }

  color[u]=c;
  num[u]=tmp;
  if(c) if(up>tmp-1) up=tmp-1;
  if(!c) if(low<1-tmp) low=1-tmp;
  if(low>up) return false;

  for(int i=0;i<g[u].size();i++){
    if(!dfs(g[u][i].first,1-c,g[u][i].second-tmp)) return false;
  }
  return true;
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int u,v;
    ll s;
    cin>>u>>v>>s;
    g[u].push_back(make_pair(v,s));
    g[v].push_back(make_pair(u,s));
  }

  memset(color,-1,sizeof(color));
  low=-1;
  up=1e9+1;

  if(dfs(1,0,0)) cout<<up-low+1<<endl;
  else cout<<0<<endl;

  return 0;
}


Measured memory_bytes: 13312
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

int main() {
    set<int> s;
    rep(i, 3) { int a; cin >> a; s.insert(a); }
    out(SZ(s));
    
    
}


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

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    vector<ll> prefix_sum(n + 1, 0);
    rep(i, n) prefix_sum[i + 1] = prefix_sum[i] + a[i];

    auto calc = [&](ll x) {
        ll tot = 0, num = 0;
        rep(i, n) {
            ll j = lower_bound(a.begin(), a.end(), x - a[i]) - a.begin();
            num += n - j;
            tot += prefix_sum[n] - prefix_sum[j];
            tot += a[i] * (n - j);
        }
        return make_pair(tot, num);
    };

    ll l = 0, r = 200200;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        if (calc(mid).second >= m) {
            l = mid;
        } else {
            r = mid;
        }
    }
    auto p = calc(l);
    ll ans = p.first;
    ans -= (p.second - m) * l;
    cout << ans << endl;
}

Measured memory_bytes: 4820
//
//  main.cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main(){	
	vector<int>W,K;
	int input;
	for(int i=0;i<10;i++){
		cin >> input;
		W.push_back(input);
	}
	for(int i=0;i<10;i++){
		cin >> input;
		K.push_back(input);
	}
	sort(W.begin(),W.end());
	sort(K.begin(),K.end());
	
	cout << W[9] + W[8] + W[7] << " " << K[9] + K[8] + K[7] << endl;
	return 0;
}

Measured memory_bytes: 3160
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int mod = 998244353;

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

int powMod(int x, int p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mul(res, x);
    }
    p >>= 1;
    x = mul(x, x);
  }
  return res;
}

int inv(int x) {
  return powMod(x, mod - 2);
}

const int maxn = (int) 1e5 + 5;
int n;
vector<int> g[3][maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int t = 0; t < 3; t++) {
    int m;
    scanf("%d", &m);
    for (int i = 0; i < n; i++) {
      g[t][i].clear();
    }
    for (int i = 0; i < m; i++) {
      int v, u;
      scanf("%d%d", &v, &u);
      v--;
      u--;
      g[t][v].push_back(u);
      g[t][u].push_back(v);
    }
  }
  return true;
}

const int X = ((long long) 1e18) % mod;

const int maxb = 17, maxx = (1 << maxb);
int d[maxn];
int mex[maxn];
int curu;
int a[3][maxx];
int b[maxx];

void solve() {
  for (int t = 0; t < 3; t++) {
    for (int v = n - 1; v >= 0; v--) {
      curu++;
      for (int i = 0; i < sz(g[t][v]); i++) {
        int u = g[t][v][i];
        if (u > v && d[u] < maxn) {
          mex[d[u]] = curu;
        }
      }
      auto &cur = d[v];
      cur = 0;
      while (mex[cur] == curu) {
        cur++;
      }
    }
    for (int i = 0; i < maxx; i++) {
      a[t][i] = 0;
    }
    for (int i = 0; i < n; i++) {
      add(a[t][d[i]], powMod(X, i + 1));
    }
    for (int bit = 0; bit < maxb; bit++) {
      for (int i = 0; i < maxx; i++) {
        if (i & (1 << bit)) {
          continue;
        }
        int x = a[t][i];
        int y = a[t][i | (1 << bit)];
        a[t][i] = x;
        add(a[t][i], y);
        a[t][i | (1 << bit)] = x;
        add(a[t][i | (1 << bit)], mod - y);
      }
    }
  }
  for (int i = 0; i < maxx; i++) {
    b[i] = mul(mul(a[0][i], a[1][i]), a[2][i]);
  }
  for (int bit = 0; bit < maxb; bit++) {
    for (int i = 0; i < maxx; i++) {
      if (i & (1 << bit)) {
        continue;
      }
      int x = b[i];
      int y = b[i | (1 << bit)];
      b[i] = x;
      add(b[i], y);
      b[i | (1 << bit)] = x;
      add(b[i | (1 << bit)], mod - y);
    }
  }
  printf("%d\n", mul(b[0], inv(maxx)));
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 20480
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
int sum = 0, ans = 0;
int E, F;
int s[5], t[5];
int vis[3005][3005];
void dfs(int x, int y)
 {
     if (x * 100 + y > F) return ;
     if (x * E < y) return ;
     if (y * (sum + ans) >= ans * (x + y)) 
	 {
          sum = x, ans = y;
     }
     for (int i = 0; i <= 2; i++)
          for (int j = 0; j <= 2; j++) 
		  {
               if (!vis[x + s[i]][y + t[j]]) 
			   {
                    vis[x + s[i]][y + t[j]] = 1;
                    dfs(x + s[i], y + t[j]);
               }

          }
     return ;
}
int main()
 {
     scanf("%d%d%d%d%d%d", &s[0], &s[1], &t[0], &t[1], &E, &F);
     s[2] = 0, t[2] = 0;
     vis[0][0] = 1;
     dfs(0, 0);
     cout << sum * 100 + ans << " " << ans << endl;
     return 0;
}


Measured memory_bytes: 512
import sys

x, a, b = map(int, sys.stdin.readline().split())

def main():
    best = -b + a
    if best >= 0:
        return 'delicious'
    elif best >= -x:
        return 'safe'
    else:
        return 'dangerous'

if __name__ == '__main__':
    ans = main()
    print(ans)

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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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

const int mod=1000000007;

int fact[2000010];
int fact_inv[2000010];


int modPow(int a, int n) {
    if(n==0)return 1;
    if(n==1)return a%mod;
    if (n%2==1)return(a*modPow(a,n-1))%mod;
    int t=modPow(a,n/2);
    return (t*t)%mod;
}

void init_fact(int N){
    fact[0]=1;
    fact_inv[0]=1;
    for(int i=1;i<=N;++i){
        fact[i]=fact[i-1]*i%mod;
        fact_inv[i]=modPow(fact[i],mod-2);
    }
}

int comb(int n,int r){
    return (((fact[n]*fact_inv[r])%mod)*fact_inv[n-r])%mod;
}

int perm(int n,int k){
    return (fact[n]*fact_inv[n-k])%mod;
}

int K;
string S;

int ans;

signed main(){
    cin>>K>>S;
    int N=S.size();
    init_fact(2000005);
    for(int k=0;k<=K;++k){
        ans+=(((modPow(25,K-k)*modPow(26,k))%mod)*comb(N+K-k-1,N-1))%mod;
        ans%=mod;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 35560
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
#define pii pair<int,int>
#define pqi priority_queue<int>
#define pb push_back()
#define INF 1000000000000000000
#define pi acos(-1)
#define deb(x) cout<<#x" = "<<x<<" "
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const int modu=998244353;//1e9+7;
 
int bigmod(int n,int p){
    if(p==0) return 1;
    int x=bigmod(n,p/2)%modu;
    x=(x*x)%modu;
    if(p%2) return (x*n)%modu;
    return x;
}
 
int modInverse(int a){
    return bigmod(a,modu-2)%modu;
}
 
void defInit(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    #ifdef OFFLINE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}

void endscreen(){
    #ifdef OFFLINE
        cerr<<endl<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    #endif
}


int add(int x,int y){
    int z =(x%modu + y%modu)%modu;
    while(z<0) z=(z+modu)%modu;
    return z;
}
 
int mul(int x,int y){
    int z = (x%modu * y%modu)%modu;
    while(z<0) z=(z+modu)%modu;
    return z;
}

// starts here

const int MAXV = 1e5; 

void min_self(int &a,int b){
    a=min(a,b);
}

int32_t main(){
    defInit();
    //If you hack my code , You are gay;
    int n,W;
    cin>>n>>W;
    int v[n+1],w[n+1];
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(MAXV+1,INF));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=MAXV;j++)if(dp[i][j]<=W){
            min_self(dp[i+1][j],dp[i][j]);
            min_self(dp[i+1][j+v[i+1]] , dp[i][j] + w[i+1]);
        }
    }
    int ans=0;
    for(int i=0;i<=MAXV;i++)if(dp[n][i]<=W){
        ans=max(ans,i);
    }
    cout<<ans;
    endscreen();
    return 0;

}

Measured memory_bytes: 80256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 5000000000000000000;

int main() {
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N), F(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> F[i];
    
    sort(ALL(A));
    reverse(ALL(A));
    sort(ALL(F));
    ll left = 2000000000000, right = -1;
    while (left - right > 1) {
        ll mid = (right + left) / 2;
        ll cnt = 0;
        rep(i, N) {
            cnt += max(0LL, A[i] - mid / F[i]);
        }
        if (cnt > K) right = mid;
        else left = mid;
    }
    cout << left << "\n";
    return 0;
}


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

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

P f(int x) {
	int a = x%10;
	int b = 0;
	while (x) {
		b = x;
		x /= 10;
	}
	return P(a, b);
}

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

	map<P, int> mp;

	for (int i = 1; i <= n; i++) {
		P p = f(i);
		mp[p]++;
	}

	ll ans = 0;

	for (int i = 1; i <= n; i++) {
		P p = f(i);
		P q(p.second, p.first);
		ans += mp[q];
	}

	cout << ans << endl;
}


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

bool PRIME(int num) {
	switch (num) {
		case 1: return false;
		case 2: return true;
	}
	if (num % 2 == 0) {
		return false;
	}
	for (int i = 3; i * i <= num; i += 2) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	int temp;
	int a = 0;
	while (cin >> temp) {
		a += (int)PRIME(temp);
	}
	cout << a << endl;
	return 0;
}


Measured memory_bytes: 3016
(function main() {
  const n = Number(require('fs').readFileSync('/dev/stdin', 'utf8'));
  const cache = [1, 1];
  const fib = (n) => cache[n] || (cache[n] = fib(n - 1) + fib(n - 2));
  console.log(fib(n));
})();


Measured memory_bytes: 15132
n = int(input())
h = list(map(int, input().split()))

dp = [0] * n
dp[1] = abs(h[0]-h[1])

for i in range(2,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
    
print(dp[-1])

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

const int INF = 0x3f3f3f3f;
int tmpa[50], cnt[50], a[50], b[50];

int mdis(int* arr, int n) {
    if(n < 2) return 0;
    int ans = INF;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            int tmp = abs(arr[i] - arr[j]);
            tmp = min(tmp, 24 - tmp);
            ans = min(ans, tmp);
        }
    }
    return ans;
}

int main() {
    int n, ans = -INF;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        if(++cnt[tmp] > 2) {
            puts("0");
            return 0;
        }
    }
    if(cnt[0] != 0) {
        puts("0");
        return 0;
    }
    int idx = 0, uidx = 0;
    for(int i = 1; i <= 12; ++i) {
        if(cnt[i] == 2) {
            a[idx++] = i;
            a[idx++] = 24 - i;
        } else if(cnt[i] == 1) {
            b[uidx++] = i;
        }
    }
    a[idx++] = 0;
    for(int i = 0; i < (1 << uidx); ++i) {
        int tidx = 0;
        for(int j = 0; j < uidx; ++j) {
            if(i >> j & 1) {
                tmpa[tidx++] = b[j];
            } else {
                tmpa[tidx++] = 24 - b[j];
            }
        }
        for(int j = 0; j < idx; ++j) {
            tmpa[tidx++] = a[j];
        }
        ans = max(mdis(tmpa, tidx), ans);
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char b = sc.next().charAt(0);
		char ans = '\u0000';
		switch (b) {
		case 'A':
			ans = 'T';
			break;
		case 'C':
			ans = 'G';
			break;
		case 'G':
			ans = 'C';
			break;
		case 'T':
			ans = 'A';
			break;
		}

		System.out.println(ans);

		sc.close();
	}
}


Measured memory_bytes: 21844
// Problem : C - One Quadrillion and One Dalmatians
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//mst,pq,mp,st,q
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int n;
		cin>>n;
		map<int,char> mp;
		char ch = 'a';
		for(int i=1;i<26;++i)
		{
			mp[i]= ch++;
		}
		mp[0] = 'z';
 		string s = "";
		while(n)
		{
			s+=mp[n%26];
			if(n%26==0)
			{
				n/=26;
				n--;
			}
			else
			n/=26;
		}
		//s+=mp[n%26];
		reverse(all(s));
		cout<<s;		
    }
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;

const int N = 1e3+10;
const LL MOD = 1e9+7;
int DP[N][N];
int h,w;
char T[N][N];

int main(){
  boost;
  cin >> h >> w;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      cin >> T[i][j];
    }
  }
  DP[1][1] = 1;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      if(T[i][j] == '#' || (i==1 && j==1))continue;
      DP[i][j] = DP[i-1][j] + DP[i][j-1];
      if(DP[i][j]>MOD) DP[i][j] %= MOD;
    }
  }
  cout << DP[h][w] << "\n";

  return 0;
}


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

int k,x; 

int a[10000005];
int main()
{
	scanf("%d%d",&k,&x);
	a[x]=true;
	int j,m;
	j=x;
	m=x;
	for(int i=1;i<=k;i++)
	{a[i]=j; j++;}
	for(int i=k+1;i<=2*k;i++)
	{
		a[i]=m; m--;
	}
	sort(a+1,a+1+2*k);
	for(int i=1;i<=2*k;i++)
	{
		if(i==k) continue;
		printf("%d ",a[i]);
	}
	return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import Text.Printf (printf)
main = do
    [a,b] <- map read . words <$> getLine
    -- without using brain
    let (d,r) = a `divMod` b
    putStr $ show d
    putChar ' '
    putStr $ show r
    putChar ' '
    putStrLn . printf "%.6f" $ (fromIntegral a ::Double) / fromIntegral b

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


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

int main() {
  int N;
  cin >> N;
  
  string S;
  cin >> S;
  vector<set<int>> cnt(26);
  //適当な値を入れる
  for( int i = 0; i < 26; i++ ) cnt.at(i).insert(INF);
  //Sの文字をsetに入れていく
  for( int i = 0; i < S.size(); i++ ) cnt.at(S.at(i)-'a').insert(i);
  
  int Q;
  cin >> Q;
  
  for( int i = 0; i < Q; i++ ){
    int num;
    cin >> num;
    if( num == 1 ){ //タイプ1のとき
      int X;
      char C;
      cin >> X >> C;
      X--;
      cnt.at(S.at(X)-'a').erase(X);
      cnt.at(C-'a').insert(X);
      S.at(X) = C;
    }else{ //タイプ2のとき
      int ans = 0;
      int L, R;
      cin >> L >> R;
      //LとRは1-indexedなのでLだけ引いておく
      L--;
      for( int j = 0; j < 26; j++ ){ //その文字が範囲内に含まれているか
        int l = *cnt.at(j).lower_bound(L);
        if( l < R ) ans++;
      }
      cout << ans << endl;
    }
  }
  
}


Measured memory_bytes: 24196
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            
            long BIG = 10;
            for(int i = 0;i<8;i++){
                BIG*=10;
            }
            BIG+=7;
            
        
            int N = sc.nextInt();
            long K = sc.nextLong();
            
            int[] arr = new int[N];
            
            for(int i = 0; i < N; i++){
                arr[i] = Integer.parseInt(sc.next());
            }
            
            long count1 = 0;
            long count2 = 0;
            
            // 次以降
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(arr[i] > arr[j]){
                        count1++;
                        count1 %= BIG;
                    }
                }   
            }
            count1 %= BIG;
            long result = add(K) % BIG;
            count1 *= result;
            
            // 自分のなか
            for(int i = 0; i < N-1; i++){
                for(int j = i+1; j < N; j++){
                    if(arr[i] > arr[j]){
                        count2++;
                    }
                }   
            }
            count2 %= BIG;
            K %= BIG;
            count2*=K;
            System.out.println((count1+count2)%BIG);
    }
    
    static long add(long K){
        long sum = 0;
        for(int i = 1; i < K; i++){
            sum += i;
        }
        return sum;
}
}


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

using ll = long long;

const bool DEBUG = 1;

const int mxn = 3e5, mod = 1e9+7;
ll n, a, b, c;
ll ac, bc, cc;

ll fac[mxn], inv[mxn];

ll modpow(ll a, ll b) {
	a%=mod;
	return b?modpow(a*a%mod,b/2)*(b&1?a:1)%mod:1;
}

ll choose(int n, int r) {
	if (n<r || n<0 || r<0) return 0;
	return fac[n]*inv[r]%mod*inv[n-r]%mod;
}

ll p(int x, int n, bool lsa) {
	return choose(n-1,x-lsa)*modpow(ac,x)%mod*modpow(bc,n-x)%mod;
}

void add(ll &a, ll b) { 
	a+=b; a%=mod;
}

ll inverse(ll a) { return modpow(a,mod-2); }

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	cin >> n >> a >> b >> c;

	// init
	for (int i = 0; i < mxn; i++)
		fac[i] = i?fac[i-1]*i%mod:1;
	inv[mxn-1] = modpow(fac[mxn-1],mod-2);
	for (int i = mxn - 2; i >= 0; i--)
		inv[i] = inv[i+1]*(i+1)%mod;

	// precomp
	ll tmp = modpow(100,mod-2);
	a=a*tmp%mod; b = b*tmp%mod; c = c*tmp%mod;
	tmp = modpow((1+mod-c)%mod,mod-2);
	ac = a*tmp%mod; bc = b*tmp%mod; cc = tmp;

	ll e = 0;
	for (int games = n; games < 2*n; games++) {
		add(e, (games*cc%mod)*
			p(n,games,1)%mod);
		add(e, (games*cc%mod)*
			p(games-n,games,0)%mod);
	}
	cout << e << endl;

#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


Measured memory_bytes: 4992