akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int N;cin >> N;
    vector<int> a(N),b(N);
    rep(i,N)cin >> a[i];
    rep(i,N)cin >> b[i];
    ll res = 0;
    for(int k=0;k<30;k++){
        vector<int> am(N),bm(N);
        ll T =(1<<k);
        rep(i,N){
            am[i]=a[i]%(2*T);
            bm[i]=b[i]%(2*T);
        }
        sort(All(bm));

        ll is_one = 0;
        rep(i,N){
            int add = 0;
            if(am[i]<=T){
                add += lower_bound(All(bm),(2*T)-am[i])-lower_bound(All(bm),T-am[i]);
            }else{
                //add += lower_bound(All(bm),(1<<(k+1)))-bm.begin();
                //add -= lower_bound(All(bm),(3*(1<<k))-a[i])-lower_bound(All(bm),(1<<(k+1))-a[i]);
                add+=lower_bound(All(bm),(2*T)-am[i])-bm.begin();
                add+=lower_bound(All(bm),(2*T))-lower_bound(All(bm),(3*T)-am[i]);
            }
            is_one+=add;
        }
        if(is_one&1)res+=T;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3432
import copy
from itertools import product
h, w, k = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]

ans = 0
for bith in product([0, 1], repeat=h):
    for bitw in product([0, 1], repeat=w):
        ss = copy.deepcopy(s)
        tmp = 0
        for i, bh in enumerate(bith):
            for j, bw in enumerate(bitw):
                if bh == 1 or bw == 1:
                    ss[i][j] = 'o'
        for i in range(h):
            for j in range(w):
                if ss[i][j] == '#':
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)


