akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

int comp(const void *c1, const void *c2)
{
    int tmp1 = *(int *)c1;
    int tmp2 = *(int *)c2;

    if (tmp1 < tmp2)
        return 1;
    if (tmp1 == tmp2)
        return 0;
    if (tmp1 > tmp2)
        return -1;
}

int main(void)
{
    int N, H, i, saidai=0, a_max=0, count, seieki;
    int b[100000], a[100000];

    scanf("%d %d", &N, &H);
    for (i = 0; i < N; i++){
        scanf("%d %d", &a[i], &b[i]);
    }

    /*まず、aの最大値考えよう。*/
    for (i = 0; i < N; i++){
        if(a[i] > a_max){
            a_max = a[i];
            saidai = i;
        }
    }

    /*b順にソートしよう。。。？*/
    qsort(b, N, sizeof(int), comp);

    seieki = 0;
    for (i = 1; i < N; i++){
        if(a[i]>=b[i]){
            seieki = i;
            break;
        }
    }

    count = 0;
    while (H > 0){
        if(count>=N){
            H -= a_max;
        } else {
            if(a_max < b[count]){
                H -= b[count];
            } else {
                H -= a_max;
            }
        }

        count++;
    }

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

    return 0;
}

Measured memory_bytes: 1276
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<stack>
#include<cstdlib>
#include<sstream>
#include<ctime>
using namespace std;
int n,m,a[200005],b[200005]; 
bool v[200005];
void qst(int lt,int rt){
	if(lt>rt) return;
	int i=lt,j=rt,T=a[rand()%(rt-lt+1)+lt];
	while(i<=j)
	{
		while(a[i]<T) i++;
		while(a[j]>T) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++;j--;
		}
	}
	qst(lt,j);
	qst(i,rt);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	qst(1,n);
	for(int i=1;i<=m;i++){
		int t=lower_bound(a+1,a+n+1,b[i])-a;
		while(v[t]) t++;
		if(t>=n+1||a[t]!=b[i]){
			cout<<"NO"<<endl;
			return 0;	
		} else {
			v[t]=1;
		}
	}
	cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int         long long   
#define double      long double
#define endl        "\n"
#define pb          push_back
#define PI          3.1415926535897932384626433832795l
#define F           first
#define S           second
#define mp          make_pair
#define f(i,n)      for(int i=0;i<n;i++)
#define fastio      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)      (v).begin(),(v).end()
#define rall(v)     (v).rbegin(),(v).rend()
#define gcd(a,b)    __gcd((a),(b))

typedef pair<int,int> pii;
typedef vector<int> vi;

signed main() 
{
    fastio;
    int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int n;
    cin>>n;
    cout<<a[n-1]<<endl;
}

