akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;

public class Main {
	 static InputReader in = new InputReader(System.in);
	 static PrintWriter out = new PrintWriter(System.out);
	 
	 public static void main(String[] args) {
		 int n = in.nextInt();
		 int[] a = new int[n];
	        for(int i =0 ;i<n;i++) a[i] = in.nextInt();   
	     Arrays.sort(a);
	     int length = 1;
	     int stand = 0;
	     int around = 1;
	     while (around<n)
	     {
	    	 if(a[around]-a[stand] <=2)
	    	 {
	    		 length = Math.max(length, around-stand+1);
	    		 around++;
	    	 }
	    	 else {
	    		 stand++;
	    	 }
	     }
	     
	     out.println(length);
	     out.close();
		 
		 
		 
	 
	 }
	 static class InputReader {
	        public BufferedReader reader;
	        public StringTokenizer tokenizer;
	 
	        public InputReader(InputStream stream) {
	            reader = new BufferedReader(new InputStreamReader(stream), 32768);
	            tokenizer = null;
	        }
	 
	        public String next() {
	            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	                try {
	                    tokenizer = new StringTokenizer(reader.readLine());
	                } catch (IOException e) {
	                    throw new RuntimeException(e);
	                }
	            }
	            return tokenizer.nextToken();
	        }
	 
	        public int nextInt() {
	            return Integer.parseInt(next());
	        }
	 
	        public long nextLong() {
	            return Long.parseLong(next());
	        }
	 
	        public double nextDouble() {
	            return Double.parseDouble(next());
	        }
	 
	        public String nextLine() {
	            try {
	                return reader.readLine();
	            } catch (Exception e) {
	                e.printStackTrace();
	            }
	            return null;
	        }
	 
	        public boolean hasNext() {
	            String next = null;
	            try {
	                next = reader.readLine();
	            } catch (Exception e) {
	            }
	            if (next == null) {
	                return false;
	            }
	            tokenizer = new StringTokenizer(next);
	            return true;
	        }
	 
