akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  
  int N;
  cin >> N;
  int ans = 0;
  
  if(N % 2 == 1){
   ans = (N-1)/2 + 1;
    cout << ans << endl;
  }else{
    ans = N/2;
    cout << ans << endl;
  }
  
  
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.next();
        if(s.equals("ABC"))
            System.out.println("ARC");
        else if(s.equals("ARC"))
            System.out.println("ABC");
    }
}


Measured memory_bytes: 35496
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String args[]) throws Exception{
        BufferedReader stdR = new BufferedReader(new InputStreamReader(System.in));
        String[] str = stdR.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int A = Integer.parseInt(str[1]);
        int B = Integer.parseInt(str[2]);
        System.out.println(Math.min(A, B) + " " +Math.max((A + B - N), 0));
    }
}

Measured memory_bytes: 22356
/********************************************************
  **░██████╗██╗░░░░░░█████╗░██╗░░░██╗██╗░█████╗░░██████╗░**
  **██╔════╝██║░░░░░██╔══██╗██║░░░██║██║██╔══██╗██╔════╝░**
  **╚█████╗░██║░░░░░███████║╚██╗░██╔╝██║██║░░╚═╝██║░░██╗░**
  **░╚═══██╗██║░░░░░██╔══██║░╚████╔╝░██║██║░░██╗██║░░╚██╗**
  **██████╔╝███████╗██║░░██║░░╚██╔╝░░██║╚█████╔╝╚██████╔╝**
  **╚═════╝░╚══════╝╚═╝░░╚═╝░░░╚═╝░░░╚═╝░╚════╝░░╚═════╝░**
  *********************************************************/

#include <bits/stdc++.h>
using namespace std;


#define ll                          long long
#define ld                          long double

#define forn(i,n)                   for(int i=0;i<n;++i)
#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(),v.rend();
#define isSubstring(s1,s2)          s1.find(s2) != std::string::npos
	
#define pb                          push_back
#define pf                          push_front
#define mp                          make_pair
#define fr                          first
#define sc                          second

#define vpi                         <vector<pair<int,int>>
#define vi                          vector<int>
#define sz(a)                       (int)a.size()

#define   endl                       "\n"
#define     nl                       cout<<"\n";
#define fastio                       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define MN                           INT_MIN
#define MX                           INT_MAX

bool isPrime(ll n){if(n<2)return false;for(ll x = 2;x*x <=n;x++){if(n%x == 0)return false;}return true;}
bool isPerfectSquare(long double x){long double sr=sqrt(x);return((sr-floor(sr))==0);}
int gcd(int a, int b){if(a==0)return b;if(b==0) return a;if(a==b)return a;if(a>b)return gcd(a-b,b);return gcd(a,b-a);} 


int32_t main()
{
	int n;
	cin >> n;
	int a[n];
	int mx=0,cnt=0;
	for(int i= 0 ;i<n;i++)
	{
		cin >> a[i];
	}
	for(int i= 0 ;i<n-1;i++)
	{
		if(a[i] < a[i+1])
		{
			mx = max(mx,cnt);
			cnt = 0;
		}else
		{
			cnt++;
			mx = max(mx,cnt);
		}
	}
	cout << mx<<endl;
}

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

void dfs(vector<vector<int>> &G, vector<int> &A, int current, int parent) {
  for (int i = 0; i < G.at(current).size(); i++) {
    if (G.at(current).at(i) == parent) continue;
    A.at(G.at(current).at(i)) += A.at(current);
    dfs(G, A, G.at(current).at(i), current);
  }
}

int main() {
  int N, Q; cin >> N >> Q;
  vector<vector<int>> G(N);
  vector<int> A(N);
  for (int i = 0; i < N-1; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    G.at(a).push_back(b);
    G.at(b).push_back(a);
  }
  for (int i = 0; i < Q; i++) {
    int p, x; cin >> p >> x;
    A.at(p-1) += x;
  }
  dfs(G, A, 0, -1);
  for (int i = 0; i < N-1; i++) cout << A.at(i) << " ";
  cout << A.at(N-1) << endl;
}


Measured memory_bytes: 29696
import sys
from collections import deque

import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()

    #    print(A)
    pp = int(bisect.bisect_left(A, 0))
    A_minus = deque(A[:pp])
    A_plus = deque(A[pp:])

    AA = deque([])
    AAm = deque([])
    if N == K:
        ans = 1
        for i in A:
            ans *= i
            ans %= mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp
            ans %= mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop()
            ans %= mod
        print(ans % mod)

    else:
        ans = A_plus.pop()

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp
            ans %= mod
        print(ans % mod)