Measured memory_bytes: 256
/*
[nikkei2019-qual] B - Touitsu
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

int N;
string A, B, C;

ll solve() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int cnt = 0;
        if (A[i] != B[i]) cnt++;
        if (B[i] != C[i]) cnt++;
        if (C[i] != A[i]) cnt++;
        ans += max(0, cnt - 1);
    }

    return ans;
}

int main() {
    cin >> N;
    cin >> A;
    cin >> B;
    cin >> C;

    cout << solve() << endl;

    return 0;
}


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


int main(){
    int n,m ;
    cin >> n >> m ;
    vector<pair<int,int> > a(m) ;
    for (size_t i = 0; i < m; i++)
    {
        cin >> a.at(i).first >> a.at(i).second ;
    }
    int copy = 0 ;   
    for (size_t i = 0; i < 1000; i++)
    {
        copy = i ;
        if (n == 2)
        {
            if (i < 10)
            {
                continue ;
            }
            
        }
        if (n == 3)
        {
            if (i < 100)
            {
                continue ;
            }
            
        }
        vector<int> num(n) ;
        for (size_t j = 0; j < n; j++)
        {
            if (j == 0)
            {
                num.at(n-1) = copy % 10 ;
            }else
            {
                copy /= 10 ;
                num.at(n-1-j) = copy % 10 ;
            }
            
            
        }
        //cout << num.at(0) << num.at(1) << num.at(2) << endl ;
        bool ans = true ;
        for (size_t j = 0; j < m; j++)
        {
            int k = a.at(j).first -1 ;

            if (num.at(k) != a.at(j).second)
            {
                ans = false ;
            }
            
        }
        if (ans == true)
        {
            cout << i << endl ;
            return 0 ;
        }
        ans = true ;
        
        
        
    }
    cout << -1 << endl ;
}    

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>
#include <string>
#include <complex>
using namespace std;

#define INT_max 2147483647


typedef long long ll;
typedef long double ld;


int mod = 1e9+7;

vector<ll> num;



ll repow(ll x,ll m){
	if(m == 1) return x;
	if(m % 2){
		return (x*repow(x,m-1)) % mod;
	}
	else{
		return repow((x*x)%mod,m/2)%mod;
	}
}


int main(){
	int N;
	string S;
	cin>>N>>S;
	ll ans = 0;
	vector<int> g;
	vector<int> r;
	for(int i = 0;i < N;i++){
		if(S[i] == 'R') r.push_back(i);
		if(S[i] == 'G') g.push_back(i);
	}
	ll b = N - (int)r.size() - (int)g.size();
	for(int i = 0;i < (int)r.size();i++){
		for(int j = 0;j < (int)g.size();j++){
			int min_ = min(r[i],g[j]);
			int max_ = max(r[i],g[j]);
			int k1 = (min_ + max_) % 2 ? -1 : (min_+max_)/2;
			int k2 = (2*min_-max_);
			int k3 = (2*max_-min_);
			ll t = 0;
			if(k1 != -1 && S[k1] == 'B') t++;
			if(k2 >= 0 && k2 < min_ && S[k2] == 'B') t++;
			if(k3 > max_ && k3 < N && S[k3] == 'B') t++;
			ans += b-t; 
		}
	}
	cout<<ans<<endl;
	return 0;
}




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

int as[100000];

int main(){
  int N,M;
  std::cin>>N>>M;
  int odd=0;
  for(int i=0;i<M;i++){
    std::cin>>as[i];
    if(as[i]%2){
      std::swap(as[i],as[odd++]);
    }
  }
  if(odd>2){
    std::cout<<"Impossible"<<std::endl;
    return 0;
  }
  
  std::vector<int> bs;
  if(M==1){
    bs.push_back(1);
    if(as[0]>1){
      bs.push_back(as[0]-1);
    }
  }else{
    std::swap(as[1],as[M-1]);
  
    bs.push_back(as[0]+1);
    for(int i=1;i<M-1;i++){
      bs.push_back(as[i]);
    }
    if(as[M-1]>1){
      bs.push_back(as[M-1]-1);
    }
  }
  for(int i=0;i<M;i++){
    if(i>0) std::cout<<" ";
    std::cout<<as[i];
  }
  std::cout<<std::endl;
  std::cout<<bs.size()<<std::endl;
  for(int i=0;i<bs.size();i++){
    if(i>0) std::cout<<" ";
    std::cout<<bs[i];
  }
  std::cout<<std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int num_500, num_100, num_50, total,count=0;
	scanf("%d %d %d %d", &num_500, &num_100, &num_50, &total);
	for (int i = (num_500>total/500)?(total/500):num_500; i >= 0; i--) {
		for (int j = num_100; j >= 0; j--) {
			for (int k = num_50; k >= 0; k--) {
				int sum = 500 * i + 100 * j + 50 * k;
				if (sum == total) {
					count++;
				}
			}
		}
	}
	printf("%d", count);
}

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

int main() {
  int N, i;
  long long ans, a, b;
  cin >> N;
  ans = 0;
  a = 2;
  b = 1;
  if(N == 1) cout << 1 << endl;
  else{
    for(i=1;i<N;i++){
      ans = a + b;
      a = b;
      b = ans;          
    }
    cout << ans << endl;
  }  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PI 3.141592653589793
ld angl[110];
ll x[110], y[110];
pair<ll, ll> mn;
ll cross(int a, int b, ll X, ll Y)
{
	return (x[a]-X)*(y[b]-Y) - (x[b]-X)*(y[a]-Y);
}
int n;
bool op(int a, int b)
{
	if (cross(a, b, mn.first, mn.second) == 0)
	{
		return x[a] > x[b];
	}
	return cross(a, b, mn.first, mn.second) < 0;
}
int points[110];
int main()
{
	scanf("%d", &n);
	if (n == 2)
	{
		printf("0.5 0.5\n");
		return 0;
	}
	mn = { 999999999, 999999999 };
	for (int i = 0; i < n; i++)
	{
		scanf("%lld%lld", &x[i], &y[i]);
		mn = min(mn, make_pair(x[i], y[i]));
		points[i] = i;
	}
	sort(points, points+n, op);
	vector<int> s;
	for (int i = 0; i < n; i++)
	{
		int a = points[i];
		mn = make_pair(x[a], y[a]);
		while (s.size() > 1)
		{
			if (op(s[s.size()-1], s[s.size()-2])) s.pop_back();
			else break;
		}
		s.push_back(a);
	}
	for (int i = 0; i < s.size(); i++)
	{
		int a = s[i];
		int pre = i-1;
		pre += s.size();
		pre %= s.size();
		int next = i+1;
		next %= s.size();
		pre = s[pre];
		next = s[next];
		ll dot = (x[next]-x[pre])*(x[a]-x[pre]) + (y[next]-y[pre])*(y[a]-y[pre]);
		ll cor = cross(next, a, x[pre], y[pre]);
		ld angle = atan2(cor, dot) * (180.0/PI);

		dot = (x[pre]-x[next])*(x[a]-x[next]) + (y[pre]-y[next])*(y[a]-y[next]);
		cor = cross(pre, a, x[next], y[next]);
		angle = abs(angle);
		ld angle2 = atan2(cor, dot) * (180.0/PI);
		angle2 = abs(angle2);
		ld angle3 = angle + angle2;
		//printf("%lld %lld %Lf %Lf %Lf\n", x[a], y[a], angle, angle2, angle3);
		angl[a] = angle3;
	}
	for (int i = 0; i < n; i++)
	{
		printf("%.8Lf\n", angl[i]/360);
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int N;
int t, x, y;
int main(){
  cin >> N;
  int timeD=0;
  int xD=0;
  int yD=0;
  bool flag =true;
  for(int i=0; i<N; i++){
    cin >> t >> x >> y;
    timeD = abs(timeD - t);
    xD = abs(xD - x);
    yD = abs(yD -y);
    if ( (timeD < xD + yD) || ((timeD > xD +yD) && (timeD - xD -yD)%2 == 1)){
      flag = false;
      break;
    }
    timeD =t;
    xD = x;
    yD =y;
  }
  if (flag) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
//#define i_7 (long long)(1e9+7)
#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int a, b, c, d;
  cin>>a>>b>>c>>d;
  int x = c - a;
  int y = d - b;
  vector<vector<long long>> dp(x + 1, vector<long long>(y + 1, 0));
  REP(i, x + 1){
    REP(j, y + 1){
      if(i == 0 && j == 0){
        dp[i][j] = 1;
        continue;
      }
      if(j - 1 >= 0){
        dp[i][j] += dp[i][j-1] * (a + i);
        dp[i][j] = mod(dp[i][j]);
      }
      if(i - 1 >= 0){
        dp[i][j] += dp[i-1][j] * (b + j);
        dp[i][j] = mod(dp[i][j]);
      }
      if(i - 1 >= 0 && j - 1 >= 0){
        dp[i][j] -= dp[i-1][j-1] * (a + i - 1) * (b + j - 1);
        dp[i][j] = mod(dp[i][j]);
      }
    }
  }
  long long ans = dp[x][y];
  cout << ans << endl;   
  return 0;
}

Measured memory_bytes: 73632
import java.util.*;

public class  Main {
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int N,sum = 0;
    ArrayList<Integer> L = new ArrayList<Integer>();
    N = s.nextInt();
    for(int i = 0; i < N ;i++){
      L.add(s.nextInt());
      sum += L.get(i);
    }
    Collections.sort(L);
    sum -= L.get(N - 1);
    if(L.get(N - 1) < sum)
      System.out.println("Yes");
    else
      System.out.println("No");
  }
}

Measured memory_bytes: 22740
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

#define DEBUG 0
#define REP(i, n) for (int i = 0; i < (n); i++) 
typedef long long ll;
typedef pair<int,int> pint;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;


int main() { 
    int n;
    cin >> n;
    int a[n];
    int jun[n];
    REP(i,n)
    {
        cin >> a[i];
        --a[i];
        jun[a[i]] = i+1;
    }
    REP(i,n)
    {
        cout << jun[i];
        if(i != n-1)
        {
            cout << " ";
        }
    }
    cout << endl;
 
    return 0;

}

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

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

    vector<int> ct_set(2);
    vector<vector<int>> ct_list(N); 
    for(int i = 0; i < N; i++){
        int c, t;
        cin >> c >> t;
        ct_set[0] = c;
        ct_set[1] = t;
        ct_list[i] = ct_set;
    }

    int min_cost = 1001;
    for(int i=0; i<N; i++){
        if(ct_list[i][0] < min_cost && ct_list[i][1] <= T){
            min_cost = ct_list[i][0];
        }
    }

    if(min_cost > 1000) cout << "TLE";
    else cout << min_cost;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 現在位置から(x, y)離れた(ただしx, y >=0)座標にちょうどt秒で着く <=> t = x + y + 2k (k = 0, 1,...)
        // <=> (t - (x + y)) % 2 = 0 && t >= x + y
        int currX = 0;
        int currY = 0;
        int currT = 0;
        
        for (int i = 0; i < n; i++) {
            int nextT = sc.nextInt();
            int nextX = sc.nextInt();
            int nextY = sc.nextInt();
            int spanT = nextT - currT;
            int spanX = Math.abs(nextX - currX);
            int spanY = Math.abs(nextY - currY);
//            U.println("sT: " + spanT + ", sX: " + spanX + ", sY: " + spanY);
            if ((spanT - spanX - spanY) % 2 != 0 || spanT < spanX + spanY) {
                System.out.println("No");
                return;
            }
            currT = nextT;
            currX = nextX;
            currY = nextY;
        }
        System.out.println("Yes");
    }
}

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

signed main() {
	int n; string s; int k; cin >> n >> s >> k;
	k--;
	for (int i = 0; i < n; i++) {
		if (s[i] != s[k])s[i] = '*';
	}

	cout << s << endl;
}

Measured memory_bytes: 3568
#include <algorithm>
#include <queue>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <ios>     // std::left, std::right
#include <iomanip> 
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;

int main(){
    vector<int> ABC(3,0);
    cin>>ABC[0]>>ABC[1]>>ABC[2];
    sort(ABC.begin(),ABC.end());
    cout << ABC[0] +ABC[1] + 10 * ABC[2];
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

ll n,m;
vector<lvector> V;

void dfs(ll pos,lvector v) {
  if(v[n-1]>0) V.emplace_back(v);
  else {
    for(ll d=0;d+v[pos]<=m;++d) {
      v[pos+1]=v[pos]+d;
      dfs(pos+1,v);
    }
  }
  return;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll q,a,b,c,d;cin>>n>>m>>q;
  vector<lvector> Q(q);
  rep(i,q) {
    cin>>a>>b>>c>>d;a--,b--;
    Q[i]=lvector{a,b,c,d};
  }
  lvector v_(n,0);v_[0]=1;
  dfs(0,v_);
  ll ans=0,ans_=0;
  for(lvector e:V) {
    ans_=0;
    for(lvector f:Q) if(e[f[1]]-e[f[0]]==f[2]) ans_+=f[3];
    ans=max(ans,ans_);
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 9000
def main():
    n, y = map(int,input().split())
    for a in range(n+1):
        for b in range(n+1):
            c = n - a - b
            if c >= 0:
                if 10000 * a + 5000 * b + 1000 * c == y:
                    print(a, b, c)
                    exit()
                else:
                    pass
            else:
                break
    print("-1 -1 -1")



if __name__ == "__main__":
    main()

Measured memory_bytes: 38896
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String dateStr = sc.nextLine();
		SimpleDateFormat sdFormat = new SimpleDateFormat("yyyy/MM/dd");
		Date inputDate = null;
		Date lastHeisei = null;
		try {
			inputDate = sdFormat.parse(dateStr);
			lastHeisei = sdFormat.parse("2019/4/30");
		} catch (ParseException e) {

		}
		if (inputDate.after(lastHeisei)) {
			System.out.println("TBD");
		} else {
			System.out.println("Heisei");
		}
		sc.close();
	}
}

Measured memory_bytes: 22352
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;

int a[12][13];
int n,m,x;

int solve(int c,vector<int> b){
  int num=INF;
  if(c==n) return num;
  num=min(num,solve(c+1,b));
  rep(i,m+1){
    b[i]+=a[c][i];
  }
  repi(i,1,m+1){
    if(b[i]<x) break;
    if(i==m){
      num=min(b[0],num);
      return num;
    }
  }
  return min(num,solve(c+1,b));
  
}

signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
 
  cin>>n>>m>>x;
  rep(i,n){
    rep(j,m+1){
      cin>>a[i][j];
    }
  }
  vector<int> now(13);
  rep(i,13){
    now[i]=0;
  }
  int ans=solve(0,now);
  if(ans==INF) cout<<-1<<endl;
  else cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr ll INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

struct UnionFind{
    vector<long long> par,r;

    //はじめに全てが根であるとしておく
    UnionFind(long long N):par(N),r(N,1){iota(par.begin(),par.end(),0);}

    long long root(long long x){//根に当たるまで再帰で探す
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    long long deep(long long x,long long A){
        if(par[x] == x) return A;
        else{A++;return deep(par[x],A);}
    }

    bool same(long long x,long long y){//つながっているかどうか判定
        return par[x] == par[y];
    }

    long long size(long long x){ //根の大きさを判定する
        return r[root(x)];
    }

    void unite(long long x, long long y){//根が同じでなかったらつなげる
        x = root(x), y = root(y);
        if(x == y) return;
        if(r[x] < r[y]) swap(x,y); //値を小さいほうを根にする
        r[x] += r[y];
        par[y] = x;
        return;
    }
};

vector<long long> G[100100];
long long num[100100] = {};
ll b = 0,w = 0;
bool used[100100] = {};

void dfs(long long X,char C){
    if(used[X]) return;
    else used[X] = 1;
    if(C == 'b'){b++;C = 'w';}
    else{w++;C = 'b';}
    REP(i,G[X].size()){
        dfs(G[X][i],C);
    }
}

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    long long N,M;cin >> N >> M;
    UnionFind UF(2*N);
    long long A,B;
    REP(i,M){
        cin >> A >> B;A--;B--;
        UF.unite(A,B + N);
        UF.unite(A + N,B);
        G[A].pb(B);G[B].pb(A);
    }
    long long sum = 0,sq = 0;
    REP(i,N) sum += i;


    REP(i,N){
        if(UF.same(i,i + N)){
            cout << sum - M << endl;
            return 0;
        }
    }
    dfs(0,b);
    sq = b*w;
    cout << sq - M << endl;
}

Measured memory_bytes: 9856
import java.util.*;

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

        if (s.indexOf('7') != -1)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int n, m;
    cin >> n >> m;
    int sum = 0;
    rep(i, m)
    {
        int a;
        cin >> a;
        sum += a;
    }

    if (sum > n) {
        cout << -1 << endl;
    } else {
        cout << n - sum << endl;
    }
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int arr[1000005][4];
int dp[1000005][4];
int solve(int i,int j,int n)
{
    if(i>=n) return 0;
    int ans1=0,ans2=0,ans3=0;
    if(dp[i][j]!=0) return dp[i][j];
    ans1=arr[i][j]+solve(i+1,(j+1)%3,n);
    ans2=arr[i][j]+solve(i+1,(j+2)%3,n);
    return dp[i][j]=max(ans1,ans2);
}
main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>arr[i][j];
        }
    }
    cout<<max(solve(0,0,n),max(solve(0,1,n),solve(0,2,n)));
}


Measured memory_bytes: 13696
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>

using namespace std;

typedef long long ll;

bool check(ll n, ll k) {
  if (k == 1) return false;
  while (n % k == 0) n /= k;
  return n % k == 1;
}

int main()
{
  ll n;
  cin >> n;

  set<ll> s;

  for (ll k1 = 1; k1 * k1 <= n; ++k1) {
    if (check(n, k1)) s.insert(k1);
    ll k2 = n / k1;
    if (check(n, k2)) s.insert(k2);
    k2 = (n - 1) / k1;
    if (check(n, k2)) s.insert(k2);
  }

  cout << s.size() << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main()
{
    int n,m;
    cin >>n >>m;

    vector<int> a(m);
    rep(i,m)
    {
        int b;
        cin >>a[i] >>b;
    }

    sort(all(a),greater<int>());

    int ans=0;
    rep(i,m-1) ans += max(0,n-a[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3128
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18
#
S = input()

print("ABC" if S == "ARC" else "ARC")

Measured memory_bytes: 65148
n,m = map(int,input().split())
bec1_list = [list(map(int,input().split())) for i in range(n)]
bec2_list = [list(map(int,input().split())) for i in range(m)]

for i in range(n):
	num = 0
	for j in range(m):
		num += bec1_list[i][j] * bec2_list[j][0]
	print(str(num))


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

int main(int argc, char*argv[]) {
  int n, m ,c;
  cin >> n >> m >> c;
  vector<int> b;
  for(int i=0; i<m ;i++ ) {
    int tmp;
    cin >> tmp;
    b.push_back(tmp);
  }
  int ans = 0;
  for(int i=0; i<n; i++) {
    int count = 0;
    for(int j=0; j<m; j++) {
      int a;
      cin >> a;
      count += a * b[j];
    }
    if (count + c > 0) {
      ans ++;
    }
  }
  cout << ans << endl;
  return 0;
}

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


long long a[20][20], w[1<<16] = {0};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  for (int S = 0; S < (1<<n); ++S) {
    for (int i = 0; i < n; ++i) if (S&(1<<i)) {
      for (int j = 0; j < i; ++j) if (S&(1<<j)) {
        w[S] += a[i][j];
      }
    }
    w[S] = max(w[S], 0ll);
  }
  for (int S = 0; S < (1<<n); ++S) {
    for (int SS = S; SS; SS = S&(SS - 1)) {
      w[S] = max(w[S], w[SS] + w[SS^S]);
    }
  }
  cout << w[(1<<n) - 1] << '\n';
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int n,m,k,w,r,a[105];
int main()
{
	int a,b;
	cin>>a>>b;
	if((a+b)%3==0 ||a%3==0 || b%3==0)cout<<"Possible" ;
	else
	cout<<"Impossible";
	cout<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int w;
    cin >> w;
    for (int i = 0; i < s.size(); i += w)
    {
        cout << s[i];
    }
    cout << endl;
}


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

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 CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = ((tmp & ma0) ^ ma0) ? 68 - __builtin_ctzll((tmp & ma0) ^ ma0) : 0;
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (64 - dig >> 3);
	while ((ct = *ci++) >= '0') tmp = tmp * 10 + ct - '0';
	return tmp;
}

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


	int A[200000], B[200000];
	int N = getint();
	rep(i, N) {
		A[i] = getint();
		B[i] = getint();
	}

	nth_element(A, A + N / 2, A + N);
	nth_element(B, B + N / 2, B + N);
	if (N % 2) {
		printf("%d\n", B[N / 2] - A[N / 2] + 1);
	}
	else {
		int a = *max_element(A, A + N / 2);
		int b = *max_element(B, B + N / 2);
		printf("%d\n", b + B[N / 2] - a - A[N / 2] + 1);
	}

	Would you please return 0;
}

Measured memory_bytes: 4908
N = int(input())
coords_list = tuple([(0, 0, 0)] + [tuple([int(elem) for elem in input().split(' ')]) for _ in range(N)])

for i in range(N):
    dt = coords_list[i + 1][0] - coords_list[i][0]
    diff = [abs(coords_list[i + 1][1] - coords_list[i][1]), 
            abs(coords_list[i + 1][2] - coords_list[i][2])]

    if sum(diff) > dt:
        print("No")
        exit(0)
    elif (diff[0] + diff[1]) % 2 == dt % 2:
        continue
    else: # diff == 0
        print("No")
        exit(0)
else:
    print("Yes")


Measured memory_bytes: 18088
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repin(a, n)  \
    vector<ll> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repins(a, n)     \
    vector<string> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repind(a, n)     \
    vector<double> a(n); \
    rep(i, n) { cin >> a[i]; }
#define in(a) \
    ll a;     \
    cin >> a;
#define ins(a) \
    string a;  \
    cin >> a;
#define ind(a) \
    double a;  \
    cin >> a;
template <class T>
inline void out(T a) {
    cout << a << endl;
}
inline void out(double a) { printf("%.10f\n", a); }
#define all(x)        (x).begin(), (x).end()
#define rep2(i, a, b) for (ll i = (a); i < (b); ++i)
#define yes           out("Yes");
#define no            out("No");

int main() {
    ins(a);
    if ('A' <= a[0] && a[0] <= 'Z') {
        out("A");
    } else {
        out("a");
    }
}

Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int Q=1<<18;
int las[Q],e[Q<<1],nn[Q<<1],inc;
void ins(int x,int y)
{
	e[++inc]=y;
	nn[inc]=las[x];
	las[x]=inc;
}
int sa[Q];int mx[Q],in[Q],out[Q],Time=0;
void MDF(int x)
{
	sa[in[x]]++,sa[out[x]+1]--;
}
int lx[Q],tr[Q];
int lt[Q],tm[Q];
void dfs(int x,int last)
{
	lx[x]=mx[last];
	mx[x]=max(x,mx[last]);
	if(mx[x]==last)lt[x]=x,tm[x]=x;
	else lt[x]=lt[last],tm[x]=max(tm[last],x);
	in[x]=++Time;
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(y==last)continue;
		dfs(y,x);
	}
	out[x]=Time;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1,0);
	for(int i=1;i<=n;i++)
		if(mx[i]!=i&&tm[i]>lx[mx[i]])MDF(lt[i]);
		else MDF(mx[i]);
	for(int i=1;i<=n;i++)
		sa[i]+=sa[i-1];
	for(int i=2;i<=n;i++)
		printf("%d ",sa[in[i]]-1);
	return 0;
}

Measured memory_bytes: 23552
#include<stdio.h>
int main(){
  long long n,m,c=0,i;
  scanf("%lld %lld",&n,&m);
  for(i=1;i<=77;i++){
    if(i%7<2)continue;
    if(i*9%11==m)c++;
  }
  c=n/11*c;//printf("%d\n",c);
  for(i=(n/11)*77;i<=n*7;i++){
    if(i%7<2)continue;
    if(i*9%11==m)c++;
  }//printf("%d %d\n",c,n*7-7);
  for(i=n*7-6;i<=n*7;i++){//printf("%d\n",i*9%11);
    if(i%7<2)continue;
    if(i*9%11==m)c--;
  }
  for(i=1;i<7;i++){
    if(i%7<2)continue;
    if(i*9%11==m)c--;
  }    
  printf("%lld\n",c);
  return 0;
}
  


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int N, A, B, C;
int l[10];
int ans = INF;
void def(int x, int y, int z, int q, int n) {
	if (n == N) {
		if (x == 0 || y == 0 || z == 0)return;
		else {
			int count = 0;
			count += abs(A - x) + abs(B - y) + abs(C - z) + 10 * ((N-3)- q);
			ans = min(ans, count);
		}
		return;
	}
    def(x, y, z, q + 1, n + 1);
    def(x + l[n], y, z, q, n + 1);
	def(x, y + l[n], z, q, n + 1);
	def(x, y, z + l[n], q, n + 1);
}


int main() {
	cin >> N >> A >> B >> C;
	for (int i = 0; i < N; ++i)cin >> l[i];
	def(0, 0, 0, 0,0);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999
vector<ll> num28;

int dfs(ll n,int p){
    if(n==1)return 0;
    if( p>=num28.size() )return -INF;
    
    int maxi = -INF;
    for(int i=0;;i++){
        maxi = max(maxi,i+dfs(n,p+1));
        if( n%num28[p]!=0 )break;
        n/=num28[p];
    }
    return maxi;
}

void make28(ll n){
    vector<ll> tmp;
    tmp.pb(2);
    tmp.pb(8);
    int tmp_size;
    int now = 1;
    while(tmp.back()<=n){
        tmp_size = tmp.size();
        for(int i=tmp_size-(1<<now);i<tmp_size;i++){
            tmp.pb( tmp[i]*10+2 );
            tmp.pb( tmp[i]*10+8 );
        }
        now++;
    }
    rep(i,tmp.size()){
        if(n%tmp[i]==0)num28.pb(tmp[i]);
    }
}


int main(){
    ll n;
    cin>>n;
    make28(n);
    int res = dfs(n,0);
    if(res<-999900000 || n==1)cout<<-1<<endl;
    else cout<<res<<endl;
}

Measured memory_bytes: 11228
class Problem
  attr_accessor :a, :b, :n, :m, :h, :w

  def initialize
    @a,@op,@b = gets.to_s.split
  end

  def solve
    if @op == "+"
      @a.to_i + @b.to_i
    else
      @a.to_i - @b.to_i
    end
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end


Measured memory_bytes: 14316
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int main()
{
    long long n,i,k,j,c=0,s;
    cin>>n;
    vector<long long>v;
    for(i=0;i<n;i++)
    {
        cin>>k;
        v.push_back(k);
    }
   // vector<long long>v;
   /* for(auto i:st)
    {
        v.push_back(i);
       // st.erase(i);
    }*/
    sort(v.begin(),v.end());
    s=v.size();
    for(i=0;i<s-2;i++)
    {
        for(j=i+1;j<s-1;j++)
        {
            for(k=j+1;k<s;k++)
            {
                if((v[i]+v[j]>v[k])&&(v[i]!=v[j]&&v[j]!=v[k]&&v[k]!=v[i]))
                {
                    c++;
                }
            }
        }
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 3616
def main():
    N = int(input())
    s = input()

    r, g, b = 0, 0, 0
    for i, c in enumerate(s, 1):
        if c == 'R':
            r += 1
        elif c == 'G':
            g += 1
        else:
            b += 1

    ans = r * g * b
    sub = 0
    for j in range(N):
        for i in range(j):
            if s[i] == s[j]:
                continue
            k = (j - i) + j
            if k >= N:
                continue
            if (s[i] == s[k]) or (s[j] == s[k]):
                continue
            sub += 1  # 相異なる3文字で(j-i)==(k-j)を満たしている数

    ans -= sub

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9068
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
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; }
typedef long long ll;
const ll MOD=1e+9+7;
struct mint{
  ll x;
  mint(ll x=0):x(x%MOD){}
  mint& operator+=(const mint a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x += MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=MOD;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a = pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }
  
