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

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

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

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

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

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

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

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      nn: usize,
    }
    for h in 1..3501 {
        for n in 1..3501 {
            let a = nn * n * h;
            if 4*h*n > nn*(h+n) {
                let b = 4*h*n - nn * (h + n);
                if a%b == 0 {
                    let w = a/b;
                    println!("{} {} {}", h, n, w);
                    debug!(nn, (4*n*h*w)/(n*w + h*w + n*h));
                    return;
                }
            }
        }
    }
}


Measured memory_bytes: 4352
def PrimeDecomp2(N):
    if N==1:
        return [1],[1],1
    else:
        I = 2
        PrimeDec = []
        PrimeCnt = []
        DivCount = 1
        while I*I<=N:
            Cnt = 0
            while N%I==0:
                N //= I
                Cnt += 1
            if Cnt>=1:
                PrimeDec.append(I)
                PrimeCnt.append(Cnt)
                DivCount *= (Cnt+1)
            I += 1
        if N>=2:
            PrimeDec.append(N)
            PrimeCnt.append(1)
            DivCount *= 2
        return PrimeDec,PrimeCnt,DivCount

N,P = (int(T) for T in input().split())
PrimeDec,PrimeCnt,_ = PrimeDecomp2(P)
Total = 1
for TP in range(0,len(PrimeCnt)):
    Total *= [1,PrimeDec[TP]**(PrimeCnt[TP]//N)][PrimeCnt[TP]>=N]
print(Total)

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

int main(){
  ll a,b;cin>>a>>b;
  if(a==0||b==0){
    cout<<"Zero\n";
    return 0;
  }
  if((a>0&&b<0)||(a<0&&b>0)){
    cout<<"Zero\n";
    return 0; 
  }
  if(a>0&&b>0){
    cout<<"Positive\n";
    return 0;
  }
  if(a<0&&b<0){
    switch((b-a)%2){
      case 0:
        cout<<"Negative\n";
        break;
      case 1: 
        cout<<"Positive\n";
        break;
    }
  }
}

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n+2,0);
    REP(i,n) cin>>a[i];

    int m=0;
    for(int i=n;i>0;i--){
        int sum=0;
        for(int j=2;j*i<=n;j++){
            sum+=a[j*i];
        }
        a[i]=(sum^a[i])&1;
        m+=a[i];
    }
    cout<<m<<endl;
    REP(i,n){
        if(a[i]) cout<<i<<" "<<endl;
    }
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }

int N,t,ans;
int x[100];
int main(){
  cin>>N; CINA(x,N);
  sort(x,x+N);
  ans=0; REP(i,N){ ans+=pow(x[i]-x[0],2);}
  if(ans>0){
    for(int p=x[0]+1;p<=x[N-1];++p){
      t = 0;
      REP(i,N){ t += pow(x[i]-p,2);}
      if(t<ans){ans=t; if(ans==0){break;}}
      else{break;}
    }
  }
  cout << ans <<"\n";
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    ll N, A, B; cin >> N >> A >> B;
    ll C = N / (A+B);
    ll ans = C * A;
    N %= (A+B);
    ans += min(A, N);
    cout << ans << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 384
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	/** 数値を英語の数字に変換するための配列 */
	private static final String[] NUMBERS = { "", "One", "Two", "Three", "Four" };

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			System.out.println(NUMBERS[(int) IntStream.range(0, n).mapToObj(i -> scanner.next()).distinct().count()]);
		}
	}
}


