akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#define dump(x) cerr << #x " = " << x << endl
#define unittest_name_helper(counter) unittest_ ## counter
#define unittest_name(counter) unittest_name_helper(counter)
#define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) ()
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, int(xs.size()) - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }

ll solve(int l, vector<ll> const & a) {
    vector<ll> acc(l + 1);
    partial_sum(ALL(a), acc.begin() + 1);
    // 0: no flow
    // 1: one flow
    // 2: two flows, left connected
    // 3: two flows, right connected
    array<ll, 4> cur = {}, prv;
    ll answer = acc[l];
    REP (i, l) {
        swap(cur, prv);
        fill(ALL(cur), LLONG_MAX);
        chmin(cur[0], prv[0] + a[i]);
        chmin(cur[1], prv[0]);
        chmin(cur[1], prv[1] + (a[i] == 0 ? 1 : a[i] % 2 == 0 ? 1 : 0));
        chmin(cur[1], prv[2] + (a[i] == 0 ? 1 : a[i] % 2 == 0 ? 1 : 0));
        chmin(cur[2], prv[0] + a[i] % 2);
        chmin(cur[2], prv[2] + (a[i] == 0 ? 2 : a[i] % 2 == 0 ? 0 : 1));
        chmin(cur[3], prv[0]);
        chmin(cur[3], prv[1] + (a[i] == 0 ? 1 : 0));
        chmin(cur[3], prv[3] + (a[i] == 0 ? 2 : a[i] % 2 == 0 ? 0 : 1));

        chmin(answer, *min_element(ALL(cur)) + acc[l] - acc[i + 1]);
// cerr << i << " : " << a[i] <<  " : " << cur[0] << ' ' << cur[1] << ' ' << cur[2] << ' ' << cur[3]<< endl;
    }
    return answer;
}

int main() {
    int l; cin >> l;
    vector<ll> a(l);
    REP (i, l) cin >> a[i];
    cout << solve(l, a) << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
    ll i,n,j,x,y,m=1e12+7;
    cin>>n;

    for(i=1; i<=sqrt(n); i++)
    {
        if(n%i==0)
        {
            x=i;
            y=n/i;
            if(x+y<m)
                m=x+y;
        }
    }
    cout<<m-2<<endl;
    return 0;
}


Measured memory_bytes: 256
al = {"a":"*","b":"*","c":"*","d":"*","e":"*","f":"*","g":"*","h":"*","i":"","j":"*","k":"*","l":"*","m":"*","n":"*","o":"*","p":"*","q":"*","r":"*","s":"*","t":"*","u":"*","v":"*","w":"*","x":"*","y":"*","z":"*"}
N = int(input())
S = input()
K = int(input())
del al[S[K-1]]
print(S.translate(str.maketrans(al)))

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main(void){
    int n, l, min = 1000000000, sum = 0;
    cin >> n >> l;

    vector<int> t(n);
    for(int i = 0;i < n;i++){
        t[i] = l+i;
        if(abs(t[i]) < abs(min)){
            min = t[i];
        } 
        sum += t[i];
    }

    cout << sum-min << endl;

    return 0;
}

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

typedef long long ll;
const ll MOD = 1000000007;

int main(){
	static string s;
	cin >> s;
	static ll dp[100010][13] = {};
	
	dp[s.size()][0] = 1;
	ll t = 1;
	for(int i = s.size()-1 ; i >= 0 ; i --){
		if(s[i] == '?'){
			for(int j = 0 ; j < 13 ; j ++){
				for(int k = 0 ; k < 10 ; k ++){
					dp[i][(j+k*t)%13] += dp[i+1][j];
				}
			}
		}
		else {
			for(int j = 0 ; j < 13 ; j ++){
				dp[i][(j+(s[i]-'0')*t)%13] += dp[i+1][j];
			}
		}
		for(int j = 0 ; j < 13 ; j ++){
			dp[i][j] %= MOD;
		}
		t *= 10;
		t %= 13;
	}
	cout << dp[0][5] << endl;
}
	

Measured memory_bytes: 10624
N = int(input())
ashiba = list(map(int, input().split()))
f_inf = float("inf")

dp = [0] * 10 ** 5
for i in range(len(dp)):
    dp[i] = f_inf

dp[0] = 0

for i in range(1, N):
    dp[i] = min(dp[i], dp[i - 1] + abs(ashiba[i] - ashiba[i - 1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i - 2] + abs(ashiba[i] - ashiba[i - 2]))

print(dp[N - 1])


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

int main() {

long long t = 1;
//cin >> t;
while(t--){
	string s;
	int c;
	c = 0;
	cin >>s;
	int n = s.length();
	for(int i = 0; i < n/2; ++i){
		if(s[i] != s[n-i-1]) c++;
	}
	cout << c;
}
return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

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

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll ans[100100],jm[100100],dist[2][225816];
int c[100100];
vector<P> g[225816];
priority_queue<P, vector<P>, greater<P> > pq;

int main(void){
	int n,m,k,i,j,u,v;
	ll p,t;
	fill(ans,ans+100100,-INFLL);
	fill(dist[0],dist[2],INFLL);
	cin >> n >> m >> k;
	for(i=0; i<n; ++i){
		cin >> p;
		g[i+n].push_back(P(MOD-p,i));
	}
	for(i=0; i<n; ++i){
		cin >> c[i]; --c[i];
	}
	for(i=0; i<n; ++i){
		cin >> jm[i];
	}
	for(i=0; i<m; ++i){
		cin >> u >> v >> t;
		--u; --v;
		g[u].push_back(P(t,v));
		g[v].push_back(P(t,u));
		g[u+n].push_back(P(t,v+n));
		g[v+n].push_back(P(t,u+n));
	}
	for(j=0; j<2; ++j){
		dist[j][n*j] = 0ll;
		pq.push(P(dist[j][n*j],n*j));
		while(!pq.empty()){
			u = pq.top().second;
			t = pq.top().first;
			pq.pop();
			if(t > dist[j][u]){
				continue;
			}
			for(i=(g[u].l_ength()-1); i>=0; --i){
				v = g[u][i].second;
				t = g[u][i].first;
				if(dist[j][v] > dist[j][u] + t){
					dist[j][v] = dist[j][u] + t;
					pq.push(P(dist[j][v],v));
				}
			}
		}
	}
	for(i=0; i<n; ++i){
		ans[c[i]] = max(ans[c[i]],jm[i]+MOD-dist[0][i]-dist[1][i]);
	}
	for(i=0; i<k; ++i){
		cout << ans[i] << endl;
	}
	return 0;
}




Measured memory_bytes: 38244
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func stringLineScan() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(stringLineScan())
	c := make(map[int]int)
	for i := 1; i <= n; i++ {
		pf := PrimeFactors(i)
		for _, v := range pf {
			c[v]++
		}
	}
	ans := 1
	for _, v := range c {
		ans = ans * (v + 1) % 1000000007
	}
	fmt.Println(ans)
}
func PrimeFactors(n int) (pfs []int) {
	for n%2 == 0 {
		pfs = append(pfs, 2)
		n = n / 2
	}
	for i := 3; i*i <= n; i = i + 2 {
		for n%i == 0 {
			pfs = append(pfs, i)
			n = n / i
		}
	}
	if n > 2 {
		pfs = append(pfs, n)
	}
	return
}


Measured memory_bytes: 768
import sys
input = sys.stdin.readline

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])