  //for prime mod
  mint inv() const{
    return pow(MOD-2);
  }
  mint& operator/=(const mint a){
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};



template <typename X>
struct Node{
  int idx;
  
  Node() = default;

  Node(int idx) : idx(idx) {}
};
template <typename X>
struct Edge{
  int from;
  int to;
  X cost;
  
  Edge() = default;

  Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {}
};
template <typename X>
class Tree{
private:
  int n; // number of node
  vector<vector<Edge<X>>> edge; 

  vector<vector<int>> parent; // parent[i][j] := node followed parent at 2^j times from node[i]
  vector<vector<X>> depth; // depth[i][j] := depth of the node[j] when root is node[i]
  const int MAXLOGN = 20;
  
  mint dp[100010][2];
  
public:
  Tree() = default;

  Tree(int n) : n(n) {
    edge.resize(n);
  }

  Tree(int n, vector<int> a, vector<int> b) : n(n) {
    edge.resize(n);
    rep(i,n-1) {
      add_edge(a[i], b[i]);
      add_edge(b[i], a[i]);  // indirected edge
    }
  }

  Tree(int n, vector<int> a, vector<int> b, vector<X> c) : n(n) {
    edge.resize(n);
    rep(i,n-1) {
      add_edge(a[i], b[i], c[i]);
      add_edge(b[i], a[i], c[i]);  // indirected edge
    }
  }  