Measured memory_bytes: 73852
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int main()
{
    int N, M, K; cin >> N >> M >> K;

    REP(i,N+1){
        REP(j,M+1){
            if(i*(M-j)+j*(N-i)==K){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    lint t, a;
    cin >> t >> a;
    vector<double> h(n);
    REP(i, n) { cin >> h[i];}
    lint ans=0;
    double min_d = 1000000;
    REP(i, n)
    {
        h[i] = t - h[i] * 0.006;
        min_d=min(min_d,abs(h[i]-a));
    }
    REP(i, n)
    {
        if(min_d==abs(h[i]-a)){
            cout << i+1 << "\n";

            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>

using u64 = unsigned long long int;
using s64 = long long int;
using u32 = unsigned int;

constexpr u32 mod = 1000000007;

int n;

u32 pow2[200001];

void reduce(u64 *a, u64 *b){
  u64 s, t, u, v;
  s = v = 1;
  u = t = 0;
  
  while(*a){
    u64 q = *b / *a;
    u64 r = *b % *a;
    std::tie(s, t, u, v) = std::forward_as_tuple(u, v, s + q*u, t + q*v);
    *b = *a;
    *a = r;
  }
  *a = u;
  *b = v;
}

u64 hash(u64 a, u64 b){
  const u64 x = 7;
  const u64 p = (1ULL<<61) - 1;

  return (a * x + b) % p;
}

int main(){

  scanf("%d", &n);
  pow2[0] = 1;
  for(int i = 1; i <= n; i++){
    pow2[i] = 2 * pow2[i-1];
    if(pow2[i] >= mod) pow2[i] -= mod;
  }

  using quot = std::pair<u64, u64>;
//  using quot = u64;
  std::vector<quot> vp, vn;
  u32 zeroa = 0;
  u32 zerob = 0;
  u32 zero2 = 0;

  for(int i = 0; i < n; i++){
    s64 a, b;
    scanf("%lld%lld", &a, &b);
    if(a == 0 && b == 0) zero2++;
    else if(a == 0) zeroa++;
    else if(b == 0) zerob++;
    else if((a^b) >= 0){
      u64 ua = std::abs(a);
      u64 ub = std::abs(b);
      reduce(&ua, &ub);
/*
      vp.push_back(hash(ua, ub));
*/
      vp.emplace_back(ua, ub);
    }
    else {
      u64 ua = std::abs(a);
      u64 ub = std::abs(b);
      reduce(&ua, &ub);
/*
      vn.push_back(hash(ub, ua));
*/
      vn.emplace_back(ub, ua);
    }
  }

  std::sort(vp.begin(), vp.end());
  std::sort(vn.begin(), vn.end());

  std::vector<std::pair<quot, u32> > vpp, vnn;
  quot prev = {0, 0};
//  quot prev = -1;
  for(auto const &x: vp){
    if(x == prev) vpp.back().second++;
    else{
      vpp.emplace_back(x, 1);
      prev = x;
    }
  }
  prev = {0, 0};
//  prev = -1;
  for(auto const &x: vn){
    if(x == prev) vnn.back().second++;
    else{
      vnn.emplace_back(x, 1);
      prev = x;
    }
  }

  u64 ans = (pow2[zeroa] + pow2[zerob] + mod - 1) % mod;
  auto ip = vpp.begin(), in = vnn.begin();
  while(ip != vpp.end() && in != vnn.end()){
    if(ip->first == in->first){
      ans = ans * (pow2[ip->second] + pow2[in->second] + mod - 1) % mod;
      ++ip, ++in;
    }
    else if(ip->first < in->first){
      ans = ans * pow2[ip->second] % mod;
      ++ip;
    }
    else {
      ans = ans * pow2[in->second] % mod;
      ++in;
    }
  }
  while(in != vnn.end()){ ans = ans * pow2[in->second] % mod; ++in; }
  while(ip != vpp.end()){ ans = ans * pow2[ip->second] % mod; ++ip; }

  ans = (ans + zero2 + mod - 1) % mod;
  printf("%llu\n", ans);

  return 0;
}


Measured memory_bytes: 13436
import java.util.*;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.nextLine());
        TreeMap<Integer, Integer> primes = new Prime().factorize(N);
        StringBuilder sb = new StringBuilder();
        sb.append(N);
        sb.append(": ");
        for (Map.Entry<Integer, Integer> e : primes.entrySet()) {
            for (int i = 0; i < e.getValue(); i++) {
                sb.append(e.getKey());
                sb.append(' ');
            }
        }
        System.out.println(sb.toString().trim());
    }

}

class Prime {
    public boolean isPrime(int n) {
        return getDivisors(n).size() == 2;
    }

    public List<Integer> getDivisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
                if (i != n / i) {
                    divisors.add(n / i);
                }
            }
        }
        return divisors;
    }

    public TreeMap<Integer, Integer> factorize(int n) {
        TreeMap<Integer, Integer> primes = new TreeMap<>();
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                primes.put(i, primes.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n != 1) {
            primes.put(n, 1);
        }
        return primes;
    }
}





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

using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n,ans = 0,nans = 0;
    cin >> n;
    string s;
    cin >> s;
    for(int i=0;i<n;i++){
    	if(s[i]=='I') nans++;
    	else if(s[i]=='D') nans--;
    	ans = max(nans,ans);
	}
    cout << ans << endl;
    
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int leap_year(int first_year, int last_year);

int main(void)
{
    int first_year, last_year;
    static int dataset_number = 0; 
    scanf("%d %d", &first_year, &last_year);
    while (1) {
        if (first_year == 0 && last_year == 0) {
            break;
        } else {
            if (dataset_number != 0) {
                printf("\n");
            }
            leap_year(first_year, last_year);
            scanf("%d %d", &first_year, &last_year);
        ++dataset_number;
        }
    }
    return 0;
}

int leap_year(int first_year, int last_year)
{
    int count = 0;
    for (int year = first_year; year <= last_year; ++year) {
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
           printf("%d\n", year);
        } else {
            ++count;
        }
    }
    if (count == last_year - first_year + 1) {
        printf("NA\n");
    }
    return 0;
}