	        public BigInteger nextBigInteger() {
	            return new BigInteger(next());
	        }
	    }
	}

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

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

    int m;
    cin>>m;
    int remainderr=m%10;
    if(remainderr==2 || remainderr==4 || remainderr==5 || remainderr==7 || remainderr==9)
        cout<<"hon";
    else if(remainderr==0  || remainderr==1 || remainderr==6 || remainderr==8)
        cout<<"pon";
    else
        cout<<"bon";
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define mp make_pair
#define fi first
#define se second
ll f[200000],n,k,var,idx;
priority_queue < pair<ll,ll> > q;
ll sum,mx;
vector < pair <ll,ll> > v;
void shift(){
    if(f[v[idx].se]>1){}
    else{
        while(f[v[idx].se]<=1 && idx>0){
            idx--;
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        ll t,d;
        cin>>t>>d;
        q.push(mp(d,t));
    }
    for(int i=1;i<=k;i++){
        sum += q.top().fi;
        if(f[q.top().se] == 0){var++;}
        v.push_back(mp(q.top().fi,q.top().se));
        f[q.top().se]++;
        q.pop();
    }
    sum += (ll)var*var;
    mx = sum;
    idx = v.size()-1;
    shift();
    while(idx > 0 && !q.empty()){
        ll t,d;
        d = q.top().fi;
        t = q.top().se;

        if(f[t]==0){
            f[t]++;
            sum -= v[idx].fi;
            sum -= (ll)var*var;
            sum += d;
            var ++;
            sum += (ll)var*var;
            f[v[idx].se]--;
            idx--;
            mx = max(mx,sum);
        }
        q.pop();
        shift();
    }
    cout<<mx<<endl;

}



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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define MINS(m, s) m.insert(make_pair(s, 1));
#define MFIN(m, s) m.find(s) != m.end()
const int mod = 1000000007;

int main() {
    double a, b, x, rad, ans;
    cin >> a >> b >> x;
    x = x / a;
    if(x > a * b / 2) {
        rad = atan(2 * (a * b - x) / (a * a));
    } else {
        rad = atan(b * b / (2 * x));
    }
    ans = rad * 180 / M_PI;
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 4028
// Two Colors Card Game
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

int main() {
    int N, M;
    cin >> N;
    map<string, int> mp;
    for (int i = 0; i < N; ++i) {
        string x;
        cin >> x;
        mp[x]++;
    }
    cin >> M;
    for (int i = 0; i < M; ++i) {
        string x;
        cin >> x;
        mp[x]--;
    }
    mp["other"] = 0;

    int ma = 0;
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        ma = max(ma, mp[iter->first]);
    }

    cout << ma << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
int main()
{
	bool sf[110]={0};
	int n,k,s=0,i;
	cin>>n>>k;
	while(k--)
	{
		int d,t;
		scanf("%d",&d);
		for(i=0;i<d;i++)
		{
			scanf("%d",&t);
			sf[t]=1;
		}
		
	}
	for(i=1;i<=n;i++)
	{
		if(!sf[i])s++;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
typedef signed long long int ll;
ll inf=1000000007;



const int MAX = 510000;
const int MOD = 1000000007;

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

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

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



int main(){
    string s;
    cin>>s;
    
    int n;
    n=(int)s.size();
    
    ll dp[100010][4]={};
    //dp[n][3]=1;
    //for(int i=0;i<3;i++) dp[n][i]=0;
    for(int i=n;i>=0;i--){
        
        //char c=s[i];
        
        for(int j=3;j>=0;j--){
            if(i==n){
                dp[i][j] = (j == 3 ? 1 : 0);
                if(j==3) dp[i][j]=1;
                else dp[i][j]=0;
            }else{
                
                dp[i][j]=dp[i+1][j]*(s[i] =='?' ? 3LL : 1LL);
                if(j < 3 && (s[i] == '?' || s[i] == "ABC"[j])){
                        dp[i][j] += dp[i+1][j+1];

                }
                dp[i][j]%=MOD;
            
            }
        }
        
        /*if(c=='?'){
            //j=3
            //何を書くかで三通り
            dp[i][3]=3LL*dp[i+1][3];
            
            //j=2
            //?にA,B,Cを入れて丸しない
            dp[i][2]=3LL*dp[i+1][2];
            //cを入れて丸
            dp[i][2]+=dp[i+1][3];
            
            //j=1
            //A,B,Cで丸しない
            dp[i][1]=3LL*dp[i+1][1];
            //Bで丸
            dp[i][1]+=dp[i+1][2];
            
            //j=0
            //丸しない
            dp[i][0]=3LL*dp[i+1][0];
            //Aで丸
            dp[i][0]+=dp[i+1][1];
        }else if(c=='C'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            //丸をするかしないか
            dp[i][2]=dp[i+1][2]+dp[i+1][3];
            //j=1
            dp[i][1]=dp[i+1][1];
            //j=0;
            dp[i][0]=dp[i+1][0];
        }else if(c=='B'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            dp[i][2]=dp[i+1][2];
            //j=1
            dp[i][1]=dp[i+1][1]+dp[i+1][2];
            
            dp[i][0]=dp[i][0];
            
        }else if(c=='A'){
            //j=3
            dp[i][3]=dp[i+1][3];
            //j=2
            dp[i][2]=dp[i+1][2];
            
            dp[i][1]=dp[i+1][1];
            
            dp[i][0]=dp[i+1][0]+dp[i+1][1];
        }*/
        
        /*for(int j=0;j<4;j++){
            dp[i][j]%=inf;
        }*/
    }
    
    cout<<dp[0][0]<<endl;
    
    
    return 0;
}


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

const int M = 1000005;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
    }
    
    vector<int> all(M);
    rep(i,n) {
        all[a[i]]++;
    }
    
    bool tf = true;
    for(int i = 2; i < M; i++) {
        int cnt = 0;
        for(int j = i; j < M; j+=i) {
            cnt += all[j];
        }
        if(cnt > 1)
            tf = false;
    }
    
    if(tf) {
        cout << "pairwise coprime" << endl;
        return 0;
    }
    
    int g = a[0];
    rep(i,n) {
        g = gcd(g,a[i]);
    }
    
    if(g == 1)
        cout << "setwise coprime" << endl;
    else
        cout << "not coprime" << endl;
    
    
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    int res = INT_MAX;
    int W[N+1]={},B[N+1]={};
    rep(i,N){
        if(S[i] == '#')B[i+1]++;
        else W[i+1]++;
        B[i+1] += B[i];
        W[i+1] += W[i];
    }
    rep(i,N+1){
        res = min(res,B[i] + (W[N] - W[i]));
    }
    cout << res << endl;
    
    return 0;
}

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

ll fac(ll x){
	if(x == 0)return 1;
	else return x * fac(x-1);
}

int main(){
	ll n; cin >> n;
	vl p(n); rep(i,n)cin >> p[i];
	vl q(n); rep(i,n)cin >> q[i];
	vl num_1(n); rep(i,n)num_1[i] = i+1;//残ってるので何番目か
	vl num_2(n); rep(i,n)num_2[i] = i+1;
	ll a=0; ll b=0;
	rep(i,n){
		ll k = 0;
		rep(j,n){
		 if(num_1[j] != 80)k++;
			if(p[i]  == num_1[j]){
				a += (k-1) * fac(n-i-1);
				num_1[j]=80;
			}
		}
	}
	rep(i,n){
		ll k = 0;
		rep(j,n){
		 if(num_2[j] != 80)k++;
			if(q[i]  == num_2[j]){
				b += (k-1) * fac(n-i-1);
				num_2[j]=80;
			}
		}
	}
	if(a > b)cout << a - b << endl;
	else cout << b - a << endl;

}

Measured memory_bytes: 256
(* O(|s|) *)
let s = read_line () in
let n = String.length s in
let f i =
  let rec loop_a a j =
    if j >= n then a
    else if s.[j] <> 'A' then a
    else loop_a (a + 1) (j + 1) in
  let rec loop_bc bc j =
    if j >= n - 1 then bc
    else if s.[j] <> 'B' || s.[j + 1] <> 'C' then bc
    else loop_bc (bc + 1) (j + 2) in
  let a = loop_a 0 i in
  if a = 0 then 0, 0, i + 1
  else
    let bc = loop_bc 0 (i + a) in
    if bc = 0 then 0, 0, i + a + 1
    else a, bc, i + a + 2 * bc in
let rec find acc a0 i =
  if i >= n then acc
  else
    let a, bc, j = f i in
    if a = 0 then find acc 0 j
    else
      let a1 = a0 + a in
      find (acc + a1 * bc) a1 j in
find 0 0 0 |> Printf.printf "%d\n"

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define SZ(i) int(i.size())
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#endif

const int MAXN = 1000006;
const ll MOD = 1000000007;

vector<string> sa;
/*********************GoodLuck***********************/
int main () {
    IOS();

    ll ans = 0;
    int n;
    cin >> n;
    REP (i, n) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        sa.emplace_back(s);
    }

    sort(sa.begin(), sa.end());

    int cnt = 1;
    REP1 (i, SZ(sa)) {
        if (i == SZ(sa) || sa[i] != sa[i-1]) {
            debug(cnt);
            ans += cnt * ll(cnt - 1) / 2;
            cnt = 0;
        }
        cnt++;
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 5748
printed_later = []
while True:
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        break
    n = int(input())
    blocked = []
    for _ in range(n):
        blocked.append([int(x) - 1 for x in input().split()])
    route_nums = [[]]
    edge = 1
    for j in range(y):
        if [0, j] in blocked:
            edge = 0
        route_nums[0].append(edge)
    edge = 1
    for i in range(1, x):
        if [i, 0] in blocked:
            edge = 0
        route_nums.append([edge])
        for j in range(1, y):
            if([i, j] in blocked):
                route_nums[i].append(0)
            else:
                route_nums[i].append(route_nums[i - 1][j] +
                                     route_nums[i][j - 1])
    printed_later.append(route_nums[-1][-1])
    #print(route_nums)
for line in printed_later:
    print(line)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,M; cin >> N >> M;
	V<ll> A(N);
	rep(i,N-1){
		ll x; cin >> x;
		A[i+1] = A[i]+x;
	}
	VV<ll> B(M,V<ll>(N));
	rep(i,N) rep(j,M) cin >> B[j][i];

	ll ans = 0;
	VV<int> st(M); rep(i,M) st[i].pb(-1);
	V<ll> f(N+1);
	rep(r,N){
		V<ll> dif(N+1);
		rep(i,M){
			while(st[i].back() != -1 && B[i][st[i].back()] <= B[i][r]){
				int K = si(st[i]);
				int x = st[i][K-2]+1, y = st[i][K-1]+1;
				ll d = B[i][r] - B[i][st[i][K-1]];
				dif[x] += d, dif[y] -= d;
				st[i].pop_back();
			}
			st[i].pb(r);
			f[r] += B[i][r];
		}
		rep(i,N) dif[i+1] += dif[i];
		rep(i,N) f[i] += dif[i];
		rep(l,r+1){
			chmax(ans,f[l]-(A[r]-A[l]));
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct Edge{
	int next,to,col,w;
}edge[maxn*2];
struct Tree{
	int l,r,num,sum;
}a[maxn*30];
int fi[maxn],se,n,q,depth[maxn],fa[maxn][18],si,rt[maxn],f[maxn][18];
inline void add_edge(int u,int v,int col,int w){
	edge[++se].next=fi[u],edge[se].to=v,fi[u]=se,edge[se].col=col,edge[se].w=w,
	edge[++se].next=fi[v],edge[se].to=u,fi[v]=se,edge[se].col=col,edge[se].w=w;
}
void change(int &x,int l,int r,int L,int w){
	a[++si]=a[x],x=si,a[x].num++,a[x].sum+=w;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(L<=mid)change(a[x].l,l,mid,L,w);
	else change(a[x].r,mid+1,r,L,w);
}
void dfs(int x){
	depth[x]=depth[fa[x][0]]+1;
	for(int i=1;;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1];
		if(!fa[x][i])break;
	}
	for(int i=fi[x];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa[x][0])continue;
		rt[v]=rt[x];change(rt[v],1,n,edge[i].col,edge[i].w);
		fa[v][0]=x,f[v][0]=edge[i].w;dfs(v);
	}
}
int up(int u,int k){
	for(int i=0;k;i++){
		if(k&(1<<i))k^=(1<<i),u=fa[u][i];
	}
	return u;
}
int lca(int u,int v){
	if(depth[u]>depth[v])swap(u,v);
	v=up(v,depth[v]-depth[u]);
	for(int i=17;~i;i--){
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	}
	return u==v?u:fa[u][0];
}
int dis(int u,int v){
	int k=depth[v]-depth[u],ans=0;
	for(int i=0;i<18;i++){
		if(k&(1<<i))ans+=f[v][i],v=fa[v][i];
	}
	return ans;
}
int query_num(int x1,int x2,int l,int r,int L){
	if(l==r)return a[x2].num-a[x1].num;
	int mid=(l+r)>>1;
	if(L<=mid)return query_num(a[x1].l,a[x2].l,l,mid,L);
	else return query_num(a[x1].r,a[x2].r,mid+1,r,L);
}
int query_sum(int x1,int x2,int l,int r,int L){
	if(l==r)return a[x2].sum-a[x1].sum;
	int mid=(l+r)>>1;
	if(L<=mid)return query_sum(a[x1].l,a[x2].l,l,mid,L);
	else return query_sum(a[x1].r,a[x2].r,mid+1,r,L);
}
int main(){
	int u,v,col,w;scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)scanf("%d%d%d%d",&u,&v,&col,&w),add_edge(u,v,col,w);
	dfs(1);
	for(int i=0;i<q;i++){
		scanf("%d%d%d%d",&col,&w,&u,&v);
		int L=lca(u,v);
		int ans=dis(L,u)+dis(L,v)+(query_num(rt[L],rt[u],1,n,col)+query_num(rt[L],rt[v],1,n,col))*w-query_sum(rt[L],rt[u],1,n,col)-query_sum(rt[L],rt[v],1,n,col);
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 55424
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int i;
  for (i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  cout << a.at(n - 1) - a.at(0) << endl;;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
using namespace std;

//?§??????°??????????????°?????¶????????????????????°
int n,m,h,k;

//???????§???????????§????1day???????????°
int s,t,p;

typedef pair<int,int> P;
typedef pair<P,int> PP;
struct edge{
	int to,cost,time,corp;
	
	edge(int to_,int cost_,int time_,int corp_){
		to=to_; cost=cost_; time=time_; corp=corp_;
	}
	
};
vector<edge> G[128];

// i????????????????????????????????????
int pass_corps[512];

// pass_cost[bit] bit?????¨?????????????????????????????????
int pass_cost[512];

//corps_cost[bit] bit?????¨???corps??????????????????1day??????????????????
int corps_cost[512];

const int INF=1e8;

int solve(int use){
	
	// d[time][pos]
	int d[25][128];
	for(int i=0;i<25;i++){
		for(int j=0;j<128;j++) d[i][j]=INF;
	}
	
	d[0][s]=corps_cost[use];
	priority_queue<PP,vector<PP>,greater<PP> > q;
	
	// cost,time,pos
	q.push(PP(P(corps_cost[use],0),s));
	while(!q.empty()){
		
		PP pp=q.top(); q.pop();
		
		int cost=pp.first.first,time=pp.first.second,pos=pp.second;
		
		//printf("cost %d, time %d, pos %d\n",cost,time,pos);
		
		if(pos==t) return cost;
		
		if(d[time][pos]<cost) continue;
		
		for(int i=0;i<G[pos].size();i++){
			edge e=G[pos][i];
			int to=e.to,ncost=cost+e.cost,nt=time+e.time,ncorp=e.corp;
			
			//printf("to %d, ncost %d, nt %d ncorp %d\n",to,ncost,nt,ncorp);
			
			if(nt>h) continue;
			
			if(use&(1<<ncorp)) ncost=cost;
			if(ncost<d[nt][to]){
				d[nt][to]=ncost;
				q.push(PP(P(ncost,nt),to));
			}
			
		}
		
	}
	
	return INF;
	
}

int main(){
	
	while(cin>>n>>m>>h>>k,n){
		
		for(int i=0;i<128;i++) G[i].clear();
		for(int i=0;i<512;i++){
			pass_corps[i]=0;
			pass_cost[i]=corps_cost[i]=INF;
		}
		for(int i=0;i<m;i++){
			int a,b,c,h,r;
			cin>>a>>b>>c>>h>>r;
			a--; b--; r--;
			
			G[a].push_back(edge(b,c,h,r));
			G[b].push_back(edge(a,c,h,r));
		}
		
		cin>>s>>t>>p;
		s--; t--;
		
		for(int i=0;i<p;i++){
			int l,d;
			cin>>l>>d;
			
			int corps=0;
			for(int j=0;j<l;j++){
				int corp;
				cin>>corp;
				corp--;
				corps|=(1<<corp);
			}
			
			pass_corps[i]=corps;
			pass_cost[corps]=d;
		}
				
		//corps_cost[bit] bit?????¨???corps??????????????????1day??????????????????
		corps_cost[0]=0;
		for(int i=0;i<(1<<k);i++){
			if(corps_cost[i]==INF) continue;
			for(int j=0;j<p;j++){
				corps_cost[i|pass_corps[j]]=min(corps_cost[i|pass_corps[j]],corps_cost[i]+pass_cost[pass_corps[j]]);
			}
		}
		
		int res=INF;
		for(int use=0;use<(1<<k);use++){
			if(corps_cost[use]==INF) continue;
			res=min(res,solve(use));
		}
		if(res==INF) res=-1;
		cout<<res<<endl;	
	}
}

Measured memory_bytes: 3228
//agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define mod 1000000007
#define endl '\n'
#define INT_MAX 1000000000000
typedef long long int ll ;
using namespace std;
ll dp[305][305];
ll dp2[305][305];
void init(){ for(int i=0;i<305;i++) for(int j=0;j<305;j++) { dp[i][j]=INT_MAX; dp2[i][j]=INT_MAX;} }
void shortest(ll n)
{
   for(int k=1;k<=n;k++){
       for(int i=1;i<=n;i++){
           for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
       }
   } 
}
int main()
{
    ll n,m,l;
    cin>>n>>m>>l;
    init();
    for(int i=1;i<=m;i++){
        ll a,b,c; cin>>a>>b>>c;
        dp[a][b]=c;
        dp[b][a]=c;
    }
    for(int i=0;i<=n;i++) dp[i][i]=0;
    shortest(n);
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++) cout<<dp[i][j]<<" ";
    //     cout<<endl;
    // }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[i][j]<=l) dp2[i][j]=0;
        }
        dp2[i][i]=0;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp2[i][j]= min(dp2[i][j],dp2[i][k]+1LL+dp2[k][j]);
            }
        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll a,b;
        cin>>a>>b;
        if(dp2[a][b]!=INT_MAX) cout<<dp2[a][b]<<endl;
        else cout<<-1<<endl;
    }
   
}

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

const int MAXN = 2005, MOD = 1e9 + 7;
long long f[MAXN * MAXN];
long long dp[MAXN][MAXN], n, k;
long long rev(long long a) {
	int b = MOD - 2;
	long long res = 1;
	for (b; b; b /= 2) {
		if (b % 2)
			res *= a, res %= MOD;
		a *= a, a %= MOD;
	}
	return res;
}
long long ch(int a, int b) {
	return f[a] * rev(f[b]) % MOD * rev(f[a - b]) % MOD;
}

int main() {
	cin >> n >> k;
	if (k == 1)
		return cout << 1, 0;
	f[0] = 1;
	for (int i = 1; i < MAXN * MAXN; i++)
		f[i] = f[i - 1] * i, f[i] %= MOD;
	for (int i = 0; i <= n; i++)
		dp[0][i] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			dp[i][j] = dp[i - 1][j] * ch(n * k - j - (i - 1) * (k - 1) - 1, k - 2) + dp[i][j - 1], dp[i][j] %= MOD;
	cout << f[n] * dp[n][n] % MOD;
}

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;


int main(){
  ll n;
   cin >> n;
   set<ll> paper;
   rep(i, 0, n){
     ll a;
     cin >> a;
     if(paper.count(a)) paper.erase(a);
     else paper.insert(a);
   }
   cout << paper.size() << endl;
}

Measured memory_bytes: 4864
X, Y, Z, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])[::-1]
B = sorted([int(a) for a in input().split()])[::-1]
C = sorted([int(a) for a in input().split()])[::-1]
L = [(0,0,0)]
for k in range(K):
    ma = 0
    for i,j,k in L:
        if A[i]+B[j]+C[k] > ma:
            ma = A[i]+B[j]+C[k]
            mai,maj,mak = i,j,k
    if mai+1<X and (mai+1,maj,mak) not in L: L.append((mai+1,maj,mak))
    if maj+1<Y and (mai,maj+1,mak) not in L: L.append((mai,maj+1,mak))
    if mak+1<Z and (mai,maj,mak+1) not in L: L.append((mai,maj,mak+1))
    print(ma)
    L.remove((mai,maj,mak))


