akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    string s;
    cin>>s;
    int k;
    cin>>k;
    long int ans=0,l=0,r=0,n=s.length(),z=0;
    vector<long int> v;
    while(1)
    {
        if(r>=n)
        break;
        while(r<n&&s[l]==s[r])
        r++;
        v.push_back((r-l)/2);
        if(r==n&&v.size()>1)
        {
            while(s[l]==s[r%n])
            r++;
            if(r>n)
            z=(r-l)/2;
            break;
        }
        l=r;
    }
    if(v.size()==1)
    ans=(k*s.length())/2;
    else if(z)
    {
        ans+=v[0]+v[v.size()-1];
        for(int i=1;i<v.size()-1;i++)
        ans+=k*v[i];
        ans+=(k-1)*z;
    }
    else
    {
    	for(int i=0;i<v.size();i++)
    	ans+=k*v[i];
	}
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define inf (1<<29)
#define sq(n) ((n)*(n))
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MEMSET(a) memset(a,0,sizeof(a))
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
using ll = long long;

signed main(){
    int m;
    cin>>m;
    rep(i,m){
        set<string> set;
        string s;
        cin>>s;
        int l=s.length();
        rep(i,l-1){
            string a=s.substr(0,i+1);
            string b=s.substr(i+1);
            set.insert(a+b);
            string c=a;
            reverse(c.begin(),c.end());
            string d=b;
            reverse(d.begin(),d.end());
            set.insert(a+d);
            set.insert(c+b);
            set.insert(c+d);
            set.insert(b+a);
            set.insert(d+a);
            set.insert(b+c);
            set.insert(d+c);
        }
        cout<<set.size()<<endl;
    }
    return 0;
}


Measured memory_bytes: 3068
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include<random>
#include<ctime>
#include<cstdlib>
#include<complex>
#include<fstream>
using namespace std;

int main(){

  int n, k, a[200000], cnt[200001]={0}, kind=0, ans=0, max=0;

  cin >> n >> k;

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

  for(int i=0; i<=200000; i++){
    if(cnt[i]!=0){
      kind++;
    }
  }

  sort(cnt, cnt+200001);

  for(int i=1; i<=200001; i++){
    if(kind<=k){
      cout << ans << endl;
      return 0;
    }
    if(cnt[i]!=0){
      ans+=cnt[i];
      kind--;
    }
  }

  return 0;
}

Measured memory_bytes: 1792
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cmp;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};

fn main() {
    proconio::input! {
        a: i64,
        b: i64,
        c: i64,
        d: i64
    }
    println!("{}", cmp::max(cmp::max(a*c,a*d), cmp::max(b*c,b*d)));
}


Measured memory_bytes: 2152
#include <stdio.h>

int main(void)
{

    int c1, c5, c10, c50, c100, c500;

    scanf("%d %d %d %d %d %d", &c1, &c5, &c10, &c50, &c100, &c500);

    c5 += c1 / 5;
    c10 += c5 / 2;
    c50 += c10 / 5;
    c100 += c50 / 2;
    c500 += c100 / 5;

    if(c500 >= 2)
        printf("1\n");
    else
        printf("0\n");

    return 0;
}

Measured memory_bytes: 584
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <stack>
#include <random>
#include <bitset>
#include <numeric>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it) {
	*this << ((it != d.b) ? ", " : "") << *it;
  }
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int nax = 1e5+5;
int a[nax];
ll s[nax];
ll minContrib[nax];
int n;

pair<ll, ll> f(ll minPara) {
	ll res = 0;
	ll par = 0;
	// printf(" min para: %lld\n", minPara);
	rep(i,0,n) {
		// a[i],  a[i] + a[j] >= minPara => a[j] >= minPara - a[i]
		int pos = lower_bound(a, a +n, minPara - a[i]) - a;
		ll ile = (n - pos);
		par += ile;
		ll contrib = 0;
		if (pos < n) contrib = s[pos];
		res += (ile * a[i]) + contrib;
		// printf("Adding:a: %d, %d -> %d-%d, res: %lld, contrib: %lld\n", i, a[i], pos, n - 1, res, contrib);
	}
	return mp(res, par);
}