Measured memory_bytes: 1044
#include <bits/stdc++.h>
using namespace std;
//debug
#ifdef grief
#define debug(...) do{\
	fprintf(stderr , "%s - %d : (%s) = " , __PRETTY_FUNCTION__ , __LINE__ , #__VA_ARGS__ );\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> 				void _DO(I&&x){	cerr<<x<<endl;	}
template<typename I,typename...T>	void _DO(I&&x,T&&...tail){	cerr<<x<<" , ";	_DO(tail...);	}
template<typename _a,typename _b> 	ostream& operator << (ostream &_s,const pair<_a,_b> &_p)
{	return _s<<'('<<_p.first<<','<<_p.second<<')';	}
#define IOS
#else
#define debug(...)
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0);
#endif
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
//macro
#define SZ(x) ((ll)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define stp setprecision(30)<<fixed
const ll INF=0x3f3f3f3f3f3f3f3f;
const int NF=0x3f3f3f3f;
const ll MAX=2e5+5,Mlg=__lg(MAX)+2;
const ll MOD=1e9+7;
//}}}
int n,arr[MAX],ss[MAX];
int main(){
	IOS
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		ss[i]=arr[i];
	}
	sort(ss,ss+n);
	cout<<ss[n-1]<< ' ';
	int gee=ss[0];
	for(int i=1;i<n-1;i++){
		if(abs(ss[i]*2-ss[n-1])<abs(gee*2-ss[n-1]))	gee=ss[i];
	}
	cout<<gee<< '\n';
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int gcd(int n, int m) {
    if (n < m) swap(n, m);
    while (m != 0) {
        int r = n % m;
        n = m;
        m = r;
    }
    return n;
}

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

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    int r;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i == 0) {
            r = a[i];
        } else {
            r = gcd(r, a[i]);
        }
    }

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

    cout << (k % r == 0 && k <= a[n - 1] ? "POSSIBLE" : "IMPOSSIBLE") << endl;

    return 0;
}

Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int n,m,q,ans=-1;
vector<int> a,b,c,d;

void dfs(vector<int> v){
    if(v.size()==n+1){
        int cnt=0;
        rep(i,q){
            if(v[b[i]]-v[a[i]]==c[i]) cnt+=d[i];
        }
        ans=max(ans,cnt);
        return;
    }
    v.push_back(v.back());
    while(v.back()<=m){
        dfs(v);
        v.back()++;
    }
}

int main(){
    cin>>n>>m>>q;
    a.assign(q,0);
    b.assign(q,0);
    c.assign(q,0);
    d.assign(q,0);
    rep(i,q){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    dfs(vector<int>(1,1));
    cout<<ans<<endl;
}

Measured memory_bytes: 3560
from collections import deque
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])
A=deque(A)
for b,c in BC[::-1]:
    for i in range(b):
        if A[0]<c:
            A.append(c)
            A.popleft()
        else:break
print(sum(A))

Measured memory_bytes: 34004
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head


void solve(){
    int n, m;
    cin >> n >> m;
    cout << n*(n-1)/2 + m*(m-1)/2 << '\n';
}

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

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


Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(10**5)

def f(x):
  for tmp in links[x]:
    if c[tmp[0]]<0:
      if tmp[1]%2==0:
        c[tmp[0]]=c[x]+0
      else:
        c[tmp[0]]=1-c[x]
      f(tmp[0])

N=int(input())
links=[[] for _ in range(N+1)]
for _ in range(N-1):
  u, v, w=map(int, input().split())
  links[u].append([v, w])
  links[v].append([u, w])
  
c=[-1]*(N+1)
c[1]=0
f(1)

print(*c[1:], sep='\n')

Measured memory_bytes: 84428
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;


