akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
          #define int long long
            #define inf  1000000007
            #define pa pair<int,int>
    #define ll long long
            #define pal pair<ll,ll>
            #define ppa pair<int,pa>
            #define  mp make_pair
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
            //----------------kokomade temple------------
int n,e,t;
int x[200020];
int dp[200010]={0};
int dp2[200010]={0};
int mod=100000000000000000ll;
int z[200021];
    signed main(){
    	cin>>n>>e>>t;
    	
    	for(int i=1;i<=n;i++) cin>>x[i];
    dp[0]=0;
    	dp2[0]=-2*x[1];
    	x[0]=-mod;

    	int d=0;
    	for(int i=1;i<=n;i++){
    		while(2*x[i]-2*x[d+1]>t)d++;
    		z[i]=d;
    //		cout<<"z"<<i<<" "<<z[i]<<endl;
    	}
    	
    	for(int i=1;i<=n;i++){
    		int u=dp[z[i]]+t;
    		if(z[i]>0)	u=min(u, dp2[z[i]-1]+2*x[i] );
    		dp[i]=u;
    //		cout<<"dp"<<i<<" "<<dp[i]<<endl;
    			dp2[i]=min(dp2[i-1],dp[i]-2*x[i+1]);
    	}
    	
    	
    	cout<<dp[n]+e<<endl;
    	
    			return 0;
    	
    //	printf("%.10f\n",ans);
    	return 0;
    }

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

const int maxn = 1e5 + 10;
vector<int> G[maxn];
int p[maxn], sz[maxn];

void dfs(int now, int fa) {
    p[now] = fa; sz[now] = 1;
    for (int u : G[now]) if (u != fa) {
        dfs(u, now);
        sz[now] += sz[u];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        G[a].push_back(b); G[b].push_back(a);
    }
    dfs(1, 0);
    vector<int> pt; pt.push_back(n);
    int cur = n;
    while (p[cur]) {
        pt.push_back(p[cur]);
        cur = p[cur];
    }
    int ans1 = sz[1], ans2 = sz[2];
    if (pt.size() & 1) ans2 = sz[pt[pt.size() / 2 - 1]], ans1 -= ans2;
    else ans2 = sz[pt[pt.size() / 2 - 1]], ans1 -= ans2;
    cout << (ans1 > ans2 ? "Fennec" : "Snuke") << endl;
    return 0;
}

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