Measured memory_bytes: 28500
#include <bits/stdc++.h>
using namespace std;
#define FAST std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define fr(i,n) for(int i=0;i<n;i++)
#define int long long int
signed main() 
{
    FAST
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n,k;
    cin>>n>>k;
    std::vector<int> v(n);
    fr(i,n) cin>>v[i];
    std::vector<std::vector<int> > dp;
    std::vector<int> row(k+1,0);
    fr(i,n+1) dp.pb(row);
    dp[0][0]=1;

    for(int i=1;i<=n;i++)
    {
        int length=v[i-1]+1;
        int sum=0;
        fr(j,k+1)
        {
            sum=(sum+dp[i-1][j])%mod;
            if(j-length>=0)
            {
                sum=(sum+mod-dp[i-1][j-length])%mod;
            }
            dp[i][j]=sum;
        }
    }
    cout<<dp[n][k]%mod;
    // fr(i,n+1)
    // {
    //     fr(j,k+1)
    //     cout<<dp[i][j]<<" ";
    //     cout<<endl;
    // }

    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define vc vector
#define sz(v) (int)(v).size()
#define pb push_back
#define FF first
#define SS second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define pll pair<ll,ll>
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
typedef long double f80;
#define endl '\n'

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
char s[N];
bool x[N];

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	fr(i, 1, 2 * n) {
		cin >> s[i];
	}
	int ans = 1;
	fr(i, 1, n) {
		ans = (ans * 1LL * i) % mod;
	}
	s[0] = 'W';
	s[2 * n + 1] = 'W';
	fr(i, 0, 2 * n) {
		if(s[i] != s[i + 1])
			x[i] = 1;
	}
	int cl = 0, cr = 0, val = 0;
	bool pos = 1;
	fr(i, 1, 2 * n) {
		if(x[i - 1]) {
			cl++;
			val++;
		}
		else {
			x[i] ^= 1;
			cr++;
			if(!val) pos = 0;
			ans = (ans * 1LL * val) % mod;
			val--;
		}
	}
	if(!pos || (cl != cr && cl != n)) {
		cout << 0;
		return 0;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

struct UnionFind{
  vector<int> d;
  UnionFind(int n) : d(n, -1){}
  int find(int x){
    if(d.at(x) < 0) return x;
    return d.at(x) = find(d.at(x));
  }
  bool unite(int x, int y){
    x = find(x); y = find(y);
    if(x == y) return false;
    if(d.at(x) > d.at(y)) swap(x, y);
    d.at(x) += d.at(y);
    d.at(y)= x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d.at(find(x)); }
};

int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> vp(m);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    vp.at(i) = {a, b};
  }
  sort(ALL(vp));
  vp.push_back({1e6, 1e7});
  priority_queue<int> q;
  int index = 0;
  int ans = 0;
  rep(i, n){
    if(q.size() > 0){
      int now = q.top(); now *= -1;
      if(now == i){
        ans++;
        while(!q.empty()) q.pop();
      }
    }
    while(i == vp.at(index).first){
      q.push(vp.at(index).second*-1);
      index++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
	ll n;
	cin >> n;
	ll ans = 0;
	for(ll i = 1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ans = i;
		}
	}
	cout<<n/ans+ans-2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

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

Measured memory_bytes: 888
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        fac = new long[h + w + 1];
        inv = new long[h + w + 1];
        fac[0] = inv[0] = 1;
        for (int i = 1; i <= h + w; i++) {
            fac[i] = fac[i - 1] * i % 1000000007;
            inv[i] = powAndMod(fac[i], 1000000005);
        }

        long ans = 0;
        for (int i = b; i < w; i++) {
            ans = (ans + combination(i, h - a - 1) * combination(w - i - 1, a - 1) % 1000000007) % 1000000007;
        }
        System.out.println(ans);
    }

    static long[] fac, inv;
    static long combination(int h, int w) {
        return fac[h + w] * inv[h] % 1000000007 * inv[w] % 1000000007;
    }

    static long powAndMod(long a, long b) {
        if (b == 0)
            return 1;
        if ((b & 1) == 1)
            return a * powAndMod(a, b - 1) % 1000000007;
        return powAndMod(a * a % 1000000007, b / 2);
    }
}

Measured memory_bytes: 26324
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		char[] cha = stdIn.next().toCharArray();
		int max = 0;
		int num = 0;
		for (int i = 0; i < 3; i++) {
			if (cha[i] == 'R') {
				num++;
				max = Math.max(num, max);
			} else {
				num = 0;
			}
		}

		System.out.println(max);

		stdIn.close();
	}
}


Measured memory_bytes: 26972
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
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; }
using ll = long long;
using vi = vector<int>; using vvi = vector<vi>;
const ll MOD = 1e9+7; ll INF = 1LL << 60;
const vi d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vi d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vi d4x = {1, 0, -1, 0}; vi d4y = {0, 1, 0, -1};
//---------------------------------------

int main(){
    ll n; cin>>n;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    bool ok=true;
    for(int i=n-1; i>0; i--){
        if(h[i]>=h[i-1]) continue;
        if(h[i-1]-h[i]==1){
            h[i-1]--;
        }else{
            ok=false;
        }
    }
    cout<<(ok==true ? "Yes" : "No")<<endl;;
}

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

#define ll long long

using namespace std;