int main(){
    int x;
    cin >> x;
    ll ans = 0LL;
    ans += (ll) 1000*(x/500);
    x -= 500*(x/500);
    ans += (x/5)*5;
    cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_set>

using namespace std;
#define INF 99999
#define _GLIBCXX_DEBUG
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define fi first
#define se second
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
using namespace std;



int main() {
    int X, t;

    cin >> X >> t;
    cout << max(0, X-t);

    return 0;
}

Measured memory_bytes: 256
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        n: usize,
        p: [(String, u32); n],
        x: String,
    }
    let mut ans = 0;
    for (s, t) in p.into_iter().rev() {
        if s == x {
            break;
        }
        ans += t;
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
# -*- coding: utf-8 -*-
# abc151/abc151_a
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    C = i2s()
    print(chr(ord(C) + 1))
    return

main()


Measured memory_bytes: 3064
// ------------------------------------
// Date:2018/ 2/24
// Problem:AGC 003 SimplifiedMahjong b.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ": " << x << '\n';

using ll = long long;

#define MOD 1000000007

int main()
{
  int N;
  ll ans = 0ll;
  cin >> N;
  vector<int> A(N);
  REP(i,N) cin >> A[i];
  REP(i,N) {
    // 小さい方からペアを組み、余る場合は上書き
    ans += A[i]/2;
    A[i] = A[i]%2;
    // 上書きして余りがり1大きいカードと先にペアを組める場合は組む
    if (i<N-1 && A[i]>0 && A[i+1]>0) {
      --A[i];
      --A[i+1];
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}



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

int main()
{

    int A, B;
    cin >> A >> B;
    bool can = false;

    for (int j = 0; j <= 10000; j++)
    {
        if (int(j * 0.08) == A && int(j * 0.1) == B)
        {
            cout << j << endl;
            can = true;
            break;
        }
        }
    if(can==false)
    {
        cout << -1 << endl;
    }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#キーエンスプログラミングコンテスト2019 B

import sys
import math
import bisect
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()))

s = input()
if s[:1] == 'k' and s[-6:] == 'eyence':
    print('YES')
elif s[:2] == 'ke' and s[-5:] == 'yence':
    print('YES')
elif s[:3] == 'key' and s[-4:] == 'ence':
    print('YES')
elif s[:4] == 'keye' and s[-3:] == 'nce':
    print('YES')
elif s[:5] == 'keyen' and s[-2:] == 'ce':
    print('YES')
elif s[:6] == 'keyenc' and s[-1:] == 'e':
    print('YES')
elif s[:7] == 'keyence' or s[-7:] == 'keyence':
    print('YES')
else:
    print('NO')


Measured memory_bytes: 38256
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 1987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 998244353;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int a[100000];
int main() {
	int n;
	scanf("%d",&n);
	int mx=-1,mn=INF;
	fup(i,0,n-1,1)
	{
		scanf("%d",a+i);
		mx=max(mx,a[i]);
		mn=min(mn,a[i]);
	}
	if(mx-mn>=2)return !printf("No");
	if(mx==mn)
	{
		if(mx==n-1 || mx<=n/2)puts("Yes");
		else puts("No");
		return 0;
	}
	int t1=0,t2=0;
	fup(i,0,n-1,1)
	{
		if(a[i]==mx)t1++;
		else t2++;
	}
	if(t2+1<=mx && mx<=t2+t1/2)puts("Yes");
	else puts("No");
}

Measured memory_bytes: 640
# -*- coding:utf-8 -*-
n, m = map(int, input().split())
a = []
b = []
ab = []
for i in range(n):
    abi = list(map(int, input().split()))
    ab.append(abi)
ab.sort(key = lambda x:(x[0]))
honsu = 0
kingaku = 0
j = 0
while honsu < m:
    honsu = honsu + ab[j][1]
    j = j + 1

honsu2 = 0
for i in range(j-1):
    honsu2 = honsu2 + ab[i][1]
    kingaku = kingaku + ab[i][0]*ab[i][1]
kingaku = kingaku + ab[j-1][0]*(m - honsu2)
print(kingaku)


Measured memory_bytes: 29020
package main

import (
	"fmt"
	"sort"
)

type Sord struct {
	a int64
	b int64
}

type Sords []Sord

func (a Sords) Len() int {
	return len(a)
}

func (a Sords) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a Sords) Less(i, j int) bool {
	return a[i].b > a[j].b
}

func main() {
	var N int
	var H int64

	fmt.Scanf("%d %d", &N, &H)

	sords := make(Sords, N)

	for i := 0; i < N; i++ {
		fmt.Scanf("%d %d", &sords[i].a, &sords[i].b)
	}

	sort.Sort(sords)

	max := sords[0].a
	for i := 0; i < N; i++ {
		if sords[i].a > max {
			max = sords[i].a
		}
	}

	attack := 0
	damage := int64(0)
	for i := 0; i < N; i++ {
		if damage >= H || sords[i].b < max {
			break
		}

		damage += sords[i].b
		attack++
	}

	if damage < H {
		more := int((H - damage) / max)
		if (H-damage)%max != 0 {
			more++
		}
		attack += more
		damage += max * int64(more)
	}

	fmt.Println(attack)
}


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

int main(){
  ll a, b, v, w, t;
  cin >> a >> v >> b >> w >> t;
  if(a<b){
    if((b-a) <= t*(v-w)){
        cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  else{
    if((a-b) <= t*(v-w)){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3632
# coding: utf-8
# Your code here!

S=input()
N=len(S)
ans=[0]*N
L2R=0 #最後に跨いだLからRの境界のRの位置
R2L=0 #最後に跨いだRからLの境界のLの位置
#LとRの境界で子供たちが往復する。

for i in range(N-1):    
    if S[i]=="R" and S[i+1]=="L":
        R2L=i+1
        temp=i-L2R+1
        ans[i]+=temp//2+temp%2
        ans[i+1]+=temp//2
    elif S[i]=="L" and S[i+1]=="R":
        L2R=i+1
        temp=i-R2L+1
        ans[R2L]+=temp//2+temp%2
        ans[R2L-1]+=temp//2

#最後のR2L以降のマスの処理
temp=N-R2L
ans[R2L]+=temp//2+temp%2
ans[R2L-1]+=temp//2

if R2L==0:
    ans=[1]*N
for a in ans:
    print(a,end=" ")    
    

Measured memory_bytes: 4976
N = int(input())
A, B = map(int, input().split())
P = list(map(int, input().split()))
one = 0
two = 0
three = 0
for i in range(N):
    if P[i] <= A:
        one += 1
    elif P[i] <= B:
        two += 1
    else:
        three += 1
print(min(one, two, three))


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

using namespace std;

int main(){
        int n;
        cin >> n;
        vector<long> group;
        for(int i=0;i<n;i++){
                long a;
                cin >> a;

                if(group.size() == 0 || group[0] >= a){
                        //cout << "Insert top " << a << endl;
                        group.insert(group.begin(), a);
                }else{
                        auto pos = lower_bound(group.begin(), group.end(), a);
                        --pos;
                        //cout << "Update " << *pos << " to " << a << endl;
                        *pos = a;
                }
        }

        cout << group.size() << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
 
typedef long long ll;

using namespace std;
using Graph = vector<vector<int>>;

#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--)

int N, M;
int a, b;


void Main()
{
    cin >> N >> M; 
    Graph root(N + 1);
    vector<int> ans(N + 1, 0);
    vector<int> check(N + 1, 0);

    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        root[a].push_back(b);
        root[b].push_back(a);
    }

    check[1] = 1;
    ans[1] = 1;

    queue<int> buff;
    buff.push(1);

    while (!buff.empty()) {
        int v = buff.front();
        buff.pop();

        for (int i = 0; i < root[v].size(); i++) {
            if (check[root[v][i]] == 0) {
                check[root[v][i]] = 1;
                ans[root[v][i]] = v;
                buff.push(root[v][i]);
            }
        }
    }
 
    for (int i = 1; i < N + 1; i++) {
        if (ans[i] == 0) {
            cout << i << " " << ans[i] << endl;
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
    for (int i = 2; i < N + 1; i++) {
            cout << ans[i] << endl;
    }
}
 
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

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

#define PI 4*atan(1)
#define INF 1e8

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> a(N), b(N);
  for(int i = 0; i < N; i++){
    cin >> a[i] >> b[i];
  }
  vector<int> c(M), d(M);
  for(int i = 0; i < M; i++){
    cin >> c[i] >> d[i];
  }
  for(int i = 0; i < N; i++){
    int min = 200000000, pos = 0;
    for(int j = 0; j < M; j++){
      int tmp = abs(c[j] - a[i]) + abs(d[j] - b[i]);
      if(min > tmp){
        min = tmp;
        pos = j;
      }
    }
    cout << pos + 1 << endl;
  }
}


Measured memory_bytes: 256
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <vector <ll>> matrix;

#define endl "\n"
#define mt make_tuple
#define mp make_pair

template <typename T1, typename T2>
bool umax(T1 &a, const T2&b) { return a < b ? a = b, 1 : 0;}
template <typename T1, typename T2> 
bool umin(T1 &a, const T2 &b) {return a > b ? a = b, 1 : 0;}
template <typename T>
T sqr(T a) {return a * a;}
const int mod = 1000000007;
template <typename T1, typename T2>
void modadd(T1 &a, const T2 &b) {
    a += b;
    a %= mod;
}

mt19937 rng(20010709);
const int INF = 1000000001;
const int N = 1 << 21;

int n;
ll k;
matrix m;

matrix operator*(const matrix &a, const matrix &b);
matrix pow2(matrix a, ll power);

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

    cin >> n >> k;

    m.resize(n, vector <ll>(n));

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

    m = pow2(m, k);

    ll result = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            modadd(result, m[i][j]);
    }

    cout << result << endl;

    return 0;
}

matrix operator*(const matrix &a, const matrix &b) {
    assert(a[0].size() == b.size());
    matrix result(a.size(), vector <ll>(b[0].size()));

    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[0].size(); j++) {
            for (int k = 0; k < b.size(); k++)
                modadd(result[i][j], a[i][k] * b[k][j]);
        }
    }

    return result;
}

matrix pow2(matrix a, ll power) {
    if (power == 1)
        return a;

    matrix tmp = pow2(a, power / 2);
    tmp = tmp * tmp;

    if (power & 1)
        return tmp * a;
    return tmp;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

int ans[maxn];
int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
    //cin >> T;
    T = 1;
    for (int cs = 1; cs <= T; cs++) {
        string s;
        cin >> s;
        int n = s.length();
        int r = 0, l = 0;
        // int mx = 0;
        //dbg(n);
        for (int i = 0; i < n; i++) {
            if (s[i] == 'R') {
                r++;
                swap(r, l);
            }
            else {
                ans[i] += r;
                ans[i - 1] += l;
               // dbg4(ans[i], ans[i - 1], l, r);
                l = r = 0;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == 'L') {
                r++;
                swap(r, l);
            }
            else {
                ans[i] += r;
                ans[i + 1] += l;
                l = r = 0;
            }
        }

        for (int i = 0; i < n; i++) {
            if (i > 0) cout << " ";
            cout << ans[i];
        }
    }

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  bool flag = false;
  for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= 9; j++){
      if(j * i == N) flag = true;
    }
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll                long long int
#define ld                long double
#define pb                push_back
#define pf                push_front
#define ppb               pop_back
#define ppf               pop_front
#define sz                size()
#define pi                acos(-1.0)
#define mod               1000000007
#define F                 first
#define S                 second
#define C                 continue
#define G                 goto done
#define maxe              max_element
#define mine              min_element
#define min3(a,b,c)       min(a,min(b,c))
#define max3(a,b,c)       max(a,max(b,c))
#define min4(a,b,c,d)     min(a,min(b,min(c,d)))
#define max4(a,b,c,d)     max(a,max(b,max(c,d)))
#define mem(a,b)          memset(a,b,sizeof(a))
#define all(a)            (a).begin(),(a).end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          ((a)*((b)/gcd(a,b)))
#define case(a)           cout<<"Case "<<(a)<<": "
#define point(a)          fixed<<setprecision(a)
#define get(a)            for(auto &x:a) cin>>x
#define print(a)          for(auto x:a) cout<<x<<" "; cout<<endl
#define see(x)            cout<<#x<<" = "<<x<<endl
#define uniq(a)           sort(all(a)); (a).erase(unique((a).begin(),(a).end()),(a).end())
#define big(a)            transform((a).begin(),(a).end(),(a).begin(),::toupper)
#define small(a)          transform((a).begin(),(a).end(),(a).begin(),::tolower)
#define ischar(a)         (('a'<=a&&a<='z')('A'<=a&&a<='Z'))
#define isvowel(a)        (a=='a'||a=='e'||a=='i'||a=='o'||a=='u'||a=='A'||a=='E'||a=='I'||a=='O'||a=='U')
#define fast              ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define tc                int test; cin>>test; while(test--)
using namespace std;
int main()
{
    ll a,b; cin>>a>>b;
    if(a>=1 && a<=9 && b>=1 && b<=9) cout<<a*b;
    else cout<<"-1";
}




















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

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	int n = s.size();
	vector<vector<int> > dp(n+1, vector<int>(8, -1e8));
	dp[0][0] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i && j < 8; j++){
			for(int k = 0; k < 8; k++){
				if(dp[i-j][k] < 0) continue;
				if(s.substr(i-j-k, k) == s.substr(i-j, j)) continue;
				dp[i][j] = max(dp[i][j], dp[i-j][k] + 1);
			}
		}
	}
	int res = 0;
	for(int i = 0; i < 8; i++){
		res = max(res, dp[n][i]);
	}
	cout << res << '\n';
}

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

