akhauriyash/Code-Regression huggingface dataset:
//https://atcoder.jp/contests/dp/tasks/dp_d
//https://atcoder.jp/contests/dp/tasks/dp_e

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << "  = " << x << endl
typedef long long int ll;
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)

#define dbg2(x, y)                                                       \
    {                                                                    \
        cout << #x << ": " << (x) << " , " << #y << ": " << (y) << endl; \
    }
#define fo(i, n) for (int i = 0; i < n; i++)
#define fok(i, k, n) for (int i = k; i < n; i++)
#define foA(i, A) for (auto i : A)
const int mxN=105;
ll val[mxN];
ll wt[mxN];

int knapsack1(int n,int w){
    ll ans;
    ll dp[n+1][w+1];//maximum value obtained by adding till weight w;
    fok(i,0, n+1){
        fok(j, 0,w+1){
            if(i==0 or j==0)dp[i][j]=0;
            else if(wt[i-1]>j)dp[i][j]=dp[i-1][j];//no way to include this element
            else {
                //each object can be indluded or not in the optimal solution
                dp[i][j]=max((dp[i-1][j-wt[i-1]]+val[i-1]), dp[i-1][j]);
            }
        }
    }
    //fo(i, n){fo(j, w+1)cout<<dp[i][j]<<" ";cout<<endl;}
    ans=dp[n][w];
    return ans;
}
int knapsack2(int n, int w){
    ll vl=0, ans=0;
    fo(i, n)vl+=val[i];
    ll dp[n+1][vl+1];//minimum weight required to get to value v
    fo(i,n+1)fo(j,vl+1){if(j==0)dp[i][j]=0;else dp[i][j]=INT_MAX;}
    fok(i,1,n+1){
        fok(j,1,vl+1){
            if(val[i-1]>j)dp[i][j]=dp[i-1][j];//no way to include this item
            else {
                dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]], dp[i-1][j]);
            }
        }
    }
    //fo(i, n+1){fo(j, vl+1)cout<<dp[i][j]<<" ";cout<<endl;}
    for(int j=vl;j>=0;j--){
        if(dp[n][j]<=w){ans=j;break;}
    }
    return ans;
}

int main(){
    fast;
    int n;
    ll w;
    cin>>n>>w;
    fo(i, n){
        cin>>wt[i]>>val[i];
    }
    cout<<knapsack2(n, w);
}

Measured memory_bytes: 79232
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Int
import qualified Data.IntMap                 as IM
import           Data.List
import qualified Data.Map                    as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

main = do
  [ss] <- readString
  let (n, s, e, w) = ('N' `elem` ss, 'S' `elem` ss, 'E' `elem` ss, 'W' `elem` ss)
   in if ((n && s) || (not n && not s)) && ((e && w) || not e && not w)
        then putStrLn "Yes"
        else putStrLn "No"


Measured memory_bytes: 508
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int n,i,d,s=0,res=0;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> d;
    res-=d*d;
    s+=d;
  }
  res+=s*s;
  res/=2;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a+b==15)
    {
        cout<<"+"<<endl;
    }
    else if(a*b==15)
    {
        cout<<"*"<<endl;
    }
    else{
        cout<<"x"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import Control.Arrow (second)
import qualified Data.Vector.Unboxed as V
import qualified Data.ByteString.Char8 as B

solve :: Int -> Int -> V.Vector Int -> Int
solve n k xs = (\t -> if null t then 0 else minimum t) $ map (\i -> dist (xs V.! i) (xs V.! (i+k-1))) [0..n-k] where
  dist x y =
    let
      l = max (-x) 0
      r = max y 0
    in
      l + r + min l r

main = do
  [n,k] <- map (fst . (\(Just x) -> x) . B.readInt) . B.words <$> B.getLine
  xs <- V.unfoldrN n (fmap (second B.tail) . B.readInt) <$> B.getLine
  print $ solve n k xs



Measured memory_bytes: 3964
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,&a[n]);
  cout<<a[n-1]-a[0]<<endl;
  return 0;
}


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

