akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define init_random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define contests_de_diya_kar 0
#define PB push_back
#define MP make_pair
#define int long long
#define sd(n) scanf("%lld", &n)
#define pd(n) printf("%lld\n", n)
#define MOD ((long long) (1000*1000*1000 + 7))
#define exit(a, b) return cout << a, b;
#define eps (double)1e-9
#define forn(a, b, i) for (int i = a; i < b; i += 1)
#define vi vector<int>
#define vb vector<bool>
#define all(v) v.begin(), v.end()
#define ll long long 
#define pii pair<int, int>
#define mii map<int, int> 
#define print(stuff) cout << stuff << endl
#define len(stuff) stuff.size()

const int N = (int) 1e5 + 100;
int fac[N + 1], invfac[N + 1];
const int M = MOD;

int modexp (int a, int b) {
	if (b == 0) return 1;
	int ans = modexp(a, b/2);
	ans = (ans * ans) % M;
	if (b % 2) ans = (ans * a) % M;
	return ans;
}

inline int inv (int a) {
	return modexp(a, M - 2);
}

void prec () {
	fac[0] = 1;
	for (int i = 1; i <= N; i++) fac[i] = (fac[i - 1] * i) % M;
	invfac[N] = inv(fac[N]);
	for (int i = N - 1; i >= 0; i--) invfac[i] = (invfac[i + 1] * (i + 1)) % M;	
}

int c (int n, int r) {
	int ans = fac[n];
	ans *= invfac[n - r], ans %= M;
	ans *= invfac[r], ans %= M;
	return ans;
}

signed main()
{
  start_routine;
  #ifndef ONLINE_JUDGE
 // freopen("input.txt", "r", stdin);
  #endif
  prec();

  string a, b;
  vi cnta(26, 0), cntb(26, 0);

  cin >> a >> b;
  for (auto c: a) cnta[c - 'a']++;
  for (auto c: b) cntb[c - 'a']++;

  sort(all(cnta));
	sort(all(cntb));

	if (cnta == cntb) {
		cout << "Yes\n";
	}
	else cout << "No\n";
  end_routine;
}

Measured memory_bytes: 2452
#include<stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))

char strs[200001];
char spells[200000];
int LRs[200000];
int main() {
	int N, Q,i,min = -1,max;
	char spell, LR;
	scanf("%d %d\n", &N, &Q); max = N;
	scanf("%s\n", strs);
	for (i = 0; i < Q; i++) {
		scanf("%c %c\n", &spell, &LR);
		spells[i] = spell;
		LRs[i] = (LR == 'L' ? 1 : 0);
	}
	for (i = Q - 1; i >= 0; i--) {
		if (LRs[i] == 1 && spells[i] == strs[min + 1]) { min++; }
		if (LRs[i] == 0 && spells[i] == strs[max - 1]) { max--; }
		if (LRs[i] == 1 &&max <N&& spells[i] == strs[max]) { max++; }
		if (LRs[i] == 0 &&min >= 0&& spells[i] == strs[min]) { min--; }
	}
	printf("%d\n", min(max(0, max - min - 1),N));
	return 0;
}

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

int n, m;
vector<int> edges[1005];
vector<int> memo, cnt(2, 0), ans;

void solve();

int main() {
  while(1) {
    cin >> n >> m;
    if(n + m == 0) break;
    for(int i = 0; i < n; ++i) edges[i].clear();
    ans.clear();
    for(int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      edges[a].push_back(b);
      edges[b].push_back(a);
    }
    memo.assign(n, 0);
    solve();
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); ++i)
      cout << ans[i] << endl;
  }
  return 0;
}

void solve() {
  queue<int> qu;
  memo[0] = 1;
  qu.push(0);
  while(!qu.empty()) {
    int now = qu.front();
    qu.pop();
    for(int i = 0; i < edges[now].size(); ++i) {
      int nextp = edges[now][i];
      if(memo[nextp] == 0) qu.push(nextp);
      if(memo[nextp] != memo[now])
        memo[nextp] |= 1 << (memo[now] % 2);
      else
        return;
    }
  }
  cnt[0] = cnt[1] = 0;
  for(int i = 0; i < n; ++i) ++cnt[memo[i] - 1];
  for(int i = 0; i < 2; ++i)
    if(cnt[i] % 2 == 0) ans.push_back(cnt[i] / 2);
  sort(ans.begin(), ans.end());
  ans.erase(unique(ans.begin(), ans.end()), ans.end());
}


Measured memory_bytes: 3196
import math
A, B, H, M = map(int, input().split())
hours = H / 12 * (2 * math.pi) + M / 60 * (math.pi / 6)
minutes = M / 60 * (2 * math.pi)
theta = 0
if hours >= minutes:
    theta = hours - minutes
else:
    theta = minutes - hours
if theta > math.pi:
    theta = math.pi*2 - theta
c = math.sqrt(A*A + B*B - 2*A*B*math.cos(theta))
print(c)

Measured memory_bytes: 9448
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

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

	int n; cin >> n;
	cout << n * n * n << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SUM(vec) accumulate(all(vec),0LL)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;}
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);}
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;}
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;}


bool isOk(ll key,ll value){
  return key >= value;
}

ll binary_search(vector<ll> a,ll key){
  ll ok = a.size()-1;
  ll ng = 0;

  while(abs(ok - ng) > 1){
    ll mid = (ok + ng) / 2;
    if(isOk(key,a[mid]))ok = mid;
    else ng = mid;
  }
  return ok;
}