int main() {
    int N,M;
    cin>>N>>M;
    priority_queue<int>q;
    for(int i=0;i<N;i++){
        int num;
        cin>>num;
        q.push(num);
    }
    for(int i=0;i<M;i++){
        int k=q.top();
        q.pop();
        k=k/2;
        q.push(k);
    }
    long long total=0;
    while(!q.empty()){
        int k=q.top();
        total+=(long long)k;
        q.pop();
    }
    cout<<total;
    return 0;
}

Measured memory_bytes: 892
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  string s;
  ll n,k,need;
  cin >> s >> k;
  n = s.size();
  for(auto &c:s){
    need = 'z' - c + 1;
    if(c != 'a' && need<=k){
      c = 'a';
      k -= need;
    }
  }
  k %= 26;
  for(int i=0;i<k;i++){
    if(s[n-1]=='z') s[n-1] = 'a';
    else s[n-1]++;
  }
  cout << s << endl;
}


Measured memory_bytes: 592
// AOJ 2176: For the Peace
// 2017.12.15 bal4u@uu

#include <stdio.h>
#include <string.h>

#define ABS(a)  ((a)>=0?(a):-(a))

int pool[10003], sz;
int *c[101], m[101], s[101];
char buf[50003], *p;

int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	p++;
	return n;
}