int main(void){
  int n;
  cin >> n;
  vector<int> v = vector<int>();
  v.reserve(n);
  for(int i = 0; i < n; ++i){
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
  for(int i = 0; i < n; ++i){
    int tmp;
    cin >> tmp;
    v[i] -= tmp;
  }
  sort(v.begin(), v.end());
  int minusnum = 0;
  ll minus = 0, plus = 0;
  for(int i = 0; i < v.size(); ++i){
    if (v[i] < 0){
      minus += v[i];
      ++minusnum;
    }else{
      plus += v[i];
    }
  }
  if (plus + minus < 0){
    cout << "-1" << endl;
    return 0;
  }
  if (minus >= 0){
    cout << minusnum << endl;
    return 0;
  }
  for(int i = v.size()-1;; --i){
    minus += v[i];
    if (minus >= 0){
      cout << minusnum + v.size()-i << endl;
      return 0;
    }
  }
  return 0;
}


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

static const int INF = 99999999;

void solve()
{
	int n, m;
	while(cin >> n >> m, n || m)
	{
		vector< vector<int> > Vec(n, vector<int>(n));
		int from, to, cost;
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				Vec[i][j] = INF;
			}
		}
		for(int i = 0; i < m; ++i)
		{
			cin >> from >> to >> cost;
			Vec[from][to] = cost;
			Vec[to][from] = cost;
		}
		vector<int> dist(n);
		vector<bool> use(n);
		for(int i = 0; i < n; ++i)
		{
			dist[i] = INF;
			use[i] = false;
		}
		dist[0] = 0;
		int res = 0;
		while(true)
		{
			int v = -1;
			for(int i = 0; i < n; ++i)
			{
				if(!use[i] && (v == -1 || dist[i] < dist[v]))
				{
					v = i;
				}
			}
			if(v == -1)
			{
				break;
			}
			use[v] = true;
			res += dist[v];
			for(int i = 0; i < n; ++i)
			{
				dist[i] = min(dist[i], Vec[v][i]);
			}
		}
		cout << res << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

char g[5][5];
char og[5][5];

int main()
{
    scanf("%s",g[0]);
    scanf("%s",g[1]);

    if(g[0][0] == g[1][2] && g[0][1] == g[1][1] && g[0][2] == g[1][0])
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}


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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    int n = in();
    vint a = in(n);
    rep(i, n)
    {
        --a[i];
    }
    int now = 0;
    vint seen(n, 0);
    int ans = 0;
    while (now != 1 && !seen[now])
    {
        seen[now] = 1;
        now = a[now];
        ++ans;
    }
    if (now != 1)
        ans = -1;
    cout << ans << endl;
}

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


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>

int main() {
    int a, b; std::cin >> a >> b;
    std::cout << a*b - a - b + 1 << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n, m, q;
    cin >> n >> m >> q;

    ll train[n+1][n+1];
    rep(i, n+1)rep(j, n+1)train[i][j] = 0;
    rep(i, m){
        ll l, r;
        cin >> l >> r;
        train[l][r]++;
    }
    ll c[n+1][n+1];
    rep(i, n+1)c[i][0] = 0;
    rep(i, n)rep(j, n)c[i+1][j+1] = c[i+1][j] + train[i+1][j+1];

    rep(i, q){
        ll h, w;
        cin >> h >> w;
        ll sum = 0;
        for(int j = h; j <= w; j++)sum+=c[j][w] - c[j][h-1];
        cout << sum << endl;
    }

}

Measured memory_bytes: 4864
N = int(input())
S = str(input())
cntw = [0]*(N+1)
cntb = [0]*(N+1)
for i in range(N):
    cntb[i+1] = cntb[i]+1 if S[i]=="#" else cntb[i]
    cntw[N-1-i] = cntw[N-i]+1 if S[N-1-i]=="." else cntw[N-i]
ans = 1e10
for i in range(N+1):
    ans = ans if ans < cntb[i]+cntw[i] else cntb[i]+cntw[i]
print(ans)


Measured memory_bytes: 12776
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include <iomanip>
#include<vector>
#include<map>
typedef long long ll;
const int mod = 1e9+7;
using namespace std;

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
ll qpow(ll a,ll b,ll p){a%=p; ll ret=1;for(;b;b>>=1,a=a*a%p) if(b&1) ret=ret*a%p; return ret;}
ll getInv(ll x,ll p){return qpow(x,p-2,p);}