bool isPrime(ll n) {
	for (int i = 2; n >= i * i; ++i) {
		if(!(n % i))return false;
	}
  return true;
}
vector<ll> primes(ll n){
  vector<ll> v(1,1);
  for (ll i = 2; n >= i * i; ++i) {
		if(!(n % i)){
      v.pb(i);
	  }
  }
  if(v.size()==1)v.pb(n);
  return v;
}


int main() {
  cin.tie(0); ios::sync_with_stdio(0);
  int n;cin>>n;
  vector<ll> a(n);rep(i,n)cin>>a[i];
  sort(all(a),greater<int>());
  int ans1 = a[0];
  pair<int,int> ans2 = mp(0,INF);
  rep(i,n){
    if(!i)continue;
    if(abs(ans1/2 - a[i]) < ans2.se){
      ans2.fi = a[i];
      ans2.se = abs(ans1/2 - a[i]);
    }
  }
  cout<<ans1<<' '<<ans2.fi<<endl;
  return 0;
} 

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

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

  multiset<int> s;
  rep(i, n) s.insert(a[i]);

  rep(i, m) {
    auto max = *s.rbegin();
    s.erase(--s.end());
    s.insert(max / 2);
  }
  ll ans = 0;
  for (auto i : s) ans += i;

  cout << ans << endl;
}


Measured memory_bytes: 8312
#include<stdio.h>
#define N 101
int main(){
  int G[N][N],n,flg[N]={},s[N],i,j,c, m1,m2=1,mi,sum=0;
  for(i=1;i<=100;i++){
      s[i]=1000000;
    }
  s[1]=0;
  scanf("%d",&n);
 
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      scanf("%d",&G[i][j]);
    }
  }
  flg[1]=1;
  while(1){    
    c=0;
    for(i=1;i<=n;i++)
      if(flg[i]==1)c++;
    if(c==n)break;
        m1=10000000; 
    for(i=1;i<=n;i++){
      if(flg[i]!=1 && G[m2][i]!=-1 && s[i]>G[m2][i])
	s[i] = G[m2][i];
      if(flg[i]!=1 && m1>s[i]){
	mi=i;
	m1=s[i];
      }
    }
  sum+=m1;
  flg[mi]=1;
  s[mi]=m1;
  m2=mi;
  }
  printf("%d\n",sum);
  
  return 0;
}



Measured memory_bytes: 2108
/*
        @uthor: Kashish Gilhotra
        user: CodeChef, CodeForces, HackerEarth, HackerRank, SPOJ: kashish001
*/

#include <bits/stdc++.h>
using namespace std;
  
#define int long long int 
typedef vector<int> vi;
typedef vector<pair<int, int>> vpi;
typedef vector<vi> vvi;
const int mod = 1e9 + 7; 

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define debug(...) cerr << "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " 
#define EB emplace_back
#define ALL(v) v.begin(), v.end() 
#define size(v) (int)v.size() 
#define endl "\n"
#define UMO unordered_map
#define USO unordered_set
#define TC int t; cin >> t; while (t--) 

int dp[(int)1e5 + 1][3];

int ans(vvi in, int n) {
    for(int i = 0 ; i < 3; i++) dp[0][i] = in[0][i];
   for(int i = 1 ; i < n; i++) {
       for(int j = 0 ; j < 3; j++) {
           for(int k =  0; k < 3; k++) {
               if(j == k) continue;
               dp[i][j] = max(dp[i][j], in[i][j] + dp[i - 1][k]);
           }
       }
   }
   int maxx = INT_MIN;
   for(int i = 0 ; i < 3; i++) maxx = max(dp[n - 1][i], maxx);
   return maxx;
}

void Panda() {
    int n;
    cin >> n;
    vvi in(n, vi(3));
    for(auto &i : in) for(auto &j : i) cin >> j;
    cout << ans(in, n) << endl;
}
  
int32_t main() {
 
    FAST;

    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout); 
    
    Panda();

    return 0; 
} 

Measured memory_bytes: 16480
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    m = e = sum(P[:K])
    c = 0
    for i in range(N - K):
        e = e + P[K + i] - P[i]
        if e > m:
            m = e
            c = i + 1
    t = sum((k + 1) for k in P[c:c + K]) / 2
    print(t)

main()


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

#define ll long long
#define mtv(kit) cout<<#kit<<" - "<<kit<<"\n";
#define ff first
#define ss second
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define pii pair<ll , ll>
#define all(x) x.begin(),x.end()
#define nl "\n"
#define ump unordered_map

void doit(){
    ll n,i;
    cin >> n;
    string s1="AC",s2="WA",s3="TLE",s;
    ll cs1=0,cs2=0,cs3=0,cs4=0;
    rep(i,0,n){
        cin >> s;
        if(s==s1)cs1++;
        else if(s==s2)cs2++;
        else if(s3==s)cs3++;
        else cs4++;
    }
    cout << s1 << " x " << cs1 << nl;
    cout << s2 << " x " << cs2 << nl;
    cout << s3 << " x " << cs3 << nl;
    cout << "RE" << " x " << cs4 << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for(ll i = 1; i <= t; i++){
        doit();
    }
}


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

bool BinarySearch(int x, int S[], int N){
  int B = 0;
  int T = N-1;

  while(B<=T){
    int mid = (B+T)/2;

    if(S[mid]==x){
      return true;
    }
    else if(S[mid]<x){
      B = mid+1;
    }
    else{
      T = mid-1;
    }
  }

  return false;
}

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

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

  int q;
  cin >> q;
  int T[q];
  for(int i=0; i<q; i++){
    cin >> T[i];
  }

  sort(T, T+q);
  int cnt=0;
  for(int i=0; i<n; i++){
   if(S[i]!=S[i+1]){
    if(BinarySearch(S[i], T, q)==true){
      cnt++;
    }
   }
  }

      cout << cnt << endl;
  return 0;
}



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