int main()
{
	int n, d, i, j, k, max, max2, f, g;

	while (fgets(p=buf, 15, stdin) && *p != '0') {
		n = getint(), d = getint();

		sz = 0;
		for (i = 0; i < n; i++) {
			fgets(p=buf, sizeof(buf), stdin);
			m[i] = getint(), s[i] = 0;
			c[i] = pool + sz;
			for (j = 0; j < m[i]; j++) c[i][j] = k = getint(), s[i] += k;
			sz += m[i];
		}

		while (sz) {
			max = max2 = 0;
			for (i = 0; i < n; i++) {
				if (s[i] >= max) max2 = max, max = s[i];
				else if (s[i] > max2) max2 = s[i];
			}

			f = 0;
			for (i = 0; i < n; i++) {
				while (m[i] > 0) {
					g = c[i][m[i]-1];
					if (max - (s[i] - g) > d) break;
					m[i]--, s[i] -= g, f = 1, sz--;
				}
			}
			if (f) continue;

			for (i = 0; i < n; i++) {
				if (s[i] == max) {
					while (m[i] > 0) {
						g = c[i][m[i]-1];
						if (ABS(s[i] - g - max2) > d) break;
						m[i]--, s[i] -= g, f = 1, sz--;
					}
				}
			}
			if (!f) break;
		}
		puts(sz ? "No" : "Yes"); 
	}
	return 0;
}