int main() {
	ios_base::sync_with_stdio(false);
	ll m;
	cin >> n >> m;
	rep(i,0,n) cin >> a[i];
	sort(a,a+n);
	s[n-1] = a[n - 1];
	ford(i, n-1, 0) s[i] = s[i + 1] + a[i];
	ll lo = 2*a[n-1] + 1, hi = 2 *a[0];
	swap(lo, hi);
	while (lo < hi) {
		ll sr = (lo + hi) / 2;
		// printf("%lld %lld\n", lo, hi);
		auto res = f(sr);
		// printf("%lld -> %lld, %lld\n", sr, res.st, res.nd);
		if (res.nd > m) {
			lo = sr + 1;
		} else {
			hi = sr;
		}
	}
	// cout << lo << endl;
	auto pom = f(lo - 1);
	pom.st -= (pom.nd - m)*(lo - 1);
	cout << pom.st << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int main() {
    int n;
    cin >> n;
    if(n==1){
        cout << "1\n";
    }
    else{
        int i, j;
        int tmp = 0, res = 0;
        for(i=2; i<=n; i++){
            for(j=2; j<=n; j++){
                tmp = pow(i, j);
                if(tmp>n){
                    break;
                }
                else{
                    res = max(res, tmp);
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3964
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		int min=9999;
		int[] a=new int[s.length()-2];
		for(int i=0; i<s.length()-2; i++) {
			a[i]=Integer.parseInt(s.substring(i, i+3));
			min=Math.min(Math.abs(a[i]-753), min);
		}
		System.out.println(min);
	}
}

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

int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    int K;

    cin >> N >> K;

    vector<long> hpList = {};
    for (int i=1; i < N+1; i++) {
        int hp;
        cin >> hp;
        hpList.push_back(hp);
    }

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

    long cnt = 0;
    for (int i=0; i < N-K; i++) {
        long hp = hpList[i];
        cnt += hp;
    }

    cout << cnt;

    return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>

using namespace std;

#define INF 999999999

int main(){
	int i, j;
	char s[101];
	stack<int> st;
	int flag;
	
	while(1){
		gets(s);
		if(s[0]=='.')break;
		flag = 1;
		while(!st.empty()) st.pop();
		
		for(i=0;s[i]!='\0';i++){
			if(s[i]=='(') st.push(1);
			else if(s[i]=='[') st.push(2);
			else if(s[i]==')'){
				if(!st.empty()&&st.top()==1){
					st.pop();
				}
				else {
					flag = 0;
					break;
				}
			}
			else if(s[i]==']'){
				if(!st.empty()&&st.top()==2){
					st.pop();
				}
				else {
					flag = 0;
					break;
				}
			}
		}
		
		if(flag && st.empty()) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

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

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

    int lcs[1010][1010];

    for (int i = 0; i < q; i++)
    {
        string x, y;
        cin >> x >> y;
        Fill(lcs, 0);
        for (int j = 1; j <= x.size(); j++)
        {
            for (int k = 1; k <= y.size(); k++)
            {
                if(x[j-1] == y[k-1]) lcs[j][k] = lcs[j-1][k-1] + 1;
                else lcs[j][k] = max(lcs[j-1][k], lcs[j][k-1]);
            }
        }
        cout << lcs[x.size()][y.size()] << endl;
    }

}


Measured memory_bytes: 7132
// 問題の URL を書いておく
// 

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

int vt[3005][3005] = {};
ll dp[3005][3005][4] = {};

int main(int, const char**)
{
    int R, C, K;
    cin >> R >> C >> K;
    rep(i, K)
    {
        int r, c, v;
        cin >> r >> c >> v;
        vt[r - 1][c - 1] = v;
    }

    rep(i, R)
    {
        rep(j, C)
        {
            for(int k = 2; k >= 0; --k)
            {
                dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + vt[i][j]);
            }
            rep(k, 4)
            {
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k]);
                dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
            }
        }
    }
    ll ans = 0;
    rep(i, 4)
    {
        ans = max(ans, dp[R - 1][C - 1][i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 320560
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int N = 2e5;
ll v[N], n, m, c, p;
bool check(ll index) {
	int n1 = upper_bound(v, v + n, v[index]) - v;
	if (n - n1 < p)
		return true;
	else {
		int n2 = upper_bound(v, v + n, v[index] + m) - v;
		if (n - n2 >= p)
			return false;
		
		ll s = m * (p - 1 + n1);
		for (int j = index + 1; j <= n - p; j++)
			s += min(m, v[index] + m - v[j]);
		if (s >= m * c)
			return true;
		else
			return false;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("intt.txt", "r", stdin);
	freopen("outt.txt", "w", stdout);
#endif
	cin >> n >> m >> c >> p;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	sort(v, v + n);
	int ans, s = 0, e = n - 1;
	while (s <= e) {
		int mid = s + (e - s) / 2;
		if (check(mid)) {
			ans = mid;
			e = mid - 1;
		}
		else
			s = mid + 1;
	}
	cout << n - ans;
	return 0;
}


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

int main() {
	int a, b, c, box;

	cin >> a >> b >> c;

	for (int i = 0; i < 3; i++) {
		if (a > b) {
			box = a;
			a = b;
			b = box;
		}
		if (b > c) {
			box = b;
			b = c;
			c = box;
		}
		if (a < b&&b < c)
			break;
	}

	cout << a << " " << b << " " << c << endl;

	return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(i) i.begin(),i.end()
template<typename T=ll> using v =vector<T>;
template<typename T=ll> using vv = vector<v<T>>;
template<typename T=ll,typename U=ll> using p = pair<T,U>;
const ll INF = (ll)1e9;
template<typename T> T chmin(T &a,T b){a=min(a,b);}
template<typename T> T chmax(T &a,T b){a=max(a,b);}


int main(){
    ll n; cin >> n;
    auto a = v<>(n,0);
    rep(i,n) cin >> a[i];
    ll ans = pow((ll)3,n);
  	ll bad = 1;
    bool gu = false;
    rep(i,n){
      bad*=a[i]%2?1:2;
    }
  	cout << ans -bad << endl;

}

Measured memory_bytes: 256
from heapq import heapreplace, heappush

n, v = map(int, input().split())
programs = [tuple(map(int, input().split())) for _ in range(n)]
programs.sort()
tmp = [None] * v
combined = []
for s, t, c in programs:
    c -= 1
    prev = tmp[c]
    if prev is not None:
        ps, pt, pc = prev
        if pt == s:
            tmp[c] = (ps, t, c)
        else:
            combined.append((ps, pt, pc))
            tmp[c] = (s, t, c)
    else:
        tmp[c] = (s, t, c)
for prev in tmp:
    if prev is not None:
        combined.append(prev)
combined.sort()

recorders = [(-1, None)]
for s, t, c in combined:
    end, channel = recorders[0]
    if end < s or c == channel:
        heapreplace(recorders, (t, c))
    else:
        heappush(recorders, (t, c))
print(len(recorders))


Measured memory_bytes: 25956
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int main(){

	ll H,W;
	scanf("%lld %lld",&H,&W);

	ll small = min(H,W);
	ll big = max(H,W);

	if(small >= 3){
		printf("%lld\n",(small-2)*(big-2));
	}else if(small == 2){
		printf("0\n");
	}else{ //samll == 1

		if(big == 1){
			printf("1\n");
		}else{
			printf("%lld\n",big-2);
		}
	}

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void printArr(int[] arr) {
        String[] ss = new String[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ss[i] = String.valueOf(arr[i]);
        }
        System.out.println(String.join(" ", ss));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] inputs = new int[n];
        for (int i = 0; i < n; i++) {
            inputs[i] = sc.nextInt();
        }
        printArr(inputs);
        for (int i = 1; i < n; i++) {
            int v = inputs[i];
            int j = i - 1;
            while(j >= 0 && inputs[j] > v) {
                inputs[j + 1] = inputs[j];
                j--;
            }
            inputs[j + 1] = v;
            printArr(inputs);
        }

    }

}


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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rrepa(i,a,n) for(int i=n-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

int main(){

    string s;
    cin>>s;

    cout<<s.substr(0,3)<<"\n";

    return 0;

}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n; cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	
	ll ans = a[n - 1] - a[0];
	for(int i = 0, j = n - 1; i < j; i++){
		if(i + 2 == j){
			ans += max(a[j] - a[i + 1], a[j - 1] - a[i]);
			break;
		}
		ans += a[j] - a[i + 1];
		ans += a[--j] - a[i];
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
using namespace std;

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;
using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

// swap(a,b);
// abs(a,b); a,bの型は問わない
// reverse(a+I,a+r); aは配列,a[i]からa[r-1]までを逆順にする.計算量はN. reverse(str.begin(),str.end());
// sortも上とあまり変わらない.
// ただし,sort(a,a+N,greater<int>());で大きい順にならべかえる.
// stack<int> a; 宣言 上に積み上げたものをとったり、一番上に積み上げる.
// a.push(x); aに要素xをつむ a.pop(); a.size(); a.empty(); これはtrue or false
// a.top;で一番上の要素を返す
// queue<int> a; a.front();
// priority_queue<int,vector<int>,greater<int>> Q1; 最も小さい奴を取り出す
// priority_queue<double,vector<double>,less<double>> Q2;最も大きい値を取り出す
// Q1.top();ができる
// count(a+l,a+r,x);
// find(a+l,a+r,x);
// 文字変換
//char a='a';
//a=a+1;
//cout<<a<<endl;


int main(){
  ll H;cin>>H;
  int N;cin>>N;
  VI A(N);
  ll max=0;
  REP(i,N){
    cin>>A[i];
    max=max+A[i];
  }
  if(max>=H){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }

}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(long long N, long long K, std::string S)
{
    ll ans = 0;

    // 「1 の個数」「0 の個数」を交互に記録していく
    vector<int> nums;
    for (int i = 0; i < S.size();)
    {
        int j = i;
        while (j < S.size() && S[j] == S[i])
            ++j;
        nums.push_back(j - i);
        i = j;
    }
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] > 1)
        {
            ans += nums[i] - 1;
        }
    }

    vector<int> points;
    if (nums.size() == 1)
    {
        cout << ans << endl;
        return;
    }
    ll cnt = nums.size() - 1;
    ll loop = ceil(cnt, 2);

    if (loop <= K)
    {
        ans += cnt;
    }
    else
    {
        ans += K * 2;
    }

    cout << ans << endl;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::string S;
    std::cin >> S;
    solve(N, K, S);
    return 0;
}


Measured memory_bytes: 1148
#include <stdio.h>

int main(){
	int N, A, i, odd_num = 0;
	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%d", &A);
		odd_num += A % 2;
	}
	if(odd_num % 2 == 0){
		printf("YES\n");
	}
	else{
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<cstdio>
 
using namespace std;
 
int main() {
  int n;
  scanf("%d",&n);
  int a[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
 
  int maxv = a[1] - a[0];
  int minv = a[0];
 
  for (int j = 1; j < n; j++) {
    minv = min(minv, a[j-1]);
    maxv = max(maxv, a[j] - minv);
  }
 
  printf("%d\n", maxv);
 
  return 0;
}

Measured memory_bytes: 3984
n=int(input())
flag=False
l=[]
for i in range(0,n):
    if(i==0):
        s=input()
        l.append(s)
    if(n==1):
        print('Yes')
        continue
    if(i>=1):
        s=input()
        li=list(st)
        if(li[-1]==s[0] and s not in l):
            flag=True
        else:
            print('No')
            exit()
        l.append(s)
    st=s
if(flag):
        print('Yes')

Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>

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 co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mod = 998244353;
const int IMAX = 100000;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}

int dp[3001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N, S;
	scanf("%d %d", &N, &S);

	int A[3000];
	rep(i, N) scanf("%d", A + i);
	sort(A, A + N);

	ll k2 = modpow(2, mod - 2);
	dp[0] = modpow(2, N);
	int s = 0;
	ll kotae = 0;
	rep(i, N) {
		s = min(S - A[i], s + A[i]);

		if (S >= A[i]) kotae += dp[S - A[i]];
		for (int j = s; j >= A[i]; j--) {
			dp[j] = (dp[j] + dp[j - A[i]] * k2) % mod;
		}
	}

	printf("%lld\n", kotae % mod * k2 % mod);

	Would you please return 0;
}

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

int INFp=1000000007;
const string minusinf ="-";
const int mininf = -1;
int cost[10]={0,
    2
    ,
    5
    ,
    5
    ,
    4
    ,
    5
    ,
    6
    ,
    3
    ,
    7
    ,
    6
};
void chmax(string &a,string b){
    if(a == minusinf) a=b;
    else if(a.size()<b.size()) a=b;
    else if(a.size()==b.size()){
        if(a<b) a=b;
    }
}


int main(){
    int n,m;
    int a[15];
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>a[i];
    
    //sort(a,a+m,greater<int>());
    
    //int dp[11000]={-1};//i本使うときの最大桁数
    
    vector<int> dp(n+1, -1);
    dp[0]=0;
    
    for(int i=0; i<=n; i++){
        if(dp[i] == -1)
            continue;
        
        int index;
        for(int j=0; j<m; j++){
            index = i + cost[a[j]];
            if(index > n)
                continue;
            
            dp[index] = max(dp[index], dp[i]+1);
        }
    }
    
    
    int costcount=n;
    
    vector<int> ans;
    int cnt = n;
    for(int i=0; i<dp[n]; i++){
        int select = -1;
        for(int j=0; j<m; j++){
            int dst = cnt - cost[a[j]];
            if(dst < 0 || dp[dst] == -1)
                continue;
            
            if(dp[cnt]-dp[dst] == 1)
                select = max(select, a[j]);
        }
        
        ans.push_back(select);
        cnt -= cost[select];
    }
    
    
    for(int i=0;i<ans.size();i++){
        cout<<ans[i];
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#define N 105
using namespace std;
typedef long long ll;
int n;
int s[N];
int main() {
	cin>>n;
	for (int i = 1; i <= n; ++i) {
		cin>>s[i];
	}
	int dp[N][10];
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 10; ++j) {
			if (dp[i][j] < 0) continue;
			dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
			dp[i+1][(j+s[i+1])%10] = max(dp[i+1][(j+s[i+1])%10], dp[i][j] + s[i+1]);
		}
	}
	int ans = 0;
	for (int i = 1; i < 10; ++i) {
		ans = max(ans, dp[n][i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
H, W, D = map(int, input().split())
C = {}
for i in range(H):
    A = [int(i) for i in input().split()]
    for j in range(W):
        C[A[j]] = (i, j)

MaxD = D * ((H*W)//D)
Cost = [[0] for i in range(D)]
for i in range(D):
    now = (D if i == 0 else i)
    nowx, nowy = C[now]
    while now + D <= H * W:
        nextx, nexty = C[now+D]
        MP = abs(nowx - nextx) + abs(nowy - nexty)
        Cost[i].append(Cost[i][-1] + MP)
        now += D
        nowx, nowy = nextx, nexty

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    mod = l % D
    if mod == 0:
        print(Cost[mod][r//D - 1] - Cost[mod][l//D - 1])
    else:
        print(Cost[mod][r//D] - Cost[mod][l//D])

Measured memory_bytes: 27488
#include<bits/stdc++.h>
#include<vector>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define rep(i,N) for(int i=0;i<N;i++)

using namespace std;

int main(void){
    int k1,h1,k2,h2,a,b,c,d,p1,p2;
    cin>>h1>>h2>>k1>>k2>>a>>b>>c>>d;
    p1=h1*a+h2*b+int(h1/10)*c+int(h2/20)*d;
    p2=k1*a+k2*b+int(k1/10)*c+int(k2/20)*d;
    if(p1>p2)cout<<"hiroshi"<<endl;
    else if(p1<p2)cout<<"kenjiro"<<endl;
    else cout<<"even"<<endl;
}




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

using namespace std;

int n, ans;

bool viz[102];

int main()
{
  pair<int, int>  v[102], v1[102];
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].first >> v[i].second;
  }
  for (int i = 1; i <= n; i++) {
    cin >> v1[i].first >> v1[i].second;
  }
  sort (v + 1, v + n + 1);
  sort (v1 + 1, v1 + n + 1);
  for (int i = 1; i <= n; i++) {
    int k = 0;
    for (int j = n; j > 0; j--)
      if (v1[i].first > v[j].first) {
        k = j;
        break;
      }
    int maxx = -1, poz;
    for (int j = k; j > 0; j--) {
      if (v[j].second < v1[i].second && !viz[j]) {
        if (maxx < v[j].second) {
          maxx = v[j].second;
          poz = j;
        }
      }
    }
    if (maxx != -1) {
      viz[poz] = 1;
      ans++;
    }
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define pa pair<ll,ll>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define lowbit(x) (x&(-x))
#define Z(x) (x>=mod?x-mod:x)
#define N 1010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
ll n;
ll x[N],y[N];
ll len[N],tot;
ll flag;
int main()
{
	//ios::sync_with_stdio(false);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	FOR(i,1,n)x[i]=read(),y[i]=read();
	flag=abs(x[1]+y[1])&1;
	FOR(i,1,n)if((abs(x[i]+y[i])&1)^flag){puts("-1");return 0;}
	printf("%lld\n1 ",32-flag);
	len[tot=1]=1;
	if(!flag){FOR(i,0,30){len[++tot]=(1<<i);printf("%d ",(1<<i));}}
	else {FOR(i,1,30){len[++tot]=(1<<i);printf("%d ",(1<<i));}}
	puts("");
	FOR(i,1,n)
	{
		ll nowx=0,nowy=0;
		string s;
		REP(j,tot,1)
		{
			ll dx=x[i]-nowx,dy=y[i]-nowy;
			if(abs(dx)>abs(dy)){dx<0?(s+='L',nowx-=len[j]):(s+='R',nowx+=len[j]);}
			else {dy<0?(s+='D',nowy-=len[j]):(s+='U',nowy+=len[j]);}

		}			
		reverse(s.begin(),s.end());
		cout<<s<<endl;
		//cout<<endl;
	}
	return 0;
}
//check first submit second


Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
inline int inv(int x){return qpow(x,mod-2);}
const int inv2= inv(2);
/* math */
int B,W;
const int N=2e5+5;int fac[N],ifac[N];
inline void init(int n){
	fac[0]=ifac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	ifac[n]=qpow(fac[n],mod-2);for(int i=n-1;i;i--)ifac[i]=mul(ifac[i+1],i+1);
}
inline int binom(int a,int b){
	if(b>a)return 0;
	return mul(fac[a], mul(ifac[b], ifac[a-b]));
}

int main()
{
	cin >> B >> W;
	init(B+W);
	int pB=0,pW=0;
	for(int i=1;i<=B+W;i++){
		printf("%d\n",add(pB, mul(inv2,sub(1,add(pB,pW)))));
		//Only_black
		pB = add(pB, mul(qpow(inv2,i), binom(i-1, W-1)));
		//Only_white
		pW = add(pW, mul(qpow(inv2,i), binom(i-1, B-1)));
	}
}

Measured memory_bytes: 3712
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n, h;
  cin >> n >> h;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i] >> b[i];

  sort(a.begin(), a.end(), greater<int>());
  sort(b.begin(), b.end(), greater<int>());

  int ans = 0;
  rep(i, n) {
    if (b[i] < a[0]) break;
    h -= b[i];
    ans++;
    if (h <= 0) {
      cout << ans << endl;
      return 0;
    }
  }

  ans += (h + a[0] - 1) / a[0];
  cout << ans << endl;


  
  return 0;
}

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

using namespace std;

#ifndef ONLINE_JUDGE
  #define pr_vars(...) do { cerr << "DEBUG: line "<< __LINE__ << ": " << __PRETTY_FUNCTION__ << ":  "; \
                            pr_var(split(#__VA_ARGS__, ',').begin(), __VA_ARGS__); } while(0)
#else
  __attribute__ ((constructor)) static void fast_cin() { ios_base::sync_with_stdio(false); cin.tie(0); }
  #define pr_vars(...) do { } while(0)
#endif /* ONLINE_JUDGE */

using ll = int64_t;
using ull = uint64_t;
using mp = pair<ll, ll>;
using mt = tuple<ll, ll, ll>;    // unpack: tie(ll, ll, ll) = mt;
#define X first
#define Y second
#define pb push_back

istream &operator>> (istream &fin, mp &p) { fin >> p.first >> p.second; return fin; }
ostream &operator<< (ostream &fout, const mp &p)
{ fout << "{" << p.first << ", " << p.second << "} "; return fout; }

template<typename T> ostream &operator<< (ostream &fout, const vector<T> &vec)
{ for (size_t i = 0; i < vec.size(); i++) fout << vec[i] << ' '; return fout; }

template<typename T> istream &operator>> (istream &fin, vector<T> &vec)
{ for (size_t i = 0; i < vec.size(); i++) fin >> vec[i]; return fin; }

vector<string> split(const string &s, char c) { vector<string> v; ull st = 0, fn = 0, lvl = 0;
for ( ; fn < s.size(); fn++ ) { if (s[fn] == c && lvl == 0) { v.push_back(s.substr(st, fn - st)); st = fn + 1; }
if (s[fn] == '(') { lvl++; } if (s[fn] == ')') { lvl--; } } v.push_back(s.substr(st, fn - st)); return v; }

void pr_var(vector<string>::iterator it) { (void) it; cerr << endl; }
template<typename T, typename... Args> void pr_var(vector<string>::iterator it, T a, Args... args)
{ cerr << *it << "=" << a << "  "; pr_var(++it, args...); }

ll div_ceil(ll n, ll d) { ll res = n / d; if (res >= 0) res += n % d ? 1 : 0; return res; }
ll gcd(ll a, ll b) { a = llabs(a); b = llabs(b); while (a && b) a > b ? a %= b : b %= a; return a + b; }
ll lcm(ll a, ll b) { ll c = gcd(a, b); return c == 0 ? 0 : llabs(a / c * b); }

#define setp(a) fixed << setprecision(a)
const double PI = acos(-1.0);
constexpr double EPS = 1e-9;
constexpr ll INF = numeric_limits<ll>::max();
constexpr ll MOD = 1e9 + 7;


constexpr ll MAX = 1e5 + 5;

int main()
{
    ll n, k; cin >> n >> k;
    vector<ll> a(n); cin >> a;
    ll res = 1;
    n -= k;
    k--;
    res += div_ceil(n, k);
    cout << res << endl;
    return 0;
}


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

int main() {
  int N, M, a, b, i;
  cin >> N >> M;
  vector<int> road(N);
  
  for(i=0; i<M; i++){
    cin >> a >> b;
    road.at(a-1)++;
    road.at(b-1)++;
  }
  
  for(i=0; i<N; i++){
    cout << road.at(i) <<endl;
  }
}

Measured memory_bytes: 256
gets.to_i
monsters = gets.split.map(&:to_i)
braves = gets.split.map(&:to_i)

original = monsters.inject(:+)

braves.each_with_index do |n, i|
  diff = monsters[i] - n

  if diff < 0
    monsters[i] = 0
    diff2 = monsters[i+1] + diff
    diff2 < 0 ? monsters[i+1] = 0 : monsters[i+1] += diff
  else
    monsters[i] -= n
  end
end

puts original - monsters.inject(:+)

Measured memory_bytes: 15500
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int memo[1024][1024];
int calc(int l, int r, const vector<pair<int,int>> &nodes) {
    if(memo[l][r] >= 0) return memo[l][r];
    if(l+1 == r) return 0;
    pair<int,int> root(min(nodes[l].first, nodes[r-1].first), min(nodes[l].second, nodes[r-1].second));
    memo[l][r] = 10000 * 10000 * 2;
    for(int m = l+1; m < r; ++m) {
        const int d = nodes[m-1].second - root.second + nodes[m].first - root.first;
        memo[l][r] = min(memo[l][r], calc(l, m, nodes) + calc(m, r, nodes) + d);
    }
    return memo[l][r];
}

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;

    vector<pair<int,int>> nodes(N);
    for(int i = 0; i < N; ++i) {
        cin >> nodes[i].first >> nodes[i].second;
    }
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= N; ++j) {
            memo[i][j] = -1;
        }
    }
    cout << calc(0, N, nodes) << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 5364
/*Arnab's Code
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define vll vector<ll>
#define vii vector<int>
#define pll pair<ll,ll>
#define pii pair<int,int>/*Arnab's Code
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define vll vector<ll>
#define vii vector<int>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define take(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define takes(a,n,st) for(ll i=st;i<n+st;i++)cin>>a[i]
ll sum(ll a[],ll n,ll s){ for(ll i=0;i<n;i++)s+=a[i]; return s;}
#define mod 1000000009
ll power(ll x, ll y, ll p)  {  
    ll res = 1;  
    x = x % p;   
    if (x == 0) return 0;  
    while (y > 0){  
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}
char s[1017];
char t[1017];
int noc(ll a, ll n){
	ll i,tot;
	tot=0;
	for(i=0;i<n;i++){
		if(t[i]!=s[i+a])
			tot++;
	}
	return tot;
}
void solve(){
	ll n1,n2,mini,i,val;
	cin>>s;
	cin>>t;
	n1=strlen(s);
	n2=strlen(t);
	mini=n1;
	for(i=0;i<=(n1-n2);i++){
		val=noc(i,n2);
		if(val<mini)
			mini=val;
	}
	cout<<mini;
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ll t,T;
//	cin>>T;
	T=1;
	for(t=1;t<=T;t++){
//		cout<<"Case #"<<t<<": ";
		solve();
	}
	return 0;
}


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

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

	ll N;
	ll answer;
	int i,j;
	int tmp;
	int counter=0;
	double ave;
	vector<int> given;

	cin >> N;

	answer=((N-1)*N)/2;
	cout << answer << endl;

	return 0;
}



Measured memory_bytes: 256
#素のPythonでは通りませんでしたが，PyPyを使ったら通りました
N, K = map(int, input().split())
As = list(map(int, input().split()))

for i in range(K):
    table = [0 for _ in range(N*2)]
    # imos法 - メモ
    for j in range(N):
        ai = As[j]
        # 電球が照らす左端をメモ
        table[max((j-ai)*2-1, 0)] += 1
        # 電球が照らす右端をメモ
        table[min((j+ai)*2+1, N*2-1)] -= 1
    
    # imos法 - シミュレート
    for j in range(N*2):
        if j > 0:
            table[j] += table[j-1]
    
    # 答えになおす
    for j in range(N):
        As[j] = table[j*2]
    
    exit_condition = True
    for j in range(N):
        if As[j] != N:
            exit_condition = False
            break
    
    if exit_condition:
        print(*As)
        exit(0)
            

print(*As)

Measured memory_bytes: 190144
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int n, k;

int main() {
	cin >> n >> k;
	int ans = 1;
	for (int i = 0; i < n; ++i) {
		if (2 * ans > ans + k) ans += k;
		else ans *= 2;
	}
	cout << ans << endl;
	return 0;
}

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

long factor(long num){
  long temp = sqrt(num)+1;
  for(; temp>1; temp--){
    if(num%temp) continue;
    else break;
  }
  return temp;
}

int main() {
  long n,temp;
  cin >> n ;
  long ans;
  temp = factor(n);
  if(temp==1){
    ans = n-1;
  }else{
    ans = temp-1+n/temp-1;
  }
  
  cout<< ans <<endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
struct List {
	struct Node {
		int key;
		Node *next, *prev;
	};
	Node *top;
	void print_list() {
		for (Node *z = top->next; z != top; z = z->next) {
			if (z != top->next)putchar(' ');
			printf("%d", z->key);
		}
		puts("");
	}
	List() {
		top = (Node*)malloc(sizeof(Node));
		top->next = top->prev = top;
	}
	void insert(int x) {
		Node *node = (Node*)malloc(sizeof(Node));
		node->key = x;
		node->next = top->next;
		top->next->prev = node;
		top->next = node;
		node->prev = top;
	}
	void deleteFirst() {
		Node *d = top->next;
		top->next = top->next->next;
		top->next->prev = top;
		free(d);
	}
	void deleteLast() {
		Node *d = top->prev;
		top->prev = top->prev->prev;
		top->prev->next = top;
		free(d);
	}
	void Delete(int x) {
		Node *z;
		for (z = top->next; z != top&&z->key != x; z = z->next);
		if (z != top&&z->key == x) {
			z->prev->next = z->next;
			z->next->prev = z->prev;
			free(z);
		}
	}


};
signed main() {

	List ls;
	int n; cin >> n;
	char order[20];
	int x;
	rep(i, 0, n) {
		scanf("%s", order);
		if (order[0] == 'i') {
			scanf("%d", &x);
			ls.insert(x);
		}
		else if (strcmp(order, "delete") == 0) {
			scanf("%d", &x);
			ls.Delete(x);
		}
		else if (order[6] == 'F')ls.deleteFirst();
		else ls.deleteLast();
	}
	ls.print_list();
	return 0;
}

Measured memory_bytes: 34392
#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
int main(){
    int n;
    cin >> n;
    long long int a[n];
    cpp_int ans=1;
    int zero=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i]==0)zero++;
    }
    if(zero>0){
        cout << 0 << endl;
        return 0;
    }
    else{
    for(int i=0;i<n;i++){
        ans *= a[i];
        if(ans>1000000000000000000){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    }
}

Measured memory_bytes: 4428
#include <stdio.h>

int main(void)
{
  int n;
  int x[4];
  int i = 0;
  
  while((x[i++] = getchar()) != EOF)
    ;
  
  if (x[0] == x[1] || x[1] == x[2] || x[2] == x[3])
    puts("Bad");
  else
    puts("Good");
  
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cmath>
#define F first
#define S second
using namespace std;
typedef pair<int, int> P;
int x, y;
vector<P> v[5];
P s, g;
int dp[5][2048];

int dist(P p1, P p2){
  return abs(p1.F - p2.F) + abs(p1.S - p2.S);
}

int last;

int solve(int i, int j, P p){
  if(i == last) return dp[i][j] = dist(p, g);
  if(dp[i][j] != -1) return dp[i][j];
  int res = 1 << 28;
  int t = (i + 1) % 5;
  for(int k = 0;k < v[t].size(); k++) res = min(res, solve(t, k, v[t][k]) + dist(p, v[t][k]));
  return dp[i][j] = res;
}

int main(void){
  for( ; ; ){
    cin >> x >> y;
    if(!x && !y) break;
    
    for(int i = 0;i < 5; i++) v[i].clear();

    for(int i = 0;i < y; i++){
      for(int j = 0;j < x; j++){
	char m;
	cin >> m;
	int t = m - '1';
	if(0 <= t && t < 5) v[t].push_back(P(j, i));
	else if(m == 'S') s = P(j, i);
	else if(m == 'G') g = P(j, i);
      }
    }

    int num = 1 << 28, type;
    for(int i = 0;i < 5; i++){
      last = (i + 4) % 5;
      memset(dp, -1, sizeof(dp));
      int t = solve(i, 0, s);
      if(t < num){
	num = t;
	type = i;
      }
    }

    if(num == 1 << 28) cout << "NA" << endl;
    else cout << type + 1 << " " << num << endl;
  }
}


Measured memory_bytes: 1292
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
signed char dp[16][16][10][1<<16];
template<typename T1,typename T2>
void chmax(T1 &a,T2 b){
  if(a<b) a=b;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n;
  cin>>n;
  using P = pair<Int, Int>;
  vector<P> v;
  for(Int i=0;i<n;i++){
    Int x,y;
    cin>>x>>y;
    v.emplace_back(x,y);
  }
  vector<vector<P> > r(n,vector<P>(n)); 
  for(Int i=0;i<n;i++){
    for(Int j=i+1;j<n;j++){
      if(v[i].first==v[j].first){
	r[i][j]=P(0,1);
	continue;
      }
      if(v[i].second==v[j].second){
	r[i][j]=P(1,0);
	continue;
      }
      Int dx=v[i].first-v[j].first;
       Int dy=v[i].second-v[j].second;
       if(dx<0){
	 dx*=-1;
	 dy*=-1;
       }
       Int k=__gcd(dx,abs(dy));
       dx/=k;dy/=k;
       r[i][j]=P(dx,dy);
       //cout<<i<<" "<<j<<":"<<dx<<" "<<dy<<endl;
     }
   }
  memset(dp,-1,sizeof(dp));
  //dp[0][0][0][0]=0;
  for(Int i=0;i<n;i++){
    for(Int j=i+1;j<n;j++){
      dp[i][j][1][(1<<i)|(1<<j)]=0;
    }
  }
  Int ans=0;
  for(Int b=0;b<(1<<n);b++){
    for(Int i=0;i<n;i++){
      for(Int j=i+1;j<n;j++){
	for(Int k=0;k<=n/2;k++){
	  if(dp[i][j][k][b]<0) continue;
	  //cout<<i<<" "<<j<<" "<<k<<" "<<b<<":"<<dp[i][j][k][b]<<endl;
	  for(Int s=0;s<n;s++){
	    for(Int t=s+1;t<n;t++){
	      if((b>>s)&1) continue;
	      if((b>>t)&1) continue;
	      Int nb=b|(1<<s)|(1<<t);
	      if(r[i][j]==r[s][t]){
		chmax(dp[s][t][k+1][nb],dp[i][j][k][b]+k);
		chmax(ans,dp[s][t][k+1][nb]);
	      }else{
		chmax(dp[s][t][1][nb],dp[i][j][k][b]);
		chmax(ans,dp[s][t][1][nb]);
	      }
	    }
	  }
	}
      }
    }
  }  
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 167040
using System;
using System.Linq;

namespace ConsoleApp1 {
    public class Class1 {
        static void Main(string[] args) {
            int[] data = Console.ReadLine().Trim().Split(' ').Select(_ => int.Parse(_)).ToArray();
            int[] nums = Console.ReadLine().Trim().Split(' ').Select(_ => int.Parse(_)).ToArray();
            int ans = data[0] - nums.Sum();
            
            if(ans < 0) {
                Console.Write("-1");
            } else {
                Console.Write(ans);
            }
        }
    }
}

Measured memory_bytes: 29232
#!/usr/bin/env python3
# -*- coding utf-8 -*-

s = input()
lists = [c for c in s]
lists_rev = [i for i in lists[::-1]]

ans = 0 
length = len(lists)
if(length%2 == 0): 
    for i in range(length//2):
        if lists[i] != lists_rev[i]:
            ans += 1
else:
    for i in range((length-1)//2 + 1): 
        if lists[i] != lists_rev[i]:
            ans += 1

print(ans)


Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

use std::collections::HashMap;

fn main() {
    let n: usize = read();
    let mut map: HashMap<String, i64> = HashMap::new();
    for _ in 0..n {
        let si: String = read();
        let current = map.entry(si).or_insert(0);
        *current += 1;
    }
    let m: usize = read();
    for _ in 0..m {
        let si: String = read();
        let current = map.entry(si).or_insert(0);
        *current -= 1;
    }
    let mut ans = 0;

    for i in map {
        if i.1 > ans {
            ans = i.1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <algorithm>

int main( void ) {
    int N;
    std::cin >> N;

    // ただし便宜的に色が9色あることにする。
    // 最後の色は、実は色ではなくて、「好きな色を使える」ことなので注意。
    std::vector<bool> color_used = std::vector<bool>(8, false);  // 8色あって、初期値はfalseです。と言う指定

    // 自由な色を使って良いメンバーが何人いるか
    // 基本的に、みんな自由な色を使えることにしてしまう。
    // しかし、「使わなきゃいけない色」が見つかったら、ここから減らす。
    int free_color_members = N;

    // 入力しながら色を振り分けていく
    for( size_t i = 0; i < N; ++i ) {
        int rate;
        std::cin >> rate;

        // よくみるとレートの変化するところは400区切りだから、400で割って割り振ってもOK
        if( rate < 3200 ) {
            color_used[ rate / 400 ] = true;
            free_color_members -= 1;
        }
    }

    // 何種類の色が、決め打ちで使用済みなのか調べる
    int used_colors = 0;
    for( size_t i = 0; i < 8; ++i ) {
        if( color_used[ i ] > 0 ) {
            used_colors += 1;
        }
    }

    // 少なくとも一人のユーザがこの問題ではいることを考えると
    // 「決め打ちの色が1つもない」のであれば
    // 「自由な色の人が何か1つ決め打ちの色をとる」ようになるということ
    // なので自由な色を使える人の数を1つ減らして、used_colorを1にすることで問題を帰着できる。
    if( used_colors == 0 ) {
        free_color_members -= 1;
        used_colors = 1;
    }

    std::cout << used_colors << " " << used_colors + free_color_members << std::endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args) {
    Scanner reader= new Scanner(System.in);
    int n=reader.nextInt();
    int m=reader.nextInt();
    int a=0;
    for(int i=0;i<m;i++)
    {
      a+=reader.nextInt();
    }
    if(n-a>=0)
    {
      System.out.println(n-a);
    }else
    {
      System.out.println("-1");
    }




  }
}

Measured memory_bytes: 46368