int main(){
    ll n; 
    cin>>n;
    vector<ll> kkk(n+1);
    for(int i=1;i<=n;i++){
        cin>>kkk[i];
        }

    map<ll,int> hhh;

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

        if(hhh[kkk[i]-i]) {
            hhh[kkk[i]-i]++;
        }

        else hhh[kkk[i]-i]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(hhh[-kkk[i]-i]) {
            ans+=hhh[-kkk[i]-i];
            }
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 26936
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#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>
#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>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

int main() {
	vector<char>data(4);
	for (int i = 0; i < 4; i++) {
		cin >> data[i];
	}
	sort(data.begin(), data.end());
	if (data[0] == data[1] && data[1] != data[2] && data[2] == data[3]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


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

//#pragma gcc optimize("O3,unroll-loop")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double

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

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

    int a, b;
    vector<int> edge[100001];
    while (m--)
        cin >> a >> b, edge[a].push_back(b), edge[b].push_back(a);

    int ans[100001] = {};
    queue<int> quu;
    quu.push(1), ans[1] = 1;
    while (!quu.empty())
    {
        int now = quu.front();
        quu.pop();

        for (auto i : edge[now])
            if (!ans[i])
                ans[i] = now, quu.push(i);
    }

    for (int i = 2; i <= n; i++)
        if (!ans[i])
            cout << "No\n", exit(0);

    cout << "Yes\n";
    for (int i = 2; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}

//      *   *  *****  *   *  *   *
//     *   *  *      **  *  *   *
//    *****  *****  * * *  *   *
//   *   *      *  *  **  *   *
//  *   *  *****  *   *   ***

//      ***** ***** *   * *     ***** *   * ***** *****
//        *  *   * *   * *       *   **  *   *   *   *
//       *  *   * ***** *       *   * * *   *   *****
//   *  *  *   *   *   *       *   *  **   *   *
//  ****  *****   *   ***** ***** *   *   *   *


Measured memory_bytes: 10532
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdlib>
#include <cmath>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
using ll = long long;
using namespace std;
int GetDig(int n) {
	return (int)(log10(n)) + 1;
}
int main() {
	int n;
	cin >> n;
	int cnt = 0;
	REP(i,n){
		GetDig(i + 1) % 2 ? cnt++ : 0;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES

#include <iostream>
#include <iterator>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <climits>
#include <ctime>

using namespace std;
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

void solve() {
	string s;
	getline(cin, s);
	int answer = 0;
	int l = 0, r = s.size() - 1;
	while (l < r) {
		if (s[l] == s[r])
			++l, --r;
		else if (s[l] == 'x')
			++l, ++answer;
		else if (s[r] == 'x')
			--r, ++answer;
		else {
			cout << -1;
			return;
		}
	}
	cout << answer;
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	solve();

#ifdef LOCAL
	cerr << double(clock()) / CLOCKS_PER_SEC << " sec" << endl;
#endif
	return 0;
}

Measured memory_bytes: 512
import java.math.*;
import java.util.*;
import java.util.function.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    sc.close();

//    BigInteger lcm = Arrays.stream(A).parallel()
//        .mapToObj(BigInteger::valueOf)
//        .reduce(BigInteger.ONE, (a, b) -> a.divide(a.gcd(b)).multiply(b));

    BigInteger lcm = BigInteger.ONE;
    for (int ai : A) {
      BigInteger a = BigInteger.valueOf(ai);
      lcm = lcm.divide(lcm.gcd(a)).multiply(a);
    }

    long mod = 1000000007;
    long modLcm = lcm.remainder(BigInteger.valueOf(mod)).longValue();

    long ans = 0;
    for (int ai : A)
      ans = (ans + modDiv(modLcm, ai, mod)) % mod;
    System.out.println(ans);
  }

  private static long modDiv(long a, long b, long mod) {
    return (a % mod) * modInv(b, mod) % mod;
  }

  private static long modInv(long x, long mod) {
    return modPow(x, mod - 2, mod);
  }

  private static long modPow(long b, long e, long mod) {
    long ans = 1;
    long x = b % mod;
    for (long y = e; y != 0; y >>= 1) {
      if ((y & 1) == 1) ans = (ans * x) % mod;
      x = (x * x) % mod;
    }
    return ans;
  }
}

Measured memory_bytes: 150408
def p_has_value_x(p:list, x:int):
  for item in p:
    if int(item) == x:
      return True
  return False

def solve(p: list, x:int) -> int:
  if not p_has_value_x(p, x):
    return x

  pos = 1
  while True:
    aim_value = x - pos
    if aim_value <= 0:
      return aim_value
    if not p_has_value_x(p, aim_value):
      return aim_value
    aim_value = x + pos
    if not p_has_value_x(p, aim_value):
      return aim_value
    pos += 1


x, n = map(int, input().split())

if n == 0:
  print(x)
else:
  p = input().split()
  print(solve(p, x))


Measured memory_bytes: 9208
N, K = map(int, input().split())
S = input()

l = [0]
curr = '1'
for c in S:
    if c != curr:
        l.append(1)
        curr = c
    else:
        l[-1] += 1
if curr == '0':
    l.append(0)

n_group = len(l) // 2
sum_ = 0
k = min(K, n_group)
for i in range(k):
    sum_ += l[2*i] + l[2*i+1]
sum_ += l[2*k]
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)


Measured memory_bytes: 10028
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(string s) {long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const int INF = 10000;

int mp[110][110];
int main(){
	int N;
	vector<int>res;
	while(cin>>N){
		if(N==0)break;
		int W,H,S,T;
		cin>>W>>H;
		REP(i,110)REP(j,110)mp[i][j]=0;
		REP(i,N){
			int x,y;
			cin>>x>>y;
			mp[x][y]=1;
		}
		cin>>S>>T;
		int sum=0;
		FOR(i,1,W+1)FOR(j,1,H+1){
			int tmp=0;
			FOR(i2,i,min(S+i,W+1))FOR(j2,j,min(T+j,H+1))if(mp[i2][j2]==1)tmp++;
			sum=max(sum,tmp);
		}
		res.PB(sum);
	}
	REP(i,SZ(res))cout<<res[i]<<endl;
	return 0;
}

Measured memory_bytes: 1264
import java.util.*

fun calc(work: LongArray, i: Int, k: Int): Long {
    Arrays.sort(work)
    var sum = 0L
    for (m in 0 until i) {
        val value = work[m];
        if (m < k - i) {
            if (value > 0) {
                sum += value
            }
        } else {
            sum += value
        }
    }
    return sum
}

fun main(args: Array<String?>) {
    val scanner = Scanner(System.`in`)

    val n = scanner.nextInt()
    val k = scanner.nextInt()
    val values = LongArray(n)
    for (i in 0 until n) {
        values[i] = scanner.nextLong()
    }

    var max = 0L
    val start = Math.max(1, k / 2)
    for (i in start..k) {
        if (i <= (n - 1)) {
            val work = LongArray(i)
            for (j in 0..i) {
                var wi = 0
                for (l in 0 until j) {
                    work[wi++] = values[l]
                }
                for (l in 0 until (i - j)) {
                    work[wi++] = values[n - l - 1]
                }
                max = Math.max(calc(work, i, k), max)
            }
        } else {
            max = Math.max(calc(values, n, k), max)
            break;
        }
    }
    println(max)
}

Measured memory_bytes: 31140
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

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

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

	cout << ((n - m) * 100 + m * 1900) * (1 << m);

	//system("pause");

	return 0;
}

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

int main(){
    int n;
    cin >> n;
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        mp[tmp]++;
    }

    int even_cnt = 0, ans = mp.size();
    for(auto x : mp){
        if(x.second % 2);
        else even_cnt++;
    }

    if(even_cnt % 2) ans--;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4992
//
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define fst first
#define scd second
using namespace std;
inline ll read() {
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int MAXN=1e5+5;
int n,a[MAXN];
int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}
struct SegmentTree {
	int g[MAXN<<2];
	void build(int p,int l,int r) {
		if(l==r) {
			g[p]=a[l]; return ;
		}
		int mid=(l+r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		g[p]=gcd(g[p<<1],g[p<<1|1]);
	}
	int query(int p,int tl,int tr,int ql,int qr) {
		if(ql<=tl && qr>=tr) return g[p];
		int mid=(tl+tr)>>1,res=0;
		if(ql<=mid) res=gcd(query(p<<1,tl,mid,ql,qr),res);
		if(qr>mid) res=gcd(query(p<<1|1,mid+1,tr,ql,qr),res);
		return res;
	}
}T;
int main() {
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);/*syn加速*/
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	if(n==1) {cout<<"1000000000"<<endl;return 0;}
	T.build(1,1,n);
	int ans=1;
	for(int i=1;i<=n;++i) {
		int g=0;
		if(i!=1) g=gcd(T.query(1,1,n,1,i-1),g);
		if(i!=n) g=gcd(T.query(1,1,n,i+1,n),g);
		ans=max(ans,g);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> B(m, 0);
    for(int& val: B)
        cin >> val;
    int ans = 0;
    vector<int> A(m, 0);
    for(int i = 0; i < n; i++) {
        int res = c;
        for(int j = 0; j < m; j++) {
            cin >> A[j];
            res += A[j]*B[j];
        }
        if (res > 0)
            ans += 1;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;


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


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



int main() {
   double x;
   cin >> x;
   double a = 100;
   for (int i=0; i<1000000; i++) {
      a = floor(a * 1.01);
      if (a >= x) {
         cout << i+1 << endl;
         return 0;
      }
   }
   return 0;
}

Measured memory_bytes: 3724
def main():
  C = [0] * 4

  for i in range(3):
    a, b = map(int, input().split())
    C[a-1] += 1
    C[b-1] += 1

  for i in range(4):
    if (2 < C[i]):
      print('NO')
      return

  print('YES')

main()


Measured memory_bytes: 2940
s = input()
for bit in range(1 << 3):
    f = s[0]
    ans = int(s[0])
    for i in range(3):
        if bit & (1 << i):
            ans += int(s[i+1])
            f += "+"
        else:
            ans -= int(s[i+1])
            f += "-"
        f += s[i+1]
    if ans == 7:
        f += "=7"
        print(f)
        break

Measured memory_bytes: 8960
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    while(1){
    long long a,b,n,x,y;
    cin>>a>>b;
    if(a==0&&b==0)goto end;
    cin>>n;
    long long dp[a+1][b+1];
    bool flag[a+1][b+1];
    memset(dp,0,(a+1)*(b+1)*sizeof(long long int));
    memset(flag,true,(a+1)*(b+1)*sizeof(bool));

    for(int i=0;i<n;i++){
        cin>>x>>y;
        flag[x][y]=false;
    }

    flag[1][1]=false;
    dp[1][1]=1;
    for(int i=1;i<a+1;i++){
        for(int j=1;j<b+1;j++){
            if(flag[i][j]){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }

    cout<<dp[a][b]<<endl;
    }

    end:
    int a=0;
}



Measured memory_bytes: 3060
#include <stdio.h>
long long a [100010];
int main (){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
int zero =0;

for(int i=0;i<n;i++)if(a[i]==0) zero ++;
if(zero >0){
// a[i] contains 0
printf("0\n");
return 0;
}
long long prod =1;
for(int i=0;i<n;i++){
if(a[i ] <=1000000000000000000/ prod ){
// This condition is equivalent to prod*a[i] <=10ˆ18
prod *=a[i];
}else{
printf("-1\n");
return 0;
}
}
printf("%lld\n",prod );
}


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

int main(void){
	int n,m;
	cin>>n>>m;
	pair<int,int> *edge=new pair<int,int>[m];
	for(int i=0;i<m;i++) cin>>edge[i].first>>edge[i].second;
	sort(edge,edge+m);

	int *ptr=new int[n+1];
	for(int i=0;i<=n;i++)ptr[i]=m;
	for(int i=0,j=0;i<m;i++){
		while(j<edge[i].first)ptr[j++]=i;
		edge[i].second--;
	}
	
	int *sen=new int[n];
	for(int i=0;i<n;i++)sen[i]=0;
	stack<int> s;
	for(int i=0;i<n;i++)s.push(i);
	int *cp=new int[n];
	for(int i=0;i<n;i++) cp[i]=((ptr[i]==ptr[i+1])?0:-1);
	while(s.empty()==0){
		int t=s.top();
		if(ptr[t]+sen[t]<ptr[t+1]){
			if(ptr[edge[ptr[t]+sen[t]].second]+sen[edge[ptr[t]+sen[t]].second]<ptr[edge[ptr[t]+sen[t]].second+1]) s.push(edge[ptr[t]+sen[t]].second);
			else cp[t]=max(cp[t],cp[edge[ptr[t]+sen[t]++].second]+1);
		}else s.pop();
	}

	int ans=cp[0]; for(int i=1;i<n;i++) ans=max(ans,cp[i]);
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  998244353
const int N = 10000;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
     ll k,a,b;
     cin >> k >> a >> b;
     for(ll i=a;i<=b;i++)
     {
          if(i%k==0)
          {
               cout<<"OK\n";
               return;
          }
     }
     cout<<"NG";
}

int main()
{
     FAST;
     ll t = 1;
   //  cin >> t; 
     for(ll i=1;i<=t;i++)
     {
         // cout<<"Case #"<<i<<": ";
          solve();
     }
}

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

int main() {
	string S, A="AKIHABARA+", T; cin >> S;
	int P=0; bool flag=true;
	for(int i=0; i<S.size(); ++i){
	    if(S[i]==A[P]) ++P;
	    else if(A[P]=='A' && S[i]==A[P+1]) P += 2;
	    else{
	        flag=false;
	        break;
	    }
	}
	if(flag && (P==8 || P==9)) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


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

#define ll long long

ll binpow(ll a, ll n, ll mod){
    ll ans = 1L;
    while(n > 0){
        if(n%2) ans = ans * a % mod;
        a = a * a % mod;
        n /= 2;
    }
    return ans % mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    if(n==1){
        cout << "0\n";
        return 0;
    }
    if(n==2){
        cout << "2\n";
        return 0;
    }
    ll mod = (ll)1e9+7;
    ll ans = binpow(10, n, mod);
    ll tmp1 = binpow(9, n, mod);
    ll tmp2 = binpow(8, n, mod);
    ans = ans - tmp1 - tmp1 + tmp2;
    while(ans<0) ans += mod;
    ans = ans % mod;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mex=10000000;
#define ll long long 
#define test int t;cin>>t;while(t--)
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,a,b) for(int i=a;i>=b;i--)
#define bg begin()
#define en end()
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define veci vector<int>
#define veclli vector<long long int> 
#define all(x) x.begin(),x.end()
#define sci(x) scanf("%d",&x);
#define scc(x) scanf("%c",&x);
#define scs(x) scanf("%s",x);
#define debug(arr,n) for(int i=0;i<n;i++) printf("%d ",arr[i]);
#define sz(x) x.size()
#define loop(x) for(auto it=x.begin();it!= x.end();it++) 

int main()
{
   int n;
   cin>>n;
   map<string,int> mp;
   fo(i,0,n)
   {
       string s;
       cin>>s;
       mp[s]++;
   }
   map<int,vector<string> > mp1;
   loop(mp)
   {
       mp1[it->se].pb(it->fi);
   }
   auto it=mp1.end();
   it--;
       sort(all(it->se));
       fo(i,0,it->se.size())
       cout<<it->se[i]<<endl;
       
   
   
}

Measured memory_bytes: 26868
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
           
            int N = sc.nextInt();
            String s = sc.next();
            int red = 0;
            
            for (int i=0; i<s.length() ; i++) {
              if(s.charAt(i) == 'R'){
                red++;
              }
            }
   
            if (N/2 < red) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
    }
}

Measured memory_bytes: 23508
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
 
class Segment_Tree{
	private:
	int n;
	vl date;
	ll Rec(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return date[k];
		int m=(l+r)/2;
		return Rec(a,b,k*2+1,l,m)+Rec(a,b,k*2+2,m,r);
	}
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vl(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	ll Query(int a,int b){
		return Rec(a,b,0,0,n);
	}
	int Open(int k){
		return date[k+n-1];
	}
};
 
ll n,N;
vl a;
 
ll f(int x){
	vl b(n+1);
	for(int i=1;i<=n;i++) b[i]=(a[i-1]>=x?1:-1);
	for(int i=1;i<=n;i++) b[i]+=b[i-1];
	Segment_Tree st(3*n);
	st.Update(n,1);
	ll t=0;
	for(int i=1;i<=n;i++){
		ll tmp=st.Query(0,b[i]+n+1);
		t+=tmp;
		st.Update(b[i]+n,1);
	}
	return t;
}
 
int main(){
	cin>>n;
	a=vl(n);
	N=n*(n+1)/2;
	for(int i=0;i<n;i++) cin>>a[i];
	ll l=0,r=inf;
	while(r-l>1){
		ll m=(l+r)/2;
		if(f(m)>=(N+1)/2) l=m;
		else r=m;
	}
	cout<<l<<endl;
}

Measured memory_bytes: 9992
// Charan Sriramula

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;

const ll lg=22;
const ll N=1e5+5;
const ll M=16;
const ll INF=1e18;
const ll mod=1e9+7;
const double PI = 3.14159265358979323846;

#define is(n) scanf("%d",&n)
#define io(n) printf("%d\n",n)
#define ls(n) scanf("%lld",&n)
#define lo(n) printf("%lld\n",n)

#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

inline ll mul(ll a, ll b, ll p){ return (a * 1ll * b) % p; }
inline ll sub(ll a, ll b, ll p){ ll c = a - b; if(c < 0) c += p; return c; }
inline ll add(ll a, ll b, ll p){ ll c = a + b; if(c > p) c -= p; return c; }

#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

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

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <cassert>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef vector<int> vi;
typedef pair<vi,int> P;
struct edge {
	int to,cap;
	vi cost;
	int rev;
	edge(int to,int cap,vi cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
};
const int MAX_V=102;
int V;
vector<edge> G[MAX_V];
vi h[MAX_V];
vi dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
vi zero(52,0),mx(52,53),vinf(52,200);
vi operator +(const vi &l,const vi &r){
	vi ret=l;
	rep(i,52) ret[i]+=r[i];
	return ret;
}
vi operator -(const vi &l,const vi &r){
	vi ret=l;
	rep(i,52) ret[i]-=r[i];
	return ret;
}
vi operator*(const int &l,const vi &r){
	vi ret=r;
	rep(i,52) ret[i]+=l;
	return ret;
}
vi operator -(const vi &l){
	vi ret=l;
	rep(i,52) ret[i]=-ret[i];
	return ret;
}
void add_edge(int from, int to, int cap, vi cost){
	edge e1=edge(to,cap,cost,G[to].size()),e2(from,0,-cost,G[from].size());
	G[from].push_back(e1);
	G[to].push_back(e2);
}
void min_cost_flow(int s, int t, int f){
	vi res=zero;
	fill(h,h+V,zero);
	while(f>0){
		priority_queue< P,vector<P>,greater<P> > que;
		fill(dist,dist+V,vinf);
		dist[s]=zero;
		que.push(P(zero,s));
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first) continue;
			rep(i,G[v].size()){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
//		if(dist[t]==vinf) return -1;
		for(int v=0;v<V;v++) h[v]=h[v]+dist[v];
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res=res+d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
}
vi tovi(int x){
	vi ret(52,0);
	ret[x]++;
	return ret;
}
int toint(vi vv){
	rep(i,52) if(vv[i]==52) return i;
	assert(false);
}
int num(char c){
	if('A'<=c&&c<='Z') return c-'A';
	return c-'a'+26;
}
char denum(int num){
	if(num<26) return 'A'+num;
	return 'a'+(num-26);
}
int main(){
	int N;
	cin>>N;
	string st[50];
	rep(i,N) cin>>st[i];
	rep(i,N){
		rep(j,N){
			add_edge(i,j+N,1,mx-tovi(num(st[i][j])));
		}
	}
	int s=2*N,t=2*N+1;
	V=2*N+2;
	rep(i,N) add_edge(s,i,1,zero);
	rep(i,N) add_edge(N+i,t,1,zero);
	string ans;
	min_cost_flow(s,t,N);
	rep(i,N){
		for(edge e:G[i]){
			if(e.cap==0) ans.pb(denum(toint(e.cost)));
		}
	}
	sort(all(ans));
	cout<<ans<<endl;
}

Measured memory_bytes: 4644
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p, l, r; };
struct Node T[MAX];
int n;

/* 先行順巡回*/
void preParse(int u) {
  if ( u == NIL ) return;
  printf(" %d", u);
  preParse(T[u].l);
  preParse(T[u].r);
}
/* 中間順巡回*/
void inParse(int u) {
  if ( u == NIL ) return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);
}
/* 後行順巡回*/
void postParse(int u) {
  if ( u == NIL ) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d", u);
}

int main() {
  int i, v, l, r, root;

  // 標準入力を受け取る
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) {
    T[i].p = NIL;
  }

  for ( i = 0; i < n; i++ ) {
    scanf("%d %d %d", &v, &l, &r);
    // 二分木なので、u.lとu.rにそれぞれ入力を代入。それぞれの子の親として自分自身のノードを代入
    T[v].l = l;
    T[v].r = r;
    if ( l != NIL ) T[l].p = v;
    if ( r != NIL ) T[r].p = v;
  }

  // root探し
  for ( i = 0; i < n; i++ ) if ( T[i].p == NIL ) root = i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

  return 0;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


int main()
{
    int N;
    cin >> N;
    vector<int> X(N);
    REP(i, N) cin >> X[i];

    int ans = 1e+7;
    FOR(P, 1, 101){
        int tot_stamina = 0;
        REP(i, N) tot_stamina += (X[i]-P)*(X[i]-P);
        ans = min(ans, tot_stamina);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256