if __name__ == "__main__":
    main()


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N;
    cin >> N;
    vector<Pll> AB(N), BA(N);
    for (ll i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        AB[i] = {a, b};
        BA[i] = {b, a};
    }
    sort(AB.begin(), AB.end());
    sort(BA.begin(), BA.end());

    ll ans;
    if (N & 1) {
        ans = BA[N / 2].first - AB[N / 2].first + 1;
    }
    else {
        ans = (BA[N / 2 - 1].first + BA[N / 2].first) - (AB[N / 2 - 1].first + AB[N / 2].first) + 1;
    }

    cout << ans << "\n";
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 9536
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
typedef long long ll;
const int INF = 1<<29;
const int N = 1e6 + 9;
ll a[N];
bool cmp(const pair<double, ll> &a, const pair<double, ll> &b)
{
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.second > b.second;
}
int main()
{
    fio;
    string s;
    vector <char> ans;
    cin >> s;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] == '0'){
            ans.pb(s[i]);
        }
        else if(s[i] == '1'){
            ans.pb(s[i]);
        }
        else if(s[i] == 'B' && ans.size() != 0){
            ans.pop_back();
        }
    }
    for(int i = 0; i < ans.size(); i ++){
        cout << ans[i];
    }
    return 0;
}


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

int main(){
  int n; cin >> n;
  long long lu1 = 2, lu2 = 1;
  for(int i = 0; i < n-1; i++){
    long long tmp = lu2;
    lu2 += lu1;
    lu1 = tmp;
  }
  cout << lu2 << endl;
}

Measured memory_bytes: 256
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(max(a, b), min(a, b))


N = int(input())
T = [int(input()) for i in range(N)]

A = T[0]
for i in range(N):
    A = lcm(A, T[i])
print(A)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int MAX = 1e9 + 5;

struct node{
  int cnt;
  long long sum;
  node *L,*R;
  node() : cnt(0), sum(0LL), L(NULL), R(NULL){}
};

node* tree;

// add
void add(node* cur, int At, int s = -MAX, int e = MAX)
{
  if(s > At || e < At)
    return;
  if(s == e){
    cur->cnt++;
    cur->sum += At;
    return;
  }
  if(!cur->L) cur->L = new node();
  if(!cur->R) cur->R = new node();
  int mid = s + (e - s) / 2;
  add(cur->L, At, s, mid);
  add(cur->R, At, mid + 1, e);
  cur->cnt = cur->L->cnt + cur->R->cnt;
  cur->sum = cur->L->sum + cur->R->sum;
}

// get Kth
int get(node* cur, int idx, int s = -MAX, int e = MAX)
{
  if(s == e)
    return s;
  if(!cur->L) cur->L = new node();
  if(!cur->R) cur->R = new node();
  int mid = s + (e - s) / 2;
  if(cur->L->cnt - 1 >= idx) return get(cur->L, idx, s, mid);
  return get(cur->R, idx - cur->L->cnt, mid + 1, e);
}

// query
pair<int, long long> query(node* cur, int i, int j, int s = -MAX, int e = MAX)
{
  if(s > j || e < i)
    return {0, 0};
  if(s >= i && e <= j)
    return { cur->cnt, cur->sum };
  if(!cur->L) cur->L = new node();
  if(!cur->R) cur->R = new node();
  int mid = s + (e - s) / 2;
  auto a = query(cur->L, i, j, s, mid);
  auto b = query(cur->R, i, j, mid + 1, e);
  return { a.first + b.first, a.second + b.second };
}

int main()
{
  node* tree = new node();
  int q, nbr = 0;
  long long sb = 0;
  scanf("%d", &q);
  while(q--){
    int t;
    scanf("%d", &t);
    if(t == 1){
      int a, b;
      scanf("%d%d", &a, &b);
      sb += b;
      add(tree, a);
      nbr++;
    }else{
      int At = get(tree, (nbr - 1) / 2);
      pair<int, long long> l = query(tree, -MAX, At);
      pair<int, long long> r = query(tree, At + 1, MAX);
      cout << At << " " << sb + 1LL * l.first * At - l.second + r.second - 1LL * r.first * At << endl;
    }
  }
  return 0;
}

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

long long N, M, A[16], fact[100009], inv[100009], dp[19][100009], mod = 1000000007;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

void init() {
	fact[0] = 1; for (int i = 1; i <= 100000; i++) fact[i] = (1LL * fact[i - 1] * i) % mod;
	for (int i = 0; i <= 100000; i++) inv[i] = Div(1, fact[i], mod);
}
long long npr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return fact[n] * inv[n - r] % mod;
}

int main() {
	init();
	cin >> N >> M;
	for (int i = 0; i < M; i++) cin >> A[i];
	reverse(A, A + M);

	dp[0][0] = 1;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << N); j++) {
			if (dp[i][j] == 0) continue;

			long long KAKUTEI = 0;
			for (int k = 0; k < N; k++) {
				if ((j / (1 << k)) % 2 == 1) KAKUTEI += (1 << k);
			}

			// A[i] を使わない場合
			dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod;

			// A[i] を使う場合
			for (int k = 0; k < N; k++) {
				if ((j / (1 << k)) % 2 == 1) continue;
				long long E = ((1 << N) - KAKUTEI) - A[i];
				long long F = npr(E, (1 << k) - 1);
				F *= (1 << k); F %= mod;
				dp[i + 1][j + (1 << k)] += dp[i][j] * F;
				dp[i + 1][j + (1 << k)] %= mod;
			}
		}
	}
	long long sum = 0;
	for (int i = 0; i < (1 << N); i++) {
		int bit = 0; for (int j = 0; j < N; j++) { if ((i / (1 << j)) % 2 == 1) bit++; }

		int rem = 0;
		for (int j = 0; j < N; j++) {
			if ((i / (1 << j)) % 2 == 0) rem += (1 << j);
		}
		long long res = dp[M][i] * fact[rem]; res %= mod;
		if (bit % 2 == 0) sum += res;
		if (bit % 2 == 1) sum -= res;
		sum += mod; sum %= mod;
	}
	sum *= (1 << N); sum %= mod;
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(e,array) for(const auto& e : array)
#define lower_index(v,a) (int)distance(v.begin(), lower_bound((v).begin(),(v).end(),a))
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
typedef long long ll;
const ll INF=1e18;
const ll MOD=1e9+7;