  void add_edge(int from, int to, X cost = 1) {
    edge[from].emplace_back(from, to, cost);
  }

  mint DFS(int v, int p, int color) {
    if(dp[v][color].x > 0) return dp[v][color];
    mint res(1);
    for(auto next: edge[v]) {
      int w = next.to;
      if(w == p) continue;
      if(color == 0) {
	res *= (DFS(w, v, 0) + DFS(w, v, 1));
      }
      else {
	res *= DFS(w, v, 0);
      }
    }
    return dp[v][color] = res;
  }
};

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

  Tree<int> tr(n, a, b);
  cout << (tr.DFS(0, -1, 0) + tr.DFS(0, -1, 1)).x  << "\n";
  
  return 0;
}


Measured memory_bytes: 23408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int c = 0;
    char prev = s[0];
    rep (i, s.size()) {
        if (prev != s[i]) {
            c++;
        }
        prev = s[i];
    }
    c++;
    if (c < 4) {
        cout << n - 1 << endl;
    } else if ((n - c) + k * 2 > n - 1){
        cout << n - 1 << endl;
    } else {
        cout << (n - c) + k * 2 << endl;
    }
}

Measured memory_bytes: 512
// #include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

cat M;

struct state {
	int pos, s0, s1, mx0, mx1;

	bool operator<(const state & s) const {
		if(pos != s.pos) return pos < s.pos;
		if(s0 != s.s0) return s0 < s.s0;
		if(s1 != s.s1) return s1 < s.s1;
		if(mx0 != s.mx0) return mx0 < s.mx0;
		return mx1 < s.mx1;
	}
};

