akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#define sz(x) ((ll)(x).size());
#define pb push_back;
#define all(x) (x).begin(),(x).end()
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

ll euclid(ll a, ll b ){
ll temp;
if( a < b ) { temp = a; a = b; b = temp; }
if( b < 1 ) return -1;
if( a % b == 0 ) return b;
return euclid( b, a % b );
}

int main(){
    ll N, X; cin >> N >> X;
    vll d(N);
    for(int i=0; i<N; i++){
        ll a; cin >> a;
        d[i] = abs(X - a);
    }
    if(N == 1){
        cout << d[0];
    }else{
        ll n = euclid(d[0],d[1]);
        for(int i=2; i<N; i++){
            n = euclid(n, d[i]);
        }
        cout << n;
    }
}

Measured memory_bytes: 1024
# coding: utf-8

# https://atcoder.jp/contests/abc089/tasks/abc089_c
# 12:34-12:50 done


def main():
    N = int(input())
    S = [None] * N
    for i in range(N):
        S[i] = input()[0]
    
    march = {s: 0 for s in "MARCH"}

    for s in S:
        if s in "MARCH":
            march[s] += 1
    
    march_filter = []
    for k, v in march.items():
        if v > 0:
            march_filter.append(v)
    
    n = len(march_filter)

    if n < 3:
        return 0

    members = []

    def rec(i, limit, member):
        if i == limit:
            if len(member) == 3:
                members.append(member)
            return None

        member_1 = member[:]
        member_2 = member[:]
        member_1.append(i)

        rec(i+1, n, member_1)
        rec(i+1, n, member_2)

    rec(0, n, [])

    ans = 0
    for member in members:
        tmp = 1
        for m in member:
            tmp *= march_filter[m]
        ans += tmp
    
    return ans


print(main())


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

int main(){
    int N,R;
    cin >> N >> R;
    if(N >= 10) cout << R << endl;
    else cout << R + 100*(10-N) << endl;
    return 0;
}

Measured memory_bytes: 256
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    lst = [0 for _ in range(n)]
    lst2 = []
    flag = 0
    for _ in range(k):
      i = int(input())
      if not i:
        flag = 1
      else:
        lst[i - 1] = 1
    l = -1
    r = -1
    for i in range(n):
      if lst[i] == 0:
        if r != -1:
          lst2.append((l,r))
          l = -1
          r = -1
      else:
        if l == -1:
          l = i
          r = i
        else:
          r += 1
    else:
      if r != -1:
        lst2.append((l,r))
    ans = 0
#    print(lst)
#    print(lst2)
    if not flag:
      for t in lst2:
        ans = max(ans,t[1] - t[0] + 1)
    else:
      for i in range(len(lst2)):
        if i == 0:
          ans = max(ans,lst2[0][1] - lst2[0][0] + 1)
        elif lst2[i][0] - lst2[i - 1][1] == 2:
          ans = max(ans,lst2[i][1] - lst2[i - 1][0] + 1)
        else:
          ans = max(ans,lst2[i][1] - lst2[i][0] + 1)
    print(ans)
  except EOFError:
    break


Measured memory_bytes: 8436
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val t = Array.fill(n)(sc.nextInt())
  val m = sc.nextInt()
  val sx = Array.fill(m)((sc.nextInt()-1, sc.nextInt()))
  val sum = t.sum
  for ((s, x) <- sx) {
    println(sum - t(s) + x)
  }
}


