akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
vector<vector<double>>dp;
double solve(double a[], int i, int x)
{
  if(x==0)
    return 1;
  if(i==0)
    return 0;
  if(dp[i][x]>=-0.9)
    return dp[i][x];
  return dp[i][x]=(a[i]*solve(a,i-1,x-1))+((1-a[i])*solve(a,i-1,x));
}
int main()
{
  int n;
  cin>>n;
  double a[n+1];
  for(int i=1;i<=n;i++)
    cin>>a[i];
  dp.resize(n+1,vector<double>(n+1,-1));
  cout<<fixed<<setprecision(10)<<solve(a,n,(n+1)/2);
  return 0;
}


Measured memory_bytes: 74100
#include <iostream>

using namespace std;

int main() {

  int n, odd = 1, p, ans = 0, old = 0;
  cin >> n;
  for(int i =1;i <= n;i++){
    cin >> p;
    if(old != p){
      ans += odd / 2;
      old = p;
      odd = 1;
    }else{
      odd++;
    }
  }
  ans += odd / 2;
  cout << ans;
  return 0;
}


Measured memory_bytes: 3524
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
struct debugger
{
    template <typename T>
    debugger &operator,(const T &v)
    {
        cerr << v << " ";
        return *this;
    }
} dbg;
map<LL, LL> mp;
LL mi[100];
void solve(long long n, vector<long long> a)
{
    mi[0] = 1;
    for (int i = 1; i <= 32; ++i) {
        mi[i] = mi[i - 1] * 2;
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        if (mp.count(a[i]) == 0)
            mp[a[i]] = 1;
        else
            mp[a[i]]++;
    }
    reverse(a.begin(), a.end());
    int ans = 0;
    for (auto i : a) {
        if (mp[i] == 0)
            continue;
        int j;
        for (j = 0; j <= 32; ++j) {
            if (mi[j] > i)
                break;
        }
        LL x = mi[j];
        if (x - i == i) {
            if (mp[i] > 1) {
                mp[i] -= 2;
                ans++;
            }
        } else if (mp.count(x - i) > 0 && mp[x - i] > 0) {
            mp[x - i]--;
            mp[i]--;
            ans++;
        }
    }
	cout<<ans<<endl;
}

int main()
{
#ifdef WAAUTOMATON
    // freopen("in.txt","r",stdin);
#endif
    long long N;
    scanf("%lld", &N);
    vector<long long> A(N - 1 + 1);
    for (int i = 0; i <= N - 1; i++) {
        scanf("%lld", &A[i]);
    }
    solve(N, A);
    return 0;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

int main(){
    int n;
    cin>>n;
    map<int,int> mp;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(mp[a]){
            cout<<"NO"<<endl;
            return 0;
        }
        mp[a]++;
    }
    cout<<"YES"<<endl;
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
# define pb push_back
# define FOR(i,a,n) for(int i=a;i<n;i++)
# define mp make_pair
# define RFOR(i,a,n) for(int i=n;i>a;i--)
# define pii pair<long long int,long long int>
#define ub upper_bound
#define lb lower_bound
#define MOD 1000000007
typedef long long int ll;
ll search(ll val,ll b[],ll m)
{
	ll l=0;
	ll r=m;
	ll ans=0;
	ll mid;
	while(r>=l)
	{
		mid=(r+l)/2;
		if(b[mid]>val)
		{
			r=mid-1;
		}
		else
		{
			ans=mid;
			l=mid+1;
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
        cout.tie(0);
		ll n,m,k;
		cin>>n>>m>>k;
		ll a[n+1],b[m+1];
		a[0]=0;
		b[0]=0;
		for(int i=1;i<=n;i++)
		cin>>a[i];
		for(int i=1;i<=m;i++)
		cin>>b[i];
		for(int i=1;i<=n;i++)
		a[i]+=a[i-1];
		for(int i=1;i<=m;i++)
		b[i]+=b[i-1];
		ll ans=0;
		ll val=0,cnt=0;
		for(int i=0;i<=n;i++)
		{
			val=k-a[i];
			if(val>=0)
			{
			cnt=search(val,b,m);
			//cout<<cnt<<endl;
			ans=max(ans,cnt+i);
		    }
		}
		cout<<ans<<endl;
}

Measured memory_bytes: 6744
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define int ll
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    signed main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int n,i,q,j,ans=0,a,b;
            cin>>n;
            int ar[n+1];
            map<int,int> mp;
            for(i=1;i<=n;++i)
            {
                cin>>ar[i];
                ans=ans+ar[i];
                ++mp[ar[i]];
            }
            cin>>q;
            while(q--)
            {
                cin>>a>>b;
                ans=ans-a*mp[a];
                mp[b]=mp[b]+mp[a];
                ans=ans+b*mp[a];
                mp[a]=0;
                cout<<ans<<endl;
            }
        }
        return 0;
    }


Measured memory_bytes: 10304
#include<bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
    
#define ll long long int
#define pb push_back
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
#define pre(i , j , n) for(ll i = j ; i >= n ; i--)
#define all(x) x.begin(), x.end()
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vll;
typedef vector<char>	vc;
typedef vector<bool>	vb;
typedef pair<ll,ll> 	pll;
#define br "\n"
#define ff first
#define ss second
ll MAX =  (ll)1000005;


void solve(){
    double d,t,s;
    cin >> d >> t >> s;
    if(d/s > t) cout << "No";
    else cout << "Yes";
    
}
	

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif  

	ll t = 1;
	// cin >> t;
	rep(i,0,t){
		solve();
	}
 
}	

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
typedef long long int ll;
string s;
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>s;
    if(s[3]==s[2]&&s[5]==s[4])
        cout<<"Yes\n";
    else
        cout<<"No\n";

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int ma = -1;
	bool isok = true;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		if(ma-a>1)
		{
			isok = false;
			break;
		}
		ma = max(a,ma);
	}
	if(isok)
	{
		cout<<"Yes\n";
	}
	else
	{
		cout<<"No\n";
	}
	return 0;
 } 

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>