Measured memory_bytes: 49884
#include <bits/stdc++.h>
using namespace std;
//define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// 許容する誤差ε
#define EPS (1e-10)
// 2つのスカラーが等しいかどうか
#define EQ(a,b) (abs((a)-(b)) < EPS)
// 2つのベクトルが等しいかどうか
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
//template
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
      }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
//typedef
typedef complex<double> Point;
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;



string str[1000];
bool used[1000*1000];
int dy[] = {-1, 0, 0, 1}, dx[] = {0,-1, 1, 0};
int h, w, k;
bool ok(int y, int x){
  if(y == 0 or y == h-1)return false;
  if(x == 0 or x == w-1)return false;
  return true;
}
int distance(int y, int x){
  int yy = min(y, (h-1)-y);
  int xx = min(x, (w-1)-x);
  return min(yy, xx);
}

signed main(){
  scanf("%lld%lld%lld", &h, &w, &k);
  rep(i,h){cin >> str[i];}
  P s;
  rep(i,h)rep(j,w)if(str[i][j] == 'S')s = P(i, j);
  
  queue<PP> q;
  q.push(PP(0, s));
  used[s.fi*w+s.se] = true;

  int d = distance(s.fi, s.se);
  while(!q.empty()){
    if(q.front().fi == k)break;
    PP p = q.front();q.pop();
    if(ok(p.se.fi, p.se.se) == false)break;
    rep(i,4){
      int yy = p.se.fi+dy[i], xx = p.se.se+dx[i];
      if(str[yy][xx] == '#' or used[yy*w+xx])continue;
      q.push(PP(p.fi+1, P(yy, xx)));
      d = min(d, distance(yy, xx));
      used[yy*w+xx] = true;
    }
  }
  
  printf("%lld\n", 1+(d+k-1)/k);
	return 0;
}









Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
#include <queue>
#include <deque>
#define ll long long
#define MP make_pair
#define PII pair<int, int>
#define F first
#define S second
using namespace std;
int n,ta,k;
string s;
ll res;
ll d,m,dm;
int main()
{
	cin >>n>>s>>ta;
	for (int tr=0;tr<ta;tr++)
	{
		cin >>k;
		res=d=m=dm=0;
		for (int i=0;i<n;i++)
	    {
			if (i>=k)
			{
				int t=i-k;
				if (s[t]=='D')
				{
					dm-=m;
					d--;
				}
				else if (s[t]=='M') m--;
			}
	    	if (s[i]=='D') d++;
	    	else if (s[i]=='M')
			{
				dm+=d;
				m++;
			}
			else if (s[i]=='C') res+=dm;
		}
		cout <<res<<"\n";
	}
	return 0;
}

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