int main(){
    ll N;cin>>N;
    vector<ll> a(N);rep(i,N) cin>>a[i];
    sort(a.begin(),a.end());
    ll res=0;
    for(ll i=0;i<N-2;++i)for(ll j=i+1;j<N-1;++j){
        ll loc=lower_index(a,a[i]+a[j]);
        res+=max(loc-j-1,(ll)0);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int a,b;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>a>>b;
	if(a>=13)rc(b);
	if(a<13 && a>5)rc(b/2);
	rc(0);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

using namespace std;
using ll = long long;

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

map<long long, long long> prime_factor(long long n) {
    map<long long, long long> res;
    for (long long i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

void Main() {
    ll A, B; cin >> A >> B;
    ll _gcd = gcd(A, B);
    auto pf = prime_factor(_gcd);
    cout << pf.size() + 1 << endl;
}

int main() {
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
import math
N, K =map(int, input().split())
k = K
bordor = []
Ans = 0
while(K >= 1):
  bordor.append(K)
  K = K / 2
  
for i in range(len(bordor) - 1):
  if bordor[i] <= N:
    Ans += (math.ceil(bordor[i]) - math.ceil(bordor[i + 1])) * (1 / (2 ** (i + 1)))
    
 
  elif bordor[i] > N >= bordor[i + 1]:
    Ans += (N + 1 - math.ceil(bordor[i + 1])) * (1 / (2 ** (i + 1)))
    
if bordor[-1] != 1:
  Ans += 1 / (2 ** len(bordor))

if N >= k:
  Ans += (N - k + 1)
Ans = Ans / N  

print(Ans)

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int main(){
	long long a;scanf("%lld",&a);
	long long ret=a/11*2;
	a%=11;
	if(a)ret++;
	if(a>6)ret++;
	printf("%lld\n",ret);
}

Measured memory_bytes: 128
package main

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

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	N := nextInt(sc)
	K := nextInt(sc)
	p := make([]int, N)
	for i := 0; i < N; i++ {
		p[i] = nextInt(sc)
	}
	// fmt.Println("N", N, "K", K, "p", p)
	e := make([]float64, N)
	for i := 0; i < N; i++ {
		e[i] = float64((1+p[i])*p[i]/2) / float64(p[i])
	}
	sum, ans := 0.0, 0.0
	for i := 0; i < N; i++ {
		sum += e[i]
		if i >= K {
			sum -= e[i-K]
		}
		ans = max(ans, sum)
	}
	fmt.Println(ans)
}
func max(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 4608
'''
[AtCoder Library]
sum((a * i + b // m) for i in range(n))
をO(log(n+m+a+b))で計算する。
説明
f(x) = (ax+b)/m とし、 0<y<=f(x) (0<=x<n)の格子点を数える
1.  明らかな整数部を先に計算し a < m, b < m にする
2.  yn = math.floor(f(n))を計算する。これが範囲内でとり得る最大の整数値
3.  f(un) = yn なる実数unを求める。
    下記ソースコードでは xn=a*un として整数xnを扱っている
4.  n - math.ceil(un) が f(i)=yn となる i の個数なので答えにこれを加える。
    下記ソースコードでは math.ceil(un) = math.ceil(xn/a) を (xn + a - 1) // a として計算
5.  軸の入れ替えを行い再帰呼び出しをする。
    傾きを考えると   a←m, m←a
    定義域を考えると n←yn
    y切片を考えると b←a*(math.ceil(un)-un)
    下記ソースコードではa*(math.ceil(un)-un)は(a-xn%a)%aとして計算
'''
def sum_of_floor_of_linear(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * b // m
        b %= m
    yn = (a * n + b) // m
    xn = yn * m - b
    if yn == 0:
        return ans
    ans += (n - (xn + a - 1) // a) * yn
    ans += sum_of_floor_of_linear(yn, a, m, (a - xn % a) % a)
    return ans

t = int(input())
query = []
for _ in range(t):
    query.append(map(int, input().split()))
for n, m, a, b in query:
    print(sum_of_floor_of_linear(n, m, a, b))


Measured memory_bytes: 100968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<29;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll A,B,N;cin>>A>>B>>N;
    ll ans=-INF;
    
    chmax(ans,(A*N)/B-N/B*A);
    
    ll x=N/B*B-1;
    if(x<=N){
        chmax(ans,(A*x)/B-(x/B)*A);
    }
    
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3660
# -*- coding: utf-8 -*-
n, m = map(int,input().split())
if n == 1:
    ans = -1
    if m == 0:
        print(0)
        exit()
    for _ in range(m):
        s, c = map(int,input().split())
        if ans == -1 or ans == c:
            ans = c
        else:
            ans = -1
    print(ans)
else:
    ans = [-1 for _ in range(n)]
    for _ in range(m):
        s, c = map(int,input().split())
        if s == 1 and c == 0:
            print(-1)
            exit()
        if ans[s - 1] == -1 or ans[s - 1] == c:
            ans[s - 1] = c
        else:
            print(-1)
            exit()
    flag = True
    for i in range(n):
        if ans[i] == -1:
            ans[i] = 0
        if ans[i] >= 1:
            flag = False
        if ans[i] == 0 and flag:
            ans[i] = 1
            flag = False
    for i in range(n):
        ans[i] = str(ans[i])
    print(''.join(ans))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pb push_back
#define F first
#define S second
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)

# define M_PIl          3.141592653589793238462643383279502884L /* pi */

const ll M=1e9+7;
const int MaxM=100005;


void SieveOfEratosthenes(int n)                                   //all prime <= n
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }

    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}


bool isPowerOfTwo (int x)
{
    return x && (!(x&(x-1)));
}



bool comp(pair<int,int> a,pair<int,int> b){
  if(a.F==b.F){
    return a.S>b.S;
  }
  return a.F<b.F;
}


int dp[100005]={0};

bool visited[100005];



int dfs(int a,vector<vector<int>> &v){
     if(!visited[a]){
        visited[a]=true;
       
               for(auto i:v[a]){
                dp[a]=max(dp[a],1+dfs(i,v));
               }

               return dp[a];
     }
     else{ return dp[a]; }

}


void solve(){

int n,m;cin>>n>>m;

vector<vector<int>> v(n+1);
int a,b;
for(int i=0;i<m;i++){
    cin>>a>>b;
    v[a].push_back(b);
}
int ans=0;

for(int i=1;i<=n;i++){

             ans=max(ans,dfs(i,v));

}


cout<<ans;

}

int main(){


   int t=1;
//  cin>>t;
   while(t--){
      solve();
       }

 }


Measured memory_bytes: 11212
using System;

namespace ITP1_4_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = Console.ReadLine().Split(' ');
            int a = int.Parse(strs[0]);
            int b = int.Parse(strs[1]);
            Console.WriteLine("{0} {1} {2}", a / b, a % b, (a / (double)b).ToString("F5"));
        }
    }
}

Measured memory_bytes: 9124
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if (b / a > c) {
            System.out.println(c);
        } else {
            System.out.println(b/ a);
        }
        sc.close();
    }
}

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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL MOD = 1e9+7;