int main(){

    while(1){
      int a,b;
      string op;
      cin>>a>>op>>b;
      if(op == "?") break;

      int ans;
      if(op == "+") ans = a+b;
      if(op == "-") ans = a-b;
      if(op == "*") ans = a*b;
      if(op == "/") ans = a/b;

      cout<<ans<<endl;
    }
    return 0;
}



Measured memory_bytes: 3084
s = input()
if s[:2] == "00" and s[2:] == "00":
  print("NA")
elif s[:2] == "00":
  if int(s[2:]) <= 12:
    print("YYMM")
  else:
    print("NA")
elif s[2:] == "00":
  if int(s[:2]) <= 12:
    print("MMYY")
  else:
    print("NA")
else:
  if int(s[:2]) <= 12 and int(s[2:]) <= 12:
    print("AMBIGUOUS")
  elif int(s[:2]) > 12 and int(s[2:]) <= 12:
    print("YYMM")
  elif int(s[:2]) <= 12 and int(s[2:]) > 12:
    print("MMYY")
  else:
    print("NA")

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
    int i,j,n,minj,k,l=0;

    scanf("%d",&n);
    int A[n];
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    for(i=0;i<=n-1;i++){
        minj=i;
        for(j=i+1;j<=n-1;j++){
            if(A[j]<A[minj]){
                minj=j;
            }
        }
        if(minj!=i){
            k=A[i];
            A[i]=A[minj];
            A[minj]=k;
            l++;
        }
    }
    
    for(i=0;i<n;i++){
        if(i==n-1) printf("%d",A[i]);
        else printf("%d ",A[i]);
    }
    printf("\n%d\n",l);
    return 0;
}


Measured memory_bytes: 2068
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

int main(){
  double N;
  cin>>N;
  double M=N;
  int F=0;
  rep(i,N){
    if(int(N*1.08)==int(M)){
      cout<<N<<endl;
      F=1;
      break;
    }
    N-=1;
  }
  if(F==0) cout<<":("<<endl;
}





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