int main() {
  ll n; cin >> n;
  ll div1,div2;
  for(ll i=1; i*i<=n; i++){
    if(n%i==0){
      div1 = i;
      div2 = n/i;
    }
  }

  cout << div2 + div1 -2 << endl;

}


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

int ruijo(int, int);
int main() {
    int n;
    cin>>n;
    vector<int> mao(n);
    for(int i=0; i<n; i++) cin>>mao.at(i);

    int64_t ans = 1;
    if(mao.at(0)!=0) {
        cout<<0<<endl;
        return 0;
    }
    else {
        vector<int> time(n);
        for(int i=1; i<n; i++) {
            time.at(mao.at(i))++;
        }
        if(time.at(0)!=0) {
            cout<<0<<endl;
            return 0;
        }
        
        for(int i=1; i<n-1; i++) {
            ans *= ruijo(time.at(i), time.at(i+1));
            ans = ans%998244353;
        }
        cout<<ans<<endl;
        return 0;
    }

    return 0;
}

int ruijo(int a, int b) {
    int i = 0;
    int64_t ans = 1;
    while(i<b) {
        ans *= a;
        ans = ans%998244353;
        i++;
    }
    return ans;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=200000+10;
struct dong{
	int id,x,y;
} p[maxn],p1,p2;
struct suan{
	dong x,y;
} a[maxn];
int sta[maxn];
int i,j,k,l,t,n,m,x,y,r,c,tot,top;
bool is(dong x){
	return x.x==0||x.y==0||x.x==r||x.y==c;
}
int sum(dong x){
    if(x.x==0) return 2*r+c+c-x.y;
    if(x.y==0) return x.x+x.y;
    if(x.x==r) return r+x.y;
    if(x.y==c) return r+c+r-x.x;
}
bool cmp(dong a,dong b){
	return sum(a)<sum(b);
}
int main(){
	scanf("%d%d%d",&r,&c,&n);
	fo(i,1,n){
		scanf("%d%d",&x,&y);
		p1=(dong){i,x,y};
		scanf("%d%d",&x,&y);
		p2=(dong){i,x,y};
		a[i]=(suan){p1,p2};
		if (is(p1)&&is(p2)){
			p[++tot]=p1;
			p[++tot]=p2;
		}
	}
	sort(p+1,p+tot+1,cmp);
	fo(i,1,tot){
		if (top&&sta[top]==p[i].id) top--;
		else sta[++top]=p[i].id;
	}
	if (top) printf("NO\n");else printf("YES\n");
}

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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);

    ll sum = 0;
    REP(i,n){
        cin >> a[i];
        sum += a[i];
    }

    ll ans = 0;
    ll half = 0;
    ll sum_2 = sum/2;
    REP(i,n){
        half += a[i];
        if(half >= sum_2){
            ans = half - (sum - half);
            ans = min(ans,(sum - (half-a[i])) - (half-a[i]));
            break;
        }
    }

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

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	int n, i;
	int k, p;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%d %d", &k, &p);
		
		if (k % p == 0){
			printf("%d\n", p);
		}
		else {
			printf("%d\n", k % p);
		}
	}
	
	return (0);
}