int safe(int x, int T) {
    return max(0, min(x, T));
}

void fill(vector<vector<int>> &v, int x, int y, int K) {
    int right = safe(x + 1, 2*K);
    int left = safe(x + 1 - K, 2*K);
    int top = safe(y + 1, 2*K);
    int bot = safe(y + 1 - K, 2*K);

    v[right][top]++;
    v[left][bot]++;
    v[left][top]--;
    v[right][bot]--;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> diff(2*K + 1, vector<int>(2*K + 1, 0));

    REP(i, N) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        if(c == 'W') {
            x += K;
        }
        x %= 2*K;
        y %= 2*K;
        FOR(s, -2, 3) {
            FOR(t, -2, 3) {
                if((s + t + 334)%2 == 0) {
                    fill(diff, x + s*K, y + t*K, K);
                }
            }
        }
    }
    vector<vector<int>> s(2*K + 1, vector<int>(2*K + 1, 0));
    s[0][0] = diff[0][0];
    int res = s[0][0];
    FOR(i, 1, 2*K + 1) {
        s[i][0] = diff[i][0] + s[i - 1][0];
        s[0][i] = diff[0][i] + s[0][i - 1];
        res = max({res, s[i][0], s[0][i]});
    }

    /*
    for(int i = 2*K;0 <= i;i--) {
        for(int j = 0;j <= 2*K;j++) {
            cout << diff[j][i] << " ";
        }
        cout << endl;
    }
    */
    FOR(i, 1, 2*K + 1) {
        FOR(j, 1, 2*K + 1) {
            s[i][j] = diff[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            res = max(res , s[i][j]);
        }
    }
    cout << res << endl;
    /*
    for(int i = 2*K;0 <= i;i--) {
        for(int j = 0;j <= 2*K;j++) {
            cout << s[j][i] << " ";
        }
        cout << endl;
    }
    */
    return 0;
}


Measured memory_bytes: 31616
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int[] d = new int[N];
		for (int i = 0; i < d.length; i++) {
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);

		PrintWriter out = new PrintWriter(System.out);
		out.println(d[N / 2] - d[N / 2 - 1]);

		out.flush();
	}

	public static int gcd(int a, int b) {
	    if (b == 0) return Math.abs(a);
	    return gcd(b, a % b);
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 26944
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

int main(){
	int q; cin >> q;
	vector<ll> a(q),b(q);
	for(int i=0;i<q;i++) cin >> a[i] >> b[i];
	for(int i=0;i<q;i++){
		ll ab=a[i]*b[i];
		ll c=sqrt(ab);
		if(c*(c+1)==ab) cout << 2*c-2;
		else if(c*(c+1)<ab) cout << 2*c-1;
		else if(a[i]!=b[i] && c*c==ab) cout << 2*c-3;
		else cout << 2*c-2;
		cout << endl;
	}

}


Measured memory_bytes: 256
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

dp = [[0] * 13 for j in range(lens)]
if S[0] == "?":
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, lens):
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
                amari = (j * 10 + k) % 13
                dp[i][amari] += dp[i - 1][j]
                dp[i][amari] %= MOD
        else:
            amari = (j * 10 + int(S[i])) % 13
            dp[i][amari] += dp[i - 1][j]
            dp[i][amari] %= MOD