int main()
{
    int k;
  cin >> k;
  vector<int> vec ={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << vec.at(k-1);
}


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

int main(){
string s;
cin>>s;
int i=0;
string ans="";
while(s[i]!='/'){
ans=ans+s[i];
i++;}
int t=stoi(ans);
if(t>2019){
cout<<"TBD";
return 0;}
i++;
ans="";
while(s[i]!='/'){
ans=ans+s[i];
i++;}
t=stoi(ans);
if(t>4){
cout<<"TBD";
return 0;}
i++;
ans="";
while(s[i]!='/'&&i<s.length()){
ans=ans+s[i];
i++;}
t=stoi(ans);
if(t>30){
cout<<"TBD";
return 0;}
cout<<"Heisei";
return 0;}

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

int main() {
    int N;
    cin >> N;
    vector<int> v(N);
    rep(i, N-1) {
        int A;
        cin >> A;
        v[A - 1]++;
    }
    rep(i, N) {
        cout << v[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3960
n = int(input())
p = list(map(int,input().split()))
mn = n
count = 0
for i in range(n):
    if(p[i]<=mn):
        count+=1
        mn = p[i]
print(count)
# 

# count = 0
# val = sum(p[0:k])
# val_lis = [val]
# mx_val = val
# index = 0
# mx_index = 0
# for i,j in enumerate(p[k:]):
#     val = val - p[index] + j
#     val_lis.append(val)
#     index +=1
#     if val > mx_val:
#         mx_index = index
#         mx_val = val 
    
# ans = 0
# for i in range(k):
#     ans += ((p[mx_index + i]+1.0)*(p[mx_index+i]))/ (p[mx_index+i] *2.0)
# print(ans)  




# h = sorted(h,reverse = True)
# print(sum(h[k:]))

# s,t= map(str, input().split())
# a,b= map(int, input().split())
# u = input()
# print("x"*len(u))

# if(u == s):
#     print(a-1,b)
# else:
#     print(a,b-1)


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

typedef vector<int> vi;  
typedef pair<int,int> ii;  
typedef vector<ii> vii;  
typedef list<int> li;  
typedef unordered_map<int,int> mii;

#define ll long long
#define rep(i,n) for (int i = 0; i < (n); i++)  
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rap(i,a,n) for (int i = a; i < (n); i++) 
#define rrap(i,n,a) for (int i = (n)-1; i >= a; i--) 

int main() {
    ios_base::sync_with_stdio(false);
    int n,a,b;
    int c=0;
    cin >> n >> a >> b;
    if (n > a+b) c = 0;
    else c = a+b-n;
    cout << min(a,b) << ' ' << c << '\n';
    return 0;

    //compile: g++ -std=c++14 -O2 -Wall NAME.cpp -o NAME
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N;
int x[101010];
int M, K;
int a[101010];

int X[101010];
int A[62][101010];
int B[101010], C[101010];

void doswap(int a[101010], int b[101010], int c[101010])
{
    REP(i,N-1) c[i] = b[a[i]];
}

signed main()
{
    cin >> N;
    REP(i,N) cin >> X[i];

    REP(i,N-1) A[0][i] = B[i] = i;

    cin >> M >> K;
    REP(i,M) {
        int x;
        cin >> x;
        swap(A[0][x-2], A[0][x-1]);
    }

    REP(i,61) {
        if (K & (1L << i)) {
            doswap(B, A[i], C);
            swap(B, C);
        }
        doswap(A[i], A[i], A[i+1]);
    }

    ll s = X[0];
    REP(i,N) {
        cout << s << endl;
        s += X[B[i]+1] - X[B[i]];
    }
}


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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

void solve() {
  int a, b;
  cin >> a >> b;
  cout << (a % b == 0 ? a / b : a / b + 1) << endl;
}

signed main() {
  solve();

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    int ans=0;
    for(int i=1;i<=a;i++)
    	if(a>i||(a==i&&b>=i))
    		ans++;
    cout<<ans<<endl;
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;
const int OFFSET = 1e5 + 2;

int v[MAXN];
int sorted[MAXN];
int tmp1[MAXN], tmp2[MAXN];
int *bal1, *bal2;

int n;

ll cur;

void calc(int l, int r, int val) {
	if (l == r) {
		if (v[l] > val) {
			cur++;
		}
		//printf("%d: %d %d -> %d\n", val, l, r, (v[l] > val ? 1 : 0));
		return;
	}
	int mid = (l + r) >> 1;
	calc(l, mid, val);
	calc(mid + 1, r, val);
	int cnt = max(mid - l + 1, r - mid);
	REPN(i, -cnt, cnt) {
		bal1[i] = bal2[i] = 0;
	}
	
	int curl = 0;
	for(int i = mid; i >= l; i--) {
		if (v[i] <= val) {
			curl--;
		} else {
			curl++;
		}
		bal1[curl]++;
	}
	
	int curr = 0;
	for(int i = mid + 1; i <= r; i++) {
		if (v[i] <= val) {
			curr--;
		} else {
			curr++;
		}
		bal2[curr]++;
	}
	
	ll sum = 0;
	REPN(i, -cnt, cnt) {
		sum += bal2[-i];
		cur += sum * bal1[i];
	}
	
	//printf("%d: %d %d %d -> %lld\n", val, l, mid, r, cur);
}

bool check(int val) {
	cur = 0ll;
	calc(0, n - 1, val);
	return 2ll * cur < (ll)n * (ll)(n + 1) / 2ll;
}

void solve(){
	bal1 = &tmp1[OFFSET];
	bal2 = &tmp2[OFFSET];
	
	scanf("%d", &n);
	REP(i, 0, n) {
		scanf("%d", &v[i]);
		sorted[i + 1] = v[i];
	}
	sort(sorted + 1, sorted + n + 1);
	sorted[0] = sorted[1] - 1;
	sorted[n + 1] = sorted[n] + 1;
	int l = 0, r = n + 1;
	while(l + 1 < r) {
		int mid = (l + r) >> 1;
		if (check(sorted[mid])) {
			r = mid;
		} else {
			l = mid;
		}
		//printf("%d %d\n", l, r);
	}
	printf("%d\n", sorted[r]);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for (int i = n - 1; i >= 0; i--)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

#define INF bit(60)
#define pb push_back
#define mod 1000000007

using namespace std;
using uif = uint_fast64_t;
using ll = long long int;
using tTree = __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

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

#define FACSIZE 200002

ll invfac[FACSIZE];
ll fac[FACSIZE];

template <class T>
bool chmax(T &, const T &);
template <class T>
bool chmin(T &, const T &);
ll gcd(ll, ll);
ll powLL(ll x, ll y);

ll mod_pow(ll, ll);
ll mod_add(ll, ll);
ll mod_mul(ll, ll);
ll mod_div(ll, ll);
ll comb(ll, ll);
void make_fact(ll);
void make_invfact(ll);
void fact_init();

int main(void)
{
  ll n;
  cin >> n;
  vector<ll> d(n);
  rep(i, n) cin >> d[i];
  sort(begin(d), end(d));

  cout << d[n / 2] - d[n / 2 - 1] << endl;

  return 0;
}

ll mod_pow(ll x, ll r)
{
  if (r == 0)
    return 1;
  else if (r == 1)
    return x % mod;
  else if (r % 2 == 0)
  {
    ll t = mod_pow(x, r / 2) % mod;
    return mod_mul(t, t);
  }
  else
  {
    ll t = mod_pow(x, r / 2) % mod;
    ll k = mod_mul(t, t);
    return (k % mod) * (x % mod);
  }
}
ll mod_add(ll a, ll b)
{
  return ((a % mod) + (b % mod)) % mod;
}

ll mod_mul(ll a, ll b)
{
  return ((a % mod) * (b % mod)) % mod;
}

ll mod_div(ll a, ll b)
{
  return mod_mul(a, mod_pow(b, mod - 2));
}

void fact_init()
{
  make_fact(FACSIZE - 1);
  make_invfact(FACSIZE);
}

void make_fact(ll n)
{
  fac[0] = 1;
  rep(i, n)
  {
    fac[i + 1] = mod_mul(fac[i], i + 1);
  }
}

void make_invfact(ll n)
{
  invfac[n] = mod_pow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--)
  {
    invfac[i] = mod_mul(invfac[i + 1], i + 1);
  }
}

ll comb(ll n, ll r)
{

  return mod_mul(mod_mul(fac[n], invfac[r]), invfac[n - r]);
}
template <class T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
  if (b < a)
  {
    a = b;
    return 1;
  }
  return 0;
}

ll qp(ll a, ll b)
{
  ll ans = 1LL;
  do
  {
    if (b & 1LL)
      ans = 1LL * mod_mul(ans, a) % mod;
    a = 1LL * mod_mul(a, a) % mod;
  } while (b >>= 1LL);
  return ans;
}
ll qp(ll a, ll b, ll mo)
{
  ll ans = 1LL;
  do
  {
    if (b & 1LL)
      ans = 1LL * (ans % mo) * (a % mo);
    a = 1LL * (a % mo) * (a % mo);
  } while (b >>= 1LL);
  return ans;
}
ll gcd(ll a, ll b)
{
  return b ? gcd(b, a % b) : a;
}
ll powLL(ll x, ll y)
{
  ll ans = 1LL;
  for (ll i = 0LL; i < y; i++)
    ans *= x;
  return ans;
}

Measured memory_bytes: 1024
'use strict'

function main(input) {
  input = input.trim().split('\n')
  const n = input[0]
  const ans = input[1]
    .split(' ')
    .map(v => parseInt(v, 10))
    .map(v => 1 / v)
    .reduce((a, b) => a + b)
  console.log(1 / ans)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 21320
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()
#define pb push_back

typedef long long ll;
const int inf = 1e9+7;
const ll infll = 1 << 60LL;
const ll mod = 1e9 + 7;
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

// 型による変数のオーバーフローに気をつけろ！！
// 悩んだら図やグラフを書け！！悩む前から書け！！

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

	int n;
	cin >> n;

	vector<char> s;

	//cout << 3 % (-2) << endl;
	if (n == 0) s.push_back('0');
	while (n != 0) {
		if(n % 2 == 1 || n % 2 == -1){ // 奇数ってこと？
			s.push_back('1');
			n--;
		}
		else {
			s.push_back('0');
		}
		n /= -2;
	}

	//cout << ((5) & 1) << endl;
	reverse(allof(s));
	rep(i,s.size()) cout << s[i];

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<map>
#include<numeric>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<stack>
#include<sstream>
#include<complex>

#define pb push_back
#define clr clear()
#define sz size()
#define fs first
#define sc second

#define rep(i,a) for(int i=0;i<(int)(a);i++)
#define rrep(i,a) for(int i=(int)(a)−1;i>=0;i−−)
#define all(a) (a).begin(),(a).end()
#define EQ(a,b) (abs((a)−(b)) < EPS)
#define INIT(a) memset(a,0,sizeof(a))

using namespace std;
typedef double D;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const D EPS = 1e-8;
const int INF = 1e8;
const D PI = acos(-1);

struct edge{
  int to,cost;
  bool operator<(const edge x)const{return cost>x.cost; }
};
int v; //頂点数
int d[20]; //s から i への最短路
vector<edge> G[20]; //ク&#12441;ラフの隣接リスト表現

void AddEdge(int s,int g,int p){
  G[s].pb((edge){g,p});
}


void BellmanFord(int s){
  fill(d,d+v,INF);
  d[s] = 0;
  for(;;){
    bool f = false; rep(i,v)rep(j,G[i].sz){
      edge e = G[i][j];
      if(d[i]<INF && d[e.to] > d[i] + e.cost){
	d[e.to] = d[i] + e.cost;
	f = true;
      }
    }
    if(!f)break;
  }
}

int n;
int a,b,c;

int main(){
  while(cin >> n,n){
    rep(i,20){
      G[i].clear();
    }

    v = 0;
    rep(i,n){
      cin >> a >> b >> c;
      v = max(v,max(a,b));
      AddEdge(a,b,c);
      AddEdge(b,a,c);
    }
    v++;

    int res = -1, dis = INF;
    rep(i,v){
      int tmp = 0;
      BellmanFord(i);
      rep(j,v)tmp += d[j];
      if(dis > tmp){
	dis = tmp; res = i;
      }
    }
    cout << res << " " << dis <<  endl;
  }
    
}

Measured memory_bytes: 1216
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn=1e5+10;
typedef pair<int,int> pii;
#define x first
#define y second
#define mp make_pair
#define pb push_back

int r,c,x1[maxn],y1[maxn],x2[maxn],y2[maxn];
int n;
vector<pii> s;
stack<int> p;

bool judge(int p)
{
	if (x1[p]!=0 && x1[p]!=r && y1[p]!=0 && y1[p]!=c) return false;
	if (x2[p]!=0 && x2[p]!=r && y2[p]!=0 && y2[p]!=c) return false;
	return true;
}

void ins(int x,int y,int p)
{
	if (y==0) s.pb(mp(x,p));
	else if (x==r) s.pb(mp(r+y,p));
	else if (y==c) s.pb(mp(2*r+c-x,p));
	else s.pb(mp(2*r+2*c-y,p));
}

int main()
{
	scanf("%d%d%d",&r,&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
	
	for(int i=1;i<=n;i++)
		if (judge(i))
		{
			ins(x1[i],y1[i],i);
			ins(x2[i],y2[i],i);
		}
	
	sort(s.begin(),s.end());
	for(int i=0;i<s.size();i++)
	{
		if (p.size() && s[i].y==p.top()) p.pop();
		else p.push(s[i].y);
	}
	
	if (p.size()) printf("NO\n");
	else printf("YES\n");
	return 0;
}

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

using namespace std;

#define foru(i, l, r) for (register int i = l; i <= r; i++)
#define ford(i, r, l) for (register int i = r; i >= l; i--)

int A, B, C, Ans;

int main() {
  scanf("%d%d%d", &A, &B, &C);
  if (B >= C) return printf("%d\n", B + C), 0;
  Ans += B << 1, C -= B, B -= B;
  printf("%d\n", Ans + min(A + 1, C));
  return 0;
}


Measured memory_bytes: 256
N = int(input())
S = input()

w = [0]*N
for i in range(1,N):
    #リーダーがi番目にいると仮定
    #リーダーよりにwestにいる人が何人いるか
    if S[i-1] == 'E':
        w[i] = w[i-1]+1
    else:
        w[i] = w[i-1]

e = [0]*N
for i in reversed(range(N)):
    #リーダーがi番目にいると仮定
    #リーダーよりにwestにいる人が何人いるか
    if i==N-1:
        continue

    if S[i+1] == 'W':
        e[i] = e[i+1]+1
    else:
        e[i] = e[i+1]

ans = 1
for i in range(N):
    ans = max(ans, e[i] + w[i]+1) #自分を含める

print(N - ans) 



Measured memory_bytes: 17568
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-5;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
    ll n,k;cin>>n>>k;
    vector<ll> a(n);
    vector<ll> co(50);
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(ll j=0;j<=40;j++){
            if(a[i]&(1LL<<j)){
                co[j]++;
            }
        }
    }
    ll s=0;
    ll ans=0;
    for(ll i=40;i>=0;i--){
        if(s+(1LL<<i)>k){
            ans+=(1LL<<i)*co[i];
            continue;
        }
        if(co[i]<n-co[i]){
            s+=(1LL<<i);
            ans+=(1LL<<i)*(n-co[i]);
        }else{
            ans+=(1LL<<i)*co[i];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

void solve(){
    LL x, k, d;
    cin >> x >> k >> d;
    // jump k times, d steps each
    // we could either end up some where around 0
    if(x < 0) x = -x;
    if((x+d-1)/d > k){
        printf("%lld",x-d*k); return ;
    }
    LL jj = x/d;
    k -= jj;
    x -= jj*d;
    if(k&1) printf("%lld",abs(x-d));
    else printf("%lld",x);
}

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

Measured memory_bytes: 3748
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;

int main(){
	mp::cpp_int n;
	cin >> n;
	mp::cpp_int res = 0;

	if (n==1) {
		cout << 0;
		return 0;
	}
	res = n * (n-1) / 2;
	cout << res;

	return 0;
}

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

using namespace std;

int main() {
  int n;
  cin>>n;
  long long int ans=0;
  for(int i=1; i<=n-1; i++)
  {
    int x = n-i, factors=0;
    for(int j=1; j<=sqrt(x); j++)
      if(x%j==0)
        factors++;
    long double sr = sqrt(x);
    if(sr - floor(sr)==0)
      ans += (factors-1)*2 + 1;
    else
      ans += factors*2;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3676
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
import math

#inf = 10**17
#mod = 10**9 + 7

n = int(input())
a = list(map(int, input().split()))
a.sort()
res = 0
for i in range(n, 3*n, 2):
    res += a[i]
print(res)

Measured memory_bytes: 37468
//From Naruto to Hokage
//#include <RJ>
#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=2005;
int expo(int base,int exponent,int mod){
    int ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
void solve(){
    ll fact[N];
    ll inv[N];
    fact[0]=1;
    inv[0]=(expo(1,hell-2,hell)+hell)%hell;
    rep(i,1,N-1){
        fact[i]=(fact[i-1]*i)%hell;
        inv[i]=(expo(fact[i],hell-2,hell)+hell)%hell;
    }
    ll n,k;
    cin>>n>>k;
    rep(i,1,k){
        ll ans=0;
        if(n-k+1-i>=0){ans=(fact[n-k+1]*((inv[n-k+1-i]*inv[i])%hell))%hell;
        ans=(ans*((fact[k-1]*((inv[i-1]*inv[k-i])%hell))%hell))%hell;}
        cout<<ans<<endl;
    }

}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long X = sc.nextLong();

		int A = 0;
		int B = 0;
		for(int i=0; i<=1000; i++) {
			for(int j=-1000; j<=1000; j++) {
				long ans = (long)Math.pow(i, 5) - (long)Math.pow(j, 5);
				if(ans == X) {
					A = i;
					B = j;
					break;
				}
			}
		}

		System.out.println(A + " " + B);

	}


}

Measured memory_bytes: 38756
<?php
fscanf(STDIN, '%d', $q);
for ($i  = 0; $i < $q; $i++) {
    fscanf(STDIN, '%d %d', $l[], $r[]);
}
$max = max($r);

$is_prime = is_prime($max);

$s = array_fill(0, $max, 0);
for ($i = 1; $i <= $max; $i++) {
    if ($is_prime[$i] && $is_prime[($i + 1) / 2]) {
        $s[$i] = $s[$i - 1] + 1;
    } else {
        $s[$i] = $s[$i - 1];
    }
}

for ($i = 0; $i < $q; $i++) {
    echo ($s[$r[$i]] - $s[$l[$i] - 1]).PHP_EOL;
}

/**
 * エラトステネスのふるい
 * $maxまでの整数が素数かどうかboolを格納した配列を返す
 */
function is_prime($max) {
    $arr = array_fill(0, $max + 1, true);
    $arr[0]  = $arr[1] = false;
    $rmax = floor(sqrt($max));
    for ($i = 2; $i <= $rmax; $i++) {
        for ($j = 2 * $i; $j <= $max; $j += $i) {
            $arr[$j] = false;
        }
    }
    return $arr;
}

Measured memory_bytes: 24692
//R<3S
#include <bits/stdc++.h>
#define hell 1000000007
#define PI 3.14159265358979323844
#define mp make_pair
#define pb push_back
#define fi first 
#define se second
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))  
#define REVERSE(v) reverse(ALL(v))
#define endl "\n"
#define vecmax(v) max_element(all(v))
#define vecmin(v) min_element(all(v))
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(x) for(auto i : x)
#define sz(a) (int)a.size()
#define sl(a) (int)a.length()
#define int long long
#define ld long double 
#define pii std::pair<int, int> 
#define pll std::pair<ll, ll>  
#define vi vector<int>  
#define vl vector<ll>
#define vvi vector<vi > 
#define vii vector<pii >
#define mii map<int,int>
#define mll map<ll,ll>


using namespace std;

void solve()
  {
	int n,w;
	cin>>n>>w;
	int wt[n],val[n];
	rep(i,n)cin>>wt[i]>>val[i];
	int dp[w+1];
	memset(dp,0,sizeof dp);
	
	rep(i,n)
	{
		repD(j,w,wt[i])
		{
			dp[j]=max(dp[j],dp[j-wt[i]]+val[i]);
		}
	}
	long long best = 0;
	for(int i = 0;i<=w;i++) best = max(best,dp[i]);
	cout << best << endl;
	
	


  }



signed main()
{
   std::ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int t;
   t=1;
   //cin>>t;
   while(t--)
    {
        solve();
    }


   return 0;
}


Measured memory_bytes: 4432
// Problem : A - ><
// Contest : AtCoder - AtCoder Grand Contest 040
// URL : https://atcoder.jp/contests/agc040/tasks/agc040_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
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;
 
#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,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define bug(x) cout<<#x<<"="<<x<<endl; 
#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()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; //check the limits, dummy
 
int main() 
{
	// && has higher precedence than ||
	ios_base::sync_with_stdio(0); cin.tie(0);    
	string str;
	cin>>str;
	int N=sz(str);
	vi ans(N+1,-1);
	vi nodes;
	if(str[0]=='<')nodes.pb(0),ans[0]=0;
	F0R(x,N)
	{
		if(str[x]=='>')
			break;
		ans[x+1]=ans[x]+1;
	}
	if(str.back()=='>')nodes.pb(N-1),ans.back()=0;
	F0Rd(x,N)
	{
		if(str[x]=='<')
			break;
		ans[x]=max(1+ans[x+1],ans[x]);
	}
	F0R(x,N-1)
	{
		if(str[x]=='>' && str[x+1]=='<')
		{
			ans[x+1]=0;
			FOR(y,x+1,N)
			{
				if(str[y]=='>')
					break;
				ans[y+1]=max(ans[y+1],ans[y]+1);
			}
			FORd(y,x+1,0)
			{
				if(str[y]=='<')
					break;
				ans[y]=max(1+ans[y+1],ans[y]);
			}
		}
	}
	ll sum=0;
	F0R(x,N+1)
		sum+=ans[x];
	cout<<sum<<nl;
		// cout<<ans[x]<<' ';
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 5868
#include <stdio.h>

int main(){
  int n, k, i;
  long long int x[100005], check, ans=-1;
  scanf("%d %d",&n, &k);
  for(i=0;i<n;i++) scanf("%lld",&x[i]);
  if(x[0]>=0) ans=x[k-1];
  else if(x[n-1]<=0) ans=abs(x[n-k]);
  else{
    for(i=0;i<n-k+1;i++){
      if(x[i+k-1]>=0){
        if(abs(x[i])<abs(x[i+k-1])) check=2*abs(x[i])+abs(x[i+k-1]);
        else check=abs(x[i])+2*abs(x[i+k-1]);
        if(check < ans || ans==-1) ans = check;
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];

  Int ans=1e18;
  auto calc=
    [&](Int x)->Int{
      Int res=0;
      for(Int i=0;i<n;i++)
	res+=abs(a[i]-(x+i));
      chmin(ans,res);
      return res;
    };

  Int l=-1e10,r=1e10;
  while(l+1<r){
    Int m=(l+r)/2;
    if(calc(m)<calc(m+1)) r=m;
    else l=m;
  }
  for(Int i=-10;i<10;i++) calc(l+i);
  for(Int i=-10;i<10;i++) calc(r+i);
  cout<<ans<<endl;
  return 0;
}


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

int main() {
  int n,k;
  cin >> n >> k;
  
  int current = 1;
  
  for(int i=0; i<n; i++) {
    int a = current * 2;
    int b = current + k;
    current = a > b ? b : a;
  }
  
  cout << current << endl;
  
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
      int ave;
      int n = 0;
      int i;
      while(true){
        n = sc.nextInt();
        if(n == 0){
          break;
        } 
      int data[] = new int [n];
      ave = 0;
      int most = 0,least = 1000;
      for(i=0;i<n;i++){
        data[i] = sc.nextInt();
        if(most <= data[i]) {
          most = data[i];
        }
        if(data[i] <= least) {
          least = data[i];
          
      }
      
      ave += data[i];
    }

      ave = (ave-(most+least))/(n-2);
      
      System.out.println(ave);
    }
    }
  }


Measured memory_bytes: 29168
#include<stdio.h>
int main(void)
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if ((a == b && a != c) || (a == c && a != b) || (b == c && b != a))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}





Measured memory_bytes: 128
while True:
    a, op, b = input().split()
    A = int(a)
    B = int(b)
    if op == '+':
        print(A+B)
    elif op == '-':
        print(A-B)
    elif op == '*':
        print(A*B)
    elif op == '/':
        print(A//B)
    elif op == '?':
        quit()


Measured memory_bytes: 5596
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include<set>


#define rep(i,p,q) for(ll i = p;i < q;++i)
#define ll long long

using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll npk(ll n, ll k) {
	ll ret = 1;
	if (n < k || n < 0)return 0;
	rep(i, 0, k) {
		ret *= (n - i);
		ret %= MOD;
	}
	if (ret < 0) ret = 0;
	return ret;
}

//135 C
int main(void) {
	ll n;
	cin >> n;
	vector<ll> a = vector<ll>(n+1);
	vector<ll> b = vector<ll>(n);
	rep(i, 0, n+1)cin >> a[i];
	rep(i, 0, n)cin >> b[i];
	ll ans = 0;
	rep(i, 0, n) {
		if (a[i] >= b[i]) {
			ans += b[i];
		}
		else {
			ans += a[i];
			b[i] -= a[i];
			if (i < n) {
				if (a[i+1] >= b[i]) {
					ans += b[i];
					a[i + 1] -= b[i];
				}
				else {
					ans += a[i + 1];
					a[i + 1] = 0;
				}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+5;
typedef long long ll;
char S[N],T[N];
int n;
int s,t,q[N];
int main()
{
    scanf("%d",&n);
    scanf("%s",S+1);
    scanf("%s",T+1);
    if(strcmp(S+1,T+1)==0){
        puts("0");
        return 0;
    }
    s=1,t=0;
    int p=n;
    int ans=0;
    for(int i=n;i>=1;i--){
        if(T[i]==T[i-1])
            continue;
        p=min(p,i);
        while(p&&T[i]!=S[p])
            p--;
        if(!p){
            puts("-1");
            return 0;
        }
        while(s<=t&&q[s]-(t-s+1)+1>i)
            s++;
        q[++t]=p;
        if(i!=p)
            ans=max(ans,t-s+1);
    }
    printf("%d\n",ans+1);
}


Measured memory_bytes: 6016
//#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
static constexpr double PI = 3.1415926535897932;

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;

void yes(bool c) { puts(c ? "yes" : "no"); }
void Yes(bool c) { puts(c ? "Yes" : "No"); }
void YES(bool c) { puts(c ? "YES" : "NO"); }
void pos(bool c) { puts(c ? "possible" : "impossible"); }
void Pos(bool c) { puts(c ? "Possible" : "Impossible"); }
void POS(bool c) { puts(c ? "POSSIBLE" : "IMPOSSIBLE"); }
template<class T>bool bmaxi(T&a, const T&b) { if (b<a)return 0;a = b;return 1; }
template<class T>bool bmini(T&a, const T&b) { if (a<b)return 0;a = b;return 1; }
template<class T>bool nmaxi(T&a, const T&b) { if (a<b) { a = b;return 1; }return 0; }
template<class T>bool nmini(T&a, const T&b) { if (b<a) { a = b;return 1; }return 0; }
template<typename T>auto scan(T&d)->typename std::enable_if<std::is_signed<T>::value>::type {
	d = 0;int c = fgetc(stdin);bool f = 0;while (c<'0' || '9'<c) { if (c == '-')f = 1;c = fgetc(stdin); }
	while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }if (f)d = -d;
}
template<typename T>auto scan(T&d)->typename std::enable_if<!std::is_signed<T>::value>::type {
	d = 0;int c = fgetc(stdin);while (c<'0' || '9'<c)c = fgetc(stdin);
	while ('0' <= c&&c <= '9') { d = d * 10 + c - '0';c = fgetc(stdin); }
}
template<>void scan(double&d) { scanf("%lf", &d); }
template<>void scan(std::string&d) {
	d.clear();int c = fgetc(stdin);
	while (c <'a' || 'z'<c)c = fgetc(stdin);while ('a' <= c&&c <= 'z') { d.push_back(c);c = fgetc(stdin); }
}
template<typename F, typename...R>void scan(F&f, R&...r) { scan(f);scan(r...); }
template<typename T>T input() { T d;scan(d);return d; }

template<typename T> 
auto print(T d)->typename std::enable_if<std::is_signed<T>::value>::type {
	static int c[20];
	std::uint_fast32_t i = 0;bool f=0;
	if (d < 0) {
		f = 1;d = -d;
	}
	while (d) { c[i++] = d % 10;d /= 10; }
	if (!i)c[i++] = 0;
	if (f) fputc(stdout, '-');
	while (i--) { fputc(c[i]+'0',stdout); }
}
template<typename T>
auto print(T d)->typename std::enable_if<!std::is_signed<T>::value>::type {
	static int c[20];
	std::uint_fast32_t i = 0;
	while (d) { c[i++] = d % 10;d /= 10; }
	if (!i)c[i++] = 0;
	while (i--) { fputc(c[i]+'0', stdout); }
}


int main(void) {
	print(input<uint32>() / 3);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll mod = 1e9 + 7;
#define endl '\n'
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
 
  ll X,K,D;
  cin >> X >> K >> D;
  if (X < 0) X = -X;
  if (K >= INT64_MAX/D) {
  } else {
    if (X-K*D >= 0) {
      cout << X-K*D << endl;
      return 0;
    }
  }
  K -= X/D;
  X %= D;
  if (K&1) {
    cout << llabs(X-D) << endl;
  } else {
    cout << X << endl;
  }
}


Measured memory_bytes: 3656
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int*a=new int[n+1];
    int*b=new int[n+1];
    int*c=new int[n];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n-1;i++) cin>>c[i];
    a[0]=-1;
    unsigned int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]-a[i-1]==1)ans+=c[a[i-1]];
        ans+=b[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256