Measured memory_bytes: 596
def main():
    w, a, b = map(int, input().split())
    a1, a2 = a, a+w
    b1, b2 = b, b+w
    if a1 <= b1 and b1 <= a2:
        ans = 0
    elif a1 <= b2 and b2 <= a2:
        ans = 0
    else:
        if b2 <= a1:
            ans = a1 - b2
        elif a2 <= b1:
            ans = b1 - a2
    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;
typedef long long ll;

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

  ll n; cin >> n;

  vector<ll> table(n+1, 0);
  vector<ll> seive(n+1, 0);

  ll ret = 0;
  for(ll i = 1; i <= n; i++) {
    for(ll j = i; j <= n; j += i) {
      table[j]++;
    }

    ret += i * table[i];
  }

  cout << ret << "\n";

  return 0;
}


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

int main() {
  long long int N;
  cin >> N;
  vector<long int> vec (N);
  long int total = 0;
  for(long int i = 0;i < N;i++){
  	cin >> vec.at(i);
  	total += vec.at(i);
  }
  vector<long int> t (N-1);
  long int test = total;
  for(long int i = 0;i < N - 1;i++){
  	test -= vec.at(i);
  	t.at(i) = abs((total - test) - test);
  }
  sort(t.begin(),t.end());
  cout << t.at(0) << endl;
}