Measured memory_bytes: 99932
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int N,K;
    cin>>N>>K;
    int A[N];
    rep(i,N)A[i]=0;
    int kind=0;
    rep(i,N){
        int a; cin>>a;
        if(A[a-1]==0)kind++;
        A[a-1]++;
    }
    int ans=0;
    sort(A,A+N);
    int i=0;
    while(kind>K){
        if(A[i]!=0){
            kind--;
            ans+=A[i];
        }
        i++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4340
function Main(input) {

	input = input.split("\n");
  	data = input[0].split(" ");
  	each_data = input[1].split(" ");

	var member_cnt = parseInt(data[0], 10);
	var max_hight = parseInt(data[1],10);
  
  	var parce_cnt = 0;
  
  	for(var cnt=0; cnt<member_cnt; cnt++){
      	if(max_hight <= parseInt(each_data[cnt])){
          	parce_cnt++;
        }
    }
  
	console.log(parce_cnt);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using ld=long double;

signed main(){
  int N;cin>>N;
  int xz,vz;cin>>xz>>vz;
  std::vector<ld> x(N),v(N);
  for(int i=0;i<N;i++)cin>>x[i]>>v[i];
  for(int i=0;i<N;i++)x[i]-=xz,v[i]-=vz;
  //v>0,x<0の奴を使って折れ線を作る
  typedef pair<ld,ld> P;
  std::vector<P> w;
  for(int i=0;i<N;i++)if(v[i]>0&&x[i]<0)w.push_back(P(v[i],x[i]));
  sort(w.begin(),w.end());
  typedef pair<P,ld> PI;
  vector<PI> oresen;//これが使われ始める時間,場所,その傾き
  oresen.push_back(PI(P(0,0),0));
  for(int i=0;i<w.size();i++){
    ld V=w[i].first,X=w[i].second;
    if(i+1<w.size()&&w[i+1].first==V)continue;
    auto ite=oresen.rbegin();
    bool f=true;
    while(f){
      auto tmp=*ite;
      ld ti=tmp.first.first,po=tmp.first.second;
      if(X+ti*V>po){
        oresen.erase(oresen.rbegin().base());//計算量はならしなのでそんなに大きくはならない
        ite=oresen.rbegin();
      }
      else f=false;
    }
    auto tmp=*ite;
    ld ti=tmp.first.first,po=tmp.first.second,inc=tmp.second;
    ld newti=(po-X-ti*V)/(V-inc);
    ld T=ti+newti;
    oresen.push_back(PI(P(T,X+V*T),V));
  }
  std::vector<ld> ans(N);
  for(int i=0;i<N;i++){
    if(x[i]<0)continue;
    int l=0,r=oresen.size();
    while(r-l>1){
      int m=(l+r)>>1;
      ld ti=oresen[m].first.first,po=oresen[m].first.second;
      if(x[i]+v[i]*ti>=po)l=m;
      else r=m;
    }
    ld ti=oresen[l].first.first,po=oresen[l].first.second,inc=oresen[l].second;
    ld newti=(po-x[i]-ti*v[i])/(v[i]-inc);
    ans[i]=ti+newti;
  }


  //逆をやる　だいたいコピペ　全てのvとxを逆にしてやる
  for(int i=0;i<N;i++)v[i]*=-1,x[i]*=-1;
  std::vector<P> w2;
  for(int i=0;i<N;i++)if(v[i]>0&&x[i]<0)w2.push_back(P(v[i],x[i]));
  sort(w2.begin(),w2.end());
  //typedef pair<P,ld> PI;
  vector<PI> oresen2;//これが使われ始める時間,場所,その傾き
  oresen2.push_back(PI(P(0,0),0));
  for(int i=0;i<w2.size();i++){
    ld V=w2[i].first,X=w2[i].second;
    if(i+1<w2.size()&&w2[i+1].first==V)continue;
    auto ite=oresen2.rbegin();
    bool f=true;
    while(f){
      auto tmp=*ite;
      ld ti=tmp.first.first,po=tmp.first.second;
      if(X+ti*V>po){
        oresen2.erase(oresen2.rbegin().base());
        ite=oresen2.rbegin();
      }
      else f=false;
    }
    auto tmp=*ite;
    ld ti=tmp.first.first,po=tmp.first.second,inc=tmp.second;
    ld newti=(po-X-ti*V)/(V-inc);
    ld T=ti+newti;
    oresen2.push_back(PI(P(T,X+V*T),V));
  }
  //std::vector<ld> ans(N);
  for(int i=0;i<N;i++){
    if(x[i]<0)continue;
    int l=0,r=oresen2.size();
    while(r-l>1){
      int m=(l+r)>>1;
      ld ti=oresen2[m].first.first,po=oresen2[m].first.second;
      if(x[i]+v[i]*ti>=po)l=m;
      else r=m;
    }
    ld ti=oresen2[l].first.first,po=oresen2[l].first.second,inc=oresen2[l].second;
    ld newti=(po-x[i]-ti*v[i])/(v[i]-inc);
    ans[i]=ti+newti;
  }
  for(int i=0;i<N;i++)if(ans[i]<0)ans[i]=-1;
  for(int i=0;i<N;i++)cout<<fixed<<setprecision(12)<<ans[i]<<endl;
}



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

int N,M;
int A[111];
int res[111];
int main(){
  cin >> N >> M;
  for(int i=0;i<M;i++){
    cin >> A[i];
    --A[i];
  }
  for(int i=0;i<M;i++){
    for(int j=0;j<N;j++){
      int b; cin >> b; --b;
      if( A[i] == b ) res[j]++;
      else res[A[i]]++;
    }
  }
  for(int i=0;i<N;i++) cout << res[i] << endl;
}

Measured memory_bytes: 1160
A,B,C=map(int,input().split())

#print(A,B,C)

week=A*7+B
W=int(C/week)
W1=int(W*week)
r=int(C-W1)

a=int((r+A-1)/A)

if(a>7):
    a=7

a+=W*7
print(a)



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

unordered_map<string, bool>mp;
bool check(string s) {
	if (s.empty())return true;
	if (*s.begin() != 'm' || *s.rbegin() != 'w')return false;
	if (mp.find(s) != mp.end())return mp[s];
	for (int i = 1; i < s.size() - 1; i++) {
		if (s[i] != 'e')continue;
		if (check(s.substr(1, i - 1)) && check(s.substr(i + 1, s.size() - i - 2)))return mp[s] = true;
	}
	return mp[s] = false;
}
int main() {
	string s; cin >> s;
	puts(check(s) ? "Cat" : "Rabbit");
}

Measured memory_bytes: 7248
N,A,B,C=map(int,input().split())

hashmap=dict()
hashmap={"A":A,"B":B,"C":C}
arr=[int(0) for i in range(N)]
for i in range(N):
    arr[i]=input()
    
output=[]

for i in range(N):
    string=arr[i]
    first=string[0]
    second=string[1]

    if hashmap[first]==0 and hashmap[second]==0:
        print("No")
        break
    elif hashmap[first]==0:
        hashmap[first]+=1
        hashmap[second]-=1
        output.append(first)
    elif hashmap[second]==0:
        hashmap[second]+=1
        hashmap[first]-=1
        output.append(second)
    elif i<N-1 and (first in arr[i+1]):
        hashmap[first]+=1
        hashmap[second]-=1
        output.append(first)
    elif i<N-1 and (second in arr[i+1]):
        hashmap[second]+=1
        hashmap[first]-=1
        output.append(second)
    else:
        output.append(first)
else:
    print("Yes")
    for i in output:
        print(i)                            


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};



int main(){
	string n, m;
	cin >> n;
	m[0] = n[0] - 0x20;
	cin >> n;
	m[1] = n[0] - 0x20;
	cin >> n;
	m[2] = n[0] - 0x20;
	cout << m[0] << m[1] << m[2] << endl;
	return 0;
}

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

int main() {
  int h, n;
  cin >> h >> n;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    h -= a;
  }
  if (h <= 0) {
    puts("Yes");
  } else {
    puts("No");
  }
}


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

