akhauriyash/Code-Regression huggingface dataset:
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    _ <- getLine
    as <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    let rs = until (any odd) (map (`div` 2)) as
    print $ f (head as) (head rs) (0 :: Int)
    where
        f a b n
            | a == b = n
            | otherwise = f (a `div` 2) b (n + 1)


Measured memory_bytes: 1020
#include <stdio.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int a[16];

bool rec() {
    int f = -1;
    rep (i, 9) if (a[i]) { f = i; break; }
    if (f == -1) return true;
    bool ans = false;
    if (a[f] >= 3) {
        a[f] -= 3;
        ans |= rec();
        a[f] += 3;
    }
    if (ans) return true;
    if (a[f] && a[f+1] && a[f+2]) {
        rep (i, 3) a[f+i]--;
        ans |= rec();
        rep (i, 3) a[f+i]++;
    }
    return ans;
}

bool is() {
    rep (i, 9) if (a[i] > 4) return false;
    bool ans = false;
    rep (i, 9) if (a[i] >= 2) {
        a[i] -= 2;
        ans |= rec();
        a[i] += 2;
        if (ans) return true;
    }
    return ans;
}

int main() {
    char buf[16];
    while (scanf("%s", buf) != EOF) {
        rep (i, 16) a[i] = 0;
        rep (i, 13) a[buf[i]-'1']++;
        bool f = false;
        rep (i, 9) {
            a[i]++;
            if (is()) {
                if (f) putchar(' ');
                f = true;
                printf("%d", i+1);
            }
            a[i]--;
        }
        if (!f) putchar('0');
        putchar('\n');
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
using namespace std;
int main() {
  int A, B;
  string S;
  cin >> A >> B >> S;
  int judge = 0;
  if (S[A] == '-') {
    for (int i = 0; i < A; i++) {
      if (S[i] == '-')
	judge = 1;
    }
    for (int i = A+1; i < A+B+1; i++) {
      if (S[i] == '-')
	judge = 1;
    }
    if (judge == 0)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>

int main(int argc, const char * argv[]) {
    char s[101];
    scanf("%s",s);
    long l=strlen(s);
    int alp[26]={0},ans=200;
    for(int i=0;i<26;i++){
        int count=0;
        for(long j=l-1;j>=0;j--){
            if(s[j]=='a'+i){
                alp[i]=alp[i]<count?count:alp[i];
                count=0;
            }else{
                count++;
            }
            if(j==0){
                alp[i]=alp[i]<count?count:alp[i];
            }
        }
        ans=ans<alp[i]?ans:alp[i];
    }
    
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 128
/***************************************************************************************

                              SUBMITTED BY-
                                       AISHWARY BAJPAI

***************************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define sl set<ll>
#define vl vector<ll>
#define vi vector<int>
#define pb push_back
#define PI  3.14159265
int main()
{
    int k;
    string s;
    cin>>k>>s;

    if(s.size()<=k)
        cout<<s<<"\n";
    else
    {
        string b=s.substr(0,k);
        b+="...";
        cout<<b<<"\n";
    }
}


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

using namespace std;
typedef long long ll;

int main() {
    ll a, b, v, w, t;
    cin >> a >> v >> b >> w >> t;
    bool ans = 0;
    if (a < b && a + v * t >= b + w * t) ans = 1;
    if (a >= b && a - v * t <= b - w * t) ans = 1;
    if (ans) puts("YES");
    else puts("NO");
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

int main(){

  long long int H, N, tmp1, tmp2;
  std::vector<long long int> A, B;
  
  scanf("%lld%lld", &H, &N);
  for(long long int i = 0; i < N; i++){
    scanf("%lld%lld", &tmp1, &tmp2);
    A.push_back(tmp1);
    B.push_back(tmp2);
  }

  // solve problem
  std::vector<long long int> dp(H+1);
  for(long long int i = 1; i < H+1; i++){
    dp[i] = 1e10;
  }

  for(long long int h = 1; h <=H; h++){
    for(long long int i = 0; i < N; i++){
      // first magic
      if(A[i] > h){
        dp[h] = std::min(dp[h], B[i]);
      }
      else{
        dp[h] = std::min(dp[h], dp[h-A[i]]+B[i]);
      }
    }
  }

  std::cerr << "Answer: " << std::endl;
  std::cout << dp[H] << std::endl;

  return 0;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
     int H,W,i,j;
     while(cin>>H>>W){
          if(H==0 && W==0){
			  break;
		  }
		  for(i=0;i<H;i++){
			for(j=0;j<W;j++){
				if((i%2==1&&j%2==1)||(i%2==0&&j%2==0)){
					cout<<"#";
				}
				else{
						cout<<"."; 
					}
				}
						cout<< endl;
  }
  cout<<endl;
}
}




Measured memory_bytes: 3056
K,N=map(int,input().split())
List = list(map(int, input().split()))
res = 0
mid = 0
for i in range(N):
  if i == N-1:
    res+= K-List[i]+List[0]
    mid = max(mid,K-List[i]+List[0])
  else:
    res+= List[i+1]-List[i]
    mid = max(mid,List[i+1]-List[i])
res = res - mid
print(res)

Measured memory_bytes: 33292
#include<iostream>
using namespace std;
int main(){
  int a,b,c,d,cnt=0;
  cin>>a>>b>>c>>d;
  int ans[110]={};
  for(int i=a;i<b;i++)  ans[i]+=1;
  for(int i=c;i<d;i++)  ans[i]+=1;
  for(int i=0;i<=100;i++){
    if(ans[i]>=2) cnt++;
  }
  cout<<cnt;

}


Measured memory_bytes: 256
Class Main
    Public Shared Sub Main()
        Dim tmp As String() = Split(Console.ReadLine(), " ")
        Dim S As Integer = CInt(tmp(0))
        Dim W As Integer = CInt(tmp(1))
    if S > W THEN
        Console.WriteLine("safe")
      else
        Console.WriteLine("unsafe")
        end if
        End Sub
End Class

Measured memory_bytes: 28328
#include<iostream>
using namespace std;
int N;
int A[200];
int i=0;
int main(){
  cin>>N;for(i=0;i<N;i++)cin>>A[i];
  int res=0;
  bool flag = false;
  while(true){for(i=0;i<N;i++){if(A[i]%2!=0)flag = true;}if(!flag){for(int j=0;j<N;j++)A[j]/=2;res++;}else break;}
  cout<<res<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll n;
	cin>>n;
	vector<ll> vec(n-1,0);
	ll sum=0;
	for(ll i=0;i<n-1;i++){
		cin>>vec[i];
	}
	
	vector<ll> v(n,INT_MAX);
	for(ll i=n-2;i>=0;i--){
		v[i+1]=min(v[i+1],vec[i]);
		v[i]=vec[i];
	}
	
	for(ll i=0;i<n;i++){
		sum+=v[i];
	}
	cout<<sum<<endl;
	
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete

nums = runSTUArray $ do
    arr <- newArray (1,100000) True :: ST s (STUArray s Int Bool)
    writeArray arr 1 False
    forM_ [2..320] $ \p -> do
        c <- readArray arr p
        when c $ do
            forM_ [p*2,p*3..100000] $ \x -> writeArray arr x False
    forM_ [100000,99999 .. 2] $ \p -> do
        c <- readArray arr p
        let t = (p+1) `div` 2
        d <- readArray arr t
        when (c && not d) $ writeArray arr p False
    res <- newArray (0,100000) 0 :: ST s (STUArray s Int Int)
    forM_ [2..100000] $ \i -> do
        c <- readArray arr i
        readArray res (i-1) >>= writeArray res i . (cond (+1) id c)
    return res

f :: Int -> Int -> Int
f l r = nums!r - nums!(l-1)

main = getInt >>= flip replicateM getInts >>= mapM_ (print . apply2 f)

Measured memory_bytes: 72444
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

int N, W;
ll dp[110][10101];
int v[110], w[110];
int main() {
	cin >> N >> W;
	rep(i, 0, N)cin >> v[i] >> w[i];

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= W;j++) {
			if (j >= w[i - 1]) {
				dp[i][j] = max(dp[i][j],max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]));
			}else{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][W] << endl;

	return 0;
}



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

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;


int main() {
    map<int, int> mp;
    for (int i = 1, x; i <= 3; i++) scanf("%d", &x), mp[x]++;
    printf("%s\n", (mp.size() == 2 ? "Yes" : "No"));
	return 0;
}


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

int n,a,b,cnt1,cnt2,cnt3;

int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;++i)
	{
		int x;
		scanf("%d",&x);
		if(x<=a)++cnt1;
		else if(x<=b)++cnt2;
		else ++cnt3;
	}
	printf("%d\n",min(cnt1,min(cnt2,cnt3)));
}

Measured memory_bytes: 256
#include <iostream>
 #include <vector>
 #include <algorithm>
#include <map>
 #include <set>
 #include <cmath>
 #include <cstring>
 #include <iomanip>
 #include <random>
 #include <chrono>
 #include <queue>
 #include <math.h>
 using namespace std;

int main(){
  char b;
  cin >> b;
  if (b=='A') cout <<'T' << endl;
    else if (b=='C')cout << 'G' << endl;
  else if (b=='G')cout <<'C'<<endl;
  else cout <<'A'<<endl;
}

Measured memory_bytes: 256
import math

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = 1
b = 1
for i in range(n):
    #n = max(math.floor(a/ta[i][0]), math.floor(b/ta[i][1]))
    n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1)
    a = n * ta[i][0]
    b = n * ta[i][1]

print(a+b)


Measured memory_bytes: 3188
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.HashSet;
import java.util.Iterator;

class Main {

    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N  = sc.nextLong();
        ArrayList<Long> prime = divisorX(N);
        //System.out.println(Arrays.toString(prime.toArray()));
        long min = Long.MAX_VALUE;
        long q1 = 0;
        long q2 = 0;
        for(int i=1;i<prime.size();i+=2){
            if(prime.get(i-1)+prime.get(i) < min){
                min = prime.get(i-1)+prime.get(i);
                q1 = prime.get(i-1);
                q2 = prime.get(i);
            }
        }
        // System.out.println(q1);
        // System.out.println(q2);
        System.out.println(min-2);
    }

    public static final ArrayList<Long> divisorX(final long n) {
		final ArrayList<Long> list = new ArrayList<Long>();

		for (long i = 1l; i * i <= n; i++) {
			if (n % i == 0l) {
				list.add(i);
				list.add(n / i);
			}
		}
		return list;
	}
}

Measured memory_bytes: 22356
S = list(input())

if ''.join(S[:len(S)//2]) != ''.join(S[len(S)//2 + 1:]):
    print("No")
    exit()

a = len(S) - 1// 2

if ''.join(S[:a//2]) != ''.join(S[a//2 + 1:]):
    print("No")
    exit()

b = len(S) + 3 // 2 - 1

if ''.join(S[:b//2]) != ''.join(S[b//2 + 1:]):
    print("No")
    exit()

print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n;
    cin >> n;
    vector<ll>a(n);
    for(ll i=0;i<n;i++){
        cin >> a[i];
    }
    for(ll i=1;i<n;i++){
        a[i]+=a[i-1];
    }
    map<ll,ll>data;
    for(ll i=0;i<n;i++){
        data[a[i]]++;
    }
    data[0]++;
    ll ans=0;
    for(auto it:data){
        ll num=it.second;
        ans+=num*(num-1)/2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 16996
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using std::cin;
using std::cout;

int main(int argc, char* argv[]) {
  int n;
  cin >> n;

  std::vector<std::string> s(n);
  for (int i = 0; i < n; ++i) {
    std::string tmp;
    cin >> tmp;
    sort(tmp.begin(), tmp.end());
    s[i] = tmp;
  }
  sort(s.begin(), s.end());

  std::string prev = s[0];
  unsigned long c = 1;
  unsigned long total = 0;
  for (int i = 1; i < n; ++i) {
    if (s[i] == prev) {
      ++c;
    } else {
      total += c * (c - 1) / 2;
      c = 1;
      prev = s[i];
    }
  }
  total += c * (c - 1) / 2;

  cout << total;

  return 0;
}


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

typedef long long int ll;

int main() {
    int N;
    cin >> N;
    vector<ll> v(N);
    for (auto& i : v) cin >> i;
    auto v_ = v;
    ll ans_l = 0LL;
    for (int i = 0; i < N; i++) {
        if (i && v[i-1]%2LL && v[i]) v[i]--, ans_l++;
        ans_l += v[i]/2LL;
    }
    ll ans_r = 0LL;
    v = v_;
    for (int i = N-1; i > -1; i--) {
        if (i+1 < N && v[i+1]%2LL && v[i] > 0) v[i]--, ans_r++;
        ans_r += v[i]/2LL;
    }

    cout << max(ans_r, ans_l) << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> G;
vector<int> num;
void dfs(int s){
    for(int e: G[s]){
        if(num[e] == 0) {
            num[e] = -num[s];
            dfs(e);
        }
    }
}
int main(){
    long long N, M;
    cin >> N >> M;
    G.resize(N);
    vector<int> a(M), b(M);
    for(int i = 0; i < M; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    num.resize(N, 0);
    num[0] = 1;
    dfs(0);
    long long cnt = 0;
    for(int i = 0; i < N; i++){
        if(num[i] == 1) cnt++;
    }
    long long cnteq = 0;
    int flag = 0;
    for(int i = 0; i < M; i++){
        if(num[a[i]] != num[b[i]]) cnteq++;
        else flag = 1;
    }
    if(flag == 0) cout << cnt * (N - cnt) - cnteq << endl;
    else cout << N * (N - 1) / 2 - M << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> p(n),q(n);
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];
    vector<int> a(n);
    rep(i,n) a[i] =i+1;

    map <vector<int>,int> mp;
    do{
        mp[a] = mp.size();
    } while (next_permutation(a.begin(),a.end()));

    int ans = abs(mp[p] - mp[q]);
    cout << ans << endl;
}

Measured memory_bytes: 5248
#include<stdio.h>
 
int main(void)
{
  int N, M, i;
  int A[100];
  int cnt=0;
  double sum=0;
  
  scanf("%d %d", &N, &M);
  for(i=0;i<N;i++)
  {
    scanf("%d",&A[i]);
    sum+=A[i];
  }
  for(i=0;i<N;i++)
  {
     if(A[i]>=sum/(4*M))
      cnt++;
  }
  
  if(cnt>=M)
    printf("Yes\n");
 
  else
    printf("No\n");
  
  return 0;
}

Measured memory_bytes: 1640
#include<bits/stdc++.h>
 
using namespace std;
 
 
int main() {
    int n;
    cin >> n;
    vector<int> x(n);
    for (int &x : x) cin >> x;
    int ans = 1000000;
    for (int i = 1; i <= 200; i++){
        int temp = 0;
        for (int j = 0; j < n; j++){
            temp += (x[j] - i) * (x[j] - i);
        }
        if (temp < ans) ans = temp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include "bits/stdc++.h"
using namespace std;

int main() {
    string s;
    cin >> s;
    int position_of_a = 0;
    for(int i = 0; i < s.size(); i++){
        if(s.at(i) == 'A'){
            position_of_a = i;
            break;
        }
    }
    int position_of_z = 0;
    for(int i = 0; i < s.size(); i++){
        if(s.at(i) == 'Z'){
            position_of_z = max(position_of_z, i);
        }
    }
    cout << position_of_z - position_of_a + 1<< endl;
}

Measured memory_bytes: 640
#include <cstdio>
using namespace std;

void egcd(long long int *px, long long int *py, long long int a, long long int b)
{
    long long int tx, ty;
    if (b == 0) {
        *px = 1;
        *py = 0;
    } else {
        egcd(&tx, &ty, b, a%b);
        *px = ty;
        *py = tx - (a/b) * ty;
    }
}

int main()
{
    long long int a, b, x, y;
    scanf("%lld %lld", &a, &b);

    if (a >= b){
        egcd(&x, &y, a, b);
    } else {
        egcd(&y, &x, b, a);
    }

    printf("%lld %lld\n", x, y);
    return 0;
}



Measured memory_bytes: 2712
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    int N;
    cin >> N;

    int sum = 0;
    int maxL = 0;
    REP(i, N) {
        int l;
        cin >> l;
        sum += l;
        maxL = max(maxL, l);
    }

    sum -= maxL;
    if (maxL < sum) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if(s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> N >> K;
	vector<int>v(N);
	for (auto &i : v)cin >> i;
	L = 0, R = MOD;
	while (R - L > 1) {
		long long int sum = 0;
		long long int mid = (R + L) / 2;
		for (auto i : v) {
			sum += (i - 1) / mid;
		}
		if (sum <= K)R = mid;
		else L = mid;
	}
	cout << R << endl;
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

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; }
const ll LINF = 1e18;

int main()
{
  int A, B; cin >> A >> B;
  cout << (A*B-A-B+1) << endl;
}

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


ll n;
ll t[1000],a[1000];

int main(){
    cin >> n;
    REP(i,n) cin >> t[i] >> a[i];
    ll nt = 1, na = 1, x = 1;
    REP(i,n){
        x = max((na + a[i] - 1) / a[i],(nt + t[i] - 1) / t[i]);
        na = a[i] * x;
        nt = t[i] * x;
    }
    cout << na + nt << endl;
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    string S;
    cin >> S;
    string A = "";
    string B = "";
    A += S[0];
    ll cnt = 1;
    for (int i = 1; i < S.size(); i++) {
        B += S[i];
        if(A != B){
            cnt++;
            A = B;
            B = "";
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 200010;
int n, k, f[2][2][N];
char s[N];
ll ans = 1e17, res;
ll a[2][2], t[2][2], tt[2][2];

template<typename T> void gi(T &x) {
	x = 0; register char c = getchar(), pre = 0;
	for(; c < '0' || c > '9'; pre = c, c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10ll + (c ^ 48);
	if(pre == '-') x = -x;
}
void Mul1() {
	rep(i, 0, 1) rep(j, 0, 1) tt[i][j] = 1e16;
	rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1) rep(h, 0, 1) {
		if(k || h || s[1] != s[n]) tt[i][j] = min(tt[i][j], t[i][k] + t[h][j]);
	}
	memcpy(t, tt, sizeof(t));
}
void Mul2() {
	rep(i, 0, 1) rep(j, 0, 1) tt[i][j] = 1e16;
	rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1) rep(h, 0, 1) {
		if(k || h || s[1] != s[n]) tt[i][j] = min(tt[i][j], a[i][k] + t[h][j]);
	}
	memcpy(a, tt, sizeof(a));
}
int main() {
	scanf("%s", s + 1), gi(k), n = strlen(s + 1);
	if(n == 1) { printf("%lld\n", (1ll * n * k) / 2); return 0; }
	f[0][0][1] = 0, f[1][1][1] = 1, f[1][0][1] = f[0][1][1] = N;
	rep(i, 2, n) {
		rep(j, 0, 1) rep(k, 0, 1) {
			if(!k && s[i] == s[i - 1]) f[j][k][i] = f[j][1][i - 1];
			else f[j][k][i] = min(f[j][0][i - 1], f[j][1][i - 1]) + k;
		}
	}
	--k; rep(i, 0, 1) rep(j, 0, 1) a[i][j] = t[i][j] = f[i][j][n];
	for(; k; k >>= 1, Mul1()) if(k & 1) Mul2();
	ans = min(a[0][0], min(a[1][0], min(a[0][1], a[1][1])));
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

 
int main()
{
    int N;

    scanf("%d",&N);

    
    if(30<=N){
        printf("Yes\n");
    } 

    else {
        printf("No\n");
    }
    

    
    
 
    return 0;
}

Measured memory_bytes: 1636
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 m, d;
  cin >> m >> d;
  i64 ans = 0;
  for (i64 i = 1; i <= m; i++)
    for (i64 j = 1; j <= d; j++)
      if (i == j / 10 * (j % 10) && 2 <= j / 10 && 2 <= j % 10)
        ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 764
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N;
ll A[100002]={};
ll B[100001]={};
int main() {
	cin>>N;

	for(int i=0;i<N+1;i++){
		cin>>A[i];
	}
	for(int i=0;i<N;i++){
		cin>>B[i];
	}

	ll R=0;
	for(int i=0;i<N;i++){
		if(A[i]+A[i+1]>B[i]){
			R+=B[i];
			if(A[i]<B[i]){
				if(A[i+1]<=(B[i]-A[i])){
					A[i+1]=0;
				}else{
					A[i+1]=A[i+1]-(B[i]-A[i]);
				}

			}
		}
		else if(A[i]+A[i+1]==B[i]){
			R+=B[i];
			A[i+1]=0;
		}
		else{
			R+=(A[i]+A[i+1]);
			A[i+1]=0;
		}
	}

	cout<<R<<endl;

	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define MOD 1000000007
#define mp make_pair
#define ll long long
#define pb push_back
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug cout<<"Debugging.."<<endl
using namespace std;
int main()
{
	faster;
	string a;
	cin>>a;
	int l=a.length();
	for(int i=0;i<l;i++)
	cout<<'x';
	
}




Measured memory_bytes: 3576
import java.util.*;
public class Main{
public static void main(String[] args){
   Scanner s=new Scanner(System.in);
        int a=s.nextInt();
        int b=0,c=0,d=0,e=0;
        for(int i=0;i<a;i++) {
            String str=s.next();

            if(str.equals("AC"))
                b++;
            else if(str.equals("TLE"))
                c++;
            else if(str.equals("WA"))
                d++;
            else
                e++;

        }
        System.out.println("AC x "+b+"\nWA x "+d+"\nTLE x "+c+"\nRE x "+e);
}
}

Measured memory_bytes: 59712
using System;
using System.Collections.Generic;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int cpN = n;
        List<int> ans = new List<int>();
        for (int i = 2; i * i <= n; i++)
        {
            while (n%i==0)
            {
                ans.Add(i);
                n /= i;
            }
        }
        if(n!=1)
            ans.Add(n);
        Console.WriteLine($"{cpN}: {string.Join(" ",ans)}");
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}


Measured memory_bytes: 18080
import std.algorithm;
import std.bigint;
import std.bitmanip;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(double a, double b, double x) {
    const t = atan(2.0 * (a * a * b - x) / a ^^ 3) * 180.0 / PI;
    const s = atan((a * b * b) / 2.0 / x) * 180.0 / PI;
    double ans;
    if (a * a * b / 2.0 <= x)
        ans = t;
    else
        ans = s;
    
    return format("%.9f", ans);
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    double a;
    a = input.front.to!double;
    input.popFront;

    double b;
    b = input.front.to!double;
    input.popFront;

    double x;
    x = input.front.to!double;
    input.popFront;

    static if (is(ReturnType!solve == void))
        solve(a, b, x);
    else
        solve(a, b, x).writeln;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	string s;
	cin >> s;
	for(int i = 0 ; i < s.size() ; i++) s[i]-='0';
	for (int i = 0; i < (1 << 3); i++)
	{
		int ans = s[0];
		for (int j = 0; j < 3; j++)
		{
			if (i & (1 << j))
			{
				ans += s[j+1];
			}
			else
			{
				ans -= s[j+1];
			}
		}
		if (ans == 7)
		{
			for(int i = 0 ; i < 4 ; i++) s[i]+='0';
			cout << s[0];
			for (int j = 0; j < 3; j++)
			{
				if (i & (1 << j))
				{
					cout <<"+"<< s[j+1];
				}
				else
				{
					cout << "-" << s[j+1];
				}
			}
			cout << "=7";
			break;
		}
	}
}


Measured memory_bytes: 256
package main

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

func main() {
	N := nextInt()
	fmt.Println(N * (N - 1) / 2)
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 640
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int get_digits(ll a) {
    if (a == 0) {
        return 1;
    }

    int digit = 0;
    while (a != 0) {
        a /= 10;
        digit++;
    }
    return digit;
}

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

    ll res = get_digits(n);
    for (ll a=1; a*a<=n; a++) {
        if (n % a == 0) {
            ll b = n / a;
            res = min(res, (ll) max(get_digits(a), get_digits(b)));
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3596
n = int(input())
aaa = list(map(int, input().split()))

ans = float('inf')
i1, i3 = 1, 3
s = [aaa[0], aaa[1], aaa[2], sum(aaa[3:])]
for i2 in range(2, n - 1):
    if i2 == i3:
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    while i1 < i2 - 1 and abs(s[0] - s[1]) > abs(s[0] - s[1] + 2 * aaa[i1]):
        s[0] += aaa[i1]
        s[1] -= aaa[i1]
        i1 += 1
    while i3 < n - 1 and abs(s[2] - s[3]) > abs(s[2] - s[3] + 2 * aaa[i3]):
        s[2] += aaa[i3]
        s[3] -= aaa[i3]
        i3 += 1
    ans = min(ans, max(s) - min(s))
    s[1] += aaa[i2]
    s[2] -= aaa[i2]

print(ans)


Measured memory_bytes: 24684
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
int F[101]={};
int P[101][11]={};

int main() {
	cin>>N;
	int f1;
	for(int j=0;j<N;j++){
		for(int i=1;i<(1<<10);i=i<<1){
			cin>>f1;
			F[j]+=f1*i;
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<11;j++){
			cin>>P[i][j];
		}
	}
	int total=-1000000001;

	for(int i=1;i<(1<<10);i++){
		int sum=0;
		for(int j=0;j<N;j++){
			int x=F[j]&i;
			int k=0;
			for(int m=1;m<(1<<10);m=m<<1){
				if((x&m)==m)k++;
			}
			sum+=P[j][k];
		}
		total=max(total,sum);
	}


	cout<<total<<endl;

	return 0;
}


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

#define all(v) v.begin(), v.end()

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

char toLowerCase(char c){
  if(isLowerCase(c)){
    return c;
  }else{
    return c+'a'-'A';
  }
}
char toUpperCase(char c){
  if(isLowerCase(c)){
    return c-('a'-'A');
  }else{
    return c;
  }
}
ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
void func(vector<int>& l, int depth, int idx){
  ;
}
int main() {
  ll a[2],k;cin>>a[0]>>a[1]>>k;
  for(int i=0;i<k;i++){
    ll half=a[i%2]/2;
    if(a[i%2]%2!=0){
      a[i%2]--;
    }
    a[i%2]-=half;
    a[(i+1)%2]+=half;
  }
  cout<<a[0]<<" "<<a[1]<<endl;
  return 0;
}


Measured memory_bytes: 3584
n = int(input())
balls = list(map(int, input().split()))

counter = {}
for b in balls:
  counter[b] = counter.get(b, 0) + 1

sum = 0
for v in counter.values():
  sum += v * (v-1) // 2
  
for b in balls:
  n_old = counter[b]
  c_old = n_old * (n_old - 1) // 2
  c_new = (n_old - 1) * (n_old - 2) // 2
  
  result = sum - c_old + c_new
  print(result)

Measured memory_bytes: 26268
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(long long i=(long long)(a);i<(long long)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int n, k;

	cin>>n>>k;

	cout<<YN((n+1)/k>=2)<<endl;
}


Measured memory_bytes: 256
import collections as cl

N = int(input())
S_list = []
for i in range(N) :
    S_list.append(input())

c = cl.Counter(S_list)
most_common = c.most_common()

max_count = most_common[0][1]
key_list = []
for item in most_common :
    if (item[1] == max_count) :
        key_list.append(item[0])
        continue
    
    break

key_list.sort()
for key in key_list :
    print(key)



Measured memory_bytes: 47672
#include <iostream>
#include <vector>

int main() {
  int N;
  std::cin >> N;
  
  std::vector<int> A(N+1);
  for(int i = 0; i < N+1; ++i) {std::cin >> A[i];}
  
  std::vector<int> B(N);
  for(int i = 0; i < N; ++i) {std::cin >> B[i];}
  
  long long total = 0;
  for(int i = 0; i < N; ++i) {
    int buf = std::min(A[i], B[i]);
    total += buf;
    A[i] -= buf;
    B[i] -= buf;
    
    buf = std::min(A[i+1], B[i]);
    total += buf;
    A[i+1] -= buf;
    B[i] -= buf;
  }
  std::cout << total << std::endl;
  return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
#AGC38 B
#スライド最小値

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
p = LI()
ans = 0
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

lst = []
cnt = 1
tmp = p[0]
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        if cnt >= k:
            lst.append(i-k)
        cnt = 1
    tmp = p[i]
if cnt >= k:
    lst.append(i-cnt+1)
par = [i for i in range(n)]
rank = [0]*n
if len(lst) > 1:
    for i in lst:
        for j in lst[::-1]:
            union(i,j)
for i in range(n-k):
    if p[i] == minlst[i] and p[i+k] == maxlst[i+1]:
        union(i,i+1)
s = set()
for i in range(n-k+1):
    s.add(root(i))
print(len(s))



Measured memory_bytes: 108236
Q,H,S,D=map(int,input().split())
N=int(input())
usage=[]
slist=[4*Q,2*H,S]
slist.sort()
s=slist[0]  #これが1Lの値段に
dlist=[8*Q,4*H,2*s,D]
dlist.sort()
d=dlist[0]  #これが2Lの値段に

if N%2==0:
    print(d*(N//2))
else:
    print(d*(N//2)+s)



Measured memory_bytes: 38384
N, K = map(int, input().split())
h = []
for i in range(N):
  h.append(int(input()))

h.sort()


min = 10 ** 20

for i in range(N):
  if i+K > N:
    break
  diff = h[i+K-1] - h[i]
  if diff < min:
    min = diff

print(min)

Measured memory_bytes: 7384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 100005;
const int MAXM = 200005;

struct Edge
{
	int to, next;	
}e[MAXM];
int head[MAXN], te = 1;

inline void addE(int u, int v)
{
	e[++te] = (Edge){v, head[u]}, head[u] = te;
}

vector<int> w[MAXN];

int ind[MAXN], tp[MAXN], f[MAXN][2], res[MAXN];

char c[MAXN];

int n, x, y, r = 1, tot = 0, cnt = 0;

bool check[MAXN];

void dfs(int u, int fa = -1)
{
	bool &ch = check[u];
	ch = (c[u] == 'B');
	for (int j = head[u]; j != 0; j = e[j].next)
	{
		int v = e[j].to;
		if (v != fa)
		{
			dfs(v, u);
			ch &= check[v];
			if (!check[v])
				w[u].push_back(v), w[v].push_back(u);
		}
	}
}

// 0 -> reach leaf, 1 -> not reach leaf

void dp(int u, int fa = -1)
{
	int pre = -1;
	for (vector<int>::iterator it = w[u].begin(); it != w[u].end(); it++)
	{
		int v = *it;
		if (v != fa)
		{
			dp(v, u);
			if (pre == -1)
			{
				res[u] = (fa == -1 ? f[v][1] : f[v][0]) + tp[u];
				f[u][0] = f[v][0];
				f[u][1] = f[v][1];
			}
			else
			{
				res[u] = max(res[u], max(f[u][0] + f[v][1] + tp[u], f[u][1] + f[v][0] + tp[u]));
				f[u][0] = max(f[u][0], f[v][0]);
				f[u][1] = max(f[u][1], f[v][1]);
			}
			pre = v;
		}
	}
	if (u != r && ind[u] == 1)
		f[u][0] = tp[u], f[u][1] = 0;
	else
		f[u][0] += tp[u], f[u][1] += tp[u];
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		addE(x, y), addE(y, x);	
	}
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	while (c[r] != 'W' && r <= n)
		r++;
	if (r > n)
	{
		cout << 0 << endl;
		exit(0);		
	}
	dfs(r);
	for (int i = 1; i <= n; i++) 
		if (!check[i])
			for (vector<int>::iterator it = w[i].begin(); it != w[i].end(); it++)
				++ind[*it], ++tot;
	for (int i = 1; i <= n; i++)
		if (!check[i])
			tp[i] = ((c[i] == 'W') ^ (ind[i] % 2 == 1)), tot += tp[i], ++cnt;
	if (cnt <= 1)
		cout << cnt << endl;	
	else
	{
		dp(r);
		int mx = 0;
		for (int i = 1; i <= n; i++)
			if (!check[i])
				mx = max(mx, res[i]);
		cout << tot - 2 * mx << endl;
	}
	return 0;
}


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


int main(){

char a[3],b[3];
for(int i=0;i<3;i++)
    cin>>a[i];
for(int i=0;i<3;i++)
    cin>>b[i];
int ct=0;
    for(int i=0;i<3;i++){
        if(a[i]==b[i])
            ct++;
    }
cout<<ct<<endl;
return 0;
}





Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
typedef long long ll;
ll MOD = 1e9+7;

using namespace std;

int main()
{
	int a[3];
	int ans=0;
	
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==5 && a[1]==5 && a[2]==7)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<ctime>
#include<string>
#include<cstring>
#define ll long long
#define inf 0x7fffffff
using namespace std;
int a[100005];
int main(){
	int n;
	cin>>n;
	int a=0,b=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x%2!=0) a++;
		if(x%4==0) b++;
	}
	if(b>=a||(b+a==n&&b+1==a)) printf("Yes\n");
	else printf("No\n"); 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  string str;
  cin>>str;
  int count=0;
  for(int i=0;i<N-2;i++){
    if(str.at(i)=='A'&&str.at(i+1)=='B'&&str.at(i+2)=='C'){
      count++;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
typedef long long ll;
#define F(i,L,R) for (ll i = L; i < R; i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define re(x) scanf("%lld",&x)
#define N 300005LL
using namespace std;

ll t[2*300005] = {0}, n;

ll query(ll l, ll r){
	ll res = INT_MIN;
	for(l +=N, r+=N;l<r; l>>=1, r>>=1){
		if(l&1) res  = max(res, t[l++]);
		if(r&1) res = max(res, t[--r]);
	}

	return res;
}

void modify(ll p, ll value){
	ll val = max(value, t[p+N]);
	for(t[p+=N] = val;p>1;p>>=1) t[p>>1] = max(t[p],t[p^1]);
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll k, ans = 0;
  cin>>n>>k;
  vector<ll> a(n);
  for(auto &i: a) cin>>i;
  for(auto i: a){
  	ll l = max(0LL, i-k), r = min(N, i+k);
  	ll cnt = query(l, r+1);
  	ans = max(ans, cnt + 1);
  	modify(i, cnt+1);
  }

  cout<<ans<<endl;

   return 0;
}

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

int main(void){
    
    int N, T;
    cin >> N;
    vector<int> S(N);
    
    for(int i = 0; i < N; i++){
        cin >> S[i];
    }
    
    cin >> T;
    int ans = 0;
    for(int i = 0; i < T; i++){
        int q;
        cin >> q;
        for(int i = 0; i < N; i++){
            if(q == S[i]) {
                ans++;
                break;
            }
        }
    }
    
    cout << ans << endl;
    
}



Measured memory_bytes: 3144