Measured memory_bytes: 55812
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.14159265
int main()
{
    double a,b,x;
    scanf("%lf %lf %lf",&a,&b,&x);
    getchar();
    int volume = a*a*b;
    if(volume==x){
        printf("%.10f\n",0);
    }else{
        if(2*x>=a*a*b){
            double m = a;
            double n = 2*(b-x/(a*a));
            double angle = atan2(n,m)* 180 / PI;
            printf("%.10lf\n",angle);
        }
        else{
            double m = b;
            double n = 2*x/(a*b);
            double angle = atan2(m,n)* 180 / PI;
            printf("%.10lf\n",angle);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int n, t;
	cin >> n >> t;
	vector<int> v(n);
	int dif = 0, mi;
	for(int i = 0; i < n; i++) {
		cin >> v[i];
		if(i == 0) mi = v[i];
		else {
			dif = max(dif, v[i] - mi);
			mi = min(mi, v[i]);
		}
	}
	mi = 1 << 30;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		mi = min(v[i], mi);
		if(mi + dif == v[i]) ans++;
	}
	cout << ans << endl;
	return 0;	
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>

int main(void)
{
  std::string str;
  std::cin >> str;

  size_t min_step = str.size();
  for(char c = 'a'; c <= 'z'; ++c){
    std::string log = str;
    if(std::find(log.begin(), log.end(), c) == log.end()){ continue; }
    size_t step = 0;
    std::string uniq = log;
    while(std::unique(uniq.begin(), uniq.end()) != uniq.begin()+1){
      step += 1;
      std::unordered_set<size_t> emp;
      for(size_t i = 0, end=log.size(); i < end; ++i){
        if(log[i] == c){
          if(i != 0){ emp.insert(i-1); }
        }
      }
      for(auto i: emp){
        log[i] = c;
      }
      log.erase(log.end()-1);
      uniq = log;
    }
    if(step < min_step){ min_step = step; }
  }
  std::cout << min_step << std::endl;

  return 0;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i +100*j + 50*k == X:
                count += 1

print("{}".format(count))

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

template< typename T >
class CumulativeSum
{
public:
    CumulativeSum() {}
    CumulativeSum(int sz) : m_Data(sz, T(0)) {};

    void Init(int sz) { m_Data.assign(sz, T(0)); }

    // k に x を加える O(1)
    void Add(int k, T x) {
        assert(static_cast<int>(m_Data.size()) >= k);
        if(static_cast<int>(m_Data.size()) <= k) { m_Data.push_back(x); }
        else { m_Data[k] = (m_Data[k] + x); }
    }

    // 累積和の構築 O(m_Data.size())
    void Build() {
        for(int i = 1; i < static_cast<int>(m_Data.size()); i++) {
            m_Data[i] = (m_Data[i] + m_Data[i - 1]);
        }
    }

    // 区間 [0, k] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int k) {
        if(k < 0) { return T(0); }
        return (m_Data[min(k, static_cast<int>(m_Data.size()) - 1)]);
    }

    // 区間 [l, h] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int l, int h) {
        return (this->Query(h) - this->Query(l-1));
    }
private:
    vector< T > m_Data;
};

int N, K;
vector<int> V;

signed main()
{
    cin >> N >> K;
    V.resize(N);
    REP(i, N) {
        cin >> V[i];
    }

    int ans = 0;

    for(int lb = 0; lb <= K; ++lb) {
        for(int rb = 0; rb <= (K - lb); ++rb) {
            int remain = K - lb - rb;       // 取り除ける数
            vector<bool> isExist(N, true);  // まだあるなら true
            vector<int> cur;                // 取った宝石

            for(int i = 0; i < lb; ++i) {
                if(lb >= N) { break; }
                cur.push_back(V[i]);
                isExist[i] = false;
            }
            for(int i = 0; i < rb; ++i) {
                int ind = N - 1 - i;
                if(ind < 0) { break; }
                if(isExist[ind]) {
                    cur.push_back(V[ind]);
                    isExist[ind] = false;
                }
            }

            DBG("lb: %lld rb: %lld remain: %lld\n", lb, rb, remain);

            SORT(cur);
            int cand = 0;
            REP(i, cur.size()) {
                DBG("  cur[%lld]: %lld\n", i, cur[i]);
                if(remain > 0 && cur[i] < 0) {
                    remain--;
                    continue;
                }
                cand += cur[i];
            }

            DBG("cand: %lld\n", cand);

            ans = max(ans, cand);
        }
    }

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


Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  As = map(int, input().strip().split())
  for A in As:
    if A%2 == 0:
      if (A%3==0 or A%5==0):
        continue
      else:
        print('DENIED')
        return
  print('APPROVED')

if __name__=='__main__':
  main()

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

struct CombInv{
                const long long MOD = 1e9+7;

                //nPrを返す
                long long Permutation(long long n, long long r){
                        long long tmp = 1;
                        long long i = n;
                        while(i!=n-r){
                                tmp *= i;
                                tmp %= MOD;
                                --i;
                        }
                        return tmp;
                }

                //x!を返す
                long long Factorial(long long x){
                        long long tmp = 1;
                        long long i = 1;
                        while(i<=x){
                                tmp *= i;
                                tmp %= MOD;
                                ++i;
                        }
                        return tmp;
                }

                //x^pを返す
                long long FastPow(long long x, long long p){
                        if(p==1) return x;
                        if(p%2==0){
                                long long sr = FastPow(x, p/2);
                                return (sr*sr)%MOD;
                        }else{
                                long long sr = FastPow(x, (p-1)/2);
                                return ((x*sr)%MOD*sr)%MOD;
                        }
                }

                //chi/parをMODで割った余りを返す
                long long FractionalRemainder(long long par, long long chi=1){
                        return (chi%MOD*FastPow(par, MOD-2))%MOD;
                }

                //nCrを返す
                long long Combination(long long n, long long r){
                        return (Permutation(n,r)*(FractionalRemainder(Factorial(r))))%MOD;
                }
        };

int main(){
        ll N,ans=0;
        cin >> N;
        CombInv c;
        ans = (c.FastPow(10,N)+c.FastPow(8,N))%mod;
        ans -= (2*c.FastPow(9,N))%mod;
        if(ans<0) ans += mod;
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
    int M=1000005;
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    vector<int> cnt(M);
    for(int x:a){
        if(cnt[x]!=0){
            cnt[x]=2;
            continue;
        }
        for(int i=x;i<M;i+=x)cnt[i]++;
    }
    int ans=0;
    for(int x:a){
        if(cnt[x]==1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8008
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  ll N,K;
  cin >> N >> K;
  vector<ll> a(N),b(N);
  rep(i,N) cin >> a[i] >> b[i];
  ll sum = 0;
  vector<pair<ll,ll>> vec(0);
  rep(i,N)
  {
    vec.push_back(make_pair(a[i],b[i]));
  }
  sort(ALL(vec));
  rep(i,N)
  {
    sum += vec[i].second;
    if(sum >= K)
    {
      cout << vec[i].first << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 6812
#include <iostream>
using namespace std;
 
int main()
{
    int abc[4];
    int tmp;
     
    cin>>abc[0]>>abc[1]>>abc[2];
    for( int i=0; i<2; i++ ) {
        for( int j=i+1; j<3; j++ ) {
            if( abc[j] < abc[i] ) {
                tmp=abc[i];
                abc[i]=abc[j];
                abc[j]=tmp;     
            }
        }
    }
 
    cout <<abc[0]<<" "<<abc[1]<<" "<<abc[2]<<endl;
      
    return 0;
}

Measured memory_bytes: 1164
while True:
    H,W = (int(x) for x in input().split())
    
    if H == 0 and W == 0:
        break

    for i in range(H):
        for j in range(W):
            if (i % 2 == 1 and j % 2 == 1) or (i % 2 == 0 and j % 2 == 0):
                print ('#', end='')
            else:
                print ('.', end='')
        print ('')
    print ('')


Measured memory_bytes: 7024
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    sidelist = dict()

    for aa in a:
        if aa not in sidelist:
            sidelist[aa] = 1
        else:
            sidelist[aa] += 1

    side_a = 0
    side_b = 0

    for s in sidelist:
        if sidelist[s] >= 4 and s > side_a:
            side_a = s
            side_b = s
        elif sidelist[s] >= 2:
            if s > side_a:
                side_b = side_a
                side_a = s
            elif s > side_b:
                side_b = s

    print(side_a*side_b)


Measured memory_bytes: 17960
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> A(N),B(N),C(N-1);
  int ans = 0;
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  for(int i=0;i<N;i++){
    cin>>B.at(i);
    ans+=B.at(i);
  }
  for(int i=0;i<N-1;i++){
    cin>>C.at(i);
  }
  for(int i=0;i<N-1;i++){
    if(A.at(i)+1==A.at(i+1)){
      ans+=C.at(A.at(i)-1);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val N = nextInt()
    val ans = IntArray(N) { nextInt() }.toCountMap().count { it.value % 2 == 1 }
    println(ans)
}

fun IntArray.toCountMap(): Map<Int, Int> {
    return this.groupBy { it }.mapValues { it.value.size }
}

Measured memory_bytes: 64664
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
	
  	string s;
	cin >> s;
	ll len = s.size();

	map<char, ll> mp;
	for(ll i = 0; i < len; i++) mp[s[i]]++;
	if(len < 26){
		char ans;
		for(char c = 'a'; c <= 'z'; c++){
			if(mp[c] == 0){
				ans = c;
				break;
			}
		}
		cout << s + ans << endl;
	}else{
    ll pos = -1;
    for(ll i = len-2; i >=0; i--){
      if(s[i] < s[i+1]){
        pos = i;
        break;
      }
    }
    if(pos == -1) cout << pos << endl;
    else{
      string t = s.substr(0, pos);
      ll pos2 = pos+1;
      for(ll i = pos2; i < len; i++){
        if(s[i] < s[pos2] && s[i] > s[pos]) pos2 = i;
      }
      t += s[pos2];
      cout << t << endl;
    }
  }
	return 0;
}

Measured memory_bytes: 256
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

int a, b, c, x, y;

void init()
{
}

void solve()
{
    int ans = 0;
    if(a + b > 2*c){
        int n = min(x, y);
        ans += n * 2 * c;
        x -= n;
        y -= n;
    }
    if(x > 0 && a > 2*c){
        ans += x * 2 * c;
        x -= x;
        y -= x;
    }
    if(y > 0 && b > 2*c){
        ans += y * 2 * c;
        x -= y;
        y -= y;
    }
    if(x > 0) ans += x * a;
    if(y > 0) ans += y * b;
    cout << ans << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a >> b >> c >> x >> y;
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> v;
    v.reserve(n*n);
    unsigned long long int total = 0;
    for(int i=0;i<n*n;i++) {
        int t;
        cin >> t;
        v.push_back(t);
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<i;j++) {
            bool flag = false;
            for(int k=0;k<n;k++) {
                if(i==k || j==k) continue;
                int t = v[i * n + j] - v[i * n + k] - v[k * n + j];
                if (t > 0) {
                    cout << -1 << endl;
                    return 0;
                }
                else if(t == 0) {
                    flag = true;
                }
            }
            if (!flag) total += v[i * n + j];
        }
    }
    cout << total << endl;
}

Measured memory_bytes: 640
def inpl(): return [int(i) for i in input().split()]
N, A, B, C, D = inpl()
for k in range(N+1):
    j = N-1-k
    if D*k - C*j >= B-A >= C*k - D*j:
        print('YES')
        break
else:
    print('NO')

Measured memory_bytes: 3060
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int cnt = 0;
    int mini = INF;
    int sum = 0;
    rep(i, n){
        sum += abs(a[i]);
        if(a[i] < 0){
            cnt++;
        }
        mini = min(mini, abs(a[i]));
    }

    if(cnt % 2){
        sum -= mini * 2;
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int main(){
    ll n,m,sx=0,sy=0;
    cin >> n >> m;
    for(int i = 0;i < n;i ++){
        ll x;
        cin >> x;
        sx += (2*i+1-n)*x;sx %= mod;
    }
    for(int i = 0;i < m;i ++){
        ll y;
        cin >> y;
        sy += (2*i+1-m)*y;sy %= mod;
    }
    cout << (sx*sy)%mod << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
//コンビネーションを10^9+7で割った余りを求める
const int MOD=1000000007;
int main(){
    
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    
   //FILE *fp;
   //fp = fopen("~/Downloads/testcase_12.txt","r")
    vector<int> zo;
    int a=1;
    if(n==1){
        zo.push_back(a);
    }
    if(s[0]=='0'){
        zo.push_back(0);
    }
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1]){
            a++;
        }
        else{
            zo.push_back(a);
            a=1;
        }
        if(i==n-1){
            zo.push_back(a);
        }
    }
    int l=zo.size();
    vector<int> sum(l+1,0);
    for(int i=1;i<=l;i++){
        sum[i] = sum[i-1] + zo[i-1];
    }
    /*
    rep(i,l){
        //cout<<sum[i]<<" ";
        cout<<zo[i]<<endl;
    }
    cout<<endl;
    */
    int ans=0;

    for(int i=0;i<l+1;i+=2){
        int tmp = sum[min(l,i+2*k+1)]-sum[i];
        //cout<<tmp<<endl;
        ans = max(ans,tmp);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1272
import numpy as np
from collections import Counter
def f(lst):
    return np.cumsum([0] + lst)

n = int(input())
lst = list(map(int,input().split()))
d = dict(Counter(f(lst)))

res = 0
for k,v in d.items():
    if v >= 2:
        res += (v*(v-1))//2
print(res)

Measured memory_bytes: 52828
#include<stdio.h>
#include <stdexcept>
#define MAX 100001

struct Process {
  char name[40];
  int time;
};

class Queue {
  Process ps[MAX];
  int head, tail;
  public:
    Queue() {
      head = 0;
      tail = 0;
    }
    void enqueue(Process p) {
      if (!isFull()) {
        ps[tail++] = p;
        tail = tail % MAX;
      } else {
        printf("%d %d\n", head, tail);
        printf("error is happened in enque\n");
        throw;
      }
    }
    Process dequeue() {
      if (!isEmpty()) {
        Process cp = ps[head++];
        head = head % MAX;
        return cp;
      } else {
        printf("error is happened in deque\n");
        throw;
      }
    }
    bool isFull() {
      return (tail % MAX) + 1 == head;
    }
    bool isEmpty() {
      return head == tail;
    }
};

int main() {
  int n, q;
  long long total = 0;
  Process p;
  Queue queue;
  scanf("%d %d", &n, &q);
  for ( int i = 0; i < n; i++ ) {
    scanf("%s %d", p.name, &p.time);
    queue.enqueue(p);
  }
  while (!queue.isEmpty()) {
    p = queue.dequeue();
    if (p.time <= q) {
      total += p.time;
      printf("%s %lld\n", p.name, total);
    } else {
      p.time -= q;
      total += q;
      queue.enqueue(p);
    }
  }
  return 0;
}


Measured memory_bytes: 6968
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define INF 10000000
using namespace std;
int n,m,x,t[14][14],mm=INF;


int main()
{

    cin>>n>>m>>x;
    vector<int> c(n);
    rep(i,n) {
        cin>>c[i];
        rep(j,m) cin>>t[i][j];
    }

    rep(i,1<<n){
        vector<int> d(m);
        int cost=0;
            rep(j,n){
                if((i>>j)&1) {
                    cost+=c[j];
                    rep(k,m) d[k]+=t[j][k];
                }
            }
            bool ok=true;
            rep(j,m) if(d[j]<x) ok =false;

        if(ok) mm=min(mm,cost);
    }

    if (mm!=INF) cout<<mm<<endl;
    else cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <sstream>
#include <set>
#include <map>
#define LLMAX 9223372036854775807

using namespace std;
using ll = long long;

int main() {
	ll argA, argB, argC, argD;
	cin >> argA >> argB >> argC >> argD;

	ll time = max(min(argB, argD) - max(argA, argC), 0LL);
	cout << time << endl;
}

Measured memory_bytes: 632
#include<map>
#include<list>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int x,y;
char a;
int main()
{
    while(a!='\n')
    {
        a=getchar();
        if(a=='C') x=1;
        if(a=='F'&&x==1) y=1;
    }
    if(x==1&&y==1) {cout<<"Yes";return 0;} 
	cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    int *V,*C;
    V = new int [N];
    C = new int [N];
    urept(i,0,N){
        cin >> V[i];
    }
    urept(i,0,N){
        cin >> C[i];
    }
    int count = 0;
    urept(i,0,N){
        if(V[i]-C[i]>0){
            count += (V[i]-C[i]);
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[505];
int ans[505];
vector<int> vec;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a-b<c) cout<<c-(a-b)<<endl;
    else cout<<0<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define cinf(x,n) for(int i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(int i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int main(){
	string s;
	int sum;
	while(true){
		cin >> s;
		if(s=="0")return 0;
		sum=0;
		rep(i,s.length()){
			sum+=s[i]-'0';
		}
		cout << sum << endl;
	}
}


Measured memory_bytes: 3184
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, k = map(int, input().split())
    s = input()

    f = '1'
    count = 0
    counts = []
    for st in s:
        if st == f:
            count += 1
        else:
            counts.append(count)
            f = str(int(f) ^ 1)
            count = 1

    counts.append(count)
    num = k*2+1

    ss = sum(counts[0:k*2+1])
    ans = ss
    for i in range(num, len(counts), 2):
        if ss > ans:
            ans = ss
        ss -= counts[i-num] + counts[i-num+1]
        ss += counts[i]
        if i+1 < len(counts):
            ss += counts[i+1]
    if ss > ans:
        ans = ss
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 44616
#入力はゼロ埋めした文字列で持つ
N, K = gets.split.map{|s| s.to_i.to_s(2).rjust(40,"0")}
A = gets.split.map{|s| s.to_i.to_s(2).rjust(40,"0")}

#dp[n桁目][未満フラグ] = 暫定最大値
dp = Array.new(40+1){Array.new(2){-1}}

dp[0][0] = 0

#各上からd桁目を走査(0-indexed)
0.upto(40-1) do |d|

  #(Aの上からd桁目)=1であるものの個数num
  num = 0
  A.each do |a|
    num += 1 if a[d] == "1"
  end

  #Xのd桁目が[0,1]であるときのf(x)のd桁目成分value
  value = [num*(2**(40-d-1)), (N.to_i(2)-num)*(2**(40-d-1))]

  #遷移dp[d][1]→dp[d+1][1]
  if dp[d][1] != -1
    dp[d+1][1] = [dp[d+1][1], dp[d][1] + value.max].max
  end

  #遷移dp[d][0]→dp[d+1][1]
  if dp[d][0] != -1
   if K[d] == "1"
      dp[d+1][1] = [dp[d+1][1], dp[d][0]+value[0]].max
   end
  end

  #遷移dp[d][0]→dp[d][0]
  if dp[d][0] != -1
    if K[d] == "1"
      dp[d+1][0] = [dp[d+1][0],dp[d][0]+value[1]].max
    else
      dp[d+1][0] = [dp[d+1][0],dp[d][0]+value[0]].max
    end
  end
end

puts [dp[40][0],dp[40][1]].max

Measured memory_bytes: 34204
//This disgusting code is wriiten by Juruo D0zingbear
//Please don't hack me! 0v0 <3
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}

// cf IO: I64d
// atcoder IO: ｌｌｄ
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int main(){
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for (int i=0;i<=n;i++){
		for (int j=0;j<=m;j++){
			int bl=i;
			int tot=bl*j+(n-bl)*(m-j);
			if (tot==k){
				printf("Yes\n");
				return 0;
			}
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N, M = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

wf = warshall_floyd(N, G)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # 辺があって、最短経路より長いなら使わない
        if G[i][j] != INF and G[i][j] > wf[i][j]:
            cnt += 1
print(cnt)


Measured memory_bytes: 3948
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] S = sc.next().toCharArray();
        int ans = 0;
        for (int i = 0; i < N-2; i++) {
            if (S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21972
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <intrin.h>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define __builtin_popcount __popcnt
#define N 200005
#define FH 400005
#define inf INT32_MAX
#define MOD 1000000007LL

using namespace std;
typedef long long ll;
typedef pair<int, int> pr;


inline void solve()
{
	int n;
	cin >> n;
	cout << n * n;
}



int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve();
}

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

typedef long long ll;

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  vector<int> ans;
  ans.push_back(a+b);
  ans.push_back(a+c);
  ans.push_back(b+c);
  printf("%d\n",*min_element(ans.begin(),ans.end()));
  return 0;
}


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

using namespace std;

typedef long long ll;

int main() {
  int a, b; cin >> a >> b;
  int cur = 1;
  int cnt = 0;
  while(true) {
    if(cur * a >= b) {
      break;
    }
    cur *= a;
  }
  int has = (cur - 1) / (a - 1);
  for(int i = 0; i <= 10; i++) {
    if(i * (a - 1) >= b - cur and i <= cur) {
      cout << has + i << '\n';
      return 0;
    }
  }
}

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

#define endl '\n'
#define ff first
#define ss second
#define pb pushback

typedef long long llong;
typedef pair<int, int> pii;

bool in_range(int a) {
	return a >= 1 && a <= 9;
}

void solve() {
	int a, b;
	cin >> a >> b;
	// cout << a << ' ' << b << endl;
	if (in_range(a) && in_range(b)) {
		cout << a * b;
	} else {
		cout << -1;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif
	solve();
}

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

#define MAX 200000

int N;
int A[MAX];

bool check( int x )
{
	typedef pair<int, int> P;
	vector<P> S;

	for( int i = 0; i < N - 1; i++ ) {
		if( A[i + 1] > A[i] ) {
			continue;
		}
		if( x <= 1 ) {
			return false;
		}
		int a = A[i + 1];
		while( S.size() && (*(S.end() - 1)).first > a ) {
			S.pop_back();
		}
		if( S.size() && (*(S.end() - 1)).first == a ) {
			(*(S.end() - 1)).second++;
		}
		else {
			S.push_back( make_pair( a, 1 ) );
		}
		while( (*(S.end() - 1)).second == x ) {
			int d = (*(S.end() - 1)).first;
			if( d == 1 ) {
				return false;
			}
			S.pop_back();
			if( S.size() && (*(S.end() - 1)).first == d - 1 ) {
				(*(S.end() - 1)).second++;
			}
			else {
				S.push_back( make_pair( d - 1, 1 ) );
			}
		}
	}
	return true;
}

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

	int l = 0;
	int r = N;
	while( r - l > 1 ) {
		int m = ( l + r ) / 2;
		if( check( m ) ) {
			r = m;
		}
		else {
			l = m;
		}
	}
	int ans = r;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define rep(i,a,b) for(int (i)=a;(i)<(int)(b);(i)++)
using ll = long long int ;

ll factral(ll a){
    if(a==0) return 1;
    if(a==1) return 1;
    else return a*factral(a-1);
}

ll gcd(ll a, ll b){
    ll tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    if(b==0) return a;
    else return gcd(b, a%b);
}
vector<int> update(vector<int> a){
    for(int i=0;i<a.size();i++){
        if(a[i]==0){
            a[i] = 1;
            break;
        }
        else a[i] = 0;
    }
    return a;
}

int main(){
    int N,sum;
    cin >> N;
    vector<int> A(N,0),B(N,0);
    rep(i,1,N) cin >> A[i];
    rep(i,1,N){
        B[A[i]-1] +=1;
    }
    for(auto x:B) cout <<x << endl;
}

Measured memory_bytes: 4844
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        a: isize, b: isize, 
    }
    println!("{}", [a+b, a-b, a*b].iter().max().unwrap());
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


Measured memory_bytes: 2104
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, p;
    int piece, num;
    cin >> a >> p;
    piece = a * 3 + p;
    num = piece / 2;
    cout << num << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{   
    ll N, K; 
    cin >> N >> K;
    if((N+1)/2 >= K){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }

    return 0;
}

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

int main(){
    string mas;
    bool judge;
    while(cin >> mas){
        judge = false;
        for(int i=0;i<9;i+=3){
            if(mas.substr(i,3) == "ooo"){
                cout << "o" << endl;
                judge = true;
                break;
            }
            if(mas.substr(i,3) == "xxx"){
                cout << "x" << endl;
                judge = true;
                break;
            }
        }
        for(int i=0;i<3;i++){
            if(mas[i] == mas[i+3] && mas[i+3] == mas[i+6] && !judge && mas[i] != 's'){
                cout << mas[i] << endl;
                judge = true;
                break;
            }
        }
        if(mas[0] == mas[4] && mas[4] == mas[8] && !judge && mas[0] != 's') {
            cout << mas[0] << endl;
            judge = true;
        }
        else if(mas[2] == mas[4] && mas[4] == mas[6] && !judge && mas[2] != 's'){
            cout << mas[2] << endl;
            judge = true;
        }
        else if(!judge) cout << "d" << endl;
    }
}

Measured memory_bytes: 1188
#ifndef ___Class_RangeTree
#define ___Class_RangeTree

// ------ Includes ------ //
#include <limits>
#include <vector>
#include <algorithm>

template<typename Type> class RangeTree {
private:
	int size_;
	std::vector<std::vector<Type> > dat;
	std::vector<std::vector<int> > vl;
	inline int query_(int a, int b, Type x, int k, int l, int r, int e) {
		// Find range [a, b) : value < x : Now k-th node and the range is [l, r) and e integers below x in the range
		if (r <= a || b <= l || e == 0) return 0;
		if (a <= l && r <= b) return e;
		int lc = query_(a, b, x, k << 1, l, (l + r) >> 1, vl[k][e - 1]);
		int rc = query_(a, b, x, k << 1 | 1, (l + r) >> 1, r, e - vl[k][e - 1]);
		return lc + rc;
	}
public:
	RangeTree() : size_(0), dat(std::vector<Type>()) {};
	template<class T>
	RangeTree(T begin_, T end_) {
		int n = (end_ - begin_);
		for (size_ = 1; size_ < n; size_ <<= 1);
		dat.resize(size_ << 1);
		vl.resize(size_);
		for (int i = 0; i < n; i++) dat[i + size_].push_back(*(begin_ + i));
		for (int i = size_ - 1; i > 0; i--) {
			dat[i].resize(dat[i << 1].size() + dat[i << 1 | 1].size());
			vl[i].resize(dat[i].size());
			int cl = 0;
			for (int j = 0; j < dat[i].size(); j++) {
				if (j - cl == dat[i << 1 | 1].size() || (cl != dat[i << 1].size() && dat[i << 1][cl] < dat[i << 1 | 1][j - cl])) dat[i][j] = dat[i << 1][cl++];
				else dat[i][j] = dat[i << 1 | 1][j - cl];
				vl[i][j] = cl;
			}
		}
	}
	inline int size() { return size_; }
	inline int query(int l, int r, Type x) {
		// Find range [a, b) : value < x
		int ptr = lower_bound(dat[1].begin(), dat[1].end(), x) - dat[1].begin();
		return query_(l, r, x, 1, 0, size_, ptr);
	}
};

#endif

#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
int n, q, l, r, e;
int main() {
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	RangeTree<int> seg(a.begin(), a.end());
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d%d", &l, &r, &e); l--;
		int x1 = seg.query(l, r, min(a[l], a[r - 1]) - e);
		int x2 = seg.query(l, r, max(a[l], a[r - 1]) + e + 1);
		printf("%d\n", (r - l) - (x2 - x1));
	}
	return 0;
}

Measured memory_bytes: 32188
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 5.5e1+5;
int n, pa[N], pb[N], d[N], ans; vector<int> ea[N], eb[N];
void dfs(int x, int p, vector<int> *e, int *fa)
{ fa[x] = p; for(auto y:e[x]) if(y != p) dfs(y, x, e, fa); }
int solve()
{
    static int op[N], in[N], q[N]; static vector<int> e[N]; int ret = 0, l = 1, r = 0;
    for(int i = 1; i <= n; ++i) ret += op[i] = pa[i] != pb[i], in[i] = 0, e[i].clear();
    for(int i = 1; i <= n; ++i) if(!op[i]&&op[pa[i]]) return -1;
    for(int i = 1; i <= n; ++i) if(op[i])
    {
        if(op[pa[i]]) e[i].push_back(pa[i]), ++in[pa[i]];
        if(op[pb[i]]) e[pb[i]].push_back(i), ++in[i];
    }
    for(int i = 1; i <= n; ++i) if(op[i]&&!in[i]) q[++r] = i;
    while(l <= r)
    {
        int x = q[l++];
        for(auto y:e[x]) if(!--in[y]) q[++r] = y;
    }
    return r^ret?-1:ret;
}
int main()
{
    for(int T = read(); T--; )
    {
        n = read(), ans = 0; for(int i = 1; i <= n; ++i) ea[i].clear(), eb[i].clear(), d[i] = 0;
        for(int i = 1, x, y; i < n; ++i) x = read(), y = read(), ea[x].push_back(y), ea[y].push_back(x), ++d[x], ++d[y];
        for(int i = 1, x, y; i < n; ++i) x = read(), y = read(), eb[x].push_back(y), eb[y].push_back(x);
        dfs(1, 0, ea, pa), dfs(1, 0, eb, pb); for(int i = 1; i <= n; ++i) if(pa[i] != pb[i]) ans = n+1;
        if(ans > n)
            for(int i = 1; i <= n; ++i) if(d[i] == 1)
            {
                dfs(i, 0, eb, pb);
                for(int j = 1; j <= n; ++j) if(i != j)
                {
                    dfs(j, 0, ea, pa), pa[j] = i, pa[i] = 0;
                    int res = solve(); if(~res) ans = min(ans, res+1);
                }
            }            
        printf("%d\n", ans>n?-1:ans);  
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using lint=long long;
using namespace std;

int main()
{
	int N,M;
	int X[100010]={};
	
	cin >> N >> M;
	for(int i=0;i<M;i++)
		cin >> X[i];
	sort(X,X+M);
	
	int sub[100010]={};
	for(int i=0;i<M-1;i++)
		sub[i]=X[i+1]-X[i];
	sort(sub,sub+M-1);
	
	int ans=0;
	for(int i=0;i<M-N;i++)
		ans+=sub[i];
	
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1024
k,n=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)
ans=[]
n.times do |i|
  if i==n-1
    ans<<k+a[0]-a[i]
    next
  end
  ans<<a[i+1]-a[i]
end
puts k-ans.max


Measured memory_bytes: 17028
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def g(ab: list, ans: list, check: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    check[i] = False
    for j in ab[i]:
        if check[j]:
            ans[j] += ans[i]
            g(ab, ans, check, j)

def main():
    N, Q = map(int, input().split())
    ab = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    ans = [0] * N
    check = [True] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    g(ab, ans, check)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__': main()

Measured memory_bytes: 271380
import heapq
from collections import defaultdict, deque
t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + (2 - p % 2):
            heapq.heappush(hq, (cs + a + (2 - p % 2) * da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + (2 - p % 2)
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p % 3) * da
        if d[p // 3 + 1] > cs + b + (3 - p % 3) * da:
            heapq.heappush(hq, (cs + b + (3 - p % 3) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (3 - p % 3) * da
        if d[p // 5] > cs + c + (p % 5) * da:
            heapq.heappush(hq, (cs + c + (p % 5) * da, p // 5))
            d[p // 5] = cs + c + (p % 5) * da
        if d[p // 5 + 1] > cs + c + (5 - p % 5) * da:
            heapq.heappush(hq, (cs + c + (5 - p % 5) * da, p // 5 + 1))
            d[p // 5 + 1] = cs + c + (5 - p % 5) * da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)


Measured memory_bytes: 12052
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double EPS=1e-10;
double add(double a, double b)
{
	if(abs(a+b)<EPS*(abs(a)+abs(b))) return 0;
	return a+b;
}

int main()
{
	int n ; cin >> n ;
	while(n--)
	{
		double x[3],y[3]; for(int i=0;i<3;i++) cin >> x[i] >> y[i] ;
		double a=x[1]-x[0];
		double b=y[1]-y[0];
		double d=x[2]-x[1];
		double e=y[2]-y[1];
		double c=add(-add(x[1]*x[1],-x[0]*x[0])/2,-add(y[1]*y[1],-y[0]*y[0])/2);
		double f=add(-add(x[2]*x[2],-x[1]*x[1])/2,-add(y[2]*y[2],-y[1]*y[1])/2);
		double X=add(b*f,-c*e)/add(a*e,-b*d);
		double Y=add(c*d,-a*f)/add(a*e,-b*d);
		double r=sqrt( add( (X-x[0])*(X-x[0]),(Y-y[0])*(Y-y[0]) ) );
		cout << fixed << setprecision(3) << X  << ' ' << Y << ' ' << r << '\n';
	}
}

Measured memory_bytes: 1288
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	int n;
	cin>>n;
	
	vector<ll> mv;
	for(int i=0;i<n;i++){
		ll t;
		cin>>t;
		mv.push_back(t);
	}
	ll fir=mv[0];
	for(int i=1;i<(int)mv.size();i++){
		if(i%2==0)fir+=mv[i];
		else fir-=mv[i];
	}
	ll firans=fir/2;
	ll lasans=firans;
	vector<ll> mvans;
	mvans.push_back(lasans);
	for(int i=0;i<(int)mv.size()-1;i++){
		lasans=mv[i]-lasans;
		mvans.push_back(lasans);
	}
	for(int i=0;i<(int)mvans.size();i++){
	if(i)cout<<" ";
	cout<<2*mvans[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3060