int main() {
    int N, K2; cin >> N >> K2;
    vector<int> V(N); for (int i = 0; i < N; i++) cin >> V[i];
    int ans = 0;
    for (int K = 1; K <= K2; K++) {
        for (int i = 0; 2*i < K; i++) {
            int k = K-i;
            if (k >= N) {
                vector<int> temp(N);
                for (int j = 0; j < N; j++) temp[j] = V[j];
                sort(temp.begin(), temp.end(), greater<int>());
                int t = 0;
                for (int j = 0; j < N-i; j++) t += temp[j];
                ans = max(ans, t);
            } else {
                for (int l = k; 0 <= l; l--) {
                    int r = N-k+l;
                    vector<int> temp;
                    for (int j = 0; j < N; j++) {
                        if (j < l || r <= j) temp.push_back(V[j]);
                    }
                    sort(temp.begin(), temp.end(), greater<int>());
                    int t = 0;
                    for (int j = 0; j < k-i; j++) t += temp[j];
                    ans = max(ans, t);
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ll long long

ll dp[3002][3002];
ll solve(ll a[],ll i , ll j,ll n)
{
    if(i>j)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll buffer=i+n-1-j;
    if(buffer&1)
    {
        return dp[i][j]=min(-a[i]+solve(a,i+1,j,n),-a[j]+solve(a,i,j-1,n));
    }
    else {
        return dp[i][j]=max(a[i]+solve(a,i+1,j,n) , a[j]+solve(a,i,j-1,n));
    }
}

void test_case()
{
    memset(dp,-1,sizeof(dp));
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
        cin>>a[i];
    cout<<solve(a,0,n-1,n);
}

int main()
{
    fastio
//    int t;
//    cin>>t;
//    while(t--)
    test_case();
}


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

#pragma GCC optimize ("O3")

using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	__int128 val = 1, a;
	while(n--){
		long long b;
		cin >> b;
		a = b;
		if(!a) val = 0;
		if(val != -1){
			val *= a;
			if(val > 1000000000000000000ll) val = -1;
		}
	}
	cout << (long long)val << "\n";
}


Measured memory_bytes: 3576
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
#define ll long long
#define lson (rt<< 1)
#define rson (rt<< 1 | 1)
#define gmid ((l+r)>> 1 )
using namespace std;

const int maxn=2000000;
int f[maxn];
int main()
{
	int k,ff=1;
	ll ans=1,a=7;
	cin>>k;
	if(a%k==0) ff=0;
	memset(f,0,sizeof(f));
	while(ff)
	{
		a=(a*10+7)%k;
		ans++;
		if(a==0) break;
		if(f[a]==1)
		{
			ans=-1;
			break;
		}
		f[a]=1;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 11448
// ------------------------------------
// Date:2018/ 3/ 5
// Problem:ABC 083 Libra a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

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

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int l = a + b;
  int r = c + d;

  string ans;
  if (l == r)     ans = "Balanced";
  else if (l > r) ans = "Left";
  else            ans = "Right";

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


Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main(){
  int N;
  int a,b,c;
  scanf("%d",&N);
  a=N/100;
  b=N%100/10;
  c=N%10;
  if(N==(100*c+10*b+a)) printf("Yes\n");
  else printf("No\n");
  return 0;
}

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

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

border = sum / (4*m)

ans = 0
for i in range(n):
    if a[i] >= border:
        ans += 1

if ans >= m:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
a = input().split()
b = input().split()
c = input()
if c == a[0]:
  b[0] = int(b[0])-1
elif c == a[1]:
  b[1] = int(b[1])-1
j = ""
for i in b: 
  j = j + " " + str(i)
print(j)



Measured memory_bytes: 3060
room = [[[0] * 10 for floor in range(3)] for building in range(4)]

n = int(input())
for i in range(n):
    b, f, r, v = map(int,input().split())
    room[b-1][f-1][r-1] += v

for j in range(4):
    if j != 0:
        print('#'*20)
    for k in range(3):
        print('',' '.join(map(str,room[j][k])))



Measured memory_bytes: 5608
package main

import (
  "fmt"
)

func main() {
  var n int 
  fmt.Scan(&n)
  cnt := 0
  for i := 0; i < n; i++ {
    var x int 
    fmt.Scan(&x)
    if x != i + 1 {cnt++}
  }
  ans := "NO"
  if cnt == 0 || cnt == 2 {ans = "YES"}
  fmt.Println(ans)
}

Measured memory_bytes: 512
import java.util.Scanner;
 
public class Main {
	public static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}
	public Main() {
		new aoj106().doIt();
	}
	class aoj106{
		void doIt() {
			int g[] = {2,3,5,10,12,15};
			int m[] = {380,550,850,1520,1870,2244};
			int ans[] = new int [65]; 
			for(int i = 1;i < 65;i++)ans[i] = 100000;
			for(int i = 0;i < 50;i++){
				for(int j = 0;j < 6;j++){
					ans[i+g[j]] = Math.min(ans[i+g[j]], ans[i]+m[j]);
				}
			}
			while(true){
				int n = sc.nextInt();
				if(n == 0)break;
				System.out.println(ans[n/100]);
			}
		}
	}
}

Measured memory_bytes: 17208
#include <iostream>
#include <vector>
using namespace std;
int main(){
	string s, t;
  	cin>>s>>t;
  	vector<vector<int>> dp(s.size(), vector<int>(t.size()));
    vector<vector<pair<int,int>>> bt(s.size(), vector<pair<int, int>>(t.size(), {-1,-1}));
	for(int i =0;i<s.size();i++){
    	for(int j=0;j<t.size();j++){
        	if(s[i]==t[j]){
           		if(i>0 && j>0){
               		dp[i][j] = dp[i-1][j-1] + 1;
                	bt[i][j] = {i-1, j-1};
                }
            	else{                 
                  dp[i][j] = 1;
                  bt[i][j] = {i-1, j-1};
                }
            }else{
              	if(i>0 && dp[i-1][j]> dp[i][j] ){
                 	dp[i][j] =  dp[i-1][j];
                	bt[i][j] = {i-1,j};
                }
              	if(j>0 && dp[i][j-1]>dp[i][j]){
                	dp[i][j] = dp[i][j-1];
                	bt[i][j] = {i, j-1};
                }
            }
        }
    }
      
    string ans;
    int i = s.size()-1;
    int j = t.size()-1;
   	while(i>=0 && j>=0){
      if(s[i]==t[j]){
        ans+=s[i];
      } 
      int tmp = i;
      i = bt[i][j].first;
      j = bt[tmp][j].second;

    } 
	reverse(ans.begin(), ans.end());
  	cout<<ans<<endl;

}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  ll n, k, ans = 0;
  cin >> n >> k;
  for (ll i = k; i <= n + 1; ++i) (ans += n * i - i * i + i + 1) %= MOD;

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


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int ar[100005];
int32_t main(){
	int n;cin>>n;for(int i=1;i<=n;i++){int tmp;cin>>tmp;ar[tmp]=i;}
	for(int i=1;i<=n;i++) cout<<ar[i]<<" ";
}


Measured memory_bytes: 1536
// https://atcoder.jp/contests/abc177/tasks/abc177_b

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
template <typename T>
using VV = V<V<T>>;
using VVL = VV<ll>;
template <typename T>
using VVV = VV<V<T>>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
using asc_pq = priority_queue<T, V<T>, greater<T>>;

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline ll len(V<T> arr) {
  return arr.size();
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}

const ll INF = 1e18;

void solve();

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

void solve() {
  string S, T;
  cin >> S >> T;

  int ss = S.size();
  int ts = T.size();

  ll res = INF;

  rep(offset, ss - ts + 1) {
    ll diff = 0;

    rep(i, ts) {
      if (S[i + offset] != T[i]) diff++;
    }

    chmin(res, diff);
  }

  drop(res);
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	string S;
	int num =0;
	while(cin>>S){
		string T(S);
		reverse(ALL(T));
		if(T==S) num++;
	}
	out(num);
	return 0;
}


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

using namespace std;

using ll = long long;

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

typedef pair<int, int> P;

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 gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

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

//	cout << (double) ((cnt) * pow(n, (m - 1))) / pow(n, m) << endl;
//	cout << (double) (cnt) / n << endl;
//	if (d == 0) cnt = cnt / 2;
//	cout << ((long double) (m - 1) / (long double) n) * ((long double) cnt / (long double) n) << endl;
	printf("%.9f\n",((double) (m - 1) / (double) n) * ((double) cnt / (double) n));
	
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
e = [sum(range(1, pi + 1)) / pi for pi in p]

tmp = 0
for i in range(n):
    tmp += e[i]
    if i >= k:
        tmp -= e[i - k]
    ans = max(ans, tmp)

print(ans)

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

int n;
int m[3] = {-1,0,1};

string solve(vector<string>&v, int i, int cnt){
	
	int u = v[i].back() - '0';
	
	for(int j=0; j<3; j++){
		if((u == 0 and j == 0) or (u == 9 and j == 2)) continue;
		
		int d  = u + m[j];
		char c  = d + '0';
		string s = v[i]+c;
		v.push_back(s);
		cnt++;
		if(cnt == n){
			return s;
		}	
	}
	
	return solve(v, i+1, cnt);
	
}

int main(){
	
	cin >> n;
	
	vector<string>v {"1", "2", "3", "4", "5", "6", "7", "8", "9"};
	
	if(n <=9) cout << v[n-1] << endl;
	else cout << solve(v, 0, 9) << endl;
	
	return 0;
}


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

int dp[3030]; // given i amount of water, how much sugar can i get?
int ps[3030]; // what the most sugar i can get that has weight <= i?

int a,b,c,d,e,f;
double density;
int sugar_water, dissolved_sugar;
int main(){
  scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);

  for(int i = 0; i <= f; i++){
    if(i > 0) ps[i] = max(ps[i], ps[i-1]);

    if(i+c <= f){
      ps[i+c] = max(ps[i+c], ps[i] + c);
    }

    if(i+d <= f){
      ps[i+d] = max(ps[i+d], ps[i] + d);
    }
  }


  dp[0] = 1;

  for(int i = 0; i <= f; i+= 100){
    if(dp[i] != 0){
      if(i + 100*a <= f){
        dp[i+100*a] = 1;
      }

      if(i+100*b <= f){
        dp[i+100*b] = 1;
      }
    }
  }

  density = -1e9;

  for(int i = 100; i <= f; i+=100){
    if(dp[i] != 0){
      int sugar_limit = min(e*i/100, f-i);
      dp[i] = ps[sugar_limit];
      double current_density = dp[i]*1.0/i;
      // printf("%d %d %f\n", i, sugar_limit, current_density);
      if(current_density > density){
        sugar_water = i+dp[i];
        dissolved_sugar = dp[i];
        density = current_density;
      }
    }
  }

  printf("%d %d\n", sugar_water, dissolved_sugar);

  return 0;
}

/*
int a,b,c,d,e,f;

vector<int> water, sugar;
int main(){
  scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);

  for(int i = 0; i*100*a <= f; i++){
    for(int j = 0; j*100*b <= f; j++){
      if(j != 0 || i != 0) water.push_back(i*100*a + j*100*b);
    }
  }

  for(int i = 0; i*c <= f; i++){
    for(int j = 0; j*d <= f; j++){
      if(j != 0 || i != 0) sugar.push_back(i*c + j*d);
    }
  }

  double max_density = -1e9;
  int max_sw = 0, max_sugar = 0;

  for(auto w: water){
    for(auto s: sugar){
      if(w+s <= f && s <= e*w/100){
        double den = s*1.0/w;
        if(den > max_density){
          max_sugar = s;
          max_sw = s+w;
          max_density = den;
        }
      }

    }
  }

  printf("%d %d\n", max_sw, max_sugar);

  return 0;
}
*/


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  long int a,b,d,r;
  double f;
  scanf("%ld %ld",&a,&b);
  d=a/b;
  r=a%b;
  f=(double)a/b;
  printf("%ld %ld %lf\n",d,r,f);
  return 0;
}


Measured memory_bytes: 2760
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map> 
using namespace std;

#define LL long long
#define MOD (1000000007)


//130
int main() {
	LL W, H, x, y;

	scanf("%lld %lld", &W, &H);
	scanf("%lld %lld", &x, &y);

	double result = 1.0 * W * H / 2.0;

	int sub = 0;

	if (x * 2 == W && y * 2 == H) {
		sub = 1;
	}

	printf("%0.6f %d\n", result, sub);

	return 0;
}

//129
/*
int main() {
	LL N, M;

	scanf("%lld %lld", &N, &M);

	static LL dp[100010];
	memset(dp, 0, sizeof(dp));

	for (int i = 0; i < M; i++) {
		LL a;
		scanf("%lld", &a);

		dp[a] = -1;
	}

	dp[0] = 1;
	for (int i = 1; i <= N; i++) {
		if (dp[i] < 0) {
			continue;
		}

		if (dp[i - 1] > 0) {
			dp[i] += dp[i - 1]; //1step
		}
		
		if (i > 1 && dp[i - 2] > 0) {
			dp[i] += dp[i - 2]; //2step
		}

		dp[i] = dp[i] % MOD;
	}

	printf("%lld\n", dp[N]);

}
*/

//128
/*
int main() {
	LL N, M;

	scanf("%lld %lld", &N, &M);

	unsigned int relation[11]; //index->switch No.
	memset(relation, 0, sizeof(relation));

	for (int i = 1; i <= M; i++) {
		LL k;
		scanf("%lld", &k);

		for (int j = 1; j <= k; j++) {
			unsigned int s;
			scanf("%d", &s);

			relation[s] |= (1 << (i - 1));
		}
	}

	unsigned int P = 0;
	for (int i = 1; i <= M; i++) {
		unsigned p;
		scanf("%d", &p);

		if (p > 0) {
			P |= (1 << (i - 1));
		}
	}

	LL result = 0;

	for (unsigned int pattern = 0; pattern < (unsigned int)pow(2, N); pattern++) {
		unsigned int on_off = 0; //bit��0�Ȃ�_��

		for (int i = 1; i <= N; i++) {
			if (((1 << (i - 1)) & pattern) != 0) {
				on_off ^= relation[i];
			}
		}

		on_off ^= P;

		if (on_off == 0) {
			result++;
		}
	}

	printf("%lld\n", result);

}
*/

//127
/*
int main() {
	LL N, M;

	scanf("%lld %lld", &N, &M);

	LL pass_count[100010];
	memset(pass_count, 0, sizeof(pass_count));

	for (int i = 1; i <= M; i++) {
		LL L, R;

		scanf("%lld %lld", &L, &R);

		pass_count[L]++;
		pass_count[R + 1]--;
	}

	LL result = 0;
	for (int i = 1; i <= N; i++) {
		pass_count[i] += pass_count[i - 1];
		if (pass_count[i] == M) {
			result++;
		}
	}

	printf("%lld\n", result);

	return 0;
}
*/


//126
/*
int main() {
	LL N, K;

	cin >> N >> K;

	static double dp[200100];
	memset(dp, 0, sizeof(dp));

	for (int i = 1; i <= N; i++) {
		dp[i] = 1.0 / (double)N;
	}

	for (LL i = 1; i < K; i++) {
		dp[i * 2] += dp[i] * 0.5;
	}

	double result = 0;

	for (LL i = K; i < 200100; i++) {
		result += dp[i];
	}

	printf("%0.11f\n", result);

	return 0;
}
*/

Measured memory_bytes: 256
// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES
#include<math.h>

//#include<cmath>

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>



//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)
//typedef pair < int, int> P;
ll gcd(ll a, ll b) {//最大公約数を求める///最大公倍数a*b/gcd(a,b)
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcd(ll a, ll b) {//最小公倍数を求める　b=0のときaを返す
	if (b == 0) return a;
	return (a / gcd(a, b)) * b;
}
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
vector<int> convertstring(string s) {
	vector<int> d;
	ll n = s.size();
	rep(i, n) {
		d.push_back(s[i] - '0');
	}
	return d;
}

ll  K;
ll dp[1000000] = { 1,2,3,4,5,6,7,8,9,10};
void maker(ll n) {
	vector<int> edig = divnum(dp[n - 1]);
	//cout << edig[0] << endl;
	//reverse(edig.begin(), edig.end());
	auto match = [&](int d) {
		for (int i = d; i > 0; --i) {
			if (edig[i] > 0) {
				edig[i - 1] = edig[i] - 1;
			}
			else {
				edig[i - 1] = 0;
			}
		}
	};
	for(int i = 1; i < edig.size(); i++) {
		//cout << edig[i] << " " << edig[i - 1] << endl;
		if (edig[i] + 1 > edig[i - 1]&&edig[i-1]<9) {
			
			edig[i-1]++;
			match(i - 1);
			break;
		}
		if (i == edig.size() - 1&&edig[i]<9) {
			edig[i]++;
			match(i);
			break;
		}
		else if (i == edig.size() - 1 && edig[i] == 9) {
			edig.push_back(1);//if(dp[n-1]==99)cout << "work" << endl;
			match(i + 1);
			break;
		}
	}
	dp[n] = 0;
	//reverse(edig.begin(), edig.end());
	rep(i, edig.size()) {
		dp[n]+=pow(10, i)* edig[i];
		//cout << edig[i] << " " << n << endl;
	}
}
int main()
{
	cin >> K;
	for (int i = 10; i < K; i++) {
		maker(i);
		//cout << dp[i] << endl;
	}
	cout << dp[K - 1] << endl;
}

Measured memory_bytes: 1152
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		int ct0 = 0;
		int ct1 = 0;
		for(var i=0;i<str.Length;i++){
			string s = str.Substring(i,1);
			if(s=="o"){
				ct0++;
			} else {
				ct1++;
			}
		}
		for(var i=str.Length;i<15;i++){
			ct0++;
		}
		string ans = "NO";
		if(ct0>=8){
			ans = "YES";
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 11092
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

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

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
//constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

void bfs(int start, vector<int>& d, vector<vector<int>> &g) {
	d[start] = 0;
	int last = -1;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		last = cur;
		for (int next : g[cur]) {
			if (d[next] != -1) continue;
			d[next] = d[cur] + 1;
			q.push(next);
		}
	}
}

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

	ll N; scanf("%lld", &N);
	vector<vector<int>> g(N * N);
	vector<int> deg(N * N);
	for (int i = 0; i < 2 * (N * N - N); i++) {
		int a, b; scanf("%d %d", &a, &b);
		a--; b--;
		deg[a]++;
		deg[b]++;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int s1 = -1;
	for (int i = 0; i < N * N; i++) if (deg[i] == 2) {
		s1 = i;
		break;
	}
	vector<vector<int>> res(N, vector<int>(N, -1));
	res[0][0] = s1;
	vector<int> d1(N * N, -1);
	bfs(s1, d1, g);
	int s2 = -1;
	vector<int> d2(N * N, -1);
	for (int i = 0; i < N * N; i++) {
		if (d1[i] == N - 1 && deg[i] == 2) {
			s2 = i;
			break;
		}
	}
	res[0][N - 1] = s2;
	bfs(s2, d2, g);
	vector<vector<int>> d1_idx(N + N + 10);
	for (int i = 0; i < N * N; i++) d1_idx[d1[i]].push_back(i);
	vector<bool> used(N * N, false);
	used[s1] = true;
	used[s2] = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (res[i][j] != -1) continue;
			ll dist1 = i + j;
			ll dist2 = N - 1 + i - j;
			for (auto e : d1_idx[dist1]) {
				if (used[e]) continue;
				if (d2[e] == dist2) {
					res[i][j] = e;
					used[e] = true;
					break;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << res[i][j] + 1;
			if (j == N - 1) cout << "\n";
			else cout << " ";
		}
	}
	return 0;
}


Measured memory_bytes: 3924
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

string mr(string s,char c){
	string ret(s.size(),'a');
	if(c=='C'){
		if(s.size()==1)return s;
		ret=s.substr(1)+s[0];
	}
	if(c=='J'){
		if(s.size()==1)return s;
		ret=s[s.size()-1]+s.substr(0,s.size()-1);
	}
	if(c=='A'){
		reverse(all(s));
		return s;
	}
	if(c=='E'){
		ret=s.substr(s.size()/2+s.size()%2)+(s.size()%2==1?s.substr(s.size()/2,1):"")+s.substr(0,s.size()/2);
	}
	if(c=='M'){
		rep(i,s.size()){
			if('0'<=s[i]&&'9'>=s[i]){
				int num=s[i]-'0';
				num+=1;num%=10;
				ret[i]=char(num+'0');
			}
			else ret[i]=s[i];
		}
	}
	if(c=='P'){
		rep(i,s.size()){
			if('0'<=s[i]&&'9'>=s[i]){
				int num=s[i]-'0';
				num+=9;num%=10;
				ret[i]=char(num+'0');
			}
			else ret[i]=s[i];
		}
	}
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	while(n--){
		string s,op;
		cin>>op>>s;
		rrep(i,op.size()){
			s=mr(s,op[i]);
		}
		cout<<s<<"\n";
	}
}


Measured memory_bytes: 3164
#include <stdio.h>
int main(){
        
        char c[1200];
        int a[26]={};
        int i;
        
        while(scanf("%s",c)!=EOF){
                for(i=0;c[i];i++){
                        if('a'<=c[i]&&c[i]<='z')a[c[i]-'a']++;
                        if('A'<=c[i]&&c[i]<='Z')a[c[i]-'A']++;
                }
        }
        
        for(i=0;i<26;i++){
                printf("%c : %d\n",'a'+i,a[i]);
        }
        
        return 0;
}



Measured memory_bytes: 2068
#include<bits/stdc++.h>
using namespace std;
const int mod = 200003;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define fr(s,n) for (int i=(int)(s);i<(int)(n);i++)
#define lc cout<<"\n"

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int k;
    cin>>k;
    string s;
    cin>>s;
    if(s.length()<=k){
        cout<<s;
    }
    else{
        cout<<s.substr(0,k)<<"...";
    }
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;cin>>n;
  map<ll,ll>cnt;
  while(n--){
    ll a;cin>>a;
    cnt[a]++;
  }
  bool fl = true;
  cin>>m;
  while(m--){
    ll a;cin>>a;
    if(cnt[a] == 0)fl =false;
    else cnt[a]--;
  }
  if(fl)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}


Measured memory_bytes: 12800
#include<stdio.h>

int main() {
    //変数の宣言
    //b棟f階のr番目の部屋にv人 vが負の数の時は退去者数を示す
    //入居者数　0 <= v <= 9
    int n; //情報の数
    int b, f, r, v;
    int hako[5][4][11];
    int i;//処理用
    
    for (b=1; b<=4; b++) {
        for (f=1; f<=3; f++) {
            for (r=1; r<=10; r++) {
                hako[b][f][r] = 0;
            }
        }
    }
    
    //入力
    scanf ("%d", &n);
    
    for (i=0; i<n; i++) {
        scanf("%d %d %d %d", &b, &f, &r, &v);
        hako[b][f][r] += v; //加える（負の数の場合あり）
    }
    
    for (b=1; b<=4; b++) {
        for (f=1; f<=3; f++) {
            for (r=1; r<=10; r++) {
                printf(" %d", hako[b][f][r]);
            }
            printf("\n");
        }
        if (b != 4) {
            printf("####################\n");
        }
    }
    
    
    return 0;
}



Measured memory_bytes: 2108
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] b = new int[a];
		int c;
		int d;
		int e;
		int f;
		int count = 0;
		for(int i = 0; a>i; i++) {
			c = sc.nextInt();
			b[i] = c;
		}

		for(int i = 1; a-1 > i ; i++) {
			d = b[i-1];
			e = b[i];
			f = b[i+1];
			if((e > d || e > f) && (e < d || e < f)) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

ll f(ll a, ll b){
	if(a > b)swap(a, b);
	if(b % a == 0){
		return (2 * (b / a) - 1) * a;
	}
	return (2 * (b / a)) * a + f(a, b % a);
}

int main(){
	ll N, X;
	cin >> N >> X;

	ll res = N + f(X, N - X);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
while 1:
	H, W = map(int, raw_input().split())
	if H == 0 and W == 0:
		break
	else:
		for h in range(0, H):
			for w in range(0, W):
				if (h + w) % 2 == 0:
					sys.stdout.write("#")
				else:
					sys.stdout.write(".")
			print ""
		print ""

Measured memory_bytes: 4208
/*input
10 10
*/
#include <bits/stdc++.h>
#define getcx getchar_unlocked
#define putcx putchar_unlocked
#define pb(x) push_back(x);
#define in(y) insert(y);
#define tt(t) while(t--)
#define itr ::iterator it;
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define si set<int>                      
#define msi map<string, int>
#define lines printf("\n")
#define ff(n) for(int i=0;i<n;i++)
#define fors(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
using namespace std;
#define MOD 1000000007

int main()
{
    int n,k;
    cin>>n>>k;
    int x=1;
    while(n--){
        if(x*2<x+k) x*=2;
        else x+=k;
    }
    cout<<x;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(x) (int)((x).size())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define FOR(i, a, n, step) for (int (i) = (a); (i) < (int)(n); (i) += (step))
#define ROF(i, a, n, step) for (int (i) = (a); (i) >= (int)(n); (i) += (step))
#define FOREACH(it, v) for (auto (it) : (v))
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll ;
typedef long double ld;
typedef pair <int, int> pii;
 
template <class T>
const bool is_impar(const T &x) {return (bool) (x & 1);}
 
int a, b, c;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b >> c;
    if (a > b)
        swap(a, b);
    if (a > c)
        swap(a, c);
    if (b > c)
        swap(b, c);
    cout << b - a + c - b;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);cout.precision(20);}} fast;

/* define */
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) (upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X))
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define ctoi(C) (C-'0')
#define pow2(x) ((long long)((long long)1<<x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1,0,-1,0};
const long long dy[] = {0,1,0,-1};
const long long dx8[] = {1,1,0,-1,-1,-1,0,1};
const long long dy8[] = {0,1,1,1,0,-1,-1,-1};
const long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};
const long long dy9[] = {0,1,1,1,0,-1,-1,-1,0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
long long max(long long x,int y){return max(x,(long long)y);}
long long max(int x,long long y){return max((long long)x,y);}
long long min(long long x,int y){return min(x,(long long)y);}
long long min(int x,long long y){return min((long long)x,y);}

/* liblary */



/* main */

void TLE(bool b){
	int a = 0;
	while(!b){
		a += 1;
	}
}

ll A,B,Q;
vl s,t,x;

signed main(){
	cin >> A >> B >> Q;
	s.resize(A);t.resize(B);x.resize(Q);
	FOR(i,0,A)cin >> s[i];
	FOR(i,0,B)cin >> t[i];
	FOR(i,0,Q)cin >> x[i];
	vl S(A,LINF);
	vl T(B,LINF);
	FOR(i,0,A){
		ll idx1 = upper_bound(ALL(t),s[i]) - t.begin();
		ll idx2 = idx1 - 1;
		if(0 <= idx1 && idx1 < t.size())chmin(S[i],abs(s[i]-t[idx1]));
		if(0 <= idx2 && idx2 < t.size())chmin(S[i],abs(s[i]-t[idx2]));
	}
	FOR(i,0,B){
		ll idx1 = upper_bound(ALL(s),t[i]) - s.begin();
		ll idx2 = idx1 - 1;
		if(0 <= idx1 && idx1 < s.size())chmin(T[i],abs(t[i]-s[idx1]));
		if(0 <= idx2 && idx2 < s.size())chmin(T[i],abs(t[i]-s[idx2]));
	}
	FOR(i,0,Q){
		ll idx1 = upper_bound(ALL(s),x[i]) - s.begin();
		ll idx2 = upper_bound(ALL(t),x[i]) - t.begin();
		vl tmp1,tmp2;
		if(idx1 < s.size())tmp1.pb(idx1);
		if(idx2 < t.size())tmp2.pb(idx2);
		if(idx1 != 0)tmp1.pb(idx1-1);
		if(idx2 != 0)tmp2.pb(idx2-1);
		ll ans = LINF;
		FOR(j,0,tmp1.size()){
			ll tmp = abs(x[i] - s[tmp1[j]]) + S[tmp1[j]];
			chmin(ans,tmp);
		}
		FOR(j,0,tmp2.size()){
			ll tmp = abs(x[i] - t[tmp2[j]]) + T[tmp2[j]];
			chmin(ans,tmp);
		}
		cout << ans << endl;
	}
}

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

using namespace std;

class LetterData
{
public:
    LetterData(int size) : count(26, vector<int>(size, 0)) {}

    void AddLetter(char ch, int pos)
    {
        count[ch - 'a'][pos] += 1;
    }

    void PartialSums()
    {
        for (auto &vec : count) {
            for (size_t i = 1; i < vec.size(); i += 1) {
                vec[i] += vec[i - 1];
            }
        }
    }

    int CountCommon(int split_pos) const
    {
        int common = 0;
        for (char ch = 'a'; ch <= 'z'; ch += 1) {
            int right_end = count[ch - 'a'].size() - 1;
            auto has_left = HasLetter(ch, 0, split_pos);
            auto has_right = HasLetter(ch, split_pos + 1, right_end);

            common += (has_left && has_right ? 1 : 0);
        }
        return common;
    }

private:
    bool HasLetter(char ch, int left, int right) const
    {
        int sum = count[ch - 'a'][right];
        if (left > 0) {
            sum -= count[ch - 'a'][left - 1];
        }
        return sum > 0;
    }

    vector<vector<int>> count;
};

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

    string str;
    getline(cin, str);

    LetterData data(n);
    for (int i = 0; i < n; i += 1) {
        data.AddLetter(str[i], i);
    }

    data.PartialSums();

    int res = 0;
    for (int i = 0; i < n; i += 1) {
        res = max(res, data.CountCommon(i));
    }

    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ n, m, x ] <- readInts
	as <- readInts
	let
		lt = length $ filter ( < x ) $ as
		gt = length $ filter ( > x ) $ as
	print $ min lt gt