int main(void){
    int a,b;
    cin>>a>>b;
    if (a==b) {
        cout<<"Draw"<<endl;
        return 0;
    }
    if (a==1) cout<<"Alice"<<endl;
    else if (b==1) cout<<"Bob"<<endl;
    else if (a>b) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
    return 0;
}

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

using namespace std;

int kaibun(int A, int B ) {
    int cou = 0;
    for (int i = A; i <= B; i++) {
        int k = i;
        if (k / 10000 == k % 10) {
            k /= 10;
            k %= 1000;
            if (k / 100 == k % 10) {
                cou++;
            }
        }
    }
    return cou;
}

int main() {
    int A, B;
    cin >> A >> B;
    int ans = kaibun(A,B);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:>
問題文============================================================

=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll sum[4] = {0};
    ll kakeru[4] = { 6000,4000,3000,2000};
    for(int i = 0; i < 4;i++){
        ll t,n; cin >> t >> n;
        cout << kakeru[t-1]*n << endl;

    }
	return 0;
}



Measured memory_bytes: 3188
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double>> any;
template<typename T> inline void pr(const vector<T> &xs){
	if(xs.empty()){
		cout << endl;
	} else {
		for(int i=0; i<xs.size()-1; i++) cout << xs[i] << " ";
		cout << xs[xs.size()-1] << endl;
	}
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

ll gcd(ll x, ll y){
	if(y==0) return x;
	else return gcd(y, x%y);
}

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

	vector<int> x;
	for(int i=2; i<31; i++){
		if((i%2==0||i%3==0||i%5==0)&&i!=15) x.push_back(i);
	}
	debug(x);
	debug(any{(int)x.size()});

	vector<int> small(x.size()+1);

	for(int i=1; i<(1<<x.size()); i++){
		int sum = 0;
		int nbit = 0;
		for(int k=0; k<x.size(); k++){
			if((i>>k)&1){
				sum += x[k];
				nbit++;
			}
		}
		if(sum%30!=0) continue;
		bool ok = true;
		int g = -1;
		for(int k=0; k<x.size(); k++){
			if((i>>k)&1){
				if(gcd(sum-x[k], x[k])==1){
					ok = false;
					break;
				}
				if(g<0) g=x[k];
				else g=gcd(g, x[k]);
			}
		}
		if(ok&&g==1||nbit<3) small[nbit] = i;
	}

	debug(small);

#ifdef DEBUG
	for(int i=0; i<=x.size(); i++){
		vector<int> a;
		for(int k=0; k<x.size(); k++){
			if((small[i]>>k)&1) a.push_back(x[k]);
		}
		debug(a);
	}
#endif

	int mod = (N-1)%x.size()+1;
	int rep = (N-1)/x.size();

	vector<int> ans;
	for(int k=0; k<x.size(); k++){
		if((small[mod]>>k)&1) ans.push_back(x[k]);
	}
	for(int i=0; i<rep; i++){
		for(int j: x){
			ans.push_back(j+30*(i+1));
		}
	}

	pr(ans);

	return 0;
}


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