Measured memory_bytes: 3328
N, K = map(int, input().split())
P = 10 ** 9 + 7
X = [0] * (K + 1)
ans = 0
for i in range(1, K + 1):
    X[i] += i
    for j in range(i * 2, K+1, i):
        X[j] -= X[i]
    ans += X[i] * pow(K//i, N, P)
print(ans % P)

Measured memory_bytes: 12800
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<i64>();
    let f = |a: i64, b: i64| max(format!("{}", a).len(), format!("{}", b).len());
    let mut i = 1;
    let mut ans = std::usize::MAX;
    while i * i <= n {
        if n % i == 0 {
            ans = min(f(i, n / i), ans);
        }
        i += 1;
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
import java.util.*;
import java.io.*;

/*
   AtCoder contest code
   coder : yoichidon
 */

class UnionFind{
    int size;
    int[] parent;
    int[] height;
    public UnionFind(int size){
        this.size = size;
        parent = new int[size];
        height = new int[size];
        for(int i=0;i<size;i++){
            parent[i]=i;
            height[i]=0;
        }
    }
    private boolean isRoot(int node){
        return node==parent[node];
    }
    private int getRoot(int node){
        if(isRoot(node)) return node;
        else{
            parent[node] = getRoot(parent[node]);
            return parent[node];
        }
    }
    public void union(int node1, int node2){
        if(height[node1]>height[node2])parent[getRoot(node2)] = getRoot(node1);
        else parent[getRoot(node1)] = getRoot(node2);
    }
    public boolean find(int node1, int node2){
        return getRoot(node1)==getRoot(node2);
    }
    public int countGroup(){
        int ans = 0;
        for(int i=0;i<size;i++) if(isRoot(i)) ans++;
        return ans;
    }
}

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

        UnionFind communicate = new UnionFind(N+M);
        //node 0,1, ... , N : person n
        //node N, N+1, ..., N+M-1 : language m

        for(int n=0; n<N; n++){
            int K = sc.nextInt();
            for(int k=0; k<K; k++){
                int l = sc.nextInt()-1;
                communicate.union(n, N+l);
            }
        }

        for(int n=1; n<N; n++){
            if(!communicate.find(0,n)){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
        return;

    }
}


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

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define mp make_pair
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(s) s.begin(),s.end()
#define vll vector<ll>
#define vi vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define vd vector<double>
#define vull vector<ull>
#define vc vector<char>
#define vs vector<string>
#define fi first
#define se second
#define sz(x) x.size()
#define cinarr(n,a) for(int i = 0; i < n; i++) cin >> a[i];
#define coutarr(n,a) for(int i = 0; i < n; i++) cout << a[i] << (i+1==n?'\n':' ');
#define fori(i,a,b,x) for(int i = a; i <= b; i+=x)
#define ford(i,a,b,x) for(int i = a; i >= b; i-=x)
#define tc int t; cin >> t; for(int cs = 1; cs <= t; cs++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL);
#define ld long double
#define reset(x,y) memset(x,y,sizeof x);
#define sqr(x) 1LL*(x)*(x)
#define cube(x) 1LL*(x)*(x)*(x)
#define ub(v, a) upper_bound(all(v), a)
#define lb(v, a) lower_bound(all(v), a)
#define EPS 1e-10
#define INF 2000000000
#define mod 1000000007
#define minof(a) min_element(all(a))
#define maxof(a) max_element(all(a))
#define debug(val) cerr << "The value of " << #val << " is = " << val << endl;
#define testing cerr << "--------------------------\n";

//input space ---> scanf("%[^\n]%*c",s);

ll n,a[3005],sum,dp[3005][3005],vis[3005][3005];

ll f(ll l, ll r) {
	if(l+1 == r) {
		return max(a[l],a[r]);
	}
	if(l == r) {
		return a[l];
	}
	if(vis[l][r])
		return dp[l][r];
	ll ret = -INF;
	ll add = min(f(l+1,r-1),f(l+2,r));
	ret = max(ret,a[l]+add);
	add = min(f(l,r-2),f(l+1,r-1));
	ret = max(ret,a[r]+add);
	vis[l][r] = 1;
	return dp[l][r] = ret;
}

int main() {
	IOS
	cin >> n;
	fori(i,0,n-1,1) {
		cin >> a[i];
		sum += a[i];
	}
	ll X = f(0,n-1);
	cout << 2*X - sum << endl;
}


Measured memory_bytes: 139904
#include <iostream>
#include <iomanip>
#include <queue>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <bitset>

#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x, y) memset(x, y, sizeof(x))
#define pb push_back
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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 (a > b) {
      a = b;
      return 1;
   }
   return 0;
}

using namespace std;
using ll = long long;

const int kInf = 2e9;
const ll kLInf = 2e18;

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()
{
   cout << fixed << setprecision(10);
   int N, K;
   cin >> N >> K;
   string S;
   cin >> S;
   string ans = "";
   REP(i, K) {
      string tmp = S;
      reverse(S.begin(), S.end());
      S = tmp + S;
      string min(N, 'z');
      REP(i, N) {
         string subst = S.substr(i, N);
         if (subst < min) min = subst;
      }
      if (i == K-1) {
         ans = min;
      } else {
         reverse(min.begin(), min.end());
         if (ans == min) {
            reverse(min.begin(), min.end());
            ans = min;
            break;
         } else {
            ans = min;
            S = min;
         }
      }
   }
   cout << ans << endl;
   return 0;
}



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

using namespace std;
int main() {
	int n;
	bool start = true;
	cin >> n;
	cout << n << ": ";
	while (n != 1) {
		if (n % 2 == 0) {
			if (start) {
				cout << 2;
				start = false;
			}
			else cout << " " << 2;
			n /= 2;
		}
		else {
			bool judge = true;
			for (int i = 2; i <= sqrt(n); i++) {
				if (n%i == 0) {
					judge = false;
					if (start) {
						cout << i;
						start = false;
					}
					else cout << " " << i;
					n /= i;
					break;
				}
			}
			if (judge) {
				if(start)cout << n ;
				else cout << " " << n;
				n = 1;
			}
		}
		
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 3088
#17D8103001E Fukushima Emi persimmon8 python 19.10.24

n=int(input())
A=list(map(int,input().split()))
count=0

def merge(A,left,mid,right):
    global count

    L=A[left:mid]+[10000000000000]
    R=A[mid:right]+[100000000000000]

    i=0
    j=0
    for k in range(left,right):
        count+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else: 
            A[k]=R[j] 
            j=j+1

def mergeSort(a,left,right):
    if left+1<right:
         mid=(left+right)//2
         mergeSort(A,left,mid)
         mergeSort(A,mid,right)
         merge(A,left,mid,right)

mergeSort(A,0,n)
d=map(str,A)
print(' '.join(d))
print(count)



Measured memory_bytes: 66772
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        var NX = ReadLine().Split();
        int N = int.Parse(NX[0]);
        long X = long.Parse(NX[1]);

        var all = new long[N + 1];
        all[0] = 1;
        var Patty = new long[N + 1];
        Patty[0] = 1;
        for (int i = 0; i < N; i++)
        {
            all[i + 1] = all[i] * 2 + 3;
            Patty[i + 1] = Patty[i] * 2 + 1;
        }
        int n = N;
        long ans = 0;
        while (n > 1)
        {
            if (X >= all[n] / 2+1)
            {
                ans += Patty[n] / 2+1;
                X -= all[n] / 2;
            }
            else if (X == all[n] / 2+1)
            {
                ans += Patty[n] / 2+1;
                break;
            }
            else if (X == all[n] / 2) {
                ans += Patty[n] / 2;
                break;
            }
            X--;
            n--;
        }
        
        if (n == 1&&X>0)
        {
            X = Min(5, X);
            string s = "BPPPB".Substring(0, (int)X);
            ans += s.Count(_ => _ == 'P');
        }
        WriteLine(ans);
        
    }
}


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


ull gcd(ull a,ull b){
	if(!b) return a;
	return gcd(b,a%b);
}


int main(){
	int n;
	cin >> n;
	int a[n],cnt[100010] = {0};
	
	rep(i,0,n){
		cin >> a[i];
		if(a[i] >= 1) cnt[a[i]-1]++;
		cnt[a[i]+1]++;
		cnt[a[i]]++;
	}
	
	sort(cnt,cnt+100010,greater<int>());
	
	cout << cnt[0] << endl;
	return 0;
}

Measured memory_bytes: 1024
// g++ macro.cpp -std=c++14
#include <bits/stdc++.h> //STL include
typedef long long ll;// long long int
const ll INF = 10000000000;//INFinity
using namespace std;//namespace

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}//transform
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//#define int long long // yabai