map<state, cat> St;

cat solve(int N, int K, int pos, int s0, int s1, int mx0, int mx1) {
	if(pos == N) return (mx0 == N && mx1 == N);
	if(mx0 < pos || mx1 < pos) return 0;
	auto it = St.find({pos, s0, s1, mx0, mx1});
	if(it != St.end()) return it->ss;
	// remove
	int mx0_nw = N, mx1_nw = N;
	if(pos%2 == 0) {
		if(2*s1-1 >= K) mx1_nw = pos + K - 2 * min(K/2, s0);
	}
	else {
		if(2*s0-1 >= K) mx0_nw = pos + K - 2 * min(K/2, s1);
	}
	cat ret1 = 0;
	ret1 = solve(N, K, pos+1, s0+(pos%2==0), s1+(pos%2==1), min(mx0, mx0_nw), min(mx1, mx1_nw));
	// don't remove
	cat ret2 = solve(N, K, pos+1, (pos%2==0)?0:s0, (pos%2==1)?0:s1, (pos%2==0)?N:mx0, (pos%2==1)?N:mx1);
	St[{pos, s0, s1, mx0, mx1}] = (ret1 + ret2) % M;
	return (ret1 + ret2) % M;
}

cat solve_1(int N, int K) {
	vector< vector<cat> > dp(N+1, vector<cat>(K+1, 0));
	dp[0][0] = 1;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j <= K; j++) dp[i+1][0] += dp[i][j];
		for(int j = 0; j < K; j++) dp[i+1][j+1] += dp[i][j];
		for(int j = 0; j <= K; j++) dp[i+1][j] %= M;
	}
	cat ret = 0;
	for(int i = 0; i <= K; i++) ret += dp[N][i];
	ret %= M;
	return ret;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, K;
	cin >> N >> K >> M;
	if(K%2 == 0 || K == 1) {
		if(K == 1) cout << solve_1(N, 2) << "\n";
		else cout << solve_1(N/2, K/2) * solve_1(N-N/2, K/2) % M << "\n";
		return 0;
	}
	cout << solve(N, K, 0, 0, 0, N, N) << "\n";
	// cerr << St.size() << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 66944
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,i,j,k,m,temp,sum=0,pen=0;
    cin >> n >> m;
    string st;
    unordered_map < long long , pair<string,long long> > a; 
    for(i=0;i<m;i++){
        cin >> temp >> st;
        if(a.find(temp)==a.end()){
            if(st=="WA") a.insert(make_pair(temp,make_pair(st,1)));
            else a.insert(make_pair(temp,make_pair(st,0)));
        }
        else{
            if(st=="WA"){
                if(a[temp].first=="WA") a[temp].second++;
            }
            else{
                a[temp].first= st;
            }
        }
    }
    for(auto it = a.begin();it!=a.end();it++){
        if((*it).second.first=="AC"){ sum++;
        pen+= (*it).second.second;
        }
    }
    cout << sum << " " << pen;
}