Measured memory_bytes: 1684
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

ans=0
for i in range(0,N):
    data=Z_algorithm(S)
    for j in range(0,len(data)):
        ans=max(min(data[j],j),ans)
    S=S[1:]
print(ans)

Measured memory_bytes: 52060
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
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 (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> tri;
typedef pair<double,double> point;
const ll MAX = 30000;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b;
    cin >> n >> a >> b;
    if (abs(a-b)%2 == 0){
        PRINT(abs(a-b)/2);
    }
    else{
        PRINT(min(((a-1)+(b-1)+1)/2,(n-a+n-b+1)/2));
    }
}


Measured memory_bytes: 3620
#include<stdio.h>
typedef long long ll;
int main(){
    ll x,ans_a,ans_b;
    ll a,b;
    
    scanf("%lld",&x);
    for(a = -200; a <= 200; a++){
        for(b = -200; b <= 200; b++){
            if((a*a*a*a*a) - (b*b*b*b*b) == x){
                ans_a = a;
                ans_b = b;
                break;
            }
        }
    }
    printf("%lld %lld\n",ans_a,ans_b);
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

vector<pii> edge[50];
bool visited[50];

int main() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge[a].eb(mp(b, i));
    edge[b].eb(mp(a, i));
  }

  int ans = 0;
  rep(i, m) {
    memset(visited, false, sizeof(visited));
    int cnt = 1;
    queue<int> q;
    q.push(0);
    visited[0] = true;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      rep(j, edge[cur].size()) {
        int next = edge[cur][j].F;
        int idx = edge[cur][j].S;
        if (idx == i || visited[next]) continue;
        visited[next] = true;
        q.push(next);
        cnt++;
      }
    }
    if (cnt != n) ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int SIZE_R;
    vector<Monoid> dat;
    
    SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, UNITY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update a, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get [a, b), a and b are 0-indexed */
    Monoid get(int a, int b) {
        Monoid vleft = UNITY, vright = UNITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }                                                                                                              
        return F(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            cout << (*this)[i];
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};