int main()
{
	int N;
	int a, x;
  
	cin >> N;
    x = N;
	for(int i=0;i<8;i++){
      a += x%10; 
      x /= 10;
	}
  if(N%a == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

}

Measured memory_bytes: 256
#include <stdio.h>

#define N 8
#define FREE 1
#define NOT_FREE -1

void putQueen(int);
void printBoard(void);

int Q[N][N];
int row[N],col[N],dpos[20],dneg[20];

int main() {
    int i,j,k,a,b;
    
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) Q[i][j] = 0;
    }
    
    scanf("%d",&k);
    
    for(i=0; i<k; i++) {
        scanf("%d%d",&a,&b);
        Q[a][b] = FREE;
    }
    
    for(i=0; i<N; i++) {
        row[i] = FREE;
        col[i] = FREE;
    }
    
    for(i=0; i<20; i++) {
        dpos[i] = FREE;
        dneg[i] = FREE;
    }
    
    putQueen(0);
    
    return 0;
}


void putQueen(int i) {
    int j;
    
    if(i==N) {
        printBoard();
        return;
    }
    
    for(j=0; j<N; j++) {
        if(col[j]==NOT_FREE ||
           dpos[i+j]==NOT_FREE ||
           dneg[i-j+N-1]==NOT_FREE) continue;

        row[i] = j;
        col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;

        putQueen(i+1);

        row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
    }
}

void printBoard() {
    int i,j;
    
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            if(Q[i][j]) {
                if(row[i]!=j) return;
            }
        }
    }
    
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            if(row[i]==j) printf("Q");
            else printf(".");
        }
        printf("\n");
    }
}

Measured memory_bytes: 572
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort()
C=list(map(int,input().split()))
C.sort()
from bisect import bisect_right
ret=0
Cb=[0]*(N+1)
for i in range(N):
  Cb[i]=N-bisect_right(C,B[i])
for i in range(N-1,-1,-1):
  Cb[i]+=Cb[i+1]
for a in A:
  bi=bisect_right(B,a)
  ret+=Cb[bi]
print(ret)

Measured memory_bytes: 23328
SA = gets.chomp.chars
SB = gets.chomp.chars
SC = gets.chomp.chars

c = 'a'

loop do
  n = case c
      when 'a'
        SA.shift
      when 'b'
        SB.shift
      when 'c'
        SC.shift
      end

  if n.nil?
    puts c.upcase
    exit
  end

  c = n
end


Measured memory_bytes: 1788
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
s = readline().rstrip().decode('utf-8')
kijun = ord("a")
if len(s) == 26:
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
        exit()
    else:
        for i in range(26):
            res = s[i:]
            flag = True
            for j in range(len(res)-1):
                if ord(res[j]) < ord(res[j+1]):
                    flag = False
                    break
            if flag:
                ans = s[:i-1]
                res2 = []
                for j in res:
                    res2.append(ord(j))
                res2.sort()
                for j in res2:
                    if ord(s[i-1]) < j:
                        print(ans + chr(j))
                        exit()




for i in range(kijun,kijun+26):
    if chr(i) not in s:
        print(s+chr(i))
        exit()