#define dump(x)  cout << #x << " = " << (x) << endl;// debug cout

#define FOR(i,a,b) for(int i=(a);i<(b);++i)// for macro
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define ALL(obj) (obj).begin(),(obj).end()// iterator

#define pb(a) push_back(a)//push_back
#define mp make_pair// make_pair


int main(){

    string s;
    cin>>s;
    //vector<int> vec;
    //REP(i,s.size())vec.pb(s.at(i)=='g'?0:1);
    //for(auto t:vec)dump(t);
    int val=0;
    int point=0;
    REP(i,s.size()%2==0?s.size():s.size()-1)val+=(s.at(i)=='g'?1:-1);
    point+=val/2;
    if(s.size()%2!=0)point+=(s.back()=='g'?0:-1);
    cout<<point<<endl;

    return 0;
}


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

int main()
{
  int k,n,ans=0;
  cin >> n >> k;
  vector<int> p(n);
  for(int i=0; i<n; i++){
    cin >> p[i];
  }
  for(int i=0; i<n-1;i++){
    for(int j=i; j<n; j++){
      if(p[i]>p[j])swap(p[i],p[j]);
    }
  }

  for(int i=0; i<k; i++)
    ans+=p[i];

  cout << ans;

  return 0;

}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 200002;
int a,b,c,d;
 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b>>c>>d;
    cout<<min(a,b)+min(c,d)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;