print(dp[-1][5])


Measured memory_bytes: 96216
n = input()
code = raw_input().split()
a = int(code[0]); b = c = -10**18
for op, v in zip(code[1::2], map(int,code[2::2])):
    if op is "+":
        b = max(b-v, c+v)
        c += v
        a = max(a+v, b)
    else:
        c = max(b+v, c-v)
        a = b = max(a-v, c)
print max(a, b, c)

Measured memory_bytes: 20724
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

namespace std {
	#define u(x, a, b) for(ll x = a; x < b; x++)
	#define d(x, a, b) for(ll x = a; x > b; x--)
}

typedef long long ll;
typedef long double ld;

#define MAXI 100010
#define MOD 1000000007

int main(){
	ll n;
	cin >> n;
	
	ll t = n%1000;
	if(t==0){cout << 0;}
	else{cout << 1000-t;}
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9+7;

ll n;
ll ans=0;
void dfs(ll x, bool a, bool b, bool c){
  if(x>n) return;
  if(a*b*c) ans++;

  dfs(10*x+3, true, b, c);
  dfs(10*x+5, a, true, c);
  dfs(10*x+7, a, b, true);
}
 
int main(){
  cin >> n;
  dfs(0, 0, 0, 0);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=2e5+9;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b,c,d;
    bool ok=false;
    cin>>a>>b>>c>>d;
    for(int i=1; ; i++){ 
        if(i%2==1){ 
            c-=b;
            if(c<=0){ 
                ok=true;
                break; 
            }
        }
        else { 
            a-=d;
            if(a<=0){ 
                ok=false;
                break; 
            }
        }
    }
    cout<<(ok?"Yes":"No")<<'\n';
    
    

    return 0;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define chmax(x,y) x = max(x,y)
using namespace std;
int dp[5005][5005];

int main(){
  int n;
  string s;
  cin >> n >> s;
  for (int i = n-1;i >= 0;i--){
    for (int j = n-1;j >= 0;j--){
      if(s[i] == s[j]){
        dp[i][j] = dp[i+1][j+1] + 1;
      }
    }
  }
  int ans = 0;
  rep(i,n)rep(j,n){
    if(i >= j) continue;
    int x = min(dp[i][j],j-i);
    chmax(ans,x);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 98048
import copy

N,M=map(int,input().split())
R=[]
for i in range(M):
    a,b=map(int,input().split())
    R.append((a,b))

def connected(N,roads):
    arrived=[0]*(N+1)
    q=[]
    q.append(1)
    try:
        while True:
            loc=q.pop()
            arrived[loc]=1
            for r in roads:
                if r[0]==loc and arrived[r[1]]==0:
                    q.append(r[1])
                if r[1]==loc and arrived[r[0]]==0:
                    q.append(r[0])
    except IndexError:
        pass
    return sum(arrived)==N

ans=0
for i in range(M):
    roads = copy.deepcopy(R)
    del roads[i]
    if not connected(N,roads):
        ans+=1
print(ans)


Measured memory_bytes: 48216
a,b = (int(i) for i in input().split())

flag = True
if(b==1):
    print(0)
    flag=False

sasi = a;
answer = 1;

if(flag==True):
    while(sasi < b):
        sasi = sasi + a - 1;
        answer += 1;
    print(answer)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
int main(void)
{
  int a[26] = {}, b[26] = {};
  char s[200001] = {}, t[200001] = {};
  bool ok = true;
  int k;
  std::cin >> s >> t;
  k = std::strlen(s);
  for(int i = 0; i != k; i++){
    a[s[i] - 'a']++;
    b[t[i] - 'a']++;
  }
  std::sort(a, a + 26);
  std::sort(b, b + 26);
  for(int i = 0; i != 26; i++){
    if(a[i] != b[i]){
      ok = false;
      break;
    }
  }
  std::cout << (ok ? "Yes" : "No") << std::endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long A, long long B, long long C, long long K){
    if(K % 2 ==0){
        cout << A-B<<endl;
    }
    else{
        cout<<B-A<<endl;
    }
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long K;
    scanf("%lld",&K);
    solve(A, B, C, K);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

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

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

ll n,m;

int main(){
	cin>>n>>m;
	vl a(n);
	for(auto &i:a) cin>>i;
	ll x=1;
	for(int i=0;i<n;i++){
		x=lcm(x,a[i]/2);
		if(x>m) break;
	}
	bool B=1;
	if(x>m) B=0;
//	cout<<x<<endl;
	for(int i=0;i<n;i++) if(x/(a[i]/2)%2==0) B=0;
	cout<<(B?(m-x)/(2*x)+1:0)<<endl;
}


Measured memory_bytes: 1024
n,m=map(int, input().split())
maru=0
pena=[0]*n

Num = []
St = []

toi=set() #重複無しのset型で用意，リストの重複がないやつ
for i in range(m):
    p, s = input().split()
    #Num.append(int(p))
    #St.append(s)
#print(Num[0])
#print(St)
    p=int(p)-1 #0index

    if p in toi:
        continue #以降はスキップ

    elif s=='AC':
        toi.add(p) #そのpの時のとい番号を保存
        #print(p)
    else: 
        pena[p]+=1
print(len(toi), sum(pena[p] for p in toi)) #各pの時のWAをたす

Measured memory_bytes: 12652
/*
 KUNAL RAUT (ZUKONIT14)  :- "DO WHAT YOU LIKE!"
 -PICT,PUNE! :)
 */
#include<bits/stdc++.h>
using namespace std;
#define ll          unsigned long long
#define int         long long
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define fi          first
#define se          second
#define mod         1000000007
#define mod9        1000000009
#define pi          3.1415926535
#define MAXN        1000005
#define N           1000001
#define MAX2N       1*1000 + 10
#define all(v)      v.begin(), v.end()
#define allr(v)     v.rbegin(), v.rend()
#define ms(s, n)    memset(s, n, sizeof(s))
#define prec(n)     fixed<<setprecision(n)
#define forci(p,n)  for(ll i=p;i<(ll)n;i++)
#define forcj(p,n)  for(ll j=p;j<(ll)n;j++)
#define bolt        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a)     __builtin_popcount(a)
#define test        ll t;cin>>t;for(ll testi=1;testi<=t;testi++)
#define djokovic    freopen("input00.txt", "r", stdin);freopen("output00.txt", "w", stdout);

ll gcd(ll a, ll b)  {    if (b == 0) return a;    return gcd(b, a % b);}
ll lcm(ll a, ll b)  {    return (a / gcd(a, b) * b);}
ll expo(ll x, ll y) {
    ll res = 1; x = x % mod; while (y > 0) {
        if (y & 1)res = (1ll * res * x) % mod;
        y = y >> 1; x = (1ll * x * x) % mod;
    } return res;
}
ll ncr(ll n, ll r)  { ll res = 1; if (r > n - r)r = n - r; for (ll i = 0; i < r; i++) {  res *= n - i;  res /= i + 1; } return res;}
ll max(ll a, ll b)  {return (a > b) ? a : b;}
bool prime(ll n)    {ll i; for (i = 2; i <= sqrt(n); i++) {if (n % i == 0)return false;} return true;}
bool sortbysec(const pair<ll, ll> &a, const pair<ll, ll> &b)
{   if (a.second == b.second)
        return a.first < b.first;
    return (a.second < b.second);
}
//https://www.youtube.com/watch?v=WTJSt4wP2ME

// ll rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
// ll cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll n, k, m, q, ans, a[MAXN], ans1[MAXN]; vector<ll>v;
void solve()
{
    ll n;map<ll,ll>mp;
    cin>>n>>k;
    for(ll i=0;i<n;i++)
    {
        ll d;cin>>d;
        for(ll j=0;j<d;j++)
        {
            ll x;cin>>x;
            mp[x]++;
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)    if(!mp[i])  ans++;
    cout<<ans;
}
signed main()
{
    bolt;
    solve();
}




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

int dp[3001][3001];

int main()
{
	int n, t, s;
	scanf("%d %d %d", &n, &t, &s);
	for (int i = 1; i <= n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		
		for (int j = 1; j <= t; j++){
			if ((j - b < s ^ s < j) && j - b >= 0){
				dp[i][j] = max(dp[i][j], dp[i - 1][j - b] + a);
			}
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}
	
	int maxi = 0;
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= t; j++){
			maxi = max(maxi, dp[i][j]);
		}
	}
	
	printf("%d\n", maxi);
	
	return 0;
}

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

typedef long long int lli;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

#define INF 2000000000
#define fastIO ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
#define endl '\n'
#define foreach(v,c) for(typeof((c).begin()) v=(c).begin();v!=(c).end();++v)
#define all(a) a.begin(),a.end()
#define in(a,b) ((b).find(a)!=(b).end())
#define fill(a,v) memset(a,v,sizeof a)
#define sz(a) ((int)(a.size()))
#define mp make_pair
#define pb push_back

int n, W, V;
lli dp[110000][110];
lli v[110];
lli w[110];
int main(){
  fastIO
  cin>>n>>W;
  V = 0;
  for(int i = 1; i <= n; i++){
    cin>>w[i]>>v[i];
    V += v[i];
  }
  for(int j = 0; j <= n; j++){
    for(int i = 0; i <= V; i++){  
      if(i == 0 && j == 0)dp[i][j] = 0;
      else if(j == 0)dp[i][j] = INF;
      else dp[i][j] = INF;
    }
  }
  for(int j = 1; j <= n; j++){
    for(int i = 0; i <= V; i++){
      if(i >= v[j])dp[i][j] = min(dp[i][j - 1], dp[i - v[j]][j - 1] + w[j]);
      else dp[i][j] = min(dp[i][j - 1], w[j]);
    }
  }
  int maxx = -1;
  for(int i = 0; i <= V; i++){
    //cout<<dp[i][n - 1]<<" ";
    if(dp[i][n] <= W){
      maxx = max(maxx, i);
    }
  }
  cout<<maxx<<endl;
}

Measured memory_bytes: 86272
N=int(input())
P=list(map(int,input().split(' ')))

def is_mid(v):
  return int(min(v)<v[1] and v[1]<max(v))
res=0
for i in range(1,N-1):
  res+=is_mid(P[(i-1):(i+2)])
print(res)

Measured memory_bytes: 3060
import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()

BtoC = [0]*N
for i in range(N):
    BtoC[i] = N - bisect.bisect_right(C,B[i])
s = [0]*N
for i in range(N):
    i = N-1-i
    if i == N-1:
        s[i] = BtoC[i]
        continue
    s[i] = s[i+1]+BtoC[i]
res = 0
for a in A:
    ind = bisect.bisect_right(B,a)
    res += s[ind] if ind <= N-1 else 0
print(res)

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

int main() {
  int H, W;

  while (true) {
    cin >> H >> W;
    if (H == 0 && W == 0)
      break;

    for (int w=0;w<W;w++)
      cout << "#";
    cout << endl;
    for (int h=1;h<H-1;h++) {
      cout << "#";
      for (int w=1;w<W-1;w++)
        cout << ".";
      cout << "#";
      cout << endl;
    }
    for (int w=0;w<W;w++)
      cout << "#";
    cout << endl;

    cout << endl;
  }
}



Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

int main(){
    int n;
    cin >> n;
    int a[n], b[n];
    for(int i=0; i<n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a, a+n);
    sort(b, b+n);
    if(n%2 == 1){
        cout << b[n/2] - a[n/2]+1;
    }else{
        cout << b[n/2]+b[n/2-1] - (a[n/2]+a[n/2-1])+1;
    }
    return 0;
}

Measured memory_bytes: 5164
import { readFileSync } from 'fs'
const input: string = readFileSync("/dev/stdin", "utf8")
export function dividing(input: string) {
  let count = 0
  let skip = false
  const s = input.trim().split('').reduce((pre, value) => {
    if (pre !== value) {
      if (skip === true) {
        count++
        skip = false
        return pre + value
      } else {
        count++
        return value  
      }
    } else {
      if (skip === true) {
        count++
        skip = false
        return pre + value
      } else {
        skip = true
        return pre
      }
    }
  }, '')
  console.log(count)
}

dividing(input)

Measured memory_bytes: 11468
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
int main(){
  int n;
  cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  vector<int> dp(n+100,1000000000);
  dp[0]=0;
  dp[1]=abs(h[0]-h[1]);
  for(int i=1;i<n-1;i++){
    dp[i+1]=min(abs(h[i]-h[i+1])+dp[i],abs(h[i-1]-h[i+1])+dp[i-1]);
  }
  cout<<dp[n-1]<<endl;
}

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

using namespace std;

const int mx = 1e6 + 9;

vector <int> divs[mx];

void generate_divisors() {
    for (int i = 1; i < mx; i++) {
        for (int j = i; j < mx; j += i) {
            divs[j].push_back(i);
        }
    }
}

bool found(int *fwd, int *bkd, int x) {
    auto it = lower_bound(fwd, bkd, x);
    if (it == bkd) return false;
    if (*it != x) return false;
    return true;
}

int main() {
    int n; scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    generate_divisors();
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (i < n - 1 and found(a + i + 1, a + n, a[i])) continue;
        if (i == 0) {
            ans++;
            continue;
        }
        bool take = true;
        for (auto d : divs[a[i]]) {
            if (found(a, a + i, d)) {
                take = false;
                break;
            }
        }

        if (take) ans++;
    }

    printf("%d\n", ans);
}

Measured memory_bytes: 118932
n = int(input())
a_lst = list(map(int, input().split()))

a_max = max(a_lst)
index_lst = [0]*(a_max + 1)

for ai in a_lst:
    for multi in range(ai, a_max+1, ai):
        index_lst[multi] += 1

ans = 0
for ai in a_lst:
    if index_lst[ai] == 1:
        ans += 1
print(ans)

Measured memory_bytes: 32060
#pragma GCC optimize("O3")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ld long double
#define rep(i,a,n) for (int i=(int)(a);i<(int)(n);i++)
#define per(i,a,n) for (int i=(int)(n-1);i>=(int)(a);i--)
#define mp(a, b) make_pair(a, b)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define fi first
#define se second
 
 
const int MOD = 1e9 + 7; // = (119<<23)+1
const int N = 5e5+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
int fact[N];
 
int su(int a, int b) {
    return ((a + b) % MOD + MOD) % MOD;
}
 
int pr(int a, int b) {
    return ((1ll * a * b) % MOD + MOD) % MOD;
}
 
int my_pow(int a, int b) {
    if (b == 0) {
        return 1;
    }
 
    int tmp = my_pow(a, b / 2);
    tmp = pr(tmp, tmp);
    if (b % 2) {
        tmp = pr(tmp, a);
    }
    return tmp;
}
 
int C(int k, int n) { 
    if (k > n) {
        return 0;
    }
    return pr(fact[n], my_pow(pr(fact[k], fact[n - k]), MOD - 2));
}
 
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
 
int main() {
    IOS;
    fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = pr(i, fact[i - 1]);
    }

    int ans = 0;

    int S;
    cin >> S;

    for (int i = 1; i * 3 <= S; ++i) {
        int cur = S - (i * 3);
        ans = su(ans, C(i - 1, cur + i - 1));
    }
    cout << ans << '\n';
}

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

int main(){
	int n, tp = 0, hp = 0;
	string tc, hc;

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>tc>>hc;
		if(tc > hc)      tp += 3;
		else if(tc < hc) hp += 3;
		else if(tc == hc){
			tp++;   hp++;
		}
	}

	cout<<tp<<" "<<hp<<endl;

	return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,k,q,i;
	cin>>n>>k>>q;
    ll a[n];
	for(i=1;i<=n;i++)
	a[i]=k;
	ll t=q;
	while(q--)
	{
		ll num;
		cin>>num;
		a[num]++;
	}
	for(i=1;i<=n;i++)
	{
		a[i]-=t;
		if(a[i]<=0)
		cout<<"No"<<endl;
		else
		cout<<"Yes"<<endl;
	}
}

Measured memory_bytes: 1408
s = input()
n = len(s)
even = [1 for i in range(n)]
odd = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(len(s)-1):
    if s[i]=='R' and s[i+1]=='R':
        even[i+1]+=odd[i]
        odd[i+1]+=even[i]
        odd[i]=0
        even[i]=0
for i in range(n-1):
    if s[n-1-i]=='L' and s[n-1-i-1]=='L':
        even[n-1-i-1]+=odd[n-i-1]
        odd[n-i-2]+=even[n-i-1]
        odd[n - i - 1]=0
        even[n-i-1]=0
for i in range(len(s)-1):
    if s[i]=='R' and s[i+1]=='L':
        ans[i]=even[i]+odd[i+1]
        ans[i+1] = even[i+1]+odd[i]
for i in ans:
    print(i,end=' ')
print('')

Measured memory_bytes: 6528
#include<cstdio>
#include<map>
using namespace std;
int tot;
int A,B,r,k;
map<int,char>f;
int main()
{
	scanf("%d%d%d",&A,&B,&k);
	if(A>B) r=A,A=B,B=r;
	for(int i=0;i<k;i++) {
		if(i+A>B) continue;
		printf("%d\n",i+A);
		f[i+A]=1;
	}
	for(int i=k-1;i>=0;i--) {
		if(f[B-i]||B-i<A) continue;
		printf("%d\n",B-i);
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll M = 1e9 + 7;

int main(void){
  int n, t;
  scanf("%d %d", &n, &t);
  vi as(n), bs(n);
  rep(i, n) scanf("%d %d", &as[i], &bs[i]);
  vector<vector<vi>> dp(2, vector<vi>(n + 1, vi(t, 0)));

  rep(i, n) rep(j, t){
    dp[0][i + 1][j] = dp[0][i][j];
    dp[1][i + 1][j] = dp[1][i][j];

    if (j - as[i] >= 0)
      dp[0][i + 1][j] = max(dp[0][i][j], dp[0][i][j - as[i]] + bs[i]);
    if (j - as[n - 1 - i] >= 0)
      dp[1][i + 1][j] = max(dp[1][i][j], dp[1][i][j - as[n - 1 - i]] + bs[n - 1 - i]);
    // cout << i << " " << j << " " << dp[0][i + 1][j] << endl;
  }

  int ans = 0;
  rep(i, n)
    rep(j, t)
      ans = max(ans, bs[i] + dp[0][i][j] + dp[1][n - 1 - i][t - 1 - j]);

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

  return 0;
}


Measured memory_bytes: 109140
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define TEST(...)                                                              \
    { printf("! "), printf(__VA_ARGS__); }
#else
#define TEST(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
  public:
    vector<int> V[maxn];
    int n;
    void solve() {
        cin >> n;
        for (int i = 1; i < n; ++i) {
            V[i].push_back(i + 1);
            V[i + 1].push_back(i);
        }
        int x, y;
        cin >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
        vector<int> ans(n + 1);
        for (int i = 1; i <= n; ++i) {
            vector<int> res = bfs(i);
            for (int j = 1; j <= n; ++j) {
                ans[res[j]]++;
            }
        }
        for (int i = 1; i < n; ++i) {
            cout << ans[i] / 2 << '\n';
        }
    }
    vector<int> bfs(int s) {
        vector<int> res(n + 1, -1);
        vector<int> que;
        res[s] = 0;
        que.push_back(s);
        for (int i = 0; i < que.size(); ++i) {
            for (int v : V[que[i]]) {
                if (res[v] == -1) {
                    res[v] = res[que[i]] + 1;
                    que.push_back(v);
                }
            }
        }
        return res;
    }
} NSPACE;
int main() {
    FPEN;
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    NSPACE.solve();
}

Measured memory_bytes: 4992