Measured memory_bytes: 892
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
p=0
for i in range(h):
    j=input()
    p+=j.count('#')
    l.append('#'+j+'#')
l.append('#'*(w+2))
q=deque([[1,1]])
s=[[-1 for j in i] for i in l]
s[1][1]=1
while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
        if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
            q.append([x+i,y+j])
            s[x+i][y+j]=s[x][y]+1
    if s[h][w]!=-1:
        break
if s[h][w]!=-1:
  print(h*w-p-s[h][w]) 
else:
  print(-1)

Measured memory_bytes: 3316
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
ans = min(abs(n % k - k), n % k)
print(ans)

Measured memory_bytes: 38256
from math import ceil

n, k = map(int, input().split())

arr = list(map(int, input().split()))

index = arr.index(1)

left = ceil(index / (k - 1))
left_used = (k - 1) * (left - 1) + k

right = ceil((n - left_used) / (k - 1))

print(left + right)


Measured memory_bytes: 13812
from sys import stdin

a = stdin.readline().rstrip()
b = [int(x) for x in stdin.readline().rstrip().split()]
count = 0

while(True):
  if sum([x % 2 for x in b]) == 0:
    count += 1
    b = [x // 2 for x in b]
  else:
    break
    
print(count)

Measured memory_bytes: 3060
#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, A, B = read_h()
    print(min(A * N, B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};


template<typename T>
struct BIT{
    vector<T> bit;
    BIT(int n) : bit(n+1) {}
    void add(int a,T w){
        for(int x=++a; x < bit.size(); x+=(x&(-x)) ){
            bit[x] += w;
        }
    }
    // return v[0]+v[1]+...+v[a-1];
    T sum(int a){
        T ret=0;
        for(int x=a;x>0;x-=(x&(-x)) ){
            ret+=bit[x];
        }
        return ret;
    }
};


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int q;
    cin>>q;
    while(q--){
        ll n;
        cin>>n;
        ll ans = 0;
        vector<vector<ll>> l(n+1),r(n+1);
        for(int i=0;i<n;i++){
            ll k,a,b;
            cin>>k>>a>>b;
            if(a>b)l[k-1].push_back(a-b);
            else r[k].push_back(b-a);
            ans += min(a,b);
        }
        priority_queue<ll> pq;
        for(int i=0;i<n;i++){
            for(auto j:r[i])pq.push(j);
            if(pq.size()){
                ans += pq.top();
                pq.pop();
            }
        }
        while(pq.size())pq.pop();
        for(int i=n-1;i>=0;i--){
            for(auto j:l[i])pq.push(j);
            if(pq.size()){
                ans += pq.top();
                pq.pop();
            }
        }
        cout << ans << "\n";
    }
}

Measured memory_bytes: 17384
#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>
#include <random>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

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

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7;
const int MAXN = static_cast<int>(1e6) + 17;

int n;
int ans[MAXN];
pair<int, int> a[MAXN];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> a[i].first;

    return true;
}