int solve(int N, int K) {
    const int MAX = 510000;
    auto func = [&](int a, int b) { return max(a, b); };
    SegTree<int> seg(MAX, func, 0);
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        int left = max(0, a - K);
        int right = min(MAX, a + K + 1);
        int val = seg.get(left, right);
        seg.update(a, val + 1);
    }
    return seg.get(0, MAX);
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << solve(N, K) << endl;
}


Measured memory_bytes: 7468
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
AA = sorted(A)
BB = sorted(B)
if N % 2 == 1:
    MIN = AA[N//2]
    MAX = BB[N//2]
    print(MAX-MIN+1)
else:
    MIN1 = AA[N//2 -1]
    MIN2 = AA[N//2]
    MAX1 = BB[N//2-1]
    MAX2 = BB[N//2]
    MIN = MIN1+MIN2
    MAX = MAX1+MAX2
    print(MAX-MIN+1)




Measured memory_bytes: 30164
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long int ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int const MOD = 1000000007;

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

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

    if(s == n) {
        cout << n + 1 << endl;
        return 0;
    }

    for(int i=2; i<=sqrt(n); i++) {
        ll t = n;
        ll b_k = 0;
        while(t != 0) {
            b_k += t % i;
            t /= i;
        }
        if(b_k == s) {
            cout << i << endl;
            return 0;
        }
    }

    repr(i, sqrt(n), 1) {
        ll b;
        if((n-s) % i != 0) continue;
        else b = (n-s) / i + 1;

        ll q = n - b * i;
        if(0 <= q && q < b && i != b) {
            cout << b << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

const long long mod = 1000000007;

int main() {
  string s;
  cin >> s;

  int n = s.length();

  int ans;
  string s2 = s;
  int temp = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (s[i] != '0') {
        temp++;
      }
    } else {
      if (s[i] != '1') {
        temp++;
      }
    }
  }
  ans = temp;

  temp = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (s[i] != '1') {
        temp++;
      }
    } else {
      if (s[i] != '0') {
        temp++;
      }
    }
  }

  ans = min(ans, temp);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
money  = 1000
stock = 0
min_price = a[0]
max_price = a[0]
is_first_time_of_drop = False
for i in range(1, n):
    if a[i] > max_price:
        max_price = a[i]
        is_first_time_of_drop = True
        if i == n - 1:
            money = (money // min_price) * max_price + money % min_price
    elif a[i] == max_price:
        if i == n - 1:
            money = (money // min_price) * max_price + money % min_price
        continue
    else:
        if is_first_time_of_drop:
            money = (money // min_price) * max_price + money % min_price
            min_price = a[i]
            max_price = a[i]
            is_first_time_of_drop = False
        else:
            if a[i] < min_price:
                min_price = a[i]
                max_price = a[i]
            elif a[i] == min_price:
                continue
            else:
                is_first_time_of_drop = True
print(money)

Measured memory_bytes: 9244