#define INF 1e9
#define vi vector<int>
#define vf vector<float>
#define vc vector<char>
#define vs vector<string>
#define vb vector<bool>
#define ll long long
#define lint long int
#define llint long long int
#define atoz abcdefghijklmnopqrstuvwxyz
#define atoZ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
#define AtoZ ABCDEFGHIJKLMNOPQRSTUVWXYZ
#define mapSI map<string, int>
#define mapII map<int, int>
#define mapSS map<string, string>
#define pb push_back

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep2(i, n) for(int i = 0; i < (n); i += 2)
#define repv(i, n, v) for(int i = 0; i < (n); i += v)
#define rrep(i, n) for(int i = n; i >= 0; i--)
#define sortN(a, b, c) c == 0 ? sort(a, a + b) : sort(a, a + b, greater<int>())
#define sortI(i, a) a == 0 ? sort(s.begin(), s.end()) : sort(s.begin(), end(), greater<int>)
#define sortS(s, a) a == 0 ? sort(s.begin(), s.end()) : sort(s.begin(), end(), greater<char>)
#define all(a) a.begin(), a.end()

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

int main(void){

  //入力
  int N, K;
  cin >> N >> K;
  
  //配列の入力
  int h[N];
  int ans = 0;
  for(int i = 0; i < N; i++){
    cin >> h[i];
    if(h[i] >= K) ans++;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 640
#include <cstdio>

using namespace std;

int N;
int cnt[100005];
int Q;
long long sum;

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int A; scanf("%d", &A);
		sum += A;
		cnt[A]++;
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++) {
		int B, C; scanf("%d%d", &B, &C);
		sum += (C - B) * cnt[B];
		cnt[C] += cnt[B];
		cnt[B] = 0;
		printf("%lld\n", sum);
	}
	return 0;
}


Measured memory_bytes: 2116
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <algorithm>

using namespace std;

#define INT_MAX 2147483647

int main( void ){

	string str;

	cin >> str;

	int cnt = 0;
	for(int i = 0; i < str.size(); i++ ){
		if(str[i] == '1') cnt++;
	}
	int a = (int)str.size() - cnt;
	int ans = (int)str.size() - abs(a-cnt);
	cout << ans << endl;
	return 0;

}



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

int main() {
	
	int A[3][3],i,j;
	for(i=0;i<3;++i)
	{
		for(j=0;j<3;++j)
		{
			cin>>A[i][j];
		}
	}
	
	int N;
	cin>>N;
	
	int B[N];
	for(i=0;i<N;++i)
	{
		cin>>B[i];
	}
	
	int c=0,f=0;
	for(i=0;i<N;++i)
	{
		for(int k=0;k<3;++k)
		{
			for(j=0;j<3;++j)
			{
				if(B[i]==A[k][j])
				{
					A[k][j]=0;
                  B[i]=0;
					c++;
					f=1;
				}
			}
		}
	}
	
	if(c<3||f==0)
	{
		cout<<"No"<<endl;
	}
	else
	{
	    if((A[0][0]==0&&A[1][1]==0&&A[2][2]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[0][2]==0&&A[1][1]==0&&A[2][0]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[0][1]==0&&A[0][2]==0&&A[0][0]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[1][1]==0&&A[1][2]==0&&A[1][0]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[2][1]==0&&A[2][2]==0&&A[2][0]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[1][1]==0&&A[0][1]==0&&A[2][1]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[1][2]==0&&A[0][2]==0&&A[2][2]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else if((A[0][0]==0&&A[1][0]==0&&A[2][0]==0))
	    {
	    	cout<<"Yes"<<endl;
	    }
	    else
	    {
	    	cout<<"No"<<endl;
	    }
	}
	
	
	
	return 0;
}


Measured memory_bytes: 256