void solve() {
    forn (i, n)
        a[i].second = i;

    sort(a, a + n);
    int m = (n - 1) / 2;

    forn (i, n) {
        if (i <= m)
            ans[a[i].second] = a[m + 1].first;
        else
            ans[a[i].second] = a[m].first;
    }

    forn (i, n)
        cout << ans[i] << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::mt19937 rand('S' + 'E' + 'R' + 'E' + 'Z' + 'H' + 'K' + 'A');

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 7936
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int n,m,par[N],dir[N];
 
void init() 
{
    for (int i=1;i<=n;i++)
	   par[i]=i,dir[i]=0;
}
 
int fd(int x) 
{
    if (x==par[x])
	   return x;
    int t=par[x];
    par[x]=fd(par[x]);
    dir[x]+=dir[t];
    return par[x];
}
 
void unite(int x,int y,int c) 
{
    int a=fd(x),b=fd(y);
    if (a==b) 
	   return;
    dir[a]=-dir[x]+c+dir[y];
    par[a]=b;
}
 
int main()
{
    cin>>n>>m;
    int l,r,d;
	init();
    bool ok=true;
    for (int i=1;i<=m;i++)
	{
        cin>>l>>r>>d;
        if (fd(l)!=fd(r)) 
		   unite(l,r,d);
        else if (dir[l]-dir[r]!=d) 
		   ok=false;
    }
    if (ok)
       cout<<"Yes";
    else
       cout<<"No";
    return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
vector<int> stk(60000);
int top = 0;

bool isEmpty() {
  return top == 0;
}

void push(int i) {
  stk.at(top) = i;
  top++;
}

int pop() {
  top--;
  return stk.at(top);
}

int main() {
  string s;
  while (cin >> s) {
    if (s == "+") {
      int a = pop();
      int b = pop();
      push(a+b);
    } else if (s == "-"){
      int a = pop();
      int b = pop();
      push(b-a);
    } else if (s == "*") {
      int a = pop();
      int b = pop();
      push(a*b);
    } else {
      push(stoi(s));
    }
  }
  cout << pop() << endl;
}



Measured memory_bytes: 3212
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    if max([max(l) for l in c]) > k:
        continue

    tmp_ans = g - 1
    now = [0] * g

    for j in range(w):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > k:
                tmp_ans += 1
                now = [c[gi][j] for gi in range(g)]
                break

    ans = min(ans, tmp_ans)

print(ans)

Measured memory_bytes: 49116
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

vector<ull> A(100000, 0);

int main() {
    ull N, a, b, c, Q;
    ull s = 0;
    cin >> N;
    for (ull i = 0; i < N; i++) {
       cin >> a;
       A[a-1]++;
       s += a;
    }
    cin >> Q;
    for (ull i = 0; i < Q; i++) {
        cin >> b >> c;
        s += (c-b)*A[b-1];
        A[c-1] += A[b-1];
        A[b-1] = 0;
        cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 3812
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  ll q;
  cin>>q;
  string f,t;
  bool isreverse=false;
  for(int i=0;i<q;i++){
    int a;
    cin>>a;
    if(a==1) isreverse=!isreverse;
    else{
      if(isreverse){
        int k;
        cin>>k;
        char c;
        cin>>c;
        if(k==1) t.push_back(c);
        else f.push_back(c);
      }
      else{
        int k;
        cin>>k;
        char c;
        cin>>c;
        if(k==1) f.push_back(c);
        else t.push_back(c);
      }
    }
  }
  reverse(f.begin(),f.end());
  f+=s;
  f+=t;
  if(isreverse) reverse(f.begin(),f.end());
  cout<<f<<endl;
}


Measured memory_bytes: 1348