Measured memory_bytes: 61904
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
int main(){
    int h,w;
    cin >> h >> w;
    vector<string> m(h);
    rep(i,h) cin >> m[i];
    rep(i,h){
        rep(j,w){
            if(m[i][j]=='#'){
                bool ok = false;
                rep(k,4){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx>=0 && nx<h && ny>=0 && ny<w && m[nx][ny]=='#'){
                        ok = true;
                        break;
                    }
                }
                if(!ok){
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int i,h,w;
  char s[100][101];
  scanf("%d%d",&h,&w);
  for(i=0;i<h;i++)scanf("%s",s[i]);
  for(i=0;i<h*2;i++)puts(s[i/2]);
  return 0;
}

Measured memory_bytes: 128
N = int(input())
maxs = 0    
s = []
for i in range(N):
    cin = int(input())
    s.append(cin)
    maxs = max(maxs, cin)
M = maxs * N

dp = [False] * (M+1)
dp[0] = True

for x in s:
    for i in range(M+1):
        if M-i < x: continue
        if dp[M-i-x]: dp[M-i] = True

for i in range(M+1):
    if (M-i)%10 != 0 and dp[M-i]:
        print(M-i)
        break
else:
    print(0) 

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) v.begin(), v.end()

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

int main(){
    int K; cin >> K;
    queue<ll> X;
    rep(i, 9){
        X.push(i + 1);
    }
    ll u;
    rep(i, K){
        u = X.front();X.pop();
        if (u % 10 != 0) X.push(10 * u + u % 10 - 1);
        X.push(10 * u + u % 10);
        if (u % 10 != 9) X.push(10 * u + u % 10 + 1);
    }
    
    cout << u << endl;
}
    

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

int main () {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  vector<int> C(N - 1);

  rep(i,N) cin >> A.at(i);
  rep(i,N) cin >> B.at(i);
  rep(i,N - 1) cin >> C.at(i);

  int ans = 0;
  int tmp = A.at(0);
  rep(i, N) {
    ans += B.at(A.at(i) - 1);
  }

  for (int i = 1; i < N; i++) {
    if (A.at(i) - tmp == 1) {
      ans += C.at(tmp - 1);
    }
    tmp = A.at(i);
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		vector<pair<int, int>> vec;
		ll ans = 0;
		int lef = 0;
		for (int i = 0; i < n; ++i) {
			int k, l, r;
			scanf("%d%d%d", &k, &l, &r);
			if (l > r) {
				vec.push_back({l - r, k});
				ans += r;
				lef++;
			} else {
				vec.push_back({r - l, -(n - k)});
				ans += l;
			}
		}
		sort(vec.rbegin(), vec.rend());
		set<int> E;
		for (int i = 1; i <= n; ++i) E.insert(i);
		auto f = [&](int m) {
			set<int> empty = E;
			ll score = 0;
			for (int i = 0; i < n; ++i) {
				int k = vec[i].second;
				if (k < 0) {
					// leftmost of last -k.
					auto it = empty.lower_bound(max(m + 1, n + k + 1));
					if (it == empty.end()) continue;
					empty.erase(it);
					score += vec[i].first;
				} else {
					// rightmost of first k.
					auto it = empty.upper_bound(min(m, k));
					if (it == empty.begin()) continue;
					--it;
					empty.erase(it);
					score += vec[i].first;
				}
			}
			return score;
		};
		ans += f(lef);
		printf("%lld\n", ans);
	}
}


Measured memory_bytes: 23520
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[4]={0,1,0,-1},mdy[4]={-1,0,1,0};


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 n,a,b;

int main(){
	cin>>n>>a>>b;
	if(a*n<b)cout<<a*n<<endl;
	else cout<<b<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC087A
{
    class Program
    {
        static void Main(string[] args)
        {
            int x, a, b, c;
            x = int.Parse(Console.ReadLine());
            a = int.Parse(Console.ReadLine());
            b = int.Parse(Console.ReadLine());
            c = (x - a) % b;
            Console.WriteLine(c);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <time.h>
using namespace std; 

int main(){
	long long K, A, B, ans = 0;
	cin >> K >> A >> B;

	if (B - A < 2){
		ans = K + 1;
	}
	else{
		long long k;
		if (K < A){
			ans = K + 1;
		}
		else{
			k = A - 1;
			ans = k + 1 + (K - k) / 2 * (B - A);
			if ((K - k) % 2 == 1)
				++ans;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#include <numeric>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int nPr(int n, int r) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++)
		sum *= i;
	return sum;
}
//int nCr(int n, int r)
int nCr2(int n, int r) {
	return FACT(n) / (FACT(r) * FACT(n - r));
}
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
//int NUMOFDIV(int n) 素因数分解して+1してかける奴
int NUMOFDIV2(int n) {
	int ans = 0;
	REP(i, n) {
		if (n % i == 0)
			ans++;
	}
	return ans;
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
inline bool PRIMEOR (int x) {
	if (x ==1)
		return false;
	if (x == 2)
		return true;
	if (x%2==0)
		return false;
	double sqrtx = sqrt(x);
	for (int i = 3; i <= sqrtx; i += 2) {
		if (x % i == 0)
			return false;
	}
	return true;
}
using namespace std;
#pragma endregion
signed main() {
	int A, B, C,K;
	cin >> A >> B >> C >> K;
	if (K % 2 == 0)
		cout << A-B;
	else
		cout << B-A;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn solve(ls: &Vec<usize>, ps: &Vec<usize>, x: usize, lv: usize) -> usize {
    if lv == 0 {
        return if x >= 1 { 1 } else { 0 };
    }
    if x == 0 {
        return 0;
    }

    if x <= ls[lv-1] + 1 {
        solve(ls, ps, x-1, lv-1)
    } else {
        1 + solve(ls, ps, x-ls[lv-1]-2, lv-1) + ps[lv-1]
    }
}

fn main() {
    input!{
      n: usize,
      x: usize,
    }

    let mut ls = vec![0usize; n+1];
    let mut ps = vec![0usize; n+1];
    ls[0] = 1;
    ps[0] = 1;

    for i in 1..n+1 {
        ls[i] = ls[i-1]*2 + 3;
        ps[i] = ps[i-1]*2 + 1;
    }
    println!("{}", solve(&ls, &ps, x, n));
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

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

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

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    cout << N/3 << endl;
    return 0;
}


Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            int N = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            int[] suretsu = new int[N];

            for (int i = 0; i < N; i++)
            {
                suretsu[i] = int.Parse(input[i]);
                while(suretsu[i] % 2 == 0)
                {
                    count++;
                    suretsu[i] /= 2;
                }
            }
        
            Console.WriteLine(count);

        }

    }
}


Measured memory_bytes: 11744
#include<iostream>

using namespace std;

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

    int tmp = N;
    int sum = 0;
    while(tmp>10){
        sum += tmp % 10;
        tmp /= 10;
    }
    sum += tmp;
    if(N%sum==0){
        cout << "Yes";
    }else{
        cout << "No";
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int n,m,ans=0;
priority_queue<int>pq;
signed main(){
    cin>>n>>m;
    rep(i,n){
        int a;
        cin>>a;
        pq.push(a);
    }
    rep(i,m){
        int t=pq.top();
        pq.pop();
        t/=2;
        pq.push(t);
    }
    rep(i,n){
        int t=pq.top();
        pq.pop();
        ans+=t;
    }
    cout<<ans<<endl;
    return 0;
}





Measured memory_bytes: 1400
<?php
// Your code here!
    $s = fgets(STDIN);
    switch(strlen($s)-1){ // なんかしらんけど長さが+1なる 改行コード？
        case 6:
            echo 90000 + 900 + 9 . PHP_EOL;
            break;
        case 5:
            echo intval($s) - 9999 + 900 + 9 . PHP_EOL;
            break;
        case 4:
            echo 900 + 9 . PHP_EOL;
            break;
        case 3:
            echo intval($s) -99 + 9 . PHP_EOL;
            break;
        case 2:
            echo 9 . PHP_EOL;
            break;
        case 1:
            echo intval($s) . PHP_EOL;
    }
?>


Measured memory_bytes: 3700
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][]po=new int[n][3];
        for(int i=0;i<n;i++)
            for(int j=0;j<3;j++)
                po[i][j]=sc.nextInt();
        int[][]dp=new int[n+1][3];
        for(int i=0;i<n;i++)
            for(int j=0;j<3;j++)
                dp[i+1][j]=Math.max(dp[i][(j+1)%3],dp[i][(j+2)%3])+po[i][j];
        System.out.println(Math.max(dp[n][0],Math.max(dp[n][1],dp[n][2])));
    }
}


Measured memory_bytes: 99076
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;
        static void Main(string[] args)
        {
            var NM = Sarray();
            N = NM[0];
            M = NM[1];
            a = new int[N].Select(_ => new List<long>()).ToArray();
            for (var i = 0; i < N - 1; ++i)
            {
                var t = Sarray();
                a[t[0] - 1].Add(t[1] - 1);
                a[t[1] - 1].Add(t[0] - 1);
            }
            dpnode = new int[N].Select(_ => 1L).ToArray();
            dpoyaof = new long[N];

            dfs(0, -1);
            dpoyaof[0] = 1;
            dfs3(0);
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            for (var i = 0; i < N; ++i)
                WriteLine(dpoyaof[i] * dpnode[i] % M);
            Out.Flush();
        }
        static List<long>[] a;
        static long N;
        static long M;
        static long[] dpnode;
        static long[] dpoyaof;
        static void dfs(long v, long p)
        {
            a[v].Remove(p);
            foreach (var n in a[v])
            {
                dfs(n, v);
                dpnode[v] = dpnode[v] * (dpnode[n] + 1) % M;
            }
        }
        static void dfs3(long v)
        {
            var st = new Stack<long>();
            st.Push(v);

            var ruil = new long[N + 1];
            var ruir = new long[N + 1];
            ruil[0] = 1;
            ruir[0] = 1;
            while (0 < st.Count)
            {
                v = st.Pop();
                var W = a[v].Count;
                if (W == 0) continue;
                for (var i = 0; i < W; ++i)
                {
                    ruil[i + 1] = ruil[i] * (dpnode[a[v][i]] + 1) % M;
                    ruir[i + 1] = ruir[i] * (dpnode[a[v][W - i - 1]] + 1) % M;
                }
                for (var i = 0; i < W; ++i)
                    dpoyaof[a[v][i]] = (ruil[i] * ruir[W - i - 1] % M * dpoyaof[v] + 1) % M;
                for (var i = 0; i < W; ++i)
                    st.Push(a[v][i]);
            }
        }
    }
}

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

int n;
string a[10000];
int arr[3];	//?°???????????????????

/*
int stoi(string str) {
	int ret;
	stringstream ss;
	ss << str;
	ss >> ret;
	return ret;
}
*/

void add(int n) {
	for (int i=2; i>=0; i--) {
		if (arr[i] > n) {
			if (i != 2) {
				arr[i+1] = arr[i];
				arr[i] = n;
			} else {
				arr[i] = n;
			}
		}
	}
}

signed main()
{
	cin >> n;
	rep(i,n) {
		cin >> a[i];
	}

	rep(i,3) arr[i] = INT_MAX;

	rep(i,n) rep(j,n) if (i != j) {
		int num = stoi(a[i] + a[j]);
		add(num);
	}

	cout << arr[2] << endl;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  long double r;
  cin >> r;
  cout << setprecision(15);
  cout << 2 * r * 3.1415 << endl;
}


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

int main(){
  int cnt[4]={};
  rep(i,3){
    int a,b; cin>>a>>b; a--,b--;
    cnt[a]++;
    cnt[b]++;
  }
  int cnt2[3]={};
  rep(i,4) cnt2[cnt[i]]++;
  if(cnt2[1]==2&&cnt2[2]==2) cout<<"YES\n";
  else cout<<"NO\n";
  return 0;
}


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


int main() {
  int a,b,c;
  cin>>a>>b>>c;
  cout<<max(0,abs(b-c)-a)<<endl;
}


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

def fctr1(n): 
    f = {}
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 2):
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f[i] = c
            c = 0
    if n != 1:
        f[n] = 1
    return f


a = fctr1(A)
b = fctr1(B)


cd_dic = {1: 1}
key_list = [1]

for k, v in a.items():
    if k in b:
        key_list.append(k)
        n = min(v, b[k])
        cd_dic[k] = n

print(len(cd_dic))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 998244353
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
const int mod = 1e9 + 7;

int main(){
    ll a,b; cin >> a >> b;
    if(a+b>=10) puts("error");
    else cout << a+b << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n and n){
        int a[n]={};
        int max=-5,min=10000,sum=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]<min){
                min=a[i];
            }
            if(a[i]>max){
                max=a[i];
            }
            sum+=a[i];
        }
        int ave=(sum-max-min)/(n-2);
        cout<<ave<<endl;
    }
    return 0;
}