template <class T = long long>
class ST {	//非再帰抽象化セグ木
   private:
	int n;
	vector<T> data;
	T unit;
	function<T(T, T)> operation;

   public:
	ST(int _n, function<T(T, T)> _operation, T _unit) : n(_n), operation(_operation), unit(_unit) {
		data.assign(n * 2, unit);
		for(int i = n - 1; i > -1; i--) {
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}
	ST(int _n, function<T(T, T)> _operation, T _unit, vector<T> raw_data) : n(_n), operation(_operation), unit(_unit) {
		data.assign(n * 2, unit);
		for(int i = 0; i < n; i++) {
			data[i + n] = raw_data[i];
		}
		for(int i = n - 1; i > -1; i--) {
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}
	ST(int _n, function<T(T, T)> _operation, T _unit, T _init) : n(_n), operation(_operation), unit(_unit) {
		data.assign(n * 2, _init);
		for(int i = n - 1; i > -1; i--) {
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}

	void update(int idx, T x) {
		idx += n;
		data[idx] = x;
		idx >>= 1;
		while(idx > 0) {
			data[idx] = operation(data[(idx << 1)], data[(idx << 1) | 1]);
			idx >>= 1;
		}
	}

	//お好きな二項演算をどうぞ 抽象化するのはちょっとやりすぎ感
	void add(int idx, T x) { update(idx, data[idx + n] + x); }

	T get(int lef, int rig) {
		T a = unit, b = unit;
		lef += n;
		rig += n;
		while(lef < rig) {
			if(lef & 1) a = operation(a, data[lef]);
			if(rig & 1) b = operation(data[rig - 1], b);
			(lef += 1) >>= 1;
			rig >>= 1;
		}
		return operation(a, b);
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ST<int> st(
		n, [](int a, int b) { return __gcd(a, b); }, 0, a);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int a, b;
		a = st.get(0, i);
		b = st.get(i + 1, n);
		ans = max(ans, __gcd(a, b));
	}
	cout << ans << endl;
}

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

int main(){
  int n;
  int m = 1;

  cin >> n;

  int a[n];
  int i = 0;
  int cnt = 0;
  int temp = 0;
  
  for(int i=0;i < n;i++){
    cin >> a[i];
  }

  i = 0;
  while(m){
    m = 0;
    
    for(int j=n-1;j > i;j--){
      if( a[j] < a[j-1] ){
	temp = a[j];
	a[j] = a[j-1];
	a[j-1] = temp;
	m = 1;
	cnt++;
      }
    }
    i++;
  }
  for(int i=0;i < n;i++){
    cout << a[i];
    if(i != n-1) cout << " ";
  }
  cout << endl;
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 3112
n = int(input())
t = [0]*(n + 1)
x = [0]*(n + 1)
y = [0]*(n + 1)
for i in range(n):
    t[i+1],x[i+1],y[i+1] = map(int,input().split())
ans = 0
#
for j in range(n):
    if (x[j+1] + y[j+1] - x[j] - y[j])%2 == 1:
        if (t[j + 1] - t[j])%2 == 1 and (x[j+1] + y[j+1] - x[j] - y[j]) <= (t[j + 1] - t[j]):
            ans+=0
        else:
            ans+=1
    else:
        if (t[j + 1] - t[j])%2 == 0 and (x[j+1] + y[j+1] - x[j] - y[j]) <= (t[j + 1] - t[j]):
            ans+=0
        else:
            ans+=1
#
if ans==0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 12044
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 = sc.nextInt();

		if (B % A == 0) {
			System.out.println(A + B);
		} else {
			System.out.println(B - A);
		}
	}
}


Measured memory_bytes: 23764
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll N,K;
    cin >> N >> K;
    ll A[N];
    rep(i,N) cin >> A[i];
    vector<ll> v(1,1);
    ll start = 0;
    ll end = 0;
    ll tmp = 0;
    ll C[N];
    rep(i,N) C[i] = 0;
    rep(i,N){
        C[tmp]++;
        if(C[tmp]==2){
            break;
        }else{
            end++;
            v.push_back(A[tmp]);
            tmp = A[tmp]-1;
        }
    }
    rep(i,end){
        if(v[i]==v[end]){
            start = i;
            break;
        }
    }
    ll out = v[start+(K-start)%(end-start)];
    if(start>K) out = v[K];
    cout << out << endl;
    return 0;
}


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

using namespace std;

#define P pair<long long int, pair<long long int,long long int> >

int main(){

    long long int n;
    vector<long long int> a;

    deque<long long int> q;

    cin >> n;
    for(long long int i=0;i<n;i++){
        long long int aa;
        cin >> aa; a.push_back(aa);
    }

    sort(a.begin(),a.end(),std::greater<long long int>());

    long long int ans=0;
    q.push_front(a[0]);

    for(long long int i=1;i<a.size();i++){
        long long int tmp=q.front();
        ans+=tmp;
        q.pop_front();
        q.push_back(a[i]); q.push_back(a[i]);
    }

    cout << ans << endl;

    
    return 0;
}

Measured memory_bytes: 6408
import math
while True:
    n=int(input())
    if n==0:
        break
    s=list(map(int,input().split()))
    m=sum(s)/n
    aa=0
    for i in s:
        aa+= (i-m)**2
    a=math.sqrt((aa)/n)
    print(f'{a:.08f}')


Measured memory_bytes: 5712
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

k = int(input())

ls = [a, b, c, d, e]

ans = 'Yay!'
for l in ls:
    for n in ls:
        if l - n > k:
            ans = ':('

print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
constexpr int MOD=1e9+7;
main(){
  int N;
  cin>>N;
  vector<int>xs(1001);
  for(int i=1;i<=N;++i){
    int tmp=i;
    for(int divisor=2;divisor<=tmp;++divisor){
      while(tmp%divisor==0){
        ++xs[divisor];
        tmp/=divisor;
      }
    }
  }
  int ans=1;
  for(int i=1;i<=N;++i)ans=ans*(xs[i]+1)%MOD;
  cout<<ans<<endl;
}


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

int main(){
    int h,w;
    cin>>h>>w;

    vector<vector<char>> c(h,vector<char>(w));
    vector<vector<char>> d(h*2,vector<char>(w));
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>c[i][j];
            d[i*2][j]=c[i][j];
            d[i*2+1][j]=c[i][j];
        }
    }

    for(int i=0; i<h*2; i++){
        for(int j=0; j<w; j++){
            cout<<d[i][j];
            if(j==w-1){
                cout<<endl;
            }
        }
    }
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(){
    int j,s_length = 0;
    char s[101],p[101];
    scanf("%s",s);
    scanf("%s",p);
 
    for(int i = 0; s[i] != '\0';i++) s_length++;
 
 	// 人家的思维是真的牛逼 
    for(int left = 0;s[left] != '\0';left++){
        for(j = 0;p[j] != '\0' && p[j] == s[(left+j)%s_length];j++);//注意他处理回文的方法，实在是太牛逼了 
        if(p[j] == '\0'){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 2140
n = int(input())

keta = len(str(n))
ans = 0
for i in range(keta):
    if i+1 != keta and (i+1) % 2 == 1:
        ans += (10 ** i) * 9
    elif i+1 == keta and (i+1) % 2 == 1:
        ans += n - (10 ** i) + 1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
using ll = long long;
template<typename T>T gcd(T a, T b){return b?gcd(b,a%b):a;}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  ll A, B;
  cin >> A >> B;

  cout << A * B / gcd(A, B) << "\n";

  return 0;
}


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

fn = [0] * (N+1)
for x in range(1,101):
    for y in range(1,101):
        if x**2 + y**2 + x*y >= N:
            break
        for z in range(1,101):
            val = x**2 + y**2 + z**2 + x*y+y*z+z*x
            if val > N:
                break
            fn[val] += 1

for v in fn[1:]:
    print(v)


Measured memory_bytes: 9184
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static final FastReader in = new FastReader();
    private static final PrintWriter out = new PrintWriter(System.out);
    static int memo[];

    static int rec(int indx, int arr[]) {
        if (indx == arr.length - 1) {
            return 0;
        }
        int v = Integer.MAX_VALUE, c = Integer.MAX_VALUE;
        if (memo[indx] != -1) {
            return memo[indx];
        }
        v = Math.abs(arr[indx ] - arr[indx+1] )+ rec(indx + 1, arr);
        if (indx + 2 < arr.length) {
            c = Math.abs(arr[indx] - arr[indx + 2]) + rec(indx + 2, arr);
        }
        return memo[indx] = Math.min(v, c);
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        memo = new int[n];
        Arrays.fill(memo, -1);
        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        out.println(rec(0, arr));
        out.flush();

    }


    static class FastReader {
        private static BufferedReader br;
        private static StringTokenizer st;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = null;
        }

        private static String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            return next();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

    }
}