using namespace std;

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

#ifdef LOCAL
#define dbg(x) cerr << #x " = " << x << endl;
#define idbg(x) #x " = " << x
#include "pretty_print.h"
#else
#define dbg(x)
#define idbg(x) ""
#endif

#ifdef _WIN32
#  define LLD "%I64d"
#else
#  define LLD "%lld"
#endif

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

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }
template <typename T> T gcd(T a, T b) { return b? gcd(b, a % b) : a; }
template <typename T> bool chmin(T &x, const T& y) { if (x > y) { x = y; return true; } return false; }
template <typename T> bool chmax(T &x, const T& y) { if (x < y) { x = y; return true; } return false; }


int main(int /* argc */, char** /* argv */)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    assert(freopen("inp", "r", stdin));
    assert(freopen("out", "w", stdout));
    #endif

    int n;
    while (cin >> n && n) {
        vector<pair<int, int>> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i].first >> a[i].second;
        }
        sort(all(a));
        reverse(all(a));

        const int MOD = 998244353;

        stack<pair<int, int>> st;
        st.push({2e+9 + 42, 1});

        int ans = 1;
        for (int i = 0; i < n; ++i) {
            int val = a[i].first + a[i].second;
            while (val > st.top().first) {
                st.pop();
            }
            ans = (ans + st.top().second) % MOD;
            st.push({a[i].first, ans});
        }
        cout << ans << "\n";
    }

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}


Measured memory_bytes: 2688
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AABCxxx solver = new AABCxxx();
        solver.solve(1, in, out);
        out.close();
    }

    static class AABCxxx {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            out.println("ABC" + in.nextInt());
        }

    }
}



Measured memory_bytes: 23636
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
 
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> x(m), len(m - 1);
    for(int i = 0; i < m; i++){
        cin >> x[i];
    }
 
    if(m == 1){
        cout << "0" << endl;
        return 0;
    }

    if(n > m){
        n = m;
    }
    
    sort(x.begin(), x.end());
    for(int i = 0; i < m - 1; i++){
        len[i] = abs(x[i] - x[i + 1]);
        //cout << "len:" << len[i] << endl;
    }
    sort(len.begin(), len.end());
 
    cout << accumulate(len.begin(), len.end() - (n - 1), 0) << endl;
 
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