Measured memory_bytes: 3016
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define fcout cout << fixed << setprecision(10)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acos(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


int H, W;
string S[30];
int d[30][30];
bool u[30][30];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };


signed main(){
    cin >> H >> W;
    rep(i, 0, H) cin >> S[i];

    int ans = 0;
    rep(i, 0, H) rep(j, 0, W) rep(s, 0, H) rep(t, 0, W){
        if(S[i][j] == '#' or S[s][t] == '#') continue;
        queue<PII> q;
        q.push({ i, j });
        u[i][j] = true;
        while(!q.empty()){
            auto p = q.front();
            q.pop();
            rep(k, 0, 4){
                int Y = p.first+dy[k];
                int X = p.second+dx[k];
                if(isin(Y, 0, H) and isin(X, 0, W) and !u[Y][X] and S[Y][X] == '.') q.push({ Y, X }), u[Y][X] = true, d[Y][X] = d[p.first][p.second]+1;
            }
        }
        chmax(ans, d[s][t]);
        rep(a, 0, 30) rep(b, 0, 30) d[a][b] = 0, u[a][b] = false;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,b,c;
    char op;
    
    for(;;){
    
             scanf("%d %c %d",&a,&op,&b);
             
             if(op=='+') c=a+b;
             else if(op=='-') c=a-b;
             else if(op=='*') c=a*b;
             else if(op=='/') c=a/b;
             else break;
    
             printf("%d\n",c);
       }
    return 0;
}

Measured memory_bytes: 600
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define EPS 1e-10
#define INF 1000000
#define mp make_pair
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;
typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<ll> L(90);
  L[0] = 2;
  L[1] = 1;
  for (int i = 2; i < L.size()-2; i++) {
    L[i] = L[i-1] + L[i-2];
  }
  cout << L[N] << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main() {
	int N;	cin >> N;
	vector<string> W(N);
	for (int i = 0; i < N; ++i) {
		cin >> W[i];
	}

	for (int i = 0; i < N - 1; ++i) {
		if (W[i][W[i].size() - 1] != W[i + 1][0]) {
			cout << "No" << endl;
			cin >> N;
			return 0;
		}
	}
	sort(W.begin(), W.end());
	for (int i = 0; i < N - 1; ++i) {
		if (W[i] == W[i + 1]) {
			cout << "No" << endl;
			cin >> N;
			return 0;
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int MOD = 1000000007;
//const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int k; cin >> k;
    string s; cin >> s;
    if (s.size() <= k) cout << s << endl;
    else cout << s.substr(0,k) << "..." << endl;
}

Measured memory_bytes: 3640
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head

const ll inv2 = (P+1)/2;
const int N = 3300;
int n,q,a[N],x[N],y[N];
int dp[N][N];
struct {int x,y;ll v;} s[N*10];

int main() {
	scanf("%d%d",&n,&q);
	REP(i,1,n) scanf("%d",a+i);
	REP(i,1,q) scanf("%d%d",x+i,y+i);
	REP(i,1,n) REP(j,1,n) dp[i][j] = a[i]>a[j];
	REP(z,1,q) { 
		int top = 0;
		REP(i,1,n) {
			if (i!=y[z]) { 
				s[++top] = {x[z],i,(dp[x[z]][i]+dp[y[z]][i])*inv2%P};
				s[++top] = {i,x[z],(dp[i][x[z]]+dp[i][y[z]])*inv2%P};
			}
			else { 
				s[++top] = {x[z],y[z],(dp[x[z]][y[z]]+dp[y[z]][x[z]])*inv2%P};
			}
			if (i!=x[z]) {
				s[++top] = {y[z],i,(dp[y[z]][i]+dp[x[z]][i])*inv2%P};
				s[++top] = {i,y[z],(dp[i][y[z]]+dp[i][x[z]])*inv2%P};
			}
			else {
				s[++top] = {y[z],x[z],(dp[x[z]][y[z]]+dp[y[z]][x[z]])*inv2%P};
			}
		}
		REP(i,1,top) dp[s[i].x][s[i].y]=s[i].v;
	}
	int ans = 0;
	REP(i,1,n) REP(j,i+1,n) ans = (ans+dp[i][j])%P;
	ans = ans*qpow(2,q)%P;
	printf("%d\n", ans);
}








Measured memory_bytes: 41216
#include<iostream>
#include<set>
#include<vector>
#include<string>
#include<stack>
using namespace std;

struct Node{
  int name;
  vector<int> edges;
};

set<int> search(vector<Node> g) {

  int now;
  for(int i=0; i<=6; i++)
    if(!g[i].edges.empty())
      now = i;

  stack<int> q;
  set<int> s;
  q.push(now);

  while(!q.empty()) {
    now = q.top();
    s.insert(now);
    q.pop();

    for(int i=0; i<g[now].edges.size(); i++)
      if( s.find(g[now].edges[i])==s.end() )
	q.push( g[now].edges[i] );
  }
  return s;
}

int main() {

  int d,c;
  while(cin>>d) {
    string s;
    vector<Node> graph;

    for(int i=0; i<=6; i++) {
      Node n;
      n.name = i;
      graph.push_back(n);
    }

    for(int i=0; i<d; i++) {
      cin>>s;
      graph[s[0]-'0'].edges.push_back(s[1]-'0');
      graph[s[1]-'0'].edges.push_back(s[0]-'0');
    }

    set<int> con = search(graph);

    for(int i=0; i<graph.size(); i++)
      if(con.find(i)==con.end() && !graph[i].edges.empty() ) {
	cout<<"No"<<endl;
	goto NEXT;
      }

    c=0;
    for(int i=0; i<graph.size(); i++)
      if(graph[i].edges.size()%2==1)
	c++;

    if(c==0||c==2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

  NEXT:
    ;
  }
}

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

b,c,d,e = 0,a[0],a[1],sum(a[2:n])
p,q,r = -1,1,1
m = sum(a)

while q <= n-3:
  c += a[q]
  d -= a[q]
  while p+1 <= q-1 and abs(b-c+2*a[p+1]) <= abs(b-c):
    p += 1
    b += a[p]
    c -= a[p]
  while r+1 <= n-2 and abs(d-e+2*a[r+1]) <= abs(d-e):
    r += 1
    d += a[r]
    e -= a[r]
  m = min(m,max(b,c,d,e) - min(b,c,d,e))
  q += 1
print(m)

Measured memory_bytes: 24684
#137D
def main():
    import sys
    import heapq as h
    from collections import defaultdict
    N, M = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    D = defaultdict(list)
    for i in range(N):
        D[L[i][0]-1].append(-L[i][1])
    
    #print(D)
    ans = 0
    tmp=[]
    h.heapify(tmp)
    for d in range(M):
        for b in D[d]:
            h.heappush(tmp, b)
        #print(tmp)
        if tmp:
            ans += h.heappop(tmp)
        
    print(-ans)



if __name__=='__main__':
    main()

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

using namespace std;

int main()
{
    string s,ss;
    cin>>s>>ss;
    int a,b;
    cin>>a>>b;
    string kk;
    cin>>kk;
    if(kk==s)a--;
    else b--;
    cout<<a<<" "<<b;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define co(n) cout<<n<<endl
using namespace std;
typedef long long ll;
typedef vector<long> vl;
typedef vector<string> vs;

int main(){
  string s;
  c(s);
  int a=0,b=0,c,d,e,f,g,h;
  c=s[0];
  d=s[1];
  a=10*(c-48)+d-48;
  c=s[2];
  d=s[3];
  b=10*(c-48)+d-48;
  
  if(0<a && a<=12){
    if(0<b && b<=12) co("AMBIGUOUS");
    if(b==0 || b>12) co("MMYY");
  }
  else{
    if(0<b && b<=12) co("YYMM");
    else co("NA");
  }
    
  return 0;
}

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

int main()
{
    int N, M;
    cin >> N >> M;
    priority_queue<int> Q;
    for(int i = 0; i < N; ++i) {
        int tmp; cin >> tmp;
        Q.push(tmp);
    }
    /*
    for(int i = 0; i < N; ++i) {
        cout << Q.top() << endl;
        Q.pop();
    }
    */

    for(int i = 0; i < M; ++i) {
        int tmp = Q.top();
        Q.pop();
        Q.push(tmp/2);
    }

    ll sum = 0;
    while(!Q.empty()) {
        int tmp = Q.top();
        sum += tmp; Q.pop();
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  string s; cin >> s;
  int x = 0, y = 0;
  for (char c : s) {
    if ('A' <= c and c <= 'M') ++y;
    if ('N' <= c and c <= 'Z') --y;
    if ('a' <= c and c <= 'm') ++x;
    if ('n' <= c and c <= 'z') --x;
  }
  string t;
  while (y) {
    if (y > 0) t += 'A', --y;
    else t += 'N', ++y;
  }
  while (x) {
    if (x > 0) t += 'a', --x;
    else t += 'n', ++x;
  }
  cout << t.size() << '\n';
  cout << t << '\n';
}


Measured memory_bytes: 3312
import sys
input = sys.stdin.readline
def print_ans(N, p):
    """Test Case
    >>> print_ans(7, "1 2 3 4 5 6 7")
    YES
    >>> print_ans(5, "2 4 3 5 1")
    NO
    >>> print_ans(5, "5 2 3 4 1")
    YES
    """
    pr = list(map(int, p.split()))
    flg = 0
    for i in range(N):
        if i + 1 != pr[i]:
            if flg == 0:
                flg = 1
            elif flg == 1:
                flg = 2
            else:
                flg = 3
    if flg > 2:
        print("NO")
    else:
        print("YES")



if __name__ == '__main__':
    N= int(input().rstrip())
    p = input().rstrip()
    print_ans(N, p)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[3];
	for(int i=0;i<3;i++)cin>>a[i];
	sort(a,a+3);
	if(a[0]+a[1]==a[2])printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <complex>
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
using namespace std;
typedef long long ll;

int IsPrime(int num){
    if(num < 2)
        return 0;
    int rtnum = sqrt(num) + 1;
    for(int i = 2; i < rtnum; ++i){
        if(num % i == 0)
            return 0;
    }
    return 1;
}

int main(){
    int x;
    cin >> x;
    for(int i = x;; ++i){
        if(IsPrime(i)){
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(n**3)
    return

#B
def B():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    ans = sum(b)
    for i in range(n-1):
        x = a[i]
        y = a[i+1]
        if y == x+1:
            ans += c[x-1]
    print(ans)
    return

#C
def C():
    n = I()
    b = LI()
    b.append(float("inf"))
    a = [min(b[i],b[i-1]) for i in range(n)]
    print(sum(a))
    return

#D
def D():
    n,k = LI()
    a = S()
    ans = 0
    for i in range(n-1):
        if a[i] == a[i+1]:
            ans += 1
    print(min(n-1,ans+2*k))        
    return

#E
def E():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    p = LI()
    r = [0]*n
    bit = [0]*(n+1)
    for i in range(n)[::-1]:
        r[i] = (n-i-1)-sum(p[i])
        add(p[i])
    print(r)
    l = [0]*n
    bit = [0]*(n+1)
    for i in range(n):
        l[i] = i-sum(p[i])
        add(p[i])
    print(l)

    return

#F
def F():
    n = I()
    s = LI()
    s.sort()
    s = s[::-1]
    if s[0] == s[1]:
        print("No")
        return
    a = [s[0]]
    j = 1
    s.append(0)
    q = deque()
    for _ in range(n):
        for i in range(1<<_):
            if a[i] > s[j]:
                a.append(s[j])
                j += 1
            else:
                q.append(a[i])
    print(a)
    return

#Solve
if __name__ == "__main__":
    D()


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, m; cin >> n >> m;
  if (n > m) swap(n, m);
  long long ans;
  ans = (n == 1) ? abs(m - 2) : (n - 2) * (m - 2);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
# def gcd(a_gcd, b_gcd):
#     while b_gcd != 0:
#         a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
#     return a_gcd
#
#
# def lcm(a_lcm, b_lcm):
#     return a_lcm * b // gcd(a_lcm, b_lcm)
#
#
# def max_sum(N_max_sum, a_max_sum):
#     dp = [0] * (N_max_sum + 1)
#     for i in range(N_max_sum):
#         dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
#     return dp[N]
#
#
# def knapsack(N_knapsack, W, weight, value):
#     inf = float("inf")
#     dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
#     for i in range(W+1):
#         dp[0][i] = 0
#
#     for i in range(N_knapsack):
#         for w in range(W+1):
#             if weight[i] <= w:
#                 dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
#             else:
#                 dp[i+1][w] = dp[i][w]
#     return dp[N_knapsack][W]


# # s = input()
# # N = int(input())
# N, K = map(int, input().split())
# # b = list(map(int, input().split()))
# # c = [list(map(int, input().split())) for _ in range(N)]
#
#
#
# print(N-K+1)

R, G, B, N = map(int, input().split())
ans = 0

if B > R:
    B, R = R, B
if B > G:
    B, G = G, B

for r_i in range(N + 1):
    if r_i * R > N:
        break
    for g_i in range(N + 1):
        if r_i * R + g_i * G > N:
            break
        if (N - (r_i * R + g_i * G)) % B == 0:
            ans += 1

print(ans)

















Measured memory_bytes: 41692
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Integer cnt = 0;
      	for(int i = 1; i < N+1; i++){
        	if(String.valueOf(i).length()%2==1){
            	cnt++;
            }
        }
		System.out.println(cnt);
	}
}


Measured memory_bytes: 28116
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np

n,k,q = map(int, input().split())
a = []
for i in range(q):
  a.append(int(input()))

cor = np.zeros(n)

for i in range(q):
  cor[a[i] - 1] += 1

b = k + cor - q
for i in range(n):
  if(b[i] <= 0):
    print('No')
  else:
    print('Yes')


Measured memory_bytes: 19944