Measured memory_bytes: 45200
#include<bits/stdc++.h>
#define R 2
#define L 3
#define D 0
#define U 1
using namespace std;

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

int bfs(int sx,int sy,int gx,int gy)
{
	int ans=0;
	queue<pair<pair<int,int>,int> > q;
	q.push(make_pair(make_pair(sx,sy), 0));
	vector<vector<bool> >  done(gx+5,vector<bool>(gy+5,false));
	done[sx][sy]=true;
	while(!q.empty())
	{
		auto get=q.front();
		q.pop();
		int x=get.first.first;
		int y=get.first.second;
		if(x==gx and y==gy)
		{
			ans = get.second;
			break;
		}
		for(int i=0;i<4;i++)
		{
			int nx = get.first.first + dx[i];
			int ny = get.first.second + dy[i];
			if(to[x][y][i]==true and done[nx][ny]==false)
			{
				q.push(make_pair(make_pair(nx,ny),get.second+1));
				done[nx][ny]=true;
			}
		}
	}

	return (ans==0)? 0 : ans+1;
}

int main()
{
	int w,h;
	while(cin >> w >> h)
	{
		if(w==0 and h==0)return 0;
		for(int i=0;i<35;i++)
			for(int j=0;j<35;j++)
				for(int k=0;k<4;k++)
					to[i][j][k]=false;
		for(int i=0;i<2*h-1;i++)
		{
			if(i%2==0)
			{
				for(int j=0;j<w-1;j++)
				{
					int in;
					cin >> in;
					if(in==0)
					{
						to[j][i/2][R]=true;
						to[j+1][i/2][L]=true;
					}
				}
			}
			else
			{
				for(int j=0;j<w;j++)
				{

					int in;
					cin >> in;
					if(in==0)
					{
						to[j][i/2][D]=true;
						to[j][(i+1)/2][U]=true;
					}
				}
			}
		}

		cout << bfs(0,0,w-1,h-1) << endl;

	}

}


Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void solve()
{
	int H, W;
	while(cin >> H >> W, H || W)
	{
		vector< vector<char> > field(H, vector<char>(W));
		vector< vector<int> > dp(H, vector<int>(W));
		for(int i = 0; i < H; ++i)
		{
			for(int j = 0; j < W; ++j)
			{
				cin >> field[i][j];
				if(field[i][j] == '.')
				{
					dp[i][j] = 1;
				}
			}
		}
		for(int i = 0; i < H; ++i)
		{
			for(int j = W - 2; j >= 0; --j)
			{
				if(field[i][j] == '.')
				{
					dp[i][j] += dp[i][j + 1];
				}
				else
				{
					dp[i][j] = 0;
				}
			}
		}

		int ans = 0;
		for(int i = 0; i < H; ++i)
		{
			for(int j = 0; j < W; ++j)
			{
				if(1 <= i && dp[i][j] == dp[i - 1][j] || dp[i][j] == 0)
				{
					continue;
				}
				ans = max(ans, dp[i][j]);
				int k = 1;
				int minimum = dp[i][j];
				while(i + k < H && dp[i + k][j] > 0)
				{
					minimum = min(minimum, dp[i + k][j]);
					++k;
					ans = max(ans, k * minimum);
				}
			}
		}
		cout << ans << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 2396
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        long A = sc.nextLong();
        double B = sc.nextDouble();

        System.out.println(solve(A, B));
    }

    private static String solve(long A, double B) {
        BigDecimal b = BigDecimal.valueOf(A);
        b = b.multiply(BigDecimal.valueOf(B));


        return b.setScale(0, RoundingMode.DOWN).toString();
    }
}