Measured memory_bytes: 10660
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

string s;

int make_int(int start){
  return (s[start]-'0')*100+(s[start+1]-'0')*10+(s[start+2]-'0');
}

int main(){
  cin >> s;
  ll ans = INF;
  REP(i,s.length()-2){
    if(abs(make_int(i)-753)<ans){
      ans = abs(make_int(i)-753);
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

const int maxn = 2e5 + 100;


ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

int n;
ll a[maxn];
ll cnt(ll x)
{
  ll res = 0;
  for(int i = 0 ; i < n ; i++)
  {
    if(a[i] < 0)
    {
      int lo = 0;
      int hi = n-1;
      int ans = n;
      while(lo <= hi)
      {
        int mid = (lo + hi) >> 1;
        if(a[mid] * a[i] <= x)
        {
          ans = mid;
          hi = mid - 1;
        }
        else
        {
          lo = mid + 1;
        }
      }
      res += n - ans;
    }

    else
    {
      int lo = 0;
      int hi = n-1;
      int ans = -1;
      while(lo <= hi)
      {
        int mid = (lo + hi) >> 1;
        if(a[mid] * a[i] <= x)
        {
          ans = mid;
          lo = mid + 1;
        }
        else
        {
          hi = mid - 1;
        }
      }
      res += ans + 1;
    }
    if(a[i] * a[i] <= x)
      res--;
  }
  res /= 2;
  return res;
}

int main()
{
  ios::sync_with_stdio(0);
  ll k;
  cin >> n >> k;

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

  sort(a, a + n);


  ll lo = -1e18;
  ll hi = 1e18;

  ll ans = 0;
  while(lo <= hi)
  {
    ll mid = (lo + hi) >> 1;

    if(cnt(mid) >= k)
    {
      ans = mid;
      hi = mid - 1;
    }
    else
    {
      lo = mid + 1;
    }
  }
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 1792