int main() {
  int N, M, K;
  cin >> N >> M >> K;

  irep(i, N) {
    int R = K - M * i;
    int S = N - 2 * i;
    if (S == 0) {
      if (R == 0) {
        cout << "Yes" << endl;
        return 0;
      }
    } else if (R % S == 0) {
      const int j = R / S;
      if (j >= 0 && j <= M) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <algorithm>
#include <array>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <stack>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define MOD ((ll)1000000007)

int gcd(int a, int b)
{
	if (a < b)
	{
		return gcd(b, a);
	}

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

int ngcd(vector<int> nums)
{
	int d = nums[0];
	for (size_t i = 1; i < nums.size(); i++)
	{
		d = gcd(d, nums[i]);
	}
	return d;
}

int main(int argc, char const *argv[])
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	int A, B, C;
	cin >> A >> B >> C;

	vector<int> v = {A, B, C};
	int d = ngcd(v);

	A /= d;
	B /= d;

	if (gcd(A, B) == 1)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m,x,y,z;
  cin >> n >> m;
  vector<vector<int>> adj(n+1);
  while(m--){
    cin >> x >> y >> z;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  vector<bool> vu(n+1);
  int nb = 0;
  for(int i = 1; i <= n; ++i){
    if(!vu[i]){
      vu[i] = true;
      ++nb;
      queue<int> q;
      q.emplace(i);
      while(!q.empty()){
        int node = q.front();
        q.pop();
        for(int j : adj[node]){
          if(!vu[j]){
            vu[j] = true;
            q.emplace(j);
          }
        }
      }
    }
  }
  cout << nb;
  return 0;
}


Measured memory_bytes: 6520
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <unistd.h>
using namespace std; 
using namespace std::chrono; 
using namespace __gnu_pbds;
#define ll long long int 
//mp.reserve(1024);
//mp.max_load_factor(0.25);
typedef tree<int, null_type, less<int>, rb_tree_tag,  
                 tree_order_statistics_node_update>  
          ordered_set;  
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
};
 
void addEdge(vector<ll> adj[], ll u, ll v) 
{ 
   adj[u].push_back(v); 
   adj[v].push_back(u); 
} 
vector<ll> z_function(string s) {
    ll n = s.length();
    vector<ll> z(n);
    for (ll i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
ll mod=1e9+7;
ll power(ll x,ll y) 
{ 
    ll res = 1; // Initialize result 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = ((res%mod) * (x%mod))%mod; 
  
        // n must be even now 
        y = y >> 1; // y = y/2 
        x = ((x%mod) * (x%mod))%mod; // Change x to x^2 
    } 
    return res; 
}

int main() 
{ 
 	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);
   	cout.tie(NULL);
    //freopen("input.txt", "r", stdin); 
    //freopen("output1.txt", "w", stdout); 
    ll n,ww;
	cin>>n>>ww;
	ll w[n+1],v[n+1];
	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
	ll dp[100005];
	for(int i=0;i<100005;i++) dp[i] = 1e18;
	dp[0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=100000;j>=v[i];j--){
			dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	ll ans = 0;
	for(int i=100000;i>=0;i--) if(dp[i] <= ww) ans=max(ans,1LL*i);
	cout<<ans<<endl;
    return 0; 
} 


Measured memory_bytes: 1024
/*
 ▓█████▄  ▄████▄  ▓██   ██▓ ██▓███   ██░ ██ ▓█████  ██▀███
▒██▀ ██▌▒██▀ ▀█   ▒██  ██▒▓██░  ██▒▓██░ ██▒▓█   ▀ ▓██ ▒ ██▒
 ░██   █▌▒▓█    ▄   ▒██ ██░▓██░ ██▓▒▒██▀▀██░▒███   ▓██ ░▄█ ▒
 ░▓█▄   ▌▒▓▓▄ ▄██▒  ░ ▐██▓░▒██▄█▓▒ ▒░▓█ ░██ ▒▓█  ▄ ▒██▀▀█▄
 ░▒████▓ ▒ ▓███▀ ░  ░ ██▒▓░▒██▒ ░  ░░▓█▒░██▓░▒████▒░██▓ ▒██▒
  ▒▒▓  ▒ ░ ░▒ ▒  ░   ██▒▒▒ ▒▓▒░ ░  ░ ▒ ░░▒░▒░░ ▒░ ░░ ▒▓ ░▒▓░
  ░ ▒  ▒   ░  ▒    ▓██ ░▒░ ░▒ ░      ▒ ░▒░ ░ ░ ░  ░  ░▒ ░ ▒░
  ░ ░  ░ ░         ▒ ▒ ░░  ░░        ░  ░░ ░   ░     ░░   ░
    ░    ░ ░       ░ ░               ░  ░  ░   ░  ░   ░
  ░      ░         ░ ░
*/
//focus less on how much problem you should solve within a fixed time and focus more on getting the problem solved and
//learning something from it
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define per(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define sedes set <ll, greater <ll> >
#define seasc set <ll>
#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define MOD 1000000007
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define umap unordered_map<ll, ll>
#define map map<ll, ll>
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define mems(a, i) memset(a, i, sizeof(a))
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define deba(a) cout << #a << " " << a << endl;
int main()
{
	fast;
#ifndef ONLINE_JUDGE
	freopen("/home/kushagra/Desktop/Kushagra/input.txt", "r", stdin);
	freopen("/home/kushagra/Desktop/Kushagra/output.txt", "w", stdout);
#endif
	ll h, w;
	cin >> h >> w;
	ll sx, sy, ex, ey;
	cin >> sx >> sy;
	cin >> ex >> ey;
	sx--, sy--, ex--, ey--;
	string grid[h];
	rep(i, 0, h)
	{
		cin >> grid[i];
	}

	deque<pair<int, int>> dq;
	int dis[h][w];
	bool poss = false;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			dis[i][j] = 1e7;
		}
	}
	dis[sx][sy] = 0;
	dq.pb({sx, sy});

	while (!dq.empty())
	{
		auto curr = dq.front();
		dq.pop_front();
		ll row = curr.ff;
		ll col = curr.ss;
		if (row == ex and col == ey)
		{
			poss = true;
			break;
		}
		rep(i, -2, 3)
		{
			rep(j, -2, 3)
			{
				ll nr = row + i;
				ll nc = col + j;

				if (nr == row and nc == col)
					continue;
				if (nr < 0 or nc<0 or nr >= h or nc >= w)
					continue;
				if (grid[nr][nc] == '#')
					continue;
				ll w = 1;
				if ((abs(nr - row) == 1 and abs(nc - col) == 0) or
				        (abs(nc - col) == 1 and abs(nr - row) == 0))
					w = 0;

				if (dis[nr][nc] > dis[row][col] + w)
				{
					dis[nr][nc] = dis[row][col] + w;
					if (w == 0)
						dq.push_front({nr, nc});
					else
						dq.push_back({nr, nc});
				}

			}
		}
	}

	if (!poss	)
		dis[ex][ey] = -1;

	cout << dis[ex][ey];
	return 0;
}

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

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n; cin >> n;
	long long ans = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= n; k++)
				ans += (__gcd(i, __gcd(j, k)));
	cout << ans << '\n';				
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const ll m=1LL<<32;

int main(){

  string s;cin>>s;
  ll q;cin>>q;
  deque<char>deq;
  rep(i,0,s.size())deq.push_back(s[i]);
  bool e=false;
  rep(i,0,q){
    ll a;cin>>a;
    if(a==1){
      e=(e?false:true);
    }else{
      ll b;cin>>b;
      char c;cin>>c;
      if(e){
        if(b==2){
          // s=c+s;
          deq.push_front(c);
        }else{
          deq.push_back(c);
        }
      }else{
        if(b==1){
          deq.push_front(c);
        }else{
          deq.push_back(c);
        }
      }
    }
  }

  // out(ans.size()/2);
  ll si=deq.size();
  if(e){
    rep(i,0,si){
      cout<<deq.back();
      deq.pop_back();
    }
    cout<<endl;
  }else{
    rep(i,0,si){
      cout<<deq.front();
      deq.pop_front();
    }
    cout<<endl;
  }
  // out(s);

  return 0;
}


Measured memory_bytes: 896
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define MOD (998244353ll)
#define l_ength size
#define EPS (1e-10)

void add_mod(ll &a, ll b){
	a += b;
	a %= MOD;
}

void mul_mod(ll &a, ll b){
	a *= b;
	a %= MOD;
}

int main(void){
	int n,c,i,j,k,x;
	ll d[33][33], t[3][33] ,ans = INFLL;
	fill(t[0],t[3],0ll);
	cin >> n >> c;
	for(i=0; i<c; ++i){
		for(j=0; j<c; ++j){
			cin >> d[i][j];
		}
	}
	for(i=0; i<n; ++i){
		for(j=0; j<n; ++j){
			cin >> x; --x;
			for(k=0; k<30; ++k){
				t[(i+j)%3][k] += d[x][k];
			}
		}
	}
	for(i=0; i<c; ++i){
		for(j=0; j<c; ++j){
			if(i == j){
				continue;
			}
			for(k=0; k<c; ++k){
				if(i==k || j==k){
					continue;
				}
				ans = min(ans,t[0][i]+t[1][j]+t[2][k]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int N;
  cin >> N;
  int a[N];
  double sum = 0, ans;
  for(int i = 0; i < N; ++i){
    cin >> a[i];
    sum += (double)1 / (double)a[i];
  }
  ans = 1 / sum;
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
    int n;
    string a, b, c;
    cin >> n;
    cin >> a >> b >> c;
    int ans = 0;
    for(int i = 0; i < n; i++){
        if (a[i] == b[i] && a[i] == c[i]) continue;
        if (a[i] == b[i]){
            ans += 1;
        } else if (b[i] == c[i]){
            ans += 1;
        } else if (a[i] == c[i]){
            ans += 1;
        }
        else {
            ans += 2;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7
d,t,s=LI()
ret=0
if d%s:
    ret=1
if d//s+ret<=t:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 76572
queue = []

def enqueue(obj):
  queue.append(obj)

def dequeue():
  v = queue[0]
  del queue[0]

  return v

n, q = map(int, input().split())
for i in range(n):
  p, t = input().split()
  queue.append({"p": p, "t": int(t)})

sum_t = 0
while len(queue) > 0:
  v = dequeue()
  c = min(v["t"], q)
  sum_t += c
  v["t"] -= c
  if v["t"] > 0:
    enqueue(v)
  else:
    print (v["p"], sum_t)



Measured memory_bytes: 20888
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <math.h>
#include <deque>
#include <queue>
#include <map>
#include <iterator>
#include <set>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

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

	int n;
	cin >> n;
	vector<int> prime;
	vector<int> seen(55556, false);
	for (int i = 2; i <= 55555; i++) {
		if (!seen[i]) {
			prime.push_back(i);
			for (int j = i + i; j <= 55555; j += i) {
				seen[j] = true;
			}
		}
	}
	vector<int> ans;
	for (int i = 0; (int)prime.size(); i++) {
		if (prime[i] % 5 == 1) ans.push_back(prime[i]);
		if (ans.size() == n) break;
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}

Measured memory_bytes: 512
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct edge { int to, cost; };
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
vector<int> par;
int root(int x) {
	if (x == par[x]) return x;
	return par[x] = root(par[x]);
}
void unite(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return;
	par[x] = y;
}
bool same(int x, int y) {
	return root(x) == root(y);
}
vector<int> depth; vector<vector<int> > parent, val;
int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = 16; i >= 0; i--) {
		if ((depth[x] - depth[y]) >= (1 << i)) x = parent[i][x];
	}
	for (int i = 16; i >= 0; i--) {
		if (parent[i][x] != parent[i][y]) {
			x = parent[i][x];
			y = parent[i][y];
		}
	}
	while (x != y) {
		x = parent[0][x];
		y = parent[0][y];
	}
	return x;
}
int query(int x, int y) {
	int z = lca(x, y);
	int t1 = depth[x] - depth[z], t2 = depth[y] - depth[z];
	int ret = 1999999999;
	for (int i = 16; i >= 0; i--) {
		if (t1 & (1 << i)) ret = min(ret, val[i][x]), x = parent[i][x];
		if (t2 & (1 << i)) ret = min(ret, val[i][y]), y = parent[i][y];
	}
	return ret;
}
void findpar(int pos, int pre, vector<vector<edge> > &G) {
	parent[0][pos] = pre;
	for (edge e : G[pos]) {
		if (e.to != pre) {
			val[0][e.to] = e.cost;
			depth[e.to] = depth[pos] + 1;
			findpar(e.to, pos, G);
		}
	}
}
int N, M, K, Q, f, t1, t2;
int main() {
	scanf("%d%d%d%d", &N, &M, &K, &Q);
	vector<vector<edge> > G(N);
	vector<int> a(M), b(M), c(M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]); a[i]--, b[i]--;
		G[a[i]].push_back(edge{ b[i], c[i] });
		G[b[i]].push_back(edge{ a[i], c[i] });
	}
	vector<int> dist(N, 1999999999);
	priority_queue<edge> que;
	for (int i = 0; i < K; i++) {
		scanf("%d", &f); f--;
		dist[f] = 0;
		que.push(edge{ f, 0 });
	}
	while (!que.empty()) {
		edge u = que.top(); que.pop();
		for (edge e : G[u.to]) {
			if (dist[e.to] > dist[u.to] + e.cost) {
				dist[e.to] = dist[u.to] + e.cost;
				que.push(edge{ e.to, -dist[e.to] });
			}
		}
	}
	vector<pair<int, int> > s;
	for (int i = 0; i < M; i++) {
		c[i] = min(dist[a[i]], dist[b[i]]);
		s.push_back(make_pair(c[i], i));
	}
	sort(s.begin(), s.end(), greater<pair<int, int> >());
	par.resize(N);
	for (int i = 0; i < N; i++) par[i] = i;
	vector<vector<edge> > G2(N);
	for (int i = 0; i < M; i++) {
		int r1 = a[s[i].second], r2 = b[s[i].second], r3 = c[s[i].second];;
		if (!same(r1, r2)) {
			unite(r1, r2);
			G2[r1].push_back(edge{ r2, r3 });
			G2[r2].push_back(edge{ r1, r3 });
		}
	}
	parent = vector<vector<int> >(17, vector<int>(N));
	val = vector<vector<int> >(17, vector<int>(N));
	depth.resize(N);
	findpar(0, -1, G2);
	for (int i = 1; i < 17; i++) {
		for (int j = 0; j < N; j++) {
			if (parent[i - 1][j] == -1) parent[i][j] = -1, val[i][j] = 1999999999;
			else parent[i][j] = parent[i - 1][parent[i - 1][j]], val[i][j] = min(val[i - 1][j], val[i - 1][parent[i - 1][j]]);
		}
	}
	while (Q--) {
		scanf("%d%d", &t1, &t2); t1--, t2--;
		printf("%d\n", query(t1, t2));
	}
	return 0;
}

Measured memory_bytes: 35560
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    w, h = map(int, input().split())
    pq = [None] * (w + h)

    for i in range(w + h):
        if i < w:
            pq[i] = (int(input()), 'x')
        else:
            pq[i] = (int(input()), 'y')

    x_count = w + 1
    y_count = h + 1
    ans = 0

    for cost, flag in sorted(pq):
        if flag == 'x':
            ans += cost * y_count
            x_count -= 1
        else:
            ans += cost * x_count
            y_count -= 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 26084
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>

const int N = 2e3 + 7;
const long long INF = (1LL << 60);

int n;
int x;
int a[N << 1];

int main() {
	scanf("%d %d", &n, &x);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		a[i + n] = a[i];
	}
	long long ans = INF;
	for (int times = 0; times < n; times++) {
		std::vector<std::pair<int, int> > queue;
		int head = 0;
		long long base = 1LL * x * times;
		for (int j = 0; j < (n << 1); j++) {
			std::pair<int, int> v = {a[j], j};
			while (head < queue.size() && queue.back().first >= v.first) {
				queue.pop_back();
			}
			queue.push_back(v);
			while (head < queue.size() && queue[head].second < j - times) head++;
			if (j >= n) {
				base += queue[head].first;
			}
		}
		ans = std::min(ans, base);
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
// problem: "https://atcoder.jp/contests/abc154/tasks/abc154_f"

#include<bits/stdc++.h>
#define ll long long
#define p (ll)(1e9+7)
#define n (ll)(2e6+3)

using namespace std;

void calcFact(vector<ll>&V)
{
    V[0] = 1;
    ll i;
    for(i=1;i!=n;i++)
        V[i] = (V[i-1]*i)%p;
}

ll power(ll a,ll m)
{
    if(!m)
        return 1;

    ll b = 1;
    if(m%2)
        b = a;

    ll ans = power(a,m/2);

    ans = ((ans*ans)%p * b)%p;

    return ans;
}


ll nCr(ll a,ll b,vector<ll>&V)
{
    ll ans = (V[a] * power((V[b]*V[a-b])%p,p-2))%p;     // define

    return ans;
}


int main()
{
    ll r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;

    vector<ll>V(n);
    calcFact(V);      // define

    cout<<(nCr(r2+c2+2,c2+1,V) + p - nCr(r1+c2+1,c2+1,V) + p - nCr(r2+c1+1,c1,V) + nCr(r1+c1,c1,V))%p;        // define

    return 0;
}


Measured memory_bytes: 15872
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;
typedef  pair<int,int> pa;
int dv[][2]={{0,1},{1,0},{-1,0},{0,-1}};
int mod=1e9+7;
const int N=2e5+100;

int main()
{
   ll k;
   cin>>k;
   ll ans=k*(k+1)/2;
   cout<<ans-k;
   return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

		int[][] x = new int[10][10];
		int ans = 0;

		for(int i = 0 ; i < 10; i++)
		{
			for(int j = 0 ; j < 10; j++){
				x[i][j] = 0;
			}
		}

		for(int i = 0 ; i < n; i++)
		{
			for(int j = 0 ; j < d; j++){
				x[i][j] = sc.nextInt();
			}
		}

		int distsq = 0;
		for(int i = 0 ; i < n; i++)
		{
			for(int j = i+1 ; j < n; j++){
				distsq = 0;
				for(int k = 0 ; k < d ; k++){
					distsq += (x[i][k] - x[j][k])*(x[i][k] - x[j][k]);
				}
				if(((int)Math.sqrt(distsq))*((int)Math.sqrt(distsq)) == distsq)
				{
					ans++;
				}
			}
		}
		//ArrayList<Integer> iarr = new ArrayList<Integer>();


		System.out.println(ans);
	}

}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int N, Q; cin >> N >> Q;
  string s; cin >> s; s = "." + s + ".";
  char t[Q], d[Q]; rep(i,Q) cin >> t[i] >> d[i];
  ll result = N;

  ll l = 0, r = N+1;
  while (l!=r) {
    ll mid = (l+r+1)/2;
    ll pos = mid;
    rep(i,Q) {
      if (s[pos]==t[i]) {
        pos += d[i]=='L' ? -1 : 1;
      }
    }
    if (pos==0) l = mid;
    else r = mid - 1;
  }
  result -= l;

  l = 0; r = N+1;
  while (l!=r) {
    ll mid = (l+r)/2;
    ll pos = mid;
    rep(i,Q) {
      if (s[pos]==t[i]) {
        pos += d[i]=='L' ? -1 : 1;
      }
    }
    if (pos==N+1) r = mid;
    else l = mid + 1;
  }
  result -= (N+1)-l;

  cout << result << endl;
  return 0;
}

Measured memory_bytes: 984
#include <bits/stdc++.h>
        using namespace std;
        #define int long long int
        #define pb push_back
        #define mk make_pair
        #define ft first
        #define sc second
        #define ppb pop_back
        #define sz size
        #define forn(i,a,n) for(i=a;i<n;i++)
        #define M 998244353 
        #define inf 2e18

        signed main() {

        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        int n,m,x;
        cin>>n>>m>>x;

        int arr[n][m];
        int c[n];

        for(int i=0;i<n;i++){
            cin>>c[i];
            for(int j=0;j<m;j++){
                cin>>arr[i][j];
            }
        }

        int ans=1e18;

        for(int mask= 0 ; mask<(1<<n); mask++){

            vector<int> cur(m,0);
            int cost=0;
            for(int i=0;i<n;i++){

                if( (mask>>i) & 1 ){
                    cost+=c[i];

                    for(int j=0;j<m;j++)
                        cur[j]+=arr[i][j];
                }
            }

            int fl=1;
            for(int i=0;i<m;i++)
                if(cur[i]<x){
                    fl=0;
                    break;
                }

            if(fl)
                ans=min(ans,cost);
        }
        if(ans!=1e18)
        cout<<ans;
        else
            cout<<-1;


        return 0;
    }

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

int main(){
	string s,t;
	cin>>s>>t;
	int a[s.size()+1][t.size()+1];
	for(int i=0;i<s.size()+1;i++)
		a[i][0] = 0;
	for(int j=0;j<t.size()+1;j++)
		a[0][j] = 0;
	for(int i=1;i<s.size()+1;i++){
		for(int j=1;j<t.size()+1;j++){
			if(s[i-1] == t[j-1])
				a[i][j] = a[i-1][j-1] + 1;
			else
				a[i][j] = max(a[i-1][j],a[i][j-1]);
		}
	}
	int i = s.size(), j = t.size();
	string ans = "";
	while(i>0 && j>0){
		if(s[i-1] == t[j-1]){
			ans += s[i-1];
			i--;
			j--;
		}
		else if(a[i][j] == a[i-1][j])
			i--;
		else
			j--;
	}
	reverse(ans.begin(),ans.end());
	cout<<ans;
}

Measured memory_bytes: 35456
Q,H,S,D=map(int,input().split())
N=int(input())

ans=0
p=min(Q*8,H*4,S*2,D)
q=N
ans=p*(q//2)

p=min(Q*4,H*2,S)
q=q%2
ans+=p*(q//1)

print(int(ans))

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef long long ll;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX/2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int n, t;
	cin >> n >> t;
	V<int> a(n);
	rep(i, n)cin >> a[i];

	V<int> mn(n), p(n);
	int mxp = 0;
	mn[0] = a[0];
	rep1(i, n - 1)mn[i] = min(mn[i - 1], a[i]);
	rep(i, n) { p[i] = a[i] - mn[i];mxp = max(mxp, p[i]); }

	int buy = 0, sell = 0;
	set<int> set;
	rep(i, n)if (p[i] == mxp) {
		sell++;
		set.insert(mn[i]);
	}
	sort(all(a));
	for (auto x : set)buy += lower_bound(all(a), x+1)-lower_bound(all(a),x);
	cout << min(sell, buy) << endl;
}

Measured memory_bytes: 3712
N, K = tuple(int(s) for s in input().split())
# arr = list(int(s) for s in input().split())

sol = 0
MOD = (10**9) + 7
for k in range(K, N+2):
    sol += N*k - ((k)*(k-1)) + 1
sol = sol % MOD
print(sol)


Measured memory_bytes: 9168
#include <cstdio>
#include <vector>
#include <set>

using namespace std;



int main(){
	int self;
	char a[5];
	char b[5];
	int h;
	int br;
	while(1){
		scanf("%s %s",a,b);
		if(a[1] == '\0' && b[1] == '\0'){
			break;		
		}
		set<int> s;
		h = 0;
		br = 0;
		for(int i=0;i<4;i++){
			if(a[i] == b[i]){
				h+=1;
			}
			s.insert(b[i]);
		}
		set< int >::iterator it;
		for(it = s.begin();	it != s.end();it++){
			for(int i=0;i<4;i++){
				if(a[i]==*it){
					br+=1;
				}
			}
		}
		br-=h;
		printf("%d %d\n",h,br);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int n,m;
    int count=0;
    cin>>n;
    set<int>s;
    set<int>q;
    vector<int>a(10e6+1);
    for(int i=0;i<=10e6;i++){
        a.at(i)=0;
    }
    for(int i=0;i<n;i++){
        cin>>m;
        if(s.count(m)){
            a.at(m+1)=1;
        }
        s.insert(m);
        q.insert(m);
    }

    while(s.size()!=0){
        m=*begin(s);
        for(int k=2*m+1;k<=10e6;k+=m){
            a.at(k)=1;
        }
        s.erase(m);
    }
                
    while(q.size()!=0){
        m=*begin(q);
        if(a.at(m+1)==0){
            count++;
        }
        q.erase(m);
    }
    cout<<count<<endl;
}

Measured memory_bytes: 60892
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;
static const int INF = 1000000;

/*
  ------  -----
--- -----
 ----
最初は、区間の始点があればflagを１にし、flagが1でかつ終点があればans++とし、flag=0としていた
しかし、これだと前の区間が残ったまま次の新しい区間が追加されると、
すでに分断されたはずの区間が終点となった時にもカウントされるためWAとなった

次に、終端を迎えたものが一つでもあった際に、今ある全ての区間を0にして、新たに区間を追加していく実装にした所、ACとなった
この実装では終端の最小値のみを記録しておけば良く、priority_queueを用いて実装した

改良版で、わざわざpriority_queueを用いる必要はないことに気づき、最小値のみを保持するようにし、よりシンプルな実装とした

*/

int ans;
int N, M;
pair<int, int> pr[100005];

int main(void) {
    scanf("%d %d", &N, &M);
    rep(i, 0, M) {
        int a, b;
        scanf("%d %d", &a, &b);
        pr[i] = mp(a, b);
    }
    sort(pr, pr+M);
    int mint = INF;
    for (int i=0; i<M; i++) {
        if (pr[i].first<mint) mint = min(mint, pr[i].second); // < となることに注意　2-3 3-4 別の橋
        else {
            ans++;
            mint = pr[i].second;
        }
    }
    ans++;

  
    printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=2e5+10;
ll b[maxn],f[maxn],g[maxn];
int pre[maxn],del[maxn];
ll a[maxn];
int main(){
	int n=read();
	REP(i,1,n) b[i]=read();
	REP(i,1,n) a[i]=b[i];
	pre[1]=1;
	f[1]=1;
	REP(i,2,n){
		f[i]=f[i-1]+1;
		pre[i]=i;
		if(a[i]<=a[i-1]){
			int u=(a[i-1]/a[i]);
			while(u>=4) u/=4,del[i]+=2;
		}
		else{
			int u=0;
			for(ll k=1;a[i-1]*k<a[i];k*=4,u+=2);
			while(pre[i]>1){
				f[i]+=u*(pre[i]-pre[pre[i]-1]);
				pre[i]=pre[pre[i]-1];
				del[pre[i]]-=u;
				if(del[pre[i]]>=0) break;
				u=-del[pre[i]];
			}
		}
	}
	REP(i,1,n) a[i]=b[i];
	pre[n]=n;
	DREP(i,n-1,1){
		g[i]=g[i+1];
		del[i]=0;
		pre[i]=i;
		if(a[i]<=a[i+1]){
			int u=(a[i+1]/a[i]);
			while(u>=4) u/=4,del[i]+=2;
		}
		else{
			int u=0;
			for(ll k=1;a[i+1]*k<a[i];k*=4,u+=2);
			while(pre[i]<n){
				g[i]+=u*(pre[pre[i]+1]-pre[i]);
				pre[i]=pre[pre[i]+1];
				del[pre[i]]-=u;
				if(del[pre[i]]>=0) break;
				u=-del[pre[i]];
			}
		}
	}
	ll ans=1e18;
	REP(i,0,n) chkmin(ans,f[i]+g[i+1]);
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 8064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Stream;

public class Main {
//    private static Scanner sc = new Scanner(System.in);
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static PrintWriter pw = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException {
        // 解答ここから
        int N = nextInt();
        int[] X = arrayOfInt();
        int[] x = X.clone();
        Arrays.sort(x);
        // 中央値の境界を取る
        int floor = N/2 - 1;
        int border = x[floor];

        int a = x[floor + 1];
        int b = x[floor];
        for(int i = 0;i < N;i++){
            if(X[i] <= border){
                println(a);
            }else{
                println(b);
            }
        }

        //解答ここまで
        pw.flush();
        return;
    }
    // 入力受け取り
    static String next() throws IOException {return br.readLine();}
    static int nextInt() throws IOException{return getInt(br.readLine());}
    static long nextLong() throws IOException{return getLong(br.readLine());}
    static String[] arrayOfString() throws IOException{return br.readLine().split(" ");}
    static int[] arrayOfInt() throws IOException{return toIntArray(arrayOfString());}
    // 変換
    static long getLong(String val) {return Long.parseLong(val);}
    static int getInt(String val) {return Integer.parseInt(val);}
    static int[] toIntArray(String[] array) {return Stream.of(array.clone()).mapToInt(Integer::parseInt).toArray();}
    static  String joinToString(String[] array) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < array.length;i++) sb.append(array[i]);
        return sb.toString();
    }
    // 出力
    static void println(Object val){pw.println(val);}
}

Measured memory_bytes: 63224
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())
def out2(n,m):
	print(str(n)+ " " + str(m) )
	exit()


X = input_one_number()

for i in range(1000000):
	for j in range(i+1):
		if j**5 - (i-j)**5 == X:
			out2(j,(i-j))
		if -j**5 - (i-j)**5 == X:
			out2(-j,(i-j))
		if -j**5 + (i-j)**5 == X:
			out2(-j,-(i-j))
		if j**5 + (i-j)**5 == X:
			out2(j,-(i-j))



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

int main(){
  string n;
  cin >> n;
  
  for (int i=0 ; i<3 ; i++){
    if (n.at(i) == '1')
      n.at(i) = '9';
    else
      n.at(i) = '1';
  } 
  
  cout << n << endl;
}

Measured memory_bytes: 3624
import sys
import math
import itertools
import statistics
n=int(input())
xy=[]
for _ in range(n):
    xy.append(list(map(int,input().split())))
lis=list(range(n))
per_lis = itertools.permutations(lis)
dis_lis=[]
for one_case in per_lis:
    dis=0
    for i in range(n-1):
        ind=one_case[i]
        stx=xy[ind][0]
        sty=xy[ind][1]
        inde=one_case[i+1]
        gox=xy[inde][0]
        goy=xy[inde][1]
        
        X = (stx-gox)**2
        Y = (sty-goy)**2

        dis += math.sqrt(X+Y)
    dis_lis.append(dis)
print(statistics.mean(dis_lis))



Measured memory_bytes: 99108
s = gets.chomp
s = s.length % 2 == 0 ? s[0,s.length-2] : s[0,s.length-1]
until s[0,s.length/2] == s[s.length/2,s.length/2]
	s = s[0,s.length - 2]
end
puts s.length

Measured memory_bytes: 1788
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>

using namespace std;
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; }

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
typedef long double ldouble;

typedef vector<llong> vecllong;
typedef vector<vecllong> vvecllong;

const llong MOD = 1e9 + 7;
const llong INF = 1e17;

#define FOR(i, n) for (llong i = 0; i < n; i++)
#define FORS(i, a, b) for (llong i = a; i < b; i++)
#define FORR(i, n) for (llong i = n; i > 0; i++)

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

    string S;
    cin >> S;
    llong x, y;
    cin >> x >> y;

    llong index = 0;
    while(index < S.length() && S[index] == 'F') {  // 最初の移動分を取り除く
        x -= 1;
        index++;
    }

    if(index == S.length()) {
        if(x == 0 and y == 0) cout << "Yes" << endl;
        else cout << "No" << endl;
        return 0;
    }

    bool isHolizon = true;
    while(index < S.length() && S[index] == 'T') {
        isHolizon = !isHolizon;
        index++;
    }

    vecllong moveHolizon(0);
    vecllong moveVertical(0);

    while(index < S.length()) {
        llong count = 0;
        while(index < S.length() && S[index] == 'F') {
            count++;
            index++;
        }
        if(isHolizon) moveHolizon.push_back(count);
        else moveVertical.push_back(count);

        while(index < S.length() && S[index] == 'T') {
            isHolizon = !isHolizon;
            index++;
        }
    }

    // x方向に到達可能か
    vector<vector<bool>> dpx(moveHolizon.size() + 1, vector<bool>(20000, false));
    dpx[0][10000] = true;
    llong i = 1;
    for_each(moveHolizon.begin(), moveHolizon.end(), [&](llong dist){
        FOR(j, 20000) {
            if(dpx[i - 1][j]) {
                dpx[i][j + dist] = true;
                dpx[i][j - dist] = true;
            }
        }
        i++;
    });
    if(!dpx[moveHolizon.size()][x + 10000]) {
        cout << "No" << endl;
        return 0;
    }

    // y方向に到達可能か
    vector<vector<bool>> dpy(moveVertical.size() + 1, vector<bool>(20000, false));
    dpy[0][10000] = true;
    i = 1;
    for_each(moveVertical.begin(), moveVertical.end(), [&](llong dist){
        FOR(j, 20000) {
            if(dpy[i - 1][j]) {
                dpy[i][j + dist] = true;
                dpy[i][j - dist] = true;
            }
        }
        i++;
    });
    if(!dpy[moveVertical.size()][y + 10000]) {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 10240
// E - Knapsack 2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// void dpprn(vector<ll> &v, ll inf){
// 	for(int i=0;i<v.size();i++){
// 		if(v[i]==inf) cout<<"∞"; else cout<<v[i];
// 		cout<<((i+1)%10?",\t":"\n");
// 	}
// 	cout<<"--\n";
// }

#define VMAX 100000LL
#define WMAX 1000000000LL
vector<ll> dp(VMAX+1, WMAX+1);

int main(){
	int N,W; cin>>N>>W;
	dp[0] = 0;
	for(int i=1; i<=N; i++){
		ll w,v; cin>>w>>v;
		for(int j=VMAX; j>=v; j--) dp[j] = min(dp[j], dp[j-v] + w);
	}
	// dpprn(dp,WMAX+1);

	ll ans = 0;
	for(ll i=1; i<=VMAX; i++) if(dp[i]<=W) ans = max(ans, i);
	cout<< ans <<endl;
}

Measured memory_bytes: 1024