Measured memory_bytes: 37684
for t in xrange(input()):
    up = 0; down = 0;
    n = input()
    h = map(int, raw_input().split())
    print max([0]+[h[i+1]-h[i] for i in xrange(n-1)]), max([0]+[h[i]-h[i+1] for i in xrange(n-1)])

Measured memory_bytes: 4220
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	var a int
	var b string

	fmt.Scan(&a, &b)
	bInt, _ := strconv.Atoi(strings.Replace(b, ".", "", -1))
	fmt.Println(a * bInt / 100)
}

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

int main() {
	int n;
	cin >> n;
	double sum = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		sum += 1 / (double)x;
	}
	cout << 1 / sum << endl;
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {                          \
            return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;

double power(double a, int n)
{
    double r;
    int abs_n;

    r = 1;

    abs_n = n < 0 ? -n : n;

    while (0 < abs_n)
    {
      if (abs_n % 2 == 1) r *= a;

      a *= a;
      abs_n /= 2;
    }

    return n >= 0 ? r : 1 / r;
}

double nthroot(double a, int n)
{
    double x, y;

    if (a <= 0 || n < 0) return 0;
    if (n == 0) return 1;

    /* When 0 < a and 0 < n */
    y = (1 < a) ? a : 1;

    do
    {
        x = y;
        y = ((n - 1) * x + a / power(x, n - 1)) / n;
    }
    while (y < x);

    return y;
}

// is_power
// power number or not
// (squared number, cubic number, uadruple number, etc.)
bool is_power(int a)
{
    if (a == 1) return 1;

    FOR (i, 2, (int)floor(log2(a)))
    {
        if ((int)power(floor(nthroot(a, i)), i) == a) return true;
    }

    return false;
}

int main()
{
    int X;

    cin >> X;

    for (int i = X; 0 <= i; i--)
    {
      if (is_power(i))
      {
          cout << i << endl;
          break;
      }
    }

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int n,m;
char p[505][505],r[505][505],b[505][505],ch;
int main(){
	scanf("%d%d\n",&n,&m);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) scanf("%c",&p[i][j]);
		scanf("%c",&ch);
	}
	for (int i=1;i<=n;i++) r[i][1]='#';
	for (int i=1;i<=n;i++) b[i][m]='#';
	for (int i=1;i<=n;i+=2)
		for (int j=2;j<m;j++) r[i][j]='#';
	for (int i=2;i<=n;i+=2)
		for (int j=2;j<m;j++) b[i][j]='#';
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) 
			if ((p[i][j]=='#') || (r[i][j]=='#')) r[i][j]='#';
			else r[i][j]='.';
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) 
			if ((p[i][j]=='#') || (b[i][j]=='#')) b[i][j]='#';
			else b[i][j]='.';
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) printf("%c",r[i][j]);
		printf("\n");
	}
	printf("\n");
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) printf("%c",b[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <string>
using namespace std;
int main(){
  int LastStop[100000]={0};
  string str;
  cin >> str;
  char d='R';str+="R";
  int Rstop=0;
  int right=0,left=0;
  
  for(int pos=0;pos<str.length()-1;pos++){
    if(str[pos]=='R' && str[pos+1]=='L'){
      Rstop=pos;
    }
    if(str[pos]=='L' && str[pos+1]=='R'){
      left=pos;
      for(int k=right;k<=left;k++){
        if((k-Rstop)%2==0)LastStop[Rstop]++;
        else LastStop[Rstop+1]++;
      }
      right=pos+1;
    }    
  }
  
  for(int i=0;i<str.length()-1;i++){
    if(i)cout << " ";
    cout << LastStop[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace::std;
#define all(n) (n).begin(),(n).end()
#define MOD 1000000007LL

struct rolling_hash{
    using u64=uint64_t;
    constexpr static u64 mod=(1ULL<<61)-1;
    constexpr static u64 base=10007;
    int sz;
    u64 hash;
    constexpr rolling_hash():sz(0),hash(0){}
    constexpr rolling_hash(char c):sz(1),hash(c){}
    rolling_hash(string s):sz(0),hash(0){
        for(auto c:s)(*this)+=c;
    }
    constexpr u64 pow(u64 s,int t){
        u64 ret=1;
        while(t){
            if(t&1)ret=mul(ret,s);
            s=mul(s,s);
            t/=2;
        }
        return ret;
    }
    constexpr u64 add(u64 s,u64 t)noexcept{
        s+=t;
        return s>=mod?s-mod:s;
    }
    constexpr u64 sub(u64 s,u64 t)noexcept{
        if(s<t)s+=mod;
        return s-t;
    }
    constexpr u64 mul(u64 a,u64 b)noexcept{
        u64 au=a>>31,ad=a&((1ULL<<31)-1);
        u64 bu=b>>31,bd=b&((1ULL<<31)-1);
        u64 mid=au*bd+ad*bu;
        u64 ret=(au*bu*2+ad*bd+(mid>>30)+((mid&((1ULL<<30)-1))<<31));
        ret=(ret>>61)+(ret&mod);
        return ret>=mod?ret-mod:ret;
    }
    constexpr rolling_hash operator+(rolling_hash s)const noexcept{return rolling_hash(*this)+=s;}
    constexpr bool operator==(rolling_hash s)noexcept{return hash==s.hash&&sz==s.sz;}
    constexpr bool operator<(rolling_hash s)const noexcept{return make_pair(hash,sz)<make_pair(s.hash,s.sz);}
    constexpr bool operator>(rolling_hash s)const noexcept{return make_pair(hash,sz)>make_pair(s.hash,s.sz);}
    constexpr bool operator<=(rolling_hash s)const noexcept{return make_pair(hash,sz)<=make_pair(s.hash,s.sz);}
    constexpr bool operator>=(rolling_hash s)const noexcept{return make_pair(hash,sz)>=make_pair(s.hash,s.sz);}
    constexpr rolling_hash operator+=(rolling_hash s)noexcept{
        (*this).hash=add((*this).hash*pow(base,s.sz),s.hash);
        (*this).sz+=s.sz;
        return *this;
    }
    constexpr int size(){return sz;}
};

int main(){
	vector<rolling_hash>m;
	int n;
	cin>>n;
	vector<rolling_hash>v(n);
	for(int i=0;i<n;++i){
		string s;
		cin>>s;
		reverse(all(s));
		vector<int>cnt(26,0);
		for(int j=0;j<(int)s.size();++j)cnt[s[j]-'a']++;
		bitset<26>b;
		for(int j=0;j<26;++j)if(cnt[j])b[j]=1;
		for(int j=0;j<(int)s.size();++j){
			for(int k=b._Find_first();k<26;k=b._Find_next(k)){
				m.push_back(v[i]+(k+'a'));
			}
			v[i]+=s[j];
			cnt[s[j]-'a']--;
			if(!cnt[s[j]-'a'])b[s[j]-'a']=0;
		}
	}
    sort(all(m));
	int64_t ans=0;
	for(int i=0;i<n;++i){
		ans+=upper_bound(all(m),v[i])-lower_bound(all(m),v[i])-1;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 529040
def pad(S,N):
    return (N-len(S)) * "0" + S

def xor_sum(A,M):
    N = len(A)
    bit_count = [0 for _ in range(60)]
    #bit_count[i]:iビット目が1であるa in Aの個数

    for i in range(N):
        A[i] = pad(bin(A[i])[2:],60)
        for j in range(60):
            if A[i][60-j-1] == "1":
                bit_count[j] += 1

    output = 0
    for j in range(60):
        tmp1 = (N-bit_count[j])*bit_count[j] % M
        tmp2 = pow(2,j,M)
        tmp = (tmp1 * tmp2) % M
        output += tmp
        output %= M

    return output

def main():
    N = int(input())
    A = list(map(int,input().split()))
    M = 10**9+7

    print(xor_sum(A,M))

if __name__ == "__main__":
    main()


Measured memory_bytes: 132104
#include <iostream>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

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

  int x; cin >> x;

  // x = 1 の場合を考慮
  int ans = 1;
  for(int b = 2; b <= x; ++b) {
    int tmp = b;
    while(true) {
      tmp *= b;
      if(tmp > x) break;
      ans = max(ans, tmp);
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def dijkstra(g, st):
    """Dijkstra method"""

    n = len(g)
    d = [float('inf')] * n
    d[st] = 0

    que = [(0, st)]     # (min_dist, vertex)
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue
        for v1, dist in g[v0]:
            if d[v1] > d[v0] + dist:
                d[v1] = d[v0] + dist
                heapq.heappush(que, (d[v1], v1))

    return d

def solve(f):
    n, m, s, t = f.read_int_list()

    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]

    for _ in xrange(m):
        u, v, a, b = f.read_int_list()
        g1[u-1].append((v-1, a))
        g1[v-1].append((u-1, a))
        g2[u-1].append((v-1, b))
        g2[v-1].append((u-1, b))

    c1 = dijkstra(g1, s-1)
    c2 = dijkstra(g2, t-1)

    ans = [0] * n
    ans[n-1] = 10**15-c1[n-1]-c2[n-1]
    for i in xrange(n-2, -1, -1):
        ans[i] = max(ans[i+1], 10**15-c1[i]-c2[i])

    return "\n".join(map(str, ans))


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


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

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

    string tmp = s.substr(0, 4);
    if (stoi(tmp) >= 2019)
    {
        tmp = s.substr(5,2);
        if (stoi(tmp) > 4)
        {
            cout << "TBD" << endl;
            return 0;
        }
    }
    cout << "Heisei" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef long double ld;
#define endl "\n"
const int MAX= 300005 ;
const long long mod = 1e9+7;
int n,w;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int i,j,x=0,y;
    cin>>n>>w;
    int v[n+1],wt[n+1];
    for(i=0;i<n;i++)
    {
        cin>>wt[i]>>v[i];
        x+=v[i];
    }
    int dp[n+1][x+1];
    for(i=1;i<=x;i++)
    {
        dp[0][i]=INT_MAX;
    }
    dp[0][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=x;j++)
        {
            dp[i][j]=INT_MAX;
        }
        for(j=0;j<=x;j++)
        {
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
            if(j>=v[i-1])
            {
                dp[i][j]=min(dp[i][j],wt[i-1]+dp[i-1][j-v[i-1]]);
            }
        }
    }
    int ans=0;
    for(i=0;i<=x;i++)
    {
        if(dp[n][i]<=w)
        {
            ans=max(ans,i);
        }
    }
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=x;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<ans<<endl;
}

Measured memory_bytes: 79232
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int W,H,x,y,r;
	cin >> W >> H >> x >> y >> r;
	cout << ((x-r>=0&&x+r<=W&&y-r>=0&&y+r<=H)?"Yes":"No") << endl;
return 0;
}

Measured memory_bytes: 1160
#include <iostream>
long long gcd(long long m,long long n){
  if (n==0)return m;
  else{
    return gcd(n,m%n);
  }
  return 0;
}
int main(){
  long long a,b,c,d,tmp,g;
  std::cin >> a>>b>>c>>d;
  --a;
  g=c*d/gcd(c,d);
  tmp=b/c+b/d-b/g-a/c-a/d+a/g;
  std::cout << b-a-tmp << '\n';
}


Measured memory_bytes: 256
import math
import pprint
import fractions
import collections
import itertools
from decimal import *
N=int(input())
N=N-1
l=[pow(26,i) for i in range(1,20)]
x=[0]
for i in range(19):
    x.append(x[len(x)-1]+l[i])
#print(x)
le=0
for i in range(1,40):
    if x[i-1]<=N<x[i]:
        N=N-x[i-1]
        le=i
        break
l.sort(reverse=True)
ans=[]
for i in range(le-1,-1,-1):
    d=N//pow(26,i)
    N=N%pow(26,i)
    ans.append(chr(d+ord("a")))
print("".join(ans))


Measured memory_bytes: 72580
#define _CRT_SECURE_NO_WARNINGS
////#define _USE_MATH_DEFINES
#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//#include<string.h>
//#include<time.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)

int main() {
	int a,b,c;
	fscanf(stdin, "%d%d%d", &a, &b, &c);
	if (c || (a&&b)) puts("Open");
	else puts("Close");
	return 0;
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define hi cout<<'h'<<'i'<<'\n' 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;
    ll x;
    cin>>x;
    int y=0;
    ll amt=100;
    while(1)
    {
        y++;
        amt*=1.01;

        if(amt>=x)break;
    }
    cout<<y;
    return 0;
}



Measured memory_bytes: 3636
def main():
	a,b,k = list(map(int,input().split()))	
	if a>=k:
		print(str(a-k),str(b))
	elif a<k and b+a>k:
		print(str(0),str(b-(k-a)))
	else:
		print(str(0),str(0))
main()

Measured memory_bytes: 3060
"""
赤い点はできるだけ自分の座標に近い青い点と仲良しペアになった方がよい。
仲良しペアになれる候補が少ない赤点ほど、さきにみていった方がよい。
Nの上限が低いことを利用できそう。
解法１：
まず各赤点ごとに、ペアになれる青点を列挙する。  

解法２：
青、赤を混合した状態でXで降順ソートする。
一つずつ座標を見ていく。
ピックアップした座標が青色の場合、Y座標の情報をqueに入れる。
このとき、queの中身が昇順になるように、bisectを使ってqueに入れる。O(N)
ピックアップした座標が赤色の場合、queの中に自分のY座標より大きい値があるかを探し、あればそれを取り出す。O(N)
全体はO(N^2)で実行可能
"""
from bisect import insort
N = int(input())
coordinates = []
for _ in range(N):
    a,b = map(int,input().split())
    coordinates.append((a,b,0))
for _ in range(N):
    c,d = map(int,input().split())
    coordinates.append((c,d,1))

coordinates.sort(reverse=True)
que = []
ans = 0
for x,y,c in coordinates:
    if c:
        insort(que,y)
    else:
        if que and que[-1] > y:
            ans += 1
            for i in range(len(que)):
                if que[i] > y:
                    que = que[:i]+que[i+1:]
                    break
print(ans)

Measured memory_bytes: 63576
/**
 *  author:   TakeruOkuyama
 *  created:  2020-04-15 11:17:28
**/
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
const int INF = 999999999;

int main(){
    int n;
    cin >> n;
    vector<int> v(n), c(n);
    rep(i,n){
        cin >> v[i];
    }
    rep(i,n){
        cin >> c[i];
    }
    int ans = 0;
    rep(i,n){
        ans += max(v[i] - c[i],0);
    }
    cout << ans << endl;
return 0;}

/**
 * g++ code.cpp
 * ./a.out
 * shift + ctrl + i
**/ 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int A,B,C,D,E;
  cin >> A >> B >> C >> D >> E;
  
  int a=A%10;
  int b=B%10;
  int c=C%10;
  int d=D%10;
  int e=E%10;
  
  if(a==0){
    a=10;
  }
  if(b==0){
    b=10;
  }
  if(c==0){
    c=10;
  }
  if(d==0){
    d=10;
  }
  if(e==0){
    e=10;
  }
  
  int m=min(min(min(min(a,b),c),d),e);
  
  cout << A+B+C+D+E-a-b-c-d-e+40+m << endl;
}

Measured memory_bytes: 256
function Main(input){
	var N = input;
  if(N < 1200)return "ABC";
  if(N < 2800)return "ARC";
  return "AGC";
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
1199
`);

Measured memory_bytes: 21064